Simplify QArrayDataOps::insert() for movable types

Avoid ever having to call a destructor and unify the code for
insertion at the front or at the end.

Change-Id: Ie50ae2d4a75477cfdae9d5bd4bddf268426d95b5
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

1 files changed, 79 insertions, 146 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index fe81e66a82..028d63efc2 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -76,50 +76,6 @@ struct QArrayExceptionSafetyPrimitives
     using parameter_type = typename QArrayDataPointer<T>::parameter_type;
     using iterator = typename QArrayDataPointer<T>::iterator;
 
-    // Constructs a range of elements at the specified position. If an exception
-    // is thrown during construction, already constructed elements are
-    // destroyed. By design, only one function (create/copy/clone/move) and only
-    // once is supposed to be called per class instance.
-    struct Constructor
-    {
-        T *const where;
-        size_t n = 0;
-
-        Constructor(T *w) noexcept : where(w) {}
-        qsizetype create(size_t size) noexcept(std::is_nothrow_default_constructible_v<T>)
-        {
-            n = 0;
-            while (n != size) {
-                new (where + n) T;
-                ++n;
-            }
-            return qsizetype(std::exchange(n, 0));
-        }
-        qsizetype copy(const T *first, const T *last) noexcept(std::is_nothrow_copy_constructible_v<T>)
-        {
-            n = 0;
-            for (; first != last; ++first) {
-                new (where + n) T(*first);
-                ++n;
-            }
-            return qsizetype(std::exchange(n, 0));
-        }
-        qsizetype clone(size_t size, parameter_type t) noexcept(std::is_nothrow_constructible_v<T, parameter_type>)
-        {
-            n = 0;
-            while (n != size) {
-                new (where + n) T(t);
-                ++n;
-            }
-            return qsizetype(std::exchange(n, 0));
-        }
-        ~Constructor() noexcept(std::is_nothrow_destructible_v<T>)
-        {
-            while (n)
-                where[--n].~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.
@@ -141,9 +97,10 @@ struct QArrayExceptionSafetyPrimitives
         void commit() noexcept { displace = 0; }
         ~Displacer() noexcept
         {
-            if (displace)
-                ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
-                          (end - begin) * sizeof(T));
+            if constexpr (!std::is_nothrow_copy_constructible_v<T>)
+                if (displace)
+                    ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
+                              (end - begin) * sizeof(T));
         }
     };
 };
@@ -829,66 +786,90 @@ public:
     // using QGenericArrayOps<T>::destroyAll;
     typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
 
-    void insert(qsizetype i, const T *data, qsizetype n)
+    struct Inserter
     {
-        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));
+        QArrayDataPointer<T> *data;
+        T *displaceFrom;
+        T *displaceTo;
+        qsizetype nInserts = 0;
+        qsizetype bytes;
 
-        T *where = this->begin() + i;
-        if (pos == QArrayData::GrowsAtBeginning)
-            insert(GrowsBackwardsTag{}, where, data, data + n);
-        else
-            insert(GrowsForwardTag{}, where, data, data + n);
-    }
+        qsizetype increment = 1;
 
-    void insert(GrowsForwardTag, 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->freeSpaceAtEnd());
+        Inserter(QArrayDataPointer<T> *d, QArrayData::GrowthPosition pos)
+            : data(d), increment(pos == QArrayData::GrowsAtBeginning ? -1 : 1)
+        {
+        }
+        ~Inserter() {
+            if constexpr (!std::is_nothrow_copy_constructible_v<T>) {
+                if (displaceFrom != displaceTo) {
+                    ::memmove(static_cast<void *>(displaceFrom), static_cast<void *>(displaceTo), bytes);
+                    nInserts -= qAbs(displaceFrom - displaceTo);
+                }
+            }
+            if (increment < 0)
+                data->ptr -= nInserts;
+            data->size += nInserts;
+        }
+
+        T *displace(qsizetype pos, qsizetype n)
+        {
+            nInserts = n;
+            T *insertionPoint = data->ptr + pos;
+            if (increment > 0) {
+                displaceFrom = data->ptr + pos;
+                displaceTo = displaceFrom + n;
+                bytes = data->size - pos;
+            } else {
+                displaceFrom = data->ptr;
+                displaceTo = displaceFrom - n;
+                --insertionPoint;
+                bytes = pos;
+            }
+            bytes *= sizeof(T);
+            ::memmove(static_cast<void *>(displaceTo), static_cast<void *>(displaceFrom), bytes);
+            return insertionPoint;
+        }
 
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
+        void insert(qsizetype pos, const T *source, qsizetype n)
+        {
+            T *where = displace(pos, n);
 
-        // Provides strong exception safety guarantee,
-        // provided T::~T() nothrow
+            if (increment < 0)
+                source += n - 1;
 
-        ReversibleDisplace displace(where, this->end(), e - b);
-        CopyConstructor copier(where);
-        const auto copiedSize = copier.copy(b, e);
-        displace.commit();
-        this->size += copiedSize;
-    }
+            while (n--) {
+                new (where) T(*source);
+                where += increment;
+                source += increment;
+                displaceFrom += increment;
+            }
+        }
 
-    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());
+        void insert(qsizetype pos, const T &t, qsizetype n)
+        {
+            T *where = displace(pos, n);
+
+            while (n--) {
+                new (where) T(t);
+                where += increment;
+                displaceFrom += increment;
+            }
+        }
+    };
 
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
 
-        // Provides strong exception safety guarantee,
-        // provided T::~T() nothrow
+    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));
 
-        ReversibleDisplace displace(this->begin(), where, -(e - b));
-        CopyConstructor copier(where - (e - b));
-        const auto copiedSize = copier.copy(b, e);
-        displace.commit();
-        this->ptr -= copiedSize;
-        this->size += copiedSize;
+        Inserter(this, pos).insert(i, data, n);
     }
 
     void insert(qsizetype i, qsizetype n, parameter_type t)
@@ -902,57 +883,9 @@ public:
         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());
-        Q_ASSERT(n);
-        Q_ASSERT(where >= this->begin() && where <= this->end());
-        Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
-
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
-
-        // Provides strong exception safety guarantee,
-        // provided T::~T() nothrow
-
-        ReversibleDisplace displace(where, this->end(), qsizetype(n));
-        CopyConstructor copier(where);
-        const auto copiedSize = copier.clone(n, t);
-        displace.commit();
-        this->size += copiedSize;
-    }
-
-    void insert(GrowsBackwardsTag, 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->freeSpaceAtBegin()) >= n);
-
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
-        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
-
-        // Provides strong exception safety guarantee,
-        // provided T::~T() nothrow
-
-        ReversibleDisplace displace(this->begin(), where, -qsizetype(n));
-        CopyConstructor copier(where - n);
-        const auto copiedSize = copier.clone(n, t);
-        displace.commit();
-        this->ptr -= copiedSize;
-        this->size += copiedSize;
+        Inserter(this, pos).insert(i, copy, n);
     }
 
-    // use moving insert
-    using QGenericArrayOps<T>::insert;
-
     template<typename... Args>
     void emplace(GrowsForwardTag, T *where, Args &&... args)
     {