Blender  V3.3
BLI_vector_set.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
48 #include "BLI_array.hh"
49 #include "BLI_hash.hh"
50 #include "BLI_hash_tables.hh"
52 #include "BLI_vector_set_slots.hh"
53 
54 namespace blender {
55 
56 template<
61  typename Key,
65  typename ProbingStrategy = DefaultProbingStrategy,
70  typename Hash = DefaultHash<Key>,
75  typename IsEqual = DefaultEquality,
82  typename Slot = typename DefaultVectorSetSlot<Key>::type,
87  typename Allocator = GuardedAllocator>
88 class VectorSet {
89  public:
90  using value_type = Key;
91  using pointer = Key *;
92  using const_pointer = const Key *;
93  using reference = Key &;
94  using const_reference = const Key &;
95  using iterator = Key *;
96  using const_iterator = const Key *;
97  using size_type = int64_t;
98 
99  private:
104  int64_t removed_slots_;
105  int64_t occupied_and_removed_slots_;
106 
111  int64_t usable_slots_;
112 
117  uint64_t slot_mask_;
118 
120  BLI_NO_UNIQUE_ADDRESS Hash hash_;
121 
123  BLI_NO_UNIQUE_ADDRESS IsEqual is_equal_;
124 
126 #define LOAD_FACTOR 1, 2
127  LoadFactor max_load_factor_ = LoadFactor(LOAD_FACTOR);
128  using SlotArray = Array<Slot, LoadFactor::compute_total_slots(4, LOAD_FACTOR), Allocator>;
129 #undef LOAD_FACTOR
130 
135  SlotArray slots_;
136 
142  Key *keys_ = nullptr;
143 
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()
149 
150  public:
156  VectorSet(Allocator allocator = {}) noexcept
157  : removed_slots_(0),
158  occupied_and_removed_slots_(0),
159  usable_slots_(0),
160  slot_mask_(0),
161  slots_(1, allocator),
162  keys_(nullptr)
163  {
164  }
165 
166  VectorSet(NoExceptConstructor, Allocator allocator = {}) : VectorSet(allocator)
167  {
168  }
169 
170  VectorSet(Span<Key> keys, Allocator allocator = {}) : VectorSet(NoExceptConstructor(), allocator)
171  {
172  this->add_multiple(keys);
173  }
174 
178  VectorSet(const std::initializer_list<Key> &keys, Allocator allocator = {})
179  : VectorSet(Span(keys), allocator)
180  {
181  }
182 
184  {
185  destruct_n(keys_, this->size());
186  if (keys_ != nullptr) {
187  this->deallocate_keys_array(keys_);
188  }
189  }
190 
191  VectorSet(const VectorSet &other) : slots_(other.slots_)
192  {
193  keys_ = this->allocate_keys_array(other.usable_slots_);
194  try {
195  uninitialized_copy_n(other.keys_, other.size(), keys_);
196  }
197  catch (...) {
198  this->deallocate_keys_array(keys_);
199  throw;
200  }
201 
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_;
206  hash_ = other.hash_;
207  is_equal_ = other.is_equal_;
208  }
209 
210  VectorSet(VectorSet &&other) noexcept
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_)),
216  keys_(other.keys_)
217  {
218  other.removed_slots_ = 0;
219  other.occupied_and_removed_slots_ = 0;
220  other.usable_slots_ = 0;
221  other.slot_mask_ = 0;
222  other.slots_ = SlotArray(1);
223  other.keys_ = nullptr;
224  }
225 
227  {
228  return copy_assign_container(*this, other);
229  }
230 
232  {
233  return move_assign_container(*this, std::move(other));
234  }
235 
239  const Key &operator[](const int64_t index) const
240  {
241  BLI_assert(index >= 0);
242  BLI_assert(index <= this->size());
243  return keys_[index];
244  }
245 
246  operator Span<Key>() const
247  {
248  return Span<Key>(keys_, this->size());
249  }
250 
258  {
259  return *this;
260  }
261 
267  void add_new(const Key &key)
268  {
269  this->add_new__impl(key, hash_(key));
270  }
271  void add_new(Key &&key)
272  {
273  this->add_new__impl(std::move(key), hash_(key));
274  }
275 
282  bool add(const Key &key)
283  {
284  return this->add_as(key);
285  }
286  bool add(Key &&key)
287  {
288  return this->add_as(std::move(key));
289  }
290  template<typename ForwardKey> bool add_as(ForwardKey &&key)
291  {
292  return this->add__impl(std::forward<ForwardKey>(key), hash_(key));
293  }
294 
303  {
304  for (const Key &key : keys) {
305  this->add(key);
306  }
307  }
308 
314  bool contains(const Key &key) const
315  {
316  return this->contains_as(key);
317  }
318  template<typename ForwardKey> bool contains_as(const ForwardKey &key) const
319  {
320  return this->contains__impl(key, hash_(key));
321  }
322 
329  bool remove(const Key &key)
330  {
331  return this->remove_as(key);
332  }
333  template<typename ForwardKey> bool remove_as(const ForwardKey &key)
334  {
335  return this->remove__impl(key, hash_(key));
336  }
337 
342  void remove_contained(const Key &key)
343  {
344  this->remove_contained_as(key);
345  }
346  template<typename ForwardKey> void remove_contained_as(const ForwardKey &key)
347  {
348  this->remove_contained__impl(key, hash_(key));
349  }
350 
356  {
357  return this->pop__impl();
358  }
359 
364  int64_t index_of(const Key &key) const
365  {
366  return this->index_of_as(key);
367  }
368  template<typename ForwardKey> int64_t index_of_as(const ForwardKey &key) const
369  {
370  return this->index_of__impl(key, hash_(key));
371  }
372 
377  int64_t index_of_try(const Key &key) const
378  {
379  return this->index_of_try_as(key);
380  }
381  template<typename ForwardKey> int64_t index_of_try_as(const ForwardKey &key) const
382  {
383  return this->index_of_try__impl(key, hash_(key));
384  }
385 
391  {
392  return this->index_of_or_add_as(key);
393  }
395  {
396  return this->index_of_or_add_as(std::move(key));
397  }
398  template<typename ForwardKey> int64_t index_of_or_add_as(ForwardKey &&key)
399  {
400  return this->index_of_or_add__impl(std::forward<ForwardKey>(key), hash_(key));
401  }
402 
407  const Key &lookup_key(const Key &key) const
408  {
409  return this->lookup_key_as(key);
410  }
411  template<typename ForwardKey> const Key &lookup_key_as(const ForwardKey &key) const
412  {
413  const Key *key_ptr = this->lookup_key_ptr_as(key);
414  BLI_assert(key_ptr != nullptr);
415  return *key_ptr;
416  }
417 
422  const Key *lookup_key_ptr(const Key &key) const
423  {
424  return this->lookup_key_ptr_as(key);
425  }
426  template<typename ForwardKey> const Key *lookup_key_ptr_as(const ForwardKey &key) const
427  {
428  const int64_t index = this->index_of_try__impl(key, hash_(key));
429  if (index >= 0) {
430  return keys_ + index;
431  }
432  return nullptr;
433  }
434 
438  const Key *data() const
439  {
440  return keys_;
441  }
442 
443  const Key *begin() const
444  {
445  return keys_;
446  }
447 
448  const Key *end() const
449  {
450  return keys_ + this->size();
451  }
452 
457  {
458  return IndexRange(this->size());
459  }
460 
464  void print_stats(StringRef name = "") const
465  {
466  HashTableStats stats(*this, this->as_span());
467  stats.print(name);
468  }
469 
473  int64_t size() const
474  {
475  return occupied_and_removed_slots_ - removed_slots_;
476  }
477 
481  bool is_empty() const
482  {
483  return occupied_and_removed_slots_ == removed_slots_;
484  }
485 
490  {
491  return slots_.size();
492  }
493 
498  {
499  return removed_slots_;
500  }
501 
506  {
507  return sizeof(Slot) + sizeof(Key);
508  }
509 
515  {
516  return static_cast<int64_t>(sizeof(Slot) * slots_.size() + sizeof(Key) * usable_slots_);
517  }
518 
522  void reserve(const int64_t n)
523  {
524  if (usable_slots_ < n) {
525  this->realloc_and_reinsert(n);
526  }
527  }
528 
532  void clear()
533  {
534  destruct_n(keys_, this->size());
535  for (Slot &slot : slots_) {
536  slot.~Slot();
537  new (&slot) Slot();
538  }
539 
540  removed_slots_ = 0;
541  occupied_and_removed_slots_ = 0;
542  }
543 
548  int64_t count_collisions(const Key &key) const
549  {
550  return this->count_collisions__impl(key, hash_(key));
551  }
552 
553  private:
554  BLI_NOINLINE void realloc_and_reinsert(const int64_t min_usable_slots)
555  {
556  int64_t total_slots, usable_slots;
557  max_load_factor_.compute_total_and_usable_slots(
558  SlotArray::inline_buffer_capacity(), min_usable_slots, &total_slots, &usable_slots);
559  BLI_assert(total_slots >= 1);
560  const uint64_t new_slot_mask = static_cast<uint64_t>(total_slots) - 1;
561 
562  /* Optimize the case when the set was empty beforehand. We can avoid some copies here. */
563  if (this->size() == 0) {
564  try {
565  slots_.reinitialize(total_slots);
566  if (keys_ != nullptr) {
567  this->deallocate_keys_array(keys_);
568  keys_ = nullptr;
569  }
570  keys_ = this->allocate_keys_array(usable_slots);
571  }
572  catch (...) {
573  this->noexcept_reset();
574  throw;
575  }
576  removed_slots_ = 0;
577  occupied_and_removed_slots_ = 0;
578  usable_slots_ = usable_slots;
579  slot_mask_ = new_slot_mask;
580  return;
581  }
582 
583  SlotArray new_slots(total_slots);
584 
585  try {
586  for (Slot &slot : slots_) {
587  if (slot.is_occupied()) {
588  this->add_after_grow(slot, new_slots, new_slot_mask);
589  slot.remove();
590  }
591  }
592  slots_ = std::move(new_slots);
593  }
594  catch (...) {
595  this->noexcept_reset();
596  throw;
597  }
598 
599  Key *new_keys = this->allocate_keys_array(usable_slots);
600  try {
601  uninitialized_relocate_n(keys_, this->size(), new_keys);
602  }
603  catch (...) {
604  this->deallocate_keys_array(new_keys);
605  this->noexcept_reset();
606  throw;
607  }
608  this->deallocate_keys_array(keys_);
609 
610  keys_ = new_keys;
611  occupied_and_removed_slots_ -= removed_slots_;
612  usable_slots_ = usable_slots;
613  removed_slots_ = 0;
614  slot_mask_ = new_slot_mask;
615  }
616 
617  void add_after_grow(Slot &old_slot, SlotArray &new_slots, const uint64_t new_slot_mask)
618  {
619  const Key &key = keys_[old_slot.index()];
620  const uint64_t hash = old_slot.get_hash(key, Hash());
621 
622  SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
623  Slot &slot = new_slots[slot_index];
624  if (slot.is_empty()) {
625  slot.occupy(old_slot.index(), hash);
626  return;
627  }
628  }
630  }
631 
632  void noexcept_reset() noexcept
633  {
634  Allocator allocator = slots_.allocator();
635  this->~VectorSet();
636  new (this) VectorSet(NoExceptConstructor(), allocator);
637  }
638 
639  template<typename ForwardKey>
640  bool contains__impl(const ForwardKey &key, const uint64_t hash) const
641  {
643  if (slot.is_empty()) {
644  return false;
645  }
646  if (slot.contains(key, is_equal_, hash, keys_)) {
647  return true;
648  }
649  }
651  }
652 
653  template<typename ForwardKey> void add_new__impl(ForwardKey &&key, const uint64_t hash)
654  {
655  BLI_assert(!this->contains_as(key));
656 
657  this->ensure_can_add();
658 
660  if (slot.is_empty()) {
661  int64_t index = this->size();
662  new (keys_ + index) Key(std::forward<ForwardKey>(key));
663  slot.occupy(index, hash);
664  occupied_and_removed_slots_++;
665  return;
666  }
667  }
669  }
670 
671  template<typename ForwardKey> bool add__impl(ForwardKey &&key, const uint64_t hash)
672  {
673  this->ensure_can_add();
674 
676  if (slot.is_empty()) {
677  int64_t index = this->size();
678  new (keys_ + index) Key(std::forward<ForwardKey>(key));
679  slot.occupy(index, hash);
680  occupied_and_removed_slots_++;
681  return true;
682  }
683  if (slot.contains(key, is_equal_, hash, keys_)) {
684  return false;
685  }
686  }
688  }
689 
690  template<typename ForwardKey>
691  int64_t index_of__impl(const ForwardKey &key, const uint64_t hash) const
692  {
693  BLI_assert(this->contains_as(key));
694 
696  if (slot.contains(key, is_equal_, hash, keys_)) {
697  return slot.index();
698  }
699  }
701  }
702 
703  template<typename ForwardKey>
704  int64_t index_of_try__impl(const ForwardKey &key, const uint64_t hash) const
705  {
707  if (slot.contains(key, is_equal_, hash, keys_)) {
708  return slot.index();
709  }
710  if (slot.is_empty()) {
711  return -1;
712  }
713  }
715  }
716 
717  template<typename ForwardKey>
718  int64_t index_of_or_add__impl(ForwardKey &&key, const uint64_t hash)
719  {
720  this->ensure_can_add();
721 
723  if (slot.contains(key, is_equal_, hash, keys_)) {
724  return slot.index();
725  }
726  if (slot.is_empty()) {
727  const int64_t index = this->size();
728  new (keys_ + index) Key(std::forward<ForwardKey>(key));
729  slot.occupy(index, hash);
730  occupied_and_removed_slots_++;
731  return index;
732  }
733  }
735  }
736 
737  Key pop__impl()
738  {
739  BLI_assert(this->size() > 0);
740 
741  const int64_t index_to_pop = this->size() - 1;
742  Key key = std::move(keys_[index_to_pop]);
743  keys_[index_to_pop].~Key();
744  const uint64_t hash = hash_(key);
745 
746  removed_slots_++;
747 
749  if (slot.has_index(index_to_pop)) {
750  slot.remove();
751  return key;
752  }
753  }
755  }
756 
757  template<typename ForwardKey> bool remove__impl(const ForwardKey &key, const uint64_t hash)
758  {
760  if (slot.contains(key, is_equal_, hash, keys_)) {
761  this->remove_key_internal(slot);
762  return true;
763  }
764  if (slot.is_empty()) {
765  return false;
766  }
767  }
769  }
770 
771  template<typename ForwardKey>
772  void remove_contained__impl(const ForwardKey &key, const uint64_t hash)
773  {
774  BLI_assert(this->contains_as(key));
775 
777  if (slot.contains(key, is_equal_, hash, keys_)) {
778  this->remove_key_internal(slot);
779  return;
780  }
781  }
783  }
784 
785  void remove_key_internal(Slot &slot)
786  {
787  int64_t index_to_remove = slot.index();
788  int64_t size = this->size();
789  int64_t last_element_index = size - 1;
790 
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);
794  }
795 
796  keys_[last_element_index].~Key();
797  slot.remove();
798  removed_slots_++;
799  return;
800  }
801 
802  void update_slot_index(const Key &key, const int64_t old_index, const int64_t new_index)
803  {
804  uint64_t hash = hash_(key);
806  if (slot.has_index(old_index)) {
807  slot.update_index(new_index);
808  return;
809  }
810  }
812  }
813 
814  template<typename ForwardKey>
815  int64_t count_collisions__impl(const ForwardKey &key, const uint64_t hash) const
816  {
817  int64_t collisions = 0;
818 
820  if (slot.contains(key, is_equal_, hash, keys_)) {
821  return collisions;
822  }
823  if (slot.is_empty()) {
824  return collisions;
825  }
826  collisions++;
827  }
829  }
830 
831  void ensure_can_add()
832  {
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_);
836  }
837  }
838 
839  Key *allocate_keys_array(const int64_t size)
840  {
841  return static_cast<Key *>(
842  slots_.allocator().allocate(sizeof(Key) * static_cast<size_t>(size), alignof(Key), AT));
843  }
844 
845  void deallocate_keys_array(Key *keys)
846  {
847  slots_.allocator().deallocate(keys);
848  }
849 };
850 
855 template<typename Key,
856  typename ProbingStrategy = DefaultProbingStrategy,
857  typename Hash = DefaultHash<Key>,
858  typename IsEqual = DefaultEquality,
859  typename Slot = typename DefaultVectorSetSlot<Key>::type>
861 
862 } // namespace blender
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_NOINLINE
#define SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define SLOT_PROBING_END()
#define AT
#define BLI_NO_UNIQUE_ADDRESS
#define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT)
#define LOAD_FACTOR
#define VECTOR_SET_SLOT_PROBING_END()
struct Key Key
static int64_t inline_buffer_capacity()
Definition: BLI_array.hh:378
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)
bool add(const Key &key)
bool add(Key &&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
const Key * data() 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)
int64_t size() const
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)
const Key * end() const
bool is_empty() const
VectorSet & operator=(VectorSet &&other)
int64_t removed_amount() const
int64_t capacity() const
VectorSet(const VectorSet &other)
const Key & operator[](const int64_t index) const
void add_new(Key &&key)
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)
#define hash
Definition: noise.c:153
__int64 int64_t
Definition: stdint.h:89
unsigned __int64 uint64_t
Definition: stdint.h:90
SimpleVectorSetSlot< Key > type