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