Blender V5.3
BLI_vector_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
48
49#include "BLI_array.hh"
50#include "BLI_hash.hh"
51#include "BLI_hash_tables.hh"
53#include "BLI_vector.hh"
55
56namespace blender {
57
58template<
63 typename Key,
67 int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)),
71 typename ProbingStrategy = DefaultProbingStrategy,
76 typename Hash = DefaultHash<Key>,
81 typename IsEqual = DefaultEquality<Key>,
88 typename Slot = typename DefaultVectorSetSlot<Key>::type,
93 typename Allocator = GuardedAllocator>
94class VectorSet {
95 public:
96 using value_type = Key;
97 using pointer = Key *;
98 using const_pointer = const Key *;
99 using reference = Key &;
100 using const_reference = const Key &;
101 using iterator = Key *;
102 using const_iterator = const Key *;
104
105 private:
110 int64_t removed_slots_;
111 int64_t occupied_and_removed_slots_;
112
117 int64_t usable_slots_;
118
123 uint64_t slot_mask_;
124
127
129 BLI_NO_UNIQUE_ADDRESS IsEqual is_equal_;
130
132#define LOAD_FACTOR 1, 2
133 static constexpr LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR);
134 using SlotArray = Array<Slot, LoadFactor::compute_total_slots(4, LOAD_FACTOR), Allocator>;
135#undef LOAD_FACTOR
136
141 SlotArray slots_;
142
144 BLI_NO_UNIQUE_ADDRESS TypedBuffer<Key, InlineBufferCapacity> inline_buffer_;
145
151 Key *keys_;
152
154#define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
155 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
156 auto &R_SLOT = slots_[SLOT_INDEX];
157#define VECTOR_SET_SLOT_PROBING_END() SLOT_PROBING_END()
158
163 template<typename Other,
164 int64_t OtherInlineBufferCapacity,
165 typename OtherProbingStrategy,
166 typename OtherHash,
167 typename OtherIsEqual,
168 typename OtherSlot,
169 typename OtherAllocator>
170 friend class VectorSet;
171
172 public:
178 VectorSet(Allocator allocator = {}) noexcept
179 : removed_slots_(0),
180 occupied_and_removed_slots_(0),
181 usable_slots_(0),
182 slot_mask_(0),
183 slots_(1, allocator)
184 {
185 keys_ = inline_buffer_;
186 }
187
189 {
190 hash_ = std::move(hash);
191 is_equal_ = std::move(is_equal);
192 }
193
194 VectorSet(NoExceptConstructor, Allocator allocator = {}) : VectorSet(allocator) {}
195
196 VectorSet(Span<Key> keys, Allocator allocator = {}) : VectorSet(NoExceptConstructor(), allocator)
197 {
198 this->add_multiple(keys);
199 }
200
204 VectorSet(const std::initializer_list<Key> &keys, Allocator allocator = {})
205 : VectorSet(Span(keys), allocator)
206 {
207 }
208
210 {
211 destruct_n(keys_, this->size());
212 if (keys_ != inline_buffer_) {
213 this->deallocate_keys_array(keys_);
214 }
215 }
216
217 VectorSet(const VectorSet &other) : slots_(other.slots_)
218 {
219 if (other.size() <= InlineBufferCapacity) {
220 usable_slots_ = other.size();
221 keys_ = inline_buffer_;
222 }
223 else {
224 keys_ = this->allocate_keys_array(other.usable_slots_);
225 usable_slots_ = other.usable_slots_;
226 }
227 try {
228 uninitialized_copy_n(other.keys_, other.size(), keys_);
229 }
230 catch (...) {
231 if (keys_ != inline_buffer_) {
232 this->deallocate_keys_array(keys_);
233 }
234 throw;
235 }
236
237 removed_slots_ = other.removed_slots_;
238 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
239 slot_mask_ = other.slot_mask_;
240 hash_ = other.hash_;
241 is_equal_ = other.is_equal_;
242 }
243
244 template<int64_t OtherInlineBufferCapacity>
247 &&other) noexcept
248 : removed_slots_(other.removed_slots_),
249 occupied_and_removed_slots_(other.occupied_and_removed_slots_),
250 slot_mask_(other.slot_mask_),
251 slots_(std::move(other.slots_))
252 {
253 if (other.is_inline()) {
254 const int64_t size = other.size();
255 usable_slots_ = size;
256
257 constexpr bool other_is_same_type = std::is_same_v<VectorSet, std::decay_t<decltype(other)>>;
258 constexpr size_t max_full_copy_size = 32;
259 if constexpr (other_is_same_type && std::is_trivial_v<Key> &&
260 sizeof(inline_buffer_) <= max_full_copy_size)
261 {
262 /* Optimize by copying the full inline buffer. Similar to #Vector move constructor. */
263 keys_ = inline_buffer_;
264 if (size > 0) {
265 memcpy(inline_buffer_, other.inline_buffer_, sizeof(inline_buffer_));
266 }
267 }
268 else {
269 if (OtherInlineBufferCapacity <= InlineBufferCapacity || size <= InlineBufferCapacity) {
270 keys_ = inline_buffer_;
271 }
272 else {
273 keys_ = this->allocate_keys_array(size);
274 }
275 uninitialized_relocate_n(other.keys_, size, keys_);
276 }
277 }
278 else {
279 keys_ = other.keys_;
280 usable_slots_ = other.usable_slots_;
281 }
282 other.removed_slots_ = 0;
283 other.occupied_and_removed_slots_ = 0;
284 other.usable_slots_ = 0;
285 other.slot_mask_ = 0;
286 other.slots_ = SlotArray(1);
287 other.keys_ = other.inline_buffer_;
288 }
289
291 {
292 return copy_assign_container(*this, other);
293 }
294
296 {
297 return move_assign_container(*this, std::move(other));
298 }
299
303 const Key &operator[](const int64_t index) const
304 {
305 BLI_assert(index >= 0);
307 return keys_[index];
308 }
309
310 operator Span<Key>() const
311 {
312 return Span<Key>(keys_, this->size());
313 }
314
315 friend bool operator==(const VectorSet &a, const VectorSet &b)
316 {
317 return a.as_span() == b.as_span();
318 }
319
327 {
328 return *this;
329 }
330
336 void add_new(const Key &key)
337 {
338 this->add_new__impl(key, hash_(key));
339 }
340 void add_new(Key &&key)
341 {
342 this->add_new__impl(std::move(key), hash_(key));
343 }
344
351 bool add(const Key &key)
352 {
353 return this->add_as(key);
354 }
355 bool add(Key &&key)
356 {
357 return this->add_as(std::move(key));
358 }
359 template<typename ForwardKey> bool add_as(ForwardKey &&key)
360 {
361 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
362 }
363
374 bool add_overwrite(const Key &key)
375 {
376 return this->add_overwrite_as(key);
377 }
378 bool add_overwrite(Key &&key)
379 {
380 return this->add_overwrite_as(std::move(key));
381 }
382 template<typename ForwardKey> bool add_overwrite_as(ForwardKey &&key)
383 {
384 return this->add_overwrite__impl(std::forward<ForwardKey>(key), hash_(key));
385 }
386
395 {
396 for (const Key &key : keys) {
397 this->add(key);
398 }
399 }
400
406 bool contains(const Key &key) const
407 {
408 return this->contains_as(key);
409 }
410 template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
411 {
412 return this->contains__impl(key, hash_(key));
413 }
414
423 bool remove(const Key &key)
424 {
425 return this->remove_as(key);
426 }
427 template<typename ForwardKey> bool remove_as(const ForwardKey &key)
428 {
429 return this->remove__impl(key, hash_(key));
430 }
431
436 void remove_contained(const Key &key)
437 {
438 this->remove_contained_as(key);
439 }
440 template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
441 {
442 this->remove_contained__impl(key, hash_(key));
443 }
444
451 template<typename Predicate> int64_t remove_if(Predicate &&predicate)
452 {
453 const int64_t prev_size = this->size();
454 for (Slot &slot : slots_) {
455 if (slot.is_occupied()) {
456 const int64_t index = slot.index();
457 const Key &key = keys_[index];
458 if (predicate(key)) {
459 this->remove_key_internal(slot);
460 }
461 }
462 }
463 return prev_size - this->size();
464 }
465
471 {
472 return this->pop__impl();
473 }
474
479 int64_t index_of(const Key &key) const
480 {
481 return this->index_of_as(key);
482 }
483 template<typename ForwardKey> int64_t index_of_as(const ForwardKey &key) const
484 {
485 return this->index_of__impl(key, hash_(key));
486 }
487
492 int64_t index_of_try(const Key &key) const
493 {
494 return this->index_of_try_as(key);
495 }
496 template<typename ForwardKey> int64_t index_of_try_as(const ForwardKey &key) const
497 {
498 return this->index_of_try__impl(key, hash_(key));
499 }
500
506 {
507 return this->index_of_or_add_as(key);
508 }
510 {
511 return this->index_of_or_add_as(std::move(key));
512 }
513 template<typename ForwardKey> int64_t index_of_or_add_as(ForwardKey &&key)
514 {
515 return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
516 }
517
522 const Key &lookup_key(const Key &key) const
523 {
524 return this->lookup_key_as(key);
525 }
526 template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
527 {
528 const Key *key_ptr = this->lookup_key_ptr_as(key);
529 BLI_assert(key_ptr != nullptr);
530 return *key_ptr;
531 }
532
537 Key lookup_key_default(const Key &key, const Key &default_value) const
538 {
539 return this->lookup_key_default_as(key, default_value);
540 }
541 template<typename ForwardKey, typename... ForwardDefault>
542 Key lookup_key_default_as(const ForwardKey &key, ForwardDefault &&...default_key) const
543 {
544 const Key *ptr = this->lookup_key_ptr_as(key);
545 if (ptr == nullptr) {
546 return Key(std::forward<ForwardDefault>(default_key)...);
547 }
548 return *ptr;
549 }
550
555 const Key *lookup_key_ptr(const Key &key) const
556 {
557 return this->lookup_key_ptr_as(key);
558 }
559 template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
560 {
561 const int64_t index = this->index_of_try__impl(key, hash_(key));
562 if (index >= 0) {
563 return keys_ + index;
564 }
565 return nullptr;
566 }
567
571 const Key *data() const
572 {
573 return keys_;
574 }
575
576 const Key *begin() const
577 {
578 return keys_;
579 }
580
581 const Key *end() const
582 {
583 return keys_ + this->size();
584 }
585
590 {
591 return IndexRange(this->size());
592 }
593
597 void print_stats(const char *name) const
598 {
599 HashTableStats stats(*this, this->as_span());
600 stats.print(name);
601 }
602
603 bool is_inline() const
604 {
605 return keys_ == inline_buffer_;
606 }
607
611 int64_t size() const
612 {
613 return occupied_and_removed_slots_ - removed_slots_;
614 }
615
619 bool is_empty() const
620 {
621 return occupied_and_removed_slots_ == removed_slots_;
622 }
623
628 {
629 return slots_.size();
630 }
631
636 {
637 return removed_slots_;
638 }
639
644 {
645 return sizeof(Slot) + sizeof(Key);
646 }
647
653 {
654 return int64_t(sizeof(Slot) * slots_.size() + sizeof(Key) * usable_slots_);
655 }
656
660 void reserve(const int64_t n)
661 {
662 if (usable_slots_ < n) {
663 this->realloc_and_reinsert(n);
664 }
665 }
666
670 void clear()
671 {
672 std::destroy_at(this);
673 new (this) VectorSet(NoExceptConstructor{});
674 }
675
684 {
685 destruct_n(keys_, this->size());
686 for (Slot &slot : slots_) {
687 slot.~Slot();
688 new (&slot) Slot();
689 }
690
691 removed_slots_ = 0;
692 occupied_and_removed_slots_ = 0;
693 }
694
699 int64_t count_collisions(const Key &key) const
700 {
701 return this->count_collisions__impl(key, hash_(key));
702 }
703
704 using VectorT = Vector<Key, default_inline_buffer_capacity(sizeof(Key)), Allocator>;
705
716 {
717 const int64_t size = this->size();
719 if (this->is_inline()) {
720 data.data = this->allocate_keys_array(size);
721 data.size = size;
722 data.capacity = size;
723 try {
724 uninitialized_relocate_n(keys_, size, data.data);
725 }
726 catch (...) {
727 this->deallocate_keys_array(data.data);
728 throw;
729 }
730 }
731 else {
732 data.data = keys_;
733 data.size = size;
734 data.capacity = usable_slots_;
735 }
736
737 /* Reset some values so that the destructor does not free the data that is moved to the
738 * #Vector. */
739 keys_ = inline_buffer_;
740 occupied_and_removed_slots_ = 0;
741 removed_slots_ = 0;
742 std::destroy_at(this);
743 new (this) VectorSet();
744
745 return VectorT(data);
746 }
747
748 private:
749 BLI_NOINLINE void realloc_and_reinsert(int64_t min_usable_slots)
750 {
751 /* Avoid rebuilding the hash table just to get rid of a few removed slots. In this case, also
752 * increase the set size to avoid a bad edge case. */
753 min_usable_slots = std::max(min_usable_slots, this->size() * 2);
754
755 int64_t total_slots, usable_slots;
756 max_load_factor_.compute_total_and_usable_slots(
757 SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots);
758 BLI_assert(total_slots >= 1);
759 const uint64_t new_slot_mask = uint64_t(total_slots) - 1;
760
761 /* Optimize the case when the set was empty beforehand. We can avoid some copies here. */
762 if (this->size() == 0) {
763 try {
764 slots_.reinitialize(total_slots);
765
766 Key *new_keys;
767 if (usable_slots <= InlineBufferCapacity) {
768 new_keys = inline_buffer_;
769 }
770 else {
771 new_keys = this->allocate_keys_array(usable_slots);
772 }
773
774 if (keys_ != inline_buffer_) {
775 this->deallocate_keys_array(keys_);
776 }
777
778 keys_ = new_keys;
779 }
780 catch (...) {
781 this->noexcept_reset();
782 throw;
783 }
784 removed_slots_ = 0;
785 occupied_and_removed_slots_ = 0;
786 usable_slots_ = usable_slots;
787 slot_mask_ = new_slot_mask;
788 return;
789 }
790
791 SlotArray new_slots(total_slots);
792
793 try {
794 for (Slot &slot : slots_) {
795 if (slot.is_occupied()) {
796 this->add_after_grow(slot, new_slots, new_slot_mask);
797 slot.remove();
798 }
799 }
800 slots_ = std::move(new_slots);
801 }
802 catch (...) {
803 this->noexcept_reset();
804 throw;
805 }
806
807 /* Allocate the new keys array, or use the inline buffer if possible. */
808 Key *new_keys;
809 if (usable_slots <= InlineBufferCapacity) {
810 new_keys = inline_buffer_;
811 }
812 else {
813 new_keys = this->allocate_keys_array(usable_slots);
814 }
815
816 /* Copy the keys to the new array. When the inline buffer isn't used before and after the
817 * reallocation (`new_keys` also references the inline buffer), no copying is necessary. */
818 if (new_keys != keys_) {
819 try {
820 uninitialized_relocate_n(keys_, this->size(), new_keys);
821 }
822 catch (...) {
823 if (new_keys != inline_buffer_) {
824 this->deallocate_keys_array(new_keys);
825 }
826 this->noexcept_reset();
827 throw;
828 }
829 }
830
831 /* Free the old keys array. */
832 if (keys_ != inline_buffer_) {
833 this->deallocate_keys_array(keys_);
834 }
835
836 keys_ = new_keys;
837 occupied_and_removed_slots_ -= removed_slots_;
838 usable_slots_ = usable_slots;
839 removed_slots_ = 0;
840 slot_mask_ = new_slot_mask;
841 }
842
843 void add_after_grow(Slot &old_slot, SlotArray &new_slots, const uint64_t new_slot_mask)
844 {
845 const Key &key = keys_[old_slot.index()];
846 const uint64_t hash = old_slot.get_hash(key, Hash());
847
848 SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
849 Slot &slot = new_slots[slot_index];
850 if (slot.is_empty()) {
851 slot.occupy(old_slot.index(), hash);
852 return;
853 }
854 }
856 }
857
858 void noexcept_reset() noexcept
859 {
860 Allocator allocator = slots_.allocator();
861 this->~VectorSet();
862 new (this) VectorSet(NoExceptConstructor(), allocator);
863 }
864
865 template<typename ForwardKey>
866 bool contains__impl(const ForwardKey &key, const uint64_t hash) const
867 {
869 if (slot.is_empty()) {
870 return false;
871 }
872 if (slot.contains(key, is_equal_, hash, keys_)) {
873 return true;
874 }
875 }
877 }
878
879 template<typename ForwardKey> void add_new__impl(ForwardKey &&key, const uint64_t hash)
880 {
881 BLI_assert(!this->contains_as(key));
882
883 this->ensure_can_add();
884
886 if (slot.is_empty()) {
887 int64_t index = this->size();
888 Key *dst = keys_ + index;
889 new (dst) Key(std::forward<ForwardKey>(key));
890 BLI_assert(hash_(*dst) == hash);
891 BLI_assert(is_equal_(*dst, *dst));
892 slot.occupy(index, hash);
893 occupied_and_removed_slots_++;
894 return;
895 }
896 }
898 }
899
900 template<typename ForwardKey> bool add__impl(ForwardKey &&key, const uint64_t hash)
901 {
902 this->ensure_can_add();
903
905 if (slot.is_empty()) {
906 const int64_t index = this->size();
907 Key *dst = keys_ + index;
908 new (dst) Key(std::forward<ForwardKey>(key));
909 BLI_assert(hash_(*dst) == hash);
910 BLI_assert(is_equal_(*dst, *dst));
911 slot.occupy(index, hash);
912 occupied_and_removed_slots_++;
913 return true;
914 }
915 if (slot.contains(key, is_equal_, hash, keys_)) {
916 return false;
917 }
918 }
920 }
921
922 template<typename ForwardKey> bool add_overwrite__impl(ForwardKey &&key, const uint64_t hash)
923 {
924 this->ensure_can_add();
925
927 if (slot.is_empty()) {
928 const int64_t index = this->size();
929 Key *dst = keys_ + index;
930 new (dst) Key(std::forward<ForwardKey>(key));
931 BLI_assert(hash_(*dst) == hash);
932 BLI_assert(is_equal_(*dst, *dst));
933 slot.occupy(index, hash);
934 occupied_and_removed_slots_++;
935 return true;
936 }
937 if (slot.contains(key, is_equal_, hash, keys_)) {
938 const int64_t index = slot.index();
939 Key &stored_key = keys_[index];
940 stored_key = std::forward<ForwardKey>(key);
941 BLI_assert(hash_(stored_key) == hash);
942 return false;
943 }
944 }
946 }
947
948 template<typename ForwardKey>
949 int64_t index_of__impl(const ForwardKey &key, const uint64_t hash) const
950 {
951 BLI_assert(this->contains_as(key));
952
954 if (slot.contains(key, is_equal_, hash, keys_)) {
955 return slot.index();
956 }
957 }
959 }
960
961 template<typename ForwardKey>
962 int64_t index_of_try__impl(const ForwardKey &key, const uint64_t hash) const
963 {
965 if (slot.contains(key, is_equal_, hash, keys_)) {
966 return slot.index();
967 }
968 if (slot.is_empty()) {
969 return -1;
970 }
971 }
973 }
974
975 template<typename ForwardKey>
976 int64_t index_of_or_add__impl(ForwardKey &&key, const uint64_t hash)
977 {
978 this->ensure_can_add();
979
981 if (slot.contains(key, is_equal_, hash, keys_)) {
982 return slot.index();
983 }
984 if (slot.is_empty()) {
985 const int64_t index = this->size();
986 Key *dst = keys_ + index;
987 new (dst) Key(std::forward<ForwardKey>(key));
988 BLI_assert(hash_(*dst) == hash);
989 BLI_assert(is_equal_(*dst, *dst));
990 slot.occupy(index, hash);
991 occupied_and_removed_slots_++;
992 return index;
993 }
994 }
996 }
997
998 Key pop__impl()
999 {
1000 BLI_assert(this->size() > 0);
1001
1002 const int64_t index_to_pop = this->size() - 1;
1003 Key key = std::move(keys_[index_to_pop]);
1004 keys_[index_to_pop].~Key();
1005 const uint64_t hash = hash_(key);
1006
1007 removed_slots_++;
1008
1010 if (slot.has_index(index_to_pop)) {
1011 slot.remove();
1012 return key;
1013 }
1014 }
1016 }
1017
1018 template<typename ForwardKey> bool remove__impl(const ForwardKey &key, const uint64_t hash)
1019 {
1021 if (slot.contains(key, is_equal_, hash, keys_)) {
1022 this->remove_key_internal(slot);
1023 return true;
1024 }
1025 if (slot.is_empty()) {
1026 return false;
1027 }
1028 }
1030 }
1031
1032 template<typename ForwardKey>
1033 void remove_contained__impl(const ForwardKey &key, const uint64_t hash)
1034 {
1035 BLI_assert(this->contains_as(key));
1036
1038 if (slot.contains(key, is_equal_, hash, keys_)) {
1039 this->remove_key_internal(slot);
1040 return;
1041 }
1042 }
1044 }
1045
1046 void remove_key_internal(Slot &slot)
1047 {
1048 int64_t index_to_remove = slot.index();
1049 int64_t size = this->size();
1050 int64_t last_element_index = size - 1;
1051
1052 if (index_to_remove < last_element_index) {
1053 keys_[index_to_remove] = std::move(keys_[last_element_index]);
1054 this->update_slot_index(keys_[index_to_remove], last_element_index, index_to_remove);
1055 }
1056
1057 keys_[last_element_index].~Key();
1058 slot.remove();
1059 removed_slots_++;
1060 }
1061
1062 void update_slot_index(const Key &key, const int64_t old_index, const int64_t new_index)
1063 {
1064 uint64_t hash = hash_(key);
1066 if (slot.has_index(old_index)) {
1067 slot.update_index(new_index);
1068 return;
1069 }
1070 }
1072 }
1073
1074 template<typename ForwardKey>
1075 int64_t count_collisions__impl(const ForwardKey &key, const uint64_t hash) const
1076 {
1077 int64_t collisions = 0;
1078
1080 if (slot.contains(key, is_equal_, hash, keys_)) {
1081 return collisions;
1082 }
1083 if (slot.is_empty()) {
1084 return collisions;
1085 }
1086 collisions++;
1087 }
1089 }
1090
1091 void ensure_can_add()
1092 {
1093 if (occupied_and_removed_slots_ >= usable_slots_) {
1094 this->realloc_and_reinsert(this->size() + 1);
1095 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
1096 }
1097 }
1098
1099 Key *allocate_keys_array(const int64_t size)
1100 {
1101 return static_cast<Key *>(
1102 slots_.allocator().allocate(sizeof(Key) * size_t(size), alignof(Key), AT));
1103 }
1104
1105 void deallocate_keys_array(Key *keys)
1106 {
1107 slots_.allocator().deallocate(keys);
1108 }
1109};
1110
1115template<typename Key,
1116 int64_t InlineBufferCapacity = 4,
1117 typename ProbingStrategy = DefaultProbingStrategy,
1118 typename Hash = DefaultHash<Key>,
1119 typename IsEqual = DefaultEquality<Key>,
1120 typename Slot = typename DefaultVectorSetSlot<Key>::type>
1123
1124template<typename T, typename GetIDFn> struct CustomIDHash {
1125 using CustomIDType = decltype(GetIDFn{}(std::declval<T>()));
1126
1127 uint64_t operator()(const T &value) const
1128 {
1129 return get_default_hash(GetIDFn{}(value));
1130 }
1132 {
1133 return get_default_hash(value);
1134 }
1135};
1136
1137template<typename T, typename GetIDFn> struct CustomIDEqual {
1138 using CustomIDType = decltype(GetIDFn{}(std::declval<T>()));
1139
1140 bool operator()(const T &a, const T &b) const
1141 {
1142 return GetIDFn{}(a) == GetIDFn{}(b);
1143 }
1144 bool operator()(const CustomIDType &a, const T &b) const
1145 {
1146 return a == GetIDFn{}(b);
1147 }
1148 bool operator()(const T &a, const CustomIDType &b) const
1149 {
1150 return GetIDFn{}(a) == b;
1151 }
1152};
1153
1161template<typename T, typename GetIDFn, int64_t InlineBufferCapacity = 4>
1163 InlineBufferCapacity,
1167
1168} // 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 VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
#define VECTOR_SET_SLOT_PROBING_END()
#define BLI_assert(a)
#define BLI_NOINLINE
#define AT
#define BLI_NO_UNIQUE_ADDRESS
long long int int64_t
void print(const char *name) const
constexpr IndexRange()=default
constexpr LoadFactor(uint8_t numerator, uint8_t denominator)
static constexpr int64_t compute_total_slots(int64_t min_usable_slots, uint8_t numerator, uint8_t denominator)
constexpr Span()=default
VectorSet(Span< Key > keys, Allocator allocator={})
VectorSet & operator=(const VectorSet &other)
int64_t index_of_try(const Key &key) const
int64_t removed_amount() const
VectorSet(Hash hash, IsEqual is_equal)
const Key * data() const
VectorSet & operator=(VectorSet &&other)
bool remove(const Key &key)
bool add_overwrite(Key &&key)
bool add(const Key &key)
void add_new(Key &&key)
const Key * lookup_key_ptr(const Key &key) const
VectorSet(Allocator allocator={}) noexcept
VectorSet(VectorSet< Key, OtherInlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator > &&other) noexcept
int64_t index_of_or_add(const Key &key)
const Key & lookup_key(const Key &key) const
int64_t capacity() const
void print_stats(const char *name) const
int64_t count_collisions(const Key &key) const
VectorSet(const std::initializer_list< Key > &keys, Allocator allocator={})
Key lookup_key_default(const Key &key, const Key &default_value) const
void reserve(const int64_t n)
int64_t index_of_or_add(Key &&key)
int64_t size_in_bytes() const
const Key * begin() const
void add_multiple(Span< Key > keys)
bool add_overwrite(const Key &key)
const Key & operator[](const int64_t index) const
int64_t index_of(const Key &key) const
const Key * end() const
VectorSet(NoExceptConstructor, Allocator allocator={})
friend bool operator==(const VectorSet &a, const VectorSet &b)
int64_t size_per_element() const
IndexRange index_range() const
VectorSet(const VectorSet &other)
bool contains(const Key &key) const
int64_t remove_if(Predicate &&predicate)
bool add(Key &&key)
Span< Key > as_span() const
void add_new(const Key &key)
void remove_contained(const Key &key)
#define index(i)
bool is_equal(float a, float b, const float epsilon)
#define T
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
VectorSet< T, InlineBufferCapacity, DefaultProbingStrategy, CustomIDHash< T, GetIDFn >, CustomIDEqual< T, GetIDFn > > CustomIDVectorSet
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)
PythonProbingStrategy<> DefaultProbingStrategy
void uninitialized_relocate_n(T *src, int64_t n, T *dst)
void destruct_n(T *ptr, int64_t n)
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252
VectorSet< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator > RawVectorSet
void allocate(PageAllocator &allocator, TileMaps &tilemaps, Statistics &stats, const uint3 global_id, const uint local_tile)
@ Hash
Definition types.hh:49
#define hash
Definition noise_c.cc:156
decltype(GetIDFn{}(std::declval< T >())) CustomIDType
bool operator()(const T &a, const CustomIDType &b) const
bool operator()(const T &a, const T &b) const
bool operator()(const CustomIDType &a, const T &b) const
uint64_t operator()(const T &value) const
decltype(GetIDFn{}(std::declval< T >())) CustomIDType
uint64_t operator()(const CustomIDType &value) const
SimpleVectorSetSlot< Key > type