summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r--src/corelib/tools/qhash.h479
1 files changed, 385 insertions, 94 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 9fd96686f5..c56324eef7 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -305,12 +305,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;
@@ -322,7 +324,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;
@@ -347,21 +353,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
inline bool operator==(const const_iterator &o) const { return i == o.i; }
inline bool operator!=(const const_iterator &o) const { return i != o.i; }
@@ -372,11 +382,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;
@@ -404,21 +419,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
};
friend class const_iterator;
@@ -443,8 +465,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; }
};
@@ -482,8 +510,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;
@@ -525,6 +556,7 @@ private:
#endif
}
friend class QSet<Key>;
+ friend class QMultiHash<Key, T>;
};
@@ -563,22 +595,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);
@@ -637,26 +653,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;
@@ -715,32 +711,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);
@@ -781,15 +751,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>
@@ -1042,11 +1025,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; }
@@ -1055,13 +1039,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());
@@ -1090,6 +1088,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();
@@ -1126,8 +1168,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)
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-04 23:35:00 +0000