[Bf-blender-cvs] [d14073a5fc8] functions: better multimap implementation for a specific use case

Jacques Lucke noreply at git.blender.org
Wed Jul 3 19:14:24 CEST 2019


Commit: d14073a5fc82b8301fd97c38efc88495f1f2e8a8
Author: Jacques Lucke
Date:   Wed Jul 3 18:42:29 2019 +0200
Branches: functions
https://developer.blender.org/rBd14073a5fc82b8301fd97c38efc88495f1f2e8a8

better multimap implementation for a specific use case

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

M	source/blender/blenkernel/BKE_node_tree.hpp
M	source/blender/blenlib/BLI_multimap.hpp
M	tests/gtests/blenlib/BLI_multimap_test.cc

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

diff --git a/source/blender/blenkernel/BKE_node_tree.hpp b/source/blender/blenkernel/BKE_node_tree.hpp
index 4f9432ff076..f57c9a166a5 100644
--- a/source/blender/blenkernel/BKE_node_tree.hpp
+++ b/source/blender/blenkernel/BKE_node_tree.hpp
@@ -13,10 +13,10 @@ namespace BKE {
 
 using BLI::ArrayRef;
 using BLI::ListBaseWrapper;
-using BLI::MultiMap;
 using BLI::SmallMap;
 using BLI::SmallVector;
 using BLI::StringRef;
+using BLI::ValueArrayMap;
 
 using bNodeList = ListBaseWrapper<struct bNode *, true>;
 using bLinkList = ListBaseWrapper<struct bNodeLink *, true>;
@@ -51,8 +51,8 @@ class NodeTreeQuery {
   SmallVector<bNode *> m_nodes;
   SmallVector<bNodeLink *> m_links;
   SmallMap<bNodeSocket *, bNode *> m_node_by_socket;
-  MultiMap<bNodeSocket *, bNodeSocket *> m_direct_links;
-  MultiMap<bNodeSocket *, bNodeSocket *> m_links_without_reroutes;
+  ValueArrayMap<bNodeSocket *, bNodeSocket *> m_direct_links;
+  ValueArrayMap<bNodeSocket *, bNodeSocket *> m_links_without_reroutes;
   SmallVector<SingleOriginLink> m_single_origin_links;
 };
 
diff --git a/source/blender/blenlib/BLI_multimap.hpp b/source/blender/blenlib/BLI_multimap.hpp
index a881c9f9c5e..660d21dd512 100644
--- a/source/blender/blenlib/BLI_multimap.hpp
+++ b/source/blender/blenlib/BLI_multimap.hpp
@@ -1,12 +1,9 @@
 #pragma once
 
-/* A map that allows storing multiple values per key.
+/* A multimap is a map that allows storing multiple values per key.
  *
- * Values per key are stored in an array without being
- * able to efficiently check if a specific value exists
- * for a key. A linear search through all values for
- * a key has to be performed. When the number of values
- * per key is expected to be small, this is still fast.
+ * The optimal data structure layout highly depends on the access pattern. For that reason, it can
+ * make sense to have multiple implementation for similar queries.
  */
 
 #include "BLI_small_map.hpp"
@@ -15,6 +12,114 @@
 
 namespace BLI {
 
+/**
+ * This stores an array per key. It should be used when the array per key changes rarely. All
+ * arrays are just concatenated with some space in between to allow for growing arrays.
+ * If an array is becomes too large, it is copied to the end, leaving a whole that will not be
+ * filled again.
+ */
+template<typename K, typename V, uint N = 4> class ValueArrayMap {
+ private:
+  struct Entry {
+    K key;
+    uint offset;
+    uint length;
+    uint capacity;
+
+    static const K &get_key(const Entry &entry)
+    {
+      BLI_STATIC_ASSERT(std::is_trivial<V>::value, "only works with trivial value types");
+      return entry.key;
+    }
+
+    ArrayRef<V> get_slice(ArrayRef<V> array)
+    {
+      return array.slice(offset, length);
+    }
+  };
+
+  SmallMap<K, Entry, N> m_map;
+  SmallVector<V, N> m_elements;
+
+ public:
+  ValueArrayMap() = default;
+
+  uint key_amount() const
+  {
+    return m_map.size();
+  }
+
+  bool add(const K &key, const V &value)
+  {
+    bool newly_inserted = m_map.insert_or_modify(
+        key,
+        /* Insert new key with value. */
+        [this, &key, &value]() -> Entry {
+          uint offset = m_elements.size();
+          m_elements.append(value);
+          return {key, offset, 1, 1};
+        },
+        /* Append new value for existing key. */
+        [this, &value](Entry &entry) {
+          if (entry.length < entry.capacity) {
+            m_elements[entry.offset + entry.length] = value;
+            entry.length += 1;
+          }
+          else {
+            uint new_offset = m_elements.size();
+
+            /* Copy the existing elements to the end. */
+            m_elements.extend(entry.get_slice(m_elements));
+            /* Insert the new value and reserve the capacity for this
+             * entry. */
+            m_elements.append_n_times(value, entry.length);
+
+            entry.offset = new_offset;
+            entry.length += 1;
+            entry.capacity *= 2;
+          }
+        });
+    return newly_inserted;
+  }
+
+  bool add_new(const K &key, const V &value)
+  {
+    BLI_assert(!m_map.contains(key));
+    uint offset = m_elements.size();
+    m_elements.append(value);
+    m_map.add_new(key, {key, offset, 1, 1});
+  }
+
+  void add_multiple_new(const K &key, ArrayRef<V> values)
+  {
+    for (const V &value : values) {
+      this->add(key, value);
+    }
+  }
+
+  ArrayRef<V> lookup(const K &key) const
+  {
+    BLI_assert(m_map.contains(key));
+    return this->lookup_default(key);
+  }
+
+  ArrayRef<V> lookup_default(const K &key, ArrayRef<V> default_array = ArrayRef<V>()) const
+  {
+    Entry *entry = m_map.lookup_ptr(key);
+    if (entry == nullptr) {
+      return default_array;
+    }
+    else {
+      return entry->get_slice(m_elements);
+    }
+  }
+
+  bool contains(const K &key) const
+  {
+    return m_map.contains(key);
+  }
+};
+
 template<typename K, typename V> class MultiMap {
  private:
   struct Entry {
diff --git a/tests/gtests/blenlib/BLI_multimap_test.cc b/tests/gtests/blenlib/BLI_multimap_test.cc
index 9208ebd058c..d54d13a4ba7 100644
--- a/tests/gtests/blenlib/BLI_multimap_test.cc
+++ b/tests/gtests/blenlib/BLI_multimap_test.cc
@@ -4,6 +4,59 @@
 using namespace BLI;
 
 using IntMap = MultiMap<int, int>;
+using IntArrayMap = ValueArrayMap<int, int>;
+
+TEST(value_array_map, DefaultConstructor)
+{
+  IntArrayMap map;
+  EXPECT_EQ(map.key_amount(), 0);
+}
+
+TEST(value_array_map, Add)
+{
+  IntArrayMap map;
+  EXPECT_FALSE(map.contains(4));
+  map.add(4, 6);
+  EXPECT_TRUE(map.contains(4));
+}
+
+TEST(value_array_map, AddMultipleTimes)
+{
+  IntArrayMap map;
+  EXPECT_FALSE(map.contains(3));
+  EXPECT_FALSE(map.contains(4));
+  EXPECT_FALSE(map.contains(5));
+  map.add(3, 10);
+  map.add(3, 11);
+  map.add(4, 10);
+  map.add(5, 10);
+  map.add(6, 10);
+  EXPECT_TRUE(map.contains(3));
+  EXPECT_TRUE(map.contains(4));
+  EXPECT_TRUE(map.contains(5));
+  EXPECT_EQ(map.key_amount(), 4);
+}
+
+TEST(value_array_map, AddMultipleNew)
+{
+  IntArrayMap map;
+  map.add_multiple_new(3, {5, 6, 7});
+  map.add_multiple_new(1, {7, 4, 2});
+  map.add_multiple_new(1, {3, 4});
+  EXPECT_EQ(map.key_amount(), 2);
+  EXPECT_EQ(map.lookup(1).size(), 5);
+  EXPECT_EQ(map.lookup(3).size(), 3);
+  EXPECT_EQ(map.lookup(1)[1], 4);
+  EXPECT_EQ(map.lookup(1)[3], 3);
+}
+
+TEST(value_array_map, LookupDefault)
+{
+  IntArrayMap map;
+  EXPECT_EQ(map.lookup_default(10).size(), 0);
+  map.add(10, 1);
+  EXPECT_EQ(map.lookup_default(10).size(), 1);
+}
 
 TEST(multimap, DefaultConstructor)
 {



More information about the Bf-blender-cvs mailing list