[Bf-blender-cvs] [4346e882868] functions: Split up the data flow graph data structure
Jacques Lucke
noreply at git.blender.org
Fri Apr 26 19:25:03 CEST 2019
Commit: 4346e8828680a65468a4281bcac396c9ab8fb220
Author: Jacques Lucke
Date: Fri Apr 26 19:21:28 2019 +0200
Branches: functions
https://developer.blender.org/rB4346e8828680a65468a4281bcac396c9ab8fb220
Split up the data flow graph data structure
The main goal is to be able to traverse the graph very efficiently
once it is build. This is hard when the structure has to be dynamic
(i.e. it can be changed). The solution is to use a builder that
can dynamically construct the graph. Once everything is set up,
the graph is converted into the compact form for further use.
===================================================================
M source/blender/blenlib/BLI_array_lookup.hpp
M source/blender/blenlib/BLI_array_ref.hpp
M source/blender/blenlib/BLI_mempool.hpp
M source/blender/blenlib/BLI_multimap.hpp
M source/blender/blenlib/BLI_optional.hpp
M source/blender/blenlib/BLI_small_map.hpp
M source/blender/functions/CMakeLists.txt
M source/blender/functions/FN_core.hpp
M source/blender/functions/backends/dependencies/fgraph_dependencies.cpp
M source/blender/functions/backends/llvm/fgraph_ir_generation.cpp
M source/blender/functions/backends/tuple_call/fgraph_tuple_call.cpp
M source/blender/functions/core/data_flow_graph.cpp
M source/blender/functions/core/data_flow_graph.hpp
A source/blender/functions/core/data_flow_graph_builder.cpp
A source/blender/functions/core/data_flow_graph_builder.hpp
M source/blender/functions/core/dot_export.cpp
A source/blender/functions/core/function_graph.cpp
A source/blender/functions/core/function_graph.hpp
M source/blender/functions/frontends/data_flow_nodes/builder.cpp
M source/blender/functions/frontends/data_flow_nodes/builder.hpp
M source/blender/functions/frontends/data_flow_nodes/function_generation.cpp
M source/blender/functions/frontends/data_flow_nodes/graph_generation.cpp
M source/blender/functions/frontends/data_flow_nodes/inserters.cpp
M source/blender/functions/frontends/data_flow_nodes/inserters.hpp
M source/blender/functions/frontends/data_flow_nodes/inserters/conversions.cpp
M source/blender/functions/frontends/data_flow_nodes/inserters/nodes.cpp
M tests/gtests/blenlib/BLI_optional_test.cc
M tests/gtests/blenlib/BLI_small_map_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
index 5cfc4c76fb7..53b234c3791 100644
--- a/source/blender/blenlib/BLI_array_lookup.hpp
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -3,6 +3,8 @@
#include "BLI_utildefines.h"
#include "BLI_small_vector.hpp"
#include "BLI_math_bits.h"
+#include "BLI_ghash.h"
+#include "BLI_hash.h"
#define SLOT_EMPTY -1
#define SLOT_DUMMY -2
@@ -22,11 +24,25 @@ template<typename T> inline const T &get_key_from_item(const T &item)
return item;
}
+template<typename T> struct ArrayLookupHash {
+ uint operator()(const T &v) const noexcept
+ {
+ return std::hash<T>{}(v);
+ }
+};
+
+template<typename T> struct ArrayLookupHash<T *> {
+ uint operator()(const T *v) const noexcept
+ {
+ return BLI_ghashutil_ptrhash(v);
+ }
+};
+
template<typename Key,
typename Item = Key,
const Key &GetKey(const Item &entry) = get_key_from_item,
uint N_EXP = 3,
- typename Hash = std::hash<Key>,
+ typename Hash = ArrayLookupHash<Key>,
typename Index = int>
class ArrayLookup {
private:
@@ -46,8 +62,7 @@ class ArrayLookup {
bool contains(Item *array, const Key &key) const
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_EMPTY) {
return false;
}
@@ -63,8 +78,7 @@ class ArrayLookup {
bool add(Item *array, const Key &key, Index potential_index)
{
int dummy_slot = -1;
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_EMPTY) {
if (dummy_slot == -1) {
bool map_changed = this->ensure_can_add(array);
@@ -103,8 +117,7 @@ class ArrayLookup {
void update_index(const Key &key, Index old_index, Index new_index)
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == old_index) {
m_map[slot] = new_index;
break;
@@ -114,8 +127,7 @@ class ArrayLookup {
Index find(Item *array, const Key &key) const
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_EMPTY) {
return -1;
}
@@ -130,8 +142,7 @@ class ArrayLookup {
void remove(const Key &key, Index index)
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == index) {
m_map[slot] = SLOT_DUMMY;
m_length--;
@@ -144,8 +155,7 @@ class ArrayLookup {
Index remove(Item *array, const Key &key)
{
BLI_assert(this->contains(array, key));
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_DUMMY) {
continue;
}
@@ -185,8 +195,7 @@ class ArrayLookup {
inline void insert_index_for_key(const Key &key, Index index)
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_EMPTY) {
m_map[slot] = index;
break;
@@ -201,8 +210,7 @@ class ArrayLookup {
inline void insert_index_for_key__no_dummy(const Key &key, Index index)
{
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_EMPTY) {
m_map[slot] = index;
break;
@@ -248,8 +256,7 @@ class ArrayLookup {
{
KeyLookupStats key_stats;
- ITER_SLOTS(key, slot, state)
- {
+ ITER_SLOTS (key, slot, state) {
if (state == SLOT_DUMMY) {
key_stats.collisions_with_dummies++;
}
diff --git a/source/blender/blenlib/BLI_array_ref.hpp b/source/blender/blenlib/BLI_array_ref.hpp
index 4271524d3e7..9b7b6234674 100644
--- a/source/blender/blenlib/BLI_array_ref.hpp
+++ b/source/blender/blenlib/BLI_array_ref.hpp
@@ -36,4 +36,61 @@ template<typename T> class ArrayRef {
}
};
+template<typename ArrayT, typename ValueT, ValueT (*GetValue)(ArrayT &item)>
+class StridedArrayRef {
+ private:
+ ArrayT *m_start = nullptr;
+ uint m_size = 0;
+
+ public:
+ StridedArrayRef() = default;
+
+ StridedArrayRef(ArrayT *start, uint size) : m_start(start), m_size(size)
+ {
+ }
+
+ uint size() const
+ {
+ return m_size;
+ }
+
+ class It {
+ private:
+ StridedArrayRef m_array_ref;
+ uint m_index;
+
+ public:
+ It(StridedArrayRef array_ref, uint index) : m_array_ref(array_ref), m_index(index)
+ {
+ }
+
+ It &operator++()
+ {
+ m_index++;
+ return *this;
+ }
+
+ bool operator!=(const It &other) const
+ {
+ BLI_assert(m_array_ref.m_start == other.m_array_ref.m_start);
+ return m_index != other.m_index;
+ }
+
+ ValueT operator*() const
+ {
+ return GetValue(m_array_ref.m_start[m_index]);
+ }
+ };
+
+ It begin() const
+ {
+ return It(*this, 0);
+ }
+
+ It end() const
+ {
+ return It(*this, m_size);
+ }
+};
+
} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_mempool.hpp b/source/blender/blenlib/BLI_mempool.hpp
index de0d0e9ff1d..24be1672526 100644
--- a/source/blender/blenlib/BLI_mempool.hpp
+++ b/source/blender/blenlib/BLI_mempool.hpp
@@ -1,6 +1,7 @@
#pragma once
#include "BLI_small_stack.hpp"
+#include "BLI_small_set.hpp"
namespace BLI {
@@ -10,6 +11,10 @@ class MemPool {
SmallVector<void *> m_start_pointers;
uint m_element_size;
+#ifdef DEBUG
+ SmallSet<void *> m_allocated_pointers;
+#endif
+
public:
MemPool(uint element_size) : m_element_size(element_size)
{
@@ -29,11 +34,19 @@ class MemPool {
if (m_free_stack.empty()) {
this->allocate_more();
}
- return m_free_stack.pop();
+ void *ptr = m_free_stack.pop();
+#ifdef DEBUG
+ m_allocated_pointers.add_new(ptr);
+#endif
+ return ptr;
}
void deallocate(void *ptr)
{
+#ifdef DEBUG
+ BLI_assert(m_allocated_pointers.contains(ptr));
+ m_allocated_pointers.remove(ptr);
+#endif
m_free_stack.push(ptr);
}
@@ -58,4 +71,4 @@ class MemPool {
}
};
-} /* namespace BLI */
\ No newline at end of file
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_multimap.hpp b/source/blender/blenlib/BLI_multimap.hpp
index b62c77d91dc..3b4fe86b33d 100644
--- a/source/blender/blenlib/BLI_multimap.hpp
+++ b/source/blender/blenlib/BLI_multimap.hpp
@@ -68,12 +68,34 @@ template<typename K, typename V> class MultiMap {
return m_map.contains(key);
}
+ bool has_at_least_one_value(const K &key) const
+ {
+ Entry *entry = m_map.lookup_ptr(key);
+ if (entry == nullptr) {
+ return false;
+ }
+ else {
+ return entry->length >= 1;
+ }
+ }
+
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>())
+ {
+ Entry *entry = m_map.lookup_ptr(key);
+ if (entry == nullptr) {
+ return default_return;
+ }
+ else {
+ return ArrayRef<V>(entry->ptr, entry->length);
+ }
+ }
};
} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_optional.hpp b/source/blender/blenlib/BLI_optional.hpp
index c7a3436eb5b..17729aaa6c7 100644
--- a/source/blender/blenlib/BLI_optional.hpp
+++ b/source/blender/blenlib/BLI_optional.hpp
@@ -13,6 +13,16 @@ template<typename T> class Optional {
bool m_set;
public:
+ static Optional FromPointer(T *ptr)
+ {
+ if (ptr == nullptr) {
+ return Optional();
+ }
+ else {
+ return Optional(*ptr);
+ }
+ }
+
Optional() : m_set(false)
{
}
@@ -132,4 +142,4 @@ template<typename T> class Optional {
}
};
-} /* 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 f2edd9a7fad..7ee35cfad8e 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -2,6 +2,7 @@
#include "BLI_small_vector.hpp"
#include "BLI_array_lookup.hpp"
+#include "BLI_array_ref.hpp"
namespace BLI {
@@ -125,57 +126,48 @@ template<typename K, typename V, uint N = 4> class SmallMap {
m_lookup.print_lookup_stats(m_entries.begin());
}
- ValueIterator values() const
+ /* Iterators
+ **************************************************/
+
+ static V &get_value_from_entry(Entry &entry)
{
- return ValueIterator(*this);
+ return entry.value;
}
- class ValueIterator {
- private:
- const SmallMap &m_map;
- uint m_index;
-
- ValueIterator(const SmallMap &map, uint index) : m_map(map), m_index(index)
- {
- }
-
- public:
- ValueIterator(const SmallMap &map) : ValueIterator(map, 0)
- {
- }
+ StridedArrayRef<Entry, V &, get_value_from_entry> values() const
+ {
+ return StridedArrayRef<Entry, V &, get_value_from_entry>(m_entries.begin(), m_entries.size());
+ }
- ValueIterator begin() const
- {
- return ValueIterator(m_map, 0);
- }
+ static const K &get_key_from_entry(Entry &entry)
+ {
+ return entry.key;
+ }
- ValueIterator end() const
- {
- return ValueIterator(m_map, m_map.size());
- }
+ StridedArrayRef<Entry, const K &, get_key_from_entry> keys() const
+ {
+ return StridedArrayRef<Entry, const K &, get_key_from_entry>(m_entries.begin(),
+ m_entries.size());
+ }
- ValueIterator &operator++()
- {
- m_index++;
- return *this;
- }
+ struct KeyValuePair {
+ const K &key;
+ V &value;
- ValueIterator operator++(int)
+ KeyValuePair(const K &key, V &value) : key(key), value(value)
{
- ValueIterator iterator = *this;
- ++*this;
- return iterator;
}
+ };
- bool operator!=(const ValueIterator &iterator) const
- {
- return m_index != iterator.m_index;
- }
+ static KeyValuePair get_key_value_pair_from_entry(Entry &entry)
+ {
+ return KeyValuePair(entry.key, entry.value);
+ }
- V &operator*() const
- {
- return m_map.m_entries[m_index].value;
- }
- };
+ StridedArrayRef<Entry, KeyValuePair, get_key_value_pair_from_entry> items() const
+ {
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list