123 int64_t occupied_and_removed_slots_;
144#define LOAD_FACTOR 1, 2
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()
168 Set(Allocator allocator = {})
noexcept
170 occupied_and_removed_slots_(0),
193 Set(
Set &&other)
noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
197 if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
198 slots_ = std::move(other.slots_);
202 slots_ = std::move(other.slots_);
205 other.noexcept_reset();
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();
235 this->add_new__impl(key, hash_(key));
239 this->add_new__impl(std::move(key), hash_(key));
254 return this->
add_as(std::move(key));
256 template<
typename ForwardKey>
bool add_as(ForwardKey &&key)
258 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
277 return this->add_overwrite__impl(std::forward<ForwardKey>(key), hash_(key));
289 for (
const Key &key : keys) {
300 for (
const Key &key : keys) {
314 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
316 return this->contains__impl(key, hash_(key));
329 return this->lookup_key__impl(key, hash_(key));
340 template<
typename ForwardKey>
343 const Key *ptr = this->lookup_key_ptr__impl(key, hash_(key));
344 if (ptr ==
nullptr) {
360 return this->lookup_key_ptr__impl(key, hash_(key));
377 return this->lookup_key_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
387 template<
typename CreateValueF>
392 template<
typename ForwardKey,
typename CreateValueF>
395 return this->lookup_key_or_add_cb__impl(
396 std::forward<ForwardKey>(key), hash_(key), std::forward<CreateValueF>(create_value));
408 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
410 return this->remove__impl(key, hash_(key));
422 this->remove_contained__impl(key, hash_(key));
449 : slots_(slots), total_slots_(total_slots), current_slot_(
current_slot)
455 while (++current_slot_ < total_slots_) {
456 if (slots_[current_slot_].is_occupied()) {
467 return copied_iterator;
472 return *slots_[current_slot_].key();
477 return slots_[current_slot_].key();
484 return a.current_slot_ !=
b.current_slot_;
495 return slots_[current_slot_];
501 for (
int64_t i = 0; i < slots_.size(); i++) {
502 if (slots_[i].is_occupied()) {
503 return Iterator(slots_.data(), slots_.size(), i);
511 return Iterator(slots_.data(), slots_.size(), slots_.size());
522 Slot &slot =
const_cast<Slot &
>(it.current_slot());
537 for (
Slot &slot : slots_) {
538 if (slot.is_occupied()) {
539 const Key &key = *slot.key();
540 if (predicate(key)) {
546 return prev_size - this->
size();
564 return this->count_collisions__impl(key, hash_(key));
572 std::destroy_at(
this);
585 for (
Slot &slot : slots_) {
591 occupied_and_removed_slots_ = 0;
600 this->realloc_and_reinsert(this->
size());
608 return occupied_and_removed_slots_ - removed_slots_;
616 return occupied_and_removed_slots_ == removed_slots_;
624 return slots_.size();
632 return removed_slots_;
649 return sizeof(
Slot) * slots_.size();
658 if (usable_slots_ < n) {
659 this->realloc_and_reinsert(n);
669 if (a.
size() >
b.size()) {
673 for (
const Key &key : a) {
674 if (
b.contains(key)) {
691 if (a.
size() !=
b.size()) {
694 for (
const Key &key : a) {
695 if (!
b.contains(key)) {
712 min_usable_slots = std::max(min_usable_slots, this->
size() * 2);
714 int64_t total_slots, usable_slots;
723 if (this->
size() == 0) {
728 this->noexcept_reset();
732 occupied_and_removed_slots_ = 0;
733 usable_slots_ = usable_slots;
734 slot_mask_ = new_slot_mask;
739 SlotArray new_slots(total_slots);
742 for (Slot &slot : slots_) {
743 if (slot.is_occupied()) {
744 this->add_after_grow(slot, new_slots, new_slot_mask);
748 slots_ = std::move(new_slots);
751 this->noexcept_reset();
755 occupied_and_removed_slots_ -= removed_slots_;
756 usable_slots_ = usable_slots;
758 slot_mask_ = new_slot_mask;
761 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
const uint64_t new_slot_mask)
766 Slot &slot = new_slots[slot_index];
767 if (slot.is_empty()) {
768 slot.occupy(std::move(*old_slot.key()),
hash);
779 void noexcept_reset() noexcept
781 Allocator allocator = slots_.allocator();
783 new (
this)
Set(NoExceptConstructor(), allocator);
786 template<
typename ForwardKey>
787 bool contains__impl(
const ForwardKey &key,
const uint64_t hash)
const
790 if (slot.is_empty()) {
793 if (slot.contains(key, is_equal_,
hash)) {
800 template<
typename ForwardKey>
801 const Key &lookup_key__impl(
const ForwardKey &key,
const uint64_t hash)
const
806 if (slot.contains(key, is_equal_,
hash)) {
813 template<
typename ForwardKey>
814 const Key *lookup_key_ptr__impl(
const ForwardKey &key,
const uint64_t hash)
const
817 if (slot.contains(key, is_equal_,
hash)) {
820 if (slot.is_empty()) {
827 template<
typename ForwardKey>
void add_new__impl(ForwardKey &&key,
const uint64_t hash)
831 this->ensure_can_add();
834 if (slot.is_empty()) {
835 slot.occupy(std::forward<ForwardKey>(key),
hash);
837 BLI_assert(is_equal_(*slot.key(), *slot.key()));
838 occupied_and_removed_slots_++;
845 template<
typename ForwardKey>
bool add__impl(ForwardKey &&key,
const uint64_t hash)
847 this->ensure_can_add();
850 if (slot.is_empty()) {
851 slot.occupy(std::forward<ForwardKey>(key),
hash);
853 BLI_assert(is_equal_(*slot.key(), *slot.key()));
854 occupied_and_removed_slots_++;
857 if (slot.contains(key, is_equal_,
hash)) {
864 template<
typename ForwardKey>
bool add_overwrite__impl(ForwardKey &&key,
const uint64_t hash)
866 this->ensure_can_add();
869 if (slot.is_empty()) {
870 slot.occupy(std::forward<ForwardKey>(key),
hash);
872 BLI_assert(is_equal_(*slot.key(), *slot.key()));
873 occupied_and_removed_slots_++;
876 if (slot.contains(key, is_equal_,
hash)) {
877 Key &stored_key = *slot.key();
878 stored_key = std::forward<ForwardKey>(key);
886 template<
typename ForwardKey>
bool remove__impl(
const ForwardKey &key,
const uint64_t hash)
889 if (slot.contains(key, is_equal_,
hash)) {
894 if (slot.is_empty()) {
901 template<
typename ForwardKey>
902 void remove_contained__impl(
const ForwardKey &key,
const uint64_t hash)
907 if (slot.contains(key, is_equal_,
hash)) {
916 template<
typename ForwardKey>
917 const Key &lookup_key_or_add__impl(ForwardKey &&key,
const uint64_t hash)
919 this->ensure_can_add();
922 if (slot.contains(key, is_equal_,
hash)) {
925 if (slot.is_empty()) {
926 slot.occupy(std::forward<ForwardKey>(key),
hash);
928 BLI_assert(is_equal_(*slot.key(), *slot.key()));
929 occupied_and_removed_slots_++;
936 template<
typename ForwardKey,
typename CreateKeyF>
937 const Key &lookup_key_or_add_cb__impl(ForwardKey &&key,
939 CreateKeyF &&create_key)
941 this->ensure_can_add();
944 if (slot.contains(key, is_equal_,
hash)) {
947 if (slot.is_empty()) {
948 slot.occupy(create_key(),
hash);
950 BLI_assert(is_equal_(*slot.key(), *slot.key()));
951 occupied_and_removed_slots_++;
958 template<
typename ForwardKey>
964 if (slot.contains(key, is_equal_,
hash)) {
967 if (slot.is_empty()) {
975 void ensure_can_add()
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_);