diff options
| author | Thiago Macieira <thiago.macieira@intel.com> | 2019-10-25 10:05:15 +0200 |
|---|---|---|
| committer | Lars Knoll <lars.knoll@qt.io> | 2019-12-08 10:29:56 +0100 |
| commit | 4802f96d4d5b2bea62073295edde1eaa348033db (patch) | |
| tree | a804f4b7fb06c3f24d86729bce2ff7e2221411d3 /src | |
| parent | 443aaa6dec4b22dc57d19353e33a0f66437fb450 (diff) | |
Various cleanups in qarraydataops and qarraydatapointer
Various cleanups. Add copyAppend overload for forward iterators and a
insert overload for inserting n elements.
Change-Id: Ic41cd20818b8307e957948d04ef6379368defa55
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
Diffstat (limited to 'src')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 282 | ||||
| -rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 109 |
2 files changed, 304 insertions, 87 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 8fe35952bfe..dbd535fa3e5 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,6 +42,7 @@ #define QARRAYDATAOPS_H #include <QtCore/qarraydata.h> +#include <QtCore/qcontainertools_impl.h> #include <new> #include <string.h> @@ -73,12 +75,26 @@ struct QPodArrayOps 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->isShared()); - Q_ASSERT(b < e); - Q_ASSERT(e - b <= this->allocatedCapacity() - 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)); @@ -90,8 +106,8 @@ struct QPodArrayOps void copyAppend(size_t n, parameter_type t) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->isShared()); + Q_ASSERT(this->isMutable() || n == 0); + Q_ASSERT(!this->isShared() || n == 0); Q_ASSERT(n <= uint(this->allocatedCapacity() - this->size)); T *iter = this->end(); @@ -113,7 +129,7 @@ struct QPodArrayOps void destroyAll() // Call from destructors, ONLY! { Q_ASSERT(this->isMutable()); - Q_ASSERT(this->ref_.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. @@ -124,9 +140,9 @@ struct QPodArrayOps Q_ASSERT(this->isMutable()); 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(e - b <= this->allocatedCapacity() - 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)); @@ -134,17 +150,56 @@ struct QPodArrayOps this->size += (e - b); } + void insert(T *where, size_t n, T 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 += n; // PODs can't throw on copy + while (n--) + *where++ = 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 @@ -161,18 +216,18 @@ struct QGenericArrayOps Q_ASSERT(newSize > uint(this->size)); 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->isShared()); - Q_ASSERT(b < e); - Q_ASSERT(e - b <= this->allocatedCapacity() - 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) { @@ -181,6 +236,18 @@ struct QGenericArrayOps } } + void copyAppend(const T *b, const T *e) + { + 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); @@ -197,8 +264,8 @@ struct QGenericArrayOps void copyAppend(size_t n, parameter_type t) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->isShared()); + 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(); @@ -227,7 +294,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_.loadRelaxed() == 0); + Q_ASSERT(this->d->ref_.loadRelaxed() == 0); const T *const b = this->begin(); const T *i = this->end(); @@ -241,9 +308,9 @@ struct QGenericArrayOps Q_ASSERT(this->isMutable()); 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(e - b <= this->allocatedCapacity() - this->size); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); // Array may be truncated at where in case of exceptions @@ -302,25 +369,112 @@ struct QGenericArrayOps } } + void insert(T *where, size_t n, T 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 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> @@ -331,15 +485,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->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(e - b <= this->allocatedCapacity() - this->size); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); // Provides strong exception safety guarantee, // provided T::~T() nothrow @@ -399,16 +554,80 @@ struct QMovableArrayOps this->size += (e - b); } + void insert(T *where, size_t n, T 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 += n; + } + 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 { - Mover(T *&start, const T *finish, int &sz) + Mover(T *&start, const T *finish, uint &sz) : destination(start) , source(start) , n(finish - start) @@ -425,9 +644,10 @@ struct QMovableArrayOps T *&destination; const T *const source; size_t n; - int &size; + uint &size; } mover(e, this->end(), this->size); + // destroy the elements we're erasing do { // Exceptions or not, dtor called once per instance (--e)->~T(); @@ -449,7 +669,7 @@ struct QMovableArrayOps { CopyConstructor(T *w) : where(w) {} - void copy(const T *src, const T *const srcEnd) + void copy(T *src, const T *const srcEnd) { n = 0; for (; src != srcEnd; ++src) { diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index c52b84f4ce1..9103064bd90 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -41,6 +41,7 @@ #define QARRAYDATAPOINTER_H #include <QtCore/qarraydataops.h> +#include <QtCore/qcontainertools_impl.h> QT_BEGIN_NAMESPACE @@ -56,38 +57,33 @@ public: typedef typename Data::const_iterator const_iterator; QArrayDataPointer() noexcept - : d(Data::sharedNull()), b(Data::sharedNullData()), size(0) + : d(Data::sharedNull()), ptr(Data::sharedNullData()), size(0) { } - QArrayDataPointer(const QArrayDataPointer &other) - : d(other.d), b(other.b), size(other.size) + QArrayDataPointer(const QArrayDataPointer &other) noexcept + : d(other.d), ptr(other.ptr), size(other.size) { - if (!other.d->ref()) { - // must clone - QPair<Data *, T *> pair = other.clone(other.d->cloneFlags()); - d = pair.first; - b = pair.second; - } + other.d->ref(); } - QArrayDataPointer(Data *header, T *data, size_t n = 0) - : d(header), b(data), size(n) + QArrayDataPointer(Data *header, T *adata, size_t n = 0) noexcept + : d(header), ptr(adata), size(n) { } - explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> data, size_t n = 0) - : d(data.first), b(data.second), size(n) + explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, size_t n = 0) + : d(adata.first), ptr(adata.second), size(n) { Q_CHECK_PTR(d); } - QArrayDataPointer(QArrayDataPointerRef<T> ref) - : d(ref.ptr), b(ref.data), size(ref.size) + QArrayDataPointer(QArrayDataPointerRef<T> dd) noexcept + : d(dd.ptr), ptr(dd.data), size(dd.size) { } - QArrayDataPointer &operator=(const QArrayDataPointer &other) + QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept { QArrayDataPointer tmp(other); this->swap(tmp); @@ -95,9 +91,11 @@ public: } QArrayDataPointer(QArrayDataPointer &&other) noexcept - : d(other.d), b(other.b), size(other.size) + : d(other.d), ptr(other.ptr), size(other.size) { other.d = Data::sharedNull(); + other.ptr = Data::sharedNullData(); + other.size = 0; } QArrayDataPointer &operator=(QArrayDataPointer &&other) noexcept @@ -107,25 +105,25 @@ public: return *this; } - DataOps &operator*() + DataOps &operator*() noexcept { Q_ASSERT(d); return *static_cast<DataOps *>(this); } - DataOps *operator->() + DataOps *operator->() noexcept { Q_ASSERT(d); return static_cast<DataOps *>(this); } - const DataOps &operator*() const + const DataOps &operator*() const noexcept { Q_ASSERT(d); return *static_cast<const DataOps *>(this); } - const DataOps *operator->() const + const DataOps *operator->() const noexcept { Q_ASSERT(d); return static_cast<const DataOps *>(this); @@ -140,43 +138,41 @@ public: } } - bool isNull() const + bool isNull() const noexcept { return d == Data::sharedNull(); } - T *data() { return b; } - const T *data() const { return b; } + T *data() noexcept { return ptr; } + const T *data() const noexcept { return ptr; } - iterator begin() { return data(); } - iterator end() { return data() + size; } - const_iterator begin() const { return data(); } - const_iterator end() const { return data() + size; } - const_iterator constBegin() const { return data(); } - const_iterator constEnd() const { return data() + size; } + iterator begin(iterator = iterator()) noexcept { return data(); } + iterator end(iterator = iterator()) noexcept { return data() + size; } + const_iterator begin(const_iterator = const_iterator()) const noexcept { return data(); } + const_iterator end(const_iterator = const_iterator()) const noexcept { return data() + size; } + const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return data(); } + const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return data() + size; } void swap(QArrayDataPointer &other) noexcept { qSwap(d, other.d); - qSwap(b, other.b); + qSwap(ptr, other.ptr); qSwap(size, other.size); } - void clear() + void clear() Q_DECL_NOEXCEPT_EXPR(std::is_nothrow_destructible<T>::value) { - QArrayDataPointer tmp(d, b, size); - d = Data::sharedNull(); - b = reinterpret_cast<T *>(d); - size = 0; + QArrayDataPointer tmp; + swap(tmp); } bool detach() { if (d->needsDetach()) { QPair<Data *, T *> copy = clone(d->detachFlags()); - QArrayDataPointer old(d, b, size); + QArrayDataPointer old(d, ptr, size); d = copy.first; - b = copy.second; + ptr = copy.second; return true; } @@ -184,20 +180,20 @@ public: } // forwards from QArrayData - int allocatedCapacity() { return d->allocatedCapacity(); } - int constAllocatedCapacity() const { return d->constAllocatedCapacity(); } - int refCounterValue() const { return d->refCounterValue(); } - bool ref() { return d->ref(); } - bool deref() { return d->deref(); } - bool isMutable() const { return d->isMutable(); } - bool isStatic() const { return d->isStatic(); } - bool isShared() const { return d->isShared(); } - bool needsDetach() const { return d->needsDetach(); } - size_t detachCapacity(size_t newSize) const { return d->detachCapacity(newSize); } - typename Data::ArrayOptions &flags() { return reinterpret_cast<typename Data::ArrayOptions &>(d->flags); } - typename Data::ArrayOptions flags() const { return typename Data::ArrayOption(d->flags); } - typename Data::ArrayOptions detachFlags() const { return d->detachFlags(); } - typename Data::ArrayOptions cloneFlags() const { return d->cloneFlags(); } + size_t allocatedCapacity() noexcept { return d->allocatedCapacity(); } + size_t constAllocatedCapacity() const noexcept { return d->constAllocatedCapacity(); } + int refCounterValue() const noexcept { return d->refCounterValue(); } + bool ref() noexcept { return d->ref(); } + bool deref() noexcept { return d->deref(); } + bool isMutable() const noexcept { return d->isMutable(); } + bool isStatic() const noexcept { return d->isStatic(); } + bool isShared() const noexcept { return d->isShared(); } + bool needsDetach() const noexcept { return d->needsDetach(); } + size_t detachCapacity(size_t newSize) const noexcept { return d->detachCapacity(newSize); } + typename Data::ArrayOptions &flags() noexcept { return reinterpret_cast<typename Data::ArrayOptions &>(d->flags); } + typename Data::ArrayOptions flags() const noexcept { return typename Data::ArrayOption(d->flags); } + typename Data::ArrayOptions detachFlags() const noexcept { return d->detachFlags(); } + typename Data::ArrayOptions cloneFlags() const noexcept { return d->cloneFlags(); } private: Q_REQUIRED_RESULT QPair<Data *, T *> clone(QArrayData::ArrayOptions options) const @@ -214,27 +210,28 @@ private: return pair; } +protected: Data *d; - T *b; + T *ptr; public: uint size; }; template <class T> -inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) +inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept { return lhs.data() == rhs.data() && lhs.size == rhs.size; } template <class T> -inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) +inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept { return lhs.data() != rhs.data() || lhs.size != rhs.size; } template <class T> -inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) +inline void qSwap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept { p1.swap(p2); } |
