Remove destructor calls from insert()

QList::insert() should never need to call a destructor. This
requires that we construct the new items in the list in order
and increment the size each time we constructed a new item.

Not having a code path that potentially calls destructors should
avoid the generation of lots of additional code for those
operations. In addition, the forward and backwards code paths
are now unified and only require somewhat different setup of
some variables at the start.

This gives us strong exception safety when appending one item,
weak exception safety in all other cases (in line with std::vector).

Change-Id: I6bf88365a34ea9e55ed1236be01a65499275d150
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

2 files changed, 217 insertions, 235 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 9e5057099e..fa3824f34b 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -120,35 +120,6 @@ struct QArrayExceptionSafetyPrimitives
         }
     };
 
-    // Watches passed pointer. Unless commit() is called, all the elements that
-    // the watched iterator passes through are deleted at the end of object
-    // lifetime.
-    //
-    // Requirements: when not at starting position, the iterator is expected to
-    //               point to a valid object (to initialized memory)
-    struct Destructor
-    {
-        T **iter;
-        T *end;
-        T *intermediate;
-
-        Destructor(T *&it) noexcept
-            : iter(std::addressof(it)), end(it)
-        { }
-        void commit() noexcept
-        {
-            iter = std::addressof(end);
-        }
-        ~Destructor() noexcept(std::is_nothrow_destructible_v<T>)
-        {
-            // Step is either 1 or -1 and depends on the interposition of *iter
-            // and end. Note that *iter is expected to point to a valid object
-            // (see the logic below).
-            for (const int step = *iter < end ? 1 : -1; *iter != end; std::advance(*iter, step))
-                (*iter)->~T();
-        }
-    };
-
     // Moves the data range in memory by the specified amount. Unless commit()
     // is called, the data is moved back to the original place at the end of
     // object lifetime.
@@ -218,6 +189,7 @@ struct QPodArrayOps
 
 protected:
     typedef QTypedArrayData<T> Data;
+    using DataPointer = QArrayDataPointer<T>;
 
 public:
     typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
@@ -283,6 +255,23 @@ public:
         // exception safe; size not updated.
     }
 
+    void insert(qsizetype i, const T *data, qsizetype n)
+    {
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        DataPointer oldData;
+        this->detachAndGrow(pos, n, &oldData);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
+
+        T *where = this->begin() + i;
+        if (pos == QArrayData::GrowsAtBeginning)
+            insert(GrowsBackwardsTag{}, where, data, data + n);
+        else
+            insert(GrowsForwardTag{}, where, data, data + n);
+    }
+
     void insert(GrowsForwardTag, T *where, const T *b, const T *e) noexcept
     {
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
@@ -318,6 +307,24 @@ public:
         this->size += (e - b);
     }
 
+    void insert(qsizetype i, qsizetype n, parameter_type t)
+    {
+        T copy(t);
+
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        this->detachAndGrow(pos, n);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
+
+        T *where = this->begin() + i;
+        if (pos == QArrayData::GrowsAtBeginning)
+            insert(GrowsBackwardsTag{}, where, n, copy);
+        else
+            insert(GrowsForwardTag{}, where, n, copy);
+    }
+
     void insert(GrowsForwardTag, T *where, size_t n, parameter_type t) noexcept
     {
         Q_ASSERT(!this->isShared());
@@ -476,6 +483,7 @@ struct QGenericArrayOps
 
 protected:
     typedef QTypedArrayData<T> Data;
+    using DataPointer = QArrayDataPointer<T>;
 
 public:
     typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
@@ -564,203 +572,179 @@ public:
         std::destroy(this->begin(), this->end());
     }
 
-    void insert(GrowsForwardTag, T *where, const T *b, const T *e)
+    struct Inserter
     {
-        Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
-        Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
-        Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b < e);
-        Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
-        Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
-
-        using Destructor = typename QArrayExceptionSafetyPrimitives<T>::Destructor;
-
-        // Array may be truncated at where in case of exceptions
-
-        T *end = this->end();
-        T *readIter = end;
-        T *writeIter = end + (e - b);
+        QArrayDataPointer<T> *data;
+        qsizetype increment = 1;
+        T *begin;
+        qsizetype size;
 
-        const T *const step1End = where + qMax(e - b, end - where);
+        qsizetype sourceCopyConstruct, nSource, move, sourceCopyAssign;
+        T *end, *last, *where;
 
-        Destructor destroyer(writeIter);
-
-        // Construct new elements in array
-        while (writeIter != step1End) {
-            --readIter;
-            // If exception happens on construction, we should not call ~T()
-            new (writeIter - 1) T(std::move(*readIter));
-            --writeIter;
-        }
-
-        while (writeIter != end) {
-            --e;
-            // If exception happens on construction, we should not call ~T()
-            new (writeIter - 1) T(*e);
-            --writeIter;
-        }
-
-        destroyer.commit();
-        this->size += destroyer.end - end;
-
-        // Copy assign over existing elements
-        while (readIter != where) {
-            --readIter;
-            --writeIter;
-            *writeIter = std::move(*readIter);
+        Inserter(QArrayDataPointer<T> *d, QArrayData::GrowthPosition pos)
+            : data(d), increment(pos == QArrayData::GrowsAtBeginning ? -1 : 1)
+        {
+            begin = d->ptr;
+            size = d->size;
+            if (increment < 0)
+                begin += size - 1;
         }
-
-        while (writeIter != where) {
-            --e;
-            --writeIter;
-            *writeIter = *e;
+        ~Inserter() {
+            if (increment < 0)
+                begin -= size - 1;
+            data->ptr = begin;
+            data->size = size;
         }
-    }
-
-    void insert(GrowsBackwardsTag, T *where, const T *b, const T *e)
-    {
-        Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
-        Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
-        Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(b < e);
-        Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
-        Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
-
-        using Destructor = typename QArrayExceptionSafetyPrimitives<T>::Destructor;
-
-        T *begin = this->begin();
-        T *readIter = begin;
-        T *writeIter = begin - (e - b);
 
-        const T *const step1End = where - qMax(e - b, where - begin);
-
-        Destructor destroyer(writeIter);
+        void setup(qsizetype pos, qsizetype n)
+        {
 
-        // Construct new elements in array
-        while (writeIter != step1End) {
-            new (writeIter) T(std::move(*readIter));
-            ++readIter;
-            ++writeIter;
+            if (increment > 0) {
+                end = begin + size;
+                last = end - 1;
+                where = begin + pos;
+                qsizetype dist = size - pos;
+                sourceCopyConstruct = 0;
+                nSource = n;
+                move = n - dist; // smaller 0
+                sourceCopyAssign = n;
+                if (n > dist) {
+                    sourceCopyConstruct = n - dist;
+                    move = 0;
+                    sourceCopyAssign -= sourceCopyConstruct;
+                }
+            } else {
+                end = begin - size;
+                last = end + 1;
+                where = end + pos;
+                sourceCopyConstruct = 0;
+                nSource = -n;
+                move = pos - n; // larger 0
+                sourceCopyAssign = -n;
+                if (n > pos) {
+                    sourceCopyConstruct = pos - n;
+                    move = 0;
+                    sourceCopyAssign -= sourceCopyConstruct;
+                }
+            }
         }
 
-        while (writeIter != begin) {
-            new (writeIter) T(*b);
-            ++b;
-            ++writeIter;
-        }
+        void insert(qsizetype pos, const T *source, qsizetype n)
+        {
+            qsizetype oldSize = size;
+            Q_UNUSED(oldSize);
+
+            setup(pos, n);
+            if (increment < 0)
+                source += n - 1;
+
+            // first create new elements at the end, by copying from elements
+            // to be inserted (if they extend past the current end of the array)
+            for (qsizetype i = 0; i != sourceCopyConstruct; i += increment) {
+                new (end + i) T(source[nSource - sourceCopyConstruct + i]);
+                ++size;
+            }
+            Q_ASSERT(size <= oldSize + n);
 
-        destroyer.commit();
-        this->size += begin - destroyer.end;
-        this->ptr -= begin - destroyer.end;
+            // now move construct new elements at the end from existing elements inside
+            // the array.
+            for (qsizetype i = sourceCopyConstruct; i != nSource; i += increment) {
+                new (end + i) T(std::move(*(end + i - nSource)));
+                ++size;
+            }
+            // array has the new size now!
+            Q_ASSERT(size == oldSize + n);
 
-        // Copy assign over existing elements
-        while (readIter != where) {
-            *writeIter = std::move(*readIter);
-            ++readIter;
-            ++writeIter;
-        }
+            // now move assign existing elements towards the end
+            for (qsizetype i = 0; i != move; i -= increment)
+                last[i] = std::move(last[i - nSource]);
 
-        while (writeIter != where) {
-            *writeIter = *b;
-            ++b;
-            ++writeIter;
+            // finally copy the remaining elements from source over
+            for (qsizetype i = 0; i != sourceCopyAssign; i += increment)
+                where[i] = source[i];
         }
-    }
 
-    void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
-    {
-        Q_ASSERT(!this->isShared());
-        Q_ASSERT(n);
-        Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
+        void insert(qsizetype pos, const T &t, qsizetype n)
+        {
+            qsizetype oldSize = size;
+            Q_UNUSED(oldSize);
 
-        using Destructor = typename QArrayExceptionSafetyPrimitives<T>::Destructor;
+            setup(pos, n);
 
-        // Array may be truncated at where in case of exceptions
-        T *end = this->end();
-        T *readIter = end;
-        T *writeIter = end + n;
+            // first create new elements at the end, by copying from elements
+            // to be inserted (if they extend past the current end of the array)
+            for (qsizetype i = 0; i != sourceCopyConstruct; i += increment) {
+                new (end + i) T(t);
+                ++size;
+            }
+            Q_ASSERT(size <= oldSize + n);
 
-        const T *const step1End = where + qMax<size_t>(n, end - where);
+            // now move construct new elements at the end from existing elements inside
+            // the array.
+            for (qsizetype i = sourceCopyConstruct; i != nSource; i += increment) {
+                new (end + i) T(std::move(*(end + i - nSource)));
+                ++size;
+            }
+            // array has the new size now!
+            Q_ASSERT(size == oldSize + n);
 
-        Destructor destroyer(writeIter);
+            // now move assign existing elements towards the end
+            for (qsizetype i = 0; i != move; i -= increment)
+                last[i] = std::move(last[i - nSource]);
 
-        // Construct new elements in array
-        while (writeIter != step1End) {
-            --readIter;
-            // If exception happens on construction, we should not call ~T()
-            new (writeIter - 1) T(std::move(*readIter));
-            --writeIter;
+            // finally copy the remaining elements from source over
+            for (qsizetype i = 0; i != sourceCopyAssign; i += increment)
+                where[i] = t;
         }
 
-        while (writeIter != end) {
-            --n;
-            // If exception happens on construction, we should not call ~T()
-            new (writeIter - 1) T(t);
-            --writeIter;
+#if 0
+        void insertHole(T *where)
+        {
+            T *oldEnd = end;
+
+            // create a new element at the end by mov constructing one existing element
+            // inside the array.
+            new (end) T(std::move(end - increment));
+            end += increment;
+
+            // now move existing elements towards the end
+            T *to = oldEnd;
+            T *from = oldEnd - increment;
+            while (from != where) {
+                *to = std::move(*from);
+                to -= increment;
+                from -= increment;
+            }
         }
+#endif
+    };
 
-        destroyer.commit();
-        this->size += destroyer.end - end;
-
-        // Copy assign over existing elements
-        while (readIter != where) {
-            --readIter;
-            --writeIter;
-            *writeIter = std::move(*readIter);
-        }
+    void insert(qsizetype i, const T *data, qsizetype n)
+    {
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        DataPointer oldData;
+        this->detachAndGrow(pos, n, &oldData);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
-        while (writeIter != where) {
-            --n;
-            --writeIter;
-            *writeIter = t;
-        }
+        Inserter(this, pos).insert(i, data, n);
     }
 
-    void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
+    void insert(qsizetype i, qsizetype n, parameter_type t)
     {
-        Q_ASSERT(!this->isShared());
-        Q_ASSERT(n);
-        Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
-
-        using Destructor = typename QArrayExceptionSafetyPrimitives<T>::Destructor;
-
-        T *begin = this->begin();
-        T *readIter = begin;
-        T *writeIter = begin - n;
-
-        const T *const step1End = where - qMax<size_t>(n, where - begin);
-
-        Destructor destroyer(writeIter);
-
-        // Construct new elements in array
-        while (writeIter != step1End) {
-            new (writeIter) T(std::move(*readIter));
-            ++readIter;
-            ++writeIter;
-        }
-
-        while (writeIter != begin) {
-            new (writeIter) T(t);
-            ++writeIter;
-        }
-
-        destroyer.commit();
-        this->size += begin - destroyer.end;
-        this->ptr -= begin - destroyer.end;
+        T copy(t);
 
-        // Copy assign over existing elements
-        while (readIter != where) {
-            *writeIter = std::move(*readIter);
-            ++readIter;
-            ++writeIter;
-        }
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        this->detachAndGrow(pos, n);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
-        while (writeIter != where) {
-            *writeIter = t;
-            ++writeIter;
-        }
+        Inserter(this, pos).insert(i, copy, n);
     }
 
     template<typename... Args>
@@ -913,6 +897,7 @@ struct QMovableArrayOps
 
 protected:
     typedef QTypedArrayData<T> Data;
+    using DataPointer = QArrayDataPointer<T>;
 
 public:
     // using QGenericArrayOps<T>::appendInitialize;
@@ -922,6 +907,23 @@ public:
     // using QGenericArrayOps<T>::destroyAll;
     typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
 
+    void insert(qsizetype i, const T *data, qsizetype n)
+    {
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        DataPointer oldData;
+        this->detachAndGrow(pos, n, &oldData);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
+
+        T *where = this->begin() + i;
+        if (pos == QArrayData::GrowsAtBeginning)
+            insert(GrowsBackwardsTag{}, where, data, data + n);
+        else
+            insert(GrowsForwardTag{}, where, data, data + n);
+    }
+
     void insert(GrowsForwardTag, T *where, const T *b, const T *e)
     {
         Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
@@ -967,6 +969,24 @@ public:
         this->size += copiedSize;
     }
 
+    void insert(qsizetype i, qsizetype n, parameter_type t)
+    {
+        T copy(t);
+
+        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
+        if (this->size != 0 && i <= (this->size >> 1))
+            pos = Data::GrowsAtBeginning;
+        this->detachAndGrow(pos, n);
+        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
+                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
+
+        T *where = this->begin() + i;
+        if (pos == QArrayData::GrowsAtBeginning)
+            insert(GrowsBackwardsTag{}, where, n, copy);
+        else
+            insert(GrowsForwardTag{}, where, n, copy);
+    }
+
     void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
     {
         Q_ASSERT(!this->isShared());
@@ -1169,41 +1189,6 @@ public:
     }
 
 public:
-    void insert(qsizetype i, qsizetype n, parameter_type t)
-    {
-        T copy(t);
-
-        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
-        if (this->size != 0 && i <= (this->size >> 1))
-            pos = Data::GrowsAtBeginning;
-        this->detachAndGrow(pos, n);
-        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
-                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
-
-        T *where = this->begin() + i;
-        if (pos == QArrayData::GrowsAtBeginning)
-            Base::insert(GrowsBackwardsTag{}, where, n, copy);
-        else
-            Base::insert(GrowsForwardTag{}, where, n, copy);
-    }
-
-    void insert(qsizetype i, const T *data, qsizetype n)
-    {
-        typename Data::GrowthPosition pos = Data::GrowsAtEnd;
-        if (this->size != 0 && i <= (this->size >> 1))
-            pos = Data::GrowsAtBeginning;
-        DataPointer oldData;
-        this->detachAndGrow(pos, n, &oldData);
-        Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
-                 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
-
-        T *where = this->begin() + i;
-        if (pos == QArrayData::GrowsAtBeginning)
-            Base::insert(GrowsBackwardsTag{}, where, data, data + n);
-        else
-            Base::insert(GrowsForwardTag{}, where, data, data + n);
-    }
-
     template<typename... Args>
     void emplace(qsizetype i, Args &&... args)
     {
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index 1aa9a670e7..763a5f7927 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -282,11 +282,8 @@ public:
         return lhs.data() != rhs.data() || lhs.size != rhs.size;
     }
 
-protected:
     Data *d;
     T *ptr;
-
-public:
     qsizetype size;
 };