[Bf-blender-cvs] [158425fc61c] functions: use a multimap data structure to store links of output sockets
Jacques Lucke
noreply at git.blender.org
Thu Apr 11 13:47:18 CEST 2019
Commit: 158425fc61cebb41739aed614caa9599dd107eec
Author: Jacques Lucke
Date: Thu Apr 11 13:47:01 2019 +0200
Branches: functions
https://developer.blender.org/rB158425fc61cebb41739aed614caa9599dd107eec
use a multimap data structure to store links of output sockets
===================================================================
A source/blender/blenlib/BLI_array_ref.hpp
A source/blender/blenlib/BLI_multimap.hpp
M source/blender/blenlib/BLI_multipool.hpp
M source/blender/blenlib/BLI_small_map.hpp
M source/blender/blenlib/BLI_small_vector.hpp
M source/blender/blenlib/CMakeLists.txt
M source/blender/functions/core/data_flow_graph.hpp
A tests/gtests/blenlib/BLI_multimap_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_array_ref.hpp b/source/blender/blenlib/BLI_array_ref.hpp
new file mode 100644
index 00000000000..bb40bdf56d3
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_ref.hpp
@@ -0,0 +1,39 @@
+#pragma once
+
+namespace BLI {
+
+ template<typename T>
+ class ArrayRef {
+ private:
+ T *m_start = nullptr;
+ uint m_size = 0;
+
+ public:
+ ArrayRef() = default;
+
+ ArrayRef(T *start, uint size)
+ : m_start(start), m_size(size) {}
+
+ T *begin()
+ {
+ return m_start;
+ }
+
+ T *end()
+ {
+ return m_start + m_size;
+ }
+
+ T &operator[](uint index) const
+ {
+ BLI_assert(index < m_size);
+ return m_start[index];
+ }
+
+ uint size() const
+ {
+ return m_size;
+ }
+ };
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_multimap.hpp b/source/blender/blenlib/BLI_multimap.hpp
new file mode 100644
index 00000000000..40112746d66
--- /dev/null
+++ b/source/blender/blenlib/BLI_multimap.hpp
@@ -0,0 +1,78 @@
+#pragma once
+
+#include "BLI_small_map.hpp"
+#include "BLI_multipool.hpp"
+#include "BLI_array_ref.hpp"
+
+namespace BLI {
+
+ 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));
+ }
+
+ bool contains(const K &key) const
+ {
+ return m_map.contains(key);
+ }
+
+ 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);
+ }
+ };
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_multipool.hpp b/source/blender/blenlib/BLI_multipool.hpp
index 5199e31ea1c..56efc285516 100644
--- a/source/blender/blenlib/BLI_multipool.hpp
+++ b/source/blender/blenlib/BLI_multipool.hpp
@@ -20,6 +20,18 @@ namespace BLI {
}
}
+ template<typename T>
+ T *allocate()
+ {
+ return (T *)this->allocate(sizeof(T));
+ }
+
+ template<typename T>
+ T *allocate_array(uint length)
+ {
+ return (T *)this->allocate(sizeof(T) * length);
+ }
+
void *allocate(uint size)
{
uint alloc_size = size + sizeof(uint);
@@ -48,4 +60,4 @@ namespace BLI {
}
};
-} /* namespace BLI */
\ No newline at end of file
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index 0e4e0607c20..911c5353e71 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -164,7 +164,7 @@ namespace BLI {
return m_index != iterator.m_index;
}
- V operator*() const
+ V &operator*() const
{
return m_map.m_entries[m_index].value;
}
diff --git a/source/blender/blenlib/BLI_small_vector.hpp b/source/blender/blenlib/BLI_small_vector.hpp
index e34cb8c4d73..445e56a7e0e 100644
--- a/source/blender/blenlib/BLI_small_vector.hpp
+++ b/source/blender/blenlib/BLI_small_vector.hpp
@@ -10,6 +10,18 @@
namespace BLI {
+ template<typename T>
+ void uninitialized_relocate_n(T *src, uint n, T *dst)
+ {
+ std::uninitialized_copy_n(
+ std::make_move_iterator(src),
+ n,
+ dst);
+ for (uint i = 0; i < n; i++) {
+ src[i].~T();
+ }
+ }
+
template<typename T, uint N = 4>
class SmallVector {
private:
@@ -253,12 +265,7 @@ namespace BLI {
m_capacity = min_capacity;
T *new_array = (T *)MEM_malloc_arrayN(m_capacity, sizeof(T), __func__);
- std::uninitialized_copy(
- std::make_move_iterator(this->begin()),
- std::make_move_iterator(this->end()),
- new_array);
-
- this->destruct_elements_but_keep_memory();
+ uninitialized_relocate_n(m_elements, m_size, new_array);
if (!this->is_small()) {
MEM_freeN(m_elements);
@@ -284,10 +291,7 @@ namespace BLI {
void steal_from_other(SmallVector &&other)
{
if (other.is_small()) {
- std::uninitialized_copy(
- std::make_move_iterator(other.begin()),
- std::make_move_iterator(other.end()),
- this->small_buffer());
+ uninitialized_relocate_n(other.begin(), other.size(), this->small_buffer());
m_elements = this->small_buffer();
}
else {
@@ -323,4 +327,4 @@ namespace BLI {
}
};
-} /* namespace BLI */
\ No newline at end of file
+} /* namespace BLI */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index f5f12235313..79cde43d399 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -233,10 +233,12 @@ set(SRC
PIL_time_utildefines.h
BLI_array_lookup.hpp
+ BLI_array_ref.hpp
BLI_composition.hpp
BLI_lazy_init.hpp
BLI_listbase_wrapper.hpp
BLI_mempool.hpp
+ BLI_multimap.hpp
BLI_multipool.hpp
BLI_optional.hpp
BLI_shared.hpp
diff --git a/source/blender/functions/core/data_flow_graph.hpp b/source/blender/functions/core/data_flow_graph.hpp
index 96f28c176ba..0e8fc2188e4 100644
--- a/source/blender/functions/core/data_flow_graph.hpp
+++ b/source/blender/functions/core/data_flow_graph.hpp
@@ -7,6 +7,7 @@
#include "BLI_small_set_vector.hpp"
#include "BLI_mempool.hpp"
#include "BLI_multipool.hpp"
+#include "BLI_multimap.hpp"
namespace FN {
@@ -43,7 +44,7 @@ namespace FN {
friend std::ostream &operator<<(std::ostream &stream, Socket socket);
inline Socket origin() const;
- inline SocketSet targets() const;
+ inline ArrayRef<Socket> targets() const;
inline bool is_linked() const;
private:
@@ -223,23 +224,9 @@ namespace FN {
Socket from = link.from();
Socket to = link.to();
- if (!m_links.contains(from)) {
- m_links.add(from, SmallSet<Socket>());
- }
- if (!m_links.contains(to)) {
- m_links.add(to, SmallSet<Socket>());
- }
-
- m_links.lookup_ref(from).add(to);
- m_links.lookup_ref(to).add(from);
- m_all_links.append(Link::New(from, to));
- }
-
- SmallSet<Socket> get_linked(Socket socket) const
- {
- SmallSet<Socket> *linked = m_links.lookup_ptr(socket);
- if (linked == nullptr) return {};
- return *linked;
+ m_origins.add_new(to, from);
+ m_targets.add(from, to);
+ m_all_links.append(link);
}
SmallVector<Link> all_links() const
@@ -250,13 +237,28 @@ namespace FN {
Socket get_origin(Socket socket) const
{
BLI_assert(socket.is_input());
- auto linked = this->get_linked(socket);
- BLI_assert(linked.size() == 1);
- return linked.any();
+ return m_origins.lookup(socket);
+ }
+
+ ArrayRef<Socket> get_targets(Socket socket) const
+ {
+ BLI_assert(socket.is_output());
+ return m_targets.lookup(socket);
+ }
+
+ bool is_linked(Socket socket) const
+ {
+ if (socket.is_input()) {
+ return m_origins.contains(socket);
+ }
+ else {
+ return m_targets.lookup(socket).size() > 0;
+ }
}
private:
- SmallMap<Socket, SmallSet<Socket>> m_links;
+ SmallMap<Socket, Socket> m_origins;
+ MultiMap<Socket, Socket> m_targets;
SmallVector<Link> m_all_links;
};
@@ -433,14 +435,14 @@ namespace FN {
return this->graph()->m_links.get_origin(*this);
}
- SocketSet Socket::targets() const
+ ArrayRef<Socket> Socket::targets() const
{
- return this->graph()->m_links.get_linked(*this);
+ return this->graph()->m_links.get_targets(*this);
}
bool Socket::is_linked() const
{
- return this->graph()->m_links.get_linked(*this).size() > 0;
+ return this->graph()->m_links.is_linked(*this);
}
} /* namespace FN */
diff --git a/tests/gtests/blenlib/BLI_multimap_test.cc b/tests/gtests/blenlib/BLI_multimap_test.cc
new file mode 100644
index 00000000000..0cc7b43422e
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_multimap_test.cc
@@ -0,0 +1,52 @@
+#include "testing/testing.h"
+#include "BLI_multimap.hpp"
+
+using namespace BLI;
+
+using IntMap = MultiMap<int, int>;
+
+TEST(multimap, DefaultConstructor)
+{
+ IntMap map;
+ EXPECT_EQ(map.size(), 0);
+}
+
+TEST(multimap, AddNewSingle)
+{
+ IntMap map;
+ map.add_new(2, 5);
+ EXPECT_EQ(map.size(), 1);
+ EXPECT_TRUE(map.contains(2));
+ EXPECT_FALSE(map.contains(5));
+ EXPECT_EQ(map.lookup(2)[0], 5);
+}
+
+TEST(multimap, AddMultipleforSameKey)
+{
+ IntMap map;
+ map.add(3, 5);
+ map.add(3, 1);
+ map.add(3, 7);
+ EXPECT_EQ(map.size(), 1);
+ EXPECT_EQ(map.lookup(3).size(), 3);
+ EXPECT_EQ(map.lookup(3)[0], 5);
+ EXPECT_EQ(map.lookup(3)[1], 1);
+ EXPECT_EQ(map.lookup(3)[2], 7);
+}
+
+
+TEST(multimap, AddMany)
+{
+ IntMap map;
+ for (uint i = 0; i < 100; i++) {
+ int key = i % 10;
+ map.add(key, i);
+ }
+
+ EXPECT_EQ(map.size(), 10);
+ EXPECT_TRUE(map.contains(3));
+ EXPECT_FALSE(map.contains(11));
+ EXPECT_EQ(map.lookup(2)[4], 42);
+ EXPECT_EQ(map.lookup(6)[1], 16);
+ EXPECT_EQ(map.lookup(7).size(), 10);
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index e1f58aa3e7b..465ac5e001c 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -56,6 +56,7 @@ BLENDER_TEST(BLI_math_color "bf_blenlib")
BLENDER_TEST(BLI_math_geom "bf_blenlib")
BLENDER_TEST(BLI_memiter "bf_blenlib")
BLENDER_TEST(BLI_mempool "bf_blenlib")
+BLENDER_TEST(BLI_multimap "bf_blenlib")
BLENDER_TEST(BLI_optional "bf_blenlib")
BLEND
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list