68template<
typename Key,
typename Value>
struct MapItem {
83 return {this->key, this->value};
111 typename Hash = DefaultHash<Key>,
116 typename IsEqual = DefaultEquality<Key>,
141 int64_t occupied_and_removed_slots_;
162#define LOAD_FACTOR 1, 2
175#define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
176 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
177 auto &R_SLOT = slots_[SLOT_INDEX];
178#define MAP_SLOT_PROBING_END() SLOT_PROBING_END()
186 Map(Allocator allocator = {})
noexcept
188 occupied_and_removed_slots_(0),
203 Map(
Map &&other)
noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
206 if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
207 slots_ = std::move(other.slots_);
211 slots_ = std::move(other.slots_);
214 other.noexcept_reset();
218 removed_slots_ = other.removed_slots_;
219 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
220 usable_slots_ = other.usable_slots_;
221 slot_mask_ = other.slot_mask_;
222 hash_ = std::move(other.hash_);
223 is_equal_ = std::move(other.is_equal_);
224 other.noexcept_reset();
235 Map(
const Span<std::pair<Key, Value>>
items, Allocator allocator = {}) :
Map(allocator)
237 for (
const std::pair<Key, Value> &item :
items) {
238 this->
add(item.first, item.second);
246 Map(
const std::initializer_list<std::pair<Key, Value>>
items, Allocator allocator = {})
279 this->
add_new_as(std::move(key), std::move(value));
281 template<
typename ForwardKey,
typename... ForwardValue>
285 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
295 bool add(
const Key &key,
const Value &value)
297 return this->
add_as(key, value);
301 return this->
add_as(key, std::move(value));
305 return this->
add_as(std::move(key), value);
309 return this->
add_as(std::move(key), std::move(value));
311 template<
typename ForwardKey,
typename... ForwardValue>
312 bool add_as(ForwardKey &&key, ForwardValue &&...value)
314 return this->add__impl(
315 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
341 template<
typename ForwardKey,
typename... ForwardValue>
344 return this->add_overwrite__impl(
345 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
357 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
359 return this->lookup_slot_ptr(key, hash_(key)) !=
nullptr;
372 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
374 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
375 if (slot ==
nullptr) {
393 Slot &slot = this->lookup_slot(key, hash_(key));
406 template<
typename ForwardKey> Value
pop_as(
const ForwardKey &key)
408 Slot &slot = this->lookup_slot(key, hash_(key));
409 Value value = std::move(*slot.value());
423 template<
typename ForwardKey> std::optional<Value>
pop_try_as(
const ForwardKey &key)
425 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
426 if (slot ==
nullptr) {
429 std::optional<Value> value = std::move(*slot->value());
447 template<
typename ForwardKey,
typename... ForwardValue>
450 Slot *slot = this->lookup_slot_ptr(key, hash_(key));
451 if (slot ==
nullptr) {
452 return Value(std::forward<ForwardValue>(default_value)...);
454 Value value = std::move(*slot->value());
480 template<
typename CreateValueF,
typename ModifyValueF>
482 const CreateValueF &create_value,
483 const ModifyValueF &modify_value) ->
decltype(create_value(
nullptr))
487 template<
typename CreateValueF,
typename ModifyValueF>
488 auto add_or_modify(
Key &&key,
const CreateValueF &create_value,
const ModifyValueF &modify_value)
489 ->
decltype(create_value(
nullptr))
493 template<
typename ForwardKey,
typename CreateValueF,
typename ModifyValueF>
495 const CreateValueF &create_value,
496 const ModifyValueF &modify_value) ->
decltype(create_value(
nullptr))
498 return this->add_or_modify__impl(
499 std::forward<ForwardKey>(key), create_value, modify_value, hash_(key));
516 template<
typename ForwardKey>
const Value *
lookup_ptr_as(
const ForwardKey &key)
const
518 const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
519 return (slot !=
nullptr) ? slot->value() :
nullptr;
523 return const_cast<Value *
>(
const_cast<const Map *
>(
this)->lookup_ptr_as(key));
535 template<
typename ForwardKey> std::optional<Value>
lookup_try_as(
const ForwardKey &key)
const
537 const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
538 return (slot !=
nullptr) ? std::optional<Value>(*slot->value()) : std::nullopt;
553 template<
typename ForwardKey>
const Value &
lookup_as(
const ForwardKey &key)
const
559 template<
typename ForwardKey> Value &
lookup_as(
const ForwardKey &key)
574 template<
typename ForwardKey,
typename... ForwardValue>
578 if (ptr !=
nullptr) {
581 return Value(std::forward<ForwardValue>(default_value)...);
604 template<
typename ForwardKey,
typename... ForwardValue>
607 return this->lookup_or_add__impl(
608 std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
619 template<
typename CreateValueF>
624 template<
typename CreateValueF>
629 template<
typename ForwardKey,
typename CreateValueF>
632 return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, hash_(key));
662 const Slot &slot = this->lookup_slot(key, hash_(key));
676 const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
677 if (slot ==
nullptr) {
691 const Slot &slot = slots_[i];
692 if (slot.is_occupied()) {
693 const Key &key = *slot.key();
694 const Value &value = *slot.value();
735 return copied_iterator;
771 if (this->
slots_[i].is_occupied()) {
772 return SubIterator(this->
slots_, this->total_slots_, i);
849 return {*slot.key(), *slot.value()};
867 return {*slot.key(), *slot.value()};
877 return KeyIterator(slots_.data(), slots_.size(), 0);
904 return ItemIterator(slots_.data(), slots_.size(), 0);
923 KeyIterator
keys() const && = delete;
924 MutableValueIterator
values() && = delete;
925 ValueIterator
values() const && = delete;
926 ItemIterator
items() const && = delete;
927 MutableItemIterator
items() && = delete;
951 for (
Slot &slot : slots_) {
952 if (slot.is_occupied()) {
953 const Key &key = *slot.key();
954 Value &value = *slot.value();
961 return prev_size - this->
size();
978 return occupied_and_removed_slots_ - removed_slots_;
988 return occupied_and_removed_slots_ == removed_slots_;
996 return slots_.size();
1004 return removed_slots_;
1012 return sizeof(
Slot);
1030 if (usable_slots_ < n) {
1031 this->realloc_and_reinsert(n);
1040 std::destroy_at(
this);
1053 for (
Slot &slot : slots_) {
1059 occupied_and_removed_slots_ = 0;
1068 return this->count_collisions__impl(key, hash_(key));
1076 if (a.
size() !=
b.size()) {
1080 const Key &key = item.key;
1081 const Value &value_a = item.value;
1082 const Value *value_b =
b.lookup_ptr(key);
1083 if (value_b ==
nullptr) {
1086 if (value_a != *value_b) {
1103 min_usable_slots = std::max(min_usable_slots, this->
size() * 2);
1105 int64_t total_slots, usable_slots;
1114 if (this->
size() == 0) {
1119 this->noexcept_reset();
1123 occupied_and_removed_slots_ = 0;
1124 usable_slots_ = usable_slots;
1125 slot_mask_ = new_slot_mask;
1129 SlotArray new_slots(total_slots);
1132 for (Slot &slot : slots_) {
1133 if (slot.is_occupied()) {
1134 this->add_after_grow(slot, new_slots, new_slot_mask);
1138 slots_ = std::move(new_slots);
1141 this->noexcept_reset();
1145 occupied_and_removed_slots_ -= removed_slots_;
1146 usable_slots_ = usable_slots;
1148 slot_mask_ = new_slot_mask;
1151 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
uint64_t new_slot_mask)
1155 Slot &slot = new_slots[slot_index];
1156 if (slot.is_empty()) {
1157 slot.occupy(std::move(*old_slot.key()),
hash, std::move(*old_slot.value()));
1164 void noexcept_reset() noexcept
1166 Allocator allocator = slots_.allocator();
1168 new (
this)
Map(NoExceptConstructor(), allocator);
1171 template<
typename ForwardKey,
typename... ForwardValue>
1172 void add_new__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1176 this->ensure_can_add();
1179 if (slot.is_empty()) {
1180 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1182 BLI_assert(is_equal_(*slot.key(), *slot.key()));
1183 occupied_and_removed_slots_++;
1190 template<
typename ForwardKey,
typename... ForwardValue>
1191 bool add__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1193 this->ensure_can_add();
1196 if (slot.is_empty()) {
1197 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1199 BLI_assert(is_equal_(*slot.key(), *slot.key()));
1200 occupied_and_removed_slots_++;
1203 if (slot.contains(key, is_equal_,
hash)) {
1214 template<
typename ForwardKey,
typename CreateValueF,
typename ModifyValueF>
1215 auto add_or_modify__impl(ForwardKey &&key,
1216 const CreateValueF &create_value,
1217 const ModifyValueF &modify_value,
1220 using CreateReturnT =
decltype(create_value(
nullptr));
1221 using ModifyReturnT =
decltype(modify_value(
nullptr));
1223 "Both callbacks should return the same type.");
1225 this->ensure_can_add();
1228 if (slot.is_empty()) {
1229 Value *value_ptr = slot.value();
1230 if constexpr (std::is_void_v<CreateReturnT>) {
1231 create_value(value_ptr);
1232 slot.occupy_no_value(std::forward<ForwardKey>(key),
hash);
1233 occupied_and_removed_slots_++;
1237 auto &&return_value = create_value(value_ptr);
1238 slot.occupy_no_value(std::forward<ForwardKey>(key),
hash);
1239 occupied_and_removed_slots_++;
1240 return return_value;
1243 if (slot.contains(key, is_equal_,
hash)) {
1244 Value *value_ptr = slot.value();
1245 return modify_value(value_ptr);
1251 template<
typename ForwardKey,
typename CreateValueF>
1252 Value &lookup_or_add_cb__impl(ForwardKey &&key,
const CreateValueF &create_value,
uint64_t hash)
1254 this->ensure_can_add();
1257 if (slot.is_empty()) {
1258 slot.occupy(std::forward<ForwardKey>(key),
hash, create_value());
1260 BLI_assert(is_equal_(*slot.key(), *slot.key()));
1261 occupied_and_removed_slots_++;
1262 return *slot.value();
1264 if (slot.contains(key, is_equal_,
hash)) {
1265 return *slot.value();
1271 template<
typename ForwardKey,
typename... ForwardValue>
1272 Value &lookup_or_add__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1274 this->ensure_can_add();
1277 if (slot.is_empty()) {
1278 slot.occupy(std::forward<ForwardKey>(key),
hash, std::forward<ForwardValue>(value)...);
1280 BLI_assert(is_equal_(*slot.key(), *slot.key()));
1281 occupied_and_removed_slots_++;
1282 return *slot.value();
1284 if (slot.contains(key, is_equal_,
hash)) {
1285 return *slot.value();
1291 template<
typename ForwardKey,
typename... ForwardValue>
1292 bool add_overwrite__impl(ForwardKey &&key,
uint64_t hash, ForwardValue &&...value)
1294 auto create_func = [&](
Value *ptr) {
1295 new (
static_cast<void *
>(ptr))
Value(std::forward<ForwardValue>(value)...);
1298 auto modify_func = [&](
Value *ptr) {
1299 *ptr =
Value(std::forward<ForwardValue>(value)...);
1302 return this->add_or_modify__impl(
1303 std::forward<ForwardKey>(key), create_func, modify_func,
hash);
1306 template<
typename ForwardKey>
1307 const Slot &lookup_slot(
const ForwardKey &key,
const uint64_t hash)
const
1311 if (slot.contains(key, is_equal_,
hash)) {
1318 template<
typename ForwardKey> Slot &lookup_slot(
const ForwardKey &key,
const uint64_t hash)
1320 return const_cast<Slot &
>(
const_cast<const Map *
>(
this)->lookup_slot(key,
hash));
1323 template<
typename ForwardKey>
1324 const Slot *lookup_slot_ptr(
const ForwardKey &key,
const uint64_t hash)
const
1327 if (slot.contains(key, is_equal_,
hash)) {
1330 if (slot.is_empty()) {
1337 template<
typename ForwardKey> Slot *lookup_slot_ptr(
const ForwardKey &key,
const uint64_t hash)
1339 return const_cast<Slot *
>(
const_cast<const Map *
>(
this)->lookup_slot_ptr(key,
hash));
1342 template<
typename ForwardKey>
1348 if (slot.contains(key, is_equal_,
hash)) {
1351 if (slot.is_empty()) {
1359 void ensure_can_add()
1361 if (occupied_and_removed_slots_ >= usable_slots_) {
1362 this->realloc_and_reinsert(this->
size() + 1);
1363 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
1372template<
typename Key,
#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
static int64_t inline_buffer_capacity()
void reinitialize(const int64_t new_size)
void print(const char *name) const
constexpr LoadFactor(uint8_t numerator, uint8_t denominator)
constexpr void compute_total_and_usable_slots(int64_t min_total_slots, int64_t min_usable_slots, int64_t *r_total_slots, int64_t *r_usable_slots) const
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)
MutableValueIterator values() &
AnimatedProperty pop_as(const ForwardKey &key)
bool add_overwrite(Key &&key, Value &&value)
AnimatedProperty pop_default_as(const ForwardKey &key, ForwardValue &&...default_value)
KeyIterator keys() const &&=delete
const Value * lookup_ptr(const Key &key) const
void print_stats(const char *name) const
int64_t size_in_bytes() const
Value pop(const Key &key)
Value & lookup(const Key &key)
std::optional< Value > lookup_try(const Key &key) const
friend bool operator!=(const Map &a, const Map &b)
Value & lookup_as(const ForwardKey &key)
std::optional< Value > pop_try(const Key &key)
void add_new(const Key &key, Value &&value)
Value & lookup_or_add_default(const Key &key)
MutableMapItem< PropIdentifier, AnimatedProperty > MutableItem
void add_new(Key &&key, const Value &value)
Value & lookup_or_add(Key &&key, const Value &value)
const PropIdentifier & lookup_key_as(const ForwardKey &key) const
Map(const Span< std::pair< Key, Value > > items, Allocator allocator={})
Value & lookup_or_add_default(Key &&key)
int64_t removed_amount() const
Map(NoExceptConstructor, Allocator allocator={}) noexcept
Map(const std::initializer_list< std::pair< Key, Value > > items, Allocator allocator={})
bool remove_as(const ForwardKey &key)
bool add_overwrite(const Key &key, const Value &value)
ValueIterator values() const &
bool add(const Key &key, const Value &value)
int64_t size_per_element() const
const Value & lookup(const Key &key) const
Value & lookup_or_add(const Key &key, Value &&value)
void remove_contained_as(const ForwardKey &key)
std::optional< AnimatedProperty > lookup_try_as(const ForwardKey &key) const
Value lookup_default(const Key &key, const Value &default_value) const
const PropIdentifier * lookup_key_ptr_as(const ForwardKey &key) const
bool add_overwrite(Key &&key, const Value &value)
int64_t count_collisions(const Key &key) const
Value & lookup_or_add_cb(Key &&key, const CreateValueF &create_value)
void add_new_as(ForwardKey &&key, ForwardValue &&...value)
AnimatedProperty & lookup_or_add_default_as(ForwardKey &&key)
AnimatedProperty & lookup_or_add_as(ForwardKey &&key, ForwardValue &&...value)
void clear_and_keep_capacity()
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
const AnimatedProperty * lookup_ptr_as(const ForwardKey &key) const
friend bool operator==(const Map &a, const Map &b)
Value * lookup_ptr(const Key &key)
void foreach_item(const FuncT &func) const
void remove_contained(const Key &key)
MutableItemIterator items() &
Map(const Map &other)=default
Map(Allocator allocator={}) noexcept
const Key & lookup_key(const Key &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))
AnimatedProperty & lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value)
void add_new(Key &&key, Value &&value)
const Key * lookup_key_ptr(const Key &key) const
void add_new(const Key &key, const Value &value)
bool add(Key &&key, Value &&value)
Map & operator=(Map &&other)
Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v< SlotArray >)
const AnimatedProperty & lookup_as(const ForwardKey &key) const
bool remove(const Key &key)
bool contains_as(const ForwardKey &key) const
MapItem< PropIdentifier, AnimatedProperty > Item
bool add(const Key &key, Value &&value)
KeyIterator keys() const &
auto add_or_modify(Key &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
bool add_overwrite_as(ForwardKey &&key, ForwardValue &&...value)
bool contains(const Key &key) const
Map & operator=(const Map &other)
Value pop_default(const Key &key, Value &&default_value)
bool add(Key &&key, const Value &value)
Value * lookup_ptr_as(const ForwardKey &key)
bool add_overwrite(const Key &key, Value &&value)
AnimatedProperty lookup_default_as(const ForwardKey &key, ForwardValue &&...default_value) const
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
int64_t remove_if(Predicate &&predicate)
Value pop_default(const Key &key, const Value &default_value)
Value & lookup_or_add(Key &&key, Value &&value)
std::optional< AnimatedProperty > pop_try_as(const ForwardKey &key)
ItemIterator items() const &
Value & lookup_or_add(const Key &key, const Value &value)
BLI_STATIC_ASSERT(MBC_BATCH_LEN< 64, "Number of batches exceeded the limit of bit fields")
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Container & copy_assign_container(Container &dst, const Container &src)
Container & move_assign_container(Container &dst, Container &&src) noexcept(std::is_nothrow_move_constructible_v< Container >)
constexpr int64_t default_inline_buffer_capacity(size_t element_size)
Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator > RawMap
PythonProbingStrategy<> DefaultProbingStrategy
SimpleMapSlot< Key, Value > type
friend bool operator==(const BaseIterator &a, const BaseIterator &b)
Slot & current_slot() const
BaseIterator operator++(int)
friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
BaseIterator & operator++()
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)