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