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>

1 files changed, 27 insertions, 0 deletions

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
     {