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 "xrange.hh"
12#include <cassert>
13#include <cstdlib>
14#include <functional>
15#include <initializer_list>
16#include <iterator>
17#include <new>
18#include <type_traits>
19#include <utility>
20
21namespace hash_set_impl {
22
23// Identity operation: accepts any type (by const or non-const reference) and
24// returns the exact same (reference) value.
25struct Identity {
26 template<typename T>
27 [[nodiscard]] inline T& operator()(T&& t) const { return t; }
28};
29
30struct PoolIndex {
31 unsigned idx;
32 [[nodiscard]] constexpr bool operator==(const PoolIndex&) const = default;
33};
34static constexpr PoolIndex invalidIndex{unsigned(-1)};
35
36// Holds the data that will be stored in the hash_set plus some extra
37// administrative data.
38// - value: the actual to be stored data
39// - hash: always equal to hasher(extract(value))
40// - nextIdx: index of next element in a single-linked-list. This is either
41// the list of colliding buckets in the hash, or the list of free objects
42// in the Pool (see below).
43template<typename Value>
44struct Element {
45 Value value;
46 unsigned hash;
48
49 template<typename V>
50 constexpr Element(V&& value_, unsigned hash_, PoolIndex nextIdx_)
51 : value(std::forward<V>(value_))
52 , hash(hash_)
53 , nextIdx(nextIdx_)
54 {
55 }
56
57 template<typename... Args>
58 explicit constexpr Element(Args&&... args)
59 : value(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 = hash_set_impl::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(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 if (elemIdx == invalidIndex) {
508 UNREACHABLE; // not allowed to call erase(end())
509 return;
510 }
511 auto& elem = pool.get(elemIdx);
512 auto tableIdx = pool.get(elemIdx).hash & allocMask;
513 auto* prev = &table[tableIdx];
514 assert(*prev != invalidIndex);
515 while (*prev != elemIdx) {
516 prev = &(pool.get(*prev).nextIdx);
517 assert(*prev != invalidIndex);
518 }
519 *prev = elem.nextIdx;
520 pool.destroy(elemIdx);
521 --elemCount;
522 }
523
524 [[nodiscard]] bool empty() const
525 {
526 return elemCount == 0;
527 }
528
529 [[nodiscard]] unsigned size() const
530 {
531 return elemCount;
532 }
533
534 void clear()
535 {
536 if (elemCount == 0) return;
537
538 for (unsigned i = 0; i <= allocMask; ++i) {
539 for (auto elemIdx = table[i]; elemIdx != invalidIndex; ) {
540 auto nextIdx = pool.get(elemIdx).nextIdx;
541 pool.destroy(elemIdx);
542 elemIdx = nextIdx;
543 }
544 table[i] = invalidIndex;
545 }
546 elemCount = 0;
547 }
548
549 template<typename K>
550 [[nodiscard]] iterator find(const K& key)
551 {
552 return iterator(this, locateElement(key));
553 }
554
555 template<typename K>
556 [[nodiscard]] const_iterator find(const K& key) const
557 {
558 return const_iterator(this, locateElement(key));
559 }
560
561 [[nodiscard]] iterator begin()
562 {
563 if (elemCount == 0) return end();
564
565 for (unsigned idx = 0; idx <= allocMask; ++idx) {
566 if (table[idx] != invalidIndex) {
567 return iterator(this, table[idx]);
568 }
569 }
571 return end(); // avoid warning
572 }
573
574 [[nodiscard]] const_iterator begin() const
575 {
576 if (elemCount == 0) return end();
577
578 for (unsigned idx = 0; idx <= allocMask; ++idx) {
579 if (table[idx] != invalidIndex) {
580 return const_iterator(this, table[idx]);
581 }
582 }
584 return end(); // avoid warning
585 }
586
587 [[nodiscard]] iterator end()
588 {
589 return iterator();
590 }
591
592 [[nodiscard]] const_iterator end() const
593 {
594 return const_iterator();
595 }
596
597 [[nodiscard]] unsigned capacity() const
598 {
599 unsigned poolCapacity = pool.capacity();
600 unsigned tableCapacity = (allocMask + 1) / 4 * 3;
601 return std::min(poolCapacity, tableCapacity);
602 }
603
604 // After this call, the hash_set can at least contain 'count' number of
605 // elements without requiring any additional memory allocation or rehash.
606 void reserve(unsigned count)
607 {
608 pool.reserve(count);
609
610 unsigned oldCount = allocMask + 1;
611 unsigned newCount = nextPowerOf2((count + 2) / 3 * 4);
612 if (oldCount >= newCount) return;
613
614 allocMask = newCount - 1;
615 if (oldCount == 0) {
616 table = static_cast<PoolIndex*>(malloc(newCount * sizeof(PoolIndex)));
617 std::fill(table, table + newCount, invalidIndex);
618 } else {
619 table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(PoolIndex)));
620 do {
621 rehash(oldCount);
622 oldCount *= 2;
623 } while (oldCount < newCount);
624 }
625 }
626
627 friend void swap(hash_set& x, hash_set& y) noexcept
628 {
629 using std::swap;
630 swap(x.table, y.table);
631 swap(x.pool, y.pool);
632 swap(x.allocMask, y.allocMask);
633 swap(x.elemCount, y.elemCount);
634 swap(x.extract , y.extract);
635 swap(x.hasher , y.hasher);
636 swap(x.equal , y.equal);
637 }
638
639 [[nodiscard]] friend auto begin( hash_set& s) { return s.begin(); }
640 [[nodiscard]] friend auto begin(const hash_set& s) { return s.begin(); }
641 [[nodiscard]] friend auto end ( hash_set& s) { return s.end(); }
642 [[nodiscard]] friend auto end (const hash_set& s) { return s.end(); }
643
644protected:
645 // Returns the smallest value that is >= x that is also a power of 2.
646 // (for x=0 it returns 0)
647 [[nodiscard]] static inline unsigned nextPowerOf2(unsigned x)
648 {
649 static_assert(sizeof(unsigned) == sizeof(uint32_t), "only works for exactly 32 bit");
650 x -= 1;
651 x |= x >> 1;
652 x |= x >> 2;
653 x |= x >> 4;
654 x |= x >> 8;
655 x |= x >> 16;
656 return x + 1;
657 }
658
659 template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename V>
660 [[nodiscard]] std::pair<iterator, bool> insert_impl(V&& value)
661 {
662 auto hash = unsigned(hasher(extract(value)));
663 auto tableIdx = hash & allocMask;
664 PoolIndex primary = invalidIndex;
665
666 if (!CHECK_CAPACITY || (elemCount > 0)) {
667 primary = table[tableIdx];
668 if constexpr (CHECK_DUPLICATE) {
669 for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
670 auto& elem = pool.get(elemIdx);
671 if ((elem.hash == hash) &&
672 equal(extract(elem.value), extract(value))) {
673 // already exists
674 return std::pair(iterator(this, elemIdx), false);
675 }
676 elemIdx = elem.nextIdx;
677 }
678 }
679 }
680
681 if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
682 grow();
683 tableIdx = hash & allocMask;
684 primary = table[tableIdx];
685 }
686
687 elemCount++;
688 auto idx = pool.create(std::forward<V>(value), hash, primary);
689 table[tableIdx] = idx;
690 return std::pair(iterator(this, idx), true);
691 }
692
693 template<bool CHECK_CAPACITY, bool CHECK_DUPLICATE, typename... Args>
694 [[nodiscard]] std::pair<iterator, bool> emplace_impl(Args&&... args)
695 {
696 auto poolIdx = pool.emplace(std::forward<Args>(args)...);
697 auto& poolElem = pool.get(poolIdx);
698
699 auto hash = unsigned(hasher(extract(poolElem.value)));
700 auto tableIdx = hash & allocMask;
701 PoolIndex primary = invalidIndex;
702
703 if (!CHECK_CAPACITY || (elemCount > 0)) {
704 primary = table[tableIdx];
705 if constexpr (CHECK_DUPLICATE) {
706 for (auto elemIdx = primary; elemIdx != invalidIndex; ) {
707 auto& elem = pool.get(elemIdx);
708 if ((elem.hash == hash) &&
709 equal(extract(elem.value), extract(poolElem.value))) {
710 // already exists
711 pool.destroy(poolIdx);
712 return std::pair(iterator(this, elemIdx), false);
713 }
714 elemIdx = elem.nextIdx;
715 }
716 }
717 }
718
719 if (CHECK_CAPACITY && (elemCount >= ((allocMask + 1) / 4 * 3))) {
720 grow();
721 tableIdx = hash & allocMask;
722 primary = table[tableIdx];
723 }
724
725 elemCount++;
726 poolElem.hash = hash;
727 poolElem.nextIdx = primary;
728 table[tableIdx] = poolIdx;
729 return std::pair(iterator(this, poolIdx), true);
730 }
731
732 void grow()
733 {
734 unsigned oldCount = allocMask + 1;
735 if (oldCount == 0) {
736 allocMask = 4 - 1; // initial size
737 table = static_cast<PoolIndex*>(malloc(4 * sizeof(PoolIndex)));
739 } else {
740 unsigned newCount = 2 * oldCount;
741 allocMask = newCount - 1;
742 table = static_cast<PoolIndex*>(realloc(table, newCount * sizeof(unsigned)));
743 rehash(oldCount);
744 }
745 }
746
747 void rehash(unsigned oldCount)
748 {
749 assert((oldCount & (oldCount - 1)) == 0); // must be a power-of-2
750 for (auto i : xrange(oldCount)) {
751 auto* p0 = &table[i];
752 auto* p1 = &table[i + oldCount];
753 for (auto p = *p0; p != invalidIndex; p = pool.get(p).nextIdx) {
754 auto& elem = pool.get(p);
755 if ((elem.hash & oldCount) == 0) {
756 *p0 = p;
757 p0 = &elem.nextIdx;
758 } else {
759 *p1 = p;
760 p1 = &elem.nextIdx;
761 }
762 }
763 *p0 = invalidIndex;
764 *p1 = invalidIndex;
765 }
766 }
767
768 template<typename K>
769 [[nodiscard]] PoolIndex locateElement(const K& key) const
770 {
771 if (elemCount == 0) return invalidIndex;
772
773 auto hash = unsigned(hasher(key));
774 auto tableIdx = hash & allocMask;
775 for (auto elemIdx = table[tableIdx]; elemIdx != invalidIndex; ) {
776 auto& elem = pool.get(elemIdx);
777 if ((elem.hash == hash) &&
778 equal(extract(elem.value), key)) {
779 return elemIdx;
780 }
781 elemIdx = elem.nextIdx;
782 }
783 return invalidIndex;
784 }
785
786protected:
787 PoolIndex* table = nullptr;
789 unsigned allocMask = unsigned(-1);
790 unsigned elemCount = 0;
791 [[no_unique_address]] Extractor extract;
792 [[no_unique_address]] Hasher hasher;
793 [[no_unique_address]] Equal equal;
794};
795
796#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
int difference_type
Definition: hash_set.hh:282
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:792
unsigned size() const
Definition: hash_set.hh:529
friend auto end(hash_set &s)
Definition: hash_set.hh:641
void rehash(unsigned oldCount)
Definition: hash_set.hh:747
bool empty() const
Definition: hash_set.hh:524
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:627
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:787
iterator end()
Definition: hash_set.hh:587
Value value_type
Definition: hash_set.hh:276
friend auto begin(hash_set &s)
Definition: hash_set.hh:639
Equal equal
Definition: hash_set.hh:793
hash_set(std::initializer_list< Value > args)
Definition: hash_set.hh:386
friend auto begin(const hash_set &s)
Definition: hash_set.hh:640
Extractor extract
Definition: hash_set.hh:791
static unsigned nextPowerOf2(unsigned x)
Definition: hash_set.hh:647
const_iterator end() const
Definition: hash_set.hh:592
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:574
unsigned elemCount
Definition: hash_set.hh:790
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:769
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:789
void clear()
Definition: hash_set.hh:534
iterator begin()
Definition: hash_set.hh:561
std::pair< iterator, bool > emplace_impl(Args &&... args)
Definition: hash_set.hh:694
iterator find(const K &key)
Definition: hash_set.hh:550
const_iterator find(const K &key) const
Definition: hash_set.hh:556
std::pair< iterator, bool > insert(V &&value)
Definition: hash_set.hh:441
~hash_set()
Definition: hash_set.hh:392
Iter< hash_set, Value > iterator
Definition: hash_set.hh:343
void reserve(unsigned count)
Definition: hash_set.hh:606
friend auto end(const hash_set &s)
Definition: hash_set.hh:642
void grow()
Definition: hash_set.hh:732
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:597
bool erase(const K &key)
Definition: hash_set.hh:483
hash_set_impl::Pool< Value > pool
Definition: hash_set.hh:788
std::pair< iterator, bool > insert_impl(V &&value)
Definition: hash_set.hh:660
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:266
typename std::remove_cvref_t< decltype(std::declval< Extractor >()(std::declval< Value >()))> ExtractedType
Definition: hash_set.hh:246
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:58
constexpr Element(V &&value_, unsigned hash_, PoolIndex nextIdx_)
Definition: hash_set.hh:50
T & operator()(T &&t) const
Definition: hash_set.hh:27
constexpr bool operator==(const PoolIndex &) const =default
#define UNREACHABLE
Definition: unreachable.hh:38
constexpr auto xrange(T e)
Definition: xrange.hh:133