diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 479 |
1 files changed, 385 insertions, 94 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 236e433101..0b8a0b283d 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -308,12 +308,14 @@ public: T &operator[](const Key &key); const T operator[](const Key &key) const; - QList<Key> uniqueKeys() const; QList<Key> keys() const; QList<Key> keys(const T &value) const; QList<T> values() const; - QList<T> values(const Key &key) const; - int count(const Key &key) const; +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QList<Key> uniqueKeys() const; + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QList<T> values(const Key &key) const; + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") int count(const Key &key) const; +#endif class const_iterator; @@ -325,7 +327,11 @@ public: QHashData::Node *i; public: +#if QT_DEPRECATED_SINCE(5, 15) 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; @@ -350,21 +356,25 @@ public: i = QHashData::nextNode(i); return r; } - inline iterator &operator--() { +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED iterator &operator--() + { i = QHashData::previousNode(i); return *this; } - inline iterator operator--(int) { + inline QT_DEPRECATED iterator operator--(int) + { iterator r = *this; i = QHashData::previousNode(i); return r; } - inline iterator operator+(int j) const + inline QT_DEPRECATED iterator operator+(int j) const { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline iterator operator-(int j) const { return operator+(-j); } - inline iterator &operator+=(int j) { return *this = *this + j; } - inline iterator &operator-=(int j) { return *this = *this - j; } - friend inline iterator operator+(int j, iterator k) { return k + j; } + inline QT_DEPRECATED iterator operator-(int j) const { return operator+(-j); } + inline QT_DEPRECATED iterator &operator+=(int j) { return *this = *this + j; } + inline QT_DEPRECATED iterator &operator-=(int j) { return *this = *this - j; } + friend inline QT_DEPRECATED iterator operator+(int j, iterator k) { return k + j; } +#endif #ifndef QT_STRICT_ITERATORS public: @@ -380,11 +390,16 @@ public: { friend class iterator; friend class QHash<Key, T>; + friend class QMultiHash<Key, T>; friend class QSet<Key>; QHashData::Node *i; public: +#if QT_DEPRECATED_SINCE(5, 15) 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; @@ -416,21 +431,28 @@ public: i = QHashData::nextNode(i); return r; } - inline const_iterator &operator--() { +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED const_iterator &operator--() + { i = QHashData::previousNode(i); return *this; } - inline const_iterator operator--(int) { + inline QT_DEPRECATED const_iterator operator--(int) + { const_iterator r = *this; i = QHashData::previousNode(i); return r; } - inline const_iterator operator+(int j) const + inline QT_DEPRECATED const_iterator operator+(int j) const { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline const_iterator operator-(int j) const { return operator+(-j); } - inline const_iterator &operator+=(int j) { return *this = *this + j; } - inline const_iterator &operator-=(int j) { return *this = *this - j; } - friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } + inline QT_DEPRECATED const_iterator operator-(int j) const { return operator+(-j); } + inline QT_DEPRECATED const_iterator &operator+=(int j) { return *this = *this + j; } + inline QT_DEPRECATED const_iterator &operator-=(int j) { return *this = *this - j; } + friend inline QT_DEPRECATED const_iterator operator+(int j, const_iterator k) + { + return k + j; + } +#endif // ### Qt 5: not sure this is necessary anymore #ifdef QT_STRICT_ITERATORS @@ -462,8 +484,14 @@ public: inline key_iterator &operator++() { ++i; return *this; } inline key_iterator operator++(int) { return key_iterator(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 key_iterator &operator--() + { + --i; + return *this; + } + inline QT_DEPRECATED key_iterator operator--(int) { return key_iterator(i--); } +#endif const_iterator base() const { return i; } }; @@ -501,8 +529,11 @@ public: const_iterator find(const Key &key) const; const_iterator constFind(const Key &key) const; iterator insert(const Key &key, const T &value); - iterator insertMulti(const Key &key, const T &value); - QHash &unite(const QHash &other); + void insert(const QHash &hash); +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QHash &unite(const QHash &other); +#endif // STL compatibility typedef T mapped_type; @@ -544,6 +575,7 @@ private: #endif } friend class QSet<Key>; + friend class QMultiHash<Key, T>; }; @@ -582,22 +614,6 @@ QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anex } template <class Key, class T> -Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) -{ - if (d == &QHashData::shared_null) { - *this = other; - } else { - QHash copy(other); - const_iterator it = copy.constEnd(); - while (it != copy.constBegin()) { - --it; - insertMulti(it.key(), it.value()); - } - } - return *this; -} - -template <class Key, class T> Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) { x->free_helper(deleteNode2); @@ -656,26 +672,6 @@ Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaul } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - const_iterator i = begin(); - if (i != end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == end()) - goto break_out_of_outer_loop; - } while (aKey == i.key()); - } - } -break_out_of_outer_loop: - return res; -} - -template <class Key, class T> Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const { QList<Key> res; @@ -734,32 +730,6 @@ Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *node = *findNode(akey); - if (node != e) { - do { - res.append(node->value); - } while ((node = node->next) != e && node->key == akey); - } - return res; -} - -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; -} - -template <class Key, class T> Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const { return value(akey); @@ -800,15 +770,28 @@ Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const K } template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey, - const T &avalue) +Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash) { + if (d == hash.d) + return; + detach(); - d->willGrow(); - uint h; - Node **nextNode = findNode(akey, &h); - return iterator(createNode(h, akey, avalue, nextNode)); + 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; + } + i = QHashData::nextNode(i); + } } template <class Key, class T> @@ -1061,11 +1044,12 @@ public: inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) { return QHash<Key, T>::insert(key, value); } - inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value) - { return QHash<Key, T>::insertMulti(key, value); } + typename QHash<Key, T>::iterator insert(const Key &key, const T &value); + + inline QMultiHash &unite(const QMultiHash &other); inline QMultiHash &operator+=(const QMultiHash &other) - { this->unite(other); return *this; } + { return unite(other); } inline QMultiHash operator+(const QMultiHash &other) const { QMultiHash result = *this; result += other; return result; } @@ -1074,13 +1058,27 @@ public: 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; + + using typename QHash<Key, T>::Node; + using typename QHash<Key, T>::iterator; + using typename QHash<Key, T>::const_iterator; bool contains(const Key &key, const T &value) const; int remove(const Key &key, const T &value); + int count(const Key &key) const; int count(const Key &key, const T &value) const; + QList<Key> uniqueKeys() const; + + QList<T> values(const Key &akey) const; + 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()); @@ -1109,6 +1107,50 @@ private: }; 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()); + } + } +#endif + } + 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(); @@ -1145,8 +1187,257 @@ Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) return n; } -Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash) -Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash) +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()); + } + } +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 int QHash<Key, T>::count(const Key &akey) const +{ + return static_cast<const QMultiHash<Key, T> *>(this)->count(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; +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &akey) const +{ + int cnt = 0; + Node *node = *findNode(akey); + if (node != this->e) { + do { + ++cnt; + } while ((node = node->next) != this->e && node->key == akey); + } + return cnt; +} + +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(); } + +public: + inline QHashIterator(const QHash<Key, T> &container) + : c(container), i(c.constBegin()), n(c.constEnd()) + { + } + inline QHashIterator &operator=(const QHash<Key, T> &container) + { + c = container; + i = c.constBegin(); + n = c.constEnd(); + return *this; + } + inline void toFront() + { + i = c.constBegin(); + n = c.constEnd(); + } + inline void toBack() + { + i = c.constEnd(); + n = c.constEnd(); + } + inline bool hasNext() const { return i != c.constEnd(); } + inline Item next() + { + n = i++; + return n; + } + inline Item peekNext() const { return i; } + inline const T &value() const + { + Q_ASSERT(item_exists()); + return *n; + } + inline const Key &key() const + { + Q_ASSERT(item_exists()); + return n.key(); + } + inline bool findNext(const T &t) + { + while ((n = i) != c.constEnd()) + if (*i++ == t) + return true; + return false; + } +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED bool hasPrevious() const { return i != c.constBegin(); } + inline QT_DEPRECATED Item previous() + { + n = --i; + return n; + } + inline QT_DEPRECATED Item peekPrevious() const + { + const_iterator p = i; + return --p; + } + inline bool QT_DEPRECATED 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> +class QMutableHashIterator +{ + typedef typename QHash<Key, T>::iterator iterator; + typedef typename QHash<Key, T>::const_iterator const_iterator; + typedef iterator Item; + QHash<Key, T> *c; + iterator i, n; + inline bool item_exists() const { return const_iterator(n) != c->constEnd(); } + +public: + inline QMutableHashIterator(QHash<Key, T> &container) : c(&container) + { + i = c->begin(); + n = c->end(); + } + inline QMutableHashIterator &operator=(QHash<Key, T> &container) + { + c = &container; + i = c->begin(); + n = c->end(); + return *this; + } + inline void toFront() + { + i = c->begin(); + n = c->end(); + } + inline void toBack() + { + i = c->end(); + n = c->end(); + } + inline bool hasNext() const { return const_iterator(i) != c->constEnd(); } + inline Item next() + { + n = i++; + return n; + } + inline Item peekNext() const { return i; } + inline void remove() + { + if (const_iterator(n) != c->constEnd()) { + i = c->erase(n); + n = c->end(); + } + } + inline void setValue(const T &t) + { + if (const_iterator(n) != c->constEnd()) + *n = t; + } + inline T &value() + { + Q_ASSERT(item_exists()); + return *n; + } + inline const T &value() const + { + Q_ASSERT(item_exists()); + return *n; + } + inline const Key &key() const + { + Q_ASSERT(item_exists()); + return n.key(); + } + inline bool findNext(const T &t) + { + while (const_iterator(n = i) != c->constEnd()) + if (*i++ == t) + return true; + return false; + } +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED bool hasPrevious() const { return const_iterator(i) != c->constBegin(); } + inline QT_DEPRECATED Item previous() + { + n = --i; + return n; + } + inline QT_DEPRECATED Item peekPrevious() const + { + iterator p = i; + return --p; + } + inline QT_DEPRECATED bool findPrevious(const T &t) + { + while (const_iterator(i) != c->constBegin()) + if (*(n = --i) == t) + return true; + n = c->end(); + return false; + } +#endif +}; template <class Key, class T> uint qHash(const QHash<Key, T> &key, uint seed = 0) |