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

Provided by KDAB

Privacy Policy
Start learning QML with our Intro Training
Find out more

source code of qtbase/src/corelib/tools/qhash.cpp