1 | // Copyright (C) 2020 The Qt Company Ltd. |
---|---|
2 | // Copyright (C) 2021 Intel Corporation. |
3 | // Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>. |
4 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
5 | |
6 | // for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h. |
7 | // put it at the beginning so some indirect inclusion doesn't break it |
8 | #ifndef _CRT_RAND_S |
9 | #define _CRT_RAND_S |
10 | #endif |
11 | #include <stdlib.h> |
12 | #include <stdint.h> |
13 | |
14 | #include "qhash.h" |
15 | |
16 | #ifdef truncate |
17 | #undef truncate |
18 | #endif |
19 | |
20 | #include <qbitarray.h> |
21 | #include <qstring.h> |
22 | #include <qglobal.h> |
23 | #include <qbytearray.h> |
24 | #include <qdatetime.h> |
25 | #include <qbasicatomic.h> |
26 | #include <qendian.h> |
27 | #include <private/qrandom_p.h> |
28 | #include <private/qsimd_p.h> |
29 | |
30 | #ifndef QT_BOOTSTRAPPED |
31 | #include <qcoreapplication.h> |
32 | #include <qrandom.h> |
33 | #include <private/qlocale_tools_p.h> |
34 | #endif // QT_BOOTSTRAPPED |
35 | |
36 | // Implementation of SipHash algorithm |
37 | #include "../../3rdparty/siphash/siphash.cpp" |
38 | |
39 | #include <array> |
40 | #include <limits.h> |
41 | |
42 | #if defined(QT_NO_DEBUG) && !defined(NDEBUG) |
43 | # define NDEBUG |
44 | #endif |
45 | #include <assert.h> |
46 | |
47 | #ifdef Q_CC_GNU |
48 | # define Q_DECL_HOT_FUNCTION __attribute__((hot)) |
49 | #else |
50 | # define Q_DECL_HOT_FUNCTION |
51 | #endif |
52 | |
53 | QT_BEGIN_NAMESPACE |
54 | |
55 | void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept; // qstring.cpp |
56 | |
57 | // We assume that pointers and size_t have the same size. If that assumption should fail |
58 | // on a platform the code selecting the different methods below needs to be fixed. |
59 | static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size."); |
60 | |
61 | namespace { |
62 | struct HashSeedStorage |
63 | { |
64 | static constexpr int SeedCount = 2; |
65 | QBasicAtomicInteger<quintptr> seeds[SeedCount] = { Q_BASIC_ATOMIC_INITIALIZER(0), Q_BASIC_ATOMIC_INITIALIZER(0) }; |
66 | |
67 | #if !QT_SUPPORTS_INIT_PRIORITY || defined(QT_BOOTSTRAPPED) |
68 | constexpr HashSeedStorage() = default; |
69 | #else |
70 | HashSeedStorage() { initialize(which: 0); } |
71 | #endif |
72 | |
73 | enum State { |
74 | OverriddenByEnvironment = -1, |
75 | JustInitialized, |
76 | AlreadyInitialized |
77 | }; |
78 | struct StateResult { |
79 | quintptr requestedSeed; |
80 | State state; |
81 | }; |
82 | |
83 | StateResult state(int which = -1); |
84 | Q_DECL_HOT_FUNCTION QHashSeed currentSeed(int which) |
85 | { |
86 | return { state(which).requestedSeed }; |
87 | } |
88 | |
89 | void resetSeed() |
90 | { |
91 | #ifndef QT_BOOTSTRAPPED |
92 | if (state().state < AlreadyInitialized) |
93 | return; |
94 | |
95 | // update the public seed |
96 | QRandomGenerator *generator = QRandomGenerator::system(); |
97 | seeds[0].storeRelaxed(newValue: sizeof(size_t) > sizeof(quint32) |
98 | ? generator->generate64() : generator->generate()); |
99 | #endif |
100 | } |
101 | |
102 | void clearSeed() |
103 | { |
104 | state(); |
105 | seeds[0].storeRelaxed(newValue: 0); // always write (smaller code) |
106 | } |
107 | |
108 | private: |
109 | Q_DECL_COLD_FUNCTION Q_NEVER_INLINE StateResult initialize(int which) noexcept; |
110 | }; |
111 | |
112 | [[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept |
113 | { |
114 | StateResult result = { .requestedSeed: 0, .state: OverriddenByEnvironment }; |
115 | #ifdef QT_BOOTSTRAPPED |
116 | Q_UNUSED(which); |
117 | Q_UNREACHABLE_RETURN(result); |
118 | #else |
119 | // can't use qEnvironmentVariableIntValue (reentrancy) |
120 | const char *seedstr = getenv(name: "QT_HASH_SEED"); |
121 | if (seedstr) { |
122 | auto r = qstrntoll(nptr: seedstr, size: strlen(s: seedstr), base: 10); |
123 | if (r.used > 0 && size_t(r.used) == strlen(s: seedstr)) { |
124 | if (r.result) { |
125 | // can't use qWarning here (reentrancy) |
126 | fprintf(stderr, format: "QT_HASH_SEED: forced seed value is not 0; ignored.\n"); |
127 | } |
128 | |
129 | // we don't have to store to the seed, since it's pre-initialized by |
130 | // the compiler to zero |
131 | return result; |
132 | } |
133 | } |
134 | |
135 | // update the full seed |
136 | auto x = qt_initial_random_value(); |
137 | for (int i = 0; i < SeedCount; ++i) { |
138 | seeds[i].storeRelaxed(newValue: x.data[i]); |
139 | if (which == i) |
140 | result.requestedSeed = x.data[i]; |
141 | } |
142 | result.state = JustInitialized; |
143 | return result; |
144 | #endif |
145 | } |
146 | |
147 | inline HashSeedStorage::StateResult HashSeedStorage::state(int which) |
148 | { |
149 | constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555)); |
150 | StateResult result = { .requestedSeed: BadSeed, .state: AlreadyInitialized }; |
151 | |
152 | #if defined(QT_BOOTSTRAPPED) |
153 | result = { 0, OverriddenByEnvironment }; |
154 | #elif !QT_SUPPORTS_INIT_PRIORITY |
155 | // dynamic initialization |
156 | static auto once = [&]() { |
157 | result = initialize(which); |
158 | return true; |
159 | }(); |
160 | Q_UNUSED(once); |
161 | #endif |
162 | |
163 | if (result.state == AlreadyInitialized && which >= 0) |
164 | return { .requestedSeed: seeds[which].loadRelaxed(), .state: AlreadyInitialized }; |
165 | return result; |
166 | } |
167 | } // unnamed namespace |
168 | |
169 | /* |
170 | The QHash seed itself. |
171 | */ |
172 | #ifdef Q_DECL_INIT_PRIORITY |
173 | Q_DECL_INIT_PRIORITY(05) |
174 | #else |
175 | Q_CONSTINIT |
176 | #endif |
177 | static HashSeedStorage qt_qhash_seed; |
178 | |
179 | /* |
180 | * Hashing for memory segments is based on the public domain MurmurHash2 by |
181 | * Austin Appleby. See http://murmurhash.googlepages.com/ |
182 | */ |
183 | #if QT_POINTER_SIZE == 4 |
184 | Q_NEVER_INLINE Q_DECL_HOT_FUNCTION |
185 | static inline uint murmurhash(const void *key, uint len, uint seed) noexcept |
186 | { |
187 | // 'm' and 'r' are mixing constants generated offline. |
188 | // They're not really 'magic', they just happen to work well. |
189 | |
190 | const unsigned int m = 0x5bd1e995; |
191 | const int r = 24; |
192 | |
193 | // Initialize the hash to a 'random' value |
194 | |
195 | unsigned int h = seed ^ len; |
196 | |
197 | // Mix 4 bytes at a time into the hash |
198 | |
199 | const unsigned char *data = reinterpret_cast<const unsigned char *>(key); |
200 | const unsigned char *end = data + (len & ~3); |
201 | |
202 | while (data != end) { |
203 | size_t k; |
204 | memcpy(&k, data, sizeof(uint)); |
205 | |
206 | k *= m; |
207 | k ^= k >> r; |
208 | k *= m; |
209 | |
210 | h *= m; |
211 | h ^= k; |
212 | |
213 | data += 4; |
214 | } |
215 | |
216 | // Handle the last few bytes of the input array |
217 | len &= 3; |
218 | if (len) { |
219 | unsigned int k = 0; |
220 | end += len; |
221 | |
222 | while (data != end) { |
223 | k <<= 8; |
224 | k |= *data; |
225 | ++data; |
226 | } |
227 | h ^= k; |
228 | h *= m; |
229 | } |
230 | |
231 | // Do a few final mixes of the hash to ensure the last few |
232 | // bytes are well-incorporated. |
233 | |
234 | h ^= h >> 13; |
235 | h *= m; |
236 | h ^= h >> 15; |
237 | |
238 | return h; |
239 | } |
240 | |
241 | #else |
242 | Q_NEVER_INLINE Q_DECL_HOT_FUNCTION |
243 | static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept |
244 | { |
245 | const uint64_t m = 0xc6a4a7935bd1e995ULL; |
246 | const int r = 47; |
247 | |
248 | uint64_t h = seed ^ (len * m); |
249 | |
250 | const unsigned char *data = reinterpret_cast<const unsigned char *>(key); |
251 | const unsigned char *end = data + (len & ~7ul); |
252 | |
253 | while (data != end) { |
254 | uint64_t k; |
255 | memcpy(dest: &k, src: data, n: sizeof(uint64_t)); |
256 | |
257 | k *= m; |
258 | k ^= k >> r; |
259 | k *= m; |
260 | |
261 | h ^= k; |
262 | h *= m; |
263 | |
264 | data += 8; |
265 | } |
266 | |
267 | len &= 7; |
268 | if (len) { |
269 | // handle the last few bytes of input |
270 | size_t k = 0; |
271 | end += len; |
272 | |
273 | while (data != end) { |
274 | k <<= 8; |
275 | k |= *data; |
276 | ++data; |
277 | } |
278 | h ^= k; |
279 | h *= m; |
280 | } |
281 | |
282 | h ^= h >> r; |
283 | h *= m; |
284 | h ^= h >> r; |
285 | |
286 | return h; |
287 | } |
288 | |
289 | #endif |
290 | |
291 | enum ZeroExtension { |
292 | None = 0, |
293 | ByteToWord = 1, |
294 | }; |
295 | |
296 | template <ZeroExtension = None> static size_t |
297 | qHashBits_fallback(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept; |
298 | template <> size_t qHashBits_fallback<None>(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept |
299 | { |
300 | if (size <= QT_POINTER_SIZE) |
301 | return murmurhash(key: p, len: size, seed); |
302 | |
303 | return siphash(in: reinterpret_cast<const uchar *>(p), inlen: size, seed, seed2); |
304 | } |
305 | |
306 | template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept |
307 | { |
308 | auto quick_from_latin1 = [](char16_t *dest, const uchar *data, size_t size) { |
309 | // Quick, "inlined" version for very short blocks |
310 | std::copy_n(first: data, n: size, result: dest); |
311 | }; |
312 | if (size <= QT_POINTER_SIZE / 2) { |
313 | std::array<char16_t, QT_POINTER_SIZE / 2> buf; |
314 | quick_from_latin1(buf.data(), data, size); |
315 | return murmurhash(key: buf.data(), len: size * 2, seed); |
316 | } |
317 | |
318 | constexpr size_t TailSizeMask = sizeof(void *) / 2 - 1; |
319 | std::array<char16_t, 256> buf; |
320 | SipHash<> siphash(size * 2, seed, seed2); |
321 | ptrdiff_t offset = 0; |
322 | for ( ; offset + buf.size() < size; offset += buf.size()) { |
323 | qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: buf.size()); |
324 | siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: sizeof(buf)); |
325 | } |
326 | if (size_t n = size - offset; n > TailSizeMask) { |
327 | n &= ~TailSizeMask; |
328 | qt_from_latin1(dst: buf.data(), str: reinterpret_cast<const char *>(data) + offset, size: n); |
329 | siphash.addBlock(in: reinterpret_cast<uint8_t *>(buf.data()), inlen: n * 2); |
330 | offset += n; |
331 | } |
332 | |
333 | quick_from_latin1(buf.data(), data + offset, size - offset); |
334 | return siphash.finalize(in: reinterpret_cast<uint8_t *>(buf.data()), left: (size - offset) * 2); |
335 | } |
336 | |
337 | #if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__) // GCC |
338 | # define QHASH_AES_SANITIZER_BUILD |
339 | #elif __has_feature(address_sanitizer) || __has_feature(thread_sanitizer) // Clang |
340 | # define QHASH_AES_SANITIZER_BUILD |
341 | #endif |
342 | |
343 | // When built with a sanitizer, aeshash() is rightfully reported to have a |
344 | // heap-buffer-overflow issue. However, we consider it to be safe in this |
345 | // specific case and overcome the problem by correctly discarding the |
346 | // out-of-range bits. To allow building the code with sanitizer, |
347 | // QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage. |
348 | #if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \ |
349 | !defined(QHASH_AES_SANITIZER_BUILD) |
350 | # define AESHASH |
351 | # define QT_FUNCTION_TARGET_STRING_AES_AVX2 "avx2,aes" |
352 | # define QT_FUNCTION_TARGET_STRING_AES_AVX512 \ |
353 | QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \ |
354 | QT_FUNCTION_TARGET_STRING_AES |
355 | # define QT_FUNCTION_TARGET_STRING_VAES_AVX512 \ |
356 | QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \ |
357 | QT_FUNCTION_TARGET_STRING_VAES |
358 | # undef QHASH_AES_SANITIZER_BUILD |
359 | # if QT_POINTER_SIZE == 8 |
360 | # define mm_set1_epz _mm_set1_epi64x |
361 | # define mm_cvtsz_si128 _mm_cvtsi64_si128 |
362 | # define mm_cvtsi128_sz _mm_cvtsi128_si64 |
363 | # define mm256_set1_epz _mm256_set1_epi64x |
364 | # else |
365 | # define mm_set1_epz _mm_set1_epi32 |
366 | # define mm_cvtsz_si128 _mm_cvtsi32_si128 |
367 | # define mm_cvtsi128_sz _mm_cvtsi128_si32 |
368 | # define mm256_set1_epz _mm256_set1_epi32 |
369 | # endif |
370 | |
371 | namespace { |
372 | // This is inspired by the algorithm in the Go language. See: |
373 | // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_amd64.s#L1105 |
374 | // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_386.s#L908 |
375 | // |
376 | // Even though we're using the AESENC instruction from the CPU, this code |
377 | // is not encryption and this routine makes no claim to be |
378 | // cryptographically secure. We're simply using the instruction that performs |
379 | // the scrambling round (step 3 in [1]) because it's just very good at |
380 | // spreading the bits around. |
381 | // |
382 | // Note on Latin-1 hashing (ZX == ByteToWord): for simplicity of the |
383 | // algorithm, we pass sizes equivalent to the UTF-16 content (ZX == None). |
384 | // That means we must multiply by 2 on entry, divide by 2 on pointer |
385 | // advancing, and load half as much data from memory (though we produce |
386 | // exactly as much data in registers). The compilers appear to optimize |
387 | // this out. |
388 | // |
389 | // [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm |
390 | |
391 | template <ZeroExtension ZX, typename T> static const T *advance(const T *ptr, ptrdiff_t n) |
392 | { |
393 | if constexpr (ZX == None) |
394 | return ptr + n; |
395 | |
396 | // see note above on ZX == ByteToWord hashing |
397 | auto p = reinterpret_cast<const uchar *>(ptr); |
398 | n *= sizeof(T); |
399 | return reinterpret_cast<const T *>(p + n/2); |
400 | } |
401 | |
402 | template <ZeroExtension> static __m128i loadu128(const void *ptr); |
403 | template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<None>(const void *ptr) |
404 | { |
405 | return _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr)); |
406 | } |
407 | template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<ByteToWord>(const void *ptr) |
408 | { |
409 | // use a MOVQ followed by PMOVZXBW |
410 | // the compiler usually combines them as a single, loading PMOVZXBW |
411 | __m128i data = _mm_loadl_epi64(p: static_cast<const __m128i *>(ptr)); |
412 | return _mm_cvtepu8_epi16(V: data); |
413 | } |
414 | |
415 | // hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1") |
416 | static void Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) QT_VECTORCALL |
417 | hash16bytes(__m128i &state0, __m128i data) |
418 | { |
419 | state0 = _mm_xor_si128(a: state0, b: data); |
420 | state0 = _mm_aesenc_si128(V: state0, R: state0); |
421 | state0 = _mm_aesenc_si128(V: state0, R: state0); |
422 | state0 = _mm_aesenc_si128(V: state0, R: state0); |
423 | } |
424 | |
425 | // hash twice 16 bytes, running 2 scramble rounds of AES on itself |
426 | template <ZeroExtension ZX> |
427 | static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL |
428 | hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1) |
429 | { |
430 | __m128i data0 = loadu128<ZX>(src0); |
431 | __m128i data1 = loadu128<ZX>(src1); |
432 | state0 = _mm_xor_si128(a: data0, b: state0); |
433 | state1 = _mm_xor_si128(a: data1, b: state1); |
434 | state0 = _mm_aesenc_si128(V: state0, R: state0); |
435 | state1 = _mm_aesenc_si128(V: state1, R: state1); |
436 | state0 = _mm_aesenc_si128(V: state0, R: state0); |
437 | state1 = _mm_aesenc_si128(V: state1, R: state1); |
438 | } |
439 | |
440 | struct AESHashSeed |
441 | { |
442 | __m128i state0; |
443 | __m128i mseed2; |
444 | AESHashSeed(size_t seed, size_t seed2) QT_FUNCTION_TARGET(AES); |
445 | __m128i state1() const QT_FUNCTION_TARGET(AES); |
446 | __m256i state0_256() const QT_FUNCTION_TARGET(AES_AVX2) |
447 | { return _mm256_set_m128i(hi: state1(), lo: state0); } |
448 | }; |
449 | } // unnamed namespace |
450 | |
451 | Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2) |
452 | { |
453 | __m128i mseed = mm_cvtsz_si128(a: seed); |
454 | mseed2 = mm_set1_epz(q: seed2); |
455 | |
456 | // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, 0, 0, 0 ] |
457 | mseed = _mm_insert_epi16(mseed, short(seed), 4); |
458 | // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, len, len, len ] |
459 | mseed = _mm_shufflehi_epi16(mseed, 0); |
460 | |
461 | // merge with the process-global seed |
462 | __m128i key = _mm_xor_si128(a: mseed, b: mseed2); |
463 | |
464 | // scramble the key |
465 | __m128i state0 = _mm_aesenc_si128(V: key, R: key); |
466 | this->state0 = state0; |
467 | } |
468 | |
469 | Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const |
470 | { |
471 | { |
472 | // unlike the Go code, we don't have more per-process seed |
473 | __m128i state1 = _mm_aesenc_si128(V: state0, R: mseed2); |
474 | return state1; |
475 | } |
476 | } |
477 | |
478 | template <ZeroExtension ZX> |
479 | static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL |
480 | aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend) |
481 | { |
482 | { |
483 | const __m128i *src2 = advance<ZX>(srcend, -1); |
484 | if (advance<ZX>(src, 1) < srcend) { |
485 | // epilogue: between 16 and 31 bytes |
486 | hash2x16bytes<ZX>(state0, state1, src, src2); |
487 | } else if (src != srcend) { |
488 | // epilogue: between 1 and 16 bytes, overlap with the end |
489 | __m128i data = loadu128<ZX>(src2); |
490 | hash16bytes(state0, data); |
491 | } |
492 | |
493 | // combine results: |
494 | state0 = _mm_xor_si128(a: state0, b: state1); |
495 | } |
496 | |
497 | return mm_cvtsi128_sz(a: state0); |
498 | } |
499 | |
500 | // load all 16 bytes and mask off the bytes past the end of the source |
501 | static const qint8 maskarray[] = { |
502 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, |
503 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
504 | }; |
505 | |
506 | // load 16 bytes ending at the data end, then shuffle them to the beginning |
507 | static const qint8 shufflecontrol[] = { |
508 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, |
509 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 |
510 | }; |
511 | |
512 | template <ZeroExtension ZX> |
513 | static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL |
514 | aeshash128_lt16(__m128i state0, const __m128i *src, const __m128i *srcend, size_t len) |
515 | { |
516 | if (len) { |
517 | // We're going to load 16 bytes and mask zero the part we don't care |
518 | // (the hash of a short string is different from the hash of a longer |
519 | // including NULLs at the end because the length is in the key) |
520 | // WARNING: this may produce valgrind warnings, but it's safe |
521 | |
522 | constexpr quintptr CachelineSize = 64; |
523 | __m128i data; |
524 | |
525 | if ((quintptr(src) & (CachelineSize / 2)) == 0) { |
526 | // lower half of the cacheline: |
527 | __m128i mask = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(maskarray + 15 - len)); |
528 | data = loadu128<ZX>(src); |
529 | data = _mm_and_si128(a: data, b: mask); |
530 | } else { |
531 | // upper half of the cacheline: |
532 | __m128i control = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len)); |
533 | data = loadu128<ZX>(advance<ZX>(srcend, -1)); |
534 | data = _mm_shuffle_epi8(a: data, b: control); |
535 | } |
536 | |
537 | hash16bytes(state0, data); |
538 | } |
539 | return mm_cvtsi128_sz(a: state0); |
540 | } |
541 | |
542 | template <ZeroExtension ZX> |
543 | static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL |
544 | aeshash128_ge32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend) |
545 | { |
546 | // main loop: scramble two 16-byte blocks |
547 | for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2)) |
548 | hash2x16bytes<ZX>(state0, state1, src, advance<ZX>(src, 1)); |
549 | |
550 | return aeshash128_16to32<ZX>(state0, state1, src, srcend); |
551 | } |
552 | |
553 | # if QT_COMPILER_SUPPORTS_HERE(VAES) |
554 | template <ZeroExtension> static __m256i loadu256(const void *ptr); |
555 | template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<None>(const void *ptr) |
556 | { |
557 | return _mm256_loadu_si256(p: reinterpret_cast<const __m256i *>(ptr)); |
558 | } |
559 | template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<ByteToWord>(const void *ptr) |
560 | { |
561 | // VPMOVZXBW xmm, ymm |
562 | __m128i data = _mm_loadu_si128(p: reinterpret_cast<const __m128i *>(ptr)); |
563 | return _mm256_cvtepu8_epi16(V: data); |
564 | } |
565 | |
566 | template <ZeroExtension ZX> |
567 | static size_t QT_FUNCTION_TARGET(VAES_AVX512) QT_VECTORCALL |
568 | aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len) |
569 | { |
570 | __m128i state0_128 = _mm256_castsi256_si128(a: state0); |
571 | if (len) { |
572 | __m256i data; |
573 | if constexpr (ZX == None) { |
574 | __mmask32 mask = _bzhi_u32(X: -1, Y: unsigned(len)); |
575 | data = _mm256_maskz_loadu_epi8(U: mask, P: p); |
576 | } else { |
577 | __mmask16 mask = _bzhi_u32(X: -1, Y: unsigned(len) / 2); |
578 | __m128i data0 = _mm_maskz_loadu_epi8(U: mask, P: p); |
579 | data = _mm256_cvtepu8_epi16(V: data0); |
580 | } |
581 | __m128i data0 = _mm256_castsi256_si128(a: data); |
582 | if (len >= sizeof(__m128i)) { |
583 | state0 = _mm256_xor_si256(a: state0, b: data); |
584 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
585 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
586 | // we're XOR'ing the two halves so we skip the third AESENC |
587 | // state0 = _mm256_aesenc_epi128(state0, state0); |
588 | |
589 | // XOR the two halves and extract |
590 | __m128i low = _mm256_extracti128_si256(state0, 0); |
591 | __m128i high = _mm256_extracti128_si256(state0, 1); |
592 | state0_128 = _mm_xor_si128(a: low, b: high); |
593 | } else { |
594 | hash16bytes(state0&: state0_128, data: data0); |
595 | } |
596 | } |
597 | return mm_cvtsi128_sz(a: state0_128); |
598 | } |
599 | |
600 | template <ZeroExtension ZX> |
601 | static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL |
602 | aeshash256_ge32(__m256i state0, const __m128i *s, const __m128i *end, size_t len) |
603 | { |
604 | static const auto hash32bytes = [](__m256i &state0, __m256i data) QT_FUNCTION_TARGET(VAES) { |
605 | state0 = _mm256_xor_si256(a: state0, b: data); |
606 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
607 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
608 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
609 | }; |
610 | |
611 | // hash twice 32 bytes, running 2 scramble rounds of AES on itself |
612 | const auto hash2x32bytes = [](__m256i &state0, __m256i &state1, const void *src0, |
613 | const void *src1) QT_FUNCTION_TARGET(VAES) { |
614 | __m256i data0 = loadu256<ZX>(src0); |
615 | __m256i data1 = loadu256<ZX>(src1); |
616 | state0 = _mm256_xor_si256(a: data0, b: state0); |
617 | state1 = _mm256_xor_si256(a: data1, b: state1); |
618 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
619 | state1 = _mm256_aesenc_epi128(A: state1, B: state1); |
620 | state0 = _mm256_aesenc_epi128(A: state0, B: state0); |
621 | state1 = _mm256_aesenc_epi128(A: state1, B: state1); |
622 | }; |
623 | |
624 | const __m256i *src = reinterpret_cast<const __m256i *>(s); |
625 | const __m256i *srcend = reinterpret_cast<const __m256i *>(end); |
626 | |
627 | __m256i state1 = _mm256_aesenc_epi128(A: state0, mm256_set1_epz(q: len)); |
628 | |
629 | // main loop: scramble two 32-byte blocks |
630 | for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2)) |
631 | hash2x32bytes(state0, state1, src, advance<ZX>(src, 1)); |
632 | |
633 | const __m256i *src2 = advance<ZX>(srcend, -1); |
634 | if (advance<ZX>(src, 1) < srcend) { |
635 | // epilogue: between 32 and 31 bytes |
636 | hash2x32bytes(state0, state1, src, src2); |
637 | } else if (src != srcend) { |
638 | // epilogue: between 1 and 32 bytes, overlap with the end |
639 | __m256i data = loadu256<ZX>(src2); |
640 | hash32bytes(state0, data); |
641 | } |
642 | |
643 | // combine results: |
644 | state0 = _mm256_xor_si256(a: state0, b: state1); |
645 | |
646 | // XOR the two halves and extract |
647 | __m128i low = _mm256_extracti128_si256(state0, 0); |
648 | __m128i high = _mm256_extracti128_si256(state0, 1); |
649 | return mm_cvtsi128_sz(a: _mm_xor_si128(a: low, b: high)); |
650 | } |
651 | |
652 | template <ZeroExtension ZX> |
653 | static size_t QT_FUNCTION_TARGET(VAES) |
654 | aeshash256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept |
655 | { |
656 | AESHashSeed state(seed, seed2); |
657 | auto src = reinterpret_cast<const __m128i *>(p); |
658 | const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); |
659 | |
660 | if (len < sizeof(__m128i)) |
661 | return aeshash128_lt16<ZX>(state.state0, src, srcend, len); |
662 | |
663 | if (len <= sizeof(__m256i)) |
664 | return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend); |
665 | |
666 | return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len); |
667 | } |
668 | |
669 | template <ZeroExtension ZX> |
670 | static size_t QT_FUNCTION_TARGET(VAES_AVX512) |
671 | aeshash256_avx256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept |
672 | { |
673 | AESHashSeed state(seed, seed2); |
674 | auto src = reinterpret_cast<const __m128i *>(p); |
675 | const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); |
676 | |
677 | if (len <= sizeof(__m256i)) |
678 | return aeshash256_lt32_avx256<ZX>(state.state0_256(), p, len); |
679 | |
680 | return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len); |
681 | } |
682 | # endif // VAES |
683 | |
684 | template <ZeroExtension ZX> |
685 | static size_t QT_FUNCTION_TARGET(AES) |
686 | aeshash128(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept |
687 | { |
688 | AESHashSeed state(seed, seed2); |
689 | auto src = reinterpret_cast<const __m128i *>(p); |
690 | const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); |
691 | |
692 | if (len < sizeof(__m128i)) |
693 | return aeshash128_lt16<ZX>(state.state0, src, srcend, len); |
694 | |
695 | if (len <= sizeof(__m256i)) |
696 | return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend); |
697 | |
698 | return aeshash128_ge32<ZX>(state.state0, state.state1(), src, srcend); |
699 | } |
700 | |
701 | template <ZeroExtension ZX = None> |
702 | static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept |
703 | { |
704 | if constexpr (ZX == ByteToWord) |
705 | len *= 2; // see note above on ZX == ByteToWord hashing |
706 | |
707 | # if QT_COMPILER_SUPPORTS_HERE(VAES) |
708 | if (qCpuHasFeature(VAES)) { |
709 | if (qCpuHasFeature(AVX512VL)) |
710 | return aeshash256_avx256<ZX>(p, len, seed, seed2); |
711 | return aeshash256<ZX>(p, len, seed, seed2); |
712 | } |
713 | # endif |
714 | return aeshash128<ZX>(p, len, seed, seed2); |
715 | } |
716 | #endif // x86 AESNI |
717 | |
718 | #if defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED) |
719 | QT_FUNCTION_TARGET(AES) |
720 | static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept |
721 | { |
722 | uint8x16_t key; |
723 | # if QT_POINTER_SIZE == 8 |
724 | uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2)); |
725 | key = vreinterpretq_u8_u64(vseed); |
726 | # else |
727 | |
728 | uint32x2_t vseed = vmov_n_u32(seed); |
729 | vseed = vset_lane_u32(seed2, vseed, 1); |
730 | key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed)); |
731 | # endif |
732 | |
733 | // Compared to x86 AES, ARM splits each round into two instructions |
734 | // and includes the pre-xor instead of the post-xor. |
735 | const auto hash16bytes = [](uint8x16_t &state0, uint8x16_t data) { |
736 | auto state1 = state0; |
737 | state0 = vaeseq_u8(state0, data); |
738 | state0 = vaesmcq_u8(state0); |
739 | auto state2 = state0; |
740 | state0 = vaeseq_u8(state0, state1); |
741 | state0 = vaesmcq_u8(state0); |
742 | auto state3 = state0; |
743 | state0 = vaeseq_u8(state0, state2); |
744 | state0 = vaesmcq_u8(state0); |
745 | state0 = veorq_u8(state0, state3); |
746 | }; |
747 | |
748 | uint8x16_t state0 = key; |
749 | |
750 | if (len < 8) |
751 | goto lt8; |
752 | if (len < 16) |
753 | goto lt16; |
754 | if (len < 32) |
755 | goto lt32; |
756 | |
757 | // rounds of 32 bytes |
758 | { |
759 | // Make state1 = ~state0: |
760 | uint8x16_t state1 = veorq_u8(state0, vdupq_n_u8(255)); |
761 | |
762 | // do simplified rounds of 32 bytes: unlike the Go code, we only |
763 | // scramble twice and we keep 256 bits of state |
764 | const auto *e = p + len - 31; |
765 | while (p < e) { |
766 | uint8x16_t data0 = vld1q_u8(p); |
767 | uint8x16_t data1 = vld1q_u8(p + 16); |
768 | auto oldstate0 = state0; |
769 | auto oldstate1 = state1; |
770 | state0 = vaeseq_u8(state0, data0); |
771 | state1 = vaeseq_u8(state1, data1); |
772 | state0 = vaesmcq_u8(state0); |
773 | state1 = vaesmcq_u8(state1); |
774 | auto laststate0 = state0; |
775 | auto laststate1 = state1; |
776 | state0 = vaeseq_u8(state0, oldstate0); |
777 | state1 = vaeseq_u8(state1, oldstate1); |
778 | state0 = vaesmcq_u8(state0); |
779 | state1 = vaesmcq_u8(state1); |
780 | state0 = veorq_u8(state0, laststate0); |
781 | state1 = veorq_u8(state1, laststate1); |
782 | p += 32; |
783 | } |
784 | state0 = veorq_u8(state0, state1); |
785 | } |
786 | len &= 0x1f; |
787 | |
788 | // do we still have 16 or more bytes? |
789 | if (len & 0x10) { |
790 | lt32: |
791 | uint8x16_t data = vld1q_u8(p); |
792 | hash16bytes(state0, data); |
793 | p += 16; |
794 | } |
795 | len &= 0xf; |
796 | |
797 | if (len & 0x08) { |
798 | lt16: |
799 | uint8x8_t data8 = vld1_u8(p); |
800 | uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0)); |
801 | hash16bytes(state0, data); |
802 | p += 8; |
803 | } |
804 | len &= 0x7; |
805 | |
806 | lt8: |
807 | if (len) { |
808 | // load the last chunk of data |
809 | // We're going to load 8 bytes and mask zero the part we don't care |
810 | // (the hash of a short string is different from the hash of a longer |
811 | // including NULLs at the end because the length is in the key) |
812 | // WARNING: this may produce valgrind warnings, but it's safe |
813 | |
814 | uint8x8_t data8; |
815 | |
816 | if (Q_LIKELY(quintptr(p + 8) & 0xff8)) { |
817 | // same page, we definitely can't fault: |
818 | // load all 8 bytes and mask off the bytes past the end of the source |
819 | static const qint8 maskarray[] = { |
820 | -1, -1, -1, -1, -1, -1, -1, |
821 | 0, 0, 0, 0, 0, 0, 0, |
822 | }; |
823 | uint8x8_t mask = vld1_u8(reinterpret_cast<const quint8 *>(maskarray) + 7 - len); |
824 | data8 = vld1_u8(p); |
825 | data8 = vand_u8(data8, mask); |
826 | } else { |
827 | // too close to the end of the page, it could fault: |
828 | // load 8 bytes ending at the data end, then shuffle them to the beginning |
829 | static const qint8 shufflecontrol[] = { |
830 | 1, 2, 3, 4, 5, 6, 7, |
831 | -1, -1, -1, -1, -1, -1, -1, |
832 | }; |
833 | uint8x8_t control = vld1_u8(reinterpret_cast<const quint8 *>(shufflecontrol) + 7 - len); |
834 | data8 = vld1_u8(p - 8 + len); |
835 | data8 = vtbl1_u8(data8, control); |
836 | } |
837 | uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0)); |
838 | hash16bytes(state0, data); |
839 | } |
840 | |
841 | // extract state0 |
842 | # if QT_POINTER_SIZE == 8 |
843 | return vgetq_lane_u64(vreinterpretq_u64_u8(state0), 0); |
844 | # else |
845 | return vgetq_lane_u32(vreinterpretq_u32_u8(state0), 0); |
846 | # endif |
847 | } |
848 | #endif |
849 | |
850 | size_t qHashBits(const void *p, size_t size, size_t seed) noexcept |
851 | { |
852 | #ifdef QT_BOOTSTRAPPED |
853 | // the seed is always 0 in bootstrapped mode (no seed generation code), |
854 | // so help the compiler do dead code elimination |
855 | seed = 0; |
856 | #endif |
857 | // mix in the length as a secondary seed. For seed == 0, seed2 must be |
858 | // size, to match what we used to do prior to Qt 6.2. |
859 | size_t seed2 = size; |
860 | if (seed) |
861 | seed2 = qt_qhash_seed.currentSeed(which: 1); |
862 | |
863 | auto data = reinterpret_cast<const uchar *>(p); |
864 | #ifdef AESHASH |
865 | if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2)) |
866 | return aeshash(p: data, len: size, seed, seed2); |
867 | #elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(CRYPTO) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED) |
868 | if (seed && qCpuHasFeature(AES)) |
869 | return aeshash(data, size, seed, seed2); |
870 | #endif |
871 | |
872 | return qHashBits_fallback<>(p: data, size, seed, seed2); |
873 | } |
874 | |
875 | size_t qHash(QByteArrayView key, size_t seed) noexcept |
876 | { |
877 | return qHashBits(p: key.constData(), size: size_t(key.size()), seed); |
878 | } |
879 | |
880 | size_t qHash(QStringView key, size_t seed) noexcept |
881 | { |
882 | return qHashBits(p: key.data(), size: key.size()*sizeof(QChar), seed); |
883 | } |
884 | |
885 | #ifndef QT_BOOTSTRAPPED |
886 | size_t qHash(const QBitArray &bitArray, size_t seed) noexcept |
887 | { |
888 | qsizetype m = bitArray.d.size() - 1; |
889 | size_t result = qHashBits(p: reinterpret_cast<const uchar *>(bitArray.d.constData()), size: size_t(qMax(a: 0, b: m)), seed); |
890 | |
891 | // deal with the last 0 to 7 bits manually, because we can't trust that |
892 | // the padding is initialized to 0 in bitArray.d |
893 | qsizetype n = bitArray.size(); |
894 | if (n & 0x7) |
895 | result = ((result << 4) + bitArray.d.at(i: m)) & ((1 << n) - 1); |
896 | return result; |
897 | } |
898 | #endif |
899 | |
900 | size_t qHash(QLatin1StringView key, size_t seed) noexcept |
901 | { |
902 | #ifdef QT_BOOTSTRAPPED |
903 | // the seed is always 0 in bootstrapped mode (no seed generation code), |
904 | // so help the compiler do dead code elimination |
905 | seed = 0; |
906 | #endif |
907 | |
908 | auto data = reinterpret_cast<const uchar *>(key.data()); |
909 | size_t size = key.size(); |
910 | |
911 | // Mix in the length as a secondary seed. |
912 | // Multiplied by 2 to match the byte size of the equiavlent UTF-16 string. |
913 | size_t seed2 = size * 2; |
914 | if (seed) |
915 | seed2 = qt_qhash_seed.currentSeed(which: 1); |
916 | |
917 | #if defined(AESHASH) |
918 | if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2)) |
919 | return aeshash<ByteToWord>(p: data, len: size, seed, seed2); |
920 | #endif |
921 | return qHashBits_fallback<ByteToWord>(data, size, seed, seed2); |
922 | } |
923 | |
924 | /*! |
925 | \class QHashSeed |
926 | \inmodule QtCore |
927 | \since 6.2 |
928 | |
929 | The QHashSeed class is used to convey the QHash seed. This is used |
930 | internally by QHash and provides three static member functions to allow |
931 | users to obtain the hash and to reset it. |
932 | |
933 | QHash and the qHash() functions implement what is called as "salted hash". |
934 | The intent is that different applications and different instances of the |
935 | same application will produce different hashing values for the same input, |
936 | thus causing the ordering of elements in QHash to be unpredictable by |
937 | external observers. This improves the applications' resilience against |
938 | attacks that attempt to force hashing tables into degenerate mode. |
939 | |
940 | Most applications will not need to deal directly with the hash seed, as |
941 | QHash will do so when needed. However, applications may wish to use this |
942 | for their own purposes in the same way as QHash does: as an |
943 | application-global random value (but see \l QRandomGenerator too). Note |
944 | that the global hash seed may change during the application's lifetime, if |
945 | the resetRandomGlobalSeed() function is called. Users of the global hash |
946 | need to store the value they are using and not rely on getting it again. |
947 | |
948 | This class also implements functionality to set the hash seed to a |
949 | deterministic value, which the qHash() functions will take to mean that |
950 | they should use a fixed hashing function on their data too. This |
951 | functionality is only meant to be used in debugging applications. This |
952 | behavior can also be controlled by setting the \c QT_HASH_SEED environment |
953 | variable to the value zero (any other value is ignored). |
954 | |
955 | \sa QHash, QRandomGenerator |
956 | */ |
957 | |
958 | /*! |
959 | \fn QHashSeed::QHashSeed(size_t data) |
960 | |
961 | Constructs a new QHashSeed object using \a data as the seed. |
962 | */ |
963 | |
964 | /*! |
965 | \fn QHashSeed::operator size_t() const |
966 | |
967 | Converts the returned hash seed into a \c size_t. |
968 | */ |
969 | |
970 | /*! |
971 | \threadsafe |
972 | |
973 | Returns the current global QHash seed. The value returned by this function |
974 | will be zero if setDeterministicGlobalSeed() has been called or if the |
975 | \c{QT_HASH_SEED} environment variable is set to zero. |
976 | */ |
977 | QHashSeed QHashSeed::globalSeed() noexcept |
978 | { |
979 | return qt_qhash_seed.currentSeed(which: 0); |
980 | } |
981 | |
982 | /*! |
983 | \threadsafe |
984 | |
985 | Forces the Qt hash seed to a deterministic value (zero) and asks the |
986 | qHash() functions to use a pre-determined hashing function. This mode is |
987 | only useful for debugging and should not be used in production code. |
988 | |
989 | Regular operation can be restored by calling resetRandomGlobalSeed(). |
990 | */ |
991 | void QHashSeed::setDeterministicGlobalSeed() |
992 | { |
993 | qt_qhash_seed.clearSeed(); |
994 | } |
995 | |
996 | /*! |
997 | \threadsafe |
998 | |
999 | Reseeds the Qt hashing seed to a new, random value. Calling this function |
1000 | is not necessary, but long-running applications may want to do so after a |
1001 | long period of time in which information about its hash may have been |
1002 | exposed to potential attackers. |
1003 | |
1004 | If the environment variable \c QT_HASH_SEED is set to zero, calling this |
1005 | function will result in a no-op. |
1006 | |
1007 | Qt never calls this function during the execution of the application, but |
1008 | unless the \c QT_HASH_SEED variable is set to 0, the hash seed returned by |
1009 | globalSeed() will be a random value as if this function had been called. |
1010 | */ |
1011 | void QHashSeed::resetRandomGlobalSeed() |
1012 | { |
1013 | qt_qhash_seed.resetSeed(); |
1014 | } |
1015 | |
1016 | #if QT_DEPRECATED_SINCE(6,6) |
1017 | /*! \relates QHash |
1018 | \since 5.6 |
1019 | \deprecated [6.6] Use QHashSeed::globalSeed() instead. |
1020 | |
1021 | Returns the current global QHash seed. |
1022 | |
1023 | The seed is set in any newly created QHash. See \l{qHash} about how this seed |
1024 | is being used by QHash. |
1025 | |
1026 | \sa QHashSeed, QHashSeed::globalSeed() |
1027 | */ |
1028 | int qGlobalQHashSeed() |
1029 | { |
1030 | return int(QHashSeed::globalSeed() & INT_MAX); |
1031 | } |
1032 | |
1033 | /*! \relates QHash |
1034 | \since 5.6 |
1035 | \deprecated [6.6] Use QHashSeed instead. |
1036 | |
1037 | Sets the global QHash seed to \a newSeed. |
1038 | |
1039 | Manually setting the global QHash seed value should be done only for testing |
1040 | and debugging purposes, when deterministic and reproducible behavior on a QHash |
1041 | is needed. We discourage to do it in production code as it can make your |
1042 | application susceptible to \l{algorithmic complexity attacks}. |
1043 | |
1044 | From Qt 5.10 and onwards, the only allowed values are 0 and -1. Passing the |
1045 | value -1 will reinitialize the global QHash seed to a random value, while |
1046 | the value of 0 is used to request a stable algorithm for C++ primitive |
1047 | types types (like \c int) and string types (QString, QByteArray). |
1048 | |
1049 | The seed is set in any newly created QHash. See \l{qHash} about how this seed |
1050 | is being used by QHash. |
1051 | |
1052 | If the environment variable \c QT_HASH_SEED is set, calling this function will |
1053 | result in a no-op. |
1054 | |
1055 | \sa QHashSeed::globalSeed(), QHashSeed |
1056 | */ |
1057 | void qSetGlobalQHashSeed(int newSeed) |
1058 | { |
1059 | if (Q_LIKELY(newSeed == 0 || newSeed == -1)) { |
1060 | if (newSeed == 0) |
1061 | QHashSeed::setDeterministicGlobalSeed(); |
1062 | else |
1063 | QHashSeed::resetRandomGlobalSeed(); |
1064 | } else { |
1065 | // can't use qWarning here (reentrancy) |
1066 | fprintf(stderr, format: "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n"); |
1067 | } |
1068 | } |
1069 | #endif // QT_DEPRECATED_SINCE(6,6) |
1070 | |
1071 | /*! |
1072 | \internal |
1073 | |
1074 | Private copy of the implementation of the Qt 4 qHash algorithm for strings, |
1075 | (that is, QChar-based arrays, so all QString-like classes), |
1076 | to be used wherever the result is somehow stored or reused across multiple |
1077 | Qt versions. The public qHash implementation can change at any time, |
1078 | therefore one must not rely on the fact that it will always give the same |
1079 | results. |
1080 | |
1081 | The qt_hash functions must *never* change their results. |
1082 | |
1083 | This function can hash discontiguous memory by invoking it on each chunk, |
1084 | passing the previous's result in the next call's \a chained argument. |
1085 | */ |
1086 | uint qt_hash(QStringView key, uint chained) noexcept |
1087 | { |
1088 | 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 | */ |
1386 | size_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 | */ |
1404 | size_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 |
3923 | namespace QHashPrivate { |
3924 | static_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 |
3928 | using Node1 = Node<int, int>; |
3929 | static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>)); |
3930 | static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>)); |
3931 | static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>)); |
3932 | static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries); |
3933 | static_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 |
3939 | static constexpr size_t NEntries = SpanConstants::NEntries; |
3940 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: 1) == NEntries); |
3941 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 0) == NEntries); |
3942 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries / 2 + 1) == 2 * NEntries); |
3943 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 - 1) == 2 * NEntries); |
3944 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 0) == 4 * NEntries); |
3945 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 1 + 1) == 4 * NEntries); |
3946 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 - 1) == 4 * NEntries); |
3947 | static_assert(GrowthPolicy::bucketsForCapacity(requestedCapacity: NEntries * 2 + 0) == 8 * NEntries); |
3948 | static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1); |
3949 | static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX); |
3950 | static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX); |
3951 | } |
3952 | #endif |
3953 | |
3954 | QT_END_NAMESPACE |
3955 |
Definitions
- HashSeedStorage
- SeedCount
- HashSeedStorage
- State
- StateResult
- currentSeed
- resetSeed
- clearSeed
- initialize
- state
- qt_qhash_seed
- murmurhash
- ZeroExtension
- qHashBits_fallback
- qHashBits_fallback
- advance
- loadu128
- loadu128
- hash16bytes
- hash2x16bytes
- AESHashSeed
- state0_256
- AESHashSeed
- state1
- aeshash128_16to32
- maskarray
- shufflecontrol
- aeshash128_lt16
- aeshash128_ge32
- loadu256
- loadu256
- aeshash256_lt32_avx256
- aeshash256_ge32
- aeshash256
- aeshash256_avx256
- aeshash128
- aeshash
- qHashBits
- qHash
- qHash
- qHash
- qHash
- globalSeed
- setDeterministicGlobalSeed
- resetRandomGlobalSeed
- qGlobalQHashSeed
- qSetGlobalQHashSeed
- qt_hash
- qHash
- qHash
Start learning QML with our Intro Training
Find out more