summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r--src/corelib/tools/qhash.h1061
1 files changed, 772 insertions, 289 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 9145891faf..e7cd4123fb 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -1,51 +1,15 @@
-/****************************************************************************
-**
-** 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>
-** 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/qalgorithms.h>
#include <QtCore/qcontainertools_impl.h>
#include <QtCore/qhashfunctions.h>
#include <QtCore/qiterator.h>
#include <QtCore/qlist.h>
-#include <QtCore/qmath.h>
#include <QtCore/qrefcount.h>
#include <initializer_list>
@@ -102,26 +66,6 @@ size_t calculateHash(const T &t, size_t seed = 0)
}
}
-// QHash uses a power of two growth policy.
-namespace GrowthPolicy {
-inline constexpr size_t maxNumBuckets() noexcept
-{
- return size_t(1) << (8 * sizeof(size_t) - 1);
-}
-inline constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept
-{
- if (requestedCapacity <= 8)
- return 16;
- if (requestedCapacity >= maxNumBuckets())
- return maxNumBuckets();
- return qNextPowerOfTwo(QIntegerForSize<sizeof(size_t)>::Unsigned(2 * requestedCapacity - 1));
-}
-inline constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept
-{
- return hash & (nBuckets - 1);
-}
-}
-
template <typename Key, typename T>
struct Node
{
@@ -228,7 +172,7 @@ struct MultiNode
MultiNode(MultiNode &&other)
: key(other.key),
- value(qExchange(other.value, nullptr))
+ value(std::exchange(other.value, nullptr))
{
}
@@ -259,7 +203,7 @@ struct MultiNode
void insertMulti(Args &&... args)
{
Chain *e = new Chain{ T(std::forward<Args>(args)...), nullptr };
- e->next = qExchange(value, e);
+ e->next = std::exchange(value, e);
}
template<typename ...Args>
void emplaceValue(Args &&... args)
@@ -274,6 +218,15 @@ constexpr bool isRelocatable()
return 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.
@@ -284,13 +237,6 @@ constexpr bool isRelocatable()
// table have a very small memory overhead compared to many other implementations.
template<typename Node>
struct Span {
- enum {
- NEntries = 128,
- LocalBucketMask = (NEntries - 1),
- UnusedEntry = 0xff
- };
- static_assert ((NEntries & LocalBucketMask) == 0, "EntriesPerSpan must be a power of two.");
-
// 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
@@ -298,19 +244,19 @@ struct Span {
// 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 {
- typename std::aligned_storage<sizeof(Node), alignof(Node)>::type storage;
+ 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[NEntries];
+ unsigned char offsets[SpanConstants::NEntries];
Entry *entries = nullptr;
unsigned char allocated = 0;
unsigned char nextFree = 0;
Span() noexcept
{
- memset(offsets, UnusedEntry, sizeof(offsets));
+ memset(offsets, SpanConstants::UnusedEntry, sizeof(offsets));
}
~Span()
{
@@ -321,7 +267,7 @@ struct Span {
if (entries) {
if constexpr (!std::is_trivially_destructible<Node>::value) {
for (auto o : offsets) {
- if (o != UnusedEntry)
+ if (o != SpanConstants::UnusedEntry)
entries[o].node().~Node();
}
}
@@ -331,8 +277,8 @@ struct Span {
}
Node *insert(size_t i)
{
- Q_ASSERT(i <= NEntries);
- Q_ASSERT(offsets[i] == UnusedEntry);
+ Q_ASSERT(i < SpanConstants::NEntries);
+ Q_ASSERT(offsets[i] == SpanConstants::UnusedEntry);
if (nextFree == allocated)
addStorage();
unsigned char entry = nextFree;
@@ -343,11 +289,11 @@ struct Span {
}
void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value)
{
- Q_ASSERT(bucket <= NEntries);
- Q_ASSERT(offsets[bucket] != UnusedEntry);
+ Q_ASSERT(bucket < SpanConstants::NEntries);
+ Q_ASSERT(offsets[bucket] != SpanConstants::UnusedEntry);
unsigned char entry = offsets[bucket];
- offsets[bucket] = UnusedEntry;
+ offsets[bucket] = SpanConstants::UnusedEntry;
entries[entry].node().~Node();
entries[entry].nextFree() = nextFree;
@@ -359,19 +305,19 @@ struct Span {
}
bool hasNode(size_t i) const noexcept
{
- return (offsets[i] != UnusedEntry);
+ return (offsets[i] != SpanConstants::UnusedEntry);
}
Node &at(size_t i) noexcept
{
- Q_ASSERT(i <= NEntries);
- Q_ASSERT(offsets[i] != UnusedEntry);
+ 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 <= NEntries);
- Q_ASSERT(offsets[i] != UnusedEntry);
+ Q_ASSERT(i < SpanConstants::NEntries);
+ Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry);
return entries[offsets[i]].node();
}
@@ -389,17 +335,17 @@ struct Span {
}
void moveLocal(size_t from, size_t to) noexcept
{
- Q_ASSERT(offsets[from] != UnusedEntry);
- Q_ASSERT(offsets[to] == UnusedEntry);
+ Q_ASSERT(offsets[from] != SpanConstants::UnusedEntry);
+ Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry);
offsets[to] = offsets[from];
- offsets[from] = UnusedEntry;
+ 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 <= NEntries);
- Q_ASSERT(offsets[to] == UnusedEntry);
- Q_ASSERT(fromIndex <= NEntries);
- Q_ASSERT(fromSpan.offsets[fromIndex] != UnusedEntry);
+ 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);
@@ -408,7 +354,7 @@ struct Span {
nextFree = toEntry.nextFree();
size_t fromOffset = fromSpan.offsets[fromIndex];
- fromSpan.offsets[fromIndex] = UnusedEntry;
+ fromSpan.offsets[fromIndex] = SpanConstants::UnusedEntry;
Entry &fromEntry = fromSpan.entries[fromOffset];
if constexpr (isRelocatable<Node>()) {
@@ -423,15 +369,28 @@ struct Span {
void addStorage()
{
- Q_ASSERT(allocated < NEntries);
+ 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. The likelihood of having below 16 entries is very small,
- // so start with that and increment by 16 each time we need to add
- // some more space
- const size_t increment = NEntries / 8;
- size_t alloc = allocated + increment;
+ // 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
@@ -444,7 +403,7 @@ struct Span {
entries[i].node().~Node();
}
}
- for (size_t i = allocated; i < allocated + increment; ++i) {
+ for (size_t i = allocated; i < alloc; ++i) {
newEntries[i].nextFree() = uchar(i + 1);
}
delete[] entries;
@@ -453,6 +412,34 @@ struct Span {
}
};
+// 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;
@@ -468,43 +455,148 @@ struct Data
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);
+ }
- Span *spans = nullptr;
+ 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);
- size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
- spans = new Span[nSpans];
+ spans = allocateSpans(numBuckets).spans;
seed = QHashSeed::globalSeed();
}
- Data(const Data &other, size_t reserved = 0)
- : size(other.size),
- numBuckets(other.numBuckets),
- seed(other.seed)
- {
- if (reserved)
- numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved));
- bool resized = numBuckets != other.numBuckets;
- size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries;
- spans = new Span[nSpans];
+ 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 < Span::NEntries; ++index) {
+ for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
if (!span.hasNode(index))
continue;
const Node &n = span.at(index);
- iterator it = resized ? find(n.key) : iterator{ this, s*Span::NEntries + index };
+ auto it = resized ? findBucket(n.key) : Bucket { spans + s, index };
Q_ASSERT(it.isUnused());
- Node *newNode = spans[it.span()].insert(it.index());
+ Node *newNode = it.insert();
new (newNode) Node(n);
}
}
}
- static Data *detached(Data *d, size_t size = 0)
+ 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);
@@ -548,20 +640,19 @@ struct Data
Span *oldSpans = spans;
size_t oldBucketCount = numBuckets;
- size_t nSpans = (newBucketCount + Span::LocalBucketMask) / Span::NEntries;
- spans = new Span[nSpans];
+ spans = allocateSpans(newBucketCount).spans;
numBuckets = newBucketCount;
- size_t oldNSpans = (oldBucketCount + Span::LocalBucketMask) / Span::NEntries;
+ size_t oldNSpans = oldBucketCount >> SpanConstants::SpanShift;
for (size_t s = 0; s < oldNSpans; ++s) {
Span &span = oldSpans[s];
- for (size_t index = 0; index < Span::NEntries; ++index) {
+ for (size_t index = 0; index < SpanConstants::NEntries; ++index) {
if (!span.hasNode(index))
continue;
Node &n = span.at(index);
- iterator it = find(n.key);
+ auto it = findBucket(n.key);
Q_ASSERT(it.isUnused());
- Node *newNode = spans[it.span()].insert(it.index());
+ Node *newNode = it.insert();
new (newNode) Node(std::move(n));
}
span.freeData();
@@ -586,39 +677,34 @@ struct Data
return size >= (numBuckets >> 1);
}
- iterator find(const Key &key) const noexcept
+ 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);
- size_t bucket = GrowthPolicy::bucketForHash(numBuckets, hash);
+ 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) {
- // Split the bucket into the indexex of span array, and the local
- // offset inside the span
- size_t span = bucket / Span::NEntries;
- size_t index = bucket & Span::LocalBucketMask;
- Span &s = spans[span];
- size_t offset = s.offset(index);
- if (offset == Span::UnusedEntry) {
- return iterator{ this, bucket };
+ size_t offset = bucket.offset();
+ if (offset == SpanConstants::UnusedEntry) {
+ return bucket;
} else {
- Node &n = s.atOffset(offset);
+ Node &n = bucket.nodeAtOffset(offset);
if (qHashEquals(n.key, key))
- return iterator{ this, bucket };
+ return bucket;
}
- bucket = nextBucket(bucket);
+ bucket.advanceWrapped(this);
}
}
- Node *findNode(const Key &key) const noexcept
+ template <typename K> Node *findNode(const K &key) const noexcept
{
- if (!size)
- return nullptr;
- iterator it = find(key);
- if (it.isUnused())
+ auto bucket = findBucket(key);
+ if (bucket.isUnused())
return nullptr;
- return it.node();
+ return bucket.node();
}
struct InsertionResult
@@ -627,64 +713,58 @@ struct Data
bool initialized;
};
- InsertionResult findOrInsert(const Key &key) noexcept
+ template <typename K> InsertionResult findOrInsert(const K &key) noexcept
{
- if (shouldGrow())
+ 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);
- iterator it = find(key);
- if (it.isUnused()) {
- spans[it.span()].insert(it.index());
- ++size;
- return { it, false };
+ it = findBucket(key); // need to get a new iterator after rehashing
}
- return { it, true };
+ Q_ASSERT(it.span != nullptr);
+ Q_ASSERT(it.isUnused());
+ it.insert();
+ ++size;
+ return { it.toIterator(this), false };
}
- iterator erase(iterator it) noexcept(std::is_nothrow_destructible<Node>::value)
+ void erase(Bucket bucket) noexcept(std::is_nothrow_destructible<Node>::value)
{
- size_t bucket = it.bucket;
- size_t span = bucket / Span::NEntries;
- size_t index = bucket & Span::LocalBucketMask;
- Q_ASSERT(spans[span].hasNode(index));
- spans[span].erase(index);
+ Q_ASSERT(bucket.span->hasNode(bucket.index));
+ bucket.span->erase(bucket.index);
--size;
// re-insert the following entries to avoid holes
- size_t hole = bucket;
- size_t next = bucket;
+ Bucket next = bucket;
while (true) {
- next = nextBucket(next);
- size_t nextSpan = next / Span::NEntries;
- size_t nextIndex = next & Span::LocalBucketMask;
- if (!spans[nextSpan].hasNode(nextIndex))
- break;
- size_t hash = QHashPrivate::calculateHash(spans[nextSpan].at(nextIndex).key, seed);
- size_t newBucket = GrowthPolicy::bucketForHash(numBuckets, hash);
+ 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 == hole) {
- // move into hole
- size_t holeSpan = hole / Span::NEntries;
- size_t holeIndex = hole & Span::LocalBucketMask;
- if (nextSpan == holeSpan) {
- spans[holeSpan].moveLocal(nextIndex, holeIndex);
+ } 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
- spans[holeSpan].moveFromSpan(spans[nextSpan], nextIndex, holeIndex);
+ bucket.span->moveFromSpan(*next.span, next.index, bucket.index);
}
- hole = next;
+ bucket = next;
break;
}
- newBucket = nextBucket(newBucket);
+ newBucket.advanceWrapped(this);
}
}
-
- // return correct position of the next element
- if (bucket == numBuckets - 1 || !spans[span].hasNode(index))
- ++it;
- return it;
}
~Data()
@@ -700,8 +780,8 @@ struct iterator {
const Data<Node> *d = nullptr;
size_t bucket = 0;
- size_t span() const noexcept { return bucket / Span::NEntries; }
- size_t index() const noexcept { return bucket & Span::LocalBucketMask; }
+ 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
@@ -817,10 +897,11 @@ 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); }
- template <typename U = T>
- QTypeTraits::compare_eq_result_container<QHash, U> operator==(const QHash &other) const noexcept
+#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;
@@ -835,9 +916,13 @@ public:
// all values must be the same as size is the same
return true;
}
- template <typename U = T>
- QTypeTraits::compare_eq_result_container<QHash, U> operator!=(const QHash &other) const noexcept
+ 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;
+#endif // Q_QDOC
inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
inline bool isEmpty() const noexcept { return !d || d->size == 0; }
@@ -845,6 +930,9 @@ public:
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
@@ -869,28 +957,45 @@ public:
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
- auto it = d->find(key);
if (it.isUnused())
return false;
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
- auto it = d->find(key);
if (it.isUnused())
return T();
T value = it.node()->takeValue();
@@ -898,6 +1003,7 @@ public:
return value;
}
+public:
bool contains(const Key &key) const noexcept
{
if (!d)
@@ -909,7 +1015,8 @@ public:
return contains(key) ? 1 : 0;
}
- Key key(const T &value, const Key &defaultKey = Key()) const noexcept
+private:
+ template <typename Fn> Key keyImpl(const T &value, Fn &&defaultFn) const noexcept
{
if (d) {
const_iterator i = begin();
@@ -920,27 +1027,57 @@ public:
}
}
- return defaultKey;
+ 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; });
}
- T value(const Key &key, const T &defaultValue = T()) const noexcept
+
+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;
+ 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, T());
+ 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);
@@ -1088,6 +1225,10 @@ public:
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)
{
@@ -1095,50 +1236,65 @@ public:
detach();
// ensure a valid iterator across the detach:
iterator i = iterator{d->detachedIterator(it.i)};
+ typename Data::Bucket bucket(i.i);
- i.i = d->erase(i.i);
+ d->erase(bucket);
+ if (bucket.toBucketIndex(d) == d->numBuckets - 1 || bucket.isUnused())
+ ++i;
return i;
}
- QPair<iterator, iterator> equal_range(const Key &key)
+ std::pair<iterator, iterator> equal_range(const Key &key)
{
- auto first = find(key);
- auto second = first;
- if (second != iterator())
- ++second;
- return qMakePair(first, second);
+ return equal_range_impl(*this, key);
}
-
- QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
+ 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 = find(key);
+ auto first = self.find(key);
auto second = first;
- if (second != iterator())
+ if (second != decltype(first){})
++second;
- return qMakePair(first, second);
+ return std::make_pair(first, second);
}
- typedef iterator Iterator;
- typedef const_iterator ConstIterator;
- inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; }
- iterator find(const Key &key)
+ 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();
- auto it = d->find(key);
+ it = typename Data::Bucket(d, bucket); // reattach in case of detach
if (it.isUnused())
- it = d->end();
- return iterator(it);
+ return end();
+ return iterator(it.toIterator(d));
}
- const_iterator find(const Key &key) const noexcept
+ template <typename K> const_iterator constFindImpl(const K &key) const noexcept
{
if (isEmpty())
return end();
- auto it = d->find(key);
+ auto it = d->findBucket(key);
if (it.isUnused())
- it = d->end();
- return const_iterator(it);
+ 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
{
@@ -1174,8 +1330,28 @@ public:
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(); }
+ 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)...);
@@ -1184,16 +1360,66 @@ public:
return iterator(result.it);
}
- 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 QHashPrivate::GrowthPolicy::maxNumBuckets(); }
-
- inline bool empty() const noexcept { return isEmpty(); }
+public:
+#ifdef __cpp_concepts
+ bool remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+ {
+ return removeImpl(key);
+ }
+ 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 <typename Key, typename T>
class QMultiHash
{
@@ -1269,8 +1495,8 @@ public:
return *this;
}
QMultiHash(QMultiHash &&other) noexcept
- : d(qExchange(other.d, nullptr)),
- m_size(qExchange(other.m_size, 0))
+ : 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)
@@ -1288,9 +1514,16 @@ public:
{
unite(std::move(other));
}
- void swap(QMultiHash &other) noexcept { qSwap(d, other.d); qSwap(m_size, other.m_size); }
- bool operator==(const QMultiHash &other) const noexcept
+ void swap(QMultiHash &other) noexcept
+ {
+ qt_ptr_swap(d, other.d);
+ std::swap(m_size, other.m_size);
+ }
+
+#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;
@@ -1304,12 +1537,12 @@ public:
if (d->size != other.d->size)
return false;
for (auto it = other.d->begin(); it != other.d->end(); ++it) {
- auto i = d->find(it.node()->key);
- if (i == d->end())
+ auto *n = d->findNode(it.node()->key);
+ if (!n)
return false;
Chain *e = it.node()->value;
while (e) {
- Chain *oe = i.node()->value;
+ Chain *oe = n->value;
while (oe) {
if (oe->value == e->value)
break;
@@ -1323,7 +1556,13 @@ public:
// all values must be the same as size is the same
return true;
}
- bool operator!=(const QMultiHash &other) const noexcept { return !(*this == other); }
+ 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
inline qsizetype size() const noexcept { return m_size; }
@@ -1332,6 +1571,9 @@ public:
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
@@ -1353,11 +1595,18 @@ public:
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
- auto it = d->find(key);
if (it.isUnused())
return 0;
qsizetype n = Node::freeChain(it.node());
@@ -1366,18 +1615,28 @@ public:
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
- auto it = d->find(key);
if (it.isUnused())
return T();
Chain *e = it.node()->value;
@@ -1395,6 +1654,7 @@ public:
return t;
}
+public:
bool contains(const Key &key) const noexcept
{
if (!d)
@@ -1402,7 +1662,8 @@ public:
return d->findNode(key) != nullptr;
}
- Key key(const T &value, const Key &defaultKey = Key()) const noexcept
+private:
+ template <typename Fn> Key keyImpl(const T &value, Fn &&defaultValue) const noexcept
{
if (d) {
auto i = d->begin();
@@ -1414,9 +1675,20 @@ public:
}
}
- return defaultKey;
+ 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; });
}
- T value(const Key &key, const T &defaultValue = T()) const noexcept
+
+private:
+ template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept
{
if (d) {
Node *n = d->findNode(key);
@@ -1425,19 +1697,37 @@ public:
return n->value->value;
}
}
- return defaultValue;
+ 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() ? 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, T());
+ 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);
@@ -1468,9 +1758,15 @@ public:
}
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);
@@ -1485,6 +1781,7 @@ public:
return values;
}
+public:
class const_iterator;
class iterator
@@ -1634,6 +1931,10 @@ public:
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)
{
@@ -1664,7 +1965,8 @@ public:
iterator erase(const_iterator it)
{
Q_ASSERT(d);
- iterator i = detach(it);
+ iterator iter = detach(it);
+ iterator i = iter;
Chain *e = *i.e;
Chain *next = e->next;
*i.e = next;
@@ -1672,9 +1974,14 @@ public:
if (!next) {
if (i.e == &i.i.node()->value) {
// last remaining entry, erase
- i = iterator(d->erase(i.i));
+ 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(++it.i);
+ i = iterator(++iter.i);
}
}
--m_size;
@@ -1686,29 +1993,44 @@ public:
typedef iterator Iterator;
typedef const_iterator ConstIterator;
inline qsizetype count() const noexcept { return size(); }
- iterator find(const Key &key)
+
+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();
- auto it = d->find(key);
+ it = typename Data::Bucket(d, bucket); // reattach in case of detach
+
if (it.isUnused())
- it = d->end();
- return iterator(it);
- }
- const_iterator find(const Key &key) const noexcept
- {
- return constFind(key);
+ return end();
+ return iterator(it.toIterator(d));
}
- const_iterator constFind(const Key &key) const noexcept
+ template <typename K> const_iterator constFindImpl(const K &key) const noexcept
{
if (isEmpty())
return end();
- auto it = d->find(key);
+ auto it = d->findBucket(key);
if (it.isUnused())
- it = d->end();
- return const_iterator(it);
+ 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);
@@ -1723,22 +2045,22 @@ public:
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();
-
- 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);
+ 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 QHashPrivate::GrowthPolicy::maxNumBuckets(); }
+ static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
inline bool empty() const noexcept { return isEmpty(); }
@@ -1756,16 +2078,15 @@ public:
template <typename ...Args>
iterator emplaceReplace(Key &&key, Args &&... args)
{
- detach();
-
- auto result = d->findOrInsert(key);
- if (!result.initialized) {
- ++m_size;
- Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
- } else {
- result.it.node()->emplaceValue(std::forward<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)...);
}
- return iterator(result.it);
+ // 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)
@@ -1775,6 +2096,11 @@ public:
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);
@@ -1783,13 +2109,21 @@ public:
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
- auto it = d->find(key);
if (it.isUnused())
return 0;
qsizetype n = 0;
@@ -1811,11 +2145,17 @@ public:
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->find(key);
+ auto it = d->findBucket(key);
if (it.isUnused())
return 0;
qsizetype n = 0;
@@ -1828,11 +2168,17 @@ public:
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->find(key);
+ auto it = d->findBucket(key);
if (it.isUnused())
return 0;
qsizetype n = 0;
@@ -1846,19 +2192,16 @@ public:
return n;
}
- iterator find(const Key &key, const T &value)
+ 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);
}
- const_iterator find(const Key &key, const T &value) const noexcept
- {
- return constFind(key, value);
- }
- const_iterator constFind(const Key &key, const T &value) const noexcept
+ template <typename K> const_iterator constFindImpl(const K &key, const T &value) const noexcept
{
const_iterator i(constFind(key));
const_iterator end(constEnd());
@@ -1870,6 +2213,21 @@ public:
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()) {
@@ -1905,27 +2263,39 @@ public:
return *this;
}
- QPair<iterator, iterator> equal_range(const Key &key)
+ 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 = qAsConst(*this).equal_range(key);
- return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
+ auto pair = std::as_const(*this).equal_range(key);
+ return {iterator(pair.first.i), iterator(pair.second.i)};
}
- QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept
+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 qMakePair(end(), end());
+ return {end(), end()};
- auto it = d->find(key);
- if (it.isUnused())
- return qMakePair(end(), end());
+ auto bucket = d->findBucket(key);
+ if (bucket.isUnused())
+ return {end(), end()};
+ auto it = bucket.toIterator(d);
auto end = it;
++end;
- return qMakePair(const_iterator(it), const_iterator(end));
+ return {const_iterator(it), const_iterator(end)};
}
-private:
void detach_helper()
{
if (!d) {
@@ -1937,6 +2307,119 @@ private:
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);
+ }
+
+public:
+#ifdef __cpp_concepts
+ qsizetype remove(const QHashPrivate::HeterogeneouslySearchableWith<Key> auto &key)
+ {
+ return removeImpl(key);
+ }
+ 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_FORWARD_ITERATOR(Hash)