diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
| -rw-r--r-- | src/corelib/tools/qhash.h | 2570 |
1 files changed, 1564 insertions, 1006 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index d03f301306..cdf5577fcb 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -1,7 +1,6 @@ /**************************************************************************** ** -** Copyright (C) 2016 The Qt Company Ltd. -** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com> +** Copyright (C) 2020 The Qt Company Ltd. ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -41,218 +40,769 @@ #ifndef QHASH_H #define QHASH_H -#include <QtCore/qchar.h> #include <QtCore/qiterator.h> -#include <QtCore/qlist.h> +#include <QtCore/qvector.h> #include <QtCore/qrefcount.h> #include <QtCore/qhashfunctions.h> #include <QtCore/qcontainertools_impl.h> +#include <QtCore/qmath.h> -#include <algorithm> #include <initializer_list> -#if defined(Q_CC_MSVC) -#pragma warning( push ) -#pragma warning( disable : 4311 ) // disable pointer truncation warning -#pragma warning( disable : 4127 ) // conditional expression is constant -#endif - QT_BEGIN_NAMESPACE -struct Q_CORE_EXPORT QHashData +struct QHashDummyValue { - struct Node { - Node *next; - uint h; - }; + bool operator==(const QHashDummyValue &) const noexcept { return true; } +}; - Node *fakeNext; - Node **buckets; - QtPrivate::RefCount ref; - int size; - int nodeSize; - short userNumBits; - short numBits; - int numBuckets; - uint seed; - uint sharable : 1; - uint strictAlignment : 1; - uint reserved : 30; - - void *allocateNode(int nodeAlign); - void freeNode(void *node); - QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), - int nodeSize, int nodeAlign); - bool willGrow(); - void hasShrunk(); - void rehash(int hint); - void free_helper(void (*node_delete)(Node *)); - Node *firstNode(); -#ifdef QT_QHASH_DEBUG - void dump(); - void checkSanity(); -#endif - static Node *nextNode(Node *node); - static Node *previousNode(Node *node); +namespace QHashPrivate { - static const QHashData shared_null; -}; +// QHash uses a power of two growth policy. +namespace GrowthPolicy +{ +inline constexpr size_t maxNumBuckets() noexcept +{ + return size_t(1) << (8*sizeof(size_t) - 1); +} +inline constexpr size_t bucketsForCapacity(size_t requestedCapacity) noexcept +{ + if (requestedCapacity <= 8) + return 16; + if (requestedCapacity >= maxNumBuckets()) + return maxNumBuckets(); + return qNextPowerOfTwo(QIntegerForSize<sizeof(size_t)>::Unsigned(2*requestedCapacity - 1)); +} +inline constexpr size_t bucketForHash(size_t nBuckets, size_t hash) noexcept +{ + return hash & (nBuckets - 1); +} +} -inline bool QHashData::willGrow() +template <typename Key, typename T> +struct Node { - if (size >= numBuckets) { - rehash(numBits + 1); - return true; - } else { - return false; + using KeyType = Key; + using ValueType = T; + + Key key; + T value; + static Node create(Key &&k, T &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>) + { + return Node{ std::move(k), std::move(t) }; } -} + static Node create(const Key &k, const T &t) noexcept(std::is_nothrow_copy_constructible_v<Key> && std::is_nothrow_copy_constructible_v<T>) + { + return Node{ k, t }; + } + void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T>) + { + value = t; + } + void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>) + { + value = std::move(t); + } + T &&takeValue() noexcept(std::is_nothrow_move_assignable_v<T>) + { + return std::move(value); + } +}; -inline void QHashData::hasShrunk() +template <typename T> +struct MultiNodeChain { - if (size <= (numBuckets >> 3) && numBits > userNumBits) { - QT_TRY { - rehash(qMax(int(numBits) - 2, int(userNumBits))); - } QT_CATCH(const std::bad_alloc &) { - // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe. + T value; + MultiNodeChain *next = nullptr; + ~MultiNodeChain() + { + } + qsizetype free() noexcept(std::is_nothrow_destructible_v<T>) + { + qsizetype nEntries = 0; + MultiNodeChain *e = this; + while (e) { + MultiNodeChain *n = e->next; + ++nEntries; + delete e; + e = n; } + return nEntries; } -} + bool contains(const T &val) const noexcept + { + const MultiNodeChain *e = this; + while (e) { + if (e->value == val) + return true; + e = e->next; + } + return false; + } +}; -inline QHashData::Node *QHashData::firstNode() +template <typename Key, typename T> +struct MultiNode { - Node *e = reinterpret_cast<Node *>(this); - Node **bucket = buckets; - int n = numBuckets; - while (n--) { - if (*bucket != e) - return *bucket; - ++bucket; + using KeyType = Key; + using ValueType = T; + using Chain = MultiNodeChain<T>; + + Key key; + Chain *value; + + static MultiNode create(Key &&k, T &&t) + { + Chain *c = new Chain{ std::move(t), nullptr }; + return MultiNode(std::move(k), c); + } + static MultiNode create(const Key &k, const T &t) + { + Chain *c = new Chain{ t, nullptr }; + return MultiNode(k, c); } - return e; -} -struct QHashDummyValue -{ + MultiNode(const Key &k, Chain *c) + : key(k), + value(c) + {} + MultiNode(Key &&k, Chain *c) noexcept(std::is_nothrow_move_assignable_v<Key>) + : key(std::move(k)), + value(c) + {} + + MultiNode(MultiNode &&other) + : key(other.key), + value(other.value) + { + other.value = nullptr; + } + + MultiNode(const MultiNode &other) + : key(other.key) + { + Chain *c = other.value; + Chain **e = &value; + while (c) { + Chain *chain = new Chain{ c->value, nullptr }; + *e = chain; + e = &chain->next; + c = c->next; + } + } + ~MultiNode() + { + if (value) + value->free(); + } + static qsizetype freeChain(MultiNode *n) noexcept(std::is_nothrow_destructible_v<T>) + { + qsizetype size = n->value->free(); + n->value = nullptr; + return size; + } + void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T, T>) + { + value->value = t; + } + void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>) + { + value->value = std::move(t); + } + void insertMulti(const T &t) + { + Chain *e = new Chain{ t, nullptr }; + e->next = value; + value = e; + } + + // compiler generated move operators are fine }; -constexpr bool operator==(const QHashDummyValue &, const QHashDummyValue &) noexcept +template<typename Node> +constexpr bool isRelocatable() { - return true; + return QTypeInfo<typename Node::KeyType>::isRelocatable && QTypeInfo<typename Node::ValueType>::isRelocatable; } -Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE); +// Regular hash tables consist of a list of buckets that can store Nodes. But simply allocating one large array of buckets +// would waste a lot of memory. To avoid this, we split the vector of buckets up into a vector of Spans. Each Span represents +// NEntries buckets. To quickly find the correct Span that holds a bucket, NEntries must be a power of two. +// +// Inside each Span, there is an offset array that represents the actual buckets. offsets contains either an index into the +// actual storage space for the Nodes (the 'entries' member) or 0xff (UnusedEntry) to flag that the bucket is empty. +// As we have only 128 entries per Span, the offset array can be represented using an unsigned char. This trick makes the hash +// table have a very small memory overhead compared to many other implementations. +template<typename Node> +struct Span { + enum { + NEntries = 128, + LocalBucketMask = (NEntries - 1), + UnusedEntry = 0xff + }; + static_assert ((NEntries & LocalBucketMask) == 0, "EntriesPerSpan must be a power of two."); + + // Entry is a slot available for storing a Node. The Span holds a pointer to + // an array of Entries. Upon construction of the array, those entries are + // unused, and nextFree() is being used to set up a singly linked list + // of free entries. + // 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; + + unsigned char &nextFree() { return *reinterpret_cast<unsigned char *>(&storage); } + Node &node() { return *reinterpret_cast<Node *>(&storage); } + }; -template <class Key, class T> -struct QHashNode -{ - QHashNode *next; - const uint h; - const Key key; - T value; + unsigned char offsets[NEntries]; + Entry *entries = nullptr; + unsigned char allocated = 0; + unsigned char nextFree = 0; + Span() noexcept + { + memset(offsets, UnusedEntry, sizeof(offsets)); + } + ~Span() + { + freeData(); + } + void freeData() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (entries) { + if constexpr (!std::is_trivially_destructible<Node>::value) { + for (auto o : offsets) { + if (o != UnusedEntry) + entries[o].node().~Node(); + } + } + delete [] entries; + entries = nullptr; + } + } + void insert(size_t i, Node &&n) + { + Q_ASSERT(i <= NEntries); + Q_ASSERT(offsets[i] == UnusedEntry); + if (nextFree == allocated) + addStorage(); + unsigned char entry = nextFree; + Q_ASSERT(entry < allocated); + nextFree = entries[entry].nextFree(); + offsets[i] = entry; + new (&entries[entry].node()) Node(std::move(n)); + } + void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value) + { + Q_ASSERT(bucket <= NEntries); + Q_ASSERT(offsets[bucket] != UnusedEntry); - inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n) - : next(n), h(hash), key(key0), value(value0) {} - inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; } + unsigned char entry = offsets[bucket]; + offsets[bucket] = UnusedEntry; -private: - Q_DISABLE_COPY(QHashNode) + entries[entry].node().~Node(); + entries[entry].nextFree() = nextFree; + nextFree = entry; + } + size_t offset(size_t i) const noexcept + { + return offsets[i]; + } + bool hasNode(size_t i) const noexcept + { + return (offsets[i] != UnusedEntry); + } + Node &at(size_t i) noexcept + { + Q_ASSERT(i <= NEntries); + Q_ASSERT(offsets[i] != UnusedEntry); + + return entries[offsets[i]].node(); + } + const Node &at(size_t i) const noexcept + { + Q_ASSERT(i <= NEntries); + Q_ASSERT(offsets[i] != UnusedEntry); + + return entries[offsets[i]].node(); + } + Node &atOffset(size_t o) noexcept + { + Q_ASSERT(o < allocated); + + return entries[o].node(); + } + const Node &atOffset(size_t o) const noexcept + { + Q_ASSERT(o < allocated); + + return entries[o].node(); + } + void moveLocal(size_t from, size_t to) noexcept + { + Q_ASSERT(offsets[from] != UnusedEntry); + Q_ASSERT(offsets[to] == UnusedEntry); + offsets[to] = offsets[from]; + offsets[from] = UnusedEntry; + } + void moveFromSpan(Span &fromSpan, size_t fromIndex, size_t to) noexcept(std::is_nothrow_move_constructible_v<Node>) + { + Q_ASSERT(to <= NEntries); + Q_ASSERT(offsets[to] == UnusedEntry); + Q_ASSERT(fromIndex <= NEntries); + Q_ASSERT(fromSpan.offsets[fromIndex] != UnusedEntry); + if (nextFree == allocated) + addStorage(); + Q_ASSERT(nextFree < allocated); + offsets[to] = nextFree; + Entry &toEntry = entries[nextFree]; + nextFree = toEntry.nextFree(); + + size_t fromOffset = fromSpan.offsets[fromIndex]; + fromSpan.offsets[fromIndex] = UnusedEntry; + Entry &fromEntry = fromSpan.entries[fromOffset]; + + if constexpr (isRelocatable<Node>()) { + memcpy(&toEntry, &fromEntry, sizeof(Entry)); + } else { + new (&toEntry.node()) Node(std::move(fromEntry.node())); + fromEntry.node().~Node(); + } + fromEntry.nextFree() = fromSpan.nextFree; + fromSpan.nextFree = static_cast<unsigned char>(fromOffset); + } + + void addStorage() + { + Q_ASSERT(allocated < NEntries); + Q_ASSERT(nextFree == allocated); + // the hash table should always be between 25 and 50% full + // this implies that we on average have between 32 and 64 entries + // in here. The likelihood of having below 16 entries is very small, + // so start with that and increment by 16 each time we need to add + // some more space + const size_t increment = NEntries/8; + size_t alloc = allocated + increment; + Entry *newEntries = new Entry[alloc]; + // we only add storage if the previous storage was fully filled, so + // simply copy the old data over + if constexpr (isRelocatable<Node>()) { + memcpy(newEntries, entries, allocated*sizeof(Entry)); + } else { + for (size_t i = 0; i < allocated; ++i) { + new (&newEntries[i].node()) Node(std::move(entries[i].node())); + entries[i].node().~Node(); + } + } + for (size_t i = allocated; i < allocated + increment; ++i) { + newEntries[i].nextFree() = uchar(i + 1); + } + delete [] entries; + entries = newEntries; + allocated = uchar(alloc); + } }; -// Specialize for QHashDummyValue in order to save some memory -template <class Key> -struct QHashNode<Key, QHashDummyValue> +template <typename Node> +struct iterator; + +template <typename Node> +struct Data { - union { - QHashNode *next; - QHashDummyValue value; - }; - const uint h; - const Key key; + using Key = typename Node::KeyType; + using T = typename Node::ValueType; + using Span = QHashPrivate::Span<Node>; + using iterator = QHashPrivate::iterator<Node>; - inline QHashNode(const Key &key0, const QHashDummyValue &, uint hash, QHashNode *n) - : next(n), h(hash), key(key0) {} - inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; } + QtPrivate::RefCount ref = {{1}}; + size_t size = 0; + size_t numBuckets = 0; + size_t seed = 0; -private: - Q_DISABLE_COPY(QHashNode) + + Span *spans = nullptr; + + Data(size_t reserve = 0) + { + numBuckets = GrowthPolicy::bucketsForCapacity(reserve); + size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries; + spans = new Span[nSpans]; + seed = qGlobalQHashSeed(); + } + Data(const Data &other) + : size(other.size), + numBuckets(other.numBuckets), + seed(other.seed) + { + size_t nSpans = (other.numBuckets + Span::LocalBucketMask) / Span::NEntries; + spans = new Span[nSpans]; + + for (size_t s = 0; s < nSpans; ++s) { + const Span &span = other.spans[s]; + for (size_t index = 0; index < Span::NEntries; ++index) { + if (!span.hasNode(index)) + continue; + const Node &n = span.at(index); + iterator it{ this, s*Span::NEntries + index }; + Q_ASSERT(it.isUnused()); + + spans[it.span()].insert(it.index(), std::move(Node(n))); + } + } + } + Data(const Data &other, size_t reserved) + : size(other.size), + seed(other.seed) + { + numBuckets = GrowthPolicy::bucketsForCapacity(qMax(size, reserved)); + size_t nSpans = (numBuckets + Span::LocalBucketMask) / Span::NEntries; + spans = new Span[nSpans]; + + for (size_t s = 0; s < nSpans; ++s) { + const Span &span = other.spans[s]; + for (size_t index = 0; index < Span::NEntries; ++index) { + if (!span.hasNode(index)) + continue; + const Node &n = span.at(index); + iterator it = find(n.key); + Q_ASSERT(it.isUnused()); + spans[it.span()].insert(it.index(), std::move(Node(n))); + } + } + } + + 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); + Data *dd = new Data(*d, size); + if (!d->ref.deref()) + delete d; + return dd; + } + + + iterator detachedIterator(iterator other) const noexcept + { + return iterator{this, other.bucket}; + } + + iterator begin() const noexcept + { + iterator it{ this, 0 }; + if (it.isUnused()) + ++it; + return it; + } + + constexpr iterator end() const noexcept + { + return iterator(); + } + + void rehash(size_t sizeHint = 0) + { + if (sizeHint == 0) + sizeHint = size; + size_t newBucketCount = GrowthPolicy::bucketsForCapacity(sizeHint); + + Span *oldSpans = spans; + size_t oldBucketCount = numBuckets; + size_t nSpans = (newBucketCount + Span::LocalBucketMask) / Span::NEntries; + spans = new Span[nSpans]; + numBuckets = newBucketCount; + size_t oldNSpans = (oldBucketCount + Span::LocalBucketMask) / Span::NEntries; + + for (size_t s = 0; s < oldNSpans; ++s) { + Span &span = oldSpans[s]; + for (size_t index = 0; index < Span::NEntries; ++index) { + if (!span.hasNode(index)) + continue; + Node &n = span.at(index); + iterator it = find(n.key); + Q_ASSERT(it.isUnused()); + spans[it.span()].insert(it.index(), std::move(n)); + } + span.freeData(); + } + delete [] oldSpans; + } + + size_t nextBucket(size_t bucket) const noexcept + { + ++bucket; + if (bucket == numBuckets) + bucket = 0; + return bucket; + } + + float loadFactor() const noexcept + { + return float(size)/numBuckets; + } + bool shouldGrow() const noexcept + { + return size >= (numBuckets >> 1); + } + + iterator find(const Key &key) const noexcept + { + Q_ASSERT(numBuckets > 0); + size_t hash = qHash(key, seed); + size_t bucket = GrowthPolicy::bucketForHash(numBuckets, hash); + // loop over the buckets until we find the entry we search for + // or an empty slot, in which case we know the entry doesn't exist + while (true) { + // Split the bucket into the indexex of span array, and the local + // offset inside the span + size_t span = bucket / Span::NEntries; + size_t index = bucket & Span::LocalBucketMask; + Span &s = spans[span]; + size_t offset = s.offset(index); + if (offset == Span::UnusedEntry) { + return iterator{ this, bucket }; + } else { + Node &n = s.atOffset(offset); + if (n.key == key) + return iterator{ this, bucket }; + } + bucket = nextBucket(bucket); + } + } + + Node *findNode(const Key &key) const noexcept + { + if (!size) + return nullptr; + iterator it = find(key); + if (it.isUnused()) + return nullptr; + return it.node(); + } + + Node *findAndInsertNode(const Key &key) noexcept + { + if (shouldGrow()) + rehash(size + 1); + iterator it = find(key); + if (it.isUnused()) { + spans[it.span()].insert(it.index(), Node::create(key, T())); + ++size; + } + return it.node(); + } + + + iterator insert(Node &&n) + { + if (shouldGrow()) + rehash(size + 1); + iterator it = find(n.key); + if (it.isUnused()) { + spans[it.span()].insert(it.index(), std::move(n)); + ++size; + } else { + it.node()->replace(std::move(n.takeValue())); + } + return it; + } + + iterator insert(const Key &key, const T &value) + { + if (shouldGrow()) + rehash(size + 1); + auto it = find(key); + if (it.isUnused()) { + spans[it.span()].insert(it.index(), Node::create(key, value)); + ++size; + } else { + it.node()->replace(value); + } + return it; + } + + iterator insertMulti(const Key &key, const T &value) + { + if (shouldGrow()) + rehash(size + 1); + auto it = find(key); + if (it.isUnused()) { + spans[it.span()].insert(it.index(), std::move(Node::create(key, value))); + ++size; + } else { + it.node()->insertMulti(value); + } + return it; + } + + + iterator erase(iterator it) noexcept(std::is_nothrow_destructible<Node>::value) + { + size_t bucket = it.bucket; + size_t span = bucket / Span::NEntries; + size_t index = bucket & Span::LocalBucketMask; + Q_ASSERT(spans[span].hasNode(index)); + spans[span].erase(index); + --size; + + // re-insert the following entries to avoid holes + size_t hole = bucket; + size_t next = bucket; + while (true) { + next = nextBucket(next); + size_t nextSpan = next / Span::NEntries; + size_t nextIndex = next & Span::LocalBucketMask; + if (!spans[nextSpan].hasNode(nextIndex)) + break; + size_t hash = qHash(spans[nextSpan].at(nextIndex).key, seed); + size_t newBucket = GrowthPolicy::bucketForHash(numBuckets, hash); + while (true) { + if (newBucket == next) { + // nothing to do, item is at the right plae + break; + } else if (newBucket == hole) { + // move into hole + size_t holeSpan = hole / Span::NEntries; + size_t holeIndex = hole & Span::LocalBucketMask; + if (nextSpan == holeSpan) { + spans[holeSpan].moveLocal(nextIndex, holeIndex); + } else { + // move between spans, more expensive + spans[holeSpan].moveFromSpan(spans[nextSpan], nextIndex, holeIndex); + } + hole = next; + break; + } + newBucket = nextBucket(newBucket); + } + } + + // return correct position of the next element + if (!spans[span].hasNode(index)) + ++it; + return it; + } + + ~Data() + { + delete [] spans; + } }; +template <typename Node> +struct iterator { + using Span = QHashPrivate::Span<Node>; -#if 0 -// ### -// The introduction of the QHash random seed breaks this optimization, as it -// relies on qHash(int i) = i. If the hash value is salted, then the hash -// table becomes corrupted. -// -// A bit more research about whether it makes sense or not to salt integer -// keys (and in general keys whose hash value is easy to invert) -// is needed, or about how keep this optimization and the seed (f.i. by -// specializing QHash for integer values, and re-apply the seed during lookup). -// -// Be aware that such changes can easily be binary incompatible, and therefore -// cannot be made during the Qt 5 lifetime. -#define Q_HASH_DECLARE_INT_NODES(key_type) \ - template <class T> \ - struct QHashDummyNode<key_type, T> { \ - QHashDummyNode *next; \ - union { uint h; key_type key; }; \ -\ - inline QHashDummyNode(key_type /* key0 */) {} \ - }; \ -\ - template <class T> \ - struct QHashNode<key_type, T> { \ - QHashNode *next; \ - union { uint h; key_type key; }; \ - T value; \ -\ - inline QHashNode(key_type /* key0 */) {} \ - inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \ - inline bool same_key(uint h0, key_type) const { return h0 == h; } \ - } - -#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN -Q_HASH_DECLARE_INT_NODES(short); -Q_HASH_DECLARE_INT_NODES(ushort); -#endif -Q_HASH_DECLARE_INT_NODES(int); -Q_HASH_DECLARE_INT_NODES(uint); -#undef Q_HASH_DECLARE_INT_NODES -#endif // #if 0 + const Data<Node> *d = nullptr; + size_t bucket = 0; -template <class Key, class T> -class QHash -{ - typedef QHashNode<Key, T> Node; + size_t span() const noexcept { return bucket / Span::NEntries; } + size_t index() const noexcept { return bucket & Span::LocalBucketMask; } + inline bool isUnused() const noexcept { return !d->spans[span()].hasNode(index()); } - union { - QHashData *d; - QHashNode<Key, T> *e; - }; + inline Node *node() const noexcept + { + Q_ASSERT(!isUnused()); + return &d->spans[span()].at(index()); + } + bool atEnd() const noexcept { return !d; } - static inline Node *concrete(QHashData::Node *node) { - return reinterpret_cast<Node *>(node); + iterator operator++() noexcept + { + while (true) { + ++bucket; + if (bucket == d->numBuckets) { + d = nullptr; + bucket = 0; + break; + } + if (!isUnused()) + break; + } + return *this; } + bool operator==(iterator other) const noexcept + { return d == other.d && bucket == other.bucket; } + bool operator!=(iterator other) const noexcept + { return !(*this == other); } +}; + - static inline int alignOfNode() { return qMax<int>(sizeof(void*), alignof(Node)); } + +} // namespace QHashPrivate + +template <class Key, class T> +class QHash +{ + using Node = QHashPrivate::Node<Key, T>; + using Data = QHashPrivate::Data<Node>; + friend class QSet<Key>; + + Data *d = nullptr; public: - inline QHash() noexcept : d(const_cast<QHashData *>(&QHashData::shared_null)) { } + using key_type = Key; + using mapped_type = T; + using value_type = T; + using size_type = qsizetype; + using difference_type = qsizetype; + using reference = T &; + using const_reference = const T &; + + inline QHash() noexcept = default; inline QHash(std::initializer_list<std::pair<Key,T> > list) - : d(const_cast<QHashData *>(&QHashData::shared_null)) + : d(new Data(list.size())) { - reserve(int(list.size())); for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) insert(it->first, it->second); } - QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); } - ~QHash() { if (!d->ref.deref()) freeData(d); } + QHash(const QHash &other) noexcept + : d(other.d) + { + if (d) + d->ref.ref(); + } + ~QHash() + { + if (d && !d->ref.deref()) + delete d; + } + + QHash &operator=(const QHash &other) noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d != other.d) { + Data *o = other.d; + if (o) + o->ref.ref(); + if (d && !d->ref.deref()) + delete d; + d = o; + } + return *this; + } - QHash &operator=(const QHash &other); - QHash(QHash &&other) noexcept : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); } - QHash &operator=(QHash &&other) noexcept - { QHash moved(std::move(other)); swap(moved); return *this; } + QHash(QHash &&other) noexcept + : d(std::exchange(other.d, nullptr)) + { + } + QHash &operator=(QHash &&other) noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d != other.d) { + if (d && !d->ref.deref()) + delete d; + d = std::exchange(other.d, nullptr); + } + return *this; + } #ifdef Q_QDOC template <typename InputIterator> QHash(InputIterator f, InputIterator l); @@ -277,170 +827,220 @@ public: #endif void swap(QHash &other) noexcept { qSwap(d, other.d); } - bool operator==(const QHash &other) const; - bool operator!=(const QHash &other) const { return !(*this == other); } + bool operator==(const QHash &other) const noexcept + { + if (d == other.d) + return true; + if (size() != other.size()) + return false; - inline int size() const { return d->size; } + for (const_iterator it = other.begin(); it != other.end(); ++it) { + const_iterator i = find(it.key()); + if (i == end() || !(i.value() == it.value())) + return false; + } + // all values must be the same as size is the same + return true; + } + bool operator!=(const QHash &other) const noexcept { return !(*this == other); } - inline bool isEmpty() const { return d->size == 0; } + inline qsizetype size() const noexcept { return d ? qsizetype(d->size) : 0; } + inline bool isEmpty() const noexcept { return !d || d->size == 0; } - inline int capacity() const { return d->numBuckets; } - void reserve(int size); - inline void squeeze() { reserve(1); } + inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; } + void reserve(qsizetype size) + { + if (isDetached()) + d->rehash(size); + else + d = Data::detached(d, size_t(size)); + } + inline void squeeze() { reserve(0); } + + inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); } + inline bool isDetached() const noexcept { return d && !d->ref.isShared(); } + bool isSharedWith(const QHash &other) const noexcept { return d == other.d; } + + void clear() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d && !d->ref.deref()) + delete d; + d = nullptr; + } - inline void detach() { if (d->ref.isShared()) detach_helper(); } - inline bool isDetached() const { return !d->ref.isShared(); } - bool isSharedWith(const QHash &other) const { return d == other.d; } + bool remove(const Key &key) + { + if (isEmpty()) // prevents detaching shared null + return false; + detach(); - void clear(); + auto it = d->find(key); + if (it.isUnused()) + return false; + d->erase(it); + return true; + } + T take(const Key &key) + { + if (isEmpty()) // prevents detaching shared null + return T(); + detach(); - int remove(const Key &key); - T take(const Key &key); + auto it = d->find(key); + if (it.isUnused()) + return T(); + T value = it.node()->takeValue(); + d->erase(it); + return value; + } - bool contains(const Key &key) const; - Key key(const T &value) const; - Key key(const T &value, const Key &defaultKey) const; - T value(const Key &key) const; - T value(const Key &key, const T &defaultValue) const; - T &operator[](const Key &key); - const T operator[](const Key &key) const; + bool contains(const Key &key) const noexcept + { + if (!d) + return false; + return d->findNode(key) != nullptr; + } + qsizetype count(const Key &key) const noexcept + { + return contains(key) ? 1 : 0; + } - QList<Key> keys() const; - QList<Key> keys(const T &value) const; - QList<T> values() const; -#if QT_DEPRECATED_SINCE(5, 15) - QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<Key> uniqueKeys() const; - QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<T> values(const Key &key) const; -#endif - int count(const Key &key) const; + Key key(const T &value, const Key &defaultKey = Key()) const noexcept + { + if (d) { + const_iterator i = begin(); + while (i != end()) { + if (i.value() == value) + return i.key(); + ++i; + } + } + + return defaultKey; + } + T value(const Key &key, const T &defaultValue = T()) const noexcept + { + if (d) { + Node *n = d->findNode(key); + if (n) + return n->value; + } + return defaultValue; + } + T &operator[](const Key &key) + { + detach(); + Node *n = d->findAndInsertNode(key); + Q_ASSERT(n); + return n->value; + } + + const T operator[](const Key &key) const noexcept + { + return value(key); + } + + QVector<Key> keys() const + { + return QVector<Key>(keyBegin(), keyEnd()); + } + QVector<Key> keys(const T &value) const + { + QVector<Key> res; + const_iterator i = begin(); + while (i != end()) { + if (i.value() == value) + res.append(i.key()); + ++i; + } + return res; + } + QVector<T> values() const + { + return QVector<T>(begin(), end()); + } class const_iterator; class iterator { + using piter = typename QHashPrivate::iterator<Node>; friend class const_iterator; friend class QHash<Key, T>; friend class QSet<Key>; - QHashData::Node *i; + piter i; + explicit inline iterator(piter it) noexcept : i(it) { } public: -#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0) - typedef std::bidirectional_iterator_tag iterator_category; -#else typedef std::forward_iterator_tag iterator_category; -#endif typedef qptrdiff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; - inline iterator() : i(nullptr) { } - explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } + constexpr iterator() noexcept = default; - inline const Key &key() const { return concrete(i)->key; } - inline T &value() const { return concrete(i)->value; } - inline T &operator*() const { return concrete(i)->value; } - inline T *operator->() const { return &concrete(i)->value; } - inline bool operator==(const iterator &o) const { return i == o.i; } - inline bool operator!=(const iterator &o) const { return i != o.i; } + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return i.node()->value; } + inline T &operator*() const noexcept { return i.node()->value; } + inline T *operator->() const noexcept { return &i.node()->value; } + inline bool operator==(const iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const iterator &o) const noexcept { return i != o.i; } - inline iterator &operator++() { - i = QHashData::nextNode(i); - return *this; - } - inline iterator operator++(int) { - iterator r = *this; - i = QHashData::nextNode(i); - return r; - } -#if QT_DEPRECATED_SINCE(5, 15) - inline QT_DEPRECATED_VERSION_5_15 iterator &operator--() + inline iterator &operator++() noexcept { - i = QHashData::previousNode(i); + ++i; return *this; } - inline QT_DEPRECATED_VERSION_5_15 iterator operator--(int) + inline iterator operator++(int) noexcept { iterator r = *this; - i = QHashData::previousNode(i); + ++i; return r; } - inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j) const - { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline QT_DEPRECATED_VERSION_5_15 iterator operator-(int j) const { return operator+(-j); } - inline QT_DEPRECATED_VERSION_5_15 iterator &operator+=(int j) { return *this = *this + j; } - inline QT_DEPRECATED_VERSION_5_15 iterator &operator-=(int j) { return *this = *this - j; } - friend inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j, iterator k) { return k + j; } -#endif - inline bool operator==(const const_iterator &o) const { return i == o.i; } - inline bool operator!=(const const_iterator &o) const { return i != o.i; } + inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; } }; friend class iterator; class const_iterator { + using piter = typename QHashPrivate::iterator<Node>; friend class iterator; friend class QHash<Key, T>; - friend class QMultiHash<Key, T>; friend class QSet<Key>; - QHashData::Node *i; + piter i; + explicit inline const_iterator(piter it) : i(it) { } public: -#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0) - typedef std::bidirectional_iterator_tag iterator_category; -#else typedef std::forward_iterator_tag iterator_category; -#endif typedef qptrdiff difference_type; typedef T value_type; typedef const T *pointer; typedef const T &reference; - Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } - explicit inline const_iterator(void *node) - : i(reinterpret_cast<QHashData::Node *>(node)) { } - inline const_iterator(const iterator &o) - { i = o.i; } - - inline const Key &key() const { return concrete(i)->key; } - inline const T &value() const { return concrete(i)->value; } - inline const T &operator*() const { return concrete(i)->value; } - inline const T *operator->() const { return &concrete(i)->value; } - Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } - Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } - - inline const_iterator &operator++() { - i = QHashData::nextNode(i); - return *this; - } - inline const_iterator operator++(int) { - const_iterator r = *this; - i = QHashData::nextNode(i); - return r; - } -#if QT_DEPRECATED_SINCE(5, 15) - inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator--() + constexpr const_iterator() noexcept = default; + inline const_iterator(const iterator &o) noexcept : i(o.i) { } + + inline const Key &key() const noexcept { return i.node()->key; } + inline const T &value() const noexcept { return i.node()->value; } + inline const T &operator*() const noexcept { return i.node()->value; } + inline const T *operator->() const noexcept { return &i.node()->value; } + inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; } + inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; } + + inline const_iterator &operator++() noexcept { - i = QHashData::previousNode(i); + ++i; return *this; } - inline QT_DEPRECATED_VERSION_5_15 const_iterator operator--(int) + inline const_iterator operator++(int) noexcept { const_iterator r = *this; - i = QHashData::previousNode(i); + ++i; return r; } - inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j) const - { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline QT_DEPRECATED_VERSION_5_15 const_iterator operator-(int j) const { return operator+(-j); } - inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator+=(int j) { return *this = *this + j; } - inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator-=(int j) { return *this = *this - j; } - friend inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j, const_iterator k) - { - return k + j; - } -#endif }; friend class const_iterator; @@ -450,641 +1050,744 @@ public: public: typedef typename const_iterator::iterator_category iterator_category; - typedef typename const_iterator::difference_type difference_type; + typedef qptrdiff difference_type; typedef Key value_type; typedef const Key *pointer; typedef const Key &reference; - key_iterator() = default; - explicit key_iterator(const_iterator o) : i(o) { } + key_iterator() noexcept = default; + explicit key_iterator(const_iterator o) noexcept : i(o) { } - const Key &operator*() const { return i.key(); } - const Key *operator->() const { return &i.key(); } - bool operator==(key_iterator o) const { return i == o.i; } - bool operator!=(key_iterator o) const { return i != o.i; } + const Key &operator*() const noexcept { return i.key(); } + const Key *operator->() const noexcept { return &i.key(); } + bool operator==(key_iterator o) const noexcept { return i == o.i; } + bool operator!=(key_iterator o) const noexcept { return i != o.i; } - inline key_iterator &operator++() { ++i; return *this; } - inline key_iterator operator++(int) { return key_iterator(i++);} -#if QT_DEPRECATED_SINCE(5, 15) - inline QT_DEPRECATED_VERSION_5_15 key_iterator &operator--() - { - --i; - return *this; - } - inline QT_DEPRECATED_VERSION_5_15 key_iterator operator--(int) { return key_iterator(i--); } -#endif - const_iterator base() const { return i; } + inline key_iterator &operator++() noexcept { ++i; return *this; } + inline key_iterator operator++(int) noexcept { return key_iterator(i++);} + const_iterator base() const noexcept { return i; } }; typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; // STL style - inline iterator begin() { detach(); return iterator(d->firstNode()); } - inline const_iterator begin() const { return const_iterator(d->firstNode()); } - inline const_iterator cbegin() const { return const_iterator(d->firstNode()); } - inline const_iterator constBegin() const { return const_iterator(d->firstNode()); } - inline iterator end() { detach(); return iterator(e); } - inline const_iterator end() const { return const_iterator(e); } - inline const_iterator cend() const { return const_iterator(e); } - inline const_iterator constEnd() const { return const_iterator(e); } - inline key_iterator keyBegin() const { return key_iterator(begin()); } - inline key_iterator keyEnd() const { return key_iterator(end()); } + inline iterator begin() { detach(); return iterator(d->begin()); } + inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline iterator end() noexcept { return iterator(); } + inline const_iterator end() const noexcept { return const_iterator(); } + inline const_iterator cend() const noexcept { return const_iterator(); } + inline const_iterator constEnd() const noexcept { return const_iterator(); } + inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); } + inline key_iterator keyEnd() const noexcept { return key_iterator(end()); } inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } - inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } - inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } - inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } + inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + 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()); } - QPair<iterator, iterator> equal_range(const Key &key); - QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept; - iterator erase(iterator it) { return erase(const_iterator(it.i)); } - iterator erase(const_iterator it); + iterator erase(const_iterator it) + { + Q_ASSERT(it != constEnd()); + detach(); + // ensure a valid iterator across the detach: + iterator i = iterator{d->detachedIterator(it.i)}; - // more Qt - typedef iterator Iterator; - typedef const_iterator ConstIterator; - inline int count() const { return d->size; } - iterator find(const Key &key); - const_iterator find(const Key &key) const; - const_iterator constFind(const Key &key) const; - iterator insert(const Key &key, const T &value); - void insert(const QHash &hash); -#if QT_DEPRECATED_SINCE(5, 15) - QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); - QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QHash &unite(const QHash &other); -#endif + i.i = d->erase(i.i); + return i; + } - // STL compatibility - typedef T mapped_type; - typedef Key key_type; - typedef qptrdiff difference_type; - typedef int size_type; + QPair<iterator, iterator> equal_range(const Key &key) + { + auto first = find(key); + auto second = first; + if (second != iterator()) + ++second; + return qMakePair(first, second); + } - inline bool empty() const { return isEmpty(); } + QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept + { + auto first = find(key); + auto second = first; + if (second != iterator()) + ++second; + return qMakePair(first, second); + } -#ifdef QT_QHASH_DEBUG - inline void dump() const { d->dump(); } - inline void checkSanity() const { d->checkSanity(); } -#endif + typedef iterator Iterator; + typedef const_iterator ConstIterator; + inline qsizetype count() const noexcept { return d ? qsizetype(d->size) : 0; } + iterator find(const Key &key) + { + if (isEmpty()) // prevents detaching shared null + return end(); + detach(); + auto it = d->find(key); + if (it.isUnused()) + it = d->end(); + return iterator(it); + } + const_iterator find(const Key &key) const noexcept + { + if (isEmpty()) + return end(); + auto it = d->find(key); + if (it.isUnused()) + it = d->end(); + return const_iterator(it); + } + const_iterator constFind(const Key &key) const noexcept + { + return find(key); + } + iterator insert(const Key &key, const T &value) + { + detach(); -private: - void detach_helper(); - void freeData(QHashData *d); - Node **findNode(const Key &key, uint *hp = nullptr) const; - Node **findNode(const Key &key, uint h) const; - Node *createNode(uint h, const Key &key, const T &value, Node **nextNode); - void deleteNode(Node *node); - static void deleteNode2(QHashData::Node *node); - - static void duplicateNode(QHashData::Node *originalNode, void *newNode); - - bool isValidIterator(const iterator &it) const noexcept - { return isValidNode(it.i); } - bool isValidIterator(const const_iterator &it) const noexcept - { return isValidNode(it.i); } - bool isValidNode(QHashData::Node *node) const noexcept - { -#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG) - while (node->next) - node = node->next; - return (static_cast<void *>(node) == d); -#else - Q_UNUSED(node); - return true; -#endif + auto i = d->insert(Node{key, value}); + return iterator(i); } - friend class QSet<Key>; - friend class QMultiHash<Key, T>; -}; + void insert(const QHash &hash) + { + if (d == hash.d || !hash.d) + return; + if (!d) { + *this = hash; + return; + } + detach(); -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node) -{ - deleteNode2(reinterpret_cast<QHashData::Node*>(node)); - d->freeNode(node); -} + for (auto it = hash.begin(); it != hash.end(); ++it) + insert(it.key(), it.value()); + } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node) -{ -#ifdef Q_CC_BOR - concrete(node)->~QHashNode<Key, T>(); -#else - concrete(node)->~Node(); -#endif -} + 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(); } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode) -{ - Node *concreteNode = concrete(node); - new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr); -} + inline bool empty() const noexcept { return isEmpty(); } +}; -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::Node * -QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode) -{ - Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode); - *anextNode = node; - ++d->size; - return node; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) -{ - x->free_helper(deleteNode2); -} template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::clear() +class QMultiHash { - *this = QHash(); -} + using Node = QHashPrivate::MultiNode<Key, T>; + using Data = QHashPrivate::Data<Node>; + using Chain = QHashPrivate::MultiNodeChain<T>; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper() -{ - QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode()); - if (!d->ref.deref()) - freeData(d); - d = x; -} + Data *d = nullptr; + qsizetype m_size = 0; -template <class Key, class T> -Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other) -{ - if (d != other.d) { - QHashData *o = other.d; - o->ref.ref(); - if (!d->ref.deref()) - freeData(d); - d = o; - if (!d->sharable) - detach_helper(); +public: + using key_type = Key; + using mapped_type = T; + using value_type = T; + using size_type = qsizetype; + using difference_type = qsizetype; + using reference = T &; + using const_reference = const T &; + + QMultiHash() noexcept = default; + inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) + : d(new Data(list.size())) + { + for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) + insert(it->first, it->second); } - return *this; -} - -template <class Key, class T> -Q_INLINE_TEMPLATE T QHash<Key, T>::value(const Key &akey) const -{ - Node *node; - if (d->size == 0 || (node = *findNode(akey)) == e) { - return T(); - } else { - return node->value; +#ifdef Q_QDOC + template <typename InputIterator> + QMultiHash(InputIterator f, InputIterator l); +#else + template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true> + QMultiHash(InputIterator f, InputIterator l) + { + QtPrivate::reserveIfForwardIterator(this, f, l); + for (; f != l; ++f) + insert(f.key(), f.value()); } -} -template <class Key, class T> -Q_INLINE_TEMPLATE T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const -{ - Node *node; - if (d->size == 0 || (node = *findNode(akey)) == e) { - return adefaultValue; - } else { - return node->value; + template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true> + QMultiHash(InputIterator f, InputIterator l) + { + QtPrivate::reserveIfForwardIterator(this, f, l); + for (; f != l; ++f) + insert(f->first, f->second); + } +#endif + QMultiHash(const QMultiHash &other) noexcept + : d(other.d), m_size(other.m_size) + { + if (d) + d->ref.ref(); + } + ~QMultiHash() + { + if (d && !d->ref.deref()) + delete d; } -} - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const -{ - QList<Key> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.key()); - ++i; - } - return res; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const -{ - QList<Key> res; - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - res.append(i.key()); - ++i; - } - return res; -} + QMultiHash &operator=(const QMultiHash &other) noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d != other.d) { + Data *o = other.d; + if (o) + o->ref.ref(); + if (d && !d->ref.deref()) + delete d; + d = o; + m_size = other.m_size; + } + return *this; + } + QMultiHash(QMultiHash &&other) noexcept : d(other.d), m_size(other.m_size) + { + other.d = nullptr; + other.m_size = 0; + } + QMultiHash &operator=(QMultiHash &&other) noexcept(std::is_nothrow_destructible<Node>::value) + { + QMultiHash moved(std::move(other)); + swap(moved); + return *this; + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE Key QHash<Key, T>::key(const T &avalue) const -{ - return key(avalue, Key()); -} + QMultiHash(const QHash<Key, T> &other) + : QMultiHash(other.begin(), other.end()) + {} + void swap(QMultiHash &other) noexcept { qSwap(d, other.d); qSwap(m_size, other.m_size); } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const -{ - const_iterator i = begin(); - while (i != end()) { - if (i.value() == avalue) - return i.key(); - ++i; + bool operator==(const QMultiHash &other) const noexcept + { + if (d == other.d) + return true; + if (!d || ! other.d) + return false; + if (m_size != other.m_size || d->size != other.d->size) + return false; + for (auto it = other.d->begin(); it != other.d->end(); ++it) { + auto i = d->find(it.node()->key); + if (i == d->end()) + return false; + Chain *e = it.node()->value; + while (e) { + Chain *oe = i.node()->value; + while (oe) { + if (oe->value == e->value) + break; + oe = oe->next; + } + if (!oe) + return false; + e = e->next; + } + } + // all values must be the same as size is the same + return true; } + bool operator!=(const QMultiHash &other) const noexcept { return !(*this == other); } - return defaultValue; -} + inline qsizetype size() const noexcept { return m_size; } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const -{ - QList<T> res; - res.reserve(size()); - const_iterator i = begin(); - while (i != end()) { - res.append(i.value()); - ++i; - } - return res; -} + inline bool isEmpty() const noexcept { return !m_size; } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const -{ - int cnt = 0; - Node *node = *findNode(akey); - if (node != e) { - do { - ++cnt; - } while ((node = node->next) != e && node->key == akey); - } - return cnt; -} + inline qsizetype capacity() const noexcept { return d ? qsizetype(d->numBuckets >> 1) : 0; } + void reserve(qsizetype size) + { + if (isDetached()) + d->rehash(size); + else + d = Data::detached(d, size_t(size)); + } + inline void squeeze() { reserve(0); } -template <class Key, class T> -Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const -{ - return value(akey); -} + inline void detach() { if (!d || d->ref.isShared()) d = Data::detached(d); } + inline bool isDetached() const noexcept { return d && !d->ref.isShared(); } + bool isSharedWith(const QMultiHash &other) const noexcept { return d == other.d; } -template <class Key, class T> -Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey) -{ - detach(); + void clear() noexcept(std::is_nothrow_destructible<Node>::value) + { + if (d && !d->ref.deref()) + delete d; + d = nullptr; + m_size = 0; + } - uint h; - Node **node = findNode(akey, &h); - if (*node == e) { - if (d->willGrow()) - node = findNode(akey, h); - return createNode(h, akey, T(), node)->value; + qsizetype remove(const Key &key) + { + if (isEmpty()) // prevents detaching shared null + return 0; + detach(); + + auto it = d->find(key); + if (it.isUnused()) + return 0; + qsizetype n = Node::freeChain(it.node()); + m_size -= n; + Q_ASSERT(m_size >= 0); + d->erase(it); + return n; } - return (*node)->value; -} + T take(const Key &key) + { + if (isEmpty()) // prevents detaching shared null + return T(); + detach(); -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey, - const T &avalue) -{ - detach(); + auto it = d->find(key); + if (it.isUnused()) + return T(); + Q_ASSERT(it.node()->value.size()); + Chain *e = it.node()->value; + Q_ASSERT(e); + if (!e->next) + d->erase(it); + else + it.node()->value = e->next; + --m_size; + Q_ASSERT(m_size >= 0); + T t = std::move(e->value); + delete e; + return t; + } - uint h; - Node **node = findNode(akey, &h); - if (*node == e) { - if (d->willGrow()) - node = findNode(akey, h); - return iterator(createNode(h, akey, avalue, node)); + bool contains(const Key &key) const noexcept + { + if (!d) + return false; + return d->findNode(key) != nullptr; } - if (!std::is_same<T, QHashDummyValue>::value) - (*node)->value = avalue; - return iterator(*node); -} + Key key(const T &value, const Key &defaultKey = Key()) 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; + ++i; + } + } -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash) -{ - if (d == hash.d) - return; - - detach(); - - QHashData::Node *i = hash.d->firstNode(); - QHashData::Node *end = reinterpret_cast<QHashData::Node *>(hash.e); - while (i != end) { - Node *n = concrete(i); - Node **node = findNode(n->key, n->h); - if (*node == e) { - if (d->willGrow()) - node = findNode(n->key, n->h); - createNode(n->h, n->key, n->value, node); - } else { - if (!std::is_same<T, QHashDummyValue>::value) - (*node)->value = n->value; + return defaultKey; + } + T value(const Key &key, const T &defaultValue = T()) const noexcept + { + if (d) { + Node *n = d->findNode(key); + if (n) { + Q_ASSERT(n->value); + return n->value->value; + } } - i = QHashData::nextNode(i); + return defaultValue; } -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey) -{ - if (isEmpty()) // prevents detaching shared null - return 0; - detach(); - - int oldSize = d->size; - Node **node = findNode(akey); - if (*node != e) { - bool deleteNext = true; - do { - Node *next = (*node)->next; - deleteNext = (next != e && next->key == (*node)->key); - deleteNode(*node); - *node = next; - --d->size; - } while (deleteNext); - d->hasShrunk(); - } - return oldSize - d->size; -} + T &operator[](const Key &key) + { + detach(); + Node *n = d->findAndInsertNode(key); + Q_ASSERT(n); + return n->value->value; + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey) -{ - if (isEmpty()) // prevents detaching shared null - return T(); - detach(); - - Node **node = findNode(akey); - if (*node != e) { - T t = std::move((*node)->value); - Node *next = (*node)->next; - deleteNode(*node); - *node = next; - --d->size; - d->hasShrunk(); - return t; + const T operator[](const Key &key) const noexcept + { + return value(key); } - return T(); -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it) -{ - Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid"); - - if (it == const_iterator(e)) - return iterator(it.i); - - if (d->ref.isShared()) { - // save 'it' across the detach: - int bucketNum = (it.i->h % d->numBuckets); - const_iterator bucketIterator(*(d->buckets + bucketNum)); - int stepsFromBucketStartToIte = 0; - while (bucketIterator != it) { - ++stepsFromBucketStartToIte; - ++bucketIterator; - } - detach(); - it = const_iterator(*(d->buckets + bucketNum)); - while (stepsFromBucketStartToIte > 0) { - --stepsFromBucketStartToIte; - ++it; + QVector<Key> uniqueKeys() const + { + QVector<Key> res; + if (d) { + auto i = d->begin(); + while (i != d->end()) { + res.append(i.node()->key); + ++i; + } } + return res; } - iterator ret(it.i); - ++ret; + QVector<Key> keys() const + { + return QVector<Key>(keyBegin(), keyEnd()); + } + QVector<Key> keys(const T &value) const + { + QVector<Key> res; + const_iterator i = begin(); + while (i != end()) { + if (i.value()->contains(value)) + res.append(i.key()); + ++i; + } + return res; + } + QVector<T> values() const + { + return QVector<T>(begin(), end()); + } + QVector<T> values(const Key &key) const + { + QVector<T> values; + if (d) { + Node *n = d->findNode(key); + if (n) { + Chain *e = n->value; + while (e) { + values.append(e->value); + e = e->next; + } + } + } + return values; + } - Node *node = concrete(it.i); - Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]); - while (*node_ptr != node) - node_ptr = &(*node_ptr)->next; - *node_ptr = node->next; - deleteNode(node); - --d->size; - return ret; -} + class const_iterator; -template <class Key, class T> -Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize) -{ - detach(); - d->rehash(-qMax(asize, 1)); -} + class iterator + { + using piter = typename QHashPrivate::iterator<Node>; + friend class const_iterator; + friend class QMultiHash<Key, T>; + piter i; + Chain **e = nullptr; + explicit inline iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry) + { + if (!it.atEnd() && !e) { + e = &it.node()->value; + Q_ASSERT(e && *e); + } + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const -{ - return const_iterator(*findNode(akey)); -} + public: + typedef std::forward_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef T *pointer; + typedef T &reference; -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const -{ - return const_iterator(*findNode(akey)); -} + constexpr iterator() noexcept = default; + + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return (*e)->value; } + inline T &operator*() const noexcept { return (*e)->value; } + inline T *operator->() const noexcept { return &(*e)->value; } + inline bool operator==(const iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const iterator &o) const noexcept { return e != o.e; } + + inline iterator &operator++() noexcept { + Q_ASSERT(e && *e); + e = &(*e)->next; + Q_ASSERT(e); + if (!*e) { + ++i; + e = i.atEnd() ? nullptr : &i.node()->value; + } + return *this; + } + inline iterator operator++(int) noexcept { + iterator r = *this; + ++(*this); + return r; + } -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey) -{ - detach(); - return iterator(*findNode(akey)); -} + inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; } + }; + friend class iterator; -template <class Key, class T> -Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const -{ - return *findNode(akey) != e; -} + class const_iterator + { + using piter = typename QHashPrivate::iterator<Node>; + friend class iterator; + friend class QMultiHash<Key, T>; + piter i; + Chain **e = nullptr; + explicit inline const_iterator(piter it, Chain **entry = nullptr) noexcept : i(it), e(entry) + { + if (!it.atEnd() && !e) { + e = &it.node()->value; + Q_ASSERT(e && *e); + } + } -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const -{ - Node **node; + public: + typedef std::forward_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef const T *pointer; + typedef const T &reference; - if (d->numBuckets) { - node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]); - Q_ASSERT(*node == e || (*node)->next); - while (*node != e && !(*node)->same_key(h, akey)) - node = &(*node)->next; - } else { - node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e)); - } - return node; -} + constexpr const_iterator() noexcept = default; + inline const_iterator(const iterator &o) noexcept : i(o.i), e(o.e) { } + + inline const Key &key() const noexcept { return i.node()->key; } + inline T &value() const noexcept { return (*e)->value; } + inline T &operator*() const noexcept { return (*e)->value; } + inline T *operator->() const noexcept { return &(*e)->value; } + inline bool operator==(const const_iterator &o) const noexcept { return e == o.e; } + inline bool operator!=(const const_iterator &o) const noexcept { return e != o.e; } + + inline const_iterator &operator++() noexcept { + Q_ASSERT(e && *e); + e = &(*e)->next; + Q_ASSERT(e); + if (!*e) { + ++i; + e = i.atEnd() ? nullptr : &i.node()->value; + } + return *this; + } + inline const_iterator operator++(int) noexcept + { + const_iterator r = *this; + ++(*this); + return r; + } + }; + friend class const_iterator; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, - uint *ahp) const -{ - uint h = 0; + class key_iterator + { + const_iterator i; - if (d->numBuckets || ahp) { - h = qHash(akey, d->seed); - if (ahp) - *ahp = h; - } - return findNode(akey, h); -} + public: + typedef typename const_iterator::iterator_category iterator_category; + typedef qptrdiff difference_type; + typedef Key value_type; + typedef const Key *pointer; + typedef const Key &reference; -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const -{ - if (d == other.d) - return true; - if (size() != other.size()) - return false; + key_iterator() noexcept = default; + explicit key_iterator(const_iterator o) noexcept : i(o) { } - const_iterator it = begin(); + const Key &operator*() const noexcept { return i.key(); } + const Key *operator->() const noexcept { return &i.key(); } + bool operator==(key_iterator o) const noexcept { return i == o.i; } + bool operator!=(key_iterator o) const noexcept { return i != o.i; } - while (it != end()) { - // Build two equal ranges for i.key(); one for *this and one for other. - // For *this we can avoid a lookup via equal_range, as we know the beginning of the range. - auto thisEqualRangeStart = it; - const Key &thisEqualRangeKey = it.key(); - size_type n = 0; - do { - ++it; - ++n; - } while (it != end() && it.key() == thisEqualRangeKey); + inline key_iterator &operator++() noexcept { ++i; return *this; } + inline key_iterator operator++(int) noexcept { return key_iterator(i++);} + const_iterator base() const noexcept { return i; } + }; - const auto otherEqualRange = other.equal_range(thisEqualRangeKey); + typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; + typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; - if (n != std::distance(otherEqualRange.first, otherEqualRange.second)) - return false; + // STL style + inline iterator begin() { detach(); return iterator(d->begin()); } + inline const_iterator begin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator cbegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline const_iterator constBegin() const noexcept { return d ? const_iterator(d->begin()): const_iterator(); } + inline iterator end() noexcept { return iterator(); } + inline const_iterator end() const noexcept { return const_iterator(); } + inline const_iterator cend() const noexcept { return const_iterator(); } + inline const_iterator constEnd() const noexcept { return const_iterator(); } + inline key_iterator keyBegin() const noexcept { return key_iterator(begin()); } + inline key_iterator keyEnd() const noexcept { return key_iterator(end()); } + inline key_value_iterator keyValueBegin() noexcept { return key_value_iterator(begin()); } + inline key_value_iterator keyValueEnd() noexcept { return key_value_iterator(end()); } + inline const_key_value_iterator keyValueBegin() const noexcept { return const_key_value_iterator(begin()); } + 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()); } + + iterator detach(const_iterator it) + { + auto i = it.i; + Chain **e = it.e; + if (d->ref.isShared()) { + // need to store iterator position before detaching + qsizetype n = 0; + Chain *entry = i.node()->value; + while (entry != *it.e) { + ++n; + entry = entry->next; + } + Q_ASSERT(entry); + detach_helper(); - // Keys in the ranges are equal by construction; this checks only the values. - if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second)) - return false; + i = d->detachedIterator(i); + e = &i.node()->value; + while (n) { + e = &(*e)->next; + --n; + } + Q_ASSERT(e && *e); + } + return iterator(i, e); } - return true; -} - -template <class Key, class T> -QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey) -{ - detach(); - auto pair = qAsConst(*this).equal_range(akey); - return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); -} - -template <class Key, class T> -QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept -{ - Node *node = *findNode(akey); - const_iterator firstIt = const_iterator(node); - - if (node != e) { - // equal keys must hash to the same value and so they all - // end up in the same bucket. So we can use node->next, - // which only works within a bucket, instead of (out-of-line) - // QHashData::nextNode() - while (node->next != e && node->next->key == akey) - node = node->next; - - // 'node' may be the last node in the bucket. To produce the end iterator, we'd - // need to enter the next bucket in this case, so we need to use - // QHashData::nextNode() here, which, unlike node->next above, can move between - // buckets. - node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node))); + iterator erase(const_iterator it) + { + Q_ASSERT(d); + iterator i = detach(it); + Chain *e = *i.e; + Chain *next = e->next; + *i.e = next; + delete e; + if (!next) { + if (i.e == &i.i.node()->value) { + // last remaining entry, erase + i = iterator(d->erase(i.i)); + } else { + i = iterator(++it.i); + } + } + --m_size; + Q_ASSERT(m_size >= 0); + return i; } - return qMakePair(firstIt, const_iterator(node)); -} - -template <class Key, class T> -class QMultiHash : public QHash<Key, T> -{ -public: - QMultiHash() noexcept {} - inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) + // more Qt + typedef iterator Iterator; + typedef const_iterator ConstIterator; + inline qsizetype count() const noexcept { return size(); } + iterator find(const Key &key) { - this->reserve(int(list.size())); - for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) - insert(it->first, it->second); + if (isEmpty()) + return end(); + detach(); + auto it = d->find(key); + if (it.isUnused()) + it = d->end(); + return iterator(it); } -#ifdef Q_QDOC - template <typename InputIterator> - QMultiHash(InputIterator f, InputIterator l); -#else - template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true> - QMultiHash(InputIterator f, InputIterator l) + const_iterator find(const Key &key) const noexcept { - QtPrivate::reserveIfForwardIterator(this, f, l); - for (; f != l; ++f) - insert(f.key(), f.value()); + return constFind(key); } - - template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true> - QMultiHash(InputIterator f, InputIterator l) + const_iterator constFind(const Key &key) const noexcept { - QtPrivate::reserveIfForwardIterator(this, f, l); - for (; f != l; ++f) - insert(f->first, f->second); + if (isEmpty()) + return end(); + auto it = d->find(key); + if (it.isUnused()) + it = d->end(); + return const_iterator(it); + } + iterator insert(const Key &key, const T &value) + { + detach(); + auto it = d->insertMulti(key, value); + ++m_size; + return iterator(it); } -#endif - // compiler-generated copy/move ctors/assignment operators are fine! - // compiler-generated destructor is fine! - - QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {} - QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {} - void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps - inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) - { return QHash<Key, T>::insert(key, value); } + 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(); } - typename QHash<Key, T>::iterator insert(const Key &key, const T &value); + inline bool empty() const noexcept { return isEmpty(); } - inline QMultiHash &unite(const QMultiHash &other); + inline typename QMultiHash<Key, T>::iterator replace(const Key &key, const T &value) + { + detach(); + qsizetype s = d->size; + auto it = d->insert(key, value); + m_size += d->size - s; + return iterator(it); + } inline QMultiHash &operator+=(const QMultiHash &other) - { return unite(other); } + { this->unite(other); return *this; } inline QMultiHash operator+(const QMultiHash &other) const { QMultiHash result = *this; result += other; return result; } - using QHash<Key, T>::contains; - using QHash<Key, T>::remove; - using QHash<Key, T>::count; - using QHash<Key, T>::find; - using QHash<Key, T>::constFind; - using QHash<Key, T>::values; - using QHash<Key, T>::findNode; - using QHash<Key, T>::createNode; - using QHash<Key, T>::concrete; - using QHash<Key, T>::detach; + bool contains(const Key &key, const T &value) const noexcept + { + if (isEmpty()) + return false; + auto n = d->findNode(key); + if (n == nullptr) + return false; + return n->value->contains(value); + } - using typename QHash<Key, T>::Node; - using typename QHash<Key, T>::iterator; - using typename QHash<Key, T>::const_iterator; + qsizetype remove(const Key &key, const T &value) + { + if (isEmpty()) // prevents detaching shared null + return false; + detach(); - bool contains(const Key &key, const T &value) const; + auto it = d->find(key); + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain **e = &it.node()->value; + while (*e) { + Chain *entry = *e; + if (entry->value == value) { + *e = entry->next; + delete entry; + ++n; + } else { + e = &entry->next; + } + } + if (!it.node()->value) + d->erase(it); + m_size -= n; + Q_ASSERT(m_size >= 0); + return n; + } - int remove(const Key &key, const T &value); + qsizetype count(const Key &key) const noexcept + { + auto it = d->find(key); + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain *e = it.node()->value; + while (e) { + ++n; + e = e->next; + } - int count(const Key &key, const T &value) const; + return n; + } - QList<Key> uniqueKeys() const; + qsizetype count(const Key &key, const T &value) const noexcept + { + auto it = d->find(key); + if (it.isUnused()) + return 0; + qsizetype n = 0; + Chain *e = it.node()->value; + while (e) { + if (e->value == value) + ++n; + e = e->next; + } - QList<T> values(const Key &akey) const; + return n; + } - typename QHash<Key, T>::iterator find(const Key &key, const T &value) { - typename QHash<Key, T>::iterator i(find(key)); - typename QHash<Key, T>::iterator end(this->end()); - while (i != end && i.key() == key) { - if (i.value() == value) - return i; - ++i; - } - return end; + iterator find(const Key &key, const T &value) + { + detach(); + auto it = constFind(key, value); + return iterator(it.i, it.e); } - typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const { - typename QHash<Key, T>::const_iterator i(constFind(key)); - typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); + 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 + { + const_iterator i(constFind(key)); + const_iterator end(constEnd()); while (i != end && i.key() == key) { if (i.value() == value) return i; @@ -1092,229 +1795,108 @@ public: } return end; } - typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const - { return find(key, value); } -private: - T &operator[](const Key &key); - const T operator[](const Key &key) const; -}; - -template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &akey, const T &avalue) -{ - detach(); - this->d->willGrow(); - - uint h; - Node **nextNode = findNode(akey, &h); - return iterator(createNode(h, akey, avalue, nextNode)); -} -template <class Key, class T> -Q_INLINE_TEMPLATE QMultiHash<Key, T> &QMultiHash<Key, T>::unite(const QMultiHash &other) -{ - if (this->d == &QHashData::shared_null) { - *this = other; - } else { -#if QT_DEPRECATED_SINCE(5, 15) - QMultiHash copy(other); - const_iterator it = copy.constEnd(); - while (it != copy.constBegin()) { - it.i = QHashData::previousNode(it.i); - insert(it.key(), it.value()); - } -#else - const QMultiHash copy(other); - const_iterator it = copy.cbegin(); - const const_iterator end = copy.cend(); - while (it != end) { - const auto rangeStart = it++; - while (it != end && rangeStart.key() == it.key()) - ++it; - const qint64 last = std::distance(rangeStart, it) - 1; - for (qint64 i = last; i >= 0; --i) { - auto next = std::next(rangeStart, i); - insert(next.key(), next.value()); - } + QMultiHash &unite(const QMultiHash &other) + { + if (isEmpty()) { + *this = other; + } else if (other.isEmpty()) { + ; + } else { + QMultiHash copy(other); + detach(); + for (auto cit = copy.cbegin(); cit != copy.cend(); ++cit) + insert(cit.key(), *cit); } -#endif + return *this; } - return *this; -} - - -template <class Key, class T> -Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const -{ - return constFind(key, value) != QHash<Key, T>::constEnd(); -} -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value) -{ - int n = 0; - typename QHash<Key, T>::iterator i(find(key)); - typename QHash<Key, T>::iterator end(QHash<Key, T>::end()); - while (i != end && i.key() == key) { - if (i.value() == value) { - i = this->erase(i); - ++n; - } else { - ++i; - } + QPair<iterator, iterator> equal_range(const Key &key) + { + detach(); + auto pair = qAsConst(*this).equal_range(key); + return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); } - return n; -} -template <class Key, class T> -Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const -{ - int n = 0; - typename QHash<Key, T>::const_iterator i(constFind(key)); - typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); - while (i != end && i.key() == key) { - if (i.value() == value) - ++n; - ++i; + QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept + { + auto it = d->find(key); + if (it.isUnused()) + return qMakePair(end(), end()); + auto end = it; + ++end; + return qMakePair(const_iterator(it), const_iterator(end)); } - return n; -} -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMultiHash<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(QHash<Key, T>::size()); // May be too much, but assume short lifetime - typename QHash<Key, T>::const_iterator i = QHash<Key, T>::begin(); - if (i != QHash<Key, T>::end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == QHash<Key, T>::end()) - goto break_out_of_outer_loop; - } while (aKey == i.key()); +private: + void detach_helper() + { + if (!d) { + d = new Data; + return; } + Data *dd = new Data(*d); + if (!d->ref.deref()) + delete d; + d = dd; } -break_out_of_outer_loop: - return res; -} - -#if QT_DEPRECATED_SINCE(5, 15) - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) { - return static_cast<QMultiHash<Key, T> *>(this)->insert(key, value); -} - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) { - return static_cast<QMultiHash<Key, T> *>(this)->unite(other); -} - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const -{ - return static_cast<const QMultiHash<Key, T> *>(this)->values(akey); -} - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const -{ - return static_cast<const QMultiHash<Key, T> *>(this)->uniqueKeys(); -} -#endif - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMultiHash<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *node = *findNode(akey); - if (node != this->e) { - do { - res.append(node->value); - } while ((node = node->next) != this->e && node->key == akey); - } - return res; -} +}; #if !defined(QT_NO_JAVA_STYLE_ITERATORS) -template <class Key, class T> +template<class Key, class T> class QHashIterator { typedef typename QHash<Key, T>::const_iterator const_iterator; typedef const_iterator Item; QHash<Key, T> c; const_iterator i, n; - inline bool item_exists() const { return n != c.constEnd(); } + inline bool item_exists() const noexcept { return n != c.constEnd(); } public: - inline QHashIterator(const QHash<Key, T> &container) + inline QHashIterator(const QHash<Key, T> &container) noexcept : c(container), i(c.constBegin()), n(c.constEnd()) - { - } - inline QHashIterator &operator=(const QHash<Key, T> &container) + { } + inline QHashIterator &operator=(const QHash<Key, T> &container) noexcept { c = container; i = c.constBegin(); n = c.constEnd(); return *this; } - inline void toFront() + inline void toFront() noexcept { i = c.constBegin(); n = c.constEnd(); } - inline void toBack() + inline void toBack() noexcept { i = c.constEnd(); n = c.constEnd(); } - inline bool hasNext() const { return i != c.constEnd(); } - inline Item next() + inline bool hasNext() const noexcept { return i != c.constEnd(); } + inline Item next() noexcept { n = i++; return n; } - inline Item peekNext() const { return i; } - inline const T &value() const + inline Item peekNext() const noexcept { return i; } + inline const T &value() const noexcept { Q_ASSERT(item_exists()); return *n; } - inline const Key &key() const + inline const Key &key() const noexcept { Q_ASSERT(item_exists()); return n.key(); } - inline bool findNext(const T &t) + inline bool findNext(const T &t) noexcept { while ((n = i) != c.constEnd()) if (*i++ == t) return true; return false; } -#if QT_DEPRECATED_SINCE(5, 15) - inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return i != c.constBegin(); } - inline QT_DEPRECATED_VERSION_5_15 Item previous() - { - n = --i; - return n; - } - inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const - { - const_iterator p = i; - return --p; - } - inline bool QT_DEPRECATED_VERSION_5_15 findPrevious(const T &t) - { - while (i != c.constBegin()) - if (*(n = --i) == t) - return true; - n = c.constEnd(); - return false; - } -#endif }; template<class Key, class T> @@ -1325,10 +1907,11 @@ class QMutableHashIterator typedef iterator Item; QHash<Key, T> *c; iterator i, n; - inline bool item_exists() const { return const_iterator(n) != c->constEnd(); } + inline bool item_exists() const noexcept { return const_iterator(n) != c->constEnd(); } public: - inline QMutableHashIterator(QHash<Key, T> &container) : c(&container) + inline QMutableHashIterator(QHash<Key, T> &container) + : c(&container) { i = c->begin(); n = c->end(); @@ -1345,18 +1928,18 @@ public: i = c->begin(); n = c->end(); } - inline void toBack() + inline void toBack() noexcept { i = c->end(); n = c->end(); } - inline bool hasNext() const { return const_iterator(i) != c->constEnd(); } - inline Item next() + inline bool hasNext() const noexcept { return const_iterator(i) != c->constEnd(); } + inline Item next() noexcept { n = i++; return n; } - inline Item peekNext() const { return i; } + inline Item peekNext() const noexcept { return i; } inline void remove() { if (const_iterator(n) != c->constEnd()) { @@ -1369,49 +1952,28 @@ public: if (const_iterator(n) != c->constEnd()) *n = t; } - inline T &value() + inline T &value() noexcept { Q_ASSERT(item_exists()); return *n; } - inline const T &value() const + inline const T &value() const noexcept { Q_ASSERT(item_exists()); return *n; } - inline const Key &key() const + inline const Key &key() const noexcept { Q_ASSERT(item_exists()); return n.key(); } - inline bool findNext(const T &t) + inline bool findNext(const T &t) noexcept { while (const_iterator(n = i) != c->constEnd()) if (*i++ == t) return true; return false; } -#if QT_DEPRECATED_SINCE(5, 15) - inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return const_iterator(i) != c->constBegin(); } - inline QT_DEPRECATED_VERSION_5_15 Item previous() - { - n = --i; - return n; - } - inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const - { - iterator p = i; - return --p; - } - inline QT_DEPRECATED_VERSION_5_15 bool findPrevious(const T &t) - { - while (const_iterator(i) != c->constBegin()) - if (*(n = --i) == t) - return true; - n = c->end(); - return false; - } -#endif }; #endif // !QT_NO_JAVA_STYLE_ITERATORS @@ -1438,8 +2000,4 @@ inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0) QT_END_NAMESPACE -#if defined(Q_CC_MSVC) -#pragma warning( pop ) -#endif - #endif // QHASH_H |