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