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