[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