openMSX
hash_set.hh
Go to the documentation of this file.
1 // hash_set
2 //
3 // Written by Wouter Vermaelen, based upon HashSet/HashMap
4 // example code and ideas provided by Jacques Van Damme.
5 
6 #ifndef HASH_SET_HH
7 #define HASH_SET_HH
8 
9 #include "stl.hh"
10 #include "unreachable.hh"
11 #include "xrange.hh"
12 #include <cassert>
13 #include <cstdlib>
14 #include <functional>
15 #include <initializer_list>
16 #include <iterator>
17 #include <new>
18 #include <type_traits>
19 #include <utility>
20 
21 namespace hash_set_impl {
22 
23 // Identity operation: accepts any type (by const or non-const reference) and
24 // returns the exact same (reference) value.
25 struct Identity {
26  template<typename T>
27  [[nodiscard]] inline T& operator()(T&& t) const { return t; }
28 };
29 
30 struct PoolIndex {
31  unsigned idx;
32  [[nodiscard]] constexpr bool operator==(const PoolIndex&) const = default;
33 };
34 static constexpr PoolIndex invalidIndex{unsigned(-1)};
35 
36 // Holds the data that will be stored in the hash_set plus some extra
37 // administrative data.
38 // - value: the actual to be stored data
39 // - hash: always equal to hasher(extract(value))
40 // - nextIdx: index of next element in a single-linked-list. This is either
41 // the list of colliding buckets in the hash, or the list of free objects
42 // in the Pool (see below).
43 template<typename Value>
44 struct Element {
45  Value value;
46  unsigned hash;
48 
49  template<typename V>
50  constexpr Element(V&& value_, unsigned hash_, PoolIndex nextIdx_)
51  : value(std::forward<V>(value_))
52  , hash(hash_)
53  , nextIdx(nextIdx_)
54  {
55  }
56 
57  template<typename... Args>
58  explicit constexpr Element(Args&&... args)
59  : value(std::forward<Args>(args)...)
60  // hash left uninitialized
61  // nextIdx left uninitialized
62  {
63  }
64 };
65 
66 
67 // Holds 'Element' objects. These objects can be in 2 states:
68 // - 'free': In that case 'nextIdx' forms a single-linked list of all
69 // free objects. 'freeIdx_' is the head of this list. Index 'invalidIndex'
70 // indicates the end of the list.
71 // - 'in-use': The Element object is in use by some other data structure,
72 // the Pool class doesn't interpret any of the Element fields.
73 template<typename Value>
74 class Pool {
75  using Elem = Element<Value>;
76 
77 public:
78  Pool() = default;
79 
80  Pool(Pool&& source) noexcept
81  : buf_ (source.buf_)
82  , freeIdx_ (source.freeIdx_)
83  , capacity_(source.capacity_)
84  {
85  source.buf_ = nullptr;
86  source.freeIdx_ = invalidIndex;
87  source.capacity_ = 0;
88  }
89 
90  Pool& operator=(Pool&& source) noexcept
91  {
92  buf_ = source.buf_;
93  freeIdx_ = source.freeIdx_;
94  capacity_ = source.capacity_;
95  source.buf_ = nullptr;
96  source.freeIdx_ = invalidIndex;
97  source.capacity_ = 0;
98  return *this;
99  }
100 
102  {
103  free(buf_);
104  }
105 
106  // Lookup Element by index. (External code) is only allowed to call this
107  // method with indices that were earlier returned from create() and have
108  // not yet been passed to destroy().
109  [[nodiscard]] Elem& get(PoolIndex idx)
110  {
111  assert(idx.idx < capacity_);
112  return buf_[idx.idx];
113  }
114  [[nodiscard]] const Elem& get(PoolIndex idx) const
115  {
116  return const_cast<Pool&>(*this).get(idx);
117  }
118 
119  // - Insert a new Element in the pool (will be created with the given
120  // Element constructor parameters).
121  // - Returns an index that can be used with the get() method. Never
122  // returns 'invalidIndex' (so it can be used as a 'special' value).
123  // - Internally Pool keeps a list of pre-allocated objects, when this
124  // list runs out Pool will automatically allocate more objects.
125  template<typename V>
126  [[nodiscard]] PoolIndex create(V&& value, unsigned hash, PoolIndex nextIdx)
127  {
128  if (freeIdx_ == invalidIndex) grow();
129  auto idx = freeIdx_;
130  auto& elem = get(idx);
131  freeIdx_ = elem.nextIdx;
132  new (&elem) Elem(std::forward<V>(value), hash, nextIdx);
133  return idx;
134  }
135 
136  // Destroys a previously created object (given by index). Index must
137  // have been returned by an earlier create() call, and the same index
138  // can only be destroyed once. It's not allowed to destroy 'invalidIndex'.
139  void destroy(PoolIndex idx)
140  {
141  auto& elem = get(idx);
142  elem.~Elem();
143  elem.nextIdx = freeIdx_;
144  freeIdx_ = idx;
145  }
146 
147  // Leaves 'hash' and 'nextIdx' members uninitialized!
148  template<typename... Args>
149  [[nodiscard]] PoolIndex emplace(Args&&... args)
150  {
151  if (freeIdx_ == invalidIndex) grow();
152  auto idx = freeIdx_;
153  auto& elem = get(idx);
154  freeIdx_ = elem.nextIdx;
155  new (&elem) Elem(std::forward<Args>(args)...);
156  return idx;
157  }
158 
159  [[nodiscard]] unsigned capacity() const
160  {
161  return capacity_;
162  }
163 
164  void reserve(unsigned count)
165  {
166  // note: not required to be a power-of-2
167  if (capacity_ >= count) return;
168  if (capacity_ != 0) {
169  growMore(count);
170  } else {
171  growInitial(count);
172  }
173  }
174 
175  friend void swap(Pool& x, Pool& y) noexcept
176  {
177  using std::swap;
178  swap(x.buf_, y.buf_);
179  swap(x.freeIdx_, y.freeIdx_);
180  swap(x.capacity_, y.capacity_);
181  }
182 
183 private:
184  void grow()
185  {
186  if (capacity_ != 0) {
187  growMore(2 * capacity_);
188  } else {
189  growInitial(4); // initial capacity = 4
190  }
191  }
192 
193  void growMore(unsigned newCapacity)
194  {
195  auto* oldBuf = buf_;
196  Elem* newBuf;
197  if constexpr (std::is_trivially_move_constructible_v<Elem> &&
198  std::is_trivially_copyable_v<Elem>) {
199  newBuf = static_cast<Elem*>(realloc(oldBuf, newCapacity * sizeof(Elem)));
200  if (!newBuf) throw std::bad_alloc();
201  } else {
202  newBuf = static_cast<Elem*>(malloc(newCapacity * sizeof(Elem)));
203  if (!newBuf) throw std::bad_alloc();
204 
205  for (size_t i : xrange(capacity_)) {
206  new (&newBuf[i]) Elem(std::move(oldBuf[i]));
207  oldBuf[i].~Elem();
208  }
209  free(oldBuf);
210  }
211 
212  for (auto i : xrange(capacity_, newCapacity - 1)) {
213  newBuf[i].nextIdx = PoolIndex{i + 1};
214  }
215  newBuf[newCapacity - 1].nextIdx = invalidIndex;
216 
217  buf_ = newBuf;
218  freeIdx_ = PoolIndex{capacity_};
219  capacity_ = newCapacity;
220  }
221 
222  void growInitial(unsigned newCapacity)
223  {
224  auto* newBuf = static_cast<Elem*>(malloc(newCapacity * sizeof(Elem)));
225  if (!newBuf) throw std::bad_alloc();
226 
227  for (auto i : xrange(newCapacity - 1)) {
228  newBuf[i].nextIdx = PoolIndex{i + 1};
229  }
230  newBuf[newCapacity - 1].nextIdx = invalidIndex;
231 
232  buf_ = newBuf;
233  freeIdx_ = PoolIndex{0};
234  capacity_ = newCapacity;
235  }
236 
237 private:
238  Elem* buf_ = nullptr;
239  PoolIndex freeIdx_ = invalidIndex; // index of a free block, 'invalidIndex' means nothing is free
240  unsigned capacity_ = 0;
241 };
242 
243 // Type-alias for the resulting type of applying Extractor on Value.
244 template<typename Value, typename Extractor>
245 using ExtractedType = typename std::remove_cvref_t<
246  decltype(std::declval<Extractor>()(std::declval<Value>()))>;
247 
248 } // namespace hash_set_impl
249 
250 
251 // hash_set
252 //
253 // A hash-set implementation with an STL-like interface.
254 //
255 // One important property of this implementation is that stored values are not
256 // the same as the keys that are used for hashing the values or looking them
257 // up.
258 //
259 // By default (when not specifying a 2nd template argument) the values are the
260 // same as the keys (so you get a classic hash-set). but it's possible to
261 // specify an extractor functor that extracts the key-part from the value (e.g.
262 // extract one member variable out of a bigger struct).
263 //
264 // If required it's also possible to specify custom hash and equality functors.
265 template<typename Value,
266  typename Extractor = hash_set_impl::Identity,
267  typename Hasher = std::hash<hash_set_impl::ExtractedType<Value, Extractor>>,
268  typename Equal = std::equal_to<>>
269 class hash_set
270 {
271 protected:
273  static constexpr auto invalidIndex = hash_set_impl::invalidIndex;
274 
275 public:
276  using value_type = Value;
277 
278  template<typename HashSet, typename IValue>
279  class Iter {
280  public:
281  using value_type = IValue;
282  using difference_type = int;
283  using pointer = IValue*;
284  using reference = IValue&;
285  using iterator_category = std::forward_iterator_tag;
286 
287  Iter() = default;
288 
289  template<typename HashSet2, typename IValue2>
290  explicit Iter(const Iter<HashSet2, IValue2>& other)
291  : hashSet(other.hashSet), elemIdx(other.elemIdx) {}
292 
293  template<typename HashSet2, typename IValue2>
295  hashSet = rhs.hashSet;
296  elemIdx = rhs.elemIdx;
297  return *this;
298  }
299 
300  [[nodiscard]] bool operator==(const Iter& rhs) const {
301  assert((hashSet == rhs.hashSet) || !hashSet || !rhs.hashSet);
302  return elemIdx == rhs.elemIdx;
303  }
304 
306  auto& oldElem = hashSet->pool.get(elemIdx);
307  elemIdx = oldElem.nextIdx;
308  if (elemIdx == invalidIndex) {
309  unsigned tableIdx = oldElem.hash & hashSet->allocMask;
310  do {
311  if (tableIdx == hashSet->allocMask) break;
312  elemIdx = hashSet->table[++tableIdx];
313  } while (elemIdx == invalidIndex);
314  }
315  return *this;
316  }
318  Iter tmp = *this;
319  ++(*this);
320  return tmp;
321  }
322 
323  [[nodiscard]] IValue& operator*() const {
324  return hashSet->pool.get(elemIdx).value;
325  }
326  [[nodiscard]] IValue* operator->() const {
327  return &hashSet->pool.get(elemIdx).value;
328  }
329 
330  //internal: should only be called from hash_set and hash_map
331  Iter(HashSet* m, PoolIndex idx)
332  : hashSet(m), elemIdx(idx) {}
333 
334  [[nodiscard]] PoolIndex getElementIdx() const {
335  return elemIdx;
336  }
337 
338  private:
339  HashSet* hashSet = nullptr;
340  PoolIndex elemIdx = invalidIndex;
341  };
342 
345 
346 public:
347  explicit hash_set(unsigned initialSize = 0,
348  Extractor extract_ = Extractor(),
349  Hasher hasher_ = Hasher(),
350  Equal equal_ = Equal())
351  : extract(extract_), hasher(hasher_), equal(equal_)
352  {
353  reserve(initialSize); // optimized away if initialSize==0
354  }
355 
356  hash_set(const hash_set& source)
357  : extract(source.extract), hasher(source.hasher)
358  , equal(source.equal)
359  {
360  if (source.elemCount == 0) return;
361  reserve(source.elemCount);
362 
363  for (unsigned i = 0; i <= source.allocMask; ++i) {
364  for (auto idx = source.table[i]; idx != invalidIndex; ) {
365  const auto& elem = source.pool.get(idx);
367  idx = elem.nextIdx;
368  }
369  }
370  }
371 
372  hash_set(hash_set&& source) noexcept
373  : table(source.table)
374  , pool(std::move(source.pool))
375  , allocMask(source.allocMask)
376  , elemCount(source.elemCount)
377  , extract(std::move(source.extract))
378  , hasher (std::move(source.hasher))
379  , equal (std::move(source.equal))
380  {
381  source.table = nullptr;
382  source.allocMask = -1;
383  source.elemCount = 0;
384  }
385 
386  explicit hash_set(std::initializer_list<Value> args)
387  {
388  reserve(args.size());
389  for (auto a : args) insert_noCapacityCheck(a); // need duplicate check??
390  }
391 
393  {
394  clear();
395  free(table);
396  }
397 
398  hash_set& operator=(const hash_set& source)
399  {
400  if (&source == this) return *this;
401  clear();
402  if (source.elemCount == 0) return *this;
403  reserve(source.elemCount);
404 
405  for (unsigned i = 0; i <= source.allocMask; ++i) {
406  for (auto idx = source.table[i]; idx != invalidIndex; ) {
407  const auto& elem = source.pool.get(idx);
409  idx = elem.nextIdx;
410  }
411  }
412  extract = source.extract;
413  hasher = source.hasher;
414  equal = source.equal;
415  return *this;
416  }
417 
418  hash_set& operator=(hash_set&& source) noexcept
419  {
420  table = source.table;
421  pool = std::move(source.pool);
422  allocMask = source.allocMask;
423  elemCount = source.elemCount;
424  extract = std::move(source.extract);
425  hasher = std::move(source.hasher);
426  equal = std::move(source.equal);
427 
428  source.table = nullptr;
429  source.allocMask = -1;
430  source.elemCount = 0;
431  return *this;
432  }
433 
434  template<typename K>
435  [[nodiscard]] bool contains(const K& key) const
436  {
437  return locateElement(key) != invalidIndex;
438  }
439 
440  template<typename V>
441  std::pair<iterator, bool> insert(V&& value)
442  {
443  return insert_impl<true, true>(std::forward<V>(value));
444  }
445  template<typename V>
446  std::pair<iterator, bool> insert_noCapacityCheck(V&& value)
447  {
448  return insert_impl<false, true>(std::forward<V>(value));
449  }
450  template<typename V>
452  {
453  return insert_impl<true, false>(std::forward<V>(value)).first;
454  }
455  template<typename V>
457  {
458  return insert_impl<false, false>(std::forward<V>(value)).first;
459  }
460 
461  template<typename... Args>
462  std::pair<iterator, bool> emplace(Args&&... args)
463  {
464  return emplace_impl<true, true>(std::forward<Args>(args)...);
465  }
466  template<typename... Args>
467  std::pair<iterator, bool> emplace_noCapacityCheck(Args&&... args)
468  {
469  return emplace_impl<false, true>(std::forward<Args>(args)...);
470  }
471  template<typename... Args>
473  {
474  return emplace_impl<true, false>(std::forward<Args>(args)...).first;
475  }
476  template<typename... Args>
478  {
479  return emplace_impl<false, false>(std::forward<Args>(args)...).first;
480  }
481 
482  template<typename K>
483  bool erase(const K& key)
484  {
485  if (elemCount == 0) return false;
486 
487  auto hash = unsigned(hasher(key));
488  auto tableIdx = hash & allocMask;
489 
490  for (auto* prev = &table[tableIdx]; *prev != invalidIndex; prev = &(pool.get(*prev).nextIdx)) {
491  auto elemIdx = *prev;
492  auto& elem = pool.get(elemIdx);
493  if (elem.hash != hash) continue;
494  if (!equal(extract(elem.value), key)) continue;
495 
496  *prev = elem.nextIdx;
497  pool.destroy(elemIdx);
498  --elemCount;
499  return true;
500  }
501  return false;
502  }
503 
504  void erase(iterator it)
505  {
506  auto elemIdx = it.getElementIdx();
507  if (elemIdx == invalidIndex) {
508  UNREACHABLE; // not allowed to call erase(end())
509  return;
510  }
511  auto& elem = pool.get(elemIdx);
512  auto tableIdx = pool.get(elemIdx).hash & allocMask;
513  auto* prev = &table[tableIdx];
514  assert(*prev != invalidIndex);
515  while (*prev != elemIdx) {
516  prev = &(pool.get(*prev).nextIdx);
517  assert(*prev != invalidIndex);
518  }
519  *prev = elem.nextIdx;
520  pool.destroy(elemIdx);
521  --elemCount;
522  }
523 
524  [[nodiscard]] bool empty() const
525  {
526  return elemCount == 0;
527  }
528 
529  [[nodiscard]] unsigned size() const
530  {
531  return elemCount;
532  }
533 
534  void clear()
535  {
536  if (elemCount == 0) return;
537 
538  for (unsigned i = 0; i <= allocMask; ++i) {
539  for (auto elemIdx = table[i]; elemIdx != invalidIndex; ) {
540  auto nextIdx = pool.get(elemIdx).nextIdx;
541  pool.destroy(elemIdx);
542  elemIdx = nextIdx;
543  }
544  table[i] = invalidIndex;
545  }
546  elemCount = 0;
547  }
548 
549  template<typename K>
550  [[nodiscard]] iterator find(const K& key)
551  {
552  return iterator(this, locateElement(key));
553  }
554 
555  template<typename K>
556  [[nodiscard]] const_iterator find(const K& key) const
557  {
558  return const_iterator(this, locateElement(key));
559  }
560 
561  [[nodiscard]] iterator begin()
562  {
563  if (elemCount == 0) return end();
564 
565  for (unsigned idx = 0; idx <= allocMask; ++idx) {
566  if (table[idx] != invalidIndex) {
567  return iterator(this, table[idx]);
568  }
569  }
570  UNREACHABLE;
571  return end(); // avoid warning
572  }
573 
574  [[nodiscard]] const_iterator begin() const
575  {
576  if (elemCount == 0) return end();
577 
578  for (unsigned idx = 0; idx <= allocMask; ++idx) {
579  if (table[idx] != invalidIndex) {
580  return const_iterator(this, table[idx]);
581  }
582  }
583  UNREACHABLE;
584  return end(); // avoid warning
585  }
586 
587  [[nodiscard]] iterator end()
588  {
589  return iterator();
590  }
591 
592  [[nodiscard]] const_iterator end() const
593  {
594  return const_iterator();
595  }
596 
597  [[nodiscard]] unsigned capacity() const
598  {
599  unsigned poolCapacity = pool.capacity();
600  unsigned tableCapacity = (allocMask + 1) / 4 * 3;
601  return std::min(poolCapacity, tableCapacity);
602  }
603 
604  // After this call, the hash_set can at least contain 'count' number of
605  // elements without requiring any additional memory allocation or rehash.
606  void reserve(unsigned count)
607  {
608  pool.reserve(count);
609 
610  unsigned oldCount = allocMask + 1;
611  unsigned newCount = nextPowerOf2((count + 2) / 3 * 4);
612  if (oldCount >= newCount) return;
613 
614  allocMask = newCount - 1;
615  if (oldCount == 0) {
616  table = static_cast<PoolIndex*>(malloc(newCount * sizeof(PoolIndex)));
617  std::fill(table, table + newCount, invalidIndex);
618  } else {
619  table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(PoolIndex)));
620  do {
621  rehash(oldCount);
622  oldCount *= 2;
623  } while (oldCount < newCount);
624  }
625  }
626 
627  friend void swap(hash_set& x, hash_set& y) noexcept
628  {
629  using std::swap;
630  swap(x.table, y.table);
631  swap(x.pool, y.pool);
632  swap(x.allocMask, y.allocMask);
633  swap(x.elemCount, y.elemCount);
634  swap(x.extract , y.extract);
635  swap(x.hasher , y.hasher);
636  swap(x.equal , y.equal);
637  }
638 
639  [[nodiscard]] friend auto begin( hash_set& s) { return s.begin(); }
640  [[nodiscard]] friend auto begin(const hash_set& s) { return s.begin(); }
641  [[nodiscard]] friend auto end ( hash_set& s) { return s.end(); }
642  [[nodiscard]] friend auto end (const hash_set& s) { return s.end(); }
643 
644 protected:
645  // Returns the smallest value that is >= x that is also a power of 2.
646  // (for x=0 it returns 0)
647  [[nodiscard]] static inline unsigned nextPowerOf2(unsigned x)
648  {
649  static_assert(sizeof(unsigned) == sizeof(uint32_t), "only works for exactly 32 bit");
650  x -= 1;
651  x |= x >> 1;
652  x |= x >> 2;
653  x |= x >> 4;
654  x |= x >> 8;
655  x |= x >> 16;
656  return x + 1;
657  }
658 
659  template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename V>
660  [[nodiscard]] std::pair<iterator, bool> insert_impl(V&& value)
661  {
662  auto hash = unsigned(hasher(extract(value)));
663  auto tableIdx = hash & allocMask;
664  PoolIndex primary = invalidIndex;
665 
666  if (!CHECK_CAPACITY || (elemCount > 0)) {
667  primary = table[tableIdx];
668  if constexpr (CHECK_DUPLICATE) {
669  for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
670  auto& elem = pool.get(elemIdx);
671  if ((elem.hash == hash) &&
672  equal(extract(elem.value), extract(value))) {
673  // already exists
674  return std::pair(iterator(this, elemIdx), false);
675  }
676  elemIdx = elem.nextIdx;
677  }
678  }
679  }
680 
681  if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
682  grow();
683  tableIdx = hash & allocMask;
684  primary = table[tableIdx];
685  }
686 
687  elemCount++;
688  auto idx = pool.create(std::forward<V>(value), hash, primary);
689  table[tableIdx] = idx;
690  return std::pair(iterator(this, idx), true);
691  }
692 
693  template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename... Args>
694  [[nodiscard]] std::pair<iterator, bool> emplace_impl(Args&&... args)
695  {
696  auto poolIdx = pool.emplace(std::forward<Args>(args)...);
697  auto& poolElem = pool.get(poolIdx);
698 
699  auto hash = unsigned(hasher(extract(poolElem.value)));
700  auto tableIdx = hash & allocMask;
701  PoolIndex primary = invalidIndex;
702 
703  if (!CHECK_CAPACITY || (elemCount > 0)) {
704  primary = table[tableIdx];
705  if constexpr (CHECK_DUPLICATE) {
706  for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
707  auto& elem = pool.get(elemIdx);
708  if ((elem.hash == hash) &&
709  equal(extract(elem.value), extract(poolElem.value))) {
710  // already exists
711  pool.destroy(poolIdx);
712  return std::pair(iterator(this, elemIdx), false);
713  }
714  elemIdx = elem.nextIdx;
715  }
716  }
717  }
718 
719  if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
720  grow();
721  tableIdx = hash & allocMask;
722  primary = table[tableIdx];
723  }
724 
725  elemCount++;
726  poolElem.hash = hash;
727  poolElem.nextIdx = primary;
728  table[tableIdx] = poolIdx;
729  return std::pair(iterator(this, poolIdx), true);
730  }
731 
732  void grow()
733  {
734  unsigned oldCount = allocMask + 1;
735  if (oldCount == 0) {
736  allocMask = 4 - 1; // initial size
737  table = static_cast<PoolIndex*>(malloc(4 * sizeof(PoolIndex)));
739  } else {
740  unsigned newCount = 2 * oldCount;
741  allocMask = newCount - 1;
742  table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(unsigned)));
743  rehash(oldCount);
744  }
745  }
746 
747  void rehash(unsigned oldCount)
748  {
749  assert((oldCount & (oldCount - 1)) == 0); // must be a power-of-2
750  for (auto i : xrange(oldCount)) {
751  auto* p0 = &table[i];
752  auto* p1 = &table[i + oldCount];
753  for (auto p = *p0; p != invalidIndex; p = pool.get(p).nextIdx) {
754  auto& elem = pool.get(p);
755  if ((elem.hash & oldCount) == 0) {
756  *p0 = p;
757  p0 = &elem.nextIdx;
758  } else {
759  *p1 = p;
760  p1 = &elem.nextIdx;
761  }
762  }
763  *p0 = invalidIndex;
764  *p1 = invalidIndex;
765  }
766  }
767 
768  template<typename K>
769  [[nodiscard]] PoolIndex locateElement(const K& key) const
770  {
771  if (elemCount == 0) return invalidIndex;
772 
773  auto hash = unsigned(hasher(key));
774  auto tableIdx = hash & allocMask;
775  for (auto elemIdx = table[tableIdx]; elemIdx != invalidIndex; ) {
776  auto& elem = pool.get(elemIdx);
777  if ((elem.hash == hash) &&
778  equal(extract(elem.value), key)) {
779  return elemIdx;
780  }
781  elemIdx = elem.nextIdx;
782  }
783  return invalidIndex;
784  }
785 
786 protected:
787  PoolIndex* table = nullptr;
789  unsigned allocMask = unsigned(-1);
790  unsigned elemCount = 0;
791  [[no_unique_address]] Extractor extract;
792  [[no_unique_address]] Hasher hasher;
793  [[no_unique_address]] Equal equal;
794 };
795 
796 #endif
TclObject t
Iter & operator++()
Definition: hash_set.hh:305
Iter(HashSet *m, PoolIndex idx)
Definition: hash_set.hh:331
IValue * pointer
Definition: hash_set.hh:283
IValue * operator->() const
Definition: hash_set.hh:326
Iter & operator=(const Iter< HashSet2, IValue2 > &rhs)
Definition: hash_set.hh:294
Iter(const Iter< HashSet2, IValue2 > &other)
Definition: hash_set.hh:290
IValue value_type
Definition: hash_set.hh:281
IValue & reference
Definition: hash_set.hh:284
Iter()=default
int difference_type
Definition: hash_set.hh:282
bool operator==(const Iter &rhs) const
Definition: hash_set.hh:300
PoolIndex getElementIdx() const
Definition: hash_set.hh:334
IValue & operator*() const
Definition: hash_set.hh:323
std::forward_iterator_tag iterator_category
Definition: hash_set.hh:285
Iter operator++(int)
Definition: hash_set.hh:317
PoolIndex emplace(Args &&... args)
Definition: hash_set.hh:149
const Elem & get(PoolIndex idx) const
Definition: hash_set.hh:114
unsigned capacity() const
Definition: hash_set.hh:159
friend void swap(Pool &x, Pool &y) noexcept
Definition: hash_set.hh:175
Pool(Pool &&source) noexcept
Definition: hash_set.hh:80
PoolIndex create(V &&value, unsigned hash, PoolIndex nextIdx)
Definition: hash_set.hh:126
Pool & operator=(Pool &&source) noexcept
Definition: hash_set.hh:90
void destroy(PoolIndex idx)
Definition: hash_set.hh:139
Elem & get(PoolIndex idx)
Definition: hash_set.hh:109
void reserve(unsigned count)
Definition: hash_set.hh:164
hash_set(unsigned initialSize=0, Extractor extract_=Extractor(), Hasher hasher_=Hasher(), Equal equal_=Equal())
Definition: hash_set.hh:347
Hasher hasher
Definition: hash_set.hh:792
unsigned size() const
Definition: hash_set.hh:529
friend auto end(hash_set &s)
Definition: hash_set.hh:641
void rehash(unsigned oldCount)
Definition: hash_set.hh:747
std::pair< iterator, bool > emplace_impl(Args &&... args)
Definition: hash_set.hh:694
bool empty() const
Definition: hash_set.hh:524
friend void swap(hash_set &x, hash_set &y) noexcept
Definition: hash_set.hh:627
bool contains(const K &key) const
Definition: hash_set.hh:435
std::pair< iterator, bool > insert_impl(V &&value)
Definition: hash_set.hh:660
void erase(iterator it)
Definition: hash_set.hh:504
PoolIndex * table
Definition: hash_set.hh:787
iterator end()
Definition: hash_set.hh:587
Value value_type
Definition: hash_set.hh:276
friend auto begin(hash_set &s)
Definition: hash_set.hh:639
Equal equal
Definition: hash_set.hh:793
hash_set(std::initializer_list< Value > args)
Definition: hash_set.hh:386
friend auto begin(const hash_set &s)
Definition: hash_set.hh:640
std::pair< iterator, bool > insert(V &&value)
Definition: hash_set.hh:441
Extractor extract
Definition: hash_set.hh:791
static unsigned nextPowerOf2(unsigned x)
Definition: hash_set.hh:647
const_iterator end() const
Definition: hash_set.hh:592
std::pair< iterator, bool > emplace_noCapacityCheck(Args &&... args)
Definition: hash_set.hh:467
iterator insert_noCapacityCheck_noDuplicateCheck(V &&value)
Definition: hash_set.hh:456
const_iterator begin() const
Definition: hash_set.hh:574
unsigned elemCount
Definition: hash_set.hh:790
hash_set(const hash_set &source)
Definition: hash_set.hh:356
iterator insert_noDuplicateCheck(V &&value)
Definition: hash_set.hh:451
PoolIndex locateElement(const K &key) const
Definition: hash_set.hh:769
Iter< const hash_set, const Value > const_iterator
Definition: hash_set.hh:344
hash_set(hash_set &&source) noexcept
Definition: hash_set.hh:372
iterator emplace_noDuplicateCheck(Args &&... args)
Definition: hash_set.hh:472
unsigned allocMask
Definition: hash_set.hh:789
void clear()
Definition: hash_set.hh:534
iterator begin()
Definition: hash_set.hh:561
iterator find(const K &key)
Definition: hash_set.hh:550
const_iterator find(const K &key) const
Definition: hash_set.hh:556
~hash_set()
Definition: hash_set.hh:392
Iter< hash_set, Value > iterator
Definition: hash_set.hh:343
void reserve(unsigned count)
Definition: hash_set.hh:606
hash_set & operator=(hash_set &&source) noexcept
Definition: hash_set.hh:418
friend auto end(const hash_set &s)
Definition: hash_set.hh:642
std::pair< iterator, bool > insert_noCapacityCheck(V &&value)
Definition: hash_set.hh:446
void grow()
Definition: hash_set.hh:732
hash_set & operator=(const hash_set &source)
Definition: hash_set.hh:398
static constexpr auto invalidIndex
Definition: hash_set.hh:273
iterator emplace_noCapacityCheck_noDuplicateCheck(Args &&... args)
Definition: hash_set.hh:477
unsigned capacity() const
Definition: hash_set.hh:597
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hash_set.hh:462
bool erase(const K &key)
Definition: hash_set.hh:483
hash_set_impl::Pool< Value > pool
Definition: hash_set.hh:788
ALWAYS_INLINE unsigned count(const uint8_t *pIn, const uint8_t *pMatch, const uint8_t *pInLimit)
Definition: lz4.cc:146
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:258
typename std::remove_cvref_t< decltype(std::declval< Extractor >()(std::declval< Value >()))> ExtractedType
Definition: hash_set.hh:246
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:127
constexpr void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:256
constexpr Element(Args &&... args)
Definition: hash_set.hh:58
constexpr Element(V &&value_, unsigned hash_, PoolIndex nextIdx_)
Definition: hash_set.hh:50
T & operator()(T &&t) const
Definition: hash_set.hh:27
constexpr bool operator==(const PoolIndex &) const =default
#define UNREACHABLE
Definition: unreachable.hh:38
constexpr auto xrange(T e)
Definition: xrange.hh:133