diff options
Diffstat (limited to 'src/corelib/tools/qarraydataops.h')
-rw-r--r-- | src/corelib/tools/qarraydataops.h | 413 |
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> |