56 #include <unordered_map>
90 typename Hash = DefaultHash<Key>,
95 typename IsEqual = DefaultEquality,
118 int64_t occupied_and_removed_slots_;
139 #define LOAD_FACTOR 1, 2
140 LoadFactor max_load_factor_ = LoadFactor(
LOAD_FACTOR);
152 #define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
153 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
154 auto &R_SLOT = slots_[SLOT_INDEX];
155 #define MAP_SLOT_PROBING_END() SLOT_PROBING_END()
163 Map(Allocator allocator = {}) noexcept
165 occupied_and_removed_slots_(0),
182 Map(
Map &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
185 if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
186 slots_ = std::move(other.slots_);
190 slots_ = std::move(other.slots_);
193 other.noexcept_reset();
197 removed_slots_ = other.removed_slots_;
198 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
199 usable_slots_ = other.usable_slots_;
200 slot_mask_ = other.slot_mask_;
201 hash_ = std::move(other.hash_);
202 is_equal_ = std::move(other.is_equal_);
203 other.noexcept_reset();
234 this->
add_new_as(std::move(key), std::move(value));
236 template<
typename ForwardKey,
typename... ForwardValue>
240 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
250 bool add(
const Key &key,
const Value &value)
252 return this->
add_as(key, value);
256 return this->
add_as(key, std::move(value));
260 return this->
add_as(std::move(key), value);
264 return this->
add_as(std::move(key), std::move(value));
266 template<
typename ForwardKey,
typename... ForwardValue>
267 bool add_as(ForwardKey &&key, ForwardValue &&...value)
269 return this->add__impl(
270 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
296 template<
typename ForwardKey,
typename... ForwardValue>
299 return this->add_overwrite__impl(
300 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
312 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
314 return this->lookup_slot_ptr(key, hash_(key)) !=
nullptr;
327 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
329 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
330 if (slot ==
nullptr) {
348 Slot &slot = this->lookup_slot(key, hash_(key));
363 Slot &slot = this->lookup_slot(key, hash_(key));
364 Value value = std::move(*slot.value());
378 template<
typename ForwardKey> std::optional<Value>
pop_try_as(
const ForwardKey &key)
380 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
381 if (slot ==
nullptr) {
384 std::optional<Value> value = std::move(*slot->value());
402 template<
typename ForwardKey,
typename... ForwardValue>
405 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
406 if (slot ==
nullptr) {
407 return Value(std::forward<ForwardValue>(default_value)...);
409 Value value = std::move(*slot->value());
435 template<
typename CreateValueF,
typename ModifyValueF>
437 const CreateValueF &create_value,
438 const ModifyValueF &modify_value) -> decltype(create_value(
nullptr))
442 template<
typename CreateValueF,
typename ModifyValueF>
443 auto add_or_modify(
Key &&key,
const CreateValueF &create_value,
const ModifyValueF &modify_value)
444 -> decltype(create_value(
nullptr))
448 template<
typename ForwardKey,
typename CreateValueF,
typename ModifyValueF>
450 const CreateValueF &create_value,
451 const ModifyValueF &modify_value) -> decltype(create_value(
nullptr))
453 return this->add_or_modify__impl(
454 std::forward<ForwardKey>(key), create_value, modify_value, hash_(key));
473 const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
474 return (slot !=
nullptr) ? slot->value() :
nullptr;
493 template<
typename ForwardKey>
const Value &
lookup_as(
const ForwardKey &key)
const
514 template<
typename ForwardKey,
typename... ForwardValue>
518 if (
ptr !=
nullptr) {
522 return Value(std::forward<ForwardValue>(default_value)...);
546 template<
typename ForwardKey,
typename... ForwardValue>
549 return this->lookup_or_add__impl(
550 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
560 template<
typename CreateValueF>
565 template<
typename CreateValueF>
570 template<
typename ForwardKey,
typename CreateValueF>
573 return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, hash_(key));
603 const Slot &slot = this->lookup_slot(key, hash_(key));
617 const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
618 if (slot ==
nullptr) {
632 const Slot &slot = slots_[i];
633 if (slot.is_occupied()) {
634 const Key &key = *slot.key();
635 const Value &value = *slot.value();
676 return copied_iterator;
683 return a.current_slot_ !=
b.current_slot_;
712 if (this->slots_[i].is_occupied()) {
713 return SubIterator(this->slots_, this->total_slots_, i);
805 return {*slot.key(), *slot.value()};
823 return {*slot.key(), *slot.value()};
833 return KeyIterator(slots_.data(), slots_.size(), 0);
903 return occupied_and_removed_slots_ - removed_slots_;
913 return occupied_and_removed_slots_ == removed_slots_;
921 return slots_.size();
929 return removed_slots_;
946 return static_cast<int64_t>(
sizeof(Slot) * slots_.size());
955 if (usable_slots_ < n) {
956 this->realloc_and_reinsert(n);
965 for (Slot &slot : slots_) {
971 occupied_and_removed_slots_ = 0;
980 return this->count_collisions__impl(key, hash_(key));
986 int64_t total_slots, usable_slots;
987 max_load_factor_.compute_total_and_usable_slots(
995 if (this->
size() == 0) {
997 slots_.reinitialize(total_slots);
1000 this->noexcept_reset();
1004 occupied_and_removed_slots_ = 0;
1005 usable_slots_ = usable_slots;
1006 slot_mask_ = new_slot_mask;
1010 SlotArray new_slots(total_slots);
1013 for (Slot &slot : slots_) {
1014 if (slot.is_occupied()) {
1015 this->add_after_grow(slot, new_slots, new_slot_mask);
1019 slots_ = std::move(new_slots);
1022 this->noexcept_reset();
1026 occupied_and_removed_slots_ -= removed_slots_;
1027 usable_slots_ = usable_slots;
1029 slot_mask_ = new_slot_mask;
1032 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
uint64_t new_slot_mask)
1036 Slot &slot = new_slots[slot_index];
1037 if (slot.is_empty()) {
1038 slot.occupy(std::move(*old_slot.key()),
hash, std::move(*old_slot.value()));
1045 void noexcept_reset() noexcept
1047 Allocator allocator = slots_.allocator();
1049 new (
this)
Map(NoExceptConstructor(), allocator);
1052 template<
typename ForwardKey,
typename... ForwardValue>
1053 void add_new__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1057 this->ensure_can_add();
1060 if (slot.is_empty()) {
1061 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1062 occupied_and_removed_slots_++;
1069 template<
typename ForwardKey,
typename... ForwardValue>
1070 bool add__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1072 this->ensure_can_add();
1075 if (slot.is_empty()) {
1076 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1077 occupied_and_removed_slots_++;
1080 if (slot.contains(key, is_equal_,
hash)) {
1087 template<
typename ForwardKey,
typename CreateValueF,
typename ModifyValueF>
1088 auto add_or_modify__impl(ForwardKey &&key,
1089 const CreateValueF &create_value,
1090 const ModifyValueF &modify_value,
1093 using CreateReturnT = decltype(create_value(
nullptr));
1094 using ModifyReturnT = decltype(modify_value(
nullptr));
1096 "Both callbacks should return the same type.");
1098 this->ensure_can_add();
1101 if (slot.is_empty()) {
1102 Value *value_ptr = slot.value();
1103 if constexpr (std::is_void_v<CreateReturnT>) {
1104 create_value(value_ptr);
1105 slot.occupy_no_value(std::forward<ForwardKey>(key),
hash);
1106 occupied_and_removed_slots_++;
1110 auto &&return_value = create_value(value_ptr);
1111 slot.occupy_no_value(std::forward<ForwardKey>(key),
hash);
1112 occupied_and_removed_slots_++;
1113 return return_value;
1116 if (slot.contains(key, is_equal_,
hash)) {
1117 Value *value_ptr = slot.value();
1118 return modify_value(value_ptr);
1124 template<
typename ForwardKey,
typename CreateValueF>
1125 Value &lookup_or_add_cb__impl(ForwardKey &&key,
const CreateValueF &create_value,
uint64_t hash)
1127 this->ensure_can_add();
1130 if (slot.is_empty()) {
1131 slot.occupy(std::forward<ForwardKey>(key),
hash, create_value());
1132 occupied_and_removed_slots_++;
1133 return *slot.value();
1135 if (slot.contains(key, is_equal_,
hash)) {
1136 return *slot.value();
1142 template<
typename ForwardKey,
typename... ForwardValue>
1143 Value &lookup_or_add__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1145 this->ensure_can_add();
1148 if (slot.is_empty()) {
1149 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1150 occupied_and_removed_slots_++;
1151 return *slot.value();
1153 if (slot.contains(key, is_equal_,
hash)) {
1154 return *slot.value();
1160 template<
typename ForwardKey,
typename... ForwardValue>
1161 bool add_overwrite__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1164 new (
static_cast<void *
>(
ptr))
Value(std::forward<ForwardValue>(value)...);
1167 auto modify_func = [&](
Value *
ptr) {
1168 *
ptr =
Value(std::forward<ForwardValue>(value)...);
1171 return this->add_or_modify__impl(
1175 template<
typename ForwardKey>
1176 const Slot &lookup_slot(
const ForwardKey &key,
const uint64_t hash)
const
1180 if (slot.contains(key, is_equal_,
hash)) {
1187 template<
typename ForwardKey> Slot &lookup_slot(
const ForwardKey &key,
const uint64_t hash)
1189 return const_cast<Slot &
>(
const_cast<const Map *
>(
this)->lookup_slot(key,
hash));
1192 template<
typename ForwardKey>
1193 const Slot *lookup_slot_ptr(
const ForwardKey &key,
const uint64_t hash)
const
1196 if (slot.contains(key, is_equal_,
hash)) {
1199 if (slot.is_empty()) {
1206 template<
typename ForwardKey> Slot *lookup_slot_ptr(
const ForwardKey &key,
const uint64_t hash)
1208 return const_cast<Slot *
>(
const_cast<const Map *
>(
this)->lookup_slot_ptr(key,
hash));
1211 template<
typename ForwardKey>
1217 if (slot.contains(key, is_equal_,
hash)) {
1220 if (slot.is_empty()) {
1228 void ensure_can_add()
1230 if (occupied_and_removed_slots_ >= usable_slots_) {
1231 this->realloc_and_reinsert(this->
size() + 1);
1232 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
1241 template<
typename Key,
1246 typename Hash = DefaultHash<Key>,
1247 typename IsEqual = DefaultEquality,
1258 using MapType = std::unordered_map<Key, Value, blender::DefaultHash<Key>>;
1264 return static_cast<int64_t>(map_.size());
1269 return map_.empty();
1277 template<
typename ForwardKey,
typename... ForwardValue>
1278 void add_new(ForwardKey &&key, ForwardValue &&...value)
1280 map_.insert({std::forward<ForwardKey>(key),
Value(std::forward<ForwardValue>(value)...)});
1283 template<
typename ForwardKey,
typename... ForwardValue>
1284 bool add(ForwardKey &&key, ForwardValue &&...value)
1287 .insert({std::forward<ForwardKey>(key),
Value(std::forward<ForwardValue>(value)...)})
1293 return map_.find(key) != map_.end();
1298 return (
bool)map_.erase(key);
1303 return map_.find(key)->second;
1308 return map_.find(key)->second;
#define BLI_STATIC_ASSERT(a, msg)
#define MAP_SLOT_PROBING_END()
#define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT)
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define BLI_NO_UNIQUE_ADDRESS
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to used to fine tune the interpolation of the input Camera Retrieve information about the camera and how it relates to the current shading point s position Clamp a value between a minimum and a maximum Vector Perform vector math operation Invert a producing a negative Combine Generate a color from its and blue Hue Saturation Value
static int64_t inline_buffer_capacity()
void print(StringRef name="")
static constexpr int64_t compute_total_slots(int64_t min_usable_slots, uint8_t numerator, uint8_t denominator)
SubIterator begin() const
BaseIteratorRange(const Slot *slots, int64_t total_slots, int64_t current_slot)
ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
const Key & operator*() const
MutableItemIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
MutableItem operator*() const
MutableValueIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
const Value & operator*() const
ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
MutableItemIterator items()
Map & operator=(Map &&other)
Value pop_as(const ForwardKey &key)
bool add_overwrite(Key &&key, Value &&value)
Value & lookup_or_add_default_as(ForwardKey &&key)
Value pop_default_as(const ForwardKey &key, ForwardValue &&...default_value)
int64_t size_in_bytes() const
Value pop(const Key &key)
const Key & lookup_key_as(const ForwardKey &key) const
void add_new(const Key &key, Value &&value)
void add_new(Key &&key, const Value &value)
int64_t removed_amount() const
Map(NoExceptConstructor, Allocator allocator={}) noexcept
Value & lookup_as(const ForwardKey &key)
Map & operator=(const Map &other)
bool remove_as(const ForwardKey &key)
bool add_overwrite(const Key &key, const Value &value)
std::optional< Value > pop_try_as(const ForwardKey &key)
Value & lookup_or_add_cb(Key &&key, const CreateValueF &create_value)
bool add(const Key &key, const Value &value)
int64_t size_per_element() const
Value & lookup_or_add(Key &&key, const Value &value)
void remove_contained_as(const ForwardKey &key)
void print_stats(StringRef name="") const
Value lookup_default(const Key &key, const Value &default_value) const
Value & lookup_or_add(Key &&key, Value &&value)
bool add_overwrite(Key &&key, const Value &value)
int64_t count_collisions(const Key &key) const
ValueIterator values() const
MutableValueIterator values()
Value & lookup_or_add_default(Key &&key)
const Value * lookup_ptr_as(const ForwardKey &key) const
const Value & lookup(const Key &key) const
Value * lookup_ptr_as(const ForwardKey &key)
void add_new_as(ForwardKey &&key, ForwardValue &&...value)
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Value & lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value)
void foreach_item(const FuncT &func) const
void remove_contained(const Key &key)
Map(const Map &other)=default
Map(Allocator allocator={}) noexcept
const Key & lookup_key(const Key &key) const
Value & lookup_or_add_default(const Key &key)
const Key * lookup_key_ptr_as(const ForwardKey &key) const
bool add_as(ForwardKey &&key, ForwardValue &&...value)
auto add_or_modify_as(ForwardKey &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
void add_new(Key &&key, Value &&value)
void add_new(const Key &key, const Value &value)
bool add(Key &&key, Value &&value)
Value & lookup_or_add_as(ForwardKey &&key, ForwardValue &&...value)
Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v< SlotArray >)
Value & lookup_or_add(const Key &key, const Value &value)
bool remove(const Key &key)
bool contains_as(const ForwardKey &key) const
ItemIterator items() const
const Value & lookup_as(const ForwardKey &key) const
bool add(const Key &key, Value &&value)
Value & lookup_or_add(const Key &key, Value &&value)
auto add_or_modify(Key &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Value & lookup(const Key &key)
bool add_overwrite_as(ForwardKey &&key, ForwardValue &&...value)
bool contains(const Key &key) const
Value pop_default(const Key &key, Value &&default_value)
bool add(Key &&key, const Value &value)
bool add_overwrite(const Key &key, Value &&value)
Value lookup_default_as(const ForwardKey &key, ForwardValue &&...default_value) const
Value * lookup_ptr(const Key &key)
const Value * lookup_ptr(const Key &key) const
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
const Key * lookup_key_ptr(const Key &key) const
Value pop_default(const Key &key, const Value &default_value)
void remove(const BaseIterator &iterator)
std::optional< Value > pop_try(const Key &key)
const Value & lookup(const Key &key) const
bool contains(const Key &key) const
void print_stats(StringRef UNUSED(name)="") const
void add_new(ForwardKey &&key, ForwardValue &&...value)
bool remove(const Key &key)
Value & lookup(const Key &key)
bool add(ForwardKey &&key, ForwardValue &&...value)
Container & move_assign_container(Container &dst, Container &&src) noexcept(std::is_nothrow_move_constructible_v< Container >)
Container & copy_assign_container(Container &dst, const Container &src)
PythonProbingStrategy<> DefaultProbingStrategy
constexpr int64_t default_inline_buffer_capacity(size_t element_size)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static PyObject * create_func(PyObject *, PyObject *args)
unsigned __int64 uint64_t
SimpleMapSlot< Key, Value > type
friend bool operator==(const BaseIterator &a, const BaseIterator &b)
BaseIterator & operator++()
Slot & current_slot() const
friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
std::ptrdiff_t difference_type
std::forward_iterator_tag iterator_category
BaseIterator(const Slot *slots, const int64_t total_slots, const int64_t current_slot)
BaseIterator operator++(int) const