1 files changed, 369 insertions, 44 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 8e19525f07..0d2be5d51c 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -1,6 +1,7 @@
 /****************************************************************************
 **
 ** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2016 Intel Corporation.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the QtCore module of the Qt Toolkit.
@@ -41,12 +42,15 @@
 #define QARRAYDATAOPS_H
 
 #include <QtCore/qarraydata.h>
+#include <QtCore/qcontainertools_impl.h>
 
 #include <new>
 #include <string.h>
 
 QT_BEGIN_NAMESPACE
 
+template <class T> struct QArrayDataPointer;
+
 namespace QtPrivate {
 
 QT_WARNING_PUSH
@@ -56,48 +60,67 @@ QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
 
 template <class T>
 struct QPodArrayOps
-    : QTypedArrayData<T>
+        : public QArrayDataPointer<T>
 {
+    typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
+
     void appendInitialize(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(newSize > uint(this->size));
-        Q_ASSERT(newSize <= this->alloc);
+        Q_ASSERT(newSize <= this->allocatedCapacity());
 
         ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T));
         this->size = int(newSize);
     }
 
+    template<typename iterator>
+    void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true)
+    {
+        Q_ASSERT(this->isMutable() || b == e);
+        Q_ASSERT(!this->isShared() || b == e);
+        Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
+
+        T *iter = this->end();
+        for (; b != e; ++iter, ++b) {
+            new (iter) T(*b);
+            ++this->size;
+        }
+    }
+
     void copyAppend(const T *b, const T *e)
     {
-        Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
-        Q_ASSERT(b < e);
-        Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+        Q_ASSERT(this->isMutable() || b == e);
+        Q_ASSERT(!this->isShared() || b == e);
+        Q_ASSERT(b <= e);
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
         ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b),
                  (e - b) * sizeof(T));
         this->size += e - b;
     }
 
-    void copyAppend(size_t n, const T &t)
+    void moveAppend(T *b, T *e)
+    { copyAppend(b, e); }
+
+    void copyAppend(size_t n, parameter_type t)
     {
-        Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
-        Q_ASSERT(n <= this->alloc - uint(this->size));
+        Q_ASSERT(this->isMutable() || n == 0);
+        Q_ASSERT(!this->isShared() || n == 0);
+        Q_ASSERT(n <= uint(this->allocatedCapacity() - this->size));
 
         T *iter = this->end();
         const T *const end = iter + n;
         for (; iter != end; ++iter)
-            ::memcpy(iter, &t, sizeof(T));
+            *iter = t;
         this->size += int(n);
     }
 
     void truncate(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(newSize < size_t(this->size));
 
         this->size = int(newSize);
@@ -106,7 +129,7 @@ struct QPodArrayOps
     void destroyAll() // Call from destructors, ONLY!
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
+        Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
 
         // As this is to be called only from destructor, it doesn't need to be
         // exception safe; size not updated.
@@ -115,11 +138,11 @@ struct QPodArrayOps
     void insert(T *where, const T *b, const T *e)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
-        Q_ASSERT(b < e);
+        Q_ASSERT(b <= e);
         Q_ASSERT(e <= where || b > this->end()); // No overlap
-        Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
         ::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where),
                   (static_cast<const T*>(this->end()) - where) * sizeof(T));
@@ -127,43 +150,97 @@ struct QPodArrayOps
         this->size += (e - b);
     }
 
+    void insert(T *where, size_t n, parameter_type t)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
+        Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+        ::memmove(static_cast<void *>(where + n), static_cast<void *>(where),
+                  (static_cast<const T*>(this->end()) - where) * sizeof(T));
+        this->size += int(n); // PODs can't throw on copy
+        while (n--)
+            *where++ = t;
+    }
+
+    void insert(T *where, T &&t)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
+
+        ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where),
+                  (static_cast<const T*>(this->end()) - where) * sizeof(T));
+        this->size += 1;
+        new (where) T(std::move(t));
+    }
+
+
     void erase(T *b, T *e)
     {
         Q_ASSERT(this->isMutable());
         Q_ASSERT(b < e);
         Q_ASSERT(b >= this->begin() && b < this->end());
-        Q_ASSERT(e > this->begin() && e < this->end());
+        Q_ASSERT(e > this->begin() && e <= this->end());
 
         ::memmove(static_cast<void *>(b), static_cast<void *>(e),
                   (static_cast<T *>(this->end()) - e) * sizeof(T));
         this->size -= (e - b);
     }
+
+    void assign(T *b, T *e, parameter_type t)
+    {
+        Q_ASSERT(b <= e);
+        Q_ASSERT(b >= this->begin() && e <= this->end());
+
+        while (b != e)
+            ::memcpy(static_cast<void *>(b++), static_cast<const void *>(&t), sizeof(T));
+    }
+
+    bool compare(const T *begin1, const T *begin2, size_t n) const
+    {
+        // only use memcmp for fundamental types or pointers.
+        // Other types could have padding in the data structure or custom comparison
+        // operators that would break the comparison using memcmp
+        if (QArrayDataPointer<T>::pass_parameter_by_value)
+            return ::memcmp(begin1, begin2, n * sizeof(T)) == 0;
+        const T *end1 = begin1 + n;
+        while (begin1 != end1) {
+            if (*begin1 == *begin2)
+                ++begin1, ++begin2;
+            else
+                return false;
+        }
+        return true;
+    }
 };
 QT_WARNING_POP
 
 template <class T>
 struct QGenericArrayOps
-    : QTypedArrayData<T>
+        : public QArrayDataPointer<T>
 {
+    typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
+
     void appendInitialize(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(newSize > uint(this->size));
-        Q_ASSERT(newSize <= this->alloc);
+        Q_ASSERT(newSize <= this->allocatedCapacity());
 
-        T *const begin = this->begin();
+        T *const b = this->begin();
         do {
-            new (begin + this->size) T;
+            new (b + this->size) T;
         } while (uint(++this->size) != newSize);
     }
 
-    void copyAppend(const T *b, const T *e)
+    template<typename iterator>
+    void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true)
     {
-        Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
-        Q_ASSERT(b < e);
-        Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+        Q_ASSERT(this->isMutable() || b == e);
+        Q_ASSERT(!this->isShared() || b == e);
+        Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
 
         T *iter = this->end();
         for (; b != e; ++iter, ++b) {
@@ -172,11 +249,37 @@ struct QGenericArrayOps
         }
     }
 
-    void copyAppend(size_t n, const T &t)
+    void copyAppend(const T *b, const T *e)
     {
-        Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
-        Q_ASSERT(n <= this->alloc - uint(this->size));
+        Q_ASSERT(this->isMutable() || b == e);
+        Q_ASSERT(!this->isShared() || b == e);
+        Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size);
+
+        T *iter = this->end();
+        this->size += e - b;
+        for (; b != e; ++iter, ++b)
+            new (iter) T(*b);
+    }
+
+    void moveAppend(T *b, T *e)
+    {
+        Q_ASSERT(this->isMutable() || b == e);
+        Q_ASSERT(!this->isShared() || b == e);
+        Q_ASSERT(b <= e);
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
+
+        T *iter = this->end();
+        for (; b != e; ++iter, ++b) {
+            new (iter) T(std::move(*b));
+            ++this->size;
+        }
+    }
+
+    void copyAppend(size_t n, parameter_type t)
+    {
+        Q_ASSERT(this->isMutable() || n == 0);
+        Q_ASSERT(!this->isShared() || n == 0);
+        Q_ASSERT(n <= size_t(this->allocatedCapacity() - this->size));
 
         T *iter = this->end();
         const T *const end = iter + n;
@@ -189,7 +292,7 @@ struct QGenericArrayOps
     void truncate(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(newSize < size_t(this->size));
 
         const T *const b = this->begin();
@@ -204,7 +307,7 @@ struct QGenericArrayOps
         // As this is to be called only from destructor, it doesn't need to be
         // exception safe; size not updated.
 
-        Q_ASSERT(this->ref.atomic.loadRelaxed() == 0);
+        Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
 
         const T *const b = this->begin();
         const T *i = this->end();
@@ -216,11 +319,11 @@ struct QGenericArrayOps
     void insert(T *where, const T *b, const T *e)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
-        Q_ASSERT(b < e);
+        Q_ASSERT(b <= e);
         Q_ASSERT(e <= where || b > this->end()); // No overlap
-        Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
         // Array may be truncated at where in case of exceptions
 
@@ -279,25 +382,139 @@ struct QGenericArrayOps
         }
     }
 
+    void insert(T *where, size_t n, parameter_type t)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+        // Array may be truncated at where in case of exceptions
+        T *const end = this->end();
+        const T *readIter = end;
+        T *writeIter = end + n;
+
+        const T *const step1End = where + qMax<size_t>(n, end - where);
+
+        struct Destructor
+        {
+            Destructor(T *&it)
+                : iter(&it)
+                , end(it)
+            {
+            }
+
+            void commit()
+            {
+                iter = &end;
+            }
+
+            ~Destructor()
+            {
+                for (; *iter != end; --*iter)
+                    (*iter)->~T();
+            }
+
+            T **iter;
+            T *end;
+        } destroyer(writeIter);
+
+        // Construct new elements in array
+        do {
+            --readIter, --writeIter;
+            new (writeIter) T(*readIter);
+        } while (writeIter != step1End);
+
+        while (writeIter != end) {
+            --n, --writeIter;
+            new (writeIter) T(t);
+        }
+
+        destroyer.commit();
+        this->size += destroyer.end - end;
+
+        // Copy assign over existing elements
+        while (readIter != where) {
+            --readIter, --writeIter;
+            *writeIter = *readIter;
+        }
+
+        while (writeIter != where) {
+            --n, --writeIter;
+            *writeIter = t;
+        }
+    }
+
+    void insert(T *where, T &&t)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
+
+        // Array may be truncated at where in case of exceptions
+        T *const end = this->end();
+
+        if (where != end) {
+            // Move elements in array
+            T *readIter = end - 1;
+            T *writeIter = end;
+            new (writeIter) T(std::move(*readIter));
+            while (readIter > where) {
+                --readIter;
+                --writeIter;
+                *writeIter = std::move(*readIter);
+            }
+            *where = std::move(t);
+        } else {
+            new (where) T(std::move(t));
+        }
+
+        ++this->size;
+    }
+
     void erase(T *b, T *e)
     {
         Q_ASSERT(this->isMutable());
         Q_ASSERT(b < e);
         Q_ASSERT(b >= this->begin() && b < this->end());
-        Q_ASSERT(e > this->begin() && e < this->end());
+        Q_ASSERT(e > this->begin() && e <= this->end());
 
         const T *const end = this->end();
 
-        do {
+        // move (by assignment) the elements from e to end
+        // onto b to the new end
+        while (e != end) {
             *b = *e;
             ++b, ++e;
-        } while (e != end);
+        }
 
+        // destroy the final elements at the end
+        // here, b points to the new end and e to the actual end
         do {
             (--e)->~T();
             --this->size;
         } while (e != b);
     }
+
+    void assign(T *b, T *e, parameter_type t)
+    {
+        Q_ASSERT(b <= e);
+        Q_ASSERT(b >= this->begin() && e <= this->end());
+
+        while (b != e)
+            *b++ = t;
+    }
+
+    bool compare(const T *begin1, const T *begin2, size_t n) const
+    {
+        const T *end1 = begin1 + n;
+        while (begin1 != end1) {
+            if (*begin1 == *begin2)
+                ++begin1, ++begin2;
+            else
+                return false;
+        }
+        return true;
+    }
 };
 
 template <class T>
@@ -308,15 +525,16 @@ struct QMovableArrayOps
     // using QGenericArrayOps<T>::copyAppend;
     // using QGenericArrayOps<T>::truncate;
     // using QGenericArrayOps<T>::destroyAll;
+    typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
 
     void insert(T *where, const T *b, const T *e)
     {
         Q_ASSERT(this->isMutable());
-        Q_ASSERT(!this->ref.isShared());
+        Q_ASSERT(!this->isShared());
         Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end
-        Q_ASSERT(b < e);
+        Q_ASSERT(b <= e);
         Q_ASSERT(e <= where || b > this->end()); // No overlap
-        Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size));
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
         // Provides strong exception safety guarantee,
         // provided T::~T() nothrow
@@ -376,12 +594,79 @@ struct QMovableArrayOps
         this->size += (e - b);
     }
 
+    void insert(T *where, size_t n, parameter_type t)
+    {
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(where >= this->begin() && where <= this->end());
+        Q_ASSERT(this->allocatedCapacity() - this->size >= n);
+
+        // Provides strong exception safety guarantee,
+        // provided T::~T() nothrow
+
+        struct ReversibleDisplace
+        {
+            ReversibleDisplace(T *start, T *finish, size_t diff)
+                : begin(start)
+                , end(finish)
+                , displace(diff)
+            {
+                ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
+                          (end - begin) * sizeof(T));
+            }
+
+            void commit() { displace = 0; }
+
+            ~ReversibleDisplace()
+            {
+                if (displace)
+                    ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
+                              (end - begin) * sizeof(T));
+            }
+
+            T *const begin;
+            T *const end;
+            size_t displace;
+
+        } displace(where, this->end(), n);
+
+        struct CopyConstructor
+        {
+            CopyConstructor(T *w) : where(w) {}
+
+            void copy(size_t count, parameter_type proto)
+            {
+                n = 0;
+                while (count--) {
+                    new (where + n) T(proto);
+                    ++n;
+                }
+                n = 0;
+            }
+
+            ~CopyConstructor()
+            {
+                while (n)
+                    where[--n].~T();
+            }
+
+            T *const where;
+            size_t n;
+        } copier(where);
+
+        copier.copy(n, t);
+        displace.commit();
+        this->size += int(n);
+    }
+
+    // use moving insert
+    using QGenericArrayOps<T>::insert;
+
     void erase(T *b, T *e)
     {
         Q_ASSERT(this->isMutable());
         Q_ASSERT(b < e);
         Q_ASSERT(b >= this->begin() && b < this->end());
-        Q_ASSERT(e > this->begin() && e < this->end());
+        Q_ASSERT(e > this->begin() && e <= this->end());
 
         struct Mover
         {
@@ -405,11 +690,51 @@ struct QMovableArrayOps
             int &size;
         } mover(e, this->end(), this->size);
 
+        // destroy the elements we're erasing
         do {
             // Exceptions or not, dtor called once per instance
             (--e)->~T();
         } while (e != b);
     }
+
+    void moveAppend(T *b, T *e)
+    {
+        Q_ASSERT(this->isMutable());
+        Q_ASSERT(!this->isShared());
+        Q_ASSERT(b <= e);
+        Q_ASSERT(e <= this->begin() || b > this->end()); // No overlap
+        Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
+
+        // Provides strong exception safety guarantee,
+        // provided T::~T() nothrow
+
+        struct CopyConstructor
+        {
+            CopyConstructor(T *w) : where(w) {}
+
+            void copy(T *src, const T *const srcEnd)
+            {
+                n = 0;
+                for (; src != srcEnd; ++src) {
+                    new (where + n) T(std::move(*src));
+                    ++n;
+                }
+                n = 0;
+            }
+
+            ~CopyConstructor()
+            {
+                while (n)
+                    where[--n].~T();
+            }
+
+            T *const where;
+            size_t n;
+        } copier(this->end());
+
+        copier.copy(b, e);
+        this->size += (e - b);
+    }
 };
 
 template <class T, class = void>