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 auto n = key.size();
1089 auto p = key.utf16();
1090
1091 uint h = chained;
1092
1093 while (n--) {
1094 h = (h << 4) + *p++;
1095 h ^= (h & 0xf0000000) >> 23;
1096 h &= 0x0fffffff;
1097 }
1098 return h;
1099}
1100
1101/*!
1102 \fn template <typename T1, typename T2> size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0)
1103 \since 5.7
1104 \relates QHash
1105
1106 Returns the hash value for the \a key, using \a seed to seed the calculation.
1107
1108 Types \c T1 and \c T2 must be supported by qHash().
1109*/
1110
1111/*!
1112 \fn template <typename... T> size_t qHashMulti(size_t seed, const T &...args)
1113 \relates QHash
1114 \since 6.0
1115
1116 Returns the hash value for the \a{args}, using \a seed to seed
1117 the calculation, by successively applying qHash() to each
1118 element and combining the hash values into a single one.
1119
1120 Note that the order of the arguments is significant. If order does
1121 not matter, use qHashMultiCommutative() instead. If you are hashing raw
1122 memory, use qHashBits(); if you are hashing a range, use qHashRange().
1123
1124 This function is provided as a convenience to implement qHash() for
1125 your own custom types. For example, here's how you could implement
1126 a qHash() overload for a class \c{Employee}:
1127
1128 \snippet code/src_corelib_tools_qhash.cpp 13
1129
1130 \sa qHashMultiCommutative, qHashRange
1131*/
1132
1133/*!
1134 \fn template <typename... T> size_t qHashMultiCommutative(size_t seed, const T &...args)
1135 \relates QHash
1136 \since 6.0
1137
1138 Returns the hash value for the \a{args}, using \a seed to seed
1139 the calculation, by successively applying qHash() to each
1140 element and combining the hash values into a single one.
1141
1142 The order of the arguments is insignificant. If order does
1143 matter, use qHashMulti() instead, as it may produce better quality
1144 hashing. If you are hashing raw memory, use qHashBits(); if you are
1145 hashing a range, use qHashRange().
1146
1147 This function is provided as a convenience to implement qHash() for
1148 your own custom types.
1149
1150 \sa qHashMulti, qHashRange
1151*/
1152
1153/*! \fn template <typename InputIterator> size_t qHashRange(InputIterator first, InputIterator last, size_t seed = 0)
1154 \relates QHash
1155 \since 5.5
1156
1157 Returns the hash value for the range [\a{first},\a{last}), using \a seed
1158 to seed the calculation, by successively applying qHash() to each
1159 element and combining the hash values into a single one.
1160
1161 The return value of this function depends on the order of elements
1162 in the range. That means that
1163
1164 \snippet code/src_corelib_tools_qhash.cpp 30
1165
1166 and
1167 \snippet code/src_corelib_tools_qhash.cpp 31
1168
1169 hash to \b{different} values. If order does not matter, for example for hash
1170 tables, use qHashRangeCommutative() instead. If you are hashing raw
1171 memory, use qHashBits().
1172
1173 Use this function only to implement qHash() for your own custom
1174 types. For example, here's how you could implement a qHash() overload for
1175 std::vector<int>:
1176
1177 \snippet code/src_corelib_tools_qhash.cpp qhashrange
1178
1179 It bears repeating that the implementation of qHashRange() - like
1180 the qHash() overloads offered by Qt - may change at any time. You
1181 \b{must not} rely on the fact that qHashRange() will give the same
1182 results (for the same inputs) across different Qt versions, even
1183 if qHash() for the element type would.
1184
1185 \sa qHashBits(), qHashRangeCommutative()
1186*/
1187
1188/*! \fn template <typename InputIterator> size_t qHashRangeCommutative(InputIterator first, InputIterator last, size_t seed = 0)
1189 \relates QHash
1190 \since 5.5
1191
1192 Returns the hash value for the range [\a{first},\a{last}), using \a seed
1193 to seed the calculation, by successively applying qHash() to each
1194 element and combining the hash values into a single one.
1195
1196 The return value of this function does not depend on the order of
1197 elements in the range. That means that
1198
1199 \snippet code/src_corelib_tools_qhash.cpp 30
1200
1201 and
1202 \snippet code/src_corelib_tools_qhash.cpp 31
1203
1204 hash to the \b{same} values. If order matters, for example, for vectors
1205 and arrays, use qHashRange() instead. If you are hashing raw
1206 memory, use qHashBits().
1207
1208 Use this function only to implement qHash() for your own custom
1209 types. For example, here's how you could implement a qHash() overload for
1210 std::unordered_set<int>:
1211
1212 \snippet code/src_corelib_tools_qhash.cpp qhashrangecommutative
1213
1214 It bears repeating that the implementation of
1215 qHashRangeCommutative() - like the qHash() overloads offered by Qt
1216 - may change at any time. You \b{must not} rely on the fact that
1217 qHashRangeCommutative() will give the same results (for the same
1218 inputs) across different Qt versions, even if qHash() for the
1219 element type would.
1220
1221 \sa qHashBits(), qHashRange()
1222*/
1223
1224/*! \fn size_t qHashBits(const void *p, size_t len, size_t seed = 0)
1225 \relates QHash
1226 \since 5.4
1227
1228 Returns the hash value for the memory block of size \a len pointed
1229 to by \a p, using \a seed to seed the calculation.
1230
1231 Use this function only to implement qHash() for your own custom
1232 types. For example, here's how you could implement a qHash() overload for
1233 std::vector<int>:
1234
1235 \snippet code/src_corelib_tools_qhash.cpp qhashbits
1236
1237 This takes advantage of the fact that std::vector lays out its data
1238 contiguously. If that is not the case, or the contained type has
1239 padding, you should use qHashRange() instead.
1240
1241 It bears repeating that the implementation of qHashBits() - like
1242 the qHash() overloads offered by Qt - may change at any time. You
1243 \b{must not} rely on the fact that qHashBits() will give the same
1244 results (for the same inputs) across different Qt versions.
1245
1246 \sa qHashRange(), qHashRangeCommutative()
1247*/
1248
1249/*! \fn size_t qHash(char key, size_t seed = 0)
1250 \relates QHash
1251 \since 5.0
1252
1253 Returns the hash value for the \a key, using \a seed to seed the calculation.
1254*/
1255
1256/*! \fn size_t qHash(uchar key, size_t seed = 0)
1257 \relates QHash
1258 \since 5.0
1259
1260 Returns the hash value for the \a key, using \a seed to seed the calculation.
1261*/
1262
1263/*! \fn size_t qHash(signed char key, size_t seed = 0)
1264 \relates QHash
1265 \since 5.0
1266
1267 Returns the hash value for the \a key, using \a seed to seed the calculation.
1268*/
1269
1270/*! \fn size_t qHash(ushort key, size_t seed = 0)
1271 \relates QHash
1272 \since 5.0
1273
1274 Returns the hash value for the \a key, using \a seed to seed the calculation.
1275*/
1276
1277/*! \fn size_t qHash(short key, size_t seed = 0)
1278 \relates QHash
1279 \since 5.0
1280
1281 Returns the hash value for the \a key, using \a seed to seed the calculation.
1282*/
1283
1284/*! \fn size_t qHash(uint key, size_t seed = 0)
1285 \relates QHash
1286 \since 5.0
1287
1288 Returns the hash value for the \a key, using \a seed to seed the calculation.
1289*/
1290
1291/*! \fn size_t qHash(int key, size_t seed = 0)
1292 \relates QHash
1293 \since 5.0
1294
1295 Returns the hash value for the \a key, using \a seed to seed the calculation.
1296*/
1297
1298/*! \fn size_t qHash(ulong key, size_t seed = 0)
1299 \relates QHash
1300 \since 5.0
1301
1302 Returns the hash value for the \a key, using \a seed to seed the calculation.
1303*/
1304
1305/*! \fn size_t qHash(long key, size_t seed = 0)
1306 \relates QHash
1307 \since 5.0
1308
1309 Returns the hash value for the \a key, using \a seed to seed the calculation.
1310*/
1311
1312/*! \fn size_t qHash(quint64 key, size_t seed = 0)
1313 \relates QHash
1314 \since 5.0
1315
1316 Returns the hash value for the \a key, using \a seed to seed the calculation.
1317*/
1318
1319/*! \fn size_t qHash(qint64 key, size_t seed = 0)
1320 \relates QHash
1321 \since 5.0
1322
1323 Returns the hash value for the \a key, using \a seed to seed the calculation.
1324*/
1325
1326/*! \fn size_t qHash(quint128 key, size_t seed = 0)
1327 \relates QHash
1328 \since 6.8
1329
1330 Returns the hash value for the \a key, using \a seed to seed the calculation.
1331
1332 \note This function is only available on platforms that support a native
1333 128-bit integer type.
1334*/
1335
1336/*! \fn size_t qHash(qint128 key, size_t seed = 0)
1337 \relates QHash
1338 \since 6.8
1339
1340 Returns the hash value for the \a key, using \a seed to seed the calculation.
1341
1342 \note This function is only available on platforms that support a native
1343 128-bit integer type.
1344 */
1345
1346/*! \fn size_t qHash(char8_t key, size_t seed = 0)
1347 \relates QHash
1348 \since 6.0
1349
1350 Returns the hash value for the \a key, using \a seed to seed the calculation.
1351*/
1352
1353/*! \fn size_t qHash(char16_t key, size_t seed = 0)
1354 \relates QHash
1355 \since 6.0
1356
1357 Returns the hash value for the \a key, using \a seed to seed the calculation.
1358*/
1359
1360/*! \fn size_t qHash(char32_t key, size_t seed = 0)
1361 \relates QHash
1362 \since 6.0
1363
1364 Returns the hash value for the \a key, using \a seed to seed the calculation.
1365*/
1366
1367/*! \fn size_t qHash(wchar_t key, size_t seed = 0)
1368 \relates QHash
1369 \since 6.0
1370
1371 Returns the hash value for the \a key, using \a seed to seed the calculation.
1372*/
1373
1374/*! \fn size_t qHash(float key, size_t seed = 0) noexcept
1375 \relates QHash
1376 \since 5.3
1377
1378 Returns the hash value for the \a key, using \a seed to seed the calculation.
1379*/
1380
1381/*! \relates QHash
1382 \since 5.3
1383
1384 Returns the hash value for the \a key, using \a seed to seed the calculation.
1385*/
1386size_t qHash(double key, size_t seed) noexcept
1387{
1388 // ensure -0 gets mapped to 0
1389 key += 0.0;
1390 if constexpr (sizeof(double) == sizeof(size_t)) {
1391 size_t k;
1392 memcpy(dest: &k, src: &key, n: sizeof(double));
1393 return QHashPrivate::hash(key: k, seed);
1394 } else {
1395 return murmurhash(key: &key, len: sizeof(key), seed);
1396 }
1397}
1398
1399/*! \relates QHash
1400 \since 5.3
1401
1402 Returns the hash value for the \a key, using \a seed to seed the calculation.
1403*/
1404size_t qHash(long double key, size_t seed) noexcept
1405{
1406 // ensure -0 gets mapped to 0
1407 key += static_cast<long double>(0.0);
1408 if constexpr (sizeof(long double) == sizeof(size_t)) {
1409 size_t k;
1410 memcpy(dest: &k, src: &key, n: sizeof(long double));
1411 return QHashPrivate::hash(key: k, seed);
1412 } else {
1413 return murmurhash(key: &key, len: sizeof(key), seed);
1414 }
1415}
1416
1417/*! \fn size_t qHash(const QChar key, size_t seed = 0)
1418 \relates QHash
1419 \since 5.0
1420
1421 Returns the hash value for the \a key, using \a seed to seed the calculation.
1422*/
1423
1424/*! \fn size_t qHash(const QByteArray &key, size_t seed = 0)
1425 \relates QHash
1426 \since 5.0
1427
1428 Returns the hash value for the \a key, using \a seed to seed the calculation.
1429*/
1430
1431/*! \fn size_t qHash(const QByteArrayView &key, size_t seed = 0)
1432 \relates QHash
1433 \since 6.0
1434
1435 Returns the hash value for the \a key, using \a seed to seed the calculation.
1436*/
1437
1438/*! \fn size_t qHash(const QBitArray &key, size_t seed = 0)
1439 \relates QHash
1440 \since 5.0
1441
1442 Returns the hash value for the \a key, using \a seed to seed the calculation.
1443*/
1444
1445/*! \fn size_t qHash(const QString &key, size_t seed = 0)
1446 \relates QHash
1447 \since 5.0
1448
1449 Returns the hash value for the \a key, using \a seed to seed the calculation.
1450*/
1451
1452/*! \fn size_t qHash(QStringView key, size_t seed = 0)
1453 \relates QStringView
1454 \since 5.10
1455
1456 Returns the hash value for the \a key, using \a seed to seed the calculation.
1457*/
1458
1459/*! \fn size_t qHash(QLatin1StringView key, size_t seed = 0)
1460 \relates QHash
1461 \since 5.0
1462
1463 Returns the hash value for the \a key, using \a seed to seed the calculation.
1464*/
1465
1466/*! \fn template <class T> size_t qHash(const T *key, size_t seed = 0)
1467 \relates QHash
1468 \since 5.0
1469
1470 Returns the hash value for the \a key, using \a seed to seed the calculation.
1471*/
1472
1473/*! \fn size_t qHash(std::nullptr_t key, size_t seed = 0)
1474 \relates QHash
1475 \since 6.0
1476
1477 Returns the hash value for the \a key, using \a seed to seed the calculation.
1478*/
1479
1480/*! \fn template<typename T> bool qHashEquals(const T &a, const T &b)
1481 \relates QHash
1482 \since 6.0
1483 \internal
1484
1485 This method is being used by QHash to compare two keys. Returns true if the
1486 keys \a a and \a b are considered equal for hashing purposes.
1487
1488 The default implementation returns the result of (a == b). It can be reimplemented
1489 for a certain type if the equality operator is not suitable for hashing purposes.
1490 This is for example the case if the equality operator uses qFuzzyCompare to compare
1491 floating point values.
1492*/
1493
1494
1495/*!
1496 \class QHash
1497 \inmodule QtCore
1498 \brief The QHash class is a template class that provides a hash-table-based dictionary.
1499
1500 \ingroup tools
1501 \ingroup shared
1502
1503 \reentrant
1504
1505 QHash\<Key, T\> is one of Qt's generic \l{container classes}. It
1506 stores (key, value) pairs and provides very fast lookup of the
1507 value associated with a key.
1508
1509 QHash provides very similar functionality to QMap. The
1510 differences are:
1511
1512 \list
1513 \li QHash provides faster lookups than QMap. (See \l{Algorithmic
1514 Complexity} for details.)
1515 \li When iterating over a QMap, the items are always sorted by
1516 key. With QHash, the items are arbitrarily ordered.
1517 \li The key type of a QMap must provide operator<(). The key
1518 type of a QHash must provide operator==() and a global
1519 hash function called qHash() (see \l{qHash}).
1520 \endlist
1521
1522 Here's an example QHash with QString keys and \c int values:
1523 \snippet code/src_corelib_tools_qhash.cpp 0
1524
1525 To insert a (key, value) pair into the hash, you can use operator[]():
1526
1527 \snippet code/src_corelib_tools_qhash.cpp 1
1528
1529 This inserts the following three (key, value) pairs into the
1530 QHash: ("one", 1), ("three", 3), and ("seven", 7). Another way to
1531 insert items into the hash is to use insert():
1532
1533 \snippet code/src_corelib_tools_qhash.cpp 2
1534
1535 To look up a value, use operator[]() or value():
1536
1537 \snippet code/src_corelib_tools_qhash.cpp 3
1538
1539 If there is no item with the specified key in the hash, these
1540 functions return a \l{default-constructed value}.
1541
1542 If you want to check whether the hash contains a particular key,
1543 use contains():
1544
1545 \snippet code/src_corelib_tools_qhash.cpp 4
1546
1547 There is also a value() overload that uses its second argument as
1548 a default value if there is no item with the specified key:
1549
1550 \snippet code/src_corelib_tools_qhash.cpp 5
1551
1552 In general, we recommend that you use contains() and value()
1553 rather than operator[]() for looking up a key in a hash. The
1554 reason is that operator[]() silently inserts an item into the
1555 hash if no item exists with the same key (unless the hash is
1556 const). For example, the following code snippet will create 1000
1557 items in memory:
1558
1559 \snippet code/src_corelib_tools_qhash.cpp 6
1560
1561 To avoid this problem, replace \c hash[i] with \c hash.value(i)
1562 in the code above.
1563
1564 Internally, QHash uses a hash table to perform lookups. This
1565 hash table automatically grows to
1566 provide fast lookups without wasting too much memory. You can
1567 still control the size of the hash table by calling reserve() if
1568 you already know approximately how many items the QHash will
1569 contain, but this isn't necessary to obtain good performance. You
1570 can also call capacity() to retrieve the hash table's size.
1571
1572 QHash will not shrink automatically if items are removed from the
1573 table. To minimize the memory used by the hash, call squeeze().
1574
1575 If you want to navigate through all the (key, value) pairs stored
1576 in a QHash, you can use an iterator. QHash provides both
1577 \l{Java-style iterators} (QHashIterator and QMutableHashIterator)
1578 and \l{STL-style iterators} (QHash::const_iterator and
1579 QHash::iterator). Here's how to iterate over a QHash<QString,
1580 int> using a Java-style iterator:
1581
1582 \snippet code/src_corelib_tools_qhash.cpp 7
1583
1584 Here's the same code, but using an STL-style iterator:
1585
1586 \snippet code/src_corelib_tools_qhash.cpp 8
1587
1588 QHash is unordered, so an iterator's sequence cannot be assumed
1589 to be predictable. If ordering by key is required, use a QMap.
1590
1591 A QHash allows only one value per key. If you call
1592 insert() with a key that already exists in the QHash, the
1593 previous value is erased. For example:
1594
1595 \snippet code/src_corelib_tools_qhash.cpp 9
1596
1597 If you need to store multiple entries for the same key in the
1598 hash table, use \l{QMultiHash}.
1599
1600 If you only need to extract the values from a hash (not the keys),
1601 you can also use range-based for:
1602
1603 \snippet code/src_corelib_tools_qhash.cpp 12
1604
1605 Items can be removed from the hash in several ways. One way is to
1606 call remove(); this will remove any item with the given key.
1607 Another way is to use QMutableHashIterator::remove(). In addition,
1608 you can clear the entire hash using clear().
1609
1610 QHash's key and value data types must be \l{assignable data
1611 types}. You cannot, for example, store a QWidget as a value;
1612 instead, store a QWidget *.
1613
1614 \target qHash
1615 \section2 The hashing function
1616
1617 A QHash's key type has additional requirements other than being an
1618 assignable data type: it must provide operator==(), and there must also be
1619 a hashing function that returns a hash value for an argument of the
1620 key's type.
1621
1622 The hashing function computes a numeric value based on a key. It
1623 can use any algorithm imaginable, as long as it always returns
1624 the same value if given the same argument. In other words, if
1625 \c{e1 == e2}, then \c{hash(e1) == hash(e2)} must hold as well.
1626 However, to obtain good performance, the hashing function should
1627 attempt to return different hash values for different keys to the
1628 largest extent possible.
1629
1630 A hashing function for a key type \c{K} may be provided in two
1631 different ways.
1632
1633 The first way is by having an overload of \c{qHash()} in \c{K}'s
1634 namespace. The \c{qHash()} function must have one of these signatures:
1635
1636 \snippet code/src_corelib_tools_qhash.cpp 32
1637
1638 The two-arguments overloads take an unsigned integer that should be used to
1639 seed the calculation of the hash function. This seed is provided by QHash
1640 in order to prevent a family of \l{algorithmic complexity attacks}.
1641
1642 \note In Qt 6 it is possible to define a \c{qHash()} overload
1643 taking only one argument; support for this is deprecated. Starting
1644 with Qt 7, it will be mandatory to use a two-arguments overload. If
1645 both a one-argument and a two-arguments overload are defined for a
1646 key type, the latter is used by QHash (note that you can simply
1647 define a two-arguments version, and use a default value for the
1648 seed parameter).
1649
1650 The second way to provide a hashing function is by specializing
1651 the \c{std::hash} class for the key type \c{K}, and providing a
1652 suitable function call operator for it:
1653
1654 \snippet code/src_corelib_tools_qhash.cpp 33
1655
1656 The seed argument has the same meaning as for \c{qHash()},
1657 and may be left out.
1658
1659 This second way allows to reuse the same hash function between
1660 QHash and the C++ Standard Library unordered associative containers.
1661 If both a \c{qHash()} overload and a \c{std::hash} specializations
1662 are provided for a type, then the \c{qHash()} overload is preferred.
1663
1664 Here's a partial list of the C++ and Qt types that can serve as keys in a
1665 QHash: any integer type (char, unsigned long, etc.), any pointer type,
1666 QChar, QString, and QByteArray. For all of these, the \c <QHash> header
1667 defines a qHash() function that computes an adequate hash value. Many other
1668 Qt classes also declare a qHash overload for their type; please refer to
1669 the documentation of each class.
1670
1671 If you want to use other types as the key, make sure that you provide
1672 operator==() and a hash implementation.
1673
1674 The convenience qHashMulti() function can be used to implement
1675 qHash() for a custom type, where one usually wants to produce a
1676 hash value from multiple fields:
1677
1678 Example:
1679 \snippet code/src_corelib_tools_qhash.cpp 13
1680
1681 In the example above, we've relied on Qt's own implementation of
1682 qHash() for QString and QDate to give us a hash value for the
1683 employee's name and date of birth respectively.
1684
1685 Note that the implementation of the qHash() overloads offered by Qt
1686 may change at any time. You \b{must not} rely on the fact that qHash()
1687 will give the same results (for the same inputs) across different Qt
1688 versions.
1689
1690 \section2 Algorithmic complexity attacks
1691
1692 All hash tables are vulnerable to a particular class of denial of service
1693 attacks, in which the attacker carefully pre-computes a set of different
1694 keys that are going to be hashed in the same bucket of a hash table (or
1695 even have the very same hash value). The attack aims at getting the
1696 worst-case algorithmic behavior (O(n) instead of amortized O(1), see
1697 \l{Algorithmic Complexity} for the details) when the data is fed into the
1698 table.
1699
1700 In order to avoid this worst-case behavior, the calculation of the hash
1701 value done by qHash() can be salted by a random seed, that nullifies the
1702 attack's extent. This seed is automatically generated by QHash once per
1703 process, and then passed by QHash as the second argument of the
1704 two-arguments overload of the qHash() function.
1705
1706 This randomization of QHash is enabled by default. Even though programs
1707 should never depend on a particular QHash ordering, there may be situations
1708 where you temporarily need deterministic behavior, for example for debugging or
1709 regression testing. To disable the randomization, define the environment
1710 variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
1711 the QHashSeed::setDeterministicGlobalSeed() function.
1712
1713 \sa QHashIterator, QMutableHashIterator, QMap, QSet
1714*/
1715
1716/*! \fn template <class Key, class T> QHash<Key, T>::QHash()
1717
1718 Constructs an empty hash.
1719
1720 \sa clear()
1721*/
1722
1723/*!
1724 \fn template <class Key, class T> QHash<Key, T>::QHash(QHash &&other)
1725
1726 Move-constructs a QHash instance, making it point at the same
1727 object that \a other was pointing to.
1728
1729 \since 5.2
1730*/
1731
1732/*! \fn template <class Key, class T> QHash<Key, T>::QHash(std::initializer_list<std::pair<Key,T> > list)
1733 \since 5.1
1734
1735 Constructs a hash with a copy of each of the elements in the
1736 initializer list \a list.
1737*/
1738
1739/*! \fn template <class Key, class T> template <class InputIterator> QHash<Key, T>::QHash(InputIterator begin, InputIterator end)
1740 \since 5.14
1741
1742 Constructs a hash with a copy of each of the elements in the iterator range
1743 [\a begin, \a end). Either the elements iterated by the range must be
1744 objects with \c{first} and \c{second} data members (like \c{std::pair}),
1745 convertible to \c Key and to \c T respectively; or the
1746 iterators must have \c{key()} and \c{value()} member functions, returning a
1747 key convertible to \c Key and a value convertible to \c T respectively.
1748*/
1749
1750/*! \fn template <class Key, class T> QHash<Key, T>::QHash(const QHash &other)
1751
1752 Constructs a copy of \a other.
1753
1754 This operation occurs in \l{constant time}, because QHash is
1755 \l{implicitly shared}. This makes returning a QHash from a
1756 function very fast. If a shared instance is modified, it will be
1757 copied (copy-on-write), and this takes \l{linear time}.
1758
1759 \sa operator=()
1760*/
1761
1762/*! \fn template <class Key, class T> QHash<Key, T>::~QHash()
1763
1764 Destroys the hash. References to the values in the hash and all
1765 iterators of this hash become invalid.
1766*/
1767
1768/*! \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(const QHash &other)
1769
1770 Assigns \a other to this hash and returns a reference to this hash.
1771*/
1772
1773/*!
1774 \fn template <class Key, class T> QHash &QHash<Key, T>::operator=(QHash &&other)
1775
1776 Move-assigns \a other to this QHash instance.
1777
1778 \since 5.2
1779*/
1780
1781/*! \fn template <class Key, class T> void QHash<Key, T>::swap(QHash &other)
1782 \since 4.8
1783
1784 Swaps hash \a other with this hash. This operation is very
1785 fast and never fails.
1786*/
1787
1788/*! \fn template <class Key, class T> void QMultiHash<Key, T>::swap(QMultiHash &other)
1789 \since 4.8
1790
1791 Swaps hash \a other with this hash. This operation is very
1792 fast and never fails.
1793*/
1794
1795/*! \fn template <class Key, class T> bool QHash<Key, T>::operator==(const QHash &other) const
1796
1797 Returns \c true if \a other is equal to this hash; otherwise returns
1798 false.
1799
1800 Two hashes are considered equal if they contain the same (key,
1801 value) pairs.
1802
1803 This function requires the value type to implement \c operator==().
1804
1805 \sa operator!=()
1806*/
1807
1808/*! \fn template <class Key, class T> bool QHash<Key, T>::operator!=(const QHash &other) const
1809
1810 Returns \c true if \a other is not equal to this hash; otherwise
1811 returns \c false.
1812
1813 Two hashes are considered equal if they contain the same (key,
1814 value) pairs.
1815
1816 This function requires the value type to implement \c operator==().
1817
1818 \sa operator==()
1819*/
1820
1821/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::size() const
1822
1823 Returns the number of items in the hash.
1824
1825 \sa isEmpty(), count()
1826*/
1827
1828/*! \fn template <class Key, class T> bool QHash<Key, T>::isEmpty() const
1829
1830 Returns \c true if the hash contains no items; otherwise returns
1831 false.
1832
1833 \sa size()
1834*/
1835
1836/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::capacity() const
1837
1838 Returns the number of buckets in the QHash's internal hash table.
1839
1840 The sole purpose of this function is to provide a means of fine
1841 tuning QHash's memory usage. In general, you will rarely ever
1842 need to call this function. If you want to know how many items are
1843 in the hash, call size().
1844
1845 \sa reserve(), squeeze()
1846*/
1847
1848/*! \fn template <class Key, class T> float QHash<Key, T>::load_factor() const noexcept
1849
1850 Returns the current load factor of the QHash's internal hash table.
1851 This is the same as capacity()/size(). The implementation used
1852 will aim to keep the load factor between 0.25 and 0.5. This avoids
1853 having too many hash table collisions that would degrade performance.
1854
1855 Even with a low load factor, the implementation of the hash table has a
1856 very low memory overhead.
1857
1858 This method purely exists for diagnostic purposes and you should rarely
1859 need to call it yourself.
1860
1861 \sa reserve(), squeeze()
1862*/
1863
1864
1865/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(qsizetype size)
1866
1867 Ensures that the QHash's internal hash table has space to store at
1868 least \a size items without having to grow the hash table.
1869
1870 This implies that the hash table will contain at least 2 * \a size buckets
1871 to ensure good performance
1872
1873 This function is useful for code that needs to build a huge hash
1874 and wants to avoid repeated reallocation. For example:
1875
1876 \snippet code/src_corelib_tools_qhash.cpp 14
1877
1878 Ideally, \a size should be the maximum number of items expected
1879 in the hash. QHash will then choose the smallest possible
1880 number of buckets that will allow storing \a size items in the table
1881 without having to grow the internal hash table. If \a size
1882 is an underestimate, the worst that will happen is that the QHash
1883 will be a bit slower.
1884
1885 In general, you will rarely ever need to call this function.
1886 QHash's internal hash table automatically grows to
1887 provide good performance without wasting too much memory.
1888
1889 \sa squeeze(), capacity()
1890*/
1891
1892/*! \fn template <class Key, class T> void QHash<Key, T>::squeeze()
1893
1894 Reduces the size of the QHash's internal hash table to save
1895 memory.
1896
1897 The sole purpose of this function is to provide a means of fine
1898 tuning QHash's memory usage. In general, you will rarely ever
1899 need to call this function.
1900
1901 \sa reserve(), capacity()
1902*/
1903
1904/*! \fn template <class Key, class T> void QHash<Key, T>::detach()
1905
1906 \internal
1907
1908 Detaches this hash from any other hashes with which it may share
1909 data.
1910
1911 \sa isDetached()
1912*/
1913
1914/*! \fn template <class Key, class T> bool QHash<Key, T>::isDetached() const
1915
1916 \internal
1917
1918 Returns \c true if the hash's internal data isn't shared with any
1919 other hash object; otherwise returns \c false.
1920
1921 \sa detach()
1922*/
1923
1924/*! \fn template <class Key, class T> bool QHash<Key, T>::isSharedWith(const QHash &other) const
1925
1926 \internal
1927
1928 Returns true if the internal hash table of this QHash is shared with \a other, otherwise false.
1929*/
1930
1931/*! \fn template <class Key, class T> void QHash<Key, T>::clear()
1932
1933 Removes all items from the hash and frees up all memory used by it.
1934
1935 \sa remove()
1936*/
1937
1938/*! \fn template <class Key, class T> bool QHash<Key, T>::remove(const Key &key)
1939
1940 Removes the item that has the \a key from the hash.
1941 Returns true if the key exists in the hash and the item has been removed,
1942 and false otherwise.
1943
1944 \sa clear(), take()
1945*/
1946
1947/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QHash<Key, T>::removeIf(Predicate pred)
1948 \since 6.1
1949
1950 Removes all elements for which the predicate \a pred returns true
1951 from the hash.
1952
1953 The function supports predicates which take either an argument of
1954 type \c{QHash<Key, T>::iterator}, or an argument of type
1955 \c{std::pair<const Key &, T &>}.
1956
1957 Returns the number of elements removed, if any.
1958
1959 \sa clear(), take()
1960*/
1961
1962/*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key)
1963
1964 Removes the item with the \a key from the hash and returns
1965 the value associated with it.
1966
1967 If the item does not exist in the hash, the function simply
1968 returns a \l{default-constructed value}.
1969
1970 If you don't use the return value, remove() is more efficient.
1971
1972 \sa remove()
1973*/
1974
1975/*! \fn template <class Key, class T> bool QHash<Key, T>::contains(const Key &key) const
1976
1977 Returns \c true if the hash contains an item with the \a key;
1978 otherwise returns \c false.
1979
1980 \sa count()
1981*/
1982
1983/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key) const
1984 \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue) const
1985 \overload
1986
1987 Returns the value associated with the \a key.
1988
1989 If the hash contains no item with the \a key, the function
1990 returns \a defaultValue, or a \l{default-constructed value} if this
1991 parameter has not been supplied.
1992*/
1993
1994/*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key)
1995
1996 Returns the value associated with the \a key as a modifiable
1997 reference.
1998
1999 If the hash contains no item with the \a key, the function inserts
2000 a \l{default-constructed value} into the hash with the \a key, and
2001 returns a reference to it.
2002
2003//! [qhash-iterator-invalidation-func-desc]
2004 \warning Returned iterators/references should be considered invalidated
2005 the next time you call a non-const function on the hash, or when the
2006 hash is destroyed.
2007//! [qhash-iterator-invalidation-func-desc]
2008
2009 \sa insert(), value()
2010*/
2011
2012/*! \fn template <class Key, class T> const T QHash<Key, T>::operator[](const Key &key) const
2013
2014 \overload
2015
2016 Same as value().
2017*/
2018
2019/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const
2020
2021 Returns a list containing all the keys in the hash, in an
2022 arbitrary order.
2023
2024 The order is guaranteed to be the same as that used by values().
2025
2026 This function creates a new list, in \l {linear time}. The time and memory
2027 use that entails can be avoided by iterating from \l keyBegin() to
2028 \l keyEnd().
2029
2030 \sa values(), key()
2031*/
2032
2033/*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const
2034
2035 \overload
2036
2037 Returns a list containing all the keys associated with value \a
2038 value, in an arbitrary order.
2039
2040 This function can be slow (\l{linear time}), because QHash's
2041 internal data structure is optimized for fast lookup by key, not
2042 by value.
2043*/
2044
2045/*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values() const
2046
2047 Returns a list containing all the values in the hash, in an
2048 arbitrary order.
2049
2050 The order is guaranteed to be the same as that used by keys().
2051
2052 This function creates a new list, in \l {linear time}. The time and memory
2053 use that entails can be avoided by iterating from \l keyValueBegin() to
2054 \l keyValueEnd().
2055
2056 \sa keys(), value()
2057*/
2058
2059/*!
2060 \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const
2061 \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const
2062 \since 4.3
2063
2064 Returns the first key mapped to \a value. If the hash contains no item
2065 mapped to \a value, returns \a defaultKey, or a \l{default-constructed
2066 value}{default-constructed key} if this parameter has not been supplied.
2067
2068 This function can be slow (\l{linear time}), because QHash's
2069 internal data structure is optimized for fast lookup by key, not
2070 by value.
2071*/
2072
2073/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count(const Key &key) const
2074
2075 Returns the number of items associated with the \a key.
2076
2077 \sa contains()
2078*/
2079
2080/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count() const
2081
2082 \overload
2083
2084 Same as size().
2085*/
2086
2087/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::begin()
2088
2089 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
2090 the hash.
2091
2092 \include qhash.cpp qhash-iterator-invalidation-func-desc
2093
2094 \sa constBegin(), end()
2095*/
2096
2097/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const
2098
2099 \overload
2100
2101 \include qhash.cpp qhash-iterator-invalidation-func-desc
2102*/
2103
2104/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const
2105 \since 5.0
2106
2107 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2108 in the hash.
2109
2110 \include qhash.cpp qhash-iterator-invalidation-func-desc
2111
2112 \sa begin(), cend()
2113*/
2114
2115/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constBegin() const
2116
2117 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
2118 in the hash.
2119
2120 \include qhash.cpp qhash-iterator-invalidation-func-desc
2121
2122 \sa begin(), constEnd()
2123*/
2124
2125/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyBegin() const
2126 \since 5.6
2127
2128 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
2129 in the hash.
2130
2131 \include qhash.cpp qhash-iterator-invalidation-func-desc
2132
2133 \sa keyEnd()
2134*/
2135
2136/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::end()
2137
2138 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
2139 after the last item in the hash.
2140
2141 \include qhash.cpp qhash-iterator-invalidation-func-desc
2142
2143 \sa begin(), constEnd()
2144*/
2145
2146/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const
2147
2148 \overload
2149
2150 \include qhash.cpp qhash-iterator-invalidation-func-desc
2151*/
2152
2153/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const
2154
2155 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2156 item after the last item in the hash.
2157
2158 \include qhash.cpp qhash-iterator-invalidation-func-desc
2159
2160 \sa constBegin(), end()
2161*/
2162
2163/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cend() const
2164 \since 5.0
2165
2166 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2167 item after the last item in the hash.
2168
2169 \include qhash.cpp qhash-iterator-invalidation-func-desc
2170
2171 \sa cbegin(), end()
2172*/
2173
2174/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::keyEnd() const
2175 \since 5.6
2176
2177 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2178 item after the last key in the hash.
2179
2180 \include qhash.cpp qhash-iterator-invalidation-func-desc
2181
2182 \sa keyBegin()
2183*/
2184
2185/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueBegin()
2186 \since 5.10
2187
2188 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2189 in the hash.
2190
2191 \include qhash.cpp qhash-iterator-invalidation-func-desc
2192
2193 \sa keyValueEnd()
2194*/
2195
2196/*! \fn template <class Key, class T> QHash<Key, T>::key_value_iterator QHash<Key, T>::keyValueEnd()
2197 \since 5.10
2198
2199 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2200 entry after the last entry in the hash.
2201
2202 \include qhash.cpp qhash-iterator-invalidation-func-desc
2203
2204 \sa keyValueBegin()
2205*/
2206
2207/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueBegin() const
2208 \since 5.10
2209
2210 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2211 in the hash.
2212
2213 \include qhash.cpp qhash-iterator-invalidation-func-desc
2214
2215 \sa keyValueEnd()
2216*/
2217
2218/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueBegin() const
2219 \since 5.10
2220
2221 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
2222 in the hash.
2223
2224 \include qhash.cpp qhash-iterator-invalidation-func-desc
2225
2226 \sa keyValueBegin()
2227*/
2228
2229/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::keyValueEnd() const
2230 \since 5.10
2231
2232 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2233 entry after the last entry in the hash.
2234
2235 \include qhash.cpp qhash-iterator-invalidation-func-desc
2236
2237 \sa keyValueBegin()
2238*/
2239
2240/*! \fn template <class Key, class T> QHash<Key, T>::const_key_value_iterator QHash<Key, T>::constKeyValueEnd() const
2241 \since 5.10
2242
2243 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
2244 entry after the last entry in the hash.
2245
2246 \include qhash.cpp qhash-iterator-invalidation-func-desc
2247
2248 \sa constKeyValueBegin()
2249*/
2250
2251/*! \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &
2252 \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &
2253 \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() &&
2254 \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const &&
2255 \since 6.4
2256
2257 Returns a range object that allows iteration over this hash as
2258 key/value pairs. For instance, this range object can be used in a
2259 range-based for loop, in combination with a structured binding declaration:
2260
2261 \snippet code/src_corelib_tools_qhash.cpp 34
2262
2263 Note that both the key and the value obtained this way are
2264 references to the ones in the hash. Specifically, mutating the value
2265 will modify the hash itself.
2266
2267 \include qhash.cpp qhash-iterator-invalidation-func-desc
2268
2269 \sa QKeyValueIterator
2270*/
2271
2272/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos)
2273 \since 5.7
2274
2275 Removes the (key, value) pair associated with the iterator \a pos
2276 from the hash, and returns an iterator to the next item in the
2277 hash.
2278
2279 This function never causes QHash to
2280 rehash its internal data structure. This means that it can safely
2281 be called while iterating, and won't affect the order of items in
2282 the hash. For example:
2283
2284 \snippet code/src_corelib_tools_qhash.cpp 15
2285
2286 \include qhash.cpp qhash-iterator-invalidation-func-desc
2287
2288 \sa remove(), take(), find()
2289*/
2290
2291/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key)
2292
2293 Returns an iterator pointing to the item with the \a key in the
2294 hash.
2295
2296 If the hash contains no item with the \a key, the function
2297 returns end().
2298
2299 If the hash contains multiple items with the \a key, this
2300 function returns an iterator that points to the most recently
2301 inserted value. The other values are accessible by incrementing
2302 the iterator. For example, here's some code that iterates over all
2303 the items with the same key:
2304
2305 \snippet code/src_corelib_tools_qhash.cpp 16
2306
2307 \include qhash.cpp qhash-iterator-invalidation-func-desc
2308
2309 \sa value(), values()
2310*/
2311
2312/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const
2313
2314 \overload
2315
2316 \include qhash.cpp qhash-iterator-invalidation-func-desc
2317*/
2318
2319/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const
2320 \since 4.1
2321
2322 Returns an iterator pointing to the item with the \a key in the
2323 hash.
2324
2325 If the hash contains no item with the \a key, the function
2326 returns constEnd().
2327
2328 \include qhash.cpp qhash-iterator-invalidation-func-desc
2329
2330 \sa find()
2331*/
2332
2333/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &key, const T &value)
2334
2335 Inserts a new item with the \a key and a value of \a value.
2336
2337 If there is already an item with the \a key, that item's value
2338 is replaced with \a value.
2339
2340 Returns an iterator pointing to the new/updated element.
2341
2342 \include qhash.cpp qhash-iterator-invalidation-func-desc
2343*/
2344
2345/*!
2346 \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args)
2347 \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args)
2348
2349 Inserts a new element into the container. This new element
2350 is constructed in-place using \a args as the arguments for its
2351 construction.
2352
2353 Returns an iterator pointing to the new element.
2354
2355 \include qhash.cpp qhash-iterator-invalidation-func-desc
2356*/
2357
2358
2359/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
2360 \since 5.15
2361
2362 Inserts all the items in the \a other hash into this hash.
2363
2364 If a key is common to both hashes, its value will be replaced with the
2365 value stored in \a other.
2366*/
2367
2368/*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const
2369
2370 This function is provided for STL compatibility. It is equivalent
2371 to isEmpty(), returning true if the hash is empty; otherwise
2372 returns \c false.
2373*/
2374
2375/*! \fn template <class Key, class T> std::pair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key)
2376 \since 5.7
2377
2378 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
2379 are stored under \a key. If the range is empty then both iterators will be equal to end().
2380
2381 \include qhash.cpp qhash-iterator-invalidation-func-desc
2382*/
2383
2384/*!
2385 \fn template <class Key, class T> std::pair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const
2386 \overload
2387 \since 5.7
2388
2389 \include qhash.cpp qhash-iterator-invalidation-func-desc
2390*/
2391
2392/*! \typedef QHash::ConstIterator
2393
2394 Qt-style synonym for QHash::const_iterator.
2395*/
2396
2397/*! \typedef QHash::Iterator
2398
2399 Qt-style synonym for QHash::iterator.
2400*/
2401
2402/*! \typedef QHash::difference_type
2403
2404 Typedef for ptrdiff_t. Provided for STL compatibility.
2405*/
2406
2407/*! \typedef QHash::key_type
2408
2409 Typedef for Key. Provided for STL compatibility.
2410*/
2411
2412/*! \typedef QHash::mapped_type
2413
2414 Typedef for T. Provided for STL compatibility.
2415*/
2416
2417/*! \typedef QHash::size_type
2418
2419 Typedef for int. Provided for STL compatibility.
2420*/
2421
2422/*! \typedef QHash::iterator::difference_type
2423 \internal
2424*/
2425
2426/*! \typedef QHash::iterator::iterator_category
2427 \internal
2428*/
2429
2430/*! \typedef QHash::iterator::pointer
2431 \internal
2432*/
2433
2434/*! \typedef QHash::iterator::reference
2435 \internal
2436*/
2437
2438/*! \typedef QHash::iterator::value_type
2439 \internal
2440*/
2441
2442/*! \typedef QHash::const_iterator::difference_type
2443 \internal
2444*/
2445
2446/*! \typedef QHash::const_iterator::iterator_category
2447 \internal
2448*/
2449
2450/*! \typedef QHash::const_iterator::pointer
2451 \internal
2452*/
2453
2454/*! \typedef QHash::const_iterator::reference
2455 \internal
2456*/
2457
2458/*! \typedef QHash::const_iterator::value_type
2459 \internal
2460*/
2461
2462/*! \typedef QHash::key_iterator::difference_type
2463 \internal
2464*/
2465
2466/*! \typedef QHash::key_iterator::iterator_category
2467 \internal
2468*/
2469
2470/*! \typedef QHash::key_iterator::pointer
2471 \internal
2472*/
2473
2474/*! \typedef QHash::key_iterator::reference
2475 \internal
2476*/
2477
2478/*! \typedef QHash::key_iterator::value_type
2479 \internal
2480*/
2481
2482/*! \class QHash::iterator
2483 \inmodule QtCore
2484 \brief The QHash::iterator class provides an STL-style non-const iterator for QHash.
2485
2486 QHash\<Key, T\>::iterator allows you to iterate over a QHash
2487 and to modify the value (but not the key) associated
2488 with a particular key. If you want to iterate over a const QHash,
2489 you should use QHash::const_iterator. It is generally good
2490 practice to use QHash::const_iterator on a non-const QHash as
2491 well, unless you need to change the QHash through the iterator.
2492 Const iterators are slightly faster, and can improve code
2493 readability.
2494
2495 The default QHash::iterator constructor creates an uninitialized
2496 iterator. You must initialize it using a QHash function like
2497 QHash::begin(), QHash::end(), or QHash::find() before you can
2498 start iterating. Here's a typical loop that prints all the (key,
2499 value) pairs stored in a hash:
2500
2501 \snippet code/src_corelib_tools_qhash.cpp 17
2502
2503 Unlike QMap, which orders its items by key, QHash stores its
2504 items in an arbitrary order.
2505
2506 Here's an example that increments every value stored in the QHash
2507 by 2:
2508
2509 \snippet code/src_corelib_tools_qhash.cpp 18
2510
2511 To remove elements from a QHash you can use erase_if(QHash\<Key, T\> &map, Predicate pred):
2512
2513 \snippet code/src_corelib_tools_qhash.cpp 21
2514
2515 Multiple iterators can be used on the same hash. However, be aware
2516 that any modification performed directly on the QHash (inserting and
2517 removing items) can cause the iterators to become invalid.
2518
2519 Inserting items into the hash or calling methods such as QHash::reserve()
2520 or QHash::squeeze() can invalidate all iterators pointing into the hash.
2521 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2522 to grow/shrink its internal hash table.
2523 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2524
2525 If you need to keep iterators over a long period of time, we recommend
2526 that you use QMap rather than QHash.
2527
2528 \warning Iterators on implicitly shared containers do not work
2529 exactly like STL-iterators. You should avoid copying a container
2530 while iterators are active on that container. For more information,
2531 read \l{Implicit sharing iterator problem}.
2532
2533 \sa QHash::const_iterator, QHash::key_iterator, QHash::key_value_iterator
2534*/
2535
2536/*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator()
2537
2538 Constructs an uninitialized iterator.
2539
2540 Functions like key(), value(), and operator++() must not be
2541 called on an uninitialized iterator. Use operator=() to assign a
2542 value to it before using it.
2543
2544 \sa QHash::begin(), QHash::end()
2545*/
2546
2547/*! \fn template <class Key, class T> const Key &QHash<Key, T>::iterator::key() const
2548
2549 Returns the current item's key as a const reference.
2550
2551 There is no direct way of changing an item's key through an
2552 iterator, although it can be done by calling QHash::erase()
2553 followed by QHash::insert().
2554
2555 \sa value()
2556*/
2557
2558/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::value() const
2559
2560 Returns a modifiable reference to the current item's value.
2561
2562 You can change the value of an item by using value() on
2563 the left side of an assignment, for example:
2564
2565 \snippet code/src_corelib_tools_qhash.cpp 22
2566
2567 \sa key(), operator*()
2568*/
2569
2570/*! \fn template <class Key, class T> T &QHash<Key, T>::iterator::operator*() const
2571
2572 Returns a modifiable reference to the current item's value.
2573
2574 Same as value().
2575
2576 \sa key()
2577*/
2578
2579/*! \fn template <class Key, class T> T *QHash<Key, T>::iterator::operator->() const
2580
2581 Returns a pointer to the current item's value.
2582
2583 \sa value()
2584*/
2585
2586/*!
2587 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const iterator &other) const
2588 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator==(const const_iterator &other) const
2589
2590 Returns \c true if \a other points to the same item as this
2591 iterator; otherwise returns \c false.
2592
2593 \sa operator!=()
2594*/
2595
2596/*!
2597 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const iterator &other) const
2598 \fn template <class Key, class T> bool QHash<Key, T>::iterator::operator!=(const const_iterator &other) const
2599
2600 Returns \c true if \a other points to a different item than this
2601 iterator; otherwise returns \c false.
2602
2603 \sa operator==()
2604*/
2605
2606/*!
2607 \fn template <class Key, class T> QHash<Key, T>::iterator &QHash<Key, T>::iterator::operator++()
2608
2609 The prefix ++ operator (\c{++i}) advances the iterator to the
2610 next item in the hash and returns an iterator to the new current
2611 item.
2612
2613 Calling this function on QHash::end() leads to undefined results.
2614*/
2615
2616/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::iterator::operator++(int)
2617
2618 \overload
2619
2620 The postfix ++ operator (\c{i++}) advances the iterator to the
2621 next item in the hash and returns an iterator to the previously
2622 current item.
2623*/
2624
2625/*! \class QHash::const_iterator
2626 \inmodule QtCore
2627 \brief The QHash::const_iterator class provides an STL-style const iterator for QHash.
2628
2629 QHash\<Key, T\>::const_iterator allows you to iterate over a
2630 QHash. If you want to modify the QHash as you
2631 iterate over it, you must use QHash::iterator instead. It is
2632 generally good practice to use QHash::const_iterator on a
2633 non-const QHash as well, unless you need to change the QHash
2634 through the iterator. Const iterators are slightly faster, and
2635 can improve code readability.
2636
2637 The default QHash::const_iterator constructor creates an
2638 uninitialized iterator. You must initialize it using a QHash
2639 function like QHash::cbegin(), QHash::cend(), or
2640 QHash::constFind() before you can start iterating. Here's a typical
2641 loop that prints all the (key, value) pairs stored in a hash:
2642
2643 \snippet code/src_corelib_tools_qhash.cpp 23
2644
2645 Unlike QMap, which orders its items by key, QHash stores its
2646 items in an arbitrary order. The only guarantee is that items that
2647 share the same key (because they were inserted using
2648 a QMultiHash) will appear consecutively, from the most
2649 recently to the least recently inserted value.
2650
2651 Multiple iterators can be used on the same hash. However, be aware
2652 that any modification performed directly on the QHash (inserting and
2653 removing items) can cause the iterators to become invalid.
2654
2655 Inserting items into the hash or calling methods such as QHash::reserve()
2656 or QHash::squeeze() can invalidate all iterators pointing into the hash.
2657 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
2658 to grow/shrink its internal hash table.
2659 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
2660
2661 You can however safely use iterators to remove entries from the hash
2662 using the QHash::erase() method. This function can safely be called while
2663 iterating, and won't affect the order of items in the hash.
2664
2665 \warning Iterators on implicitly shared containers do not work
2666 exactly like STL-iterators. You should avoid copying a container
2667 while iterators are active on that container. For more information,
2668 read \l{Implicit sharing iterator problem}.
2669
2670 \sa QHash::iterator, QHash::key_iterator, QHash::const_key_value_iterator
2671*/
2672
2673/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator()
2674
2675 Constructs an uninitialized iterator.
2676
2677 Functions like key(), value(), and operator++() must not be
2678 called on an uninitialized iterator. Use operator=() to assign a
2679 value to it before using it.
2680
2681 \sa QHash::constBegin(), QHash::constEnd()
2682*/
2683
2684/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator(const iterator &other)
2685
2686 Constructs a copy of \a other.
2687*/
2688
2689/*! \fn template <class Key, class T> const Key &QHash<Key, T>::const_iterator::key() const
2690
2691 Returns the current item's key.
2692
2693 \sa value()
2694*/
2695
2696/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::value() const
2697
2698 Returns the current item's value.
2699
2700 \sa key(), operator*()
2701*/
2702
2703/*! \fn template <class Key, class T> const T &QHash<Key, T>::const_iterator::operator*() const
2704
2705 Returns the current item's value.
2706
2707 Same as value().
2708
2709 \sa key()
2710*/
2711
2712/*! \fn template <class Key, class T> const T *QHash<Key, T>::const_iterator::operator->() const
2713
2714 Returns a pointer to the current item's value.
2715
2716 \sa value()
2717*/
2718
2719/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
2720
2721 Returns \c true if \a other points to the same item as this
2722 iterator; otherwise returns \c false.
2723
2724 \sa operator!=()
2725*/
2726
2727/*! \fn template <class Key, class T> bool QHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
2728
2729 Returns \c true if \a other points to a different item than this
2730 iterator; otherwise returns \c false.
2731
2732 \sa operator==()
2733*/
2734
2735/*!
2736 \fn template <class Key, class T> QHash<Key, T>::const_iterator &QHash<Key, T>::const_iterator::operator++()
2737
2738 The prefix ++ operator (\c{++i}) advances the iterator to the
2739 next item in the hash and returns an iterator to the new current
2740 item.
2741
2742 Calling this function on QHash::end() leads to undefined results.
2743*/
2744
2745/*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int)
2746
2747 \overload
2748
2749 The postfix ++ operator (\c{i++}) advances the iterator to the
2750 next item in the hash and returns an iterator to the previously
2751 current item.
2752*/
2753
2754/*! \class QHash::key_iterator
2755 \inmodule QtCore
2756 \since 5.6
2757 \brief The QHash::key_iterator class provides an STL-style const iterator for QHash keys.
2758
2759 QHash::key_iterator is essentially the same as QHash::const_iterator
2760 with the difference that operator*() and operator->() return a key
2761 instead of a value.
2762
2763 For most uses QHash::iterator and QHash::const_iterator should be used,
2764 you can easily access the key by calling QHash::iterator::key():
2765
2766 \snippet code/src_corelib_tools_qhash.cpp 27
2767
2768 However, to have interoperability between QHash's keys and STL-style
2769 algorithms we need an iterator that dereferences to a key instead
2770 of a value. With QHash::key_iterator we can apply an algorithm to a
2771 range of keys without having to call QHash::keys(), which is inefficient
2772 as it costs one QHash iteration and memory allocation to create a temporary
2773 QList.
2774
2775 \snippet code/src_corelib_tools_qhash.cpp 28
2776
2777 QHash::key_iterator is const, it's not possible to modify the key.
2778
2779 The default QHash::key_iterator constructor creates an uninitialized
2780 iterator. You must initialize it using a QHash function like
2781 QHash::keyBegin() or QHash::keyEnd().
2782
2783 \warning Iterators on implicitly shared containers do not work
2784 exactly like STL-iterators. You should avoid copying a container
2785 while iterators are active on that container. For more information,
2786 read \l{Implicit sharing iterator problem}.
2787
2788 \sa QHash::const_iterator, QHash::iterator
2789*/
2790
2791/*! \fn template <class Key, class T> const T &QHash<Key, T>::key_iterator::operator*() const
2792
2793 Returns the current item's key.
2794*/
2795
2796/*! \fn template <class Key, class T> const T *QHash<Key, T>::key_iterator::operator->() const
2797
2798 Returns a pointer to the current item's key.
2799*/
2800
2801/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator==(key_iterator other) const
2802
2803 Returns \c true if \a other points to the same item as this
2804 iterator; otherwise returns \c false.
2805
2806 \sa operator!=()
2807*/
2808
2809/*! \fn template <class Key, class T> bool QHash<Key, T>::key_iterator::operator!=(key_iterator other) const
2810
2811 Returns \c true if \a other points to a different item than this
2812 iterator; otherwise returns \c false.
2813
2814 \sa operator==()
2815*/
2816
2817/*!
2818 \fn template <class Key, class T> QHash<Key, T>::key_iterator &QHash<Key, T>::key_iterator::operator++()
2819
2820 The prefix ++ operator (\c{++i}) advances the iterator to the
2821 next item in the hash and returns an iterator to the new current
2822 item.
2823
2824 Calling this function on QHash::keyEnd() leads to undefined results.
2825
2826*/
2827
2828/*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int)
2829
2830 \overload
2831
2832 The postfix ++ operator (\c{i++}) advances the iterator to the
2833 next item in the hash and returns an iterator to the previous
2834 item.
2835*/
2836
2837/*! \fn template <class Key, class T> const_iterator QHash<Key, T>::key_iterator::base() const
2838 Returns the underlying const_iterator this key_iterator is based on.
2839*/
2840
2841/*! \typedef QHash::const_key_value_iterator
2842 \inmodule QtCore
2843 \since 5.10
2844 \brief The QHash::const_key_value_iterator typedef provides an STL-style const iterator for QHash.
2845
2846 QHash::const_key_value_iterator is essentially the same as QHash::const_iterator
2847 with the difference that operator*() returns a key/value pair instead of a
2848 value.
2849
2850 \sa QKeyValueIterator
2851*/
2852
2853/*! \typedef QHash::key_value_iterator
2854 \inmodule QtCore
2855 \since 5.10
2856 \brief The QHash::key_value_iterator typedef provides an STL-style iterator for QHash.
2857
2858 QHash::key_value_iterator is essentially the same as QHash::iterator
2859 with the difference that operator*() returns a key/value pair instead of a
2860 value.
2861
2862 \sa QKeyValueIterator
2863*/
2864
2865/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
2866 \relates QHash
2867
2868 Writes the hash \a hash to stream \a out.
2869
2870 This function requires the key and value types to implement \c
2871 operator<<().
2872
2873 \sa {Serializing Qt Data Types}
2874*/
2875
2876/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QHash<Key, T> &hash)
2877 \relates QHash
2878
2879 Reads a hash from stream \a in into \a hash.
2880
2881 This function requires the key and value types to implement \c
2882 operator>>().
2883
2884 \sa {Serializing Qt Data Types}
2885*/
2886
2887/*! \class QMultiHash
2888 \inmodule QtCore
2889 \brief The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
2890
2891 \ingroup tools
2892 \ingroup shared
2893
2894 \reentrant
2895
2896 QMultiHash\<Key, T\> is one of Qt's generic \l{container classes}.
2897 It inherits QHash and extends it with a few convenience functions
2898 that make it more suitable than QHash for storing multi-valued
2899 hashes. A multi-valued hash is a hash that allows multiple values
2900 with the same key.
2901
2902 QMultiHash mostly mirrors QHash's API. For example, you can use isEmpty() to test
2903 whether the hash is empty, and you can traverse a QMultiHash using
2904 QHash's iterator classes (for example, QHashIterator). But opposed to
2905 QHash, it provides an insert() function that allows the insertion of
2906 multiple items with the same key. The replace() function corresponds to
2907 QHash::insert(). It also provides convenient operator+() and
2908 operator+=().
2909
2910 Unlike QMultiMap, QMultiHash does not provide and ordering of the
2911 inserted items. The only guarantee is that items that
2912 share the same key will appear consecutively, from the most
2913 recently to the least recently inserted value.
2914
2915 Example:
2916 \snippet code/src_corelib_tools_qhash.cpp 24
2917
2918 Unlike QHash, QMultiHash provides no operator[]. Use value() or
2919 replace() if you want to access the most recently inserted item
2920 with a certain key.
2921
2922 If you want to retrieve all the values for a single key, you can
2923 use values(const Key &key), which returns a QList<T>:
2924
2925 \snippet code/src_corelib_tools_qhash.cpp 25
2926
2927 The items that share the same key are available from most
2928 recently to least recently inserted.
2929
2930 A more efficient approach is to call find() to get
2931 the STL-style iterator for the first item with a key and iterate from
2932 there:
2933
2934 \snippet code/src_corelib_tools_qhash.cpp 26
2935
2936 QMultiHash's key and value data types must be \l{assignable data
2937 types}. You cannot, for example, store a QWidget as a value;
2938 instead, store a QWidget *. In addition, QMultiHash's key type
2939 must provide operator==(), and there must also be a qHash() function
2940 in the type's namespace that returns a hash value for an argument of the
2941 key's type. See the QHash documentation for details.
2942
2943 \sa QHash, QHashIterator, QMutableHashIterator, QMultiMap
2944*/
2945
2946/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash()
2947
2948 Constructs an empty hash.
2949*/
2950
2951/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(std::initializer_list<std::pair<Key,T> > list)
2952 \since 5.1
2953
2954 Constructs a multi-hash with a copy of each of the elements in the
2955 initializer list \a list.
2956*/
2957
2958/*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other)
2959
2960 Constructs a copy of \a other (which can be a QHash or a
2961 QMultiHash).
2962*/
2963
2964/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end)
2965 \since 5.14
2966
2967 Constructs a multi-hash with a copy of each of the elements in the iterator range
2968 [\a begin, \a end). Either the elements iterated by the range must be
2969 objects with \c{first} and \c{second} data members (like \c{std::pair}),
2970 convertible to \c Key and to \c T respectively; or the
2971 iterators must have \c{key()} and \c{value()} member functions, returning a
2972 key convertible to \c Key and a value convertible to \c T respectively.
2973*/
2974
2975/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::replace(const Key &key, const T &value)
2976
2977 Inserts a new item with the \a key and a value of \a value.
2978
2979 If there is already an item with the \a key, that item's value
2980 is replaced with \a value.
2981
2982 If there are multiple items with the \a key, the most
2983 recently inserted item's value is replaced with \a value.
2984
2985 Returns an iterator pointing to the new/updated element.
2986
2987 \include qhash.cpp qhash-iterator-invalidation-func-desc
2988
2989 \sa insert()
2990*/
2991
2992/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &key, const T &value)
2993
2994 Inserts a new item with the \a key and a value of \a value.
2995
2996 If there is already an item with the same key in the hash, this
2997 function will simply create a new one. (This behavior is
2998 different from replace(), which overwrites the value of an
2999 existing item.)
3000
3001 Returns an iterator pointing to the new element.
3002
3003 \include qhash.cpp qhash-iterator-invalidation-func-desc
3004
3005 \sa replace()
3006*/
3007
3008/*!
3009 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args)
3010 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args)
3011
3012 Inserts a new element into the container. This new element
3013 is constructed in-place using \a args as the arguments for its
3014 construction.
3015
3016 If there is already an item with the same key in the hash, this
3017 function will simply create a new one. (This behavior is
3018 different from replace(), which overwrites the value of an
3019 existing item.)
3020
3021 Returns an iterator pointing to the new element.
3022
3023 \include qhash.cpp qhash-iterator-invalidation-func-desc
3024
3025 \sa insert
3026*/
3027
3028/*!
3029 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args)
3030 \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args)
3031
3032 Inserts a new element into the container. This new element
3033 is constructed in-place using \a args as the arguments for its
3034 construction.
3035
3036 If there is already an item with the same key in the hash, that item's
3037 value is replaced with a value constructed from \a args.
3038
3039 Returns an iterator pointing to the new element.
3040
3041 \include qhash.cpp qhash-iterator-invalidation-func-desc
3042
3043 \sa replace, emplace
3044*/
3045
3046
3047/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
3048 \since 5.13
3049
3050 Inserts all the items in the \a other hash into this hash
3051 and returns a reference to this hash.
3052
3053 \sa insert()
3054*/
3055
3056
3057/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QHash<Key, T> &other)
3058 \since 6.0
3059
3060 Inserts all the items in the \a other hash into this hash
3061 and returns a reference to this hash.
3062
3063 \sa insert()
3064*/
3065
3066/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const
3067 \since 5.13
3068
3069 Returns a list containing all the keys in the map. Keys that occur multiple
3070 times in the map occur only once in the returned list.
3071
3072 \sa keys(), values()
3073*/
3074
3075/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key) const
3076 \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue) const
3077
3078 Returns the value associated with the \a key.
3079
3080 If the hash contains no item with the \a key, the function
3081 returns \a defaultValue, or a \l{default-constructed value} if this
3082 parameter has not been supplied.
3083
3084 If there are multiple
3085 items for the \a key in the hash, the value of the most recently
3086 inserted one is returned.
3087*/
3088
3089/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const
3090 \overload
3091
3092 Returns a list of all the values associated with the \a key,
3093 from the most recently inserted to the least recently inserted.
3094
3095 \sa count(), insert()
3096*/
3097
3098/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::operator[](const Key &key)
3099
3100 Returns the value associated with the \a key as a modifiable reference.
3101
3102 If the hash contains no item with the \a key, the function inserts
3103 a \l{default-constructed value} into the hash with the \a key, and
3104 returns a reference to it.
3105
3106 If the hash contains multiple items with the \a key, this function returns
3107 a reference to the most recently inserted value.
3108
3109 \include qhash.cpp qhash-iterator-invalidation-func-desc
3110
3111 \sa insert(), value()
3112*/
3113
3114/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other)
3115
3116 Inserts all the items in the \a other hash into this hash
3117 and returns a reference to this hash.
3118
3119 \sa unite(), insert()
3120*/
3121
3122/*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const
3123
3124 Returns a hash that contains all the items in this hash in
3125 addition to all the items in \a other. If a key is common to both
3126 hashes, the resulting hash will contain the key multiple times.
3127
3128 \sa operator+=()
3129*/
3130
3131/*!
3132 \fn template <class Key, class T> bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
3133 \since 4.3
3134
3135 Returns \c true if the hash contains an item with the \a key and
3136 \a value; otherwise returns \c false.
3137
3138 \sa contains()
3139*/
3140
3141/*!
3142 \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key)
3143 \since 4.3
3144
3145 Removes all the items that have the \a key from the hash.
3146 Returns the number of items removed.
3147
3148 \sa remove()
3149*/
3150
3151/*!
3152 \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key, const T &value)
3153 \since 4.3
3154
3155 Removes all the items that have the \a key and the value \a
3156 value from the hash. Returns the number of items removed.
3157
3158 \sa remove()
3159*/
3160
3161/*!
3162 \fn template <class Key, class T> void QMultiHash<Key, T>::clear()
3163 \since 4.3
3164
3165 Removes all items from the hash and frees up all memory used by it.
3166
3167 \sa remove()
3168*/
3169
3170/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QMultiHash<Key, T>::removeIf(Predicate pred)
3171 \since 6.1
3172
3173 Removes all elements for which the predicate \a pred returns true
3174 from the multi hash.
3175
3176 The function supports predicates which take either an argument of
3177 type \c{QMultiHash<Key, T>::iterator}, or an argument of type
3178 \c{std::pair<const Key &, T &>}.
3179
3180 Returns the number of elements removed, if any.
3181
3182 \sa clear(), take()
3183*/
3184
3185/*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key)
3186
3187 Removes the item with the \a key from the hash and returns
3188 the value associated with it.
3189
3190 If the item does not exist in the hash, the function simply
3191 returns a \l{default-constructed value}. If there are multiple
3192 items for \a key in the hash, only the most recently inserted one
3193 is removed.
3194
3195 If you don't use the return value, remove() is more efficient.
3196
3197 \sa remove()
3198*/
3199
3200/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::keys() const
3201
3202 Returns a list containing all the keys in the hash, in an
3203 arbitrary order. Keys that occur multiple times in the hash
3204 also occur multiple times in the list.
3205
3206 The order is guaranteed to be the same as that used by values().
3207
3208 This function creates a new list, in \l {linear time}. The time and memory
3209 use that entails can be avoided by iterating from \l keyBegin() to
3210 \l keyEnd().
3211
3212 \sa values(), key()
3213*/
3214
3215/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values() const
3216
3217 Returns a list containing all the values in the hash, in an
3218 arbitrary order. If a key is associated with multiple values, all of
3219 its values will be in the list, and not just the most recently
3220 inserted one.
3221
3222 The order is guaranteed to be the same as that used by keys().
3223
3224 This function creates a new list, in \l {linear time}. The time and memory
3225 use that entails can be avoided by iterating from \l keyValueBegin() to
3226 \l keyValueEnd().
3227
3228 \sa keys(), value()
3229*/
3230
3231/*!
3232 \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value) const
3233 \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey) const
3234 \since 4.3
3235
3236 Returns the first key mapped to \a value. If the hash contains no item
3237 mapped to \a value, returns \a defaultKey, or a \l{default-constructed
3238 value}{default-constructed key} if this parameter has not been supplied.
3239
3240 This function can be slow (\l{linear time}), because QMultiHash's
3241 internal data structure is optimized for fast lookup by key, not
3242 by value.
3243*/
3244
3245/*!
3246 \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::count(const Key &key, const T &value) const
3247 \since 4.3
3248
3249 Returns the number of items with the \a key and \a value.
3250
3251 \sa count()
3252*/
3253
3254/*!
3255 \fn template <class Key, class T> typename QMultiHash<Key, T>::iterator QMultiHash<Key, T>::find(const Key &key, const T &value)
3256 \since 4.3
3257
3258 Returns an iterator pointing to the item with the \a key and \a value.
3259 If the hash contains no such item, the function returns end().
3260
3261 If the hash contains multiple items with the \a key and \a value, the
3262 iterator returned points to the most recently inserted item.
3263
3264 \include qhash.cpp qhash-iterator-invalidation-func-desc
3265*/
3266
3267/*!
3268 \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const
3269 \since 4.3
3270 \overload
3271
3272 \include qhash.cpp qhash-iterator-invalidation-func-desc
3273*/
3274
3275/*!
3276 \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constFind(const Key &key, const T &value) const
3277 \since 4.3
3278
3279 Returns an iterator pointing to the item with the \a key and the
3280 \a value in the hash.
3281
3282 If the hash contains no such item, the function returns
3283 constEnd().
3284
3285 \include qhash.cpp qhash-iterator-invalidation-func-desc
3286*/
3287
3288/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin()
3289
3290 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
3291 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>::begin() const
3299
3300 \overload
3301
3302 \include qhash.cpp qhash-iterator-invalidation-func-desc
3303*/
3304
3305/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const
3306 \since 5.0
3307
3308 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3309 in the hash.
3310
3311 \include qhash.cpp qhash-iterator-invalidation-func-desc
3312
3313 \sa begin(), cend()
3314*/
3315
3316/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constBegin() const
3317
3318 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
3319 in the hash.
3320
3321 \include qhash.cpp qhash-iterator-invalidation-func-desc
3322
3323 \sa begin(), constEnd()
3324*/
3325
3326/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyBegin() const
3327 \since 5.6
3328
3329 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
3330 in the hash.
3331
3332 \include qhash.cpp qhash-iterator-invalidation-func-desc
3333
3334 \sa keyEnd()
3335*/
3336
3337/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::end()
3338
3339 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
3340 after the last item in the hash.
3341
3342 \include qhash.cpp qhash-iterator-invalidation-func-desc
3343
3344 \sa begin(), constEnd()
3345*/
3346
3347/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::end() const
3348
3349 \overload
3350*/
3351
3352/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::constEnd() const
3353
3354 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3355 item after the last item in the hash.
3356
3357 \include qhash.cpp qhash-iterator-invalidation-func-desc
3358
3359 \sa constBegin(), end()
3360*/
3361
3362/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cend() const
3363 \since 5.0
3364
3365 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3366 item after the last item in the hash.
3367
3368 \include qhash.cpp qhash-iterator-invalidation-func-desc
3369
3370 \sa cbegin(), end()
3371*/
3372
3373/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::keyEnd() const
3374 \since 5.6
3375
3376 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3377 item after the last key in the hash.
3378
3379 \include qhash.cpp qhash-iterator-invalidation-func-desc
3380
3381 \sa keyBegin()
3382*/
3383
3384/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueBegin()
3385 \since 5.10
3386
3387 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3388 in the hash.
3389
3390 \include qhash.cpp qhash-iterator-invalidation-func-desc
3391
3392 \sa keyValueEnd()
3393*/
3394
3395/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_value_iterator QMultiHash<Key, T>::keyValueEnd()
3396 \since 5.10
3397
3398 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3399 entry after the last entry in the hash.
3400
3401 \include qhash.cpp qhash-iterator-invalidation-func-desc
3402
3403 \sa keyValueBegin()
3404*/
3405
3406/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueBegin() const
3407 \since 5.10
3408
3409 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3410 in the hash.
3411
3412 \include qhash.cpp qhash-iterator-invalidation-func-desc
3413
3414 \sa keyValueEnd()
3415*/
3416
3417/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueBegin() const
3418 \since 5.10
3419
3420 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
3421 in the hash.
3422
3423 \include qhash.cpp qhash-iterator-invalidation-func-desc
3424
3425 \sa keyValueBegin()
3426*/
3427
3428/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::keyValueEnd() const
3429 \since 5.10
3430
3431 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3432 entry after the last entry in the hash.
3433
3434 \include qhash.cpp qhash-iterator-invalidation-func-desc
3435
3436 \sa keyValueBegin()
3437*/
3438
3439/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_key_value_iterator QMultiHash<Key, T>::constKeyValueEnd() const
3440 \since 5.10
3441
3442 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
3443 entry after the last entry in the hash.
3444
3445 \include qhash.cpp qhash-iterator-invalidation-func-desc
3446
3447 \sa constKeyValueBegin()
3448*/
3449
3450/*! \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &
3451 \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &
3452 \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() &&
3453 \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const &&
3454 \since 6.4
3455
3456 Returns a range object that allows iteration over this hash as
3457 key/value pairs. For instance, this range object can be used in a
3458 range-based for loop, in combination with a structured binding declaration:
3459
3460 \snippet code/src_corelib_tools_qhash.cpp 35
3461
3462 Note that both the key and the value obtained this way are
3463 references to the ones in the hash. Specifically, mutating the value
3464 will modify the hash itself.
3465
3466 \include qhash.cpp qhash-iterator-invalidation-func-desc
3467
3468 \sa QKeyValueIterator
3469*/
3470
3471/*! \class QMultiHash::iterator
3472 \inmodule QtCore
3473 \brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash.
3474
3475 QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash
3476 and to modify the value (but not the key) associated
3477 with a particular key. If you want to iterate over a const QMultiHash,
3478 you should use QMultiHash::const_iterator. It is generally good
3479 practice to use QMultiHash::const_iterator on a non-const QMultiHash as
3480 well, unless you need to change the QMultiHash through the iterator.
3481 Const iterators are slightly faster, and can improve code
3482 readability.
3483
3484 The default QMultiHash::iterator constructor creates an uninitialized
3485 iterator. You must initialize it using a QMultiHash function like
3486 QMultiHash::begin(), QMultiHash::end(), or QMultiHash::find() before you can
3487 start iterating. Here's a typical loop that prints all the (key,
3488 value) pairs stored in a hash:
3489
3490 \snippet code/src_corelib_tools_qhash.cpp 17
3491
3492 Unlike QMap, which orders its items by key, QMultiHash stores its
3493 items in an arbitrary order.
3494
3495 Here's an example that increments every value stored in the QMultiHash
3496 by 2:
3497
3498 \snippet code/src_corelib_tools_qhash.cpp 18
3499
3500 To remove elements from a QMultiHash you can use erase_if(QMultiHash\<Key, T\> &map, Predicate pred):
3501
3502 \snippet code/src_corelib_tools_qhash.cpp 21
3503
3504 Multiple iterators can be used on the same hash. However, be aware
3505 that any modification performed directly on the QHash (inserting and
3506 removing items) can cause the iterators to become invalid.
3507
3508 Inserting items into the hash or calling methods such as QHash::reserve()
3509 or QHash::squeeze() can invalidate all iterators pointing into the hash.
3510 Iterators are guaranteed to stay valid only as long as the QHash doesn't have
3511 to grow/shrink its internal hash table.
3512 Using any iterator after a rehashing operation has occurred will lead to undefined behavior.
3513
3514 If you need to keep iterators over a long period of time, we recommend
3515 that you use QMultiMap rather than QHash.
3516
3517 \warning Iterators on implicitly shared containers do not work
3518 exactly like STL-iterators. You should avoid copying a container
3519 while iterators are active on that container. For more information,
3520 read \l{Implicit sharing iterator problem}.
3521
3522 \sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMultiHash::key_value_iterator
3523*/
3524
3525/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator::iterator()
3526
3527 Constructs an uninitialized iterator.
3528
3529 Functions like key(), value(), and operator++() must not be
3530 called on an uninitialized iterator. Use operator=() to assign a
3531 value to it before using it.
3532
3533 \sa QMultiHash::begin(), QMultiHash::end()
3534*/
3535
3536/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::iterator::key() const
3537
3538 Returns the current item's key as a const reference.
3539
3540 There is no direct way of changing an item's key through an
3541 iterator, although it can be done by calling QMultiHash::erase()
3542 followed by QMultiHash::insert().
3543
3544 \sa value()
3545*/
3546
3547/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::value() const
3548
3549 Returns a modifiable reference to the current item's value.
3550
3551 You can change the value of an item by using value() on
3552 the left side of an assignment, for example:
3553
3554 \snippet code/src_corelib_tools_qhash.cpp 22
3555
3556 \sa key(), operator*()
3557*/
3558
3559/*! \fn template <class Key, class T> T &QMultiHash<Key, T>::iterator::operator*() const
3560
3561 Returns a modifiable reference to the current item's value.
3562
3563 Same as value().
3564
3565 \sa key()
3566*/
3567
3568/*! \fn template <class Key, class T> T *QMultiHash<Key, T>::iterator::operator->() const
3569
3570 Returns a pointer to the current item's value.
3571
3572 \sa value()
3573*/
3574
3575/*!
3576 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const iterator &other) const
3577 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator==(const const_iterator &other) const
3578
3579 Returns \c true if \a other points to the same item as this
3580 iterator; otherwise returns \c false.
3581
3582 \sa operator!=()
3583*/
3584
3585/*!
3586 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const iterator &other) const
3587 \fn template <class Key, class T> bool QMultiHash<Key, T>::iterator::operator!=(const const_iterator &other) const
3588
3589 Returns \c true if \a other points to a different item than this
3590 iterator; otherwise returns \c false.
3591
3592 \sa operator==()
3593*/
3594
3595/*!
3596 \fn template <class Key, class T> QMultiHash<Key, T>::iterator &QMultiHash<Key, T>::iterator::operator++()
3597
3598 The prefix ++ operator (\c{++i}) advances the iterator to the
3599 next item in the hash and returns an iterator to the new current
3600 item.
3601
3602 Calling this function on QMultiHash::end() leads to undefined results.
3603*/
3604
3605/*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::iterator::operator++(int)
3606
3607 \overload
3608
3609 The postfix ++ operator (\c{i++}) advances the iterator to the
3610 next item in the hash and returns an iterator to the previously
3611 current item.
3612*/
3613
3614/*! \class QMultiHash::const_iterator
3615 \inmodule QtCore
3616 \brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash.
3617
3618 QMultiHash\<Key, T\>::const_iterator allows you to iterate over a
3619 QMultiHash. If you want to modify the QMultiHash as you
3620 iterate over it, you must use QMultiHash::iterator instead. It is
3621 generally good practice to use QMultiHash::const_iterator on a
3622 non-const QMultiHash as well, unless you need to change the QMultiHash
3623 through the iterator. Const iterators are slightly faster, and
3624 can improve code readability.
3625
3626 The default QMultiHash::const_iterator constructor creates an
3627 uninitialized iterator. You must initialize it using a QMultiHash
3628 function like QMultiHash::cbegin(), QMultiHash::cend(), or
3629 QMultiHash::constFind() before you can start iterating. Here's a typical
3630 loop that prints all the (key, value) pairs stored in a hash:
3631
3632 \snippet code/src_corelib_tools_qhash.cpp 23
3633
3634 Unlike QMap, which orders its items by key, QMultiHash stores its
3635 items in an arbitrary order. The only guarantee is that items that
3636 share the same key (because they were inserted using
3637 a QMultiHash) will appear consecutively, from the most
3638 recently to the least recently inserted value.
3639
3640 Multiple iterators can be used on the same hash. However, be aware
3641 that any modification performed directly on the QMultiHash (inserting and
3642 removing items) can cause the iterators to become invalid.
3643
3644 Inserting items into the hash or calling methods such as QMultiHash::reserve()
3645 or QMultiHash::squeeze() can invalidate all iterators pointing into the hash.
3646 Iterators are guaranteed to stay valid only as long as the QMultiHash doesn't have
3647 to grow/shrink it's internal hash table.
3648 Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior.
3649
3650 If you need to keep iterators over a long period of time, we recommend
3651 that you use QMultiMap rather than QMultiHash.
3652
3653 \warning Iterators on implicitly shared containers do not work
3654 exactly like STL-iterators. You should avoid copying a container
3655 while iterators are active on that container. For more information,
3656 read \l{Implicit sharing iterator problem}.
3657
3658 \sa QMultiHash::iterator, QMultiHash::key_iterator, QMultiHash::const_key_value_iterator
3659*/
3660
3661/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator()
3662
3663 Constructs an uninitialized iterator.
3664
3665 Functions like key(), value(), and operator++() must not be
3666 called on an uninitialized iterator. Use operator=() to assign a
3667 value to it before using it.
3668
3669 \sa QMultiHash::constBegin(), QMultiHash::constEnd()
3670*/
3671
3672/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator(const iterator &other)
3673
3674 Constructs a copy of \a other.
3675*/
3676
3677/*! \fn template <class Key, class T> const Key &QMultiHash<Key, T>::const_iterator::key() const
3678
3679 Returns the current item's key.
3680
3681 \sa value()
3682*/
3683
3684/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::value() const
3685
3686 Returns the current item's value.
3687
3688 \sa key(), operator*()
3689*/
3690
3691/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::const_iterator::operator*() const
3692
3693 Returns the current item's value.
3694
3695 Same as value().
3696
3697 \sa key()
3698*/
3699
3700/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::const_iterator::operator->() const
3701
3702 Returns a pointer to the current item's value.
3703
3704 \sa value()
3705*/
3706
3707/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator==(const const_iterator &other) const
3708
3709 Returns \c true if \a other points to the same item as this
3710 iterator; otherwise returns \c false.
3711
3712 \sa operator!=()
3713*/
3714
3715/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::const_iterator::operator!=(const const_iterator &other) const
3716
3717 Returns \c true if \a other points to a different item than this
3718 iterator; otherwise returns \c false.
3719
3720 \sa operator==()
3721*/
3722
3723/*!
3724 \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator &QMultiHash<Key, T>::const_iterator::operator++()
3725
3726 The prefix ++ operator (\c{++i}) advances the iterator to the
3727 next item in the hash and returns an iterator to the new current
3728 item.
3729
3730 Calling this function on QMultiHash::end() leads to undefined results.
3731*/
3732
3733/*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_iterator::operator++(int)
3734
3735 \overload
3736
3737 The postfix ++ operator (\c{i++}) advances the iterator to the
3738 next item in the hash and returns an iterator to the previously
3739 current item.
3740*/
3741
3742/*! \class QMultiHash::key_iterator
3743 \inmodule QtCore
3744 \since 5.6
3745 \brief The QMultiHash::key_iterator class provides an STL-style const iterator for QMultiHash keys.
3746
3747 QMultiHash::key_iterator is essentially the same as QMultiHash::const_iterator
3748 with the difference that operator*() and operator->() return a key
3749 instead of a value.
3750
3751 For most uses QMultiHash::iterator and QMultiHash::const_iterator should be used,
3752 you can easily access the key by calling QMultiHash::iterator::key():
3753
3754 \snippet code/src_corelib_tools_qhash.cpp 27
3755
3756 However, to have interoperability between QMultiHash's keys and STL-style
3757 algorithms we need an iterator that dereferences to a key instead
3758 of a value. With QMultiHash::key_iterator we can apply an algorithm to a
3759 range of keys without having to call QMultiHash::keys(), which is inefficient
3760 as it costs one QMultiHash iteration and memory allocation to create a temporary
3761 QList.
3762
3763 \snippet code/src_corelib_tools_qhash.cpp 28
3764
3765 QMultiHash::key_iterator is const, it's not possible to modify the key.
3766
3767 The default QMultiHash::key_iterator constructor creates an uninitialized
3768 iterator. You must initialize it using a QMultiHash function like
3769 QMultiHash::keyBegin() or QMultiHash::keyEnd().
3770
3771 \warning Iterators on implicitly shared containers do not work
3772 exactly like STL-iterators. You should avoid copying a container
3773 while iterators are active on that container. For more information,
3774 read \l{Implicit sharing iterator problem}.
3775
3776 \sa QMultiHash::const_iterator, QMultiHash::iterator
3777*/
3778
3779/*! \fn template <class Key, class T> const T &QMultiHash<Key, T>::key_iterator::operator*() const
3780
3781 Returns the current item's key.
3782*/
3783
3784/*! \fn template <class Key, class T> const T *QMultiHash<Key, T>::key_iterator::operator->() const
3785
3786 Returns a pointer to the current item's key.
3787*/
3788
3789/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator==(key_iterator other) const
3790
3791 Returns \c true if \a other points to the same item as this
3792 iterator; otherwise returns \c false.
3793
3794 \sa operator!=()
3795*/
3796
3797/*! \fn template <class Key, class T> bool QMultiHash<Key, T>::key_iterator::operator!=(key_iterator other) const
3798
3799 Returns \c true if \a other points to a different item than this
3800 iterator; otherwise returns \c false.
3801
3802 \sa operator==()
3803*/
3804
3805/*!
3806 \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator &QMultiHash<Key, T>::key_iterator::operator++()
3807
3808 The prefix ++ operator (\c{++i}) advances the iterator to the
3809 next item in the hash and returns an iterator to the new current
3810 item.
3811
3812 Calling this function on QMultiHash::keyEnd() leads to undefined results.
3813*/
3814
3815/*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::key_iterator::operator++(int)
3816
3817 \overload
3818
3819 The postfix ++ operator (\c{i++}) advances the iterator to the
3820 next item in the hash and returns an iterator to the previous
3821 item.
3822*/
3823
3824/*! \fn template <class Key, class T> const_iterator QMultiHash<Key, T>::key_iterator::base() const
3825 Returns the underlying const_iterator this key_iterator is based on.
3826*/
3827
3828/*! \typedef QMultiHash::const_key_value_iterator
3829 \inmodule QtCore
3830 \since 5.10
3831 \brief The QMultiHash::const_key_value_iterator typedef provides an STL-style const iterator for QMultiHash.
3832
3833 QMultiHash::const_key_value_iterator is essentially the same as QMultiHash::const_iterator
3834 with the difference that operator*() returns a key/value pair instead of a
3835 value.
3836
3837 \sa QKeyValueIterator
3838*/
3839
3840/*! \typedef QMultiHash::key_value_iterator
3841 \inmodule QtCore
3842 \since 5.10
3843 \brief The QMultiHash::key_value_iterator typedef provides an STL-style iterator for QMultiHash.
3844
3845 QMultiHash::key_value_iterator is essentially the same as QMultiHash::iterator
3846 with the difference that operator*() returns a key/value pair instead of a
3847 value.
3848
3849 \sa QKeyValueIterator
3850*/
3851
3852/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiHash<Key, T>& hash)
3853 \relates QMultiHash
3854
3855 Writes the hash \a hash to stream \a out.
3856
3857 This function requires the key and value types to implement \c
3858 operator<<().
3859
3860 \sa {Serializing Qt Data Types}
3861*/
3862
3863/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiHash<Key, T> &hash)
3864 \relates QMultiHash
3865
3866 Reads a hash from stream \a in into \a hash.
3867
3868 This function requires the key and value types to implement \c
3869 operator>>().
3870
3871 \sa {Serializing Qt Data Types}
3872*/
3873
3874/*!
3875 \fn template <class Key, class T> size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
3876 \since 5.8
3877 \relates QHash
3878
3879 Returns the hash value for the \a key, using \a seed to seed the calculation.
3880
3881 Type \c T must be supported by qHash().
3882*/
3883
3884/*!
3885 \fn template <class Key, class T> size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0)
3886 \since 5.8
3887 \relates QMultiHash
3888
3889 Returns the hash value for the \a key, using \a seed to seed the calculation.
3890
3891 Type \c T must be supported by qHash().
3892*/
3893
3894/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
3895 \relates QHash
3896 \since 6.1
3897
3898 Removes all elements for which the predicate \a pred returns true
3899 from the hash \a hash.
3900
3901 The function supports predicates which take either an argument of
3902 type \c{QHash<Key, T>::iterator}, or an argument of type
3903 \c{std::pair<const Key &, T &>}.
3904
3905 Returns the number of elements removed, if any.
3906*/
3907
3908/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred)
3909 \relates QMultiHash
3910 \since 6.1
3911
3912 Removes all elements for which the predicate \a pred returns true
3913 from the multi hash \a hash.
3914
3915 The function supports predicates which take either an argument of
3916 type \c{QMultiHash<Key, T>::iterator}, or an argument of type
3917 \c{std::pair<const Key &, T &>}.
3918
3919 Returns the number of elements removed, if any.
3920*/
3921
3922#ifdef QT_HAS_CONSTEXPR_BITOPS
3923namespace QHashPrivate {
3924static_assert(qPopulationCount(v: SpanConstants::NEntries) == 1,
3925 "NEntries must be a power of 2 for bucketForHash() to work.");
3926
3927// ensure the size of a Span does not depend on the template parameters
3928using Node1 = Node<int, int>;
3929static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>));
3930static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>));
3931static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>));
3932static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries);
3933static_assert(qNextPowerOfTwo(v: sizeof(Span<Node1>)) == SpanConstants::NEntries * 2);
3934
3935// ensure allocations are always a power of two, at a minimum NEntries,
3936// obeying the fomula
3937// qNextPowerOfTwo(2 * N);
3938// without overflowing
3939static constexpr size_t NEntries = SpanConstants::NEntries;
3940static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: 1) == NEntries);
3941static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 0) == NEntries);
3942static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 1) == 2 * NEntries);
3943static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 - 1) == 2 * NEntries);
3944static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 0) == 4 * NEntries);
3945static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 1) == 4 * NEntries);
3946static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 - 1) == 4 * NEntries);
3947static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 + 0) == 8 * NEntries);
3948static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1);
3949static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX);
3950static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX);
3951}
3952#endif
3953
3954QT_END_NAMESPACE
3955

Provided by KDAB

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

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