QHash/QMultiHash: fix operator==

The existing QHash::operator== does not work when the same
keys appear in different order between the two hashes being compared.
However, relying on iteration order on a QHash is (as usual) a bad
idea and one should never do it.

Task-number: QTBUG-60395
Change-Id: Ifb39a6779230e26bbd6fdba82ccc0247b9cdc6ed
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
(cherry picked from commit dbd55cdaf367bdc9d6774bcb9927cbe19f18065f)
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>

3 files changed, 116 insertions, 12 deletions

diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h
index b22c5e219c..503f98feee 100644
--- a/src/corelib/tools/qalgorithms.h
+++ b/src/corelib/tools/qalgorithms.h
@@ -40,6 +40,10 @@
 #include <intrin.h>
 #endif
 
+#include <iterator>
+#include <utility>
+#include <algorithm>
+
 QT_BEGIN_NAMESPACE
 QT_WARNING_PUSH
 QT_WARNING_DISABLE_GCC("-Wdeprecated-declarations")
@@ -70,6 +74,31 @@ template <typename RandomAccessIterator, typename T, typename LessThan>
 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
 #endif // QT_DEPRECATED_SINCE(5, 2)
 
+template <typename ForwardIterator1, typename ForwardIterator2>
+bool qIsPermutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
+{
+    // find and exclude a common prefix
+    const std::pair<ForwardIterator1, ForwardIterator2> commonPrefix = std::mismatch(first1, last1, first2);
+
+    // unpack commonPrefix
+    first1 = commonPrefix.first;
+    first2 = commonPrefix.second;
+
+    // is there anything else to check? if so, for each element left to check in the
+    // first range, count how many times it appears in both ranges; the counts must match
+    if (first1 != last1) {
+        ForwardIterator2 last2 = first2;
+        std::advance(last2, std::distance(first1, last1));
+
+        for (ForwardIterator1 it = first1; it != last1; ++it) {
+            if (std::count(first1, last1, *it) != std::count(first2, last2, *it))
+                return false;
+        }
+    }
+
+    return true;
+}
+
 }
 
 #if QT_DEPRECATED_SINCE(5, 2)
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index adb7782efc..c181de94bb 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -40,6 +40,7 @@
 #include <QtCore/qlist.h>
 #include <QtCore/qrefcount.h>
 #include <QtCore/qhashfunctions.h>
+#include <QtCore/qalgorithms.h>
 
 #ifdef Q_COMPILER_INITIALIZER_LISTS
 #include <initializer_list>
@@ -916,18 +917,27 @@ Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
     const_iterator it = begin();
 
     while (it != end()) {
-        const Key &akey = it.key();
+        // Build two equal ranges for i.key(); one for *this and one for other.
+        // For *this we can avoid a lookup via find, as we know the beginning of the range.
+        const_iterator thisEqualRangeEnd = it;
+        while (thisEqualRangeEnd != end() && it.key() == thisEqualRangeEnd.key())
+            ++thisEqualRangeEnd;
 
-        const_iterator it2 = other.find(akey);
-        do {
-            if (it2 == other.end() || !(it2.key() == akey))
-                return false;
-            if (!(it.value() == it2.value()))
-                return false;
-            ++it;
-            ++it2;
-        } while (it != end() && it.key() == akey);
+        const const_iterator otherEqualRangeBegin = other.find(it.key());
+        const_iterator otherEqualRangeEnd = otherEqualRangeBegin;
+        while (otherEqualRangeEnd != other.end() && it.key() == otherEqualRangeEnd.key())
+            ++otherEqualRangeEnd;
+
+        if (std::distance(it, thisEqualRangeEnd) != std::distance(otherEqualRangeBegin, otherEqualRangeEnd))
+            return false;
+
+        // Keys in the ranges are equal by construction; this checks only the values.
+        if (!QAlgorithmsPrivate::qIsPermutation(it, thisEqualRangeEnd, otherEqualRangeBegin))
+            return false;
+
+        it = thisEqualRangeEnd;
     }
+
     return true;
 }
 
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index d485040a14..e26c019b01 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -54,7 +54,7 @@ private slots:
     void constFind(); // copied from tst_QMap
     void contains(); // copied from tst_QMap
     void take(); // copied from tst_QMap
-    void operator_eq(); // copied from tst_QMap
+    void operator_eq(); // slightly modified from tst_QMap
     void rehash_isnt_quadratic();
     void dont_need_default_constructor();
     void qmultihash_specific();
@@ -710,7 +710,7 @@ void tst_QHash::take()
     QVERIFY(!map.contains(3));
 }
 
-//copied from tst_QMap
+// slightly modified from tst_QMap
 void tst_QHash::operator_eq()
 {
     {
@@ -787,6 +787,71 @@ void tst_QHash::operator_eq()
         QVERIFY(a != b);
         QVERIFY(!(a == b));
     }
+
+    // unlike multi-maps, multi-hashes should be equal iff their contents are equal,
+    // regardless of insertion or iteration order
+
+    {
+        QHash<int, int> a;
+        QHash<int, int> b;
+
+        a.insertMulti(0, 0);
+        a.insertMulti(0, 1);
+
+        b.insertMulti(0, 1);
+        b.insertMulti(0, 0);
+
+        QVERIFY(a == b);
+        QVERIFY(!(a != b));
+    }
+
+    {
+        QHash<int, int> a;
+        QHash<int, int> b;
+
+        enum { Count = 100 };
+
+        for (int key = 0; key < Count; ++key) {
+            for (int value = 0; value < Count; ++value)
+                a.insertMulti(key, value);
+        }
+
+        for (int key = Count - 1; key >= 0; --key) {
+            for (int value = 0; value < Count; ++value)
+                b.insertMulti(key, value);
+        }
+
+        QVERIFY(a == b);
+        QVERIFY(!(a != b));
+    }
+
+    {
+        QHash<int, int> a;
+        QHash<int, int> b;
+
+        enum {
+            Count = 100,
+            KeyStep = 17,   // coprime with Count
+            ValueStep = 23, // coprime with Count
+        };
+
+        for (int key = 0; key < Count; ++key) {
+            for (int value = 0; value < Count; ++value)
+                a.insertMulti(key, value);
+        }
+
+        // Generates two permutations of [0, Count) for the keys and values,
+        // so that b will be identical to a, just built in a very different order.
+
+        for (int k = 0; k < Count; ++k) {
+           const int key = (k * KeyStep) % Count;
+           for (int v = 0; v < Count; ++v)
+               b.insertMulti(key, (v * ValueStep) % Count);
+        }
+
+        QVERIFY(a == b);
+        QVERIFY(!(a != b));
+    }
 }
 
 void tst_QHash::compare()