BLI: various data structure improvements

* Rename template parameter N to InlineBufferCapacity
* Expose InlineBufferCapacity parameter for Set and Map
* Add some comments
* Fixed an error that I introduced recently

source/blender/blenlib/BLI_array.hh

@@ -31,12 +31,13 @@
 
 namespace BLI {
 
-template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Array {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Array {
  private:
   T *m_data;
   uint m_size;
   Allocator m_allocator;
-  AlignedBuffer<sizeof(T) * N, alignof(T)> m_inline_storage;
+  AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage;
 
  public:
   Array()
@@ -204,7 +205,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ar
  private:
   T *get_buffer_for_size(uint size)
   {
-    if (size <= N) {
+    if (size <= InlineBufferCapacity) {
       return this->inline_storage();
     }
     else {

source/blender/blenlib/BLI_map.hh

@@ -53,7 +53,11 @@ namespace BLI {
 
 // clang-format on
 
-template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator> class Map {
+template<typename KeyT,
+         typename ValueT,
+         uint32_t InlineBufferCapacity = 4,
+         typename Allocator = GuardedAllocator>
+class Map {
  private:
   static constexpr uint OFFSET_MASK = 3;
   static constexpr uint OFFSET_SHIFT = 2;
@@ -65,8 +69,8 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     static constexpr uint8_t IS_DUMMY = 2;
 
     uint8_t m_status[4];
-    char m_keys[4 * sizeof(KeyT)];
-    char m_values[4 * sizeof(ValueT)];
+    AlignedBuffer<4 * sizeof(KeyT), alignof(KeyT)> m_keys_buffer;
+    AlignedBuffer<4 * sizeof(ValueT), alignof(ValueT)> m_values_buffer;
 
    public:
     static constexpr uint slots_per_item = 4;
@@ -134,12 +138,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
 
     KeyT *key(uint offset) const
     {
-      return (KeyT *)(m_keys + offset * sizeof(KeyT));
+      return (KeyT *)m_keys_buffer.ptr() + offset;
     }
 
     ValueT *value(uint offset) const
     {
-      return (ValueT *)(m_values + offset * sizeof(ValueT));
+      return (ValueT *)m_values_buffer.ptr() + offset;
     }
 
     template<typename ForwardKeyT, typename ForwardValueT>
@@ -167,7 +171,7 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     }
   };
 
-  using ArrayType = OpenAddressingArray<Item, 1, Allocator>;
+  using ArrayType = OpenAddressingArray<Item, InlineBufferCapacity, Allocator>;
   ArrayType m_array;
 
  public:
@@ -351,6 +355,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     ITER_SLOTS_END(offset);
   }
 
+  ValueT *lookup_ptr(const KeyT &key)
+  {
+    const Map *const_this = this;
+    return const_cast<ValueT *>(const_this->lookup_ptr(key));
+  }
+
   /**
    * Lookup the value that corresponds to the key.
    * Asserts when the key does not exist.
@@ -362,12 +372,6 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     return *ptr;
   }
 
-  ValueT *lookup_ptr(const KeyT &key)
-  {
-    const Map *const_this = this;
-    return const_cast<ValueT *>(const_this->lookup_ptr(key));
-  }
-
   ValueT &lookup(const KeyT &key)
   {
     const Map *const_this = this;
@@ -413,6 +417,9 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     return m_array.slots_set();
   }
 
+  /**
+   * Calls the given function for each key-value-pair.
+   */
   template<typename FuncT> void foreach_item(const FuncT &func) const
   {
     for (const Item &item : m_array) {

source/blender/blenlib/BLI_open_addressing.hh

@@ -40,15 +40,76 @@
 
 namespace BLI {
 
-template<typename Item, uint32_t ItemsInSmallStorage = 1, typename Allocator = GuardedAllocator>
+/** \name Constexpr utility functions.
+ * \{ */
+
+inline constexpr int is_power_of_2_i_constexpr(int n)
+{
+  return (n & (n - 1)) == 0;
+}
+
+inline constexpr uint32_t log2_floor_u_constexpr(uint32_t x)
+{
+  return x <= 1 ? 0 : 1 + log2_floor_u_constexpr(x >> 1);
+}
+
+inline constexpr uint32_t log2_ceil_u_constexpr(uint32_t x)
+{
+  return (is_power_of_2_i_constexpr((int)x)) ? log2_floor_u_constexpr(x) :
+                                               log2_floor_u_constexpr(x) + 1;
+}
+
+template<typename IntT> inline constexpr IntT ceil_division(IntT x, IntT y)
+{
+  BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
+  return x / y + ((x % y) != 0);
+}
+
+template<typename IntT> inline constexpr IntT floor_division(IntT x, IntT y)
+{
+  BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
+  return x / y;
+}
+
+inline constexpr uint8_t compute_item_exponent(uint32_t min_usable_slots,
+                                               uint32_t slots_per_item,
+                                               uint32_t max_load_factor_numerator,
+                                               uint32_t max_load_factor_denominator)
+{
+  // uint64_t min_total_slots = ceil_division((uint64_t)min_usable_slots *
+  //                                              (uint64_t)max_load_factor_denominator,
+  //                                          (uint64_t)max_load_factor_numerator);
+  // uint32_t min_total_items = (uint32_t)ceil_division(min_total_slots, (uint64_t)slots_per_item);
+  // uint8_t item_exponent = (uint8_t)log2_ceil_u_constexpr(min_total_items);
+  // return item_exponent;
+
+  return (uint8_t)log2_ceil_u_constexpr((uint32_t)ceil_division(
+      ceil_division((uint64_t)min_usable_slots * (uint64_t)max_load_factor_denominator,
+                    (uint64_t)max_load_factor_numerator),
+      (uint64_t)slots_per_item));
+}
+
+/** \} */
+
+template<typename Item,
+         uint32_t MinUsableSlotsInSmallStorage = 1,
+         typename Allocator = GuardedAllocator>
 class OpenAddressingArray {
  private:
-  static constexpr uint32_t slots_per_item = Item::slots_per_item;
-  static constexpr float max_load_factor = 0.5f;
+  static constexpr uint32_t s_max_load_factor_numerator = 1;
+  static constexpr uint32_t s_max_load_factor_denominator = 2;
+  static constexpr uint32_t s_slots_per_item = Item::slots_per_item;
+
+  static constexpr uint8_t s_small_storage_item_exponent = compute_item_exponent(
+      MinUsableSlotsInSmallStorage,
+      s_slots_per_item,
+      s_max_load_factor_numerator,
+      s_max_load_factor_denominator);
+  static constexpr uint32_t s_items_in_small_storage = 1u << s_small_storage_item_exponent;
 
   /* Invariants:
    *   2^m_item_exponent = m_item_amount
-   *   m_item_amount * slots_per_item = m_slots_total
+   *   m_item_amount * s_slots_per_item = m_slots_total
    *   m_slot_mask = m_slots_total - 1
    *   m_slots_set_or_dummy < m_slots_total
    */
@@ -70,20 +131,23 @@ class OpenAddressingArray {
   /* Can be used to map a hash value into the range of valid slot indices. */
   uint32_t m_slot_mask;
   Allocator m_allocator;
-  AlignedBuffer<(uint)sizeof(Item) * ItemsInSmallStorage, (uint)alignof(Item)> m_local_storage;
+  AlignedBuffer<(uint)sizeof(Item) * s_items_in_small_storage, (uint)alignof(Item)>
+      m_local_storage;
 
  public:
-  explicit OpenAddressingArray(uint8_t item_exponent = 0)
+  explicit OpenAddressingArray(uint8_t item_exponent = s_small_storage_item_exponent)
   {
-    m_slots_total = ((uint32_t)1 << item_exponent) * slots_per_item;
+    m_item_exponent = item_exponent;
+    m_item_amount = 1u << item_exponent;
+    m_slots_total = m_item_amount * s_slots_per_item;
+    m_slot_mask = m_slots_total - 1;
     m_slots_set_or_dummy = 0;
     m_slots_dummy = 0;
-    m_slots_usable = (uint32_t)((float)m_slots_total * max_load_factor);
-    m_slot_mask = m_slots_total - 1;
-    m_item_amount = m_slots_total / slots_per_item;
-    m_item_exponent = item_exponent;
+    m_slots_usable = (uint32_t)floor_division((uint64_t)m_slots_total *
+                                                  (uint64_t)s_max_load_factor_numerator,
+                                              (uint64_t)s_max_load_factor_denominator);
 
-    if (m_item_amount <= ItemsInSmallStorage) {
+    if (m_item_amount <= s_items_in_small_storage) {
       m_items = this->small_storage();
     }
     else {
@@ -118,7 +182,7 @@ class OpenAddressingArray {
     m_item_amount = other.m_item_amount;
     m_item_exponent = other.m_item_exponent;
 
-    if (m_item_amount <= ItemsInSmallStorage) {
+    if (m_item_amount <= s_items_in_small_storage) {
       m_items = this->small_storage();
     }
     else {
@@ -180,9 +244,10 @@ class OpenAddressingArray {
    * empty. */
   OpenAddressingArray init_reserved(uint32_t min_usable_slots) const
   {
-    float min_total_slots = (float)min_usable_slots / max_load_factor;
-    uint32_t min_total_items = (uint32_t)std::ceil(min_total_slots / (float)slots_per_item);
-    uint8_t item_exponent = (uint8_t)log2_ceil_u(min_total_items);
+    uint8_t item_exponent = compute_item_exponent(min_usable_slots,
+                                                  s_slots_per_item,
+                                                  s_max_load_factor_numerator,
+                                                  s_max_load_factor_denominator);
     OpenAddressingArray grown(item_exponent);
     grown.m_slots_set_or_dummy = this->slots_set();
     return grown;

source/blender/blenlib/BLI_set.hh

@@ -50,7 +50,8 @@ namespace BLI {
 
 // clang-format on
 
-template<typename T, typename Allocator = GuardedAllocator> class Set {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Set {
  private:
   static constexpr uint OFFSET_MASK = 3;
   static constexpr uint OFFSET_SHIFT = 2;
@@ -62,7 +63,7 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
     static constexpr uint8_t IS_DUMMY = 2;
 
     uint8_t m_status[4];
-    char m_values[4 * sizeof(T)];
+    AlignedBuffer<4 * sizeof(T), alignof(T)> m_buffer;
 
    public:
     static constexpr uint slots_per_item = 4;
@@ -114,7 +115,7 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
 
     T *value(uint offset) const
     {
-      return (T *)(m_values + offset * sizeof(T));
+      return (T *)m_buffer.ptr() + offset;
     }
 
     template<typename ForwardT> void store(uint offset, ForwardT &&value)
@@ -153,8 +154,8 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
     }
   };
 
-  using ArrayType = OpenAddressingArray<Item, 1, Allocator>;
-  ArrayType m_array = OpenAddressingArray<Item>();
+  using ArrayType = OpenAddressingArray<Item, InlineBufferCapacity, Allocator>;
+  ArrayType m_array;
 
  public:
   Set() = default;
@@ -202,6 +203,7 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
 
   /**
    * Add a new value to the set if it does not exist yet.
+   * Returns true of the value has been newly added.
    */
   bool add(const T &value)
   {
@@ -266,16 +268,9 @@ template<typename T, typename Allocator = GuardedAllocator> class Set {
     ITER_SLOTS_END(offset);
   }
 
-  Vector<T> to_small_vector() const
-  {
-    Vector<T> vector;
-    vector.reserve(this->size());
-    for (const T &value : *this) {
-      vector.append(value);
-    }
-    return vector;
-  }
-
+  /**
+   * Get the amount of values stored in the set.
+   */
   uint32_t size() const
   {
     return m_array.slots_set();

source/blender/blenlib/BLI_stack.hh

@@ -27,9 +27,10 @@
 
 namespace BLI {
 
-template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Stack {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Stack {
  private:
-  Vector<T, N, Allocator> m_elements;
+  Vector<T, InlineBufferCapacity, Allocator> m_elements;
 
  public:
   Stack() = default;

source/blender/blenlib/BLI_vector.hh

@@ -43,13 +43,14 @@
 
 namespace BLI {
 
-template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Vector {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Vector {
  private:
   T *m_begin;
   T *m_end;
   T *m_capacity_end;
   Allocator m_allocator;
-  AlignedBuffer<(uint)sizeof(T) * N, (uint)alignof(T)> m_small_buffer;
+  AlignedBuffer<(uint)sizeof(T) * InlineBufferCapacity, (uint)alignof(T)> m_small_buffer;
 
 #ifndef NDEBUG
   /* Storing size in debug builds, because it makes debugging much easier sometimes. */
@@ -70,7 +71,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
   {
     m_begin = this->small_buffer();
     m_end = m_begin;
-    m_capacity_end = m_begin + N;
+    m_capacity_end = m_begin + InlineBufferCapacity;
     UPDATE_VECTOR_SIZE(this);
   }
 
@@ -140,7 +141,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
   /**
    * Create a copy of another vector.
    * The other vector will not be changed.
-   * If the other vector has less than N elements, no allocation will be made.
+   * If the other vector has less than InlineBufferCapacity elements, no allocation will be made.
    */
   Vector(const Vector &other) : m_allocator(other.m_allocator)
   {
@@ -164,11 +165,11 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     uint size = other.size();
 
     if (other.is_small()) {
-      if (size <= N) {
+      if (size <= InlineBufferCapacity) {
         /* Copy between inline buffers. */
         m_begin = this->small_buffer();
         m_end = m_begin + size;
-        m_capacity_end = m_begin + N;
+        m_capacity_end = m_begin + InlineBufferCapacity;
         uninitialized_relocate_n(other.m_begin, size, m_begin);
       }
       else {
@@ -283,7 +284,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
 
     m_begin = this->small_buffer();
     m_end = m_begin;
-    m_capacity_end = m_begin + N;
+    m_capacity_end = m_begin + InlineBufferCapacity;
     UPDATE_VECTOR_SIZE(this);
   }
 
@@ -578,7 +579,8 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     std::cout << "Small Vector at " << (void *)this << ":" << std::endl;
     std::cout << "  Elements: " << this->size() << std::endl;
     std::cout << "  Capacity: " << (m_capacity_end - m_begin) << std::endl;
-    std::cout << "  Small Elements: " << N << "  Size on Stack: " << sizeof(*this) << std::endl;
+    std::cout << "  Small Elements: " << InlineBufferCapacity
+              << "  Size on Stack: " << sizeof(*this) << std::endl;
   }
 
  private:
@@ -634,9 +636,9 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     uint size = other.size();
     uint capacity = size;
 
-    if (size <= N) {
+    if (size <= InlineBufferCapacity) {
       m_begin = this->small_buffer();
-      capacity = N;
+      capacity = InlineBufferCapacity;
     }
     else {
       m_begin = (T *)m_allocator.allocate_aligned(
@@ -658,7 +660,8 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
  * Use when the vector is used in the local scope of a function. It has a larger inline storage by
  * default to make allocations less likely.
  */
-template<typename T, uint N = 20> using ScopedVector = Vector<T, N, GuardedAllocator>;
+template<typename T, uint InlineBufferCapacity = 20>
+using ScopedVector = Vector<T, InlineBufferCapacity, GuardedAllocator>;
 
 } /* namespace BLI */
 

source/blender/blenlib/BLI_vector_set.hh

@@ -150,7 +150,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
 
   ~VectorSet()
   {
-    destruct_n(m_elements, m_array.slots_usable());
+    destruct_n(m_elements, this->size());
     this->deallocate_elements_array(m_elements);
   }
 
@@ -242,7 +242,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
     BLI_assert(this->contains(value));
     ITER_SLOTS_BEGIN (value, m_array, , slot) {
       if (slot.has_value(value, m_elements)) {
-        uint old_index = m_array.slots_set() - 1;
+        uint old_index = this->size() - 1;
         uint new_index = slot.index();
 
         if (new_index < old_index) {
@@ -265,7 +265,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
   T pop()
   {
     BLI_assert(this->size() > 0);
-    uint index_to_pop = m_array.slots_usable() - 1;
+    uint index_to_pop = this->size() - 1;
     T value = std::move(m_elements[index_to_pop]);
     destruct(m_elements + index_to_pop);
 
@@ -324,12 +324,12 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
 
   const T *end() const
   {
-    return m_elements + m_array.slots_set();
+    return m_elements + this->size();
   }
 
   const T &operator[](uint index) const
   {
-    BLI_assert(index <= m_array.slots_set());
+    BLI_assert(index <= this->size());
     return m_elements[index];
   }
 
@@ -340,7 +340,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
 
   operator ArrayRef<T>() const
   {
-    return ArrayRef<T>(m_elements, m_array.slots_set());
+    return ArrayRef<T>(m_elements, this->size());
   }
 
   void print_stats() const
@@ -367,7 +367,7 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
 
   template<typename ForwardT> void add_new_in_slot(Slot &slot, ForwardT &&value)
   {
-    uint index = m_array.slots_set();
+    uint index = this->size();
     slot.set_index(index);
     new (m_elements + index) T(std::forward<ForwardT>(value));
     m_array.update__empty_to_set();

tests/gtests/blenlib/BLI_set_test.cc

@@ -155,16 +155,6 @@ TEST(set, AddMultipleNew)
   EXPECT_TRUE(a.contains(6));
 }
 
-TEST(set, ToSmallVector)
-{
-  IntSet a = {5, 2, 8};
-  BLI::Vector<int> vec = a.to_small_vector();
-  EXPECT_EQ(vec.size(), 3);
-  EXPECT_TRUE(vec.contains(5));
-  EXPECT_TRUE(vec.contains(2));
-  EXPECT_TRUE(vec.contains(8));
-}
-
 TEST(set, Iterator)
 {
   IntSet set = {1, 3, 2, 5, 4};