Commit: 0f1b4d7c38e6dd0225c9c5fe72fb844e63bb49aa
Author: Jacques Lucke
Date: Sun Apr 7 17:01:31 2019 +0200
Branches: functions
https://developer.blender.org/rB0f1b4d7c38e6dd0225c9c5fe72fb844e63bb49aa
Use actual hash tables instead of linear search
The hash functions themselves are not optimized yet.
===================================================================
A source/blender/blenlib/BLI_array_lookup.hpp
M source/blender/blenlib/BLI_shared.hpp
M source/blender/blenlib/BLI_small_map.hpp
M source/blender/blenlib/BLI_small_set.hpp
M source/blender/blenlib/BLI_small_set_vector.hpp
M source/blender/blenlib/BLI_small_vector.hpp
M source/blender/blenlib/CMakeLists.txt
M source/blender/functions/core/data_flow_graph.hpp
M source/blender/functions/core/type.hpp
M source/blender/functions/frontends/data_flow_nodes/inserters.cpp
A tests/gtests/blenlib/BLI_array_lookup_test.cc
M tests/gtests/blenlib/BLI_small_map_test.cc
M tests/gtests/blenlib/BLI_small_set_vector_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_array_lookup.hpp
b/source/blender/blenlib/BLI_array_lookup.hpp
new file mode 100644
index 00000000000..08741f9ff96
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -0,0 +1,181 @@
+#pragma once
+
+#include "BLI_utildefines.h"
+#include "BLI_small_vector.hpp"
+#include "BLI_math_bits.h"
+
+#define SLOT_EMPTY -1
+#define SLOT_DUMMY -2
+#define LOAD_FACTOR 0.6f
+#define PERTURB_SHIFT 5
+
+#define ITER_SLOTS(KEY, SLOT, STATE) \
+ uint32_t SLOT, SLOT##_perturb; \
+ State STATE; \
+ for (this->first_slot(KEY, &SLOT, &SLOT##_perturb), STATE =
m_map[SLOT];; \
+ this->next_slot(&SLOT, &SLOT##_perturb), STATE = m_map[SLOT])
+
+namespace BLI {
+
+ template<typename T>
+ inline const T &get_key_from_item(const T &item)
+ {
+ return item;
+ }
+
+ 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 Index = uint32_t>
+ class ArrayLookup {
+ private:
+ using State = typename std::make_signed<Index>::type;
+ using Mapping = SmallVector<State, (1 << N_EXP)>;
+ Mapping m_map;
+ uint m_usable_slots;
+ uint m_length;
+ uint32_t m_slot_mask;
+
+ public:
+ ArrayLookup()
+ {
+ this->reset_map(1 << N_EXP);
+ m_length = 0;
+ }
+
+ void ensure_can_add(Item *array, uint amount = 1)
+ {
+ if (LIKELY(m_usable_slots >= amount)) {
+ return;
+ }
+
+ this->reset_map(m_map.size() * 2);
+ for (uint i = 0; i < m_length; i++) {
+ const Key &key = GetKey(array[i]);
+ this->insert_index(key, i);
+ }
+ m_usable_slots -= m_length;
+ }
+
+ bool contains(Item *array, const Key &key) const
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == SLOT_EMPTY) {
+ return false;
+ }
+ else if (state == SLOT_DUMMY) {
+ continue;
+ }
+ else if (GetKey(array[state]) == key) {
+ return true;
+ }
+ }
+ }
+
+ void add_new(Item *array, Index index)
+ {
+ this->ensure_can_add(array);
+ const Key &key = GetKey(array[index]);
+ this->add_new__fast(key, index);
+ m_usable_slots--;
+ m_length++;
+ }
+
+ void add_new_range(Item *array, Index start, Index end)
+ {
+ BLI_assert(start <= end);
+ uint amount = end - start;
+ this->ensure_can_add(array, amount);
+ for (Index i = start; i < end; i++) {
+ const Key &key = GetKey(array[index]);
+ this->add_new__fast(key, i);
+ }
+ m_usable_slots -= amount;
+ m_length += amount;
+ }
+
+ void add_new__fast(const Key &key, Index index)
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == SLOT_EMPTY) {
+ m_map[slot] = (State)index;
+ break;
+ }
+ }
+ }
+
+ void remove(const Key &key, Index index)
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == index) {
+ m_map[slot] = SLOT_DUMMY;
+ m_length--;
+ break;
+ }
+ }
+ }
+
+ typename std::make_signed<Index>::type find(
+ Item *array, const Key &key) const
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == SLOT_EMPTY) {
+ return -1;
+ }
+ else if (state == SLOT_DUMMY) {
+ continue;
+ }
+ else if (GetKey(array[state]) == key) {
+ return state;
+ }
+ }
+ }
+
+ private:
+ inline void reset_map(uint size)
+ {
+ BLI_assert(count_bits_i(size) == 1);
+ m_map = Mapping(size);
+ m_map.fill(SLOT_EMPTY);
+ m_usable_slots = m_map.size() * LOAD_FACTOR;
+ m_slot_mask = size - 1;
+ }
+
+ inline void insert_index(const Key &key, Index index)
+ {
+ ITER_SLOTS(key, slot, state) {
+ if (state == SLOT_EMPTY) {
+ m_map[slot] = index;
+ break;
+ }
+ }
+ }
+
+ inline void first_slot(
+ const Key &key,
+ uint32_t *slot,
+ uint32_t *perturb) const
+ {
+ uint32_t hash_value = Hash{}(key);
+ *slot = hash_value & m_slot_mask;
+ *perturb = hash_value;
+ }
+
+ inline void next_slot(
+ uint32_t *slot,
+ uint32_t *perturb) const
+ {
+ *slot = m_slot_mask & ((5 + *slot) + 1 + *perturb);
+ *perturb >>= PERTURB_SHIFT;
+ }
+ };
+
+} /* namespace BLI */
+
+#undef SLOT_EMPTY
+#undef SLOT_DUMMY
+#undef LOAD_FACTOR
+#undef PERTURB_SHIFT
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_shared.hpp
b/source/blender/blenlib/BLI_shared.hpp
index 5fb62635aa1..dc608eb75ca 100644
--- a/source/blender/blenlib/BLI_shared.hpp
+++ b/source/blender/blenlib/BLI_shared.hpp
@@ -143,7 +143,7 @@ namespace BLI {
friend bool operator==(const AutoRefCount &a, const
AutoRefCount &b)
{
- return a.m_object == b.m_object;
+ return *a.ptr() == *b.ptr();
}
friend bool operator!=(const AutoRefCount &a, const
AutoRefCount &b)
@@ -152,4 +152,19 @@ namespace BLI {
}
};
-} /* namespace BLI */
\ No newline at end of file
+} /* namespace BLI */
+
+namespace std
+{
+ template<typename T>
+ struct hash<BLI::AutoRefCount<T>>
+ {
+ typedef BLI::AutoRefCount<T> argument_type;
+ typedef size_t result_type;
+
+ result_type operator()(argument_type const &v) const noexcept
+ {
+ return std::hash<T>{}(*v.ptr());
+ }
+ };
+}
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_small_map.hpp
b/source/blender/blenlib/BLI_small_map.hpp
index cddf82edd26..bea14230212 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -1,6 +1,7 @@
#pragma once
#include "BLI_small_vector.hpp"
+#include "BLI_array_lookup.hpp"
namespace BLI {
@@ -16,27 +17,31 @@ namespace BLI {
: key(key), value(value) {}
};
+ static const K &get_key_from_entry(const Entry &entry)
+ {
+ return entry.key;
+ }
+
SmallVector<Entry> m_entries;
+ ArrayLookup<K, Entry, get_key_from_entry> m_lookup;
public:
class ValueIterator;
SmallMap() = default;
- void add(K key, V value)
+ void add(const K &key, const V &value)
{
BLI_assert(!this->contains(key));
- m_entries.append(Entry(key, value));
+ uint index = m_entries.size();
+ Entry entry(key, value);
+ m_entries.append(entry);
+ m_lookup.add_new(m_entries.begin(), index);
}
- bool contains(K key) const
+ bool contains(const K &key) const
{
- for (Entry entry : m_entries) {
- if (entry.key == key) {
- return true;
- }
- }
- return false;
+ return m_lookup.contains(m_entries.begin(), key);
}
V lookup(const K &key) const
@@ -63,12 +68,13 @@ namespace BLI {
V *lookup_ptr(const K &key) const
{
- for (Entry &entry : m_entries) {
- if (entry.key == key) {
- return &entry.value;
- }
+ int index = m_lookup.find(m_entries.begin(), key);
+ if (index >= 0) {
+ return &m_entries[index].value;
+ }
+ else {
+ return nullptr;
}
- return nullptr;
}
uint size() const
diff --git a/source/blender/blenlib/BLI_small_set.hpp
b/source/blender/blenlib/BLI_small_set.hpp
index d01d5a6f0c2..3b9a85e64e2 100644
--- a/source/blender/blenlib/BLI_small_set.hpp
+++ b/source/blender/blenlib/BLI_small_set.hpp
@@ -1,86 +1,80 @@
#pragma once
#include "BLI_small_vector.hpp"
+#include "BLI_array_lookup.hpp"
namespace BLI {
- template<typename T, uint N = 4>
+ template<
+ typename T,
+ uint N = 4,
+ typename Hash = std::hash<T>>
class SmallSet {
protected:
- SmallVector<T> m_entries;
+ SmallVector<T> m_elements;
+ ArrayLookup<T> m_lookup;
public:
SmallSet() = default;
- SmallSet(const std::initializer_list<T> &values)
+ SmallSet(const SmallVector<T> &values)
{
- for (T value : values) {
+ for (const T &value : values) {
this->add(value);
}
}
- SmallSet(const SmallVector<T> &values)
+ SmallSet (const std::initializer_list<T> &values)
{
- for (T value : values) {
+ for (const T &value : values) {
this->add(value);
}
}
- void add(T value)
+ uint size() const
{
- if (!this->contains(value)) {
- m_entries.append(value);
- }
+ return m_elements.size();
}
- bool contains(T value) const
+ bool contains(const T &value) const
{
- for (T entry : m_entries) {
- if (entry == value) {
- return true;
- }
- }
- return false;
+ return m_lookup.contains(m_elements.begin(), value);
}
- uint size() const
+ void add(const T &value)
{
- return m_entries.size();
+ if (!this->contains(value)) {
+ uint index = m_elements.size();
+ m_elements.append(value);
+ m_lookup.add_new(m_elements.begin(), index);
+ }
}
- T any() const
+ T pop()
{
BLI_assert(this->size() > 0);
- return m_entries[0];
+ T value = m_elements.pop_last();
+ uint index = m_elements.size();
+ m_lookup.remove(value, index);
+ return value;
}
- T pop()
+ T any() const
{
- return m_entries.pop_last();
+ BLI_assert(this->size() > 0);
+ return m_elements[0];
}
-
- /* Iterators */
-
T *begin() const
{
- return m_entries.begin();
+ return m_elements.begin();
}
T *end() const
{
- return m_entries.end();
+ return m_elements.end();
}
- const T *cbegin() const
- {
- return m_entries.cbegin();
- }
-
- const T *cend() const
- {
- return m_entries.cend();
- }
};
} /* namespace BLI */
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_small_set_vector.hpp
b/source/blender/blenlib/BLI_small_set_vector.hpp
index 8c18c53234f..3e25e603a3f 100644
--- a/source/blender/blenlib/BLI_small_set_vector.hpp
+++ b/source/blender/blenlib/BLI_small_set_vector.hpp
@@ -19,7 +19,7 @@ namespace BLI {
int index(const T &value) const
{
for (uint i = 0; i < this->size(); i++) {
- if (this->m_entries[i] == value) {
+ if (this->m_elements[i] == value) {
return i;
}
}
@@ -29,7 +29,7 @@ namespace BLI {
T operator[](const int index) const
{
BLI_assert(index >= 0 && index < this->size());
- return this->m_entries[index];
+ return this->m_elements[index];
}
};
diff --git a/source/blender/blenlib/BLI_small_vector.hpp
b/source/blender/blenlib/BLI_small_vector.hpp
index c5ffee5dc7a..e34cb8c4d73 100644
--- a/source/blender/blenlib/BLI_small_vector.hpp
+++ b/source/blender/blenlib/BLI_small_vector.hpp
@@ -56,9 +56,7 @@ namespace BLI {
~SmallVector()
{
- if (m_elements != nullptr) {
- this->destruct_elements_and_free_memory();
- }
+ this->destruct_eleme
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
