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 {
277  static constexpr auto invalidIndex = hash_set_impl::invalidIndex;
278 
279 public:
280  using value_type = Value;
281 
282  template<typename HashSet, typename IValue>
283  class Iter {
284  public:
285  using value_type = IValue;
286  using difference_type = int;
287  using pointer = IValue*;
288  using reference = IValue&;
289  using iterator_category = std::forward_iterator_tag;
290 
291  Iter() = default;
292 
293  template<typename HashSet2, typename IValue2>
294  explicit Iter(const Iter<HashSet2, IValue2>& other)
295  : hashSet(other.hashSet), elemIdx(other.elemIdx) {}
296 
297  template<typename HashSet2, typename IValue2>
299  hashSet = rhs.hashSet;
300  elemIdx = rhs.elemIdx;
301  return *this;
302  }
303 
304  [[nodiscard]] bool operator==(const Iter& rhs) const {
305  assert((hashSet == rhs.hashSet) || !hashSet || !rhs.hashSet);
306  return elemIdx == rhs.elemIdx;
307  }
308  [[nodiscard]] bool operator!=(const Iter& rhs) const {
309  return !(*this == rhs);
310  }
311 
313  auto& oldElem = hashSet->pool.get(elemIdx);
314  elemIdx = oldElem.nextIdx;
315  if (elemIdx == invalidIndex) {
316  unsigned tableIdx = oldElem.hash & hashSet->allocMask;
317  do {
318  if (tableIdx == hashSet->allocMask) break;
319  elemIdx = hashSet->table[++tableIdx];
320  } while (elemIdx == invalidIndex);
321  }
322  return *this;
323  }
325  Iter tmp = *this;
326  ++(*this);
327  return tmp;
328  }
329 
330  [[nodiscard]] IValue& operator*() const {
331  return hashSet->pool.get(elemIdx).value;
332  }
333  [[nodiscard]] IValue* operator->() const {
334  return &hashSet->pool.get(elemIdx).value;
335  }
336 
337  private:
338  friend class hash_set;
339 
340  Iter(HashSet* m, PoolIndex idx)
341  : hashSet(m), elemIdx(idx) {}
342 
343  [[nodiscard]] PoolIndex getElementIdx() const {
344  return elemIdx;
345  }
346 
347  private:
348  HashSet* hashSet = nullptr;
349  PoolIndex elemIdx = invalidIndex;
350  };
351 
354 
355 public:
356  explicit hash_set(unsigned initialSize = 0,
357  Extractor extract_ = Extractor(),
358  Hasher hasher_ = Hasher(),
359  Equal equal_ = Equal())
360  : extract(extract_), hasher(hasher_), equal(equal_)
361  {
362  reserve(initialSize); // optimized away if initialSize==0
363  }
364 
365  hash_set(const hash_set& source)
366  : extract(source.extract), hasher(source.hasher)
367  , equal(source.equal)
368  {
369  if (source.elemCount == 0) return;
370  reserve(source.elemCount);
371 
372  for (unsigned i = 0; i <= source.allocMask; ++i) {
373  for (auto idx = source.table[i]; idx != invalidIndex; ) {
374  const auto& elem = source.pool.get(idx);
376  idx = elem.nextIdx;
377  }
378  }
379  }
380 
381  hash_set(hash_set&& source) noexcept
382  : table(source.table)
383  , pool(std::move(source.pool))
384  , allocMask(source.allocMask)
385  , elemCount(source.elemCount)
386  , extract(std::move(source.extract))
387  , hasher (std::move(source.hasher))
388  , equal (std::move(source.equal))
389  {
390  source.table = nullptr;
391  source.allocMask = -1;
392  source.elemCount = 0;
393  }
394 
395  explicit hash_set(std::initializer_list<Value> args)
396  {
397  reserve(args.size());
398  for (auto a : args) insert_noCapacityCheck(a); // need duplicate check??
399  }
400 
402  {
403  clear();
404  free(table);
405  }
406 
407  hash_set& operator=(const hash_set& source)
408  {
409  if (&source == this) return *this;
410  clear();
411  if (source.elemCount == 0) return *this;
412  reserve(source.elemCount);
413 
414  for (unsigned i = 0; i <= source.allocMask; ++i) {
415  for (auto idx = source.table[i]; idx != invalidIndex; ) {
416  const auto& elem = source.pool.get(idx);
418  idx = elem.nextIdx;
419  }
420  }
421  extract = source.extract;
422  hasher = source.hasher;
423  equal = source.equal;
424  return *this;
425  }
426 
427  hash_set& operator=(hash_set&& source) noexcept
428  {
429  table = source.table;
430  pool = std::move(source.pool);
431  allocMask = source.allocMask;
432  elemCount = source.elemCount;
433  extract = std::move(source.extract);
434  hasher = std::move(source.hasher);
435  equal = std::move(source.equal);
436 
437  source.table = nullptr;
438  source.allocMask = -1;
439  source.elemCount = 0;
440  return *this;
441  }
442 
443  template<typename K>
444  [[nodiscard]] bool contains(const K& key) const
445  {
446  return locateElement(key) != invalidIndex;
447  }
448 
449  template<typename V>
450  std::pair<iterator, bool> insert(V&& value)
451  {
452  return insert_impl<true, true>(std::forward<V>(value));
453  }
454  template<typename V>
455  std::pair<iterator, bool> insert_noCapacityCheck(V&& value)
456  {
457  return insert_impl<false, true>(std::forward<V>(value));
458  }
459  template<typename V>
461  {
462  return insert_impl<true, false>(std::forward<V>(value)).first;
463  }
464  template<typename V>
466  {
467  return insert_impl<false, false>(std::forward<V>(value)).first;
468  }
469 
470  template<typename... Args>
471  std::pair<iterator, bool> emplace(Args&&... args)
472  {
473  return emplace_impl<true, true>(std::forward<Args>(args)...);
474  }
475  template<typename... Args>
476  std::pair<iterator, bool> emplace_noCapacityCheck(Args&&... args)
477  {
478  return emplace_impl<false, true>(std::forward<Args>(args)...);
479  }
480  template<typename... Args>
482  {
483  return emplace_impl<true, false>(std::forward<Args>(args)...).first;
484  }
485  template<typename... Args>
487  {
488  return emplace_impl<false, false>(std::forward<Args>(args)...).first;
489  }
490 
491  template<typename K>
492  bool erase(const K& key)
493  {
494  if (elemCount == 0) return false;
495 
496  auto hash = unsigned(hasher(key));
497  auto tableIdx = hash & allocMask;
498 
499  for (auto* prev = &table[tableIdx]; *prev != invalidIndex; prev = &(pool.get(*prev).nextIdx)) {
500  auto elemIdx = *prev;
501  auto& elem = pool.get(elemIdx);
502  if (elem.hash != hash) continue;
503  if (!equal(extract(elem.value), key)) continue;
504 
505  *prev = elem.nextIdx;
506  pool.destroy(elemIdx);
507  --elemCount;
508  return true;
509  }
510  return false;
511  }
512 
513  void erase(iterator it)
514  {
515  auto elemIdx = it.getElementIdx();
516  if (elemIdx == invalidIndex) {
517  UNREACHABLE; // not allowed to call erase(end())
518  return;
519  }
520  auto& elem = pool.get(elemIdx);
521  auto tableIdx = pool.get(elemIdx).hash & allocMask;
522  auto* prev = &table[tableIdx];
523  assert(*prev != invalidIndex);
524  while (*prev != elemIdx) {
525  prev = &(pool.get(*prev).nextIdx);
526  assert(*prev != invalidIndex);
527  }
528  *prev = elem.nextIdx;
529  pool.destroy(elemIdx);
530  --elemCount;
531  }
532 
533  [[nodiscard]] bool empty() const
534  {
535  return elemCount == 0;
536  }
537 
538  [[nodiscard]] unsigned size() const
539  {
540  return elemCount;
541  }
542 
543  void clear()
544  {
545  if (elemCount == 0) return;
546 
547  for (unsigned i = 0; i <= allocMask; ++i) {
548  for (auto elemIdx = table[i]; elemIdx != invalidIndex; ) {
549  auto nextIdx = pool.get(elemIdx).nextIdx;
550  pool.destroy(elemIdx);
551  elemIdx = nextIdx;
552  }
553  table[i] = invalidIndex;
554  }
555  elemCount = 0;
556  }
557 
558  template<typename K>
559  [[nodiscard]] iterator find(const K& key)
560  {
561  return iterator(this, locateElement(key));
562  }
563 
564  template<typename K>
565  [[nodiscard]] const_iterator find(const K& key) const
566  {
567  return const_iterator(this, locateElement(key));
568  }
569 
570  [[nodiscard]] iterator begin()
571  {
572  if (elemCount == 0) return end();
573 
574  for (unsigned idx = 0; idx <= allocMask; ++idx) {
575  if (table[idx] != invalidIndex) {
576  return iterator(this, table[idx]);
577  }
578  }
579  UNREACHABLE;
580  return end(); // avoid warning
581  }
582 
583  [[nodiscard]] const_iterator begin() const
584  {
585  if (elemCount == 0) return end();
586 
587  for (unsigned idx = 0; idx <= allocMask; ++idx) {
588  if (table[idx] != invalidIndex) {
589  return const_iterator(this, table[idx]);
590  }
591  }
592  UNREACHABLE;
593  return end(); // avoid warning
594  }
595 
596  [[nodiscard]] iterator end()
597  {
598  return iterator();
599  }
600 
601  [[nodiscard]] const_iterator end() const
602  {
603  return const_iterator();
604  }
605 
606  [[nodiscard]] unsigned capacity() const
607  {
608  unsigned poolCapacity = pool.capacity();
609  unsigned tableCapacity = (allocMask + 1) / 4 * 3;
610  return std::min(poolCapacity, tableCapacity);
611  }
612 
613  // After this call, the hash_set can at least contain 'count' number of
614  // elements without requiring any additional memory allocation or rehash.
615  void reserve(unsigned count)
616  {
617  pool.reserve(count);
618 
619  unsigned oldCount = allocMask + 1;
620  unsigned newCount = nextPowerOf2((count + 2) / 3 * 4);
621  if (oldCount >= newCount) return;
622 
623  allocMask = newCount - 1;
624  if (oldCount == 0) {
625  table = static_cast<PoolIndex*>(malloc(newCount * sizeof(PoolIndex)));
626  std::fill(table, table + newCount, invalidIndex);
627  } else {
628  table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(PoolIndex)));
629  do {
630  rehash(oldCount);
631  oldCount *= 2;
632  } while (oldCount < newCount);
633  }
634  }
635 
636  friend void swap(hash_set& x, hash_set& y) noexcept
637  {
638  using std::swap;
639  swap(x.table, y.table);
640  swap(x.pool, y.pool);
641  swap(x.allocMask, y.allocMask);
642  swap(x.elemCount, y.elemCount);
643  swap(x.extract , y.extract);
644  swap(x.hasher , y.hasher);
645  swap(x.equal , y.equal);
646  }
647 
648  [[nodiscard]] friend auto begin( hash_set& s) { return s.begin(); }
649  [[nodiscard]] friend auto begin(const hash_set& s) { return s.begin(); }
650  [[nodiscard]] friend auto end ( hash_set& s) { return s.end(); }
651  [[nodiscard]] friend auto end (const hash_set& s) { return s.end(); }
652 
653 private:
654  // Returns the smallest value that is >= x that is also a power of 2.
655  // (for x=0 it returns 0)
656  [[nodiscard]] static inline unsigned nextPowerOf2(unsigned x)
657  {
658  static_assert(sizeof(unsigned) == sizeof(uint32_t), "only works for exactly 32 bit");
659  x -= 1;
660  x |= x >> 1;
661  x |= x >> 2;
662  x |= x >> 4;
663  x |= x >> 8;
664  x |= x >> 16;
665  return x + 1;
666  }
667 
668  template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename V>
669  [[nodiscard]] std::pair<iterator, bool> insert_impl(V&& value)
670  {
671  auto hash = unsigned(hasher(extract(value)));
672  auto tableIdx = hash & allocMask;
673  PoolIndex primary = invalidIndex;
674 
675  if (!CHECK_CAPACITY || (elemCount > 0)) {
676  primary = table[tableIdx];
677  if (CHECK_DUPLICATE) {
678  for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
679  auto& elem = pool.get(elemIdx);
680  if ((elem.hash == hash) &&
681  equal(extract(elem.value), extract(value))) {
682  // already exists
683  return std::pair(iterator(this, elemIdx), false);
684  }
685  elemIdx = elem.nextIdx;
686  }
687  }
688  }
689 
690  if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
691  grow();
692  tableIdx = hash & allocMask;
693  primary = table[tableIdx];
694  }
695 
696  elemCount++;
697  auto idx = pool.create(std::forward<V>(value), hash, primary);
698  table[tableIdx] = idx;
699  return std::pair(iterator(this, idx), true);
700  }
701 
702  template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename... Args>
703  [[nodiscard]] std::pair<iterator, bool> emplace_impl(Args&&... args)
704  {
705  auto poolIdx = pool.emplace(std::forward<Args>(args)...);
706  auto& poolElem = pool.get(poolIdx);
707 
708  auto hash = unsigned(hasher(extract(poolElem.value)));
709  auto tableIdx = hash & allocMask;
710  PoolIndex primary = invalidIndex;
711 
712  if (!CHECK_CAPACITY || (elemCount > 0)) {
713  primary = table[tableIdx];
714  if (CHECK_DUPLICATE) {
715  for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
716  auto& elem = pool.get(elemIdx);
717  if ((elem.hash == hash) &&
718  equal(extract(elem.value), extract(poolElem.value))) {
719  // already exists
720  pool.destroy(poolIdx);
721  return std::pair(iterator(this, elemIdx), false);
722  }
723  elemIdx = elem.nextIdx;
724  }
725  }
726  }
727 
728  if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
729  grow();
730  tableIdx = hash & allocMask;
731  primary = table[tableIdx];
732  }
733 
734  elemCount++;
735  poolElem.hash = hash;
736  poolElem.nextIdx = primary;
737  table[tableIdx] = poolIdx;
738  return std::pair(iterator(this, poolIdx), true);
739  }
740 
741  void grow()
742  {
743  unsigned oldCount = allocMask + 1;
744  if (oldCount == 0) {
745  allocMask = 4 - 1; // initial size
746  table = static_cast<PoolIndex*>(malloc(4 * sizeof(PoolIndex)));
747  std::fill(table, table + 4, invalidIndex);
748  } else {
749  unsigned newCount = 2 * oldCount;
750  allocMask = newCount - 1;
751  table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(unsigned)));
752  rehash(oldCount);
753  }
754  }
755 
756  void rehash(unsigned oldCount)
757  {
758  assert((oldCount & (oldCount - 1)) == 0); // must be a power-of-2
759  for (auto i : xrange(oldCount)) {
760  auto* p0 = &table[i];
761  auto* p1 = &table[i + oldCount];
762  for (auto p = *p0; p != invalidIndex; p = pool.get(p).nextIdx) {
763  auto& elem = pool.get(p);
764  if ((elem.hash & oldCount) == 0) {
765  *p0 = p;
766  p0 = &elem.nextIdx;
767  } else {
768  *p1 = p;
769  p1 = &elem.nextIdx;
770  }
771  }
772  *p0 = invalidIndex;
773  *p1 = invalidIndex;
774  }
775  }
776 
777  template<typename K>
778  [[nodiscard]] PoolIndex locateElement(const K& key) const
779  {
780  if (elemCount == 0) return invalidIndex;
781 
782  auto hash = unsigned(hasher(key));
783  auto tableIdx = hash & allocMask;
784  for (auto elemIdx = table[tableIdx]; elemIdx != invalidIndex; ) {
785  auto& elem = pool.get(elemIdx);
786  if ((elem.hash == hash) &&
787  equal(extract(elem.value), key)) {
788  return elemIdx;
789  }
790  elemIdx = elem.nextIdx;
791  }
792  return invalidIndex;
793  }
794 
795 private:
796  PoolIndex* table = nullptr;
798  unsigned allocMask = unsigned(-1);
799  unsigned elemCount = 0;
800  Extractor extract;
801  Hasher hasher;
802  Equal equal;
803 };
804 
805 #endif
TclObject t
Iter & operator++()
Definition: hash_set.hh:312
IValue * pointer
Definition: hash_set.hh:287
IValue * operator->() const
Definition: hash_set.hh:333
Iter & operator=(const Iter< HashSet2, IValue2 > &rhs)
Definition: hash_set.hh:298
Iter(const Iter< HashSet2, IValue2 > &other)
Definition: hash_set.hh:294
IValue value_type
Definition: hash_set.hh:285
IValue & reference
Definition: hash_set.hh:288
Iter()=default
int difference_type
Definition: hash_set.hh:286
bool operator==(const Iter &rhs) const
Definition: hash_set.hh:304
IValue & operator*() const
Definition: hash_set.hh:330
std::forward_iterator_tag iterator_category
Definition: hash_set.hh:289
Iter operator++(int)
Definition: hash_set.hh:324
bool operator!=(const Iter &rhs) const
Definition: hash_set.hh:308
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:356
unsigned size() const
Definition: hash_set.hh:538
friend auto end(hash_set &s)
Definition: hash_set.hh:650
bool empty() const
Definition: hash_set.hh:533
friend void swap(hash_set &x, hash_set &y) noexcept
Definition: hash_set.hh:636
bool contains(const K &key) const
Definition: hash_set.hh:444
void erase(iterator it)
Definition: hash_set.hh:513
iterator end()
Definition: hash_set.hh:596
Value value_type
Definition: hash_set.hh:280
friend auto begin(hash_set &s)
Definition: hash_set.hh:648
hash_set(std::initializer_list< Value > args)
Definition: hash_set.hh:395
friend auto begin(const hash_set &s)
Definition: hash_set.hh:649
std::pair< iterator, bool > insert(V &&value)
Definition: hash_set.hh:450
const_iterator end() const
Definition: hash_set.hh:601
std::pair< iterator, bool > emplace_noCapacityCheck(Args &&... args)
Definition: hash_set.hh:476
iterator insert_noCapacityCheck_noDuplicateCheck(V &&value)
Definition: hash_set.hh:465
const_iterator begin() const
Definition: hash_set.hh:583
hash_set(const hash_set &source)
Definition: hash_set.hh:365
iterator insert_noDuplicateCheck(V &&value)
Definition: hash_set.hh:460
Iter< const hash_set, const Value > const_iterator
Definition: hash_set.hh:353
hash_set(hash_set &&source) noexcept
Definition: hash_set.hh:381
iterator emplace_noDuplicateCheck(Args &&... args)
Definition: hash_set.hh:481
void clear()
Definition: hash_set.hh:543
iterator begin()
Definition: hash_set.hh:570
iterator find(const K &key)
Definition: hash_set.hh:559
const_iterator find(const K &key) const
Definition: hash_set.hh:565
~hash_set()
Definition: hash_set.hh:401
Iter< hash_set, Value > iterator
Definition: hash_set.hh:352
void reserve(unsigned count)
Definition: hash_set.hh:615
hash_set & operator=(hash_set &&source) noexcept
Definition: hash_set.hh:427
friend auto end(const hash_set &s)
Definition: hash_set.hh:651
std::pair< iterator, bool > insert_noCapacityCheck(V &&value)
Definition: hash_set.hh:455
hash_set & operator=(const hash_set &source)
Definition: hash_set.hh:407
iterator emplace_noCapacityCheck_noDuplicateCheck(Args &&... args)
Definition: hash_set.hh:486
unsigned capacity() const
Definition: hash_set.hh:606
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hash_set.hh:471
bool erase(const K &key)
Definition: hash_set.hh:492
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:124
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