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 void reallocationHelper(const Data &other, size_t nSpans, bool resized)
562 {
563 for (size_t s = 0; s < nSpans; ++s) {
564 const Span &span = other.spans[s];
565 for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
566 if (!span.hasNode(index))
567 continue;
568 const Node &n = span.at(index);
569 auto it = resized ? findBucket(n.key) : Bucket { spans + s, index };
570 Q_ASSERT(it.isUnused());
571 Node *newNode = it.insert();
572 new (newNode) Node(n);
573 }
574 }
575 }
576
577 Data(const Data &other) : size(other.size), numBuckets(other.numBuckets), seed(other.seed)
578 {
579 auto r = allocateSpans(numBuckets);
580 spans = r.spans;
581 reallocationHelper(other, nSpans: r.nSpans, resized: false);
582 }
583 Data(const Data &other, size_t reserved) : size(other.size), seed(other.seed)
584 {
585 numBuckets = GrowthPolicy::bucketsForCapacity(requestedCapacity: qMax(a: size, b: reserved));
586 spans = allocateSpans(numBuckets).spans;
587 size_t otherNSpans = other.numBuckets >> SpanConstants::SpanShift;
588 reallocationHelper(other, nSpans: otherNSpans, resized: numBuckets != other.numBuckets);
589 }
590
591 static Data *detached(Data *d)
592 {
593 if (!d)
594 return new Data;
595 Data *dd = new Data(*d);
596 if (!d->ref.deref())
597 delete d;
598 return dd;
599 }
600 static Data *detached(Data *d, size_t size)
601 {
602 if (!d)
603 return new Data(size);
604 Data *dd = new Data(*d, size);
605 if (!d->ref.deref())
606 delete d;
607 return dd;
608 }
609
610 void clear()
611 {
612 delete[] spans;
613 spans = nullptr;
614 size = 0;
615 numBuckets = 0;
616 }
617
618 iterator detachedIterator(iterator other) const noexcept
619 {
620 return iterator{this, other.bucket};
621 }
622
623 iterator begin() const noexcept
624 {
625 iterator it{ this, 0 };
626 if (it.isUnused())
627 ++it;
628 return it;
629 }
630
631 constexpr iterator end() const noexcept
632 {
633 return iterator();
634 }
635
636 void rehash(size_t sizeHint = 0)
637 {
638 if (sizeHint == 0)
639 sizeHint = size;
640 size_t newBucketCount = GrowthPolicy::bucketsForCapacity(requestedCapacity: sizeHint);
641
642 Span *oldSpans = spans;
643 size_t oldBucketCount = numBuckets;
644 spans = allocateSpans(numBuckets: newBucketCount).spans;
645 numBuckets = newBucketCount;
646 size_t oldNSpans = oldBucketCount >> SpanConstants::SpanShift;
647
648 for (size_t s = 0; s < oldNSpans; ++s) {
649 Span &span = oldSpans[s];
650 for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
651 if (!span.hasNode(index))
652 continue;
653 Node &n = span.at(index);
654 auto it = findBucket(n.key);
655 Q_ASSERT(it.isUnused());
656 Node *newNode = it.insert();
657 new (newNode) Node(std::move(n));
658 }
659 span.freeData();
660 }
661 delete[] oldSpans;
662 }
663
664 size_t nextBucket(size_t bucket) const noexcept
665 {
666 ++bucket;
667 if (bucket == numBuckets)
668 bucket = 0;
669 return bucket;
670 }
671
672 float loadFactor() const noexcept
673 {
674 return float(size)/numBuckets;
675 }
676 bool shouldGrow() const noexcept
677 {
678 return size >= (numBuckets >> 1);
679 }
680
681 template <typename K> Bucket findBucket(const K &key) const noexcept
682 {
683 static_assert(std::is_same_v<std::remove_cv_t<Key>, K> ||
684 QHashHeterogeneousSearch<std::remove_cv_t<Key>, K>::value);
685 Q_ASSERT(numBuckets > 0);
686 size_t hash = QHashPrivate::calculateHash(key, seed);
687 Bucket bucket(this, GrowthPolicy::bucketForHash(nBuckets: numBuckets, hash));
688 // loop over the buckets until we find the entry we search for
689 // or an empty slot, in which case we know the entry doesn't exist
690 while (true) {
691 size_t offset = bucket.offset();
692 if (offset == SpanConstants::UnusedEntry) {
693 return bucket;
694 } else {
695 Node &n = bucket.nodeAtOffset(offset);
696 if (qHashEquals(n.key, key))
697 return bucket;
698 }
699 bucket.advanceWrapped(this);
700 }
701 }
702
703 template <typename K> Node *findNode(const K &key) const noexcept
704 {
705 auto bucket = findBucket(key);
706 if (bucket.isUnused())
707 return nullptr;
708 return bucket.node();
709 }
710
711 struct InsertionResult
712 {
713 iterator it;
714 bool initialized;
715 };
716
717 template <typename K> InsertionResult findOrInsert(const K &key) noexcept
718 {
719 Bucket it(static_cast<Span *>(nullptr), 0);
720 if (numBuckets > 0) {
721 it = findBucket(key);
722 if (!it.isUnused())
723 return { it.toIterator(this), true };
724 }
725 if (shouldGrow()) {
726 rehash(sizeHint: size + 1);
727 it = findBucket(key); // need to get a new iterator after rehashing
728 }
729 Q_ASSERT(it.span != nullptr);
730 Q_ASSERT(it.isUnused());
731 it.insert();
732 ++size;
733 return { it.toIterator(this), false };
734 }
735
736 void erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value)
737 {
738 Q_ASSERT(bucket.span->hasNode(bucket.index));
739 bucket.span->erase(bucket.index);
740 --size;
741
742 // re-insert the following entries to avoid holes
743 Bucket next = bucket;
744 while (true) {
745 next.advanceWrapped(this);
746 size_t offset = next.offset();
747 if (offset == SpanConstants::UnusedEntry)
748 return;
749 size_t hash = QHashPrivate::calculateHash(next.nodeAtOffset(offset).key, seed);
750 Bucket newBucket(this, GrowthPolicy::bucketForHash(nBuckets: numBuckets, hash));
751 while (true) {
752 if (newBucket == next) {
753 // nothing to do, item is at the right plae
754 break;
755 } else if (newBucket == bucket) {
756 // move into the hole we created earlier
757 if (next.span == bucket.span) {
758 bucket.span->moveLocal(next.index, bucket.index);
759 } else {
760 // move between spans, more expensive
761 bucket.span->moveFromSpan(*next.span, next.index, bucket.index);
762 }
763 bucket = next;
764 break;
765 }
766 newBucket.advanceWrapped(this);
767 }
768 }
769 }
770
771 ~Data()
772 {
773 delete [] spans;
774 }
775};
776
777template <typename Node>
778struct iterator {
779 using Span = QHashPrivate::Span<Node>;
780
781 const Data<Node> *d = nullptr;
782 size_t bucket = 0;
783
784 size_t span() const noexcept { return bucket >> SpanConstants::SpanShift; }
785 size_t index() const noexcept { return bucket & SpanConstants::LocalBucketMask; }
786 inline bool isUnused() const noexcept { return !d->spans[span()].hasNode(index()); }
787
788 inline Node *node() const noexcept
789 {
790 Q_ASSERT(!isUnused());
791 return &d->spans[span()].at(index());
792 }
793 bool atEnd() const noexcept { return !d; }
794
795 iterator operator++() noexcept
796 {
797 while (true) {
798 ++bucket;
799 if (bucket == d->numBuckets) {
800 d = nullptr;
801 bucket = 0;
802 break;
803 }
804 if (!isUnused())
805 break;
806 }
807 return *this;
808 }
809 bool operator==(iterator other) const noexcept
810 { return d == other.d && bucket == other.bucket; }
811 bool operator!=(iterator other) const noexcept
812 { return !(*this == other); }
813};
814
815
816
817} // namespace QHashPrivate
818
819template <typename Key, typename T>
820class QHash
821{
822 using Node = QHashPrivate::Node<Key, T>;
823 using Data = QHashPrivate::Data<Node>;
824 friend class QSet<Key>;
825 friend class QMultiHash<Key, T>;
826 friend tst_QHash;
827
828 Data *d = nullptr;
829
830public:
831 using key_type = Key;
832 using mapped_type = T;
833 using value_type = T;
834 using size_type = qsizetype;
835 using difference_type = qsizetype;
836 using reference = T &;
837 using const_reference = const T &;
838
839 inline QHash() noexcept = default;
840 inline QHash(std::initializer_list<std::pair<Key,T> > list)
841 : d(new Data(list.size()))
842 {
843 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
844 insert(it->first, it->second);
845 }
846 QHash(const QHash &other) noexcept
847 : d(other.d)
848 {
849 if (d)
850 d->ref.ref();
851 }
852 ~QHash()
853 {
854 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
855 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
856
857 if (d && !d->ref.deref())
858 delete d;
859 }
860
861 QHash &operator=(const QHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
862 {
863 if (d != other.d) {
864 Data *o = other.d;
865 if (o)
866 o->ref.ref();
867 if (d && !d->ref.deref())
868 delete d;
869 d = o;
870 }
871 return *this;
872 }
873
874 QHash(QHash &&other) noexcept
875 : d(std::exchange(other.d, nullptr))
876 {
877 }
878 QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QHash)
879#ifdef Q_QDOC
880 template <typename InputIterator>
881 QHash(InputIterator f, InputIterator l);
882#else
883 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
884 QHash(InputIterator f, InputIterator l)
885 : QHash()
886 {
887 QtPrivate::reserveIfForwardIterator(this, f, l);
888 for (; f != l; ++f)
889 insert(f.key(), f.value());
890 }
891
892 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
893 QHash(InputIterator f, InputIterator l)
894 : QHash()
895 {
896 QtPrivate::reserveIfForwardIterator(this, f, l);
897 for (; f != l; ++f) {
898 auto &&e = *f;
899 using V = decltype(e);
900 insert(std::forward<V>(e).first, std::forward<V>(e).second);
901 }
902 }
903#endif
904 void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); }
905
906#ifndef Q_QDOC
907 template <typename AKey = Key, typename AT = T>
908 QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator==(const QHash &other) const noexcept
909 {
910 if (d == other.d)
911 return true;
912 if (size() != other.size())
913 return false;
914
915 for (const_iterator it = other.begin(); it != other.end(); ++it) {
916 const_iterator i = find(it.key());
917 if (i == end() || !i.i.node()->valuesEqual(it.i.node()))
918 return false;
919 }
920 // all values must be the same as size is the same
921 return true;
922 }
923 template <typename AKey = Key, typename AT = T>
924 QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator!=(const QHash &other) const noexcept
925 { return !(*this == other); }
926#else
927 bool operator==(const QHash &other) const;
928 bool operator!=(const QHash &other) const;
929#endif // Q_QDOC
930
931 inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
932 inline bool isEmpty() const noexcept { return !d || d->size == 0; }
933
934 inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
935 void reserve(qsizetype size)
936 {
937 // reserve(0) is used in squeeze()
938 if (size && (this->capacity() >= size))
939 return;
940 if (isDetached())
941 d->rehash(size);
942 else
943 d = Data::detached(d, size_t(size));
944 }
945 inline void squeeze()
946 {
947 if (capacity())
948 reserve(size: 0);
949 }
950
951 inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
952 inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
953 bool isSharedWith(const QHash &other) const noexcept { return d == other.d; }
954
955 void clear() noexcept(std::is_nothrow_destructible<Node>::value)
956 {
957 if (d && !d->ref.deref())
958 delete d;
959 d = nullptr;
960 }
961
962 bool remove(const Key &key)
963 {
964 return removeImpl(key);
965 }
966private:
967 template <typename K> bool removeImpl(const K &key)
968 {
969 if (isEmpty()) // prevents detaching shared null
970 return false;
971 auto it = d->findBucket(key);
972 size_t bucket = it.toBucketIndex(d);
973 detach();
974 it = typename Data::Bucket(d, bucket); // reattach in case of detach
975
976 if (it.isUnused())
977 return false;
978 d->erase(it);
979 return true;
980 }
981
982public:
983 template <typename Predicate>
984 qsizetype removeIf(Predicate pred)
985 {
986 return QtPrivate::associative_erase_if(*this, pred);
987 }
988
989 T take(const Key &key)
990 {
991 return takeImpl(key);
992 }
993private:
994 template <typename K> T takeImpl(const K &key)
995 {
996 if (isEmpty()) // prevents detaching shared null
997 return T();
998 auto it = d->findBucket(key);
999 size_t bucket = it.toBucketIndex(d);
1000 detach();
1001 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1002
1003 if (it.isUnused())
1004 return T();
1005 T value = it.node()->takeValue();
1006 d->erase(it);
1007 return value;
1008 }
1009
1010public:
1011 bool contains(const Key &key) const noexcept
1012 {
1013 if (!d)
1014 return false;
1015 return d->findNode(key) != nullptr;
1016 }
1017 qsizetype count(const Key &key) const noexcept
1018 {
1019 return contains(key) ? 1 : 0;
1020 }
1021
1022private:
1023 const Key *keyImpl(const T &value) const noexcept
1024 {
1025 if (d) {
1026 const_iterator i = begin();
1027 while (i != end()) {
1028 if (i.value() == value)
1029 return &i.key();
1030 ++i;
1031 }
1032 }
1033
1034 return nullptr;
1035 }
1036
1037public:
1038 Key key(const T &value) const noexcept
1039 {
1040 if (auto *k = keyImpl(value))
1041 return *k;
1042 else
1043 return Key();
1044 }
1045 Key key(const T &value, const Key &defaultKey) const noexcept
1046 {
1047 if (auto *k = keyImpl(value))
1048 return *k;
1049 else
1050 return defaultKey;
1051 }
1052
1053private:
1054 template <typename K>
1055 T *valueImpl(const K &key) const noexcept
1056 {
1057 if (d) {
1058 Node *n = d->findNode(key);
1059 if (n)
1060 return &n->value;
1061 }
1062 return nullptr;
1063 }
1064public:
1065 T value(const Key &key) const noexcept
1066 {
1067 if (T *v = valueImpl(key))
1068 return *v;
1069 else
1070 return T();
1071 }
1072
1073 T value(const Key &key, const T &defaultValue) const noexcept
1074 {
1075 if (T *v = valueImpl(key))
1076 return *v;
1077 else
1078 return defaultValue;
1079 }
1080
1081 T &operator[](const Key &key)
1082 {
1083 return operatorIndexImpl(key);
1084 }
1085private:
1086 template <typename K> T &operatorIndexImpl(const K &key)
1087 {
1088 const auto copy = isDetached() ? QHash() : *this; // keep 'key' alive across the detach
1089 detach();
1090 auto result = d->findOrInsert(key);
1091 Q_ASSERT(!result.it.atEnd());
1092 if (!result.initialized)
1093 Node::createInPlace(result.it.node(), Key(key), T());
1094 return result.it.node()->value;
1095 }
1096
1097public:
1098 const T operator[](const Key &key) const noexcept
1099 {
1100 return value(key);
1101 }
1102
1103 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1104 QList<Key> keys(const T &value) const
1105 {
1106 QList<Key> res;
1107 const_iterator i = begin();
1108 while (i != end()) {
1109 if (i.value() == value)
1110 res.append(i.key());
1111 ++i;
1112 }
1113 return res;
1114 }
1115 QList<T> values() const { return QList<T>(begin(), end()); }
1116
1117 class const_iterator;
1118
1119 class iterator
1120 {
1121 using piter = typename QHashPrivate::iterator<Node>;
1122 friend class const_iterator;
1123 friend class QHash<Key, T>;
1124 friend class QSet<Key>;
1125 piter i;
1126 explicit inline iterator(piter it) noexcept : i(it) { }
1127
1128 public:
1129 typedef std::forward_iterator_tag iterator_category;
1130 typedef qptrdiff difference_type;
1131 typedef T value_type;
1132 typedef T *pointer;
1133 typedef T &reference;
1134
1135 constexpr iterator() noexcept = default;
1136
1137 inline const Key &key() const noexcept { return i.node()->key; }
1138 inline T &value() const noexcept { return i.node()->value; }
1139 inline T &operator*() const noexcept { return i.node()->value; }
1140 inline T *operator->() const noexcept { return &i.node()->value; }
1141 inline bool operator==(const iterator &o) const noexcept { return i == o.i; }
1142 inline bool operator!=(const iterator &o) const noexcept { return i != o.i; }
1143
1144 inline iterator &operator++() noexcept
1145 {
1146 ++i;
1147 return *this;
1148 }
1149 inline iterator operator++(int) noexcept
1150 {
1151 iterator r = *this;
1152 ++i;
1153 return r;
1154 }
1155
1156 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1157 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1158 };
1159 friend class iterator;
1160
1161 class const_iterator
1162 {
1163 using piter = typename QHashPrivate::iterator<Node>;
1164 friend class iterator;
1165 friend class QHash<Key, T>;
1166 friend class QSet<Key>;
1167 piter i;
1168 explicit inline const_iterator(piter it) : i(it) { }
1169
1170 public:
1171 typedef std::forward_iterator_tag iterator_category;
1172 typedef qptrdiff difference_type;
1173 typedef T value_type;
1174 typedef const T *pointer;
1175 typedef const T &reference;
1176
1177 constexpr const_iterator() noexcept = default;
1178 inline const_iterator(const iterator &o) noexcept : i(o.i) { }
1179
1180 inline const Key &key() const noexcept { return i.node()->key; }
1181 inline const T &value() const noexcept { return i.node()->value; }
1182 inline const T &operator*() const noexcept { return i.node()->value; }
1183 inline const T *operator->() const noexcept { return &i.node()->value; }
1184 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; }
1185 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; }
1186
1187 inline const_iterator &operator++() noexcept
1188 {
1189 ++i;
1190 return *this;
1191 }
1192 inline const_iterator operator++(int) noexcept
1193 {
1194 const_iterator r = *this;
1195 ++i;
1196 return r;
1197 }
1198 };
1199 friend class const_iterator;
1200
1201 class key_iterator
1202 {
1203 const_iterator i;
1204
1205 public:
1206 typedef typename const_iterator::iterator_category iterator_category;
1207 typedef qptrdiff difference_type;
1208 typedef Key value_type;
1209 typedef const Key *pointer;
1210 typedef const Key &reference;
1211
1212 key_iterator() noexcept = default;
1213 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1214
1215 const Key &operator*() const noexcept { return i.key(); }
1216 const Key *operator->() const noexcept { return &i.key(); }
1217 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1218 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1219
1220 inline key_iterator &operator++() noexcept { ++i; return *this; }
1221 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1222 const_iterator base() const noexcept { return i; }
1223 };
1224
1225 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1226 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1227
1228 // STL style
1229 inline iterator begin() { detach(); return iterator(d->begin()); }
1230 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1231 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1232 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1233 inline iterator end() noexcept { return iterator(); }
1234 inline const_iterator end() const noexcept { return const_iterator(); }
1235 inline const_iterator cend() const noexcept { return const_iterator(); }
1236 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1237 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1238 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1239 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
1240 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
1241 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1242 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1243 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1244 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1245 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1246 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
1247 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1248 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1249
1250 iterator erase(const_iterator it)
1251 {
1252 Q_ASSERT(it != constEnd());
1253 detach();
1254 // ensure a valid iterator across the detach:
1255 iterator i = iterator{d->detachedIterator(it.i)};
1256 typename Data::Bucket bucket(i.i);
1257
1258 d->erase(bucket);
1259 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
1260 ++i;
1261 return i;
1262 }
1263
1264 std::pair<iterator, iterator> equal_range(const Key &key)
1265 {
1266 return equal_range_impl(*this, key);
1267 }
1268 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
1269 {
1270 return equal_range_impl(*this, key);
1271 }
1272private:
1273 template <typename Hash, typename K> static auto equal_range_impl(Hash &self, const K &key)
1274 {
1275 auto first = self.find(key);
1276 auto second = first;
1277 if (second != decltype(first){})
1278 ++second;
1279 return std::make_pair(first, second);
1280 }
1281
1282 template <typename K> iterator findImpl(const K &key)
1283 {
1284 if (isEmpty()) // prevents detaching shared null
1285 return end();
1286 auto it = d->findBucket(key);
1287 size_t bucket = it.toBucketIndex(d);
1288 detach();
1289 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1290 if (it.isUnused())
1291 return end();
1292 return iterator(it.toIterator(d));
1293 }
1294 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
1295 {
1296 if (isEmpty())
1297 return end();
1298 auto it = d->findBucket(key);
1299 if (it.isUnused())
1300 return end();
1301 return const_iterator({d, it.toBucketIndex(d)});
1302 }
1303
1304public:
1305 typedef iterator Iterator;
1306 typedef const_iterator ConstIterator;
1307 inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
1308 iterator find(const Key &key)
1309 {
1310 return findImpl(key);
1311 }
1312 const_iterator find(const Key &key) const noexcept
1313 {
1314 return constFindImpl(key);
1315 }
1316 const_iterator constFind(const Key &key) const noexcept
1317 {
1318 return find(key);
1319 }
1320 iterator insert(const Key &key, const T &value)
1321 {
1322 return emplace(key, value);
1323 }
1324
1325 void insert(const QHash &hash)
1326 {
1327 if (d == hash.d || !hash.d)
1328 return;
1329 if (!d) {
1330 *this = hash;
1331 return;
1332 }
1333
1334 detach();
1335
1336 for (auto it = hash.begin(); it != hash.end(); ++it)
1337 emplace(it.key(), it.value());
1338 }
1339
1340 template <typename ...Args>
1341 iterator emplace(const Key &key, Args &&... args)
1342 {
1343 Key copy = key; // Needs to be explicit for MSVC 2019
1344 return emplace(std::move(copy), std::forward<Args>(args)...);
1345 }
1346
1347 template <typename ...Args>
1348 iterator emplace(Key &&key, Args &&... args)
1349 {
1350 if (isDetached()) {
1351 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
1352 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
1353 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1354 }
1355 // else: we must detach
1356 const auto copy = *this; // keep 'args' alive across the detach/growth
1357 detach();
1358 return emplace_helper(std::move(key), std::forward<Args>(args)...);
1359 }
1360
1361 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
1362 static float max_load_factor() noexcept { return 0.5; }
1363 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
1364 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
1365
1366 inline bool empty() const noexcept { return isEmpty(); }
1367
1368private:
1369 template <typename ...Args>
1370 iterator emplace_helper(Key &&key, Args &&... args)
1371 {
1372 auto result = d->findOrInsert(key);
1373 if (!result.initialized)
1374 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
1375 else
1376 result.it.node()->emplaceValue(std::forward<Args>(args)...);
1377 return iterator(result.it);
1378 }
1379
1380 template <typename K>
1381 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
1382
1383 template <typename K>
1384 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
1385
1386public:
1387 template <typename K, if_heterogeneously_searchable<K> = true>
1388 bool remove(const K &key)
1389 {
1390 return removeImpl(key);
1391 }
1392 template <typename K, if_heterogeneously_searchable<K> = true>
1393 T take(const K &key)
1394 {
1395 return takeImpl(key);
1396 }
1397 template <typename K, if_heterogeneously_searchable<K> = true>
1398 bool contains(const K &key) const
1399 {
1400 return d ? d->findNode(key) != nullptr : false;
1401 }
1402 template <typename K, if_heterogeneously_searchable<K> = true>
1403 qsizetype count(const K &key) const
1404 {
1405 return contains(key) ? 1 : 0;
1406 }
1407 template <typename K, if_heterogeneously_searchable<K> = true>
1408 T value(const K &key) const noexcept
1409 {
1410 if (auto *v = valueImpl(key))
1411 return *v;
1412 else
1413 return T();
1414 }
1415 template <typename K, if_heterogeneously_searchable<K> = true>
1416 T value(const K &key, const T &defaultValue) const noexcept
1417 {
1418 if (auto *v = valueImpl(key))
1419 return *v;
1420 else
1421 return defaultValue;
1422 }
1423 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
1424 T &operator[](const K &key)
1425 {
1426 return operatorIndexImpl(key);
1427 }
1428 template <typename K, if_heterogeneously_searchable<K> = true>
1429 const T operator[](const K &key) const noexcept
1430 {
1431 return value(key);
1432 }
1433 template <typename K, if_heterogeneously_searchable<K> = true>
1434 std::pair<iterator, iterator>
1435 equal_range(const K &key)
1436 {
1437 return equal_range_impl(*this, key);
1438 }
1439 template <typename K, if_heterogeneously_searchable<K> = true>
1440 std::pair<const_iterator, const_iterator>
1441 equal_range(const K &key) const noexcept
1442 {
1443 return equal_range_impl(*this, key);
1444 }
1445 template <typename K, if_heterogeneously_searchable<K> = true>
1446 iterator find(const K &key)
1447 {
1448 return findImpl(key);
1449 }
1450 template <typename K, if_heterogeneously_searchable<K> = true>
1451 const_iterator find(const K &key) const noexcept
1452 {
1453 return constFindImpl(key);
1454 }
1455 template <typename K, if_heterogeneously_searchable<K> = true>
1456 const_iterator constFind(const K &key) const noexcept
1457 {
1458 return find(key);
1459 }
1460};
1461
1462
1463template <typename Key, typename T>
1464class QMultiHash
1465{
1466 using Node = QHashPrivate::MultiNode<Key, T>;
1467 using Data = QHashPrivate::Data<Node>;
1468 using Chain = QHashPrivate::MultiNodeChain<T>;
1469
1470 Data *d = nullptr;
1471 qsizetype m_size = 0;
1472
1473public:
1474 using key_type = Key;
1475 using mapped_type = T;
1476 using value_type = T;
1477 using size_type = qsizetype;
1478 using difference_type = qsizetype;
1479 using reference = T &;
1480 using const_reference = const T &;
1481
1482 QMultiHash() noexcept = default;
1483 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1484 : d(new Data(list.size()))
1485 {
1486 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1487 insert(key: it->first, value: it->second);
1488 }
1489#ifdef Q_QDOC
1490 template <typename InputIterator>
1491 QMultiHash(InputIterator f, InputIterator l);
1492#else
1493 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1494 QMultiHash(InputIterator f, InputIterator l)
1495 {
1496 QtPrivate::reserveIfForwardIterator(this, f, l);
1497 for (; f != l; ++f)
1498 insert(key: f.key(), value: f.value());
1499 }
1500
1501 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1502 QMultiHash(InputIterator f, InputIterator l)
1503 {
1504 QtPrivate::reserveIfForwardIterator(this, f, l);
1505 for (; f != l; ++f) {
1506 auto &&e = *f;
1507 using V = decltype(e);
1508 insert(key: std::forward<V>(e).first, value: std::forward<V>(e).second);
1509 }
1510 }
1511#endif
1512 QMultiHash(const QMultiHash &other) noexcept
1513 : d(other.d), m_size(other.m_size)
1514 {
1515 if (d)
1516 d->ref.ref();
1517 }
1518 ~QMultiHash()
1519 {
1520 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
1521 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
1522
1523 if (d && !d->ref.deref())
1524 delete d;
1525 }
1526
1527 QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value)
1528 {
1529 if (d != other.d) {
1530 Data *o = other.d;
1531 if (o)
1532 o->ref.ref();
1533 if (d && !d->ref.deref())
1534 delete d;
1535 d = o;
1536 m_size = other.m_size;
1537 }
1538 return *this;
1539 }
1540 QMultiHash(QMultiHash &&other) noexcept
1541 : d(std::exchange(other.d, nullptr)),
1542 m_size(std::exchange(other.m_size, 0))
1543 {
1544 }
1545 QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value)
1546 {
1547 QMultiHash moved(std::move(other));
1548 swap(other&: moved);
1549 return *this;
1550 }
1551
1552 explicit QMultiHash(const QHash<Key, T> &other)
1553 : QMultiHash(other.begin(), other.end())
1554 {}
1555
1556 explicit QMultiHash(QHash<Key, T> &&other)
1557 {
1558 unite(std::move(other));
1559 }
1560
1561 void swap(QMultiHash &other) noexcept
1562 {
1563 qt_ptr_swap(d, other.d);
1564 std::swap(m_size, other.m_size);
1565 }
1566
1567#ifndef Q_QDOC
1568 template <typename AKey = Key, typename AT = T>
1569 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator==(const QMultiHash &other) const noexcept
1570 {
1571 if (d == other.d)
1572 return true;
1573 if (m_size != other.m_size)
1574 return false;
1575 if (m_size == 0)
1576 return true;
1577 // equal size, and both non-zero size => d pointers allocated for both
1578 Q_ASSERT(d);
1579 Q_ASSERT(other.d);
1580 if (d->size != other.d->size)
1581 return false;
1582 for (auto it = other.d->begin(); it != other.d->end(); ++it) {
1583 auto *n = d->findNode(it.node()->key);
1584 if (!n)
1585 return false;
1586 Chain *e = it.node()->value;
1587 while (e) {
1588 Chain *oe = n->value;
1589 while (oe) {
1590 if (oe->value == e->value)
1591 break;
1592 oe = oe->next;
1593 }
1594 if (!oe)
1595 return false;
1596 e = e->next;
1597 }
1598 }
1599 // all values must be the same as size is the same
1600 return true;
1601 }
1602 template <typename AKey = Key, typename AT = T>
1603 QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator!=(const QMultiHash &other) const noexcept
1604 { return !(*this == other); }
1605#else
1606 bool operator==(const QMultiHash &other) const;
1607 bool operator!=(const QMultiHash &other) const;
1608#endif // Q_QDOC
1609
1610 inline qsizetype size() const noexcept { return m_size; }
1611
1612 inline bool isEmpty() const noexcept { return !m_size; }
1613
1614 inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; }
1615 void reserve(qsizetype size)
1616 {
1617 // reserve(0) is used in squeeze()
1618 if (size && (this->capacity() >= size))
1619 return;
1620 if (isDetached())
1621 d->rehash(size);
1622 else
1623 d = Data::detached(d, size_t(size));
1624 }
1625 inline void squeeze() { reserve(size: 0); }
1626
1627 inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); }
1628 inline bool isDetached() const noexcept { return d && !d->ref.isShared(); }
1629 bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; }
1630
1631 void clear() noexcept(std::is_nothrow_destructible<Node>::value)
1632 {
1633 if (d && !d->ref.deref())
1634 delete d;
1635 d = nullptr;
1636 m_size = 0;
1637 }
1638
1639 qsizetype remove(const Key &key)
1640 {
1641 return removeImpl(key);
1642 }
1643private:
1644 template <typename K> qsizetype removeImpl(const K &key)
1645 {
1646 if (isEmpty()) // prevents detaching shared null
1647 return 0;
1648 auto it = d->findBucket(key);
1649 size_t bucket = it.toBucketIndex(d);
1650 detach();
1651 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1652
1653 if (it.isUnused())
1654 return 0;
1655 qsizetype n = Node::freeChain(it.node());
1656 m_size -= n;
1657 Q_ASSERT(m_size >= 0);
1658 d->erase(it);
1659 return n;
1660 }
1661
1662public:
1663 template <typename Predicate>
1664 qsizetype removeIf(Predicate pred)
1665 {
1666 return QtPrivate::associative_erase_if(*this, pred);
1667 }
1668
1669 T take(const Key &key)
1670 {
1671 return takeImpl(key);
1672 }
1673private:
1674 template <typename K> T takeImpl(const K &key)
1675 {
1676 if (isEmpty()) // prevents detaching shared null
1677 return T();
1678 auto it = d->findBucket(key);
1679 size_t bucket = it.toBucketIndex(d);
1680 detach();
1681 it = typename Data::Bucket(d, bucket); // reattach in case of detach
1682
1683 if (it.isUnused())
1684 return T();
1685 Chain *e = it.node()->value;
1686 Q_ASSERT(e);
1687 T t = std::move(e->value);
1688 if (e->next) {
1689 it.node()->value = e->next;
1690 delete e;
1691 } else {
1692 // erase() deletes the values.
1693 d->erase(it);
1694 }
1695 --m_size;
1696 Q_ASSERT(m_size >= 0);
1697 return t;
1698 }
1699
1700public:
1701 bool contains(const Key &key) const noexcept
1702 {
1703 if (!d)
1704 return false;
1705 return d->findNode(key) != nullptr;
1706 }
1707
1708private:
1709 const Key *keyImpl(const T &value) const noexcept
1710 {
1711 if (d) {
1712 auto i = d->begin();
1713 while (i != d->end()) {
1714 Chain *e = i.node()->value;
1715 if (e->contains(value))
1716 return &i.node()->key;
1717 ++i;
1718 }
1719 }
1720
1721 return nullptr;
1722 }
1723public:
1724 Key key(const T &value) const noexcept
1725 {
1726 if (auto *k = keyImpl(value))
1727 return *k;
1728 else
1729 return Key();
1730 }
1731 Key key(const T &value, const Key &defaultKey) const noexcept
1732 {
1733 if (auto *k = keyImpl(value))
1734 return *k;
1735 else
1736 return defaultKey;
1737 }
1738
1739private:
1740 template <typename K>
1741 T *valueImpl(const K &key) const noexcept
1742 {
1743 if (d) {
1744 Node *n = d->findNode(key);
1745 if (n) {
1746 Q_ASSERT(n->value);
1747 return &n->value->value;
1748 }
1749 }
1750 return nullptr;
1751 }
1752public:
1753 T value(const Key &key) const noexcept
1754 {
1755 if (auto *v = valueImpl(key))
1756 return *v;
1757 else
1758 return T();
1759 }
1760 T value(const Key &key, const T &defaultValue) const noexcept
1761 {
1762 if (auto *v = valueImpl(key))
1763 return *v;
1764 else
1765 return defaultValue;
1766 }
1767
1768 T &operator[](const Key &key)
1769 {
1770 return operatorIndexImpl(key);
1771 }
1772private:
1773 template <typename K> T &operatorIndexImpl(const K &key)
1774 {
1775 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
1776 detach();
1777 auto result = d->findOrInsert(key);
1778 Q_ASSERT(!result.it.atEnd());
1779 if (!result.initialized) {
1780 Node::createInPlace(result.it.node(), Key(key), T());
1781 ++m_size;
1782 }
1783 return result.it.node()->value->value;
1784 }
1785
1786public:
1787 const T operator[](const Key &key) const noexcept
1788 {
1789 return value(key);
1790 }
1791
1792 QList<Key> uniqueKeys() const
1793 {
1794 QList<Key> res;
1795 if (d) {
1796 auto i = d->begin();
1797 while (i != d->end()) {
1798 res.append(i.node()->key);
1799 ++i;
1800 }
1801 }
1802 return res;
1803 }
1804
1805 QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); }
1806 QList<Key> keys(const T &value) const
1807 {
1808 QList<Key> res;
1809 const_iterator i = begin();
1810 while (i != end()) {
1811 if (i.value() == value)
1812 res.append(i.key());
1813 ++i;
1814 }
1815 return res;
1816 }
1817
1818 QList<T> values() const { return QList<T>(begin(), end()); }
1819 QList<T> values(const Key &key) const
1820 {
1821 return valuesImpl(key);
1822 }
1823private:
1824 template <typename K> QList<T> valuesImpl(const K &key) const
1825 {
1826 QList<T> values;
1827 if (d) {
1828 Node *n = d->findNode(key);
1829 if (n) {
1830 Chain *e = n->value;
1831 while (e) {
1832 values.append(e->value);
1833 e = e->next;
1834 }
1835 }
1836 }
1837 return values;
1838 }
1839
1840public:
1841 class const_iterator;
1842
1843 class iterator
1844 {
1845 using piter = typename QHashPrivate::iterator<Node>;
1846 friend class const_iterator;
1847 friend class QMultiHash<Key, T>;
1848 piter i;
1849 Chain **e = nullptr;
1850 explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1851 {
1852 if (!it.atEnd() && !e) {
1853 e = &it.node()->value;
1854 Q_ASSERT(e && *e);
1855 }
1856 }
1857
1858 public:
1859 typedef std::forward_iterator_tag iterator_category;
1860 typedef qptrdiff difference_type;
1861 typedef T value_type;
1862 typedef T *pointer;
1863 typedef T &reference;
1864
1865 constexpr iterator() noexcept = default;
1866
1867 inline const Key &key() const noexcept { return i.node()->key; }
1868 inline T &value() const noexcept { return (*e)->value; }
1869 inline T &operator*() const noexcept { return (*e)->value; }
1870 inline T *operator->() const noexcept { return &(*e)->value; }
1871 inline bool operator==(const iterator &o) const noexcept { return e == o.e; }
1872 inline bool operator!=(const iterator &o) const noexcept { return e != o.e; }
1873
1874 inline iterator &operator++() noexcept {
1875 Q_ASSERT(e && *e);
1876 e = &(*e)->next;
1877 Q_ASSERT(e);
1878 if (!*e) {
1879 ++i;
1880 e = i.atEnd() ? nullptr : &i.node()->value;
1881 }
1882 return *this;
1883 }
1884 inline iterator operator++(int) noexcept {
1885 iterator r = *this;
1886 ++(*this);
1887 return r;
1888 }
1889
1890 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1891 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1892 };
1893 friend class iterator;
1894
1895 class const_iterator
1896 {
1897 using piter = typename QHashPrivate::iterator<Node>;
1898 friend class iterator;
1899 friend class QMultiHash<Key, T>;
1900 piter i;
1901 Chain **e = nullptr;
1902 explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry)
1903 {
1904 if (!it.atEnd() && !e) {
1905 e = &it.node()->value;
1906 Q_ASSERT(e && *e);
1907 }
1908 }
1909
1910 public:
1911 typedef std::forward_iterator_tag iterator_category;
1912 typedef qptrdiff difference_type;
1913 typedef T value_type;
1914 typedef const T *pointer;
1915 typedef const T &reference;
1916
1917 constexpr const_iterator() noexcept = default;
1918 inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { }
1919
1920 inline const Key &key() const noexcept { return i.node()->key; }
1921 inline T &value() const noexcept { return (*e)->value; }
1922 inline T &operator*() const noexcept { return (*e)->value; }
1923 inline T *operator->() const noexcept { return &(*e)->value; }
1924 inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; }
1925 inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; }
1926
1927 inline const_iterator &operator++() noexcept {
1928 Q_ASSERT(e && *e);
1929 e = &(*e)->next;
1930 Q_ASSERT(e);
1931 if (!*e) {
1932 ++i;
1933 e = i.atEnd() ? nullptr : &i.node()->value;
1934 }
1935 return *this;
1936 }
1937 inline const_iterator operator++(int) noexcept
1938 {
1939 const_iterator r = *this;
1940 ++(*this);
1941 return r;
1942 }
1943 };
1944 friend class const_iterator;
1945
1946 class key_iterator
1947 {
1948 const_iterator i;
1949
1950 public:
1951 typedef typename const_iterator::iterator_category iterator_category;
1952 typedef qptrdiff difference_type;
1953 typedef Key value_type;
1954 typedef const Key *pointer;
1955 typedef const Key &reference;
1956
1957 key_iterator() noexcept = default;
1958 explicit key_iterator(const_iterator o) noexcept : i(o) { }
1959
1960 const Key &operator*() const noexcept { return i.key(); }
1961 const Key *operator->() const noexcept { return &i.key(); }
1962 bool operator==(key_iterator o) const noexcept { return i == o.i; }
1963 bool operator!=(key_iterator o) const noexcept { return i != o.i; }
1964
1965 inline key_iterator &operator++() noexcept { ++i; return *this; }
1966 inline key_iterator operator++(int) noexcept { return key_iterator(i++);}
1967 const_iterator base() const noexcept { return i; }
1968 };
1969
1970 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1971 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1972
1973 // STL style
1974 inline iterator begin() { detach(); return iterator(d->begin()); }
1975 inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1976 inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1977 inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); }
1978 inline iterator end() noexcept { return iterator(); }
1979 inline const_iterator end() const noexcept { return const_iterator(); }
1980 inline const_iterator cend() const noexcept { return const_iterator(); }
1981 inline const_iterator constEnd() const noexcept { return const_iterator(); }
1982 inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); }
1983 inline key_iterator keyEnd() const noexcept { return key_iterator(end()); }
1984 inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); }
1985 inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); }
1986 inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1987 inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); }
1988 inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1989 inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); }
1990 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1991 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
1992 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1993 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1994
1995 iterator detach(const_iterator it)
1996 {
1997 auto i = it.i;
1998 Chain **e = it.e;
1999 if (d->ref.isShared()) {
2000 // need to store iterator position before detaching
2001 qsizetype n = 0;
2002 Chain *entry = i.node()->value;
2003 while (entry != *it.e) {
2004 ++n;
2005 entry = entry->next;
2006 }
2007 Q_ASSERT(entry);
2008 detach_helper();
2009
2010 i = d->detachedIterator(i);
2011 e = &i.node()->value;
2012 while (n) {
2013 e = &(*e)->next;
2014 --n;
2015 }
2016 Q_ASSERT(e && *e);
2017 }
2018 return iterator(i, e);
2019 }
2020
2021 iterator erase(const_iterator it)
2022 {
2023 Q_ASSERT(d);
2024 iterator iter = detach(it);
2025 iterator i = iter;
2026 Chain *e = *i.e;
2027 Chain *next = e->next;
2028 *i.e = next;
2029 delete e;
2030 if (!next) {
2031 if (i.e == &i.i.node()->value) {
2032 // last remaining entry, erase
2033 typename Data::Bucket bucket(i.i);
2034 d->erase(bucket);
2035 if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
2036 i = iterator(++iter.i);
2037 else // 'i' currently has a nullptr chain. So, we must recreate it
2038 i = iterator(bucket.toIterator(d));
2039 } else {
2040 i = iterator(++iter.i);
2041 }
2042 }
2043 --m_size;
2044 Q_ASSERT(m_size >= 0);
2045 return i;
2046 }
2047
2048 // more Qt
2049 typedef iterator Iterator;
2050 typedef const_iterator ConstIterator;
2051 inline qsizetype count() const noexcept { return size(); }
2052
2053private:
2054 template <typename K> iterator findImpl(const K &key)
2055 {
2056 if (isEmpty())
2057 return end();
2058 auto it = d->findBucket(key);
2059 size_t bucket = it.toBucketIndex(d);
2060 detach();
2061 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2062
2063 if (it.isUnused())
2064 return end();
2065 return iterator(it.toIterator(d));
2066 }
2067 template <typename K> const_iterator constFindImpl(const K &key) const noexcept
2068 {
2069 if (isEmpty())
2070 return end();
2071 auto it = d->findBucket(key);
2072 if (it.isUnused())
2073 return constEnd();
2074 return const_iterator(it.toIterator(d));
2075 }
2076public:
2077 iterator find(const Key &key)
2078 {
2079 return findImpl(key);
2080 }
2081 const_iterator constFind(const Key &key) const noexcept
2082 {
2083 return constFindImpl(key);
2084 }
2085 const_iterator find(const Key &key) const noexcept
2086 {
2087 return constFindImpl(key);
2088 }
2089
2090 iterator insert(const Key &key, const T &value)
2091 {
2092 return emplace(key, value);
2093 }
2094
2095 template <typename ...Args>
2096 iterator emplace(const Key &key, Args &&... args)
2097 {
2098 return emplace(Key(key), std::forward<Args>(args)...);
2099 }
2100
2101 template <typename ...Args>
2102 iterator emplace(Key &&key, Args &&... args)
2103 {
2104 if (isDetached()) {
2105 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2106 return emplace_helper(std::move(key), T(std::forward<Args>(args)...));
2107 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2108 }
2109 // else: we must detach
2110 const auto copy = *this; // keep 'args' alive across the detach/growth
2111 detach();
2112 return emplace_helper(std::move(key), std::forward<Args>(args)...);
2113 }
2114
2115
2116 float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
2117 static float max_load_factor() noexcept { return 0.5; }
2118 size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
2119 static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
2120
2121 inline bool empty() const noexcept { return isEmpty(); }
2122
2123 inline iterator replace(const Key &key, const T &value)
2124 {
2125 return emplaceReplace(key, value);
2126 }
2127
2128 template <typename ...Args>
2129 iterator emplaceReplace(const Key &key, Args &&... args)
2130 {
2131 return emplaceReplace(Key(key), std::forward<Args>(args)...);
2132 }
2133
2134 template <typename ...Args>
2135 iterator emplaceReplace(Key &&key, Args &&... args)
2136 {
2137 if (isDetached()) {
2138 if (d->shouldGrow()) // Construct the value now so that no dangling references are used
2139 return emplaceReplace_helper(std::move(key), T(std::forward<Args>(args)...));
2140 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2141 }
2142 // else: we must detach
2143 const auto copy = *this; // keep 'args' alive across the detach/growth
2144 detach();
2145 return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...);
2146 }
2147
2148 inline QMultiHash &operator+=(const QMultiHash &other)
2149 { this->unite(other); return *this; }
2150 inline QMultiHash operator+(const QMultiHash &other) const
2151 { QMultiHash result = *this; result += other; return result; }
2152
2153 bool contains(const Key &key, const T &value) const noexcept
2154 {
2155 return containsImpl(key, value);
2156 }
2157private:
2158 template <typename K> bool containsImpl(const K &key, const T &value) const noexcept
2159 {
2160 if (isEmpty())
2161 return false;
2162 auto n = d->findNode(key);
2163 if (n == nullptr)
2164 return false;
2165 return n->value->contains(value);
2166 }
2167
2168public:
2169 qsizetype remove(const Key &key, const T &value)
2170 {
2171 return removeImpl(key, value);
2172 }
2173private:
2174 template <typename K> qsizetype removeImpl(const K &key, const T &value)
2175 {
2176 if (isEmpty()) // prevents detaching shared null
2177 return 0;
2178 auto it = d->findBucket(key);
2179 size_t bucket = it.toBucketIndex(d);
2180 detach();
2181 it = typename Data::Bucket(d, bucket); // reattach in case of detach
2182
2183 if (it.isUnused())
2184 return 0;
2185 qsizetype n = 0;
2186 Chain **e = &it.node()->value;
2187 while (*e) {
2188 Chain *entry = *e;
2189 if (entry->value == value) {
2190 *e = entry->next;
2191 delete entry;
2192 ++n;
2193 } else {
2194 e = &entry->next;
2195 }
2196 }
2197 if (!it.node()->value)
2198 d->erase(it);
2199 m_size -= n;
2200 Q_ASSERT(m_size >= 0);
2201 return n;
2202 }
2203
2204public:
2205 qsizetype count(const Key &key) const noexcept
2206 {
2207 return countImpl(key);
2208 }
2209private:
2210 template <typename K> qsizetype countImpl(const K &key) const noexcept
2211 {
2212 if (!d)
2213 return 0;
2214 auto it = d->findBucket(key);
2215 if (it.isUnused())
2216 return 0;
2217 qsizetype n = 0;
2218 Chain *e = it.node()->value;
2219 while (e) {
2220 ++n;
2221 e = e->next;
2222 }
2223
2224 return n;
2225 }
2226
2227public:
2228 qsizetype count(const Key &key, const T &value) const noexcept
2229 {
2230 return countImpl(key, value);
2231 }
2232private:
2233 template <typename K> qsizetype countImpl(const K &key, const T &value) const noexcept
2234 {
2235 if (!d)
2236 return 0;
2237 auto it = d->findBucket(key);
2238 if (it.isUnused())
2239 return 0;
2240 qsizetype n = 0;
2241 Chain *e = it.node()->value;
2242 while (e) {
2243 if (e->value == value)
2244 ++n;
2245 e = e->next;
2246 }
2247
2248 return n;
2249 }
2250
2251 template <typename K> iterator findImpl(const K &key, const T &value)
2252 {
2253 if (isEmpty())
2254 return end();
2255 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key'/'value' alive across the detach
2256 detach();
2257 auto it = constFind(key, value);
2258 return iterator(it.i, it.e);
2259 }
2260 template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept
2261 {
2262 const_iterator i(constFind(key));
2263 const_iterator end(constEnd());
2264 while (i != end && i.key() == key) {
2265 if (i.value() == value)
2266 return i;
2267 ++i;
2268 }
2269 return end;
2270 }
2271
2272public:
2273 iterator find(const Key &key, const T &value)
2274 {
2275 return findImpl(key, value);
2276 }
2277
2278 const_iterator constFind(const Key &key, const T &value) const noexcept
2279 {
2280 return constFindImpl(key, value);
2281 }
2282 const_iterator find(const Key &key, const T &value) const noexcept
2283 {
2284 return constFind(key, value);
2285 }
2286
2287 QMultiHash &unite(const QMultiHash &other)
2288 {
2289 if (isEmpty()) {
2290 *this = other;
2291 } else if (other.isEmpty()) {
2292 ;
2293 } else {
2294 QMultiHash copy(other);
2295 detach();
2296 for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit)
2297 insert(key: cit.key(), value: *cit);
2298 }
2299 return *this;
2300 }
2301
2302 QMultiHash &unite(const QHash<Key, T> &other)
2303 {
2304 for (auto cit = other.cbegin(); cit != other.cend(); ++cit)
2305 insert(key: cit.key(), value: *cit);
2306 return *this;
2307 }
2308
2309 QMultiHash &unite(QHash<Key, T> &&other)
2310 {
2311 if (!other.isDetached()) {
2312 unite(other);
2313 return *this;
2314 }
2315 auto it = other.d->begin();
2316 for (const auto end = other.d->end(); it != end; ++it)
2317 emplace(std::move(it.node()->key), std::move(it.node()->takeValue()));
2318 other.clear();
2319 return *this;
2320 }
2321
2322 std::pair<iterator, iterator> equal_range(const Key &key)
2323 {
2324 return equal_range_impl(key);
2325 }
2326private:
2327 template <typename K> std::pair<iterator, iterator> equal_range_impl(const K &key)
2328 {
2329 const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach
2330 detach();
2331 auto pair = std::as_const(*this).equal_range(key);
2332 return {iterator(pair.first.i), iterator(pair.second.i)};
2333 }
2334
2335public:
2336 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
2337 {
2338 return equal_range_impl(key);
2339 }
2340private:
2341 template <typename K> std::pair<const_iterator, const_iterator> equal_range_impl(const K &key) const noexcept
2342 {
2343 if (!d)
2344 return {end(), end()};
2345
2346 auto bucket = d->findBucket(key);
2347 if (bucket.isUnused())
2348 return {end(), end()};
2349 auto it = bucket.toIterator(d);
2350 auto end = it;
2351 ++end;
2352 return {const_iterator(it), const_iterator(end)};
2353 }
2354
2355 void detach_helper()
2356 {
2357 if (!d) {
2358 d = new Data;
2359 return;
2360 }
2361 Data *dd = new Data(*d);
2362 if (!d->ref.deref())
2363 delete d;
2364 d = dd;
2365 }
2366
2367 template<typename... Args>
2368 iterator emplace_helper(Key &&key, Args &&...args)
2369 {
2370 auto result = d->findOrInsert(key);
2371 if (!result.initialized)
2372 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2373 else
2374 result.it.node()->insertMulti(std::forward<Args>(args)...);
2375 ++m_size;
2376 return iterator(result.it);
2377 }
2378
2379 template<typename... Args>
2380 iterator emplaceReplace_helper(Key &&key, Args &&...args)
2381 {
2382 auto result = d->findOrInsert(key);
2383 if (!result.initialized) {
2384 Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
2385 ++m_size;
2386 } else {
2387 result.it.node()->emplaceValue(std::forward<Args>(args)...);
2388 }
2389 return iterator(result.it);
2390 }
2391
2392 template <typename K>
2393 using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
2394
2395 template <typename K>
2396 using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
2397
2398public:
2399 template <typename K, if_heterogeneously_searchable<K> = true>
2400 qsizetype remove(const K &key)
2401 {
2402 return removeImpl(key);
2403 }
2404 template <typename K, if_heterogeneously_searchable<K> = true>
2405 T take(const K &key)
2406 {
2407 return takeImpl(key);
2408 }
2409 template <typename K, if_heterogeneously_searchable<K> = true>
2410 bool contains(const K &key) const noexcept
2411 {
2412 if (!d)
2413 return false;
2414 return d->findNode(key) != nullptr;
2415 }
2416 template <typename K, if_heterogeneously_searchable<K> = true>
2417 T value(const K &key) const noexcept
2418 {
2419 if (auto *v = valueImpl(key))
2420 return *v;
2421 else
2422 return T();
2423 }
2424 template <typename K, if_heterogeneously_searchable<K> = true>
2425 T value(const K &key, const T &defaultValue) const noexcept
2426 {
2427 if (auto *v = valueImpl(key))
2428 return *v;
2429 else
2430 return defaultValue;
2431 }
2432 template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
2433 T &operator[](const K &key)
2434 {
2435 return operatorIndexImpl(key);
2436 }
2437 template <typename K, if_heterogeneously_searchable<K> = true>
2438 const T operator[](const K &key) const noexcept
2439 {
2440 return value(key);
2441 }
2442 template <typename K, if_heterogeneously_searchable<K> = true>
2443 QList<T> values(const K &key)
2444 {
2445 return valuesImpl(key);
2446 }
2447 template <typename K, if_heterogeneously_searchable<K> = true>
2448 iterator find(const K &key)
2449 {
2450 return findImpl(key);
2451 }
2452 template <typename K, if_heterogeneously_searchable<K> = true>
2453 const_iterator constFind(const K &key) const noexcept
2454 {
2455 return constFindImpl(key);
2456 }
2457 template <typename K, if_heterogeneously_searchable<K> = true>
2458 const_iterator find(const K &key) const noexcept
2459 {
2460 return constFindImpl(key);
2461 }
2462 template <typename K, if_heterogeneously_searchable<K> = true>
2463 bool contains(const K &key, const T &value) const noexcept
2464 {
2465 return containsImpl(key, value);
2466 }
2467 template <typename K, if_heterogeneously_searchable<K> = true>
2468 qsizetype remove(const K &key, const T &value)
2469 {
2470 return removeImpl(key, value);
2471 }
2472 template <typename K, if_heterogeneously_searchable<K> = true>
2473 qsizetype count(const K &key) const noexcept
2474 {
2475 return countImpl(key);
2476 }
2477 template <typename K, if_heterogeneously_searchable<K> = true>
2478 qsizetype count(const K &key, const T &value) const noexcept
2479 {
2480 return countImpl(key, value);
2481 }
2482 template <typename K, if_heterogeneously_searchable<K> = true>
2483 iterator find(const K &key, const T &value)
2484 {
2485 return findImpl(key, value);
2486 }
2487 template <typename K, if_heterogeneously_searchable<K> = true>
2488 const_iterator constFind(const K &key, const T &value) const noexcept
2489 {
2490 return constFindImpl(key, value);
2491 }
2492 template <typename K, if_heterogeneously_searchable<K> = true>
2493 const_iterator find(const K &key, const T &value) const noexcept
2494 {
2495 return constFind(key, value);
2496 }
2497 template <typename K, if_heterogeneously_searchable<K> = true>
2498 std::pair<iterator, iterator>
2499 equal_range(const K &key)
2500 {
2501 return equal_range_impl(key);
2502 }
2503 template <typename K, if_heterogeneously_searchable<K> = true>
2504 std::pair<const_iterator, const_iterator>
2505 equal_range(const K &key) const noexcept
2506 {
2507 return equal_range_impl(key);
2508 }
2509};
2510
2511Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2512Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(Hash)
2513Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2514Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash)
2515
2516template <class Key, class T>
2517size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
2518 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2519{
2520 size_t hash = 0;
2521 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2522 QtPrivate::QHashCombine combine;
2523 size_t h = combine(seed, it.key());
2524 // use + to keep the result independent of the ordering of the keys
2525 hash += combine(h, it.value());
2526 }
2527 return hash;
2528}
2529
2530template <class Key, class T>
2531inline size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
2532 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
2533{
2534 size_t hash = 0;
2535 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
2536 QtPrivate::QHashCombine combine;
2537 size_t h = combine(seed, it.key());
2538 // use + to keep the result independent of the ordering of the keys
2539 hash += combine(h, it.value());
2540 }
2541 return hash;
2542}
2543
2544template <typename Key, typename T, typename Predicate>
2545qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
2546{
2547 return QtPrivate::associative_erase_if(hash, pred);
2548}
2549
2550template <typename Key, typename T, typename Predicate>
2551qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
2552{
2553 return QtPrivate::associative_erase_if(hash, pred);
2554}
2555
2556QT_END_NAMESPACE
2557
2558#endif // QHASH_H
2559

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