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>

4 files changed, 104 insertions, 13 deletions

diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp
index cea41dbaff..03465238b8 100644
--- a/src/corelib/tools/qarraydata.cpp
+++ b/src/corelib/tools/qarraydata.cpp
@@ -145,7 +145,7 @@ static inline qsizetype calculateBlockSize(qsizetype &capacity, qsizetype object
     // Calculate the byte size
     // allocSize = objectSize * capacity + headerSize, but checked for overflow
     // plus padded to grow in size
-    if (options & QArrayData::GrowsForward) {
+    if (options & (QArrayData::GrowsForward | QArrayData::GrowsBackwards)) {
         auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize);
         capacity = r.elementCount;
         return r.size;
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index f6384ca998..8c0ca8f2f4 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -465,6 +465,19 @@ public:
 
     void reallocate(qsizetype alloc, typename Data::ArrayOptions options)
     {
+        // when reallocating, take care of the situation when no growth is
+        // happening - need to move the data in this case, unfortunately
+        const bool grows = options & (Data::GrowsForward | Data::GrowsBackwards);
+
+        // ### optimize me: there may be cases when moving is not obligatory
+        if (this->d && !grows) {
+            const auto gap = this->freeSpaceAtBegin();
+            auto oldBegin = this->begin();
+            this->ptr -= gap;
+            ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
+                      this->size * sizeof(T));
+        }
+
         auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, options);
         this->d = pair.first;
         this->ptr = pair.second;
@@ -1033,11 +1046,55 @@ struct QArrayOpsSelector<T,
     typedef QMovableArrayOps<T> Type;
 };
 
+template <class T>
+struct QCommonArrayOps : QArrayOpsSelector<T>::Type
+{
+    using Base = typename QArrayOpsSelector<T>::Type;
+    using parameter_type = typename Base::parameter_type;
+    using iterator = typename Base::iterator;
+    using const_iterator = typename Base::const_iterator;
+
+    // Returns whether reallocation is desirable before adding more elements
+    // into the container. This is a helper function that one can use to
+    // theoretically improve average operations performance. Ignoring this
+    // function does not affect the correctness of the array operations.
+    bool shouldGrowBeforeInsert(const_iterator where, qsizetype n) const noexcept
+    {
+        if (this->d == nullptr)
+            return true;
+        if (this->d->flags & QArrayData::CapacityReserved)
+            return false;
+        if (!(this->d->flags & (QArrayData::GrowsForward | QArrayData::GrowsBackwards)))
+            return false;
+        Q_ASSERT(where >= this->begin() && where <= this->end());  // in range
+
+        const qsizetype freeAtBegin = this->freeSpaceAtBegin();
+        const qsizetype freeAtEnd = this->freeSpaceAtEnd();
+        const qsizetype capacity = this->constAllocatedCapacity();
+
+        if (where == this->begin()) {  // prepend
+            // Qt5 QList in prepend: not enough space at begin && 33% full
+            // Now (below):
+            return freeAtBegin < n && (this->size >= (capacity / 3));
+        }
+
+        if (where == this->end()) {  // append
+            // Qt5 QList in append: not enough space at end && less than 66% free space at front
+            // Now (below):
+            return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3));
+        }
+
+        // Qt5 QList in insert: no free space
+        // Now: no free space OR not enough space on either of the sides (bad perf. case)
+        return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n);
+    }
+};
+
 } // namespace QtPrivate
 
 template <class T>
 struct QArrayDataOps
-    : QtPrivate::QArrayOpsSelector<T>::Type
+    : QtPrivate::QCommonArrayOps<T>
 {
 };
 
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index d1697d6493..aebc83ba3f 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -209,6 +209,33 @@ public:
         return d->constAllocatedCapacity() - freeSpaceAtBegin() - this->size;
     }
 
+    static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype capacity,
+                                          qsizetype newSize, QArrayData::ArrayOptions options)
+    {
+        auto [header, dataPtr] = Data::allocate(capacity, options);
+        const bool valid = header != nullptr && dataPtr != nullptr;
+        const bool grows = (options & (Data::GrowsForward | Data::GrowsBackwards));
+        if (!valid || !grows)
+            return QArrayDataPointer(header, dataPtr);
+
+        // when growing, special rules apply to memory layout
+
+        if (from.needsDetach()) {
+            // When detaching: the free space reservation is biased towards
+            // append as in Qt5 QList. If we're growing backwards, put the data
+            // in the middle instead of at the end - assuming that prepend is
+            // uncommon and even initial prepend will eventually be followed by
+            // at least some appends.
+            if (options & Data::GrowsBackwards)
+                dataPtr += (header->alloc - newSize) / 2;
+        } else {
+            // When not detaching: fake ::realloc() policy - preserve existing
+            // free space at beginning.
+            dataPtr += from.freeSpaceAtBegin();
+        }
+        return QArrayDataPointer(header, dataPtr);
+    }
+
 private:
     Q_REQUIRED_RESULT QPair<Data *, T *> clone(QArrayData::ArrayOptions options) const
     {
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index fad61bf8e6..300baeba8c 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -560,10 +560,12 @@ inline void QList<T>::append(const_iterator i1, const_iterator i2)
 {
     if (i1 == i2)
         return;
-    const size_t newSize = size() + std::distance(i1, i2);
-    if (d->needsDetach() || newSize > d->allocatedCapacity()) {
-        DataPointer detached(Data::allocate(d->detachCapacity(newSize),
-                                            d->detachFlags() | Data::GrowsForward));
+    const size_t distance = std::distance(i1, i2);
+    const size_t newSize = size() + distance;
+    const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), qsizetype(distance));
+    if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) {
+        DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                       d->detachFlags() | Data::GrowsForward));
         detached->copyAppend(constBegin(), constEnd());
         detached->copyAppend(i1, i2);
         d.swap(detached);
@@ -582,9 +584,10 @@ inline void QList<T>::append(QList<T> &&other)
         return append(other);
 
     const size_t newSize = size() + other.size();
-    if (d->needsDetach() || newSize > d->allocatedCapacity()) {
-        DataPointer detached(Data::allocate(d->detachCapacity(newSize),
-                                            d->detachFlags() | Data::GrowsForward));
+    const bool shouldGrow = d->shouldGrowBeforeInsert(d.end(), other.size());
+    if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) {
+        DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                       d->detachFlags() | Data::GrowsForward));
 
         if (!d->needsDetach())
             detached->moveAppend(begin(), end());
@@ -610,10 +613,12 @@ QList<T>::insert(qsizetype i, qsizetype n, parameter_type t)
     // it's not worth wasting CPU cycles for that
 
     const size_t newSize = size() + n;
-    if (d->needsDetach() || newSize > d->allocatedCapacity()) {
+    const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + i, n);
+    if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) {
         typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward;
 
-        DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
+        DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                       flags));
         const_iterator where = constBegin() + i;
         detached->copyAppend(constBegin(), where);
         detached->copyAppend(n, t);
@@ -638,11 +643,13 @@ QList<T>::emplace(qsizetype i, Args&&... args)
 {
      Q_ASSERT_X(i >= 0 && i <= d->size, "QList<T>::insert", "index out of range");
 
+    const bool shouldGrow = d->shouldGrowBeforeInsert(d.begin() + i, 1);
     const size_t newSize = size() + 1;
-    if (d->needsDetach() || newSize > d->allocatedCapacity()) {
+    if (d->needsDetach() || newSize > d->allocatedCapacity() || shouldGrow) {
         typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward;
 
-        DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
+        DataPointer detached(DataPointer::allocateGrow(d, d->detachCapacity(newSize), newSize,
+                                                       flags));
         const_iterator where = constBegin() + i;
 
         // First, create an element to handle cases, when a user moves