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