diff options
Diffstat (limited to 'tests/auto/corelib/tools/qset/tst_qset.cpp')
-rw-r--r-- | tests/auto/corelib/tools/qset/tst_qset.cpp | 381 |
1 files changed, 309 insertions, 72 deletions
diff --git a/tests/auto/corelib/tools/qset/tst_qset.cpp b/tests/auto/corelib/tools/qset/tst_qset.cpp index ee6cf7f533..116d38112b 100644 --- a/tests/auto/corelib/tools/qset/tst_qset.cpp +++ b/tests/auto/corelib/tools/qset/tst_qset.cpp @@ -1,39 +1,14 @@ -/**************************************************************************** -** -** 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$ -** -****************************************************************************/ - -#include <QtTest/QtTest> +// Copyright (C) 2016 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only + +#include <QTest> #include <qset.h> #include <qdebug.h> int toNumber(const QString &str) { int res = 0; - for (int i = 0; i < str.length(); ++i) + for (int i = 0; i < str.size(); ++i) res = (res * 10) + str[i].digitValue(); return res; } @@ -59,7 +34,9 @@ private slots: void begin(); void end(); void insert(); + void insertConstructionCounted(); void setOperations(); + void setOperationsOnEmptySet(); void stlIterator(); void stlMutableIterator(); void javaIterator(); @@ -68,6 +45,8 @@ private slots: void initializerList(); void qhash(); void intersects(); + void find(); + void values(); }; struct IdentityTracker { @@ -160,43 +139,44 @@ void tst_QSet::size() QSet<int> set; QVERIFY(set.size() == 0); QVERIFY(set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); + QVERIFY(!set.isDetached()); set.insert(1); QVERIFY(set.size() == 1); QVERIFY(!set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); set.insert(1); QVERIFY(set.size() == 1); QVERIFY(!set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); set.insert(2); QVERIFY(set.size() == 2); QVERIFY(!set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); set.remove(1); QVERIFY(set.size() == 1); QVERIFY(!set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); set.remove(1); QVERIFY(set.size() == 1); QVERIFY(!set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); set.remove(2); QVERIFY(set.size() == 0); QVERIFY(set.isEmpty()); - QVERIFY(set.count() == set.size()); + QVERIFY(set.size() == set.size()); QVERIFY(set.isEmpty() == set.empty()); } @@ -205,6 +185,7 @@ void tst_QSet::capacity() QSet<int> set; int n = set.capacity(); QVERIFY(n == 0); + QVERIFY(!set.isDetached()); for (int i = 0; i < 1000; ++i) { set.insert(i); @@ -238,8 +219,12 @@ void tst_QSet::reserve() void tst_QSet::squeeze() { QSet<int> set; - int n = set.capacity(); - QVERIFY(n == 0); + QCOMPARE(set.capacity(), 0); + + set.squeeze(); + QCOMPARE(set.capacity(), 0); + + QVERIFY(!set.isDetached()); set.reserve(1000); QVERIFY(set.capacity() >= 1000); @@ -247,27 +232,39 @@ void tst_QSet::squeeze() set.squeeze(); QVERIFY(set.capacity() < 100); - for (int i = 0; i < 512; ++i) + for (int i = 0; i < 500; ++i) set.insert(i); - QVERIFY(set.capacity() == 512); + QCOMPARE(set.size(), 500); + + // squeezed capacity for 500 elements + qsizetype capacity = set.capacity(); // current implementation: 512 + QCOMPARE_GE(capacity, set.size()); set.reserve(50000); - QVERIFY(set.capacity() >= 50000); + QVERIFY(set.capacity() >= 50000); // current implementation: 65536 set.squeeze(); - QVERIFY(set.capacity() == 512); + QCOMPARE(set.capacity(), capacity); + // removing elements does not shed capacity set.remove(499); - QVERIFY(set.capacity() == 512); + QCOMPARE(set.capacity(), capacity); set.insert(499); - QVERIFY(set.capacity() == 512); + QCOMPARE(set.capacity(), capacity); - set.insert(1000); - QVERIFY(set.capacity() == 1024); + // grow it beyond the current capacity + for (int i = set.size(); i <= capacity; ++i) + set.insert(i); + QCOMPARE(set.size(), capacity + 1); + QCOMPARE_GT(set.capacity(), capacity + 1);// current implementation: 2 * capacity (1024) for (int i = 0; i < 500; ++i) set.remove(i); + + // removing elements does not shed capacity + QCOMPARE_GT(set.capacity(), capacity + 1); + set.squeeze(); QVERIFY(set.capacity() < 100); } @@ -311,6 +308,7 @@ void tst_QSet::clear() set1.clear(); QVERIFY(set1.size() == 0); + QVERIFY(!set1.isDetached()); set1.insert("foo"); QVERIFY(set1.size() != 0); @@ -328,10 +326,9 @@ void tst_QSet::clear() void tst_QSet::cpp17ctad() { -#ifdef __cpp_deduction_guides #define QVERIFY_IS_SET_OF(obj, Type) \ QVERIFY2((std::is_same<decltype(obj), QSet<Type>>::value), \ - QMetaType::typeName(qMetaTypeId<decltype(obj)::value_type>())) + QMetaType::fromType<decltype(obj)::value_type>().name()) #define CHECK(Type, One, Two, Three) \ do { \ const Type v[] = {One, Two, Three}; \ @@ -348,29 +345,36 @@ void tst_QSet::cpp17ctad() CHECK(QString, QStringLiteral("one"), QStringLiteral("two"), QStringLiteral("three")); #undef QVERIFY_IS_SET_OF #undef CHECK -#else - QSKIP("This test requires C++17 Constructor Template Argument Deduction support enabled in the compiler."); -#endif } void tst_QSet::remove() { - QSet<QString> set1; + QSet<QString> set; + QCOMPARE(set.remove("test"), false); + QVERIFY(!set.isDetached()); + + const auto cnt = set.removeIf([](auto it) { + Q_UNUSED(it); + return true; + }); + QCOMPARE(cnt, 0); for (int i = 0; i < 500; ++i) - set1.insert(QString::number(i)); + set.insert(QString::number(i)); - QCOMPARE(set1.size(), 500); + QCOMPARE(set.size(), 500); for (int j = 0; j < 500; ++j) { - set1.remove(QString::number((j * 17) % 500)); - QCOMPARE(set1.size(), 500 - j - 1); + set.remove(QString::number((j * 17) % 500)); + QCOMPARE(set.size(), 500 - j - 1); } } void tst_QSet::contains() { QSet<QString> set1; + QVERIFY(!set1.contains("test")); + QVERIFY(!set1.isDetached()); for (int i = 0; i < 500; ++i) { QVERIFY(!set1.contains(QString::number(i))); @@ -395,6 +399,7 @@ void tst_QSet::containsSet() // empty set contains the empty set QVERIFY(set1.contains(set2)); + QVERIFY(!set1.isDetached()); for (int i = 0; i < 500; ++i) { set1.insert(QString::number(i)); @@ -416,6 +421,7 @@ void tst_QSet::containsSet() // the empty set doesn't contain a filled set QVERIFY(!set3.contains(set1)); + QVERIFY(!set3.isDetached()); // verify const signature const QSet<QString> set4; @@ -437,6 +443,8 @@ void tst_QSet::begin() QVERIFY(k == ell); QVERIFY(i == k); QVERIFY(j == ell); + QVERIFY(!set1.isDetached()); + QVERIFY(!set2.isDetached()); } set1.insert(44); @@ -466,6 +474,31 @@ void tst_QSet::begin() QVERIFY(i == k); QVERIFY(j == ell); } + + const QSet<int> set3; + QSet<int> set4 = set3; + + { + QSet<int>::const_iterator i = set3.begin(); + QSet<int>::const_iterator j = set3.cbegin(); + QSet<int>::const_iterator k = set4.begin(); + QVERIFY(i == j); + QVERIFY(k == j); + QVERIFY(!set3.isDetached()); + QVERIFY(set4.isDetached()); + } + + set4.insert(1); + + { + QSet<int>::const_iterator i = set3.begin(); + QSet<int>::const_iterator j = set3.cbegin(); + QSet<int>::const_iterator k = set4.begin(); + QVERIFY(i == j); + QVERIFY(k != j); + QVERIFY(!set3.isDetached()); + QVERIFY(set4.isDetached()); + } } void tst_QSet::end() @@ -486,6 +519,9 @@ void tst_QSet::end() QVERIFY(set1.constBegin() == set1.constEnd()); QVERIFY(set2.constBegin() == set2.constEnd()); + + QVERIFY(!set1.isDetached()); + QVERIFY(!set2.isDetached()); } set1.insert(44); @@ -526,6 +562,37 @@ void tst_QSet::end() set2.clear(); QVERIFY(set1.constBegin() == set1.constEnd()); QVERIFY(set2.constBegin() == set2.constEnd()); + + const QSet<int> set3; + QSet<int> set4 = set3; + + { + QSet<int>::const_iterator i = set3.end(); + QSet<int>::const_iterator j = set3.cend(); + QSet<int>::const_iterator k = set4.end(); + QVERIFY(i == j); + QVERIFY(k == j); + QVERIFY(!set3.isDetached()); + QVERIFY(!set4.isDetached()); + + QVERIFY(set3.constBegin() == set3.constEnd()); + QVERIFY(set4.constBegin() == set4.constEnd()); + } + + set4.insert(1); + + { + QSet<int>::const_iterator i = set3.end(); + QSet<int>::const_iterator j = set3.cend(); + QSet<int>::const_iterator k = set4.end(); + QVERIFY(i == j); + QVERIFY(k == j); + QVERIFY(!set3.isDetached()); + QVERIFY(set4.isDetached()); + + QVERIFY(set3.constBegin() == set3.constEnd()); + QVERIFY(set4.constBegin() != set4.constEnd()); + } } void tst_QSet::insert() @@ -579,6 +646,84 @@ void tst_QSet::insert() } } +struct ConstructionCounted +{ + ConstructionCounted(int i) : i(i) { } + ConstructionCounted(ConstructionCounted &&other) noexcept + : i(other.i), copies(other.copies), moves(other.moves + 1) + { + // set to some easily noticeable values + other.i = -64; + other.copies = -64; + other.moves = -64; + } + ConstructionCounted &operator=(ConstructionCounted &&other) noexcept + { + ConstructionCounted moved = std::move(other); + std::swap(*this, moved); + return *this; + } + ConstructionCounted(const ConstructionCounted &other) noexcept + : i(other.i), copies(other.copies + 1), moves(other.moves) + { + } + ConstructionCounted &operator=(const ConstructionCounted &other) noexcept + { + ConstructionCounted copy = other; + std::swap(*this, copy); + return *this; + } + ~ConstructionCounted() = default; + + friend bool operator==(const ConstructionCounted &lhs, const ConstructionCounted &rhs) + { + return lhs.i == rhs.i; + } + + QString toString() { return QString::number(i); } + + int i; + int copies = 0; + int moves = 0; +}; + +size_t qHash(const ConstructionCounted &c, std::size_t seed = 0) +{ + return qHash(c.i, seed); +} + +void tst_QSet::insertConstructionCounted() +{ + QSet<ConstructionCounted> set; + + // copy-insert + ConstructionCounted toCopy(7); + auto inserted = set.insert(toCopy); + QCOMPARE(set.size(), 1); + auto element = set.begin(); + QCOMPARE(inserted, element); + QCOMPARE(inserted->copies, 1); + QCOMPARE(inserted->moves, 1); + QCOMPARE(inserted->i, 7); + + // move-insert + ConstructionCounted toMove(8); + inserted = set.insert(std::move(toMove)); + element = set.find(8); + QCOMPARE(set.size(), 2); + QVERIFY(element != set.end()); + QCOMPARE(inserted, element); + QCOMPARE(inserted->copies, 0); + QCOMPARE(inserted->moves, 1); + QCOMPARE(inserted->i, 8); + + inserted = set.insert(std::move(toCopy)); // move-insert an existing value + QCOMPARE(set.size(), 2); + // The previously existing key is used as they compare equal: + QCOMPARE(inserted->copies, 1); + QCOMPARE(inserted->moves, 1); +} + void tst_QSet::setOperations() { QSet<QString> set1, set2; @@ -677,6 +822,44 @@ void tst_QSet::setOperations() QVERIFY(set18 == set8); } +void tst_QSet::setOperationsOnEmptySet() +{ + { + // Both sets are empty + QSet<int> set1; + QSet<int> set2; + + set1.unite(set2); + QVERIFY(set1.isEmpty()); + QVERIFY(!set1.isDetached()); + + set1.intersect(set2); + QVERIFY(set1.isEmpty()); + QVERIFY(!set1.isDetached()); + + set1.subtract(set2); + QVERIFY(set1.isEmpty()); + QVERIFY(!set1.isDetached()); + } + { + // Second set is not empty + QSet<int> empty; + QSet<int> nonEmpty { 1, 2, 3 }; + + empty.intersect(nonEmpty); + QVERIFY(empty.isEmpty()); + QVERIFY(!empty.isDetached()); + + empty.subtract(nonEmpty); + QVERIFY(empty.isEmpty()); + QVERIFY(!empty.isDetached()); + + empty.unite(nonEmpty); + QCOMPARE(empty, nonEmpty); + QVERIFY(!empty.isDetached()); + } +} + void tst_QSet::stlIterator() { QSet<QString> set1; @@ -756,13 +939,11 @@ void tst_QSet::javaIterator() QSetIterator<QString> i(set1); QSetIterator<QString> j(set1); - int n = 0; while (i.hasNext()) { QVERIFY(j.hasNext()); set1.remove(i.peekNext()); sum1 += toNumber(i.next()); sum2 += toNumber(j.next()); - ++n; } QVERIFY(!j.hasNext()); QVERIFY(sum1 == 24999 * 25000 / 2); @@ -840,7 +1021,7 @@ void tst_QSet::makeSureTheComfortFunctionsCompile() void tst_QSet::initializerList() { QSet<int> set = {1, 1, 2, 3, 4, 5}; - QCOMPARE(set.count(), 5); + QCOMPARE(set.size(), 5); QVERIFY(set.contains(1)); QVERIFY(set.contains(2)); QVERIFY(set.contains(3)); @@ -849,7 +1030,7 @@ void tst_QSet::initializerList() // check _which_ of the equal elements gets inserted (in the QHash/QMap case, it's the last): const QSet<IdentityTracker> set2 = {{1, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; - QCOMPARE(set2.count(), 5); + QCOMPARE(set2.size(), 5); const int dummy = -1; const IdentityTracker searchKey = {1, dummy}; QCOMPARE(set2.find(searchKey)->id, 0); @@ -868,23 +1049,33 @@ void tst_QSet::qhash() // { // create some deterministic initial state: - qSetGlobalQHashSeed(0); + QHashSeed::setDeterministicGlobalSeed(); QSet<int> s1; s1.reserve(4); s1 << 400 << 300 << 200 << 100; - // also change the seed: - qSetGlobalQHashSeed(0x10101010); + int retries = 128; + while (--retries >= 0) { + // reset the global seed to something different + QHashSeed::resetRandomGlobalSeed(); - QSet<int> s2; - s2.reserve(100); // provoke different bucket counts - s2 << 100 << 200 << 300 << 400; // and insert elements in different order, too + QSet<int> s2; + s2.reserve(100); // provoke different bucket counts + s2 << 100 << 200 << 300 << 400; // and insert elements in different order, too + QVERIFY(s1.capacity() != s2.capacity()); - QVERIFY(s1.capacity() != s2.capacity()); - QCOMPARE(s1, s2); - QVERIFY(!std::equal(s1.cbegin(), s1.cend(), s2.cbegin())); // verify that the order _is_ different - QCOMPARE(qHash(s1), qHash(s2)); + // see if we got a _different_ order + if (std::equal(s1.cbegin(), s1.cend(), s2.cbegin())) + continue; + + // check if the two QHashes still compare equal and produce the + // same hash, despite containing elements in different orders + QCOMPARE(s1, s2); + QCOMPARE(qHash(s1), qHash(s2)); + } + QVERIFY2(retries != 0, "Could not find a QSet with a different order of elements even " + "after a lot of retries. This is unlikely, but possible."); } // @@ -903,6 +1094,8 @@ void tst_QSet::intersects() QVERIFY(!s1.intersects(s1)); QVERIFY(!s1.intersects(s2)); + QVERIFY(!s1.isDetached()); + QVERIFY(!s2.isDetached()); s1 << 100; QVERIFY(s1.intersects(s1)); @@ -914,7 +1107,7 @@ void tst_QSet::intersects() s1 << 200; QVERIFY(s1.intersects(s2)); - qSetGlobalQHashSeed(0x10101010); + QHashSeed::resetRandomGlobalSeed(); QSet<int> s3; s3 << 500; QVERIFY(!s1.intersects(s3)); @@ -922,6 +1115,50 @@ void tst_QSet::intersects() QVERIFY(s1.intersects(s3)); } +void tst_QSet::find() +{ + QSet<int> set; + QCOMPARE(set.find(1), set.end()); + QCOMPARE(set.constFind(1), set.constEnd()); + QVERIFY(!set.isDetached()); + + set.insert(1); + set.insert(2); + + QVERIFY(set.find(1) != set.end()); + QVERIFY(set.constFind(2) != set.constEnd()); + QVERIFY(set.find(3) == set.end()); + QVERIFY(set.constFind(4) == set.constEnd()); +} + +template<typename T> +QList<T> sorted(const QList<T> &list) +{ + QList<T> res = list; + std::sort(res.begin(), res.end()); + return res; +} + +void tst_QSet::values() +{ + QSet<int> set; + QVERIFY(set.values().isEmpty()); + QVERIFY(!set.isDetached()); + + set.insert(1); + QCOMPARE(set.values(), QList<int> { 1 }); + + set.insert(10); + set.insert(5); + set.insert(2); + + QCOMPARE(sorted(set.values()), QList<int>({ 1, 2, 5, 10 })); + + set.remove(5); + + QCOMPARE(sorted(set.values()), QList<int>({ 1, 2, 10 })); +} + QTEST_APPLESS_MAIN(tst_QSet) #include "tst_qset.moc" |