From 14090760a87f23509b7bb5ad846537c766cb44a5 Mon Sep 17 00:00:00 2001 From: Giuseppe D'Angelo Date: Wed, 22 Jul 2020 14:07:48 +0200 Subject: Long Live QMap as a refcounted std::map! ... and QMultiMap as std::multimap. Just use the implementation from the STL; we can't really claim that our code is much better than STL's, or does things any differently (de facto they're both red-black trees). Decouple QMultiMap from QMap, by making it NOT inherit from QMap any longer. This completes the deprecation started in 5.15: QMap now does not store duplicated keys any more. Something to establish is where to put the QExplictlySharedDataPointer replcement that is in there as an ad-hoc solution. There's a number of patches in-flight by Marc that try to introduce the same (or very similar) functionality. Miscellanea changes to the Q(Multi)Map code itself: * consistently use size_type instead of int; * pass iterators by value; * drop QT_STRICT_ITERATORS; * iterators implictly convert to const_iterators, and APIs take const_iterators; * iterators are just bidirectional and not random access; * added noexcept where it makes sense; * "inline" dropped (churn); * qMapLessThanKey dropped (undocumented, 0 hits in Qt, 1 hit in KDE); * operator== on Q(Multi)Map requires operator== on the key type (we're checking for equality, not equivalence!). Very few breakages occur in qtbase. [ChangeLog][Potentially Source-Incompatible Changes] QMap does not support multiple equivalent keys any more. Any related functionality has been removed from QMap, following the deprecation that happened in Qt 5.15. Use QMultiMap for this use case. [ChangeLog][Potentially Source-Incompatible Changes] QMap and QMultiMap iterators random-access API have been removed. Note that the iterators have always been just bidirectional; moving an iterator by N positions can still be achieved using std::next or std::advance, at the same cost as before (O(N)). [ChangeLog][Potentially Source-Incompatible Changes] QMultiMap does not inherit from QMap any more. Amongst other things, this means that iterators on a QMultiMap now belong to the QMultiMap class (and not to the QMap class); new Java iterators have been added. Change-Id: I5a0fe9b020f92c21b37065a1defff783b5d2b7a9 Reviewed-by: Thiago Macieira Reviewed-by: Lars Knoll --- .../corelib/tools/collections/tst_collections.cpp | 73 ++++++++++++---------- tests/auto/corelib/tools/qmap/tst_qmap.cpp | 71 ++++++++++----------- 2 files changed, 74 insertions(+), 70 deletions(-) (limited to 'tests/auto/corelib/tools') diff --git a/tests/auto/corelib/tools/collections/tst_collections.cpp b/tests/auto/corelib/tools/collections/tst_collections.cpp index 2cab6312aa..e5cfb0fbad 100644 --- a/tests/auto/corelib/tools/collections/tst_collections.cpp +++ b/tests/auto/corelib/tools/collections/tst_collections.cpp @@ -2609,6 +2609,7 @@ class LessThanComparable { public: bool operator<(const LessThanComparable &) const { return true; } + bool operator==(const LessThanComparable &) const { return true; } }; class EqualsComparable @@ -2937,20 +2938,6 @@ void tst_Collections::forwardDeclared() } } -class alignas(4) Aligned4 -{ - char i; -public: - Aligned4(int i = 0) : i(i) {} - - enum { PreferredAlignment = 4 }; - - inline bool operator==(const Aligned4 &other) const { return i == other.i; } - inline bool operator<(const Aligned4 &other) const { return i < other.i; } - friend inline size_t qHash(const Aligned4 &a) { return qHash(a.i); } -}; -static_assert(alignof(Aligned4) % 4 == 0); - #if defined(Q_PROCESSOR_ARM) # if defined(Q_COMPILER_ALIGNAS) && defined(__BIGGEST_ALIGNMENT__) // On ARM __BIGGEST_ALIGNMENT__ must be multiplied by 8 to @@ -2963,18 +2950,29 @@ static_assert(alignof(Aligned4) % 4 == 0); # define BIGGEST_ALIGNMENT_TO_TEST 128 #endif -class alignas(BIGGEST_ALIGNMENT_TO_TEST) AlignedBiggest +template +class alignas(Alignment) AlignedClass { char i; + public: - AlignedBiggest(int i = 0) : i(i) {} + AlignedClass(int i = 0) : i(i) {} - enum { PreferredAlignment = BIGGEST_ALIGNMENT_TO_TEST }; + enum { PreferredAlignment = Alignment }; - inline bool operator==(const AlignedBiggest &other) const { return i == other.i; } - inline bool operator<(const AlignedBiggest &other) const { return i < other.i; } - friend inline int qHash(const AlignedBiggest &a) { return qHash(a.i); } + inline bool operator==(const AlignedClass &other) const { return i == other.i; } + inline bool operator<(const AlignedClass &other) const { return i < other.i; } + friend inline int qHash(const AlignedClass &a) { return qHash(a.i); } }; + +using Aligned4 = AlignedClass<4>; +static_assert(alignof(Aligned4) % 4 == 0); + +using AlignedStdMax = AlignedClass; +static_assert(alignof(AlignedStdMax) % alignof(std::max_align_t) == 0); + +using AlignedBiggest = AlignedClass; +static_assert(BIGGEST_ALIGNMENT_TO_TEST > alignof(std::max_align_t), "Not overly aligned"); static_assert(alignof(AlignedBiggest) % BIGGEST_ALIGNMENT_TO_TEST == 0); template @@ -3032,18 +3030,29 @@ void testAssociativeContainerAlignment() void tst_Collections::alignment() { - testVectorAlignment>(); - testVectorAlignment>(); - testContiguousCacheAlignment>(); - testContiguousCacheAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); - testAssociativeContainerAlignment>(); + testVectorAlignment >(); + testVectorAlignment >(); + testVectorAlignment >(); + + testContiguousCacheAlignment >(); + testContiguousCacheAlignment >(); + testContiguousCacheAlignment >(); + + // there's no guarentee that std::map supports over-aligned types + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); + testAssociativeContainerAlignment >(); } #ifndef QT_NO_TEMPLATE_TEMPLATE_PARAMETERS diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index b812eb89a1..c8a228f8dd 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -36,8 +36,8 @@ class tst_QMap : public QObject { Q_OBJECT protected: - template - void sanityCheckTree(const QMap &m, int calledFromLine); + template + void sanityCheckTree(const Map &m, int calledFromLine); public slots: void init(); private slots: @@ -119,15 +119,15 @@ QDebug operator << (QDebug d, const MyClass &c) { return d; } -template -void tst_QMap::sanityCheckTree(const QMap &m, int calledFromLine) +template +void tst_QMap::sanityCheckTree(const Map &m, int calledFromLine) { QString possibleFrom; possibleFrom.setNum(calledFromLine); possibleFrom = "Called from line: " + possibleFrom; int count = 0; - typename QMap::const_iterator oldite = m.constBegin(); - for (typename QMap::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) { + typename Map::const_iterator oldite = m.constBegin(); + for (typename Map::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) { count++; bool oldIteratorIsLarger = i.key() < oldite.key(); QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8()); @@ -594,7 +594,7 @@ void tst_QMap::contains() void tst_QMap::find() { - QMap map1; + QMultiMap map1; QString testString="Teststring %0"; QString compareString; int i,count=0; @@ -614,7 +614,7 @@ void tst_QMap::find() QCOMPARE(map1.count(4), i - 2); } - QMap::const_iterator it=map1.constFind(4); + QMultiMap::const_iterator it=map1.constFind(4); for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) { compareString = testString.arg(i); @@ -627,7 +627,7 @@ void tst_QMap::find() void tst_QMap::constFind() { - QMap map1; + QMultiMap map1; QString testString="Teststring %0"; QString compareString; int i,count=0; @@ -648,7 +648,7 @@ void tst_QMap::constFind() map1.insertMulti(4, compareString); } - QMap::const_iterator it=map1.constFind(4); + QMultiMap::const_iterator it=map1.constFind(4); for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) { compareString = testString.arg(i); @@ -661,7 +661,7 @@ void tst_QMap::constFind() void tst_QMap::lowerUpperBound() { - QMap map1; + QMultiMap map1; map1.insert(1, "one"); map1.insert(5, "five"); @@ -712,7 +712,7 @@ void tst_QMap::lowerUpperBound() void tst_QMap::mergeCompare() { - QMap map1, map2, map3, map1b, map2b; + QMultiMap map1, map2, map3, map1b, map2b; map1.insert(1,"ett"); map1.insert(3,"tre"); @@ -770,13 +770,13 @@ void tst_QMap::iterators() QMap::iterator stlIt = map.begin(); QCOMPARE(stlIt.value(), QLatin1String("Teststring 1")); - stlIt+=5; + std::advance(stlIt, 5); QCOMPARE(stlIt.value(), QLatin1String("Teststring 6")); stlIt++; QCOMPARE(stlIt.value(), QLatin1String("Teststring 7")); - stlIt-=3; + std::advance(stlIt, -3); QCOMPARE(stlIt.value(), QLatin1String("Teststring 4")); stlIt--; @@ -791,13 +791,13 @@ void tst_QMap::iterators() QMap::const_iterator cstlIt = map.constBegin(); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 1")); - cstlIt+=5; + std::advance(cstlIt, 5); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 6")); cstlIt++; QCOMPARE(cstlIt.value(), QLatin1String("Teststring 7")); - cstlIt-=3; + std::advance(cstlIt, -3); QCOMPARE(cstlIt.value(), QLatin1String("Teststring 4")); cstlIt--; @@ -926,28 +926,23 @@ void tst_QMap::keyValueIterator() void tst_QMap::keys_values_uniqueKeys() { - QMap map; - QVERIFY(map.uniqueKeys().isEmpty()); + QMultiMap map; QVERIFY(map.keys().isEmpty()); QVERIFY(map.values().isEmpty()); map.insertMulti("alpha", 1); QVERIFY(map.keys() == (QList() << "alpha")); - QVERIFY(map.uniqueKeys() == map.keys()); QVERIFY(map.values() == (QList() << 1)); map.insertMulti("beta", -2); QVERIFY(map.keys() == (QList() << "alpha" << "beta")); - QVERIFY(map.keys() == map.uniqueKeys()); QVERIFY(map.values() == (QList() << 1 << -2)); map.insertMulti("alpha", 2); - QVERIFY(map.uniqueKeys() == (QList() << "alpha" << "beta")); QVERIFY(map.keys() == (QList() << "alpha" << "alpha" << "beta")); QVERIFY(map.values() == (QList() << 2 << 1 << -2)); map.insertMulti("beta", 4); - QVERIFY(map.uniqueKeys() == (QList() << "alpha" << "beta")); QVERIFY(map.keys() == (QList() << "alpha" << "alpha" << "beta" << "beta")); QVERIFY(map.values() == (QList() << 2 << 1 << 4 << -2)); } @@ -1077,14 +1072,14 @@ void tst_QMap::const_shared_null() void tst_QMap::equal_range() { - QMap map; - const QMap &cmap = map; + QMultiMap map; + const QMultiMap &cmap = map; - QPair::iterator, QMap::iterator> result = map.equal_range(0); + QPair::iterator, QMultiMap::iterator> result = map.equal_range(0); QCOMPARE(result.first, map.end()); QCOMPARE(result.second, map.end()); - QPair::const_iterator, QMap::const_iterator> cresult = cmap.equal_range(0); + QPair::const_iterator, QMultiMap::const_iterator> cresult = cmap.equal_range(0); QCOMPARE(cresult.first, cmap.cend()); QCOMPARE(cresult.second, cmap.cend()); @@ -1294,10 +1289,10 @@ void tst_QMap::insertMap() // make sure this isn't adding multiple entries with the // same key to the QMap. QMap map; - QMultiMap map2; - map2.insert(0, 0); + map.insert(0, 0); + + QMap map2; map2.insert(0, 1); - map2.insert(0, 2); map.insert(map2); @@ -1452,11 +1447,11 @@ void tst_QMap::testInsertWithHint() void tst_QMap::testInsertMultiWithHint() { - QMap map; + QMultiMap map; map.insertMulti(map.end(), 64, 65); - map[128] = 129; - map[256] = 257; + map.insert(128, 129); + map.insert(256, 257); sanityCheckTree(map, __LINE__); map.insertMulti(map.end(), 512, 513); @@ -1467,11 +1462,11 @@ void tst_QMap::testInsertMultiWithHint() sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 6); - QMap::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint + QMultiMap::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 7); - QMap::iterator j = map.insertMulti(map.constBegin(), 69, 66); + QMultiMap::iterator j = map.insertMulti(map.constBegin(), 69, 66); sanityCheckTree(map, __LINE__); QCOMPARE(map.size(), 8); @@ -1502,14 +1497,14 @@ void tst_QMap::testInsertMultiWithHint() void tst_QMap::eraseValidIteratorOnSharedMap() { - QMap a, b; + QMultiMap a, b; a.insert(10, 10); a.insertMulti(10, 40); a.insertMulti(10, 25); a.insertMulti(10, 30); a.insert(20, 20); - QMap::iterator i = a.begin(); + QMultiMap::iterator i = a.begin(); while (i.value() != 25) ++i; @@ -1529,12 +1524,12 @@ void tst_QMap::eraseValidIteratorOnSharedMap() QCOMPARE(itemsWith10, 4); // Border cases - QMap ms1, ms2, ms3; + QMultiMap ms1, ms2, ms3; ms1.insert("foo", "bar"); ms1.insertMulti("foo", "quux"); ms1.insertMulti("foo", "bar"); - QMap ::iterator si = ms1.begin(); + QMultiMap ::iterator si = ms1.begin(); ms2 = ms1; ms1.erase(si); si = ms1.begin(); -- cgit v1.2.3