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