Page MenuHome

C++ data structures in BLI
AbandonedPublic

Authored by Jacques Lucke (JacquesLucke) on May 28 2019, 4:00 PM.

Details

Summary

This patch introduces a new BLI C++ namespace.

It contains some core data structures that can be used in
many places. I developed those as part of the functions
branch, but it makes sense to commit them separately.
I'm currently not aware of any bugs and most methods
have unit tests already.

The patch contains two kinds of structures:
Containers and references to containers.

Containers

All containers have built-in small-object-optimization.
So, when they only contain very few elements, they do
not do a memory allocation. This is why the names
have the "Small" prefix (the same name is used in llvm).

The following types are included:

  • SmallVector<typename T, uint N>
  • SmallMap<typename K, typename V, uint N>
  • SmallSet<typename T, uint N>
  • SmallSetVector<typename T, uint N>
  • SmallStack<typenameT, uint N>

References to Containers

Many functions just need an array of data as input and
don't care what kind of data structure owns that array.
For example the array could be owned by std::vector,
BLI::SmallVector, std::initializer_list, ...

There are multiple solutions to allow callers to pass
any of these containers into a function:

  • The function could be implemented multiple times.
  • The function could have a template argument.
  • The input arguments have to be converted to the required container type.

All of these solutions have quite big drawbacks when it
comes to code complexity and maintainability.
A better solution is use the provided ArrayRef<T> as argument.
It contains just a pointer and a size, but does not own the
underlying data itself.

For same issues exists for strings. They are mostly stored in either
a char * or in std::string. We want functions to accept both
types as inputs, without doing potentially costly conversions.
Therefore, there is also a StringRef and StringRefNull type.
The difference between the two is that the latter guarantees that
the string is null-terminated.

Review

We don't need to merge this before Blender 2.80, although it
probably would not harm us since the code is not used in master
at all.

I'm just adding a bunch of reviewers here, because (if they
are accepted) the data structures will affect everyone in the future.

Diff Detail

Repository
rB Blender
Branch
cpp-core-data-structures (branched from master)
Build Status
Buildable 3755
Build 3755: arc lint + arc unit

Event Timeline

I'll submit this for review in smaller patches.
First one: D5592: Blenlib: New ArrayRef data structure.