summaryrefslogtreecommitdiffstats
path: root/tests/auto/corelib/tools/qhash/tst_qhash.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'tests/auto/corelib/tools/qhash/tst_qhash.cpp')
-rw-r--r--tests/auto/corelib/tools/qhash/tst_qhash.cpp1451
1 files changed, 1356 insertions, 95 deletions
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index 014617f8d4..b3dbdfa40c 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -1,48 +1,32 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the test suite of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:GPL-EXCEPT$
-** Commercial License Usage
-** Licensees holding valid commercial Qt licenses may use this file in
-** accordance with the commercial license agreement provided with the
-** Software or, alternatively, in accordance with the terms contained in
-** a written agreement between you and The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 3 as published by the Free Software
-** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
+// Copyright (C) 2016 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
#include <QTest>
+#include <qdebug.h>
#include <qhash.h>
#include <qmap.h>
+#include <qscopeguard.h>
+#include <qset.h>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <string>
+#include <qsemaphore.h>
+
+using namespace Qt::StringLiterals;
+
class tst_QHash : public QObject
{
Q_OBJECT
private slots:
void insert1();
void erase();
+ void erase_edge_case();
void key();
+ void keys();
void swap();
void count(); // copied from tst_QMap
@@ -54,17 +38,35 @@ private slots:
void qhash();
void take(); // copied from tst_QMap
void operator_eq(); // slightly modified from tst_QMap
+ void heterogeneousSearch();
+ void heterogeneousSearchConstKey();
+ void heterogeneousSearchByteArray();
+ void heterogeneousSearchString();
+ void heterogeneousSearchLatin1String();
+
void rehash_isnt_quadratic();
void dont_need_default_constructor();
void qmultihash_specific();
void qmultihash_qhash_rvalue_ref_ctor();
void qmultihash_qhash_rvalue_ref_unite();
+ void qmultihashUnite();
+ void qmultihashSize();
+ void qmultihashHeterogeneousSearch();
+ void qmultihashHeterogeneousSearchConstKey();
+ void qmultihashHeterogeneousSearchByteArray();
+ void qmultihashHeterogeneousSearchString();
+ void qmultihashHeterogeneousSearchLatin1String();
void compare();
void compare2();
void iterators(); // sligthly modified from tst_QMap
+ void multihashIterators();
+ void iteratorsInEmptyHash();
void keyIterator();
+ void multihashKeyIterator();
void keyValueIterator();
+ void multihashKeyValueIterator();
+ void keyValueIteratorInEmptyHash();
void keys_values_uniqueKeys(); // slightly modified from tst_QMap
void const_shared_null();
@@ -73,6 +75,7 @@ private slots:
void eraseValidIteratorOnSharedHash();
void equal_range();
void insert_hash();
+ void multiHashStoresInReverseInsertionOrder();
void emplace();
@@ -80,6 +83,25 @@ private slots:
void hashOfHash();
void stdHash();
+
+ void countInEmptyHash();
+ void removeInEmptyHash();
+ void valueInEmptyHash();
+ void fineTuningInEmptyHash();
+
+ void reserveShared();
+ void reserveLessThanCurrentAmount();
+ void reserveKeepCapacity_data();
+ void reserveKeepCapacity();
+
+ void QTBUG98265();
+
+ void detachAndReferences();
+
+ void lookupUsingKeyIterator();
+
+ void squeeze();
+ void squeezeShared();
};
struct IdentityTracker {
@@ -95,6 +117,8 @@ struct Foo {
Foo():c(count) { ++count; }
Foo(const Foo& o):c(o.c) { ++count; }
~Foo() { --count; }
+ constexpr Foo &operator=(const Foo &o) noexcept { c = o.c; return *this; }
+
int c;
int data[8];
};
@@ -161,13 +185,13 @@ void tst_QHash::count()
{
MyMap map;
MyMap map2( map );
- QCOMPARE( map.count(), 0 );
- QCOMPARE( map2.count(), 0 );
+ QCOMPARE( map.size(), 0 );
+ QCOMPARE( map2.size(), 0 );
QCOMPARE( MyClass::count, 0 );
// detach
map2["Hallo"] = MyClass( "Fritz" );
- QCOMPARE( map.count(), 0 );
- QCOMPARE( map2.count(), 1 );
+ QCOMPARE( map.size(), 0 );
+ QCOMPARE( map2.size(), 1 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 1 );
#endif
@@ -177,11 +201,11 @@ void tst_QHash::count()
{
typedef QHash<QString, MyClass> Map;
Map map;
- QCOMPARE( map.count(), 0);
+ QCOMPARE( map.size(), 0);
map.insert( "Torben", MyClass("Weis") );
- QCOMPARE( map.count(), 1 );
+ QCOMPARE( map.size(), 1 );
map.insert( "Claudia", MyClass("Sorg") );
- QCOMPARE( map.count(), 2 );
+ QCOMPARE( map.size(), 2 );
map.insert( "Lars", MyClass("Linzbach") );
map.insert( "Matthias", MyClass("Ettrich") );
map.insert( "Sue", MyClass("Paludo") );
@@ -189,7 +213,7 @@ void tst_QHash::count()
map.insert( "Haavard", MyClass("Nord") );
map.insert( "Arnt", MyClass("Gulbrandsen") );
map.insert( "Paul", MyClass("Tvete") );
- QCOMPARE( map.count(), 9 );
+ QCOMPARE( map.size(), 9 );
map.insert( "Paul", MyClass("Tvete 1") );
map.insert( "Paul", MyClass("Tvete 2") );
map.insert( "Paul", MyClass("Tvete 3") );
@@ -197,68 +221,68 @@ void tst_QHash::count()
map.insert( "Paul", MyClass("Tvete 5") );
map.insert( "Paul", MyClass("Tvete 6") );
- QCOMPARE( map.count(), 9 );
+ QCOMPARE( map.size(), 9 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
Map map2( map );
- QVERIFY( map2.count() == 9 );
+ QVERIFY( map2.size() == 9 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
map2.insert( "Kay", MyClass("Roemer") );
- QVERIFY( map2.count() == 10 );
- QVERIFY( map.count() == 9 );
+ QVERIFY( map2.size() == 10 );
+ QVERIFY( map.size() == 9 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 19 );
#endif
map2 = map;
- QVERIFY( map.count() == 9 );
- QVERIFY( map2.count() == 9 );
+ QVERIFY( map.size() == 9 );
+ QVERIFY( map2.size() == 9 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
map2.insert( "Kay", MyClass("Roemer") );
- QVERIFY( map2.count() == 10 );
+ QVERIFY( map2.size() == 10 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 19 );
#endif
map2.clear();
- QVERIFY( map.count() == 9 );
- QVERIFY( map2.count() == 0 );
+ QVERIFY( map.size() == 9 );
+ QVERIFY( map2.size() == 0 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
map2 = map;
- QVERIFY( map.count() == 9 );
- QVERIFY( map2.count() == 9 );
+ QVERIFY( map.size() == 9 );
+ QVERIFY( map2.size() == 9 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
map2.clear();
- QVERIFY( map.count() == 9 );
- QVERIFY( map2.count() == 0 );
+ QVERIFY( map.size() == 9 );
+ QVERIFY( map2.size() == 0 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 9 );
#endif
map.remove( "Lars" );
- QVERIFY( map.count() == 8 );
- QVERIFY( map2.count() == 0 );
+ QVERIFY( map.size() == 8 );
+ QVERIFY( map2.size() == 0 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 8 );
#endif
map.remove( "Mist" );
- QVERIFY( map.count() == 8 );
- QVERIFY( map2.count() == 0 );
+ QVERIFY( map.size() == 8 );
+ QVERIFY( map2.size() == 0 );
#ifndef Q_CC_SUN
QCOMPARE( MyClass::count, 8 );
#endif
@@ -272,22 +296,22 @@ void tst_QHash::count()
#ifndef Q_CC_SUN
QVERIFY( MyClass::count == 1 );
#endif
- QVERIFY( map.count() == 1 );
+ QVERIFY( map.size() == 1 );
(void)map["Torben"].str;
(void)map["Lars"].str;
#ifndef Q_CC_SUN
QVERIFY( MyClass::count == 2 );
#endif
- QVERIFY( map.count() == 2 );
+ QVERIFY( map.size() == 2 );
const Map& cmap = map;
(void)cmap["Depp"].str;
#ifndef Q_CC_SUN
QVERIFY( MyClass::count == 2 );
#endif
- QVERIFY( map.count() == 2 );
- QVERIFY( cmap.count() == 2 );
+ QVERIFY( map.size() == 2 );
+ QVERIFY( cmap.size() == 2 );
}
QCOMPARE( MyClass::count, 0 );
{
@@ -482,6 +506,7 @@ QT_WARNING_POP
{
QHash<IdentityTracker, int> hash;
QCOMPARE(hash.size(), 0);
+ QVERIFY(!hash.isDetached());
const int dummy = -1;
IdentityTracker id00 = {0, 0}, id01 = {0, 1}, searchKey = {0, dummy};
QCOMPARE(hash.insert(id00, id00.id).key().id, id00.id);
@@ -526,6 +551,66 @@ void tst_QHash::erase()
auto mit = h2.erase(bit);
mit = h2.erase(h2.begin());
QVERIFY(mit == h2.end());
+
+ h2 = QMultiHash<int, int>();
+ h2.emplace(1, 1);
+ h2.emplace(1, 2);
+ h2.emplace(3, 1);
+ h2.emplace(3, 4);
+ QMultiHash<int, int> h3 = h2;
+ auto it = h3.constFind(3);
+ ++it;
+ QVERIFY(h3.isSharedWith(h2));
+ it = h3.erase(it);
+ QVERIFY(!h3.isSharedWith(h2));
+ if (it != h3.cend()) {
+ auto it2 = h3.constFind(it.key());
+ QCOMPARE(it, it2);
+ }
+}
+
+/*
+ With a specific seed we could end up in a situation where, upon deleting the
+ last entry in a QHash, the returned iterator would not point to the end()
+ iterator.
+*/
+void tst_QHash::erase_edge_case()
+{
+ QHashSeed::setDeterministicGlobalSeed();
+ auto resetSeed = qScopeGuard([&]() {
+ QHashSeed::resetRandomGlobalSeed();
+ });
+
+ QHash<int, int> h1;
+ h1.reserve(2);
+ qsizetype capacity = h1.capacity();
+ // Beholden to QHash internals:
+ qsizetype numBuckets = capacity << 1;
+
+ // Find some keys which will both be slotted into the last bucket:
+ int keys[2];
+ int index = 0;
+ for (qsizetype i = 0; i < numBuckets * 4 && index < 2; ++i) {
+ const size_t hash = qHash(i, QHashSeed::globalSeed());
+ const size_t bucketForHash = QHashPrivate::GrowthPolicy::bucketForHash(numBuckets, hash);
+ if (qsizetype(bucketForHash) == numBuckets - 1)
+ keys[index++] = i;
+ }
+ QCOMPARE(index, 2); // Sanity check. If this fails then the test needs an update!
+
+ // As mentioned earlier these are both calculated to be in the last bucket:
+ h1.insert(keys[0], 4);
+ h1.insert(keys[1], 6);
+ // As a sanity-check, make sure that the key we inserted last is the first one (because its
+ // allocation to the last bucket would make it wrap around):
+ // NOTE: If this fails this then this test may need an update!!!
+ QCOMPARE(h1.constBegin().key(), keys[1]);
+ // Then we delete the last entry:
+ QHash<int, int>::iterator it1 = h1.begin();
+ ++it1;
+ it1 = h1.erase(it1);
+ // Now, since we deleted the last entry, the iterator should be at the end():
+ QVERIFY(it1 == h1.end());
}
void tst_QHash::key()
@@ -536,6 +621,7 @@ void tst_QHash::key()
QHash<QString, int> hash1;
QCOMPARE(hash1.key(1), QString());
QCOMPARE(hash1.key(1, def), def);
+ QVERIFY(!hash1.isDetached());
hash1.insert("one", 1);
QCOMPARE(hash1.key(1), QLatin1String("one"));
@@ -566,6 +652,7 @@ void tst_QHash::key()
QHash<int, QString> hash2;
QCOMPARE(hash2.key("one"), 0);
QCOMPARE(hash2.key("one", def), def);
+ QVERIFY(!hash2.isDetached());
hash2.insert(1, "one");
QCOMPARE(hash2.key("one"), 1);
@@ -597,6 +684,62 @@ void tst_QHash::key()
QCOMPARE(hash2.key("zero"), 0);
QCOMPARE(hash2.key("zero", def), 0);
}
+
+ {
+ const int def = -1;
+ QMultiHash<int, QString> hash;
+ QCOMPARE(hash.key("val"), 0);
+ QCOMPARE(hash.key("val", def), def);
+ QVERIFY(!hash.isDetached());
+
+ hash.insert(1, "value1");
+ hash.insert(1, "value2");
+ hash.insert(2, "value1");
+
+ QCOMPARE(hash.key("value2"), 1);
+ const auto key = hash.key("value1");
+ QVERIFY(key == 1 || key == 2);
+ QCOMPARE(hash.key("value"), 0);
+ QCOMPARE(hash.key("value", def), def);
+ }
+}
+
+template <typename T>
+QList<T> sorted(const QList<T> &list)
+{
+ QList<T> res = list;
+ std::sort(res.begin(), res.end());
+ return res;
+}
+
+void tst_QHash::keys()
+{
+ {
+ QHash<QString, int> hash;
+ QVERIFY(hash.keys().isEmpty());
+ QVERIFY(hash.keys(1).isEmpty());
+ QVERIFY(!hash.isDetached());
+
+ hash.insert("key1", 1);
+ hash.insert("key2", 2);
+ hash.insert("key3", 1);
+
+ QCOMPARE(sorted(hash.keys()), QStringList({ "key1", "key2", "key3" }));
+ QCOMPARE(sorted(hash.keys(1)), QStringList({ "key1", "key3" }));
+ }
+ {
+ QMultiHash<QString, int> hash;
+ QVERIFY(hash.keys().isEmpty());
+ QVERIFY(hash.keys(1).isEmpty());
+ QVERIFY(!hash.isDetached());
+
+ hash.insert("key1", 1);
+ hash.insert("key2", 1);
+ hash.insert("key1", 2);
+
+ QCOMPARE(sorted(hash.keys()), QStringList({ "key1", "key1", "key2" }));
+ QCOMPARE(sorted(hash.keys(1)), QStringList({ "key1", "key2" }));
+ }
}
void tst_QHash::swap()
@@ -626,6 +769,25 @@ void tst_QHash::clear()
QVERIFY( map.isEmpty() );
}
QCOMPARE( MyClass::count, int(0) );
+
+ {
+ QMultiHash<QString, MyClass> multiHash;
+ multiHash.clear();
+ QVERIFY(multiHash.isEmpty());
+
+ multiHash.insert("key", MyClass("value0"));
+ QVERIFY(!multiHash.isEmpty());
+ multiHash.clear();
+ QVERIFY(multiHash.isEmpty());
+
+ multiHash.insert("key0", MyClass("value0"));
+ multiHash.insert("key0", MyClass("value1"));
+ multiHash.insert("key1", MyClass("value2"));
+ QVERIFY(!multiHash.isEmpty());
+ multiHash.clear();
+ QVERIFY(multiHash.isEmpty());
+ }
+ QCOMPARE(MyClass::count, int(0));
}
//copied from tst_QMap
void tst_QHash::empty()
@@ -633,24 +795,31 @@ void tst_QHash::empty()
QHash<int, QString> map1;
QVERIFY(map1.isEmpty());
+ QVERIFY(map1.empty());
map1.insert(1, "one");
QVERIFY(!map1.isEmpty());
+ QVERIFY(!map1.empty());
map1.clear();
QVERIFY(map1.isEmpty());
-
+ QVERIFY(map1.empty());
}
//copied from tst_QMap
void tst_QHash::find()
{
+ const QHash<int, QString> constEmptyHash;
+ QVERIFY(constEmptyHash.find(1) == constEmptyHash.end());
+ QVERIFY(!constEmptyHash.isDetached());
+
QHash<int, QString> map1;
QString testString="Teststring %0";
QString compareString;
int i,count=0;
QVERIFY(map1.find(1) == map1.end());
+ QVERIFY(!map1.isDetached());
map1.insert(1,"Mensch");
map1.insert(1,"Mayer");
@@ -659,6 +828,16 @@ void tst_QHash::find()
QCOMPARE(map1.find(1).value(), QLatin1String("Mayer"));
QCOMPARE(map1.find(2).value(), QLatin1String("Hej"));
+ const QMultiHash<int, QString> constEmptyMultiHash;
+ QVERIFY(constEmptyMultiHash.find(1) == constEmptyMultiHash.cend());
+ QVERIFY(constEmptyMultiHash.find(1, "value") == constEmptyMultiHash.cend());
+ QVERIFY(!constEmptyMultiHash.isDetached());
+
+ QMultiHash<int, QString> emptyMultiHash;
+ QVERIFY(emptyMultiHash.find(1) == emptyMultiHash.end());
+ QVERIFY(emptyMultiHash.find(1, "value") == emptyMultiHash.end());
+ QVERIFY(!emptyMultiHash.isDetached());
+
QMultiHash<int, QString> multiMap(map1);
for (i = 3; i < 10; ++i) {
compareString = testString.arg(i);
@@ -685,6 +864,7 @@ void tst_QHash::constFind()
int i,count=0;
QVERIFY(map1.constFind(1) == map1.constEnd());
+ QVERIFY(!map1.isDetached());
map1.insert(1,"Mensch");
map1.insert(1,"Mayer");
@@ -693,6 +873,10 @@ void tst_QHash::constFind()
QCOMPARE(map1.constFind(1).value(), QLatin1String("Mayer"));
QCOMPARE(map1.constFind(2).value(), QLatin1String("Hej"));
+ QMultiHash<int, QString> emptyMultiHash;
+ QVERIFY(emptyMultiHash.constFind(1) == emptyMultiHash.constEnd());
+ QVERIFY(!emptyMultiHash.isDetached());
+
QMultiHash<int, QString> multiMap(map1);
for (i = 3; i < 10; ++i) {
compareString = testString.arg(i);
@@ -716,6 +900,9 @@ void tst_QHash::contains()
QHash<int, QString> map1;
int i;
+ QVERIFY(!map1.contains(1));
+ QVERIFY(!map1.isDetached());
+
map1.insert(1, "one");
QVERIFY(map1.contains(1));
@@ -734,16 +921,31 @@ class QGlobalQHashSeedResetter
int oldSeed;
public:
// not entirely correct (may lost changes made by another thread between the query
- // of the old and the setting of the new seed), but qSetGlobalQHashSeed doesn't
+ // of the old and the setting of the new seed), but setHashSeed() can't
// return the old value, so this is the best we can do:
explicit QGlobalQHashSeedResetter(int newSeed)
- : oldSeed(qGlobalQHashSeed())
+ : oldSeed(getHashSeed())
{
- qSetGlobalQHashSeed(newSeed);
+ setHashSeed(newSeed);
}
~QGlobalQHashSeedResetter()
{
- qSetGlobalQHashSeed(oldSeed);
+ setHashSeed(oldSeed);
+ }
+
+private:
+ // The functions are implemented to replace the deprecated
+ // qGlobalQHashSeed() and qSetGlobalQHashSeed()
+ static int getHashSeed()
+ {
+ return int(QHashSeed::globalSeed() & INT_MAX);
+ }
+ static void setHashSeed(int seed)
+ {
+ if (seed == 0)
+ QHashSeed::setDeterministicGlobalSeed();
+ else
+ QHashSeed::resetRandomGlobalSeed();
}
};
@@ -794,13 +996,33 @@ void tst_QHash::qhash()
//copied from tst_QMap
void tst_QHash::take()
{
- QHash<int, QString> map;
+ {
+ QHash<int, QString> map;
+ QCOMPARE(map.take(1), QString());
+ QVERIFY(!map.isDetached());
+
+ map.insert(2, "zwei");
+ map.insert(3, "drei");
+
+ QCOMPARE(map.take(3), QLatin1String("drei"));
+ QVERIFY(!map.contains(3));
+ }
+ {
+ QMultiHash<int, QString> hash;
+ QCOMPARE(hash.take(1), QString());
+ QVERIFY(!hash.isDetached());
- map.insert(2, "zwei");
- map.insert(3, "drei");
+ hash.insert(1, "value1");
+ hash.insert(2, "value2");
+ hash.insert(1, "value3");
- QCOMPARE(map.take(3), QLatin1String("drei"));
- QVERIFY(!map.contains(3));
+ // The docs tell that if there are multiple values for a key, then the
+ // most recent is returned.
+ QCOMPARE(hash.take(1), "value3");
+ QCOMPARE(hash.take(1), "value1");
+ QCOMPARE(hash.take(1), QString());
+ QCOMPARE(hash.take(2), "value2");
+ }
}
// slightly modified from tst_QMap
@@ -947,6 +1169,222 @@ void tst_QHash::operator_eq()
}
}
+#ifdef __cpp_concepts
+struct HeterogeneousHashingType
+{
+ inline static int conversionCount = 0;
+ QString s;
+
+ Q_IMPLICIT operator QString() const
+ {
+ ++conversionCount;
+ return s;
+ }
+
+ // std::equality_comparable_with requires we be self-comparable too
+ friend bool operator==(const HeterogeneousHashingType &t1, const HeterogeneousHashingType &t2) = default;
+
+ friend bool operator==(const QString &string, const HeterogeneousHashingType &tester)
+ { return tester.s == string; }
+ friend bool operator!=(const QString &string, const HeterogeneousHashingType &tester)
+ { return !(tester.s == string); }
+
+ friend size_t qHash(const HeterogeneousHashingType &tester, size_t seed)
+ { return qHash(tester.s, seed); }
+};
+QT_BEGIN_NAMESPACE
+template <> struct QHashHeterogeneousSearch<QString, HeterogeneousHashingType> : std::true_type {};
+template <> struct QHashHeterogeneousSearch<HeterogeneousHashingType, QString> : std::true_type {};
+QT_END_NAMESPACE
+static_assert(std::is_same_v<QString, std::common_type_t<QString, HeterogeneousHashingType>>);
+static_assert(std::equality_comparable_with<QString, HeterogeneousHashingType>);
+static_assert(QHashPrivate::HeterogeneouslySearchableWith<QString, HeterogeneousHashingType>);
+static_assert(QHashPrivate::HeterogeneouslySearchableWith<HeterogeneousHashingType, QString>);
+
+template <typename T> struct HeterogeneousSearchTestHelper
+{
+ static void resetCounter() {}
+ static void checkCounter() {}
+};
+template <> struct HeterogeneousSearchTestHelper<HeterogeneousHashingType>
+{
+ static void resetCounter()
+ {
+ HeterogeneousHashingType::conversionCount = 0;
+ }
+ static void checkCounter()
+ {
+ QTest::setThrowOnFail(true);
+ auto scopeExit = qScopeGuard([] { QTest::setThrowOnFail(false); });
+ QCOMPARE(HeterogeneousHashingType::conversionCount, 0);
+ }
+};
+#else
+using HeterogeneousHashingType = QString;
+#endif
+
+template <template <typename, typename> class Hash, typename String, typename View, typename Converter>
+static void heterogeneousSearchTest(const QList<std::remove_const_t<String>> &keys, Converter conv)
+{
+#ifdef __cpp_concepts
+ using Helper = HeterogeneousSearchTestHelper<View>;
+ String key = keys.last();
+ String otherKey = keys.first();
+ auto keyHolder = conv(key);
+ auto otherKeyHolder = conv(otherKey);
+ View keyView(keyHolder);
+ View otherKeyView(otherKeyHolder);
+
+ Hash<String, qsizetype> hash;
+ static constexpr bool IsMultiHash = !std::is_same_v<decltype(hash.remove(String())), bool>;
+ hash[key] = keys.size();
+
+ Helper::resetCounter();
+ QVERIFY(hash.contains(keyView));
+ QCOMPARE_EQ(hash.count(keyView), 1);
+ QCOMPARE_EQ(hash.value(keyView), keys.size());
+ QCOMPARE_EQ(hash.value(keyView, -1), keys.size());
+ QCOMPARE_EQ(std::as_const(hash)[keyView], keys.size());
+ QCOMPARE_EQ(hash.find(keyView), hash.begin());
+ QCOMPARE_EQ(std::as_const(hash).find(keyView), hash.constBegin());
+ QCOMPARE_EQ(hash.constFind(keyView), hash.constBegin());
+ QCOMPARE_EQ(hash.equal_range(keyView), std::make_pair(hash.begin(), hash.end()));
+ QCOMPARE_EQ(std::as_const(hash).equal_range(keyView),
+ std::make_pair(hash.constBegin(), hash.constEnd()));
+ Helper::checkCounter();
+
+ QVERIFY(!hash.contains(otherKeyView));
+ QCOMPARE_EQ(hash.count(otherKeyView), 0);
+ QCOMPARE_EQ(hash.value(otherKeyView), 0);
+ QCOMPARE_EQ(hash.value(otherKeyView, -1), -1);
+ QCOMPARE_EQ(std::as_const(hash)[otherKeyView], 0);
+ QCOMPARE_EQ(hash.find(otherKeyView), hash.end());
+ QCOMPARE_EQ(std::as_const(hash).find(otherKeyView), hash.constEnd());
+ QCOMPARE_EQ(hash.constFind(otherKeyView), hash.constEnd());
+ QCOMPARE_EQ(hash.equal_range(otherKeyView), std::make_pair(hash.end(), hash.end()));
+ QCOMPARE_EQ(std::as_const(hash).equal_range(otherKeyView),
+ std::make_pair(hash.constEnd(), hash.constEnd()));
+ Helper::checkCounter();
+
+ // non-const versions
+ QCOMPARE_EQ(hash[keyView], keys.size()); // already there
+ Helper::checkCounter();
+
+ QCOMPARE_EQ(hash[otherKeyView], 0); // inserts
+ Helper::resetCounter();
+ hash[otherKeyView] = INT_MAX;
+ Helper::checkCounter();
+
+ if constexpr (IsMultiHash) {
+ hash.insert(key, keys.size());
+ QCOMPARE_EQ(hash.count(keyView), 2);
+
+ // not depending on which of the two the current implementation finds
+ QCOMPARE_NE(hash.value(keyView), 0);
+ QCOMPARE_NE(hash.value(keyView, -1000), -1000);
+ QCOMPARE_NE(std::as_const(hash)[keyView], 0);
+ QCOMPARE_NE(hash.find(keyView), hash.end());
+ QCOMPARE_NE(std::as_const(hash).find(keyView), hash.constEnd());
+ QCOMPARE_NE(hash.constFind(keyView), hash.constEnd());
+ QCOMPARE_NE(hash.equal_range(keyView), std::make_pair(hash.end(), hash.end()));
+ QCOMPARE_NE(std::as_const(hash).equal_range(keyView),
+ std::make_pair(hash.constEnd(), hash.constEnd()));
+
+ // QMultiHash-specific functions
+ QVERIFY(hash.contains(keyView, keys.size()));
+ QCOMPARE_EQ(hash.count(keyView, 0), 0);
+ QCOMPARE_EQ(hash.count(keyView, keys.size()), 2);
+ QCOMPARE_EQ(hash.values(keyView), QList<qsizetype>({ keys.size(), keys.size() }));
+
+ hash.insert(key, -keys.size());
+ QCOMPARE_EQ(hash.count(keyView), 3);
+ QCOMPARE_EQ(hash.find(keyView, 0), hash.end());
+ QCOMPARE_NE(hash.find(keyView, keys.size()), hash.end());
+ QCOMPARE_NE(hash.find(keyView, -keys.size()), hash.end());
+ QCOMPARE_EQ(std::as_const(hash).find(keyView, 0), hash.constEnd());
+ QCOMPARE_NE(std::as_const(hash).find(keyView, keys.size()), hash.constEnd());
+ QCOMPARE_NE(std::as_const(hash).find(keyView, -keys.size()), hash.constEnd());
+ QCOMPARE_EQ(hash.constFind(keyView, 0), hash.constEnd());
+ QCOMPARE_NE(hash.constFind(keyView, keys.size()), hash.constEnd());
+ QCOMPARE_NE(hash.constFind(keyView, -keys.size()), hash.constEnd());
+
+ // removals
+ QCOMPARE_EQ(hash.remove(keyView, -keys.size()), 1);
+ QCOMPARE_EQ(hash.remove(keyView), 2);
+ } else {
+ // removals
+ QCOMPARE_EQ(hash.remove(keyView), true);
+ }
+
+ QCOMPARE_EQ(hash.take(otherKeyView), INT_MAX);
+ QVERIFY(hash.isEmpty());
+ Helper::checkCounter();
+
+ // repeat with more keys
+ for (qsizetype i = 0; i < keys.size() - 1; ++i) {
+ hash.insert(keys[i], -(i + 1));
+ hash.insert(keys[i], i + 1);
+ }
+
+ QVERIFY(!hash.contains(keyView));
+ QCOMPARE_EQ(hash.count(keyView), 0);
+ QCOMPARE_EQ(hash.value(keyView), 0);
+ QCOMPARE_EQ(hash.value(keyView, -1), -1);
+ QCOMPARE_EQ(std::as_const(hash)[keyView], 0);
+ QCOMPARE_EQ(hash.find(keyView), hash.end());
+ QCOMPARE_EQ(hash.constFind(keyView), hash.constEnd());
+ Helper::checkCounter();
+#else
+ Q_UNUSED(keys);
+ Q_UNUSED(conv);
+ QSKIP("This feature requires C++20 (concepts)");
+#endif
+}
+
+template <template <typename, typename> class Hash, typename String, typename View>
+static void heterogeneousSearchTest(const QList<std::remove_const_t<String>> &keys)
+{
+ heterogeneousSearchTest<Hash, String, View>(keys, [](const String &s) { return View(s); });
+}
+
+template <template <typename, typename> class Hash, typename T>
+static void heterogeneousSearchLatin1String(T)
+{
+ if constexpr (!T::value) {
+ QSKIP("QLatin1StringView and QString do not have the same hash on this platform");
+ } else {
+ // similar to the above
+ auto toLatin1 = [](const QString &s) { return s.toLatin1(); };
+ heterogeneousSearchTest<Hash, QString, QLatin1StringView>({ "Hello", {}, "World" }, toLatin1);
+ }
+}
+
+void tst_QHash::heterogeneousSearch()
+{
+ heterogeneousSearchTest<QHash, QString, HeterogeneousHashingType>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::heterogeneousSearchConstKey()
+{
+ // QHash<const QString, X> seen in the wild (e.g. Qt Creator)
+ heterogeneousSearchTest<QHash, const QString, HeterogeneousHashingType>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::heterogeneousSearchByteArray()
+{
+ heterogeneousSearchTest<QHash, QByteArray, QByteArrayView>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::heterogeneousSearchString()
+{
+ heterogeneousSearchTest<QHash, QString, QStringView>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::heterogeneousSearchLatin1String()
+{
+ ::heterogeneousSearchLatin1String<QHash>(QHashHeterogeneousSearch<QString, QLatin1StringView>{});
+}
+
void tst_QHash::compare()
{
QHash<int, QString> hash1,hash2;
@@ -1099,14 +1537,144 @@ void tst_QHash::iterators()
}
}
+void tst_QHash::multihashIterators()
+{
+ QMultiHash<int, QString> hash;
+ QMap<int, QString> referenceMap;
+ QString testString = "Teststring %1-%2";
+ int i = 0;
+
+ // Add 5 elements for each key
+ for (i = 0; i < 10; ++i) {
+ for (int j = 0; j < 5; ++j)
+ hash.insert(i, testString.arg(i, j));
+ }
+
+ hash.squeeze();
+
+ // Verify that iteration is reproducible.
+
+ // STL iterator
+ QMultiHash<int, QString>::iterator stlIt;
+
+ for (stlIt = hash.begin(), i = 1; stlIt != hash.end(); ++stlIt, ++i)
+ referenceMap.insert(i, *stlIt);
+
+ stlIt = hash.begin();
+ QCOMPARE(*stlIt, referenceMap[1]);
+
+ for (i = 0; i < 5; ++i)
+ stlIt++;
+ QCOMPARE(*stlIt, referenceMap[6]);
+
+ for (i = 0; i < 44; ++i)
+ stlIt++;
+ QCOMPARE(*stlIt, referenceMap[50]);
+
+ // const STL iterator
+ referenceMap.clear();
+ QMultiHash<int, QString>::const_iterator cstlIt;
+
+ for (cstlIt = hash.cbegin(), i = 1; cstlIt != hash.cend(); ++cstlIt, ++i)
+ referenceMap.insert(i, *cstlIt);
+
+ cstlIt = hash.cbegin();
+ QCOMPARE(*cstlIt, referenceMap[1]);
+
+ for (i = 0; i < 5; ++i)
+ cstlIt++;
+ QCOMPARE(*cstlIt, referenceMap[6]);
+
+ for (i = 0; i < 44; ++i)
+ cstlIt++;
+ QCOMPARE(*cstlIt, referenceMap[50]);
+
+ // Java-Style iterator
+ referenceMap.clear();
+ QMultiHashIterator<int, QString> javaIt(hash);
+
+ // walk through
+ i = 0;
+ while (javaIt.hasNext()) {
+ ++i;
+ javaIt.next();
+ referenceMap.insert(i, javaIt.value());
+ }
+ javaIt.toFront();
+ i = 0;
+ while (javaIt.hasNext()) {
+ ++i;
+ javaIt.next();
+ QCOMPARE(javaIt.value(), referenceMap.value(i));
+ }
+
+ // peekNext()
+ javaIt.toFront();
+ javaIt.next();
+ QString nextValue;
+ while (javaIt.hasNext()) {
+ nextValue = javaIt.peekNext().value();
+ javaIt.next();
+ QCOMPARE(javaIt.value(), nextValue);
+ }
+}
+
+template<typename T>
+void iteratorsInEmptyHashTestMethod()
+{
+ T hash;
+ using ConstIter = typename T::const_iterator;
+ ConstIter it1 = hash.cbegin();
+ ConstIter it2 = hash.constBegin();
+ QVERIFY(it1 == it2 && it2 == ConstIter());
+ QVERIFY(!hash.isDetached());
+
+ ConstIter it3 = hash.cend();
+ ConstIter it4 = hash.constEnd();
+ QVERIFY(it3 == it4 && it4 == ConstIter());
+ QVERIFY(!hash.isDetached());
+
+ // to call const overloads of begin() and end()
+ const T hash2;
+ ConstIter it5 = hash2.begin();
+ ConstIter it6 = hash2.end();
+ QVERIFY(it5 == it6 && it6 == ConstIter());
+ QVERIFY(!hash2.isDetached());
+
+ T hash3;
+ using Iter = typename T::iterator;
+ Iter it7 = hash3.end();
+ QVERIFY(it7 == Iter());
+ QVERIFY(!hash3.isDetached());
+
+ Iter it8 = hash3.begin(); // calls detach()
+ QVERIFY(it8 == Iter());
+ QVERIFY(hash3.isDetached());
+}
+
+void tst_QHash::iteratorsInEmptyHash()
+{
+ iteratorsInEmptyHashTestMethod<QHash<int, QString>>();
+ if (QTest::currentTestFailed())
+ return;
+
+ iteratorsInEmptyHashTestMethod<QMultiHash<int, QString>>();
+}
+
void tst_QHash::keyIterator()
{
QHash<int, int> hash;
+ using KeyIterator = QHash<int, int>::key_iterator;
+ KeyIterator it1 = hash.keyBegin();
+ KeyIterator it2 = hash.keyEnd();
+ QVERIFY(it1 == it2 && it2 == KeyIterator());
+ QVERIFY(!hash.isDetached());
+
for (int i = 0; i < 100; ++i)
hash.insert(i, i*100);
- QHash<int, int>::key_iterator key_it = hash.keyBegin();
+ KeyIterator key_it = hash.keyBegin();
QHash<int, int>::const_iterator it = hash.cbegin();
for (int i = 0; i < 100; ++i) {
QCOMPARE(*key_it, it.key());
@@ -1121,20 +1689,54 @@ void tst_QHash::keyIterator()
QCOMPARE(*key_it, it.key());
QCOMPARE(*(key_it++), (it++).key());
if (key_it != hash.keyEnd()) {
- QVERIFY(it != hash.end());
+ QVERIFY(it != hash.cend());
++key_it;
++it;
if (key_it != hash.keyEnd())
QCOMPARE(*key_it, it.key());
else
- QVERIFY(it == hash.end());
+ QVERIFY(it == hash.cend());
}
QCOMPARE(std::count(hash.keyBegin(), hash.keyEnd(), 99), 1);
// DefaultConstructible test
- typedef QHash<int, int>::key_iterator keyIterator;
- static_assert(std::is_default_constructible<keyIterator>::value);
+ static_assert(std::is_default_constructible<KeyIterator>::value);
+}
+
+void tst_QHash::multihashKeyIterator()
+{
+ QMultiHash<int, int> hash;
+
+ using KeyIterator = QMultiHash<int, int>::key_iterator;
+ KeyIterator it1 = hash.keyBegin();
+ KeyIterator it2 = hash.keyEnd();
+ QVERIFY(it1 == it2 && it2 == KeyIterator());
+ QVERIFY(!hash.isDetached());
+
+ for (int i = 0; i < 10; ++i) {
+ for (int j = 0; j < 5; ++j)
+ hash.insert(i, i * 100 + j);
+ }
+
+ KeyIterator keyIt = hash.keyBegin();
+ QMultiHash<int, int>::const_iterator it = hash.cbegin();
+ while (keyIt != hash.keyEnd() && it != hash.cend()) {
+ QCOMPARE(*keyIt, it.key());
+ keyIt++;
+ it++;
+ }
+
+ keyIt = std::find(hash.keyBegin(), hash.keyEnd(), 5);
+ it = std::find(hash.cbegin(), hash.cend(), 5 * 100 + 2);
+
+ QVERIFY(keyIt != hash.keyEnd());
+ QCOMPARE(*keyIt, it.key());
+
+ QCOMPARE(std::count(hash.keyBegin(), hash.keyEnd(), 9), 5);
+
+ // DefaultConstructible test
+ static_assert(std::is_default_constructible<KeyIterator>::value);
}
void tst_QHash::keyValueIterator()
@@ -1179,7 +1781,7 @@ void tst_QHash::keyValueIterator()
++it;
++key_value_it;
- if (it != hash.end())
+ if (it != hash.cend())
QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
else
QVERIFY(key_value_it == hash.constKeyValueEnd());
@@ -1189,13 +1791,95 @@ void tst_QHash::keyValueIterator()
QCOMPARE(std::count(hash.constKeyValueBegin(), hash.constKeyValueEnd(), entry_type(key, value)), 1);
}
+void tst_QHash::multihashKeyValueIterator()
+{
+ QMultiHash<int, int> hash;
+ using EntryType = QHash<int, int>::const_key_value_iterator::value_type;
+
+ for (int i = 0; i < 10; ++i) {
+ for (int j = 0; j < 5; j++)
+ hash.insert(i, i * 100 + j);
+ }
+
+ auto keyValueIt = hash.constKeyValueBegin();
+ auto it = hash.cbegin();
+
+ for (int i = 0; i < hash.size(); ++i) {
+ QVERIFY(keyValueIt != hash.constKeyValueEnd());
+ QVERIFY(it != hash.cend());
+
+ EntryType pair(it.key(), it.value());
+ QCOMPARE(*keyValueIt, pair);
+ QCOMPARE(keyValueIt->first, pair.first);
+ QCOMPARE(keyValueIt->second, pair.second);
+ ++keyValueIt;
+ ++it;
+ }
+
+ QVERIFY(keyValueIt == hash.constKeyValueEnd());
+ QVERIFY(it == hash.cend());
+
+ int key = 5;
+ int value = key * 100 + 3;
+ EntryType pair(key, value);
+ keyValueIt = std::find(hash.constKeyValueBegin(), hash.constKeyValueEnd(), pair);
+ it = std::find(hash.cbegin(), hash.cend(), value);
+
+ QVERIFY(keyValueIt != hash.constKeyValueEnd());
+ QCOMPARE(*keyValueIt, EntryType(it.key(), it.value()));
+
+ key = 9;
+ value = key * 100 + 4;
+ const auto numItems =
+ std::count(hash.constKeyValueBegin(), hash.constKeyValueEnd(), EntryType(key, value));
+ QCOMPARE(numItems, 1);
+}
+
+template<typename T>
+void keyValueIteratorInEmptyHashTestMethod()
+{
+ T hash;
+ using ConstKeyValueIter = typename T::const_key_value_iterator;
+
+ ConstKeyValueIter it1 = hash.constKeyValueBegin();
+ ConstKeyValueIter it2 = hash.constKeyValueEnd();
+ QVERIFY(it1 == it2 && it2 == ConstKeyValueIter());
+ QVERIFY(!hash.isDetached());
+
+ const T hash2;
+ ConstKeyValueIter it3 = hash2.keyValueBegin();
+ ConstKeyValueIter it4 = hash2.keyValueEnd();
+ QVERIFY(it3 == it4 && it4 == ConstKeyValueIter());
+ QVERIFY(!hash.isDetached());
+
+ T hash3;
+ using KeyValueIter = typename T::key_value_iterator;
+
+ KeyValueIter it5 = hash3.keyValueEnd();
+ QVERIFY(it5 == KeyValueIter());
+ QVERIFY(!hash3.isDetached());
+
+ KeyValueIter it6 = hash3.keyValueBegin(); // calls detach()
+ QVERIFY(it6 == KeyValueIter());
+ QVERIFY(hash3.isDetached());
+}
+
+void tst_QHash::keyValueIteratorInEmptyHash()
+{
+ keyValueIteratorInEmptyHashTestMethod<QHash<int, int>>();
+ if (QTest::currentTestFailed())
+ return;
+
+ keyValueIteratorInEmptyHashTestMethod<QMultiHash<int, int>>();
+}
+
void tst_QHash::rehash_isnt_quadratic()
{
// this test should be incredibly slow if rehash() is quadratic
for (int j = 0; j < 5; ++j) {
- QMultiHash<int, int> testHash;
+ QHash<int, int> testHash;
for (int i = 0; i < 500000; ++i)
- testHash.insert(1, 1);
+ testHash.insert(i, 1);
}
}
@@ -1227,16 +1911,24 @@ void tst_QHash::dont_need_default_constructor()
void tst_QHash::qmultihash_specific()
{
QMultiHash<int, int> hash1;
+
+ QVERIFY(!hash1.contains(1));
+ QVERIFY(!hash1.contains(1, 2));
+ QVERIFY(!hash1.isDetached());
+
for (int i = 1; i <= 9; ++i) {
+ QVERIFY(!hash1.contains(i));
for (int j = 1; j <= i; ++j) {
int k = i * 10 + j;
QVERIFY(!hash1.contains(i, k));
hash1.insert(i, k);
QVERIFY(hash1.contains(i, k));
}
+ QVERIFY(hash1.contains(i));
}
for (int i = 1; i <= 9; ++i) {
+ QVERIFY(hash1.contains(i));
for (int j = 1; j <= i; ++j) {
int k = i * 10 + j;
QVERIFY(hash1.contains(i, k));
@@ -1244,26 +1936,26 @@ void tst_QHash::qmultihash_specific()
}
QVERIFY(hash1.contains(9, 99));
- QCOMPARE(hash1.count(), 45);
+ QCOMPARE(hash1.size(), 45);
hash1.remove(9, 99);
QVERIFY(!hash1.contains(9, 99));
- QCOMPARE(hash1.count(), 44);
+ QCOMPARE(hash1.size(), 44);
hash1.remove(9, 99);
QVERIFY(!hash1.contains(9, 99));
- QCOMPARE(hash1.count(), 44);
+ QCOMPARE(hash1.size(), 44);
hash1.remove(1, 99);
- QCOMPARE(hash1.count(), 44);
+ QCOMPARE(hash1.size(), 44);
hash1.insert(1, 99);
hash1.insert(1, 99);
- QCOMPARE(hash1.count(), 46);
+ QCOMPARE(hash1.size(), 46);
hash1.remove(1, 99);
- QCOMPARE(hash1.count(), 44);
+ QCOMPARE(hash1.size(), 44);
hash1.remove(1, 99);
- QCOMPARE(hash1.count(), 44);
+ QCOMPARE(hash1.size(), 44);
{
QMultiHash<int, int>::const_iterator i = hash1.constFind(1, 11);
@@ -1308,6 +2000,12 @@ void tst_QHash::qmultihash_specific()
QVERIFY(i.value() == 98);
}
+ QCOMPARE(hash1.count(9), 8);
+ QCOMPARE(hash1.size(), 44);
+ hash1.remove(9);
+ QCOMPARE(hash1.count(9), 0);
+ QCOMPARE(hash1.size(), 36);
+
{
QMultiHash<int, int> map1;
map1.insert(42, 1);
@@ -1322,15 +2020,16 @@ void tst_QHash::qmultihash_specific()
map2.insert(42, 1);
map2.insert(10, 2);
map2.insert(48, 3);
- QCOMPARE(map1.count(), map2.count());
+ QCOMPARE(map1.size(), map2.size());
QVERIFY(map1.remove(42,5));
+ QVERIFY(map1 != map2);
QVERIFY(map2.remove(42,5));
QVERIFY(map1 == map2);
QHash<int, int> hash;
hash.insert(-1, -1);
map2.unite(hash);
- QCOMPARE(map2.count(), 6);
+ QCOMPARE(map2.size(), 6);
QCOMPARE(map2[-1], -1);
}
}
@@ -1446,12 +2145,238 @@ void tst_QHash::qmultihash_qhash_rvalue_ref_unite()
}
}
-template <typename T>
-QList<T> sorted(const QList<T> &list)
+void tst_QHash::qmultihashUnite()
{
- QList<T> res = list;
- std::sort(res.begin(), res.end());
- return res;
+ // Joining two multi hashes, first is empty
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash2.emplace(0, "a");
+ hash2.emplace(1, "b");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+
+ hash1.unite(hash2);
+ // hash1 is empty, so we just share the data between hash1 and hash2
+ QCOMPARE(hash1.size(), 2);
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+ }
+ // Joining two multi hashes, second is empty
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash1.emplace(0, "a");
+ hash1.emplace(1, "b");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+
+ hash1.unite(hash2);
+ // hash2 is empty, so nothing happens
+ QVERIFY(hash2.isEmpty());
+ QVERIFY(!hash2.isDetached());
+ QCOMPARE(hash1.size(), 2);
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+ }
+ // Joining two multi hashes
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash1.emplace(0, "a");
+ hash1.emplace(1, "b");
+ hash2.emplace(0, "c");
+ hash2.emplace(1, "d");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 4);
+
+ hash1.unite(hash2);
+ QCOMPARE(hash1.size(), 4);
+ QCOMPARE(MyClass::copies, 2);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 6);
+ }
+
+ // operator+() uses unite() internally.
+
+ // using operator+(), hash1 is empty
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash2.emplace(0, "a");
+ hash2.emplace(1, "b");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+
+ auto hash3 = hash1 + hash2;
+ // hash1 is empty, so we just share the data between hash3 and hash2
+ QCOMPARE(hash1.size(), 0);
+ QCOMPARE(hash2.size(), 2);
+ QCOMPARE(hash3.size(), 2);
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+ }
+ // using operator+(), hash2 is empty
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash1.emplace(0, "a");
+ hash1.emplace(1, "b");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+
+ auto hash3 = hash1 + hash2;
+ // hash2 is empty, so we just share the data between hash3 and hash1
+ QCOMPARE(hash1.size(), 2);
+ QCOMPARE(hash2.size(), 0);
+ QCOMPARE(hash3.size(), 2);
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 2);
+ }
+ // using operator+()
+ {
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+ QMultiHash<int, MyClass> hash1;
+ QMultiHash<int, MyClass> hash2;
+ hash1.emplace(0, "a");
+ hash1.emplace(1, "b");
+ hash2.emplace(0, "c");
+ hash2.emplace(1, "d");
+
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 4);
+
+ auto hash3 = hash1 + hash2;
+ QCOMPARE(hash1.size(), 2);
+ QCOMPARE(hash2.size(), 2);
+ QCOMPARE(hash3.size(), 4);
+ QCOMPARE(MyClass::copies, 4);
+ QCOMPARE(MyClass::moves, 0);
+ QCOMPARE(MyClass::count, 8);
+ }
+}
+
+void tst_QHash::qmultihashSize()
+{
+ // QMultiHash has an extra m_size member that counts the number of values,
+ // while d->size (shared with QHash) counts the number of distinct keys.
+ {
+ QMultiHash<int, int> hash;
+ QCOMPARE(hash.size(), 0);
+ QVERIFY(hash.isEmpty());
+
+ hash.insert(0, 42);
+ QCOMPARE(hash.size(), 1);
+ QVERIFY(!hash.isEmpty());
+
+ hash.insert(0, 42);
+ QCOMPARE(hash.size(), 2);
+ QVERIFY(!hash.isEmpty());
+
+ hash.emplace(0, 42);
+ QCOMPARE(hash.size(), 3);
+ QVERIFY(!hash.isEmpty());
+
+ QCOMPARE(hash.take(0), 42);
+ QCOMPARE(hash.size(), 2);
+ QVERIFY(!hash.isEmpty());
+
+ QCOMPARE(hash.remove(0), 2);
+ QCOMPARE(hash.size(), 0);
+ QVERIFY(hash.isEmpty());
+ }
+
+ {
+ QMultiHash<int, int> hash;
+ hash.emplace(0, 0);
+ hash.emplace(0, 0);
+ QCOMPARE(hash.size(), 2);
+ QVERIFY(!hash.isEmpty());
+
+ hash.emplace(0, 1);
+ QCOMPARE(hash.size(), 3);
+ QVERIFY(!hash.isEmpty());
+
+ QCOMPARE(hash.remove(0, 0), 2);
+ QCOMPARE(hash.size(), 1);
+ QVERIFY(!hash.isEmpty());
+
+ hash.remove(0);
+ QCOMPARE(hash.size(), 0);
+ QVERIFY(hash.isEmpty());
+ }
+
+ {
+ QMultiHash<int, int> hash;
+
+ hash[0] = 0;
+ QCOMPARE(hash.size(), 1);
+ QVERIFY(!hash.isEmpty());
+
+ hash.replace(0, 1);
+ QCOMPARE(hash.size(), 1);
+ QVERIFY(!hash.isEmpty());
+
+ hash.insert(0, 1);
+ hash.erase(hash.cbegin());
+ QCOMPARE(hash.size(), 1);
+ QVERIFY(!hash.isEmpty());
+
+ hash.erase(hash.cbegin());
+ QCOMPARE(hash.size(), 0);
+ QVERIFY(hash.isEmpty());
+ }
+}
+
+void tst_QHash::qmultihashHeterogeneousSearch()
+{
+ heterogeneousSearchTest<QMultiHash, QString, HeterogeneousHashingType>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::qmultihashHeterogeneousSearchConstKey()
+{
+ heterogeneousSearchTest<QMultiHash, const QString, HeterogeneousHashingType>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::qmultihashHeterogeneousSearchByteArray()
+{
+ heterogeneousSearchTest<QMultiHash, QByteArray, QByteArrayView>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::qmultihashHeterogeneousSearchString()
+{
+ heterogeneousSearchTest<QMultiHash, QString, QStringView>({ "Hello", {}, "World" });
+}
+
+void tst_QHash::qmultihashHeterogeneousSearchLatin1String()
+{
+ ::heterogeneousSearchLatin1String<QMultiHash>(QHashHeterogeneousSearch<QString, QLatin1StringView>{});
}
void tst_QHash::keys_values_uniqueKeys()
@@ -1460,6 +2385,7 @@ void tst_QHash::keys_values_uniqueKeys()
QVERIFY(hash.uniqueKeys().isEmpty());
QVERIFY(hash.keys().isEmpty());
QVERIFY(hash.values().isEmpty());
+ QVERIFY(!hash.isDetached());
hash.insert("alpha", 1);
QVERIFY(sorted(hash.keys()) == (QList<QString>() << "alpha"));
@@ -1587,7 +2513,7 @@ void tst_QHash::twoArguments_qHash()
void tst_QHash::initializerList()
{
QHash<int, QString> hash = {{1, "bar"}, {1, "hello"}, {2, "initializer_list"}};
- QCOMPARE(hash.count(), 2);
+ QCOMPARE(hash.size(), 2);
QCOMPARE(hash[1], QString("hello"));
QCOMPARE(hash[2], QString("initializer_list"));
@@ -1597,9 +2523,9 @@ void tst_QHash::initializerList()
// QCOMPARE(stdh[1], QString("bar"));
QMultiHash<QString, int> multiHash{{"il", 1}, {"il", 2}, {"il", 3}};
- QCOMPARE(multiHash.count(), 3);
+ QCOMPARE(multiHash.size(), 3);
QList<int> values = multiHash.values("il");
- QCOMPARE(values.count(), 3);
+ QCOMPARE(values.size(), 3);
QHash<int, int> emptyHash{};
QVERIFY(emptyHash.isEmpty());
@@ -1771,7 +2697,7 @@ void tst_QHash::insert_hash()
hash.insert(hash2);
- QCOMPARE(hash.count(), 5);
+ QCOMPARE(hash.size(), 5);
for (int i = 0; i < 5; ++i)
QCOMPARE(hash[i], i);
}
@@ -1783,7 +2709,7 @@ void tst_QHash::insert_hash()
hash.insert(hash2);
- QCOMPARE(hash.count(), 1);
+ QCOMPARE(hash.size(), 1);
QCOMPARE(hash[0], 5);
}
{
@@ -1793,7 +2719,7 @@ void tst_QHash::insert_hash()
hash.insert(hash2);
- QCOMPARE(hash.count(), 1);
+ QCOMPARE(hash.size(), 1);
QCOMPARE(hash[0], 5);
QCOMPARE(hash, hash2);
}
@@ -1806,13 +2732,31 @@ void tst_QHash::insert_hash()
// insert into ourself, nothing should happen
hash.insert(hash);
- QCOMPARE(hash.count(), 3);
+ QCOMPARE(hash.size(), 3);
QCOMPARE(hash[0], 7);
QCOMPARE(hash[2], 5);
QCOMPARE(hash[7], 55);
}
}
+void tst_QHash::multiHashStoresInReverseInsertionOrder()
+{
+ const QString strings[] = {
+ u"zero"_s,
+ u"null"_s,
+ u"nada"_s,
+ };
+ {
+ QMultiHash<int, QString> hash;
+ for (const QString &string : strings)
+ hash.insert(0, string);
+ auto printOnFailure = qScopeGuard([&] { qDebug() << hash; });
+ QVERIFY(std::equal(hash.begin(), hash.end(),
+ std::rbegin(strings), std::rend(strings)));
+ printOnFailure.dismiss();
+ }
+}
+
void tst_QHash::emplace()
{
{
@@ -1976,5 +2920,322 @@ void tst_QHash::stdHash()
QVERIFY(!strings.contains("z"));
}
+void tst_QHash::countInEmptyHash()
+{
+ {
+ QHash<int, int> hash;
+ QCOMPARE(hash.size(), 0);
+ QCOMPARE(hash.count(42), 0);
+ }
+
+ {
+ QMultiHash<int, int> hash;
+ QCOMPARE(hash.size(), 0);
+ QCOMPARE(hash.count(42), 0);
+ QCOMPARE(hash.count(42, 1), 0);
+ }
+}
+
+void tst_QHash::removeInEmptyHash()
+{
+ {
+ QHash<QString, int> hash;
+ QCOMPARE(hash.remove("test"), false);
+ QVERIFY(!hash.isDetached());
+
+ using Iter = QHash<QString, int>::iterator;
+ const auto removed = hash.removeIf([](Iter) { return true; });
+ QCOMPARE(removed, 0);
+ }
+ {
+ QMultiHash<QString, int> hash;
+ QCOMPARE(hash.remove("key"), 0);
+ QCOMPARE(hash.remove("key", 1), 0);
+ QVERIFY(!hash.isDetached());
+
+ using Iter = QMultiHash<QString, int>::iterator;
+ const auto removed = hash.removeIf([](Iter) { return true; });
+ QCOMPARE(removed, 0);
+ }
+}
+
+template<typename T>
+void valueInEmptyHashTestFunction()
+{
+ T hash;
+ QCOMPARE(hash.value("key"), 0);
+ QCOMPARE(hash.value("key", -1), -1);
+ QVERIFY(hash.values().isEmpty());
+ QVERIFY(!hash.isDetached());
+
+ const T constHash;
+ QCOMPARE(constHash["key"], 0);
+}
+
+void tst_QHash::valueInEmptyHash()
+{
+ valueInEmptyHashTestFunction<QHash<QString, int>>();
+ if (QTest::currentTestFailed())
+ return;
+
+ valueInEmptyHashTestFunction<QMultiHash<QString, int>>();
+}
+
+void tst_QHash::fineTuningInEmptyHash()
+{
+ QHash<QString, int> hash;
+ QCOMPARE(hash.capacity(), 0);
+ hash.squeeze();
+ QCOMPARE(hash.capacity(), 0);
+ QVERIFY(qFuzzyIsNull(hash.load_factor()));
+ QVERIFY(!hash.isDetached());
+
+ hash.reserve(10);
+ QVERIFY(hash.capacity() >= 10);
+ hash.squeeze();
+ QVERIFY(hash.capacity() > 0);
+}
+
+void tst_QHash::reserveShared()
+{
+ QHash<char, char> hash;
+ hash.insert('c', 'c');
+ auto hash2 = hash;
+
+ QCOMPARE(hash2.capacity(), hash.capacity());
+ auto oldCap = hash.capacity();
+
+ hash2.reserve(100); // This shouldn't crash
+
+ QVERIFY(hash2.capacity() >= 100);
+ QCOMPARE(hash.capacity(), oldCap);
+}
+
+void tst_QHash::reserveLessThanCurrentAmount()
+{
+ {
+ QHash<int, int> hash;
+ for (int i = 0; i < 1000; ++i)
+ hash.insert(i, i * 10);
+
+ // This used to hang in an infinite loop: QTBUG-102067
+ hash.reserve(1);
+
+ // Make sure that hash still has all elements
+ for (int i = 0; i < 1000; ++i)
+ QCOMPARE(hash.value(i), i * 10);
+ }
+ {
+ QMultiHash<int, int> hash;
+ for (int i = 0; i < 1000; ++i) {
+ hash.insert(i, i * 10);
+ hash.insert(i, i * 10 + 1);
+ }
+
+ // This used to hang in infinite loop: QTBUG-102067
+ hash.reserve(1);
+
+ // Make sure that hash still has all elements
+ for (int i = 0; i < 1000; ++i)
+ QCOMPARE(hash.values(i), QList<int>({ i * 10 + 1, i * 10 }));
+ }
+}
+
+void tst_QHash::reserveKeepCapacity_data()
+{
+ QTest::addColumn<qsizetype>("requested");
+ auto addRow = [](qsizetype requested) {
+ QTest::addRow("%td", ptrdiff_t(requested)) << requested;
+ };
+
+ QHash<int, int> testHash = {{1, 1}};
+ qsizetype minCapacity = testHash.capacity();
+ addRow(minCapacity - 1);
+ addRow(minCapacity + 0);
+ addRow(minCapacity + 1);
+ addRow(2 * minCapacity - 1);
+ addRow(2 * minCapacity + 0);
+ addRow(2 * minCapacity + 1);
+}
+
+void tst_QHash::reserveKeepCapacity()
+{
+ QFETCH(qsizetype, requested);
+
+ QHash<qsizetype, qsizetype> hash;
+ hash.reserve(requested);
+ qsizetype initialCapacity = hash.capacity();
+ QCOMPARE_GE(initialCapacity, requested);
+
+ // insert this many elements into the hash
+ for (qsizetype i = 0; i < requested; ++i)
+ hash.insert(i, i);
+
+ // it mustn't have increased capacity after inserting the elements
+ QCOMPARE(hash.capacity(), initialCapacity);
+}
+
+void tst_QHash::QTBUG98265()
+{
+ QMultiHash<QUuid, QByteArray> a;
+ QMultiHash<QUuid, QByteArray> b;
+ a.insert(QUuid("3e0dfb4d-90eb-43a4-bd54-88f5b69832c1"), QByteArray());
+ b.insert(QUuid("1b710ada-3dd7-432e-b7c8-e852e59f46a0"), QByteArray());
+
+ QVERIFY(a != b);
+}
+
+/*
+ Calling functions which take a const-ref argument for a key with a reference
+ to a key inside the hash itself should keep the key valid as long as it is
+ needed. If not users may get hard-to-debug races where CoW should've
+ shielded them.
+*/
+void tst_QHash::detachAndReferences()
+{
+ // Repeat a few times because it's not a guarantee
+ for (int i = 0; i < 50; ++i) {
+ QHash<char, char> hash;
+ hash.insert('a', 'a');
+ hash.insert('b', 'a');
+ hash.insert('c', 'a');
+ hash.insert('d', 'a');
+ hash.insert('e', 'a');
+ hash.insert('f', 'a');
+ hash.insert('g', 'a');
+
+ QSemaphore sem;
+ QSemaphore sem2;
+ std::thread th([&sem, &sem2, hash]() mutable {
+ sem.release();
+ sem2.acquire();
+ hash.reserve(100); // [2]: ...then this rehashes directly, without detaching
+ });
+
+ // The key is a reference to an entry in the hash. If we were already
+ // detached then no problem occurs! The problem happens because _after_
+ // we detach but before using the key the other thread resizes and
+ // rehashes, leaving our const-ref dangling.
+ auto it = hash.constBegin();
+ const auto &key = it.key(); // [3]: leaving our const-refs dangling
+ auto kCopy = key;
+ const auto &value = it.value();
+ auto vCopy = value;
+ sem2.release();
+ sem.acquire();
+ hash.insert(key, value); // [1]: this detaches first...
+
+ th.join();
+ QCOMPARE(hash.size(), 7);
+ QVERIFY(hash.contains(kCopy));
+ QCOMPARE(hash.value(kCopy), vCopy);
+ }
+}
+
+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"_s);
+
+ for (auto it = hash.keyBegin(), end = hash.keyEnd(); it != end; ++it)
+ QVERIFY(!hash[*it].isEmpty());
+}
+
+void tst_QHash::squeeze()
+{
+ {
+ QHash<int, int> hash;
+ hash.reserve(1000);
+ for (int i = 0; i < 10; ++i)
+ hash.insert(i, i * 10);
+ QVERIFY(hash.isDetached());
+ const size_t buckets = hash.bucket_count();
+ const qsizetype size = hash.size();
+
+ hash.squeeze();
+
+ QVERIFY(hash.bucket_count() < buckets);
+ QCOMPARE(hash.size(), size);
+ for (int i = 0; i < size; ++i)
+ QCOMPARE(hash.value(i), i * 10);
+ }
+ {
+ QMultiHash<int, int> hash;
+ hash.reserve(1000);
+ for (int i = 0; i < 10; ++i) {
+ hash.insert(i, i * 10);
+ hash.insert(i, i * 10 + 1);
+ }
+ QVERIFY(hash.isDetached());
+ const size_t buckets = hash.bucket_count();
+ const qsizetype size = hash.size();
+
+ hash.squeeze();
+
+ QVERIFY(hash.bucket_count() < buckets);
+ QCOMPARE(hash.size(), size);
+ for (int i = 0; i < (size / 2); ++i)
+ QCOMPARE(hash.values(i), QList<int>({ i * 10 + 1, i * 10 }));
+ }
+}
+
+void tst_QHash::squeezeShared()
+{
+ {
+ QHash<int, int> hash;
+ hash.reserve(1000);
+ for (int i = 0; i < 10; ++i)
+ hash.insert(i, i * 10);
+
+ QHash<int, int> other = hash;
+
+ // Check that when squeezing a hash with shared d_ptr, the number of
+ // buckets actually decreases.
+ QVERIFY(!other.isDetached());
+ const size_t buckets = other.bucket_count();
+ const qsizetype size = other.size();
+
+ other.squeeze();
+
+ QCOMPARE(hash.bucket_count(), buckets);
+ QVERIFY(other.bucket_count() < buckets);
+
+ QCOMPARE(other.size(), size);
+ for (int i = 0; i < size; ++i)
+ QCOMPARE(other.value(i), i * 10);
+ }
+ {
+ QMultiHash<int, int> hash;
+ hash.reserve(1000);
+ for (int i = 0; i < 10; ++i) {
+ hash.insert(i, i * 10);
+ hash.insert(i, i * 10 + 1);
+ }
+
+ QMultiHash<int, int> other = hash;
+
+ // Check that when squeezing a hash with shared d_ptr, the number of
+ // buckets actually decreases.
+ QVERIFY(!other.isDetached());
+ const size_t buckets = other.bucket_count();
+ const qsizetype size = other.size();
+
+ other.squeeze();
+
+ QCOMPARE(hash.bucket_count(), buckets);
+ QVERIFY(other.bucket_count() < buckets);
+
+ QCOMPARE(other.size(), size);
+ for (int i = 0; i < (size / 2); ++i)
+ QCOMPARE(other.values(i), QList<int>({ i * 10 + 1, i * 10 }));
+ }
+}
+
QTEST_APPLESS_MAIN(tst_QHash)
#include "tst_qhash.moc"
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-18 00:36:56 +0000