70 typename Hash = DefaultHash<Key>,
75 typename IsEqual = DefaultEquality,
105 int64_t occupied_and_removed_slots_;
126 #define LOAD_FACTOR 1, 2
127 LoadFactor max_load_factor_ = LoadFactor(
LOAD_FACTOR);
142 Key *keys_ =
nullptr;
145 #define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
146 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
147 auto &R_SLOT = slots_[SLOT_INDEX];
148 #define VECTOR_SET_SLOT_PROBING_END() SLOT_PROBING_END()
158 occupied_and_removed_slots_(0),
161 slots_(1, allocator),
178 VectorSet(
const std::initializer_list<Key> &keys, Allocator allocator = {})
186 if (keys_ !=
nullptr) {
187 this->deallocate_keys_array(keys_);
193 keys_ = this->allocate_keys_array(other.usable_slots_);
198 this->deallocate_keys_array(keys_);
202 removed_slots_ = other.removed_slots_;
203 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
204 usable_slots_ = other.usable_slots_;
205 slot_mask_ = other.slot_mask_;
207 is_equal_ = other.is_equal_;
211 : removed_slots_(other.removed_slots_),
212 occupied_and_removed_slots_(other.occupied_and_removed_slots_),
213 usable_slots_(other.usable_slots_),
214 slot_mask_(other.slot_mask_),
215 slots_(std::move(other.slots_)),
218 other.removed_slots_ = 0;
219 other.occupied_and_removed_slots_ = 0;
220 other.usable_slots_ = 0;
221 other.slot_mask_ = 0;
223 other.keys_ =
nullptr;
269 this->add_new__impl(key, hash_(key));
273 this->add_new__impl(std::move(key), hash_(key));
288 return this->
add_as(std::move(key));
290 template<
typename ForwardKey>
bool add_as(ForwardKey &&key)
292 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
304 for (
const Key &key : keys) {
318 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
320 return this->contains__impl(key, hash_(key));
333 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
335 return this->remove__impl(key, hash_(key));
348 this->remove_contained__impl(key, hash_(key));
357 return this->pop__impl();
370 return this->index_of__impl(key, hash_(key));
383 return this->index_of_try__impl(key, hash_(key));
400 return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
428 const int64_t index = this->index_of_try__impl(key, hash_(key));
430 return keys_ + index;
450 return keys_ + this->
size();
475 return occupied_and_removed_slots_ - removed_slots_;
483 return occupied_and_removed_slots_ == removed_slots_;
491 return slots_.size();
499 return removed_slots_;
507 return sizeof(Slot) +
sizeof(
Key);
516 return static_cast<int64_t>(
sizeof(Slot) * slots_.size() +
sizeof(
Key) * usable_slots_);
524 if (usable_slots_ < n) {
525 this->realloc_and_reinsert(n);
535 for (Slot &slot : slots_) {
541 occupied_and_removed_slots_ = 0;
550 return this->count_collisions__impl(key, hash_(key));
556 int64_t total_slots, usable_slots;
557 max_load_factor_.compute_total_and_usable_slots(
563 if (this->
size() == 0) {
565 slots_.reinitialize(total_slots);
566 if (keys_ !=
nullptr) {
567 this->deallocate_keys_array(keys_);
570 keys_ = this->allocate_keys_array(usable_slots);
573 this->noexcept_reset();
577 occupied_and_removed_slots_ = 0;
578 usable_slots_ = usable_slots;
579 slot_mask_ = new_slot_mask;
583 SlotArray new_slots(total_slots);
586 for (Slot &slot : slots_) {
587 if (slot.is_occupied()) {
588 this->add_after_grow(slot, new_slots, new_slot_mask);
592 slots_ = std::move(new_slots);
595 this->noexcept_reset();
599 Key *new_keys = this->allocate_keys_array(usable_slots);
604 this->deallocate_keys_array(new_keys);
605 this->noexcept_reset();
608 this->deallocate_keys_array(keys_);
611 occupied_and_removed_slots_ -= removed_slots_;
612 usable_slots_ = usable_slots;
614 slot_mask_ = new_slot_mask;
617 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
const uint64_t new_slot_mask)
619 const Key &key = keys_[old_slot.index()];
623 Slot &slot = new_slots[slot_index];
624 if (slot.is_empty()) {
625 slot.occupy(old_slot.index(),
hash);
632 void noexcept_reset() noexcept
634 Allocator allocator = slots_.allocator();
636 new (
this)
VectorSet(NoExceptConstructor(), allocator);
639 template<
typename ForwardKey>
640 bool contains__impl(
const ForwardKey &key,
const uint64_t hash)
const
643 if (slot.is_empty()) {
646 if (slot.contains(key, is_equal_,
hash, keys_)) {
653 template<
typename ForwardKey>
void add_new__impl(ForwardKey &&key,
const uint64_t hash)
657 this->ensure_can_add();
660 if (slot.is_empty()) {
662 new (keys_ + index)
Key(std::forward<ForwardKey>(key));
663 slot.occupy(index,
hash);
664 occupied_and_removed_slots_++;
671 template<
typename ForwardKey>
bool add__impl(ForwardKey &&key,
const uint64_t hash)
673 this->ensure_can_add();
676 if (slot.is_empty()) {
678 new (keys_ + index)
Key(std::forward<ForwardKey>(key));
679 slot.occupy(index,
hash);
680 occupied_and_removed_slots_++;
683 if (slot.contains(key, is_equal_,
hash, keys_)) {
690 template<
typename ForwardKey>
696 if (slot.contains(key, is_equal_,
hash, keys_)) {
703 template<
typename ForwardKey>
707 if (slot.contains(key, is_equal_,
hash, keys_)) {
710 if (slot.is_empty()) {
717 template<
typename ForwardKey>
720 this->ensure_can_add();
723 if (slot.contains(key, is_equal_,
hash, keys_)) {
726 if (slot.is_empty()) {
728 new (keys_ + index)
Key(std::forward<ForwardKey>(key));
729 slot.occupy(index,
hash);
730 occupied_and_removed_slots_++;
742 Key key = std::move(keys_[index_to_pop]);
743 keys_[index_to_pop].~Key();
749 if (slot.has_index(index_to_pop)) {
757 template<
typename ForwardKey>
bool remove__impl(
const ForwardKey &key,
const uint64_t hash)
760 if (slot.contains(key, is_equal_,
hash, keys_)) {
761 this->remove_key_internal(slot);
764 if (slot.is_empty()) {
771 template<
typename ForwardKey>
772 void remove_contained__impl(
const ForwardKey &key,
const uint64_t hash)
777 if (slot.contains(key, is_equal_,
hash, keys_)) {
778 this->remove_key_internal(slot);
785 void remove_key_internal(Slot &slot)
787 int64_t index_to_remove = slot.index();
791 if (index_to_remove < last_element_index) {
792 keys_[index_to_remove] = std::move(keys_[last_element_index]);
793 this->update_slot_index(keys_[index_to_remove], last_element_index, index_to_remove);
796 keys_[last_element_index].~Key();
802 void update_slot_index(
const Key &key,
const int64_t old_index,
const int64_t new_index)
806 if (slot.has_index(old_index)) {
807 slot.update_index(new_index);
814 template<
typename ForwardKey>
820 if (slot.contains(key, is_equal_,
hash, keys_)) {
823 if (slot.is_empty()) {
831 void ensure_can_add()
833 if (occupied_and_removed_slots_ >= usable_slots_) {
834 this->realloc_and_reinsert(this->
size() + 1);
835 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
841 return static_cast<Key *
>(
842 slots_.allocator().allocate(
sizeof(
Key) *
static_cast<size_t>(
size),
alignof(
Key),
AT));
845 void deallocate_keys_array(
Key *keys)
847 slots_.allocator().deallocate(keys);
855 template<
typename Key,
857 typename Hash = DefaultHash<Key>,
858 typename IsEqual = DefaultEquality,
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define BLI_NO_UNIQUE_ADDRESS
#define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
#define VECTOR_SET_SLOT_PROBING_END()
static int64_t inline_buffer_capacity()
void print(StringRef name="")
static constexpr int64_t compute_total_slots(int64_t min_usable_slots, uint8_t numerator, uint8_t denominator)
Span< Key > as_span() const
VectorSet & operator=(const VectorSet &other)
VectorSet(VectorSet &&other) noexcept
int64_t index_of(const Key &key) const
void reserve(const int64_t n)
int64_t count_collisions(const Key &key) const
int64_t index_of_or_add_as(ForwardKey &&key)
const Key * begin() const
int64_t index_of_try_as(const ForwardKey &key) const
const Key & lookup_key(const Key &key) const
void add_new(const Key &key)
const Key * lookup_key_ptr(const Key &key) const
int64_t index_of_as(const ForwardKey &key) const
bool add_as(ForwardKey &&key)
const Key & lookup_key_as(const ForwardKey &key) const
bool contains_as(const ForwardKey &key) const
int64_t size_per_element() const
VectorSet(Allocator allocator={}) noexcept
VectorSet(Span< Key > keys, Allocator allocator={})
void print_stats(StringRef name="") const
int64_t index_of_try(const Key &key) const
const Key * lookup_key_ptr_as(const ForwardKey &key) const
IndexRange index_range() const
int64_t size_in_bytes() const
int64_t index_of_or_add(Key &&key)
void remove_contained_as(const ForwardKey &key)
VectorSet(NoExceptConstructor, Allocator allocator={})
VectorSet(const std::initializer_list< Key > &keys, Allocator allocator={})
void remove_contained(const Key &key)
VectorSet & operator=(VectorSet &&other)
int64_t removed_amount() const
VectorSet(const VectorSet &other)
const Key & operator[](const int64_t index) const
bool contains(const Key &key) const
bool remove_as(const ForwardKey &key)
int64_t index_of_or_add(const Key &key)
void add_multiple(Span< Key > keys)
bool remove(const Key &key)
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
void uninitialized_relocate_n(T *src, int64_t n, T *dst)
void destruct_n(T *ptr, int64_t n)
void uninitialized_copy_n(const T *src, int64_t n, T *dst)
unsigned __int64 uint64_t
SimpleVectorSetSlot< Key > type