111 int64_t occupied_and_removed_slots_;
132#define LOAD_FACTOR 1, 2
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()
163 template<
typename Other,
164 int64_t OtherInlineBufferCapacity,
165 typename OtherProbingStrategy,
167 typename OtherIsEqual,
169 typename OtherAllocator>
180 occupied_and_removed_slots_(0),
185 keys_ = inline_buffer_;
190 hash_ = std::move(
hash);
204 VectorSet(
const std::initializer_list<Key> &keys, Allocator allocator = {})
212 if (keys_ != inline_buffer_) {
213 this->deallocate_keys_array(keys_);
219 if (other.
size() <= InlineBufferCapacity) {
220 usable_slots_ = other.size();
221 keys_ = inline_buffer_;
224 keys_ = this->allocate_keys_array(other.usable_slots_);
225 usable_slots_ = other.usable_slots_;
228 uninitialized_copy_n(other.keys_, other.size(), keys_);
231 if (keys_ != inline_buffer_) {
232 this->deallocate_keys_array(keys_);
237 removed_slots_ = other.removed_slots_;
238 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
239 slot_mask_ = other.slot_mask_;
241 is_equal_ = other.is_equal_;
244 template<
int64_t OtherInlineBufferCapacity>
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_))
253 if (other.is_inline()) {
255 usable_slots_ =
size;
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)
263 keys_ = inline_buffer_;
265 memcpy(inline_buffer_, other.inline_buffer_,
sizeof(inline_buffer_));
269 if (OtherInlineBufferCapacity <= InlineBufferCapacity ||
size <= InlineBufferCapacity) {
270 keys_ = inline_buffer_;
273 keys_ = this->allocate_keys_array(
size);
280 usable_slots_ = other.usable_slots_;
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_;
338 this->add_new__impl(key, hash_(key));
342 this->add_new__impl(std::move(key), hash_(key));
357 return this->
add_as(std::move(key));
359 template<
typename ForwardKey>
bool add_as(ForwardKey &&key)
361 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
384 return this->add_overwrite__impl(std::forward<ForwardKey>(key), hash_(key));
396 for (
const Key &key : keys) {
410 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
412 return this->contains__impl(key, hash_(key));
427 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
429 return this->remove__impl(key, hash_(key));
442 this->remove_contained__impl(key, hash_(key));
454 for (
Slot &slot : slots_) {
455 if (slot.is_occupied()) {
458 if (predicate(key)) {
459 this->remove_key_internal(slot);
463 return prev_size - this->
size();
472 return this->pop__impl();
485 return this->index_of__impl(key, hash_(key));
498 return this->index_of_try__impl(key, hash_(key));
515 return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
541 template<
typename ForwardKey,
typename... ForwardDefault>
545 if (ptr ==
nullptr) {
546 return Key(std::forward<ForwardDefault>(default_key)...);
561 const int64_t index = this->index_of_try__impl(key, hash_(key));
563 return keys_ +
index;
583 return keys_ + this->
size();
605 return keys_ == inline_buffer_;
613 return occupied_and_removed_slots_ - removed_slots_;
621 return occupied_and_removed_slots_ == removed_slots_;
629 return slots_.size();
637 return removed_slots_;
645 return sizeof(
Slot) +
sizeof(
Key);
654 return int64_t(
sizeof(
Slot) * slots_.size() +
sizeof(
Key) * usable_slots_);
662 if (usable_slots_ < n) {
663 this->realloc_and_reinsert(n);
672 std::destroy_at(
this);
686 for (
Slot &slot : slots_) {
692 occupied_and_removed_slots_ = 0;
701 return this->count_collisions__impl(key, hash_(key));
720 data.data = this->allocate_keys_array(
size);
727 this->deallocate_keys_array(
data.data);
734 data.capacity = usable_slots_;
739 keys_ = inline_buffer_;
740 occupied_and_removed_slots_ = 0;
742 std::destroy_at(
this);
753 min_usable_slots = std::max(min_usable_slots, this->
size() * 2);
755 int64_t total_slots, usable_slots;
756 max_load_factor_.compute_total_and_usable_slots(
762 if (this->
size() == 0) {
764 slots_.reinitialize(total_slots);
767 if (usable_slots <= InlineBufferCapacity) {
768 new_keys = inline_buffer_;
771 new_keys = this->allocate_keys_array(usable_slots);
774 if (keys_ != inline_buffer_) {
775 this->deallocate_keys_array(keys_);
781 this->noexcept_reset();
785 occupied_and_removed_slots_ = 0;
786 usable_slots_ = usable_slots;
787 slot_mask_ = new_slot_mask;
791 SlotArray new_slots(total_slots);
794 for (Slot &slot : slots_) {
795 if (slot.is_occupied()) {
796 this->add_after_grow(slot, new_slots, new_slot_mask);
800 slots_ = std::move(new_slots);
803 this->noexcept_reset();
809 if (usable_slots <= InlineBufferCapacity) {
810 new_keys = inline_buffer_;
813 new_keys = this->allocate_keys_array(usable_slots);
818 if (new_keys != keys_) {
823 if (new_keys != inline_buffer_) {
824 this->deallocate_keys_array(new_keys);
826 this->noexcept_reset();
832 if (keys_ != inline_buffer_) {
833 this->deallocate_keys_array(keys_);
837 occupied_and_removed_slots_ -= removed_slots_;
838 usable_slots_ = usable_slots;
840 slot_mask_ = new_slot_mask;
843 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
const uint64_t new_slot_mask)
845 const Key &key = keys_[old_slot.index()];
849 Slot &slot = new_slots[slot_index];
850 if (slot.is_empty()) {
851 slot.occupy(old_slot.index(),
hash);
858 void noexcept_reset() noexcept
860 Allocator allocator = slots_.allocator();
862 new (
this)
VectorSet(NoExceptConstructor(), allocator);
865 template<
typename ForwardKey>
866 bool contains__impl(
const ForwardKey &key,
const uint64_t hash)
const
869 if (slot.is_empty()) {
872 if (slot.contains(key, is_equal_,
hash, keys_)) {
879 template<
typename ForwardKey>
void add_new__impl(ForwardKey &&key,
const uint64_t hash)
883 this->ensure_can_add();
886 if (slot.is_empty()) {
888 Key *dst = keys_ +
index;
889 new (dst) Key(std::forward<ForwardKey>(key));
893 occupied_and_removed_slots_++;
900 template<
typename ForwardKey>
bool add__impl(ForwardKey &&key,
const uint64_t hash)
902 this->ensure_can_add();
905 if (slot.is_empty()) {
907 Key *dst = keys_ +
index;
908 new (dst) Key(std::forward<ForwardKey>(key));
912 occupied_and_removed_slots_++;
915 if (slot.contains(key, is_equal_,
hash, keys_)) {
922 template<
typename ForwardKey>
bool add_overwrite__impl(ForwardKey &&key,
const uint64_t hash)
924 this->ensure_can_add();
927 if (slot.is_empty()) {
929 Key *dst = keys_ +
index;
930 new (dst) Key(std::forward<ForwardKey>(key));
934 occupied_and_removed_slots_++;
937 if (slot.contains(key, is_equal_,
hash, keys_)) {
939 Key &stored_key = keys_[
index];
940 stored_key = std::forward<ForwardKey>(key);
948 template<
typename ForwardKey>
954 if (slot.contains(key, is_equal_,
hash, keys_)) {
961 template<
typename ForwardKey>
965 if (slot.contains(key, is_equal_,
hash, keys_)) {
968 if (slot.is_empty()) {
975 template<
typename ForwardKey>
978 this->ensure_can_add();
981 if (slot.contains(key, is_equal_,
hash, keys_)) {
984 if (slot.is_empty()) {
986 Key *dst = keys_ +
index;
987 new (dst) Key(std::forward<ForwardKey>(key));
991 occupied_and_removed_slots_++;
1003 Key key = std::move(keys_[index_to_pop]);
1004 keys_[index_to_pop].~Key();
1010 if (slot.has_index(index_to_pop)) {
1018 template<
typename ForwardKey>
bool remove__impl(
const ForwardKey &key,
const uint64_t hash)
1021 if (slot.contains(key, is_equal_,
hash, keys_)) {
1022 this->remove_key_internal(slot);
1025 if (slot.is_empty()) {
1032 template<
typename ForwardKey>
1033 void remove_contained__impl(
const ForwardKey &key,
const uint64_t hash)
1038 if (slot.contains(key, is_equal_,
hash, keys_)) {
1039 this->remove_key_internal(slot);
1046 void remove_key_internal(Slot &slot)
1048 int64_t index_to_remove = slot.index();
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);
1057 keys_[last_element_index].~Key();
1062 void update_slot_index(
const Key &key,
const int64_t old_index,
const int64_t new_index)
1066 if (slot.has_index(old_index)) {
1067 slot.update_index(new_index);
1074 template<
typename ForwardKey>
1080 if (slot.contains(key, is_equal_,
hash, keys_)) {
1083 if (slot.is_empty()) {
1091 void ensure_can_add()
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_);
1101 return static_cast<Key *
>(
1102 slots_.allocator().
allocate(
sizeof(Key) *
size_t(
size),
alignof(Key),
AT));
1105 void deallocate_keys_array(Key *keys)
1107 slots_.allocator().deallocate(keys);