diff options
Diffstat (limited to 'src/corelib/tools/qarraydataops.h')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 1073 |
1 files changed, 809 insertions, 264 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 8e19525f07..c3e9821e81 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1,187 +1,378 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** 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 -namespace QtPrivate { +template <class T> struct QArrayDataPointer; -QT_WARNING_PUSH -#if defined(Q_CC_GNU) && Q_CC_GNU >= 700 -QT_WARNING_DISABLE_GCC("-Wstringop-overflow") -#endif +namespace QtPrivate { template <class T> struct QPodArrayOps - : QTypedArrayData<T> + : public QArrayDataPointer<T> { - void appendInitialize(size_t newSize) + 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; + + using QArrayDataPointer<T>::QArrayDataPointer; + + void appendInitialize(qsizetype newSize) noexcept { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->alloc); - - ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T)); - this->size = int(newSize); + Q_ASSERT(!this->isShared()); + 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(); } - void copyAppend(const T *b, const T *e) + void copyAppend(const T *b, const T *e) noexcept { - 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((e - b) <= this->freeSpaceAtEnd()); + + if (b == e) + return; - ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b), - (e - b) * sizeof(T)); - this->size += e - b; + ::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 copyAppend(qsizetype n, parameter_type t) noexcept { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(n <= this->alloc - uint(this->size)); + Q_ASSERT(!this->isShared() || n == 0); + Q_ASSERT(this->freeSpaceAtEnd() >= n); + if (!n) + return; + + T *where = this->end(); + this->size += qsizetype(n); + while (n--) + *where++ = t; + } - T *iter = this->end(); - const T *const end = iter + n; - for (; iter != end; ++iter) - ::memcpy(iter, &t, sizeof(T)); - this->size += int(n); + 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->ref.isShared()); + 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->isMutable()); - Q_ASSERT(this->ref.atomic.loadRelaxed() == 0); + Q_ASSERT(this->d); + 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. } - 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->ref.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->alloc - uint(this->size)); + Q_ASSERT((pos == QArrayData::GrowsAtBeginning && n <= this->freeSpaceAtBegin()) || + (pos == QArrayData::GrowsAtEnd && n <= this->freeSpaceAtEnd())); + + 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; + } - ::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); + void insert(qsizetype i, const T *data, qsizetype n) + { + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; + + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + T *where = createHole(pos, i, n); + ::memcpy(static_cast<void *>(where), static_cast<const void *>(data), n * sizeof(T)); } - void erase(T *b, T *e) + void insert(qsizetype i, qsizetype n, parameter_type t) { + T copy(t); + + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; + + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); + + 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, 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()); + Q_ASSERT(e > this->begin() && e <= this->end()); + + // 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 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()); + + 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 constexpr (QArrayDataPointer<T>::pass_parameter_by_value) { + return ::memcmp(begin1, begin2, n * sizeof(T)) == 0; + } else { + const T *end1 = begin1 + n; + while (begin1 != end1) { + if (*begin1 == *begin2) { + ++begin1; + ++begin2; + } else { + return false; + } + } + return true; + } + } - ::memmove(static_cast<void *>(b), static_cast<void *>(e), - (static_cast<T *>(this->end()) - e) * sizeof(T)); - this->size -= (e - b); + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) + { + 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 - : QTypedArrayData<T> + : public QArrayDataPointer<T> { - void appendInitialize(size_t newSize) + 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(qsizetype newSize) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->alloc); + Q_ASSERT(!this->isShared()); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); - T *const begin = this->begin(); + T *const b = this->begin(); do { - new (begin + this->size) T; - } while (uint(++this->size) != newSize); + new (b + this->size) T; + } while (++this->size != newSize); } 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)); - - T *iter = this->end(); - for (; b != e; ++iter, ++b) { - new (iter) T(*b); + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + 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 *data = this->begin(); + while (b < e) { + new (data + this->size) T(*b); + ++b; ++this->size; } } - void copyAppend(size_t n, const T &t) + void copyAppend(qsizetype n, parameter_type t) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(n <= this->alloc - uint(this->size)); + Q_ASSERT(!this->isShared() || n == 0); + Q_ASSERT(this->freeSpaceAtEnd() >= n); + if (!n) + return; + + T *data = this->begin(); + while (n--) { + new (data + this->size) T(t); + ++this->size; + } + } - T *iter = this->end(); - const T *const end = iter + n; - for (; iter != end; ++iter) { - new (iter) T(t); + void moveAppend(T *b, T *e) + { + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(b <= e); + Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); + + if (b == e) + return; + + T *data = this->begin(); + while (b < e) { + new (data + this->size) T(std::move(*b)); + ++b; ++this->size; } } @@ -189,114 +380,300 @@ 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(); - 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 { - Q_ASSERT(this->isMutable()); + Q_ASSERT(this->d); // 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); - - const T *const b = this->begin(); - const T *i = this->end(); + Q_ASSERT(this->d->ref_.loadRelaxed() == 0); - 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->ref.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->alloc - uint(this->size)); + QArrayDataPointer<T> *data; + T *begin; + qsizetype size; - // Array may be truncated at where in case of exceptions + qsizetype sourceCopyConstruct = 0, nSource = 0, move = 0, sourceCopyAssign = 0; + T *end = nullptr, *last = nullptr, *where = nullptr; - T *const end = this->end(); - const T *readIter = end; - T *writeIter = end + (e - b); + Inserter(QArrayDataPointer<T> *d) : data(d) + { + begin = d->ptr; + size = d->size; + } + ~Inserter() { + data->ptr = begin; + data->size = size; + } + Q_DISABLE_COPY(Inserter) - const T *const step1End = where + qMax(e - b, end - where); + 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; + } + } - struct Destructor + void insert(qsizetype pos, const T *source, qsizetype n) { - Destructor(T *&it) - : iter(&it) - , end(it) - { + qsizetype oldSize = size; + Q_UNUSED(oldSize); + + setup(pos, n); + + // 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 commit() - { - iter = &end; + // 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); + + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - nSource]); + + // finally copy the remaining elements from source over + for (qsizetype i = 0; i != sourceCopyAssign; ++i) + where[i] = source[i]; + } + + void insert(qsizetype pos, const T &t, qsizetype n) + { + const qsizetype oldSize = size; + Q_UNUSED(oldSize); - ~Destructor() - { - for (; *iter != end; --*iter) - (*iter)->~T(); + setup(pos, n); + + // 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) { - --e, --writeIter; - new (writeIter) T(*e); + // 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; + 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); + } + } + }; + + 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 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); + } + } - // Copy assign over existing elements - while (readIter != where) { - --readIter, --writeIter; - *writeIter = *readIter; + 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)...); + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; + + this->detachAndGrow(pos, 1, nullptr, nullptr); - while (writeIter != where) { - --e, --writeIter; - *writeIter = *e; + 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()); + Q_ASSERT(e > this->begin() && e <= this->end()); + + // 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); + } - const T *const end = this->end(); + void eraseFirst() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + this->begin()->~T(); + ++this->ptr; + --this->size; + } - do { - *b = *e; - ++b, ++e; - } while (e != end); + void eraseLast() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + (this->end() - 1)->~T(); + --this->size; + } - 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; } }; @@ -304,111 +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->ref.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->alloc - uint(this->size)); + 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) - // Provides strong exception safety guarantee, - // provided T::~T() nothrow + T *displace(qsizetype pos, qsizetype n) + { + 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; + } - struct ReversibleDisplace + void insert(qsizetype pos, const T *source, 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)); + T *where = displace(pos, n); + + while (n--) { + new (where) T(*source); + ++where; + ++source; + ++displaceFrom; } + } - void commit() { displace = 0; } + void insert(qsizetype pos, const T &t, 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(t); + ++where; + ++displaceFrom; } + } - T *const begin; - T *const end; - size_t displace; + void insertOne(qsizetype pos, T &&t) + { + T *where = displace(pos, 1); + new (where) T(std::move(t)); + ++displaceFrom; + Q_ASSERT(displaceFrom == displaceTo); + } - } displace(where, this->end(), size_t(e - b)); + }; - struct CopyConstructor - { - 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; - } - ~CopyConstructor() - { - while (n) - where[--n].~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); + } + } - T *const where; - size_t n; - } copier(where); + 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); + } + } - copier.copy(b, e); - displace.commit(); - this->size += (e - b); + 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)...); + 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)); + } } - 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, int &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; - int &size; - } mover(e, this->end(), this->size); + Q_ASSERT(e > this->begin() && e <= this->end()); + + // 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. + + 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; + } - do { - // Exceptions or not, dtor called once per instance - (--e)->~T(); - } while (e != b); + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) + { + 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; } }; @@ -421,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; @@ -430,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> { }; |