[Bf-blender-cvs] [10437bba07d] functions: only use new multimap implementation
Jacques Lucke
noreply at git.blender.org
Wed Jul 3 19:14:29 CEST 2019
Commit: 10437bba07d2885a61fe6723bf791a9c9bf93b17
Author: Jacques Lucke
Date: Wed Jul 3 19:01:14 2019 +0200
Branches: functions
https://developer.blender.org/rB10437bba07d2885a61fe6723bf791a9c9bf93b17
only use new multimap implementation
===================================================================
M source/blender/blenkernel/BKE_node_tree.hpp
M source/blender/blenlib/BLI_multimap.hpp
M source/blender/functions/core/data_flow_graph_builder.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 f57c9a166a5..c1542bb98be 100644
--- a/source/blender/blenkernel/BKE_node_tree.hpp
+++ b/source/blender/blenkernel/BKE_node_tree.hpp
@@ -14,9 +14,9 @@ namespace BKE {
using BLI::ArrayRef;
using BLI::ListBaseWrapper;
using BLI::SmallMap;
+using BLI::SmallMultiMap;
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;
- ValueArrayMap<bNodeSocket *, bNodeSocket *> m_direct_links;
- ValueArrayMap<bNodeSocket *, bNodeSocket *> m_links_without_reroutes;
+ SmallMultiMap<bNodeSocket *, bNodeSocket *> m_direct_links;
+ SmallMultiMap<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 c8241770b90..8a656430cc3 100644
--- a/source/blender/blenlib/BLI_multimap.hpp
+++ b/source/blender/blenlib/BLI_multimap.hpp
@@ -1,10 +1,6 @@
#pragma once
-/* A multimap is a map that allows storing multiple values per key.
- *
- * 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.
- */
+/* A multimap is a map that allows storing multiple values per key. */
#include "BLI_small_map.hpp"
#include "BLI_multipool.hpp"
@@ -12,13 +8,7 @@
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 {
+template<typename K, typename V, uint N = 4> class SmallMultiMap {
private:
struct Entry {
K key;
@@ -42,13 +32,18 @@ template<typename K, typename V, uint N = 4> class ValueArrayMap {
SmallVector<V, N> m_elements;
public:
- ValueArrayMap() = default;
+ SmallMultiMap() = default;
uint key_amount() const
{
return m_map.size();
}
+ uint value_amount(const K &key) const
+ {
+ return this->lookup_default(key).size();
+ }
+
bool add(const K &key, const V &value)
{
bool newly_inserted = m_map.insert_or_modify(
@@ -82,7 +77,7 @@ template<typename K, typename V, uint N = 4> class ValueArrayMap {
return newly_inserted;
}
- bool add_new(const K &key, const V &value)
+ void add_new(const K &key, const V &value)
{
BLI_assert(!m_map.contains(key));
uint offset = m_elements.size();
@@ -119,112 +114,6 @@ template<typename K, typename V, uint N = 4> class ValueArrayMap {
{
return m_map.contains(key);
}
-};
-
-template<typename K, typename V> class MultiMap {
- private:
- struct Entry {
- K key;
- V *ptr;
- uint length;
- uint capacity;
-
- Entry(K key, V *ptr, uint length, uint capacity)
- : key(key), ptr(ptr), length(length), capacity(capacity)
- {
- }
- };
-
- static const K &get_key_from_item(const Entry &entry)
- {
- return entry.key;
- }
-
- SmallMap<K, Entry> m_map;
- MemMultiPool m_pool;
-
- public:
- uint size() const
- {
- return m_map.size();
- }
-
- void add(const K &key, const V &value)
- {
- if (m_map.contains(key)) {
- Entry &entry = m_map.lookup_ref(key);
- if (entry.length == entry.capacity) {
- uint new_capacity = entry.capacity * 2;
- V *old_ptr = entry.ptr;
- V *new_ptr = m_pool.allocate_array<V>(new_capacity);
- uninitialized_relocate_n(old_ptr, entry.length, new_ptr);
- m_pool.deallocate(old_ptr);
- entry.ptr = new_ptr;
- entry.capacity = new_capacity;
- }
- std::uninitialized_copy_n(&value, 1, entry.ptr + entry.length);
- entry.length++;
- }
- else {
- this->add_new(key, value);
- }
- }
-
- void add_new(const K &key, const V &value)
- {
- BLI_assert(!m_map.contains(key));
- V *ptr = m_pool.allocate<V>();
- std::uninitialized_copy_n(&value, 1, ptr);
- m_map.add_new(key, Entry(key, ptr, 1, 1));
- }
-
- void add_multiple_new(const K &key, ArrayRef<V> values)
- {
- BLI_assert(!m_map.contains(key));
- uint amount = values.size();
- V *ptr = m_pool.allocate_array<V>(amount);
- std::uninitialized_copy_n(values.begin(), amount, ptr);
- m_map.add_new(key, Entry(key, ptr, amount, amount));
- }
-
- bool contains(const K &key) const
- {
- return m_map.contains(key);
- }
-
- bool has_at_least_one_value(const K &key) const
- {
- return this->values_for_key(key) >= 1;
- }
-
- uint values_for_key(const K &key) const
- {
- Entry *entry = m_map.lookup_ptr(key);
- if (entry == nullptr) {
- return 0;
- }
- else {
- return entry->length;
- }
- }
-
- ArrayRef<V> lookup(const K &key) const
- {
- BLI_assert(this->contains(key));
- Entry &entry = m_map.lookup_ref(key);
- return ArrayRef<V>(entry.ptr, entry.length);
- }
-
- ArrayRef<V> lookup_default(const K &key, ArrayRef<V> default_return = ArrayRef<V>()) const
- {
- Entry *entry = m_map.lookup_ptr(key);
- if (entry == nullptr) {
- return default_return;
- }
- else {
- return ArrayRef<V>(entry->ptr, entry->length);
- }
- }
typename SmallMap<K, Entry>::KeysReturnT keys() const
{
diff --git a/source/blender/functions/core/data_flow_graph_builder.hpp b/source/blender/functions/core/data_flow_graph_builder.hpp
index 6a2109752bd..cf91e042a06 100644
--- a/source/blender/functions/core/data_flow_graph_builder.hpp
+++ b/source/blender/functions/core/data_flow_graph_builder.hpp
@@ -190,7 +190,7 @@ class DataFlowGraphBuilder {
private:
SmallSet<DFGB_Node *> m_nodes;
SmallMap<DFGB_Socket, DFGB_Socket> m_input_origins;
- MultiMap<DFGB_Socket, DFGB_Socket> m_output_targets;
+ SmallMultiMap<DFGB_Socket, DFGB_Socket> m_output_targets;
MemPool m_node_pool;
std::unique_ptr<MemMultiPool> m_source_info_pool;
@@ -245,7 +245,7 @@ inline bool DFGB_Socket::is_linked()
return this->builder().m_input_origins.contains(*this);
}
else {
- return this->builder().m_output_targets.has_at_least_one_value(*this);
+ return this->builder().m_output_targets.value_amount(*this) > 0;
}
}
diff --git a/tests/gtests/blenlib/BLI_multimap_test.cc b/tests/gtests/blenlib/BLI_multimap_test.cc
index d54d13a4ba7..89672dee73c 100644
--- a/tests/gtests/blenlib/BLI_multimap_test.cc
+++ b/tests/gtests/blenlib/BLI_multimap_test.cc
@@ -3,72 +3,19 @@
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);
-}
+using IntMultiMap = SmallMultiMap<int, int>;
TEST(multimap, DefaultConstructor)
{
- IntMap map;
- EXPECT_EQ(map.size(), 0);
+ IntMultiMap map;
+ EXPECT_EQ(map.key_amount(), 0);
}
TEST(multimap, AddNewSingle)
{
- IntMap map;
+ IntMultiMap map;
map.add_new(2, 5);
- EXPECT_EQ(map.size(), 1);
+ EXPECT_EQ(map.key_amount(), 1);
EXPECT_TRUE(map.contains(2));
EXPECT_FALSE(map.contains(5));
EXPECT_EQ(map.lookup(2)[0], 5);
@@ -76,11 +23,11 @@ TEST(multimap, AddNewSingle)
TEST(multimap, AddMultipleforSameKey)
{
- IntMap map;
+ IntMultiMap map;
map.add(3, 5);
map.add(3, 1);
map.add(3, 7);
- EXPECT_EQ(map.size(), 1);
+ EXPECT_EQ(map.key_amount(), 1);
EXPECT_EQ(map.lookup(3).size(), 3);
EXPECT_EQ(map.lookup(3)[0], 5);
EXPECT_EQ(map.lookup(3)[1], 1);
@@ -89,13 +36,13 @@ TEST(multimap, AddMultipleforSameKey)
TEST(multimap, AddMany)
{
- IntMap map;
+ IntMultiMap map;
for (uint i = 0; i < 100; i++) {
int key = i % 10;
map.add(key, i);
}
- EXPECT_EQ(map.size(), 10);
+ EXPECT_EQ(map.key_amount(), 10);
EXPECT_TRUE(map.contains(3));
EXPECT_FALSE(map.contains(11));
EXPECT_EQ(map.lookup(2)[4], 42);
@@ -105,11 +52,11 @@ TEST(multimap, AddMany)
TEST(multimap, AddMultipleNew)
{
- IntMap map;
+ IntMultiMap map;
map.add_multiple_new(3, {6, 7, 8});
map.add_multiple_new(2, {1, 2, 5, 7});
- EXPECT_EQ(map.size(), 2);
+ EXPECT_EQ(map.key_amount(), 2);
EXPECT_TRUE(map.contains(3));
EXPECT_TRUE(map.contains(2));
EXPECT_TRUE(map.lookup(2).contains(2));
@@ -118,19 +65,19 @@ TEST(multimap, AddMultipleNew)
TEST(multimap, ValuesForKey)
{
- IntMap map;
+ IntMultiMap map;
map.add(3, 5);
map.add(3, 7);
map.add(3, 8);
map.add(4, 2);
map.add(4, 3);
- EXPECT_EQ(map.values_for_key(3), 3);
- EXPECT_EQ(map.values_for_key(4), 2);
+ EXPECT_EQ(map.value_amount(3), 3);
+ EXPECT_EQ(map.value_amount(4), 2);
}
TEST(multimap, Keys)
{
- IntMap map;
+ IntMultiMap map;
map.add(3, 6);
map.a
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list