1// Copyright (C) 2020 The Qt Company Ltd.
2// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, [email protected], author Giuseppe D'Angelo <[email protected]>
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#ifndef QHASH_H
6#define QHASH_H
7
8#include <QtCore/qalgorithms.h>
9#include <QtCore/qcontainertools_impl.h>
10#include <QtCore/qhashfunctions.h>
11#include <QtCore/qiterator.h>
12#include <QtCore/qlist.h>
13#include <QtCore/qrefcount.h>
14#include <QtCore/qttypetraits.h>
15
16#include <initializer_list>
17#include <functional> // for std::hash
18
19class tst_QHash; // for befriending
20
21QT_BEGIN_NAMESPACE
22
23struct QHashDummyValue
24{
25 bool operator==(const QHashDummyValue &) const noexcept { return true; }
26};
27
28namespace QHashPrivate {
29
30template <typename T, typename = void>
31constexpr inline bool HasQHashOverload = false;
32
33template <typename T>
34constexpr inline bool HasQHashOverload<T, std::enable_if_t<
35 std::is_convertible_v<decltype(qHash(std::declval<const T &>(), std::declval<size_t>())), size_t>
36>> = true;
37
38template <typename T, typename = void>
39constexpr inline bool HasStdHashSpecializationWithSeed = false;
40
41template <typename T>
42constexpr inline bool HasStdHashSpecializationWithSeed<T, std::enable_if_t<
43 std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>(), std::declval<size_t>())), size_t>
44>> = true;
45
46template <typename T, typename = void>
47constexpr inline bool HasStdHashSpecializationWithoutSeed = false;
48
49template <typename T>
50constexpr inline bool HasStdHashSpecializationWithoutSeed<T, std::enable_if_t<
51 std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>())), size_t>
52>> = true;
53
54template <typename T>
55size_t calculateHash(const T &t, size_t seed = 0)
56{
57 if constexpr (HasQHashOverload<T>) {
58 return qHash(t, seed);
59 } else if constexpr (HasStdHashSpecializationWithSeed<T>) {
60 return std::hash<T>()(t, seed);
61 } else if constexpr (HasStdHashSpecializationWithoutSeed<T>) {
62 Q_UNUSED(seed);
63 return std::hash<T>()(t);
64 } else {
65 static_assert(sizeof(T) == 0, "The key type must have a qHash overload or a std::hash specialization");
66 return 0;
67 }
68}
69
70template <typename Key, typename T>
71struct Node
72{
73 using KeyType = Key;
74 using ValueType = T;
75
76 Key key;
77 T value;
78 template<typename ...Args>
79 static void createInPlace(Node *n, Key &&k, Args &&... args)
80 { new (n) Node{ std::move(k), T(std::forward<Args>(args)...) }; }
81 template<typename ...Args>
82 static void createInPlace(Node *n, const Key &k, Args &&... args)
83 { new (n) Node{ Key(k), T(std::forward<Args>(args)...) }; }
84 template<typename ...Args>
85 void emplaceValue(Args &&... args)
86 {
87 value = T(std::forward<Args>(args)...);
88 }
89 T &&takeValue() noexcept(std::is_nothrow_move_assignable_v<T>)
90 {
91 return std::move(value);
92 }
93 bool valuesEqual(const Node *other) const { return value == other->value; }
94};
95
96template <typename Key>
97struct Node<Key, QHashDummyValue> {
98 using KeyType = Key;
99 using ValueType = QHashDummyValue;
100
101 Key key;
102 template<typename ...Args>
103 static void createInPlace(Node *n, Key &&k, Args &&...)
104 { new (n) Node{ std::move(k) }; }
105 template<typename ...Args>
106 static void createInPlace(Node *n, const Key &k, Args &&...)
107 { new (n) Node{ k }; }
108 template<typename ...Args>
109 void emplaceValue(Args &&...)
110 {
111 }
112 ValueType takeValue() { return QHashDummyValue(); }
113 bool valuesEqual(const Node *) const { return true; }
114};
115
116template <typename T>
117struct MultiNodeChain
118{
119 T value;
120 MultiNodeChain *next = nullptr;
121 ~MultiNodeChain()
122 {
123 }
124 qsizetype free() noexcept(std::is_nothrow_destructible_v<T>)
125 {
126 qsizetype nEntries = 0;
127 MultiNodeChain *e = this;
128 while (e) {
129 MultiNodeChain *n = e->next;
130 ++nEntries;
131 delete e;
132 e = n;
133 }
134 return nEntries;
135 }
136 bool contains(const T &val) const noexcept
137 {
138 const MultiNodeChain *e = this;
139 while (e) {
140 if (e->value == val)
141 return true;
142 e = e->next;
143 }
144 return false;
145 }
146};
147
148template <typename Key, typename T>
149struct MultiNode
150{
151 using KeyType = Key;
152 using ValueType = T;
153 using Chain = MultiNodeChain<T>;
154
155 Key key;
156 Chain *value;
157
158 template<typename ...Args>
159 static void createInPlace(MultiNode *n, Key &&k, Args &&... args)
160 { new (n) MultiNode(std::move(k), new Chain{ T(std::forward<Args>(args)...), nullptr }); }
161 template<typename ...Args>
162 static void createInPlace(MultiNode *n, const Key &k, Args &&... args)
163 { new (n) MultiNode(k, new Chain{ T(std::forward<Args>(args)...), nullptr }); }
164
165 MultiNode(const Key &k, Chain *c)
166 : key(k),
167 value(c)
168 {}
169 MultiNode(Key &&k, Chain *c) noexcept(std::is_nothrow_move_assignable_v<Key>)
170 : key(std::move(k)),
171 value(c)
172 {}
173
174 MultiNode(MultiNode &&other)
175 : key(other.key),
176 value(std::exchange(other.value, nullptr))
177 {
178 }
179
180 MultiNode(const MultiNode &other)
181 : key(other.key)
182 {
183 Chain *c = other.value;
184 Chain **e = &value;
185 while (c) {
186 Chain *chain = new Chain{ c->value, nullptr };
187 *e = chain;
188 e = &chain->next;
189 c = c->next;
190 }
191 }
192 ~MultiNode()
193 {
194 if (value)
195 value->free();
196 }
197 static qsizetype freeChain(MultiNode *n) noexcept(std::is_nothrow_destructible_v<T>)
198 {
199 qsizetype size = n->value->free();
200 n->value = nullptr;
201 return size;
202 }
203 template<typename ...Args>
204 void insertMulti(Args &&... args)
205 {
206 Chain *e = new Chain{ T(std::forward<Args>(args)...), nullptr };
207 e->next = std::exchange(value, e);
208 }
209 template<typename ...Args>
210 void emplaceValue(Args &&... args)
211 {
212 value->value = T(std::forward<Args>(args)...);
213 }
214};
215
216template<typename Node>
217constexpr bool isRelocatable()
218{
219 return QTypeInfo<typename Node::KeyType>::isRelocatable && QTypeInfo<typename Node::ValueType>::isRelocatable;
220}
221
222struct SpanConstants {
223 static constexpr size_t SpanShift = 7;
224 static constexpr size_t NEntries = (1 << SpanShift);
225 static constexpr size_t LocalBucketMask = (NEntries - 1);
226 static constexpr size_t UnusedEntry = 0xff;
227
228 static_assert ((NEntries & LocalBucketMask) == 0, "NEntries must be a power of two.");
229};
230
231// Regular hash tables consist of a list of buckets that can store Nodes. But simply allocating one large array of buckets
232// would waste a lot of memory. To avoid this, we split the vector of buckets up into a vector of Spans. Each Span represents
233// NEntries buckets. To quickly find the correct Span that holds a bucket, NEntries must be a power of two.
234//
235// Inside each Span, there is an offset array that represents the actual buckets. offsets contains either an index into the
236// actual storage space for the Nodes (the 'entries' member) or 0xff (UnusedEntry) to flag that the bucket is empty.
237// As we have only 128 entries per Span, the offset array can be represented using an unsigned char. This trick makes the hash
238// table have a very small memory overhead compared to many other implementations.
239template<typename Node>
240struct Span {
241 // Entry is a slot available for storing a Node. The Span holds a pointer to
242 // an array of Entries. Upon construction of the array, those entries are
243 // unused, and nextFree() is being used to set up a singly linked list
244 // of free entries.
245 // When a node gets inserted, the first free entry is being picked, removed
246 // from the singly linked list and the Node gets constructed in place.
247 struct Entry {
248 struct { alignas(Node) unsigned char data[sizeof(Node)]; } storage;
249
250 unsigned char &nextFree() { return *reinterpret_cast<unsigned char *>(&storage); }
251 Node &node() { return *reinterpret_cast<Node *>(&storage); }
252 };
253
254 unsigned char offsets[SpanConstants::NEntries];
255 Entry *entries = nullptr;
256 unsigned char allocated = 0;
257 unsigned char nextFree = 0;
258 Span() noexcept
259 {
260 memset(s: offsets, c: SpanConstants::UnusedEntry, n: sizeof(offsets));
261 }
262 ~Span()
263 {
264 freeData();
265 }
266 void freeData() noexcept(std::is_nothrow_destructible<Node>::value)
267 {
268 if (entries) {
269 if constexpr (!std::is_trivially_destructible<Node>::value) {
270 for (auto o : offsets) {
271 if (o != SpanConstants::UnusedEntry)
272 entries[o].node().~Node();
273 }
274 }
275 delete[] entries;
276 entries = nullptr;
277 }
278 }
279 Node *insert(size_t i)
280 {
281 Q_ASSERT(i < SpanConstants::NEntries);
282 Q_ASSERT(offsets[i] == SpanConstants::UnusedEntry);
283 if (nextFree == allocated)
284 addStorage();
285 unsigned char entry = nextFree;
286 Q_ASSERT(entry < allocated);
287 nextFree = entries[entry].nextFree();
288 offsets[i] = entry;
289 return &entries[entry].node();
290 }
291 void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value)
292 {
293 Q_ASSERT(bucket < SpanConstants::NEntries);
294 Q_ASSERT(offsets[bucket] != SpanConstants::UnusedEntry);
295
296 unsigned char entry = offsets[bucket];
297 offsets[bucket] = SpanConstants::UnusedEntry;
298
299 entries[entry].node().~Node();
300 entries[entry].nextFree() = nextFree;
301 nextFree = entry;
302 }
303 size_t offset(size_t i) const noexcept
304 {
305 return offsets[i];
306 }
307 bool hasNode(size_t i) const noexcept
308 {
309 return (offsets[i] != SpanConstants::UnusedEntry);
310 }
311 Node &at(size_t i) noexcept
312 {
313 Q_ASSERT(i < SpanConstants::NEntries);
314 Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry);
315
316 return entries[offsets[i]].node();
317 }
318 const Node &at(size_t i) const noexcept
319 {
320 Q_ASSERT(i < SpanConstants::NEntries);
321 Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry);
322
323 return entries[offsets[i]].node();
324 }
325 Node &atOffset(size_t o) noexcept
326 {
327 Q_ASSERT(o < allocated);
328
329 return entries[o].node();
330 }
331 const Node &atOffset(size_t o) const noexcept
332 {
333 Q_ASSERT(o < allocated);
334
335 return entries[o].node();
336 }
337 void moveLocal(size_t from, size_t to) noexcept
338 {
339 Q_ASSERT(offsets[from] != SpanConstants::UnusedEntry);
340 Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry);
341 offsets[to] = offsets[from];
342 offsets[from] = SpanConstants::UnusedEntry;
343 }
344 void moveFromSpan(Span &fromSpan, size_t fromIndex, size_t to) noexcept(std::is_nothrow_move_constructible_v<Node>)
345 {
346 Q_ASSERT(to < SpanConstants::NEntries);
347 Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry);
348 Q_ASSERT(fromIndex < SpanConstants::NEntries);
349 Q_ASSERT(fromSpan.offsets[fromIndex] != SpanConstants::UnusedEntry);
350 if (nextFree == allocated)
351 addStorage();
352 Q_ASSERT(nextFree < allocated);
353 offsets[to] = nextFree;
354 Entry &toEntry = entries[nextFree];
355 nextFree = toEntry.nextFree();
356
357 size_t fromOffset = fromSpan.offsets[fromIndex];
358 fromSpan.offsets[fromIndex] = SpanConstants::UnusedEntry;
359 Entry &fromEntry = fromSpan.entries[fromOffset];
360
361 if constexpr (isRelocatable<Node>()) {
362 memcpy(&toEntry, &fromEntry, sizeof(Entry));
363 } else {
364 new (&toEntry.node()) Node(std::move(fromEntry.node()));
365 fromEntry.node().~Node();
366 }
367 fromEntry.nextFree() = fromSpan.nextFree;
368 fromSpan.nextFree = static_cast<unsigned char>(fromOffset);
369 }
370
371 void addStorage()
372 {
373 Q_ASSERT(allocated < SpanConstants::NEntries);
374 Q_ASSERT(nextFree == allocated);
375 // the hash table should always be between 25 and 50% full
376 // this implies that we on average have between 32 and 64 entries
377 // in here. More exactly, we have a binominal distribution of the amount of
378 // occupied entries.
379 // For a 25% filled table, the average is 32 entries, with a 95% chance that we have between
380 // 23 and 41 entries.
381 // For a 50% filled table, the average is 64 entries, with a 95% chance that we have between
382 // 53 and 75 entries.
383 // Since we only resize the table once it's 50% filled and we want to avoid copies of
384 // data where possible, we initially allocate 48 entries, then resize to 80 entries, after that
385 // resize by increments of 16. That way, we usually only get one resize of the table
386 // while filling it.
387 size_t alloc;
388 static_assert(SpanConstants::NEntries % 8 == 0);
389 if (!allocated)
390 alloc = SpanConstants::NEntries / 8 * 3;
391 else if (allocated == SpanConstants::NEntries / 8 * 3)
392 alloc = SpanConstants::NEntries / 8 * 5;
393 else
394 alloc = allocated + SpanConstants::NEntries/8;
395 Entry *newEntries = new Entry[alloc];
396 // we only add storage if the previous storage was fully filled, so
397 // simply copy the old data over
398 if constexpr (isRelocatable<Node>()) {
399 if (allocated)
400 memcpy(newEntries, entries, allocated * sizeof(Entry));
401 } else {
402 for (size_t i = 0; i < allocated; ++i) {
403 new (&newEntries[i].node()) Node(std::move(entries[i].node()));
404 entries[i].node().~Node();
405 }
406 }
407 for (size_t i = allocated; i < alloc; ++i) {
408 newEntries[i].nextFree() = uchar(i + 1);
409 }
410 delete[] entries;
411 entries = newEntries;
412 allocated = uchar(alloc);
413 }
414};
415
416// QHash uses a power of two growth policy.
417namespace GrowthPolicy {
418inline constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept
419{
420 constexpr int SizeDigits = std::numeric_limits<size_t>::digits;
421
422 // We want to use at minimum a full span (128 entries), so we hardcode it for any requested
423 // capacity <= 64. Any capacity above that gets rounded to a later power of two.
424 if (requestedCapacity <= 64)
425 return SpanConstants::NEntries;
426
427 // Same as
428 // qNextPowerOfTwo(2 * requestedCapacity);
429 //
430 // but ensuring neither our multiplication nor the function overflow.
431 // Additionally, the maximum memory allocation is 2^31-1 or 2^63-1 bytes
432 // (limited by qsizetype and ptrdiff_t).
433 int count = qCountLeadingZeroBits(v: requestedCapacity);
434 if (count < 2)
435 return (std::numeric_limits<size_t>::max)(); // will cause std::bad_alloc
436 return size_t(1) << (SizeDigits - count + 1);
437}
438inline constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept
439{
440 return hash & (nBuckets - 1);
441}
442} // namespace GrowthPolicy
443
444template <typename Node>
445struct iterator;
446
447template <typename Node>
448struct Data
449{
450 using Key = typename Node::KeyType;
451 using T = typename Node::ValueType;
452 using Span = QHashPrivate::Span<Node>;
453 using iterator = QHashPrivate::iterator<Node>;
454
455 QtPrivate::RefCount ref = {.atomic: {1}};
456 size_t size = 0;
457 size_t numBuckets = 0;
458 size_t seed = 0;
459 Span *spans = nullptr;
460
461 static constexpr size_t maxNumBuckets() noexcept
462 {
463 return (std::numeric_limits<ptrdiff_t>::max)() / sizeof(Span);
464 }
465
466 struct Bucket {
467 Span *span;
468 size_t index;
469
470 Bucket(Span *s, size_t i) noexcept
471 : span(s), index(i)
472 {}
473 Bucket(const Data *d, size_t bucket) noexcept
474 : span(d->spans + (bucket >> SpanConstants::SpanShift)),
475 index(bucket & SpanConstants::LocalBucketMask)
476 {}
477 Bucket(iterator it) noexcept
478 : Bucket(it.d, it.bucket)
479 {}
480
481 size_t toBucketIndex(const Data *d) const noexcept
482 {
483 return ((span - d->spans) << SpanConstants::SpanShift) | index;
484 }
485 iterator toIterator(const Data *d) const noexcept { return iterator{d, toBucketIndex(d)}; }
486 void advanceWrapped(const Data *d) noexcept
487 {
488 advance_impl(d, whenAtEnd: d->spans);
489 }
490 void advance(const Data *d) noexcept
491 {
492 advance_impl(d, whenAtEnd: nullptr);
493 }
494 bool isUnused() const noexcept
495 {
496 return !span->hasNode(index);
497 }
498 size_t offset() const noexcept
499 {
500 return span->offset(index);
501 }
502 Node &nodeAtOffset(size_t offset)
503 {
504 return span->atOffset(offset);
505 }
506 Node *node()
507 {
508 return &span->at(index);
509 }
510 Node *insert() const
511 {
512 return span->insert(index);
513 }
514
515 private:
516 friend bool operator==(Bucket lhs, Bucket rhs) noexcept
517 {
518 return lhs.span == rhs.span && lhs.index == rhs.index;
519 }
520 friend bool operator!=(Bucket lhs, Bucket rhs) noexcept { return !(lhs == rhs); }
521
522 void advance_impl(const Data *d, Span *whenAtEnd) noexcept
523 {
524 Q_ASSERT(span);
525 ++index;
526 if (Q_UNLIKELY(index == SpanConstants::NEntries)) {
527 index = 0;
528 ++span;
529 if (span - d->spans == ptrdiff_t(d->numBuckets >> SpanConstants::SpanShift))
530 span = whenAtEnd;
531 }
532 }
533 };
534
535 static auto allocateSpans(size_t numBuckets)
536 {
537 struct R {
538 Span *spans;
539 size_t nSpans;
540 };
541
542 constexpr qptrdiff MaxSpanCount = (std::numeric_limits<qptrdiff>::max)() / sizeof(Span);
543 constexpr size_t MaxBucketCount = MaxSpanCount << SpanConstants::SpanShift;
544
545 if (numBuckets > MaxBucketCount) {
546 Q_CHECK_PTR(false);
547 Q_UNREACHABLE(); // no exceptions and no assertions -> no error reporting
548 }
549
550 size_t nSpans = numBuckets >> SpanConstants::SpanShift;
551 return R{ new Span[nSpans], nSpans };
552 }
553
554 Data(size_t reserve = 0)
555 {
556 numBuckets = GrowthPolicy::bucketsForCapacity(requestedCapacity: reserve);
557 spans = allocateSpans(numBuckets).spans;
558 seed = QHashSeed::globalSeed();
559 }
560
561 // The Resized parameter is a template param to make sure the compiler will get rid of the
562 // branch, for performance.
563 template <bool Resized>
564 Q_ALWAYS_INLINE
565 void reallocationHelper(const Data &other, size_t nSpans)
566 {
567 for (size_t s = 0; s < nSpans; ++s) {
568 const Span &span = other.spans[s];
569 for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
570 if (!span.hasNode(index))
571 continue;
572 const Node &n = span.at(index);
573 auto it = Resized ? findBucket(n.key) : Bucket { spans + s, index };
574 Q_ASSERT(it.isUnused());
575 Node *newNode = it.insert();
576 new (newNode) Node(n);
577 }
578 }
579 }
580
581 Data(const Data &other) : size(other.size), numBuckets(other.numBuckets), seed(other.seed)
582 {
583 auto r = allocateSpans(numBuckets);
584 spans = r.spans;
585 reallocationHelper<false>(other, r.nSpans);
586 }
587 Data(const Data &other, size_t reserved) : size(other.size), seed(other.seed)
588 {
589 numBuckets = GrowthPolicy::bucketsForCapacity(requestedCapacity: qMax(a: size, b: reserved));
590 spans = allocateSpans(numBuckets).spans;
591 size_t otherNSpans = other.numBuckets >> SpanConstants::SpanShift;
592 reallocationHelper<true>(other, otherNSpans);
593 }
594
595 static Data *detached(Data *d)
596 {
597 if (!d)
598 return new Data;
599 Data *dd = new Data(*d);
600 if (!d->ref.deref())
601 delete d;
602 return dd;
603 }
604 static Data *detached(Data *d, size_t size)
605 {
606 if (!d)
607 return new Data(size);
608 Data *dd = new Data(*d, size);
609 if (!d->ref.deref())
610 delete d;
611 return dd;
612 }
613
614 void clear()
615 {
616 delete[] spans;
617 spans = nullptr;
618 size = 0;
619 numBuckets = 0;
620 }
621
622 iterator detachedIterator(iterator other) const noexcept
623 {
624 return iterator{this, other.bucket};
625 }
626
627 iterator begin() const noexcept
628 {
629 iterator it{ this, 0 };
630 if (it.isUnused())
631 ++it;
632 return it;
633 }
634
635 constexpr iterator end() const noexcept
636 {
637 return iterator();
638 }
639
640 void rehash(size_t sizeHint = 0)
641 {
642 if (sizeHint == 0)
643 sizeHint = size;
644 size_t newBucketCount = GrowthPolicy::bucketsForCapacity(requestedCapacity: sizeHint);
645
646 Span *oldSpans = spans;
647 size_t oldBucketCount = numBuckets;
648 spans = allocateSpans(numBuckets: newBucketCount).spans;
649 numBuckets = newBucketCount;
650 size_t oldNSpans = oldBucketCount >> SpanConstants::SpanShift;
651
652 for (size_t s = 0; s < oldNSpans; ++s) {
653 Span &span = oldSpans[s];
654 for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
655 if (!span.hasNode(index))
656 continue;
657 Node &n = span.at(index);
658 auto it = findBucket(n.key);
659 Q_ASSERT(it.isUnused());
660 Node *newNode = it.insert();
661 new (newNode) Node(std::move(n));
662 }
663 span.freeData();
664 }
665 delete[] oldSpans;
666 }
667
668 size_t nextBucket(size_t bucket) const noexcept
669 {
670 ++bucket;
671 if (bucket == numBuckets)
672 bucket = 0;
673 return bucket;
674 }
675
676 float loadFactor() const noexcept
677 {
678 return float(size)/numBuckets;
679 }
680 bool shouldGrow() const noexcept
681 {
682 return size >= (numBuckets >> 1);
683 }
684
685 template <typename K> Bucket findBucket(const K &key) const noexcept
686 {
687 static_assert(std::is_same_v<std::remove_cv_t<Key>, K> ||
688 QHashHeterogeneousSearch<std::remove_cv_t<Key>, K>::value);
689 Q_ASSERT(numBuckets > 0);
690 size_t hash = QHashPrivate::calculateHash(key, seed);
691 Bucket bucket(this, GrowthPolicy::bucketForHash(nBuckets: numBuckets, hash));
692 // loop over the buckets until we find the entry we search for
693 // or an empty slot, in which case we know the entry doesn't exist
694 while (true) {
695 size_t offset = bucket.offset();
696 if (offset == SpanConstants::UnusedEntry) {
697 return bucket;
698 } else {
699 Node &n = bucket.nodeAtOffset(offset);
700 if (qHashEquals(n.key, key))
701 return bucket;
702 }
703 bucket.advanceWrapped(this);
704 }
705 }
706
707 template <typename K> Node *findNode(const K &key) const noexcept
708 {
709 auto bucket = findBucket(key);
710 if (bucket.isUnused())
711 return nullptr;
712 return bucket.node();
713 }
714
715 struct InsertionResult
716 {
717 iterator it;
718 bool initialized;
719 };
720
721 template <typename K> InsertionResult findOrInsert(const K &key) noexcept
722 {
723 Bucket it(static_cast<Span *>(nullptr), 0);
724 if (numBuckets > 0) {
725 it = findBucket(key);
726 if (!it.isUnused())
727 return { it.toIterator(this), true };
728 }
729 if (shouldGrow()) {
730 rehash(sizeHint: size + 1);
731 it = findBucket(key); // need to get a new iterator after rehashing
732 }
733 Q_ASSERT(it.span != nullptr);
734 Q_ASSERT(it.isUnused());
735 it.insert();
736 ++size;
737 return { it.toIterator(this), false };
738 }
739
740 void erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value)
741 {
742 Q_ASSERT(bucket.span->hasNode(bucket.index));
743 bucket.span->erase(bucket.index);
744 --size;
745
746 // re-insert the following entries to avoid holes
747 Bucket next = bucket;
748 while (true) {
749 next.advanceWrapped(this);
750 size_t offset = next.offset();
751 if (offset == SpanConstants::UnusedEntry)
752 return;
753 size_t hash = QHashPrivate::calculateHash(next.nodeAtOffset(offset).key, seed);
754 Bucket newBucket(this, GrowthPolicy::bucketForHash(nBuckets: numBuckets, hash));
755 while (true) {
756 if (newBucket == next) {
757 // nothing to do, item is at the right plae
758 break;
759 } else if (newBucket == bucket) {
760 // move into the hole we created earlier
761 if (next.span == bucket.span) {
762 bucket.span->moveLocal(next.index, bucket.index);
763 } else {
764 // move between spans, more expensive
765 bucket.span->moveFromSpan(*next.span, next.index, bucket.index);
766 }
767 bucket = next;
768 break;
769 }
770 newBucket.advanceWrapped(this);
771 }
772 }
773 }
774
775 ~Data()
776 {
777 delete [] spans;
778 }
779};
780
781template <typename Node>
782struct iterator {
783 using Span = QHashPrivate::Span<Node>;
784
785 const Data<Node> *d = nullptr;
786 size_t bucket = 0;
787
788 size_t span() const noexcept { return bucket >> SpanConstants::SpanShift; }
789 size_t index() const noexcept { return bucket & SpanConstants::LocalBucketMask; }
790 inline bool isUnused() const noexcept { return !d->spans[span()].hasNode(index()); }
791
792 inline Node *node() const noexcept
793 {
794 Q_ASSERT(!isUnused());
795 return &d->spans[span()].at(index());
796 }
797 bool atEnd() const noexcept { return !d; }
798
799 iterator operator++() noexcept
800 {
801 while (true) {
802 ++bucket;
803 if (bucket == d->numBuckets) {
804 d = nullptr;
805 bucket = 0;
806 break;
807 }
808 if (!isUnused())
809 break;
810 }
811 return *this;
812 }
813 bool operator==(iterator other) const noexcept
814 { return d == other.d && bucket == other.bucket; }
815 bool operator!=(iterator other) const noexcept
816 { return !(*this == other); }
817};
818
819
820
821} // namespace QHashPrivate
822
823template <typename Key, typename T>
824class QHash
825{
826 using Node = QHashPrivate::Node<Key, T>;
827 using Data = QHashPrivate::Data<Node>;
828 friend class QSet<Key>;
829 friend class QMultiHash<Key, T>;
830 friend tst_QHash;
831
832 Data *d = nullptr;
833
834public:
835 using key_type = Key;
836 using mapped_type = T;
837 using value_type = T;
838 using size_type = qsizetype;
839 using difference_type = qsizetype;
840 using reference = T &;
841 using const_reference = const T &;
842
843 inline QHash() noexcept = default;
844 inline QHash(std::initializer_list<std::pair<Key,T> > list)
845 : d(new Data(list.size()))
846 {
847 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
848 insert(it->first, it->second);
849 }
850 QHash(const QHash &other) noexcept
851 : d(other.d)
852 {
853 if (d)
854 d->ref.ref();
855 }
856 ~QHash()
857 {
858 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
859 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
860
861 if (d && !d->ref.deref())
862 delete d;
863 }
864
865 QHash &operator=(const QHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
866 {
867 if (d != other.d) {
868 Data *o = other.d;
869 if (o)
870 o->ref.ref();
871 if (d && !d->ref.deref())
872 delete d;
873 d = o;
874 }
875 return *this;
876 }
877
878 QHash(QHash &&other) noexcept
879 : d(std::exchange(other.d, nullptr))
880 {
881 }
882 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QHash)
883#ifdef Q_QDOC
884 template <typename InputIterator>
885 QHash(InputIterator f, InputIterator l);
886#else
887 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
888 QHash(InputIterator f, InputIterator l)
889 : QHash()
890 {
891 QtPrivate::reserveIfForwardIterator(this, f, l);
892 for (; f != l; ++f)
893 insert(f.key(), f.value());
894 }
895
896 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
897 QHash(InputIterator f, InputIterator l)
898 : QHash()
899 {
900 QtPrivate::reserveIfForwardIterator(this, f, l);
901 for (; f != l; ++f) {
902 auto &&e = *f;
903 using V = decltype(e);
904 insert(std::forward<V>(e).first, std::forward<V>(e).second);
905 }
906 }
907#endif
908 void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); }
909
910#ifndef Q_QDOC
911 template <typename AKey = Key, typename AT = T>
912 QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator==(const QHash &other) const noexcept
913 {
914 if (d == other.d)
915 return true;
916 if (size() != other.size())
917 return false;
918
919 for (const_iterator it = other.begin(); it != other.end(); ++it) {
920 const_iterator i = find(it.key());
921 if (i == end() || !i.i.node()->valuesEqual(it.i.node()))
922 return false;
923 }
924 // all values must be the same as size is the same
925 return true;
926 }
927 template <typename AKey = Key, typename AT = T>
928 QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator!=(const QHash &other) const noexcept
929 { return !(*this == other); }
930#else
931 bool operator==(const QHash &other) const;
932 bool operator!=(const QHash &other) const;
933#endif // Q_QDOC
934
935 inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
936
937 [[nodiscard]]
938 inline bool isEmpty() const noexcept { return !d || d->size == 0; }
939
940 inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
941 void reserve(qsizetype size)
942 {
943 // reserve(0) is used in squeeze()
944 if (size && (this->capacity() >= size))
945 return;
946 if (isDetached())
947 d->rehash(size);
948 else
949 d = Data::detached(d, size_t(size));
950 }
951 inline void squeeze()
952 {
953 if (capacity())
954 reserve(size: 0);
955 }
956
957 inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
958 inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
959 bool isSharedWith(const QHash &other) const noexcept { return d == other.d; }
960
961 void clear() noexcept(std::is_nothrow_destructible<Node>::value)
962 {
963 if (d && !d->ref.deref())
964 delete d;
965 d = nullptr;
966 }
967
968 bool remove(const Key &key)
969 {
970 return removeImpl(key);
971 }
972private:
973 template <typename K> bool removeImpl(const K &key)
974 {
975 if (isEmpty()) // prevents detaching shared null
976 return false;
977 auto it = d->findBucket(key);
978 if (it.isUnused())
979 return false;
980
981 size_t bucket = it.toBucketIndex(d);
982 detach();
983 it = typename Data::Bucket(d, bucket); // reattach in case of detach
984
985 d->erase(it);
986 return true;
987 }
988
989public:
990 template <typename Predicate>
991 qsizetype removeIf(Predicate pred)
992 {
993 return QtPrivate::associative_erase_if(*this, pred);
994 }
995
996 T take(const Key &key)
997 {
998 return takeImpl(key);
999 }
1000private:
1001 template <typename K> T takeImpl(const K &key)
1002 {
1003 if (isEmpty()) // prevents detaching shared null
1004 return T();
1005 auto it = d->findBucket(key);
1006 size_t bucket = it.toBucketIndex(d);
1007 detach();
1008 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1009
1010 if (it.isUnused())
1011 return T();
1012 T value = it.node()->takeValue();
1013 d->erase(it);
1014 return value;
1015 }
1016
1017public:
1018 bool contains(const Key &key) const noexcept
1019 {
1020 if (!d)
1021 return false;
1022 return d->findNode(key) != nullptr;
1023 }
1024 qsizetype count(const Key &key) const noexcept
1025 {
1026 return contains(key) ? 1 : 0;
1027 }
1028
1029private:
1030 const Key *keyImpl(const T &value) const noexcept
1031 {
1032 if (d) {
1033 const_iterator i = begin();
1034 while (i != end()) {
1035 if (i.value() == value)
1036 return &i.key();
1037 ++i;
1038 }
1039 }
1040
1041 return nullptr;
1042 }
1043
1044public:
1045 Key key(const T &value) const noexcept
1046 {
1047 if (auto *k = keyImpl(value))
1048 return *k;
1049 else
1050 return Key();
1051 }
1052 Key key(const T &value, const Key &defaultKey) const noexcept
1053 {
1054 if (auto *k = keyImpl(value))
1055 return *k;
1056 else
1057 return defaultKey;
1058 }
1059
1060private:
1061 template <typename K>
1062 T *valueImpl(const K &key) const noexcept
1063 {
1064 if (d) {
1065 Node *n = d->findNode(key);
1066 if (n)
1067 return &n->value;
1068 }
1069 return nullptr;
1070 }
1071public:
1072 T value(const Key &key) const noexcept
1073 {
1074 if (T *v = valueImpl(key))
1075 return *v;
1076 else
1077 return T();
1078 }
1079
1080 T value(const Key &key, const T &defaultValue) const noexcept
1081 {
1082 if (T *v = valueImpl(key))
1083 return *v;
1084 else
1085 return defaultValue;
1086 }
1087
1088 T &operator[](const Key &key)
1089 {
1090 return operatorIndexImpl(key);
1091 }
1092private:
1093 template <typename K> T &operatorIndexImpl(const K &key)
1094 {
1095 const auto copy = isDetached() ? QHash() : *this; // keep 'key' alive across the detach
1096 detach();
1097 auto result = d->findOrInsert(key);
1098 Q_ASSERT(!result.it.atEnd());
1099 if (!result.initialized)
1100 Node::createInPlace(result.it.node(), Key(key), T());
1101 return result.it.node()->value;
1102 }
1103
1104public:
1105 const T operator[](const Key &key) const noexcept
1106 {
1107 return value(key);
1108 }
1109
1110 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1111 QList<Key> keys(const T &value) const
1112 {
1113 QList<Key> res;
1114 const_iterator i = begin();
1115 while (i != end()) {
1116 if (i.value() == value)
1117 res.append(i.key());
1118 ++i;
1119 }
1120 return res;
1121 }
1122 QList<T> values() const { return QList<T>(begin(), end()); }
1123
1124 class const_iterator;
1125
1126 class iterator
1127 {
1128 using piter = typename QHashPrivate::iterator<Node>;
1129 friend class const_iterator;
1130 friend class QHash<Key, T>;
1131 friend class QSet<Key>;
1132 piter i;
1133 explicit inline iterator(piter it) noexcept : i(it) { }
1134
1135 public:
1136 typedef std::forward_iterator_tag iterator_category;
1137 typedef qptrdiff difference_type;
1138 typedef T value_type;
1139 typedef T *pointer;
1140 typedef T &reference;
1141
1142 constexpr iterator() noexcept = default;
1143
1144 inline const Key &key() const noexcept { return i.node()->key; }
1145 inline T &value() const noexcept { return i.node()->value; }
1146 inline T &operator*() const noexcept { return i.node()->value; }
1147 inline T *operator->() const noexcept { return &i.node()->value; }
1148 inline bool operator==(const iterator &o) const noexcept { return i == o.i; }
1149 inline bool operator!=(const iterator &o) const noexcept { return i != o.i; }
1150
1151 inline iterator &operator++() noexcept
1152 {
1153 ++i;
1154 return *this;
1155 }
1156 inline iterator operator++(int) noexcept
1157 {
1158 iterator r = *this;
1159 ++i;
1160 return r;
1161 }
1162
1163 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1164 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1165 };
1166 friend class iterator;
1167
1168 class const_iterator
1169 {
1170 using piter = typename QHashPrivate::iterator<Node>;
1171 friend class iterator;
1172 friend class QHash<Key, T>;
1173 friend class QSet<Key>;
1174 piter i;
1175 explicit inline const_iterator(piter it) : i(it) { }
1176
1177 public:
1178 typedef std::forward_iterator_tag iterator_category;
1179 typedef qptrdiff difference_type;
1180 typedef T value_type;
1181 typedef const T *pointer;
1182 typedef const T &reference;
1183
1184 constexpr const_iterator() noexcept = default;
1185 inline const_iterator(const iterator &o) noexcept : i(o.i) { }
1186
1187 inline const Key &key() const noexcept { return i.node()->key; }
1188 inline const T &value() const noexcept { return i.node()->value; }
1189 inline const T &operator*() const noexcept { return i.node()->value; }
1190 inline const T *operator->() const noexcept { return &i.node()->value; }
1191 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1192 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1193
1194 inline const_iterator &operator++() noexcept
1195 {
1196 ++i;
1197 return *this;
1198 }
1199 inline const_iterator operator++(int) noexcept
1200 {
1201 const_iterator r = *this;
1202 ++i;
1203 return r;
1204 }
1205 };
1206 friend class const_iterator;
1207
1208 class key_iterator
1209 {
1210 const_iterator i;
1211
1212 public:
1213 typedef typename const_iterator::iterator_category iterator_category;
1214 typedef qptrdiff difference_type;
1215 typedef Key value_type;
1216 typedef const Key *pointer;
1217 typedef const Key &reference;
1218
1219 key_iterator() noexcept = default;
1220 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1221
1222 const Key &operator*() const noexcept { return i.key(); }
1223 const Key *operator->() const noexcept { return &i.key(); }
1224 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1225 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1226
1227 inline key_iterator &operator++() noexcept { ++i; return *this; }
1228 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1229 const_iterator base() const noexcept { return i; }
1230 };
1231
1232 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1233 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1234
1235 // STL style
1236 inline iterator begin() { detach(); return iterator(d->begin()); }
1237 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1238 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1239 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1240 inline iterator end() noexcept { return iterator(); }
1241 inline const_iterator end() const noexcept { return const_iterator(); }
1242 inline const_iterator cend() const noexcept { return const_iterator(); }
1243 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1244 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1245 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1246 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
1247 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
1248 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1249 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1250 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1251 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1252 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1253 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
1254 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1255 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1256
1257 iterator erase(const_iterator it)
1258 {
1259 Q_ASSERT(it != constEnd());
1260 detach();
1261 // ensure a valid iterator across the detach:
1262 iterator i = iterator{d->detachedIterator(it.i)};
1263 typename Data::Bucket bucket(i.i);
1264
1265 d->erase(bucket);
1266 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
1267 ++i;
1268 return i;
1269 }
1270
1271 std::pair<iterator, iterator> equal_range(const Key &key)
1272 {
1273 return equal_range_impl(*this, key);
1274 }
1275 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
1276 {
1277 return equal_range_impl(*this, key);
1278 }
1279private:
1280 template <typename Hash, typename K> static auto equal_range_impl(Hash &self, const K &key)
1281 {
1282 auto first = self.find(key);
1283 auto second = first;
1284 if (second != decltype(first){})
1285 ++second;
1286 return std::make_pair(first, second);
1287 }
1288
1289 template <typename K> iterator findImpl(const K &key)
1290 {
1291 if (isEmpty()) // prevents detaching shared null
1292 return end();
1293 auto it = d->findBucket(key);
1294 size_t bucket = it.toBucketIndex(d);
1295 detach();
1296 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1297 if (it.isUnused())
1298 return end();
1299 return iterator(it.toIterator(d));
1300 }
1301 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
1302 {
1303 if (isEmpty())
1304 return end();
1305 auto it = d->findBucket(key);
1306 if (it.isUnused())
1307 return end();
1308 return const_iterator({d, it.toBucketIndex(d)});
1309 }
1310
1311public:
1312 typedef iterator Iterator;
1313 typedef const_iterator ConstIterator;
1314 inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
1315 iterator find(const Key &key)
1316 {
1317 return findImpl(key);
1318 }
1319 const_iterator find(const Key &key) const noexcept
1320 {
1321 return constFindImpl(key);
1322 }
1323 const_iterator constFind(const Key &key) const noexcept
1324 {
1325 return find(key);
1326 }
1327 iterator insert(const Key &key, const T &value)
1328 {
1329 return emplace(key, value);
1330 }
1331
1332 void insert(const QHash &hash)
1333 {
1334 if (d == hash.d || !hash.d)
1335 return;
1336 if (!d) {
1337 *this = hash;
1338 return;
1339 }
1340
1341 detach();
1342
1343 for (auto it = hash.begin(); it != hash.end(); ++it)
1344 emplace(it.key(), it.value());
1345 }
1346
1347 template <typename ...Args>
1348 iterator emplace(const Key &key, Args &&... args)
1349 {
1350 Key copy = key; // Needs to be explicit for MSVC 2019
1351 return emplace(std::move(copy), std::forward<Args>(args)...);
1352 }
1353
1354 template <typename ...Args>
1355 iterator emplace(Key &&key, Args &&... args)
1356 {
1357 if (isDetached()) {
1358 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
1359 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
1360 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1361 }
1362 // else: we must detach
1363 const auto copy = *this; // keep 'args' alive across the detach/growth
1364 detach();
1365 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1366 }
1367
1368 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
1369 static float max_load_factor() noexcept { return 0.5; }
1370 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
1371 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
1372
1373 [[nodiscard]]
1374 inline bool empty() const noexcept { return isEmpty(); }
1375
1376private:
1377 template <typename ...Args>
1378 iterator emplace_helper(Key &&key, Args &&... args)
1379 {
1380 auto result = d->findOrInsert(key);
1381 if (!result.initialized)
1382 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
1383 else
1384 result.it.node()->emplaceValue(std::forward<Args>(args)...);
1385 return iterator(result.it);
1386 }
1387
1388 template <typename K>
1389 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
1390
1391 template <typename K>
1392 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
1393
1394public:
1395 template <typename K, if_heterogeneously_searchable<K> = true>
1396 bool remove(const K &key)
1397 {
1398 return removeImpl(key);
1399 }
1400 template <typename K, if_heterogeneously_searchable<K> = true>
1401 T take(const K &key)
1402 {
1403 return takeImpl(key);
1404 }
1405 template <typename K, if_heterogeneously_searchable<K> = true>
1406 bool contains(const K &key) const
1407 {
1408 return d ? d->findNode(key) != nullptr : false;
1409 }
1410 template <typename K, if_heterogeneously_searchable<K> = true>
1411 qsizetype count(const K &key) const
1412 {
1413 return contains(key) ? 1 : 0;
1414 }
1415 template <typename K, if_heterogeneously_searchable<K> = true>
1416 T value(const K &key) const noexcept
1417 {
1418 if (auto *v = valueImpl(key))
1419 return *v;
1420 else
1421 return T();
1422 }
1423 template <typename K, if_heterogeneously_searchable<K> = true>
1424 T value(const K &key, const T &defaultValue) const noexcept
1425 {
1426 if (auto *v = valueImpl(key))
1427 return *v;
1428 else
1429 return defaultValue;
1430 }
1431 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
1432 T &operator[](const K &key)
1433 {
1434 return operatorIndexImpl(key);
1435 }
1436 template <typename K, if_heterogeneously_searchable<K> = true>
1437 const T operator[](const K &key) const noexcept
1438 {
1439 return value(key);
1440 }
1441 template <typename K, if_heterogeneously_searchable<K> = true>
1442 std::pair<iterator, iterator>
1443 equal_range(const K &key)
1444 {
1445 return equal_range_impl(*this, key);
1446 }
1447 template <typename K, if_heterogeneously_searchable<K> = true>
1448 std::pair<const_iterator, const_iterator>
1449 equal_range(const K &key) const noexcept
1450 {
1451 return equal_range_impl(*this, key);
1452 }
1453 template <typename K, if_heterogeneously_searchable<K> = true>
1454 iterator find(const K &key)
1455 {
1456 return findImpl(key);
1457 }
1458 template <typename K, if_heterogeneously_searchable<K> = true>
1459 const_iterator find(const K &key) const noexcept
1460 {
1461 return constFindImpl(key);
1462 }
1463 template <typename K, if_heterogeneously_searchable<K> = true>
1464 const_iterator constFind(const K &key) const noexcept
1465 {
1466 return find(key);
1467 }
1468};
1469
1470
1471template <typename Key, typename T>
1472class QMultiHash
1473{
1474 using Node = QHashPrivate::MultiNode<Key, T>;
1475 using Data = QHashPrivate::Data<Node>;
1476 using Chain = QHashPrivate::MultiNodeChain<T>;
1477
1478 Data *d = nullptr;
1479 qsizetype m_size = 0;
1480
1481public:
1482 using key_type = Key;
1483 using mapped_type = T;
1484 using value_type = T;
1485 using size_type = qsizetype;
1486 using difference_type = qsizetype;
1487 using reference = T &;
1488 using const_reference = const T &;
1489
1490 QMultiHash() noexcept = default;
1491 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1492 : d(new Data(list.size()))
1493 {
1494 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1495 insert(key: it->first, value: it->second);
1496 }
1497#ifdef Q_QDOC
1498 template <typename InputIterator>
1499 QMultiHash(InputIterator f, InputIterator l);
1500#else
1501 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1502 QMultiHash(InputIterator f, InputIterator l)
1503 {
1504 QtPrivate::reserveIfForwardIterator(this, f, l);
1505 for (; f != l; ++f)
1506 insert(key: f.key(), value: f.value());
1507 }
1508
1509 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1510 QMultiHash(InputIterator f, InputIterator l)
1511 {
1512 QtPrivate::reserveIfForwardIterator(this, f, l);
1513 for (; f != l; ++f) {
1514 auto &&e = *f;
1515 using V = decltype(e);
1516 insert(key: std::forward<V>(e).first, value: std::forward<V>(e).second);
1517 }
1518 }
1519#endif
1520 QMultiHash(const QMultiHash &other) noexcept
1521 : d(other.d), m_size(other.m_size)
1522 {
1523 if (d)
1524 d->ref.ref();
1525 }
1526 ~QMultiHash()
1527 {
1528 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
1529 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
1530
1531 if (d && !d->ref.deref())
1532 delete d;
1533 }
1534
1535 QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
1536 {
1537 if (d != other.d) {
1538 Data *o = other.d;
1539 if (o)
1540 o->ref.ref();
1541 if (d && !d->ref.deref())
1542 delete d;
1543 d = o;
1544 m_size = other.m_size;
1545 }
1546 return *this;
1547 }
1548 QMultiHash(QMultiHash &&other) noexcept
1549 : d(std::exchange(other.d, nullptr)),
1550 m_size(std::exchange(other.m_size, 0))
1551 {
1552 }
1553 QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value)
1554 {
1555 QMultiHash moved(std::move(other));
1556 swap(other&: moved);
1557 return *this;
1558 }
1559
1560 explicit QMultiHash(const QHash<Key, T> &other)
1561 : QMultiHash(other.begin(), other.end())
1562 {}
1563
1564 explicit QMultiHash(QHash<Key, T> &&other)
1565 {
1566 unite(std::move(other));
1567 }
1568
1569 void swap(QMultiHash &other) noexcept
1570 {
1571 qt_ptr_swap(d, other.d);
1572 std::swap(m_size, other.m_size);
1573 }
1574
1575#ifndef Q_QDOC
1576 template <typename AKey = Key, typename AT = T>
1577 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator==(const QMultiHash &other) const noexcept
1578 {
1579 if (d == other.d)
1580 return true;
1581 if (m_size != other.m_size)
1582 return false;
1583 if (m_size == 0)
1584 return true;
1585 // equal size, and both non-zero size => d pointers allocated for both
1586 Q_ASSERT(d);
1587 Q_ASSERT(other.d);
1588 if (d->size != other.d->size)
1589 return false;
1590 for (auto it = other.d->begin(); it != other.d->end(); ++it) {
1591 auto *n = d->findNode(it.node()->key);
1592 if (!n)
1593 return false;
1594 Chain *e = it.node()->value;
1595 while (e) {
1596 Chain *oe = n->value;
1597 while (oe) {
1598 if (oe->value == e->value)
1599 break;
1600 oe = oe->next;
1601 }
1602 if (!oe)
1603 return false;
1604 e = e->next;
1605 }
1606 }
1607 // all values must be the same as size is the same
1608 return true;
1609 }
1610 template <typename AKey = Key, typename AT = T>
1611 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator!=(const QMultiHash &other) const noexcept
1612 { return !(*this == other); }
1613#else
1614 bool operator==(const QMultiHash &other) const;
1615 bool operator!=(const QMultiHash &other) const;
1616#endif // Q_QDOC
1617
1618 inline qsizetype size() const noexcept { return m_size; }
1619
1620 [[nodiscard]]
1621 inline bool isEmpty() const noexcept { return !m_size; }
1622
1623 inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
1624 void reserve(qsizetype size)
1625 {
1626 // reserve(0) is used in squeeze()
1627 if (size && (this->capacity() >= size))
1628 return;
1629 if (isDetached())
1630 d->rehash(size);
1631 else
1632 d = Data::detached(d, size_t(size));
1633 }
1634 inline void squeeze() { reserve(size: 0); }
1635
1636 inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
1637 inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
1638 bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; }
1639
1640 void clear() noexcept(std::is_nothrow_destructible<Node>::value)
1641 {
1642 if (d && !d->ref.deref())
1643 delete d;
1644 d = nullptr;
1645 m_size = 0;
1646 }
1647
1648 qsizetype remove(const Key &key)
1649 {
1650 return removeImpl(key);
1651 }
1652private:
1653 template <typename K> qsizetype removeImpl(const K &key)
1654 {
1655 if (isEmpty()) // prevents detaching shared null
1656 return 0;
1657 auto it = d->findBucket(key);
1658 size_t bucket = it.toBucketIndex(d);
1659 detach();
1660 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1661
1662 if (it.isUnused())
1663 return 0;
1664 qsizetype n = Node::freeChain(it.node());
1665 m_size -= n;
1666 Q_ASSERT(m_size >= 0);
1667 d->erase(it);
1668 return n;
1669 }
1670
1671public:
1672 template <typename Predicate>
1673 qsizetype removeIf(Predicate pred)
1674 {
1675 return QtPrivate::associative_erase_if(*this, pred);
1676 }
1677
1678 T take(const Key &key)
1679 {
1680 return takeImpl(key);
1681 }
1682private:
1683 template <typename K> T takeImpl(const K &key)
1684 {
1685 if (isEmpty()) // prevents detaching shared null
1686 return T();
1687 auto it = d->findBucket(key);
1688 size_t bucket = it.toBucketIndex(d);
1689 detach();
1690 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1691
1692 if (it.isUnused())
1693 return T();
1694 Chain *e = it.node()->value;
1695 Q_ASSERT(e);
1696 T t = std::move(e->value);
1697 if (e->next) {
1698 it.node()->value = e->next;
1699 delete e;
1700 } else {
1701 // erase() deletes the values.
1702 d->erase(it);
1703 }
1704 --m_size;
1705 Q_ASSERT(m_size >= 0);
1706 return t;
1707 }
1708
1709public:
1710 bool contains(const Key &key) const noexcept
1711 {
1712 if (!d)
1713 return false;
1714 return d->findNode(key) != nullptr;
1715 }
1716
1717private:
1718 const Key *keyImpl(const T &value) const noexcept
1719 {
1720 if (d) {
1721 auto i = d->begin();
1722 while (i != d->end()) {
1723 Chain *e = i.node()->value;
1724 if (e->contains(value))
1725 return &i.node()->key;
1726 ++i;
1727 }
1728 }
1729
1730 return nullptr;
1731 }
1732public:
1733 Key key(const T &value) const noexcept
1734 {
1735 if (auto *k = keyImpl(value))
1736 return *k;
1737 else
1738 return Key();
1739 }
1740 Key key(const T &value, const Key &defaultKey) const noexcept
1741 {
1742 if (auto *k = keyImpl(value))
1743 return *k;
1744 else
1745 return defaultKey;
1746 }
1747
1748private:
1749 template <typename K>
1750 T *valueImpl(const K &key) const noexcept
1751 {
1752 if (d) {
1753 Node *n = d->findNode(key);
1754 if (n) {
1755 Q_ASSERT(n->value);
1756 return &n->value->value;
1757 }
1758 }
1759 return nullptr;
1760 }
1761public:
1762 T value(const Key &key) const noexcept
1763 {
1764 if (auto *v = valueImpl(key))
1765 return *v;
1766 else
1767 return T();
1768 }
1769 T value(const Key &key, const T &defaultValue) const noexcept
1770 {
1771 if (auto *v = valueImpl(key))
1772 return *v;
1773 else
1774 return defaultValue;
1775 }
1776
1777 T &operator[](const Key &key)
1778 {
1779 return operatorIndexImpl(key);
1780 }
1781private:
1782 template <typename K> T &operatorIndexImpl(const K &key)
1783 {
1784 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
1785 detach();
1786 auto result = d->findOrInsert(key);
1787 Q_ASSERT(!result.it.atEnd());
1788 if (!result.initialized) {
1789 Node::createInPlace(result.it.node(), Key(key), T());
1790 ++m_size;
1791 }
1792 return result.it.node()->value->value;
1793 }
1794
1795public:
1796 const T operator[](const Key &key) const noexcept
1797 {
1798 return value(key);
1799 }
1800
1801 QList<Key> uniqueKeys() const
1802 {
1803 QList<Key> res;
1804 if (d) {
1805 auto i = d->begin();
1806 while (i != d->end()) {
1807 res.append(i.node()->key);
1808 ++i;
1809 }
1810 }
1811 return res;
1812 }
1813
1814 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1815 QList<Key> keys(const T &value) const
1816 {
1817 QList<Key> res;
1818 const_iterator i = begin();
1819 while (i != end()) {
1820 if (i.value() == value)
1821 res.append(i.key());
1822 ++i;
1823 }
1824 return res;
1825 }
1826
1827 QList<T> values() const { return QList<T>(begin(), end()); }
1828 QList<T> values(const Key &key) const
1829 {
1830 return valuesImpl(key);
1831 }
1832private:
1833 template <typename K> QList<T> valuesImpl(const K &key) const
1834 {
1835 QList<T> values;
1836 if (d) {
1837 Node *n = d->findNode(key);
1838 if (n) {
1839 Chain *e = n->value;
1840 while (e) {
1841 values.append(e->value);
1842 e = e->next;
1843 }
1844 }
1845 }
1846 return values;
1847 }
1848
1849public:
1850 class const_iterator;
1851
1852 class iterator
1853 {
1854 using piter = typename QHashPrivate::iterator<Node>;
1855 friend class const_iterator;
1856 friend class QMultiHash<Key, T>;
1857 piter i;
1858 Chain **e = nullptr;
1859 explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1860 {
1861 if (!it.atEnd() && !e) {
1862 e = &it.node()->value;
1863 Q_ASSERT(e && *e);
1864 }
1865 }
1866
1867 public:
1868 typedef std::forward_iterator_tag iterator_category;
1869 typedef qptrdiff difference_type;
1870 typedef T value_type;
1871 typedef T *pointer;
1872 typedef T &reference;
1873
1874 constexpr iterator() noexcept = default;
1875
1876 inline const Key &key() const noexcept { return i.node()->key; }
1877 inline T &value() const noexcept { return (*e)->value; }
1878 inline T &operator*() const noexcept { return (*e)->value; }
1879 inline T *operator->() const noexcept { return &(*e)->value; }
1880 inline bool operator==(const iterator &o) const noexcept { return e == o.e; }
1881 inline bool operator!=(const iterator &o) const noexcept { return e != o.e; }
1882
1883 inline iterator &operator++() noexcept {
1884 Q_ASSERT(e && *e);
1885 e = &(*e)->next;
1886 Q_ASSERT(e);
1887 if (!*e) {
1888 ++i;
1889 e = i.atEnd() ? nullptr : &i.node()->value;
1890 }
1891 return *this;
1892 }
1893 inline iterator operator++(int) noexcept {
1894 iterator r = *this;
1895 ++(*this);
1896 return r;
1897 }
1898
1899 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1900 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1901 };
1902 friend class iterator;
1903
1904 class const_iterator
1905 {
1906 using piter = typename QHashPrivate::iterator<Node>;
1907 friend class iterator;
1908 friend class QMultiHash<Key, T>;
1909 piter i;
1910 Chain **e = nullptr;
1911 explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1912 {
1913 if (!it.atEnd() && !e) {
1914 e = &it.node()->value;
1915 Q_ASSERT(e && *e);
1916 }
1917 }
1918
1919 public:
1920 typedef std::forward_iterator_tag iterator_category;
1921 typedef qptrdiff difference_type;
1922 typedef T value_type;
1923 typedef const T *pointer;
1924 typedef const T &reference;
1925
1926 constexpr const_iterator() noexcept = default;
1927 inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { }
1928
1929 inline const Key &key() const noexcept { return i.node()->key; }
1930 inline T &value() const noexcept { return (*e)->value; }
1931 inline T &operator*() const noexcept { return (*e)->value; }
1932 inline T *operator->() const noexcept { return &(*e)->value; }
1933 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1934 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1935
1936 inline const_iterator &operator++() noexcept {
1937 Q_ASSERT(e && *e);
1938 e = &(*e)->next;
1939 Q_ASSERT(e);
1940 if (!*e) {
1941 ++i;
1942 e = i.atEnd() ? nullptr : &i.node()->value;
1943 }
1944 return *this;
1945 }
1946 inline const_iterator operator++(int) noexcept
1947 {
1948 const_iterator r = *this;
1949 ++(*this);
1950 return r;
1951 }
1952 };
1953 friend class const_iterator;
1954
1955 class key_iterator
1956 {
1957 const_iterator i;
1958
1959 public:
1960 typedef typename const_iterator::iterator_category iterator_category;
1961 typedef qptrdiff difference_type;
1962 typedef Key value_type;
1963 typedef const Key *pointer;
1964 typedef const Key &reference;
1965
1966 key_iterator() noexcept = default;
1967 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1968
1969 const Key &operator*() const noexcept { return i.key(); }
1970 const Key *operator->() const noexcept { return &i.key(); }
1971 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1972 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1973
1974 inline key_iterator &operator++() noexcept { ++i; return *this; }
1975 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1976 const_iterator base() const noexcept { return i; }
1977 };
1978
1979 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1980 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1981
1982 // STL style
1983 inline iterator begin() { detach(); return iterator(d->begin()); }
1984 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1985 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1986 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1987 inline iterator end() noexcept { return iterator(); }
1988 inline const_iterator end() const noexcept { return const_iterator(); }
1989 inline const_iterator cend() const noexcept { return const_iterator(); }
1990 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1991 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1992 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1993 inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); }
1994 inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); }
1995 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1996 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1997 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1998 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1999 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
2000 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
2001 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
2002 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
2003
2004 iterator detach(const_iterator it)
2005 {
2006 auto i = it.i;
2007 Chain **e = it.e;
2008 if (d->ref.isShared()) {
2009 // need to store iterator position before detaching
2010 qsizetype n = 0;
2011 Chain *entry = i.node()->value;
2012 while (entry != *it.e) {
2013 ++n;
2014 entry = entry->next;
2015 }
2016 Q_ASSERT(entry);
2017 detach_helper();
2018
2019 i = d->detachedIterator(i);
2020 e = &i.node()->value;
2021 while (n) {
2022 e = &(*e)->next;
2023 --n;
2024 }
2025 Q_ASSERT(e && *e);
2026 }
2027 return iterator(i, e);
2028 }
2029
2030 iterator erase(const_iterator it)
2031 {
2032 Q_ASSERT(d);
2033 iterator iter = detach(it);
2034 iterator i = iter;
2035 Chain *e = *i.e;
2036 Chain *next = e->next;
2037 *i.e = next;
2038 delete e;
2039 if (!next) {
2040 if (i.e == &i.i.node()->value) {
2041 // last remaining entry, erase
2042 typename Data::Bucket bucket(i.i);
2043 d->erase(bucket);
2044 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
2045 i = iterator(++iter.i);
2046 else // 'i' currently has a nullptr chain. So, we must recreate it
2047 i = iterator(bucket.toIterator(d));
2048 } else {
2049 i = iterator(++iter.i);
2050 }
2051 }
2052 --m_size;
2053 Q_ASSERT(m_size >= 0);
2054 return i;
2055 }
2056
2057 // more Qt
2058 typedef iterator Iterator;
2059 typedef const_iterator ConstIterator;
2060 inline qsizetype count() const noexcept { return size(); }
2061
2062private:
2063 template <typename K> iterator findImpl(const K &key)
2064 {
2065 if (isEmpty())
2066 return end();
2067 auto it = d->findBucket(key);
2068 size_t bucket = it.toBucketIndex(d);
2069 detach();
2070 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2071
2072 if (it.isUnused())
2073 return end();
2074 return iterator(it.toIterator(d));
2075 }
2076 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
2077 {
2078 if (isEmpty())
2079 return end();
2080 auto it = d->findBucket(key);
2081 if (it.isUnused())
2082 return constEnd();
2083 return const_iterator(it.toIterator(d));
2084 }
2085public:
2086 iterator find(const Key &key)
2087 {
2088 return findImpl(key);
2089 }
2090 const_iterator constFind(const Key &key) const noexcept
2091 {
2092 return constFindImpl(key);
2093 }
2094 const_iterator find(const Key &key) const noexcept
2095 {
2096 return constFindImpl(key);
2097 }
2098
2099 iterator insert(const Key &key, const T &value)
2100 {
2101 return emplace(key, value);
2102 }
2103
2104 template <typename ...Args>
2105 iterator emplace(const Key &key, Args &&... args)
2106 {
2107 return emplace(Key(key), std::forward<Args>(args)...);
2108 }
2109
2110 template <typename ...Args>
2111 iterator emplace(Key &&key, Args &&... args)
2112 {
2113 if (isDetached()) {
2114 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2115 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
2116 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2117 }
2118 // else: we must detach
2119 const auto copy = *this; // keep 'args' alive across the detach/growth
2120 detach();
2121 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2122 }
2123
2124
2125 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
2126 static float max_load_factor() noexcept { return 0.5; }
2127 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
2128 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
2129
2130 [[nodiscard]]
2131 inline bool empty() const noexcept { return isEmpty(); }
2132
2133 inline iterator replace(const Key &key, const T &value)
2134 {
2135 return emplaceReplace(key, value);
2136 }
2137
2138 template <typename ...Args>
2139 iterator emplaceReplace(const Key &key, Args &&... args)
2140 {
2141 return emplaceReplace(Key(key), std::forward<Args>(args)...);
2142 }
2143
2144 template <typename ...Args>
2145 iterator emplaceReplace(Key &&key, Args &&... args)
2146 {
2147 if (isDetached()) {
2148 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2149 return emplaceReplace_helper(std::move(key), T(std::forward<Args>(args)...));
2150 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2151 }
2152 // else: we must detach
2153 const auto copy = *this; // keep 'args' alive across the detach/growth
2154 detach();
2155 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2156 }
2157
2158 inline QMultiHash &operator+=(const QMultiHash &other)
2159 { this->unite(other); return *this; }
2160 inline QMultiHash operator+(const QMultiHash &other) const
2161 { QMultiHash result = *this; result += other; return result; }
2162
2163 bool contains(const Key &key, const T &value) const noexcept
2164 {
2165 return containsImpl(key, value);
2166 }
2167private:
2168 template <typename K> bool containsImpl(const K &key, const T &value) const noexcept
2169 {
2170 if (isEmpty())
2171 return false;
2172 auto n = d->findNode(key);
2173 if (n == nullptr)
2174 return false;
2175 return n->value->contains(value);
2176 }
2177
2178public:
2179 qsizetype remove(const Key &key, const T &value)
2180 {
2181 return removeImpl(key, value);
2182 }
2183private:
2184 template <typename K> qsizetype removeImpl(const K &key, const T &value)
2185 {
2186 if (isEmpty()) // prevents detaching shared null
2187 return 0;
2188 auto it = d->findBucket(key);
2189 size_t bucket = it.toBucketIndex(d);
2190 detach();
2191 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2192
2193 if (it.isUnused())
2194 return 0;
2195 qsizetype n = 0;
2196 Chain **e = &it.node()->value;
2197 while (*e) {
2198 Chain *entry = *e;
2199 if (entry->value == value) {
2200 *e = entry->next;
2201 delete entry;
2202 ++n;
2203 } else {
2204 e = &entry->next;
2205 }
2206 }
2207 if (!it.node()->value)
2208 d->erase(it);
2209 m_size -= n;
2210 Q_ASSERT(m_size >= 0);
2211 return n;
2212 }
2213
2214public:
2215 qsizetype count(const Key &key) const noexcept
2216 {
2217 return countImpl(key);
2218 }
2219private:
2220 template <typename K> qsizetype countImpl(const K &key) const noexcept
2221 {
2222 if (!d)
2223 return 0;
2224 auto it = d->findBucket(key);
2225 if (it.isUnused())
2226 return 0;
2227 qsizetype n = 0;
2228 Chain *e = it.node()->value;
2229 while (e) {
2230 ++n;
2231 e = e->next;
2232 }
2233
2234 return n;
2235 }
2236
2237public:
2238 qsizetype count(const Key &key, const T &value) const noexcept
2239 {
2240 return countImpl(key, value);
2241 }
2242private:
2243 template <typename K> qsizetype countImpl(const K &key, const T &value) const noexcept
2244 {
2245 if (!d)
2246 return 0;
2247 auto it = d->findBucket(key);
2248 if (it.isUnused())
2249 return 0;
2250 qsizetype n = 0;
2251 Chain *e = it.node()->value;
2252 while (e) {
2253 if (e->value == value)
2254 ++n;
2255 e = e->next;
2256 }
2257
2258 return n;
2259 }
2260
2261 template <typename K> iterator findImpl(const K &key, const T &value)
2262 {
2263 if (isEmpty())
2264 return end();
2265 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key'/'value' alive across the detach
2266 detach();
2267 auto it = constFind(key, value);
2268 return iterator(it.i, it.e);
2269 }
2270 template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept
2271 {
2272 const_iterator i(constFind(key));
2273 const_iterator end(constEnd());
2274 while (i != end && i.key() == key) {
2275 if (i.value() == value)
2276 return i;
2277 ++i;
2278 }
2279 return end;
2280 }
2281
2282public:
2283 iterator find(const Key &key, const T &value)
2284 {
2285 return findImpl(key, value);
2286 }
2287
2288 const_iterator constFind(const Key &key, const T &value) const noexcept
2289 {
2290 return constFindImpl(key, value);
2291 }
2292 const_iterator find(const Key &key, const T &value) const noexcept
2293 {
2294 return constFind(key, value);
2295 }
2296
2297 QMultiHash &unite(const QMultiHash &other)
2298 {
2299 if (isEmpty()) {
2300 *this = other;
2301 } else if (other.isEmpty()) {
2302 ;
2303 } else {
2304 QMultiHash copy(other);
2305 detach();
2306 for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit)
2307 insert(key: cit.key(), value: *cit);
2308 }
2309 return *this;
2310 }
2311
2312 QMultiHash &unite(const QHash<Key, T> &other)
2313 {
2314 for (auto cit = other.cbegin(); cit != other.cend(); ++cit)
2315 insert(key: cit.key(), value: *cit);
2316 return *this;
2317 }
2318
2319 QMultiHash &unite(QHash<Key, T> &&other)
2320 {
2321 if (!other.isDetached()) {
2322 unite(other);
2323 return *this;
2324 }
2325 auto it = other.d->begin();
2326 for (const auto end = other.d->end(); it != end; ++it)
2327 emplace(std::move(it.node()->key), std::move(it.node()->takeValue()));
2328 other.clear();
2329 return *this;
2330 }
2331
2332 std::pair<iterator, iterator> equal_range(const Key &key)
2333 {
2334 return equal_range_impl(key);
2335 }
2336private:
2337 template <typename K> std::pair<iterator, iterator> equal_range_impl(const K &key)
2338 {
2339 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
2340 detach();
2341 auto pair = std::as_const(*this).equal_range(key);
2342 return {iterator(pair.first.i), iterator(pair.second.i)};
2343 }
2344
2345public:
2346 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
2347 {
2348 return equal_range_impl(key);
2349 }
2350private:
2351 template <typename K> std::pair<const_iterator, const_iterator> equal_range_impl(const K &key) const noexcept
2352 {
2353 if (!d)
2354 return {end(), end()};
2355
2356 auto bucket = d->findBucket(key);
2357 if (bucket.isUnused())
2358 return {end(), end()};
2359 auto it = bucket.toIterator(d);
2360 auto end = it;
2361 ++end;
2362 return {const_iterator(it), const_iterator(end)};
2363 }
2364
2365 void detach_helper()
2366 {
2367 if (!d) {
2368 d = new Data;
2369 return;
2370 }
2371 Data *dd = new Data(*d);
2372 if (!d->ref.deref())
2373 delete d;
2374 d = dd;
2375 }
2376
2377 template<typename... Args>
2378 iterator emplace_helper(Key &&key, Args &&...args)
2379 {
2380 auto result = d->findOrInsert(key);
2381 if (!result.initialized)
2382 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2383 else
2384 result.it.node()->insertMulti(std::forward<Args>(args)...);
2385 ++m_size;
2386 return iterator(result.it);
2387 }
2388
2389 template<typename... Args>
2390 iterator emplaceReplace_helper(Key &&key, Args &&...args)
2391 {
2392 auto result = d->findOrInsert(key);
2393 if (!result.initialized) {
2394 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2395 ++m_size;
2396 } else {
2397 result.it.node()->emplaceValue(std::forward<Args>(args)...);
2398 }
2399 return iterator(result.it);
2400 }
2401
2402 template <typename K>
2403 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
2404
2405 template <typename K>
2406 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
2407
2408public:
2409 template <typename K, if_heterogeneously_searchable<K> = true>
2410 qsizetype remove(const K &key)
2411 {
2412 return removeImpl(key);
2413 }
2414 template <typename K, if_heterogeneously_searchable<K> = true>
2415 T take(const K &key)
2416 {
2417 return takeImpl(key);
2418 }
2419 template <typename K, if_heterogeneously_searchable<K> = true>
2420 bool contains(const K &key) const noexcept
2421 {
2422 if (!d)
2423 return false;
2424 return d->findNode(key) != nullptr;
2425 }
2426 template <typename K, if_heterogeneously_searchable<K> = true>
2427 T value(const K &key) const noexcept
2428 {
2429 if (auto *v = valueImpl(key))
2430 return *v;
2431 else
2432 return T();
2433 }
2434 template <typename K, if_heterogeneously_searchable<K> = true>
2435 T value(const K &key, const T &defaultValue) const noexcept
2436 {
2437 if (auto *v = valueImpl(key))
2438 return *v;
2439 else
2440 return defaultValue;
2441 }
2442 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
2443 T &operator[](const K &key)
2444 {
2445 return operatorIndexImpl(key);
2446 }
2447 template <typename K, if_heterogeneously_searchable<K> = true>
2448 const T operator[](const K &key) const noexcept
2449 {
2450 return value(key);
2451 }
2452 template <typename K, if_heterogeneously_searchable<K> = true>
2453 QList<T> values(const K &key)
2454 {
2455 return valuesImpl(key);
2456 }
2457 template <typename K, if_heterogeneously_searchable<K> = true>
2458 iterator find(const K &key)
2459 {
2460 return findImpl(key);
2461 }
2462 template <typename K, if_heterogeneously_searchable<K> = true>
2463 const_iterator constFind(const K &key) const noexcept
2464 {
2465 return constFindImpl(key);
2466 }
2467 template <typename K, if_heterogeneously_searchable<K> = true>
2468 const_iterator find(const K &key) const noexcept
2469 {
2470 return constFindImpl(key);
2471 }
2472 template <typename K, if_heterogeneously_searchable<K> = true>
2473 bool contains(const K &key, const T &value) const noexcept
2474 {
2475 return containsImpl(key, value);
2476 }
2477 template <typename K, if_heterogeneously_searchable<K> = true>
2478 qsizetype remove(const K &key, const T &value)
2479 {
2480 return removeImpl(key, value);
2481 }
2482 template <typename K, if_heterogeneously_searchable<K> = true>
2483 qsizetype count(const K &key) const noexcept
2484 {
2485 return countImpl(key);
2486 }
2487 template <typename K, if_heterogeneously_searchable<K> = true>
2488 qsizetype count(const K &key, const T &value) const noexcept
2489 {
2490 return countImpl(key, value);
2491 }
2492 template <typename K, if_heterogeneously_searchable<K> = true>
2493 iterator find(const K &key, const T &value)
2494 {
2495 return findImpl(key, value);
2496 }
2497 template <typename K, if_heterogeneously_searchable<K> = true>
2498 const_iterator constFind(const K &key, const T &value) const noexcept
2499 {
2500 return constFindImpl(key, value);
2501 }
2502 template <typename K, if_heterogeneously_searchable<K> = true>
2503 const_iterator find(const K &key, const T &value) const noexcept
2504 {
2505 return constFind(key, value);
2506 }
2507 template <typename K, if_heterogeneously_searchable<K> = true>
2508 std::pair<iterator, iterator>
2509 equal_range(const K &key)
2510 {
2511 return equal_range_impl(key);
2512 }
2513 template <typename K, if_heterogeneously_searchable<K> = true>
2514 std::pair<const_iterator, const_iterator>
2515 equal_range(const K &key) const noexcept
2516 {
2517 return equal_range_impl(key);
2518 }
2519};
2520
2521Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2522Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2523Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2524Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2525
2526template <class Key, class T>
2527size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
2528 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2529{
2530 size_t hash = 0;
2531 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2532 QtPrivate::QHashCombine combine;
2533 size_t h = combine(seed, it.key());
2534 // use + to keep the result independent of the ordering of the keys
2535 hash += combine(h, it.value());
2536 }
2537 return hash;
2538}
2539
2540template <class Key, class T>
2541inline size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
2542 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2543{
2544 size_t hash = 0;
2545 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2546 QtPrivate::QHashCombine combine;
2547 size_t h = combine(seed, it.key());
2548 // use + to keep the result independent of the ordering of the keys
2549 hash += combine(h, it.value());
2550 }
2551 return hash;
2552}
2553
2554template <typename Key, typename T, typename Predicate>
2555qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
2556{
2557 return QtPrivate::associative_erase_if(hash, pred);
2558}
2559
2560template <typename Key, typename T, typename Predicate>
2561qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
2562{
2563 return QtPrivate::associative_erase_if(hash, pred);
2564}
2565
2566QT_END_NAMESPACE
2567
2568#endif // QHASH_H
2569

source code of qtbase/src/corelib/tools/qhash.h