diff options
Diffstat (limited to 'src/corelib/tools/qhash.cpp')
| -rw-r--r-- | src/corelib/tools/qhash.cpp | 1638 |
1 files changed, 1317 insertions, 321 deletions
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index ff2ae6813c..12e90daecf 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1,43 +1,7 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Copyright (C) 2016 Intel Corporation. -** Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtCore module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2020 The Qt Company Ltd. +// Copyright (C) 2021 Intel Corporation. +// Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only // for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h. // put it at the beginning so some indirect inclusion doesn't break it @@ -60,27 +24,161 @@ #include <qdatetime.h> #include <qbasicatomic.h> #include <qendian.h> +#include <private/qrandom_p.h> #include <private/qsimd_p.h> #ifndef QT_BOOTSTRAPPED #include <qcoreapplication.h> #include <qrandom.h> +#include <private/qlocale_tools_p.h> #endif // QT_BOOTSTRAPPED +#include <array> #include <limits.h> +#if defined(QT_NO_DEBUG) && !defined(NDEBUG) +# define NDEBUG +#endif +#include <assert.h> + +#ifdef Q_CC_GNU +# define Q_DECL_HOT_FUNCTION __attribute__((hot)) +#else +# define Q_DECL_HOT_FUNCTION +#endif + QT_BEGIN_NAMESPACE +void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept; // qstring.cpp + // We assume that pointers and size_t have the same size. If that assumption should fail // on a platform the code selecting the different methods below needs to be fixed. static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size."); +namespace { +struct HashSeedStorage +{ + static constexpr int SeedCount = 2; + QBasicAtomicInteger<quintptr> seeds[SeedCount] = { Q_BASIC_ATOMIC_INITIALIZER(0), Q_BASIC_ATOMIC_INITIALIZER(0) }; + +#if !QT_SUPPORTS_INIT_PRIORITY || defined(QT_BOOTSTRAPPED) + constexpr HashSeedStorage() = default; +#else + HashSeedStorage() { initialize(0); } +#endif + + enum State { + OverriddenByEnvironment = -1, + JustInitialized, + AlreadyInitialized + }; + struct StateResult { + quintptr requestedSeed; + State state; + }; + + StateResult state(int which = -1); + Q_DECL_HOT_FUNCTION QHashSeed currentSeed(int which) + { + return { state(which).requestedSeed }; + } + + void resetSeed() + { +#ifndef QT_BOOTSTRAPPED + if (state().state < AlreadyInitialized) + return; + + // update the public seed + QRandomGenerator *generator = QRandomGenerator::system(); + seeds[0].storeRelaxed(sizeof(size_t) > sizeof(quint32) + ? generator->generate64() : generator->generate()); +#endif + } + + void clearSeed() + { + state(); + seeds[0].storeRelaxed(0); // always write (smaller code) + } + +private: + Q_DECL_COLD_FUNCTION Q_NEVER_INLINE StateResult initialize(int which) noexcept; +}; + +[[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept +{ + StateResult result = { 0, OverriddenByEnvironment }; +#ifdef QT_BOOTSTRAPPED + Q_UNUSED(which); + Q_UNREACHABLE_RETURN(result); +#else + // can't use qEnvironmentVariableIntValue (reentrancy) + const char *seedstr = getenv("QT_HASH_SEED"); + if (seedstr) { + auto r = qstrntoll(seedstr, strlen(seedstr), 10); + if (r.used > 0 && size_t(r.used) == strlen(seedstr)) { + if (r.result) { + // can't use qWarning here (reentrancy) + fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0; ignored.\n"); + } + + // we don't have to store to the seed, since it's pre-initialized by + // the compiler to zero + return result; + } + } + + // update the full seed + auto x = qt_initial_random_value(); + for (int i = 0; i < SeedCount; ++i) { + seeds[i].storeRelaxed(x.data[i]); + if (which == i) + result.requestedSeed = x.data[i]; + } + result.state = JustInitialized; + return result; +#endif +} + +inline HashSeedStorage::StateResult HashSeedStorage::state(int which) +{ + constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555)); + StateResult result = { BadSeed, AlreadyInitialized }; + +#if defined(QT_BOOTSTRAPPED) + result = { 0, OverriddenByEnvironment }; +#elif !QT_SUPPORTS_INIT_PRIORITY + // dynamic initialization + static auto once = [&]() { + result = initialize(which); + return true; + }(); + Q_UNUSED(once); +#endif + + if (result.state == AlreadyInitialized && which >= 0) + return { seeds[which].loadRelaxed(), AlreadyInitialized }; + return result; +} +} // unnamed namespace + +/* + The QHash seed itself. +*/ +#ifdef Q_DECL_INIT_PRIORITY +Q_DECL_INIT_PRIORITY(05) +#else +Q_CONSTINIT +#endif +static HashSeedStorage qt_qhash_seed; + /* * Hashing for memory segments is based on the public domain MurmurHash2 by * Austin Appleby. See http://murmurhash.googlepages.com/ */ #if QT_POINTER_SIZE == 4 - +Q_NEVER_INLINE Q_DECL_HOT_FUNCTION static inline uint murmurhash(const void *key, uint len, uint seed) noexcept { // 'm' and 'r' are mixing constants generated offline. @@ -138,7 +236,7 @@ static inline uint murmurhash(const void *key, uint len, uint seed) noexcept } #else - +Q_NEVER_INLINE Q_DECL_HOT_FUNCTION static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept { const uint64_t m = 0xc6a4a7935bd1e995ULL; @@ -187,20 +285,11 @@ static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) #endif -#if QT_POINTER_SIZE == 8 +namespace { // This is an inlined version of the SipHash implementation that is // trying to avoid some memcpy's from uint64 to uint8[] and back. -// -// The original algorithm uses a 128bit seed. Our public API only allows -// for a 64bit seed, so we mix in the length of the string to get some more -// bits for the seed. -// -// Use SipHash-1-2, which has similar performance characteristics as -// stablehash() above, instead of the SipHash-2-4 default -#define cROUNDS 1 -#define dROUNDS 2 -#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) +#define ROTL(x, b) (((x) << (b)) | ((x) >> (sizeof(x) * 8 - (b)))) #define SIPROUND \ do { \ @@ -220,8 +309,7 @@ static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) v2 = ROTL(v2, 32); \ } while (0) - -static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) +template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash64 { /* "somepseudorandomlygeneratedbytes" */ uint64_t v0 = 0x736f6d6570736575ULL; @@ -229,17 +317,32 @@ static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) uint64_t v2 = 0x6c7967656e657261ULL; uint64_t v3 = 0x7465646279746573ULL; uint64_t b; - uint64_t k0 = seed; - uint64_t k1 = seed ^ inlen; - int i; - const uint8_t *end = in + (inlen & ~7ULL); - const int left = inlen & 7; + uint64_t k0; + uint64_t k1; + + inline SipHash64(uint64_t fulllen, uint64_t seed, uint64_t seed2); + inline void addBlock(const uint8_t *in, size_t inlen); + inline uint64_t finalize(const uint8_t *in, size_t left); +}; + +template <int cROUNDS, int dROUNDS> +SipHash64<cROUNDS, dROUNDS>::SipHash64(uint64_t inlen, uint64_t seed, uint64_t seed2) +{ b = inlen << 56; + k0 = seed; + k1 = seed2; v3 ^= k1; v2 ^= k0; v1 ^= k1; v0 ^= k0; +} +template <int cROUNDS, int dROUNDS> Q_DECL_HOT_FUNCTION void +SipHash64<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen) +{ + Q_ASSERT((inlen & 7ULL) == 0); + int i; + const uint8_t *end = in + inlen; for (; in != end; in += 8) { uint64_t m = qFromUnaligned<uint64_t>(in); v3 ^= m; @@ -249,24 +352,31 @@ static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) v0 ^= m; } +} - -#if defined(Q_CC_GNU) && Q_CC_GNU >= 700 - QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough") -#endif +template <int cROUNDS, int dROUNDS> Q_DECL_HOT_FUNCTION uint64_t +SipHash64<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left) +{ + int i; switch (left) { case 7: b |= ((uint64_t)in[6]) << 48; + Q_FALLTHROUGH(); case 6: b |= ((uint64_t)in[5]) << 40; + Q_FALLTHROUGH(); case 5: b |= ((uint64_t)in[4]) << 32; + Q_FALLTHROUGH(); case 4: b |= ((uint64_t)in[3]) << 24; + Q_FALLTHROUGH(); case 3: b |= ((uint64_t)in[2]) << 16; + Q_FALLTHROUGH(); case 2: b |= ((uint64_t)in[1]) << 8; + Q_FALLTHROUGH(); case 1: b |= ((uint64_t)in[0]); break; @@ -289,7 +399,8 @@ static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) b = v0 ^ v1 ^ v2 ^ v3; return b; } -#else +#undef SIPROUND + // This is a "SipHash" implementation adopted for 32bit platforms. It performs // basically the same operations as the 64bit version using 4 byte at a time // instead of 8. @@ -300,12 +411,6 @@ static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) // // For the v0-v4 constants, simply use the first four bytes of the 64 bit versions. // -// Use SipHash-1-2, which has similar performance characteristics as -// stablehash() above, instead of the SipHash-2-4 default -#define cROUNDS 1 -#define dROUNDS 2 - -#define ROTL(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b)))) #define SIPROUND \ do { \ @@ -325,8 +430,7 @@ static uint64_t siphash(const uint8_t *in, uint64_t inlen, const uint64_t seed) v2 = ROTL(v2, 16); \ } while (0) - -static uint siphash(const uint8_t *in, uint inlen, const uint seed) +template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash32 { /* "somepseudorandomlygeneratedbytes" */ uint v0 = 0x736f6d65U; @@ -334,17 +438,32 @@ static uint siphash(const uint8_t *in, uint inlen, const uint seed) uint v2 = 0x6c796765U; uint v3 = 0x74656462U; uint b; + uint k0; + uint k1; + + inline SipHash32(size_t fulllen, uint seed, uint seed2); + inline void addBlock(const uint8_t *in, size_t inlen); + inline uint finalize(const uint8_t *in, size_t left); +}; + +template <int cROUNDS, int dROUNDS> inline +SipHash32<cROUNDS, dROUNDS>::SipHash32(size_t inlen, uint seed, uint seed2) +{ uint k0 = seed; - uint k1 = seed ^ inlen; - int i; - const uint8_t *end = in + (inlen & ~3ULL); - const int left = inlen & 3; + uint k1 = seed2; b = inlen << 24; v3 ^= k1; v2 ^= k0; v1 ^= k1; v0 ^= k0; +} +template <int cROUNDS, int dROUNDS> inline Q_DECL_HOT_FUNCTION void +SipHash32<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen) +{ + Q_ASSERT((inlen & 3ULL) == 0); + int i; + const uint8_t *end = in + inlen; for (; in != end; in += 4) { uint m = qFromUnaligned<uint>(in); v3 ^= m; @@ -354,15 +473,19 @@ static uint siphash(const uint8_t *in, uint inlen, const uint seed) v0 ^= m; } +} -#if defined(Q_CC_GNU) && Q_CC_GNU >= 700 - QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough") -#endif +template <int cROUNDS, int dROUNDS> inline Q_DECL_HOT_FUNCTION uint +SipHash32<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left) +{ + int i; switch (left) { case 3: b |= ((uint)in[2]) << 16; + Q_FALLTHROUGH(); case 2: b |= ((uint)in[1]) << 8; + Q_FALLTHROUGH(); case 1: b |= ((uint)in[0]); break; @@ -385,22 +508,610 @@ static uint siphash(const uint8_t *in, uint inlen, const uint seed) b = v0 ^ v1 ^ v2 ^ v3; return b; } -#endif +#undef SIPROUND +#undef ROTL -size_t qHashBits(const void *p, size_t size, size_t seed) noexcept +// Use SipHash-1-2, which has similar performance characteristics as +// stablehash() above, instead of the SipHash-2-4 default +template <int cROUNDS = 1, int dROUNDS = 2> +using SipHash = std::conditional_t<sizeof(void *) == 8, + SipHash64<cROUNDS, dROUNDS>, SipHash32<cROUNDS, dROUNDS>>; +} // unnamed namespace + +Q_NEVER_INLINE Q_DECL_HOT_FUNCTION +static size_t siphash(const uint8_t *in, size_t inlen, size_t seed, size_t seed2) +{ + constexpr size_t TailSizeMask = sizeof(void *) - 1; + SipHash<> hasher(inlen, seed, seed2); + hasher.addBlock(in, inlen & ~TailSizeMask); + return hasher.finalize(in + (inlen & ~TailSizeMask), inlen & TailSizeMask); +} + +enum ZeroExtension { + None = 0, + ByteToWord = 1, +}; + +template <ZeroExtension = None> static size_t +qHashBits_fallback(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept; +template <> size_t qHashBits_fallback<None>(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept { if (size <= QT_POINTER_SIZE) return murmurhash(p, size, seed); - return siphash(reinterpret_cast<const uchar *>(p), size, seed); + return siphash(reinterpret_cast<const uchar *>(p), size, seed, seed2); } -size_t qHash(const QByteArray &key, size_t seed) noexcept +template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept { - return qHashBits(key.constData(), size_t(key.size()), seed); + auto quick_from_latin1 = [](char16_t *dest, const uchar *data, size_t size) { + // Quick, "inlined" version for very short blocks + std::copy_n(data, size, dest); + }; + if (size <= QT_POINTER_SIZE / 2) { + std::array<char16_t, QT_POINTER_SIZE / 2> buf; + quick_from_latin1(buf.data(), data, size); + return murmurhash(buf.data(), size * 2, seed); + } + + constexpr size_t TailSizeMask = sizeof(void *) / 2 - 1; + std::array<char16_t, 256> buf; + SipHash<> siphash(size * 2, seed, seed2); + ptrdiff_t offset = 0; + for ( ; offset + buf.size() < size; offset += buf.size()) { + qt_from_latin1(buf.data(), reinterpret_cast<const char *>(data) + offset, buf.size()); + siphash.addBlock(reinterpret_cast<uint8_t *>(buf.data()), sizeof(buf)); + } + if (size_t n = size - offset; n > TailSizeMask) { + n &= ~TailSizeMask; + qt_from_latin1(buf.data(), reinterpret_cast<const char *>(data) + offset, n); + siphash.addBlock(reinterpret_cast<uint8_t *>(buf.data()), n * 2); + offset += n; + } + + quick_from_latin1(buf.data(), data + offset, size - offset); + return siphash.finalize(reinterpret_cast<uint8_t *>(buf.data()), (size - offset) * 2); +} + +#if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__) // GCC +# define QHASH_AES_SANITIZER_BUILD +#elif __has_feature(address_sanitizer) || __has_feature(thread_sanitizer) // Clang +# define QHASH_AES_SANITIZER_BUILD +#endif + +// When built with a sanitizer, aeshash() is rightfully reported to have a +// heap-buffer-overflow issue. However, we consider it to be safe in this +// specific case and overcome the problem by correctly discarding the +// out-of-range bits. To allow building the code with sanitizer, +// QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage. +#if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \ + !defined(QHASH_AES_SANITIZER_BUILD) +# define AESHASH +# define QT_FUNCTION_TARGET_STRING_AES_AVX2 "avx2,aes" +# define QT_FUNCTION_TARGET_STRING_AES_AVX512 \ + QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \ + QT_FUNCTION_TARGET_STRING_AES +# define QT_FUNCTION_TARGET_STRING_VAES_AVX512 \ + QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 "," \ + QT_FUNCTION_TARGET_STRING_VAES +# undef QHASH_AES_SANITIZER_BUILD +# if QT_POINTER_SIZE == 8 +# define mm_set1_epz _mm_set1_epi64x +# define mm_cvtsz_si128 _mm_cvtsi64_si128 +# define mm_cvtsi128_sz _mm_cvtsi128_si64 +# define mm256_set1_epz _mm256_set1_epi64x +# else +# define mm_set1_epz _mm_set1_epi32 +# define mm_cvtsz_si128 _mm_cvtsi32_si128 +# define mm_cvtsi128_sz _mm_cvtsi128_si32 +# define mm256_set1_epz _mm256_set1_epi32 +# endif + +namespace { + // This is inspired by the algorithm in the Go language. See: + // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_amd64.s#L1105 + // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_386.s#L908 + // + // Even though we're using the AESENC instruction from the CPU, this code + // is not encryption and this routine makes no claim to be + // cryptographically secure. We're simply using the instruction that performs + // the scrambling round (step 3 in [1]) because it's just very good at + // spreading the bits around. + // + // Note on Latin-1 hashing (ZX == ByteToWord): for simplicity of the + // algorithm, we pass sizes equivalent to the UTF-16 content (ZX == None). + // That means we must multiply by 2 on entry, divide by 2 on pointer + // advancing, and load half as much data from memory (though we produce + // exactly as much data in registers). The compilers appear to optimize + // this out. + // + // [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm + + template <ZeroExtension ZX, typename T> static const T *advance(const T *ptr, ptrdiff_t n) + { + if constexpr (ZX == None) + return ptr + n; + + // see note above on ZX == ByteToWord hashing + auto p = reinterpret_cast<const uchar *>(ptr); + n *= sizeof(T); + return reinterpret_cast<const T *>(p + n/2); + } + + template <ZeroExtension> static __m128i loadu128(const void *ptr); + template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<None>(const void *ptr) + { + return _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr)); + } + template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<ByteToWord>(const void *ptr) + { + // use a MOVQ followed by PMOVZXBW + // the compiler usually combines them as a single, loading PMOVZXBW + __m128i data = _mm_loadl_epi64(static_cast<const __m128i *>(ptr)); + return _mm_cvtepu8_epi16(data); + } + + // hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1") + static void Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) QT_VECTORCALL + hash16bytes(__m128i &state0, __m128i data) + { + state0 = _mm_xor_si128(state0, data); + state0 = _mm_aesenc_si128(state0, state0); + state0 = _mm_aesenc_si128(state0, state0); + state0 = _mm_aesenc_si128(state0, state0); + } + + // hash twice 16 bytes, running 2 scramble rounds of AES on itself + template <ZeroExtension ZX> + static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL + hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1) + { + __m128i data0 = loadu128<ZX>(src0); + __m128i data1 = loadu128<ZX>(src1); + state0 = _mm_xor_si128(data0, state0); + state1 = _mm_xor_si128(data1, state1); + state0 = _mm_aesenc_si128(state0, state0); + state1 = _mm_aesenc_si128(state1, state1); + state0 = _mm_aesenc_si128(state0, state0); + state1 = _mm_aesenc_si128(state1, state1); + } + + struct AESHashSeed + { + __m128i state0; + __m128i mseed2; + AESHashSeed(size_t seed, size_t seed2) QT_FUNCTION_TARGET(AES); + __m128i state1() const QT_FUNCTION_TARGET(AES); + __m256i state0_256() const QT_FUNCTION_TARGET(AES_AVX2) + { return _mm256_set_m128i(state1(), state0); } + }; +} // unnamed namespace + +Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2) +{ + __m128i mseed = mm_cvtsz_si128(seed); + mseed2 = mm_set1_epz(seed2); + + // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, 0, 0, 0 ] + mseed = _mm_insert_epi16(mseed, short(seed), 4); + // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, len, len, len ] + mseed = _mm_shufflehi_epi16(mseed, 0); + + // merge with the process-global seed + __m128i key = _mm_xor_si128(mseed, mseed2); + + // scramble the key + __m128i state0 = _mm_aesenc_si128(key, key); + this->state0 = state0; } -size_t qHash(const QByteArrayView &key, size_t seed) noexcept +Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const +{ + { + // unlike the Go code, we don't have more per-process seed + __m128i state1 = _mm_aesenc_si128(state0, mseed2); + return state1; + } +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL +aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend) +{ + { + const __m128i *src2 = advance<ZX>(srcend, -1); + if (advance<ZX>(src, 1) < srcend) { + // epilogue: between 16 and 31 bytes + hash2x16bytes<ZX>(state0, state1, src, src2); + } else if (src != srcend) { + // epilogue: between 1 and 16 bytes, overlap with the end + __m128i data = loadu128<ZX>(src2); + hash16bytes(state0, data); + } + + // combine results: + state0 = _mm_xor_si128(state0, state1); + } + + return mm_cvtsi128_sz(state0); +} + +// load all 16 bytes and mask off the bytes past the end of the source +static const qint8 maskarray[] = { + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +}; + +// load 16 bytes ending at the data end, then shuffle them to the beginning +static const qint8 shufflecontrol[] = { + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 +}; + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL +aeshash128_lt16(__m128i state0, const __m128i *src, const __m128i *srcend, size_t len) +{ + if (len) { + // We're going to load 16 bytes and mask zero the part we don't care + // (the hash of a short string is different from the hash of a longer + // including NULLs at the end because the length is in the key) + // WARNING: this may produce valgrind warnings, but it's safe + + constexpr quintptr CachelineSize = 64; + __m128i data; + + if ((quintptr(src) & (CachelineSize / 2)) == 0) { + // lower half of the cacheline: + __m128i mask = _mm_loadu_si128(reinterpret_cast<const __m128i *>(maskarray + 15 - len)); + data = loadu128<ZX>(src); + data = _mm_and_si128(data, mask); + } else { + // upper half of the cacheline: + __m128i control = _mm_loadu_si128(reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len)); + data = loadu128<ZX>(advance<ZX>(srcend, -1)); + data = _mm_shuffle_epi8(data, control); + } + + hash16bytes(state0, data); + } + return mm_cvtsi128_sz(state0); +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL +aeshash128_ge32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend) +{ + // main loop: scramble two 16-byte blocks + for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2)) + hash2x16bytes<ZX>(state0, state1, src, advance<ZX>(src, 1)); + + return aeshash128_16to32<ZX>(state0, state1, src, srcend); +} + +# if QT_COMPILER_SUPPORTS_HERE(VAES) +template <ZeroExtension> static __m256i loadu256(const void *ptr); +template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<None>(const void *ptr) +{ + return _mm256_loadu_si256(reinterpret_cast<const __m256i *>(ptr)); +} +template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<ByteToWord>(const void *ptr) +{ + // VPMOVZXBW xmm, ymm + __m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr)); + return _mm256_cvtepu8_epi16(data); +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(VAES_AVX512) QT_VECTORCALL +aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len) +{ + __m128i state0_128 = _mm256_castsi256_si128(state0); + if (len) { + __m256i data; + if constexpr (ZX == None) { + __mmask32 mask = _bzhi_u32(-1, unsigned(len)); + data = _mm256_maskz_loadu_epi8(mask, p); + } else { + __mmask16 mask = _bzhi_u32(-1, unsigned(len) / 2); + __m128i data0 = _mm_maskz_loadu_epi8(mask, p); + data = _mm256_cvtepu8_epi16(data0); + } + __m128i data0 = _mm256_castsi256_si128(data); + if (len >= sizeof(__m128i)) { + state0 = _mm256_xor_si256(state0, data); + state0 = _mm256_aesenc_epi128(state0, state0); + state0 = _mm256_aesenc_epi128(state0, state0); + // we're XOR'ing the two halves so we skip the third AESENC + // state0 = _mm256_aesenc_epi128(state0, state0); + + // XOR the two halves and extract + __m128i low = _mm256_extracti128_si256(state0, 0); + __m128i high = _mm256_extracti128_si256(state0, 1); + state0_128 = _mm_xor_si128(low, high); + } else { + hash16bytes(state0_128, data0); + } + } + return mm_cvtsi128_sz(state0_128); +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL +aeshash256_ge32(__m256i state0, const __m128i *s, const __m128i *end, size_t len) +{ + static const auto hash32bytes = [](__m256i &state0, __m256i data) QT_FUNCTION_TARGET(VAES) { + state0 = _mm256_xor_si256(state0, data); + state0 = _mm256_aesenc_epi128(state0, state0); + state0 = _mm256_aesenc_epi128(state0, state0); + state0 = _mm256_aesenc_epi128(state0, state0); + }; + + // hash twice 32 bytes, running 2 scramble rounds of AES on itself + const auto hash2x32bytes = [](__m256i &state0, __m256i &state1, const void *src0, + const void *src1) QT_FUNCTION_TARGET(VAES) { + __m256i data0 = loadu256<ZX>(src0); + __m256i data1 = loadu256<ZX>(src1); + state0 = _mm256_xor_si256(data0, state0); + state1 = _mm256_xor_si256(data1, state1); + state0 = _mm256_aesenc_epi128(state0, state0); + state1 = _mm256_aesenc_epi128(state1, state1); + state0 = _mm256_aesenc_epi128(state0, state0); + state1 = _mm256_aesenc_epi128(state1, state1); + }; + + const __m256i *src = reinterpret_cast<const __m256i *>(s); + const __m256i *srcend = reinterpret_cast<const __m256i *>(end); + + __m256i state1 = _mm256_aesenc_epi128(state0, mm256_set1_epz(len)); + + // main loop: scramble two 32-byte blocks + for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2)) + hash2x32bytes(state0, state1, src, advance<ZX>(src, 1)); + + const __m256i *src2 = advance<ZX>(srcend, -1); + if (advance<ZX>(src, 1) < srcend) { + // epilogue: between 32 and 31 bytes + hash2x32bytes(state0, state1, src, src2); + } else if (src != srcend) { + // epilogue: between 1 and 32 bytes, overlap with the end + __m256i data = loadu256<ZX>(src2); + hash32bytes(state0, data); + } + + // combine results: + state0 = _mm256_xor_si256(state0, state1); + + // XOR the two halves and extract + __m128i low = _mm256_extracti128_si256(state0, 0); + __m128i high = _mm256_extracti128_si256(state0, 1); + return mm_cvtsi128_sz(_mm_xor_si128(low, high)); +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(VAES) +aeshash256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept +{ + AESHashSeed state(seed, seed2); + auto src = reinterpret_cast<const __m128i *>(p); + const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); + + if (len < sizeof(__m128i)) + return aeshash128_lt16<ZX>(state.state0, src, srcend, len); + + if (len <= sizeof(__m256i)) + return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend); + + return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len); +} + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(VAES_AVX512) +aeshash256_avx256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept +{ + AESHashSeed state(seed, seed2); + auto src = reinterpret_cast<const __m128i *>(p); + const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); + + if (len <= sizeof(__m256i)) + return aeshash256_lt32_avx256<ZX>(state.state0_256(), p, len); + + return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len); +} +# endif // VAES + +template <ZeroExtension ZX> +static size_t QT_FUNCTION_TARGET(AES) +aeshash128(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept +{ + AESHashSeed state(seed, seed2); + auto src = reinterpret_cast<const __m128i *>(p); + const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len)); + + if (len < sizeof(__m128i)) + return aeshash128_lt16<ZX>(state.state0, src, srcend, len); + + if (len <= sizeof(__m256i)) + return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend); + + return aeshash128_ge32<ZX>(state.state0, state.state1(), src, srcend); +} + +template <ZeroExtension ZX = None> +static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept +{ + if constexpr (ZX == ByteToWord) + len *= 2; // see note above on ZX == ByteToWord hashing + +# if QT_COMPILER_SUPPORTS_HERE(VAES) + if (qCpuHasFeature(VAES)) { + if (qCpuHasFeature(AVX512VL)) + return aeshash256_avx256<ZX>(p, len, seed, seed2); + return aeshash256<ZX>(p, len, seed, seed2); + } +# endif + return aeshash128<ZX>(p, len, seed, seed2); +} +#endif // x86 AESNI + +#if defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(AES) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED) +QT_FUNCTION_TARGET(AES) +static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept +{ + uint8x16_t key; +# if QT_POINTER_SIZE == 8 + uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2)); + key = vreinterpretq_u8_u64(vseed); +# else + + uint32x2_t vseed = vmov_n_u32(seed); + vseed = vset_lane_u32(seed2, vseed, 1); + key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed)); +# endif + + // Compared to x86 AES, ARM splits each round into two instructions + // and includes the pre-xor instead of the post-xor. + const auto hash16bytes = [](uint8x16_t &state0, uint8x16_t data) { + auto state1 = state0; + state0 = vaeseq_u8(state0, data); + state0 = vaesmcq_u8(state0); + auto state2 = state0; + state0 = vaeseq_u8(state0, state1); + state0 = vaesmcq_u8(state0); + auto state3 = state0; + state0 = vaeseq_u8(state0, state2); + state0 = vaesmcq_u8(state0); + state0 = veorq_u8(state0, state3); + }; + + uint8x16_t state0 = key; + + if (len < 8) + goto lt8; + if (len < 16) + goto lt16; + if (len < 32) + goto lt32; + + // rounds of 32 bytes + { + // Make state1 = ~state0: + uint8x16_t state1 = veorq_u8(state0, vdupq_n_u8(255)); + + // do simplified rounds of 32 bytes: unlike the Go code, we only + // scramble twice and we keep 256 bits of state + const auto *e = p + len - 31; + while (p < e) { + uint8x16_t data0 = vld1q_u8(p); + uint8x16_t data1 = vld1q_u8(p + 16); + auto oldstate0 = state0; + auto oldstate1 = state1; + state0 = vaeseq_u8(state0, data0); + state1 = vaeseq_u8(state1, data1); + state0 = vaesmcq_u8(state0); + state1 = vaesmcq_u8(state1); + auto laststate0 = state0; + auto laststate1 = state1; + state0 = vaeseq_u8(state0, oldstate0); + state1 = vaeseq_u8(state1, oldstate1); + state0 = vaesmcq_u8(state0); + state1 = vaesmcq_u8(state1); + state0 = veorq_u8(state0, laststate0); + state1 = veorq_u8(state1, laststate1); + p += 32; + } + state0 = veorq_u8(state0, state1); + } + len &= 0x1f; + + // do we still have 16 or more bytes? + if (len & 0x10) { +lt32: + uint8x16_t data = vld1q_u8(p); + hash16bytes(state0, data); + p += 16; + } + len &= 0xf; + + if (len & 0x08) { +lt16: + uint8x8_t data8 = vld1_u8(p); + uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0)); + hash16bytes(state0, data); + p += 8; + } + len &= 0x7; + +lt8: + if (len) { + // load the last chunk of data + // We're going to load 8 bytes and mask zero the part we don't care + // (the hash of a short string is different from the hash of a longer + // including NULLs at the end because the length is in the key) + // WARNING: this may produce valgrind warnings, but it's safe + + uint8x8_t data8; + + if (Q_LIKELY(quintptr(p + 8) & 0xff8)) { + // same page, we definitely can't fault: + // load all 8 bytes and mask off the bytes past the end of the source + static const qint8 maskarray[] = { + -1, -1, -1, -1, -1, -1, -1, + 0, 0, 0, 0, 0, 0, 0, + }; + uint8x8_t mask = vld1_u8(reinterpret_cast<const quint8 *>(maskarray) + 7 - len); + data8 = vld1_u8(p); + data8 = vand_u8(data8, mask); + } else { + // too close to the end of the page, it could fault: + // load 8 bytes ending at the data end, then shuffle them to the beginning + static const qint8 shufflecontrol[] = { + 1, 2, 3, 4, 5, 6, 7, + -1, -1, -1, -1, -1, -1, -1, + }; + uint8x8_t control = vld1_u8(reinterpret_cast<const quint8 *>(shufflecontrol) + 7 - len); + data8 = vld1_u8(p - 8 + len); + data8 = vtbl1_u8(data8, control); + } + uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0)); + hash16bytes(state0, data); + } + + // extract state0 +# if QT_POINTER_SIZE == 8 + return vgetq_lane_u64(vreinterpretq_u64_u8(state0), 0); +# else + return vgetq_lane_u32(vreinterpretq_u32_u8(state0), 0); +# endif +} +#endif + +size_t qHashBits(const void *p, size_t size, size_t seed) noexcept +{ +#ifdef QT_BOOTSTRAPPED + // the seed is always 0 in bootstrapped mode (no seed generation code), + // so help the compiler do dead code elimination + seed = 0; +#endif + // mix in the length as a secondary seed. For seed == 0, seed2 must be + // size, to match what we used to do prior to Qt 6.2. + size_t seed2 = size; + if (seed) + seed2 = qt_qhash_seed.currentSeed(1); + + auto data = reinterpret_cast<const uchar *>(p); +#ifdef AESHASH + if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2)) + return aeshash(data, size, seed, seed2); +#elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(AES) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED) + if (seed && qCpuHasFeature(AES)) + return aeshash(data, size, seed, seed2); +#endif + + return qHashBits_fallback<>(data, size, seed, seed2); +} + +size_t qHash(QByteArrayView key, size_t seed) noexcept { return qHashBits(key.constData(), size_t(key.size()), seed); } @@ -410,92 +1121,157 @@ size_t qHash(QStringView key, size_t seed) noexcept return qHashBits(key.data(), key.size()*sizeof(QChar), seed); } +#ifndef QT_BOOTSTRAPPED size_t qHash(const QBitArray &bitArray, size_t seed) noexcept { - int m = bitArray.d.size() - 1; + qsizetype m = bitArray.d.size() - 1; size_t result = qHashBits(reinterpret_cast<const uchar *>(bitArray.d.constData()), size_t(qMax(0, m)), seed); // deal with the last 0 to 7 bits manually, because we can't trust that // the padding is initialized to 0 in bitArray.d - int n = bitArray.size(); + qsizetype n = bitArray.size(); if (n & 0x7) result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1); return result; } +#endif -size_t qHash(QLatin1String key, size_t seed) noexcept +size_t qHash(QLatin1StringView key, size_t seed) noexcept { - return qHashBits(reinterpret_cast<const uchar *>(key.data()), size_t(key.size()), seed); +#ifdef QT_BOOTSTRAPPED + // the seed is always 0 in bootstrapped mode (no seed generation code), + // so help the compiler do dead code elimination + seed = 0; +#endif + + auto data = reinterpret_cast<const uchar *>(key.data()); + size_t size = key.size(); + + // Mix in the length as a secondary seed. + // Multiplied by 2 to match the byte size of the equiavlent UTF-16 string. + size_t seed2 = size * 2; + if (seed) + seed2 = qt_qhash_seed.currentSeed(1); + +#if defined(AESHASH) + if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2)) + return aeshash<ByteToWord>(data, size, seed, seed2); +#endif + return qHashBits_fallback<ByteToWord>(data, size, seed, seed2); } /*! - \internal + \class QHashSeed + \inmodule QtCore + \since 6.2 + + The QHashSeed class is used to convey the QHash seed. This is used + internally by QHash and provides three static member functions to allow + users to obtain the hash and to reset it. + + QHash and the qHash() functions implement what is called as "salted hash". + The intent is that different applications and different instances of the + same application will produce different hashing values for the same input, + thus causing the ordering of elements in QHash to be unpredictable by + external observers. This improves the applications' resilience against + attacks that attempt to force hashing tables into degenerate mode. + + Most applications will not need to deal directly with the hash seed, as + QHash will do so when needed. However, applications may wish to use this + for their own purposes in the same way as QHash does: as an + application-global random value (but see \l QRandomGenerator too). Note + that the global hash seed may change during the application's lifetime, if + the resetRandomGlobalSeed() function is called. Users of the global hash + need to store the value they are using and not rely on getting it again. + + This class also implements functionality to set the hash seed to a + deterministic value, which the qHash() functions will take to mean that + they should use a fixed hashing function on their data too. This + functionality is only meant to be used in debugging applications. This + behavior can also be controlled by setting the \c QT_HASH_SEED environment + variable to the value zero (any other value is ignored). + + \sa QHash, QRandomGenerator */ -static uint qt_create_qhash_seed() -{ - uint seed = 0; -#ifndef QT_BOOTSTRAPPED - QByteArray envSeed = qgetenv("QT_HASH_SEED"); - if (!envSeed.isNull()) { - uint seed = envSeed.toUInt(); - if (seed) { - // can't use qWarning here (reentrancy) - fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0, cannot guarantee that the " - "hashing functions will produce a stable value."); - } - return seed; - } +/*! + \fn QHashSeed::QHashSeed(size_t data) - seed = QRandomGenerator::system()->generate(); -#endif // QT_BOOTSTRAPPED + Constructs a new QHashSeed object using \a data as the seed. + */ + +/*! + \fn QHashSeed::operator size_t() const - return seed; + Converts the returned hash seed into a \c size_t. + */ + +/*! + \threadsafe + + Returns the current global QHash seed. The value returned by this function + will be zero if setDeterministicGlobalSeed() has been called or if the + \c{QT_HASH_SEED} environment variable is set to zero. + */ +QHashSeed QHashSeed::globalSeed() noexcept +{ + return qt_qhash_seed.currentSeed(0); } -/* - The QHash seed itself. -*/ -static QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1); +/*! + \threadsafe + + Forces the Qt hash seed to a deterministic value (zero) and asks the + qHash() functions to use a pre-determined hashing function. This mode is + only useful for debugging and should not be used in production code. + + Regular operation can be restored by calling resetRandomGlobalSeed(). + */ +void QHashSeed::setDeterministicGlobalSeed() +{ + qt_qhash_seed.clearSeed(); +} /*! - \internal + \threadsafe - Seed == -1 means it that it was not initialized yet. + Reseeds the Qt hashing seed to a new, random value. Calling this function + is not necessary, but long-running applications may want to do so after a + long period of time in which information about its hash may have been + exposed to potential attackers. - We let qt_create_qhash_seed return any unsigned integer, - but convert it to signed in order to initialize the seed. + If the environment variable \c QT_HASH_SEED is set to zero, calling this + function will result in a no-op. - We don't actually care about the fact that different calls to - qt_create_qhash_seed() might return different values, - as long as in the end everyone uses the very same value. -*/ -static void qt_initialize_qhash_seed() + Qt never calls this function during the execution of the application, but + unless the \c QT_HASH_SEED variable is set to 0, the hash seed returned by + globalSeed() will be a random value as if this function had been called. + */ +void QHashSeed::resetRandomGlobalSeed() { - if (qt_qhash_seed.loadRelaxed() == -1) { - int x(qt_create_qhash_seed() & INT_MAX); - qt_qhash_seed.testAndSetRelaxed(-1, x); - } + qt_qhash_seed.resetSeed(); } +#if QT_DEPRECATED_SINCE(6,6) /*! \relates QHash \since 5.6 + \deprecated [6.6] Use QHashSeed::globalSeed() instead. Returns the current global QHash seed. The seed is set in any newly created QHash. See \l{qHash} about how this seed is being used by QHash. - \sa qSetGlobalQHashSeed + \sa QHashSeed, QHashSeed::globalSeed() */ int qGlobalQHashSeed() { - qt_initialize_qhash_seed(); - return qt_qhash_seed.loadRelaxed(); + return int(QHashSeed::globalSeed() & INT_MAX); } /*! \relates QHash \since 5.6 + \deprecated [6.6] Use QHashSeed instead. Sets the global QHash seed to \a newSeed. @@ -515,24 +1291,21 @@ int qGlobalQHashSeed() If the environment variable \c QT_HASH_SEED is set, calling this function will result in a no-op. - \sa qGlobalQHashSeed + \sa QHashSeed::globalSeed(), QHashSeed */ void qSetGlobalQHashSeed(int newSeed) { - if (qEnvironmentVariableIsSet("QT_HASH_SEED")) - return; - if (newSeed == -1) { - int x(qt_create_qhash_seed() & INT_MAX); - qt_qhash_seed.storeRelaxed(x); + if (Q_LIKELY(newSeed == 0 || newSeed == -1)) { + if (newSeed == 0) + QHashSeed::setDeterministicGlobalSeed(); + else + QHashSeed::resetRandomGlobalSeed(); } else { - if (newSeed) { - // can't use qWarning here (reentrancy) - fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0, cannot guarantee that the " - "hashing functions will produce a stable value."); - } - qt_qhash_seed.storeRelaxed(newSeed & INT_MAX); + // can't use qWarning here (reentrancy) + fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n"); } } +#endif // QT_DEPRECATED_SINCE(6,6) /*! \internal @@ -565,16 +1338,6 @@ uint qt_hash(QStringView key, uint chained) noexcept } /*! - \fn template <typename T1, typename T2> size_t qHash(const QPair<T1, T2> &key, size_t seed = 0) - \since 5.0 - \relates QHash - - Returns the hash value for the \a key, using \a seed to seed the calculation. - - Types \c T1 and \c T2 must be supported by qHash(). -*/ - -/*! \fn template <typename T1, typename T2> size_t qHash(const std::pair<T1, T2> &key, size_t seed = 0) \since 5.7 \relates QHash @@ -582,11 +1345,6 @@ uint qt_hash(QStringView key, uint chained) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. Types \c T1 and \c T2 must be supported by qHash(). - - \note The return type of this function is \e{not} the same as that of - \snippet code/src_corelib_tools_qhash.cpp 29 - The two functions use different hashing algorithms; due to binary compatibility - constraints, we cannot change the QPair algorithm to match the std::pair one before Qt 6. */ /*! @@ -804,6 +1562,26 @@ uint qt_hash(QStringView key, uint chained) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. */ +/*! \fn size_t qHash(quint128 key, size_t seed = 0) + \relates QHash + \since 6.8 + + Returns the hash value for the \a key, using \a seed to seed the calculation. + + \note This function is only available on platforms that support a native + 128-bit integer type. +*/ + +/*! \fn size_t qHash(qint128 key, size_t seed = 0) + \relates QHash + \since 6.8 + + Returns the hash value for the \a key, using \a seed to seed the calculation. + + \note This function is only available on platforms that support a native + 128-bit integer type. + */ + /*! \fn size_t qHash(char8_t key, size_t seed = 0) \relates QHash \since 6.0 @@ -832,7 +1610,7 @@ uint qt_hash(QStringView key, uint chained) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. */ -/*! \fn size_t qHash(float key, size_t seed) noexcept +/*! \fn size_t qHash(float key, size_t seed = 0) noexcept \relates QHash \since 5.3 @@ -857,7 +1635,6 @@ size_t qHash(double key, size_t seed) noexcept } } -#if !defined(Q_OS_DARWIN) || defined(Q_CLANG_QDOC) /*! \relates QHash \since 5.3 @@ -875,7 +1652,6 @@ size_t qHash(long double key, size_t seed) noexcept return murmurhash(&key, sizeof(key), seed); } } -#endif /*! \fn size_t qHash(const QChar key, size_t seed = 0) \relates QHash @@ -912,13 +1688,6 @@ size_t qHash(long double key, size_t seed) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. */ -/*! \fn size_t qHash(const QStringRef &key, size_t seed = 0) - \relates QHash - \since 5.0 - - Returns the hash value for the \a key, using \a seed to seed the calculation. -*/ - /*! \fn size_t qHash(QStringView key, size_t seed = 0) \relates QStringView \since 5.10 @@ -926,7 +1695,7 @@ size_t qHash(long double key, size_t seed) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. */ -/*! \fn size_t qHash(QLatin1String key, size_t seed = 0) +/*! \fn size_t qHash(QLatin1StringView key, size_t seed = 0) \relates QHash \since 5.0 @@ -940,13 +1709,28 @@ size_t qHash(long double key, size_t seed) noexcept Returns the hash value for the \a key, using \a seed to seed the calculation. */ -/*! \fn template <class T> size_t qHash(std::nullptr_t key, size_t seed = 0) +/*! \fn size_t qHash(std::nullptr_t key, size_t seed = 0) \relates QHash \since 6.0 Returns the hash value for the \a key, using \a seed to seed the calculation. */ +/*! \fn template<typename T> bool qHashEquals(const T &a, const T &b) + \relates QHash + \since 6.0 + \internal + + This method is being used by QHash to compare two keys. Returns true if the + keys \a a and \a b are considered equal for hashing purposes. + + The default implementation returns the result of (a == b). It can be reimplemented + for a certain type if the equality operator is not suitable for hashing purposes. + This is for example the case if the equality operator uses qFuzzyCompare to compare + floating point values. +*/ + + /*! \class QHash \inmodule QtCore @@ -1053,7 +1837,7 @@ size_t qHash(long double key, size_t seed) noexcept hash table, use \l{QMultiHash}. If you only need to extract the values from a hash (not the keys), - you can also use \l{foreach}: + you can also use range-based for: \snippet code/src_corelib_tools_qhash.cpp 12 @@ -1067,31 +1851,54 @@ size_t qHash(long double key, size_t seed) noexcept instead, store a QWidget *. \target qHash - \section2 The qHash() hashing function + \section2 The hashing function A QHash's key type has additional requirements other than being an assignable data type: it must provide operator==(), and there must also be - a qHash() function in the type's namespace that returns a hash value for an - argument of the key's type. + a hashing function that returns a hash value for an argument of the + key's type. - The qHash() function computes a numeric value based on a key. It + The hashing function computes a numeric value based on a key. It can use any algorithm imaginable, as long as it always returns the same value if given the same argument. In other words, if - \c{e1 == e2}, then \c{qHash(e1) == qHash(e2)} must hold as well. - However, to obtain good performance, the qHash() function should + \c{e1 == e2}, then \c{hash(e1) == hash(e2)} must hold as well. + However, to obtain good performance, the hashing function should attempt to return different hash values for different keys to the largest extent possible. - For a key type \c{K}, the qHash function must have one of these signatures: + A hashing function for a key type \c{K} may be provided in two + different ways. + + The first way is by having an overload of \c{qHash()} in \c{K}'s + namespace. The \c{qHash()} function must have one of these signatures: \snippet code/src_corelib_tools_qhash.cpp 32 The two-arguments overloads take an unsigned integer that should be used to seed the calculation of the hash function. This seed is provided by QHash - in order to prevent a family of \l{algorithmic complexity attacks}. If both - a one-argument and a two-arguments overload are defined for a key type, - the latter is used by QHash (note that you can simply define a - two-arguments version, and use a default value for the seed parameter). + in order to prevent a family of \l{algorithmic complexity attacks}. + + \note In Qt 6 it is possible to define a \c{qHash()} overload + taking only one argument; support for this is deprecated. Starting + with Qt 7, it will be mandatory to use a two-arguments overload. If + both a one-argument and a two-arguments overload are defined for a + key type, the latter is used by QHash (note that you can simply + define a two-arguments version, and use a default value for the + seed parameter). + + The second way to provide a hashing function is by specializing + the \c{std::hash} class for the key type \c{K}, and providing a + suitable function call operator for it: + + \snippet code/src_corelib_tools_qhash.cpp 33 + + The seed argument has the same meaning as for \c{qHash()}, + and may be left out. + + This second way allows to reuse the same hash function between + QHash and the C++ Standard Library unordered associative containers. + If both a \c{qHash()} overload and a \c{std::hash} specializations + are provided for a type, then the \c{qHash()} overload is preferred. Here's a partial list of the C++ and Qt types that can serve as keys in a QHash: any integer type (char, unsigned long, etc.), any pointer type, @@ -1101,9 +1908,11 @@ size_t qHash(long double key, size_t seed) noexcept the documentation of each class. If you want to use other types as the key, make sure that you provide - operator==() and a qHash() implementation. The convenience qHashMulti() - function can be used to implement qHash() for a custom type, where - one usually wants to produce a hash value from multiple fields: + operator==() and a hash implementation. + + The convenience qHashMulti() function can be used to implement + qHash() for a custom type, where one usually wants to produce a + hash value from multiple fields: Example: \snippet code/src_corelib_tools_qhash.cpp 13 @@ -1138,7 +1947,7 @@ size_t qHash(long double key, size_t seed) noexcept where you temporarily need deterministic behavior, for example for debugging or regression testing. To disable the randomization, define the environment variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call - the qSetGlobalQHashSeed() function with the value 0. + the QHashSeed::setDeterministicGlobalSeed() function. \sa QHashIterator, QMutableHashIterator, QMap, QSet */ @@ -1171,8 +1980,8 @@ size_t qHash(long double key, size_t seed) noexcept Constructs a hash with a copy of each of the elements in the iterator range [\a begin, \a end). Either the elements iterated by the range must be - objects with \c{first} and \c{second} data members (like \c{QPair}, - \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the + objects with \c{first} and \c{second} data members (like \c{std::pair}), + convertible to \c Key and to \c T respectively; or the iterators must have \c{key()} and \c{value()} member functions, returning a key convertible to \c Key and a value convertible to \c T respectively. */ @@ -1248,7 +2057,7 @@ size_t qHash(long double key, size_t seed) noexcept \sa operator==() */ -/*! \fn template <class Key, class T> int QHash<Key, T>::size() const +/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::size() const Returns the number of items in the hash. @@ -1263,7 +2072,7 @@ size_t qHash(long double key, size_t seed) noexcept \sa size() */ -/*! \fn template <class Key, class T> int QHash<Key, T>::capacity() const +/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::capacity() const Returns the number of buckets in the QHash's internal hash table. @@ -1292,7 +2101,7 @@ size_t qHash(long double key, size_t seed) noexcept */ -/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(int size) +/*! \fn template <class Key, class T> void QHash<Key, T>::reserve(qsizetype size) Ensures that the QHash's internal hash table has space to store at least \a size items without having to grow the hash table. @@ -1374,6 +2183,21 @@ size_t qHash(long double key, size_t seed) noexcept \sa clear(), take() */ +/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QHash<Key, T>::removeIf(Predicate pred) + \since 6.1 + + Removes all elements for which the predicate \a pred returns true + from the hash. + + The function supports predicates which take either an argument of + type \c{QHash<Key, T>::iterator}, or an argument of type + \c{std::pair<const Key &, T &>}. + + Returns the number of elements removed, if any. + + \sa clear(), take() +*/ + /*! \fn template <class Key, class T> T QHash<Key, T>::take(const Key &key) Removes the item with the \a key from the hash and returns @@ -1392,17 +2216,18 @@ size_t qHash(long double key, size_t seed) noexcept Returns \c true if the hash contains an item with the \a key; otherwise returns \c false. - \sa count(), QMultiHash::contains() + \sa count() */ -/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const +/*! \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key) const + \fn template <class Key, class T> T QHash<Key, T>::value(const Key &key, const T &defaultValue) const \overload Returns the value associated with the \a key. If the hash contains no item with the \a key, the function - returns \a defaultValue, which is a \l{default-constructed value} if the - parameter has not been specified. + returns \a defaultValue, or a \l{default-constructed value} if this + parameter has not been supplied. */ /*! \fn template <class Key, class T> T &QHash<Key, T>::operator[](const Key &key) @@ -1414,6 +2239,12 @@ size_t qHash(long double key, size_t seed) noexcept a \l{default-constructed value} into the hash with the \a key, and returns a reference to it. +//! [qhash-iterator-invalidation-func-desc] + \warning Returned iterators/references should be considered invalidated + the next time you call a non-const function on the hash, or when the + hash is destroyed. +//! [qhash-iterator-invalidation-func-desc] + \sa insert(), value() */ @@ -1465,25 +2296,27 @@ size_t qHash(long double key, size_t seed) noexcept */ /*! - \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const + \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value) const + \fn template <class Key, class T> Key QHash<Key, T>::key(const T &value, const Key &defaultKey) const \since 4.3 - Returns the first key mapped to \a value, or \a defaultKey if the - hash contains no item mapped to \a value. + Returns the first key mapped to \a value. If the hash contains no item + mapped to \a value, returns \a defaultKey, or a \l{default-constructed + value}{default-constructed key} if this parameter has not been supplied. This function can be slow (\l{linear time}), because QHash's internal data structure is optimized for fast lookup by key, not by value. */ -/*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const +/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count(const Key &key) const Returns the number of items associated with the \a key. \sa contains() */ -/*! \fn template <class Key, class T> int QHash<Key, T>::count() const +/*! \fn template <class Key, class T> qsizetype QHash<Key, T>::count() const \overload @@ -1495,12 +2328,16 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constBegin(), end() */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::begin() const \overload + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::cbegin() const @@ -1509,6 +2346,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), cend() */ @@ -1517,6 +2356,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), constEnd() */ @@ -1526,6 +2367,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyEnd() */ @@ -1534,12 +2377,16 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), constEnd() */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::end() const \overload + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constEnd() const @@ -1547,6 +2394,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constBegin(), end() */ @@ -1556,6 +2405,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa cbegin(), end() */ @@ -1565,6 +2416,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last key in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyBegin() */ @@ -1574,6 +2427,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueEnd() */ @@ -1583,6 +2438,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -1592,6 +2449,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueEnd() */ @@ -1601,6 +2460,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -1610,6 +2471,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -1619,9 +2482,32 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constKeyValueBegin() */ +/*! \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() & + \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const & + \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() && + \fn template <class Key, class T> auto QHash<Key, T>::asKeyValueRange() const && + \since 6.4 + + Returns a range object that allows iteration over this hash as + key/value pairs. For instance, this range object can be used in a + range-based for loop, in combination with a structured binding declaration: + + \snippet code/src_corelib_tools_qhash.cpp 34 + + Note that both the key and the value obtained this way are + references to the ones in the hash. Specifically, mutating the value + will modify the hash itself. + + \include qhash.cpp qhash-iterator-invalidation-func-desc + + \sa QKeyValueIterator +*/ + /*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator pos) \since 5.7 @@ -1636,11 +2522,9 @@ size_t qHash(long double key, size_t seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 15 - \sa remove(), take(), find() -*/ + \include qhash.cpp qhash-iterator-invalidation-func-desc -/*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::erase(iterator pos) - \overload + \sa remove(), take(), find() */ /*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::find(const Key &key) @@ -1659,12 +2543,16 @@ size_t qHash(long double key, size_t seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 16 + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa value(), values() */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &key) const \overload + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &key) const @@ -1676,6 +2564,8 @@ size_t qHash(long double key, size_t seed) noexcept If the hash contains no item with the \a key, the function returns constEnd(). + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa find() */ @@ -1685,17 +2575,23 @@ size_t qHash(long double key, size_t seed) noexcept If there is already an item with the \a key, that item's value is replaced with \a value. + + Returns an iterator pointing to the new/updated element. + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! - \fn template <typename T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args) - \fn template <typename T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args) Inserts a new element into the container. This new element is constructed in-place using \a args as the arguments for its construction. Returns an iterator pointing to the new element. + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ @@ -1706,9 +2602,6 @@ size_t qHash(long double key, size_t seed) noexcept If a key is common to both hashes, its value will be replaced with the value stored in \a other. - - \note If \a other contains multiple entries with the same key then the - final value of the key is undefined. */ /*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const @@ -1718,17 +2611,21 @@ size_t qHash(long double key, size_t seed) noexcept returns \c false. */ -/*! \fn template <class Key, class T> QPair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key) +/*! \fn template <class Key, class T> std::pair<iterator, iterator> QMultiHash<Key, T>::equal_range(const Key &key) \since 5.7 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that are stored under \a key. If the range is empty then both iterators will be equal to end(). + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! - \fn template <class Key, class T> QPair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const + \fn template <class Key, class T> std::pair<const_iterator, const_iterator> QMultiHash<Key, T>::equal_range(const Key &key) const \overload \since 5.7 + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \typedef QHash::ConstIterator @@ -1825,12 +2722,6 @@ size_t qHash(long double key, size_t seed) noexcept \inmodule QtCore \brief The QHash::iterator class provides an STL-style non-const iterator for QHash. - QHash features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - QHash\<Key, T\>::iterator allows you to iterate over a QHash and to modify the value (but not the key) associated with a particular key. If you want to iterate over a const QHash, @@ -1851,31 +2742,15 @@ size_t qHash(long double key, size_t seed) noexcept Unlike QMap, which orders its items by key, QHash stores its items in an arbitrary order. - Let's see a few examples of things we can do with a - QHash::iterator that we cannot do with a QHash::const_iterator. Here's an example that increments every value stored in the QHash by 2: \snippet code/src_corelib_tools_qhash.cpp 18 - Here's an example that removes all the items whose key is a - string that starts with an underscore character: - - \snippet code/src_corelib_tools_qhash.cpp 19 - - The call to QHash::erase() removes the item pointed to by the - iterator from the hash, and returns an iterator to the next item. - Here's another way of removing an item while iterating: - - \snippet code/src_corelib_tools_qhash.cpp 20 - - It might be tempting to write code like this: + To remove elements from a QHash you can use erase_if(QHash\<Key, T\> &map, Predicate pred): \snippet code/src_corelib_tools_qhash.cpp 21 - However, this will potentially crash in \c{++i}, because \c i is - a dangling iterator after the call to erase(). - Multiple iterators can be used on the same hash. However, be aware that any modification performed directly on the QHash (inserting and removing items) can cause the iterators to become invalid. @@ -1886,10 +2761,6 @@ size_t qHash(long double key, size_t seed) noexcept to grow/shrink its internal hash table. Using any iterator after a rehashing operation has occurred will lead to undefined behavior. - You can however safely use iterators to remove entries from the hash - using the QHash::erase() method. This function can safely be called while - iterating, and won't affect the order of items in the hash. - If you need to keep iterators over a long period of time, we recommend that you use QMap rather than QHash. @@ -1898,7 +2769,7 @@ size_t qHash(long double key, size_t seed) noexcept while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. - \sa QHash::const_iterator, QHash::key_iterator, QMutableHashIterator + \sa QHash::const_iterator, QHash::key_iterator, QHash::key_value_iterator */ /*! \fn template <class Key, class T> QHash<Key, T>::iterator::iterator() @@ -1994,12 +2865,6 @@ size_t qHash(long double key, size_t seed) noexcept \inmodule QtCore \brief The QHash::const_iterator class provides an STL-style const iterator for QHash. - QHash features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - QHash\<Key, T\>::const_iterator allows you to iterate over a QHash. If you want to modify the QHash as you iterate over it, you must use QHash::iterator instead. It is @@ -2010,8 +2875,8 @@ size_t qHash(long double key, size_t seed) noexcept The default QHash::const_iterator constructor creates an uninitialized iterator. You must initialize it using a QHash - function like QHash::constBegin(), QHash::constEnd(), or - QHash::find() before you can start iterating. Here's a typical + function like QHash::cbegin(), QHash::cend(), or + QHash::constFind() before you can start iterating. Here's a typical loop that prints all the (key, value) pairs stored in a hash: \snippet code/src_corelib_tools_qhash.cpp 23 @@ -2032,12 +2897,16 @@ size_t qHash(long double key, size_t seed) noexcept to grow/shrink its internal hash table. Using any iterator after a rehashing operation has occurred will lead to undefined behavior. + You can however safely use iterators to remove entries from the hash + using the QHash::erase() method. This function can safely be called while + iterating, and won't affect the order of items in the hash. + \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. - \sa QHash::iterator, QHashIterator + \sa QHash::iterator, QHash::key_iterator, QHash::const_key_value_iterator */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator::const_iterator() @@ -2110,8 +2979,6 @@ size_t qHash(long double key, size_t seed) noexcept item. Calling this function on QHash::end() leads to undefined results. - - \sa operator--() */ /*! \fn template <class Key, class T> QHash<Key, T>::const_iterator QHash<Key, T>::const_iterator::operator++(int) @@ -2195,7 +3062,6 @@ size_t qHash(long double key, size_t seed) noexcept Calling this function on QHash::keyEnd() leads to undefined results. - \sa operator--() */ /*! \fn template <class Key, class T> QHash<Key, T>::key_iterator QHash<Key, T>::key_iterator::operator++(int) @@ -2272,11 +3138,10 @@ size_t qHash(long double key, size_t seed) noexcept hashes. A multi-valued hash is a hash that allows multiple values with the same key. - Because QMultiHash inherits QHash, all of QHash's functionality also - applies to QMultiHash. For example, you can use isEmpty() to test + QMultiHash mostly mirrors QHash's API. For example, you can use isEmpty() to test whether the hash is empty, and you can traverse a QMultiHash using QHash's iterator classes (for example, QHashIterator). But opposed to - QHash, it provides an insert() function will allow the insertion of + QHash, it provides an insert() function that allows the insertion of multiple items with the same key. The replace() function corresponds to QHash::insert(). It also provides convenient operator+() and operator+=(). @@ -2327,17 +3192,12 @@ size_t qHash(long double key, size_t seed) noexcept Constructs a multi-hash with a copy of each of the elements in the initializer list \a list. - - This function is only available if the program is being - compiled in C++11 mode. */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::QMultiHash(const QHash<Key, T> &other) Constructs a copy of \a other (which can be a QHash or a QMultiHash). - - \sa operator=() */ /*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end) @@ -2345,8 +3205,8 @@ size_t qHash(long double key, size_t seed) noexcept Constructs a multi-hash with a copy of each of the elements in the iterator range [\a begin, \a end). Either the elements iterated by the range must be - objects with \c{first} and \c{second} data members (like \c{QPair}, - \c{std::pair}, etc.) convertible to \c Key and to \c T respectively; or the + objects with \c{first} and \c{second} data members (like \c{std::pair}), + convertible to \c Key and to \c T respectively; or the iterators must have \c{key()} and \c{value()} member functions, returning a key convertible to \c Key and a value convertible to \c T respectively. */ @@ -2361,6 +3221,10 @@ size_t qHash(long double key, size_t seed) noexcept If there are multiple items with the \a key, the most recently inserted item's value is replaced with \a value. + Returns an iterator pointing to the new/updated element. + + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa insert() */ @@ -2373,12 +3237,16 @@ size_t qHash(long double key, size_t seed) noexcept different from replace(), which overwrites the value of an existing item.) + Returns an iterator pointing to the new element. + + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa replace() */ /*! - \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args) - \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args) Inserts a new element into the container. This new element is constructed in-place using \a args as the arguments for its @@ -2391,12 +3259,14 @@ size_t qHash(long double key, size_t seed) noexcept Returns an iterator pointing to the new element. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa insert */ /*! - \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args) - \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args) + \fn template <class Key, class T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args) Inserts a new element into the container. This new element is constructed in-place using \a args as the arguments for its @@ -2407,6 +3277,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an iterator pointing to the new element. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa replace, emplace */ @@ -2420,6 +3292,16 @@ size_t qHash(long double key, size_t seed) noexcept \sa insert() */ + +/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QHash<Key, T> &other) + \since 6.0 + + Inserts all the items in the \a other hash into this hash + and returns a reference to this hash. + + \sa insert() +*/ + /*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const \since 5.13 @@ -2429,14 +3311,14 @@ size_t qHash(long double key, size_t seed) noexcept \sa keys(), values() */ -/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue = T()) const - \overload +/*! \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key) const + \fn template <class Key, class T> T QMultiHash<Key, T>::value(const Key &key, const T &defaultValue) const Returns the value associated with the \a key. If the hash contains no item with the \a key, the function - returns \a defaultValue, which is a \l{default-constructed value} if the - parameter has not been specified. + returns \a defaultValue, or a \l{default-constructed value} if this + parameter has not been supplied. If there are multiple items for the \a key in the hash, the value of the most recently @@ -2463,6 +3345,8 @@ size_t qHash(long double key, size_t seed) noexcept If the hash contains multiple items with the \a key, this function returns a reference to the most recently inserted value. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa insert(), value() */ @@ -2494,7 +3378,17 @@ size_t qHash(long double key, size_t seed) noexcept */ /*! - \fn template <class Key, class T> int QMultiHash<Key, T>::remove(const Key &key, const T &value) + \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key) + \since 4.3 + + Removes all the items that have the \a key from the hash. + Returns the number of items removed. + + \sa remove() +*/ + +/*! + \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::remove(const Key &key, const T &value) \since 4.3 Removes all the items that have the \a key and the value \a @@ -2503,6 +3397,30 @@ size_t qHash(long double key, size_t seed) noexcept \sa remove() */ +/*! + \fn template <class Key, class T> void QMultiHash<Key, T>::clear() + \since 4.3 + + Removes all items from the hash and frees up all memory used by it. + + \sa remove() +*/ + +/*! \fn template <class Key, class T> template <typename Predicate> qsizetype QMultiHash<Key, T>::removeIf(Predicate pred) + \since 6.1 + + Removes all elements for which the predicate \a pred returns true + from the multi hash. + + The function supports predicates which take either an argument of + type \c{QMultiHash<Key, T>::iterator}, or an argument of type + \c{std::pair<const Key &, T &>}. + + Returns the number of elements removed, if any. + + \sa clear(), take() +*/ + /*! \fn template <class Key, class T> T QMultiHash<Key, T>::take(const Key &key) Removes the item with the \a key from the hash and returns @@ -2550,11 +3468,13 @@ size_t qHash(long double key, size_t seed) noexcept */ /*! - \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey = Key()) const + \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value) const + \fn template <class Key, class T> Key QMultiHash<Key, T>::key(const T &value, const Key &defaultKey) const \since 4.3 - Returns the first key mapped to \a value, or \a defaultKey if the - hash contains no item mapped to \a value. + Returns the first key mapped to \a value. If the hash contains no item + mapped to \a value, returns \a defaultKey, or a \l{default-constructed + value}{default-constructed key} if this parameter has not been supplied. This function can be slow (\l{linear time}), because QMultiHash's internal data structure is optimized for fast lookup by key, not @@ -2562,7 +3482,7 @@ size_t qHash(long double key, size_t seed) noexcept */ /*! - \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const + \fn template <class Key, class T> qsizetype QMultiHash<Key, T>::count(const Key &key, const T &value) const \since 4.3 Returns the number of items with the \a key and \a value. @@ -2579,12 +3499,16 @@ size_t qHash(long double key, size_t seed) noexcept If the hash contains multiple items with the \a key and \a value, the iterator returned points to the most recently inserted item. + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> typename QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::find(const Key &key, const T &value) const \since 4.3 \overload + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! @@ -2596,6 +3520,8 @@ size_t qHash(long double key, size_t seed) noexcept If the hash contains no such item, the function returns constEnd(). + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::begin() @@ -2603,12 +3529,16 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constBegin(), end() */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::begin() const \overload + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::cbegin() const @@ -2617,6 +3547,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), cend() */ @@ -2625,6 +3557,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), constEnd() */ @@ -2634,6 +3568,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyEnd() */ @@ -2642,6 +3578,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa begin(), constEnd() */ @@ -2655,6 +3593,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constBegin(), end() */ @@ -2664,6 +3604,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last item in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa cbegin(), end() */ @@ -2673,6 +3615,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item after the last key in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyBegin() */ @@ -2682,6 +3626,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueEnd() */ @@ -2691,6 +3637,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -2700,6 +3648,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueEnd() */ @@ -2709,6 +3659,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -2718,6 +3670,8 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa keyValueBegin() */ @@ -2727,20 +3681,36 @@ size_t qHash(long double key, size_t seed) noexcept Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary entry after the last entry in the hash. + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa constKeyValueBegin() */ +/*! \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() & + \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const & + \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() && + \fn template <class Key, class T> auto QMultiHash<Key, T>::asKeyValueRange() const && + \since 6.4 + + Returns a range object that allows iteration over this hash as + key/value pairs. For instance, this range object can be used in a + range-based for loop, in combination with a structured binding declaration: + + \snippet code/src_corelib_tools_qhash.cpp 35 + + Note that both the key and the value obtained this way are + references to the ones in the hash. Specifically, mutating the value + will modify the hash itself. + + \include qhash.cpp qhash-iterator-invalidation-func-desc + + \sa QKeyValueIterator +*/ /*! \class QMultiHash::iterator \inmodule QtCore \brief The QMultiHash::iterator class provides an STL-style non-const iterator for QMultiHash. - QMultiHash features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - QMultiHash\<Key, T\>::iterator allows you to iterate over a QMultiHash and to modify the value (but not the key) associated with a particular key. If you want to iterate over a const QMultiHash, @@ -2761,31 +3731,15 @@ size_t qHash(long double key, size_t seed) noexcept Unlike QMap, which orders its items by key, QMultiHash stores its items in an arbitrary order. - Let's see a few examples of things we can do with a - QMultiHash::iterator that we cannot do with a QMultiHash::const_iterator. Here's an example that increments every value stored in the QMultiHash by 2: \snippet code/src_corelib_tools_qhash.cpp 18 - Here's an example that removes all the items whose key is a - string that starts with an underscore character: - - \snippet code/src_corelib_tools_qhash.cpp 19 - - The call to QMultiHash::erase() removes the item pointed to by the - iterator from the hash, and returns an iterator to the next item. - Here's another way of removing an item while iterating: - - \snippet code/src_corelib_tools_qhash.cpp 20 - - It might be tempting to write code like this: + To remove elements from a QMultiHash you can use erase_if(QMultiHash\<Key, T\> &map, Predicate pred): \snippet code/src_corelib_tools_qhash.cpp 21 - However, this will potentially crash in \c{++i}, because \c i is - a dangling iterator after the call to erase(). - Multiple iterators can be used on the same hash. However, be aware that any modification performed directly on the QHash (inserting and removing items) can cause the iterators to become invalid. @@ -2796,10 +3750,6 @@ size_t qHash(long double key, size_t seed) noexcept to grow/shrink its internal hash table. Using any iterator after a rehashing operation has occurred will lead to undefined behavior. - You can however safely use iterators to remove entries from the hash - using the QHash::erase() method. This function can safely be called while - iterating, and won't affect the order of items in the hash. - If you need to keep iterators over a long period of time, we recommend that you use QMultiMap rather than QHash. @@ -2808,7 +3758,7 @@ size_t qHash(long double key, size_t seed) noexcept while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. - \sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMutableHashIterator + \sa QMultiHash::const_iterator, QMultiHash::key_iterator, QMultiHash::key_value_iterator */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::iterator::iterator() @@ -2904,12 +3854,6 @@ size_t qHash(long double key, size_t seed) noexcept \inmodule QtCore \brief The QMultiHash::const_iterator class provides an STL-style const iterator for QMultiHash. - QMultiHash features both \l{STL-style iterators} and \l{Java-style - iterators}. The STL-style iterators are more low-level and more - cumbersome to use; on the other hand, they are slightly faster - and, for developers who already know STL, have the advantage of - familiarity. - QMultiHash\<Key, T\>::const_iterator allows you to iterate over a QMultiHash. If you want to modify the QMultiHash as you iterate over it, you must use QMultiHash::iterator instead. It is @@ -2920,8 +3864,8 @@ size_t qHash(long double key, size_t seed) noexcept The default QMultiHash::const_iterator constructor creates an uninitialized iterator. You must initialize it using a QMultiHash - function like QMultiHash::constBegin(), QMultiHash::constEnd(), or - QMultiHash::find() before you can start iterating. Here's a typical + function like QMultiHash::cbegin(), QMultiHash::cend(), or + QMultiHash::constFind() before you can start iterating. Here's a typical loop that prints all the (key, value) pairs stored in a hash: \snippet code/src_corelib_tools_qhash.cpp 23 @@ -2933,28 +3877,24 @@ size_t qHash(long double key, size_t seed) noexcept recently to the least recently inserted value. Multiple iterators can be used on the same hash. However, be aware - that any modification performed directly on the QHash (inserting and + that any modification performed directly on the QMultiHash (inserting and removing items) can cause the iterators to become invalid. - Inserting items into the hash or calling methods such as QHash::reserve() - or QHash::squeeze() can invalidate all iterators pointing into the hash. - Iterators are guaranteed to stay valid only as long as the QHash doesn't have + Inserting items into the hash or calling methods such as QMultiHash::reserve() + or QMultiHash::squeeze() can invalidate all iterators pointing into the hash. + Iterators are guaranteed to stay valid only as long as the QMultiHash doesn't have to grow/shrink it's internal hash table. Using any iterator after a rehashing operation ahs occurred will lead to undefined behavior. - You can however safely use iterators to remove entries from the hash - using the QHash::erase() method. This function can safely be called while - iterating, and won't affect the order of items in the hash. - If you need to keep iterators over a long period of time, we recommend - that you use QMap rather than QHash. + that you use QMultiMap rather than QMultiHash. \warning Iterators on implicitly shared containers do not work exactly like STL-iterators. You should avoid copying a container while iterators are active on that container. For more information, read \l{Implicit sharing iterator problem}. - \sa QMultiHash::iterator, QMultiHashIterator + \sa QMultiHash::iterator, QMultiHash::key_iterator, QMultiHash::const_key_value_iterator */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator() @@ -3027,8 +3967,6 @@ size_t qHash(long double key, size_t seed) noexcept item. Calling this function on QMultiHash::end() leads to undefined results. - - \sa operator--() */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator QMultiHash<Key, T>::const_iterator::operator++(int) @@ -3111,8 +4049,6 @@ size_t qHash(long double key, size_t seed) noexcept item. Calling this function on QMultiHash::keyEnd() leads to undefined results. - - \sa operator--() */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::key_iterator QMultiHash<Key, T>::key_iterator::operator++(int) @@ -3194,4 +4130,64 @@ size_t qHash(long double key, size_t seed) noexcept Type \c T must be supported by qHash(). */ +/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QHash<Key, T> &hash, Predicate pred) + \relates QHash + \since 6.1 + + Removes all elements for which the predicate \a pred returns true + from the hash \a hash. + + The function supports predicates which take either an argument of + type \c{QHash<Key, T>::iterator}, or an argument of type + \c{std::pair<const Key &, T &>}. + + Returns the number of elements removed, if any. +*/ + +/*! \fn template <typename Key, typename T, typename Predicate> qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred) + \relates QMultiHash + \since 6.1 + + Removes all elements for which the predicate \a pred returns true + from the multi hash \a hash. + + The function supports predicates which take either an argument of + type \c{QMultiHash<Key, T>::iterator}, or an argument of type + \c{std::pair<const Key &, T &>}. + + Returns the number of elements removed, if any. +*/ + +#ifdef QT_HAS_CONSTEXPR_BITOPS +namespace QHashPrivate { +static_assert(qPopulationCount(SpanConstants::NEntries) == 1, + "NEntries must be a power of 2 for bucketForHash() to work."); + +// ensure the size of a Span does not depend on the template parameters +using Node1 = Node<int, int>; +static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>)); +static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>)); +static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>)); +static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries); +static_assert(qNextPowerOfTwo(sizeof(Span<Node1>)) == SpanConstants::NEntries * 2); + +// ensure allocations are always a power of two, at a minimum NEntries, +// obeying the fomula +// qNextPowerOfTwo(2 * N); +// without overflowing +static constexpr size_t NEntries = SpanConstants::NEntries; +static_assert(GrowthPolicy::bucketsForCapacity(1) == NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries / 2 + 0) == NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries / 2 + 1) == 2 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 - 1) == 2 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 + 0) == 4 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 + 1) == 4 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 2 - 1) == 4 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 2 + 0) == 8 * NEntries); +static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1); +static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX); +static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX); +} +#endif + QT_END_NAMESPACE |