diff options
Diffstat (limited to 'src/corelib/tools/qarraydataops.h')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 1192 |
1 files changed, 696 insertions, 496 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index a97f2da175..c3e9821e81 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1,51 +1,21 @@ -/**************************************************************************** -** -** 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. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2020 The Qt Company Ltd. +// Copyright (C) 2016 Intel Corporation. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only #ifndef QARRAYDATAOPS_H #define QARRAYDATAOPS_H #include <QtCore/qarraydata.h> #include <QtCore/qcontainertools_impl.h> +#include <QtCore/qnamespace.h> +#include <memory> #include <new> #include <string.h> +#include <utility> +#include <iterator> +#include <tuple> +#include <type_traits> QT_BEGIN_NAMESPACE @@ -53,86 +23,77 @@ template <class T> struct QArrayDataPointer; namespace QtPrivate { -QT_WARNING_PUSH -#if defined(Q_CC_GNU) && Q_CC_GNU >= 700 -QT_WARNING_DISABLE_GCC("-Wstringop-overflow") -#endif - template <class T> struct QPodArrayOps : public QArrayDataPointer<T> { -private: + static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + +protected: typedef QTypedArrayData<T> Data; + using DataPointer = QArrayDataPointer<T>; + public: typedef typename QArrayDataPointer<T>::parameter_type parameter_type; - void appendInitialize(size_t newSize) + using QArrayDataPointer<T>::QArrayDataPointer; + + void appendInitialize(qsizetype newSize) noexcept { Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); - Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->allocatedCapacity()); - - ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T)); - this->size = int(newSize); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); + + T *where = this->end(); + this->size = newSize; + const T *e = this->end(); + while (where != e) + *where++ = T(); } - 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) + void copyAppend(const T *b, const T *e) noexcept { 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); + Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); - ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b), - (e - b) * sizeof(T)); - this->size += e - b; - } + if (b == e) + return; - void moveAppend(T *b, T *e) - { copyAppend(b, e); } + ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b), (e - b) * sizeof(T)); + this->size += (e - b); + } - void copyAppend(size_t n, parameter_type t) + void copyAppend(qsizetype n, parameter_type t) noexcept { - Q_ASSERT(this->isMutable() || n == 0); Q_ASSERT(!this->isShared() || n == 0); - Q_ASSERT(n <= uint(this->allocatedCapacity() - this->size)); + Q_ASSERT(this->freeSpaceAtEnd() >= n); + if (!n) + return; - T *iter = this->end(); - const T *const end = iter + n; - for (; iter != end; ++iter) - *iter = t; - this->size += int(n); + T *where = this->end(); + this->size += qsizetype(n); + while (n--) + *where++ = t; } - template <typename ...Args> - void emplaceBack(Args&&... args) { this->emplace(this->end(), T(std::forward<Args>(args)...)); } + void moveAppend(T *b, T *e) noexcept + { + copyAppend(b, e); + } - void truncate(size_t newSize) + void truncate(size_t newSize) noexcept { Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); Q_ASSERT(newSize < size_t(this->size)); - this->size = int(newSize); + this->size = qsizetype(newSize); } - void destroyAll() // Call from destructors, ONLY! + void destroyAll() noexcept // Call from destructors, ONLY! { Q_ASSERT(this->d); Q_ASSERT(this->d->ref_.loadRelaxed() == 0); @@ -141,72 +102,166 @@ public: // exception safe; size not updated. } - void insert(T *where, const T *b, const T *e) + T *createHole(QArrayData::GrowthPosition pos, qsizetype where, qsizetype n) { - 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(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); + Q_ASSERT((pos == QArrayData::GrowsAtBeginning && n <= this->freeSpaceAtBegin()) || + (pos == QArrayData::GrowsAtEnd && n <= this->freeSpaceAtEnd())); - ::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where), - (static_cast<const T*>(this->end()) - where) * sizeof(T)); - ::memcpy(static_cast<void *>(where), static_cast<const void *>(b), (e - b) * sizeof(T)); - this->size += (e - b); + T *insertionPoint = this->ptr + where; + if (pos == QArrayData::GrowsAtEnd) { + if (where < this->size) + ::memmove(static_cast<void *>(insertionPoint + n), static_cast<void *>(insertionPoint), (this->size - where) * sizeof(T)); + } else { + Q_ASSERT(where == 0); + this->ptr -= n; + insertionPoint -= n; + } + this->size += n; + return insertionPoint; } - void insert(T *where, size_t n, parameter_type t) + void insert(qsizetype i, const T *data, qsizetype n) { - Q_ASSERT(!this->isShared()); - Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end - Q_ASSERT(this->allocatedCapacity() - this->size >= n); + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; - ::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; - } + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - template <typename ...Args> - void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); } + T *where = createHole(pos, i, n); + ::memcpy(static_cast<void *>(where), static_cast<const void *>(data), n * sizeof(T)); + } - template <typename ...Args> - void emplace(T *where, Args&&... args) + void insert(qsizetype i, qsizetype n, parameter_type t) { - Q_ASSERT(!this->isShared()); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(this->allocatedCapacity() - this->size >= 1); + T copy(t); - if (where == this->end()) { - new (this->end()) T(std::forward<Args>(args)...); - } else { - // Preserve the value, because it might be a reference to some part of the moved chunk - T t(std::forward<Args>(args)...); + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; - ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where), - (static_cast<const T*>(this->end()) - where) * sizeof(T)); - *where = t; - } + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - ++this->size; + T *where = createHole(pos, i, n); + while (n--) + *where++ = copy; } + template<typename... Args> + void emplace(qsizetype i, Args &&... args) + { + bool detach = this->needsDetach(); + if (!detach) { + if (i == this->size && this->freeSpaceAtEnd()) { + new (this->end()) T(std::forward<Args>(args)...); + ++this->size; + return; + } + if (i == 0 && this->freeSpaceAtBegin()) { + new (this->begin() - 1) T(std::forward<Args>(args)...); + --this->ptr; + ++this->size; + return; + } + } + T tmp(std::forward<Args>(args)...); + typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = QArrayData::GrowsAtBeginning; + + this->detachAndGrow(pos, 1, nullptr, nullptr); + + T *where = createHole(pos, i, 1); + new (where) T(std::move(tmp)); + } - void erase(T *b, T *e) + void erase(T *b, qsizetype n) { + T *e = b + n; Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < 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); + // Comply with std::vector::erase(): erased elements and all after them + // are invalidated. However, erasing from the beginning effectively + // means that all iterators are invalidated. We can use this freedom to + // erase by moving towards the end. + if (b == this->begin() && e != this->end()) { + this->ptr = e; + } else if (e != this->end()) { + ::memmove(static_cast<void *>(b), static_cast<void *>(e), + (static_cast<T *>(this->end()) - e) * sizeof(T)); + } + this->size -= n; } - void assign(T *b, T *e, parameter_type t) + void eraseFirst() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + ++this->ptr; + --this->size; + } + + void eraseLast() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + --this->size; + } + + template <typename Predicate> + qsizetype eraseIf(Predicate pred) + { + qsizetype result = 0; + if (this->size == 0) + return result; + + if (!this->needsDetach()) { + auto end = this->end(); + auto it = std::remove_if(this->begin(), end, pred); + if (it != end) { + result = std::distance(it, end); + erase(it, result); + } + } else { + const auto begin = this->begin(); + const auto end = this->end(); + auto it = std::find_if(begin, end, pred); + if (it == end) + return result; + + QPodArrayOps<T> other(this->size); + Q_CHECK_PTR(other.data()); + auto dest = other.begin(); + // std::uninitialized_copy will fallback to ::memcpy/memmove() + dest = std::uninitialized_copy(begin, it, dest); + dest = q_uninitialized_remove_copy_if(std::next(it), end, dest, pred); + other.size = std::distance(other.data(), dest); + result = this->size - other.size; + this->swap(other); + } + return result; + } + + struct Span { T *begin; T *end; }; + + void copyRanges(std::initializer_list<Span> ranges) + { + auto it = this->begin(); + std::for_each(ranges.begin(), ranges.end(), [&it](const auto &span) { + it = std::copy(span.begin, span.end, it); + }); + this->size = std::distance(this->begin(), it); + } + + void assign(T *b, T *e, parameter_type t) noexcept { Q_ASSERT(b <= e); Q_ASSERT(b >= this->begin() && e <= this->end()); @@ -220,70 +275,88 @@ public: // 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) + if constexpr (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; + } else { + const T *end1 = begin1 + n; + while (begin1 != end1) { + if (*begin1 == *begin2) { + ++begin1; + ++begin2; + } else { + return false; + } + } + return true; } - return true; } - void reallocate(qsizetype alloc, typename Data::ArrayOptions options) + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) { - auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, options); + auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, option); + Q_CHECK_PTR(pair.second); + Q_ASSERT(pair.first != nullptr); this->d = pair.first; this->ptr = pair.second; } }; -QT_WARNING_POP template <class T> struct QGenericArrayOps : public QArrayDataPointer<T> { + static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + +protected: + typedef QTypedArrayData<T> Data; + using DataPointer = QArrayDataPointer<T>; + +public: typedef typename QArrayDataPointer<T>::parameter_type parameter_type; - void appendInitialize(size_t newSize) + void appendInitialize(qsizetype newSize) { Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); - Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->allocatedCapacity()); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); T *const b = this->begin(); do { new (b + this->size) T; - } while (uint(++this->size) != newSize); + } while (++this->size != newSize); } - template<typename iterator> - void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true) + 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); + Q_ASSERT(b <= e); + Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); + + if (b == e) // short-cut and handling the case b and e == nullptr + return; - T *iter = this->end(); - for (; b != e; ++iter, ++b) { - new (iter) T(*b); + T *data = this->begin(); + while (b < e) { + new (data + this->size) T(*b); + ++b; ++this->size; } } - void copyAppend(const T *b, const T *e) + void copyAppend(qsizetype n, parameter_type t) { - 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); + Q_ASSERT(!this->isShared() || n == 0); + Q_ASSERT(this->freeSpaceAtEnd() >= n); + if (!n) + return; - T *iter = this->end(); - this->size += e - b; - for (; b != e; ++iter, ++b) - new (iter) T(*b); + T *data = this->begin(); + while (n--) { + new (data + this->size) T(t); + ++this->size; + } } void moveAppend(T *b, T *e) @@ -291,45 +364,27 @@ struct QGenericArrayOps 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; - } - } + Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); - 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)); + if (b == e) + return; - T *iter = this->end(); - const T *const end = iter + n; - for (; iter != end; ++iter) { - new (iter) T(t); + T *data = this->begin(); + while (b < e) { + new (data + this->size) T(std::move(*b)); + ++b; ++this->size; } } - template <typename ...Args> - void emplaceBack(Args&&... args) - { - this->emplace(this->end(), std::forward<Args>(args)...); - } - void truncate(size_t newSize) { Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); Q_ASSERT(newSize < size_t(this->size)); - const T *const b = this->begin(); - do { - (b + --this->size)->~T(); - } while (uint(this->size) != newSize); + std::destroy(this->begin() + newSize, this->end()); + this->size = newSize; } void destroyAll() // Call from destructors, ONLY @@ -340,181 +395,264 @@ struct QGenericArrayOps Q_ASSERT(this->d->ref_.loadRelaxed() == 0); - const T *const b = this->begin(); - const T *i = this->end(); - - while (i != b) - (--i)->~T(); + std::destroy(this->begin(), this->end()); } - void insert(T *where, const T *b, const T *e) + struct Inserter { - 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(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); - - // Array may be truncated at where in case of exceptions - - T *const end = this->end(); - const T *readIter = end; - T *writeIter = end + (e - b); + QArrayDataPointer<T> *data; + T *begin; + qsizetype size; - const T *const step1End = where + qMax(e - b, end - where); + qsizetype sourceCopyConstruct = 0, nSource = 0, move = 0, sourceCopyAssign = 0; + T *end = nullptr, *last = nullptr, *where = nullptr; - struct Destructor + Inserter(QArrayDataPointer<T> *d) : data(d) { - Destructor(T *&it) - : iter(&it) - , end(it) - { - } - - void commit() - { - iter = &end; - } + begin = d->ptr; + size = d->size; + } + ~Inserter() { + data->ptr = begin; + data->size = size; + } + Q_DISABLE_COPY(Inserter) - ~Destructor() - { - for (; *iter != end; --*iter) - (*iter)->~T(); + void setup(qsizetype pos, qsizetype n) + { + end = begin + size; + last = end - 1; + where = begin + pos; + qsizetype dist = size - pos; + sourceCopyConstruct = 0; + nSource = n; + move = n - dist; // smaller 0 + sourceCopyAssign = n; + if (n > dist) { + sourceCopyConstruct = n - dist; + move = 0; + sourceCopyAssign -= sourceCopyConstruct; } - - T **iter; - T *end; - } destroyer(writeIter); - - // Construct new elements in array - do { - --readIter, --writeIter; - new (writeIter) T(*readIter); - } while (writeIter != step1End); - - while (writeIter != end) { - --e, --writeIter; - new (writeIter) T(*e); } - destroyer.commit(); - this->size += destroyer.end - end; + void insert(qsizetype pos, const T *source, qsizetype n) + { + qsizetype oldSize = size; + Q_UNUSED(oldSize); - // Copy assign over existing elements - while (readIter != where) { - --readIter, --writeIter; - *writeIter = *readIter; - } + setup(pos, n); - while (writeIter != where) { - --e, --writeIter; - *writeIter = *e; - } - } + // first create new elements at the end, by copying from elements + // to be inserted (if they extend past the current end of the array) + for (qsizetype i = 0; i != sourceCopyConstruct; ++i) { + new (end + i) T(source[nSource - sourceCopyConstruct + i]); + ++size; + } + Q_ASSERT(size <= oldSize + n); - 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); + // now move construct new elements at the end from existing elements inside + // the array. + for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) { + new (end + i) T(std::move(*(end + i - nSource))); + ++size; + } + // array has the new size now! + Q_ASSERT(size == oldSize + n); - // Array may be truncated at where in case of exceptions - T *const end = this->end(); - const T *readIter = end; - T *writeIter = end + n; + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - nSource]); - const T *const step1End = where + qMax<size_t>(n, end - where); + // finally copy the remaining elements from source over + for (qsizetype i = 0; i != sourceCopyAssign; ++i) + where[i] = source[i]; + } - struct Destructor + void insert(qsizetype pos, const T &t, qsizetype n) { - Destructor(T *&it) - : iter(&it) - , end(it) - { - } + const qsizetype oldSize = size; + Q_UNUSED(oldSize); - void commit() - { - iter = &end; - } + setup(pos, n); - ~Destructor() - { - for (; *iter != end; --*iter) - (*iter)->~T(); + // first create new elements at the end, by copying from elements + // to be inserted (if they extend past the current end of the array) + for (qsizetype i = 0; i != sourceCopyConstruct; ++i) { + new (end + i) T(t); + ++size; } + Q_ASSERT(size <= oldSize + n); - T **iter; - T *end; - } destroyer(writeIter); + // now move construct new elements at the end from existing elements inside + // the array. + for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) { + new (end + i) T(std::move(*(end + i - nSource))); + ++size; + } + // array has the new size now! + Q_ASSERT(size == oldSize + n); - // Construct new elements in array - do { - --readIter, --writeIter; - new (writeIter) T(*readIter); - } while (writeIter != step1End); + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - nSource]); - while (writeIter != end) { - --n, --writeIter; - new (writeIter) T(t); + // finally copy the remaining elements from source over + for (qsizetype i = 0; i != sourceCopyAssign; ++i) + where[i] = t; } - destroyer.commit(); - this->size += destroyer.end - end; - - // Copy assign over existing elements - while (readIter != where) { - --readIter, --writeIter; - *writeIter = *readIter; + void insertOne(qsizetype pos, T &&t) + { + setup(pos, 1); + + if (sourceCopyConstruct) { + Q_ASSERT(sourceCopyConstruct == 1); + new (end) T(std::move(t)); + ++size; + } else { + // create a new element at the end by move constructing one existing element + // inside the array. + new (end) T(std::move(*(end - 1))); + ++size; + + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - 1]); + + // and move the new item into place + *where = std::move(t); + } } + }; - while (writeIter != where) { - --n, --writeIter; - *writeIter = t; + void insert(qsizetype i, const T *data, qsizetype n) + { + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + if (growsAtBegin) { + // copy construct items in reverse order at the begin + Q_ASSERT(this->freeSpaceAtBegin() >= n); + while (n) { + --n; + new (this->begin() - 1) T(data[n]); + --this->ptr; + ++this->size; + } + } else { + Inserter(this).insert(i, data, n); } } - template <typename ...Args> - void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); } + void insert(qsizetype i, qsizetype n, parameter_type t) + { + T copy(t); + + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + if (growsAtBegin) { + // copy construct items in reverse order at the begin + Q_ASSERT(this->freeSpaceAtBegin() >= n); + while (n--) { + new (this->begin() - 1) T(copy); + --this->ptr; + ++this->size; + } + } else { + Inserter(this).insert(i, copy, n); + } + } - template <typename iterator, typename ...Args> - void emplace(iterator where, Args&&... args) + template<typename... Args> + void emplace(qsizetype i, Args &&... args) { - Q_ASSERT(!this->isShared()); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(this->allocatedCapacity() - this->size >= 1); + bool detach = this->needsDetach(); + if (!detach) { + if (i == this->size && this->freeSpaceAtEnd()) { + new (this->end()) T(std::forward<Args>(args)...); + ++this->size; + return; + } + if (i == 0 && this->freeSpaceAtBegin()) { + new (this->begin() - 1) T(std::forward<Args>(args)...); + --this->ptr; + ++this->size; + return; + } + } + T tmp(std::forward<Args>(args)...); + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; - createInPlace(this->end(), std::forward<Args>(args)...); - ++this->size; + this->detachAndGrow(pos, 1, nullptr, nullptr); - std::rotate(where, this->end() - 1, this->end()); + if (growsAtBegin) { + Q_ASSERT(this->freeSpaceAtBegin()); + new (this->begin() - 1) T(std::move(tmp)); + --this->ptr; + ++this->size; + } else { + Inserter(this).insertOne(i, std::move(tmp)); + } } - void erase(T *b, T *e) + void erase(T *b, qsizetype n) { + T *e = b + n; Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < this->end()); Q_ASSERT(e > this->begin() && e <= this->end()); - const T *const end = this->end(); - - // move (by assignment) the elements from e to end - // onto b to the new end - while (e != end) { - *b = *e; - ++b, ++e; + // Comply with std::vector::erase(): erased elements and all after them + // are invalidated. However, erasing from the beginning effectively + // means that all iterators are invalidated. We can use this freedom to + // erase by moving towards the end. + if (b == this->begin() && e != this->end()) { + this->ptr = e; + } else { + const T *const end = this->end(); + + // move (by assignment) the elements from e to end + // onto b to the new end + while (e != end) { + *b = std::move(*e); + ++b; + ++e; + } } + this->size -= n; + std::destroy(b, e); + } - // 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 eraseFirst() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + this->begin()->~T(); + ++this->ptr; + --this->size; + } + + void eraseLast() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + (this->end() - 1)->~T(); + --this->size; } + void assign(T *b, T *e, parameter_type t) { Q_ASSERT(b <= e); @@ -528,10 +666,12 @@ struct QGenericArrayOps { const T *end1 = begin1 + n; while (begin1 != end1) { - if (*begin1 == *begin2) - ++begin1, ++begin2; - else + if (*begin1 == *begin2) { + ++begin1; + ++begin2; + } else { return false; + } } return true; } @@ -541,219 +681,195 @@ template <class T> struct QMovableArrayOps : QGenericArrayOps<T> { - // using QGenericArrayOps<T>::appendInitialize; + static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + +protected: + typedef QTypedArrayData<T> Data; + using DataPointer = QArrayDataPointer<T>; + +public: // using QGenericArrayOps<T>::copyAppend; + // using QGenericArrayOps<T>::moveAppend; // 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) + struct Inserter { - 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(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); - - // Provides strong exception safety guarantee, - // provided T::~T() nothrow + QArrayDataPointer<T> *data; + T *displaceFrom; + T *displaceTo; + qsizetype nInserts = 0; + qsizetype bytes; + + Inserter(QArrayDataPointer<T> *d) : data(d) { } + ~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); + } + } + data->size += nInserts; + } + Q_DISABLE_COPY(Inserter) - struct ReversibleDisplace + T *displace(qsizetype pos, qsizetype n) { - 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)); - } + nInserts = n; + T *insertionPoint = data->ptr + pos; + displaceFrom = data->ptr + pos; + displaceTo = displaceFrom + n; + bytes = data->size - pos; + bytes *= sizeof(T); + ::memmove(static_cast<void *>(displaceTo), static_cast<void *>(displaceFrom), bytes); + return insertionPoint; + } - void commit() { displace = 0; } + void insert(qsizetype pos, const T *source, qsizetype n) + { + T *where = displace(pos, n); - ~ReversibleDisplace() - { - if (displace) - ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace), - (end - begin) * sizeof(T)); + while (n--) { + new (where) T(*source); + ++where; + ++source; + ++displaceFrom; } + } - T *const begin; - T *const end; - size_t displace; - - } displace(where, this->end(), size_t(e - b)); - - struct CopyConstructor + void insert(qsizetype pos, const T &t, qsizetype n) { - CopyConstructor(T *w) : where(w) {} - - void copy(const T *src, const T *const srcEnd) - { - n = 0; - for (; src != srcEnd; ++src) { - new (where + n) T(*src); - ++n; - } - n = 0; - } + T *where = displace(pos, n); - ~CopyConstructor() - { - while (n) - where[--n].~T(); + while (n--) { + new (where) T(t); + ++where; + ++displaceFrom; } + } - T *const where; - size_t n; - } copier(where); - - copier.copy(b, e); - displace.commit(); - this->size += (e - b); - } + void insertOne(qsizetype pos, T &&t) + { + T *where = displace(pos, 1); + new (where) T(std::move(t)); + ++displaceFrom; + Q_ASSERT(displaceFrom == displaceTo); + } - 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 insert(qsizetype i, const T *data, qsizetype n) + { + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + if (growsAtBegin) { + // copy construct items in reverse order at the begin + Q_ASSERT(this->freeSpaceAtBegin() >= n); + while (n) { + --n; + new (this->begin() - 1) T(data[n]); + --this->ptr; + ++this->size; } + } else { + Inserter(this).insert(i, data, n); + } + } - void commit() { displace = 0; } - - ~ReversibleDisplace() - { - if (displace) - ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace), - (end - begin) * sizeof(T)); + void insert(qsizetype i, qsizetype n, parameter_type t) + { + T copy(t); + + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + if (growsAtBegin) { + // copy construct items in reverse order at the begin + Q_ASSERT(this->freeSpaceAtBegin() >= n); + while (n--) { + new (this->begin() - 1) T(copy); + --this->ptr; + ++this->size; } + } else { + Inserter(this).insert(i, copy, n); + } + } - 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; + template<typename... Args> + void emplace(qsizetype i, Args &&... args) + { + bool detach = this->needsDetach(); + if (!detach) { + if (i == this->size && this->freeSpaceAtEnd()) { + new (this->end()) T(std::forward<Args>(args)...); + ++this->size; + return; } - - ~CopyConstructor() - { - while (n) - where[--n].~T(); + if (i == 0 && this->freeSpaceAtBegin()) { + new (this->begin() - 1) T(std::forward<Args>(args)...); + --this->ptr; + ++this->size; + return; } - - T *const where; - size_t n; - } copier(where); - - copier.copy(n, t); - displace.commit(); - this->size += int(n); + } + T tmp(std::forward<Args>(args)...); + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + this->detachAndGrow(pos, 1, nullptr, nullptr); + if (growsAtBegin) { + Q_ASSERT(this->freeSpaceAtBegin()); + new (this->begin() - 1) T(std::move(tmp)); + --this->ptr; + ++this->size; + } else { + Inserter(this).insertOne(i, std::move(tmp)); + } } - // use moving insert - using QGenericArrayOps<T>::insert; - - void erase(T *b, T *e) + void erase(T *b, qsizetype n) { + T *e = b + n; + Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < this->end()); Q_ASSERT(e > this->begin() && e <= this->end()); - struct Mover - { - Mover(T *&start, const T *finish, qsizetype &sz) - : destination(start) - , source(start) - , n(finish - start) - , size(sz) - { - } - - ~Mover() - { - ::memmove(static_cast<void *>(destination), static_cast<const void *>(source), n * sizeof(T)); - size -= (source - destination); - } - - T *&destination; - const T *const source; - size_t n; - qsizetype &size; - } mover(e, this->end(), this->size); + // Comply with std::vector::erase(): erased elements and all after them + // are invalidated. However, erasing from the beginning effectively + // means that all iterators are invalidated. We can use this freedom to + // erase by moving towards the end. - // destroy the elements we're erasing - do { - // Exceptions or not, dtor called once per instance - (--e)->~T(); - } while (e != b); + std::destroy(b, e); + if (b == this->begin() && e != this->end()) { + this->ptr = e; + } else if (e != this->end()) { + memmove(static_cast<void *>(b), static_cast<const void *>(e), (static_cast<const T *>(this->end()) - e)*sizeof(T)); + } + this->size -= n; } - void moveAppend(T *b, T *e) + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) { - 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); + auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, option); + Q_CHECK_PTR(pair.second); + Q_ASSERT(pair.first != nullptr); + this->d = pair.first; + this->ptr = pair.second; } }; @@ -766,7 +882,7 @@ struct QArrayOpsSelector template <class T> struct QArrayOpsSelector<T, typename std::enable_if< - !QTypeInfoQuery<T>::isComplex && QTypeInfoQuery<T>::isRelocatable + !QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable >::type> { typedef QPodArrayOps<T> Type; @@ -775,17 +891,101 @@ struct QArrayOpsSelector<T, template <class T> struct QArrayOpsSelector<T, typename std::enable_if< - QTypeInfoQuery<T>::isComplex && QTypeInfoQuery<T>::isRelocatable + QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable >::type> { typedef QMovableArrayOps<T> Type; }; +template <class T> +struct QCommonArrayOps : QArrayOpsSelector<T>::Type +{ + using Base = typename QArrayOpsSelector<T>::Type; + using Data = QTypedArrayData<T>; + using DataPointer = QArrayDataPointer<T>; + using parameter_type = typename Base::parameter_type; + +protected: + using Self = QCommonArrayOps<T>; + +public: + // using Base::truncate; + // using Base::destroyAll; + // using Base::assign; + // using Base::compare; + + template<typename It> + void appendIteratorRange(It b, It e, QtPrivate::IfIsForwardIterator<It> = true) + { + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + const qsizetype distance = std::distance(b, e); + Q_ASSERT(distance >= 0 && distance <= this->allocatedCapacity() - this->size); + Q_UNUSED(distance); + +#if __cplusplus >= 202002L && defined(__cpp_concepts) && defined(__cpp_lib_concepts) + constexpr bool canUseCopyAppend = + std::contiguous_iterator<It> && + std::is_same_v< + std::remove_cv_t<typename std::iterator_traits<It>::value_type>, + T + >; + if constexpr (canUseCopyAppend) { + this->copyAppend(std::to_address(b), std::to_address(e)); + } else +#endif + { + T *iter = this->end(); + for (; b != e; ++iter, ++b) { + new (iter) T(*b); + ++this->size; + } + } + } + + // slightly higher level API than copyAppend() that also preallocates space + void growAppend(const T *b, const T *e) + { + if (b == e) + return; + Q_ASSERT(b < e); + const qsizetype n = e - b; + DataPointer old; + + // points into range: + if (QtPrivate::q_points_into_range(b, *this)) + this->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old); + else + this->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr); + Q_ASSERT(this->freeSpaceAtEnd() >= n); + // b might be updated so use [b, n) + this->copyAppend(b, b + n); + } + + void appendUninitialized(qsizetype newSize) + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(!this->isShared()); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); + + T *const b = this->begin(); + do { + auto ptr = b + this->size; + + if constexpr (std::is_constructible_v<T, Qt::Initialization>) + new (ptr) T(Qt::Uninitialized); + else + new (ptr) T; // not T() -- default-construct + } while (++this->size != newSize); + } +}; + } // namespace QtPrivate template <class T> struct QArrayDataOps - : QtPrivate::QArrayOpsSelector<T>::Type + : QtPrivate::QCommonArrayOps<T> { }; |