1	// Copyright (C) 2020 The Qt Company Ltd.
2	// Copyright (C) 2021 Intel Corporation.
3	// Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>.
4	// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
5
6	// for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h.
7	// put it at the beginning so some indirect inclusion doesn't break it
8	#ifndef _CRT_RAND_S
9	#define _CRT_RAND_S
10	#endif
11	#include <stdlib.h>
12	#include <stdint.h>
13
14	#include "qhash.h"
15
16	#ifdef truncate
17	#undef truncate
18	#endif
19
20	#include <qbitarray.h>
21	#include <qstring.h>
22	#include <qglobal.h>
23	#include <qbytearray.h>
24	#include <qdatetime.h>
25	#include <qbasicatomic.h>
26	#include <qendian.h>
27	#include <private/qrandom_p.h>
28	#include <private/qsimd_p.h>
29
30	#ifndef QT_BOOTSTRAPPED
31	#include <qcoreapplication.h>
32	#include <qrandom.h>
33	#include <private/qlocale_tools_p.h>
34	#endif // QT_BOOTSTRAPPED
35
36	// Implementation of SipHash algorithm
37	#include "../../3rdparty/siphash/siphash.cpp"
38
39	#include <array>
40	#include <limits.h>
41
42	#if defined(QT_NO_DEBUG) && !defined(NDEBUG)
43	# define NDEBUG
44	#endif
45	#include <assert.h>
46
47	#ifdef Q_CC_GNU
48	# define Q_DECL_HOT_FUNCTION __attribute__((hot))
49	#else
50	# define Q_DECL_HOT_FUNCTION
51	#endif
52
53	QT_BEGIN_NAMESPACE
54
55	void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept; // qstring.cpp
56
57	// We assume that pointers and size_t have the same size. If that assumption should fail
58	// on a platform the code selecting the different methods below needs to be fixed.
59	static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size.");
60
61	namespace {
62	struct HashSeedStorage
63	{
64	static constexpr int SeedCount = 2;
65	QBasicAtomicInteger<quintptr> seeds[SeedCount] = { Q_BASIC_ATOMIC_INITIALIZER(0), Q_BASIC_ATOMIC_INITIALIZER(0) };
66
67	#if !QT_SUPPORTS_INIT_PRIORITY || defined(QT_BOOTSTRAPPED)
68	constexpr HashSeedStorage() = default;
69	#else
70	HashSeedStorage() { initialize(which: 0); }
71	#endif
72
73	enum State {
74	OverriddenByEnvironment = -1,
75	JustInitialized,
76	AlreadyInitialized
77	};
78	struct StateResult {
79	quintptr requestedSeed;
80	State state;
81	};
82
83	StateResult state(int which = -1);
84	Q_DECL_HOT_FUNCTION QHashSeed currentSeed(int which)
85	{
86	return { state(which).requestedSeed };
87	}
88
89	void resetSeed()
90	{
91	#ifndef QT_BOOTSTRAPPED
92	if (state().state < AlreadyInitialized)
93	return;
94
95	// update the public seed
96	QRandomGenerator *generator = QRandomGenerator::system();
97	seeds[0].storeRelaxed(newValue: sizeof(size_t) > sizeof(quint32)
98	? generator->generate64() : generator->generate());
99	#endif
100	}
101
102	void clearSeed()
103	{
104	state();
105	seeds[0].storeRelaxed(newValue: 0); // always write (smaller code)
106	}
107
108	private:
109	Q_DECL_COLD_FUNCTION Q_NEVER_INLINE StateResult initialize(int which) noexcept;
110	};
111
112	[[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept
113	{
114	StateResult result = { .requestedSeed: 0, .state: OverriddenByEnvironment };
115	#ifdef QT_BOOTSTRAPPED
116	Q_UNUSED(which);
117	Q_UNREACHABLE_RETURN(result);
118	#else
119	// can't use qEnvironmentVariableIntValue (reentrancy)
120	const char *seedstr = getenv(name: "QT_HASH_SEED");
121	if (seedstr) {
122	auto r = qstrntoll(nptr: seedstr, size: strlen(s: seedstr), base: 10);
123	if (r.used > 0 && size_t(r.used) == strlen(s: seedstr)) {
124	if (r.result) {
125	// can't use qWarning here (reentrancy)
126	fprintf(stderr, format: "QT_HASH_SEED: forced seed value is not 0; ignored.\n");
127	}
128
129	// we don't have to store to the seed, since it's pre-initialized by
130	// the compiler to zero
131	return result;
132	}
133	}
134
135	// update the full seed
136	auto x = qt_initial_random_value();
137	for (int i = 0; i < SeedCount; ++i) {
138	seeds[i].storeRelaxed(newValue: x.data[i]);
139	if (which == i)
140	result.requestedSeed = x.data[i];
141	}
142	result.state = JustInitialized;
143	return result;
144	#endif
145	}
146
147	inline HashSeedStorage::StateResult HashSeedStorage::state(int which)
148	{
149	constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555));
150	StateResult result = { .requestedSeed: BadSeed, .state: AlreadyInitialized };
151
152	#if defined(QT_BOOTSTRAPPED)
153	result = { 0, OverriddenByEnvironment };
154	#elif !QT_SUPPORTS_INIT_PRIORITY
155	// dynamic initialization
156	static auto once = [&]() {
157	result = initialize(which);
158	return true;
159	}();
160	Q_UNUSED(once);
161	#endif
162
163	if (result.state == AlreadyInitialized && which >= 0)
164	return { .requestedSeed: seeds[which].loadRelaxed(), .state: AlreadyInitialized };
165	return result;
166	}
167	} // unnamed namespace
168
169	/*
170	The QHash seed itself.
171	*/
172	#ifdef Q_DECL_INIT_PRIORITY
173	Q_DECL_INIT_PRIORITY(05)
174	#else
175	Q_CONSTINIT
176	#endif
177	static HashSeedStorage qt_qhash_seed;
178
179	/*
180	* Hashing for memory segments is based on the public domain MurmurHash2 by
181	* Austin Appleby. See http://murmurhash.googlepages.com/
182	*/
183	#if QT_POINTER_SIZE == 4
184	Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
185	static inline uint murmurhash(const void *key, uint len, uint seed) noexcept
186	{
187	// 'm' and 'r' are mixing constants generated offline.
188	// They're not really 'magic', they just happen to work well.
189
190	const unsigned int m = 0x5bd1e995;
191	const int r = 24;
192
193	// Initialize the hash to a 'random' value
194
195	unsigned int h = seed ^ len;
196
197	// Mix 4 bytes at a time into the hash
198
199	const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
200	const unsigned char *end = data + (len & ~3);
201
202	while (data != end) {
203	size_t k;
204	memcpy(&k, data, sizeof(uint));
205
206	k *= m;
207	k ^= k >> r;
208	k *= m;
209
210	h *= m;
211	h ^= k;
212
213	data += 4;
214	}
215
216	// Handle the last few bytes of the input array
217	len &= 3;
218	if (len) {
219	unsigned int k = 0;
220	end += len;
221
222	while (data != end) {
223	k <<= 8;
224	k |= *data;
225	++data;
226	}
227	h ^= k;
228	h *= m;
229	}
230
231	// Do a few final mixes of the hash to ensure the last few
232	// bytes are well-incorporated.
233
234	h ^= h >> 13;
235	h *= m;
236	h ^= h >> 15;
237
238	return h;
239	}
240
241	#else
242	Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
243	static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept
244	{
245	const uint64_t m = 0xc6a4a7935bd1e995ULL;
246	const int r = 47;
247
248	uint64_t h = seed ^ (len * m);
249
250	const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
251	const unsigned char *end = data + (len & ~7ul);
252
253	while (data != end) {
254	uint64_t k;
255	memcpy(dest: &k, src: data, n: sizeof(uint64_t));
256
257	k *= m;
258	k ^= k >> r;
259	k *= m;
260
261	h ^= k;
262	h *= m;
263
264	data += 8;
265	}
266
267	len &= 7;
268	if (len) {
269	// handle the last few bytes of input
270	size_t k = 0;
271	end += len;
272
273	while (data != end) {
274	k <<= 8;
275	k |= *data;
276	++data;
277	}
278	h ^= k;
279	h *= m;
280	}
281
282	h ^= h >> r;
283	h *= m;
284	h ^= h >> r;
285
286	return h;
287	}
288
289	#endif
290
291	enum ZeroExtension {
292	None = 0,
293	ByteToWord = 1,
294	};
295
296	template <ZeroExtension = None> static size_t
297	qHashBits_fallback(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept;
298	template <> size_t qHashBits_fallback<None>(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept
299	{
300	if (size <= QT_POINTER_SIZE)
301	return murmurhash(key: p, len: size, seed);
302
303	return siphash(in: reinterpret_cast<const uchar *>(p), inlen: size, seed, seed2);
304	}
305
306	template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept
307	{
308	auto quick_from_latin1 = [](char16_t *dest, const uchar *data, size_t size) {
309	// Quick, "inlined" version for very short blocks
310	std::copy_n(first: data, n: size, result: dest);
311	};
312	if (size <= QT_POINTER_SIZE / 2) {
313	std::array<char16_t, QT_POINTER_SIZE / 2> buf;
314	quick_from_latin1(buf.data(), data, size);
315	return murmurhash(key: buf.data(), len: size * 2, seed);
316	}
317
318	constexpr size_t TailSizeMask = sizeof(void *) / 2 - 1;
319	std::array<char16_t, 256> buf;
320	SipHash<> siphash(size * 2, seed, seed2);
321	ptrdiff_t offset = 0;
322	for ( ; offset + buf.size() < size; offset += buf.size()) {
323	qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: buf.size());
324	siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: sizeof(buf));
325	}
326	if (size_t n = size - offset; n > TailSizeMask) {
327	n &= ~TailSizeMask;
328	qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: n);
329	siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: n * 2);
330	offset += n;
331	}
332
333	quick_from_latin1(buf.data(), data + offset, size - offset);
334	return siphash.finalize(in: reinterpret_cast<uint8_t *>(buf.data()), left: (size - offset) * 2);
335	}
336
337	#if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__) // GCC
338	# define QHASH_AES_SANITIZER_BUILD
339	#elif __has_feature(address_sanitizer) || __has_feature(thread_sanitizer) // Clang
340	# define QHASH_AES_SANITIZER_BUILD
341	#endif
342
343	// When built with a sanitizer, aeshash() is rightfully reported to have a
344	// heap-buffer-overflow issue. However, we consider it to be safe in this
345	// specific case and overcome the problem by correctly discarding the
346	// out-of-range bits. To allow building the code with sanitizer,
347	// QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage.
348	#if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \
349	!defined(QHASH_AES_SANITIZER_BUILD)
350	# define AESHASH
351	# define QT_FUNCTION_TARGET_STRING_AES_AVX2 "avx2,aes"
352	# define QT_FUNCTION_TARGET_STRING_AES_AVX512 \
353	QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \
354	QT_FUNCTION_TARGET_STRING_AES
355	# define QT_FUNCTION_TARGET_STRING_VAES_AVX512 \
356	QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \
357	QT_FUNCTION_TARGET_STRING_VAES
358	# undef QHASH_AES_SANITIZER_BUILD
359	# if QT_POINTER_SIZE == 8
360	# define mm_set1_epz _mm_set1_epi64x
361	# define mm_cvtsz_si128 _mm_cvtsi64_si128
362	# define mm_cvtsi128_sz _mm_cvtsi128_si64
363	# define mm256_set1_epz _mm256_set1_epi64x
364	# else
365	# define mm_set1_epz _mm_set1_epi32
366	# define mm_cvtsz_si128 _mm_cvtsi32_si128
367	# define mm_cvtsi128_sz _mm_cvtsi128_si32
368	# define mm256_set1_epz _mm256_set1_epi32
369	# endif
370
371	namespace {
372	// This is inspired by the algorithm in the Go language. See:
373	// https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_amd64.s#L1105
374	// https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_386.s#L908
375	//
376	// Even though we're using the AESENC instruction from the CPU, this code
377	// is not encryption and this routine makes no claim to be
378	// cryptographically secure. We're simply using the instruction that performs
379	// the scrambling round (step 3 in [1]) because it's just very good at
380	// spreading the bits around.
381	//
382	// Note on Latin-1 hashing (ZX == ByteToWord): for simplicity of the
383	// algorithm, we pass sizes equivalent to the UTF-16 content (ZX == None).
384	// That means we must multiply by 2 on entry, divide by 2 on pointer
385	// advancing, and load half as much data from memory (though we produce
386	// exactly as much data in registers). The compilers appear to optimize
387	// this out.
388	//
389	// [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm
390
391	template <ZeroExtension ZX, typename T> static const T *advance(const T *ptr, ptrdiff_t n)
392	{
393	if constexpr (ZX == None)
394	return ptr + n;
395
396	// see note above on ZX == ByteToWord hashing
397	auto p = reinterpret_cast<const uchar *>(ptr);
398	n *= sizeof(T);
399	return reinterpret_cast<const T *>(p + n/2);
400	}
401
402	template <ZeroExtension> static __m128i loadu128(const void *ptr);
403	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<None>(const void *ptr)
404	{
405	return _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr));
406	}
407	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<ByteToWord>(const void *ptr)
408	{
409	// use a MOVQ followed by PMOVZXBW
410	// the compiler usually combines them as a single, loading PMOVZXBW
411	__m128i data = _mm_loadl_epi64(p: static_cast<const __m128i *>(ptr));
412	return _mm_cvtepu8_epi16(V: data);
413	}
414
415	// hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1")
416	static void Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) QT_VECTORCALL
417	hash16bytes(__m128i &state0, __m128i data)
418	{
419	state0 = _mm_xor_si128(a: state0, b: data);
420	state0 = _mm_aesenc_si128(V: state0, R: state0);
421	state0 = _mm_aesenc_si128(V: state0, R: state0);
422	state0 = _mm_aesenc_si128(V: state0, R: state0);
423	}
424
425	// hash twice 16 bytes, running 2 scramble rounds of AES on itself
426	template <ZeroExtension ZX>
427	static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
428	hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1)
429	{
430	__m128i data0 = loadu128<ZX>(src0);
431	__m128i data1 = loadu128<ZX>(src1);
432	state0 = _mm_xor_si128(a: data0, b: state0);
433	state1 = _mm_xor_si128(a: data1, b: state1);
434	state0 = _mm_aesenc_si128(V: state0, R: state0);
435	state1 = _mm_aesenc_si128(V: state1, R: state1);
436	state0 = _mm_aesenc_si128(V: state0, R: state0);
437	state1 = _mm_aesenc_si128(V: state1, R: state1);
438	}
439
440	struct AESHashSeed
441	{
442	__m128i state0;
443	__m128i mseed2;
444	AESHashSeed(size_t seed, size_t seed2) QT_FUNCTION_TARGET(AES);
445	__m128i state1() const QT_FUNCTION_TARGET(AES);
446	__m256i state0_256() const QT_FUNCTION_TARGET(AES_AVX2)
447	{ return _mm256_set_m128i(hi: state1(), lo: state0); }
448	};
449	} // unnamed namespace
450
451	Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2)
452	{
453	__m128i mseed = mm_cvtsz_si128(a: seed);
454	mseed2 = mm_set1_epz(q: seed2);
455
456	// mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, 0, 0, 0 ]
457	mseed = _mm_insert_epi16(mseed, short(seed), 4);
458	// mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, len, len, len ]
459	mseed = _mm_shufflehi_epi16(mseed, 0);
460
461	// merge with the process-global seed
462	__m128i key = _mm_xor_si128(a: mseed, b: mseed2);
463
464	// scramble the key
465	__m128i state0 = _mm_aesenc_si128(V: key, R: key);
466	this->state0 = state0;
467	}
468
469	Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const
470	{
471	{
472	// unlike the Go code, we don't have more per-process seed
473	__m128i state1 = _mm_aesenc_si128(V: state0, R: mseed2);
474	return state1;
475	}
476	}
477
478	template <ZeroExtension ZX>
479	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
480	aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
481	{
482	{
483	const __m128i *src2 = advance<ZX>(srcend, -1);
484	if (advance<ZX>(src, 1) < srcend) {
485	// epilogue: between 16 and 31 bytes
486	hash2x16bytes<ZX>(state0, state1, src, src2);
487	} else if (src != srcend) {
488	// epilogue: between 1 and 16 bytes, overlap with the end
489	__m128i data = loadu128<ZX>(src2);
490	hash16bytes(state0, data);
491	}
492
493	// combine results:
494	state0 = _mm_xor_si128(a: state0, b: state1);
495	}
496
497	return mm_cvtsi128_sz(a: state0);
498	}
499
500	// load all 16 bytes and mask off the bytes past the end of the source
501	static const qint8 maskarray[] = {
502	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
503	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
504	};
505
506	// load 16 bytes ending at the data end, then shuffle them to the beginning
507	static const qint8 shufflecontrol[] = {
508	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
509	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
510	};
511
512	template <ZeroExtension ZX>
513	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
514	aeshash128_lt16(__m128i state0, const __m128i *src, const __m128i *srcend, size_t len)
515	{
516	if (len) {
517	// We're going to load 16 bytes and mask zero the part we don't care
518	// (the hash of a short string is different from the hash of a longer
519	// including NULLs at the end because the length is in the key)
520	// WARNING: this may produce valgrind warnings, but it's safe
521
522	constexpr quintptr CachelineSize = 64;
523	__m128i data;
524
525	if ((quintptr(src) & (CachelineSize / 2)) == 0) {
526	// lower half of the cacheline:
527	__m128i mask = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(maskarray + 15 - len));
528	data = loadu128<ZX>(src);
529	data = _mm_and_si128(a: data, b: mask);
530	} else {
531	// upper half of the cacheline:
532	__m128i control = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len));
533	data = loadu128<ZX>(advance<ZX>(srcend, -1));
534	data = _mm_shuffle_epi8(a: data, b: control);
535	}
536
537	hash16bytes(state0, data);
538	}
539	return mm_cvtsi128_sz(a: state0);
540	}
541
542	template <ZeroExtension ZX>
543	static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
544	aeshash128_ge32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
545	{
546	// main loop: scramble two 16-byte blocks
547	for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
548	hash2x16bytes<ZX>(state0, state1, src, advance<ZX>(src, 1));
549
550	return aeshash128_16to32<ZX>(state0, state1, src, srcend);
551	}
552
553	# if QT_COMPILER_SUPPORTS_HERE(VAES)
554	template <ZeroExtension> static __m256i loadu256(const void *ptr);
555	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<None>(const void *ptr)
556	{
557	return _mm256_loadu_si256(p: reinterpret_cast<const __m256i *>(ptr));
558	}
559	template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<ByteToWord>(const void *ptr)
560	{
561	// VPMOVZXBW xmm, ymm
562	__m128i data = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr));
563	return _mm256_cvtepu8_epi16(V: data);
564	}
565
566	template <ZeroExtension ZX>
567	static size_t QT_FUNCTION_TARGET(VAES_AVX512) QT_VECTORCALL
568	aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len)
569	{
570	__m128i state0_128 = _mm256_castsi256_si128(a: state0);
571	if (len) {
572	__m256i data;
573	if constexpr (ZX == None) {
574	__mmask32 mask = _bzhi_u32(X: -1, Y: unsigned(len));
575	data = _mm256_maskz_loadu_epi8(U: mask, P: p);
576	} else {
577	__mmask16 mask = _bzhi_u32(X: -1, Y: unsigned(len) / 2);
578	__m128i data0 = _mm_maskz_loadu_epi8(U: mask, P: p);
579	data = _mm256_cvtepu8_epi16(V: data0);
580	}
581	__m128i data0 = _mm256_castsi256_si128(a: data);
582	if (len >= sizeof(__m128i)) {
583	state0 = _mm256_xor_si256(a: state0, b: data);
584	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
585	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
586	// we're XOR'ing the two halves so we skip the third AESENC
587	// state0 = _mm256_aesenc_epi128(state0, state0);
588
589	// XOR the two halves and extract
590	__m128i low = _mm256_extracti128_si256(state0, 0);
591	__m128i high = _mm256_extracti128_si256(state0, 1);
592	state0_128 = _mm_xor_si128(a: low, b: high);
593	} else {
594	hash16bytes(state0&: state0_128, data: data0);
595	}
596	}
597	return mm_cvtsi128_sz(a: state0_128);
598	}
599
600	template <ZeroExtension ZX>
601	static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL
602	aeshash256_ge32(__m256i state0, const __m128i *s, const __m128i *end, size_t len)
603	{
604	static const auto hash32bytes = [](__m256i &state0, __m256i data) QT_FUNCTION_TARGET(VAES) {
605	state0 = _mm256_xor_si256(a: state0, b: data);
606	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
607	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
608	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
609	};
610
611	// hash twice 32 bytes, running 2 scramble rounds of AES on itself
612	const auto hash2x32bytes = [](__m256i &state0, __m256i &state1, const void *src0,
613	const void *src1) QT_FUNCTION_TARGET(VAES) {
614	__m256i data0 = loadu256<ZX>(src0);
615	__m256i data1 = loadu256<ZX>(src1);
616	state0 = _mm256_xor_si256(a: data0, b: state0);
617	state1 = _mm256_xor_si256(a: data1, b: state1);
618	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
619	state1 = _mm256_aesenc_epi128(A: state1, B: state1);
620	state0 = _mm256_aesenc_epi128(A: state0, B: state0);
621	state1 = _mm256_aesenc_epi128(A: state1, B: state1);
622	};
623
624	const __m256i *src = reinterpret_cast<const __m256i *>(s);
625	const __m256i *srcend = reinterpret_cast<const __m256i *>(end);
626
627	__m256i state1 = _mm256_aesenc_epi128(A: state0, mm256_set1_epz(q: len));
628
629	// main loop: scramble two 32-byte blocks
630	for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
631	hash2x32bytes(state0, state1, src, advance<ZX>(src, 1));
632
633	const __m256i *src2 = advance<ZX>(srcend, -1);
634	if (advance<ZX>(src, 1) < srcend) {
635	// epilogue: between 32 and 31 bytes
636	hash2x32bytes(state0, state1, src, src2);
637	} else if (src != srcend) {
638	// epilogue: between 1 and 32 bytes, overlap with the end
639	__m256i data = loadu256<ZX>(src2);
640	hash32bytes(state0, data);
641	}
642
643	// combine results:
644	state0 = _mm256_xor_si256(a: state0, b: state1);
645
646	// XOR the two halves and extract
647	__m128i low = _mm256_extracti128_si256(state0, 0);
648	__m128i high = _mm256_extracti128_si256(state0, 1);
649	return mm_cvtsi128_sz(a: _mm_xor_si128(a: low, b: high));
650	}
651
652	template <ZeroExtension ZX>
653	static size_t QT_FUNCTION_TARGET(VAES)
654	aeshash256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
655	{
656	AESHashSeed state(seed, seed2);
657	auto src = reinterpret_cast<const __m128i *>(p);
658	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
659
660	if (len < sizeof(__m128i))
661	return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
662
663	if (len <= sizeof(__m256i))
664	return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
665
666	return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
667	}
668
669	template <ZeroExtension ZX>
670	static size_t QT_FUNCTION_TARGET(VAES_AVX512)
671	aeshash256_avx256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
672	{
673	AESHashSeed state(seed, seed2);
674	auto src = reinterpret_cast<const __m128i *>(p);
675	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
676
677	if (len <= sizeof(__m256i))
678	return aeshash256_lt32_avx256<ZX>(state.state0_256(), p, len);
679
680	return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
681	}
682	# endif // VAES
683
684	template <ZeroExtension ZX>
685	static size_t QT_FUNCTION_TARGET(AES)
686	aeshash128(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
687	{
688	AESHashSeed state(seed, seed2);
689	auto src = reinterpret_cast<const __m128i *>(p);
690	const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
691
692	if (len < sizeof(__m128i))
693	return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
694
695	if (len <= sizeof(__m256i))
696	return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
697
698	return aeshash128_ge32<ZX>(state.state0, state.state1(), src, srcend);
699	}
700
701	template <ZeroExtension ZX = None>
702	static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
703	{
704	if constexpr (ZX == ByteToWord)
705	len *= 2; // see note above on ZX == ByteToWord hashing
706
707	# if QT_COMPILER_SUPPORTS_HERE(VAES)
708	if (qCpuHasFeature(VAES)) {
709	if (qCpuHasFeature(AVX512VL))
710	return aeshash256_avx256<ZX>(p, len, seed, seed2);
711	return aeshash256<ZX>(p, len, seed, seed2);
712	}
713	# endif
714	return aeshash128<ZX>(p, len, seed, seed2);
715	}
716	#endif // x86 AESNI
717
718	#if defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
719	QT_FUNCTION_TARGET(AES)
720	static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
721	{
722	uint8x16_t key;
723	# if QT_POINTER_SIZE == 8
724	uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2));
725	key = vreinterpretq_u8_u64(vseed);
726	# else
727
728	uint32x2_t vseed = vmov_n_u32(seed);
729	vseed = vset_lane_u32(seed2, vseed, 1);
730	key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed));
731	# endif
732
733	// Compared to x86 AES, ARM splits each round into two instructions
734	// and includes the pre-xor instead of the post-xor.
735	const auto hash16bytes = [](uint8x16_t &state0, uint8x16_t data) {
736	auto state1 = state0;
737	state0 = vaeseq_u8(state0, data);
738	state0 = vaesmcq_u8(state0);
739	auto state2 = state0;
740	state0 = vaeseq_u8(state0, state1);
741	state0 = vaesmcq_u8(state0);
742	auto state3 = state0;
743	state0 = vaeseq_u8(state0, state2);
744	state0 = vaesmcq_u8(state0);
745	state0 = veorq_u8(state0, state3);
746	};
747
748	uint8x16_t state0 = key;
749
750	if (len < 8)
751	goto lt8;
752	if (len < 16)
753	goto lt16;
754	if (len < 32)
755	goto lt32;
756
757	// rounds of 32 bytes
758	{
759	// Make state1 = ~state0:
760	uint8x16_t state1 = veorq_u8(state0, vdupq_n_u8(255));
761
762	// do simplified rounds of 32 bytes: unlike the Go code, we only
763	// scramble twice and we keep 256 bits of state
764	const auto *e = p + len - 31;
765	while (p < e) {
766	uint8x16_t data0 = vld1q_u8(p);
767	uint8x16_t data1 = vld1q_u8(p + 16);
768	auto oldstate0 = state0;
769	auto oldstate1 = state1;
770	state0 = vaeseq_u8(state0, data0);
771	state1 = vaeseq_u8(state1, data1);
772	state0 = vaesmcq_u8(state0);
773	state1 = vaesmcq_u8(state1);
774	auto laststate0 = state0;
775	auto laststate1 = state1;
776	state0 = vaeseq_u8(state0, oldstate0);
777	state1 = vaeseq_u8(state1, oldstate1);
778	state0 = vaesmcq_u8(state0);
779	state1 = vaesmcq_u8(state1);
780	state0 = veorq_u8(state0, laststate0);
781	state1 = veorq_u8(state1, laststate1);
782	p += 32;
783	}
784	state0 = veorq_u8(state0, state1);
785	}
786	len &= 0x1f;
787
788	// do we still have 16 or more bytes?
789	if (len & 0x10) {
790	lt32:
791	uint8x16_t data = vld1q_u8(p);
792	hash16bytes(state0, data);
793	p += 16;
794	}
795	len &= 0xf;
796
797	if (len & 0x08) {
798	lt16:
799	uint8x8_t data8 = vld1_u8(p);
800	uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
801	hash16bytes(state0, data);
802	p += 8;
803	}
804	len &= 0x7;
805
806	lt8:
807	if (len) {
808	// load the last chunk of data
809	// We're going to load 8 bytes and mask zero the part we don't care
810	// (the hash of a short string is different from the hash of a longer
811	// including NULLs at the end because the length is in the key)
812	// WARNING: this may produce valgrind warnings, but it's safe
813
814	uint8x8_t data8;
815
816	if (Q_LIKELY(quintptr(p + 8) & 0xff8)) {
817	// same page, we definitely can't fault:
818	// load all 8 bytes and mask off the bytes past the end of the source
819	static const qint8 maskarray[] = {
820	-1, -1, -1, -1, -1, -1, -1,
821	0, 0, 0, 0, 0, 0, 0,
822	};
823	uint8x8_t mask = vld1_u8(reinterpret_cast<const quint8 *>(maskarray) + 7 - len);
824	data8 = vld1_u8(p);
825	data8 = vand_u8(data8, mask);
826	} else {
827	// too close to the end of the page, it could fault:
828	// load 8 bytes ending at the data end, then shuffle them to the beginning
829	static const qint8 shufflecontrol[] = {
830	1, 2, 3, 4, 5, 6, 7,
831	-1, -1, -1, -1, -1, -1, -1,
832	};
833	uint8x8_t control = vld1_u8(reinterpret_cast<const quint8 *>(shufflecontrol) + 7 - len);
834	data8 = vld1_u8(p - 8 + len);
835	data8 = vtbl1_u8(data8, control);
836	}
837	uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
838	hash16bytes(state0, data);
839	}
840
841	// extract state0
842	# if QT_POINTER_SIZE == 8
843	return vgetq_lane_u64(vreinterpretq_u64_u8(state0), 0);
844	# else
845	return vgetq_lane_u32(vreinterpretq_u32_u8(state0), 0);
846	# endif
847	}
848	#endif
849
850	size_t qHashBits(const void *p, size_t size, size_t seed) noexcept
851	{
852	#ifdef QT_BOOTSTRAPPED
853	// the seed is always 0 in bootstrapped mode (no seed generation code),
854	// so help the compiler do dead code elimination
855	seed = 0;
856	#endif
857	// mix in the length as a secondary seed. For seed == 0, seed2 must be
858	// size, to match what we used to do prior to Qt 6.2.
859	size_t seed2 = size;
860	if (seed)
861	seed2 = qt_qhash_seed.currentSeed(which: 1);
862
863	auto data = reinterpret_cast<const uchar *>(p);
864	#ifdef AESHASH
865	if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
866	return aeshash(p: data, len: size, seed, seed2);
867	#elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
868	if (seed && qCpuHasFeature(AES))
869	return aeshash(data, size, seed, seed2);
870	#endif
871
872	return qHashBits_fallback<>(p: data, size, seed, seed2);
873	}
874
875	size_t qHash(QByteArrayView key, size_t seed) noexcept
876	{
877	return qHashBits(p: key.constData(), size: size_t(key.size()), seed);
878	}
879
880	size_t qHash(QStringView key, size_t seed) noexcept
881	{
882	return qHashBits(p: key.data(), size: key.size()*sizeof(QChar), seed);
883	}
884
885	#ifndef QT_BOOTSTRAPPED
886	size_t qHash(const QBitArray &bitArray, size_t seed) noexcept
887	{
888	qsizetype m = bitArray.d.size() - 1;
889	size_t result = qHashBits(p: reinterpret_cast<const uchar *>(bitArray.d.constData()), size: size_t(qMax(a: 0, b: m)), seed);
890
891	// deal with the last 0 to 7 bits manually, because we can't trust that
892	// the padding is initialized to 0 in bitArray.d
893	qsizetype n = bitArray.size();
894	if (n & 0x7)
895	result = ((result << 4) + bitArray.d.at(i: m)) & ((1 << n) - 1);
896	return result;
897	}
898	#endif
899
900	size_t qHash(QLatin1StringView key, size_t seed) noexcept
901	{
902	#ifdef QT_BOOTSTRAPPED
903	// the seed is always 0 in bootstrapped mode (no seed generation code),
904	// so help the compiler do dead code elimination
905	seed = 0;
906	#endif
907
908	auto data = reinterpret_cast<const uchar *>(key.data());
909	size_t size = key.size();
910
911	// Mix in the length as a secondary seed.
912	// Multiplied by 2 to match the byte size of the equiavlent UTF-16 string.
913	size_t seed2 = size * 2;
914	if (seed)
915	seed2 = qt_qhash_seed.currentSeed(which: 1);
916
917	#if defined(AESHASH)
918	if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
919	return aeshash<ByteToWord>(p: data, len: size, seed, seed2);
920	#endif
921	return qHashBits_fallback<ByteToWord>(data, size, seed, seed2);
922	}
923
924	/*!
925	\class QHashSeed
926	\inmodule QtCore
927	\since 6.2
928
929	The QHashSeed class is used to convey the QHash seed. This is used
930	internally by QHash and provides three static member functions to allow
931	users to obtain the hash and to reset it.
932
933	QHash and the qHash() functions implement what is called as "salted hash".
934	The intent is that different applications and different instances of the
935	same application will produce different hashing values for the same input,
936	thus causing the ordering of elements in QHash to be unpredictable by
937	external observers. This improves the applications' resilience against
938	attacks that attempt to force hashing tables into degenerate mode.
939
940	Most applications will not need to deal directly with the hash seed, as
941	QHash will do so when needed. However, applications may wish to use this
942	for their own purposes in the same way as QHash does: as an
943	application-global random value (but see \l QRandomGenerator too). Note
944	that the global hash seed may change during the application's lifetime, if
945	the resetRandomGlobalSeed() function is called. Users of the global hash
946	need to store the value they are using and not rely on getting it again.
947
948	This class also implements functionality to set the hash seed to a
949	deterministic value, which the qHash() functions will take to mean that
950	they should use a fixed hashing function on their data too. This
951	functionality is only meant to be used in debugging applications. This
952	behavior can also be controlled by setting the \c QT_HASH_SEED environment
953	variable to the value zero (any other value is ignored).
954
955	\sa QHash, QRandomGenerator
956	*/
957
958	/*!
959	\fn QHashSeed::QHashSeed(size_t data)
960
961	Constructs a new QHashSeed object using \a data as the seed.
962	*/
963
964	/*!
965	\fn QHashSeed::operator size_t() const
966
967	Converts the returned hash seed into a \c size_t.
968	*/
969
970	/*!
971	\threadsafe
972
973	Returns the current global QHash seed. The value returned by this function
974	will be zero if setDeterministicGlobalSeed() has been called or if the
975	\c{QT_HASH_SEED} environment variable is set to zero.
976	*/
977	QHashSeed QHashSeed::globalSeed() noexcept
978	{
979	return qt_qhash_seed.currentSeed(which: 0);
980	}
981
982	/*!
983	\threadsafe
984
985	Forces the Qt hash seed to a deterministic value (zero) and asks the
986	qHash() functions to use a pre-determined hashing function. This mode is
987	only useful for debugging and should not be used in production code.
988
989	Regular operation can be restored by calling resetRandomGlobalSeed().
990	*/
991	void QHashSeed::setDeterministicGlobalSeed()
992	{
993	qt_qhash_seed.clearSeed();
994	}
995
996	/*!
997	\threadsafe
998
999	Reseeds the Qt hashing seed to a new, random value. Calling this function
1000	is not necessary, but long-running applications may want to do so after a
1001	long period of time in which information about its hash may have been
1002	exposed to potential attackers.
1003
1004	If the environment variable \c QT_HASH_SEED is set to zero, calling this
1005	function will result in a no-op.
1006
1007	Qt never calls this function during the execution of the application, but
1008	unless the \c QT_HASH_SEED variable is set to 0, the hash seed returned by
1009	globalSeed() will be a random value as if this function had been called.
1010	*/
1011	void QHashSeed::resetRandomGlobalSeed()
1012	{
1013	qt_qhash_seed.resetSeed();
1014	}
1015
1016	#if QT_DEPRECATED_SINCE(6,6)
1017	/*! \relates QHash
1018	\since 5.6
1019	\deprecated [6.6] Use QHashSeed::globalSeed() instead.
1020
1021	Returns the current global QHash seed.
1022
1023	The seed is set in any newly created QHash. See \l{qHash} about how this seed
1024	is being used by QHash.
1025
1026	\sa QHashSeed, QHashSeed::globalSeed()
1027	*/
1028	int qGlobalQHashSeed()
1029	{
1030	return int(QHashSeed::globalSeed() & INT_MAX);
1031	}
1032
1033	/*! \relates QHash
1034	\since 5.6
1035	\deprecated [6.6] Use QHashSeed instead.
1036
1037	Sets the global QHash seed to \a newSeed.
1038
1039	Manually setting the global QHash seed value should be done only for testing
1040	and debugging purposes, when deterministic and reproducible behavior on a QHash
1041	is needed. We discourage to do it in production code as it can make your
1042	application susceptible to \l{algorithmic complexity attacks}.
1043
1044	From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the
1045	value -1 will reinitialize the global QHash seed to a random value, while
1046	the value of 0 is used to request a stable algorithm for C++ primitive
1047	types types (like \c int) and string types (QString, QByteArray).
1048
1049	The seed is set in any newly created QHash. See \l{qHash} about how this seed
1050	is being used by QHash.
1051
1052	If the environment variable \c QT_HASH_SEED is set, calling this function will
1053	result in a no-op.
1054
1055	\sa QHashSeed::globalSeed(), QHashSeed
1056	*/
1057	void qSetGlobalQHashSeed(int newSeed)
1058	{
1059	if (Q_LIKELY(newSeed == 0 || newSeed == -1)) {
1060	if (newSeed == 0)
1061	QHashSeed::setDeterministicGlobalSeed();
1062	else
1063	QHashSeed::resetRandomGlobalSeed();
1064	} else {
1065	// can't use qWarning here (reentrancy)
1066	fprintf(stderr, format: "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n");
1067	}
1068	}
1069	#endif // QT_DEPRECATED_SINCE(6,6)
1070
1071	/*!
1072	\internal
1073
1074	Private copy of the implementation of the Qt 4 qHash algorithm for strings,
1075	(that is, QChar-based arrays, so all QString-like classes),
1076	to be used wherever the result is somehow stored or reused across multiple
1077	Qt versions. The public qHash implementation can change at any time,
1078	therefore one must not rely on the fact that it will always give the same
1079	results.
1080
1081	The qt_hash functions must *never* change their results.
1082
1083	This function can hash discontiguous memory by invoking it on each chunk,
1084	passing the previous's result in the next call's \a chained argument.
1085	*/
1086	uint qt_hash(QStringView key, uint chained) noexcept
1087	{
1088	uint h = chained;
1089
1090	for (auto c: key) {
1091	h = (h << 4) + c.unicode();
1092	h ^= (h & 0xf0000000) >> 23;
1093	}
1094	h &= 0x0fffffff;
1095	return h;
1096	}
1097
1098	/*!
1099	\fn template <typename T1, typename T2> size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
1100	\since 5.7
1101	\qhashbuiltinTS{T1}{T2}
1102	*/
1103
1104	/*!
1105	\fn template <typename... T> size_t qHashMulti(size_t seed, const T &...args)
1106	\relates QHash
1107	\since 6.0
1108
1109	Returns the hash value for the \a{args}, using \a seed to seed
1110	the calculation, by successively applying qHash() to each
1111	element and combining the hash values into a single one.
1112
1113	Note that the order of the arguments is significant. If order does
1114	not matter, use qHashMultiCommutative() instead. If you are hashing raw
1115	memory, use qHashBits(); if you are hashing a range, use qHashRange().
1116
1117	This function is provided as a convenience to implement qHash() for
1118	your own custom types. For example, here's how you could implement
1119	a qHash() overload for a class \c{Employee}:
1120
1121	\snippet code/src_corelib_tools_qhash.cpp 13
1122
1123	\sa qHashMultiCommutative, qHashRange
1124	*/
1125
1126	/*!
1127	\fn template <typename... T> size_t qHashMultiCommutative(size_t seed, const T &...args)
1128	\relates QHash
1129	\since 6.0
1130
1131	Returns the hash value for the \a{args}, using \a seed to seed
1132	the calculation, by successively applying qHash() to each
1133	element and combining the hash values into a single one.
1134
1135	The order of the arguments is insignificant. If order does
1136	matter, use qHashMulti() instead, as it may produce better quality
1137	hashing. If you are hashing raw memory, use qHashBits(); if you are
1138	hashing a range, use qHashRange().
1139
1140	This function is provided as a convenience to implement qHash() for
1141	your own custom types.
1142
1143	\sa qHashMulti, qHashRange
1144	*/
1145
1146	/*! \fn template <typename InputIterator> size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
1147	\relates QHash
1148	\since 5.5
1149
1150	Returns the hash value for the range [\a{first},\a{last}), using \a seed
1151	to seed the calculation, by successively applying qHash() to each
1152	element and combining the hash values into a single one.
1153
1154	The return value of this function depends on the order of elements
1155	in the range. That means that
1156
1157	\snippet code/src_corelib_tools_qhash.cpp 30
1158
1159	and
1160	\snippet code/src_corelib_tools_qhash.cpp 31
1161
1162	hash to \b{different} values. If order does not matter, for example for hash
1163	tables, use qHashRangeCommutative() instead. If you are hashing raw
1164	memory, use qHashBits().
1165
1166	Use this function only to implement qHash() for your own custom
1167	types. For example, here's how you could implement a qHash() overload for
1168	std::vector<int>:
1169
1170	\snippet code/src_corelib_tools_qhash.cpp qhashrange
1171
1172	It bears repeating that the implementation of qHashRange() - like
1173	the qHash() overloads offered by Qt - may change at any time. You
1174	\b{must not} rely on the fact that qHashRange() will give the same
1175	results (for the same inputs) across different Qt versions, even
1176	if qHash() for the element type would.
1177
1178	\sa qHashBits(), qHashRangeCommutative()
1179	*/
1180
1181	/*! \fn template <typename InputIterator> size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
1182	\relates QHash
1183	\since 5.5
1184
1185	Returns the hash value for the range [\a{first},\a{last}), using \a seed
1186	to seed the calculation, by successively applying qHash() to each
1187	element and combining the hash values into a single one.
1188
1189	The return value of this function does not depend on the order of
1190	elements in the range. That means that
1191
1192	\snippet code/src_corelib_tools_qhash.cpp 30
1193
1194	and
1195	\snippet code/src_corelib_tools_qhash.cpp 31
1196
1197	hash to the \b{same} values. If order matters, for example, for vectors
1198	and arrays, use qHashRange() instead. If you are hashing raw
1199	memory, use qHashBits().
1200
1201	Use this function only to implement qHash() for your own custom
1202	types. For example, here's how you could implement a qHash() overload for
1203	std::unordered_set<int>:
1204
1205	\snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
1206
1207	It bears repeating that the implementation of
1208	qHashRangeCommutative() - like the qHash() overloads offered by Qt
1209	- may change at any time. You \b{must not} rely on the fact that
1210	qHashRangeCommutative() will give the same results (for the same
1211	inputs) across different Qt versions, even if qHash() for the
1212	element type would.
1213
1214	\sa qHashBits(), qHashRange()
1215	*/
1216
1217	/*! \fn size_t qHashBits(const void *p, size_t len, size_t seed = 0)
1218	\relates QHash
1219	\since 5.4
1220
1221	Returns the hash value for the memory block of size \a len pointed
1222	to by \a p, using \a seed to seed the calculation.
1223
1224	Use this function only to implement qHash() for your own custom
1225	types. For example, here's how you could implement a qHash() overload for
1226	std::vector<int>:
1227
1228	\snippet code/src_corelib_tools_qhash.cpp qhashbits
1229
1230	This takes advantage of the fact that std::vector lays out its data
1231	contiguously. If that is not the case, or the contained type has
1232	padding, you should use qHashRange() instead.
1233
1234	It bears repeating that the implementation of qHashBits() - like
1235	the qHash() overloads offered by Qt - may change at any time. You
1236	\b{must not} rely on the fact that qHashBits() will give the same
1237	results (for the same inputs) across different Qt versions.
1238
1239	\sa qHashRange(), qHashRangeCommutative()
1240	*/
1241
1242	/*! \fn size_t qHash(char key, size_t seed = 0)
1243	\since 5.0
1244	\qhashbuiltin
1245	*/
1246
1247	/*! \fn size_t qHash(uchar key, size_t seed = 0)
1248	\since 5.0
1249	\qhashbuiltin
1250	*/
1251
1252	/*! \fn size_t qHash(signed char key, size_t seed = 0)
1253	\since 5.0
1254	\qhashbuiltin
1255	*/
1256
1257	/*! \fn size_t qHash(ushort key, size_t seed = 0)
1258	\since 5.0
1259	\qhashbuiltin
1260	*/
1261
1262	/*! \fn size_t qHash(short key, size_t seed = 0)
1263	\since 5.0
1264	\qhashbuiltin
1265	*/
1266
1267	/*! \fn size_t qHash(uint key, size_t seed = 0)
1268	\since 5.0
1269	\qhashbuiltin
1270	*/
1271
1272	/*! \fn size_t qHash(int key, size_t seed = 0)
1273	\since 5.0
1274	\qhashbuiltin
1275	*/
1276
1277	/*! \fn size_t qHash(ulong key, size_t seed = 0)
1278	\since 5.0
1279	\qhashbuiltin
1280	*/
1281
1282	/*! \fn size_t qHash(long key, size_t seed = 0)
1283	\since 5.0
1284	\qhashbuiltin
1285	*/
1286
1287	/*! \fn size_t qHash(quint64 key, size_t seed = 0)
1288	\since 5.0
1289	\qhashbuiltin
1290	*/
1291
1292	/*! \fn size_t qHash(qint64 key, size_t seed = 0)
1293	\since 5.0
1294	\qhashbuiltin
1295	*/
1296
1297	/*! \fn size_t qHash(quint128 key, size_t seed = 0)
1298	\since 6.8
1299	\qhashbuiltin
1300
1301	\note This function is only available on platforms that support a native
1302	128-bit integer type.
1303	*/
1304
1305	/*! \fn size_t qHash(qint128 key, size_t seed = 0)
1306	\since 6.8
1307	\qhashbuiltin
1308
1309	\note This function is only available on platforms that support a native
1310	128-bit integer type.
1311	*/
1312
1313	/*! \fn size_t qHash(char8_t key, size_t seed = 0)
1314	\since 6.0
1315	\qhashbuiltin
1316	*/
1317
1318	/*! \fn size_t qHash(char16_t key, size_t seed = 0)
1319	\since 6.0
1320	\qhashbuiltin
1321	*/
1322
1323	/*! \fn size_t qHash(char32_t key, size_t seed = 0)
1324	\since 6.0
1325	\qhashbuiltin
1326	*/
1327
1328	/*! \fn size_t qHash(wchar_t key, size_t seed = 0)
1329	\since 6.0
1330	\qhashbuiltin
1331	*/
1332
1333	/*! \fn size_t qHash(float key, size_t seed = 0) noexcept
1334	\since 5.3
1335	\qhashbuiltin
1336	*/
1337
1338	/*!
1339	\since 5.3
1340	\qhashbuiltin
1341	*/
1342	size_t qHash(double key, size_t seed) noexcept
1343	{
1344	// ensure -0 gets mapped to 0
1345	key += 0.0;
1346	if constexpr (sizeof(double) == sizeof(size_t)) {
1347	size_t k;
1348	memcpy(dest: &k, src: &key, n: sizeof(double));
1349	return QHashPrivate::hash(key: k, seed);
1350	} else {
1351	return murmurhash(key: &key, len: sizeof(key), seed);
1352	}
1353	}
1354
1355	/*!
1356	\since 5.3
1357	\qhashbuiltin
1358	*/
1359	size_t qHash(long double key, size_t seed) noexcept
1360	{
1361	// ensure -0 gets mapped to 0
1362	key += static_cast<long double>(0.0);
1363	if constexpr (sizeof(long double) == sizeof(size_t)) {
1364	size_t k;
1365	memcpy(dest: &k, src: &key, n: sizeof(long double));
1366	return QHashPrivate::hash(key: k, seed);
1367	} else {
1368	return murmurhash(key: &key, len: sizeof(key), seed);
1369	}
1370	}
1371
1372	/*!
1373	\fn template <typename Enum, std::enable_if_t<std::is_enum_v<Enum>, bool> = true> size_t qHash(Enum key, size_t seed)
1374	\since 6.5
1375	\qhashbuiltin
1376
1377	\note Prior to Qt 6.5, unscoped enums relied on the integer overloads of this
1378	function due to implicit conversion to their underlying integer types.
1379	For scoped enums, you had to implement an overload yourself. This is still the
1380	backwards-compatible fix to remain compatible with older Qt versions.
1381	*/
1382
1383	/*! \fn size_t qHash(const QChar key, size_t seed = 0)
1384	\since 5.0
1385	\qhashold{QHash}
1386	*/
1387
1388	/*! \fn size_t qHash(const QByteArray &key, size_t seed = 0)
1389	\since 5.0
1390	\qhashold{QHash}
1391	*/
1392
1393	/*! \fn size_t qHash(const QByteArrayView &key, size_t seed = 0)
1394	\since 6.0
1395	\qhashold{QHash}
1396	*/
1397
1398	/*! \fn size_t qHash(const QBitArray &key, size_t seed = 0)
1399	\since 5.0
1400	\qhashold{QHash}
1401	*/
1402
1403	/*! \fn size_t qHash(const QString &key, size_t seed = 0)
1404	\since 5.0
1405	\qhashold{QHash}
1406	*/
1407
1408	/*! \fn size_t qHash(QLatin1StringView key, size_t seed = 0)
1409	\since 5.0
1410	\qhashold{QHash}
1411	*/
1412
1413	/*! \fn template <class T> size_t qHash(const T *key, size_t seed = 0)
1414	\since 5.0
1415	\qhashbuiltin
1416	*/
1417
1418	/*! \fn size_t qHash(std::nullptr_t key, size_t seed = 0)
1419	\since 6.0
1420	\qhashbuiltin
1421	*/
1422
1423	/*! \fn template<typename T> bool qHashEquals(const T &a, const T &b)
1424	\relates QHash
1425	\since 6.0
1426	\internal
1427
1428	This method is being used by QHash to compare two keys. Returns true if the
1429	keys \a a and \a b are considered equal for hashing purposes.
1430
1431	The default implementation returns the result of (a == b). It can be reimplemented
1432	for a certain type if the equality operator is not suitable for hashing purposes.
1433	This is for example the case if the equality operator uses qFuzzyCompare to compare
1434	floating point values.
1435	*/
1436
1437
1438	/*!
1439	\class QHash
1440	\inmodule QtCore
1441	\brief The QHash class is a template class that provides a hash-table-based dictionary.
1442
1443	\ingroup tools
1444	\ingroup shared
1445
1446	\reentrant
1447
1448	QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1449	stores (key, value) pairs and provides very fast lookup of the
1450	value associated with a key.
1451
1452	QHash provides very similar functionality to QMap. The
1453	differences are:
1454
1455	\list
1456	\li QHash provides faster lookups than QMap. (See \l{Algorithmic
1457	Complexity} for details.)
1458	\li When iterating over a QMap, the items are always sorted by
1459	key. With QHash, the items are arbitrarily ordered.
1460	\li The key type of a QMap must provide operator<(). The key
1461	type of a QHash must provide operator==() and a global
1462	hash function called qHash() (see \l{qHash}).
1463	\endlist
1464
1465	Here's an example QHash with QString keys and \c int values:
1466	\snippet code/src_corelib_tools_qhash.cpp 0
1467
1468	To insert a (key, value) pair into the hash, you can use operator[]():
1469
1470	\snippet code/src_corelib_tools_qhash.cpp 1
1471
1472	This inserts the following three (key, value) pairs into the
1473	QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1474	insert items into the hash is to use insert():
1475
1476	\snippet code/src_corelib_tools_qhash.cpp 2
1477
1478	To look up a value, use operator[]() or value():
1479
1480	\snippet code/src_corelib_tools_qhash.cpp 3
1481
1482	If there is no item with the specified key in the hash, these
1483	functions return a \l{default-constructed value}.
1484
1485	If you want to check whether the hash contains a particular key,
1486	use contains():
1487
1488	\snippet code/src_corelib_tools_qhash.cpp 4
1489
1490	There is also a value() overload that uses its second argument as
1491	a default value if there is no item with the specified key:
1492
1493	\snippet code/src_corelib_tools_qhash.cpp 5
1494
1495	In general, we recommend that you use contains() and value()
1496	rather than operator[]() for looking up a key in a hash. The
1497	reason is that operator[]() silently inserts an item into the
1498	hash if no item exists with the same key (unless the hash is
1499	const). For example, the following code snippet will create 1000
1500	items in memory:
1501
1502	\snippet code/src_corelib_tools_qhash.cpp 6
1503
1504	To avoid this problem, replace \c hash[i] with \c hash.value(i)
1505	in the code above.
1506
1507	Internally, QHash uses a hash table to perform lookups. This
1508	hash table automatically grows to
1509	provide fast lookups without wasting too much memory. You can
1510	still control the size of the hash table by calling reserve() if
1511	you already know approximately how many items the QHash will
1512	contain, but this isn't necessary to obtain good performance. You
1513	can also call capacity() to retrieve the hash table's size.
1514
1515	QHash will not shrink automatically if items are removed from the
1516	table. To minimize the memory used by the hash, call squeeze().
1517
1518	If you want to navigate through all the (key, value) pairs stored
1519	in a QHash, you can use an iterator. QHash provides both
1520	\l{Java-style iterators} (QHashIterator and QMutableHashIterator)
1521	and \l{STL-style iterators} (QHash::const_iterator and
1522	QHash::iterator). Here's how to iterate over a QHash<QString,
1523	int> using a Java-style iterator:
1524
1525	\snippet code/src_corelib_tools_qhash.cpp 7
1526
1527	Here's the same code, but using an STL-style iterator:
1528
1529	\snippet code/src_corelib_tools_qhash.cpp 8
1530
1531	QHash is unordered, so an iterator's sequence cannot be assumed
1532	to be predictable. If ordering by key is required, use a QMap.
1533
1534	A QHash allows only one value per key. If you call
1535	insert() with a key that already exists in the QHash, the
1536	previous value is erased. For example:
1537
1538	\snippet code/src_corelib_tools_qhash.cpp 9
1539
1540	If you need to store multiple entries for the same key in the
1541	hash table, use \l{QMultiHash}.
1542
1543	If you only need to extract the values from a hash (not the keys),
1544	you can also use range-based for:
1545
1546	\snippet code/src_corelib_tools_qhash.cpp 12
1547
1548	Items can be removed from the hash in several ways. One way is to
1549	call remove(); this will remove any item with the given key.
1550	Another way is to use QMutableHashIterator::remove(). In addition,
1551	you can clear the entire hash using clear().
1552
1553	QHash's key and value data types must be \l{assignable data
1554	types}. You cannot, for example, store a QWidget as a value;
1555	instead, store a QWidget *.
1556
1557	\target qHash
1558	\section2 The hashing function
1559
1560	A QHash's key type has additional requirements other than being an
1561	assignable data type: it must provide operator==(), and there must also be
1562	a hashing function that returns a hash value for an argument of the
1563	key's type.
1564
1565	The hashing function computes a numeric value based on a key. It
1566	can use any algorithm imaginable, as long as it always returns
1567	the same value if given the same argument. In other words, if
1568	\c{e1 == e2}, then \c{hash(e1) == hash(e2)} must hold as well.
1569	However, to obtain good performance, the hashing function should
1570	attempt to return different hash values for different keys to the
1571	largest extent possible.
1572
1573	A hashing function for a key type \c{K} may be provided in two
1574	different ways.
1575
1576	The first way is by having an overload of \c{qHash()} in \c{K}'s
1577	namespace. The \c{qHash()} function must have one of these signatures:
1578
1579	\snippet code/src_corelib_tools_qhash.cpp 32
1580
1581	The two-arguments overloads take an unsigned integer that should be used to
1582	seed the calculation of the hash function. This seed is provided by QHash
1583	in order to prevent a family of \l{algorithmic complexity attacks}.
1584
1585	\note In Qt 6 it is possible to define a \c{qHash()} overload
1586	taking only one argument; support for this is deprecated. Starting
1587	with Qt 7, it will be mandatory to use a two-arguments overload. If
1588	both a one-argument and a two-arguments overload are defined for a
1589	key type, the latter is used by QHash (note that you can simply
1590	define a two-arguments version, and use a default value for the
1591	seed parameter).
1592
1593	The second way to provide a hashing function is by specializing
1594	the \c{std::hash} class for the key type \c{K}, and providing a
1595	suitable function call operator for it:
1596
1597	\snippet code/src_corelib_tools_qhash.cpp 33
1598
1599	The seed argument has the same meaning as for \c{qHash()},
1600	and may be left out.
1601
1602	This second way allows to reuse the same hash function between
1603	QHash and the C++ Standard Library unordered associative containers.
1604	If both a \c{qHash()} overload and a \c{std::hash} specializations
1605	are provided for a type, then the \c{qHash()} overload is preferred.
1606
1607	Here's a partial list of the C++ and Qt types that can serve as keys in a
1608	QHash: any integer type (char, unsigned long, etc.), any pointer type,
1609	QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1610	defines a qHash() function that computes an adequate hash value. Many other
1611	Qt classes also declare a qHash overload for their type; please refer to
1612	the documentation of each class.
1613
1614	If you want to use other types as the key, make sure that you provide
1615	operator==() and a hash implementation.
1616
1617	The convenience qHashMulti() function can be used to implement
1618	qHash() for a custom type, where one usually wants to produce a
1619	hash value from multiple fields:
1620
1621	Example:
1622	\snippet code/src_corelib_tools_qhash.cpp 13
1623
1624	In the example above, we've relied on Qt's own implementation of
1625	qHash() for QString and QDate to give us a hash value for the
1626	employee's name and date of birth respectively.
1627
1628	Note that the implementation of the qHash() overloads offered by Qt
1629	may change at any time. You \b{must not} rely on the fact that qHash()
1630	will give the same results (for the same inputs) across different Qt
1631	versions.
1632
1633	\section2 Algorithmic complexity attacks
1634
1635	All hash tables are vulnerable to a particular class of denial of service
1636	attacks, in which the attacker carefully pre-computes a set of different
1637	keys that are going to be hashed in the same bucket of a hash table (or
1638	even have the very same hash value). The attack aims at getting the
1639	worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1640	\l{Algorithmic Complexity} for the details) when the data is fed into the
1641	table.
1642
1643	In order to avoid this worst-case behavior, the calculation of the hash
1644	value done by qHash() can be salted by a random seed, that nullifies the
1645	attack's extent. This seed is automatically generated by QHash once per
1646	process, and then passed by QHash as the second argument of the
1647	two-arguments overload of the qHash() function.
1648
1649	This randomization of QHash is enabled by default. Even though programs
1650	should never depend on a particular QHash ordering, there may be situations
1651	where you temporarily need deterministic behavior, for example for debugging or
1652	regression testing. To disable the randomization, define the environment
1653	variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1654	the QHashSeed::setDeterministicGlobalSeed() function.
1655
1656	\sa QHashIterator, QMutableHashIterator, QMap, QSet
1657	*/
1658
1659	/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1660
1661	Constructs an empty hash.
1662
1663	\sa clear()
1664	*/
1665
1666	/*!
1667	\fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1668
1669	Move-constructs a QHash instance, making it point at the same
1670	object that \a other was pointing to.
1671
1672	\since 5.2
1673	*/
1674
1675	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1676	\since 5.1
1677
1678	Constructs a hash with a copy of each of the elements in the
1679	initializer list \a list.
1680	*/
1681
1682	/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1683	\since 5.14
1684
1685	Constructs a hash with a copy of each of the elements in the iterator range
1686	[\a begin, \a end). Either the elements iterated by the range must be
1687	objects with \c{first} and \c{second} data members (like \c{std::pair}),
1688	convertible to \c Key and to \c T respectively; or the
1689	iterators must have \c{key()} and \c{value()} member functions, returning a
1690	key convertible to \c Key and a value convertible to \c T respectively.
1691	*/
1692
1693	/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1694
1695	Constructs a copy of \a other.
1696
1697	This operation occurs in \l{constant time}, because QHash is
1698	\l{implicitly shared}. This makes returning a QHash from a
1699	function very fast. If a shared instance is modified, it will be
1700	copied (copy-on-write), and this takes \l{linear time}.
1701
1702	\sa operator=()
1703	*/
1704
1705	/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1706
1707	Destroys the hash. References to the values in the hash and all
1708	iterators of this hash become invalid.
1709	*/
1710
1711	/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1712
1713	Assigns \a other to this hash and returns a reference to this hash.
1714	*/
1715
1716	/*!
1717	\fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1718
1719	Move-assigns \a other to this QHash instance.
1720
1721	\since 5.2
1722	*/
1723
1724	/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1725	\since 4.8
1726	\memberswap{hash}
1727	*/
1728
1729	/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1730	\since 4.8
1731	\memberswap{multi-hash}
1732	*/
1733
1734	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1735
1736	Returns \c true if \a other is equal to this hash; otherwise returns
1737	false.
1738
1739	Two hashes are considered equal if they contain the same (key,
1740	value) pairs.
1741
1742	This function requires the value type to implement \c operator==().
1743
1744	\sa operator!=()
1745	*/
1746
1747	/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1748
1749	Returns \c true if \a other is not equal to this hash; otherwise
1750	returns \c false.
1751
1752	Two hashes are considered equal if they contain the same (key,
1753	value) pairs.
1754
1755	This function requires the value type to implement \c operator==().
1756
1757	\sa operator==()
1758	*/
1759
1760	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::size() const
1761
1762	Returns the number of items in the hash.
1763
1764	\sa isEmpty(), count()
1765	*/
1766
1767	/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1768
1769	Returns \c true if the hash contains no items; otherwise returns
1770	false.
1771
1772	\sa size()
1773	*/
1774
1775	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::capacity() const
1776
1777	Returns the number of buckets in the QHash's internal hash table.
1778
1779	The sole purpose of this function is to provide a means of fine
1780	tuning QHash's memory usage. In general, you will rarely ever
1781	need to call this function. If you want to know how many items are
1782	in the hash, call size().
1783
1784	\sa reserve(), squeeze()
1785	*/
1786
1787	/*! \fn template <class Key, class T> float QHash<Key, T>::load_factor() const noexcept
1788
1789	Returns the current load factor of the QHash's internal hash table.
1790	This is the same as capacity()/size(). The implementation used
1791	will aim to keep the load factor between 0.25 and 0.5. This avoids
1792	having too many hash table collisions that would degrade performance.
1793
1794	Even with a low load factor, the implementation of the hash table has a
1795	very low memory overhead.
1796
1797	This method purely exists for diagnostic purposes and you should rarely
1798	need to call it yourself.
1799
1800	\sa reserve(), squeeze()
1801	*/
1802
1803
1804	/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(qsizetype size)
1805
1806	Ensures that the QHash's internal hash table has space to store at
1807	least \a size items without having to grow the hash table.
1808
1809	This implies that the hash table will contain at least 2 * \a size buckets
1810	to ensure good performance
1811
1812	This function is useful for code that needs to build a huge hash
1813	and wants to avoid repeated reallocation. For example:
1814
1815	\snippet code/src_corelib_tools_qhash.cpp 14
1816
1817	Ideally, \a size should be the maximum number of items expected
1818	in the hash. QHash will then choose the smallest possible
1819	number of buckets that will allow storing \a size items in the table
1820	without having to grow the internal hash table. If \a size
1821	is an underestimate, the worst that will happen is that the QHash
1822	will be a bit slower.
1823
1824	In general, you will rarely ever need to call this function.
1825	QHash's internal hash table automatically grows to
1826	provide good performance without wasting too much memory.
1827
1828	\sa squeeze(), capacity()
1829	*/
1830
1831	/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1832
1833	Reduces the size of the QHash's internal hash table to save
1834	memory.
1835
1836	The sole purpose of this function is to provide a means of fine
1837	tuning QHash's memory usage. In general, you will rarely ever
1838	need to call this function.
1839
1840	\sa reserve(), capacity()
1841	*/
1842
1843	/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1844
1845	\internal
1846
1847	Detaches this hash from any other hashes with which it may share
1848	data.
1849
1850	\sa isDetached()
1851	*/
1852
1853	/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1854
1855	\internal
1856
1857	Returns \c true if the hash's internal data isn't shared with any
1858	other hash object; otherwise returns \c false.
1859
1860	\sa detach()
1861	*/
1862
1863	/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1864
1865	\internal
1866
1867	Returns true if the internal hash table of this QHash is shared with \a other, otherwise false.
1868	*/
1869
1870	/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1871
1872	Removes all items from the hash and frees up all memory used by it.
1873
1874	\sa remove()
1875	*/
1876
1877	/*! \fn template <class Key, class T> bool QHash<Key, T>::remove(const Key &key)
1878
1879	Removes the item that has the \a key from the hash.
1880	Returns true if the key exists in the hash and the item has been removed,
1881	and false otherwise.
1882
1883	\sa clear(), take()
1884	*/
1885
1886	/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QHash<Key, T>::removeIf(Predicate pred)
1887	\since 6.1
1888
1889	Removes all elements for which the predicate \a pred returns true
1890	from the hash.
1891
1892	The function supports predicates which take either an argument of
1893	type \c{QHash<Key, T>::iterator}, or an argument of type
1894	\c{std::pair<const Key &, T &>}.
1895
1896	Returns the number of elements removed, if any.
1897
1898	\sa clear(), take()
1899	*/
1900
1901	/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1902
1903	Removes the item with the \a key from the hash and returns
1904	the value associated with it.
1905
1906	If the item does not exist in the hash, the function simply
1907	returns a \l{default-constructed value}.
1908
1909	If you don't use the return value, remove() is more efficient.
1910
1911	\sa remove()
1912	*/
1913
1914	/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1915
1916	Returns \c true if the hash contains an item with the \a key;
1917	otherwise returns \c false.
1918
1919	\sa count()
1920	*/
1921
1922	/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key) const
1923	\fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1924	\overload
1925
1926	Returns the value associated with the \a key.
1927
1928	If the hash contains no item with the \a key, the function
1929	returns \a defaultValue, or a \l{default-constructed value} if this
1930	parameter has not been supplied.
1931	*/
1932
1933	/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1934
1935	Returns the value associated with the \a key as a modifiable
1936	reference.
1937
1938	If the hash contains no item with the \a key, the function inserts
1939	a \l{default-constructed value} into the hash with the \a key, and
1940	returns a reference to it.
1941
1942	//! [qhash-iterator-invalidation-func-desc]
1943	\warning Returned iterators/references should be considered invalidated
1944	the next time you call a non-const function on the hash, or when the
1945	hash is destroyed.
1946	//! [qhash-iterator-invalidation-func-desc]
1947
1948	\sa insert(), value()
1949	*/
1950
1951	/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
1952
1953	\overload
1954
1955	Same as value().
1956	*/
1957
1958	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
1959
1960	Returns a list containing all the keys in the hash, in an
1961	arbitrary order.
1962
1963	The order is guaranteed to be the same as that used by values().
1964
1965	This function creates a new list, in \l {linear time}. The time and memory
1966	use that entails can be avoided by iterating from \l keyBegin() to
1967	\l keyEnd().
1968
1969	\sa values(), key()
1970	*/
1971
1972	/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
1973
1974	\overload
1975
1976	Returns a list containing all the keys associated with value \a
1977	value, in an arbitrary order.
1978
1979	This function can be slow (\l{linear time}), because QHash's
1980	internal data structure is optimized for fast lookup by key, not
1981	by value.
1982	*/
1983
1984	/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
1985
1986	Returns a list containing all the values in the hash, in an
1987	arbitrary order.
1988
1989	The order is guaranteed to be the same as that used by keys().
1990
1991	This function creates a new list, in \l {linear time}. The time and memory
1992	use that entails can be avoided by iterating from \l keyValueBegin() to
1993	\l keyValueEnd().
1994
1995	\sa keys(), value()
1996	*/
1997
1998	/*!
1999	\fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
2000	\fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
2001	\since 4.3
2002
2003	Returns the first key mapped to \a value. If the hash contains no item
2004	mapped to \a value, returns \a defaultKey, or a \l{default-constructed
2005	value}{default-constructed key} if this parameter has not been supplied.
2006
2007	This function can be slow (\l{linear time}), because QHash's
2008	internal data structure is optimized for fast lookup by key, not
2009	by value.
2010	*/
2011
2012	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count(const Key &key) const
2013
2014	Returns the number of items associated with the \a key.
2015
2016	\sa contains()
2017	*/
2018
2019	/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count() const
2020
2021	\overload
2022
2023	Same as size().
2024	*/
2025
2026	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
2027
2028	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
2029	the hash.
2030
2031	\include qhash.cpp qhash-iterator-invalidation-func-desc
2032
2033	\sa constBegin(), end()
2034	*/
2035
2036	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
2037
2038	\overload
2039
2040	\include qhash.cpp qhash-iterator-invalidation-func-desc
2041	*/
2042
2043	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
2044	\since 5.0
2045
2046	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2047	in the hash.
2048
2049	\include qhash.cpp qhash-iterator-invalidation-func-desc
2050
2051	\sa begin(), cend()
2052	*/
2053
2054	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
2055
2056	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2057	in the hash.
2058
2059	\include qhash.cpp qhash-iterator-invalidation-func-desc
2060
2061	\sa begin(), constEnd()
2062	*/
2063
2064	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
2065	\since 5.6
2066
2067	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
2068	in the hash.
2069
2070	\include qhash.cpp qhash-iterator-invalidation-func-desc
2071
2072	\sa keyEnd()
2073	*/
2074
2075	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
2076
2077	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
2078	after the last item in the hash.
2079
2080	\include qhash.cpp qhash-iterator-invalidation-func-desc
2081
2082	\sa begin(), constEnd()
2083	*/
2084
2085	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
2086
2087	\overload
2088
2089	\include qhash.cpp qhash-iterator-invalidation-func-desc
2090	*/
2091
2092	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
2093
2094	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2095	item after the last item in the hash.
2096
2097	\include qhash.cpp qhash-iterator-invalidation-func-desc
2098
2099	\sa constBegin(), end()
2100	*/
2101
2102	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
2103	\since 5.0
2104
2105	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2106	item after the last item in the hash.
2107
2108	\include qhash.cpp qhash-iterator-invalidation-func-desc
2109
2110	\sa cbegin(), end()
2111	*/
2112
2113	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
2114	\since 5.6
2115
2116	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2117	item after the last key in the hash.
2118
2119	\include qhash.cpp qhash-iterator-invalidation-func-desc
2120
2121	\sa keyBegin()
2122	*/
2123
2124	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
2125	\since 5.10
2126
2127	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2128	in the hash.
2129
2130	\include qhash.cpp qhash-iterator-invalidation-func-desc
2131
2132	\sa keyValueEnd()
2133	*/
2134
2135	/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
2136	\since 5.10
2137
2138	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2139	entry after the last entry in the hash.
2140
2141	\include qhash.cpp qhash-iterator-invalidation-func-desc
2142
2143	\sa keyValueBegin()
2144	*/
2145
2146	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
2147	\since 5.10
2148
2149	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2150	in the hash.
2151
2152	\include qhash.cpp qhash-iterator-invalidation-func-desc
2153
2154	\sa keyValueEnd()
2155	*/
2156
2157	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
2158	\since 5.10
2159
2160	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2161	in the hash.
2162
2163	\include qhash.cpp qhash-iterator-invalidation-func-desc
2164
2165	\sa keyValueBegin()
2166	*/
2167
2168	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
2169	\since 5.10
2170
2171	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2172	entry after the last entry in the hash.
2173
2174	\include qhash.cpp qhash-iterator-invalidation-func-desc
2175
2176	\sa keyValueBegin()
2177	*/
2178
2179	/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
2180	\since 5.10
2181
2182	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2183	entry after the last entry in the hash.
2184
2185	\include qhash.cpp qhash-iterator-invalidation-func-desc
2186
2187	\sa constKeyValueBegin()
2188	*/
2189
2190	/*! \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &
2191	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &
2192	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &&
2193	\fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &&
2194	\since 6.4
2195
2196	Returns a range object that allows iteration over this hash as
2197	key/value pairs. For instance, this range object can be used in a
2198	range-based for loop, in combination with a structured binding declaration:
2199
2200	\snippet code/src_corelib_tools_qhash.cpp 34
2201
2202	Note that both the key and the value obtained this way are
2203	references to the ones in the hash. Specifically, mutating the value
2204	will modify the hash itself.
2205
2206	\include qhash.cpp qhash-iterator-invalidation-func-desc
2207
2208	\sa QKeyValueIterator
2209	*/
2210
2211	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
2212	\since 5.7
2213
2214	Removes the (key, value) pair associated with the iterator \a pos
2215	from the hash, and returns an iterator to the next item in the
2216	hash.
2217
2218	This function never causes QHash to
2219	rehash its internal data structure. This means that it can safely
2220	be called while iterating, and won't affect the order of items in
2221	the hash. For example:
2222
2223	\snippet code/src_corelib_tools_qhash.cpp 15
2224
2225	\include qhash.cpp qhash-iterator-invalidation-func-desc
2226
2227	\sa remove(), take(), find()
2228	*/
2229
2230	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
2231
2232	Returns an iterator pointing to the item with the \a key in the
2233	hash.
2234
2235	If the hash contains no item with the \a key, the function
2236	returns end().
2237
2238	If the hash contains multiple items with the \a key, this
2239	function returns an iterator that points to the most recently
2240	inserted value. The other values are accessible by incrementing
2241	the iterator. For example, here's some code that iterates over all
2242	the items with the same key:
2243
2244	\snippet code/src_corelib_tools_qhash.cpp 16
2245
2246	\include qhash.cpp qhash-iterator-invalidation-func-desc
2247
2248	\sa value(), values()
2249	*/
2250
2251	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
2252
2253	\overload
2254
2255	\include qhash.cpp qhash-iterator-invalidation-func-desc
2256	*/
2257
2258	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
2259	\since 4.1
2260
2261	Returns an iterator pointing to the item with the \a key in the
2262	hash.
2263
2264	If the hash contains no item with the \a key, the function
2265	returns constEnd().
2266
2267	\include qhash.cpp qhash-iterator-invalidation-func-desc
2268
2269	\sa find()
2270	*/
2271
2272	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
2273
2274	Inserts a new item with the \a key and a value of \a value.
2275
2276	If there is already an item with the \a key, that item's value
2277	is replaced with \a value.
2278
2279	Returns an iterator pointing to the new/updated element.
2280
2281	\include qhash.cpp qhash-iterator-invalidation-func-desc
2282	*/
2283
2284	/*!
2285	\fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args)
2286	\fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args)
2287
2288	Inserts a new element into the container. This new element
2289	is constructed in-place using \a args as the arguments for its
2290	construction.
2291
2292	Returns an iterator pointing to the new element.
2293
2294	\include qhash.cpp qhash-iterator-invalidation-func-desc
2295	*/
2296
2297
2298	/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
2299	\since 5.15
2300
2301	Inserts all the items in the \a other hash into this hash.
2302
2303	If a key is common to both hashes, its value will be replaced with the
2304	value stored in \a other.
2305	*/
2306
2307	/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
2308
2309	This function is provided for STL compatibility. It is equivalent
2310	to isEmpty(), returning true if the hash is empty; otherwise
2311	returns \c false.
2312	*/
2313
2314	/*! \fn template <class Key, class T> std::pair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key)
2315	\since 5.7
2316
2317	Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
2318	are stored under \a key. If the range is empty then both iterators will be equal to end().
2319
2320	\include qhash.cpp qhash-iterator-invalidation-func-desc
2321	*/
2322
2323	/*!
2324	\fn template <class Key, class T> std::pair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const
2325	\overload
2326	\since 5.7
2327
2328	\include qhash.cpp qhash-iterator-invalidation-func-desc
2329	*/
2330
2331	/*! \typedef QHash::ConstIterator
2332
2333	Qt-style synonym for QHash::const_iterator.
2334	*/
2335
2336	/*! \typedef QHash::Iterator
2337
2338	Qt-style synonym for QHash::iterator.
2339	*/
2340
2341	/*! \typedef QHash::difference_type
2342
2343	Typedef for ptrdiff_t. Provided for STL compatibility.
2344	*/
2345
2346	/*! \typedef QHash::key_type
2347
2348	Typedef for Key. Provided for STL compatibility.
2349	*/
2350
2351	/*! \typedef QHash::mapped_type
2352
2353	Typedef for T. Provided for STL compatibility.
2354	*/
2355
2356	/*! \typedef QHash::size_type
2357
2358	Typedef for int. Provided for STL compatibility.
2359	*/
2360
2361	/*! \typedef QHash::iterator::difference_type
2362	\internal
2363	*/
2364
2365	/*! \typedef QHash::iterator::iterator_category
2366	\internal
2367	*/
2368
2369	/*! \typedef QHash::iterator::pointer
2370	\internal
2371	*/
2372
2373	/*! \typedef QHash::iterator::reference
2374	\internal
2375	*/
2376
2377	/*! \typedef QHash::iterator::value_type
2378	\internal
2379	*/
2380
2381	/*! \typedef QHash::const_iterator::difference_type
2382	\internal
2383	*/
2384
2385	/*! \typedef QHash::const_iterator::iterator_category
2386	\internal
2387	*/
2388
2389	/*! \typedef QHash::const_iterator::pointer
2390	\internal
2391	*/
2392
2393	/*! \typedef QHash::const_iterator::reference
2394	\internal
2395	*/
2396
2397	/*! \typedef QHash::const_iterator::value_type
2398	\internal
2399	*/
2400
2401	/*! \typedef QHash::key_iterator::difference_type
2402	\internal
2403	*/
2404
2405	/*! \typedef QHash::key_iterator::iterator_category
2406	\internal
2407	*/
2408
2409	/*! \typedef QHash::key_iterator::pointer
2410	\internal
2411	*/
2412
2413	/*! \typedef QHash::key_iterator::reference
2414	\internal
2415	*/
2416
2417	/*! \typedef QHash::key_iterator::value_type
2418	\internal
2419	*/
2420
2421	/*! \class QHash::iterator
2422	\inmodule QtCore
2423	\brief The QHash::iterator class provides an STL-style non-const iterator for QHash.
2424
2425	QHash\<Key, T\>::iterator allows you to iterate over a QHash
2426	and to modify the value (but not the key) associated
2427	with a particular key. If you want to iterate over a const QHash,
2428	you should use QHash::const_iterator. It is generally good
2429	practice to use QHash::const_iterator on a non-const QHash as
2430	well, unless you need to change the QHash through the iterator.
2431	Const iterators are slightly faster, and can improve code
2432	readability.
2433
2434	The default QHash::iterator constructor creates an uninitialized
2435	iterator. You must initialize it using a QHash function like
2436	QHash::begin(), QHash::end(), or QHash::find() before you can
2437	start iterating. Here's a typical loop that prints all the (key,
2438	value) pairs stored in a hash:
2439
2440	\snippet code/src_corelib_tools_qhash.cpp 17
2441
2442	Unlike QMap, which orders its items by key, QHash stores its
2443	items in an arbitrary order.
2444
2445	Here's an example that increments every value stored in the QHash
2446	by 2:
2447
2448	\snippet code/src_corelib_tools_qhash.cpp 18
2449
2450	To remove elements from a QHash you can use erase_if(QHash\<Key, T\> &map, Predicate pred):
2451
2452	\snippet code/src_corelib_tools_qhash.cpp 21
2453
2454	Multiple iterators can be used on the same hash. However, be aware
2455	that any modification performed directly on the QHash (inserting and
2456	removing items) can cause the iterators to become invalid.
2457
2458	Inserting items into the hash or calling methods such as QHash::reserve()
2459	or QHash::squeeze() can invalidate all iterators pointing into the hash.
2460	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2461	to grow/shrink its internal hash table.
2462	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2463
2464	If you need to keep iterators over a long period of time, we recommend
2465	that you use QMap rather than QHash.
2466
2467	\warning Iterators on implicitly shared containers do not work
2468	exactly like STL-iterators. You should avoid copying a container
2469	while iterators are active on that container. For more information,
2470	read \l{Implicit sharing iterator problem}.
2471
2472	\sa QHash::const_iterator, QHash::key_iterator, QHash::key_value_iterator
2473	*/
2474
2475	/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2476
2477	Constructs an uninitialized iterator.
2478
2479	Functions like key(), value(), and operator++() must not be
2480	called on an uninitialized iterator. Use operator=() to assign a
2481	value to it before using it.
2482
2483	\sa QHash::begin(), QHash::end()
2484	*/
2485
2486	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2487
2488	Returns the current item's key as a const reference.
2489
2490	There is no direct way of changing an item's key through an
2491	iterator, although it can be done by calling QHash::erase()
2492	followed by QHash::insert().
2493
2494	\sa value()
2495	*/
2496
2497	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2498
2499	Returns a modifiable reference to the current item's value.
2500
2501	You can change the value of an item by using value() on
2502	the left side of an assignment, for example:
2503
2504	\snippet code/src_corelib_tools_qhash.cpp 22
2505
2506	\sa key(), operator*()
2507	*/
2508
2509	/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2510
2511	Returns a modifiable reference to the current item's value.
2512
2513	Same as value().
2514
2515	\sa key()
2516	*/
2517
2518	/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2519
2520	Returns a pointer to the current item's value.
2521
2522	\sa value()
2523	*/
2524
2525	/*!
2526	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2527	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2528
2529	Returns \c true if \a other points to the same item as this
2530	iterator; otherwise returns \c false.
2531
2532	\sa operator!=()
2533	*/
2534
2535	/*!
2536	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2537	\fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2538
2539	Returns \c true if \a other points to a different item than this
2540	iterator; otherwise returns \c false.
2541
2542	\sa operator==()
2543	*/
2544
2545	/*!
2546	\fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2547
2548	The prefix ++ operator (\c{++i}) advances the iterator to the
2549	next item in the hash and returns an iterator to the new current
2550	item.
2551
2552	Calling this function on QHash::end() leads to undefined results.
2553	*/
2554
2555	/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2556
2557	\overload
2558
2559	The postfix ++ operator (\c{i++}) advances the iterator to the
2560	next item in the hash and returns an iterator to the previously
2561	current item.
2562	*/
2563
2564	/*! \class QHash::const_iterator
2565	\inmodule QtCore
2566	\brief The QHash::const_iterator class provides an STL-style const iterator for QHash.
2567
2568	QHash\<Key, T\>::const_iterator allows you to iterate over a
2569	QHash. If you want to modify the QHash as you
2570	iterate over it, you must use QHash::iterator instead. It is
2571	generally good practice to use QHash::const_iterator on a
2572	non-const QHash as well, unless you need to change the QHash
2573	through the iterator. Const iterators are slightly faster, and
2574	can improve code readability.
2575
2576	The default QHash::const_iterator constructor creates an
2577	uninitialized iterator. You must initialize it using a QHash
2578	function like QHash::cbegin(), QHash::cend(), or
2579	QHash::constFind() before you can start iterating. Here's a typical
2580	loop that prints all the (key, value) pairs stored in a hash:
2581
2582	\snippet code/src_corelib_tools_qhash.cpp 23
2583
2584	Unlike QMap, which orders its items by key, QHash stores its
2585	items in an arbitrary order. The only guarantee is that items that
2586	share the same key (because they were inserted using
2587	a QMultiHash) will appear consecutively, from the most
2588	recently to the least recently inserted value.
2589
2590	Multiple iterators can be used on the same hash. However, be aware
2591	that any modification performed directly on the QHash (inserting and
2592	removing items) can cause the iterators to become invalid.
2593
2594	Inserting items into the hash or calling methods such as QHash::reserve()
2595	or QHash::squeeze() can invalidate all iterators pointing into the hash.
2596	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2597	to grow/shrink its internal hash table.
2598	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2599
2600	You can however safely use iterators to remove entries from the hash
2601	using the QHash::erase() method. This function can safely be called while
2602	iterating, and won't affect the order of items in the hash.
2603
2604	\warning Iterators on implicitly shared containers do not work
2605	exactly like STL-iterators. You should avoid copying a container
2606	while iterators are active on that container. For more information,
2607	read \l{Implicit sharing iterator problem}.
2608
2609	\sa QHash::iterator, QHash::key_iterator, QHash::const_key_value_iterator
2610	*/
2611
2612	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2613
2614	Constructs an uninitialized iterator.
2615
2616	Functions like key(), value(), and operator++() must not be
2617	called on an uninitialized iterator. Use operator=() to assign a
2618	value to it before using it.
2619
2620	\sa QHash::constBegin(), QHash::constEnd()
2621	*/
2622
2623	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2624
2625	Constructs a copy of \a other.
2626	*/
2627
2628	/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2629
2630	Returns the current item's key.
2631
2632	\sa value()
2633	*/
2634
2635	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2636
2637	Returns the current item's value.
2638
2639	\sa key(), operator*()
2640	*/
2641
2642	/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2643
2644	Returns the current item's value.
2645
2646	Same as value().
2647
2648	\sa key()
2649	*/
2650
2651	/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2652
2653	Returns a pointer to the current item's value.
2654
2655	\sa value()
2656	*/
2657
2658	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2659
2660	Returns \c true if \a other points to the same item as this
2661	iterator; otherwise returns \c false.
2662
2663	\sa operator!=()
2664	*/
2665
2666	/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2667
2668	Returns \c true if \a other points to a different item than this
2669	iterator; otherwise returns \c false.
2670
2671	\sa operator==()
2672	*/
2673
2674	/*!
2675	\fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2676
2677	The prefix ++ operator (\c{++i}) advances the iterator to the
2678	next item in the hash and returns an iterator to the new current
2679	item.
2680
2681	Calling this function on QHash::end() leads to undefined results.
2682	*/
2683
2684	/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2685
2686	\overload
2687
2688	The postfix ++ operator (\c{i++}) advances the iterator to the
2689	next item in the hash and returns an iterator to the previously
2690	current item.
2691	*/
2692
2693	/*! \class QHash::key_iterator
2694	\inmodule QtCore
2695	\since 5.6
2696	\brief The QHash::key_iterator class provides an STL-style const iterator for QHash keys.
2697
2698	QHash::key_iterator is essentially the same as QHash::const_iterator
2699	with the difference that operator*() and operator->() return a key
2700	instead of a value.
2701
2702	For most uses QHash::iterator and QHash::const_iterator should be used,
2703	you can easily access the key by calling QHash::iterator::key():
2704
2705	\snippet code/src_corelib_tools_qhash.cpp 27
2706
2707	However, to have interoperability between QHash's keys and STL-style
2708	algorithms we need an iterator that dereferences to a key instead
2709	of a value. With QHash::key_iterator we can apply an algorithm to a
2710	range of keys without having to call QHash::keys(), which is inefficient
2711	as it costs one QHash iteration and memory allocation to create a temporary
2712	QList.
2713
2714	\snippet code/src_corelib_tools_qhash.cpp 28
2715
2716	QHash::key_iterator is const, it's not possible to modify the key.
2717
2718	The default QHash::key_iterator constructor creates an uninitialized
2719	iterator. You must initialize it using a QHash function like
2720	QHash::keyBegin() or QHash::keyEnd().
2721
2722	\warning Iterators on implicitly shared containers do not work
2723	exactly like STL-iterators. You should avoid copying a container
2724	while iterators are active on that container. For more information,
2725	read \l{Implicit sharing iterator problem}.
2726
2727	\sa QHash::const_iterator, QHash::iterator
2728	*/
2729
2730	/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2731
2732	Returns the current item's key.
2733	*/
2734
2735	/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2736
2737	Returns a pointer to the current item's key.
2738	*/
2739
2740	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2741
2742	Returns \c true if \a other points to the same item as this
2743	iterator; otherwise returns \c false.
2744
2745	\sa operator!=()
2746	*/
2747
2748	/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2749
2750	Returns \c true if \a other points to a different item than this
2751	iterator; otherwise returns \c false.
2752
2753	\sa operator==()
2754	*/
2755
2756	/*!
2757	\fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2758
2759	The prefix ++ operator (\c{++i}) advances the iterator to the
2760	next item in the hash and returns an iterator to the new current
2761	item.
2762
2763	Calling this function on QHash::keyEnd() leads to undefined results.
2764
2765	*/
2766
2767	/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2768
2769	\overload
2770
2771	The postfix ++ operator (\c{i++}) advances the iterator to the
2772	next item in the hash and returns an iterator to the previous
2773	item.
2774	*/
2775
2776	/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2777	Returns the underlying const_iterator this key_iterator is based on.
2778	*/
2779
2780	/*! \typedef QHash::const_key_value_iterator
2781	\inmodule QtCore
2782	\since 5.10
2783	\brief The QHash::const_key_value_iterator typedef provides an STL-style const iterator for QHash.
2784
2785	QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2786	with the difference that operator*() returns a key/value pair instead of a
2787	value.
2788
2789	\sa QKeyValueIterator
2790	*/
2791
2792	/*! \typedef QHash::key_value_iterator
2793	\inmodule QtCore
2794	\since 5.10
2795	\brief The QHash::key_value_iterator typedef provides an STL-style iterator for QHash.
2796
2797	QHash::key_value_iterator is essentially the same as QHash::iterator
2798	with the difference that operator*() returns a key/value pair instead of a
2799	value.
2800
2801	\sa QKeyValueIterator
2802	*/
2803
2804	/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2805	\relates QHash
2806
2807	Writes the hash \a hash to stream \a out.
2808
2809	This function requires the key and value types to implement \c
2810	operator<<().
2811
2812	\sa {Serializing Qt Data Types}
2813	*/
2814
2815	/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2816	\relates QHash
2817
2818	Reads a hash from stream \a in into \a hash.
2819
2820	This function requires the key and value types to implement \c
2821	operator>>().
2822
2823	\sa {Serializing Qt Data Types}
2824	*/
2825
2826	/*! \class QMultiHash
2827	\inmodule QtCore
2828	\brief The QMultiHash class provides a multi-valued hash table.
2829
2830	\ingroup tools
2831	\ingroup shared
2832
2833	\reentrant
2834
2835	QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2836	It provides a hash table that allows multiple values for the same key.
2837
2838	QMultiHash mostly mirrors QHash's API. For example, you can use isEmpty() to test
2839	whether the hash is empty, and you can traverse a QMultiHash using
2840	QHash's iterator classes (for example, QHashIterator). But opposed to
2841	QHash, it provides an insert() function that allows the insertion of
2842	multiple items with the same key. The replace() function corresponds to
2843	QHash::insert(). It also provides convenient operator+() and
2844	operator+=().
2845
2846	Unlike QMultiMap, QMultiHash does not provide ordering of the
2847	inserted items. The only guarantee is that items that
2848	share the same key will appear consecutively, from the most
2849	recently to the least recently inserted value.
2850
2851	Example:
2852	\snippet code/src_corelib_tools_qhash.cpp 24
2853
2854	Unlike QHash, QMultiHash provides no operator[]. Use value() or
2855	replace() if you want to access the most recently inserted item
2856	with a certain key.
2857
2858	If you want to retrieve all the values for a single key, you can
2859	use values(const Key &key), which returns a QList<T>:
2860
2861	\snippet code/src_corelib_tools_qhash.cpp 25
2862
2863	The items that share the same key are available from most
2864	recently to least recently inserted.
2865
2866	A more efficient approach is to call find() to get
2867	the STL-style iterator for the first item with a key and iterate from
2868	there:
2869
2870	\snippet code/src_corelib_tools_qhash.cpp 26
2871
2872	QMultiHash's key and value data types must be \l{assignable data
2873	types}. You cannot, for example, store a QWidget as a value;
2874	instead, store a QWidget *. In addition, QMultiHash's key type
2875	must provide operator==(), and there must also be a qHash() function
2876	in the type's namespace that returns a hash value for an argument of the
2877	key's type. See the QHash documentation for details.
2878
2879	\sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2880	*/
2881
2882	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2883
2884	Constructs an empty hash.
2885	*/
2886
2887	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2888	\since 5.1
2889
2890	Constructs a multi-hash with a copy of each of the elements in the
2891	initializer list \a list.
2892	*/
2893
2894	/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2895
2896	Constructs a copy of \a other (which can be a QHash or a
2897	QMultiHash).
2898	*/
2899
2900	/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
2901	\since 5.14
2902
2903	Constructs a multi-hash with a copy of each of the elements in the iterator range
2904	[\a begin, \a end). Either the elements iterated by the range must be
2905	objects with \c{first} and \c{second} data members (like \c{std::pair}),
2906	convertible to \c Key and to \c T respectively; or the
2907	iterators must have \c{key()} and \c{value()} member functions, returning a
2908	key convertible to \c Key and a value convertible to \c T respectively.
2909	*/
2910
2911	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2912
2913	Inserts a new item with the \a key and a value of \a value.
2914
2915	If there is already an item with the \a key, that item's value
2916	is replaced with \a value.
2917
2918	If there are multiple items with the \a key, the most
2919	recently inserted item's value is replaced with \a value.
2920
2921	Returns an iterator pointing to the new/updated element.
2922
2923	\include qhash.cpp qhash-iterator-invalidation-func-desc
2924
2925	\sa insert()
2926	*/
2927
2928	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2929
2930	Inserts a new item with the \a key and a value of \a value.
2931
2932	If there is already an item with the same key in the hash, this
2933	function will simply create a new one. (This behavior is
2934	different from replace(), which overwrites the value of an
2935	existing item.)
2936
2937	Returns an iterator pointing to the new element.
2938
2939	\include qhash.cpp qhash-iterator-invalidation-func-desc
2940
2941	\sa replace()
2942	*/
2943
2944	/*!
2945	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args)
2946	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args)
2947
2948	Inserts a new element into the container. This new element
2949	is constructed in-place using \a args as the arguments for its
2950	construction.
2951
2952	If there is already an item with the same key in the hash, this
2953	function will simply create a new one. (This behavior is
2954	different from replace(), which overwrites the value of an
2955	existing item.)
2956
2957	Returns an iterator pointing to the new element.
2958
2959	\include qhash.cpp qhash-iterator-invalidation-func-desc
2960
2961	\sa insert
2962	*/
2963
2964	/*!
2965	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args)
2966	\fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args)
2967
2968	Inserts a new element into the container. This new element
2969	is constructed in-place using \a args as the arguments for its
2970	construction.
2971
2972	If there is already an item with the same key in the hash, that item's
2973	value is replaced with a value constructed from \a args.
2974
2975	Returns an iterator pointing to the new element.
2976
2977	\include qhash.cpp qhash-iterator-invalidation-func-desc
2978
2979	\sa replace, emplace
2980	*/
2981
2982
2983	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
2984	\since 5.13
2985
2986	Inserts all the items in the \a other hash into this hash
2987	and returns a reference to this hash.
2988
2989	\sa insert()
2990	*/
2991
2992
2993	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QHash<Key, T> &other)
2994	\since 6.0
2995
2996	Inserts all the items in the \a other hash into this hash
2997	and returns a reference to this hash.
2998
2999	\sa insert()
3000	*/
3001
3002	/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
3003	\since 5.13
3004
3005	Returns a list containing all the keys in the map. Keys that occur multiple
3006	times in the map occur only once in the returned list.
3007
3008	\sa keys(), values()
3009	*/
3010
3011	/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key) const
3012	\fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue) const
3013
3014	Returns the value associated with the \a key.
3015
3016	If the hash contains no item with the \a key, the function
3017	returns \a defaultValue, or a \l{default-constructed value} if this
3018	parameter has not been supplied.
3019
3020	If there are multiple
3021	items for the \a key in the hash, the value of the most recently
3022	inserted one is returned.
3023	*/
3024
3025	/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
3026	\overload
3027
3028	Returns a list of all the values associated with the \a key,
3029	from the most recently inserted to the least recently inserted.
3030
3031	\sa count(), insert()
3032	*/
3033
3034	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::operator[](const Key &key)
3035
3036	Returns the value associated with the \a key as a modifiable reference.
3037
3038	If the hash contains no item with the \a key, the function inserts
3039	a \l{default-constructed value} into the hash with the \a key, and
3040	returns a reference to it.
3041
3042	If the hash contains multiple items with the \a key, this function returns
3043	a reference to the most recently inserted value.
3044
3045	\include qhash.cpp qhash-iterator-invalidation-func-desc
3046
3047	\sa insert(), value()
3048	*/
3049
3050	/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
3051
3052	Inserts all the items in the \a other hash into this hash
3053	and returns a reference to this hash.
3054
3055	\sa unite(), insert()
3056	*/
3057
3058	/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
3059
3060	Returns a hash that contains all the items in this hash in
3061	addition to all the items in \a other. If a key is common to both
3062	hashes, the resulting hash will contain the key multiple times.
3063
3064	\sa operator+=()
3065	*/
3066
3067	/*!
3068	\fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
3069	\since 4.3
3070
3071	Returns \c true if the hash contains an item with the \a key and
3072	\a value; otherwise returns \c false.
3073
3074	\sa contains()
3075	*/
3076
3077	/*!
3078	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key)
3079	\since 4.3
3080
3081	Removes all the items that have the \a key from the hash.
3082	Returns the number of items removed.
3083
3084	\sa remove()
3085	*/
3086
3087	/*!
3088	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key, const T &value)
3089	\since 4.3
3090
3091	Removes all the items that have the \a key and the value \a
3092	value from the hash. Returns the number of items removed.
3093
3094	\sa remove()
3095	*/
3096
3097	/*!
3098	\fn template <class Key, class T> void QMultiHash<Key, T>::clear()
3099	\since 4.3
3100
3101	Removes all items from the hash and frees up all memory used by it.
3102
3103	\sa remove()
3104	*/
3105
3106	/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QMultiHash<Key, T>::removeIf(Predicate pred)
3107	\since 6.1
3108
3109	Removes all elements for which the predicate \a pred returns true
3110	from the multi hash.
3111
3112	The function supports predicates which take either an argument of
3113	type \c{QMultiHash<Key, T>::iterator}, or an argument of type
3114	\c{std::pair<const Key &, T &>}.
3115
3116	Returns the number of elements removed, if any.
3117
3118	\sa clear(), take()
3119	*/
3120
3121	/*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key)
3122
3123	Removes the item with the \a key from the hash and returns
3124	the value associated with it.
3125
3126	If the item does not exist in the hash, the function simply
3127	returns a \l{default-constructed value}. If there are multiple
3128	items for \a key in the hash, only the most recently inserted one
3129	is removed.
3130
3131	If you don't use the return value, remove() is more efficient.
3132
3133	\sa remove()
3134	*/
3135
3136	/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::keys() const
3137
3138	Returns a list containing all the keys in the hash, in an
3139	arbitrary order. Keys that occur multiple times in the hash
3140	also occur multiple times in the list.
3141
3142	The order is guaranteed to be the same as that used by values().
3143
3144	This function creates a new list, in \l {linear time}. The time and memory
3145	use that entails can be avoided by iterating from \l keyBegin() to
3146	\l keyEnd().
3147
3148	\sa values(), key()
3149	*/
3150
3151	/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values() const
3152
3153	Returns a list containing all the values in the hash, in an
3154	arbitrary order. If a key is associated with multiple values, all of
3155	its values will be in the list, and not just the most recently
3156	inserted one.
3157
3158	The order is guaranteed to be the same as that used by keys().
3159
3160	This function creates a new list, in \l {linear time}. The time and memory
3161	use that entails can be avoided by iterating from \l keyValueBegin() to
3162	\l keyValueEnd().
3163
3164	\sa keys(), value()
3165	*/
3166
3167	/*!
3168	\fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value) const
3169	\fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey) const
3170	\since 4.3
3171
3172	Returns the first key mapped to \a value. If the hash contains no item
3173	mapped to \a value, returns \a defaultKey, or a \l{default-constructed
3174	value}{default-constructed key} if this parameter has not been supplied.
3175
3176	This function can be slow (\l{linear time}), because QMultiHash's
3177	internal data structure is optimized for fast lookup by key, not
3178	by value.
3179	*/
3180
3181	/*!
3182	\fn template <class Key, class T> qsizetype QMultiHash<Key, T>::count(const Key &key, const T &value) const
3183	\since 4.3
3184
3185	Returns the number of items with the \a key and \a value.
3186
3187	\sa count()
3188	*/
3189
3190	/*!
3191	\fn template <class Key, class T> typename QMultiHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
3192	\since 4.3
3193
3194	Returns an iterator pointing to the item with the \a key and \a value.
3195	If the hash contains no such item, the function returns end().
3196
3197	If the hash contains multiple items with the \a key and \a value, the
3198	iterator returned points to the most recently inserted item.
3199
3200	\include qhash.cpp qhash-iterator-invalidation-func-desc
3201	*/
3202
3203	/*!
3204	\fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
3205	\since 4.3
3206	\overload
3207
3208	\include qhash.cpp qhash-iterator-invalidation-func-desc
3209	*/
3210
3211	/*!
3212	\fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
3213	\since 4.3
3214
3215	Returns an iterator pointing to the item with the \a key and the
3216	\a value in the hash.
3217
3218	If the hash contains no such item, the function returns
3219	constEnd().
3220
3221	\include qhash.cpp qhash-iterator-invalidation-func-desc
3222	*/
3223
3224	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin()
3225
3226	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
3227	the hash.
3228
3229	\include qhash.cpp qhash-iterator-invalidation-func-desc
3230
3231	\sa constBegin(), end()
3232	*/
3233
3234	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::begin() const
3235
3236	\overload
3237
3238	\include qhash.cpp qhash-iterator-invalidation-func-desc
3239	*/
3240
3241	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const
3242	\since 5.0
3243
3244	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3245	in the hash.
3246
3247	\include qhash.cpp qhash-iterator-invalidation-func-desc
3248
3249	\sa begin(), cend()
3250	*/
3251
3252	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constBegin() const
3253
3254	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3255	in the hash.
3256
3257	\include qhash.cpp qhash-iterator-invalidation-func-desc
3258
3259	\sa begin(), constEnd()
3260	*/
3261
3262	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyBegin() const
3263	\since 5.6
3264
3265	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
3266	in the hash.
3267
3268	\include qhash.cpp qhash-iterator-invalidation-func-desc
3269
3270	\sa keyEnd()
3271	*/
3272
3273	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::end()
3274
3275	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
3276	after the last item in the hash.
3277
3278	\include qhash.cpp qhash-iterator-invalidation-func-desc
3279
3280	\sa begin(), constEnd()
3281	*/
3282
3283	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::end() const
3284
3285	\overload
3286	*/
3287
3288	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constEnd() const
3289
3290	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3291	item after the last item in the hash.
3292
3293	\include qhash.cpp qhash-iterator-invalidation-func-desc
3294
3295	\sa constBegin(), end()
3296	*/
3297
3298	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cend() const
3299	\since 5.0
3300
3301	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3302	item after the last item in the hash.
3303
3304	\include qhash.cpp qhash-iterator-invalidation-func-desc
3305
3306	\sa cbegin(), end()
3307	*/
3308
3309	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyEnd() const
3310	\since 5.6
3311
3312	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3313	item after the last key in the hash.
3314
3315	\include qhash.cpp qhash-iterator-invalidation-func-desc
3316
3317	\sa keyBegin()
3318	*/
3319
3320	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueBegin()
3321	\since 5.10
3322
3323	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3324	in the hash.
3325
3326	\include qhash.cpp qhash-iterator-invalidation-func-desc
3327
3328	\sa keyValueEnd()
3329	*/
3330
3331	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueEnd()
3332	\since 5.10
3333
3334	Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3335	entry after the last entry in the hash.
3336
3337	\include qhash.cpp qhash-iterator-invalidation-func-desc
3338
3339	\sa keyValueBegin()
3340	*/
3341
3342	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueBegin() const
3343	\since 5.10
3344
3345	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3346	in the hash.
3347
3348	\include qhash.cpp qhash-iterator-invalidation-func-desc
3349
3350	\sa keyValueEnd()
3351	*/
3352
3353	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueBegin() const
3354	\since 5.10
3355
3356	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3357	in the hash.
3358
3359	\include qhash.cpp qhash-iterator-invalidation-func-desc
3360
3361	\sa keyValueBegin()
3362	*/
3363
3364	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueEnd() const
3365	\since 5.10
3366
3367	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3368	entry after the last entry in the hash.
3369
3370	\include qhash.cpp qhash-iterator-invalidation-func-desc
3371
3372	\sa keyValueBegin()
3373	*/
3374
3375	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueEnd() const
3376	\since 5.10
3377
3378	Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3379	entry after the last entry in the hash.
3380
3381	\include qhash.cpp qhash-iterator-invalidation-func-desc
3382
3383	\sa constKeyValueBegin()
3384	*/
3385
3386	/*! \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &
3387	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &
3388	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &&
3389	\fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &&
3390	\since 6.4
3391
3392	Returns a range object that allows iteration over this hash as
3393	key/value pairs. For instance, this range object can be used in a
3394	range-based for loop, in combination with a structured binding declaration:
3395
3396	\snippet code/src_corelib_tools_qhash.cpp 35
3397
3398	Note that both the key and the value obtained this way are
3399	references to the ones in the hash. Specifically, mutating the value
3400	will modify the hash itself.
3401
3402	\include qhash.cpp qhash-iterator-invalidation-func-desc
3403
3404	\sa QKeyValueIterator
3405	*/
3406
3407	/*! \class QMultiHash::iterator
3408	\inmodule QtCore
3409	\brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash.
3410
3411	QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash
3412	and to modify the value (but not the key) associated
3413	with a particular key. If you want to iterate over a const QMultiHash,
3414	you should use QMultiHash::const_iterator. It is generally good
3415	practice to use QMultiHash::const_iterator on a non-const QMultiHash as
3416	well, unless you need to change the QMultiHash through the iterator.
3417	Const iterators are slightly faster, and can improve code
3418	readability.
3419
3420	The default QMultiHash::iterator constructor creates an uninitialized
3421	iterator. You must initialize it using a QMultiHash function like
3422	QMultiHash::begin(), QMultiHash::end(), or QMultiHash::find() before you can
3423	start iterating. Here's a typical loop that prints all the (key,
3424	value) pairs stored in a hash:
3425
3426	\snippet code/src_corelib_tools_qhash.cpp 17
3427
3428	Unlike QMap, which orders its items by key, QMultiHash stores its
3429	items in an arbitrary order.
3430
3431	Here's an example that increments every value stored in the QMultiHash
3432	by 2:
3433
3434	\snippet code/src_corelib_tools_qhash.cpp 18
3435
3436	To remove elements from a QMultiHash you can use erase_if(QMultiHash\<Key, T\> &map, Predicate pred):
3437
3438	\snippet code/src_corelib_tools_qhash.cpp 21
3439
3440	Multiple iterators can be used on the same hash. However, be aware
3441	that any modification performed directly on the QHash (inserting and
3442	removing items) can cause the iterators to become invalid.
3443
3444	Inserting items into the hash or calling methods such as QHash::reserve()
3445	or QHash::squeeze() can invalidate all iterators pointing into the hash.
3446	Iterators are guaranteed to stay valid only as long as the QHash doesn't have
3447	to grow/shrink its internal hash table.
3448	Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
3449
3450	If you need to keep iterators over a long period of time, we recommend
3451	that you use QMultiMap rather than QHash.
3452
3453	\warning Iterators on implicitly shared containers do not work
3454	exactly like STL-iterators. You should avoid copying a container
3455	while iterators are active on that container. For more information,
3456	read \l{Implicit sharing iterator problem}.
3457
3458	\sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMultiHash::key_value_iterator
3459	*/
3460
3461	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator::iterator()
3462
3463	Constructs an uninitialized iterator.
3464
3465	Functions like key(), value(), and operator++() must not be
3466	called on an uninitialized iterator. Use operator=() to assign a
3467	value to it before using it.
3468
3469	\sa QMultiHash::begin(), QMultiHash::end()
3470	*/
3471
3472	/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::iterator::key() const
3473
3474	Returns the current item's key as a const reference.
3475
3476	There is no direct way of changing an item's key through an
3477	iterator, although it can be done by calling QMultiHash::erase()
3478	followed by QMultiHash::insert().
3479
3480	\sa value()
3481	*/
3482
3483	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::value() const
3484
3485	Returns a modifiable reference to the current item's value.
3486
3487	You can change the value of an item by using value() on
3488	the left side of an assignment, for example:
3489
3490	\snippet code/src_corelib_tools_qhash.cpp 22
3491
3492	\sa key(), operator*()
3493	*/
3494
3495	/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::operator*() const
3496
3497	Returns a modifiable reference to the current item's value.
3498
3499	Same as value().
3500
3501	\sa key()
3502	*/
3503
3504	/*! \fn template <class Key, class T> T *QMultiHash<Key, T>::iterator::operator->() const
3505
3506	Returns a pointer to the current item's value.
3507
3508	\sa value()
3509	*/
3510
3511	/*!
3512	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const iterator &other) const
3513	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const const_iterator &other) const
3514
3515	Returns \c true if \a other points to the same item as this
3516	iterator; otherwise returns \c false.
3517
3518	\sa operator!=()
3519	*/
3520
3521	/*!
3522	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const iterator &other) const
3523	\fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const const_iterator &other) const
3524
3525	Returns \c true if \a other points to a different item than this
3526	iterator; otherwise returns \c false.
3527
3528	\sa operator==()
3529	*/
3530
3531	/*!
3532	\fn template <class Key, class T> QMultiHash<Key, T>::iterator &QMultiHash<Key, T>::iterator::operator++()
3533
3534	The prefix ++ operator (\c{++i}) advances the iterator to the
3535	next item in the hash and returns an iterator to the new current
3536	item.
3537
3538	Calling this function on QMultiHash::end() leads to undefined results.
3539	*/
3540
3541	/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::iterator::operator++(int)
3542
3543	\overload
3544
3545	The postfix ++ operator (\c{i++}) advances the iterator to the
3546	next item in the hash and returns an iterator to the previously
3547	current item.
3548	*/
3549
3550	/*! \class QMultiHash::const_iterator
3551	\inmodule QtCore
3552	\brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash.
3553
3554	QMultiHash\<Key, T\>::const_iterator allows you to iterate over a
3555	QMultiHash. If you want to modify the QMultiHash as you
3556	iterate over it, you must use QMultiHash::iterator instead. It is
3557	generally good practice to use QMultiHash::const_iterator on a
3558	non-const QMultiHash as well, unless you need to change the QMultiHash
3559	through the iterator. Const iterators are slightly faster, and
3560	can improve code readability.
3561
3562	The default QMultiHash::const_iterator constructor creates an
3563	uninitialized iterator. You must initialize it using a QMultiHash
3564	function like QMultiHash::cbegin(), QMultiHash::cend(), or
3565	QMultiHash::constFind() before you can start iterating. Here's a typical
3566	loop that prints all the (key, value) pairs stored in a hash:
3567
3568	\snippet code/src_corelib_tools_qhash.cpp 23
3569
3570	Unlike QMap, which orders its items by key, QMultiHash stores its
3571	items in an arbitrary order. The only guarantee is that items that
3572	share the same key (because they were inserted using
3573	a QMultiHash) will appear consecutively, from the most
3574	recently to the least recently inserted value.
3575
3576	Multiple iterators can be used on the same hash. However, be aware
3577	that any modification performed directly on the QMultiHash (inserting and
3578	removing items) can cause the iterators to become invalid.
3579
3580	Inserting items into the hash or calling methods such as QMultiHash::reserve()
3581	or QMultiHash::squeeze() can invalidate all iterators pointing into the hash.
3582	Iterators are guaranteed to stay valid only as long as the QMultiHash doesn't have
3583	to grow/shrink it's internal hash table.
3584	Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior.
3585
3586	If you need to keep iterators over a long period of time, we recommend
3587	that you use QMultiMap rather than QMultiHash.
3588
3589	\warning Iterators on implicitly shared containers do not work
3590	exactly like STL-iterators. You should avoid copying a container
3591	while iterators are active on that container. For more information,
3592	read \l{Implicit sharing iterator problem}.
3593
3594	\sa QMultiHash::iterator, QMultiHash::key_iterator, QMultiHash::const_key_value_iterator
3595	*/
3596
3597	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator()
3598
3599	Constructs an uninitialized iterator.
3600
3601	Functions like key(), value(), and operator++() must not be
3602	called on an uninitialized iterator. Use operator=() to assign a
3603	value to it before using it.
3604
3605	\sa QMultiHash::constBegin(), QMultiHash::constEnd()
3606	*/
3607
3608	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator(const iterator &other)
3609
3610	Constructs a copy of \a other.
3611	*/
3612
3613	/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::const_iterator::key() const
3614
3615	Returns the current item's key.
3616
3617	\sa value()
3618	*/
3619
3620	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::value() const
3621
3622	Returns the current item's value.
3623
3624	\sa key(), operator*()
3625	*/
3626
3627	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::operator*() const
3628
3629	Returns the current item's value.
3630
3631	Same as value().
3632
3633	\sa key()
3634	*/
3635
3636	/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::const_iterator::operator->() const
3637
3638	Returns a pointer to the current item's value.
3639
3640	\sa value()
3641	*/
3642
3643	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
3644
3645	Returns \c true if \a other points to the same item as this
3646	iterator; otherwise returns \c false.
3647
3648	\sa operator!=()
3649	*/
3650
3651	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
3652
3653	Returns \c true if \a other points to a different item than this
3654	iterator; otherwise returns \c false.
3655
3656	\sa operator==()
3657	*/
3658
3659	/*!
3660	\fn template <class Key, class T> QMultiHash<Key, T>::const_iterator &QMultiHash<Key, T>::const_iterator::operator++()
3661
3662	The prefix ++ operator (\c{++i}) advances the iterator to the
3663	next item in the hash and returns an iterator to the new current
3664	item.
3665
3666	Calling this function on QMultiHash::end() leads to undefined results.
3667	*/
3668
3669	/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_iterator::operator++(int)
3670
3671	\overload
3672
3673	The postfix ++ operator (\c{i++}) advances the iterator to the
3674	next item in the hash and returns an iterator to the previously
3675	current item.
3676	*/
3677
3678	/*! \class QMultiHash::key_iterator
3679	\inmodule QtCore
3680	\since 5.6
3681	\brief The QMultiHash::key_iterator class provides an STL-style const iterator for QMultiHash keys.
3682
3683	QMultiHash::key_iterator is essentially the same as QMultiHash::const_iterator
3684	with the difference that operator*() and operator->() return a key
3685	instead of a value.
3686
3687	For most uses QMultiHash::iterator and QMultiHash::const_iterator should be used,
3688	you can easily access the key by calling QMultiHash::iterator::key():
3689
3690	\snippet code/src_corelib_tools_qhash.cpp 27
3691
3692	However, to have interoperability between QMultiHash's keys and STL-style
3693	algorithms we need an iterator that dereferences to a key instead
3694	of a value. With QMultiHash::key_iterator we can apply an algorithm to a
3695	range of keys without having to call QMultiHash::keys(), which is inefficient
3696	as it costs one QMultiHash iteration and memory allocation to create a temporary
3697	QList.
3698
3699	\snippet code/src_corelib_tools_qhash.cpp 28
3700
3701	QMultiHash::key_iterator is const, it's not possible to modify the key.
3702
3703	The default QMultiHash::key_iterator constructor creates an uninitialized
3704	iterator. You must initialize it using a QMultiHash function like
3705	QMultiHash::keyBegin() or QMultiHash::keyEnd().
3706
3707	\warning Iterators on implicitly shared containers do not work
3708	exactly like STL-iterators. You should avoid copying a container
3709	while iterators are active on that container. For more information,
3710	read \l{Implicit sharing iterator problem}.
3711
3712	\sa QMultiHash::const_iterator, QMultiHash::iterator
3713	*/
3714
3715	/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::key_iterator::operator*() const
3716
3717	Returns the current item's key.
3718	*/
3719
3720	/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::key_iterator::operator->() const
3721
3722	Returns a pointer to the current item's key.
3723	*/
3724
3725	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator==(key_iterator other) const
3726
3727	Returns \c true if \a other points to the same item as this
3728	iterator; otherwise returns \c false.
3729
3730	\sa operator!=()
3731	*/
3732
3733	/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator!=(key_iterator other) const
3734
3735	Returns \c true if \a other points to a different item than this
3736	iterator; otherwise returns \c false.
3737
3738	\sa operator==()
3739	*/
3740
3741	/*!
3742	\fn template <class Key, class T> QMultiHash<Key, T>::key_iterator &QMultiHash<Key, T>::key_iterator::operator++()
3743
3744	The prefix ++ operator (\c{++i}) advances the iterator to the
3745	next item in the hash and returns an iterator to the new current
3746	item.
3747
3748	Calling this function on QMultiHash::keyEnd() leads to undefined results.
3749	*/
3750
3751	/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::key_iterator::operator++(int)
3752
3753	\overload
3754
3755	The postfix ++ operator (\c{i++}) advances the iterator to the
3756	next item in the hash and returns an iterator to the previous
3757	item.
3758	*/
3759
3760	/*! \fn template <class Key, class T> const_iterator QMultiHash<Key, T>::key_iterator::base() const
3761	Returns the underlying const_iterator this key_iterator is based on.
3762	*/
3763
3764	/*! \typedef QMultiHash::const_key_value_iterator
3765	\inmodule QtCore
3766	\since 5.10
3767	\brief The QMultiHash::const_key_value_iterator typedef provides an STL-style const iterator for QMultiHash.
3768
3769	QMultiHash::const_key_value_iterator is essentially the same as QMultiHash::const_iterator
3770	with the difference that operator*() returns a key/value pair instead of a
3771	value.
3772
3773	\sa QKeyValueIterator
3774	*/
3775
3776	/*! \typedef QMultiHash::key_value_iterator
3777	\inmodule QtCore
3778	\since 5.10
3779	\brief The QMultiHash::key_value_iterator typedef provides an STL-style iterator for QMultiHash.
3780
3781	QMultiHash::key_value_iterator is essentially the same as QMultiHash::iterator
3782	with the difference that operator*() returns a key/value pair instead of a
3783	value.
3784
3785	\sa QKeyValueIterator
3786	*/
3787
3788	/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiHash<Key, T>& hash)
3789	\relates QMultiHash
3790
3791	Writes the hash \a hash to stream \a out.
3792
3793	This function requires the key and value types to implement \c
3794	operator<<().
3795
3796	\sa {Serializing Qt Data Types}
3797	*/
3798
3799	/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiHash<Key, T> &hash)
3800	\relates QMultiHash
3801
3802	Reads a hash from stream \a in into \a hash.
3803
3804	This function requires the key and value types to implement \c
3805	operator>>().
3806
3807	\sa {Serializing Qt Data Types}
3808	*/
3809
3810	/*!
3811	\fn template <class Key, class T> size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
3812	\since 5.8
3813	\qhasholdTS{QHash}{Key}{T}
3814	*/
3815
3816	/*!
3817	\fn template <class Key, class T> size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
3818	\since 5.8
3819	\qhasholdTS{QMultiHash}{Key}{T}
3820	*/
3821
3822	/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
3823	\relates QHash
3824	\since 6.1
3825
3826	Removes all elements for which the predicate \a pred returns true
3827	from the hash \a hash.
3828
3829	The function supports predicates which take either an argument of
3830	type \c{QHash<Key, T>::iterator}, or an argument of type
3831	\c{std::pair<const Key &, T &>}.
3832
3833	Returns the number of elements removed, if any.
3834	*/
3835
3836	/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
3837	\relates QMultiHash
3838	\since 6.1
3839
3840	Removes all elements for which the predicate \a pred returns true
3841	from the multi hash \a hash.
3842
3843	The function supports predicates which take either an argument of
3844	type \c{QMultiHash<Key, T>::iterator}, or an argument of type
3845	\c{std::pair<const Key &, T &>}.
3846
3847	Returns the number of elements removed, if any.
3848	*/
3849
3850	#ifdef QT_HAS_CONSTEXPR_BITOPS
3851	namespace QHashPrivate {
3852	static_assert(qPopulationCount(v: SpanConstants::NEntries) == 1,
3853	"NEntries must be a power of 2 for bucketForHash() to work.");
3854
3855	// ensure the size of a Span does not depend on the template parameters
3856	using Node1 = Node<int, int>;
3857	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>));
3858	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>));
3859	static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>));
3860	static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries);
3861	static_assert(qNextPowerOfTwo(v: sizeof(Span<Node1>)) == SpanConstants::NEntries * 2);
3862
3863	// ensure allocations are always a power of two, at a minimum NEntries,
3864	// obeying the fomula
3865	// qNextPowerOfTwo(2 * N);
3866	// without overflowing
3867	static constexpr size_t NEntries = SpanConstants::NEntries;
3868	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: 1) == NEntries);
3869	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 0) == NEntries);
3870	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 1) == 2 * NEntries);
3871	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 - 1) == 2 * NEntries);
3872	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 0) == 4 * NEntries);
3873	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 1) == 4 * NEntries);
3874	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 - 1) == 4 * NEntries);
3875	static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 + 0) == 8 * NEntries);
3876	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1);
3877	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX);
3878	static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX);
3879	}
3880	#endif
3881
3882	QT_END_NAMESPACE
3883