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