Revision control
++ // 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
++ // Qt-Security score:significant reason:default
++
++ #ifndef QHASH_H
++ #define QHASH_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/qscopeguard.h>
++ #include <QtCore/qttypetraits.h>
++
++ #include <initializer_list>
++ #include <functional> // for std::hash
++ #include <QtCore/q20type_traits.h>
++
++ class tst_QHash; // for befriending
++
++ QT_BEGIN_NAMESPACE
++
++ struct QHashDummyValue
++ {
++ explicit QHashDummyValue() = default;
++ friend constexpr bool operator==(QHashDummyValue, QHashDummyValue) noexcept { return true; }
++ #ifndef __cpp_impl_three_way_comparison
++ friend constexpr bool operator!=(QHashDummyValue, QHashDummyValue) noexcept { return false; }
++ #endif
++ friend constexpr size_t qHash(QHashDummyValue) noexcept = delete;
++ friend constexpr size_t qHash(QHashDummyValue, size_t) noexcept = delete;
++ };
++
++ namespace QHashPrivate {
++
++ 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;
++
++ 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 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 {
++ static_assert(QtPrivate::type_dependent_false<T>(), "The key type must have a qHash overload or a std::hash specialization");
++ return 0;
++ }
++ }
++
++ template <typename Key, typename T>
++ struct Node
++ {
++ 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
++ {
++ return std::move(value);
++ }
++ bool valuesEqual(const Node *other) const { return value == other->value; }
++ };
++
++ 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 &&...)
++ {
++ }
++ ValueType takeValue() noexcept { return QHashDummyValue(); }
++ bool valuesEqual(const Node *) const { return true; }
++ };
++
++ 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;
++ }
++ };
++
++ template <typename Key, typename T>
++ struct MultiNode
++ {
++ 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(std::move(other.key)),
++ value(std::exchange(other.value, nullptr))
++ {
++ }
++
++ 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<typename Node>
++ inline constexpr bool isRelocatable_v =
++ QTypeInfo<typename Node::KeyType>::isRelocatable &&
++ QTypeInfo<typename Node::ValueType>::isRelocatable;
++
++ 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;
++
++ static_assert ((NEntries & LocalBucketMask) == 0, "NEntries must be a power of two.");
++ };
++
++ // 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); }
++ };
++
++ 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;
++
++ 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_v<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_v<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
++
++ template <typename Node>
++ struct iterator;
++
++ template <typename Node>
++ struct Data
++ {
++ 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);
++ }
++
++ 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 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();
++ }
++
++ // The Resized parameter is a template param to make sure the compiler will get rid of the
++ // branch, for performance.
++ template <bool Resized>
++ Q_ALWAYS_INLINE
++ void reallocationHelper(const Data &other, size_t nSpans)
++ {
++ 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<false>(other, r.nSpans);
++ }
++ 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<true>(other, otherNSpans);
++ }
++
++ 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();
++ }
++
++ 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
++ {
++ size_t hash = QHashPrivate::calculateHash(key, seed);
++ return findBucketWithHash(key, hash);
++ }
++
++ template <typename K> Bucket findBucketWithHash(const K &key, size_t hash) 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);
++ 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);
++ size_t hash = QHashPrivate::calculateHash(key, seed);
++ if (numBuckets > 0) {
++ it = findBucketWithHash(key, hash);
++ if (!it.isUnused())
++ return { it.toIterator(this), true };
++ }
++ if (shouldGrow()) {
++ rehash(size + 1);
++ it = findBucketWithHash(key, hash); // 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); }
++ };
++
++ template <typename HashKey, typename KeyArgument>
++ using HeterogenousConstructProxy = std::conditional_t<
++ std::is_same_v<HashKey, q20::remove_cvref_t<KeyArgument>>,
++ KeyArgument, // HashKey == KeyArg w/ potential modifiers, so we keep modifiers
++ HashKey
++ >;
++
++ } // 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:
++ 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(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);
++ }
++ 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) noexcept
++ {
++ 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);
++ #else
++ template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
++ QHash(InputIterator f, InputIterator l)
++ : QHash()
++ {
++ QtPrivate::reserveIfForwardIterator(this, f, l);
++ for (; f != l; ++f)
++ insert(f.key(), f.value());
++ }
++
++ template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
++ QHash(InputIterator f, InputIterator l)
++ : QHash()
++ {
++ QtPrivate::reserveIfForwardIterator(this, f, l);
++ for (; f != l; ++f) {
++ auto &&e = *f;
++ using V = decltype(e);
++ insert(std::forward<V>(e).first, std::forward<V>(e).second);
++ }
++ }
++ #endif
++ void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); }
++
++ class const_iterator;
++
++ #ifndef Q_QDOC
++ private:
++ static bool compareIterators(const const_iterator &lhs, const const_iterator &rhs)
++ {
++ return lhs.i.node()->valuesEqual(rhs.i.node());
++ }
++
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QHash, AKey, AT> = true>
++ friend bool comparesEqual(const QHash &lhs, const QHash &rhs) noexcept
++ {
++ if (lhs.d == rhs.d)
++ return true;
++ if (lhs.size() != rhs.size())
++ return false;
++
++ for (const_iterator it = rhs.begin(); it != rhs.end(); ++it) {
++ const_iterator i = lhs.find(it.key());
++ if (i == lhs.end() || !compareIterators(i, it))
++ return false;
++ }
++ // all values must be the same as size is the same
++ return true;
++ }
++ QT_DECLARE_EQUALITY_OPERATORS_HELPER(QHash, QHash, /* non-constexpr */, noexcept,
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QHash, AKey, AT> = true>)
++ public:
++ #else
++ friend bool operator==(const QHash &lhs, const QHash &rhs) noexcept;
++ friend bool operator!=(const QHash &lhs, const QHash &rhs) noexcept;
++ #endif // Q_QDOC
++
++ inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
++
++ [[nodiscard]]
++ inline bool isEmpty() const noexcept { return !d || d->size == 0; }
++
++ 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);
++ if (it.isUnused())
++ return false;
++
++ size_t bucket = it.toBucketIndex(d);
++ detach();
++ it = typename Data::Bucket(d, bucket); // reattach in case of detach
++
++ d->erase(it);
++ return true;
++ }
++
++ public:
++ template <typename Predicate>
++ qsizetype removeIf(Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(*this, pred);
++ }
++
++ 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();
++
++ const auto eraser = qScopeGuard([&] { d->erase(it); });
++ return it.node()->takeValue();
++ }
++
++ 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;
++ }
++
++ private:
++ const Key *keyImpl(const T &value) const noexcept
++ {
++ if (d) {
++ const_iterator i = begin();
++ while (i != end()) {
++ if (i.value() == value)
++ return &i.key();
++ ++i;
++ }
++ }
++
++ return nullptr;
++ }
++
++ public:
++ Key key(const T &value) const noexcept
++ {
++ if (auto *k = keyImpl(value))
++ return *k;
++ else
++ return Key();
++ }
++ Key key(const T &value, const Key &defaultKey) const noexcept
++ {
++ if (auto *k = keyImpl(value))
++ return *k;
++ else
++ return defaultKey;
++ }
++
++ private:
++ template <typename K>
++ T *valueImpl(const K &key) const noexcept
++ {
++ if (d) {
++ Node *n = d->findNode(key);
++ if (n)
++ return &n->value;
++ }
++ return nullptr;
++ }
++ public:
++ T value(const Key &key) const noexcept
++ {
++ if (T *v = valueImpl(key))
++ return *v;
++ else
++ return T();
++ }
++
++ T value(const Key &key, const T &defaultValue) const noexcept
++ {
++ if (T *v = valueImpl(key))
++ return *v;
++ else
++ return defaultValue;
++ }
++
++ T &operator[](const Key &key)
++ {
++ return *tryEmplace(key).iterator;
++ }
++
++ 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 iterator
++ {
++ using piter = typename QHashPrivate::iterator<Node>;
++ friend class const_iterator;
++ friend class QHash<Key, T>;
++ friend class QSet<Key>;
++ piter i;
++ explicit inline iterator(piter it) noexcept : i(it) { }
++
++ public:
++ typedef std::forward_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef T *pointer;
++ typedef T &reference;
++
++ constexpr iterator() noexcept = default;
++
++ 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++() noexcept
++ {
++ ++i;
++ return *this;
++ }
++ inline iterator operator++(int) noexcept
++ {
++ iterator r = *this;
++ ++i;
++ return r;
++ }
++
++ 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>;
++ piter i;
++ explicit inline const_iterator(piter it) : i(it) { }
++
++ public:
++ typedef std::forward_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef const T *pointer;
++ typedef const T &reference;
++
++ 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) noexcept
++ {
++ const_iterator r = *this;
++ ++i;
++ return r;
++ }
++ };
++ friend class const_iterator;
++
++ class key_iterator
++ {
++ const_iterator i;
++
++ 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;
++
++ key_iterator() noexcept = default;
++ explicit key_iterator(const_iterator o) noexcept : i(o) { }
++
++ 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++() 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() { if (!d) return iterator(); 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 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<QHash &>(*this); }
++ auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange<const QHash &>(*this); }
++ auto asKeyValueRange() && { return QtPrivate::QKeyValueRange<QHash>(std::move(*this)); }
++ auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange<QHash>(std::move(*this)); }
++
++ struct TryEmplaceResult
++ {
++ QHash::iterator iterator;
++ bool inserted;
++
++ TryEmplaceResult() = default;
++ // Generated SMFs are fine!
++ TryEmplaceResult(QHash::iterator it, bool b)
++ : iterator(it), inserted(b)
++ {
++ }
++
++ // Implicit conversion _from_ the return-type of try_emplace:
++ Q_IMPLICIT TryEmplaceResult(const std::pair<key_value_iterator, bool> &p)
++ : iterator(p.first.base()), inserted(p.second)
++ {
++ }
++ // Implicit conversion _to_ the return-type of try_emplace:
++ Q_IMPLICIT operator std::pair<key_value_iterator, bool>()
++ {
++ return { key_value_iterator(iterator), inserted };
++ }
++ };
++
++ 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);
++
++ d->erase(bucket);
++ if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
++ ++i;
++ return i;
++ }
++
++ 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 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);
++ }
++
++ iterator insert(const Key &key, T &&value)
++ {
++ return emplace(key, std::move(value));
++ }
++
++ iterator insert(Key &&key, const T &value)
++ {
++ return emplace(std::move(key), value);
++ }
++
++ iterator insert(Key &&key, T &&value)
++ {
++ return emplace(std::move(key), std::move(value));
++ }
++
++ 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());
++ }
++
++ 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 <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 <typename... Args>
++ TryEmplaceResult tryEmplace(const Key &key, Args &&...args)
++ {
++ return tryEmplace_impl(key, std::forward<Args>(args)...);
++ }
++ template <typename... Args>
++ TryEmplaceResult tryEmplace(Key &&key, Args &&...args)
++ {
++ return tryEmplace_impl(std::move(key), std::forward<Args>(args)...);
++ }
++
++ TryEmplaceResult tryInsert(const Key &key, const T &value)
++ {
++ return tryEmplace_impl(key, value);
++ }
++
++ template <typename... Args>
++ std::pair<key_value_iterator, bool> try_emplace(const Key &key, Args &&...args)
++ {
++ return tryEmplace_impl(key, std::forward<Args>(args)...);
++ }
++ template <typename... Args>
++ std::pair<key_value_iterator, bool> try_emplace(Key &&key, Args &&...args)
++ {
++ return tryEmplace_impl(std::move(key), std::forward<Args>(args)...);
++ }
++ template <typename... Args>
++ key_value_iterator try_emplace(const_iterator /*hint*/, const Key &key, Args &&...args)
++ {
++ return key_value_iterator(tryEmplace_impl(key, std::forward<Args>(args)...).iterator);
++ }
++ template <typename... Args>
++ key_value_iterator try_emplace(const_iterator /*hint*/, Key &&key, Args &&...args)
++ {
++ return key_value_iterator(tryEmplace_impl(std::move(key), std::forward<Args>(args)...).iterator);
++ }
++
++ private:
++ template <typename K, typename... Args>
++ TryEmplaceResult tryEmplace_impl(K &&key, Args &&...args)
++ {
++ if (!d)
++ detach();
++ QHash detachGuard;
++
++ size_t hash = QHashPrivate::calculateHash(key, d->seed);
++ typename Data::Bucket bucket = d->findBucketWithHash(key, hash);
++ const bool shouldInsert = bucket.isUnused();
++
++ // Even if we don't insert we may have to detach because we are
++ // returning a non-const iterator:
++ if (!isDetached() || (shouldInsert && d->shouldGrow())) {
++ detachGuard = *this;
++ const bool resized = shouldInsert && d->shouldGrow();
++ const size_t bucketIndex = bucket.toBucketIndex(d);
++
++ // Must detach from detachGuard
++ d = resized ? Data::detached(d, d->size + 1) : Data::detached(d);
++ bucket = resized ? d->findBucketWithHash(key, hash) : typename Data::Bucket(d, bucketIndex);
++ }
++ if (shouldInsert) {
++ Node *n = bucket.insert();
++ using ConstructProxy = typename QHashPrivate::HeterogenousConstructProxy<Key, K>;
++ Node::createInPlace(n, ConstructProxy(std::forward<K>(key)),
++ std::forward<Args>(args)...);
++ ++d->size;
++ }
++ return {iterator(bucket.toIterator(d)), shouldInsert};
++ }
++ public:
++ template <typename Value>
++ TryEmplaceResult insertOrAssign(const Key &key, Value &&value)
++ {
++ return insertOrAssign_impl(key, std::forward<Value>(value));
++ }
++ template <typename Value>
++ TryEmplaceResult insertOrAssign(Key &&key, Value &&value)
++ {
++ return insertOrAssign_impl(std::move(key), std::forward<Value>(value));
++ }
++ template <typename Value>
++ std::pair<key_value_iterator, bool> insert_or_assign(const Key &key, Value &&value)
++ {
++ return insertOrAssign_impl(key, std::forward<Value>(value));
++ }
++ template <typename Value>
++ std::pair<key_value_iterator, bool> insert_or_assign(Key &&key, Value &&value)
++ {
++ return insertOrAssign_impl(std::move(key), std::forward<Value>(value));
++ }
++ template <typename Value>
++ key_value_iterator insert_or_assign(const_iterator /*hint*/, const Key &key, Value &&value)
++ {
++ return key_value_iterator(insertOrAssign_impl(key, std::forward<Value>(value)).iterator);
++ }
++ template <typename Value>
++ key_value_iterator insert_or_assign(const_iterator /*hint*/, Key &&key, Value &&value)
++ {
++ return key_value_iterator(insertOrAssign_impl(std::move(key), std::forward<Value>(value)).iterator);
++ }
++
++ private:
++ template <typename K, typename Value>
++ TryEmplaceResult insertOrAssign_impl(K &&key, Value &&value)
++ {
++ auto r = tryEmplace(std::forward<K>(key), std::forward<Value>(value));
++ if (!r.inserted)
++ *r.iterator = std::forward<Value>(value); // `value` is untouched if we get here
++ return r;
++ }
++
++ public:
++
++ 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(); }
++
++ [[nodiscard]]
++ inline bool empty() const noexcept { return isEmpty(); }
++
++ 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 <typename K>
++ using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
++
++ template <typename K>
++ using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
++
++ public:
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ bool remove(const K &key)
++ {
++ return removeImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T take(const K &key)
++ {
++ return takeImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ bool contains(const K &key) const
++ {
++ return d ? d->findNode(key) != nullptr : false;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ qsizetype count(const K &key) const
++ {
++ return contains(key) ? 1 : 0;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T value(const K &key) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return T();
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T value(const K &key, const T &defaultValue) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return defaultValue;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ T &operator[](const K &key)
++ {
++ return *tryEmplace(key).iterator;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const T operator[](const K &key) const noexcept
++ {
++ return value(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ std::pair<iterator, iterator>
++ equal_range(const K &key)
++ {
++ return equal_range_impl(*this, key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ std::pair<const_iterator, const_iterator>
++ equal_range(const K &key) const noexcept
++ {
++ return equal_range_impl(*this, key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ iterator find(const K &key)
++ {
++ return findImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator find(const K &key) const noexcept
++ {
++ return constFindImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator constFind(const K &key) const noexcept
++ {
++ return find(key);
++ }
++ template <typename K, typename... Args, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ TryEmplaceResult tryEmplace(K &&key, Args &&...args)
++ {
++ return tryEmplace_impl(std::forward<K>(key), std::forward<Args>(args)...);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ TryEmplaceResult tryInsert(K &&key, const T &value)
++ {
++ return tryEmplace_impl(std::forward<K>(key), value);
++ }
++ template <typename K, typename... Args, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ std::pair<key_value_iterator, bool> try_emplace(K &&key, Args &&...args)
++ {
++ return tryEmplace_impl(std::forward<K>(key), std::forward<Args>(args)...);
++ }
++ template <typename K, typename... Args, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ key_value_iterator try_emplace(const_iterator /*hint*/, K &&key, Args &&...args)
++ {
++ return key_value_iterator(tryEmplace_impl(std::forward<K>(key), std::forward<Args>(args)...).iterator);
++ }
++ template <typename K, typename Value, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ TryEmplaceResult insertOrAssign(K &&key, Value &&value)
++ {
++ return insertOrAssign_impl(std::forward<K>(key), std::forward<Value>(value));
++ }
++ template <typename K, typename Value, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ std::pair<key_value_iterator, bool> insert_or_assign(K &&key, Value &&value)
++ {
++ return insertOrAssign_impl(std::forward<K>(key), std::forward<Value>(value));
++ }
++ template <typename K, typename Value, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ key_value_iterator insert_or_assign(const_iterator /*hint*/, K &&key, Value &&value)
++ {
++ return key_value_iterator(insertOrAssign_impl(std::forward<K>(key), std::forward<Value>(value)).iterator);
++ }
++ };
++
++
++ template <typename Key, typename T>
++ class QMultiHash
++ {
++ using Node = QHashPrivate::MultiNode<Key, T>;
++ using Data = QHashPrivate::Data<Node>;
++ using Chain = QHashPrivate::MultiNodeChain<T>;
++
++ Data *d = nullptr;
++ qsizetype m_size = 0;
++
++ 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());
++ }
++
++ template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
++ QMultiHash(InputIterator f, InputIterator l)
++ {
++ QtPrivate::reserveIfForwardIterator(this, f, l);
++ for (; f != l; ++f) {
++ auto &&e = *f;
++ using V = decltype(e);
++ insert(std::forward<V>(e).first, std::forward<V>(e).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.");
++
++ if (d && !d->ref.deref())
++ delete d;
++ }
++
++ 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;
++ }
++
++ explicit QMultiHash(const QHash<Key, T> &other)
++ : QMultiHash(other.begin(), other.end())
++ {}
++
++ explicit QMultiHash(QHash<Key, T> &&other)
++ {
++ unite(std::move(other));
++ }
++
++ void swap(QMultiHash &other) noexcept
++ {
++ qt_ptr_swap(d, other.d);
++ std::swap(m_size, other.m_size);
++ }
++
++ #ifndef Q_QDOC
++ private:
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> = true>
++ friend bool comparesEqual(const QMultiHash &lhs, const QMultiHash &rhs) noexcept
++ {
++ if (lhs.d == rhs.d)
++ return true;
++ if (lhs.m_size != rhs.m_size)
++ return false;
++ if (lhs.m_size == 0)
++ return true;
++ // equal size, and both non-zero size => d pointers allocated for both
++ Q_ASSERT(lhs.d);
++ Q_ASSERT(rhs.d);
++ if (lhs.d->size != rhs.d->size)
++ return false;
++ for (auto it = rhs.d->begin(); it != rhs.d->end(); ++it) {
++ auto *n = lhs.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;
++ }
++ QT_DECLARE_EQUALITY_OPERATORS_HELPER(QMultiHash, QMultiHash, /* non-constexpr */, noexcept,
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> = true>)
++ public:
++ #else
++ friend bool operator==(const QMultiHash &lhs, const QMultiHash &rhs) noexcept;
++ friend bool operator!=(const QMultiHash &lhs, const QMultiHash &rhs) noexcept;
++ #endif // Q_QDOC
++
++ inline qsizetype size() const noexcept { return m_size; }
++
++ [[nodiscard]]
++ inline bool isEmpty() const noexcept { return !m_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() { 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 QMultiHash &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;
++ m_size = 0;
++ }
++
++ 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;
++ }
++
++ public:
++ template <typename Predicate>
++ qsizetype removeIf(Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(*this, pred);
++ }
++
++ 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;
++ }
++
++ public:
++ bool contains(const Key &key) const noexcept
++ {
++ if (!d)
++ return false;
++ return d->findNode(key) != nullptr;
++ }
++
++ private:
++ const Key *keyImpl(const T &value) 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;
++ }
++ }
++
++ return nullptr;
++ }
++ public:
++ Key key(const T &value) const noexcept
++ {
++ if (auto *k = keyImpl(value))
++ return *k;
++ else
++ return Key();
++ }
++ Key key(const T &value, const Key &defaultKey) const noexcept
++ {
++ if (auto *k = keyImpl(value))
++ return *k;
++ else
++ return defaultKey;
++ }
++
++ private:
++ template <typename K>
++ T *valueImpl(const K &key) const noexcept
++ {
++ if (d) {
++ Node *n = d->findNode(key);
++ if (n) {
++ Q_ASSERT(n->value);
++ return &n->value->value;
++ }
++ }
++ return nullptr;
++ }
++ public:
++ T value(const Key &key) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return T();
++ }
++ T value(const Key &key, const T &defaultValue) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return defaultValue;
++ }
++
++ 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;
++ }
++
++ public:
++ const T operator[](const Key &key) const noexcept
++ {
++ return value(key);
++ }
++
++ QList<Key> uniqueKeys() const
++ {
++ QList<Key> res;
++ if (d) {
++ auto i = d->begin();
++ while (i != d->end()) {
++ res.append(i.node()->key);
++ ++i;
++ }
++ }
++ 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;
++ }
++
++ 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;
++ }
++
++ public:
++ class const_iterator;
++
++ 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);
++ }
++ }
++
++ public:
++ typedef std::forward_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef T *pointer;
++ typedef T &reference;
++
++ 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;
++ }
++
++ 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;
++
++ 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);
++ }
++ }
++
++ public:
++ typedef std::forward_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef const T *pointer;
++ typedef const T &reference;
++
++ 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;
++
++ class key_iterator
++ {
++ const_iterator i;
++
++ 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;
++
++ key_iterator() noexcept = default;
++ explicit key_iterator(const_iterator o) noexcept : i(o) { }
++
++ 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++() 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() { if (!d) return iterator(); 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<QMultiHash &>(*this); }
++ auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange<const QMultiHash &>(*this); }
++ auto asKeyValueRange() && { return QtPrivate::QKeyValueRange<QMultiHash>(std::move(*this)); }
++ auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange<QMultiHash>(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();
++
++ i = d->detachedIterator(i);
++ e = &i.node()->value;
++ while (n) {
++ e = &(*e)->next;
++ --n;
++ }
++ Q_ASSERT(e && *e);
++ }
++ return iterator(i, e);
++ }
++
++ 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;
++ }
++
++ // more Qt
++ typedef iterator Iterator;
++ typedef const_iterator ConstIterator;
++ inline qsizetype count() const noexcept { return size(); }
++
++ 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
++
++ 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));
++ }
++ public:
++ iterator find(const Key &key)
++ {
++ return findImpl(key);
++ }
++ const_iterator constFind(const Key &key) const noexcept
++ {
++ return constFindImpl(key);
++ }
++ const_iterator find(const Key &key) const noexcept
++ {
++ return constFindImpl(key);
++ }
++
++ iterator insert(const Key &key, const T &value)
++ {
++ return emplace(key, value);
++ }
++
++ iterator insert(const Key &key, T &&value)
++ {
++ return emplace(key, std::move(value));
++ }
++
++ iterator insert(Key &&key, const T &value)
++ {
++ return emplace(std::move(key), value);
++ }
++
++ iterator insert(Key &&key, T &&value)
++ {
++ return emplace(std::move(key), std::move(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)...);
++ }
++
++
++ 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(); }
++
++ [[nodiscard]]
++ 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)...);
++ }
++
++ 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; }
++
++ 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);
++ }
++
++ 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;
++ }
++
++ 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;
++ }
++
++ return n;
++ }
++
++ 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 n;
++ }
++
++ 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;
++ ++i;
++ }
++ return end;
++ }
++
++ 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), it.node()->takeValue());
++ other.clear();
++ return *this;
++ }
++
++ std::pair<iterator, iterator> equal_range(const Key &key)
++ {
++ return equal_range_impl(key);
++ }
++ private:
++ 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)};
++ }
++
++ 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)};
++ }
++
++ 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 {
++ result.it.node()->emplaceValue(std::forward<Args>(args)...);
++ }
++ return iterator(result.it);
++ }
++
++ template <typename K>
++ using if_heterogeneously_searchable = QHashPrivate::if_heterogeneously_searchable_with<Key, K>;
++
++ template <typename K>
++ using if_key_constructible_from = std::enable_if_t<std::is_constructible_v<Key, K>, bool>;
++
++ public:
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ qsizetype remove(const K &key)
++ {
++ return removeImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T take(const K &key)
++ {
++ return takeImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ bool contains(const K &key) const noexcept
++ {
++ if (!d)
++ return false;
++ return d->findNode(key) != nullptr;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T value(const K &key) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return T();
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ T value(const K &key, const T &defaultValue) const noexcept
++ {
++ if (auto *v = valueImpl(key))
++ return *v;
++ else
++ return defaultValue;
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true, if_key_constructible_from<K> = true>
++ T &operator[](const K &key)
++ {
++ return operatorIndexImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const T operator[](const K &key) const noexcept
++ {
++ return value(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ QList<T> values(const K &key)
++ {
++ return valuesImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ iterator find(const K &key)
++ {
++ return findImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator constFind(const K &key) const noexcept
++ {
++ return constFindImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator find(const K &key) const noexcept
++ {
++ return constFindImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ bool contains(const K &key, const T &value) const noexcept
++ {
++ return containsImpl(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ qsizetype remove(const K &key, const T &value)
++ {
++ return removeImpl(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ qsizetype count(const K &key) const noexcept
++ {
++ return countImpl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ qsizetype count(const K &key, const T &value) const noexcept
++ {
++ return countImpl(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ iterator find(const K &key, const T &value)
++ {
++ return findImpl(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator constFind(const K &key, const T &value) const noexcept
++ {
++ return constFindImpl(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ const_iterator find(const K &key, const T &value) const noexcept
++ {
++ return constFind(key, value);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ std::pair<iterator, iterator>
++ equal_range(const K &key)
++ {
++ return equal_range_impl(key);
++ }
++ template <typename K, if_heterogeneously_searchable<K> = true>
++ std::pair<const_iterator, const_iterator>
++ equal_range(const K &key) const noexcept
++ {
++ return equal_range_impl(key);
++ }
++ };
++
++ 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>
++ size_t qHash(const QHash<Key, T> &key, size_t seed = 0)
++ noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
++ {
++ const QtPrivate::QHashCombine combine(seed);
++ size_t hash = 0;
++ for (auto it = key.begin(), end = key.end(); it != end; ++it) {
++ 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;
++ }
++
++ template <class Key, class T>
++ 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 QtPrivate::QHashCombine combine(seed);
++ size_t hash = 0;
++ for (auto it = key.begin(), end = key.end(); it != end; ++it) {
++ 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;
++ }
++
++ template <typename Key, typename T, typename Predicate>
++ qsizetype erase_if(QHash<Key, T> &hash, Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(hash, pred);
++ }
++
++ 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