diff options
Diffstat (limited to 'source/blender/blenlib/BLI_map.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_map.hh | 441 |
1 files changed, 197 insertions, 244 deletions
diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh index 9737367ebca..dd375272fdb 100644 --- a/source/blender/blenlib/BLI_map.hh +++ b/source/blender/blenlib/BLI_map.hh @@ -67,13 +67,13 @@ * interface as blender::Map. This is useful for benchmarking. */ +#include <optional> #include <unordered_map> #include "BLI_array.hh" #include "BLI_hash.hh" #include "BLI_hash_tables.hh" #include "BLI_map_slots.hh" -#include "BLI_optional.hh" #include "BLI_probing_strategies.hh" namespace blender { @@ -92,13 +92,10 @@ template< * The minimum number of elements that can be stored in this Map without doing a heap * allocation. This is useful when you expect to have many small maps. However, keep in mind * that (unlike vector) initializing a map has a O(n) cost in the number of slots. - * - * When Key or Value are large, the small buffer optimization is disabled by default to avoid - * large unexpected allocations on the stack. It can still be enabled explicitely though. */ - uint32_t InlineBufferCapacity = (sizeof(Key) + sizeof(Value) < 100) ? 4 : 0, + int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) + sizeof(Value)), /** - * The strategy used to deal with collistions. They are defined in BLI_probing_strategies.hh. + * The strategy used to deal with collisions. They are defined in BLI_probing_strategies.hh. */ typename ProbingStrategy = DefaultProbingStrategy, /** @@ -129,30 +126,30 @@ class Map { * Slots are either empty, occupied or removed. The number of occupied slots can be computed by * subtracting the removed slots from the occupied-and-removed slots. */ - uint32_t m_removed_slots; - uint32_t m_occupied_and_removed_slots; + int64_t removed_slots_; + int64_t occupied_and_removed_slots_; /** * The maximum number of slots that can be used (either occupied or removed) until the set has to * grow. This is the total number of slots times the max load factor. */ - uint32_t m_usable_slots; + int64_t usable_slots_; /** * The number of slots minus one. This is a bit mask that can be used to turn any integer into a * valid slot index efficiently. */ - uint32_t m_slot_mask; + uint64_t slot_mask_; /** This is called to hash incoming keys. */ - Hash m_hash; + Hash hash_; /** This is called to check equality of two keys. */ - IsEqual m_is_equal; + IsEqual is_equal_; /** The max load factor is 1/2 = 50% by default. */ #define LOAD_FACTOR 1, 2 - LoadFactor m_max_load_factor = LoadFactor(LOAD_FACTOR); + LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR); using SlotArray = Array<Slot, LoadFactor::compute_total_slots(InlineBufferCapacity, LOAD_FACTOR), Allocator>; #undef LOAD_FACTOR @@ -161,12 +158,12 @@ class Map { * This is the array that contains the actual slots. There is always at least one empty slot and * the size of the array is a power of two. */ - SlotArray m_slots; + SlotArray slots_; /** Iterate over a slot index sequence for a given hash. */ #define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT) \ - SLOT_PROBING_BEGIN (ProbingStrategy, HASH, m_slot_mask, SLOT_INDEX) \ - auto &R_SLOT = m_slots[SLOT_INDEX]; + SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \ + auto &R_SLOT = slots_[SLOT_INDEX]; #define MAP_SLOT_PROBING_END() SLOT_PROBING_END() public: @@ -176,13 +173,13 @@ class Map { * operation is performed on the first insertion. */ Map() - : m_removed_slots(0), - m_occupied_and_removed_slots(0), - m_usable_slots(0), - m_slot_mask(0), - m_hash(), - m_is_equal(), - m_slots(1) + : removed_slots_(0), + occupied_and_removed_slots_(0), + usable_slots_(0), + slot_mask_(0), + hash_(), + is_equal_(), + slots_(1) { } @@ -191,13 +188,13 @@ class Map { Map(const Map &other) = default; Map(Map &&other) noexcept - : m_removed_slots(other.m_removed_slots), - m_occupied_and_removed_slots(other.m_occupied_and_removed_slots), - m_usable_slots(other.m_usable_slots), - m_slot_mask(other.m_slot_mask), - m_hash(std::move(other.m_hash)), - m_is_equal(std::move(other.m_is_equal)), - m_slots(std::move(other.m_slots)) + : removed_slots_(other.removed_slots_), + occupied_and_removed_slots_(other.occupied_and_removed_slots_), + usable_slots_(other.usable_slots_), + slot_mask_(other.slot_mask_), + hash_(std::move(other.hash_)), + is_equal_(std::move(other.is_equal_)), + slots_(std::move(other.slots_)) { other.~Map(); new (&other) Map(); @@ -233,19 +230,19 @@ class Map { */ void add_new(const Key &key, const Value &value) { - this->add_new__impl(key, value, m_hash(key)); + this->add_new__impl(key, value, hash_(key)); } void add_new(const Key &key, Value &&value) { - this->add_new__impl(key, std::move(value), m_hash(key)); + this->add_new__impl(key, std::move(value), hash_(key)); } void add_new(Key &&key, const Value &value) { - this->add_new__impl(std::move(key), value, m_hash(key)); + this->add_new__impl(std::move(key), value, hash_(key)); } void add_new(Key &&key, Value &&value) { - this->add_new__impl(std::move(key), std::move(value), m_hash(key)); + this->add_new__impl(std::move(key), std::move(value), hash_(key)); } /** @@ -271,15 +268,11 @@ class Map { { return this->add_as(std::move(key), std::move(value)); } - - /** - * Same as `add`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey, typename ForwardValue> bool add_as(ForwardKey &&key, ForwardValue &&value) { return this->add__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), m_hash(key)); + std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); } /** @@ -305,15 +298,11 @@ class Map { { return this->add_overwrite_as(std::move(key), std::move(value)); } - - /** - * Same as `add_overwrite`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey, typename ForwardValue> bool add_overwrite_as(ForwardKey &&key, ForwardValue &&value) { return this->add_overwrite__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), m_hash(key)); + std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); } /** @@ -325,13 +314,9 @@ class Map { { return this->contains_as(key); } - - /** - * Same as `contains`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey> bool contains_as(const ForwardKey &key) const { - return this->contains__impl(key, m_hash(key)); + return this->contains__impl(key, hash_(key)); } /** @@ -344,13 +329,9 @@ class Map { { return this->remove_as(key); } - - /** - * Same as `remove`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey> bool remove_as(const ForwardKey &key) { - return this->remove__impl(key, m_hash(key)); + return this->remove__impl(key, hash_(key)); } /** @@ -361,14 +342,9 @@ class Map { { this->remove_contained_as(key); } - - /** - * Same as `remove_contained`, but accepts other key types that are supported by the hash - * function. - */ template<typename ForwardKey> void remove_contained_as(const ForwardKey &key) { - this->remove_contained__impl(key, m_hash(key)); + this->remove_contained__impl(key, hash_(key)); } /** @@ -379,30 +355,22 @@ class Map { { return this->pop_as(key); } - - /** - * Same as `pop`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey> Value pop_as(const ForwardKey &key) { - return this->pop__impl(key, m_hash(key)); + return this->pop__impl(key, hash_(key)); } /** * Get the value that is stored for the given key and remove it from the map. If the key is not * in the map, a value-less optional is returned. */ - Optional<Value> pop_try(const Key &key) + std::optional<Value> pop_try(const Key &key) { return this->pop_try_as(key); } - - /** - * Same as `pop_try`, but accepts other key types that are supported by the hash function. - */ - template<typename ForwardKey> Optional<Value> pop_try_as(const ForwardKey &key) + template<typename ForwardKey> std::optional<Value> pop_try_as(const ForwardKey &key) { - return this->pop_try__impl(key, m_hash(key)); + return this->pop_try__impl(key, hash_(key)); } /** @@ -417,14 +385,10 @@ class Map { { return this->pop_default_as(key, std::move(default_value)); } - - /** - * Same as `pop_default`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey, typename ForwardValue> Value pop_default_as(const ForwardKey &key, ForwardValue &&default_value) { - return this->pop_default__impl(key, std::forward<ForwardValue>(default_value), m_hash(key)); + return this->pop_default__impl(key, std::forward<ForwardValue>(default_value), hash_(key)); } /** @@ -460,17 +424,13 @@ class Map { { return this->add_or_modify_as(std::move(key), create_value, modify_value); } - - /** - * Same as `add_or_modify`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey, typename CreateValueF, typename ModifyValueF> auto add_or_modify_as(ForwardKey &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr)) { return this->add_or_modify__impl( - std::forward<Key>(key), create_value, modify_value, m_hash(key)); + std::forward<ForwardKey>(key), create_value, modify_value, hash_(key)); } /** @@ -487,17 +447,13 @@ class Map { { return this->lookup_ptr_as(key); } - - /** - * Same as `lookup_ptr`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey> const Value *lookup_ptr_as(const ForwardKey &key) const { - return this->lookup_ptr__impl(key, m_hash(key)); + return this->lookup_ptr__impl(key, hash_(key)); } template<typename ForwardKey> Value *lookup_ptr_as(const ForwardKey &key) { - return const_cast<Value *>(this->lookup_ptr__impl(key, m_hash(key))); + return const_cast<Value *>(this->lookup_ptr__impl(key, hash_(key))); } /** @@ -512,10 +468,6 @@ class Map { { return this->lookup_as(key); } - - /** - * Same as `lookup`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey> const Value &lookup_as(const ForwardKey &key) const { const Value *ptr = this->lookup_ptr_as(key); @@ -537,10 +489,6 @@ class Map { { return this->lookup_default_as(key, default_value); } - - /** - * Same as `lookup_default`, but accepts other key types that are supported by the hash function. - */ template<typename ForwardKey, typename ForwardValue> Value lookup_default_as(const ForwardKey &key, ForwardValue &&default_value) const { @@ -573,16 +521,11 @@ class Map { { return this->lookup_or_add_as(std::move(key), std::move(value)); } - - /** - * Same as `lookup_or_add`, but accepts other key types that are supported by the hash - * function. - */ template<typename ForwardKey, typename ForwardValue> Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&value) { return this->lookup_or_add__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), m_hash(key)); + std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); } /** @@ -602,15 +545,10 @@ class Map { { return this->lookup_or_add_cb_as(std::move(key), create_value); } - - /** - * Same as `lookup_or_add_cb`, but accepts other key types that are supported by the hash - * function. - */ template<typename ForwardKey, typename CreateValueF> Value &lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value) { - return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, m_hash(key)); + return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, hash_(key)); } /** @@ -625,11 +563,6 @@ class Map { { return this->lookup_or_add_default_as(std::move(key)); } - - /** - * Same as `lookup_or_add_default`, but accepts other key types that are supported by the hash - * function. - */ template<typename ForwardKey> Value &lookup_or_add_default_as(ForwardKey &&key) { return this->lookup_or_add_cb_as(std::forward<ForwardKey>(key), []() { return Value(); }); @@ -641,9 +574,9 @@ class Map { */ template<typename FuncT> void foreach_item(const FuncT &func) const { - uint32_t size = this->size(); - for (uint32_t i = 0; i < size; i++) { - const Slot &slot = m_slots[i]; + int64_t size = slots_.size(); + for (int64_t i = 0; i < size; i++) { + const Slot &slot = slots_[i]; if (slot.is_occupied()) { const Key &key = *slot.key(); const Value &value = *slot.value(); @@ -657,21 +590,19 @@ class Map { * This uses the "curiously recurring template pattern" (CRTP). */ template<typename SubIterator> struct BaseIterator { - Slot *m_slots; - uint32_t m_total_slots; - uint32_t m_current_slot; - - BaseIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) - : m_slots(const_cast<Slot *>(slots)), - m_total_slots(total_slots), - m_current_slot(current_slot) + Slot *slots_; + int64_t total_slots_; + int64_t current_slot_; + + BaseIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) + : slots_(const_cast<Slot *>(slots)), total_slots_(total_slots), current_slot_(current_slot) { } BaseIterator &operator++() { - while (++m_current_slot < m_total_slots) { - if (m_slots[m_current_slot].is_occupied()) { + while (++current_slot_ < total_slots_) { + if (slots_[current_slot_].is_occupied()) { break; } } @@ -680,16 +611,16 @@ class Map { friend bool operator!=(const BaseIterator &a, const BaseIterator &b) { - BLI_assert(a.m_slots == b.m_slots); - BLI_assert(a.m_total_slots == b.m_total_slots); - return a.m_current_slot != b.m_current_slot; + BLI_assert(a.slots_ == b.slots_); + BLI_assert(a.total_slots_ == b.total_slots_); + return a.current_slot_ != b.current_slot_; } SubIterator begin() const { - for (uint32_t i = 0; i < m_total_slots; i++) { - if (m_slots[i].is_occupied()) { - return SubIterator(m_slots, m_total_slots, i); + for (int64_t i = 0; i < total_slots_; i++) { + if (slots_[i].is_occupied()) { + return SubIterator(slots_, total_slots_, i); } } return this->end(); @@ -697,18 +628,18 @@ class Map { SubIterator end() const { - return SubIterator(m_slots, m_total_slots, m_total_slots); + return SubIterator(slots_, total_slots_, total_slots_); } Slot ¤t_slot() const { - return m_slots[m_current_slot]; + return slots_[current_slot_]; } }; class KeyIterator final : public BaseIterator<KeyIterator> { public: - KeyIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) + KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) : BaseIterator<KeyIterator>(slots, total_slots, current_slot) { } @@ -721,7 +652,7 @@ class Map { class ValueIterator final : public BaseIterator<ValueIterator> { public: - ValueIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) + ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) : BaseIterator<ValueIterator>(slots, total_slots, current_slot) { } @@ -734,7 +665,7 @@ class Map { class MutableValueIterator final : public BaseIterator<MutableValueIterator> { public: - MutableValueIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) + MutableValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) : BaseIterator<MutableValueIterator>(slots, total_slots, current_slot) { } @@ -745,18 +676,28 @@ class Map { } }; + struct Item { + const Key &key; + const Value &value; + }; + + struct MutableItem { + const Key &key; + Value &value; + + operator Item() const + { + return Item{key, value}; + } + }; + class ItemIterator final : public BaseIterator<ItemIterator> { public: - ItemIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) + ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) : BaseIterator<ItemIterator>(slots, total_slots, current_slot) { } - struct Item { - const Key &key; - const Value &value; - }; - Item operator*() const { const Slot &slot = this->current_slot(); @@ -766,17 +707,12 @@ class Map { class MutableItemIterator final : public BaseIterator<MutableItemIterator> { public: - MutableItemIterator(const Slot *slots, uint32_t total_slots, uint32_t current_slot) + MutableItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot) : BaseIterator<MutableItemIterator>(slots, total_slots, current_slot) { } - struct Item { - const Key &key; - Value &value; - }; - - Item operator*() const + MutableItem operator*() const { Slot &slot = this->current_slot(); return {*slot.key(), *slot.value()}; @@ -789,7 +725,7 @@ class Map { */ KeyIterator keys() const { - return KeyIterator(m_slots.data(), m_slots.size(), 0); + return KeyIterator(slots_.data(), slots_.size(), 0); } /** @@ -798,7 +734,7 @@ class Map { */ ValueIterator values() const { - return ValueIterator(m_slots.data(), m_slots.size(), 0); + return ValueIterator(slots_.data(), slots_.size(), 0); } /** @@ -807,7 +743,7 @@ class Map { */ MutableValueIterator values() { - return MutableValueIterator(m_slots.data(), m_slots.size(), 0); + return MutableValueIterator(slots_.data(), slots_.size(), 0); } /** @@ -817,7 +753,7 @@ class Map { */ ItemIterator items() const { - return ItemIterator(m_slots.data(), m_slots.size(), 0); + return ItemIterator(slots_.data(), slots_.size(), 0); } /** @@ -829,7 +765,7 @@ class Map { */ MutableItemIterator items() { - return MutableItemIterator(m_slots.data(), m_slots.size(), 0); + return MutableItemIterator(slots_.data(), slots_.size(), 0); } /** @@ -838,15 +774,15 @@ class Map { void print_stats(StringRef name = "") const { HashTableStats stats(*this, this->keys()); - stats.print(); + stats.print(name); } /** * Return the number of key-value-pairs that are stored in the map. */ - uint32_t size() const + int64_t size() const { - return m_occupied_and_removed_slots - m_removed_slots; + return occupied_and_removed_slots_ - removed_slots_; } /** @@ -856,29 +792,29 @@ class Map { */ bool is_empty() const { - return m_occupied_and_removed_slots == m_removed_slots; + return occupied_and_removed_slots_ == removed_slots_; } /** * Returns the number of available slots. This is mostly for debugging purposes. */ - uint32_t capacity() const + int64_t capacity() const { - return m_slots.size(); + return slots_.size(); } /** * Returns the amount of removed slots in the set. This is mostly for debugging purposes. */ - uint32_t removed_amount() const + int64_t removed_amount() const { - return m_removed_slots; + return removed_slots_; } /** * Returns the bytes required per element. This is mostly for debugging purposes. */ - uint32_t size_per_element() const + int64_t size_per_element() const { return sizeof(Slot); } @@ -887,18 +823,18 @@ class Map { * Returns the approximate memory requirements of the map in bytes. This becomes more exact the * larger the map becomes. */ - uint32_t size_in_bytes() const + int64_t size_in_bytes() const { - return sizeof(Slot) * m_slots.size(); + return (int64_t)(sizeof(Slot) * slots_.size()); } /** * Potentially resize the map such that the specified number of elements can be added without * another grow operation. */ - void reserve(uint32_t n) + void reserve(int64_t n) { - if (m_usable_slots < n) { + if (usable_slots_ < n) { this->realloc_and_reinsert(n); } } @@ -916,35 +852,36 @@ class Map { * Get the number of collisions that the probing strategy has to go through to find the key or * determine that it is not in the map. */ - uint32_t count_collisions(const Key &key) const + int64_t count_collisions(const Key &key) const { - return this->count_collisions__impl(key, m_hash(key)); + return this->count_collisions__impl(key, hash_(key)); } private: - BLI_NOINLINE void realloc_and_reinsert(uint32_t min_usable_slots) + BLI_NOINLINE void realloc_and_reinsert(int64_t min_usable_slots) { - uint32_t total_slots, usable_slots; - m_max_load_factor.compute_total_and_usable_slots( + int64_t total_slots, usable_slots; + max_load_factor_.compute_total_and_usable_slots( SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots); - uint32_t new_slot_mask = total_slots - 1; + BLI_assert(total_slots >= 1); + const uint64_t new_slot_mask = (uint64_t)total_slots - 1; /** * Optimize the case when the map was empty beforehand. We can avoid some copies here. */ if (this->size() == 0) { - m_slots.~Array(); - new (&m_slots) SlotArray(total_slots); - m_removed_slots = 0; - m_occupied_and_removed_slots = 0; - m_usable_slots = usable_slots; - m_slot_mask = new_slot_mask; + slots_.~Array(); + new (&slots_) SlotArray(total_slots); + removed_slots_ = 0; + occupied_and_removed_slots_ = 0; + usable_slots_ = usable_slots; + slot_mask_ = new_slot_mask; return; } SlotArray new_slots(total_slots); - for (Slot &slot : m_slots) { + for (Slot &slot : slots_) { if (slot.is_occupied()) { this->add_after_grow_and_destruct_old(slot, new_slots, new_slot_mask); } @@ -952,19 +889,19 @@ class Map { /* All occupied slots have been destructed already and empty/removed slots are assumed to be * trivially destructible. */ - m_slots.clear_without_destruct(); - m_slots = std::move(new_slots); - m_occupied_and_removed_slots -= m_removed_slots; - m_usable_slots = usable_slots; - m_removed_slots = 0; - m_slot_mask = new_slot_mask; + slots_.clear_without_destruct(); + slots_ = std::move(new_slots); + occupied_and_removed_slots_ -= removed_slots_; + usable_slots_ = usable_slots; + removed_slots_ = 0; + slot_mask_ = new_slot_mask; } void add_after_grow_and_destruct_old(Slot &old_slot, SlotArray &new_slots, - uint32_t new_slot_mask) + uint64_t new_slot_mask) { - uint32_t hash = old_slot.get_hash(Hash()); + uint64_t hash = old_slot.get_hash(Hash()); SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) { Slot &slot = new_slots[slot_index]; if (slot.is_empty()) { @@ -975,13 +912,13 @@ class Map { SLOT_PROBING_END(); } - template<typename ForwardKey> bool contains__impl(const ForwardKey &key, uint32_t hash) const + template<typename ForwardKey> bool contains__impl(const ForwardKey &key, uint64_t hash) const { MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { return false; } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return true; } } @@ -989,12 +926,12 @@ class Map { } template<typename ForwardKey, typename ForwardValue> - void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint32_t hash) + void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) { BLI_assert(!this->contains_as(key)); this->ensure_can_add(); - m_occupied_and_removed_slots++; + occupied_and_removed_slots_++; MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { @@ -1006,29 +943,29 @@ class Map { } template<typename ForwardKey, typename ForwardValue> - bool add__impl(ForwardKey &&key, ForwardValue &&value, uint32_t hash) + bool add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) { this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash); - m_occupied_and_removed_slots++; + occupied_and_removed_slots_++; return true; } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return false; } } MAP_SLOT_PROBING_END(); } - template<typename ForwardKey> bool remove__impl(const ForwardKey &key, uint32_t hash) + template<typename ForwardKey> bool remove__impl(const ForwardKey &key, uint64_t hash) { MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { slot.remove(); - m_removed_slots++; + removed_slots_++; return true; } if (slot.is_empty()) { @@ -1038,14 +975,14 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey> void remove_contained__impl(const ForwardKey &key, uint32_t hash) + template<typename ForwardKey> void remove_contained__impl(const ForwardKey &key, uint64_t hash) { BLI_assert(this->contains_as(key)); - m_removed_slots++; + removed_slots_++; MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { slot.remove(); return; } @@ -1053,14 +990,14 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey> Value pop__impl(const ForwardKey &key, uint32_t hash) + template<typename ForwardKey> Value pop__impl(const ForwardKey &key, uint64_t hash) { BLI_assert(this->contains_as(key)); - m_removed_slots++; + removed_slots_++; MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { Value value = std::move(*slot.value()); slot.remove(); return value; @@ -1069,13 +1006,14 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey> Optional<Value> pop_try__impl(const ForwardKey &key, uint32_t hash) + template<typename ForwardKey> + std::optional<Value> pop_try__impl(const ForwardKey &key, uint64_t hash) { MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { - Optional<Value> value = std::move(*slot.value()); + if (slot.contains(key, is_equal_, hash)) { + std::optional<Value> value = std::move(*slot.value()); slot.remove(); - m_removed_slots++; + removed_slots_++; return value; } if (slot.is_empty()) { @@ -1086,13 +1024,13 @@ class Map { } template<typename ForwardKey, typename ForwardValue> - Value pop_default__impl(const ForwardKey &key, ForwardValue &&default_value, uint32_t hash) + Value pop_default__impl(const ForwardKey &key, ForwardValue &&default_value, uint64_t hash) { MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { Value value = std::move(*slot.value()); slot.remove(); - m_removed_slots++; + removed_slots_++; return value; } if (slot.is_empty()) { @@ -1106,23 +1044,23 @@ class Map { auto add_or_modify__impl(ForwardKey &&key, const CreateValueF &create_value, const ModifyValueF &modify_value, - uint32_t hash) -> decltype(create_value(nullptr)) + uint64_t hash) -> decltype(create_value(nullptr)) { using CreateReturnT = decltype(create_value(nullptr)); using ModifyReturnT = decltype(modify_value(nullptr)); - BLI_STATIC_ASSERT((std::is_same<CreateReturnT, ModifyReturnT>::value), + BLI_STATIC_ASSERT((std::is_same_v<CreateReturnT, ModifyReturnT>), "Both callbacks should return the same type."); this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { - m_occupied_and_removed_slots++; + occupied_and_removed_slots_++; slot.occupy_without_value(std::forward<ForwardKey>(key), hash); Value *value_ptr = slot.value(); return create_value(value_ptr); } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { Value *value_ptr = slot.value(); return modify_value(value_ptr); } @@ -1131,17 +1069,17 @@ class Map { } template<typename ForwardKey, typename CreateValueF> - Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint32_t hash) + Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint64_t hash) { this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { slot.occupy(std::forward<ForwardKey>(key), create_value(), hash); - m_occupied_and_removed_slots++; + occupied_and_removed_slots_++; return *slot.value(); } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return *slot.value(); } } @@ -1149,17 +1087,17 @@ class Map { } template<typename ForwardKey, typename ForwardValue> - Value &lookup_or_add__impl(ForwardKey &&key, ForwardValue &&value, uint32_t hash) + Value &lookup_or_add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) { this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash); - m_occupied_and_removed_slots++; + occupied_and_removed_slots_++; return *slot.value(); } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return *slot.value(); } } @@ -1167,10 +1105,10 @@ class Map { } template<typename ForwardKey, typename ForwardValue> - bool add_overwrite__impl(ForwardKey &&key, ForwardValue &&value, uint32_t hash) + bool add_overwrite__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) { auto create_func = [&](Value *ptr) { - new (ptr) Value(std::forward<ForwardValue>(value)); + new ((void *)ptr) Value(std::forward<ForwardValue>(value)); return true; }; auto modify_func = [&](Value *ptr) { @@ -1182,13 +1120,13 @@ class Map { } template<typename ForwardKey> - const Value *lookup_ptr__impl(const ForwardKey &key, uint32_t hash) const + const Value *lookup_ptr__impl(const ForwardKey &key, uint64_t hash) const { MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { return nullptr; } - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return slot.value(); } } @@ -1196,12 +1134,12 @@ class Map { } template<typename ForwardKey> - uint32_t count_collisions__impl(const ForwardKey &key, uint32_t hash) const + int64_t count_collisions__impl(const ForwardKey &key, uint64_t hash) const { - uint32_t collisions = 0; + int64_t collisions = 0; MAP_SLOT_PROBING_BEGIN (hash, slot) { - if (slot.contains(key, m_is_equal, hash)) { + if (slot.contains(key, is_equal_, hash)) { return collisions; } if (slot.is_empty()) { @@ -1214,73 +1152,88 @@ class Map { void ensure_can_add() { - if (m_occupied_and_removed_slots >= m_usable_slots) { + if (occupied_and_removed_slots_ >= usable_slots_) { this->realloc_and_reinsert(this->size() + 1); - BLI_assert(m_occupied_and_removed_slots < m_usable_slots); + BLI_assert(occupied_and_removed_slots_ < usable_slots_); } } }; /** + * Same as a normal Map, but does not use Blender's guarded allocator. This is useful when + * allocating memory with static storage duration. + */ +template<typename Key, + typename Value, + int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) + + sizeof(Value)), + typename ProbingStrategy = DefaultProbingStrategy, + typename Hash = DefaultHash<Key>, + typename IsEqual = DefaultEquality, + typename Slot = typename DefaultMapSlot<Key, Value>::type> +using RawMap = + Map<Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator>; + +/** * A wrapper for std::unordered_map with the API of blender::Map. This can be used for * benchmarking. */ template<typename Key, typename Value> class StdUnorderedMapWrapper { private: using MapType = std::unordered_map<Key, Value, blender::DefaultHash<Key>>; - MapType m_map; + MapType map_; public: - uint32_t size() const + int64_t size() const { - return (uint32_t)m_map.size(); + return (int64_t)map_.size(); } bool is_empty() const { - return m_map.empty(); + return map_.empty(); } - void reserve(uint32_t n) + void reserve(int64_t n) { - m_map.reserve(n); + map_.reserve(n); } template<typename ForwardKey, typename ForwardValue> void add_new(ForwardKey &&key, ForwardValue &&value) { - m_map.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}); + map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}); } template<typename ForwardKey, typename ForwardValue> bool add(ForwardKey &&key, ForwardValue &&value) { - return m_map.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}).second; + return map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}).second; } bool contains(const Key &key) const { - return m_map.find(key) != m_map.end(); + return map_.find(key) != map_.end(); } bool remove(const Key &key) { - return (bool)m_map.erase(key); + return (bool)map_.erase(key); } Value &lookup(const Key &key) { - return m_map.find(key)->second; + return map_.find(key)->second; } const Value &lookup(const Key &key) const { - return m_map.find(key)->second; + return map_.find(key)->second; } void clear() { - m_map.clear(); + map_.clear(); } void print_stats(StringRef UNUSED(name) = "") const |