From 4084f96052ea1568c847f8cfb52b6ae6d205ec4d Mon Sep 17 00:00:00 2001 From: Giuseppe D'Angelo Date: Tue, 25 Apr 2017 15:58:57 +0100 Subject: 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 (cherry picked from commit dbd55cdaf367bdc9d6774bcb9927cbe19f18065f) Reviewed-by: Edward Welbourne --- src/corelib/tools/qalgorithms.h | 29 ++++++++++++ src/corelib/tools/qhash.h | 30 ++++++++---- tests/auto/corelib/tools/qhash/tst_qhash.cpp | 69 +++++++++++++++++++++++++++- 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 #endif +#include +#include +#include + QT_BEGIN_NAMESPACE QT_WARNING_PUSH QT_WARNING_DISABLE_GCC("-Wdeprecated-declarations") @@ -70,6 +74,31 @@ template 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 +bool qIsPermutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) +{ + // find and exclude a common prefix + const std::pair 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 #include #include +#include #ifdef Q_COMPILER_INITIALIZER_LISTS #include @@ -916,18 +917,27 @@ Q_OUTOFLINE_TEMPLATE bool QHash::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 a; + QHash b; + + a.insertMulti(0, 0); + a.insertMulti(0, 1); + + b.insertMulti(0, 1); + b.insertMulti(0, 0); + + QVERIFY(a == b); + QVERIFY(!(a != b)); + } + + { + QHash a; + QHash 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 a; + QHash 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() -- cgit v1.2.3