Blender V5.3
BLI_set.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
57
58#include "BLI_array.hh"
59#include "BLI_hash.hh"
60#include "BLI_hash_tables.hh"
62#include "BLI_set_slots.hh"
63
64namespace blender {
65
66template<
71 typename Key,
77 int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)),
81 typename ProbingStrategy = DefaultProbingStrategy,
86 typename Hash = DefaultHash<Key>,
91 typename IsEqual = DefaultEquality<Key>,
100 typename Slot = typename DefaultSetSlot<Key>::type,
105 typename Allocator = GuardedAllocator>
106class Set {
107 public:
108 class Iterator;
110 using pointer = Key *;
111 using const_pointer = const Key *;
112 using reference = Key &;
113 using const_reference = const Key &;
114 using iterator = Iterator;
116
117 private:
122 int64_t removed_slots_;
123 int64_t occupied_and_removed_slots_;
124
129 int64_t usable_slots_;
130
135 uint64_t slot_mask_;
136
139
141 BLI_NO_UNIQUE_ADDRESS IsEqual is_equal_;
142
144#define LOAD_FACTOR 1, 2
145 static constexpr LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR);
146 using SlotArray =
147 Array<Slot, LoadFactor::compute_total_slots(InlineBufferCapacity, LOAD_FACTOR), Allocator>;
148#undef LOAD_FACTOR
149
154 SlotArray slots_;
155
157#define SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
158 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
159 auto &R_SLOT = slots_[SLOT_INDEX];
160#define SET_SLOT_PROBING_END() SLOT_PROBING_END()
161
162 public:
168 Set(Allocator allocator = {}) noexcept
169 : removed_slots_(0),
170 occupied_and_removed_slots_(0),
171 usable_slots_(0),
172 slot_mask_(0),
173 slots_(1, allocator)
174 {
175 }
176
177 Set(NoExceptConstructor, Allocator allocator = {}) noexcept : Set(allocator) {}
178
179 Set(Span<Key> values, Allocator allocator = {}) : Set(NoExceptConstructor(), allocator)
180 {
181 this->add_multiple(values);
182 }
183
187 Set(const std::initializer_list<Key> &values) : Set(Span<Key>(values)) {}
188
189 ~Set() = default;
190
191 Set(const Set &other) = default;
192
193 Set(Set &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
194 : Set(NoExceptConstructor(), other.slots_.allocator())
195
196 {
197 if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
198 slots_ = std::move(other.slots_);
199 }
200 else {
201 try {
202 slots_ = std::move(other.slots_);
203 }
204 catch (...) {
205 other.noexcept_reset();
206 throw;
207 }
208 }
209 removed_slots_ = other.removed_slots_;
210 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
211 usable_slots_ = other.usable_slots_;
212 slot_mask_ = other.slot_mask_;
213 hash_ = std::move(other.hash_);
214 is_equal_ = std::move(other.is_equal_);
215 other.noexcept_reset();
216 }
217
218 Set &operator=(const Set &other)
219 {
220 return copy_assign_container(*this, other);
221 }
222
223 Set &operator=(Set &&other)
224 {
225 return move_assign_container(*this, std::move(other));
226 }
227
233 void add_new(const Key &key)
234 {
235 this->add_new__impl(key, hash_(key));
236 }
237 void add_new(Key &&key)
238 {
239 this->add_new__impl(std::move(key), hash_(key));
240 }
241
248 bool add(const Key &key)
249 {
250 return this->add_as(key);
251 }
252 bool add(Key &&key)
253 {
254 return this->add_as(std::move(key));
255 }
256 template<typename ForwardKey> bool add_as(ForwardKey &&key)
257 {
258 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
259 }
260
267 bool add_overwrite(const Key &key)
268 {
269 return this->add_overwrite_as(key);
270 }
271 bool add_overwrite(Key &&key)
272 {
273 return this->add_overwrite_as(std::move(key));
274 }
275 template<typename ForwardKey> bool add_overwrite_as(ForwardKey &&key)
276 {
277 return this->add_overwrite__impl(std::forward<ForwardKey>(key), hash_(key));
278 }
279
288 {
289 for (const Key &key : keys) {
290 this->add(key);
291 }
292 }
293
299 {
300 for (const Key &key : keys) {
301 this->add_new(key);
302 }
303 }
304
310 bool contains(const Key &key) const
311 {
312 return this->contains_as(key);
313 }
314 template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
315 {
316 return this->contains__impl(key, hash_(key));
317 }
318
323 const Key &lookup_key(const Key &key) const
324 {
325 return this->lookup_key_as(key);
326 }
327 template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
328 {
329 return this->lookup_key__impl(key, hash_(key));
330 }
331
336 const Key &lookup_key_default(const Key &key, const Key &default_value) const
337 {
338 return this->lookup_key_default_as(key, default_value);
339 }
340 template<typename ForwardKey>
341 const Key &lookup_key_default_as(const ForwardKey &key, const Key &default_key) const
342 {
343 const Key *ptr = this->lookup_key_ptr__impl(key, hash_(key));
344 if (ptr == nullptr) {
345 return default_key;
346 }
347 return *ptr;
348 }
349
354 const Key *lookup_key_ptr(const Key &key) const
355 {
356 return this->lookup_key_ptr_as(key);
357 }
358 template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
359 {
360 return this->lookup_key_ptr__impl(key, hash_(key));
361 }
362
367 const Key &lookup_key_or_add(const Key &key)
368 {
369 return this->lookup_key_or_add_as(key);
370 }
372 {
373 return this->lookup_key_or_add_as(std::move(key));
374 }
375 template<typename ForwardKey> const Key &lookup_key_or_add_as(ForwardKey &&key)
376 {
377 return this->lookup_key_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
378 }
379
387 template<typename CreateValueF>
388 const Key &lookup_key_or_add_cb(const Key &key, CreateValueF &&create_value)
389 {
390 return this->lookup_key_or_add_cb_as(key, std::forward<CreateValueF>(create_value));
391 }
392 template<typename ForwardKey, typename CreateValueF>
393 const Key &lookup_key_or_add_cb_as(ForwardKey &&key, CreateValueF &&create_value)
394 {
395 return this->lookup_key_or_add_cb__impl(
396 std::forward<ForwardKey>(key), hash_(key), std::forward<CreateValueF>(create_value));
397 }
398
404 bool remove(const Key &key)
405 {
406 return this->remove_as(key);
407 }
408 template<typename ForwardKey> bool remove_as(const ForwardKey &key)
409 {
410 return this->remove__impl(key, hash_(key));
411 }
412
416 void remove_contained(const Key &key)
417 {
418 this->remove_contained_as(key);
419 }
420 template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
421 {
422 this->remove_contained__impl(key, hash_(key));
423 }
424
432 class Iterator {
433 public:
434 using iterator_category = std::forward_iterator_tag;
436 using pointer = const Key *;
437 using reference = const Key &;
438 using difference_type = std::ptrdiff_t;
439
440 private:
441 const Slot *slots_;
442 int64_t total_slots_;
443 int64_t current_slot_;
444
445 friend Set;
446
447 public:
448 Iterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
449 : slots_(slots), total_slots_(total_slots), current_slot_(current_slot)
450 {
451 }
452
454 {
455 while (++current_slot_ < total_slots_) {
456 if (slots_[current_slot_].is_occupied()) {
457 break;
458 }
459 }
460 return *this;
461 }
462
464 {
465 Iterator copied_iterator = *this;
466 ++(*this);
467 return copied_iterator;
468 }
469
470 const Key &operator*() const
471 {
472 return *slots_[current_slot_].key();
473 }
474
475 const Key *operator->() const
476 {
477 return slots_[current_slot_].key();
478 }
479
480 friend bool operator!=(const Iterator &a, const Iterator &b)
481 {
482 BLI_assert(a.slots_ == b.slots_);
483 BLI_assert(a.total_slots_ == b.total_slots_);
484 return a.current_slot_ != b.current_slot_;
485 }
486
487 friend bool operator==(const Iterator &a, const Iterator &b)
488 {
489 return !(a != b);
490 }
491
492 protected:
493 const Slot &current_slot() const
494 {
495 return slots_[current_slot_];
496 }
497 };
498
499 Iterator begin() const
500 {
501 for (int64_t i = 0; i < slots_.size(); i++) {
502 if (slots_[i].is_occupied()) {
503 return Iterator(slots_.data(), slots_.size(), i);
504 }
505 }
506 return this->end();
507 }
508
509 Iterator end() const
510 {
511 return Iterator(slots_.data(), slots_.size(), slots_.size());
512 }
513
519 void remove(const Iterator &it)
520 {
521 /* The const cast is valid because this method itself is not const. */
522 Slot &slot = const_cast<Slot &>(it.current_slot());
523 BLI_assert(slot.is_occupied());
524 slot.remove();
525 removed_slots_++;
526 }
527
534 template<typename Predicate> int64_t remove_if(Predicate &&predicate)
535 {
536 const int64_t prev_size = this->size();
537 for (Slot &slot : slots_) {
538 if (slot.is_occupied()) {
539 const Key &key = *slot.key();
540 if (predicate(key)) {
541 slot.remove();
542 removed_slots_++;
543 }
544 }
545 }
546 return prev_size - this->size();
547 }
548
552 void print_stats(const char *name) const
553 {
554 HashTableStats stats(*this, *this);
555 stats.print(name);
556 }
557
562 int64_t count_collisions(const Key &key) const
563 {
564 return this->count_collisions__impl(key, hash_(key));
565 }
566
570 void clear()
571 {
572 std::destroy_at(this);
573 new (this) Set(NoExceptConstructor{});
574 }
575
584 {
585 for (Slot &slot : slots_) {
586 slot.~Slot();
587 new (&slot) Slot();
588 }
589
590 removed_slots_ = 0;
591 occupied_and_removed_slots_ = 0;
592 }
593
598 void rehash()
599 {
600 this->realloc_and_reinsert(this->size());
601 }
602
606 int64_t size() const
607 {
608 return occupied_and_removed_slots_ - removed_slots_;
609 }
610
614 bool is_empty() const
615 {
616 return occupied_and_removed_slots_ == removed_slots_;
617 }
618
623 {
624 return slots_.size();
625 }
626
631 {
632 return removed_slots_;
633 }
634
639 {
640 return sizeof(Slot);
641 }
642
648 {
649 return sizeof(Slot) * slots_.size();
650 }
651
656 void reserve(const int64_t n)
657 {
658 if (usable_slots_ < n) {
659 this->realloc_and_reinsert(n);
660 }
661 }
662
666 static bool Intersects(const Set &a, const Set &b)
667 {
668 /* Make sure we iterate over the shorter set. */
669 if (a.size() > b.size()) {
670 return Intersects(b, a);
671 }
672
673 for (const Key &key : a) {
674 if (b.contains(key)) {
675 return true;
676 }
677 }
678 return false;
679 }
680
684 static bool Disjoint(const Set &a, const Set &b)
685 {
686 return !Intersects(a, b);
687 }
688
689 friend bool operator==(const Set &a, const Set &b)
690 {
691 if (a.size() != b.size()) {
692 return false;
693 }
694 for (const Key &key : a) {
695 if (!b.contains(key)) {
696 return false;
697 }
698 }
699 return true;
700 }
701
702 friend bool operator!=(const Set &a, const Set &b)
703 {
704 return !(a == b);
705 }
706
707 private:
708 BLI_NOINLINE void realloc_and_reinsert(int64_t min_usable_slots)
709 {
710 /* Avoid rebuilding the hash table just to get rid of a few removed slots. In this case, also
711 * increase the set size to avoid a bad edge case. */
712 min_usable_slots = std::max(min_usable_slots, this->size() * 2);
713
714 int64_t total_slots, usable_slots;
715 max_load_factor_.compute_total_and_usable_slots(
716 SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots);
717 BLI_assert(total_slots >= 1);
718 const uint64_t new_slot_mask = uint64_t(total_slots) - 1;
719
723 if (this->size() == 0) {
724 try {
725 slots_.reinitialize(total_slots);
726 }
727 catch (...) {
728 this->noexcept_reset();
729 throw;
730 }
731 removed_slots_ = 0;
732 occupied_and_removed_slots_ = 0;
733 usable_slots_ = usable_slots;
734 slot_mask_ = new_slot_mask;
735 return;
736 }
737
738 /* The grown array that we insert the keys into. */
739 SlotArray new_slots(total_slots);
740
741 try {
742 for (Slot &slot : slots_) {
743 if (slot.is_occupied()) {
744 this->add_after_grow(slot, new_slots, new_slot_mask);
745 slot.remove();
746 }
747 }
748 slots_ = std::move(new_slots);
749 }
750 catch (...) {
751 this->noexcept_reset();
752 throw;
753 }
754
755 occupied_and_removed_slots_ -= removed_slots_;
756 usable_slots_ = usable_slots;
757 removed_slots_ = 0;
758 slot_mask_ = new_slot_mask;
759 }
760
761 void add_after_grow(Slot &old_slot, SlotArray &new_slots, const uint64_t new_slot_mask)
762 {
763 const uint64_t hash = old_slot.get_hash(Hash());
764
765 SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
766 Slot &slot = new_slots[slot_index];
767 if (slot.is_empty()) {
768 slot.occupy(std::move(*old_slot.key()), hash);
769 return;
770 }
771 }
773 }
774
779 void noexcept_reset() noexcept
780 {
781 Allocator allocator = slots_.allocator();
782 this->~Set();
783 new (this) Set(NoExceptConstructor(), allocator);
784 }
785
786 template<typename ForwardKey>
787 bool contains__impl(const ForwardKey &key, const uint64_t hash) const
788 {
790 if (slot.is_empty()) {
791 return false;
792 }
793 if (slot.contains(key, is_equal_, hash)) {
794 return true;
795 }
796 }
798 }
799
800 template<typename ForwardKey>
801 const Key &lookup_key__impl(const ForwardKey &key, const uint64_t hash) const
802 {
803 BLI_assert(this->contains_as(key));
804
806 if (slot.contains(key, is_equal_, hash)) {
807 return *slot.key();
808 }
809 }
811 }
812
813 template<typename ForwardKey>
814 const Key *lookup_key_ptr__impl(const ForwardKey &key, const uint64_t hash) const
815 {
817 if (slot.contains(key, is_equal_, hash)) {
818 return slot.key();
819 }
820 if (slot.is_empty()) {
821 return nullptr;
822 }
823 }
825 }
826
827 template<typename ForwardKey> void add_new__impl(ForwardKey &&key, const uint64_t hash)
828 {
829 BLI_assert(!this->contains_as(key));
830
831 this->ensure_can_add();
832
834 if (slot.is_empty()) {
835 slot.occupy(std::forward<ForwardKey>(key), hash);
836 BLI_assert(hash_(*slot.key()) == hash);
837 BLI_assert(is_equal_(*slot.key(), *slot.key()));
838 occupied_and_removed_slots_++;
839 return;
840 }
841 }
843 }
844
845 template<typename ForwardKey> bool add__impl(ForwardKey &&key, const uint64_t hash)
846 {
847 this->ensure_can_add();
848
850 if (slot.is_empty()) {
851 slot.occupy(std::forward<ForwardKey>(key), hash);
852 BLI_assert(hash_(*slot.key()) == hash);
853 BLI_assert(is_equal_(*slot.key(), *slot.key()));
854 occupied_and_removed_slots_++;
855 return true;
856 }
857 if (slot.contains(key, is_equal_, hash)) {
858 return false;
859 }
860 }
862 }
863
864 template<typename ForwardKey> bool add_overwrite__impl(ForwardKey &&key, const uint64_t hash)
865 {
866 this->ensure_can_add();
867
869 if (slot.is_empty()) {
870 slot.occupy(std::forward<ForwardKey>(key), hash);
871 BLI_assert(hash_(*slot.key()) == hash);
872 BLI_assert(is_equal_(*slot.key(), *slot.key()));
873 occupied_and_removed_slots_++;
874 return true;
875 }
876 if (slot.contains(key, is_equal_, hash)) {
877 Key &stored_key = *slot.key();
878 stored_key = std::forward<ForwardKey>(key);
879 BLI_assert(hash_(stored_key) == hash);
880 return false;
881 }
882 }
884 }
885
886 template<typename ForwardKey> bool remove__impl(const ForwardKey &key, const uint64_t hash)
887 {
889 if (slot.contains(key, is_equal_, hash)) {
890 slot.remove();
891 removed_slots_++;
892 return true;
893 }
894 if (slot.is_empty()) {
895 return false;
896 }
897 }
899 }
900
901 template<typename ForwardKey>
902 void remove_contained__impl(const ForwardKey &key, const uint64_t hash)
903 {
904 BLI_assert(this->contains_as(key));
905
907 if (slot.contains(key, is_equal_, hash)) {
908 slot.remove();
909 removed_slots_++;
910 return;
911 }
912 }
914 }
915
916 template<typename ForwardKey>
917 const Key &lookup_key_or_add__impl(ForwardKey &&key, const uint64_t hash)
918 {
919 this->ensure_can_add();
920
922 if (slot.contains(key, is_equal_, hash)) {
923 return *slot.key();
924 }
925 if (slot.is_empty()) {
926 slot.occupy(std::forward<ForwardKey>(key), hash);
927 BLI_assert(hash_(*slot.key()) == hash);
928 BLI_assert(is_equal_(*slot.key(), *slot.key()));
929 occupied_and_removed_slots_++;
930 return *slot.key();
931 }
932 }
934 }
935
936 template<typename ForwardKey, typename CreateKeyF>
937 const Key &lookup_key_or_add_cb__impl(ForwardKey &&key,
938 const uint64_t hash,
939 CreateKeyF &&create_key)
940 {
941 this->ensure_can_add();
942
944 if (slot.contains(key, is_equal_, hash)) {
945 return *slot.key();
946 }
947 if (slot.is_empty()) {
948 slot.occupy(create_key(), hash);
949 BLI_assert(hash_(*slot.key()) == hash);
950 BLI_assert(is_equal_(*slot.key(), *slot.key()));
951 occupied_and_removed_slots_++;
952 return *slot.key();
953 }
954 }
956 }
957
958 template<typename ForwardKey>
959 int64_t count_collisions__impl(const ForwardKey &key, const uint64_t hash) const
960 {
961 int64_t collisions = 0;
962
964 if (slot.contains(key, is_equal_, hash)) {
965 return collisions;
966 }
967 if (slot.is_empty()) {
968 return collisions;
969 }
970 collisions++;
971 }
973 }
974
975 void ensure_can_add()
976 {
977 if (occupied_and_removed_slots_ >= usable_slots_) {
978 this->realloc_and_reinsert(this->size() + 1);
979 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
980 }
981 }
982};
983
988template<typename Key,
989 int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)),
990 typename ProbingStrategy = DefaultProbingStrategy,
991 typename Hash = DefaultHash<Key>,
992 typename IsEqual = DefaultEquality<Key>,
993 typename Slot = typename DefaultSetSlot<Key>::type>
995
996} // namespace blender
#define LOAD_FACTOR
Definition BLI_map.hh:162
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define SET_SLOT_PROBING_END()
Definition BLI_set.hh:160
#define SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
Definition BLI_set.hh:157
#define BLI_assert(a)
#define BLI_NOINLINE
#define BLI_NO_UNIQUE_ADDRESS
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
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)
Iterator operator++(int)
Definition BLI_set.hh:463
std::ptrdiff_t difference_type
Definition BLI_set.hh:438
friend bool operator!=(const Iterator &a, const Iterator &b)
Definition BLI_set.hh:480
Iterator & operator++()
Definition BLI_set.hh:453
const Key * operator->() const
Definition BLI_set.hh:475
std::forward_iterator_tag iterator_category
Definition BLI_set.hh:434
const Key & operator*() const
Definition BLI_set.hh:470
const Key & reference
Definition BLI_set.hh:437
const Slot & current_slot() const
Definition BLI_set.hh:493
friend bool operator==(const Iterator &a, const Iterator &b)
Definition BLI_set.hh:487
const Key * pointer
Definition BLI_set.hh:436
Iterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
Definition BLI_set.hh:448
Set(NoExceptConstructor, Allocator allocator={}) noexcept
Definition BLI_set.hh:177
const std::string & lookup_key_or_add_as(ForwardKey &&key)
Definition BLI_set.hh:375
void remove(const Iterator &it)
Definition BLI_set.hh:519
const std::string & const_reference
Definition BLI_set.hh:113
int64_t size_per_element() const
Definition BLI_set.hh:638
const Key & lookup_key_default(const Key &key, const Key &default_value) const
Definition BLI_set.hh:336
bool remove_as(const ForwardKey &key)
Definition BLI_set.hh:408
bool add_overwrite_as(ForwardKey &&key)
Definition BLI_set.hh:275
Set(const std::initializer_list< Key > &values)
Definition BLI_set.hh:187
int64_t size_in_bytes() const
Definition BLI_set.hh:647
void clear_and_keep_capacity()
Definition BLI_set.hh:583
~Set()=default
Set(const Set &other)=default
Iterator begin() const
Definition BLI_set.hh:499
const Key & lookup_key_or_add(const Key &key)
Definition BLI_set.hh:367
void add_multiple_new(Span< Key > keys)
Definition BLI_set.hh:298
const Key & lookup_key(const Key &key) const
Definition BLI_set.hh:323
void print_stats(const char *name) const
Definition BLI_set.hh:552
static bool Disjoint(const Set &a, const Set &b)
Definition BLI_set.hh:684
bool add(Key &&key)
Definition BLI_set.hh:252
const std::string & lookup_key_as(const ForwardKey &key) const
Definition BLI_set.hh:327
bool add_as(ForwardKey &&key)
Definition BLI_set.hh:256
int64_t removed_amount() const
Definition BLI_set.hh:630
bool contains_as(const ForwardKey &key) const
Definition BLI_set.hh:314
void reserve(const int64_t n)
Definition BLI_set.hh:656
const std::string & lookup_key_default_as(const ForwardKey &key, const std::string &default_key) const
Definition BLI_set.hh:341
Iterator end() const
Definition BLI_set.hh:509
Set(Span< Key > values, Allocator allocator={})
Definition BLI_set.hh:179
void remove_contained(const Key &key)
Definition BLI_set.hh:416
const std::string * const_pointer
Definition BLI_set.hh:111
friend bool operator!=(const Set &a, const Set &b)
Definition BLI_set.hh:702
bool contains(const Key &key) const
Definition BLI_set.hh:310
static bool Intersects(const Set &a, const Set &b)
Definition BLI_set.hh:666
int64_t capacity() const
Definition BLI_set.hh:622
const Key & lookup_key_or_add_cb(const Key &key, CreateValueF &&create_value)
Definition BLI_set.hh:388
int64_t count_collisions(const Key &key) const
Definition BLI_set.hh:562
friend bool operator==(const Set &a, const Set &b)
Definition BLI_set.hh:689
bool add_overwrite(Key &&key)
Definition BLI_set.hh:271
bool add(const Key &key)
Definition BLI_set.hh:248
Set & operator=(const Set &other)
Definition BLI_set.hh:218
bool is_empty() const
Definition BLI_set.hh:614
Set & operator=(Set &&other)
Definition BLI_set.hh:223
void add_multiple(Span< Key > keys)
Definition BLI_set.hh:287
const std::string * lookup_key_ptr_as(const ForwardKey &key) const
Definition BLI_set.hh:358
const std::string & lookup_key_or_add_cb_as(ForwardKey &&key, CreateValueF &&create_value)
Definition BLI_set.hh:393
Set(Set &&other) noexcept(std::is_nothrow_move_constructible_v< SlotArray >)
Definition BLI_set.hh:193
void add_new(const Key &key)
Definition BLI_set.hh:233
bool add_overwrite(const Key &key)
Definition BLI_set.hh:267
const Key & lookup_key_or_add(Key &&key)
Definition BLI_set.hh:371
Set(Allocator allocator={}) noexcept
Definition BLI_set.hh:168
int64_t remove_if(Predicate &&predicate)
Definition BLI_set.hh:534
void clear()
Definition BLI_set.hh:570
void remove_contained_as(const ForwardKey &key)
Definition BLI_set.hh:420
const Key * lookup_key_ptr(const Key &key) const
Definition BLI_set.hh:354
bool remove(const Key &key)
Definition BLI_set.hh:404
void rehash()
Definition BLI_set.hh:598
void add_new(Key &&key)
Definition BLI_set.hh:237
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
Container & copy_assign_container(Container &dst, const Container &src)
Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator > RawSet
Definition BLI_set.hh:994
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)
PythonProbingStrategy<> DefaultProbingStrategy
@ Hash
Definition types.hh:49
#define hash
Definition noise_c.cc:156
SimpleSetSlot< Key > type