diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
| -rw-r--r-- | src/corelib/tools/qhash.h | 633 |
1 files changed, 437 insertions, 196 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index c4b4098c0f..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> @@ -208,7 +172,7 @@ struct MultiNode MultiNode(MultiNode &&other) : key(other.key), - value(qExchange(other.value, nullptr)) + value(std::exchange(other.value, nullptr)) { } @@ -239,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) @@ -280,7 +244,7 @@ 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); } @@ -313,7 +277,7 @@ struct Span { } Node *insert(size_t i) { - Q_ASSERT(i <= SpanConstants::NEntries); + Q_ASSERT(i < SpanConstants::NEntries); Q_ASSERT(offsets[i] == SpanConstants::UnusedEntry); if (nextFree == allocated) addStorage(); @@ -325,7 +289,7 @@ struct Span { } void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value) { - Q_ASSERT(bucket <= SpanConstants::NEntries); + Q_ASSERT(bucket < SpanConstants::NEntries); Q_ASSERT(offsets[bucket] != SpanConstants::UnusedEntry); unsigned char entry = offsets[bucket]; @@ -345,14 +309,14 @@ struct Span { } Node &at(size_t i) noexcept { - Q_ASSERT(i <= SpanConstants::NEntries); + 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(i < SpanConstants::NEntries); Q_ASSERT(offsets[i] != SpanConstants::UnusedEntry); return entries[offsets[i]].node(); @@ -378,9 +342,9 @@ struct Span { } 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(to < SpanConstants::NEntries); Q_ASSERT(offsets[to] == SpanConstants::UnusedEntry); - Q_ASSERT(fromIndex <= SpanConstants::NEntries); + Q_ASSERT(fromIndex < SpanConstants::NEntries); Q_ASSERT(fromSpan.offsets[fromIndex] != SpanConstants::UnusedEntry); if (nextFree == allocated) addStorage(); @@ -450,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 { @@ -496,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; @@ -565,33 +531,41 @@ 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(); } - 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 >> SpanConstants::SpanShift; - spans = new Span[nSpans]; - size_t otherNSpans = other.numBuckets >> SpanConstants::SpanShift; - for (size_t s = 0; s < otherNSpans; ++s) { + void reallocationHelper(const Data &other, size_t nSpans, bool resized) + { + for (size_t s = 0; s < nSpans; ++s) { const Span &span = other.spans[s]; for (size_t index = 0; index < SpanConstants::NEntries; ++index) { if (!span.hasNode(index)) continue; const Node &n = span.at(index); - auto it = resized ? findBucket(n.key) : Bucket{ spans + s, index }; + auto it = resized ? findBucket(n.key) : Bucket { spans + s, index }; Q_ASSERT(it.isUnused()); Node *newNode = it.insert(); new (newNode) Node(n); @@ -599,7 +573,30 @@ struct Data } } - 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); @@ -643,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; @@ -681,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)); @@ -701,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 @@ -727,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) { @@ -911,9 +897,9 @@ public: insert(f->first, f->second); } #endif - void swap(QHash &other) noexcept { qSwap(d, other.d); } + void swap(QHash &other) noexcept { qt_ptr_swap(d, other.d); } -#ifndef Q_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 { @@ -936,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; } @@ -944,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 @@ -968,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); @@ -980,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); @@ -1001,6 +1003,7 @@ public: return value; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -1013,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,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) { @@ -1243,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 { - auto first = find(key); + 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 != 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(); @@ -1276,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(); @@ -1285,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); @@ -1333,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(); } @@ -1348,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> @@ -1427,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) @@ -1446,9 +1514,14 @@ public: { unite(std::move(other)); } - void swap(QMultiHash &other) noexcept { qSwap(d, other.d); qSwap(m_size, other.m_size); } -#ifndef Q_CLANG_QDOC + 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 { @@ -1489,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; } @@ -1498,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 @@ -1519,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); @@ -1534,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); @@ -1565,6 +1654,7 @@ public: return t; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -1573,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); @@ -1672,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); @@ -1689,6 +1781,7 @@ public: return values; } +public: class const_iterator; class iterator @@ -1838,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) { @@ -1896,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(); @@ -1909,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(); @@ -1922,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); @@ -1951,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(); } @@ -1987,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); @@ -1995,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); @@ -2025,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); @@ -2042,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); @@ -2060,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(); @@ -2069,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()); @@ -2085,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()) { @@ -2120,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) { @@ -2179,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) |