Blender  V3.3
BLI_map.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
55 #include <optional>
56 #include <unordered_map>
57 
58 #include "BLI_array.hh"
59 #include "BLI_hash.hh"
60 #include "BLI_hash_tables.hh"
61 #include "BLI_map_slots.hh"
63 
64 namespace blender {
65 
66 template<
71  typename Key,
75  typename Value,
81  int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) + sizeof(Value)),
85  typename ProbingStrategy = DefaultProbingStrategy,
90  typename Hash = DefaultHash<Key>,
95  typename IsEqual = DefaultEquality,
102  typename Slot = typename DefaultMapSlot<Key, Value>::type,
107  typename Allocator = GuardedAllocator>
108 class Map {
109  public:
111 
112  private:
117  int64_t removed_slots_;
118  int64_t occupied_and_removed_slots_;
119 
124  int64_t usable_slots_;
125 
130  uint64_t slot_mask_;
131 
133  BLI_NO_UNIQUE_ADDRESS Hash hash_;
134 
136  BLI_NO_UNIQUE_ADDRESS IsEqual is_equal_;
137 
139 #define LOAD_FACTOR 1, 2
140  LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR);
141  using SlotArray =
142  Array<Slot, LoadFactor::compute_total_slots(InlineBufferCapacity, LOAD_FACTOR), Allocator>;
143 #undef LOAD_FACTOR
144 
149  SlotArray slots_;
150 
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()
156 
157  public:
163  Map(Allocator allocator = {}) noexcept
164  : removed_slots_(0),
165  occupied_and_removed_slots_(0),
166  usable_slots_(0),
167  slot_mask_(0),
168  hash_(),
169  is_equal_(),
170  slots_(1, allocator)
171  {
172  }
173 
174  Map(NoExceptConstructor, Allocator allocator = {}) noexcept : Map(allocator)
175  {
176  }
177 
178  ~Map() = default;
179 
180  Map(const Map &other) = default;
181 
182  Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
183  : Map(NoExceptConstructor(), other.slots_.allocator())
184  {
185  if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
186  slots_ = std::move(other.slots_);
187  }
188  else {
189  try {
190  slots_ = std::move(other.slots_);
191  }
192  catch (...) {
193  other.noexcept_reset();
194  throw;
195  }
196  }
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();
204  }
205 
206  Map &operator=(const Map &other)
207  {
208  return copy_assign_container(*this, other);
209  }
210 
211  Map &operator=(Map &&other)
212  {
213  return move_assign_container(*this, std::move(other));
214  }
215 
220  void add_new(const Key &key, const Value &value)
221  {
222  this->add_new_as(key, value);
223  }
224  void add_new(const Key &key, Value &&value)
225  {
226  this->add_new_as(key, std::move(value));
227  }
228  void add_new(Key &&key, const Value &value)
229  {
230  this->add_new_as(std::move(key), value);
231  }
232  void add_new(Key &&key, Value &&value)
233  {
234  this->add_new_as(std::move(key), std::move(value));
235  }
236  template<typename ForwardKey, typename... ForwardValue>
237  void add_new_as(ForwardKey &&key, ForwardValue &&...value)
238  {
239  this->add_new__impl(
240  std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
241  }
242 
250  bool add(const Key &key, const Value &value)
251  {
252  return this->add_as(key, value);
253  }
254  bool add(const Key &key, Value &&value)
255  {
256  return this->add_as(key, std::move(value));
257  }
258  bool add(Key &&key, const Value &value)
259  {
260  return this->add_as(std::move(key), value);
261  }
262  bool add(Key &&key, Value &&value)
263  {
264  return this->add_as(std::move(key), std::move(value));
265  }
266  template<typename ForwardKey, typename... ForwardValue>
267  bool add_as(ForwardKey &&key, ForwardValue &&...value)
268  {
269  return this->add__impl(
270  std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
271  }
272 
280  bool add_overwrite(const Key &key, const Value &value)
281  {
282  return this->add_overwrite_as(key, value);
283  }
284  bool add_overwrite(const Key &key, Value &&value)
285  {
286  return this->add_overwrite_as(key, std::move(value));
287  }
288  bool add_overwrite(Key &&key, const Value &value)
289  {
290  return this->add_overwrite_as(std::move(key), value);
291  }
292  bool add_overwrite(Key &&key, Value &&value)
293  {
294  return this->add_overwrite_as(std::move(key), std::move(value));
295  }
296  template<typename ForwardKey, typename... ForwardValue>
297  bool add_overwrite_as(ForwardKey &&key, ForwardValue &&...value)
298  {
299  return this->add_overwrite__impl(
300  std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
301  }
302 
308  bool contains(const Key &key) const
309  {
310  return this->contains_as(key);
311  }
312  template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
313  {
314  return this->lookup_slot_ptr(key, hash_(key)) != nullptr;
315  }
316 
323  bool remove(const Key &key)
324  {
325  return this->remove_as(key);
326  }
327  template<typename ForwardKey> bool remove_as(const ForwardKey &key)
328  {
329  Slot *slot = this->lookup_slot_ptr(key, hash_(key));
330  if (slot == nullptr) {
331  return false;
332  }
333  slot->remove();
334  removed_slots_++;
335  return true;
336  }
337 
342  void remove_contained(const Key &key)
343  {
344  this->remove_contained_as(key);
345  }
346  template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
347  {
348  Slot &slot = this->lookup_slot(key, hash_(key));
349  slot.remove();
350  removed_slots_++;
351  }
352 
357  Value pop(const Key &key)
358  {
359  return this->pop_as(key);
360  }
361  template<typename ForwardKey> Value pop_as(const ForwardKey &key)
362  {
363  Slot &slot = this->lookup_slot(key, hash_(key));
364  Value value = std::move(*slot.value());
365  slot.remove();
366  removed_slots_++;
367  return value;
368  }
369 
374  std::optional<Value> pop_try(const Key &key)
375  {
376  return this->pop_try_as(key);
377  }
378  template<typename ForwardKey> std::optional<Value> pop_try_as(const ForwardKey &key)
379  {
380  Slot *slot = this->lookup_slot_ptr(key, hash_(key));
381  if (slot == nullptr) {
382  return {};
383  }
384  std::optional<Value> value = std::move(*slot->value());
385  slot->remove();
386  removed_slots_++;
387  return value;
388  }
389 
394  Value pop_default(const Key &key, const Value &default_value)
395  {
396  return this->pop_default_as(key, default_value);
397  }
398  Value pop_default(const Key &key, Value &&default_value)
399  {
400  return this->pop_default_as(key, std::move(default_value));
401  }
402  template<typename ForwardKey, typename... ForwardValue>
403  Value pop_default_as(const ForwardKey &key, ForwardValue &&...default_value)
404  {
405  Slot *slot = this->lookup_slot_ptr(key, hash_(key));
406  if (slot == nullptr) {
407  return Value(std::forward<ForwardValue>(default_value)...);
408  }
409  Value value = std::move(*slot->value());
410  slot->remove();
411  removed_slots_++;
412  return value;
413  }
414 
435  template<typename CreateValueF, typename ModifyValueF>
436  auto add_or_modify(const Key &key,
437  const CreateValueF &create_value,
438  const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
439  {
440  return this->add_or_modify_as(key, create_value, modify_value);
441  }
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))
445  {
446  return this->add_or_modify_as(std::move(key), create_value, modify_value);
447  }
448  template<typename ForwardKey, typename CreateValueF, typename ModifyValueF>
449  auto add_or_modify_as(ForwardKey &&key,
450  const CreateValueF &create_value,
451  const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
452  {
453  return this->add_or_modify__impl(
454  std::forward<ForwardKey>(key), create_value, modify_value, hash_(key));
455  }
456 
463  const Value *lookup_ptr(const Key &key) const
464  {
465  return this->lookup_ptr_as(key);
466  }
467  Value *lookup_ptr(const Key &key)
468  {
469  return this->lookup_ptr_as(key);
470  }
471  template<typename ForwardKey> const Value *lookup_ptr_as(const ForwardKey &key) const
472  {
473  const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
474  return (slot != nullptr) ? slot->value() : nullptr;
475  }
476  template<typename ForwardKey> Value *lookup_ptr_as(const ForwardKey &key)
477  {
478  return const_cast<Value *>(const_cast<const Map *>(this)->lookup_ptr_as(key));
479  }
480 
485  const Value &lookup(const Key &key) const
486  {
487  return this->lookup_as(key);
488  }
489  Value &lookup(const Key &key)
490  {
491  return this->lookup_as(key);
492  }
493  template<typename ForwardKey> const Value &lookup_as(const ForwardKey &key) const
494  {
495  const Value *ptr = this->lookup_ptr_as(key);
496  BLI_assert(ptr != nullptr);
497  return *ptr;
498  }
499  template<typename ForwardKey> Value &lookup_as(const ForwardKey &key)
500  {
501  Value *ptr = this->lookup_ptr_as(key);
502  BLI_assert(ptr != nullptr);
503  return *ptr;
504  }
505 
510  Value lookup_default(const Key &key, const Value &default_value) const
511  {
512  return this->lookup_default_as(key, default_value);
513  }
514  template<typename ForwardKey, typename... ForwardValue>
515  Value lookup_default_as(const ForwardKey &key, ForwardValue &&...default_value) const
516  {
517  const Value *ptr = this->lookup_ptr_as(key);
518  if (ptr != nullptr) {
519  return *ptr;
520  }
521  else {
522  return Value(std::forward<ForwardValue>(default_value)...);
523  }
524  }
525 
530  Value &lookup_or_add(const Key &key, const Value &value)
531  {
532  return this->lookup_or_add_as(key, value);
533  }
534  Value &lookup_or_add(const Key &key, Value &&value)
535  {
536  return this->lookup_or_add_as(key, std::move(value));
537  }
538  Value &lookup_or_add(Key &&key, const Value &value)
539  {
540  return this->lookup_or_add_as(std::move(key), value);
541  }
542  Value &lookup_or_add(Key &&key, Value &&value)
543  {
544  return this->lookup_or_add_as(std::move(key), std::move(value));
545  }
546  template<typename ForwardKey, typename... ForwardValue>
547  Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&...value)
548  {
549  return this->lookup_or_add__impl(
550  std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...);
551  }
552 
560  template<typename CreateValueF>
561  Value &lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
562  {
563  return this->lookup_or_add_cb_as(key, create_value);
564  }
565  template<typename CreateValueF>
566  Value &lookup_or_add_cb(Key &&key, const CreateValueF &create_value)
567  {
568  return this->lookup_or_add_cb_as(std::move(key), create_value);
569  }
570  template<typename ForwardKey, typename CreateValueF>
571  Value &lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value)
572  {
573  return this->lookup_or_add_cb__impl(std::forward<ForwardKey>(key), create_value, hash_(key));
574  }
575 
581  {
582  return this->lookup_or_add_default_as(key);
583  }
585  {
586  return this->lookup_or_add_default_as(std::move(key));
587  }
588  template<typename ForwardKey> Value &lookup_or_add_default_as(ForwardKey &&key)
589  {
590  return this->lookup_or_add_cb_as(std::forward<ForwardKey>(key), []() { return Value(); });
591  }
592 
597  const Key &lookup_key(const Key &key) const
598  {
599  return this->lookup_key_as(key);
600  }
601  template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
602  {
603  const Slot &slot = this->lookup_slot(key, hash_(key));
604  return *slot.key();
605  }
606 
611  const Key *lookup_key_ptr(const Key &key) const
612  {
613  return this->lookup_key_ptr_as(key);
614  }
615  template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
616  {
617  const Slot *slot = this->lookup_slot_ptr(key, hash_(key));
618  if (slot == nullptr) {
619  return nullptr;
620  }
621  return slot->key();
622  }
623 
628  template<typename FuncT> void foreach_item(const FuncT &func) const
629  {
630  int64_t size = slots_.size();
631  for (int64_t i = 0; i < size; i++) {
632  const Slot &slot = slots_[i];
633  if (slot.is_occupied()) {
634  const Key &key = *slot.key();
635  const Value &value = *slot.value();
636  func(key, value);
637  }
638  }
639  }
640 
641  /* Common base class for all iterators below. */
642  struct BaseIterator {
643  public:
644  using iterator_category = std::forward_iterator_tag;
645  using difference_type = std::ptrdiff_t;
646 
647  protected:
648  /* We could have separate base iterators for const and non-const iterators, but that would add
649  * more complexity than benefits right now. */
650  Slot *slots_;
653 
654  friend Map;
655 
656  public:
657  BaseIterator(const Slot *slots, const int64_t total_slots, const int64_t current_slot)
658  : slots_(const_cast<Slot *>(slots)), total_slots_(total_slots), current_slot_(current_slot)
659  {
660  }
661 
663  {
664  while (++current_slot_ < total_slots_) {
665  if (slots_[current_slot_].is_occupied()) {
666  break;
667  }
668  }
669  return *this;
670  }
671 
673  {
674  BaseIterator copied_iterator = *this;
675  ++copied_iterator;
676  return copied_iterator;
677  }
678 
679  friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
680  {
681  BLI_assert(a.slots_ == b.slots_);
682  BLI_assert(a.total_slots_ == b.total_slots_);
683  return a.current_slot_ != b.current_slot_;
684  }
685 
686  friend bool operator==(const BaseIterator &a, const BaseIterator &b)
687  {
688  return !(a != b);
689  }
690 
691  protected:
692  Slot &current_slot() const
693  {
694  return slots_[current_slot_];
695  }
696  };
697 
702  template<typename SubIterator> class BaseIteratorRange : public BaseIterator {
703  public:
704  BaseIteratorRange(const Slot *slots, int64_t total_slots, int64_t current_slot)
705  : BaseIterator(slots, total_slots, current_slot)
706  {
707  }
708 
709  SubIterator begin() const
710  {
711  for (int64_t i = 0; i < this->total_slots_; i++) {
712  if (this->slots_[i].is_occupied()) {
713  return SubIterator(this->slots_, this->total_slots_, i);
714  }
715  }
716  return this->end();
717  }
718 
719  SubIterator end() const
720  {
721  return SubIterator(this->slots_, this->total_slots_, this->total_slots_);
722  }
723  };
724 
725  class KeyIterator final : public BaseIteratorRange<KeyIterator> {
726  public:
727  using value_type = Key;
728  using pointer = const Key *;
729  using reference = const Key &;
730 
731  KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
732  : BaseIteratorRange<KeyIterator>(slots, total_slots, current_slot)
733  {
734  }
735 
736  const Key &operator*() const
737  {
738  return *this->current_slot().key();
739  }
740  };
741 
742  class ValueIterator final : public BaseIteratorRange<ValueIterator> {
743  public:
744  using value_type = Value;
745  using pointer = const Value *;
746  using reference = const Value &;
747 
748  ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
749  : BaseIteratorRange<ValueIterator>(slots, total_slots, current_slot)
750  {
751  }
752 
753  const Value &operator*() const
754  {
755  return *this->current_slot().value();
756  }
757  };
758 
759  class MutableValueIterator final : public BaseIteratorRange<MutableValueIterator> {
760  public:
761  using value_type = Value;
762  using pointer = Value *;
763  using reference = Value &;
764 
766  : BaseIteratorRange<MutableValueIterator>(slots, total_slots, current_slot)
767  {
768  }
769 
771  {
772  return *this->current_slot().value();
773  }
774  };
775 
776  struct Item {
777  const Key &key;
778  const Value &value;
779  };
780 
781  struct MutableItem {
782  const Key &key;
784 
785  operator Item() const
786  {
787  return Item{key, value};
788  }
789  };
790 
791  class ItemIterator final : public BaseIteratorRange<ItemIterator> {
792  public:
793  using value_type = Item;
794  using pointer = Item *;
795  using reference = Item &;
796 
797  ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
798  : BaseIteratorRange<ItemIterator>(slots, total_slots, current_slot)
799  {
800  }
801 
802  Item operator*() const
803  {
804  const Slot &slot = this->current_slot();
805  return {*slot.key(), *slot.value()};
806  }
807  };
808 
809  class MutableItemIterator final : public BaseIteratorRange<MutableItemIterator> {
810  public:
812  using pointer = MutableItem *;
814 
815  MutableItemIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
816  : BaseIteratorRange<MutableItemIterator>(slots, total_slots, current_slot)
817  {
818  }
819 
821  {
822  Slot &slot = this->current_slot();
823  return {*slot.key(), *slot.value()};
824  }
825  };
826 
832  {
833  return KeyIterator(slots_.data(), slots_.size(), 0);
834  }
835 
841  {
842  return ValueIterator(slots_.data(), slots_.size(), 0);
843  }
844 
850  {
851  return MutableValueIterator(slots_.data(), slots_.size(), 0);
852  }
853 
860  {
861  return ItemIterator(slots_.data(), slots_.size(), 0);
862  }
863 
872  {
873  return MutableItemIterator(slots_.data(), slots_.size(), 0);
874  }
875 
881  void remove(const BaseIterator &iterator)
882  {
883  Slot &slot = iterator.current_slot();
884  BLI_assert(slot.is_occupied());
885  slot.remove();
886  removed_slots_++;
887  }
888 
892  void print_stats(StringRef name = "") const
893  {
894  HashTableStats stats(*this, this->keys());
895  stats.print(name);
896  }
897 
901  int64_t size() const
902  {
903  return occupied_and_removed_slots_ - removed_slots_;
904  }
905 
911  bool is_empty() const
912  {
913  return occupied_and_removed_slots_ == removed_slots_;
914  }
915 
920  {
921  return slots_.size();
922  }
923 
928  {
929  return removed_slots_;
930  }
931 
936  {
937  return sizeof(Slot);
938  }
939 
945  {
946  return static_cast<int64_t>(sizeof(Slot) * slots_.size());
947  }
948 
953  void reserve(int64_t n)
954  {
955  if (usable_slots_ < n) {
956  this->realloc_and_reinsert(n);
957  }
958  }
959 
963  void clear()
964  {
965  for (Slot &slot : slots_) {
966  slot.~Slot();
967  new (&slot) Slot();
968  }
969 
970  removed_slots_ = 0;
971  occupied_and_removed_slots_ = 0;
972  }
973 
978  int64_t count_collisions(const Key &key) const
979  {
980  return this->count_collisions__impl(key, hash_(key));
981  }
982 
983  private:
984  BLI_NOINLINE void realloc_and_reinsert(int64_t min_usable_slots)
985  {
986  int64_t total_slots, usable_slots;
987  max_load_factor_.compute_total_and_usable_slots(
988  SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots);
989  BLI_assert(total_slots >= 1);
990  const uint64_t new_slot_mask = static_cast<uint64_t>(total_slots) - 1;
991 
995  if (this->size() == 0) {
996  try {
997  slots_.reinitialize(total_slots);
998  }
999  catch (...) {
1000  this->noexcept_reset();
1001  throw;
1002  }
1003  removed_slots_ = 0;
1004  occupied_and_removed_slots_ = 0;
1005  usable_slots_ = usable_slots;
1006  slot_mask_ = new_slot_mask;
1007  return;
1008  }
1009 
1010  SlotArray new_slots(total_slots);
1011 
1012  try {
1013  for (Slot &slot : slots_) {
1014  if (slot.is_occupied()) {
1015  this->add_after_grow(slot, new_slots, new_slot_mask);
1016  slot.remove();
1017  }
1018  }
1019  slots_ = std::move(new_slots);
1020  }
1021  catch (...) {
1022  this->noexcept_reset();
1023  throw;
1024  }
1025 
1026  occupied_and_removed_slots_ -= removed_slots_;
1027  usable_slots_ = usable_slots;
1028  removed_slots_ = 0;
1029  slot_mask_ = new_slot_mask;
1030  }
1031 
1032  void add_after_grow(Slot &old_slot, SlotArray &new_slots, uint64_t new_slot_mask)
1033  {
1034  uint64_t hash = old_slot.get_hash(Hash());
1035  SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
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()));
1039  return;
1040  }
1041  }
1042  SLOT_PROBING_END();
1043  }
1044 
1045  void noexcept_reset() noexcept
1046  {
1047  Allocator allocator = slots_.allocator();
1048  this->~Map();
1049  new (this) Map(NoExceptConstructor(), allocator);
1050  }
1051 
1052  template<typename ForwardKey, typename... ForwardValue>
1053  void add_new__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
1054  {
1055  BLI_assert(!this->contains_as(key));
1056 
1057  this->ensure_can_add();
1058 
1059  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1060  if (slot.is_empty()) {
1061  slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
1062  occupied_and_removed_slots_++;
1063  return;
1064  }
1065  }
1067  }
1068 
1069  template<typename ForwardKey, typename... ForwardValue>
1070  bool add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
1071  {
1072  this->ensure_can_add();
1073 
1074  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1075  if (slot.is_empty()) {
1076  slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...);
1077  occupied_and_removed_slots_++;
1078  return true;
1079  }
1080  if (slot.contains(key, is_equal_, hash)) {
1081  return false;
1082  }
1083  }
1085  }
1086 
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,
1091  uint64_t hash) -> decltype(create_value(nullptr))
1092  {
1093  using CreateReturnT = decltype(create_value(nullptr));
1094  using ModifyReturnT = decltype(modify_value(nullptr));
1095  BLI_STATIC_ASSERT((std::is_same_v<CreateReturnT, ModifyReturnT>),
1096  "Both callbacks should return the same type.");
1097 
1098  this->ensure_can_add();
1099 
1100  MAP_SLOT_PROBING_BEGIN (hash, slot) {
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_++;
1107  return;
1108  }
1109  else {
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;
1114  }
1115  }
1116  if (slot.contains(key, is_equal_, hash)) {
1117  Value *value_ptr = slot.value();
1118  return modify_value(value_ptr);
1119  }
1120  }
1122  }
1123 
1124  template<typename ForwardKey, typename CreateValueF>
1125  Value &lookup_or_add_cb__impl(ForwardKey &&key, const CreateValueF &create_value, uint64_t hash)
1126  {
1127  this->ensure_can_add();
1128 
1129  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1130  if (slot.is_empty()) {
1131  slot.occupy(std::forward<ForwardKey>(key), hash, create_value());
1132  occupied_and_removed_slots_++;
1133  return *slot.value();
1134  }
1135  if (slot.contains(key, is_equal_, hash)) {
1136  return *slot.value();
1137  }
1138  }
1140  }
1141 
1142  template<typename ForwardKey, typename... ForwardValue>
1143  Value &lookup_or_add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
1144  {
1145  this->ensure_can_add();
1146 
1147  MAP_SLOT_PROBING_BEGIN (hash, slot) {
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();
1152  }
1153  if (slot.contains(key, is_equal_, hash)) {
1154  return *slot.value();
1155  }
1156  }
1158  }
1159 
1160  template<typename ForwardKey, typename... ForwardValue>
1161  bool add_overwrite__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&...value)
1162  {
1163  auto create_func = [&](Value *ptr) {
1164  new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value)...);
1165  return true;
1166  };
1167  auto modify_func = [&](Value *ptr) {
1168  *ptr = Value(std::forward<ForwardValue>(value)...);
1169  return false;
1170  };
1171  return this->add_or_modify__impl(
1172  std::forward<ForwardKey>(key), create_func, modify_func, hash);
1173  }
1174 
1175  template<typename ForwardKey>
1176  const Slot &lookup_slot(const ForwardKey &key, const uint64_t hash) const
1177  {
1178  BLI_assert(this->contains_as(key));
1179  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1180  if (slot.contains(key, is_equal_, hash)) {
1181  return slot;
1182  }
1183  }
1185  }
1186 
1187  template<typename ForwardKey> Slot &lookup_slot(const ForwardKey &key, const uint64_t hash)
1188  {
1189  return const_cast<Slot &>(const_cast<const Map *>(this)->lookup_slot(key, hash));
1190  }
1191 
1192  template<typename ForwardKey>
1193  const Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash) const
1194  {
1195  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1196  if (slot.contains(key, is_equal_, hash)) {
1197  return &slot;
1198  }
1199  if (slot.is_empty()) {
1200  return nullptr;
1201  }
1202  }
1204  }
1205 
1206  template<typename ForwardKey> Slot *lookup_slot_ptr(const ForwardKey &key, const uint64_t hash)
1207  {
1208  return const_cast<Slot *>(const_cast<const Map *>(this)->lookup_slot_ptr(key, hash));
1209  }
1210 
1211  template<typename ForwardKey>
1212  int64_t count_collisions__impl(const ForwardKey &key, uint64_t hash) const
1213  {
1214  int64_t collisions = 0;
1215 
1216  MAP_SLOT_PROBING_BEGIN (hash, slot) {
1217  if (slot.contains(key, is_equal_, hash)) {
1218  return collisions;
1219  }
1220  if (slot.is_empty()) {
1221  return collisions;
1222  }
1223  collisions++;
1224  }
1226  }
1227 
1228  void ensure_can_add()
1229  {
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_);
1233  }
1234  }
1235 };
1236 
1241 template<typename Key,
1242  typename Value,
1243  int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key) +
1244  sizeof(Value)),
1245  typename ProbingStrategy = DefaultProbingStrategy,
1246  typename Hash = DefaultHash<Key>,
1247  typename IsEqual = DefaultEquality,
1248  typename Slot = typename DefaultMapSlot<Key, Value>::type>
1249 using RawMap =
1251 
1256 template<typename Key, typename Value> class StdUnorderedMapWrapper {
1257  private:
1258  using MapType = std::unordered_map<Key, Value, blender::DefaultHash<Key>>;
1259  MapType map_;
1260 
1261  public:
1262  int64_t size() const
1263  {
1264  return static_cast<int64_t>(map_.size());
1265  }
1266 
1267  bool is_empty() const
1268  {
1269  return map_.empty();
1270  }
1271 
1273  {
1274  map_.reserve(n);
1275  }
1276 
1277  template<typename ForwardKey, typename... ForwardValue>
1278  void add_new(ForwardKey &&key, ForwardValue &&...value)
1279  {
1280  map_.insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)});
1281  }
1282 
1283  template<typename ForwardKey, typename... ForwardValue>
1284  bool add(ForwardKey &&key, ForwardValue &&...value)
1285  {
1286  return map_
1287  .insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)})
1288  .second;
1289  }
1290 
1291  bool contains(const Key &key) const
1292  {
1293  return map_.find(key) != map_.end();
1294  }
1295 
1296  bool remove(const Key &key)
1297  {
1298  return (bool)map_.erase(key);
1299  }
1300 
1301  Value &lookup(const Key &key)
1302  {
1303  return map_.find(key)->second;
1304  }
1305 
1306  const Value &lookup(const Key &key) const
1307  {
1308  return map_.find(key)->second;
1309  }
1310 
1311  void clear()
1312  {
1313  map_.clear();
1314  }
1315 
1316  void print_stats(StringRef UNUSED(name) = "") const
1317  {
1318  }
1319 };
1320 
1321 } // namespace blender
#define BLI_STATIC_ASSERT(a, msg)
Definition: BLI_assert.h:83
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_NOINLINE
#define final(a, b, c)
Definition: BLI_hash.h:21
#define LOAD_FACTOR
Definition: BLI_map.hh:139
#define MAP_SLOT_PROBING_END()
Definition: BLI_map.hh:155
#define MAP_SLOT_PROBING_BEGIN(HASH, R_SLOT)
Definition: BLI_map.hh:152
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define UNUSED(x)
#define BLI_NO_UNIQUE_ADDRESS
struct Key Key
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()
Definition: BLI_array.hh:378
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
Definition: BLI_map.hh:709
BaseIteratorRange(const Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:704
SubIterator end() const
Definition: BLI_map.hh:719
Item operator*() const
Definition: BLI_map.hh:802
ItemIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:797
KeyIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:731
const Key & operator*() const
Definition: BLI_map.hh:736
MutableItemIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:815
MutableItem operator*() const
Definition: BLI_map.hh:820
MutableValueIterator(Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:765
const Value & reference
Definition: BLI_map.hh:746
const Value & operator*() const
Definition: BLI_map.hh:753
ValueIterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
Definition: BLI_map.hh:748
MutableItemIterator items()
Definition: BLI_map.hh:871
Map & operator=(Map &&other)
Definition: BLI_map.hh:211
Value pop_as(const ForwardKey &key)
Definition: BLI_map.hh:361
bool add_overwrite(Key &&key, Value &&value)
Definition: BLI_map.hh:292
Value & lookup_or_add_default_as(ForwardKey &&key)
Definition: BLI_map.hh:588
Value pop_default_as(const ForwardKey &key, ForwardValue &&...default_value)
Definition: BLI_map.hh:403
void clear()
Definition: BLI_map.hh:963
int64_t size_type
Definition: BLI_map.hh:110
int64_t size_in_bytes() const
Definition: BLI_map.hh:944
Value pop(const Key &key)
Definition: BLI_map.hh:357
const Key & lookup_key_as(const ForwardKey &key) const
Definition: BLI_map.hh:601
void add_new(const Key &key, Value &&value)
Definition: BLI_map.hh:224
void add_new(Key &&key, const Value &value)
Definition: BLI_map.hh:228
KeyIterator keys() const
Definition: BLI_map.hh:831
int64_t removed_amount() const
Definition: BLI_map.hh:927
Map(NoExceptConstructor, Allocator allocator={}) noexcept
Definition: BLI_map.hh:174
Value & lookup_as(const ForwardKey &key)
Definition: BLI_map.hh:499
Map & operator=(const Map &other)
Definition: BLI_map.hh:206
bool remove_as(const ForwardKey &key)
Definition: BLI_map.hh:327
bool add_overwrite(const Key &key, const Value &value)
Definition: BLI_map.hh:280
std::optional< Value > pop_try_as(const ForwardKey &key)
Definition: BLI_map.hh:378
~Map()=default
Value & lookup_or_add_cb(Key &&key, const CreateValueF &create_value)
Definition: BLI_map.hh:566
bool add(const Key &key, const Value &value)
Definition: BLI_map.hh:250
int64_t size_per_element() const
Definition: BLI_map.hh:935
Value & lookup_or_add(Key &&key, const Value &value)
Definition: BLI_map.hh:538
void remove_contained_as(const ForwardKey &key)
Definition: BLI_map.hh:346
void print_stats(StringRef name="") const
Definition: BLI_map.hh:892
Value lookup_default(const Key &key, const Value &default_value) const
Definition: BLI_map.hh:510
Value & lookup_or_add(Key &&key, Value &&value)
Definition: BLI_map.hh:542
bool add_overwrite(Key &&key, const Value &value)
Definition: BLI_map.hh:288
int64_t count_collisions(const Key &key) const
Definition: BLI_map.hh:978
ValueIterator values() const
Definition: BLI_map.hh:840
MutableValueIterator values()
Definition: BLI_map.hh:849
Value & lookup_or_add_default(Key &&key)
Definition: BLI_map.hh:584
int64_t capacity() const
Definition: BLI_map.hh:919
const Value * lookup_ptr_as(const ForwardKey &key) const
Definition: BLI_map.hh:471
const Value & lookup(const Key &key) const
Definition: BLI_map.hh:485
Value * lookup_ptr_as(const ForwardKey &key)
Definition: BLI_map.hh:476
void add_new_as(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:237
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition: BLI_map.hh:561
Value & lookup_or_add_cb_as(ForwardKey &&key, const CreateValueF &create_value)
Definition: BLI_map.hh:571
void foreach_item(const FuncT &func) const
Definition: BLI_map.hh:628
void remove_contained(const Key &key)
Definition: BLI_map.hh:342
Map(const Map &other)=default
Map(Allocator allocator={}) noexcept
Definition: BLI_map.hh:163
const Key & lookup_key(const Key &key) const
Definition: BLI_map.hh:597
Value & lookup_or_add_default(const Key &key)
Definition: BLI_map.hh:580
const Key * lookup_key_ptr_as(const ForwardKey &key) const
Definition: BLI_map.hh:615
bool add_as(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:267
auto add_or_modify_as(ForwardKey &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition: BLI_map.hh:449
void add_new(Key &&key, Value &&value)
Definition: BLI_map.hh:232
void add_new(const Key &key, const Value &value)
Definition: BLI_map.hh:220
bool add(Key &&key, Value &&value)
Definition: BLI_map.hh:262
Value & lookup_or_add_as(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:547
Map(Map &&other) noexcept(std::is_nothrow_move_constructible_v< SlotArray >)
Definition: BLI_map.hh:182
Value & lookup_or_add(const Key &key, const Value &value)
Definition: BLI_map.hh:530
bool remove(const Key &key)
Definition: BLI_map.hh:323
int64_t size() const
Definition: BLI_map.hh:901
bool contains_as(const ForwardKey &key) const
Definition: BLI_map.hh:312
ItemIterator items() const
Definition: BLI_map.hh:859
const Value & lookup_as(const ForwardKey &key) const
Definition: BLI_map.hh:493
bool add(const Key &key, Value &&value)
Definition: BLI_map.hh:254
Value & lookup_or_add(const Key &key, Value &&value)
Definition: BLI_map.hh:534
auto add_or_modify(Key &&key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition: BLI_map.hh:443
bool is_empty() const
Definition: BLI_map.hh:911
void reserve(int64_t n)
Definition: BLI_map.hh:953
Value & lookup(const Key &key)
Definition: BLI_map.hh:489
bool add_overwrite_as(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:297
bool contains(const Key &key) const
Definition: BLI_map.hh:308
Value pop_default(const Key &key, Value &&default_value)
Definition: BLI_map.hh:398
bool add(Key &&key, const Value &value)
Definition: BLI_map.hh:258
bool add_overwrite(const Key &key, Value &&value)
Definition: BLI_map.hh:284
Value lookup_default_as(const ForwardKey &key, ForwardValue &&...default_value) const
Definition: BLI_map.hh:515
Value * lookup_ptr(const Key &key)
Definition: BLI_map.hh:467
const Value * lookup_ptr(const Key &key) const
Definition: BLI_map.hh:463
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition: BLI_map.hh:436
const Key * lookup_key_ptr(const Key &key) const
Definition: BLI_map.hh:611
Value pop_default(const Key &key, const Value &default_value)
Definition: BLI_map.hh:394
void remove(const BaseIterator &iterator)
Definition: BLI_map.hh:881
std::optional< Value > pop_try(const Key &key)
Definition: BLI_map.hh:374
const Value & lookup(const Key &key) const
Definition: BLI_map.hh:1306
bool contains(const Key &key) const
Definition: BLI_map.hh:1291
void print_stats(StringRef UNUSED(name)="") const
Definition: BLI_map.hh:1316
void add_new(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:1278
bool remove(const Key &key)
Definition: BLI_map.hh:1296
Value & lookup(const Key &key)
Definition: BLI_map.hh:1301
bool add(ForwardKey &&key, ForwardValue &&...value)
Definition: BLI_map.hh:1284
static unsigned a[3]
Definition: RandGen.cpp:78
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)
#define hash
Definition: noise.c:153
static PyObject * create_func(PyObject *, PyObject *args)
Definition: python.cpp:156
__int64 int64_t
Definition: stdint.h:89
unsigned __int64 uint64_t
Definition: stdint.h:90
SimpleMapSlot< Key, Value > type
friend bool operator==(const BaseIterator &a, const BaseIterator &b)
Definition: BLI_map.hh:686
BaseIterator & operator++()
Definition: BLI_map.hh:662
Slot & current_slot() const
Definition: BLI_map.hh:692
friend bool operator!=(const BaseIterator &a, const BaseIterator &b)
Definition: BLI_map.hh:679
std::ptrdiff_t difference_type
Definition: BLI_map.hh:645
std::forward_iterator_tag iterator_category
Definition: BLI_map.hh:644
BaseIterator(const Slot *slots, const int64_t total_slots, const int64_t current_slot)
Definition: BLI_map.hh:657
BaseIterator operator++(int) const
Definition: BLI_map.hh:672
const Key & key
Definition: BLI_map.hh:777
const Value & value
Definition: BLI_map.hh:778
PointerRNA * ptr
Definition: wm_files.c:3480