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.h524
1 files changed, 384 insertions, 140 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 5075459531..e7cd4123fb 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -5,11 +5,11 @@
#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>
@@ -172,7 +172,7 @@ struct MultiNode
MultiNode(MultiNode &&other)
: key(other.key),
- value(qExchange(other.value, nullptr))
+ value(std::exchange(other.value, nullptr))
{
}
@@ -203,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)
@@ -414,28 +414,25 @@ struct Span {
// QHash uses a power of two growth policy.
namespace GrowthPolicy {
-inline constexpr size_t maxNumBuckets() noexcept
-{
- // ensure the size of a Span does not depend on the template parameters
- using Node1 = Node<int, int>;
- using Node2 = Node<char, void *>;
- using Node3 = Node<qsizetype, QHashDummyValue>;
- static_assert(sizeof(Span<Node1>) == sizeof(Span<Node2>));
- static_assert(sizeof(Span<Node1>) == sizeof(Span<Node3>));
-
- // Maximum is 2^31-1 or 2^63-1 bytes (limited by qsizetype and ptrdiff_t)
- size_t max = (std::numeric_limits<ptrdiff_t>::max)();
- return max / sizeof(Span<Node1>) * SpanConstants::NEntries;
-}
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;
- if (requestedCapacity >= maxNumBuckets())
- return maxNumBuckets();
- return qNextPowerOfTwo(QIntegerForSize<sizeof(size_t)>::Unsigned(2 * requestedCapacity - 1));
+
+ // 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
{
@@ -460,6 +457,11 @@ struct Data
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;
@@ -529,11 +531,29 @@ struct Data
}
};
+ 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 >> SpanConstants::SpanShift;
- spans = new Span[nSpans];
+ spans = allocateSpans(numBuckets).spans;
seed = QHashSeed::globalSeed();
}
@@ -555,17 +575,16 @@ struct Data
Data(const Data &other) : size(other.size), numBuckets(other.numBuckets), seed(other.seed)
{
- size_t nSpans = numBuckets >> SpanConstants::SpanShift;
- spans = new Span[nSpans];
- reallocationHelper(other, nSpans, false);
+ 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));
- size_t nSpans = numBuckets >> SpanConstants::SpanShift;
- spans = new Span[nSpans];
+ spans = allocateSpans(numBuckets).spans;
size_t otherNSpans = other.numBuckets >> SpanConstants::SpanShift;
- reallocationHelper(other, otherNSpans, true);
+ reallocationHelper(other, otherNSpans, numBuckets != other.numBuckets);
}
static Data *detached(Data *d)
@@ -621,8 +640,7 @@ struct Data
Span *oldSpans = spans;
size_t oldBucketCount = numBuckets;
- size_t nSpans = newBucketCount >> SpanConstants::SpanShift;
- spans = new Span[nSpans];
+ spans = allocateSpans(newBucketCount).spans;
numBuckets = newBucketCount;
size_t oldNSpans = oldBucketCount >> SpanConstants::SpanShift;
@@ -659,8 +677,10 @@ struct Data
return size >= (numBuckets >> 1);
}
- Bucket findBucket(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);
Bucket bucket(this, GrowthPolicy::bucketForHash(numBuckets, hash));
@@ -679,24 +699,12 @@ struct Data
}
}
- Node *findNode(const Key &key) const noexcept
+ template <typename K> Node *findNode(const K &key) const noexcept
{
- Q_ASSERT(numBuckets > 0);
- size_t hash = QHashPrivate::calculateHash(key, seed);
- Bucket bucket(this, GrowthPolicy::bucketForHash(numBuckets, hash));
- // loop over the buckets until we find the entry we search for
- // or an empty slot, in which case we know the entry doesn't exist
- while (true) {
- size_t offset = bucket.offset();
- if (offset == SpanConstants::UnusedEntry) {
- return nullptr;
- } else {
- Node &n = bucket.nodeAtOffset(offset);
- if (qHashEquals(n.key, key))
- return &n;
- }
- bucket.advanceWrapped(this);
- }
+ auto bucket = findBucket(key);
+ if (bucket.isUnused())
+ return nullptr;
+ return bucket.node();
}
struct InsertionResult
@@ -705,7 +713,7 @@ struct Data
bool initialized;
};
- InsertionResult findOrInsert(const Key &key) noexcept
+ template <typename K> InsertionResult findOrInsert(const K &key) noexcept
{
Bucket it(static_cast<Span *>(nullptr), 0);
if (numBuckets > 0) {
@@ -891,7 +899,7 @@ public:
#endif
void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); }
-#ifndef Q_CLANG_QDOC
+#ifndef Q_QDOC
template <typename AKey = Key, typename AT = T>
QTypeTraits::compare_eq_result_container<QHash, AKey, AT> operator==(const QHash &other) const noexcept
{
@@ -914,7 +922,7 @@ public:
#else
bool operator==(const QHash &other) const;
bool operator!=(const QHash &other) const;
-#endif // Q_CLANG_QDOC
+#endif // Q_QDOC
inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; }
inline bool isEmpty() const noexcept { return !d || d->size == 0; }
@@ -949,6 +957,11 @@ 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);
@@ -961,13 +974,21 @@ public:
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);
@@ -982,6 +1003,7 @@ public:
return value;
}
+public:
bool contains(const Key &key) const noexcept
{
if (!d)
@@ -994,74 +1016,68 @@ public:
}
private:
- const Key *keyImpl(const T &value) const noexcept
+ template <typename Fn> Key keyImpl(const T &value, Fn &&defaultFn) const noexcept
{
if (d) {
const_iterator i = begin();
while (i != end()) {
if (i.value() == value)
- return &i.key();
+ return i.key();
++i;
}
}
- return nullptr;
+ return defaultFn();
}
public:
Key key(const T &value) const noexcept
{
- if (auto *k = keyImpl(value))
- return *k;
- else
- return Key();
+ return keyImpl(value, [] { return Key(); });
}
Key key(const T &value, const Key &defaultKey) const noexcept
{
- if (auto *k = keyImpl(value))
- return *k;
- else
- return defaultKey;
+ return keyImpl(value, [&] { return defaultKey; });
}
private:
- T *valueImpl(const Key &key) const noexcept
+ 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 n->value;
}
- return nullptr;
+ return defaultValue();
}
public:
T value(const Key &key) const noexcept
{
- if (T *v = valueImpl(key))
- return *v;
- else
- return T();
+ return valueImpl(key, [] { return T(); });
}
T value(const Key &key, const T &defaultValue) const noexcept
{
- if (T *v = valueImpl(key))
- return *v;
- else
- return defaultValue;
+ 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);
@@ -1228,28 +1244,25 @@ public:
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();
@@ -1261,7 +1274,7 @@ public:
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();
@@ -1270,6 +1283,19 @@ public:
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);
@@ -1318,7 +1344,7 @@ 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 QHashPrivate::GrowthPolicy::maxNumBuckets(); }
+ static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
inline bool empty() const noexcept { return isEmpty(); }
@@ -1333,8 +1359,65 @@ private:
result.it.node()->emplaceValue(std::forward<Args>(args)...);
return iterator(result.it);
}
-};
+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>
@@ -1412,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)
@@ -1438,7 +1521,7 @@ public:
std::swap(m_size, other.m_size);
}
-#ifndef Q_CLANG_QDOC
+#ifndef Q_QDOC
template <typename AKey = Key, typename AT = T>
QTypeTraits::compare_eq_result_container<QMultiHash, AKey, AT> operator==(const QMultiHash &other) const noexcept
{
@@ -1479,7 +1562,7 @@ public:
#else
bool operator==(const QMultiHash &other) const;
bool operator!=(const QMultiHash &other) const;
-#endif // Q_CLANG_QDOC
+#endif // Q_QDOC
inline qsizetype size() const noexcept { return m_size; }
@@ -1512,6 +1595,11 @@ 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);
@@ -1527,13 +1615,21 @@ 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);
@@ -1558,6 +1654,7 @@ public:
return t;
}
+public:
bool contains(const Key &key) const noexcept
{
if (!d)
@@ -1566,75 +1663,71 @@ public:
}
private:
- const Key *keyImpl(const T &value) const noexcept
+ template <typename Fn> Key keyImpl(const T &value, Fn &&defaultValue) const noexcept
{
if (d) {
auto i = d->begin();
while (i != d->end()) {
Chain *e = i.node()->value;
if (e->contains(value))
- return &i.node()->key;
+ return i.node()->key;
++i;
}
}
- return nullptr;
+ return defaultValue();
}
public:
Key key(const T &value) const noexcept
{
- if (auto *k = keyImpl(value))
- return *k;
- else
- return Key();
+ return keyImpl(value, [] { return Key(); });
}
Key key(const T &value, const Key &defaultKey) const noexcept
{
- if (auto *k = keyImpl(value))
- return *k;
- else
- return defaultKey;
+ return keyImpl(value, [&] { return defaultKey; });
}
private:
- T *valueImpl(const Key &key) const noexcept
+ template <typename K, typename Fn> T valueImpl(const K &key, Fn &&defaultValue) const noexcept
{
if (d) {
Node *n = d->findNode(key);
if (n) {
Q_ASSERT(n->value);
- return &n->value->value;
+ return n->value->value;
}
}
- return nullptr;
+ return defaultValue();
}
public:
T value(const Key &key) const noexcept
{
- if (auto *v = valueImpl(key))
- return *v;
- else
- return T();
+ return valueImpl(key, [] { return T(); });
}
T value(const Key &key, const T &defaultValue) const noexcept
{
- if (auto *v = valueImpl(key))
- return *v;
- else
- return defaultValue;
+ 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);
@@ -1665,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);
@@ -1682,6 +1781,7 @@ public:
return values;
}
+public:
class const_iterator;
class iterator
@@ -1893,7 +1993,9 @@ 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();
@@ -1906,11 +2008,7 @@ public:
return end();
return iterator(it.toIterator(d));
}
- const_iterator find(const Key &key) const noexcept
- {
- return constFind(key);
- }
- const_iterator constFind(const Key &key) const noexcept
+ template <typename K> const_iterator constFindImpl(const K &key) const noexcept
{
if (isEmpty())
return end();
@@ -1919,6 +2017,20 @@ public:
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);
@@ -1948,7 +2060,7 @@ 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 QHashPrivate::GrowthPolicy::maxNumBuckets(); }
+ static size_t max_bucket_count() noexcept { return Data::maxNumBuckets(); }
inline bool empty() const noexcept { return isEmpty(); }
@@ -1984,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);
@@ -1992,8 +2109,14 @@ 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);
@@ -2022,8 +2145,14 @@ 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->findBucket(key);
@@ -2039,8 +2168,14 @@ 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->findBucket(key);
@@ -2057,7 +2192,7 @@ 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();
@@ -2066,11 +2201,7 @@ public:
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());
@@ -2082,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()) {
@@ -2117,29 +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 bucket = d->findBucket(key);
if (bucket.isUnused())
- return qMakePair(end(), end());
+ 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) {
@@ -2176,6 +2332,94 @@ private:
}
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)