Fix hash lookup using the value of a key iterator

QHash::operator[] could grow the hash even if the key being
looked up already existed. This in turn invalidated all iterators.
Avoid this by refactoring findOrInsert() to not grow if the key
already exists.

Added advantage is that this should make lookups of existing keys
slightly faster.

Fixes: QTBUG-97752
Pick-to: 6.3 6.2
Change-Id: I9df30459797b42c434ba0ee299fd1d55af8d2313
Reviewed-by: Marc Mutz <marc.mutz@qt.io>

2 files changed, 30 insertions, 7 deletions

diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 49a015f2fe..5d7c2eb80d 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -655,15 +655,21 @@ struct Data
 
     InsertionResult findOrInsert(const Key &key) noexcept
     {
-        if (shouldGrow())
+        iterator it;
+        if (numBuckets > 0) {
+            it = find(key);
+            if (!it.isUnused())
+                return { it, true };
+        }
+        if (shouldGrow()) {
             rehash(size + 1);
-        iterator it = find(key);
-        if (it.isUnused()) {
-            spans[it.span()].insert(it.index());
-            ++size;
-            return { it, false };
+            it = find(key); // need to get a new iterator after rehashing
         }
-        return { it, true };
+        Q_ASSERT(it.d);
+        Q_ASSERT(it.isUnused());
+        spans[it.span()].insert(it.index());
+        ++size;
+        return { it, false };
     }
 
     iterator erase(iterator it) noexcept(std::is_nothrow_destructible<Node>::value)
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index 11e7237ba4..50c2b0d84e 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -101,6 +101,8 @@ private slots:
     void QTBUG98265();
 
     void detachAndReferences();
+
+    void lookupUsingKeyIterator();
 };
 
 struct IdentityTracker {
@@ -2699,5 +2701,20 @@ void tst_QHash::detachAndReferences()
 #endif
 }
 
+void tst_QHash::lookupUsingKeyIterator()
+{
+    QHash<QString, QString> hash;
+    hash.reserve(1);
+    qsizetype minCapacity = hash.capacity();
+    // Beholden to internal implementation details:
+    qsizetype rehashLimit = minCapacity == 64 ? 63 : 8;
+
+    for (char16_t c = u'a'; c <= u'a' + rehashLimit; ++c)
+        hash.insert(QString(QChar(c)), u"h"_qs);
+
+    for (auto it = hash.keyBegin(), end = hash.keyEnd(); it != end; ++it)
+        QVERIFY(!hash[*it].isEmpty());
+}
+
 QTEST_APPLESS_MAIN(tst_QHash)
 #include "tst_qhash.moc"