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>

1 files changed, 35 insertions, 0 deletions

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);
 
@@ -945,6 +947,39 @@ Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
 }
 
 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>
 {
 public: