Add AllocationOption::Grow

This is meant to reduce the number of allocations on growing containers.
It serves the same purpose as the existing qAllocMore which is currently
used by container classes.

While only a container knows when it is growing, it doesn't need to care
how that information is used. qAllocMore is currently treated as a
black-box and its result is (basically) forwarded blindly to an allocate
function. In that respect, container code using qAllocMore acts as an
intermediary.

By merging that functionality in the allocate function itself we offer
the same benefits without the intermediaries, allowing for simpler code
and centralized decisions on memory allocation.

Once all users of qAllocMore get ported to QArrayData and
QArrayData::allocate, qAllocMore can be moved or more closely integrated
into qarraydata.cpp and qtools_p.h can be dropped.

Change-Id: I4c09bf7df274b45c399082fc7113a18e4641c5f0
Reviewed-by: Bradley T. Hughes <bradley.hughes@nokia.com>

2 files changed, 36 insertions, 4 deletions

diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h
index a0a9b5f764..fe8108bff2 100644
--- a/tests/auto/corelib/tools/qarraydata/simplevector.h
+++ b/tests/auto/corelib/tools/qarraydata/simplevector.h
@@ -178,7 +178,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             detached.d->copyAppend(first, last);
             detached.d->copyAppend(begin, begin + d->size);
@@ -199,7 +199,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             if (d->size) {
                 const T *const begin = constBegin();
@@ -239,7 +239,7 @@ public:
                 || capacity() - size() < size_t(last - first)) {
             SimpleVector detached(Data::allocate(
                         qMax(capacity(), size() + (last - first)),
-                        d->detachFlags()));
+                        d->detachFlags() | Data::Grow));
 
             if (position)
                 detached.d->copyAppend(begin, where);
diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
index 36bf7516a9..f3f1daba0f 100644
--- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
+++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
@@ -87,6 +87,7 @@ private slots:
     void literals();
     void variadicLiterals();
     void rValueReferences();
+    void grow();
 };
 
 template <class T> const T &const_(const T &t) { return t; }
@@ -651,6 +652,7 @@ void tst_QArrayData::allocate_data()
             QArrayData::CapacityReserved | QArrayData::Unsharable, true, false,
             unsharable_empty },
         { "Unsharable", QArrayData::Unsharable, false, false, unsharable_empty },
+        { "Grow", QArrayData::Grow, false, true, shared_empty }
     };
 
     for (size_t i = 0; i < sizeof(types)/sizeof(types[0]); ++i)
@@ -690,7 +692,10 @@ void tst_QArrayData::allocate()
         keeper.headers.append(data);
 
         QCOMPARE(data->size, 0);
-        QVERIFY(data->alloc >= uint(capacity));
+        if (allocateOptions & QArrayData::Grow)
+            QVERIFY(data->alloc > uint(capacity));
+        else
+            QCOMPARE(data->alloc, uint(capacity));
         QCOMPARE(data->capacityReserved, uint(isCapacityReserved));
         QCOMPARE(data->ref.isSharable(), isSharable);
 
@@ -1385,5 +1390,32 @@ void tst_QArrayData::rValueReferences()
 #endif
 }
 
+void tst_QArrayData::grow()
+{
+    SimpleVector<int> vector;
+
+    QCOMPARE(vector.size(), size_t(0));
+
+    size_t previousCapacity = vector.capacity();
+    size_t allocations = 0;
+    for (size_t i = 1; i <=  (1 << 20); ++i) {
+        int source[1] = { i };
+        vector.append(source, source + 1);
+        QCOMPARE(vector.size(), i);
+        if (vector.capacity() != previousCapacity) {
+            previousCapacity = vector.capacity();
+            ++allocations;
+        }
+    }
+    QCOMPARE(vector.size(), size_t(1 << 20));
+
+    // QArrayData::Grow prevents excessive allocations on a growing container
+    QVERIFY(allocations > 20 / 2);
+    QVERIFY(allocations < 20 * 2);
+
+    for (size_t i = 0; i < (1 << 20); ++i)
+        QCOMPARE(const_(vector).at(i), int(i + 1));
+}
+
 QTEST_APPLESS_MAIN(tst_QArrayData)
 #include "tst_qarraydata.moc"