diff options
Diffstat (limited to 'tests/auto/corelib/tools/qlist/tst_qlist.cpp')
| -rw-r--r-- | tests/auto/corelib/tools/qlist/tst_qlist.cpp | 1251 |
1 files changed, 1186 insertions, 65 deletions
diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index 323c1f5136..35d69e8433 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -1,43 +1,18 @@ -/**************************************************************************** -** -** Copyright (C) 2021 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) 2021 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only #include <QTest> #include <QAtomicInt> #include <QThread> #include <QSemaphore> -#include <QScopedValueRollback> +#include <QAtomicScopedValueRollback> #include <qlist.h> -#if __cplusplus >= 202002L && (!defined(_GLIBCXX_RELEASE) || _GLIBCXX_RELEASE >= 11) +#ifdef QT_COMPILER_HAS_LWG3346 # if __has_include(<concepts>) # include <concepts> -# if defined(__cpp_concepts) +# if defined(__cpp_lib_concepts) && __cpp_lib_concepts >= 202002L static_assert(std::contiguous_iterator<QList<int>::iterator>); static_assert(std::contiguous_iterator<QList<int>::const_iterator>); # endif @@ -159,6 +134,7 @@ struct Custom { i = 0; counter.fetchAndAddRelaxed(-1); state = Destructed; + QVERIFY(heapData.use_count() > 0); // otherwise it's double free } bool operator ==(const Custom &other) const @@ -187,6 +163,9 @@ struct Custom { char i; // used to identify orgin of an instance private: Custom *that; // used to check if an instance was moved + // shared_ptr triggers ASan/LSan and can track if double free happens, which + // is convenient to ensure there's no malfunctioning QList APIs + std::shared_ptr<int> heapData = std::shared_ptr<int>(new int(42)); enum State { Constructed = 106, Destructed = 110 }; State state; @@ -252,6 +231,16 @@ private slots: void appendCustom() const { append<Custom>(); } void appendRvalue() const; void appendList() const; + void assignEmpty() const; + void assignInt() const { assign<int>(); } + void assignMovable() const { assign<Movable>(); } + void assignCustom() const { assign<Custom>(); } + void assignUsesPrependBuffer_int_data() { assignUsesPrependBuffer_data(); } + void assignUsesPrependBuffer_int() const { assignUsesPrependBuffer<int>(); } + void assignUsesPrependBuffer_Movable_data() { assignUsesPrependBuffer_data(); } + void assignUsesPrependBuffer_Movable() const { assignUsesPrependBuffer<Movable>(); } + void assignUsesPrependBuffer_Custom_data() { assignUsesPrependBuffer_data(); } + void assignUsesPrependBuffer_Custom() const { assignUsesPrependBuffer<Custom>(); } void at() const; void capacityInt() const { capacity<int>(); } void capacityMovable() const { capacity<Movable>(); } @@ -314,6 +303,7 @@ private slots: void prependInt() const { prepend<int>(); } void prependMovable() const { prepend<Movable>(); } void prependCustom() const { prepend<Custom>(); } + void prependRvalue() const; void qhashInt() const { qhash<int>(); } void qhashMovable() const { qhash<Movable>(); } void qhashCustom() const { qhash<Custom>(); } @@ -332,6 +322,9 @@ private slots: void resizeToZero() const; void resizeToTheSameSize_data(); void resizeToTheSameSize() const; + void resizeForOverwrite() const; + void iterators() const; + void constIterators() const; void reverseIterators() const; void sizeInt() const { size<int>(); } void sizeMovable() const { size<Movable>(); } @@ -369,18 +362,54 @@ private slots: void emplaceConsistentWithStdVectorMovable() { emplaceConsistentWithStdVectorImpl<Movable>(); } void emplaceConsistentWithStdVectorQString() { emplaceConsistentWithStdVectorImpl<QString>(); } void emplaceReturnsIterator(); + void emplaceFront() const; + void emplaceFrontReturnsRef() const; void emplaceBack(); void emplaceBackReturnsRef(); void emplaceWithElementFromTheSameContainer(); void emplaceWithElementFromTheSameContainer_data(); + void replaceInt() const { replace<int>(); } + void replaceCustom() const { replace<Custom>(); } + void replaceMovable() const { replace<Movable>(); } void fromReadOnlyData() const; void reallocateCustomAlignedType_qtbug90359() const; + void reinsertToBeginInt_qtbug91360() const { reinsertToBegin<int>(); } + void reinsertToBeginMovable_qtbug91360() const { reinsertToBegin<Movable>(); } + void reinsertToBeginCustom_qtbug91360() const { reinsertToBegin<Custom>(); } + void reinsertToEndInt_qtbug91360() const { reinsertToEnd<int>(); } + void reinsertToEndMovable_qtbug91360() const { reinsertToEnd<Movable>(); } + void reinsertToEndCustom_qtbug91360() const { reinsertToEnd<Custom>(); } + void reinsertRangeToEndInt_qtbug91360() const { reinsertRangeToEnd<int>(); } + void reinsertRangeToEndMovable_qtbug91360() const { reinsertRangeToEnd<Movable>(); } + void reinsertRangeToEndCustom_qtbug91360() const { reinsertRangeToEnd<Custom>(); } + // QList reference stability tests: + void stability_reserveInt() const { stability_reserve<int>(); } + void stability_reserveMovable() const { stability_reserve<Movable>(); } + void stability_reserveCustom() const { stability_reserve<Custom>(); } + void stability_eraseInt() const { stability_erase<int>(); } + void stability_eraseMovable() const { stability_erase<Movable>(); } + void stability_eraseCustom() const { stability_erase<Custom>(); } + void stability_appendInt() const { stability_append<int>(); } + void stability_appendMovable() const { stability_append<Movable>(); } + void stability_appendCustom() const { stability_append<Custom>(); } + void stability_insertElementInt() const { stability_insertElement<int>(); } + void stability_insertElementMovable() const { stability_insertElement<Movable>(); } + void stability_insertElementCustom() const { stability_insertElement<Custom>(); } + void stability_emplaceInt() const { stability_emplace<int>(); } + void stability_emplaceMovable() const { stability_emplace<Movable>(); } + void stability_emplaceCustom() const { stability_emplace<Custom>(); } + void stability_resizeInt() const { stability_resize<int>(); } + void stability_resizeMovable() const { stability_resize<Movable>(); } + void stability_resizeCustom() const { stability_resize<Custom>(); } private: template<typename T> void copyConstructor() const; template<typename T> void testAssignment() const; template<typename T> void add() const; template<typename T> void append() const; + template<typename T> void assign() const; + void assignUsesPrependBuffer_data() const; + template<typename T> void assignUsesPrependBuffer() const; template<typename T> void assignFromInitializerList() const; template<typename T> void capacity() const; template<typename T> void clear() const; @@ -405,6 +434,56 @@ private: template<typename T> void detachThreadSafety() const; template<typename T> void emplaceImpl() const; template<typename T> void emplaceConsistentWithStdVectorImpl() const; + template<typename T> void replace() const; + template<typename T, typename Reinsert> + void reinsert(Reinsert op) const; + template<typename T> + void reinsertToBegin() const + { + reinsert<T>([](QList<T> &list) { + list.prepend(list.back()); + list.removeLast(); + }); + } + template<typename T> + void reinsertToEnd() const + { + reinsert<T>([](QList<T> &list) { + list.append(list.front()); + list.removeFirst(); + }); + } + template<typename T> + void reinsertRangeToEnd() const + { + reinsert<T>([](QList<T> &list) { + list.append(list.begin(), list.begin() + 1); + list.removeFirst(); + }); + } + template<typename T> + void stability_reserve() const; + template<typename T> + void stability_erase() const; + template<typename T> + void stability_append() const; + template<typename T, typename Insert> + void stability_insert(Insert op) const; + template<typename T> + void stability_resize() const; + + template<typename T> + void stability_insertElement() const + { + stability_insert<T>( + [](QList<T> &list, int pos, const T &value) { list.insert(pos, 1, value); }); + } + template<typename T> + void stability_emplace() const + { + stability_insert<T>( + [](QList<T> &list, int pos, const T &value) { list.emplace(pos, value); }); + } }; @@ -442,6 +521,18 @@ const Custom SimpleValue<Custom>::Values[] = { 110, 105, 101, 114, 111, 98 }; #define T_DOG SimpleValue<T>::at(4) #define T_BLAH SimpleValue<T>::at(5) +// returns a pair of QList<T> and QList<T *> +template<typename It> +decltype(auto) qlistCopyAndReferenceFromRange(It first, It last) +{ + using T = typename std::iterator_traits<It>::value_type; + QList<T> copy(first, last); + QList<T *> reference; + for (; first != last; ++first) + reference.append(std::addressof(*first)); + return std::make_pair(copy, reference); +} + void tst_QList::constructors_empty() const { QList<int> emptyInt; @@ -471,25 +562,22 @@ void tst_QList::constructors_reserveAndInitialize() const { // default-initialise items - QList<int> myInt(5, 42); + const QList<int> myInt(5, 42); QVERIFY(myInt.capacity() == 5); - foreach (int meaningoflife, myInt) { + for (int meaningoflife : myInt) QCOMPARE(meaningoflife, 42); - } - QList<QString> myString(5, QString::fromLatin1("c++")); + const QList<QString> myString(5, QString::fromLatin1("c++")); QVERIFY(myString.capacity() == 5); // make sure all items are initialised ok - foreach (QString meaningoflife, myString) { + for (const QString &meaningoflife : myString) QCOMPARE(meaningoflife, QString::fromLatin1("c++")); - } - QList<Custom> myCustom(5, Custom('n')); + const QList<Custom> myCustom(5, Custom('n')); QVERIFY(myCustom.capacity() == 5); // make sure all items are initialised ok - foreach (Custom meaningoflife, myCustom) { + for (Custom meaningoflife : myCustom) QCOMPARE(meaningoflife.i, 'n'); - } } template<typename T> @@ -640,6 +728,193 @@ void tst_QList::append() const QCOMPARE(v, combined); } + { + const QList<T> otherVec { SimpleValue<T>::at(0), + SimpleValue<T>::at(1), + SimpleValue<T>::at(2), + SimpleValue<T>::at(3) }; + QList<T> myvec; + myvec.append(otherVec.cbegin(), otherVec.cbegin() + 3); + QCOMPARE(myvec.size(), 3); + QCOMPARE(myvec, QList<T>() << SimpleValue<T>::at(0) + << SimpleValue<T>::at(1) + << SimpleValue<T>::at(2)); + } + { + QList<T> emptyVec; + QList<T> otherEmptyVec; + + emptyVec.append(otherEmptyVec); + + QVERIFY(emptyVec.isEmpty()); + QVERIFY(!emptyVec.isDetached()); + QVERIFY(!otherEmptyVec.isDetached()); + } + { + QList<T> myvec { SimpleValue<T>::at(0), SimpleValue<T>::at(1) }; + QList<T> emptyVec; + + myvec.append(emptyVec); + QVERIFY(emptyVec.isEmpty()); + QVERIFY(!emptyVec.isDetached()); + QCOMPARE(myvec, QList<T>({ SimpleValue<T>::at(0), SimpleValue<T>::at(1) })); + } +} + +void tst_QList::assignEmpty() const +{ + // Test that the realloc branch in assign(it, it) doesn't crash. + using T = int; + QList<T> list; + QList<T> ref1 = list; + QVERIFY(list.d.needsDetach()); + list.assign(list.begin(), list.begin()); + +#if !defined Q_OS_QNX // QNX has problems with the empty istream_iterator + auto empty = std::istream_iterator<T>{}; + list.squeeze(); + QCOMPARE_EQ(list.capacity(), 0); + ref1 = list; + QVERIFY(list.d.needsDetach()); + list.assign(empty, empty); +#endif +} + +template <typename T> +void tst_QList::assign() const +{ + TST_QLIST_CHECK_LEAKS(T) + { + QList<T> myvec; + myvec.assign(2, T_FOO); + QVERIFY(myvec.isDetached()); + QCOMPARE(myvec, QList<T>() << T_FOO << T_FOO); + + QList<T> myvecCopy = myvec; + QVERIFY(!myvec.isDetached()); + QVERIFY(!myvecCopy.isDetached()); + QVERIFY(myvec.isSharedWith(myvecCopy)); + QVERIFY(myvecCopy.isSharedWith(myvec)); + + myvec.assign(3, T_BAR); + QCOMPARE(myvec, QList<T>() << T_BAR << T_BAR << T_BAR); + QVERIFY(myvec.isDetached()); + QVERIFY(myvecCopy.isDetached()); + QVERIFY(!myvec.isSharedWith(myvecCopy)); + QVERIFY(!myvecCopy.isSharedWith(myvec)); + } + { + QList<T> myvec; + myvec.assign(4, T_FOO); + QVERIFY(myvec.isDetached()); + QCOMPARE(myvec, QList<T>() << T_FOO << T_FOO << T_FOO << T_FOO); + + QList<T> myvecCopy = myvec; + QVERIFY(!myvec.isDetached()); + QVERIFY(!myvecCopy.isDetached()); + QVERIFY(myvec.isSharedWith(myvecCopy)); + QVERIFY(myvecCopy.isSharedWith(myvec)); + + myvecCopy.assign(myvec.begin(), myvec.begin() + 2); + QVERIFY(myvec.isDetached()); + QVERIFY(myvecCopy.isDetached()); + QVERIFY(!myvec.isSharedWith(myvecCopy)); + QVERIFY(!myvecCopy.isSharedWith(myvec)); + QCOMPARE(myvecCopy, QList<T>() << T_FOO << T_FOO); + } +} + +inline namespace Scenarios { +Q_NAMESPACE +enum ListState { + UnsharedList, + SharedList, +}; +Q_ENUM_NS(ListState) +enum RelationWithPrependBuffer { + FitsIntoFreeSpaceAtBegin, + FitsFreeSpaceAtBeginExactly, + ExceedsFreeSpaceAtBegin, + FitsFreeSpaceAtBeginPlusSizeExactly, + FullCapacity, +}; +Q_ENUM_NS(RelationWithPrependBuffer) +} // namespace Scenarios + +void tst_QList::assignUsesPrependBuffer_data() const +{ + QTest::addColumn<ListState>("listState"); + QTest::addColumn<RelationWithPrependBuffer>("relationWithPrependBuffer"); + + const auto sme = QMetaEnum::fromType<ListState>(); + const auto rme = QMetaEnum::fromType<RelationWithPrependBuffer>(); + + for (int i = 0, s = sme.value(i); s != -1; s = sme.value(++i)) { + for (int j = 0, r = rme.value(j); r != -1; r = rme.value(++j)) { + QTest::addRow("%s-%s", sme.key(i), rme.key(j)) + << ListState(s) << RelationWithPrependBuffer(r); + } + } +} + +template <typename T> +void tst_QList::assignUsesPrependBuffer() const +{ + QFETCH(const ListState, listState); + QFETCH(const RelationWithPrependBuffer, relationWithPrependBuffer); + + const auto capBegin = [](const QList<T> &l) { + return l.begin() - l.d.freeSpaceAtBegin(); + }; + const auto capEnd = [](const QList<T> &l) { + return l.end() + l.d.freeSpaceAtEnd(); + }; + + TST_QLIST_CHECK_LEAKS(T) + { + // Test the prepend optimization. + QList<T> withFreeSpaceAtBegin(16, T_FOO); + // try at most 100 times to create freeSpaceAtBegin(): + for (int i = 0; i < 100 && withFreeSpaceAtBegin.d.freeSpaceAtBegin() < 2; ++i) + withFreeSpaceAtBegin.prepend(T_FOO); + QCOMPARE_GT(withFreeSpaceAtBegin.d.freeSpaceAtBegin(), 1); + + auto c = [&] { + switch (listState) { + case UnsharedList: return std::move(withFreeSpaceAtBegin); + case SharedList: return withFreeSpaceAtBegin; + } + Q_UNREACHABLE_RETURN(withFreeSpaceAtBegin); + }(); + + const auto n = [&] () -> qsizetype { + switch (relationWithPrependBuffer) { + case FitsIntoFreeSpaceAtBegin: + return qsizetype(1); + case FitsFreeSpaceAtBeginExactly: + return c.d.freeSpaceAtBegin(); + case ExceedsFreeSpaceAtBegin: + return c.d.freeSpaceAtBegin() + 1; + case FitsFreeSpaceAtBeginPlusSizeExactly: + return c.d.freeSpaceAtBegin() + c.size(); + case FullCapacity: + return c.capacity(); + }; + Q_UNREACHABLE_RETURN(0); + }(); + + const auto oldCapBegin = capBegin(c); + const auto oldCapEnd = capEnd(c); + + const std::vector v(n, T_BAR); + c.assign(v.begin(), v.end()); + QCOMPARE_EQ(c.d.freeSpaceAtBegin(), 0); // we used the prepend-buffer + if (listState != SharedList) { + // check that we didn't reallocate + QCOMPARE_EQ(capBegin(c), oldCapBegin); + QCOMPARE_EQ(capEnd(c), oldCapEnd); + } + } } void tst_QList::appendRvalue() const @@ -648,9 +923,15 @@ void tst_QList::appendRvalue() const v.append("hello"); QString world = "world"; v.append(std::move(world)); - QVERIFY(world.isEmpty()); QCOMPARE(v.front(), QString("hello")); QCOMPARE(v.back(), QString("world")); + + // check append rvalue to empty list + QList<QString> myvec; + QString test = "test"; + myvec.append(std::move(test)); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.front(), QString("test")); } struct ConstructionCounted @@ -827,6 +1108,7 @@ void tst_QList::appendList() const // Using operators // << QList<ConstructionCounted> v6; + v6.reserve(4); v6 << (QList<ConstructionCounted>() << 1 << 2); v6 << (QList<ConstructionCounted>() << 3 << 4); QCOMPARE(v6, expectedFour); @@ -883,6 +1165,7 @@ void tst_QList::capacity() const // TODO: is this guaranteed? seems a safe assumption, but I suppose preallocation of a // few items isn't an entirely unforseeable possibility. QVERIFY(myvec.capacity() == 0); + QVERIFY(!myvec.isDetached()); // test it gets a size myvec << SimpleValue<T>::at(0) << SimpleValue<T>::at(1) << SimpleValue<T>::at(2); @@ -911,6 +1194,9 @@ void tst_QList::clear() const TST_QLIST_CHECK_LEAKS(T) QList<T> myvec; + myvec.clear(); + QVERIFY(!myvec.isDetached()); + myvec << SimpleValue<T>::at(0) << SimpleValue<T>::at(1) << SimpleValue<T>::at(2); const auto oldCapacity = myvec.capacity(); @@ -924,14 +1210,21 @@ void tst_QList::constData() const { int arr[] = { 42, 43, 44 }; QList<int> myvec; + QCOMPARE(myvec.constData(), nullptr); + QVERIFY(!myvec.isDetached()); + myvec << 42 << 43 << 44; - QVERIFY(memcmp(myvec.constData(), reinterpret_cast<const int *>(&arr), sizeof(int) * 3) == 0); + QCOMPARE(memcmp(myvec.constData(), reinterpret_cast<const int *>(&arr), sizeof(int) * 3), 0); } void tst_QList::contains() const { QList<QString> myvec; + + QVERIFY(!myvec.contains(QLatin1String("test"))); + QVERIFY(!myvec.isDetached()); + myvec << "aaa" << "bbb" << "ccc"; QVERIFY(myvec.contains(QLatin1String("aaa"))); @@ -953,24 +1246,28 @@ void tst_QList::count() const { // zero size QList<T> myvec; - QVERIFY(myvec.count() == 0); + QVERIFY(myvec.size() == 0); + QVERIFY(!myvec.isDetached()); // grow myvec.append(SimpleValue<T>::at(0)); - QVERIFY(myvec.count() == 1); + QVERIFY(myvec.size() == 1); myvec.append(SimpleValue<T>::at(1)); - QVERIFY(myvec.count() == 2); + QVERIFY(myvec.size() == 2); // shrink myvec.remove(0); - QVERIFY(myvec.count() == 1); + QVERIFY(myvec.size() == 1); myvec.remove(0); - QVERIFY(myvec.count() == 0); + QVERIFY(myvec.size() == 0); } // count of items { QList<T> myvec; + QCOMPARE(myvec.count(SimpleValue<T>::at(0)), 0); + QVERIFY(!myvec.isDetached()); + myvec << SimpleValue<T>::at(0) << SimpleValue<T>::at(1) << SimpleValue<T>::at(2); // initial tests @@ -989,7 +1286,6 @@ void tst_QList::count() const void tst_QList::cpp17ctad() const { -#ifdef __cpp_deduction_guides #define QVERIFY_IS_VECTOR_OF(obj, Type) \ QVERIFY2((std::is_same<decltype(obj), QList<Type>>::value), \ QMetaType::fromType<decltype(obj)::value_type>().name()) @@ -1009,14 +1305,13 @@ void tst_QList::cpp17ctad() const CHECK(QString, QStringLiteral("one"), QStringLiteral("two"), QStringLiteral("three")); #undef QVERIFY_IS_VECTOR_OF #undef CHECK -#else - QSKIP("This test requires C++17 Constructor Template Argument Deduction support enabled in the compiler."); -#endif } void tst_QList::data() const { QList<int> myvec; + QCOMPARE(myvec.data(), nullptr); + myvec << 42 << 43 << 44; // make sure it starts off ok @@ -1029,7 +1324,11 @@ void tst_QList::data() const QCOMPARE(*(myvec.data() + 1), 69); int arr[] = { 42, 69, 44 }; - QVERIFY(memcmp(myvec.data(), reinterpret_cast<int *>(&arr), sizeof(int) * 3) == 0); + QCOMPARE(memcmp(myvec.data(), reinterpret_cast<int *>(&arr), sizeof(int) * 3), 0); + + const QList<int> constVec = myvec; + QCOMPARE(memcmp(constVec.data(), reinterpret_cast<const int *>(&arr), sizeof(int) * 3), 0); + QVERIFY(!constVec.isDetached()); // const data() does not detach() } template<typename T> @@ -1041,6 +1340,7 @@ void tst_QList::empty() const // starts empty QVERIFY(myvec.empty()); + QVERIFY(!myvec.isDetached()); // not empty myvec.append(SimpleValue<T>::at(2)); @@ -1225,6 +1525,10 @@ void tst_QList::fill() const QList<T> myvec; + // fill an empty list - it should resize + myvec.fill(SimpleValue<T>::at(1), 2); + QCOMPARE(myvec, QList<T>({ SimpleValue<T>::at(1), SimpleValue<T>::at(1) })); + // resize myvec.resize(5); myvec.fill(SimpleValue<T>::at(1)); @@ -1416,6 +1720,11 @@ void tst_QList::fromStdVector() const void tst_QList::indexOf() const { QList<QString> myvec; + + QCOMPARE(myvec.indexOf("A"), -1); + QCOMPARE(myvec.indexOf("A", 5), -1); + QVERIFY(!myvec.isDetached()); + myvec << "A" << "B" << "C" << "B" << "A"; QVERIFY(myvec.indexOf("B") == 1); @@ -1505,6 +1814,52 @@ void tst_QList::insert() const QCOMPARE(myvec, QList<T>() << tB << tB << tX << tZ << ti << ti << tA << tB << tC << tT); QCOMPARE(myvec2, myvec); + + // Different insert() into empty list overloads + { + QList<T> myvec; + auto it = myvec.insert(0, tA); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.front(), tA); + QCOMPARE(it, myvec.begin()); + } + { + QList<T> myvec; + auto it = myvec.insert(0, 3, tX); + QCOMPARE(myvec.size(), 3); + QCOMPARE(myvec, QList<T>({ tX, tX, tX })); + QCOMPARE(it, myvec.begin()); + } + { + QList<T> myvec; + auto it = myvec.insert(myvec.cbegin(), tA); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.front(), tA); + QCOMPARE(it, myvec.begin()); + } + { + QList<T> myvec; + auto it = myvec.insert(myvec.cbegin(), 3, tX); + QCOMPARE(myvec.size(), 3); + QCOMPARE(myvec, QList<T>({ tX, tX, tX })); + QCOMPARE(it, myvec.begin()); + } + { + QList<QString> myvec; + QString test = "test"; + auto it = myvec.insert(0, std::move(test)); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.front(), u"test"); + QCOMPARE(it, myvec.begin()); + } + { + QList<QString> myvec; + QString test = "test"; + auto it = myvec.insert(myvec.cbegin(), std::move(test)); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.front(), u"test"); + QCOMPARE(it, myvec.begin()); + } } void tst_QList::insertZeroCount_data() @@ -1533,6 +1888,7 @@ void tst_QList::isEmpty() const // starts ok QVERIFY(myvec.isEmpty()); + QVERIFY(!myvec.isDetached()); // not empty now myvec.append(QLatin1String("hello there")); @@ -1638,6 +1994,11 @@ void tst_QList::constLast() const void tst_QList::lastIndexOf() const { QList<QString> myvec; + + QCOMPARE(myvec.lastIndexOf("A"), -1); + QCOMPARE(myvec.lastIndexOf("A", 5), -1); + QVERIFY(!myvec.isDetached()); + myvec << "A" << "B" << "C" << "B" << "A"; QVERIFY(myvec.lastIndexOf("B") == 3); @@ -1661,6 +2022,12 @@ void tst_QList::lastIndexOf() const void tst_QList::mid() const { QList<QString> list; + + QCOMPARE(list.mid(4, 2), QList<QString>()); + QCOMPARE(list.mid(0, 3), QList<QString>()); + QCOMPARE(list.mid(-2, 3), QList<QString>()); + QVERIFY(!list.isDetached()); + list << "foo" << "bar" << "baz" << "bak" << "buck" << "hello" << "kitty"; QCOMPARE(list.mid(3, 3), QList<QString>() << "bak" << "buck" << "hello"); @@ -1706,11 +2073,11 @@ void tst_QList::move() const list << T_FOO << T_BAR << T_BAZ; // move an item - list.move(0, list.count() - 1); + list.move(0, list.size() - 1); QCOMPARE(list, QList<T>() << T_BAR << T_BAZ << T_FOO); // move it back - list.move(list.count() - 1, 0); + list.move(list.size() - 1, 0); QCOMPARE(list, QList<T>() << T_FOO << T_BAR << T_BAZ); // move an item in the middle @@ -1724,11 +2091,19 @@ void tst_QList::prepend() const TST_QLIST_CHECK_LEAKS(T) QList<T> myvec; + T val1 = SimpleValue<T>::at(0); T val2 = SimpleValue<T>::at(1); T val3 = SimpleValue<T>::at(2); T val4 = SimpleValue<T>::at(3); T val5 = SimpleValue<T>::at(4); + + // prepend to default-constructed empty list + myvec.prepend(val1); + QCOMPARE(myvec.size(), 1); + QCOMPARE(myvec.at(0), val1); + myvec.clear(); + myvec << val1 << val2 << val3; // starts ok @@ -1756,6 +2131,21 @@ void tst_QList::prepend() const QCOMPARE(myvec.at(0), val5); } +void tst_QList::prependRvalue() const +{ + QList<QString> myvec; + + QString hello = "hello"; + QString world = "world"; + + myvec.prepend(std::move(world)); + QCOMPARE(myvec.size(), 1); + + myvec.prepend(std::move(hello)); + QCOMPARE(myvec.size(), 2); + QCOMPARE(myvec, QList<QString>({ "hello", "world" })); +} + void tst_QList::removeAllWithAlias() const { QList<QString> strings; @@ -1773,31 +2163,48 @@ void tst_QList::remove() const T val2 = SimpleValue<T>::at(2); T val3 = SimpleValue<T>::at(3); T val4 = SimpleValue<T>::at(4); - myvec << val1 << val2 << val3; - myvec << val1 << val2 << val3; - myvec << val1 << val2 << val3; - // remove middle + T val5 = SimpleValue<T>::at(5); + + // some operations on empty list + QVERIFY(!myvec.removeOne(val1)); + QCOMPARE(myvec.removeAll(val2), 0); + auto count = myvec.removeIf([](const T&) { return true; }); + QCOMPARE(count, 0); + + myvec << val1 << val2 << val3 << val4; + myvec << val1 << val2 << val3 << val4; + myvec << val1 << val2 << val3 << val4; + // remove by index myvec.remove(1); - QCOMPARE(myvec, QList<T>() << val1 << val3 << val1 << val2 << val3 << val1 << val2 << val3); + QCOMPARE(myvec, QList<T>({ val1, val3, val4, val1, val2, val3, val4, val1, val2, val3, val4 })); + myvec.removeAt(6); + QCOMPARE(myvec, QList<T>({ val1, val3, val4, val1, val2, val3, val1, val2, val3, val4 })); // removeOne() - QVERIFY(!myvec.removeOne(val4)); + QVERIFY(!myvec.removeOne(val5)); QVERIFY(myvec.removeOne(val2)); - QCOMPARE(myvec, QList<T>() << val1 << val3 << val1 << val3 << val1 << val2 << val3); + QCOMPARE(myvec, QList<T>({ val1, val3, val4, val1, val3, val1, val2, val3, val4 })); QList<T> myvecCopy = myvec; QVERIFY(myvecCopy.isSharedWith(myvec)); // removeAll() - QCOMPARE(myvec.removeAll(val4), 0); + QCOMPARE(myvec.removeAll(val5), 0); QVERIFY(myvecCopy.isSharedWith(myvec)); QCOMPARE(myvec.removeAll(val1), 3); QVERIFY(!myvecCopy.isSharedWith(myvec)); - QCOMPARE(myvec, QList<T>() << val3 << val3 << val2 << val3); + QCOMPARE(myvec, QList<T>({ val3, val4, val3, val2, val3, val4 })); + QCOMPARE(myvecCopy, QList<T>({ val1, val3, val4, val1, val3, val1, val2, val3, val4 })); myvecCopy = myvec; QVERIFY(myvecCopy.isSharedWith(myvec)); QCOMPARE(myvec.removeAll(val2), 1); QVERIFY(!myvecCopy.isSharedWith(myvec)); - QCOMPARE(myvec, QList<T>() << val3 << val3 << val3); + QCOMPARE(myvec, QList<T>({ val3, val4, val3, val3, val4 })); + QCOMPARE(myvecCopy, QList<T>({ val3, val4, val3, val2, val3, val4 })); + + // removeIf + count = myvec.removeIf([&val4](const T &val) { return val == val4; }); + QCOMPARE(count, 2); + QCOMPARE(myvec, QList<T>({ val3, val3, val3 })); // remove rest myvec.remove(0, 3); @@ -1923,7 +2330,9 @@ void tst_QList::resizePOD_data() const QVERIFY(nonEmptyReserved.capacity() >= 15); QTest::newRow("null") << null << 10; + QTest::newRow("null and 0 size") << null << 0; QTest::newRow("empty") << empty << 10; + QTest::newRow("empty and 0 size") << empty << 0; QTest::newRow("emptyReserved") << emptyReserved << 10; QTest::newRow("nonEmpty") << nonEmpty << 10; QTest::newRow("nonEmptyReserved") << nonEmptyReserved << 10; @@ -1939,6 +2348,9 @@ void tst_QList::resizePOD() const vector.resize(size); QCOMPARE(vector.size(), size); QVERIFY(vector.capacity() >= size); + if (vector.isEmpty()) + QVERIFY(!vector.isDetached()); + for (int i = oldSize; i < size; ++i) QVERIFY(vector[i] == 0); // check initialization @@ -1971,7 +2383,9 @@ void tst_QList::resizeComplexMovable_data() const QVERIFY(nonEmptyReserved.capacity() >= 15); QTest::newRow("null") << null << 10; + QTest::newRow("null and 0 size") << null << 0; QTest::newRow("empty") << empty << 10; + QTest::newRow("empty and 0 size") << empty << 0; QTest::newRow("emptyReserved") << emptyReserved << 10; QTest::newRow("nonEmpty") << nonEmpty << 10; QTest::newRow("nonEmptyReserved") << nonEmptyReserved << 10; @@ -1989,6 +2403,8 @@ void tst_QList::resizeComplexMovable() const vector.resize(size); QCOMPARE(vector.size(), size); QVERIFY(vector.capacity() >= size); + if (vector.isEmpty()) + QVERIFY(!vector.isDetached()); for (int i = oldSize; i < size; ++i) QVERIFY(vector[i] == 'j'); // check initialization @@ -2023,7 +2439,9 @@ void tst_QList::resizeComplex_data() const QVERIFY(nonEmptyReserved.capacity() >= 15); QTest::newRow("null") << null << 10; + QTest::newRow("null and 0 size") << null << 0; QTest::newRow("empty") << empty << 10; + QTest::newRow("empty and 0 size") << empty << 0; QTest::newRow("emptyReserved") << emptyReserved << 10; QTest::newRow("nonEmpty") << nonEmpty << 10; QTest::newRow("nonEmptyReserved") << nonEmptyReserved << 10; @@ -2040,6 +2458,8 @@ void tst_QList::resizeComplex() const vector.resize(size); QCOMPARE(vector.size(), size); QVERIFY(vector.capacity() >= size); + if (vector.isEmpty()) + QVERIFY(!vector.isDetached()); for (int i = oldSize; i < size; ++i) QVERIFY(vector[i].i == 'j'); // check default initialization @@ -2112,6 +2532,335 @@ void tst_QList::resizeToTheSameSize() const QCOMPARE(y.size(), x.size()); } +void tst_QList::resizeForOverwrite() const +{ + constexpr int BUILD_COUNT = 42; + { + // Smoke test + QList<int> l(BUILD_COUNT, Qt::Uninitialized); + l.resizeForOverwrite(l.size() + BUILD_COUNT); + } + + { + const int beforeCounter = Movable::counter.loadRelaxed(); + QList<Movable> l(BUILD_COUNT, Qt::Uninitialized); + const int after1Counter = Movable::counter.loadRelaxed(); + QCOMPARE(after1Counter, beforeCounter + BUILD_COUNT); + + l.resizeForOverwrite(l.size() + BUILD_COUNT); + const int after2Counter = Movable::counter.loadRelaxed(); + QCOMPARE(after2Counter, after1Counter + BUILD_COUNT); + } + + struct QtInitializationSupport { + bool wasInitialized; + QtInitializationSupport() : wasInitialized(true) {} + explicit QtInitializationSupport(Qt::Initialization) : wasInitialized(false) {} + }; + + { + QList<QtInitializationSupport> l(BUILD_COUNT); + for (const auto &elem : l) + QVERIFY(elem.wasInitialized); + l.resize(l.size() + BUILD_COUNT); + for (const auto &elem : l) + QVERIFY(elem.wasInitialized); + } + + { + QList<QtInitializationSupport> l(BUILD_COUNT, Qt::Uninitialized); + for (const auto &elem : l) + QVERIFY(!elem.wasInitialized); + l.resizeForOverwrite(l.size() + BUILD_COUNT); + for (const auto &elem : l) + QVERIFY(!elem.wasInitialized); + } +} + +void tst_QList::iterators() const +{ + QList<int> v; + + QCOMPARE(v.begin(), v.end()); + QCOMPARE(v.rbegin(), v.rend()); + + qsizetype idx = 0; + for (; idx < 10; ++idx) + v.push_back(idx); + + // stl-style iterators + idx = 0; + auto it = v.begin(); + QCOMPARE(*it, idx); + // idx == 0 + + std::advance(it, 7); + idx += 7; + QCOMPARE(*it, idx); + // idx == 7 + + it++; + idx++; + QCOMPARE(*it, idx); + // idx == 8 + + ++it; + ++idx; + QCOMPARE(*it, idx); + // idx == 9 + + std::advance(it, -3); + idx -= 3; + QCOMPARE(*it, idx); + // idx == 6 + + it--; + idx--; + QCOMPARE(*it, idx); + // idx == 5 + + --it; + --idx; + QCOMPARE(*it, idx); + // idx == 4 + + it = it + 1; + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 5 + + it = it + ptrdiff_t(1); + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 6 + + it = it + qsizetype(1); + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 7 + + it = it - qsizetype(1); + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 6 + + it = it - ptrdiff_t(1); + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 5 + + it = it - 1; + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 4 + + it -= 1; + idx -= 1; + QCOMPARE(*it, idx); + // idx == 3 + + it -= qsizetype(1); + idx -= 1; + QCOMPARE(*it, idx); + // idx == 2 + + it -= ptrdiff_t(1); + idx -= 1; + QCOMPARE(*it, idx); + // idx == 1 + + it += ptrdiff_t(1); + idx += 1; + QCOMPARE(*it, idx); + // idx == 2 + + it += qsizetype(1); + idx += 1; + QCOMPARE(*it, idx); + // idx == 3 + + it += 1; + idx += 1; + QCOMPARE(*it, idx); + // idx == 4 + + *it = idx + 1; + QCOMPARE(*it, idx + 1); + *it = idx; + + // stl-style reverse iterators + idx = v.size() - 1; + auto rit = v.rbegin(); + QCOMPARE(*rit, idx); + + *rit = idx + 1; + QCOMPARE(*rit, idx + 1); + *rit = idx; + + std::advance(rit, 5); + idx -= 5; + QCOMPARE(*rit, idx); + + ++rit; + --idx; + QCOMPARE(*rit, idx); + + rit++; + idx--; + QCOMPARE(*rit, idx); + + std::advance(rit, -4); + idx += 4; + QCOMPARE(*rit, idx); + + --rit; + ++idx; + QCOMPARE(*rit, idx); + + rit--; + idx++; + QCOMPARE(*rit, idx); +} + +void tst_QList::constIterators() const +{ + const QList<int> constEmptyList; + QCOMPARE(constEmptyList.cbegin(), constEmptyList.cend()); + QCOMPARE(constEmptyList.begin(), constEmptyList.cbegin()); + QCOMPARE(constEmptyList.end(), constEmptyList.cend()); + QCOMPARE(constEmptyList.constBegin(), constEmptyList.constEnd()); + QCOMPARE(constEmptyList.constBegin(), constEmptyList.cbegin()); + QCOMPARE(constEmptyList.constEnd(), constEmptyList.cend()); + QVERIFY(!constEmptyList.isDetached()); + + const QList<int> v { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + + // stl-style iterators + qsizetype idx = 0; + auto it = v.cbegin(); + QCOMPARE(*it, idx); + // idx == 0 + + std::advance(it, 7); + idx += 7; + QCOMPARE(*it, idx); + // idx == 7 + + it++; + idx++; + QCOMPARE(*it, idx); + // idx == 8 + + ++it; + ++idx; + QCOMPARE(*it, idx); + // idx == 9 + + std::advance(it, -3); + idx -= 3; + QCOMPARE(*it, idx); + // idx == 6 + + it--; + idx--; + QCOMPARE(*it, idx); + // idx == 5 + + --it; + --idx; + QCOMPARE(*it, idx); + // idx == 4 + + it = it + 1; + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 5 + + it = it + ptrdiff_t(1); + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 6 + + it = it + qsizetype(1); + idx = idx + 1; + QCOMPARE(*it, idx); + // idx == 7 + + it = it - qsizetype(1); + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 6 + + it = it - ptrdiff_t(1); + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 5 + + it = it - 1; + idx = idx - 1; + QCOMPARE(*it, idx); + // idx == 4 + + it -= 1; + idx -= 1; + QCOMPARE(*it, idx); + // idx == 3 + + it -= qsizetype(1); + idx -= 1; + QCOMPARE(*it, idx); + // idx == 2 + + it -= ptrdiff_t(1); + idx -= 1; + QCOMPARE(*it, idx); + // idx == 1 + + it += ptrdiff_t(1); + idx += 1; + QCOMPARE(*it, idx); + // idx == 2 + + it += qsizetype(1); + idx += 1; + QCOMPARE(*it, idx); + // idx == 3 + + it += 1; + idx += 1; + QCOMPARE(*it, idx); + // idx == 4 + + // stl-style reverse iterators + idx = v.size() - 1; + auto rit = v.crbegin(); + QCOMPARE(*rit, idx); + + std::advance(rit, 5); + idx -= 5; + QCOMPARE(*rit, idx); + + ++rit; + --idx; + QCOMPARE(*rit, idx); + + rit++; + idx--; + QCOMPARE(*rit, idx); + + std::advance(rit, -4); + idx += 4; + QCOMPARE(*rit, idx); + + --rit; + ++idx; + QCOMPARE(*rit, idx); + + rit--; + idx++; + QCOMPARE(*rit, idx); +} + void tst_QList::reverseIterators() const { QList<int> v; @@ -2132,21 +2881,29 @@ void tst_QList::size() const { TST_QLIST_CHECK_LEAKS(T) + // also verify that length() is an alias to size() + // zero size QList<T> myvec; QVERIFY(myvec.size() == 0); + QCOMPARE(myvec.size(), myvec.size()); + QVERIFY(!myvec.isDetached()); // grow myvec.append(SimpleValue<T>::at(0)); QVERIFY(myvec.size() == 1); + QCOMPARE(myvec.size(), myvec.size()); myvec.append(SimpleValue<T>::at(1)); QVERIFY(myvec.size() == 2); + QCOMPARE(myvec.size(), myvec.size()); // shrink myvec.remove(0); QVERIFY(myvec.size() == 1); + QCOMPARE(myvec.size(), myvec.size()); myvec.remove(0); QVERIFY(myvec.size() == 0); + QCOMPARE(myvec.size(), myvec.size()); } // ::squeeze() is tested in ::capacity(). @@ -2219,6 +2976,11 @@ void tst_QList::toStdVector() const void tst_QList::value() const { QList<QString> myvec; + + QCOMPARE(myvec.value(1), QString()); + QCOMPARE(myvec.value(-1, QLatin1String("default")), QLatin1String("default")); + QVERIFY(!myvec.isDetached()); + myvec << "A" << "B" << "C"; // valid calls @@ -2335,6 +3097,14 @@ void tst_QList::reserveZero() vec.append(42); QCOMPARE(vec.size(), 1); QVERIFY(vec.capacity() >= 1); + + QList<int> vec2; + vec2.reserve(0); // should not crash either + vec2.reserve(-1); + vec2.squeeze(); + QCOMPARE(vec2.size(), 0); + QCOMPARE(vec2.capacity(), 0); + QVERIFY(!vec2.isDetached()); } template<typename T> @@ -2622,9 +3392,34 @@ void tst_QList::emplaceReturnsIterator() QCOMPARE(vec[0].i, 'p'); } +void tst_QList::emplaceFront() const +{ + QAtomicScopedValueRollback rollback(Movable::counter, 0); + + QList<Movable> vec; + vec.emplaceFront('b'); + QCOMPARE(Movable::counter, 1); + + vec.emplaceFront('a'); + QCOMPARE(Movable::counter, 2); + + QCOMPARE(vec, QList<Movable>({ 'a', 'b' })); +} + +void tst_QList::emplaceFrontReturnsRef() const +{ + QList<Movable> vec; + + QCOMPARE(vec.emplaceFront('c').i, 'c'); + + vec.emplaceFront('b').i = 'a'; + + QCOMPARE(vec.front().i, 'a'); +} + void tst_QList::emplaceBack() { - QScopedValueRollback<QAtomicInt> rollback(Movable::counter, 0); + QAtomicScopedValueRollback rollback(Movable::counter, 0); QList<Movable> vec; @@ -2687,7 +3482,42 @@ void tst_QList::emplaceImpl() const vec.emplace(2, 'k'); + QCOMPARE(vec.size(), 5); // emplace adds new element QCOMPARE(vec[2], T('k')); + + vec.emplace(vec.end(), T('f')); + + QCOMPARE(vec.size(), 6); + QCOMPARE(vec.back(), T('f')); + + // emplace() into empty container + { + QList<T> vec; + vec.emplace(vec.begin(), 'a'); + QCOMPARE(vec.size(), 1); + QCOMPARE(vec.front(), T('a')); + } + { + QList<T> vec; + vec.emplace(0, 'a'); + QCOMPARE(vec.size(), 1); + QCOMPARE(vec.front(), T('a')); + } +} + +template <typename T> +void tst_QList::replace() const +{ + TST_QLIST_CHECK_LEAKS(T) + + QList<T> vec { 'a', 'b', 'c', 'd' }; + T e = 'e'; + vec.replace(0, e); + QCOMPARE(vec[0], T('e')); + + T f = 'f'; + vec.replace(2, std::move(f)); + QCOMPARE(vec[2], T('f')); } template <class T> @@ -2797,7 +3627,7 @@ void tst_QList::fromReadOnlyData() const QCOMPARE(v.size(), qsizetype(11)); // v.capacity() is unspecified, for now - QCOMPARE((void*)(const char*)(v.constBegin() + v.size()), (void*)(const char*)v.constEnd()); + QCOMPARE((void*)(v.constBegin() + v.size()).operator->(), (void*)v.constEnd().operator->()); for (int i = 0; i < 10; ++i) QCOMPARE(v[i], char('A' + i)); @@ -2844,5 +3674,296 @@ void tst_QList::reallocateCustomAlignedType_qtbug90359() const QCOMPARE(actual, expected); } +template<typename T, typename Reinsert> +void tst_QList::reinsert(Reinsert op) const +{ + TST_QLIST_CHECK_LEAKS(T) + + QList<T> list(1); + // this constant is big enough for the QList to stop reallocating, after + // all, size is always less than 3 + const int maxIters = 128; + for (int i = 0; i < maxIters; ++i) { + op(list); + } + + // if QList continues to grow, it's an error + qsizetype capacity = list.capacity(); + for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) { + op(list); + QCOMPARE(capacity, list.capacity()); + } +} + +template<typename T> +void tst_QList::stability_reserve() const +{ + TST_QLIST_CHECK_LEAKS(T) + + // NOTE: this test verifies that QList::constData() stays unchanged when + // inserting as much as requested by the reserve. This is specifically + // designed this way as in cases when QTypeInfo<T>::isRelocatable returns + // true, reallocation might use fast ::realloc() path which may in theory + // (and, actually, in practice) just expand the current memory area and thus + // keep QList::constData() unchanged, which means checks like + // QVERIFY(oldConstData != vec.constData()) are flaky. When + // QTypeInfo<T>::isRelocatable returns false, constData() will always change + // if a reallocation happens and this will fail the test. This should be + // sufficient on its own to test the stability requirements. + + { + QList<T> vec; + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList<T>(64)); + QCOMPARE(ptr, vec.constData()); + } + + { + QList<T> vec; + vec.prepend(SimpleValue<T>::at(0)); + vec.removeFirst(); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList<T>(64)); + QCOMPARE(ptr, vec.constData()); + } + + { + QList<T> vec; + const T *ptr = vec.constData(); + vec.reserve(vec.capacity()); + QCOMPARE(ptr, vec.constData()); + vec.append(QList<T>(vec.capacity())); + QCOMPARE(ptr, vec.constData()); + } + + { + QList<T> vec; + vec.prepend(SimpleValue<T>::at(0)); + vec.removeFirst(); + vec.reserve(vec.capacity()); + const T *ptr = vec.constData(); + vec.append(QList<T>(vec.capacity())); + QCOMPARE(ptr, vec.constData()); + } + + { + QList<T> vec; + vec.append(SimpleValue<T>::at(0)); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList<T>(64 - vec.size())); // 1 element is already in the container + QCOMPARE(ptr, vec.constData()); + QCOMPARE(vec.size(), 64); + QCOMPARE(vec.capacity(), 64); + const qsizetype oldCapacity = vec.capacity(); + vec.append(SimpleValue<T>::at(1)); // will reallocate as this exceeds 64 + QVERIFY(oldCapacity < vec.capacity()); + } + + { + QList<T> vec; + vec.prepend(SimpleValue<T>::at(0)); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList<T>(64 - vec.size())); // 1 element is already in the container + QCOMPARE(ptr, vec.constData()); + QCOMPARE(vec.size(), 64); + QCOMPARE(vec.capacity(), 64); + const qsizetype oldCapacity = vec.capacity(); + vec.append(SimpleValue<T>::at(1)); // will reallocate as this exceeds 64 + QVERIFY(oldCapacity < vec.capacity()); + } +} + +template<typename T> +void tst_QList::stability_erase() const +{ + TST_QLIST_CHECK_LEAKS(T) + + // invalidated: [pos, end()) + for (int pos = 1; pos < 10; ++pos) { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + const auto ptr = v.constData(); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + + v.remove(pos, 1); + QVERIFY(ptr == v.constData()); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + + // 0 is a special case, because all values get invalidated + { + QList<T> v(10); + const auto ptr = v.constData(); + v.remove(0, 2); + QVERIFY(ptr != v.constData()); // can do fast removal from begin() + } + + // when erasing everything, leave the data pointer in place (not strictly + // required, but this makes more sense in general) + { + QList<T> v(10); + const auto ptr = v.constData(); + v.remove(0, v.size()); + QVERIFY(ptr == v.constData()); + } +} + +template<typename T> +void tst_QList::stability_append() const +{ + TST_QLIST_CHECK_LEAKS(T) + + { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + QList<T> src(1, SimpleValue<T>::at(0)); + v.append(src.begin(), src.end()); + QCOMPARE_LE(v.size(), v.capacity()); + + for (int i = 0; i < v.capacity() - v.size(); ++i) { + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + v.append(SimpleValue<T>::at(i)); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + } + + { + QList<T> v; + v.reserve(10); + const qsizetype capacity = v.capacity(); + const T *ptr = v.constData(); + v.prepend(SimpleValue<T>::at(0)); + // here we abuse the internal details of QList. since there's enough + // free space, QList should've only rearranged the data in memory, + // without reallocating. + QCOMPARE(capacity, v.capacity()); // otherwise cannot rely on ptr + const qsizetype freeSpaceAtBegin = v.constData() - ptr; + const qsizetype freeSpaceAtEnd = v.capacity() - v.size() - freeSpaceAtBegin; + QVERIFY(freeSpaceAtEnd > 0); // otherwise this test is useless + QVERIFY(v.size() + freeSpaceAtBegin + freeSpaceAtEnd == v.capacity()); + + for (int i = 0; i < freeSpaceAtEnd; ++i) { + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + QList<T> src(1, SimpleValue<T>::at(i)); + v.append(src.begin(), src.end()); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + } +} + +template<typename T, typename Insert> +void tst_QList::stability_insert(Insert op) const +{ + TST_QLIST_CHECK_LEAKS(T) + + // invalidated: [pos, end()) + for (int pos = 1; pos <= 10; ++pos) { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + v.append(SimpleValue<T>::at(0)); // causes growth + v.removeLast(); + QCOMPARE(v.size(), 10); + QVERIFY(v.size() < v.capacity()); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + op(v, pos, SimpleValue<T>::at(0)); + for (int i = 0; i < pos; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + for (int pos = 1; pos <= 10; ++pos) { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + v.prepend(SimpleValue<T>::at(0)); // causes growth and free space at begin > 0 + v.removeFirst(); + QCOMPARE(v.size(), 10); + QVERIFY(v.size() < v.capacity()); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + op(v, pos, SimpleValue<T>::at(0)); + for (int i = 0; i < pos; ++i) + QCOMPARE(*reference[i], copy[i]); + } +} + +template<typename T> +void tst_QList::stability_resize() const +{ + TST_QLIST_CHECK_LEAKS(T) + + { + QList<T> v(10); + v.reserve(15); + QVERIFY(v.size() < v.capacity()); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(15); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + + { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(10); + for (int i = 0; i < 10; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + { + QList<T> v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(5); + for (int i = 0; i < 5; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + // special case due to prepend: + { + QList<T> v; + v.reserve(20); + const qsizetype capacity = v.capacity(); + const T *ptr = v.constData(); + v.prepend(SimpleValue<T>::at(0)); // now there's free space at begin + v.resize(10); + QVERIFY(v.size() < v.capacity()); + // here we abuse the internal details of QList. since there's enough + // free space, QList should've only rearranged the data in memory, + // without reallocating. + QCOMPARE(capacity, v.capacity()); // otherwise cannot rely on ptr + const qsizetype freeSpaceAtBegin = v.constData() - ptr; + const qsizetype freeSpaceAtEnd = v.capacity() - v.size() - freeSpaceAtBegin; + QVERIFY(freeSpaceAtEnd > 0); // otherwise this test is useless + QVERIFY(v.size() + freeSpaceAtBegin + freeSpaceAtEnd == v.capacity()); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue<T>::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(v.size() + freeSpaceAtEnd); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } +} + QTEST_MAIN(tst_QList) #include "tst_qlist.moc" |