diff options
Diffstat (limited to 'src/corelib/tools/qarraydataops.h')
| -rw-r--r-- | src/corelib/tools/qarraydataops.h | 1796 |
1 files changed, 630 insertions, 1166 deletions
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 9626f4eeff..c3e9821e81 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1,50 +1,15 @@ -/**************************************************************************** -** -** Copyright (C) 2020 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 <algorithm> +#include <memory> #include <new> #include <string.h> #include <utility> @@ -58,211 +23,68 @@ template <class T> struct QArrayDataPointer; namespace QtPrivate { -/*! - \internal - - This class provides basic building blocks to do reversible operations. This - in turn allows to reason about exception safety under certain conditions. - - This class is not part of the Qt API. It exists for the convenience of other - Qt classes. This class may change from version to version without notice, - or even be removed. - - We mean it. - */ -template<typename T> -struct QArrayExceptionSafetyPrimitives -{ - using parameter_type = typename QArrayDataPointer<T>::parameter_type; - using iterator = typename QArrayDataPointer<T>::iterator; - - // Constructs a range of elements at the specified position. If an exception - // is thrown during construction, already constructed elements are - // destroyed. By design, only one function (create/copy/clone/move) and only - // once is supposed to be called per class instance. - struct Constructor - { - T *const where; - size_t n = 0; - - template<typename It> - using iterator_copy_value = decltype(*std::declval<It>()); - template<typename It> - using iterator_move_value = decltype(std::move(*std::declval<It>())); - - Constructor(T *w) noexcept : where(w) {} - qsizetype create(size_t size) noexcept(std::is_nothrow_default_constructible_v<T>) - { - n = 0; - while (n != size) { - new (where + n) T; - ++n; - } - return qsizetype(std::exchange(n, 0)); - } - template<typename ForwardIt> - qsizetype copy(ForwardIt first, ForwardIt last) - noexcept(std::is_nothrow_constructible_v<T, iterator_copy_value<ForwardIt>>) - { - n = 0; - for (; first != last; ++first) { - new (where + n) T(*first); - ++n; - } - return qsizetype(std::exchange(n, 0)); - } - qsizetype clone(size_t size, parameter_type t) - noexcept(std::is_nothrow_constructible_v<T, parameter_type>) - { - n = 0; - while (n != size) { - new (where + n) T(t); - ++n; - } - return qsizetype(std::exchange(n, 0)); - } - template<typename ForwardIt> - qsizetype move(ForwardIt first, ForwardIt last) - noexcept(std::is_nothrow_constructible_v<T, iterator_move_value<ForwardIt>>) - { - n = 0; - for (; first != last; ++first) { - new (where + n) T(std::move(*first)); - ++n; - } - return qsizetype(std::exchange(n, 0)); - } - ~Constructor() noexcept(std::is_nothrow_destructible_v<T>) - { - while (n) - where[--n].~T(); - } - }; - - // Watches passed iterator. Unless commit() is called, all the elements that - // the watched iterator passes through are deleted at the end of object - // lifetime. - // - // Requirements: when not at starting position, the iterator is expected to - // point to a valid object (to initialized memory) - template<typename It = iterator> - struct Destructor - { - It *iter; - It end; - It intermediate; - - Destructor(It &it) noexcept(std::is_nothrow_copy_constructible_v<It>) - : iter(std::addressof(it)), end(it) - { } - void commit() noexcept - { - iter = std::addressof(end); - } - void freeze() noexcept(std::is_nothrow_copy_constructible_v<It>) - { - intermediate = *iter; iter = std::addressof(intermediate); - } - ~Destructor() noexcept(std::is_nothrow_destructible_v<T>) - { - // Step is either 1 or -1 and depends on the interposition of *iter - // and end. Note that *iter is expected to point to a valid object - // (see the logic below). - for (const int step = *iter < end ? 1 : -1; *iter != end; std::advance(*iter, step)) - (*iter)->~T(); - } - }; - - // Moves the data range in memory by the specified amount. Unless commit() - // is called, the data is moved back to the original place at the end of - // object lifetime. - struct Displacer - { - T *const begin; - T *const end; - qsizetype displace; - - static_assert(QTypeInfo<T>::isRelocatable, "Type must be relocatable"); - - Displacer(T *start, T *finish, qsizetype diff) noexcept - : begin(start), end(finish), displace(diff) - { - ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin), - (end - begin) * sizeof(T)); - } - void commit() noexcept { displace = 0; } - ~Displacer() noexcept - { - if (displace) - ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace), - (end - begin) * sizeof(T)); - } - }; - - // Watches passed iterator. Moves the data range (defined as a start - // iterator and a length) to the new starting position at the end of object - // lifetime. - struct Mover - { - T *&destination; - const T *const source; - size_t n; - qsizetype &size; - - static_assert(QTypeInfo<T>::isRelocatable, "Type must be relocatable"); - - Mover(T *&start, size_t length, qsizetype &sz) noexcept - : destination(start), source(start), n(length), size(sz) - { } - ~Mover() noexcept - { - ::memmove(static_cast<void *>(destination), static_cast<const void *>(source), - n * sizeof(T)); - size -= source > destination ? source - destination : destination - source; - } - }; -}; - -// Tags for compile-time dispatch based on backwards vs forward growing policy -struct GrowsForwardTag {}; -struct GrowsBackwardsTag {}; -template<typename> struct InverseTag; -template<> struct InverseTag<GrowsForwardTag> { using tag = GrowsBackwardsTag; }; -template<> struct InverseTag<GrowsBackwardsTag> { using tag = GrowsForwardTag; }; - -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> { + static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); + protected: typedef QTypedArrayData<T> Data; - - template <typename ...Args> - void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); } + 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 > size_t(this->size)); - Q_ASSERT(newSize - this->size <= size_t(this->freeSpaceAtEnd())); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); - ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T)); - this->size = qsizetype(newSize); + T *where = this->end(); + this->size = newSize; + const T *e = this->end(); + while (where != e) + *where++ = T(); } - void moveAppend(T *b, T *e) - { insert(this->end(), b, 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((e - b) <= this->freeSpaceAtEnd()); - void truncate(size_t newSize) + if (b == e) + return; + + ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b), (e - b) * sizeof(T)); + this->size += (e - b); + } + + void copyAppend(qsizetype n, parameter_type t) noexcept + { + 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; + } + + void moveAppend(T *b, T *e) noexcept + { + copyAppend(b, e); + } + + void truncate(size_t newSize) noexcept { Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); @@ -271,7 +93,7 @@ public: 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); @@ -280,154 +102,166 @@ public: // exception safe; size not updated. } - void insert(T *where, const T *b, const T *e) - { insert(GrowsForwardTag{}, where, b, e); } - - void insert(GrowsForwardTag, T *where, const T *b, const T *e) + T *createHole(QArrayData::GrowthPosition pos, qsizetype where, qsizetype n) { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); + 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(GrowsBackwardsTag, T *where, const T *b, const T *e) + void insert(qsizetype i, const T *data, qsizetype n) { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtBegin()); - - auto oldBegin = this->begin(); - this->ptr -= (e - b); - ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), - (where - static_cast<const T*>(oldBegin)) * sizeof(T)); - ::memcpy(static_cast<void *>(where - (e - b)), static_cast<const void *>(b), - (e - b) * sizeof(T)); - this->size += (e - b); - } + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; - void insert(T *where, size_t n, parameter_type t) - { insert(GrowsForwardTag{}, where, n, t); } - - void insert(GrowsForwardTag, T *where, size_t n, parameter_type t) - { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n); + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - ::memmove(static_cast<void *>(where + n), static_cast<void *>(where), - (static_cast<const T*>(this->end()) - where) * sizeof(T)); - this->size += qsizetype(n); // PODs can't throw on copy - while (n--) - *where++ = t; + T *where = createHole(pos, i, n); + ::memcpy(static_cast<void *>(where), static_cast<const void *>(data), n * sizeof(T)); } - void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t) + void insert(qsizetype i, qsizetype n, parameter_type t) { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n); - - auto oldBegin = this->begin(); - this->ptr -= n; - ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), - (where - static_cast<const T*>(oldBegin)) * sizeof(T)); - this->size += qsizetype(n); // PODs can't throw on copy - where -= n; - while (n--) - *where++ = t; - } - - - template <typename ...Args> - void emplace(T *where, Args&&... args) - { emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...); } + T copy(t); - template <typename ...Args> - void emplace(GrowsForwardTag, T *where, Args&&... args) - { - Q_ASSERT(!this->isShared()); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(this->freeSpaceAtEnd() >= 1); + typename Data::GrowthPosition pos = Data::GrowsAtEnd; + if (this->size != 0 && i == 0) + pos = Data::GrowsAtBeginning; - 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)...); + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where), - (static_cast<const T*>(this->end()) - where) * sizeof(T)); - *where = t; - } - - ++this->size; + T *where = createHole(pos, i, n); + while (n--) + *where++ = copy; } - template <typename ...Args> - void emplace(GrowsBackwardsTag, T *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->freeSpaceAtBegin() >= 1); - - if (where == this->begin()) { - new (this->begin() - 1) T(std::forward<Args>(args)...); - --this->ptr; - } else { - // Preserve the value, because it might be a reference to some part of the moved chunk - T t(std::forward<Args>(args)...); - - auto oldBegin = this->begin(); - --this->ptr; - ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), - (where - oldBegin) * sizeof(T)); - *(where - 1) = t; + 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->size; - } + this->detachAndGrow(pos, 1, nullptr, nullptr); - void erase(T *b, T *e) - { erase(GrowsForwardTag{}, b, e); } + T *where = createHole(pos, i, 1); + new (where) T(std::move(tmp)); + } - void erase(GrowsForwardTag, 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 erase(GrowsBackwardsTag, T *b, T *e) + void eraseFirst() noexcept { 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(this->size); + ++this->ptr; + --this->size; + } - const auto oldBegin = this->begin(); - this->ptr += (e - b); - ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), - (b - static_cast<T *>(oldBegin)) * sizeof(T)); - this->size -= (e - b); + void eraseLast() noexcept + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(this->size); + --this->size; } - void assign(T *b, T *e, parameter_type t) + 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()); @@ -457,67 +291,90 @@ public: } } - void reallocate(qsizetype alloc, typename Data::ArrayOptions options) + void reallocate(qsizetype alloc, QArrayData::AllocationOption option) { - // when reallocating, take care of the situation when no growth is - // happening - need to move the data in this case, unfortunately - const bool grows = options & (Data::GrowsForward | Data::GrowsBackwards); - - // ### optimize me: there may be cases when moving is not obligatory - if (const auto gap = this->freeSpaceAtBegin(); this->d && !grows && gap) { - auto oldBegin = this->begin(); - this->ptr -= gap; - ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin), - this->size * sizeof(T)); - } - - 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; - - template <typename ...Args> - void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); } + 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 > size_t(this->size)); - Q_ASSERT(newSize - this->size <= size_t(this->freeSpaceAtEnd())); + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); T *const b = this->begin(); do { new (b + this->size) T; - } while (size_t(++this->size) != newSize); + } while (++this->size != newSize); } - void moveAppend(T *b, T *e) + void copyAppend(const T *b, const T *e) { Q_ASSERT(this->isMutable() || b == e); Q_ASSERT(!this->isShared() || b == e); Q_ASSERT(b <= e); Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); - typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor; + if (b == e) // short-cut and handling the case b and e == nullptr + return; - // Provides strong exception safety guarantee, - // provided T::~T() nothrow + T *data = this->begin(); + while (b < e) { + new (data + this->size) T(*b); + ++b; + ++this->size; + } + } - CopyConstructor copier(this->end()); - this->size += copier.move(b, e); + void copyAppend(qsizetype n, parameter_type t) + { + 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; + } + } + + 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; + } } void truncate(size_t newSize) @@ -526,10 +383,8 @@ public: Q_ASSERT(!this->isShared()); Q_ASSERT(newSize < size_t(this->size)); - const T *const b = this->begin(); - do { - (b + --this->size)->~T(); - } while (size_t(this->size) != newSize); + std::destroy(this->begin() + newSize, this->end()); + this->size = newSize; } void destroyAll() // Call from destructors, ONLY @@ -540,304 +395,264 @@ public: 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) - { insert(GrowsForwardTag{}, where, b, e); } - - void insert(GrowsForwardTag, T *where, const T *b, const T *e) + struct Inserter { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); - - typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor; + 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); - - const T *const step1End = where + qMax(e - b, end - where); - - Destructor destroyer(writeIter); - - // Construct new elements in array - while (writeIter != step1End) { - --readIter; - // If exception happens on construction, we should not call ~T() - new (writeIter - 1) T(*readIter); - --writeIter; - } - - while (writeIter != end) { - --e; - // If exception happens on construction, we should not call ~T() - new (writeIter - 1) T(*e); - --writeIter; + Inserter(QArrayDataPointer<T> *d) : data(d) + { + begin = d->ptr; + size = d->size; } - - destroyer.commit(); - this->size += destroyer.end - end; - - // Copy assign over existing elements - while (readIter != where) { - --readIter; - --writeIter; - *writeIter = *readIter; + ~Inserter() { + data->ptr = begin; + data->size = size; } + Q_DISABLE_COPY(Inserter) - while (writeIter != where) { - --e; - --writeIter; - *writeIter = *e; + 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; + } } - } - - void insert(GrowsBackwardsTag, T *where, const T *b, const T *e) - { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtBegin()); - - typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor; - T *const begin = this->begin(); - const T *readIter = begin; - T *writeIter = begin - (e - b); - - const T *const step1End = where - qMax(e - b, where - begin); + void insert(qsizetype pos, const T *source, qsizetype n) + { + qsizetype oldSize = size; + Q_UNUSED(oldSize); - Destructor destroyer(writeIter); + setup(pos, n); - // Construct new elements in array - while (writeIter != step1End) { - new (writeIter) T(*readIter); - ++readIter; - ++writeIter; - } + // 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); - while (writeIter != begin) { - new (writeIter) T(*b); - ++b; - ++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); - destroyer.commit(); - this->size += begin - destroyer.end; - this->ptr -= begin - destroyer.end; + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - nSource]); - // Copy assign over existing elements - while (readIter != where) { - *writeIter = *readIter; - ++readIter; - ++writeIter; + // finally copy the remaining elements from source over + for (qsizetype i = 0; i != sourceCopyAssign; ++i) + where[i] = source[i]; } - while (writeIter != where) { - *writeIter = *b; - ++b; - ++writeIter; - } - } - - void insert(T *where, size_t n, parameter_type t) - { insert(GrowsForwardTag{}, where, n, t); } - - void insert(GrowsForwardTag, T *where, size_t n, parameter_type t) - { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n); + void insert(qsizetype pos, const T &t, qsizetype n) + { + const qsizetype oldSize = size; + Q_UNUSED(oldSize); - typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor; + setup(pos, n); - // Array may be truncated at where in case of exceptions - T *const end = this->end(); - const T *readIter = end; - T *writeIter = end + 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); - const T *const step1End = where + qMax<size_t>(n, end - where); + // 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); - Destructor destroyer(writeIter); + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - nSource]); - // Construct new elements in array - while (writeIter != step1End) { - --readIter; - // If exception happens on construction, we should not call ~T() - new (writeIter - 1) T(*readIter); - --writeIter; + // finally copy the remaining elements from source over + for (qsizetype i = 0; i != sourceCopyAssign; ++i) + where[i] = t; } - while (writeIter != end) { - --n; - // If exception happens on construction, we should not call ~T() - new (writeIter - 1) T(t); - --writeIter; - } + void insertOne(qsizetype pos, T &&t) + { + setup(pos, 1); - destroyer.commit(); - this->size += destroyer.end - end; + 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; - // Copy assign over existing elements - while (readIter != where) { - --readIter; - --writeIter; - *writeIter = *readIter; - } + // now move assign existing elements towards the end + for (qsizetype i = 0; i != move; --i) + last[i] = std::move(last[i - 1]); - while (writeIter != where) { - --n; - --writeIter; - *writeIter = t; + // and move the new item into place + *where = std::move(t); + } } - } + }; - void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t) + void insert(qsizetype i, const T *data, qsizetype n) { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n); + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; - typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor; + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - T *const begin = this->begin(); - const T *readIter = begin; - T *writeIter = begin - n; - - const T *const step1End = where - qMax<size_t>(n, where - begin); - - Destructor destroyer(writeIter); - - // Construct new elements in array - while (writeIter != step1End) { - new (writeIter) T(*readIter); - ++readIter; - ++writeIter; - } - - while (writeIter != begin) { - new (writeIter) T(t); - ++writeIter; - } - - destroyer.commit(); - this->size += begin - destroyer.end; - this->ptr -= begin - destroyer.end; - - // Copy assign over existing elements - while (readIter != where) { - *writeIter = *readIter; - ++readIter; - ++writeIter; - } - - while (writeIter != where) { - *writeIter = t; - ++writeIter; + 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 iterator, typename ...Args> - void emplace(iterator where, Args&&... args) - { emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...); } - - template <typename iterator, typename ...Args> - void emplace(GrowsForwardTag, iterator 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->freeSpaceAtEnd() >= 1); + T copy(t); - createInPlace(this->end(), std::forward<Args>(args)...); - ++this->size; + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; - std::rotate(where, this->end() - 1, this->end()); + 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(GrowsBackwardsTag, 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->freeSpaceAtBegin() >= 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->begin() - 1, std::forward<Args>(args)...); - --this->ptr; - ++this->size; + this->detachAndGrow(pos, 1, nullptr, nullptr); - std::rotate(this->begin(), this->begin() + 1, where); + 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) - { erase(GrowsForwardTag{}, b, e); } - - void erase(GrowsForwardTag, 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; + } } - - // destroy the final elements at the end - // here, b points to the new end and e to the actual end - do { - // Exceptions or not, dtor called once per instance - --this->size; - (--e)->~T(); - } while (e != b); + this->size -= n; + std::destroy(b, e); } - void erase(GrowsBackwardsTag, T *b, T *e) + void eraseFirst() noexcept { 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 begin = this->begin(); - - // move (by assignment) the elements from begin to b - // onto the new begin to e - while (b != begin) { - --b; - --e; - *e = *b; - } + Q_ASSERT(this->size); + this->begin()->~T(); + ++this->ptr; + --this->size; + } - // destroy the final elements at the begin - // here, e points to the new begin and b to the actual begin - do { - // Exceptions or not, dtor called once per instance - ++this->ptr; - --this->size; - (b++)->~T(); - } while (b != e); + 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); @@ -866,144 +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) - { insert(GrowsForwardTag{}, where, b, e); } - - void insert(GrowsForwardTag, T *where, const T *b, const T *e) + struct Inserter { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtEnd()); + QArrayDataPointer<T> *data; + T *displaceFrom; + T *displaceTo; + qsizetype nInserts = 0; + qsizetype bytes; - typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; - typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor; + 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; + } - ReversibleDisplace displace(where, this->end(), e - b); - CopyConstructor copier(where); - const auto copiedSize = copier.copy(b, e); - displace.commit(); - this->size += copiedSize; - } + void insert(qsizetype pos, const T *source, qsizetype n) + { + T *where = displace(pos, n); - void insert(GrowsBackwardsTag, T *where, const T *b, const T *e) - { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->freeSpaceAtBegin()); + while (n--) { + new (where) T(*source); + ++where; + ++source; + ++displaceFrom; + } + } - typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor; - typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; + void insert(qsizetype pos, const T &t, qsizetype n) + { + T *where = displace(pos, n); - // Provides strong exception safety guarantee, - // provided T::~T() nothrow + while (n--) { + new (where) T(t); + ++where; + ++displaceFrom; + } + } - ReversibleDisplace displace(this->begin(), where, -(e - b)); - CopyConstructor copier(where - (e - b)); - const auto copiedSize = copier.copy(b, e); - displace.commit(); - this->ptr -= copiedSize; - this->size += copiedSize; - } + 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) - { insert(GrowsForwardTag{}, where, n, t); } + }; - void insert(GrowsForwardTag, T *where, size_t n, parameter_type t) - { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n); - typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; - typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor; + 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; - // Provides strong exception safety guarantee, - // provided T::~T() nothrow + DataPointer oldData; + this->detachAndGrow(pos, n, &data, &oldData); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - ReversibleDisplace displace(where, this->end(), qsizetype(n)); - CopyConstructor copier(where); - const auto copiedSize = copier.clone(n, t); - displace.commit(); - this->size += copiedSize; + 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(GrowsBackwardsTag, T *where, size_t n, parameter_type t) + void insert(qsizetype i, qsizetype n, parameter_type t) { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n); - - typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor; - typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace; - - // Provides strong exception safety guarantee, - // provided T::~T() nothrow - - ReversibleDisplace displace(this->begin(), where, -qsizetype(n)); - CopyConstructor copier(where - n); - const auto copiedSize = copier.clone(n, t); - displace.commit(); - this->ptr -= copiedSize; - this->size += copiedSize; - } + T copy(t); - // use moving insert - using QGenericArrayOps<T>::insert; + const bool growsAtBegin = this->size != 0 && i == 0; + const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd; - void erase(T *b, T *e) - { erase(GrowsForwardTag{}, b, e); } + this->detachAndGrow(pos, n, nullptr, nullptr); + Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) || + (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n)); - void erase(GrowsForwardTag, 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()); - - typedef typename QArrayExceptionSafetyPrimitives<T>::Mover Mover; + 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); + } + } - Mover mover(e, static_cast<const T *>(this->end()) - e, this->size); + 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; - // destroy the elements we're erasing - do { - // Exceptions or not, dtor called once per instance - (--e)->~T(); - } while (e != b); + 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(GrowsBackwardsTag, 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()); - typedef typename QArrayExceptionSafetyPrimitives<T>::Mover Mover; + // 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. - Mover mover(this->ptr, b - static_cast<const T *>(this->begin()), this->size); + 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; + } - // destroy the elements we're erasing - do { - // Exceptions or not, dtor called once per instance - ++this->ptr; - (b++)->~T(); - } while (b != e); + 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; } }; @@ -1035,485 +901,83 @@ 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; - using iterator = typename Base::iterator; - using const_iterator = typename Base::const_iterator; protected: using Self = QCommonArrayOps<T>; - // Tag dispatched helper functions - inline void adjustPointer(GrowsBackwardsTag, size_t distance) noexcept - { - this->ptr -= distance; - } - inline void adjustPointer(GrowsForwardTag, size_t distance) noexcept - { - this->ptr += distance; - } - qsizetype freeSpace(GrowsBackwardsTag) const noexcept { return this->freeSpaceAtBegin(); } - qsizetype freeSpace(GrowsForwardTag) const noexcept { return this->freeSpaceAtEnd(); } - - struct RelocatableMoveOps - { - // The necessary evil. Performs move "to the left" when grows backwards and - // move "to the right" when grows forward - template<typename GrowthTag> - static void moveInGrowthDirection(GrowthTag tag, Self *this_, size_t futureGrowth) - { - Q_ASSERT(this_->isMutable()); - Q_ASSERT(!this_->isShared()); - Q_ASSERT(futureGrowth <= size_t(this_->freeSpace(tag))); - - const auto oldBegin = this_->begin(); - this_->adjustPointer(tag, futureGrowth); - - // Note: move all elements! - ::memmove(static_cast<void *>(this_->begin()), static_cast<const void *>(oldBegin), - this_->size * sizeof(T)); - } - }; - - struct GenericMoveOps - { - template <typename ...Args> - static void createInPlace(T *where, Args&&... args) - { - new (where) T(std::forward<Args>(args)...); - } - - template <typename ...Args> - static void createInPlace(std::reverse_iterator<iterator> where, Args&&... args) - { - // Note: instead of std::addressof(*where) - createInPlace(where.base() - 1, std::forward<Args>(args)...); - } - - // Moves non-pod data range. Handles overlapping regions. By default, expect - // this method to perform move to the _right_. When move to the _left_ is - // needed, use reverse iterators. - template<typename GrowthTag, typename It> - static void moveNonPod(GrowthTag, Self *this_, It where, It begin, It end) - { - Q_ASSERT(begin <= end); - Q_ASSERT(where > begin); // move to the right - - using Destructor = typename QArrayExceptionSafetyPrimitives<T>::template Destructor<It>; - - auto start = where + std::distance(begin, end); - auto e = end; - - Destructor destroyer(start); // Keep track of added items - - auto [oldRangeEnd, overlapStart] = std::minmax(where, end); - - // step 1. move-initialize elements in uninitialized memory region - while (start != overlapStart) { - --e; - createInPlace(start - 1, std::move_if_noexcept(*e)); - // change tracked iterator only after creation succeeded - avoid - // destructing partially constructed objects if exception thrown - --start; - } - - // re-created the range. now there is an initialized memory region - // somewhere in the allocated area. if something goes wrong, we must - // clean it up, so "freeze" the position for now (cannot commit yet) - destroyer.freeze(); - - // step 2. move assign over existing elements in the overlapping - // region (if there's an overlap) - while (e != begin) { - --start; - --e; - *start = std::move_if_noexcept(*e); - } - - // step 3. destroy elements in the old range - const qsizetype originalSize = this_->size; - start = begin; // delete elements in reverse order to prevent any gaps - while (start != oldRangeEnd) { - // Exceptions or not, dtor called once per instance - if constexpr (std::is_same_v<std::decay_t<GrowthTag>, GrowsForwardTag>) - ++this_->ptr; - --this_->size; - (start++)->~T(); - } - - destroyer.commit(); - // restore old size as we consider data move to be done, the pointer - // still has to be adjusted! - this_->size = originalSize; - } - - // Super inefficient function. The necessary evil. Performs move "to - // the left" when grows backwards and move "to the right" when grows - // forward - template<typename GrowthTag> - static void moveInGrowthDirection(GrowthTag tag, Self *this_, size_t futureGrowth) - { - Q_ASSERT(this_->isMutable()); - Q_ASSERT(!this_->isShared()); - Q_ASSERT(futureGrowth <= size_t(this_->freeSpace(tag))); - - if (futureGrowth == 0) // avoid doing anything if there's no need - return; - - // Note: move all elements! - if constexpr (std::is_same_v<std::decay_t<GrowthTag>, GrowsBackwardsTag>) { - auto where = this_->begin() - futureGrowth; - // here, magic happens. instead of having move to the right, we'll - // have move to the left by using reverse iterators - moveNonPod(tag, this_, - std::make_reverse_iterator(where + this_->size), // rwhere - std::make_reverse_iterator(this_->end()), // rbegin - std::make_reverse_iterator(this_->begin())); // rend - this_->ptr = where; - } else { - auto where = this_->begin() + futureGrowth; - moveNonPod(tag, this_, where, this_->begin(), this_->end()); - this_->ptr = where; - } - } - }; - - // Moves all elements in a specific direction by moveSize if available - // free space at one of the ends is smaller than required. Free space - // becomes available at the beginning if grows backwards and at the end - // if grows forward - template<typename GrowthTag> - qsizetype prepareFreeSpace(GrowthTag tag, size_t required, size_t moveSize) - { - Q_ASSERT(this->isMutable() || required == 0); - Q_ASSERT(!this->isShared() || required == 0); - Q_ASSERT(required <= size_t(this->constAllocatedCapacity() - this->size)); - - using MoveOps = std::conditional_t<QTypeInfo<T>::isRelocatable, - RelocatableMoveOps, - GenericMoveOps>; - - // if free space at the end is not enough, we need to move the data, - // move is performed in an inverse direction - if (size_t(freeSpace(tag)) < required) { - using MoveTag = typename InverseTag<std::decay_t<GrowthTag>>::tag; - MoveOps::moveInGrowthDirection(MoveTag{}, this, moveSize); - - if constexpr (std::is_same_v<MoveTag, GrowsBackwardsTag>) { - return -qsizetype(moveSize); // moving data to the left - } else { - return qsizetype(moveSize); // moving data to the right - } - } - return 0; - } - - // Helper wrapper that adjusts passed iterators along with moving the data - // around. The adjustment is necessary when iterators point inside the - // to-be-moved range - template<typename GrowthTag, typename It> - void prepareFreeSpace(GrowthTag tag, size_t required, size_t moveSize, It &b, It &e) { - // Returns whether passed iterators are inside [this->begin(), this->end()] - const auto iteratorsInRange = [&] (const It &first, const It &last) { - using DecayedIt = std::decay_t<It>; - using RemovedConstVolatileIt = std::remove_cv_t<It>; - constexpr bool selfIterator = - // if passed type is an iterator type: - std::is_same_v<DecayedIt, iterator> - || std::is_same_v<DecayedIt, const_iterator> - // if passed type is a pointer type: - || std::is_same_v<RemovedConstVolatileIt, T *> - || std::is_same_v<RemovedConstVolatileIt, const T *> - || std::is_same_v<RemovedConstVolatileIt, const volatile T *>; - if constexpr (selfIterator) { - return (first >= this->begin() && last <= this->end()); - } else { - return false; - } - }; - - const bool inRange = iteratorsInRange(b, e); - const auto diff = prepareFreeSpace(tag, required, moveSize); - if (inRange) { - std::advance(b, diff); - std::advance(e, diff); - } - } - - size_t moveSizeForAppend(size_t) - { - // Qt5 QList in append: make 100% free space at end if not enough space - // Now: - return this->freeSpaceAtBegin(); - } - - size_t moveSizeForPrepend(size_t required) - { - // Qt5 QList in prepend: make 33% of all space at front if not enough space - // Now: - qsizetype space = this->allocatedCapacity() / 3; - space = qMax(space, qsizetype(required)); // in case required > 33% of all space - return qMin(space, this->freeSpaceAtEnd()); - } - - // Helper functions that reduce usage boilerplate - void prepareSpaceForAppend(size_t required) - { - prepareFreeSpace(GrowsForwardTag{}, required, moveSizeForAppend(required)); - } - void prepareSpaceForPrepend(size_t required) - { - prepareFreeSpace(GrowsBackwardsTag{}, required, moveSizeForPrepend(required)); - } - template<typename It> - void prepareSpaceForAppend(It &b, It &e, size_t required) - { - prepareFreeSpace(GrowsForwardTag{}, required, moveSizeForAppend(required), b, e); - } - template<typename It> - void prepareSpaceForPrepend(It &b, It &e, size_t required) - { - prepareFreeSpace(GrowsBackwardsTag{}, required, moveSizeForPrepend(required), b, e); - } - - // Tells how much of the given size to insert at the beginning of the - // container. This is insert-specific helper function - qsizetype sizeToInsertAtBegin(const T *const where, qsizetype maxSize) - { - Q_ASSERT(maxSize <= this->allocatedCapacity() - this->size); - Q_ASSERT(where >= this->begin() && where <= this->end()); // in range - - const auto freeAtBegin = this->freeSpaceAtBegin(); - const auto freeAtEnd = this->freeSpaceAtEnd(); - - // Idea: * if enough space on both sides, try to affect less elements - // * if enough space on one of the sides, use only that side - // * otherwise, split between front and back (worst case) - if (freeAtBegin >= maxSize && freeAtEnd >= maxSize) { - if (where - this->begin() < this->end() - where) { - return maxSize; - } else { - return 0; - } - } else if (freeAtBegin >= maxSize) { - return maxSize; - } else if (freeAtEnd >= maxSize) { - return 0; - } else { - return maxSize - freeAtEnd; - } - } - public: - // Returns whether reallocation is desirable before adding more elements - // into the container. This is a helper function that one can use to - // theoretically improve average operations performance. Ignoring this - // function does not affect the correctness of the array operations. - bool shouldGrowBeforeInsert(const_iterator where, qsizetype n) const noexcept - { - if (this->d == nullptr) - return true; - if (this->d->flags & QArrayData::CapacityReserved) - return false; - if (!(this->d->flags & (QArrayData::GrowsForward | QArrayData::GrowsBackwards))) - return false; - Q_ASSERT(where >= this->begin() && where <= this->end()); // in range - - const qsizetype freeAtBegin = this->freeSpaceAtBegin(); - const qsizetype freeAtEnd = this->freeSpaceAtEnd(); - const qsizetype capacity = this->constAllocatedCapacity(); - - if (this->size > 0 && where == this->begin()) { // prepend - // Qt5 QList in prepend: not enough space at begin && 33% full - // Now (below): - return freeAtBegin < n && (this->size >= (capacity / 3)); - } - - if (where == this->end()) { // append - // Qt5 QList in append: not enough space at end && less than 66% free space at front - // Now (below): - return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3)); - } - - // Qt5 QList in insert: no free space - // Now: no free space OR not enough space on either of the sides (bad perf. case) - return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n); - } - // using Base::truncate; // using Base::destroyAll; // using Base::assign; // using Base::compare; - void appendInitialize(size_t newSize) - { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->isShared()); - Q_ASSERT(newSize > size_t(this->size)); - Q_ASSERT(newSize <= size_t(this->allocatedCapacity())); - - // Since this is mostly an initialization function, do not follow append - // logic of space arrangement. Instead, only prepare as much free space - // as needed for this specific operation - const size_t n = newSize - this->size; - prepareFreeSpace(GrowsForwardTag{}, n, - qMin(n, size_t(this->freeSpaceAtBegin()))); // ### perf. loss - - Base::appendInitialize(newSize); - } - - void copyAppend(const T *b, const T *e) - { - Q_ASSERT(this->isMutable() || b == e); - Q_ASSERT(!this->isShared() || b == e); - Q_ASSERT(b <= e); - Q_ASSERT((e - b) <= this->allocatedCapacity() - this->size); - if (b == e) // short-cut and handling the case b and e == nullptr - return; - - prepareSpaceForAppend(b, e, e - b); // ### perf. loss - Base::insert(GrowsForwardTag{}, this->end(), b, e); - } - template<typename It> - void copyAppend(It b, It e, QtPrivate::IfIsForwardIterator<It> = true, - QtPrivate::IfIsNotSame<std::decay_t<It>, iterator> = true, - QtPrivate::IfIsNotSame<std::decay_t<It>, const_iterator> = true) + 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); - - prepareSpaceForAppend(b, e, distance); // ### perf. loss - - T *iter = this->end(); - for (; b != e; ++iter, ++b) { - new (iter) T(*b); - ++this->size; - } - } - - 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->allocatedCapacity() - this->size); - if (b == e) // short-cut and handling the case b and e == nullptr - return; - - prepareSpaceForAppend(b, e, e - b); // ### perf. loss - Base::moveAppend(b, e); - } - - void copyAppend(size_t n, parameter_type t) - { - Q_ASSERT(!this->isShared() || n == 0); - Q_ASSERT(size_t(this->allocatedCapacity() - this->size) >= n); - - // Preserve the value, because it might be a reference to some part of the moved chunk - T tmp(t); - prepareSpaceForAppend(n); // ### perf. loss - Base::insert(GrowsForwardTag{}, this->end(), n, tmp); - } - - void insert(T *where, const T *b, const T *e) - { - Q_ASSERT(this->isMutable() || (b == e && where == this->end())); - Q_ASSERT(!this->isShared() || (b == e && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(b <= e); - Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append - Q_ASSERT((e - b) <= this->allocatedCapacity() - this->size); - if (b == e) // short-cut and handling the case b and e == nullptr - return; - - if (this->size > 0 && where == this->begin()) { // prepend case - special space arrangement - prepareSpaceForPrepend(b, e, e - b); // ### perf. loss - Base::insert(GrowsBackwardsTag{}, this->begin(), b, e); - return; - } else if (where == this->end()) { // append case - special space arrangement - copyAppend(b, e); - return; + 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; + } } - - // Insert elements based on the divided distance. Good case: only 1 - // insert happens (either to the front part or to the back part). Bad - // case: both inserts happen, meaning that we touch all N elements in - // the container (this should be handled "outside" by ensuring enough - // free space by reallocating more frequently) - const auto k = sizeToInsertAtBegin(where, e - b); - Base::insert(GrowsBackwardsTag{}, where, b, b + k); - Base::insert(GrowsForwardTag{}, where, b + k, e); } - void insert(T *where, size_t n, parameter_type t) + // slightly higher level API than copyAppend() that also preallocates space + void growAppend(const T *b, const T *e) { - Q_ASSERT(!this->isShared() || (n == 0 && where == this->end())); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(size_t(this->allocatedCapacity() - this->size) >= n); - - if (this->size > 0 && where == this->begin()) { // prepend case - special space arrangement - // Preserve the value, because it might be a reference to some part of the moved chunk - T tmp(t); - prepareSpaceForPrepend(n); // ### perf. loss - Base::insert(GrowsBackwardsTag{}, this->begin(), n, tmp); - return; - } else if (where == this->end()) { // append case - special space arrangement - copyAppend(n, t); + if (b == e) return; - } + Q_ASSERT(b < e); + const qsizetype n = e - b; + DataPointer old; - // Insert elements based on the divided distance. Good case: only 1 - // insert happens (either to the front part or to the back part). Bad - // case: both inserts happen, meaning that we touch all N elements in - // the container (this should be handled "outside" by ensuring enough - // free space by reallocating more frequently) - const auto beginSize = sizeToInsertAtBegin(where, qsizetype(n)); - Base::insert(GrowsBackwardsTag{}, where, beginSize, t); - Base::insert(GrowsForwardTag{}, where, qsizetype(n) - beginSize, t); + // 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); } - template <typename iterator, typename ...Args> - void emplace(iterator where, Args&&... args) + void appendUninitialized(qsizetype newSize) { + Q_ASSERT(this->isMutable()); Q_ASSERT(!this->isShared()); - Q_ASSERT(where >= this->begin() && where <= this->end()); - Q_ASSERT(this->allocatedCapacity() - this->size >= 1); - - // Qt5 QList in insert(1): try to move less data around - // Now: - const bool shouldInsertAtBegin = (where - this->begin()) < (this->end() - where) - || this->freeSpaceAtEnd() <= 0; - if (this->freeSpaceAtBegin() > 0 && shouldInsertAtBegin) { - Base::emplace(GrowsBackwardsTag{}, where, std::forward<Args>(args)...); - } else { - Base::emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...); - } - } - - template <typename ...Args> - void emplaceBack(Args&&... args) - { - this->emplace(this->end(), std::forward<Args>(args)...); - } + Q_ASSERT(newSize > this->size); + Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd()); - 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()); + T *const b = this->begin(); + do { + auto ptr = b + 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. - if (b == this->begin()) { - Base::erase(GrowsBackwardsTag{}, b, e); - } else { - Base::erase(GrowsForwardTag{}, b, e); - } + 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); } }; |