[Bf-blender-cvs] [8f5a4a4da33] master: BLI: various data structure improvements
Jacques Lucke
noreply at git.blender.org
Thu Apr 23 20:07:39 CEST 2020
Commit: 8f5a4a4da33375b591dd77e424096878ff2e2aaf
Author: Jacques Lucke
Date: Thu Apr 23 20:05:53 2020 +0200
Branches: master
https://developer.blender.org/rB8f5a4a4da33375b591dd77e424096878ff2e2aaf
BLI: various data structure improvements
* Rename template parameter N to InlineBufferCapacity
* Expose InlineBufferCapacity parameter for Set and Map
* Add some comments
* Fixed an error that I introduced recently
===================================================================
M source/blender/blenlib/BLI_array.hh
M source/blender/blenlib/BLI_map.hh
M source/blender/blenlib/BLI_open_addressing.hh
M source/blender/blenlib/BLI_set.hh
M source/blender/blenlib/BLI_stack.hh
M source/blender/blenlib/BLI_vector.hh
M source/blender/blenlib/BLI_vector_set.hh
M tests/gtests/blenlib/BLI_set_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index c6536f6c1ed..61d57599619 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -31,12 +31,13 @@
namespace BLI {
-template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Array {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Array {
private:
T *m_data;
uint m_size;
Allocator m_allocator;
- AlignedBuffer<sizeof(T) * N, alignof(T)> m_inline_storage;
+ AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage;
public:
Array()
@@ -204,7 +205,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ar
private:
T *get_buffer_for_size(uint size)
{
- if (size <= N) {
+ if (size <= InlineBufferCapacity) {
return this->inline_storage();
}
else {
diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh
index 626c971c959..4e8c9f67338 100644
--- a/source/blender/blenlib/BLI_map.hh
+++ b/source/blender/blenlib/BLI_map.hh
@@ -53,7 +53,11 @@ namespace BLI {
// clang-format on
-template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator> class Map {
+template<typename KeyT,
+ typename ValueT,
+ uint32_t InlineBufferCapacity = 4,
+ typename Allocator = GuardedAllocator>
+class Map {
private:
static constexpr uint OFFSET_MASK = 3;
static constexpr uint OFFSET_SHIFT = 2;
@@ -65,8 +69,8 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
static constexpr uint8_t IS_DUMMY = 2;
uint8_t m_status[4];
- char m_keys[4 * sizeof(KeyT)];
- char m_values[4 * sizeof(ValueT)];
+ AlignedBuffer<4 * sizeof(KeyT), alignof(KeyT)> m_keys_buffer;
+ AlignedBuffer<4 * sizeof(ValueT), alignof(ValueT)> m_values_buffer;
public:
static constexpr uint slots_per_item = 4;
@@ -134,12 +138,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
KeyT *key(uint offset) const
{
- return (KeyT *)(m_keys + offset * sizeof(KeyT));
+ return (KeyT *)m_keys_buffer.ptr() + offset;
}
ValueT *value(uint offset) const
{
- return (ValueT *)(m_values + offset * sizeof(ValueT));
+ return (ValueT *)m_values_buffer.ptr() + offset;
}
template<typename ForwardKeyT, typename ForwardValueT>
@@ -167,7 +171,7 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
}
};
- using ArrayType = OpenAddressingArray<Item, 1, Allocator>;
+ using ArrayType = OpenAddressingArray<Item, InlineBufferCapacity, Allocator>;
ArrayType m_array;
public:
@@ -351,6 +355,12 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
ITER_SLOTS_END(offset);
}
+ ValueT *lookup_ptr(const KeyT &key)
+ {
+ const Map *const_this = this;
+ return const_cast<ValueT *>(const_this->lookup_ptr(key));
+ }
+
/**
* Lookup the value that corresponds to the key.
* Asserts when the key does not exist.
@@ -362,12 +372,6 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
return *ptr;
}
- ValueT *lookup_ptr(const KeyT &key)
- {
- const Map *const_this = this;
- return const_cast<ValueT *>(const_this->lookup_ptr(key));
- }
-
ValueT &lookup(const KeyT &key)
{
const Map *const_this = this;
@@ -413,6 +417,9 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
return m_array.slots_set();
}
+ /**
+ * Calls the given function for each key-value-pair.
+ */
template<typename FuncT> void foreach_item(const FuncT &func) const
{
for (const Item &item : m_array) {
diff --git a/source/blender/blenlib/BLI_open_addressing.hh b/source/blender/blenlib/BLI_open_addressing.hh
index 7b8adcf9bd2..d466a915b2f 100644
--- a/source/blender/blenlib/BLI_open_addressing.hh
+++ b/source/blender/blenlib/BLI_open_addressing.hh
@@ -40,15 +40,76 @@
namespace BLI {
-template<typename Item, uint32_t ItemsInSmallStorage = 1, typename Allocator = GuardedAllocator>
+/** \name Constexpr utility functions.
+ * \{ */
+
+inline constexpr int is_power_of_2_i_constexpr(int n)
+{
+ return (n & (n - 1)) == 0;
+}
+
+inline constexpr uint32_t log2_floor_u_constexpr(uint32_t x)
+{
+ return x <= 1 ? 0 : 1 + log2_floor_u_constexpr(x >> 1);
+}
+
+inline constexpr uint32_t log2_ceil_u_constexpr(uint32_t x)
+{
+ return (is_power_of_2_i_constexpr((int)x)) ? log2_floor_u_constexpr(x) :
+ log2_floor_u_constexpr(x) + 1;
+}
+
+template<typename IntT> inline constexpr IntT ceil_division(IntT x, IntT y)
+{
+ BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
+ return x / y + ((x % y) != 0);
+}
+
+template<typename IntT> inline constexpr IntT floor_division(IntT x, IntT y)
+{
+ BLI_STATIC_ASSERT(!std::is_signed<IntT>::value, "");
+ return x / y;
+}
+
+inline constexpr uint8_t compute_item_exponent(uint32_t min_usable_slots,
+ uint32_t slots_per_item,
+ uint32_t max_load_factor_numerator,
+ uint32_t max_load_factor_denominator)
+{
+ // uint64_t min_total_slots = ceil_division((uint64_t)min_usable_slots *
+ // (uint64_t)max_load_factor_denominator,
+ // (uint64_t)max_load_factor_numerator);
+ // uint32_t min_total_items = (uint32_t)ceil_division(min_total_slots, (uint64_t)slots_per_item);
+ // uint8_t item_exponent = (uint8_t)log2_ceil_u_constexpr(min_total_items);
+ // return item_exponent;
+
+ return (uint8_t)log2_ceil_u_constexpr((uint32_t)ceil_division(
+ ceil_division((uint64_t)min_usable_slots * (uint64_t)max_load_factor_denominator,
+ (uint64_t)max_load_factor_numerator),
+ (uint64_t)slots_per_item));
+}
+
+/** \} */
+
+template<typename Item,
+ uint32_t MinUsableSlotsInSmallStorage = 1,
+ typename Allocator = GuardedAllocator>
class OpenAddressingArray {
private:
- static constexpr uint32_t slots_per_item = Item::slots_per_item;
- static constexpr float max_load_factor = 0.5f;
+ static constexpr uint32_t s_max_load_factor_numerator = 1;
+ static constexpr uint32_t s_max_load_factor_denominator = 2;
+ static constexpr uint32_t s_slots_per_item = Item::slots_per_item;
+
+ static constexpr uint8_t s_small_storage_item_exponent = compute_item_exponent(
+ MinUsableSlotsInSmallStorage,
+ s_slots_per_item,
+ s_max_load_factor_numerator,
+ s_max_load_factor_denominator);
+ static constexpr uint32_t s_items_in_small_storage = 1u << s_small_storage_item_exponent;
/* Invariants:
* 2^m_item_exponent = m_item_amount
- * m_item_amount * slots_per_item = m_slots_total
+ * m_item_amount * s_slots_per_item = m_slots_total
* m_slot_mask = m_slots_total - 1
* m_slots_set_or_dummy < m_slots_total
*/
@@ -70,20 +131,23 @@ class OpenAddressingArray {
/* Can be used to map a hash value into the range of valid slot indices. */
uint32_t m_slot_mask;
Allocator m_allocator;
- AlignedBuffer<(uint)sizeof(Item) * ItemsInSmallStorage, (uint)alignof(Item)> m_local_storage;
+ AlignedBuffer<(uint)sizeof(Item) * s_items_in_small_storage, (uint)alignof(Item)>
+ m_local_storage;
public:
- explicit OpenAddressingArray(uint8_t item_exponent = 0)
+ explicit OpenAddressingArray(uint8_t item_exponent = s_small_storage_item_exponent)
{
- m_slots_total = ((uint32_t)1 << item_exponent) * slots_per_item;
+ m_item_exponent = item_exponent;
+ m_item_amount = 1u << item_exponent;
+ m_slots_total = m_item_amount * s_slots_per_item;
+ m_slot_mask = m_slots_total - 1;
m_slots_set_or_dummy = 0;
m_slots_dummy = 0;
- m_slots_usable = (uint32_t)((float)m_slots_total * max_load_factor);
- m_slot_mask = m_slots_total - 1;
- m_item_amount = m_slots_total / slots_per_item;
- m_item_exponent = item_exponent;
+ m_slots_usable = (uint32_t)floor_division((uint64_t)m_slots_total *
+ (uint64_t)s_max_load_factor_numerator,
+ (uint64_t)s_max_load_factor_denominator);
- if (m_item_amount <= ItemsInSmallStorage) {
+ if (m_item_amount <= s_items_in_small_storage) {
m_items = this->small_storage();
}
else {
@@ -118,7 +182,7 @@ class OpenAddressingArray {
m_item_amount = other.m_item_amount;
m_item_exponent = other.m_item_exponent;
- if (m_item_amount <= ItemsInSmallStorage) {
+ if (m_item_amount <= s_items_in_small_storage) {
m_items = this->small_storage();
}
else {
@@ -180,9 +244,10 @@ class OpenAddressingArray {
* empty. */
OpenAddressingArray init_reserved(uint32_t min_usable_slots) const
{
- float min_total_slots = (float)min_usable_slots / max_load_factor;
- uint32_t min_total_items = (uint32_t)std::ceil(min_total_slots / (float)slots_per_item);
- uint8_t item_exponent = (uint8_t)log2_ceil_u(min_total_items);
+ uint8_t item_exponent = compute_item_exponent(min_usable_slots,
+ s_slots_per_item,
+ s_max_load_factor_numerator,
+ s_max_load_factor_denominator);
OpenAddressingArray grown(item_exponent);
grown.m_slots_set_or_dummy = this->slots_set();
return grown;
diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh
index 2ef92bf1c48..b09dd910007 100644
--- a/source/blender/blenlib/BLI_set.hh
+++ b/source/blender/blenlib/BLI_set.hh
@@ -50,7 +50,8 @@ namespace BLI {
// clang-format on
-template<typename T, typename Allocator = GuardedAllocator> class Set {
+template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+class Set {
private:
static constexpr uint OFFSET_MASK = 3;
s
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list