58 #include <unordered_set>
87 typename Hash = DefaultHash<Key>,
92 typename IsEqual = DefaultEquality,
124 int64_t occupied_and_removed_slots_;
145 #define LOAD_FACTOR 1, 2
146 LoadFactor max_load_factor_ = LoadFactor(
LOAD_FACTOR);
158 #define SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
159 SLOT_PROBING_BEGIN (ProbingStrategy, HASH, slot_mask_, SLOT_INDEX) \
160 auto &R_SLOT = slots_[SLOT_INDEX];
161 #define SET_SLOT_PROBING_END() SLOT_PROBING_END()
169 Set(Allocator allocator = {}) noexcept
171 occupied_and_removed_slots_(0),
198 Set(
Set &&other) noexcept(std::is_nothrow_move_constructible_v<SlotArray>)
202 if constexpr (std::is_nothrow_move_constructible_v<SlotArray>) {
203 slots_ = std::move(other.slots_);
207 slots_ = std::move(other.slots_);
210 other.noexcept_reset();
214 removed_slots_ = other.removed_slots_;
215 occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
216 usable_slots_ = other.usable_slots_;
217 slot_mask_ = other.slot_mask_;
218 hash_ = std::move(other.hash_);
219 is_equal_ = std::move(other.is_equal_);
220 other.noexcept_reset();
240 this->add_new__impl(key, hash_(key));
244 this->add_new__impl(std::move(key), hash_(key));
259 return this->
add_as(std::move(key));
261 template<
typename ForwardKey>
bool add_as(ForwardKey &&key)
263 return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
275 for (
const Key &key : keys) {
286 for (
const Key &key : keys) {
300 template<
typename ForwardKey>
bool contains_as(
const ForwardKey &key)
const
302 return this->contains__impl(key, hash_(key));
315 return this->lookup_key__impl(key, hash_(key));
326 template<
typename ForwardKey>
329 const Key *
ptr = this->lookup_key_ptr__impl(key, hash_(key));
330 if (
ptr ==
nullptr) {
346 return this->lookup_key_ptr__impl(key, hash_(key));
363 return this->lookup_key_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
375 template<
typename ForwardKey>
bool remove_as(
const ForwardKey &key)
377 return this->remove__impl(key, hash_(key));
389 this->remove_contained__impl(key, hash_(key));
416 : slots_(slots), total_slots_(total_slots), current_slot_(
current_slot)
422 while (++current_slot_ < total_slots_) {
423 if (slots_[current_slot_].is_occupied()) {
434 return copied_iterator;
439 return *slots_[current_slot_].key();
444 return slots_[current_slot_].key();
451 return a.current_slot_ !=
b.current_slot_;
462 return slots_[current_slot_];
468 for (
int64_t i = 0; i < slots_.size(); i++) {
469 if (slots_[i].is_occupied()) {
470 return Iterator(slots_.data(), slots_.size(), i);
478 return Iterator(slots_.data(), slots_.size(), slots_.size());
510 return this->count_collisions__impl(key, hash_(key));
518 for (Slot &slot : slots_) {
524 occupied_and_removed_slots_ = 0;
533 this->realloc_and_reinsert(this->
size());
541 return occupied_and_removed_slots_ - removed_slots_;
549 return occupied_and_removed_slots_ == removed_slots_;
557 return slots_.size();
565 return removed_slots_;
582 return sizeof(Slot) * slots_.size();
591 if (usable_slots_ < n) {
592 this->realloc_and_reinsert(n);
602 if (
a.size() >
b.size()) {
606 for (
const Key &key :
a) {
607 if (
b.contains(key)) {
625 int64_t total_slots, usable_slots;
626 max_load_factor_.compute_total_and_usable_slots(
634 if (this->
size() == 0) {
636 slots_.reinitialize(total_slots);
639 this->noexcept_reset();
643 occupied_and_removed_slots_ = 0;
644 usable_slots_ = usable_slots;
645 slot_mask_ = new_slot_mask;
650 SlotArray new_slots(total_slots);
653 for (Slot &slot : slots_) {
654 if (slot.is_occupied()) {
655 this->add_after_grow(slot, new_slots, new_slot_mask);
659 slots_ = std::move(new_slots);
662 this->noexcept_reset();
666 occupied_and_removed_slots_ -= removed_slots_;
667 usable_slots_ = usable_slots;
669 slot_mask_ = new_slot_mask;
672 void add_after_grow(Slot &old_slot, SlotArray &new_slots,
const uint64_t new_slot_mask)
677 Slot &slot = new_slots[slot_index];
678 if (slot.is_empty()) {
679 slot.occupy(std::move(*old_slot.key()),
hash);
690 void noexcept_reset() noexcept
692 Allocator allocator = slots_.allocator();
694 new (
this)
Set(NoExceptConstructor(), allocator);
697 template<
typename ForwardKey>
698 bool contains__impl(
const ForwardKey &key,
const uint64_t hash)
const
701 if (slot.is_empty()) {
704 if (slot.contains(key, is_equal_,
hash)) {
711 template<
typename ForwardKey>
712 const Key &lookup_key__impl(
const ForwardKey &key,
const uint64_t hash)
const
717 if (slot.contains(key, is_equal_,
hash)) {
724 template<
typename ForwardKey>
725 const Key *lookup_key_ptr__impl(
const ForwardKey &key,
const uint64_t hash)
const
728 if (slot.contains(key, is_equal_,
hash)) {
731 if (slot.is_empty()) {
738 template<
typename ForwardKey>
void add_new__impl(ForwardKey &&key,
const uint64_t hash)
742 this->ensure_can_add();
745 if (slot.is_empty()) {
746 slot.occupy(std::forward<ForwardKey>(key),
hash);
747 occupied_and_removed_slots_++;
754 template<
typename ForwardKey>
bool add__impl(ForwardKey &&key,
const uint64_t hash)
756 this->ensure_can_add();
759 if (slot.is_empty()) {
760 slot.occupy(std::forward<ForwardKey>(key),
hash);
761 occupied_and_removed_slots_++;
764 if (slot.contains(key, is_equal_,
hash)) {
771 template<
typename ForwardKey>
bool remove__impl(
const ForwardKey &key,
const uint64_t hash)
774 if (slot.contains(key, is_equal_,
hash)) {
779 if (slot.is_empty()) {
786 template<
typename ForwardKey>
787 void remove_contained__impl(
const ForwardKey &key,
const uint64_t hash)
792 if (slot.contains(key, is_equal_,
hash)) {
801 template<
typename ForwardKey>
802 const Key &lookup_key_or_add__impl(ForwardKey &&key,
const uint64_t hash)
804 this->ensure_can_add();
807 if (slot.contains(key, is_equal_,
hash)) {
810 if (slot.is_empty()) {
811 slot.occupy(std::forward<ForwardKey>(key),
hash);
812 occupied_and_removed_slots_++;
819 template<
typename ForwardKey>
825 if (slot.contains(key, is_equal_,
hash)) {
828 if (slot.is_empty()) {
836 void ensure_can_add()
838 if (occupied_and_removed_slots_ >= usable_slots_) {
839 this->realloc_and_reinsert(this->
size() + 1);
840 BLI_assert(occupied_and_removed_slots_ < usable_slots_);
851 using SetType = std::unordered_set<Key, blender::DefaultHash<Key>>;
857 return static_cast<int64_t>(set_.size());
876 set_.insert(std::move(key));
881 return set_.insert(key).second;
885 return set_.insert(std::move(key)).second;
890 for (
const Key &key : keys) {
897 return set_.find(key) != set_.end();
902 return (
bool)set_.erase(key);
907 return set_.erase(key);
915 typename SetType::iterator
begin()
const
920 typename SetType::iterator
end()
const
930 template<
typename Key,
933 typename Hash = DefaultHash<Key>,
934 typename IsEqual = DefaultEquality,
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define SET_SLOT_PROBING_END()
#define SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
#define BLI_NO_UNIQUE_ADDRESS
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)
std::ptrdiff_t difference_type
friend bool operator!=(const Iterator &a, const Iterator &b)
const Key * operator->() const
const Key & operator*() const
std::forward_iterator_tag iterator_category
friend bool operator==(const Iterator &a, const Iterator &b)
Iterator(const Slot *slots, int64_t total_slots, int64_t current_slot)
const Slot & current_slot() const
Iterator operator++(int) const
Set(NoExceptConstructor, Allocator allocator={}) noexcept
void remove(const Iterator &it)
const Key & lookup_key_or_add(Key &&key)
int64_t size_per_element() const
const Key & lookup_key_default_as(const ForwardKey &key, const Key &default_key) const
bool remove_as(const ForwardKey &key)
Set(const std::initializer_list< Key > &values)
Set & operator=(const Set &other)
int64_t size_in_bytes() const
Set & operator=(Set &&other)
Set(const Set &other)=default
void add_multiple_new(Span< Key > keys)
const Key * lookup_key_ptr(const Key &key) const
static bool Disjoint(const Set &a, const Set &b)
const Key & lookup_key(const Key &key) const
bool add_as(ForwardKey &&key)
int64_t removed_amount() const
bool contains_as(const ForwardKey &key) const
void reserve(const int64_t n)
const Key * lookup_key_ptr_as(const ForwardKey &key) const
Set(Span< Key > values, Allocator allocator={})
void remove_contained(const Key &key)
bool contains(const Key &key) const
static bool Intersects(const Set &a, const Set &b)
const Key & lookup_key_or_add_as(ForwardKey &&key)
const Key & lookup_key_or_add(const Key &key)
int64_t count_collisions(const Key &key) const
void add_multiple(Span< Key > keys)
Set(Set &&other) noexcept(std::is_nothrow_move_constructible_v< SlotArray >)
void add_new(const Key &key)
Set(Allocator allocator={}) noexcept
void remove_contained_as(const ForwardKey &key)
void print_stats(StringRef name="") const
const Key & lookup_key_default(const Key &key, const Key &default_value) const
bool remove(const Key &key)
const Key & lookup_key_as(const ForwardKey &key) const
bool remove(const Key &key)
bool contains(const Key &key) const
void remove_contained(const Key &key)
SetType::iterator begin() const
void add_multiple(Span< Key > keys)
void add_new(const Key &key)
SetType::iterator end() const
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
constexpr int64_t default_inline_buffer_capacity(size_t element_size)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
unsigned __int64 uint64_t
SimpleSetSlot< Key > type