1// Copyright (C) 2020 The Qt Company Ltd.
2// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
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 size_t bucket = it.toBucketIndex(d);
979 detach();
980 it = typename Data::Bucket(d, bucket); // reattach in case of detach
981
982 if (it.isUnused())
983 return false;
984 d->erase(it);
985 return true;
986 }
987
988public:
989 template <typename Predicate>
990 qsizetype removeIf(Predicate pred)
991 {
992 return QtPrivate::associative_erase_if(*this, pred);
993 }
994
995 T take(const Key &key)
996 {
997 return takeImpl(key);
998 }
999private:
1000 template <typename K> T takeImpl(const K &key)
1001 {
1002 if (isEmpty()) // prevents detaching shared null
1003 return T();
1004 auto it = d->findBucket(key);
1005 size_t bucket = it.toBucketIndex(d);
1006 detach();
1007 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1008
1009 if (it.isUnused())
1010 return T();
1011 T value = it.node()->takeValue();
1012 d->erase(it);
1013 return value;
1014 }
1015
1016public:
1017 bool contains(const Key &key) const noexcept
1018 {
1019 if (!d)
1020 return false;
1021 return d->findNode(key) != nullptr;
1022 }
1023 qsizetype count(const Key &key) const noexcept
1024 {
1025 return contains(key) ? 1 : 0;
1026 }
1027
1028private:
1029 const Key *keyImpl(const T &value) const noexcept
1030 {
1031 if (d) {
1032 const_iterator i = begin();
1033 while (i != end()) {
1034 if (i.value() == value)
1035 return &i.key();
1036 ++i;
1037 }
1038 }
1039
1040 return nullptr;
1041 }
1042
1043public:
1044 Key key(const T &value) const noexcept
1045 {
1046 if (auto *k = keyImpl(value))
1047 return *k;
1048 else
1049 return Key();
1050 }
1051 Key key(const T &value, const Key &defaultKey) const noexcept
1052 {
1053 if (auto *k = keyImpl(value))
1054 return *k;
1055 else
1056 return defaultKey;
1057 }
1058
1059private:
1060 template <typename K>
1061 T *valueImpl(const K &key) const noexcept
1062 {
1063 if (d) {
1064 Node *n = d->findNode(key);
1065 if (n)
1066 return &n->value;
1067 }
1068 return nullptr;
1069 }
1070public:
1071 T value(const Key &key) const noexcept
1072 {
1073 if (T *v = valueImpl(key))
1074 return *v;
1075 else
1076 return T();
1077 }
1078
1079 T value(const Key &key, const T &defaultValue) const noexcept
1080 {
1081 if (T *v = valueImpl(key))
1082 return *v;
1083 else
1084 return defaultValue;
1085 }
1086
1087 T &operator[](const Key &key)
1088 {
1089 return operatorIndexImpl(key);
1090 }
1091private:
1092 template <typename K> T &operatorIndexImpl(const K &key)
1093 {
1094 const auto copy = isDetached() ? QHash() : *this; // keep 'key' alive across the detach
1095 detach();
1096 auto result = d->findOrInsert(key);
1097 Q_ASSERT(!result.it.atEnd());
1098 if (!result.initialized)
1099 Node::createInPlace(result.it.node(), Key(key), T());
1100 return result.it.node()->value;
1101 }
1102
1103public:
1104 const T operator[](const Key &key) const noexcept
1105 {
1106 return value(key);
1107 }
1108
1109 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1110 QList<Key> keys(const T &value) const
1111 {
1112 QList<Key> res;
1113 const_iterator i = begin();
1114 while (i != end()) {
1115 if (i.value() == value)
1116 res.append(i.key());
1117 ++i;
1118 }
1119 return res;
1120 }
1121 QList<T> values() const { return QList<T>(begin(), end()); }
1122
1123 class const_iterator;
1124
1125 class iterator
1126 {
1127 using piter = typename QHashPrivate::iterator<Node>;
1128 friend class const_iterator;
1129 friend class QHash<Key, T>;
1130 friend class QSet<Key>;
1131 piter i;
1132 explicit inline iterator(piter it) noexcept : i(it) { }
1133
1134 public:
1135 typedef std::forward_iterator_tag iterator_category;
1136 typedef qptrdiff difference_type;
1137 typedef T value_type;
1138 typedef T *pointer;
1139 typedef T &reference;
1140
1141 constexpr iterator() noexcept = default;
1142
1143 inline const Key &key() const noexcept { return i.node()->key; }
1144 inline T &value() const noexcept { return i.node()->value; }
1145 inline T &operator*() const noexcept { return i.node()->value; }
1146 inline T *operator->() const noexcept { return &i.node()->value; }
1147 inline bool operator==(const iterator &o) const noexcept { return i == o.i; }
1148 inline bool operator!=(const iterator &o) const noexcept { return i != o.i; }
1149
1150 inline iterator &operator++() noexcept
1151 {
1152 ++i;
1153 return *this;
1154 }
1155 inline iterator operator++(int) noexcept
1156 {
1157 iterator r = *this;
1158 ++i;
1159 return r;
1160 }
1161
1162 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1163 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1164 };
1165 friend class iterator;
1166
1167 class const_iterator
1168 {
1169 using piter = typename QHashPrivate::iterator<Node>;
1170 friend class iterator;
1171 friend class QHash<Key, T>;
1172 friend class QSet<Key>;
1173 piter i;
1174 explicit inline const_iterator(piter it) : i(it) { }
1175
1176 public:
1177 typedef std::forward_iterator_tag iterator_category;
1178 typedef qptrdiff difference_type;
1179 typedef T value_type;
1180 typedef const T *pointer;
1181 typedef const T &reference;
1182
1183 constexpr const_iterator() noexcept = default;
1184 inline const_iterator(const iterator &o) noexcept : i(o.i) { }
1185
1186 inline const Key &key() const noexcept { return i.node()->key; }
1187 inline const T &value() const noexcept { return i.node()->value; }
1188 inline const T &operator*() const noexcept { return i.node()->value; }
1189 inline const T *operator->() const noexcept { return &i.node()->value; }
1190 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1191 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1192
1193 inline const_iterator &operator++() noexcept
1194 {
1195 ++i;
1196 return *this;
1197 }
1198 inline const_iterator operator++(int) noexcept
1199 {
1200 const_iterator r = *this;
1201 ++i;
1202 return r;
1203 }
1204 };
1205 friend class const_iterator;
1206
1207 class key_iterator
1208 {
1209 const_iterator i;
1210
1211 public:
1212 typedef typename const_iterator::iterator_category iterator_category;
1213 typedef qptrdiff difference_type;
1214 typedef Key value_type;
1215 typedef const Key *pointer;
1216 typedef const Key &reference;
1217
1218 key_iterator() noexcept = default;
1219 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1220
1221 const Key &operator*() const noexcept { return i.key(); }
1222 const Key *operator->() const noexcept { return &i.key(); }
1223 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1224 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1225
1226 inline key_iterator &operator++() noexcept { ++i; return *this; }
1227 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1228 const_iterator base() const noexcept { return i; }
1229 };
1230
1231 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1232 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1233
1234 // STL style
1235 inline iterator begin() { detach(); return iterator(d->begin()); }
1236 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1237 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1238 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1239 inline iterator end() noexcept { return iterator(); }
1240 inline const_iterator end() const noexcept { return const_iterator(); }
1241 inline const_iterator cend() const noexcept { return const_iterator(); }
1242 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1243 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1244 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1245 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
1246 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
1247 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1248 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1249 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1250 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1251 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1252 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
1253 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1254 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1255
1256 iterator erase(const_iterator it)
1257 {
1258 Q_ASSERT(it != constEnd());
1259 detach();
1260 // ensure a valid iterator across the detach:
1261 iterator i = iterator{d->detachedIterator(it.i)};
1262 typename Data::Bucket bucket(i.i);
1263
1264 d->erase(bucket);
1265 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
1266 ++i;
1267 return i;
1268 }
1269
1270 std::pair<iterator, iterator> equal_range(const Key &key)
1271 {
1272 return equal_range_impl(*this, key);
1273 }
1274 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
1275 {
1276 return equal_range_impl(*this, key);
1277 }
1278private:
1279 template <typename Hash, typename K> static auto equal_range_impl(Hash &self, const K &key)
1280 {
1281 auto first = self.find(key);
1282 auto second = first;
1283 if (second != decltype(first){})
1284 ++second;
1285 return std::make_pair(first, second);
1286 }
1287
1288 template <typename K> iterator findImpl(const K &key)
1289 {
1290 if (isEmpty()) // prevents detaching shared null
1291 return end();
1292 auto it = d->findBucket(key);
1293 size_t bucket = it.toBucketIndex(d);
1294 detach();
1295 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1296 if (it.isUnused())
1297 return end();
1298 return iterator(it.toIterator(d));
1299 }
1300 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
1301 {
1302 if (isEmpty())
1303 return end();
1304 auto it = d->findBucket(key);
1305 if (it.isUnused())
1306 return end();
1307 return const_iterator({d, it.toBucketIndex(d)});
1308 }
1309
1310public:
1311 typedef iterator Iterator;
1312 typedef const_iterator ConstIterator;
1313 inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
1314 iterator find(const Key &key)
1315 {
1316 return findImpl(key);
1317 }
1318 const_iterator find(const Key &key) const noexcept
1319 {
1320 return constFindImpl(key);
1321 }
1322 const_iterator constFind(const Key &key) const noexcept
1323 {
1324 return find(key);
1325 }
1326 iterator insert(const Key &key, const T &value)
1327 {
1328 return emplace(key, value);
1329 }
1330
1331 void insert(const QHash &hash)
1332 {
1333 if (d == hash.d || !hash.d)
1334 return;
1335 if (!d) {
1336 *this = hash;
1337 return;
1338 }
1339
1340 detach();
1341
1342 for (auto it = hash.begin(); it != hash.end(); ++it)
1343 emplace(it.key(), it.value());
1344 }
1345
1346 template <typename ...Args>
1347 iterator emplace(const Key &key, Args &&... args)
1348 {
1349 Key copy = key; // Needs to be explicit for MSVC 2019
1350 return emplace(std::move(copy), std::forward<Args>(args)...);
1351 }
1352
1353 template <typename ...Args>
1354 iterator emplace(Key &&key, Args &&... args)
1355 {
1356 if (isDetached()) {
1357 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
1358 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
1359 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1360 }
1361 // else: we must detach
1362 const auto copy = *this; // keep 'args' alive across the detach/growth
1363 detach();
1364 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1365 }
1366
1367 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
1368 static float max_load_factor() noexcept { return 0.5; }
1369 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
1370 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
1371
1372 [[nodiscard]]
1373 inline bool empty() const noexcept { return isEmpty(); }
1374
1375private:
1376 template <typename ...Args>
1377 iterator emplace_helper(Key &&key, Args &&... args)
1378 {
1379 auto result = d->findOrInsert(key);
1380 if (!result.initialized)
1381 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
1382 else
1383 result.it.node()->emplaceValue(std::forward<Args>(args)...);
1384 return iterator(result.it);
1385 }
1386
1387 template <typename K>
1388 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
1389
1390 template <typename K>
1391 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
1392
1393public:
1394 template <typename K, if_heterogeneously_searchable<K> = true>
1395 bool remove(const K &key)
1396 {
1397 return removeImpl(key);
1398 }
1399 template <typename K, if_heterogeneously_searchable<K> = true>
1400 T take(const K &key)
1401 {
1402 return takeImpl(key);
1403 }
1404 template <typename K, if_heterogeneously_searchable<K> = true>
1405 bool contains(const K &key) const
1406 {
1407 return d ? d->findNode(key) != nullptr : false;
1408 }
1409 template <typename K, if_heterogeneously_searchable<K> = true>
1410 qsizetype count(const K &key) const
1411 {
1412 return contains(key) ? 1 : 0;
1413 }
1414 template <typename K, if_heterogeneously_searchable<K> = true>
1415 T value(const K &key) const noexcept
1416 {
1417 if (auto *v = valueImpl(key))
1418 return *v;
1419 else
1420 return T();
1421 }
1422 template <typename K, if_heterogeneously_searchable<K> = true>
1423 T value(const K &key, const T &defaultValue) const noexcept
1424 {
1425 if (auto *v = valueImpl(key))
1426 return *v;
1427 else
1428 return defaultValue;
1429 }
1430 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
1431 T &operator[](const K &key)
1432 {
1433 return operatorIndexImpl(key);
1434 }
1435 template <typename K, if_heterogeneously_searchable<K> = true>
1436 const T operator[](const K &key) const noexcept
1437 {
1438 return value(key);
1439 }
1440 template <typename K, if_heterogeneously_searchable<K> = true>
1441 std::pair<iterator, iterator>
1442 equal_range(const K &key)
1443 {
1444 return equal_range_impl(*this, key);
1445 }
1446 template <typename K, if_heterogeneously_searchable<K> = true>
1447 std::pair<const_iterator, const_iterator>
1448 equal_range(const K &key) const noexcept
1449 {
1450 return equal_range_impl(*this, key);
1451 }
1452 template <typename K, if_heterogeneously_searchable<K> = true>
1453 iterator find(const K &key)
1454 {
1455 return findImpl(key);
1456 }
1457 template <typename K, if_heterogeneously_searchable<K> = true>
1458 const_iterator find(const K &key) const noexcept
1459 {
1460 return constFindImpl(key);
1461 }
1462 template <typename K, if_heterogeneously_searchable<K> = true>
1463 const_iterator constFind(const K &key) const noexcept
1464 {
1465 return find(key);
1466 }
1467};
1468
1469
1470template <typename Key, typename T>
1471class QMultiHash
1472{
1473 using Node = QHashPrivate::MultiNode<Key, T>;
1474 using Data = QHashPrivate::Data<Node>;
1475 using Chain = QHashPrivate::MultiNodeChain<T>;
1476
1477 Data *d = nullptr;
1478 qsizetype m_size = 0;
1479
1480public:
1481 using key_type = Key;
1482 using mapped_type = T;
1483 using value_type = T;
1484 using size_type = qsizetype;
1485 using difference_type = qsizetype;
1486 using reference = T &;
1487 using const_reference = const T &;
1488
1489 QMultiHash() noexcept = default;
1490 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1491 : d(new Data(list.size()))
1492 {
1493 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1494 insert(key: it->first, value: it->second);
1495 }
1496#ifdef Q_QDOC
1497 template <typename InputIterator>
1498 QMultiHash(InputIterator f, InputIterator l);
1499#else
1500 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1501 QMultiHash(InputIterator f, InputIterator l)
1502 {
1503 QtPrivate::reserveIfForwardIterator(this, f, l);
1504 for (; f != l; ++f)
1505 insert(key: f.key(), value: f.value());
1506 }
1507
1508 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1509 QMultiHash(InputIterator f, InputIterator l)
1510 {
1511 QtPrivate::reserveIfForwardIterator(this, f, l);
1512 for (; f != l; ++f) {
1513 auto &&e = *f;
1514 using V = decltype(e);
1515 insert(key: std::forward<V>(e).first, value: std::forward<V>(e).second);
1516 }
1517 }
1518#endif
1519 QMultiHash(const QMultiHash &other) noexcept
1520 : d(other.d), m_size(other.m_size)
1521 {
1522 if (d)
1523 d->ref.ref();
1524 }
1525 ~QMultiHash()
1526 {
1527 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
1528 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
1529
1530 if (d && !d->ref.deref())
1531 delete d;
1532 }
1533
1534 QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
1535 {
1536 if (d != other.d) {
1537 Data *o = other.d;
1538 if (o)
1539 o->ref.ref();
1540 if (d && !d->ref.deref())
1541 delete d;
1542 d = o;
1543 m_size = other.m_size;
1544 }
1545 return *this;
1546 }
1547 QMultiHash(QMultiHash &&other) noexcept
1548 : d(std::exchange(other.d, nullptr)),
1549 m_size(std::exchange(obj&: other.m_size, new_val: 0))
1550 {
1551 }
1552 QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value)
1553 {
1554 QMultiHash moved(std::move(other));
1555 swap(other&: moved);
1556 return *this;
1557 }
1558
1559 explicit QMultiHash(const QHash<Key, T> &other)
1560 : QMultiHash(other.begin(), other.end())
1561 {}
1562
1563 explicit QMultiHash(QHash<Key, T> &&other)
1564 {
1565 unite(std::move(other));
1566 }
1567
1568 void swap(QMultiHash &other) noexcept
1569 {
1570 qt_ptr_swap(d, other.d);
1571 std::swap(a&: m_size, b&: other.m_size);
1572 }
1573
1574#ifndef Q_QDOC
1575 template <typename AKey = Key, typename AT = T>
1576 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator==(const QMultiHash &other) const noexcept
1577 {
1578 if (d == other.d)
1579 return true;
1580 if (m_size != other.m_size)
1581 return false;
1582 if (m_size == 0)
1583 return true;
1584 // equal size, and both non-zero size => d pointers allocated for both
1585 Q_ASSERT(d);
1586 Q_ASSERT(other.d);
1587 if (d->size != other.d->size)
1588 return false;
1589 for (auto it = other.d->begin(); it != other.d->end(); ++it) {
1590 auto *n = d->findNode(it.node()->key);
1591 if (!n)
1592 return false;
1593 Chain *e = it.node()->value;
1594 while (e) {
1595 Chain *oe = n->value;
1596 while (oe) {
1597 if (oe->value == e->value)
1598 break;
1599 oe = oe->next;
1600 }
1601 if (!oe)
1602 return false;
1603 e = e->next;
1604 }
1605 }
1606 // all values must be the same as size is the same
1607 return true;
1608 }
1609 template <typename AKey = Key, typename AT = T>
1610 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator!=(const QMultiHash &other) const noexcept
1611 { return !(*this == other); }
1612#else
1613 bool operator==(const QMultiHash &other) const;
1614 bool operator!=(const QMultiHash &other) const;
1615#endif // Q_QDOC
1616
1617 inline qsizetype size() const noexcept { return m_size; }
1618
1619 [[nodiscard]]
1620 inline bool isEmpty() const noexcept { return !m_size; }
1621
1622 inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
1623 void reserve(qsizetype size)
1624 {
1625 // reserve(0) is used in squeeze()
1626 if (size && (this->capacity() >= size))
1627 return;
1628 if (isDetached())
1629 d->rehash(size);
1630 else
1631 d = Data::detached(d, size_t(size));
1632 }
1633 inline void squeeze() { reserve(size: 0); }
1634
1635 inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
1636 inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
1637 bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; }
1638
1639 void clear() noexcept(std::is_nothrow_destructible<Node>::value)
1640 {
1641 if (d && !d->ref.deref())
1642 delete d;
1643 d = nullptr;
1644 m_size = 0;
1645 }
1646
1647 qsizetype remove(const Key &key)
1648 {
1649 return removeImpl(key);
1650 }
1651private:
1652 template <typename K> qsizetype removeImpl(const K &key)
1653 {
1654 if (isEmpty()) // prevents detaching shared null
1655 return 0;
1656 auto it = d->findBucket(key);
1657 size_t bucket = it.toBucketIndex(d);
1658 detach();
1659 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1660
1661 if (it.isUnused())
1662 return 0;
1663 qsizetype n = Node::freeChain(it.node());
1664 m_size -= n;
1665 Q_ASSERT(m_size >= 0);
1666 d->erase(it);
1667 return n;
1668 }
1669
1670public:
1671 template <typename Predicate>
1672 qsizetype removeIf(Predicate pred)
1673 {
1674 return QtPrivate::associative_erase_if(*this, pred);
1675 }
1676
1677 T take(const Key &key)
1678 {
1679 return takeImpl(key);
1680 }
1681private:
1682 template <typename K> T takeImpl(const K &key)
1683 {
1684 if (isEmpty()) // prevents detaching shared null
1685 return T();
1686 auto it = d->findBucket(key);
1687 size_t bucket = it.toBucketIndex(d);
1688 detach();
1689 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1690
1691 if (it.isUnused())
1692 return T();
1693 Chain *e = it.node()->value;
1694 Q_ASSERT(e);
1695 T t = std::move(e->value);
1696 if (e->next) {
1697 it.node()->value = e->next;
1698 delete e;
1699 } else {
1700 // erase() deletes the values.
1701 d->erase(it);
1702 }
1703 --m_size;
1704 Q_ASSERT(m_size >= 0);
1705 return t;
1706 }
1707
1708public:
1709 bool contains(const Key &key) const noexcept
1710 {
1711 if (!d)
1712 return false;
1713 return d->findNode(key) != nullptr;
1714 }
1715
1716private:
1717 const Key *keyImpl(const T &value) const noexcept
1718 {
1719 if (d) {
1720 auto i = d->begin();
1721 while (i != d->end()) {
1722 Chain *e = i.node()->value;
1723 if (e->contains(value))
1724 return &i.node()->key;
1725 ++i;
1726 }
1727 }
1728
1729 return nullptr;
1730 }
1731public:
1732 Key key(const T &value) const noexcept
1733 {
1734 if (auto *k = keyImpl(value))
1735 return *k;
1736 else
1737 return Key();
1738 }
1739 Key key(const T &value, const Key &defaultKey) const noexcept
1740 {
1741 if (auto *k = keyImpl(value))
1742 return *k;
1743 else
1744 return defaultKey;
1745 }
1746
1747private:
1748 template <typename K>
1749 T *valueImpl(const K &key) const noexcept
1750 {
1751 if (d) {
1752 Node *n = d->findNode(key);
1753 if (n) {
1754 Q_ASSERT(n->value);
1755 return &n->value->value;
1756 }
1757 }
1758 return nullptr;
1759 }
1760public:
1761 T value(const Key &key) const noexcept
1762 {
1763 if (auto *v = valueImpl(key))
1764 return *v;
1765 else
1766 return T();
1767 }
1768 T value(const Key &key, const T &defaultValue) const noexcept
1769 {
1770 if (auto *v = valueImpl(key))
1771 return *v;
1772 else
1773 return defaultValue;
1774 }
1775
1776 T &operator[](const Key &key)
1777 {
1778 return operatorIndexImpl(key);
1779 }
1780private:
1781 template <typename K> T &operatorIndexImpl(const K &key)
1782 {
1783 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
1784 detach();
1785 auto result = d->findOrInsert(key);
1786 Q_ASSERT(!result.it.atEnd());
1787 if (!result.initialized) {
1788 Node::createInPlace(result.it.node(), Key(key), T());
1789 ++m_size;
1790 }
1791 return result.it.node()->value->value;
1792 }
1793
1794public:
1795 const T operator[](const Key &key) const noexcept
1796 {
1797 return value(key);
1798 }
1799
1800 QList<Key> uniqueKeys() const
1801 {
1802 QList<Key> res;
1803 if (d) {
1804 auto i = d->begin();
1805 while (i != d->end()) {
1806 res.append(i.node()->key);
1807 ++i;
1808 }
1809 }
1810 return res;
1811 }
1812
1813 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1814 QList<Key> keys(const T &value) const
1815 {
1816 QList<Key> res;
1817 const_iterator i = begin();
1818 while (i != end()) {
1819 if (i.value() == value)
1820 res.append(i.key());
1821 ++i;
1822 }
1823 return res;
1824 }
1825
1826 QList<T> values() const { return QList<T>(begin(), end()); }
1827 QList<T> values(const Key &key) const
1828 {
1829 return valuesImpl(key);
1830 }
1831private:
1832 template <typename K> QList<T> valuesImpl(const K &key) const
1833 {
1834 QList<T> values;
1835 if (d) {
1836 Node *n = d->findNode(key);
1837 if (n) {
1838 Chain *e = n->value;
1839 while (e) {
1840 values.append(e->value);
1841 e = e->next;
1842 }
1843 }
1844 }
1845 return values;
1846 }
1847
1848public:
1849 class const_iterator;
1850
1851 class iterator
1852 {
1853 using piter = typename QHashPrivate::iterator<Node>;
1854 friend class const_iterator;
1855 friend class QMultiHash<Key, T>;
1856 piter i;
1857 Chain **e = nullptr;
1858 explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1859 {
1860 if (!it.atEnd() && !e) {
1861 e = &it.node()->value;
1862 Q_ASSERT(e && *e);
1863 }
1864 }
1865
1866 public:
1867 typedef std::forward_iterator_tag iterator_category;
1868 typedef qptrdiff difference_type;
1869 typedef T value_type;
1870 typedef T *pointer;
1871 typedef T &reference;
1872
1873 constexpr iterator() noexcept = default;
1874
1875 inline const Key &key() const noexcept { return i.node()->key; }
1876 inline T &value() const noexcept { return (*e)->value; }
1877 inline T &operator*() const noexcept { return (*e)->value; }
1878 inline T *operator->() const noexcept { return &(*e)->value; }
1879 inline bool operator==(const iterator &o) const noexcept { return e == o.e; }
1880 inline bool operator!=(const iterator &o) const noexcept { return e != o.e; }
1881
1882 inline iterator &operator++() noexcept {
1883 Q_ASSERT(e && *e);
1884 e = &(*e)->next;
1885 Q_ASSERT(e);
1886 if (!*e) {
1887 ++i;
1888 e = i.atEnd() ? nullptr : &i.node()->value;
1889 }
1890 return *this;
1891 }
1892 inline iterator operator++(int) noexcept {
1893 iterator r = *this;
1894 ++(*this);
1895 return r;
1896 }
1897
1898 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1899 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1900 };
1901 friend class iterator;
1902
1903 class const_iterator
1904 {
1905 using piter = typename QHashPrivate::iterator<Node>;
1906 friend class iterator;
1907 friend class QMultiHash<Key, T>;
1908 piter i;
1909 Chain **e = nullptr;
1910 explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1911 {
1912 if (!it.atEnd() && !e) {
1913 e = &it.node()->value;
1914 Q_ASSERT(e && *e);
1915 }
1916 }
1917
1918 public:
1919 typedef std::forward_iterator_tag iterator_category;
1920 typedef qptrdiff difference_type;
1921 typedef T value_type;
1922 typedef const T *pointer;
1923 typedef const T &reference;
1924
1925 constexpr const_iterator() noexcept = default;
1926 inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { }
1927
1928 inline const Key &key() const noexcept { return i.node()->key; }
1929 inline T &value() const noexcept { return (*e)->value; }
1930 inline T &operator*() const noexcept { return (*e)->value; }
1931 inline T *operator->() const noexcept { return &(*e)->value; }
1932 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1933 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1934
1935 inline const_iterator &operator++() noexcept {
1936 Q_ASSERT(e && *e);
1937 e = &(*e)->next;
1938 Q_ASSERT(e);
1939 if (!*e) {
1940 ++i;
1941 e = i.atEnd() ? nullptr : &i.node()->value;
1942 }
1943 return *this;
1944 }
1945 inline const_iterator operator++(int) noexcept
1946 {
1947 const_iterator r = *this;
1948 ++(*this);
1949 return r;
1950 }
1951 };
1952 friend class const_iterator;
1953
1954 class key_iterator
1955 {
1956 const_iterator i;
1957
1958 public:
1959 typedef typename const_iterator::iterator_category iterator_category;
1960 typedef qptrdiff difference_type;
1961 typedef Key value_type;
1962 typedef const Key *pointer;
1963 typedef const Key &reference;
1964
1965 key_iterator() noexcept = default;
1966 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1967
1968 const Key &operator*() const noexcept { return i.key(); }
1969 const Key *operator->() const noexcept { return &i.key(); }
1970 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1971 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1972
1973 inline key_iterator &operator++() noexcept { ++i; return *this; }
1974 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1975 const_iterator base() const noexcept { return i; }
1976 };
1977
1978 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1979 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1980
1981 // STL style
1982 inline iterator begin() { detach(); return iterator(d->begin()); }
1983 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1984 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1985 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1986 inline iterator end() noexcept { return iterator(); }
1987 inline const_iterator end() const noexcept { return const_iterator(); }
1988 inline const_iterator cend() const noexcept { return const_iterator(); }
1989 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1990 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1991 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1992 inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); }
1993 inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); }
1994 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1995 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1996 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1997 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1998 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1999 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
2000 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
2001 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
2002
2003 iterator detach(const_iterator it)
2004 {
2005 auto i = it.i;
2006 Chain **e = it.e;
2007 if (d->ref.isShared()) {
2008 // need to store iterator position before detaching
2009 qsizetype n = 0;
2010 Chain *entry = i.node()->value;
2011 while (entry != *it.e) {
2012 ++n;
2013 entry = entry->next;
2014 }
2015 Q_ASSERT(entry);
2016 detach_helper();
2017
2018 i = d->detachedIterator(i);
2019 e = &i.node()->value;
2020 while (n) {
2021 e = &(*e)->next;
2022 --n;
2023 }
2024 Q_ASSERT(e && *e);
2025 }
2026 return iterator(i, e);
2027 }
2028
2029 iterator erase(const_iterator it)
2030 {
2031 Q_ASSERT(d);
2032 iterator iter = detach(it);
2033 iterator i = iter;
2034 Chain *e = *i.e;
2035 Chain *next = e->next;
2036 *i.e = next;
2037 delete e;
2038 if (!next) {
2039 if (i.e == &i.i.node()->value) {
2040 // last remaining entry, erase
2041 typename Data::Bucket bucket(i.i);
2042 d->erase(bucket);
2043 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
2044 i = iterator(++iter.i);
2045 else // 'i' currently has a nullptr chain. So, we must recreate it
2046 i = iterator(bucket.toIterator(d));
2047 } else {
2048 i = iterator(++iter.i);
2049 }
2050 }
2051 --m_size;
2052 Q_ASSERT(m_size >= 0);
2053 return i;
2054 }
2055
2056 // more Qt
2057 typedef iterator Iterator;
2058 typedef const_iterator ConstIterator;
2059 inline qsizetype count() const noexcept { return size(); }
2060
2061private:
2062 template <typename K> iterator findImpl(const K &key)
2063 {
2064 if (isEmpty())
2065 return end();
2066 auto it = d->findBucket(key);
2067 size_t bucket = it.toBucketIndex(d);
2068 detach();
2069 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2070
2071 if (it.isUnused())
2072 return end();
2073 return iterator(it.toIterator(d));
2074 }
2075 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
2076 {
2077 if (isEmpty())
2078 return end();
2079 auto it = d->findBucket(key);
2080 if (it.isUnused())
2081 return constEnd();
2082 return const_iterator(it.toIterator(d));
2083 }
2084public:
2085 iterator find(const Key &key)
2086 {
2087 return findImpl(key);
2088 }
2089 const_iterator constFind(const Key &key) const noexcept
2090 {
2091 return constFindImpl(key);
2092 }
2093 const_iterator find(const Key &key) const noexcept
2094 {
2095 return constFindImpl(key);
2096 }
2097
2098 iterator insert(const Key &key, const T &value)
2099 {
2100 return emplace(key, value);
2101 }
2102
2103 template <typename ...Args>
2104 iterator emplace(const Key &key, Args &&... args)
2105 {
2106 return emplace(Key(key), std::forward<Args>(args)...);
2107 }
2108
2109 template <typename ...Args>
2110 iterator emplace(Key &&key, Args &&... args)
2111 {
2112 if (isDetached()) {
2113 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2114 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
2115 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2116 }
2117 // else: we must detach
2118 const auto copy = *this; // keep 'args' alive across the detach/growth
2119 detach();
2120 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2121 }
2122
2123
2124 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
2125 static float max_load_factor() noexcept { return 0.5; }
2126 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
2127 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
2128
2129 [[nodiscard]]
2130 inline bool empty() const noexcept { return isEmpty(); }
2131
2132 inline iterator replace(const Key &key, const T &value)
2133 {
2134 return emplaceReplace(key, value);
2135 }
2136
2137 template <typename ...Args>
2138 iterator emplaceReplace(const Key &key, Args &&... args)
2139 {
2140 return emplaceReplace(Key(key), std::forward<Args>(args)...);
2141 }
2142
2143 template <typename ...Args>
2144 iterator emplaceReplace(Key &&key, Args &&... args)
2145 {
2146 if (isDetached()) {
2147 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2148 return emplaceReplace_helper(std::move(key), T(std::forward<Args>(args)...));
2149 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2150 }
2151 // else: we must detach
2152 const auto copy = *this; // keep 'args' alive across the detach/growth
2153 detach();
2154 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2155 }
2156
2157 inline QMultiHash &operator+=(const QMultiHash &other)
2158 { this->unite(other); return *this; }
2159 inline QMultiHash operator+(const QMultiHash &other) const
2160 { QMultiHash result = *this; result += other; return result; }
2161
2162 bool contains(const Key &key, const T &value) const noexcept
2163 {
2164 return containsImpl(key, value);
2165 }
2166private:
2167 template <typename K> bool containsImpl(const K &key, const T &value) const noexcept
2168 {
2169 if (isEmpty())
2170 return false;
2171 auto n = d->findNode(key);
2172 if (n == nullptr)
2173 return false;
2174 return n->value->contains(value);
2175 }
2176
2177public:
2178 qsizetype remove(const Key &key, const T &value)
2179 {
2180 return removeImpl(key, value);
2181 }
2182private:
2183 template <typename K> qsizetype removeImpl(const K &key, const T &value)
2184 {
2185 if (isEmpty()) // prevents detaching shared null
2186 return 0;
2187 auto it = d->findBucket(key);
2188 size_t bucket = it.toBucketIndex(d);
2189 detach();
2190 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2191
2192 if (it.isUnused())
2193 return 0;
2194 qsizetype n = 0;
2195 Chain **e = &it.node()->value;
2196 while (*e) {
2197 Chain *entry = *e;
2198 if (entry->value == value) {
2199 *e = entry->next;
2200 delete entry;
2201 ++n;
2202 } else {
2203 e = &entry->next;
2204 }
2205 }
2206 if (!it.node()->value)
2207 d->erase(it);
2208 m_size -= n;
2209 Q_ASSERT(m_size >= 0);
2210 return n;
2211 }
2212
2213public:
2214 qsizetype count(const Key &key) const noexcept
2215 {
2216 return countImpl(key);
2217 }
2218private:
2219 template <typename K> qsizetype countImpl(const K &key) const noexcept
2220 {
2221 if (!d)
2222 return 0;
2223 auto it = d->findBucket(key);
2224 if (it.isUnused())
2225 return 0;
2226 qsizetype n = 0;
2227 Chain *e = it.node()->value;
2228 while (e) {
2229 ++n;
2230 e = e->next;
2231 }
2232
2233 return n;
2234 }
2235
2236public:
2237 qsizetype count(const Key &key, const T &value) const noexcept
2238 {
2239 return countImpl(key, value);
2240 }
2241private:
2242 template <typename K> qsizetype countImpl(const K &key, const T &value) const noexcept
2243 {
2244 if (!d)
2245 return 0;
2246 auto it = d->findBucket(key);
2247 if (it.isUnused())
2248 return 0;
2249 qsizetype n = 0;
2250 Chain *e = it.node()->value;
2251 while (e) {
2252 if (e->value == value)
2253 ++n;
2254 e = e->next;
2255 }
2256
2257 return n;
2258 }
2259
2260 template <typename K> iterator findImpl(const K &key, const T &value)
2261 {
2262 if (isEmpty())
2263 return end();
2264 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key'/'value' alive across the detach
2265 detach();
2266 auto it = constFind(key, value);
2267 return iterator(it.i, it.e);
2268 }
2269 template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept
2270 {
2271 const_iterator i(constFind(key));
2272 const_iterator end(constEnd());
2273 while (i != end && i.key() == key) {
2274 if (i.value() == value)
2275 return i;
2276 ++i;
2277 }
2278 return end;
2279 }
2280
2281public:
2282 iterator find(const Key &key, const T &value)
2283 {
2284 return findImpl(key, value);
2285 }
2286
2287 const_iterator constFind(const Key &key, const T &value) const noexcept
2288 {
2289 return constFindImpl(key, value);
2290 }
2291 const_iterator find(const Key &key, const T &value) const noexcept
2292 {
2293 return constFind(key, value);
2294 }
2295
2296 QMultiHash &unite(const QMultiHash &other)
2297 {
2298 if (isEmpty()) {
2299 *this = other;
2300 } else if (other.isEmpty()) {
2301 ;
2302 } else {
2303 QMultiHash copy(other);
2304 detach();
2305 for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit)
2306 insert(key: cit.key(), value: *cit);
2307 }
2308 return *this;
2309 }
2310
2311 QMultiHash &unite(const QHash<Key, T> &other)
2312 {
2313 for (auto cit = other.cbegin(); cit != other.cend(); ++cit)
2314 insert(key: cit.key(), value: *cit);
2315 return *this;
2316 }
2317
2318 QMultiHash &unite(QHash<Key, T> &&other)
2319 {
2320 if (!other.isDetached()) {
2321 unite(other);
2322 return *this;
2323 }
2324 auto it = other.d->begin();
2325 for (const auto end = other.d->end(); it != end; ++it)
2326 emplace(std::move(it.node()->key), std::move(it.node()->takeValue()));
2327 other.clear();
2328 return *this;
2329 }
2330
2331 std::pair<iterator, iterator> equal_range(const Key &key)
2332 {
2333 return equal_range_impl(key);
2334 }
2335private:
2336 template <typename K> std::pair<iterator, iterator> equal_range_impl(const K &key)
2337 {
2338 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
2339 detach();
2340 auto pair = std::as_const(*this).equal_range(key);
2341 return {iterator(pair.first.i), iterator(pair.second.i)};
2342 }
2343
2344public:
2345 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
2346 {
2347 return equal_range_impl(key);
2348 }
2349private:
2350 template <typename K> std::pair<const_iterator, const_iterator> equal_range_impl(const K &key) const noexcept
2351 {
2352 if (!d)
2353 return {end(), end()};
2354
2355 auto bucket = d->findBucket(key);
2356 if (bucket.isUnused())
2357 return {end(), end()};
2358 auto it = bucket.toIterator(d);
2359 auto end = it;
2360 ++end;
2361 return {const_iterator(it), const_iterator(end)};
2362 }
2363
2364 void detach_helper()
2365 {
2366 if (!d) {
2367 d = new Data;
2368 return;
2369 }
2370 Data *dd = new Data(*d);
2371 if (!d->ref.deref())
2372 delete d;
2373 d = dd;
2374 }
2375
2376 template<typename... Args>
2377 iterator emplace_helper(Key &&key, Args &&...args)
2378 {
2379 auto result = d->findOrInsert(key);
2380 if (!result.initialized)
2381 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2382 else
2383 result.it.node()->insertMulti(std::forward<Args>(args)...);
2384 ++m_size;
2385 return iterator(result.it);
2386 }
2387
2388 template<typename... Args>
2389 iterator emplaceReplace_helper(Key &&key, Args &&...args)
2390 {
2391 auto result = d->findOrInsert(key);
2392 if (!result.initialized) {
2393 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2394 ++m_size;
2395 } else {
2396 result.it.node()->emplaceValue(std::forward<Args>(args)...);
2397 }
2398 return iterator(result.it);
2399 }
2400
2401 template <typename K>
2402 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
2403
2404 template <typename K>
2405 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
2406
2407public:
2408 template <typename K, if_heterogeneously_searchable<K> = true>
2409 qsizetype remove(const K &key)
2410 {
2411 return removeImpl(key);
2412 }
2413 template <typename K, if_heterogeneously_searchable<K> = true>
2414 T take(const K &key)
2415 {
2416 return takeImpl(key);
2417 }
2418 template <typename K, if_heterogeneously_searchable<K> = true>
2419 bool contains(const K &key) const noexcept
2420 {
2421 if (!d)
2422 return false;
2423 return d->findNode(key) != nullptr;
2424 }
2425 template <typename K, if_heterogeneously_searchable<K> = true>
2426 T value(const K &key) const noexcept
2427 {
2428 if (auto *v = valueImpl(key))
2429 return *v;
2430 else
2431 return T();
2432 }
2433 template <typename K, if_heterogeneously_searchable<K> = true>
2434 T value(const K &key, const T &defaultValue) const noexcept
2435 {
2436 if (auto *v = valueImpl(key))
2437 return *v;
2438 else
2439 return defaultValue;
2440 }
2441 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
2442 T &operator[](const K &key)
2443 {
2444 return operatorIndexImpl(key);
2445 }
2446 template <typename K, if_heterogeneously_searchable<K> = true>
2447 const T operator[](const K &key) const noexcept
2448 {
2449 return value(key);
2450 }
2451 template <typename K, if_heterogeneously_searchable<K> = true>
2452 QList<T> values(const K &key)
2453 {
2454 return valuesImpl(key);
2455 }
2456 template <typename K, if_heterogeneously_searchable<K> = true>
2457 iterator find(const K &key)
2458 {
2459 return findImpl(key);
2460 }
2461 template <typename K, if_heterogeneously_searchable<K> = true>
2462 const_iterator constFind(const K &key) const noexcept
2463 {
2464 return constFindImpl(key);
2465 }
2466 template <typename K, if_heterogeneously_searchable<K> = true>
2467 const_iterator find(const K &key) const noexcept
2468 {
2469 return constFindImpl(key);
2470 }
2471 template <typename K, if_heterogeneously_searchable<K> = true>
2472 bool contains(const K &key, const T &value) const noexcept
2473 {
2474 return containsImpl(key, value);
2475 }
2476 template <typename K, if_heterogeneously_searchable<K> = true>
2477 qsizetype remove(const K &key, const T &value)
2478 {
2479 return removeImpl(key, value);
2480 }
2481 template <typename K, if_heterogeneously_searchable<K> = true>
2482 qsizetype count(const K &key) const noexcept
2483 {
2484 return countImpl(key);
2485 }
2486 template <typename K, if_heterogeneously_searchable<K> = true>
2487 qsizetype count(const K &key, const T &value) const noexcept
2488 {
2489 return countImpl(key, value);
2490 }
2491 template <typename K, if_heterogeneously_searchable<K> = true>
2492 iterator find(const K &key, const T &value)
2493 {
2494 return findImpl(key, value);
2495 }
2496 template <typename K, if_heterogeneously_searchable<K> = true>
2497 const_iterator constFind(const K &key, const T &value) const noexcept
2498 {
2499 return constFindImpl(key, value);
2500 }
2501 template <typename K, if_heterogeneously_searchable<K> = true>
2502 const_iterator find(const K &key, const T &value) const noexcept
2503 {
2504 return constFind(key, value);
2505 }
2506 template <typename K, if_heterogeneously_searchable<K> = true>
2507 std::pair<iterator, iterator>
2508 equal_range(const K &key)
2509 {
2510 return equal_range_impl(key);
2511 }
2512 template <typename K, if_heterogeneously_searchable<K> = true>
2513 std::pair<const_iterator, const_iterator>
2514 equal_range(const K &key) const noexcept
2515 {
2516 return equal_range_impl(key);
2517 }
2518};
2519
2520Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2521Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2522Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2523Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2524
2525template <class Key, class T>
2526size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
2527 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2528{
2529 size_t hash = 0;
2530 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2531 QtPrivate::QHashCombine combine;
2532 size_t h = combine(seed, it.key());
2533 // use + to keep the result independent of the ordering of the keys
2534 hash += combine(h, it.value());
2535 }
2536 return hash;
2537}
2538
2539template <class Key, class T>
2540inline size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
2541 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2542{
2543 size_t hash = 0;
2544 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2545 QtPrivate::QHashCombine combine;
2546 size_t h = combine(seed, it.key());
2547 // use + to keep the result independent of the ordering of the keys
2548 hash += combine(h, it.value());
2549 }
2550 return hash;
2551}
2552
2553template <typename Key, typename T, typename Predicate>
2554qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
2555{
2556 return QtPrivate::associative_erase_if(hash, pred);
2557}
2558
2559template <typename Key, typename T, typename Predicate>
2560qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
2561{
2562 return QtPrivate::associative_erase_if(hash, pred);
2563}
2564
2565QT_END_NAMESPACE
2566
2567#endif // QHASH_H
2568