diff options
Diffstat (limited to 'tests/auto/corelib/tools/qhash/tst_qhash.cpp')
-rw-r--r-- | tests/auto/corelib/tools/qhash/tst_qhash.cpp | 671 |
1 files changed, 583 insertions, 88 deletions
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp index bab22c454a..b3dbdfa40c 100644 --- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp +++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp @@ -1,35 +1,13 @@ -/**************************************************************************** -** -** 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> @@ -38,6 +16,8 @@ #include <qsemaphore.h> +using namespace Qt::StringLiterals; + class tst_QHash : public QObject { Q_OBJECT @@ -58,12 +38,24 @@ 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(); @@ -83,6 +75,7 @@ private slots: void eraseValidIteratorOnSharedHash(); void equal_range(); void insert_hash(); + void multiHashStoresInReverseInsertionOrder(); void emplace(); @@ -97,12 +90,18 @@ private slots: void fineTuningInEmptyHash(); void reserveShared(); + void reserveLessThanCurrentAmount(); + void reserveKeepCapacity_data(); + void reserveKeepCapacity(); void QTBUG98265(); void detachAndReferences(); void lookupUsingKeyIterator(); + + void squeeze(); + void squeezeShared(); }; struct IdentityTracker { @@ -186,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 @@ -202,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") ); @@ -214,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") ); @@ -222,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 @@ -297,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 ); { @@ -594,7 +593,7 @@ void tst_QHash::erase_edge_case() 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 (bucketForHash == numBuckets - 1) + if (qsizetype(bucketForHash) == numBuckets - 1) keys[index++] = i; } QCOMPARE(index, 2); // Sanity check. If this fails then the test needs an update! @@ -922,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(); } }; @@ -1155,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; @@ -1647,9 +1877,9 @@ 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); } } @@ -1706,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); @@ -1771,10 +2001,10 @@ void tst_QHash::qmultihash_specific() } QCOMPARE(hash1.count(9), 8); - QCOMPARE(hash1.count(), 44); + QCOMPARE(hash1.size(), 44); hash1.remove(9); QCOMPARE(hash1.count(9), 0); - QCOMPARE(hash1.count(), 36); + QCOMPARE(hash1.size(), 36); { QMultiHash<int, int> map1; @@ -1790,7 +2020,7 @@ 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)); @@ -1799,7 +2029,7 @@ void tst_QHash::qmultihash_specific() QHash<int, int> hash; hash.insert(-1, -1); map2.unite(hash); - QCOMPARE(map2.count(), 6); + QCOMPARE(map2.size(), 6); QCOMPARE(map2[-1], -1); } } @@ -2052,6 +2282,103 @@ void tst_QHash::qmultihashUnite() } } +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() { QMultiHash<QString, int> hash; @@ -2186,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")); @@ -2196,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()); @@ -2370,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); } @@ -2382,7 +2709,7 @@ void tst_QHash::insert_hash() hash.insert(hash2); - QCOMPARE(hash.count(), 1); + QCOMPARE(hash.size(), 1); QCOMPARE(hash[0], 5); } { @@ -2392,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); } @@ -2405,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() { { @@ -2579,13 +2924,13 @@ void tst_QHash::countInEmptyHash() { { QHash<int, int> hash; - QCOMPARE(hash.count(), 0); + QCOMPARE(hash.size(), 0); QCOMPARE(hash.count(42), 0); } { QMultiHash<int, int> hash; - QCOMPARE(hash.count(), 0); + QCOMPARE(hash.size(), 0); QCOMPARE(hash.count(42), 0); QCOMPARE(hash.count(42, 1), 0); } @@ -2666,6 +3011,70 @@ void tst_QHash::reserveShared() 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; @@ -2684,9 +3093,6 @@ void tst_QHash::QTBUG98265() */ void tst_QHash::detachAndReferences() { -#if !QT_CONFIG(cxx11_future) - QSKIP("This test requires cxx11_future") -#else // Repeat a few times because it's not a guarantee for (int i = 0; i < 50; ++i) { QHash<char, char> hash; @@ -2724,7 +3130,6 @@ void tst_QHash::detachAndReferences() QVERIFY(hash.contains(kCopy)); QCOMPARE(hash.value(kCopy), vCopy); } -#endif } void tst_QHash::lookupUsingKeyIterator() @@ -2736,11 +3141,101 @@ void tst_QHash::lookupUsingKeyIterator() 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); + 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" |