diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 467 |
1 files changed, 355 insertions, 112 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 09766859a9..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 @@ -531,11 +532,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(); } @@ -557,17 +576,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) @@ -623,8 +641,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; @@ -661,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)); @@ -681,24 +700,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 @@ -707,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) { @@ -951,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); @@ -963,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); @@ -984,6 +1004,7 @@ public: return value; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -996,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); @@ -1230,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 { - 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(); @@ -1263,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(); @@ -1272,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); @@ -1335,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> @@ -1514,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); @@ -1529,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); @@ -1560,6 +1655,7 @@ public: return t; } +public: bool contains(const Key &key) const noexcept { if (!d) @@ -1568,75 +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()); + 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); @@ -1667,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); @@ -1684,6 +1782,7 @@ public: return values; } +public: class const_iterator; class iterator @@ -1895,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(); @@ -1908,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(); @@ -1921,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); @@ -1986,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); @@ -1994,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); @@ -2024,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); @@ -2041,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); @@ -2059,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(); @@ -2068,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()); @@ -2084,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()) { @@ -2119,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) { @@ -2178,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) |