diff options
author | Andrei Golubev <andrei.golubev@qt.io> | 2020-08-12 11:37:06 +0200 |
---|---|---|
committer | Andrei Golubev <andrei.golubev@qt.io> | 2020-08-27 18:58:20 +0200 |
commit | 4a56a5f6cf76c7f47d15f1d3dbab3852357b22a3 (patch) | |
tree | dfabf36e014ee40cec6c03ed9de989232ae0697e | |
parent | f9bb3aa5ce15040cf84fa28ae42030a322dce5d1 (diff) |
Support GrowsBackwards prepend in QList
Restored previously deleted logic of setting GrowsBackwards flag for
prepend-like cases. This should be sufficient to fully enable prepend
optimization
Fixed QList::emplace to not use implementation detail logic. Updated
tests to cover changed behavior and its correctness
Task-number: QTBUG-84320
Change-Id: I4aadab0647fe436140b7bb5cf71309f6887e36ab
Reviewed-by: Sona Kurazyan <sona.kurazyan@qt.io>
-rw-r--r-- | src/corelib/tools/qlist.h | 22 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qlist/tst_qlist.cpp | 31 |
2 files changed, 33 insertions, 20 deletions
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index 300baeba8c..4298434a94 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -616,6 +616,8 @@ QList<T>::insert(qsizetype i, qsizetype n, parameter_type t) const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + i, n); if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) { typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward; + if (size_t(i) <= newSize / 4) + flags |= Data::GrowsBackwards; DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize, flags)); @@ -647,25 +649,21 @@ QList<T>::emplace(qsizetype i, Args&&... args) const size_t newSize = size() + 1; if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) { typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward; + if (size_t(i) <= newSize / 4) + flags |= Data::GrowsBackwards; DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize, flags)); const_iterator where = constBegin() + i; + // Create an element here to handle cases when a user moves the element + // from a container to the same container. This is a critical step for + // COW types (e.g. Qt types) since copyAppend() done before emplace() + // would shallow-copy the passed element and ruin the move + T tmp(std::forward<Args>(args)...); - // First, create an element to handle cases, when a user moves - // the element from a container to the same container - detached->createInPlace(detached.begin() + i, std::forward<Args>(args)...); - - // Then, put the first part of the elements to the new location detached->copyAppend(constBegin(), where); - - // After that, increase the actual size, because we created - // one extra element - ++detached.size; - - // Finally, put the rest of the elements to the new location + detached->emplace(detached.end(), std::move(tmp)); detached->copyAppend(where, constEnd()); - d.swap(detached); } else { d->emplace(d.begin() + i, std::forward<Args>(args)...); diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index f37633b64c..8a7100d14c 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -332,6 +332,7 @@ private slots: void emplaceConsistentWithStdVectorInt(); void emplaceConsistentWithStdVectorCustom(); void emplaceConsistentWithStdVectorMovable(); + void emplaceConsistentWithStdVectorQString(); void emplaceReturnsIterator(); void emplaceBack(); void emplaceBackReturnsRef(); @@ -874,7 +875,7 @@ void tst_QList::appendList() const v6 << (QList<ConstructionCounted>() << 3 << 4); QCOMPARE(v6, expectedFour); QCOMPARE(v6.at(0).copies, 2); - QCOMPARE(v6.at(0).moves, 1); + QCOMPARE(v6.at(0).moves, 2); // += QList<ConstructionCounted> v7; @@ -2916,6 +2917,11 @@ void tst_QList::emplaceConsistentWithStdVectorMovable() emplaceConsistentWithStdVectorImpl<Movable>(); } +void tst_QList::emplaceConsistentWithStdVectorQString() +{ + emplaceConsistentWithStdVectorImpl<QString>(); +} + void tst_QList::emplaceReturnsIterator() { QList<Movable> vec; @@ -3008,20 +3014,29 @@ static void squeezeVec(QList<T> &qVec, std::vector<T> &stdVec) template<typename T> void tst_QList::emplaceConsistentWithStdVectorImpl() const { - QList<T> qVec {'a', 'b', 'c', 'd', 'e'}; - std::vector<T> stdVec {'a', 'b', 'c', 'd', 'e'}; + // fast-patch to make QString work with the old logic + const auto convert = [] (char i) { + if constexpr (std::is_same_v<QString, T>) { + return QChar(i); + } else { + return i; + } + }; + + QList<T> qVec {convert('a'), convert('b'), convert('c'), convert('d'), convert('e')}; + std::vector<T> stdVec {convert('a'), convert('b'), convert('c'), convert('d'), convert('e')}; vecEq(qVec, stdVec); - qVec.emplaceBack('f'); - stdVec.emplace_back('f'); + qVec.emplaceBack(convert('f')); + stdVec.emplace_back(convert('f')); vecEq(qVec, stdVec); - qVec.emplace(3, 'g'); - stdVec.emplace(stdVec.begin() + 3, 'g'); + qVec.emplace(3, convert('g')); + stdVec.emplace(stdVec.begin() + 3, convert('g')); vecEq(qVec, stdVec); T t; - // while QList is safe with regards to emplacing elements moved form itself, it's UB + // while QList is safe with regards to emplacing elements moved from itself, it's UB // for std::vector, so do the moving in two steps there. qVec.emplaceBack(std::move(qVec[0])); stdVec.emplace_back(std::move(t = std::move(stdVec[0]))); |