diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
| -rw-r--r-- | src/corelib/tools/qhash.h | 3059 |
1 files changed, 2186 insertions, 873 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 9fd96686f5..e7cd4123fb 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -1,258 +1,880 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.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) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only #ifndef QHASH_H #define QHASH_H -#include <QtCore/qchar.h> +#include <QtCore/qalgorithms.h> +#include <QtCore/qcontainertools_impl.h> +#include <QtCore/qhashfunctions.h> #include <QtCore/qiterator.h> #include <QtCore/qlist.h> #include <QtCore/qrefcount.h> -#include <QtCore/qhashfunctions.h> -#include <QtCore/qcontainertools_impl.h> -#include <algorithm> #include <initializer_list> +#include <functional> // for std::hash -#if defined(Q_CC_MSVC) -#pragma warning( push ) -#pragma warning( disable : 4311 ) // disable pointer truncation warning -#pragma warning( disable : 4127 ) // conditional expression is constant -#endif +class tst_QHash; // for befriending QT_BEGIN_NAMESPACE -struct Q_CORE_EXPORT QHashData +struct QHashDummyValue { - struct Node { - Node *next; - uint h; - }; + bool operator==(const QHashDummyValue &) const noexcept { return true; } +}; - Node *fakeNext; - Node **buckets; - QtPrivate::RefCount ref; - int size; - int nodeSize; - short userNumBits; - short numBits; - int numBuckets; - uint seed; - uint sharable : 1; - uint strictAlignment : 1; - uint reserved : 30; - - void *allocateNode(int nodeAlign); - void freeNode(void *node); - QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), - int nodeSize, int nodeAlign); - bool willGrow(); - void hasShrunk(); - void rehash(int hint); - void free_helper(void (*node_delete)(Node *)); - Node *firstNode(); -#ifdef QT_QHASH_DEBUG - void dump(); - void checkSanity(); -#endif - static Node *nextNode(Node *node); - static Node *previousNode(Node *node); +namespace QHashPrivate { - static const QHashData shared_null; -}; +template <typename T, typename = void> +constexpr inline bool HasQHashOverload = false; + +template <typename T> +constexpr inline bool HasQHashOverload<T, std::enable_if_t< + std::is_convertible_v<decltype(qHash(std::declval<const T &>(), std::declval<size_t>())), size_t> +>> = true; + +template <typename T, typename = void> +constexpr inline bool HasStdHashSpecializationWithSeed = false; + +template <typename T> +constexpr inline bool HasStdHashSpecializationWithSeed<T, std::enable_if_t< + std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>(), std::declval<size_t>())), size_t> +>> = true; + +template <typename T, typename = void> +constexpr inline bool HasStdHashSpecializationWithoutSeed = false; -inline bool QHashData::willGrow() +template <typename T> +constexpr inline bool HasStdHashSpecializationWithoutSeed<T, std::enable_if_t< + std::is_convertible_v<decltype(std::hash<T>()(std::declval<const T &>())), size_t> +>> = true; + +template <typename T> +size_t calculateHash(const T &t, size_t seed = 0) { - if (size >= numBuckets) { - rehash(numBits + 1); - return true; + if constexpr (HasQHashOverload<T>) { + return qHash(t, seed); + } else if constexpr (HasStdHashSpecializationWithSeed<T>) { + return std::hash<T>()(t, seed); + } else if constexpr (HasStdHashSpecializationWithoutSeed<T>) { + Q_UNUSED(seed); + return std::hash<T>()(t); } else { - return false; + static_assert(sizeof(T) == 0, "The key type must have a qHash overload or a std::hash specialization"); + return 0; } } -inline void QHashData::hasShrunk() +template <typename Key, typename T> +struct Node { - if (size <= (numBuckets >> 3) && numBits > userNumBits) { - QT_TRY { - rehash(qMax(int(numBits) - 2, int(userNumBits))); - } QT_CATCH(const std::bad_alloc &) { - // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe. - } + using KeyType = Key; + using ValueType = T; + + Key key; + T value; + template<typename ...Args> + static void createInPlace(Node *n, Key &&k, Args &&... args) + { new (n) Node{ std::move(k), T(std::forward<Args>(args)...) }; } + template<typename ...Args> + static void createInPlace(Node *n, const Key &k, Args &&... args) + { new (n) Node{ Key(k), T(std::forward<Args>(args)...) }; } + template<typename ...Args> + void emplaceValue(Args &&... args) + { + value = T(std::forward<Args>(args)...); } -} + T &&takeValue() noexcept(std::is_nothrow_move_assignable_v<T>) + { + return std::move(value); + } + bool valuesEqual(const Node *other) const { return value == other->value; } +}; -inline QHashData::Node *QHashData::firstNode() -{ - Node *e = reinterpret_cast<Node *>(this); - Node **bucket = buckets; - int n = numBuckets; - while (n--) { - if (*bucket != e) - return *bucket; - ++bucket; +template <typename Key> +struct Node<Key, QHashDummyValue> { + using KeyType = Key; + using ValueType = QHashDummyValue; + + Key key; + template<typename ...Args> + static void createInPlace(Node *n, Key &&k, Args &&...) + { new (n) Node{ std::move(k) }; } + template<typename ...Args> + static void createInPlace(Node *n, const Key &k, Args &&...) + { new (n) Node{ k }; } + template<typename ...Args> + void emplaceValue(Args &&...) + { } - return e; -} + ValueType takeValue() { return QHashDummyValue(); } + bool valuesEqual(const Node *) const { return true; } +}; -struct QHashDummyValue +template <typename T> +struct MultiNodeChain { + T value; + MultiNodeChain *next = nullptr; + ~MultiNodeChain() + { + } + qsizetype free() noexcept(std::is_nothrow_destructible_v<T>) + { + qsizetype nEntries = 0; + MultiNodeChain *e = this; + while (e) { + MultiNodeChain *n = e->next; + ++nEntries; + delete e; + e = n; + } + return nEntries; + } + bool contains(const T &val) const noexcept + { + const MultiNodeChain *e = this; + while (e) { + if (e->value == val) + return true; + e = e->next; + } + return false; + } }; -constexpr bool operator==(const QHashDummyValue &, const QHashDummyValue &) noexcept +template <typename Key, typename T> +struct MultiNode { - return true; -} + using KeyType = Key; + using ValueType = T; + using Chain = MultiNodeChain<T>; + + Key key; + Chain *value; + + template<typename ...Args> + static void createInPlace(MultiNode *n, Key &&k, Args &&... args) + { new (n) MultiNode(std::move(k), new Chain{ T(std::forward<Args>(args)...), nullptr }); } + template<typename ...Args> + static void createInPlace(MultiNode *n, const Key &k, Args &&... args) + { new (n) MultiNode(k, new Chain{ T(std::forward<Args>(args)...), nullptr }); } + + MultiNode(const Key &k, Chain *c) + : key(k), + value(c) + {} + MultiNode(Key &&k, Chain *c) noexcept(std::is_nothrow_move_assignable_v<Key>) + : key(std::move(k)), + value(c) + {} + + MultiNode(MultiNode &&other) + : key(other.key), + value(std::exchange(other.value, nullptr)) + { + } -Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE); + MultiNode(const MultiNode &other) + : key(other.key) + { + Chain *c = other.value; + Chain **e = &value; + while (c) { + Chain *chain = new Chain{ c->value, nullptr }; + *e = chain; + e = &chain->next; + c = c->next; + } + } + ~MultiNode() + { + if (value) + value->free(); + } + static qsizetype freeChain(MultiNode *n) noexcept(std::is_nothrow_destructible_v<T>) + { + qsizetype size = n->value->free(); + n->value = nullptr; + return size; + } + template<typename ...Args> + void insertMulti(Args &&... args) + { + Chain *e = new Chain{ T(std::forward<Args>(args)...), nullptr }; + e->next = std::exchange(value, e); + } + template<typename ...Args> + void emplaceValue(Args &&... args) + { + value->value = T(std::forward<Args>(args)...); + } +}; -template <class Key, class T> -struct QHashNode +template<typename Node> +constexpr bool isRelocatable() { - QHashNode *next; - const uint h; - const Key key; - T value; + return QTypeInfo<typename Node::KeyType>::isRelocatable && QTypeInfo<typename Node::ValueType>::isRelocatable; +} - inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n) - : next(n), h(hash), key(key0), value(value0) {} - inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; } +struct SpanConstants { + static constexpr size_t SpanShift = 7; + static constexpr size_t NEntries = (1 << SpanShift); + static constexpr size_t LocalBucketMask = (NEntries - 1); + static constexpr size_t UnusedEntry = 0xff; -private: - Q_DISABLE_COPY(QHashNode) + static_assert ((NEntries & LocalBucketMask) == 0, "NEntries must be a power of two."); }; -// Specialize for QHashDummyValue in order to save some memory -template <class Key> -struct QHashNode<Key, QHashDummyValue> -{ - union { - QHashNode *next; - QHashDummyValue value; +// Regular hash tables consist of a list of buckets that can store Nodes. But simply allocating one large array of buckets +// would waste a lot of memory. To avoid this, we split the vector of buckets up into a vector of Spans. Each Span represents +// NEntries buckets. To quickly find the correct Span that holds a bucket, NEntries must be a power of two. +// +// Inside each Span, there is an offset array that represents the actual buckets. offsets contains either an index into the +// actual storage space for the Nodes (the 'entries' member) or 0xff (UnusedEntry) to flag that the bucket is empty. +// As we have only 128 entries per Span, the offset array can be represented using an unsigned char. This trick makes the hash +// table have a very small memory overhead compared to many other implementations. +template<typename Node> +struct Span { + // Entry is a slot available for storing a Node. The Span holds a pointer to + // an array of Entries. Upon construction of the array, those entries are + // unused, and nextFree() is being used to set up a singly linked list + // of free entries. + // When a node gets inserted, the first free entry is being picked, removed + // from the singly linked list and the Node gets constructed in place. + struct Entry { + struct { alignas(Node) unsigned char data[sizeof(Node)]; } storage; + + unsigned char &nextFree() { return *reinterpret_cast<unsigned char *>(&storage); } + Node &node() { return *reinterpret_cast<Node *>(&storage); } }; - const uint h; - const Key key; - inline QHashNode(const Key &key0, const QHashDummyValue &, uint hash, QHashNode *n) - : next(n), h(hash), key(key0) {} - inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; } + unsigned char offsets[SpanConstants::NEntries]; + Entry *entries = nullptr; + unsigned char allocated = 0; + unsigned char nextFree = 0; + Span() noexcept + { + memset(offsets, SpanConstants::UnusedEntry, sizeof(offsets)); + } + ~Span() + { + freeData(); + } + void freeData() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (entries) { + if constexpr (!std::is_trivially_destructible<Node>::value) { + for (auto o : offsets) { + if (o != SpanConstants::UnusedEntry) + entries[o].node().~Node(); + } + } + delete[] entries; + entries = nullptr; + } + } + Node *insert(size_t i) + { + Q_ASSERT(i < SpanConstants::NEntries); + Q_ASSERT(offsets[i] == SpanConstants::UnusedEntry); + if (nextFree == allocated) + addStorage(); + unsigned char entry = nextFree; + Q_ASSERT(entry < allocated); + nextFree = entries[entry].nextFree(); + offsets[i] = entry; + return &entries[entry].node(); + } + void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value) + { + Q_ASSERT(bucket < SpanConstants::NEntries); + Q_ASSERT(offsets[bucket] != SpanConstants::UnusedEntry); + + unsigned char entry = offsets[bucket]; + offsets[bucket] = SpanConstants::UnusedEntry; -private: - Q_DISABLE_COPY(QHashNode) + entries[entry].node().~Node(); + entries[entry].nextFree() = nextFree; + nextFree = entry; + } + size_t offset(size_t i) const noexcept + { + return offsets[i]; + } + bool hasNode(size_t i) const noexcept + { + return (offsets[i] != SpanConstants::UnusedEntry); + } + Node &at(size_t i) noexcept + { + Q_ASSERT(i < SpanConstants::NEntries); + Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry); + + return entries[offsets[i]].node(); + } + const Node &at(size_t i) const noexcept + { + Q_ASSERT(i < SpanConstants::NEntries); + Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry); + + return entries[offsets[i]].node(); + } + Node &atOffset(size_t o) noexcept + { + Q_ASSERT(o < allocated); + + return entries[o].node(); + } + const Node &atOffset(size_t o) const noexcept + { + Q_ASSERT(o < allocated); + + return entries[o].node(); + } + void moveLocal(size_t from, size_t to) noexcept + { + Q_ASSERT(offsets[from] != SpanConstants::UnusedEntry); + Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry); + offsets[to] = offsets[from]; + offsets[from] = SpanConstants::UnusedEntry; + } + void moveFromSpan(Span &fromSpan, size_t fromIndex, size_t to) noexcept(std::is_nothrow_move_constructible_v<Node>) + { + Q_ASSERT(to < SpanConstants::NEntries); + Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry); + Q_ASSERT(fromIndex < SpanConstants::NEntries); + Q_ASSERT(fromSpan.offsets[fromIndex] != SpanConstants::UnusedEntry); + if (nextFree == allocated) + addStorage(); + Q_ASSERT(nextFree < allocated); + offsets[to] = nextFree; + Entry &toEntry = entries[nextFree]; + nextFree = toEntry.nextFree(); + + size_t fromOffset = fromSpan.offsets[fromIndex]; + fromSpan.offsets[fromIndex] = SpanConstants::UnusedEntry; + Entry &fromEntry = fromSpan.entries[fromOffset]; + + if constexpr (isRelocatable<Node>()) { + memcpy(&toEntry, &fromEntry, sizeof(Entry)); + } else { + new (&toEntry.node()) Node(std::move(fromEntry.node())); + fromEntry.node().~Node(); + } + fromEntry.nextFree() = fromSpan.nextFree; + fromSpan.nextFree = static_cast<unsigned char>(fromOffset); + } + + void addStorage() + { + Q_ASSERT(allocated < SpanConstants::NEntries); + Q_ASSERT(nextFree == allocated); + // the hash table should always be between 25 and 50% full + // this implies that we on average have between 32 and 64 entries + // in here. More exactly, we have a binominal distribution of the amount of + // occupied entries. + // For a 25% filled table, the average is 32 entries, with a 95% chance that we have between + // 23 and 41 entries. + // For a 50% filled table, the average is 64 entries, with a 95% chance that we have between + // 53 and 75 entries. + // Since we only resize the table once it's 50% filled and we want to avoid copies of + // data where possible, we initially allocate 48 entries, then resize to 80 entries, after that + // resize by increments of 16. That way, we usually only get one resize of the table + // while filling it. + size_t alloc; + static_assert(SpanConstants::NEntries % 8 == 0); + if (!allocated) + alloc = SpanConstants::NEntries / 8 * 3; + else if (allocated == SpanConstants::NEntries / 8 * 3) + alloc = SpanConstants::NEntries / 8 * 5; + else + alloc = allocated + SpanConstants::NEntries/8; + Entry *newEntries = new Entry[alloc]; + // we only add storage if the previous storage was fully filled, so + // simply copy the old data over + if constexpr (isRelocatable<Node>()) { + if (allocated) + memcpy(newEntries, entries, allocated * sizeof(Entry)); + } else { + for (size_t i = 0; i < allocated; ++i) { + new (&newEntries[i].node()) Node(std::move(entries[i].node())); + entries[i].node().~Node(); + } + } + for (size_t i = allocated; i < alloc; ++i) { + newEntries[i].nextFree() = uchar(i + 1); + } + delete[] entries; + entries = newEntries; + allocated = uchar(alloc); + } }; +// QHash uses a power of two growth policy. +namespace GrowthPolicy { +inline constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept +{ + constexpr int SizeDigits = std::numeric_limits<size_t>::digits; + + // We want to use at minimum a full span (128 entries), so we hardcode it for any requested + // capacity <= 64. Any capacity above that gets rounded to a later power of two. + if (requestedCapacity <= 64) + return SpanConstants::NEntries; + + // Same as + // qNextPowerOfTwo(2 * requestedCapacity); + // + // but ensuring neither our multiplication nor the function overflow. + // Additionally, the maximum memory allocation is 2^31-1 or 2^63-1 bytes + // (limited by qsizetype and ptrdiff_t). + int count = qCountLeadingZeroBits(requestedCapacity); + if (count < 2) + return (std::numeric_limits<size_t>::max)(); // will cause std::bad_alloc + return size_t(1) << (SizeDigits - count + 1); +} +inline constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept +{ + return hash & (nBuckets - 1); +} +} // namespace GrowthPolicy -#if 0 -// ### -// The introduction of the QHash random seed breaks this optimization, as it -// relies on qHash(int i) = i. If the hash value is salted, then the hash -// table becomes corrupted. -// -// A bit more research about whether it makes sense or not to salt integer -// keys (and in general keys whose hash value is easy to invert) -// is needed, or about how keep this optimization and the seed (f.i. by -// specializing QHash for integer values, and re-apply the seed during lookup). -// -// Be aware that such changes can easily be binary incompatible, and therefore -// cannot be made during the Qt 5 lifetime. -#define Q_HASH_DECLARE_INT_NODES(key_type) \ - template <class T> \ - struct QHashDummyNode<key_type, T> { \ - QHashDummyNode *next; \ - union { uint h; key_type key; }; \ -\ - inline QHashDummyNode(key_type /* key0 */) {} \ - }; \ -\ - template <class T> \ - struct QHashNode<key_type, T> { \ - QHashNode *next; \ - union { uint h; key_type key; }; \ - T value; \ -\ - inline QHashNode(key_type /* key0 */) {} \ - inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \ - inline bool same_key(uint h0, key_type) const { return h0 == h; } \ - } - -#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN -Q_HASH_DECLARE_INT_NODES(short); -Q_HASH_DECLARE_INT_NODES(ushort); -#endif -Q_HASH_DECLARE_INT_NODES(int); -Q_HASH_DECLARE_INT_NODES(uint); -#undef Q_HASH_DECLARE_INT_NODES -#endif // #if 0 +template <typename Node> +struct iterator; -template <class Key, class T> -class QHash +template <typename Node> +struct Data { - typedef QHashNode<Key, T> Node; + using Key = typename Node::KeyType; + using T = typename Node::ValueType; + using Span = QHashPrivate::Span<Node>; + using iterator = QHashPrivate::iterator<Node>; + + QtPrivate::RefCount ref = {{1}}; + size_t size = 0; + size_t numBuckets = 0; + size_t seed = 0; + Span *spans = nullptr; + + static constexpr size_t maxNumBuckets() noexcept + { + return (std::numeric_limits<ptrdiff_t>::max)() / sizeof(Span); + } + + struct Bucket { + Span *span; + size_t index; + + Bucket(Span *s, size_t i) noexcept + : span(s), index(i) + {} + Bucket(const Data *d, size_t bucket) noexcept + : span(d->spans + (bucket >> SpanConstants::SpanShift)), + index(bucket & SpanConstants::LocalBucketMask) + {} + Bucket(iterator it) noexcept + : Bucket(it.d, it.bucket) + {} + + size_t toBucketIndex(const Data *d) const noexcept + { + return ((span - d->spans) << SpanConstants::SpanShift) | index; + } + iterator toIterator(const Data *d) const noexcept { return iterator{d, toBucketIndex(d)}; } + void advanceWrapped(const Data *d) noexcept + { + advance_impl(d, d->spans); + } + void advance(const Data *d) noexcept + { + advance_impl(d, nullptr); + } + bool isUnused() const noexcept + { + return !span->hasNode(index); + } + size_t offset() const noexcept + { + return span->offset(index); + } + Node &nodeAtOffset(size_t offset) + { + return span->atOffset(offset); + } + Node *node() + { + return &span->at(index); + } + Node *insert() const + { + return span->insert(index); + } - union { - QHashData *d; - QHashNode<Key, T> *e; + private: + friend bool operator==(Bucket lhs, Bucket rhs) noexcept + { + return lhs.span == rhs.span && lhs.index == rhs.index; + } + friend bool operator!=(Bucket lhs, Bucket rhs) noexcept { return !(lhs == rhs); } + + void advance_impl(const Data *d, Span *whenAtEnd) noexcept + { + Q_ASSERT(span); + ++index; + if (Q_UNLIKELY(index == SpanConstants::NEntries)) { + index = 0; + ++span; + if (span - d->spans == ptrdiff_t(d->numBuckets >> SpanConstants::SpanShift)) + span = whenAtEnd; + } + } }; - static inline Node *concrete(QHashData::Node *node) { - return reinterpret_cast<Node *>(node); + static auto allocateSpans(size_t numBuckets) + { + struct R { + Span *spans; + size_t nSpans; + }; + + constexpr qptrdiff MaxSpanCount = (std::numeric_limits<qptrdiff>::max)() / sizeof(Span); + constexpr size_t MaxBucketCount = MaxSpanCount << SpanConstants::SpanShift; + + if (numBuckets > MaxBucketCount) { + Q_CHECK_PTR(false); + Q_UNREACHABLE(); // no exceptions and no assertions -> no error reporting + } + + size_t nSpans = numBuckets >> SpanConstants::SpanShift; + return R{ new Span[nSpans], nSpans }; + } + + Data(size_t reserve = 0) + { + numBuckets = GrowthPolicy::bucketsForCapacity(reserve); + spans = allocateSpans(numBuckets).spans; + seed = QHashSeed::globalSeed(); + } + + void reallocationHelper(const Data &other, size_t nSpans, bool resized) + { + for (size_t s = 0; s < nSpans; ++s) { + const Span &span = other.spans[s]; + for (size_t index = 0; index < SpanConstants::NEntries; ++index) { + if (!span.hasNode(index)) + continue; + const Node &n = span.at(index); + auto it = resized ? findBucket(n.key) : Bucket { spans + s, index }; + Q_ASSERT(it.isUnused()); + Node *newNode = it.insert(); + new (newNode) Node(n); + } + } + } + + Data(const Data &other) : size(other.size), numBuckets(other.numBuckets), seed(other.seed) + { + auto r = allocateSpans(numBuckets); + spans = r.spans; + reallocationHelper(other, r.nSpans, false); + } + Data(const Data &other, size_t reserved) : size(other.size), seed(other.seed) + { + numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved)); + spans = allocateSpans(numBuckets).spans; + size_t otherNSpans = other.numBuckets >> SpanConstants::SpanShift; + reallocationHelper(other, otherNSpans, numBuckets != other.numBuckets); + } + + static Data *detached(Data *d) + { + if (!d) + return new Data; + Data *dd = new Data(*d); + if (!d->ref.deref()) + delete d; + return dd; + } + static Data *detached(Data *d, size_t size) + { + if (!d) + return new Data(size); + Data *dd = new Data(*d, size); + if (!d->ref.deref()) + delete d; + return dd; + } + + void clear() + { + delete[] spans; + spans = nullptr; + size = 0; + numBuckets = 0; + } + + iterator detachedIterator(iterator other) const noexcept + { + return iterator{this, other.bucket}; + } + + iterator begin() const noexcept + { + iterator it{ this, 0 }; + if (it.isUnused()) + ++it; + return it; + } + + constexpr iterator end() const noexcept + { + return iterator(); } - static inline int alignOfNode() { return qMax<int>(sizeof(void*), alignof(Node)); } + void rehash(size_t sizeHint = 0) + { + if (sizeHint == 0) + sizeHint = size; + size_t newBucketCount = GrowthPolicy::bucketsForCapacity(sizeHint); + + Span *oldSpans = spans; + size_t oldBucketCount = numBuckets; + spans = allocateSpans(newBucketCount).spans; + numBuckets = newBucketCount; + size_t oldNSpans = oldBucketCount >> SpanConstants::SpanShift; + + for (size_t s = 0; s < oldNSpans; ++s) { + Span &span = oldSpans[s]; + for (size_t index = 0; index < SpanConstants::NEntries; ++index) { + if (!span.hasNode(index)) + continue; + Node &n = span.at(index); + auto it = findBucket(n.key); + Q_ASSERT(it.isUnused()); + Node *newNode = it.insert(); + new (newNode) Node(std::move(n)); + } + span.freeData(); + } + delete[] oldSpans; + } + + size_t nextBucket(size_t bucket) const noexcept + { + ++bucket; + if (bucket == numBuckets) + bucket = 0; + return bucket; + } + + float loadFactor() const noexcept + { + return float(size)/numBuckets; + } + bool shouldGrow() const noexcept + { + return size >= (numBuckets >> 1); + } + + template <typename K> Bucket findBucket(const K &key) const noexcept + { + static_assert(std::is_same_v<std::remove_cv_t<Key>, K> || + QHashHeterogeneousSearch<std::remove_cv_t<Key>, K>::value); + Q_ASSERT(numBuckets > 0); + size_t hash = QHashPrivate::calculateHash(key, seed); + Bucket bucket(this, GrowthPolicy::bucketForHash(numBuckets, hash)); + // loop over the buckets until we find the entry we search for + // or an empty slot, in which case we know the entry doesn't exist + while (true) { + size_t offset = bucket.offset(); + if (offset == SpanConstants::UnusedEntry) { + return bucket; + } else { + Node &n = bucket.nodeAtOffset(offset); + if (qHashEquals(n.key, key)) + return bucket; + } + bucket.advanceWrapped(this); + } + } + + template <typename K> Node *findNode(const K &key) const noexcept + { + auto bucket = findBucket(key); + if (bucket.isUnused()) + return nullptr; + return bucket.node(); + } + + struct InsertionResult + { + iterator it; + bool initialized; + }; + + template <typename K> InsertionResult findOrInsert(const K &key) noexcept + { + Bucket it(static_cast<Span *>(nullptr), 0); + if (numBuckets > 0) { + it = findBucket(key); + if (!it.isUnused()) + return { it.toIterator(this), true }; + } + if (shouldGrow()) { + rehash(size + 1); + it = findBucket(key); // need to get a new iterator after rehashing + } + Q_ASSERT(it.span != nullptr); + Q_ASSERT(it.isUnused()); + it.insert(); + ++size; + return { it.toIterator(this), false }; + } + + void erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value) + { + Q_ASSERT(bucket.span->hasNode(bucket.index)); + bucket.span->erase(bucket.index); + --size; + + // re-insert the following entries to avoid holes + Bucket next = bucket; + while (true) { + next.advanceWrapped(this); + size_t offset = next.offset(); + if (offset == SpanConstants::UnusedEntry) + return; + size_t hash = QHashPrivate::calculateHash(next.nodeAtOffset(offset).key, seed); + Bucket newBucket(this, GrowthPolicy::bucketForHash(numBuckets, hash)); + while (true) { + if (newBucket == next) { + // nothing to do, item is at the right plae + break; + } else if (newBucket == bucket) { + // move into the hole we created earlier + if (next.span == bucket.span) { + bucket.span->moveLocal(next.index, bucket.index); + } else { + // move between spans, more expensive + bucket.span->moveFromSpan(*next.span, next.index, bucket.index); + } + bucket = next; + break; + } + newBucket.advanceWrapped(this); + } + } + } + + ~Data() + { + delete [] spans; + } +}; + +template <typename Node> +struct iterator { + using Span = QHashPrivate::Span<Node>; + + const Data<Node> *d = nullptr; + size_t bucket = 0; + + size_t span() const noexcept { return bucket >> SpanConstants::SpanShift; } + size_t index() const noexcept { return bucket & SpanConstants::LocalBucketMask; } + inline bool isUnused() const noexcept { return !d->spans[span()].hasNode(index()); } + + inline Node *node() const noexcept + { + Q_ASSERT(!isUnused()); + return &d->spans[span()].at(index()); + } + bool atEnd() const noexcept { return !d; } + + iterator operator++() noexcept + { + while (true) { + ++bucket; + if (bucket == d->numBuckets) { + d = nullptr; + bucket = 0; + break; + } + if (!isUnused()) + break; + } + return *this; + } + bool operator==(iterator other) const noexcept + { return d == other.d && bucket == other.bucket; } + bool operator!=(iterator other) const noexcept + { return !(*this == other); } +}; + + + +} // namespace QHashPrivate + +template <typename Key, typename T> +class QHash +{ + using Node = QHashPrivate::Node<Key, T>; + using Data = QHashPrivate::Data<Node>; + friend class QSet<Key>; + friend class QMultiHash<Key, T>; + friend tst_QHash; + + Data *d = nullptr; public: - inline QHash() noexcept : d(const_cast<QHashData *>(&QHashData::shared_null)) { } + using key_type = Key; + using mapped_type = T; + using value_type = T; + using size_type = qsizetype; + using difference_type = qsizetype; + using reference = T &; + using const_reference = const T &; + + inline QHash() noexcept = default; inline QHash(std::initializer_list<std::pair<Key,T> > list) - : d(const_cast<QHashData *>(&QHashData::shared_null)) + : d(new Data(list.size())) { - reserve(int(list.size())); for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) insert(it->first, it->second); } - QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); } - ~QHash() { if (!d->ref.deref()) freeData(d); } + QHash(const QHash &other) noexcept + : d(other.d) + { + if (d) + d->ref.ref(); + } + ~QHash() + { + static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers."); + static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + + if (d && !d->ref.deref()) + delete d; + } - QHash &operator=(const QHash &other); - QHash(QHash &&other) noexcept : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); } - QHash &operator=(QHash &&other) noexcept - { QHash moved(std::move(other)); swap(moved); return *this; } + QHash &operator=(const QHash &other) noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d != other.d) { + Data *o = other.d; + if (o) + o->ref.ref(); + if (d && !d->ref.deref()) + delete d; + d = o; + } + return *this; + } + + QHash(QHash &&other) noexcept + : d(std::exchange(other.d, nullptr)) + { + } + QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QHash) #ifdef Q_QDOC template <typename InputIterator> QHash(InputIterator f, InputIterator l); @@ -275,150 +897,287 @@ public: insert(f->first, f->second); } #endif - void swap(QHash &other) noexcept { qSwap(d, other.d); } + void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); } + +#ifndef Q_QDOC + template <typename AKey = Key, typename AT = T> + QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator==(const QHash &other) const noexcept + { + if (d == other.d) + return true; + if (size() != other.size()) + return false; + for (const_iterator it = other.begin(); it != other.end(); ++it) { + const_iterator i = find(it.key()); + if (i == end() || !i.i.node()->valuesEqual(it.i.node())) + return false; + } + // all values must be the same as size is the same + return true; + } + template <typename AKey = Key, typename AT = T> + QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator!=(const QHash &other) const noexcept + { return !(*this == other); } +#else bool operator==(const QHash &other) const; - bool operator!=(const QHash &other) const { return !(*this == other); } + bool operator!=(const QHash &other) const; +#endif // Q_QDOC + + inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; } + inline bool isEmpty() const noexcept { return !d || d->size == 0; } - inline int size() const { return d->size; } + inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; } + void reserve(qsizetype size) + { + // reserve(0) is used in squeeze() + if (size && (this->capacity() >= size)) + return; + if (isDetached()) + d->rehash(size); + else + d = Data::detached(d, size_t(size)); + } + inline void squeeze() + { + if (capacity()) + reserve(0); + } + + inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); } + inline bool isDetached() const noexcept { return d && !d->ref.isShared(); } + bool isSharedWith(const QHash &other) const noexcept { return d == other.d; } + + void clear() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d && !d->ref.deref()) + delete d; + d = nullptr; + } + + bool remove(const Key &key) + { + return removeImpl(key); + } +private: + template <typename K> bool removeImpl(const K &key) + { + if (isEmpty()) // prevents detaching shared null + return false; + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach - inline bool isEmpty() const { return d->size == 0; } + if (it.isUnused()) + return false; + d->erase(it); + return true; + } - inline int capacity() const { return d->numBuckets; } - void reserve(int size); - inline void squeeze() { reserve(1); } +public: + template <typename Predicate> + qsizetype removeIf(Predicate pred) + { + return QtPrivate::associative_erase_if(*this, pred); + } - inline void detach() { if (d->ref.isShared()) detach_helper(); } - inline bool isDetached() const { return !d->ref.isShared(); } - bool isSharedWith(const QHash &other) const { return d == other.d; } + T take(const Key &key) + { + return takeImpl(key); + } +private: + template <typename K> T takeImpl(const K &key) + { + if (isEmpty()) // prevents detaching shared null + return T(); + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach - void clear(); + if (it.isUnused()) + return T(); + T value = it.node()->takeValue(); + d->erase(it); + return value; + } - int remove(const Key &key); - T take(const Key &key); +public: + bool contains(const Key &key) const noexcept + { + if (!d) + return false; + return d->findNode(key) != nullptr; + } + qsizetype count(const Key &key) const noexcept + { + return contains(key) ? 1 : 0; + } - bool contains(const Key &key) const; - const Key key(const T &value) const; - const Key key(const T &value, const Key &defaultKey) const; - const T value(const Key &key) const; - const T value(const Key &key, const T &defaultValue) const; - T &operator[](const Key &key); - const T operator[](const Key &key) const; +private: + template <typename Fn> Key keyImpl(const T &value, Fn &&defaultFn) const noexcept + { + if (d) { + const_iterator i = begin(); + while (i != end()) { + if (i.value() == value) + return i.key(); + ++i; + } + } - QList<Key> uniqueKeys() const; - QList<Key> keys() const; - QList<Key> keys(const T &value) const; - QList<T> values() const; - QList<T> values(const Key &key) const; - int count(const Key &key) const; + return defaultFn(); + } + +public: + Key key(const T &value) const noexcept + { + return keyImpl(value, [] { return Key(); }); + } + Key key(const T &value, const Key &defaultKey) const noexcept + { + return keyImpl(value, [&] { return defaultKey; }); + } + +private: + template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept + { + if (d) { + Node *n = d->findNode(key); + if (n) + return n->value; + } + return defaultValue(); + } +public: + T value(const Key &key) const noexcept + { + return valueImpl(key, [] { return T(); }); + } + + T value(const Key &key, const T &defaultValue) const noexcept + { + return valueImpl(key, [&] { return defaultValue; }); + } + + T &operator[](const Key &key) + { + return operatorIndexImpl(key); + } +private: + template <typename K> T &operatorIndexImpl(const K &key) + { + const auto copy = isDetached() ? QHash() : *this; // keep 'key' alive across the detach + detach(); + auto result = d->findOrInsert(key); + Q_ASSERT(!result.it.atEnd()); + if (!result.initialized) + Node::createInPlace(result.it.node(), Key(key), T()); + return result.it.node()->value; + } + +public: + const T operator[](const Key &key) const noexcept + { + return value(key); + } + + QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); } + QList<Key> keys(const T &value) const + { + QList<Key> res; + const_iterator i = begin(); + while (i != end()) { + if (i.value() == value) + res.append(i.key()); + ++i; + } + return res; + } + QList<T> values() const { return QList<T>(begin(), end()); } class const_iterator; class iterator { + using piter = typename QHashPrivate::iterator<Node>; friend class const_iterator; friend class QHash<Key, T>; friend class QSet<Key>; - QHashData::Node *i; + piter i; + explicit inline iterator(piter it) noexcept : i(it) { } public: - typedef std::bidirectional_iterator_tag iterator_category; + typedef std::forward_iterator_tag iterator_category; typedef qptrdiff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; - inline iterator() : i(nullptr) { } - explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } + constexpr iterator() noexcept = default; - inline const Key &key() const { return concrete(i)->key; } - inline T &value() const { return concrete(i)->value; } - inline T &operator*() const { return concrete(i)->value; } - inline T *operator->() const { return &concrete(i)->value; } - inline bool operator==(const iterator &o) const { return i == o.i; } - inline bool operator!=(const iterator &o) const { return i != o.i; } + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return i.node()->value; } + inline T &operator*() const noexcept { return i.node()->value; } + inline T *operator->() const noexcept { return &i.node()->value; } + inline bool operator==(const iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const iterator &o) const noexcept { return i != o.i; } - inline iterator &operator++() { - i = QHashData::nextNode(i); - return *this; - } - inline iterator operator++(int) { - iterator r = *this; - i = QHashData::nextNode(i); - return r; - } - inline iterator &operator--() { - i = QHashData::previousNode(i); + inline iterator &operator++() noexcept + { + ++i; return *this; } - inline iterator operator--(int) { + inline iterator operator++(int) noexcept + { iterator r = *this; - i = QHashData::previousNode(i); + ++i; return r; } - inline iterator operator+(int j) const - { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline iterator operator-(int j) const { return operator+(-j); } - inline iterator &operator+=(int j) { return *this = *this + j; } - inline iterator &operator-=(int j) { return *this = *this - j; } - friend inline iterator operator+(int j, iterator k) { return k + j; } - - inline bool operator==(const const_iterator &o) const { return i == o.i; } - inline bool operator!=(const const_iterator &o) const { return i != o.i; } + + inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; } }; friend class iterator; class const_iterator { + using piter = typename QHashPrivate::iterator<Node>; friend class iterator; friend class QHash<Key, T>; friend class QSet<Key>; - QHashData::Node *i; + piter i; + explicit inline const_iterator(piter it) : i(it) { } public: - typedef std::bidirectional_iterator_tag iterator_category; + typedef std::forward_iterator_tag iterator_category; typedef qptrdiff difference_type; typedef T value_type; typedef const T *pointer; typedef const T &reference; - Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } - explicit inline const_iterator(void *node) - : i(reinterpret_cast<QHashData::Node *>(node)) { } - inline const_iterator(const iterator &o) - { i = o.i; } - - inline const Key &key() const { return concrete(i)->key; } - inline const T &value() const { return concrete(i)->value; } - inline const T &operator*() const { return concrete(i)->value; } - inline const T *operator->() const { return &concrete(i)->value; } - Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } - Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } - - inline const_iterator &operator++() { - i = QHashData::nextNode(i); - return *this; - } - inline const_iterator operator++(int) { - const_iterator r = *this; - i = QHashData::nextNode(i); - return r; - } - inline const_iterator &operator--() { - i = QHashData::previousNode(i); + constexpr const_iterator() noexcept = default; + inline const_iterator(const iterator &o) noexcept : i(o.i) { } + + inline const Key &key() const noexcept { return i.node()->key; } + inline const T &value() const noexcept { return i.node()->value; } + inline const T &operator*() const noexcept { return i.node()->value; } + inline const T *operator->() const noexcept { return &i.node()->value; } + inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; } + + inline const_iterator &operator++() noexcept + { + ++i; return *this; } - inline const_iterator operator--(int) { + inline const_iterator operator++(int) noexcept + { const_iterator r = *this; - i = QHashData::previousNode(i); + ++i; return r; } - inline const_iterator operator+(int j) const - { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline const_iterator operator-(int j) const { return operator+(-j); } - inline const_iterator &operator+=(int j) { return *this = *this + j; } - inline const_iterator &operator-=(int j) { return *this = *this - j; } - friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } }; friend class const_iterator; @@ -428,653 +1187,1024 @@ public: public: typedef typename const_iterator::iterator_category iterator_category; - typedef typename const_iterator::difference_type difference_type; + typedef qptrdiff difference_type; typedef Key value_type; typedef const Key *pointer; typedef const Key &reference; - key_iterator() = default; - explicit key_iterator(const_iterator o) : i(o) { } + key_iterator() noexcept = default; + explicit key_iterator(const_iterator o) noexcept : i(o) { } - const Key &operator*() const { return i.key(); } - const Key *operator->() const { return &i.key(); } - bool operator==(key_iterator o) const { return i == o.i; } - bool operator!=(key_iterator o) const { return i != o.i; } + const Key &operator*() const noexcept { return i.key(); } + const Key *operator->() const noexcept { return &i.key(); } + bool operator==(key_iterator o) const noexcept { return i == o.i; } + bool operator!=(key_iterator o) const noexcept { return i != o.i; } - inline key_iterator &operator++() { ++i; return *this; } - inline key_iterator operator++(int) { return key_iterator(i++);} - inline key_iterator &operator--() { --i; return *this; } - inline key_iterator operator--(int) { return key_iterator(i--); } - const_iterator base() const { return i; } + inline key_iterator &operator++() noexcept { ++i; return *this; } + inline key_iterator operator++(int) noexcept { return key_iterator(i++);} + const_iterator base() const noexcept { return i; } }; typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; // STL style - inline iterator begin() { detach(); return iterator(d->firstNode()); } - inline const_iterator begin() const { return const_iterator(d->firstNode()); } - inline const_iterator cbegin() const { return const_iterator(d->firstNode()); } - inline const_iterator constBegin() const { return const_iterator(d->firstNode()); } - inline iterator end() { detach(); return iterator(e); } - inline const_iterator end() const { return const_iterator(e); } - inline const_iterator cend() const { return const_iterator(e); } - inline const_iterator constEnd() const { return const_iterator(e); } - inline key_iterator keyBegin() const { return key_iterator(begin()); } - inline key_iterator keyEnd() const { return key_iterator(end()); } + inline iterator begin() { detach(); return iterator(d->begin()); } + inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline iterator end() noexcept { return iterator(); } + inline const_iterator end() const noexcept { return const_iterator(); } + inline const_iterator cend() const noexcept { return const_iterator(); } + inline const_iterator constEnd() const noexcept { return const_iterator(); } + inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); } + inline key_iterator keyEnd() const noexcept { return key_iterator(end()); } inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } - inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } - inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); } + inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); } + auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); } + auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); } + + iterator erase(const_iterator it) + { + Q_ASSERT(it != constEnd()); + detach(); + // ensure a valid iterator across the detach: + iterator i = iterator{d->detachedIterator(it.i)}; + typename Data::Bucket bucket(i.i); - QPair<iterator, iterator> equal_range(const Key &key); - QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept; - iterator erase(iterator it) { return erase(const_iterator(it.i)); } - iterator erase(const_iterator it); + d->erase(bucket); + if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused()) + ++i; + return i; + } - // more Qt + std::pair<iterator, iterator> equal_range(const Key &key) + { + return equal_range_impl(*this, key); + } + std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept + { + return equal_range_impl(*this, key); + } +private: + template <typename Hash, typename K> static auto equal_range_impl(Hash &self, const K &key) + { + auto first = self.find(key); + auto second = first; + if (second != decltype(first){}) + ++second; + return std::make_pair(first, second); + } + + template <typename K> iterator findImpl(const K &key) + { + if (isEmpty()) // prevents detaching shared null + return end(); + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach + if (it.isUnused()) + return end(); + return iterator(it.toIterator(d)); + } + template <typename K> const_iterator constFindImpl(const K &key) const noexcept + { + if (isEmpty()) + return end(); + auto it = d->findBucket(key); + if (it.isUnused()) + return end(); + return const_iterator({d, it.toBucketIndex(d)}); + } + +public: typedef iterator Iterator; typedef const_iterator ConstIterator; - inline int count() const { return d->size; } - iterator find(const Key &key); - const_iterator find(const Key &key) const; - const_iterator constFind(const Key &key) const; - iterator insert(const Key &key, const T &value); - iterator insertMulti(const Key &key, const T &value); - QHash &unite(const QHash &other); - - // STL compatibility - typedef T mapped_type; - typedef Key key_type; - typedef qptrdiff difference_type; - typedef int size_type; - - inline bool empty() const { return isEmpty(); } - -#ifdef QT_QHASH_DEBUG - inline void dump() const { d->dump(); } - inline void checkSanity() const { d->checkSanity(); } -#endif + inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; } + iterator find(const Key &key) + { + return findImpl(key); + } + const_iterator find(const Key &key) const noexcept + { + return constFindImpl(key); + } + const_iterator constFind(const Key &key) const noexcept + { + return find(key); + } + iterator insert(const Key &key, const T &value) + { + return emplace(key, value); + } -private: - void detach_helper(); - void freeData(QHashData *d); - Node **findNode(const Key &key, uint *hp = nullptr) const; - Node **findNode(const Key &key, uint h) const; - Node *createNode(uint h, const Key &key, const T &value, Node **nextNode); - void deleteNode(Node *node); - static void deleteNode2(QHashData::Node *node); - - static void duplicateNode(QHashData::Node *originalNode, void *newNode); - - bool isValidIterator(const iterator &it) const noexcept - { return isValidNode(it.i); } - bool isValidIterator(const const_iterator &it) const noexcept - { return isValidNode(it.i); } - bool isValidNode(QHashData::Node *node) const noexcept - { -#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG) - while (node->next) - node = node->next; - return (static_cast<void *>(node) == d); -#else - Q_UNUSED(node); - return true; -#endif + void insert(const QHash &hash) + { + if (d == hash.d || !hash.d) + return; + if (!d) { + *this = hash; + return; + } + + detach(); + + for (auto it = hash.begin(); it != hash.end(); ++it) + emplace(it.key(), it.value()); } - friend class QSet<Key>; -}; + template <typename ...Args> + iterator emplace(const Key &key, Args &&... args) + { + Key copy = key; // Needs to be explicit for MSVC 2019 + return emplace(std::move(copy), std::forward<Args>(args)...); + } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node) -{ - deleteNode2(reinterpret_cast<QHashData::Node*>(node)); - d->freeNode(node); -} + template <typename ...Args> + iterator emplace(Key &&key, Args &&... args) + { + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplace_helper(std::move(key), std::forward<Args>(args)...); + } + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth + detach(); + return emplace_helper(std::move(key), std::forward<Args>(args)...); + } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node) -{ -#ifdef Q_CC_BOR - concrete(node)->~QHashNode<Key, T>(); -#else - concrete(node)->~Node(); -#endif -} + float load_factor() const noexcept { return d ? d->loadFactor() : 0; } + static float max_load_factor() noexcept { return 0.5; } + size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; } + static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode) -{ - Node *concreteNode = concrete(node); - new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr); -} + inline bool empty() const noexcept { return isEmpty(); } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::Node * -QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode) -{ - Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode); - *anextNode = node; - ++d->size; - return node; -} +private: + template <typename ...Args> + iterator emplace_helper(Key &&key, Args &&... args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + else + result.it.node()->emplaceValue(std::forward<Args>(args)...); + return iterator(result.it); + } -template <class Key, class T> -Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) -{ - if (d == &QHashData::shared_null) { - *this = other; - } else { - QHash copy(other); - const_iterator it = copy.constEnd(); - while (it != copy.constBegin()) { - --it; - insertMulti(it.key(), it.value()); - } +public: +#ifdef __cpp_concepts + bool remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return removeImpl(key); } - return *this; -} + T take(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return takeImpl(key); + } + bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return d ? d->findNode(key) != nullptr : false; + } + qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return contains(key) ? 1 : 0; + } + T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return valueImpl(key, [] { return T(); }); + } + T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &defaultValue) const noexcept + { + return valueImpl(key, [&] { return defaultValue; }); + } + T &operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return operatorIndexImpl(key); + } + const T operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return value(key); + } + std::pair<iterator, iterator> + equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return equal_range_impl(*this, key); + } + std::pair<const_iterator, const_iterator> + equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return equal_range_impl(*this, key); + } + iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return findImpl(key); + } + const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return constFindImpl(key); + } + const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return find(key); + } +#endif // __cpp_concepts +}; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) -{ - x->free_helper(deleteNode2); -} -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::clear() +template <typename Key, typename T> +class QMultiHash { - *this = QHash(); -} + using Node = QHashPrivate::MultiNode<Key, T>; + using Data = QHashPrivate::Data<Node>; + using Chain = QHashPrivate::MultiNodeChain<T>; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper() -{ - QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode()); - if (!d->ref.deref()) - freeData(d); - d = x; -} + Data *d = nullptr; + qsizetype m_size = 0; -template <class Key, class T> -Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other) -{ - if (d != other.d) { - QHashData *o = other.d; - o->ref.ref(); - if (!d->ref.deref()) - freeData(d); - d = o; - if (!d->sharable) - detach_helper(); +public: + using key_type = Key; + using mapped_type = T; + using value_type = T; + using size_type = qsizetype; + using difference_type = qsizetype; + using reference = T &; + using const_reference = const T &; + + QMultiHash() noexcept = default; + inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) + : d(new Data(list.size())) + { + for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) + insert(it->first, it->second); + } +#ifdef Q_QDOC + template <typename InputIterator> + QMultiHash(InputIterator f, InputIterator l); +#else + template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true> + QMultiHash(InputIterator f, InputIterator l) + { + QtPrivate::reserveIfForwardIterator(this, f, l); + for (; f != l; ++f) + insert(f.key(), f.value()); } - return *this; -} -template <class Key, class T> -Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const -{ - Node *node; - if (d->size == 0 || (node = *findNode(akey)) == e) { - return T(); - } else { - return node->value; + template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true> + QMultiHash(InputIterator f, InputIterator l) + { + QtPrivate::reserveIfForwardIterator(this, f, l); + for (; f != l; ++f) + insert(f->first, f->second); } -} +#endif + QMultiHash(const QMultiHash &other) noexcept + : d(other.d), m_size(other.m_size) + { + if (d) + d->ref.ref(); + } + ~QMultiHash() + { + static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers."); + static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); -template <class Key, class T> -Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const -{ - Node *node; - if (d->size == 0 || (node = *findNode(akey)) == e) { - return adefaultValue; - } else { - return node->value; + if (d && !d->ref.deref()) + delete d; } -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - const_iterator i = begin(); - if (i != end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == end()) - goto break_out_of_outer_loop; - } while (aKey == i.key()); + QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d != other.d) { + Data *o = other.d; + if (o) + o->ref.ref(); + if (d && !d->ref.deref()) + delete d; + d = o; + m_size = other.m_size; } + return *this; + } + QMultiHash(QMultiHash &&other) noexcept + : d(std::exchange(other.d, nullptr)), + m_size(std::exchange(other.m_size, 0)) + { + } + QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value) + { + QMultiHash moved(std::move(other)); + swap(moved); + return *this; } -break_out_of_outer_loop: - return res; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const -{ - QList<Key> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.key()); - ++i; - } - return res; -} + explicit QMultiHash(const QHash<Key, T> &other) + : QMultiHash(other.begin(), other.end()) + {} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const -{ - QList<Key> res; - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - res.append(i.key()); - ++i; - } - return res; -} + explicit QMultiHash(QHash<Key, T> &&other) + { + unite(std::move(other)); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const -{ - return key(avalue, Key()); -} + void swap(QMultiHash &other) noexcept + { + qt_ptr_swap(d, other.d); + std::swap(m_size, other.m_size); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const -{ - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - return i.key(); - ++i; +#ifndef Q_QDOC + template <typename AKey = Key, typename AT = T> + QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator==(const QMultiHash &other) const noexcept + { + if (d == other.d) + return true; + if (m_size != other.m_size) + return false; + if (m_size == 0) + return true; + // equal size, and both non-zero size => d pointers allocated for both + Q_ASSERT(d); + Q_ASSERT(other.d); + if (d->size != other.d->size) + return false; + for (auto it = other.d->begin(); it != other.d->end(); ++it) { + auto *n = d->findNode(it.node()->key); + if (!n) + return false; + Chain *e = it.node()->value; + while (e) { + Chain *oe = n->value; + while (oe) { + if (oe->value == e->value) + break; + oe = oe->next; + } + if (!oe) + return false; + e = e->next; + } + } + // all values must be the same as size is the same + return true; } + template <typename AKey = Key, typename AT = T> + QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator!=(const QMultiHash &other) const noexcept + { return !(*this == other); } +#else + bool operator==(const QMultiHash &other) const; + bool operator!=(const QMultiHash &other) const; +#endif // Q_QDOC - return defaultValue; -} + inline qsizetype size() const noexcept { return m_size; } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const -{ - QList<T> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.value()); - ++i; - } - return res; -} + inline bool isEmpty() const noexcept { return !m_size; } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *node = *findNode(akey); - if (node != e) { - do { - res.append(node->value); - } while ((node = node->next) != e && node->key == akey); - } - return res; -} + inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; } + void reserve(qsizetype size) + { + // reserve(0) is used in squeeze() + if (size && (this->capacity() >= size)) + return; + if (isDetached()) + d->rehash(size); + else + d = Data::detached(d, size_t(size)); + } + inline void squeeze() { reserve(0); } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const -{ - int cnt = 0; - Node *node = *findNode(akey); - if (node != e) { - do { - ++cnt; - } while ((node = node->next) != e && node->key == akey); - } - return cnt; -} + inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); } + inline bool isDetached() const noexcept { return d && !d->ref.isShared(); } + bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; } -template <class Key, class T> -Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const -{ - return value(akey); -} + void clear() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d && !d->ref.deref()) + delete d; + d = nullptr; + m_size = 0; + } -template <class Key, class T> -Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey) -{ - detach(); + qsizetype remove(const Key &key) + { + return removeImpl(key); + } +private: + template <typename K> qsizetype removeImpl(const K &key) + { + if (isEmpty()) // prevents detaching shared null + return 0; + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach + + if (it.isUnused()) + return 0; + qsizetype n = Node::freeChain(it.node()); + m_size -= n; + Q_ASSERT(m_size >= 0); + d->erase(it); + return n; + } - uint h; - Node **node = findNode(akey, &h); - if (*node == e) { - if (d->willGrow()) - node = findNode(akey, h); - return createNode(h, akey, T(), node)->value; +public: + template <typename Predicate> + qsizetype removeIf(Predicate pred) + { + return QtPrivate::associative_erase_if(*this, pred); } - return (*node)->value; -} -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey, - const T &avalue) -{ - detach(); + T take(const Key &key) + { + return takeImpl(key); + } +private: + template <typename K> T takeImpl(const K &key) + { + if (isEmpty()) // prevents detaching shared null + return T(); + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach + + if (it.isUnused()) + return T(); + Chain *e = it.node()->value; + Q_ASSERT(e); + T t = std::move(e->value); + if (e->next) { + it.node()->value = e->next; + delete e; + } else { + // erase() deletes the values. + d->erase(it); + } + --m_size; + Q_ASSERT(m_size >= 0); + return t; + } - uint h; - Node **node = findNode(akey, &h); - if (*node == e) { - if (d->willGrow()) - node = findNode(akey, h); - return iterator(createNode(h, akey, avalue, node)); +public: + bool contains(const Key &key) const noexcept + { + if (!d) + return false; + return d->findNode(key) != nullptr; } - if (!std::is_same<T, QHashDummyValue>::value) - (*node)->value = avalue; - return iterator(*node); -} +private: + template <typename Fn> Key keyImpl(const T &value, Fn &&defaultValue) const noexcept + { + if (d) { + auto i = d->begin(); + while (i != d->end()) { + Chain *e = i.node()->value; + if (e->contains(value)) + return i.node()->key; + ++i; + } + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey, - const T &avalue) -{ - detach(); - d->willGrow(); + return defaultValue(); + } +public: + Key key(const T &value) const noexcept + { + return keyImpl(value, [] { return Key(); }); + } + Key key(const T &value, const Key &defaultKey) const noexcept + { + return keyImpl(value, [&] { return defaultKey; }); + } - uint h; - Node **nextNode = findNode(akey, &h); - return iterator(createNode(h, akey, avalue, nextNode)); -} +private: + template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept + { + if (d) { + Node *n = d->findNode(key); + if (n) { + Q_ASSERT(n->value); + return n->value->value; + } + } + return defaultValue(); + } +public: + T value(const Key &key) const noexcept + { + return valueImpl(key, [] { return T(); }); + } + T value(const Key &key, const T &defaultValue) const noexcept + { + return valueImpl(key, [&] { return defaultValue; }); + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey) -{ - if (isEmpty()) // prevents detaching shared null - return 0; - detach(); - - int oldSize = d->size; - Node **node = findNode(akey); - if (*node != e) { - bool deleteNext = true; - do { - Node *next = (*node)->next; - deleteNext = (next != e && next->key == (*node)->key); - deleteNode(*node); - *node = next; - --d->size; - } while (deleteNext); - d->hasShrunk(); - } - return oldSize - d->size; -} + T &operator[](const Key &key) + { + return operatorIndexImpl(key); + } +private: + template <typename K> T &operatorIndexImpl(const K &key) + { + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach + detach(); + auto result = d->findOrInsert(key); + Q_ASSERT(!result.it.atEnd()); + if (!result.initialized) { + Node::createInPlace(result.it.node(), Key(key), T()); + ++m_size; + } + return result.it.node()->value->value; + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey) -{ - if (isEmpty()) // prevents detaching shared null - return T(); - detach(); - - Node **node = findNode(akey); - if (*node != e) { - T t = std::move((*node)->value); - Node *next = (*node)->next; - deleteNode(*node); - *node = next; - --d->size; - d->hasShrunk(); - return t; +public: + const T operator[](const Key &key) const noexcept + { + return value(key); } - return T(); -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it) -{ - Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid"); - - if (it == const_iterator(e)) - return iterator(it.i); - - if (d->ref.isShared()) { - // save 'it' across the detach: - int bucketNum = (it.i->h % d->numBuckets); - const_iterator bucketIterator(*(d->buckets + bucketNum)); - int stepsFromBucketStartToIte = 0; - while (bucketIterator != it) { - ++stepsFromBucketStartToIte; - ++bucketIterator; + QList<Key> uniqueKeys() const + { + QList<Key> res; + if (d) { + auto i = d->begin(); + while (i != d->end()) { + res.append(i.node()->key); + ++i; + } } - detach(); - it = const_iterator(*(d->buckets + bucketNum)); - while (stepsFromBucketStartToIte > 0) { - --stepsFromBucketStartToIte; - ++it; + return res; + } + + QList<Key> keys() const { return QList<Key>(keyBegin(), keyEnd()); } + QList<Key> keys(const T &value) const + { + QList<Key> res; + const_iterator i = begin(); + while (i != end()) { + if (i.value() == value) + res.append(i.key()); + ++i; } + return res; } - iterator ret(it.i); - ++ret; + QList<T> values() const { return QList<T>(begin(), end()); } + QList<T> values(const Key &key) const + { + return valuesImpl(key); + } +private: + template <typename K> QList<T> valuesImpl(const K &key) const + { + QList<T> values; + if (d) { + Node *n = d->findNode(key); + if (n) { + Chain *e = n->value; + while (e) { + values.append(e->value); + e = e->next; + } + } + } + return values; + } - Node *node = concrete(it.i); - Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]); - while (*node_ptr != node) - node_ptr = &(*node_ptr)->next; - *node_ptr = node->next; - deleteNode(node); - --d->size; - return ret; -} +public: + class const_iterator; -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize) -{ - detach(); - d->rehash(-qMax(asize, 1)); -} + class iterator + { + using piter = typename QHashPrivate::iterator<Node>; + friend class const_iterator; + friend class QMultiHash<Key, T>; + piter i; + Chain **e = nullptr; + explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry) + { + if (!it.atEnd() && !e) { + e = &it.node()->value; + Q_ASSERT(e && *e); + } + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const -{ - return const_iterator(*findNode(akey)); -} + public: + typedef std::forward_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef T *pointer; + typedef T &reference; -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const -{ - return const_iterator(*findNode(akey)); -} + constexpr iterator() noexcept = default; + + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return (*e)->value; } + inline T &operator*() const noexcept { return (*e)->value; } + inline T *operator->() const noexcept { return &(*e)->value; } + inline bool operator==(const iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const iterator &o) const noexcept { return e != o.e; } + + inline iterator &operator++() noexcept { + Q_ASSERT(e && *e); + e = &(*e)->next; + Q_ASSERT(e); + if (!*e) { + ++i; + e = i.atEnd() ? nullptr : &i.node()->value; + } + return *this; + } + inline iterator operator++(int) noexcept { + iterator r = *this; + ++(*this); + return r; + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey) -{ - detach(); - return iterator(*findNode(akey)); -} + inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; } + }; + friend class iterator; -template <class Key, class T> -Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const -{ - return *findNode(akey) != e; -} + class const_iterator + { + using piter = typename QHashPrivate::iterator<Node>; + friend class iterator; + friend class QMultiHash<Key, T>; + piter i; + Chain **e = nullptr; + explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry) + { + if (!it.atEnd() && !e) { + e = &it.node()->value; + Q_ASSERT(e && *e); + } + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const -{ - Node **node; + public: + typedef std::forward_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef const T *pointer; + typedef const T &reference; - if (d->numBuckets) { - node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]); - Q_ASSERT(*node == e || (*node)->next); - while (*node != e && !(*node)->same_key(h, akey)) - node = &(*node)->next; - } else { - node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e)); - } - return node; -} + constexpr const_iterator() noexcept = default; + inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { } + + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return (*e)->value; } + inline T &operator*() const noexcept { return (*e)->value; } + inline T *operator->() const noexcept { return &(*e)->value; } + inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; } + + inline const_iterator &operator++() noexcept { + Q_ASSERT(e && *e); + e = &(*e)->next; + Q_ASSERT(e); + if (!*e) { + ++i; + e = i.atEnd() ? nullptr : &i.node()->value; + } + return *this; + } + inline const_iterator operator++(int) noexcept + { + const_iterator r = *this; + ++(*this); + return r; + } + }; + friend class const_iterator; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, - uint *ahp) const -{ - uint h = 0; + class key_iterator + { + const_iterator i; - if (d->numBuckets || ahp) { - h = qHash(akey, d->seed); - if (ahp) - *ahp = h; - } - return findNode(akey, h); -} + public: + typedef typename const_iterator::iterator_category iterator_category; + typedef qptrdiff difference_type; + typedef Key value_type; + typedef const Key *pointer; + typedef const Key &reference; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const -{ - if (d == other.d) - return true; - if (size() != other.size()) - return false; + key_iterator() noexcept = default; + explicit key_iterator(const_iterator o) noexcept : i(o) { } - const_iterator it = begin(); + const Key &operator*() const noexcept { return i.key(); } + const Key *operator->() const noexcept { return &i.key(); } + bool operator==(key_iterator o) const noexcept { return i == o.i; } + bool operator!=(key_iterator o) const noexcept { return i != o.i; } - while (it != end()) { - // Build two equal ranges for i.key(); one for *this and one for other. - // For *this we can avoid a lookup via equal_range, as we know the beginning of the range. - auto thisEqualRangeStart = it; - const Key &thisEqualRangeKey = it.key(); - size_type n = 0; - do { - ++it; - ++n; - } while (it != end() && it.key() == thisEqualRangeKey); + inline key_iterator &operator++() noexcept { ++i; return *this; } + inline key_iterator operator++(int) noexcept { return key_iterator(i++);} + const_iterator base() const noexcept { return i; } + }; - const auto otherEqualRange = other.equal_range(thisEqualRangeKey); + typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; + typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; - if (n != std::distance(otherEqualRange.first, otherEqualRange.second)) - return false; + // STL style + inline iterator begin() { detach(); return iterator(d->begin()); } + inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline iterator end() noexcept { return iterator(); } + inline const_iterator end() const noexcept { return const_iterator(); } + inline const_iterator cend() const noexcept { return const_iterator(); } + inline const_iterator constEnd() const noexcept { return const_iterator(); } + inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); } + inline key_iterator keyEnd() const noexcept { return key_iterator(end()); } + inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); } + inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); } + inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + inline const_key_value_iterator constKeyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + inline const_key_value_iterator keyValueEnd() const noexcept { return const_key_value_iterator(end()); } + inline const_key_value_iterator constKeyValueEnd() const noexcept { return const_key_value_iterator(end()); } + auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); } + auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); } + auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); } + + iterator detach(const_iterator it) + { + auto i = it.i; + Chain **e = it.e; + if (d->ref.isShared()) { + // need to store iterator position before detaching + qsizetype n = 0; + Chain *entry = i.node()->value; + while (entry != *it.e) { + ++n; + entry = entry->next; + } + Q_ASSERT(entry); + detach_helper(); - // Keys in the ranges are equal by construction; this checks only the values. - if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second)) - return false; + i = d->detachedIterator(i); + e = &i.node()->value; + while (n) { + e = &(*e)->next; + --n; + } + Q_ASSERT(e && *e); + } + return iterator(i, e); } - return true; -} - -template <class Key, class T> -QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey) -{ - detach(); - auto pair = qAsConst(*this).equal_range(akey); - return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); -} + iterator erase(const_iterator it) + { + Q_ASSERT(d); + iterator iter = detach(it); + iterator i = iter; + Chain *e = *i.e; + Chain *next = e->next; + *i.e = next; + delete e; + if (!next) { + if (i.e == &i.i.node()->value) { + // last remaining entry, erase + typename Data::Bucket bucket(i.i); + d->erase(bucket); + if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused()) + i = iterator(++iter.i); + else // 'i' currently has a nullptr chain. So, we must recreate it + i = iterator(bucket.toIterator(d)); + } else { + i = iterator(++iter.i); + } + } + --m_size; + Q_ASSERT(m_size >= 0); + return i; + } -template <class Key, class T> -QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept -{ - Node *node = *findNode(akey); - const_iterator firstIt = const_iterator(node); + // more Qt + typedef iterator Iterator; + typedef const_iterator ConstIterator; + inline qsizetype count() const noexcept { return size(); } - if (node != e) { - // equal keys must hash to the same value and so they all - // end up in the same bucket. So we can use node->next, - // which only works within a bucket, instead of (out-of-line) - // QHashData::nextNode() - while (node->next != e && node->next->key == akey) - node = node->next; +private: + template <typename K> iterator findImpl(const K &key) + { + if (isEmpty()) + return end(); + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach - // 'node' may be the last node in the bucket. To produce the end iterator, we'd - // need to enter the next bucket in this case, so we need to use - // QHashData::nextNode() here, which, unlike node->next above, can move between - // buckets. - node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node))); + if (it.isUnused()) + return end(); + return iterator(it.toIterator(d)); + } + template <typename K> const_iterator constFindImpl(const K &key) const noexcept + { + if (isEmpty()) + return end(); + auto it = d->findBucket(key); + if (it.isUnused()) + return constEnd(); + return const_iterator(it.toIterator(d)); } - - return qMakePair(firstIt, const_iterator(node)); -} - -template <class Key, class T> -class QMultiHash : public QHash<Key, T> -{ public: - QMultiHash() noexcept {} - inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) + iterator find(const Key &key) { - this->reserve(int(list.size())); - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); + return findImpl(key); } -#ifdef Q_QDOC - template <typename InputIterator> - QMultiHash(InputIterator f, InputIterator l); -#else - template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true> - QMultiHash(InputIterator f, InputIterator l) + const_iterator constFind(const Key &key) const noexcept { - QtPrivate::reserveIfForwardIterator(this, f, l); - for (; f != l; ++f) - insert(f.key(), f.value()); + return constFindImpl(key); + } + const_iterator find(const Key &key) const noexcept + { + return constFindImpl(key); } - template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true> - QMultiHash(InputIterator f, InputIterator l) + iterator insert(const Key &key, const T &value) { - QtPrivate::reserveIfForwardIterator(this, f, l); - for (; f != l; ++f) - insert(f->first, f->second); + return emplace(key, value); + } + + template <typename ...Args> + iterator emplace(const Key &key, Args &&... args) + { + return emplace(Key(key), std::forward<Args>(args)...); + } + + template <typename ...Args> + iterator emplace(Key &&key, Args &&... args) + { + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplace_helper(std::move(key), std::forward<Args>(args)...); + } + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth + detach(); + return emplace_helper(std::move(key), std::forward<Args>(args)...); } -#endif - // compiler-generated copy/move ctors/assignment operators are fine! - // compiler-generated destructor is fine! - QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {} - QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {} - void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps - inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) - { return QHash<Key, T>::insert(key, value); } + float load_factor() const noexcept { return d ? d->loadFactor() : 0; } + static float max_load_factor() noexcept { return 0.5; } + size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; } + static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); } + + inline bool empty() const noexcept { return isEmpty(); } + + inline iterator replace(const Key &key, const T &value) + { + return emplaceReplace(key, value); + } + + template <typename ...Args> + iterator emplaceReplace(const Key &key, Args &&... args) + { + return emplaceReplace(Key(key), std::forward<Args>(args)...); + } - inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value) - { return QHash<Key, T>::insertMulti(key, value); } + template <typename ...Args> + iterator emplaceReplace(Key &&key, Args &&... args) + { + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplaceReplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...); + } + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth + detach(); + return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...); + } inline QMultiHash &operator+=(const QMultiHash &other) { this->unite(other); return *this; } inline QMultiHash operator+(const QMultiHash &other) const { QMultiHash result = *this; result += other; return result; } - using QHash<Key, T>::contains; - using QHash<Key, T>::remove; - using QHash<Key, T>::count; - using QHash<Key, T>::find; - using QHash<Key, T>::constFind; + bool contains(const Key &key, const T &value) const noexcept + { + return containsImpl(key, value); + } +private: + template <typename K> bool containsImpl(const K &key, const T &value) const noexcept + { + if (isEmpty()) + return false; + auto n = d->findNode(key); + if (n == nullptr) + return false; + return n->value->contains(value); + } - bool contains(const Key &key, const T &value) const; +public: + qsizetype remove(const Key &key, const T &value) + { + return removeImpl(key, value); + } +private: + template <typename K> qsizetype removeImpl(const K &key, const T &value) + { + if (isEmpty()) // prevents detaching shared null + return 0; + auto it = d->findBucket(key); + size_t bucket = it.toBucketIndex(d); + detach(); + it = typename Data::Bucket(d, bucket); // reattach in case of detach + + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain **e = &it.node()->value; + while (*e) { + Chain *entry = *e; + if (entry->value == value) { + *e = entry->next; + delete entry; + ++n; + } else { + e = &entry->next; + } + } + if (!it.node()->value) + d->erase(it); + m_size -= n; + Q_ASSERT(m_size >= 0); + return n; + } - int remove(const Key &key, const T &value); +public: + qsizetype count(const Key &key) const noexcept + { + return countImpl(key); + } +private: + template <typename K> qsizetype countImpl(const K &key) const noexcept + { + if (!d) + return 0; + auto it = d->findBucket(key); + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain *e = it.node()->value; + while (e) { + ++n; + e = e->next; + } - int count(const Key &key, const T &value) const; + return n; + } - typename QHash<Key, T>::iterator find(const Key &key, const T &value) { - typename QHash<Key, T>::iterator i(find(key)); - typename QHash<Key, T>::iterator end(this->end()); - while (i != end && i.key() == key) { - if (i.value() == value) - return i; - ++i; +public: + qsizetype count(const Key &key, const T &value) const noexcept + { + return countImpl(key, value); + } +private: + template <typename K> qsizetype countImpl(const K &key, const T &value) const noexcept + { + if (!d) + return 0; + auto it = d->findBucket(key); + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain *e = it.node()->value; + while (e) { + if (e->value == value) + ++n; + e = e->next; } - return end; + + return n; } - typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const { - typename QHash<Key, T>::const_iterator i(constFind(key)); - typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); + + template <typename K> iterator findImpl(const K &key, const T &value) + { + if (isEmpty()) + return end(); + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key'/'value' alive across the detach + detach(); + auto it = constFind(key, value); + return iterator(it.i, it.e); + } + template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept + { + const_iterator i(constFind(key)); + const_iterator end(constEnd()); while (i != end && i.key() == key) { if (i.value() == value) return i; @@ -1082,78 +2212,261 @@ public: } return end; } - typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const - { return find(key, value); } + +public: + iterator find(const Key &key, const T &value) + { + return findImpl(key, value); + } + + const_iterator constFind(const Key &key, const T &value) const noexcept + { + return constFindImpl(key, value); + } + const_iterator find(const Key &key, const T &value) const noexcept + { + return constFind(key, value); + } + + QMultiHash &unite(const QMultiHash &other) + { + if (isEmpty()) { + *this = other; + } else if (other.isEmpty()) { + ; + } else { + QMultiHash copy(other); + detach(); + for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit) + insert(cit.key(), *cit); + } + return *this; + } + + QMultiHash &unite(const QHash<Key, T> &other) + { + for (auto cit = other.cbegin(); cit != other.cend(); ++cit) + insert(cit.key(), *cit); + return *this; + } + + QMultiHash &unite(QHash<Key, T> &&other) + { + if (!other.isDetached()) { + unite(other); + return *this; + } + auto it = other.d->begin(); + for (const auto end = other.d->end(); it != end; ++it) + emplace(std::move(it.node()->key), std::move(it.node()->takeValue())); + other.clear(); + return *this; + } + + std::pair<iterator, iterator> equal_range(const Key &key) + { + return equal_range_impl(key); + } private: - T &operator[](const Key &key); - const T operator[](const Key &key) const; -}; + template <typename K> std::pair<iterator, iterator> equal_range_impl(const K &key) + { + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach + detach(); + auto pair = std::as_const(*this).equal_range(key); + return {iterator(pair.first.i), iterator(pair.second.i)}; + } -template <class Key, class T> -Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const -{ - return constFind(key, value) != QHash<Key, T>::constEnd(); -} +public: + std::pair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept + { + return equal_range_impl(key); + } +private: + template <typename K> std::pair<const_iterator, const_iterator> equal_range_impl(const K &key) const noexcept + { + if (!d) + return {end(), end()}; + + auto bucket = d->findBucket(key); + if (bucket.isUnused()) + return {end(), end()}; + auto it = bucket.toIterator(d); + auto end = it; + ++end; + return {const_iterator(it), const_iterator(end)}; + } -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value) -{ - int n = 0; - typename QHash<Key, T>::iterator i(find(key)); - typename QHash<Key, T>::iterator end(QHash<Key, T>::end()); - while (i != end && i.key() == key) { - if (i.value() == value) { - i = this->erase(i); - ++n; + void detach_helper() + { + if (!d) { + d = new Data; + return; + } + Data *dd = new Data(*d); + if (!d->ref.deref()) + delete d; + d = dd; + } + + template<typename... Args> + iterator emplace_helper(Key &&key, Args &&...args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + else + result.it.node()->insertMulti(std::forward<Args>(args)...); + ++m_size; + return iterator(result.it); + } + + template<typename... Args> + iterator emplaceReplace_helper(Key &&key, Args &&...args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) { + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + ++m_size; } else { - ++i; + result.it.node()->emplaceValue(std::forward<Args>(args)...); } + return iterator(result.it); } - return n; -} -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const -{ - int n = 0; - typename QHash<Key, T>::const_iterator i(constFind(key)); - typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); - while (i != end && i.key() == key) { - if (i.value() == value) - ++n; - ++i; +public: +#ifdef __cpp_concepts + qsizetype remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return removeImpl(key); } - return n; -} + T take(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return takeImpl(key); + } + bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + if (!d) + return false; + return d->findNode(key) != nullptr; + } + T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return valueImpl(key, [] { return T(); }); + } + T value(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &defaultValue) const noexcept + { + return valueImpl(key, [&] { return defaultValue; }); + } + T &operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return operatorIndexImpl(key); + } + const T operator[](const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return value(key); + } + QList<T> values(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return valuesImpl(key); + } + iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return findImpl(key); + } + const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return constFindImpl(key); + } + const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return constFindImpl(key); + } + bool contains(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept + { + return containsImpl(key, value); + } + qsizetype remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) + { + return removeImpl(key, value); + } + qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return countImpl(key); + } + qsizetype count(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept + { + return countImpl(key, value); + } + iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) + { + return findImpl(key, value); + } + const_iterator constFind(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept + { + return constFindImpl(key, value); + } + const_iterator find(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key, const T &value) const noexcept + { + return constFind(key, value); + } + std::pair<iterator, iterator> + equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) + { + return equal_range_impl(key); + } + std::pair<const_iterator, const_iterator> + equal_range(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key) const noexcept + { + return equal_range_impl(key); + } +#endif // __cpp_concepts +}; -Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash) -Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash) +Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash) +Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(Hash) +Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash) +Q_DECLARE_MUTABLE_ASSOCIATIVE_FORWARD_ITERATOR(MultiHash) template <class Key, class T> -uint qHash(const QHash<Key, T> &key, uint seed = 0) +size_t qHash(const QHash<Key, T> &key, size_t seed = 0) noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>()))) { - QtPrivate::QHashCombineCommutative hash; + size_t hash = 0; for (auto it = key.begin(), end = key.end(); it != end; ++it) { - const Key &k = it.key(); - const T &v = it.value(); - seed = hash(seed, std::pair<const Key&, const T&>(k, v)); + QtPrivate::QHashCombine combine; + size_t h = combine(seed, it.key()); + // use + to keep the result independent of the ordering of the keys + hash += combine(h, it.value()); } - return seed; + return hash; } template <class Key, class T> -inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0) +inline size_t qHash(const QMultiHash<Key, T> &key, size_t seed = 0) noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>()))) { - const QHash<Key, T> &key2 = key; - return qHash(key2, seed); + size_t hash = 0; + for (auto it = key.begin(), end = key.end(); it != end; ++it) { + QtPrivate::QHashCombine combine; + size_t h = combine(seed, it.key()); + // use + to keep the result independent of the ordering of the keys + hash += combine(h, it.value()); + } + return hash; } -QT_END_NAMESPACE +template <typename Key, typename T, typename Predicate> +qsizetype erase_if(QHash<Key, T> &hash, Predicate pred) +{ + return QtPrivate::associative_erase_if(hash, pred); +} -#if defined(Q_CC_MSVC) -#pragma warning( pop ) -#endif +template <typename Key, typename T, typename Predicate> +qsizetype erase_if(QMultiHash<Key, T> &hash, Predicate pred) +{ + return QtPrivate::associative_erase_if(hash, pred); +} + +QT_END_NAMESPACE #endif // QHASH_H |