[Bf-blender-cvs] [f12b5445151] functions: new multi map implementation that can deal with non trivial types

Jacques Lucke noreply at git.blender.org
Thu Jan 2 16:37:54 CET 2020


Commit: f12b544515120af2b90829e9055960f205364c76
Author: Jacques Lucke
Date:   Thu Jan 2 14:06:21 2020 +0100
Branches: functions
https://developer.blender.org/rBf12b544515120af2b90829e9055960f205364c76

new multi map implementation that can deal with non trivial types

===================================================================

M	source/blender/blenlib/BLI_multi_map.h
M	tests/gtests/blenlib/CMakeLists.txt

===================================================================

diff --git a/source/blender/blenlib/BLI_multi_map.h b/source/blender/blenlib/BLI_multi_map.h
index cdf7e34990a..0b9c8c645e0 100644
--- a/source/blender/blenlib/BLI_multi_map.h
+++ b/source/blender/blenlib/BLI_multi_map.h
@@ -25,155 +25,201 @@
 #include "BLI_map.h"
 #include "BLI_array_ref.h"
 #include "BLI_vector.h"
+#include "BLI_monotonic_allocator.h"
 
 namespace BLI {
 
-template<typename K, typename V, uint N = 4> class MultiMap {
+template<typename KeyT, typename ValueT, uint N = 4> class MultiMap {
  private:
   struct Entry {
-    uint offset;
-    uint length;
-    uint capacity;
-
-    ArrayRef<V> get_slice(ArrayRef<V> array) const
-    {
-      return array.slice(offset, length);
-    }
+    ValueT *ptr = nullptr;
+    uint length = 0;
+    uint capacity = 0;
   };
 
-  Map<K, Entry> m_map;
-  Vector<V, N> m_elements;
+  MonotonicAllocator<sizeof(ValueT) * N> m_allocator;
+  Map<KeyT, Entry> m_map;
 
  public:
   MultiMap() = default;
 
-  uint key_amount() const
+  ~MultiMap()
   {
-    return m_map.size();
+    this->foreach_value([](ValueT &value) { value.~ValueT(); });
   }
 
-  uint value_amount(const K &key) const
+  MultiMap(const MultiMap &other)
   {
-    return this->lookup_default(key).size();
+    this->add_multiple(other);
   }
 
-  bool add(const K &key, const V &value)
+  MultiMap &operator=(const MultiMap &other)
   {
-    BLI_STATIC_ASSERT(std::is_trivially_destructible<V>::value, "");
-    bool newly_inserted = m_map.add_or_modify(
-        key,
-        /* Insert new key with value. */
-        [&](Entry *r_entry) {
-          UNUSED_VARS(key);
-          uint offset = m_elements.size();
-          m_elements.append(value);
-          *r_entry = {offset, 1, 1};
-          return true;
-        },
-        /* Append new value for existing key. */
-        [&](Entry *entry) {
-          if (entry->length < entry->capacity) {
-            m_elements[entry->offset + entry->length] = value;
-            entry->length += 1;
-          }
-          else {
-            uint new_offset = m_elements.size();
-            uint new_capacity = entry->capacity * 2;
-
-            m_elements.reserve(m_elements.size() + new_capacity);
-
-            /* Copy the existing elements to the end. */
-            ArrayRef<V> old_values = entry->get_slice(m_elements);
-            m_elements.extend_unchecked(old_values);
+    if (this == &other) {
+      return *this;
+    }
+    this->~MultiMap();
+    new (this) MultiMap(other);
+    return *this;
+  }
 
-            /* Insert the new value. */
-            m_elements.append_unchecked(value);
+  uint key_amount() const
+  {
+    return m_map.size();
+  }
 
-            /* Reserve the remaining capacity for this entry-> */
-            m_elements.increase_size_unchecked(entry->length - 1);
+  uint value_amount(const KeyT &key) const
+  {
+    return m_map.lookup_default(key, {}).length;
+  }
 
-            entry->offset = new_offset;
-            entry->length += 1;
-            entry->capacity = new_capacity;
-          }
-          return false;
-        });
-    return newly_inserted;
+  void add_new(const KeyT &key, const ValueT &value)
+  {
+    BLI_assert(!this->contains(key));
+    this->add(key, value);
   }
 
-  template<uint OtherN> void add_multiple(MultiMap<K, V, OtherN> &other)
+  void add_multiple_new(const KeyT &key, ArrayRef<ValueT> values)
   {
-    BLI_assert(this != &other);
-    other.foreach_item([&](const K &key, ArrayRef<V> values) { this->add_multiple(key, values); });
+    BLI_assert(!this->contains(key));
+    this->add_multiple(key, values);
   }
 
-  void add_multiple(const K &key, ArrayRef<V> values)
+  bool add(const KeyT &key, const ValueT &value)
   {
-    for (const V &value : values) {
-      this->add(key, value);
-    }
+    return this->add__impl(key, value);
+  }
+  bool add(const KeyT &key, ValueT &&value)
+  {
+    return this->add__impl(key, std::move(value));
+  }
+  bool add(KeyT &&key, const ValueT &value)
+  {
+    return this->add__impl(std::move(key), value);
+  }
+  bool add(KeyT &&key, ValueT &&value)
+  {
+    return this->add__impl(std::move(key), std::move(value));
   }
 
-  void add_new(const K &key, const V &value)
+  void add_multiple(const KeyT &key, ArrayRef<ValueT> values)
+  {
+    this->add_multiple__impl(key, values);
+  }
+  void add_multiple(const KeyT &&key, ArrayRef<ValueT> values)
   {
-    BLI_assert(!m_map.contains(key));
-    uint offset = m_elements.size();
-    m_elements.append(value);
-    m_map.add_new(key, {offset, 1, 1});
+    this->add_multiple__impl(std::move(key), values);
   }
 
-  void add_multiple_new(const K &key, ArrayRef<V> values)
+  template<uint OtherN> void add_multiple(const MultiMap<KeyT, ValueT, OtherN> &other)
   {
-    BLI_assert(!m_map.contains(key));
-    uint offset = m_elements.size();
-    m_elements.extend(values);
-    m_map.add_new(key, {offset, values.size(), values.size()});
+    BLI_assert(this != &other);
+    other.foreach_item(
+        [&](const KeyT &key, ArrayRef<ValueT> values) { this->add_multiple(key, values); });
   }
 
-  ArrayRef<V> lookup(const K &key) const
+  ArrayRef<ValueT> lookup(const KeyT &key) const
   {
-    BLI_assert(m_map.contains(key));
-    return this->lookup_default(key);
+    const Entry &entry = m_map.lookup(key);
+    return ArrayRef<ValueT>(entry.ptr, entry.length);
   }
 
-  ArrayRef<V> lookup_default(const K &key, ArrayRef<V> default_array = ArrayRef<V>()) const
+  ArrayRef<ValueT> lookup_default(const KeyT &key,
+                                  ArrayRef<ValueT> default_array = ArrayRef<ValueT>()) const
   {
     const Entry *entry = m_map.lookup_ptr(key);
     if (entry == nullptr) {
       return default_array;
     }
     else {
-      return entry->get_slice(m_elements);
+      return ArrayRef<ValueT>(entry->ptr, entry->length);
     }
   }
 
-  bool contains(const K &key) const
+  bool contains(const KeyT &key) const
   {
     return m_map.contains(key);
   }
 
-  typename Map<K, Entry>::KeyIterator keys() const
+  typename Map<KeyT, Entry>::KeyIterator keys() const
   {
     return m_map.keys();
   }
 
+  template<typename FuncT> void foreach_value(const FuncT &func) const
+  {
+    for (const Entry &entry : m_map.values()) {
+      for (const ValueT &value : ArrayRef<ValueT>(entry.ptr, entry.length)) {
+        func(value);
+      }
+    }
+  }
+
   template<typename FuncT> void foreach_value(const FuncT &func)
   {
     for (Entry &entry : m_map.values()) {
-      for (const V &value : entry.get_slice(m_elements)) {
+      for (ValueT &value : MutableArrayRef<ValueT>(entry.ptr, entry.length)) {
         func(value);
       }
     }
   }
 
-  template<typename FuncT> void foreach_item(const FuncT &func)
+  template<typename FuncT> void foreach_item(const FuncT &func) const
   {
     for (auto item : m_map.items()) {
-      const K &key = item.key;
-      ArrayRef<V> values = item.value.get_slice(m_elements);
+      const KeyT &key = item.key;
+      ArrayRef<ValueT> values{item.value.ptr, item.value.length};
       func(key, values);
     }
   }
+
+ private:
+  template<typename ForwardKeyT>
+  void add_multiple__impl(ForwardKeyT &&key, ArrayRef<ValueT> values)
+  {
+    for (const ValueT &value : values) {
+      this->add(key, value);
+    }
+  }
+
+  template<typename ForwardKeyT, typename ForwardValueT>
+  bool add__impl(ForwardKeyT &&key, ForwardValueT &&value)
+  {
+    bool newly_inserted = m_map.add_or_modify(
+        std::forward<ForwardKeyT>(key),
+        /* Insert new key with value. */
+        [&](Entry *r_entry) -> bool {
+          uint initial_capacity = 1;
+          ValueT *array = (ValueT *)m_allocator.allocate(sizeof(ValueT) * initial_capacity,
+                                                         alignof(ValueT));
+          new (array) ValueT(std::forward<ForwardValueT>(value));
+          r_entry->ptr = array;
+          r_entry->length = 1;
+          r_entry->capacity = initial_capacity;
+          return true;
+        },
+        /* Append new value for existing key. */
+        [&](Entry *entry) -> bool {
+          if (entry->length < entry->capacity) {
+            new (entry->ptr + entry->length) ValueT(std::forward<ForwardValueT>(value));
+            entry->length++;
+          }
+          else {
+            uint old_capacity = entry->capacity;
+            BLI_assert(old_capacity >= 1);
+            uint new_capacity = old_capacity * 2;
+            ValueT *new_array = (ValueT *)m_allocator.allocate(sizeof(ValueT) * new_capacity,
+                                                               alignof(ValueT));
+            uninitialized_relocate_n(entry->ptr, old_capacity, new_array);
+            new (new_array + entry->length) ValueT(std::forward<ForwardValueT>(value));
+            entry->ptr = new_array;
+            entry->length++;
+            entry->capacity = new_capacity;
+          }
+          return false;
+        });
+    return newly_inserted;
+  }
 };
 
 } /* namespace BLI */
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index 752a6601e98..37a3a86dc48 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -62,6 +62,7 @@ BLENDER_TEST(BLI_math_color "bf_blenlib")
 BLENDER_TEST(BLI_math_geom "bf_blenlib")
 BLENDER_TEST(BLI_memiter "bf_blenlib")
 BLENDER_TEST(BLI_monotonic_allocator "bf_blenlib")
+BLENDER_TEST(BLI_multi_map "bf_blenlib")
 BLENDER_TEST(BLI_multi_vector "bf_blenlib")
 BLENDER_TEST(BLI_optional "bf_blenlib")
 BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")



More information about the Bf-blender-cvs mailing list