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