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