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