QArrayDataOps::insert

Inserting elements anywhere in the array requires moving the elements
that follow out of the way and writing in the new ones. Trivial for PODs
and almost as much for movable types.

For "complex" types, we start by extending the array with placement new
and copy constructing elements. Then, copy assignment resets the
elements that were previously part of the array.

QPodArrayOps uses non-throwing operations. QMovableArrayOps provides
full rollback in the face of exceptions (strong guarantee).
QGenericArrayOps enforces that no data is leaked (all destructors
called) and invariants are maintained on exceptions -- the basic
guarantee.

With 3 different implementations, 2 of which are non-trivial, this
operation is a good showcase for QArrayOpsSelector and the different
implementations. As such, it warrants its own commit.

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

2 files changed, 238 insertions, 0 deletions

diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h
index 36c9b7bc50..4aa3ab09c8 100644
--- a/tests/auto/corelib/tools/qarraydata/simplevector.h
+++ b/tests/auto/corelib/tools/qarraydata/simplevector.h
@@ -135,6 +135,113 @@ public:
         return *(end() - 1);
     }
 
+    void reserve(size_t n)
+    {
+        if (n > capacity()
+                || (n
+                && !d->capacityReserved
+                && (d->ref != 1 || (d->capacityReserved = 1, false)))) {
+            SimpleVector detached(Data::allocate(n, true));
+            static_cast<DataOps *>(detached.d)->copyAppend(constBegin(), constEnd());
+            detached.swap(*this);
+        }
+    }
+
+    void prepend(const_iterator first, const_iterator last)
+    {
+        if (!d->size) {
+            append(first, last);
+            return;
+        }
+
+        if (first == last)
+            return;
+
+        T *const begin = d->begin();
+        if (d->ref != 1
+                || capacity() - size() < size_t(last - first)) {
+            SimpleVector detached(Data::allocate(
+                        qMax(capacity(), size() + (last - first)), d->capacityReserved));
+
+            static_cast<DataOps *>(detached.d)->copyAppend(first, last);
+            static_cast<DataOps *>(detached.d)->copyAppend(begin, begin + d->size);
+            detached.swap(*this);
+
+            return;
+        }
+
+        static_cast<DataOps *>(d)->insert(begin, first, last);
+    }
+
+    void append(const_iterator first, const_iterator last)
+    {
+        if (first == last)
+            return;
+
+        if (d->ref != 1
+                || capacity() - size() < size_t(last - first)) {
+            SimpleVector detached(Data::allocate(
+                        qMax(capacity(), size() + (last - first)), d->capacityReserved));
+
+            if (d->size) {
+                const T *const begin = constBegin();
+                static_cast<DataOps *>(detached.d)->copyAppend(begin, begin + d->size);
+            }
+            static_cast<DataOps *>(detached.d)->copyAppend(first, last);
+            detached.swap(*this);
+
+            return;
+        }
+
+        static_cast<DataOps *>(d)->copyAppend(first, last);
+    }
+
+    void insert(int position, const_iterator first, const_iterator last)
+    {
+        if (position < 0)
+            position += d->size + 1;
+
+        if (position <= 0) {
+            prepend(first, last);
+            return;
+        }
+
+        if (size_t(position) >= size()) {
+            append(first, last);
+            return;
+        }
+
+        if (first == last)
+            return;
+
+        T *const begin = d->begin();
+        T *const where = begin + position;
+        const T *const end = begin + d->size;
+        if (d->ref != 1
+                || capacity() - size() < size_t(last - first)) {
+            SimpleVector detached(Data::allocate(
+                        qMax(capacity(), size() + (last - first)), d->capacityReserved));
+
+            if (position)
+                static_cast<DataOps *>(detached.d)->copyAppend(begin, where);
+            static_cast<DataOps *>(detached.d)->copyAppend(first, last);
+            static_cast<DataOps *>(detached.d)->copyAppend(where, end);
+            detached.swap(*this);
+
+            return;
+        }
+
+        // Temporarily copy overlapping data, if needed
+        if ((first >= where && first < end)
+                || (last > where && last <= end)) {
+            SimpleVector tmp(first, last);
+            static_cast<DataOps *>(d)->insert(where, tmp.constBegin(), tmp.constEnd());
+            return;
+        }
+
+        static_cast<DataOps *>(d)->insert(where, first, last);
+    }
+
     void swap(SimpleVector &other)
     {
         qSwap(d, other.d);
diff --git a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
index 2972f0a678..808aa73c98 100644
--- a/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
+++ b/tests/auto/corelib/tools/qarraydata/tst_qarraydata.cpp
@@ -293,6 +293,67 @@ void tst_QArrayData::simpleVector()
         QVERIFY(v5.isSharedWith(v6));
         QVERIFY(!v1.isSharedWith(v5));
     }
+
+    v1.prepend(array, array + sizeof(array)/sizeof(array[0]));
+    QCOMPARE(v1.size(), size_t(10));
+    QVERIFY(v1 == v8);
+
+    v6 = v1;
+    QVERIFY(v1.isSharedWith(v6));
+
+    v1.prepend(array, array + sizeof(array)/sizeof(array[0]));
+    QVERIFY(!v1.isSharedWith(v6));
+    QCOMPARE(v1.size(), size_t(20));
+    QCOMPARE(v6.size(), size_t(10));
+
+    for (int i = 0; i < 20; ++i)
+        QCOMPARE(v1[i], v6[i % 10]);
+
+    v1.clear();
+
+    v1.append(array, array + sizeof(array)/sizeof(array[0]));
+    QCOMPARE(v1.size(), size_t(10));
+    QVERIFY(v1 == v8);
+
+    v6 = v1;
+    QVERIFY(v1.isSharedWith(v6));
+
+    v1.append(array, array + sizeof(array)/sizeof(array[0]));
+    QVERIFY(!v1.isSharedWith(v6));
+    QCOMPARE(v1.size(), size_t(20));
+    QCOMPARE(v6.size(), size_t(10));
+
+    for (int i = 0; i < 20; ++i)
+        QCOMPARE(v1[i], v6[i % 10]);
+
+    v1.insert(0, v6.constBegin(), v6.constEnd());
+    QCOMPARE(v1.size(), size_t(30));
+
+    v6 = v1;
+    QVERIFY(v1.isSharedWith(v6));
+
+    v1.insert(10, v6.constBegin(), v6.constEnd());
+    QVERIFY(!v1.isSharedWith(v6));
+    QCOMPARE(v1.size(), size_t(60));
+    QCOMPARE(v6.size(), size_t(30));
+
+    for (int i = 0; i < 30; ++i)
+        QCOMPARE(v6[i], v8[i % 10]);
+
+    v1.insert(v1.size(), v6.constBegin(), v6.constEnd());
+    QCOMPARE(v1.size(), size_t(90));
+
+    v1.insert(-1, v8.constBegin(), v8.constEnd());
+    QCOMPARE(v1.size(), size_t(100));
+
+    v1.insert(-11, v8.constBegin(), v8.constEnd());
+    QCOMPARE(v1.size(), size_t(110));
+
+    v1.insert(-200, v8.constBegin(), v8.constEnd());
+    QCOMPARE(v1.size(), size_t(120));
+
+    for (int i = 0; i < 120; ++i)
+        QCOMPARE(v1[i], v8[i % 10]);
 }
 
 struct Deallocator
@@ -669,12 +730,82 @@ void tst_QArrayData::arrayOps()
     vs = SimpleVector<QString>(5, referenceString);
     vo = SimpleVector<CountedObject>(5, referenceObject);
 
+    QCOMPARE(vi.size(), size_t(5));
+    QCOMPARE(vs.size(), size_t(5));
+    QCOMPARE(vo.size(), size_t(5));
+
     QCOMPARE(CountedObject::liveCount, size_t(11));
     for (int i = 0; i < 5; ++i) {
         QCOMPARE(vi[i], referenceInt);
         QVERIFY(vs[i].isSharedWith(referenceString));
         QCOMPARE(vo[i].id, referenceObject.id);
     }
+
+    ////////////////////////////////////////////////////////////////////////////
+    // insert
+    vi.reserve(30);
+    vs.reserve(30);
+    vo.reserve(30);
+
+    QCOMPARE(vi.size(), size_t(5));
+    QCOMPARE(vs.size(), size_t(5));
+    QCOMPARE(vo.size(), size_t(5));
+
+    QVERIFY(vi.capacity() >= 30);
+    QVERIFY(vs.capacity() >= 30);
+    QVERIFY(vo.capacity() >= 30);
+
+    // Displace as many elements as array is extended by
+    vi.insert(0, intArray, intArray + 5);
+    vs.insert(0, stringArray, stringArray + 5);
+    vo.insert(0, objArray, objArray + 5);
+
+    QCOMPARE(vi.size(), size_t(10));
+    QCOMPARE(vs.size(), size_t(10));
+    QCOMPARE(vo.size(), size_t(10));
+
+    // Displace more elements than array is extended by
+    vi.insert(0, intArray, intArray + 5);
+    vs.insert(0, stringArray, stringArray + 5);
+    vo.insert(0, objArray, objArray + 5);
+
+    QCOMPARE(vi.size(), size_t(15));
+    QCOMPARE(vs.size(), size_t(15));
+    QCOMPARE(vo.size(), size_t(15));
+
+    // Displace less elements than array is extended by
+    vi.insert(5, vi.constBegin(), vi.constEnd());
+    vs.insert(5, vs.constBegin(), vs.constEnd());
+    vo.insert(5, vo.constBegin(), vo.constEnd());
+
+    QCOMPARE(vi.size(), size_t(30));
+    QCOMPARE(vs.size(), size_t(30));
+    QCOMPARE(vo.size(), size_t(30));
+
+    QCOMPARE(CountedObject::liveCount, size_t(36));
+    for (int i = 0; i < 15; ++i) {
+        QCOMPARE(vi[i], intArray[i % 5]);
+        QVERIFY(vs[i].isSharedWith(stringArray[i % 5]));
+        QCOMPARE(vo[i].id, objArray[i % 5].id);
+    }
+
+    for (int i = 15; i < 20; ++i) {
+        QCOMPARE(vi[i], referenceInt);
+        QVERIFY(vs[i].isSharedWith(referenceString));
+        QCOMPARE(vo[i].id, referenceObject.id);
+    }
+
+    for (int i = 20; i < 25; ++i) {
+        QCOMPARE(vi[i], intArray[i % 5]);
+        QVERIFY(vs[i].isSharedWith(stringArray[i % 5]));
+        QCOMPARE(vo[i].id, objArray[i % 5].id);
+    }
+
+    for (int i = 25; i < 30; ++i) {
+        QCOMPARE(vi[i], referenceInt);
+        QVERIFY(vs[i].isSharedWith(referenceString));
+        QCOMPARE(vo[i].id, referenceObject.id);
+    }
 }
 
 QTEST_APPLESS_MAIN(tst_QArrayData)