diff options
Diffstat (limited to 'src/corelib/tools/qhash.cpp')
| -rw-r--r-- | src/corelib/tools/qhash.cpp | 1267 |
1 files changed, 896 insertions, 371 deletions
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index fe3d8d912e..12e90daecf 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1,43 +1,7 @@ -/**************************************************************************** -** -** Copyright (C) 2020 The Qt Company Ltd. -** Copyright (C) 2021 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 @@ -66,22 +30,155 @@ #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. @@ -139,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; @@ -188,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 { \ @@ -221,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; @@ -230,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; @@ -250,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; @@ -290,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. @@ -301,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 { \ @@ -326,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; @@ -335,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; @@ -355,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; @@ -386,7 +508,70 @@ static uint siphash(const uint8_t *in, uint inlen, const uint seed) b = v0 ^ v1 ^ v2 ^ v3; return b; } -#endif +#undef SIPROUND +#undef ROTL + +// 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, seed2); +} + +template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept +{ + 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 @@ -402,29 +587,30 @@ static uint siphash(const uint8_t *in, uint inlen, const uint seed) #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 -#undef QHASH_AES_SANITIZER_BUILD - -QT_FUNCTION_TARGET(AES) -static size_t aeshash(const uchar *p, size_t len, size_t seed) noexcept -{ - __m128i key; - if (sizeof(size_t) == 8) { -#ifdef Q_PROCESSOR_X86_64 - quint64 seededlen = seed ^ len; - __m128i mseed = _mm_cvtsi64_si128(seed); - key = _mm_insert_epi64(mseed, seededlen, 1); -#endif - } else { - quint32 replicated_len = quint16(len) | (quint32(quint16(len)) << 16); - __m128i mseed = _mm_cvtsi32_si128(int(seed)); - key = _mm_insert_epi32(mseed, replicated_len, 1); - key = _mm_unpacklo_epi64(key, key); - } - +namespace { // This is inspired by the algorithm in the Go language. See: - // https://github.com/golang/go/blob/894abb5f680c040777f17f9f8ee5a5ab3a03cb94/src/runtime/asm_386.s#L902 - // https://github.com/golang/go/blob/894abb5f680c040777f17f9f8ee5a5ab3a03cb94/src/runtime/asm_amd64.s#L903 + // 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 @@ -432,115 +618,354 @@ static size_t aeshash(const uchar *p, size_t len, size_t seed) noexcept // 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") - const auto hash16bytes = [](__m128i &state0, __m128i data) QT_FUNCTION_TARGET(AES) { + 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 - __m128i state0 = key; - auto src = reinterpret_cast<const __m128i *>(p); +Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2) +{ + __m128i mseed = mm_cvtsz_si128(seed); + mseed2 = mm_set1_epz(seed2); - if (len < 16) - goto lt16; - if (len < 32) - goto lt32; + // 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); - // rounds of 32 bytes + // 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; +} + +Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const +{ { - // Make state1 = ~state0: - __m128i one = _mm_cmpeq_epi64(key, key); - __m128i state1 = _mm_xor_si128(state0, one); + // unlike the Go code, we don't have more per-process seed + __m128i state1 = _mm_aesenc_si128(state0, mseed2); + return state1; + } +} - // do simplified rounds of 32 bytes: unlike the Go code, we only - // scramble twice and we keep 256 bits of state - const auto srcend = src + (len / 32); - while (src < srcend) { - __m128i data0 = _mm_loadu_si128(src); - __m128i data1 = _mm_loadu_si128(src + 1); - 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); - src += 2; +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); } - len &= 0x1f; - // do we still have 16 or more bytes? - if (len & 0x10) { -lt32: - __m128i data = _mm_loadu_si128(src); - hash16bytes(state0, data); - ++src; - } - len &= 0xf; + return mm_cvtsi128_sz(state0); +} -lt16: +// 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) { - // load the last chunk of data // 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 (Q_LIKELY(quintptr(src + 1) & 0xff0)) { - // same page, we definitely can't fault: - // 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, - }; + if ((quintptr(src) & (CachelineSize / 2)) == 0) { + // lower half of the cacheline: __m128i mask = _mm_loadu_si128(reinterpret_cast<const __m128i *>(maskarray + 15 - len)); - data = _mm_loadu_si128(src); + data = loadu128<ZX>(src); data = _mm_and_si128(data, mask); } else { - // too close to the end of the page, it could fault: - // 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 - }; + // upper half of the cacheline: __m128i control = _mm_loadu_si128(reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len)); - p = reinterpret_cast<const uchar *>(src - 1); - data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(p + len)); + data = loadu128<ZX>(advance<ZX>(srcend, -1)); data = _mm_shuffle_epi8(data, control); } hash16bytes(state0, data); } + return mm_cvtsi128_sz(state0); +} - // extract state0 -# if QT_POINTER_SIZE == 8 - return _mm_cvtsi128_si64(state0); -# else - return _mm_cvtsi128_si32(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 +#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) noexcept +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 - quint64 seededlen = seed ^ len; - uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seededlen)); + uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2)); key = vreinterpretq_u8_u64(vseed); # else - quint32 replicated_len = quint16(len) | (quint32(quint16(len)) << 16); + uint32x2_t vseed = vmov_n_u32(seed); - vseed = vset_lane_u32(replicated_len, vseed, 1); + vseed = vset_lane_u32(seed2, vseed, 1); key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed)); # endif @@ -668,31 +1093,25 @@ size_t qHashBits(const void *p, size_t size, size_t seed) noexcept // 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(reinterpret_cast<const uchar *>(p), size, seed); + 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 defined(Q_OS_LINUX) - // Do specific runtime-only check as Yocto hard enables Crypto extension for - // all armv8 configs - if (seed && (qCpuFeatures() & CpuFeatureAES)) -# else if (seed && qCpuHasFeature(AES)) -# endif - return aeshash(reinterpret_cast<const uchar *>(p), size, seed); + return aeshash(data, size, seed, seed2); #endif - if (size <= QT_POINTER_SIZE) - return murmurhash(p, size, seed); - return siphash(reinterpret_cast<const uchar *>(p), size, seed); + return qHashBits_fallback<>(data, size, seed, seed2); } -size_t qHash(const QByteArray &key, size_t seed) noexcept -{ - return qHashBits(key.constData(), size_t(key.size()), seed); -} - -size_t qHash(const QByteArrayView &key, size_t seed) noexcept +size_t qHash(QByteArrayView key, size_t seed) noexcept { return qHashBits(key.constData(), size_t(key.size()), seed); } @@ -702,6 +1121,7 @@ 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 { qsizetype m = bitArray.d.size() - 1; @@ -714,72 +1134,35 @@ size_t qHash(const QBitArray &bitArray, size_t seed) noexcept result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1); return result; } +#endif -size_t qHash(QLatin1String key, size_t seed) noexcept -{ - return qHashBits(reinterpret_cast<const uchar *>(key.data()), size_t(key.size()), seed); -} - -/*! - \internal - - Note: not \c{noexcept}, but called from a \c{noexcept} function and thus - will cause termination if any of the functions here throw. -*/ -enum HashCreationMode { Initial, Reseed }; -static size_t qt_create_qhash_seed(HashCreationMode mode) +size_t qHash(QLatin1StringView key, size_t seed) noexcept { - size_t seed = 0; - #ifdef QT_BOOTSTRAPPED - Q_UNUSED(mode) -#else - bool ok; - seed = qEnvironmentVariableIntValue("QT_HASH_SEED", &ok); - if (ok) { - if (seed) { - // can't use qWarning here (reentrancy) - fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0; ignored.\n"); - } - seed = 1; // QHashSeed::globalSeed subtracts 1 - } else if (mode == Initial) { - auto data = qt_initial_random_value(); - seed = data.data[0] ^ data.data[1]; - } else if (sizeof(seed) > sizeof(uint)) { - seed = QRandomGenerator::system()->generate64(); - } else { - seed = QRandomGenerator::system()->generate(); - } -#endif // 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 - return seed; -} + auto data = reinterpret_cast<const uchar *>(key.data()); + size_t size = key.size(); -/* - The QHash seed itself. - - We store the seed value plus one, so the value zero is used to indicate the - seed is not initialized. This is corrected before passing to the user. -*/ -static QBasicAtomicInteger<size_t> qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(0); + // 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); -/*! - \internal - \threadsafe - - Initializes the seed and returns it. -*/ -static size_t qt_initialize_qhash_seed() -{ - size_t theirSeed; // another thread's seed - size_t ourSeed = qt_create_qhash_seed(Initial); - if (qt_qhash_seed.testAndSetRelaxed(0, ourSeed, theirSeed)) - return ourSeed; - return theirSeed; +#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); } /*! \class QHashSeed + \inmodule QtCore \since 6.2 The QHashSeed class is used to convey the QHash seed. This is used @@ -832,11 +1215,7 @@ static size_t qt_initialize_qhash_seed() */ QHashSeed QHashSeed::globalSeed() noexcept { - size_t seed = qt_qhash_seed.loadRelaxed(); - if (Q_UNLIKELY(seed == 0)) - seed = qt_initialize_qhash_seed(); - - return { seed - 1 }; + return qt_qhash_seed.currentSeed(0); } /*! @@ -850,7 +1229,7 @@ QHashSeed QHashSeed::globalSeed() noexcept */ void QHashSeed::setDeterministicGlobalSeed() { - qt_qhash_seed.storeRelease(1); + qt_qhash_seed.clearSeed(); } /*! @@ -870,8 +1249,7 @@ void QHashSeed::setDeterministicGlobalSeed() */ void QHashSeed::resetRandomGlobalSeed() { - size_t seed = qt_create_qhash_seed(Reseed); - qt_qhash_seed.storeRelaxed(seed + 1); + qt_qhash_seed.resetSeed(); } #if QT_DEPRECATED_SINCE(6,6) @@ -913,7 +1291,7 @@ int qGlobalQHashSeed() If the environment variable \c QT_HASH_SEED is set, calling this function will result in a no-op. - \sa qHashSeed::globalSeed, QHashSeed + \sa QHashSeed::globalSeed(), QHashSeed */ void qSetGlobalQHashSeed(int newSeed) { @@ -1184,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 @@ -1212,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 @@ -1237,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 @@ -1255,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 @@ -1299,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 @@ -1313,7 +1709,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 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 @@ -1441,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 @@ -1480,10 +1876,15 @@ size_t qHash(long double key, size_t seed) noexcept 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 @@ -1579,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. */ @@ -1656,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. @@ -1671,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. @@ -1815,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) @@ -1837,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() */ @@ -1888,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 @@ -1918,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 @@ -1932,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() */ @@ -1940,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() */ @@ -1949,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() */ @@ -1957,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 @@ -1970,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() */ @@ -1979,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() */ @@ -1988,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() */ @@ -1997,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() */ @@ -2006,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() */ @@ -2015,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() */ @@ -2024,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() */ @@ -2033,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() */ @@ -2042,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 @@ -2059,6 +2522,8 @@ size_t qHash(long double key, size_t seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 15 + \include qhash.cpp qhash-iterator-invalidation-func-desc + \sa remove(), take(), find() */ @@ -2078,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 @@ -2095,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() */ @@ -2104,6 +2575,10 @@ 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 */ /*! @@ -2115,6 +2590,8 @@ size_t qHash(long double key, size_t seed) noexcept construction. Returns an iterator pointing to the new element. + + \include qhash.cpp qhash-iterator-invalidation-func-desc */ @@ -2125,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 @@ -2137,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 @@ -2244,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, @@ -2270,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. @@ -2305,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. @@ -2317,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() @@ -2413,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 @@ -2429,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 @@ -2451,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() @@ -2742,9 +3192,6 @@ 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) @@ -2758,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. */ @@ -2774,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() */ @@ -2786,6 +3237,10 @@ 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() */ @@ -2804,6 +3259,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 insert */ @@ -2820,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 */ @@ -2852,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 @@ -2886,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() */ @@ -2917,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 @@ -2997,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 @@ -3009,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. @@ -3026,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 */ /*! @@ -3043,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() @@ -3050,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 @@ -3064,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() */ @@ -3072,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() */ @@ -3081,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() */ @@ -3089,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() */ @@ -3102,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() */ @@ -3111,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() */ @@ -3120,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() */ @@ -3129,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() */ @@ -3138,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() */ @@ -3147,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() */ @@ -3156,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() */ @@ -3165,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() */ @@ -3174,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, @@ -3208,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. @@ -3243,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. @@ -3255,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() @@ -3351,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 @@ -3367,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 @@ -3380,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 + \sa QMultiHash::iterator, QMultiHash::key_iterator, QMultiHash::const_key_value_iterator */ /*! \fn template <class Key, class T> QMultiHash<Key, T>::const_iterator::const_iterator() @@ -3665,4 +4158,36 @@ size_t qHash(long double key, size_t seed) noexcept 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 |