QList: re-use the prepend buffer, if any, on assign()

Task-number: QTBUG-106196
Change-Id: I62d8610529cab528ae1b114d29707133b4fc28dc
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>

2 files changed, 138 insertions, 14 deletions

diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index 3839baefcf..466cdecfc7 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -8,6 +8,7 @@
 #include <QtCore/qcontainertools_impl.h>
 
 #include <QtCore/q20functional.h>
+#include <QtCore/q20memory.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -317,9 +318,7 @@ public:
 
         if constexpr (IsFwdIt) {
             const qsizetype n = std::distance(first, last);
-            // Use of freeSpaceAtBegin() isn't, yet, implemented.
-            const auto usableCapacity = constAllocatedCapacity() - freeSpaceAtBegin();
-            if (needsDetach() || n > usableCapacity) {
+            if (needsDetach() || n > constAllocatedCapacity()) {
                 QArrayDataPointer allocated(Data::allocate(detachCapacity(n)));
                 swap(allocated);
             }
@@ -329,8 +328,48 @@ public:
             // We don't want to copy data that we know we'll overwrite
         }
 
-        auto dst = begin();
+        auto offset = freeSpaceAtBegin();
+        const auto capacityBegin = begin() - offset;
+        const auto prependBufferEnd = begin();
+
+        if constexpr (!std::is_nothrow_constructible_v<T, decltype(proj(*first))>) {
+            // If construction can throw, and we have freeSpaceAtBegin(),
+            // it's easiest to just clear the container and start fresh.
+            // The alternative would be to keep track of two active, disjoint ranges.
+            if (offset) {
+                (*this)->truncate(0);
+                setBegin(capacityBegin);
+                offset = 0;
+            }
+        }
+
+        auto dst = capacityBegin;
         const auto dend = end();
+        if (offset) { // avoids dead stores
+            setBegin(capacityBegin); // undo prepend optimization
+
+            // By construction, the following loop is nothrow!
+            // (otherwise, we can't reach here)
+            // Assumes InputIterator operations don't throw.
+            // (but we can't statically assert that, as these operations
+            //  have preconditons, so typically aren't noexcept)
+            while (true) {
+                if (dst == prependBufferEnd) {  // ran out of prepend buffer space
+                    size += offset;
+                    // we now have a contiguous buffer, continue with the main loop:
+                    break;
+                }
+                if (first == last) {            // ran out of elements to assign
+                    std::destroy(prependBufferEnd, dend);
+                    size = dst - begin();
+                    return;
+                }
+                q20::construct_at(dst, proj(*first)); // construct element in prepend buffer
+                ++dst;
+                ++first;
+            }
+        }
+
         while (true) {
             if (first == last) {    // ran out of elements to assign
                 std::destroy(dst, dend);
diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp
index 050bb80ab1..f52d4650d2 100644
--- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp
+++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp
@@ -234,6 +234,12 @@ private slots:
     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>(); }
@@ -400,6 +406,8 @@ private:
     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;
@@ -796,21 +804,98 @@ void tst_QList::assign() const
         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(); ++i)
+        for (int i = 0; i < 100 && withFreeSpaceAtBegin.d.freeSpaceAtBegin() < 2; ++i)
              withFreeSpaceAtBegin.prepend(T_FOO);
-        QCOMPARE_GT(withFreeSpaceAtBegin.d.freeSpaceAtBegin(), 0);
-        const auto oldData = withFreeSpaceAtBegin.constData();
-        std::vector<T> v(withFreeSpaceAtBegin.capacity(), T_BAR);
-        withFreeSpaceAtBegin.assign(v.begin(), v.end());
-        QCOMPARE_EQ(withFreeSpaceAtBegin.d.freeSpaceAtBegin(), 0);
-        // TODO: Check for equality after the prepend optimization
-        // the following test checks that we didn't reallocate, but re-used the prepend buffer
-        QEXPECT_FAIL("","Use of freeSpaceAtBegin() isn't, yet, implemented", Continue);
-        QVERIFY(QtPrivate::q_points_into_range(oldData, withFreeSpaceAtBegin));
+        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);
+        }
     }
 }