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