diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 409 |
1 files changed, 323 insertions, 86 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index a4de3e377c..9cc6fbf30b 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -11,6 +11,7 @@ #include <QtCore/qiterator.h> #include <QtCore/qlist.h> #include <QtCore/qrefcount.h> +#include <QtCore/qttypetraits.h> #include <initializer_list> #include <functional> // for std::hash @@ -584,7 +585,7 @@ struct Data numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved)); 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) @@ -677,8 +678,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)); @@ -697,7 +700,7 @@ struct Data } } - Node *findNode(const Key &key) const noexcept + template <typename K> Node *findNode(const K &key) const noexcept { auto bucket = findBucket(key); if (bucket.isUnused()) @@ -711,7 +714,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) { @@ -955,6 +958,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); @@ -967,13 +975,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); @@ -988,6 +1004,7 @@ public: return value; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -1000,74 +1017,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); @@ -1234,28 +1245,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(); @@ -1267,7 +1275,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(); @@ -1276,6 +1284,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); @@ -1339,8 +1360,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> @@ -1518,6 +1596,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); @@ -1533,13 +1616,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); @@ -1564,6 +1655,7 @@ public: return t; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -1572,77 +1664,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()); + 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); @@ -1673,9 +1759,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); @@ -1690,6 +1782,7 @@ public: return values; } +public: class const_iterator; class iterator @@ -1901,7 +1994,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(); @@ -1914,11 +2009,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(); @@ -1927,6 +2018,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); @@ -1992,6 +2097,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); @@ -2000,8 +2110,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); @@ -2030,8 +2146,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); @@ -2047,8 +2169,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); @@ -2065,7 +2193,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(); @@ -2074,11 +2202,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()); @@ -2090,6 +2214,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()) { @@ -2125,29 +2264,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 = std::as_const(*this).equal_range(key); - return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); + 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) { @@ -2184,6 +2333,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) |