From 6139fbeb5f41843e524ec40ce5be57f0df23e922 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?S=C3=A9rgio=20Martins?= <sergio.martins@kdab.com>
Date: Sun, 7 Feb 2016 02:49:33 +0000
Subject: Introduce QHash::equal_range()

Similar to QMap::equal_range().
Will allow to easily fix inefficient code such as:

    foreach (auto value, hash.values(key)) { ... }

[ChangeLog][QtCore][QHash] Added QHash::equal_range()

Change-Id: I6e19e25de632e897ad83d3141d9d07f0313f7200
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
---
 src/corelib/tools/qhash.cpp | 13 +++++++++++++
 src/corelib/tools/qhash.h   | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 48 insertions(+)

(limited to 'src/corelib')

diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index c1a1b9715f..b49c9d683a 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -1803,6 +1803,19 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW
     returns \c false.
 */
 
+/*! \fn QPair<iterator, iterator> QHash::equal_range(const Key &key)
+    \since 5.7
+
+    Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
+    are stored under \a key. If the range is empty then both iterators will be equal to end().
+*/
+
+/*!
+    \fn QPair<const_iterator, const_iterator> QHash::equal_range(const Key &key) const
+    \overload
+    \since 5.7
+*/
+
 /*! \typedef QHash::ConstIterator
 
     Qt-style synonym for QHash::const_iterator.
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 819631932b..5e3016d313 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -458,6 +458,8 @@ public:
     inline key_iterator keyBegin() const { return key_iterator(begin()); }
     inline key_iterator keyEnd() const { return key_iterator(end()); }
 
+    QPair<iterator, iterator> equal_range(const Key &key);
+    QPair<const_iterator, const_iterator> equal_range(const Key &key) const Q_DECL_NOTHROW;
     iterator erase(iterator it) { return erase(const_iterator(it.i)); }
     iterator erase(const_iterator it);
 
@@ -944,6 +946,39 @@ Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
     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 Q_DECL_NOTHROW
+{
+    uint h;
+    Node *node = *findNode(akey, &h);
+    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)));
+    }
+
+    return qMakePair(firstIt, const_iterator(node));
+}
+
 template <class Key, class T>
 class QMultiHash : public QHash<Key, T>
 {
-- 
cgit v1.2.3