Support GrowsBackwards flag in QArrayDataPointer

Introduced allocation function in QArrayDataPointer with
interface similar to QArrayData::allocate that supports growing
strategies. This func is used instead of the original in cases
when prepend-aware storage is needed. Tried to follow Qt5 QList
policy in terms of space reservation

Updated QPodArrayOps::reallocate to be aware of growing
shenanigans. It doesn't look like a perfect solution but it is
rather close and similar to what Qt6 QList is doing when not
growing (e.g. reserve/squeeze)

Added initial QCommonArrayOps with helper function that tells
when reallocation is preferable over just using the insert-like
operation. This comes up later on when GrowsBackwards policy is
properly supported in operations

Essentially, 2/3 main data management blocks for prepend optimization
are introduced here. The last one being a generalized data move that
is done instead of reallocation when existing free space is not enough

Task-number: QTBUG-84320
Change-Id: I9a2bac62ad600613a6d7c5348325e0e54aadb73d
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

2 files changed, 158 insertions, 21 deletions

diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h
index 13c859edd9..1e9812d08e 100644
--- a/tests/auto/corelib/tools/qarraydata/simplevector.h
+++ b/tests/auto/corelib/tools/qarraydata/simplevector.h
@@ -1,6 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the test suite of the Qt Toolkit.
@@ -40,6 +40,7 @@ struct SimpleVector
 {
 private:
     typedef QTypedArrayData<T> Data;
+    typedef QArrayDataPointer<T> DataPointer;
 
 public:
     typedef T value_type;
@@ -81,6 +82,11 @@ public:
     {
     }
 
+    SimpleVector(const QArrayDataPointer<T> &other)
+        : d(other)
+    {
+    }
+
     bool empty() const { return d.size == 0; }
     bool isNull() const { return d.isNull(); }
     bool isEmpty() const { return this->empty(); }
@@ -195,11 +201,15 @@ public:
             return;
 
         T *const begin = d->begin();
+        const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin(), last - first);
+        const auto newSize = size() + (last - first);
         if (d->needsDetach()
-                || capacity() - size() < size_t(last - first)) {
-            SimpleVector detached(Data::allocate(
-                        d->detachCapacity(size() + (last - first)),
-                        d->detachFlags() | Data::GrowsForward));
+                || capacity() - size() < size_t(last - first)
+                || shouldGrow) {
+            // QTBUG-84320: change to GrowsBackwards once supported in operations
+            auto flags = d->detachFlags() | Data::GrowsForward;
+            SimpleVector detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                            flags));
 
             detached.d->copyAppend(first, last);
             detached.d->copyAppend(begin, begin + d->size);
@@ -216,11 +226,13 @@ public:
         if (first == last)
             return;
 
+        const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), last - first);
+        const auto newSize = size() + (last - first);
         if (d->needsDetach()
-                || capacity() - size() < size_t(last - first)) {
-            SimpleVector detached(Data::allocate(
-                        d->detachCapacity(size() + (last - first)),
-                        d->detachFlags() | Data::GrowsForward));
+                || capacity() - size() < size_t(last - first)
+                || shouldGrow) {
+            SimpleVector detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                            d->detachFlags() | Data::GrowsForward));
 
             if (d->size) {
                 const T *const begin = constBegin();
@@ -256,11 +268,13 @@ public:
         const iterator begin = d->begin();
         const iterator where = begin + position;
         const iterator end = begin + d->size;
+        const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + position, last - first);
+        const auto newSize = size() + (last - first);
         if (d->needsDetach()
-                || capacity() - size() < size_t(last - first)) {
-            SimpleVector detached(Data::allocate(
-                        d->detachCapacity(size() + (last - first)),
-                        d->detachFlags() | Data::GrowsForward));
+                || capacity() - size() < size_t(last - first)
+                || shouldGrow) {
+            SimpleVector detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                            d->detachFlags() | Data::GrowsForward));
 
             if (position)
                 detached.d->copyAppend(begin, where);
@@ -329,7 +343,7 @@ public:
 
     static SimpleVector fromRawData(const T *data, size_t size)
     {
-        return SimpleVector({ nullptr, const_cast<T *>(data), size });
+        return SimpleVector(QArrayDataPointer<T>::fromRawData(data, size));
     }
 
 private:
diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
index 0172927042..c27147dfdb 100644
--- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
+++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
@@ -38,6 +38,7 @@
 #include <algorithm>
 #include <vector>
 #include <stdexcept>
+#include <functional>
 
 // A wrapper for a test function. Calls a function, if it fails, reports failure
 #define RUN_TEST_FUNC(test, ...) \
@@ -78,6 +79,10 @@ private slots:
     void grow();
     void freeSpace_data();
     void freeSpace();
+    void dataPointerAllocate_data() { arrayOps_data(); }
+    void dataPointerAllocate();
+    void dataPointerAllocateAlignedWithReallocate_data();
+    void dataPointerAllocateAlignedWithReallocate();
 #ifndef QT_NO_EXCEPTIONS
     void exceptionSafetyPrimitives_constructor();
     void exceptionSafetyPrimitives_destructor();
@@ -473,7 +478,8 @@ void tst_QArrayData::allocate_data()
     } options[] = {
         { "Default", QArrayData::DefaultAllocationFlags, false },
         { "Reserved", QArrayData::CapacityReserved, true },
-        { "Grow", QArrayData::GrowsForward, false }
+        { "Grow", QArrayData::GrowsForward, false },
+        { "GrowBack", QArrayData::GrowsBackwards, false }
     };
 
     for (size_t i = 0; i < sizeof(types)/sizeof(types[0]); ++i)
@@ -507,7 +513,7 @@ void tst_QArrayData::allocate()
 
         keeper.headers.append(data);
 
-        if (allocateOptions & QArrayData::GrowsForward)
+        if (allocateOptions & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))
             QVERIFY(data->allocatedCapacity() > capacity);
         else
             QCOMPARE(data->allocatedCapacity(), capacity);
@@ -549,7 +555,7 @@ void tst_QArrayData::reallocate()
     keeper.headers.clear();
     keeper.headers.append(data);
 
-    if (allocateOptions & QArrayData::GrowsForward)
+    if (allocateOptions & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))
         QVERIFY(data->allocatedCapacity() > newCapacity);
     else
         QCOMPARE(data->allocatedCapacity(), newCapacity);
@@ -1128,6 +1134,7 @@ void tst_QArrayData::arrayOpsExtra()
 
     const auto setupDataPointers = [&allocationOptions] (size_t capacity, size_t initialSize = 0) {
         const qsizetype alloc = qsizetype(capacity);
+        // QTBUG-84320: change to growing function once supported
         QArrayDataPointer<int> i(QTypedArrayData<int>::allocate(alloc, allocationOptions));
         QArrayDataPointer<QString> s(QTypedArrayData<QString>::allocate(alloc, allocationOptions));
         QArrayDataPointer<CountedObject> o(QTypedArrayData<CountedObject>::allocate(alloc, allocationOptions));
@@ -1839,14 +1846,14 @@ void tst_QArrayData::freeSpace()
 {
     QFETCH(QArrayData::ArrayOptions, allocationOptions);
     QFETCH(size_t, n);
-    const auto testFreeSpace = [] (auto dummy, auto options, size_t n) {
+    const auto testFreeSpace = [] (auto dummy, auto options, qsizetype n) {
         using Type = std::decay_t<decltype(dummy)>;
-        using Data = QTypedArrayData<Type>;
         using DataPointer = QArrayDataPointer<Type>;
         Q_UNUSED(dummy);
-        DataPointer ptr(Data::allocate(n, options));
+        const qsizetype capacity = n + 1;
+        auto ptr = DataPointer::allocateGrow(DataPointer(), capacity, n, options);
         const auto alloc = qsizetype(ptr.constAllocatedCapacity());
-        QVERIFY(size_t(alloc) >= n);
+        QVERIFY(alloc >= capacity);
         QCOMPARE(ptr.freeSpaceAtBegin() + ptr.freeSpaceAtEnd(), alloc);
     };
     RUN_TEST_FUNC(testFreeSpace, char(0), allocationOptions, n);
@@ -1856,6 +1863,122 @@ void tst_QArrayData::freeSpace()
     RUN_TEST_FUNC(testFreeSpace, CountedObject(), allocationOptions, n);
 }
 
+void tst_QArrayData::dataPointerAllocate()
+{
+    QFETCH(QArrayData::ArrayOptions, allocationOptions);
+    const auto createDataPointer = [] (qsizetype capacity, auto initValue) {
+        using Type = std::decay_t<decltype(initValue)>;
+        Q_UNUSED(initValue);
+        return QArrayDataPointer<Type>(QTypedArrayData<Type>::allocate(capacity));
+    };
+
+    const auto testRealloc = [&] (qsizetype capacity, qsizetype newSize, auto initValue) {
+        using Type = std::decay_t<decltype(initValue)>;
+        using DataPointer = QArrayDataPointer<Type>;
+
+        auto oldDataPointer = createDataPointer(capacity, initValue);
+        oldDataPointer->insert(oldDataPointer.begin(), 1, initValue);  // trigger prepend
+        QVERIFY(!oldDataPointer.needsDetach());
+
+        auto newDataPointer = DataPointer::allocateGrow(
+            oldDataPointer, oldDataPointer->detachCapacity(newSize), newSize, allocationOptions);
+        const auto newAlloc = newDataPointer.constAllocatedCapacity();
+        const auto freeAtBegin = newDataPointer.freeSpaceAtBegin();
+        const auto freeAtEnd = newDataPointer.freeSpaceAtEnd();
+
+        QVERIFY(newAlloc > oldDataPointer.constAllocatedCapacity());
+        QCOMPARE(size_t(freeAtBegin + freeAtEnd), newAlloc);
+        // when not detached, the behavior is the same as of ::realloc
+        if (allocationOptions & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))
+            QCOMPARE(freeAtBegin, oldDataPointer.freeSpaceAtBegin());
+        else
+            QCOMPARE(freeAtBegin, 0);
+    };
+
+    for (size_t n : {10, 512, 1000}) {
+        RUN_TEST_FUNC(testRealloc, n, n + 1, int(0));
+        RUN_TEST_FUNC(testRealloc, n, n + 1, char('a'));
+        RUN_TEST_FUNC(testRealloc, n, n + 1, char16_t(u'a'));
+        RUN_TEST_FUNC(testRealloc, n, n + 1, QString("hello, world!"));
+        RUN_TEST_FUNC(testRealloc, n, n + 1, CountedObject());
+    }
+
+    const auto testDetachRealloc = [&] (qsizetype capacity, qsizetype newSize, auto initValue) {
+        using Type = std::decay_t<decltype(initValue)>;
+        using DataPointer = QArrayDataPointer<Type>;
+
+        auto oldDataPointer = createDataPointer(capacity, initValue);
+        oldDataPointer->insert(oldDataPointer.begin(), 1, initValue);  // trigger prepend
+        auto oldDataPointerCopy = oldDataPointer;  // force detach later
+        QVERIFY(oldDataPointer.needsDetach());
+
+        auto newDataPointer = DataPointer::allocateGrow(
+            oldDataPointer, oldDataPointer->detachCapacity(newSize), newSize, allocationOptions);
+        const auto newAlloc = newDataPointer.constAllocatedCapacity();
+        const auto freeAtBegin = newDataPointer.freeSpaceAtBegin();
+        const auto freeAtEnd = newDataPointer.freeSpaceAtEnd();
+
+        QVERIFY(newAlloc > oldDataPointer.constAllocatedCapacity());
+        QCOMPARE(size_t(freeAtBegin + freeAtEnd), newAlloc);
+        if (allocationOptions & QArrayData::GrowsBackwards) {
+            QCOMPARE(size_t(freeAtBegin), (newAlloc - newSize) / 2);
+        } else {
+            QCOMPARE(freeAtBegin, 0);
+        }
+    };
+
+    for (size_t n : {10, 512, 1000}) {
+        RUN_TEST_FUNC(testDetachRealloc, n, n + 1, int(0));
+        RUN_TEST_FUNC(testDetachRealloc, n, n + 1, char('a'));
+        RUN_TEST_FUNC(testDetachRealloc, n, n + 1, char16_t(u'a'));
+        RUN_TEST_FUNC(testDetachRealloc, n, n + 1, QString("hello, world!"));
+        RUN_TEST_FUNC(testDetachRealloc, n, n + 1, CountedObject());
+    }
+}
+
+void tst_QArrayData::dataPointerAllocateAlignedWithReallocate_data()
+{
+    QTest::addColumn<QArrayData::ArrayOptions>("initFlags");
+    QTest::addColumn<QArrayData::ArrayOptions>("newFlags");
+
+    QTest::newRow("default-flags") << QArrayData::ArrayOptions(QArrayData::DefaultAllocationFlags)
+                                   << QArrayData::ArrayOptions(QArrayData::DefaultAllocationFlags);
+    QTest::newRow("no-grows-backwards") << QArrayData::ArrayOptions(QArrayData::GrowsForward)
+                                        << QArrayData::ArrayOptions(QArrayData::GrowsForward);
+    QTest::newRow("grows-backwards") << QArrayData::ArrayOptions(QArrayData::GrowsBackwards)
+                                     << QArrayData::ArrayOptions(QArrayData::GrowsBackwards);
+    QTest::newRow("removed-grows-backwards") << QArrayData::ArrayOptions(QArrayData::GrowsBackwards)
+                                             << QArrayData::ArrayOptions(QArrayData::GrowsForward);
+    QTest::newRow("removed-growth") << QArrayData::ArrayOptions(QArrayData::GrowsBackwards)
+                                    << QArrayData::ArrayOptions(QArrayData::DefaultAllocationFlags);
+}
+
+void tst_QArrayData::dataPointerAllocateAlignedWithReallocate()
+{
+    QFETCH(QArrayData::ArrayOptions, initFlags);
+    QFETCH(QArrayData::ArrayOptions, newFlags);
+
+    // Note: using the same type to ensure alignment and padding are the same.
+    //       otherwise, we may get differences in the allocated size
+    auto a = QArrayDataPointer<int>::allocateGrow(QArrayDataPointer<int>(), 50, 0, initFlags);
+    auto b = QArrayDataPointer<int>::allocateGrow(QArrayDataPointer<int>(), 50, 0, initFlags);
+
+    if (initFlags & QArrayData::GrowsBackwards) {
+        QVERIFY(a.freeSpaceAtBegin() > 0);
+    } else {
+        QVERIFY(a.freeSpaceAtBegin() == 0);
+    }
+    QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin());
+
+    a->reallocate(100, newFlags);
+    b = QArrayDataPointer<int>::allocateGrow(b, 100, b.size, newFlags);
+
+    // It is enough to test that the behavior of reallocate is the same as the
+    // behavior of allocate w.r.t. pointer adjustment in case of
+    // GrowsBackwards. Actual values are not that interesting
+    QCOMPARE(a.freeSpaceAtBegin(), b.freeSpaceAtBegin());
+}
+
 #ifndef QT_NO_EXCEPTIONS
 struct ThrowingTypeWatcher
 {