summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorThiago Macieira <thiago.macieira@intel.com>2019-10-25 10:05:15 +0200
committerLars Knoll <lars.knoll@qt.io>2019-12-08 10:29:56 +0100
commit4802f96d4d5b2bea62073295edde1eaa348033db (patch)
treea804f4b7fb06c3f24d86729bce2ff7e2221411d3 /src
parent443aaa6dec4b22dc57d19353e33a0f66437fb450 (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.h282
-rw-r--r--src/corelib/tools/qarraydatapointer.h109
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);
}