diff options
Diffstat (limited to 'src/corelib/tools/qarraydatapointer.h')
| -rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 487 |
1 files changed, 358 insertions, 129 deletions
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index ad5acdb7fd..6657d40cf9 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -1,41 +1,5 @@ -/**************************************************************************** -** -** Copyright (C) 2020 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. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only #ifndef QARRAYDATAPOINTER_H #define QARRAYDATAPOINTER_H @@ -43,6 +7,9 @@ #include <QtCore/qarraydataops.h> #include <QtCore/qcontainertools_impl.h> +#include <QtCore/q20functional.h> +#include <QtCore/q20memory.h> + QT_BEGIN_NAMESPACE template <class T> @@ -53,33 +20,46 @@ private: typedef QArrayDataOps<T> DataOps; public: - typedef typename Data::iterator iterator; - typedef typename Data::const_iterator const_iterator; - enum { pass_parameter_by_value = std::is_fundamental<T>::value || std::is_pointer<T>::value }; + enum { + pass_parameter_by_value = + std::is_arithmetic<T>::value || std::is_pointer<T>::value || std::is_enum<T>::value + }; typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type; + Q_NODISCARD_CTOR constexpr QArrayDataPointer() noexcept : d(nullptr), ptr(nullptr), size(0) { } + Q_NODISCARD_CTOR QArrayDataPointer(const QArrayDataPointer &other) noexcept : d(other.d), ptr(other.ptr), size(other.size) { ref(); } + Q_NODISCARD_CTOR constexpr QArrayDataPointer(Data *header, T *adata, qsizetype n = 0) noexcept : d(header), ptr(adata), size(n) { } - explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, qsizetype n = 0) noexcept + Q_NODISCARD_CTOR + explicit QArrayDataPointer(std::pair<QTypedArrayData<T> *, T *> adata, qsizetype n = 0) noexcept : d(adata.first), ptr(adata.second), size(n) { } + Q_NODISCARD_CTOR explicit + QArrayDataPointer(qsizetype alloc, qsizetype n = 0, + QArrayData::AllocationOption option = QArrayData::KeepSize) + : QArrayDataPointer(Data::allocate(alloc, option), n) + { + } + + Q_NODISCARD_CTOR static QArrayDataPointer fromRawData(const T *rawData, qsizetype length) noexcept { Q_ASSERT(rawData || !length); @@ -93,20 +73,15 @@ public: return *this; } + Q_NODISCARD_CTOR QArrayDataPointer(QArrayDataPointer &&other) noexcept - : d(other.d), ptr(other.ptr), size(other.size) + : d(std::exchange(other.d, nullptr)), + ptr(std::exchange(other.ptr, nullptr)), + size(std::exchange(other.size, 0)) { - other.d = nullptr; - other.ptr = nullptr; - other.size = 0; } - QArrayDataPointer &operator=(QArrayDataPointer &&other) noexcept - { - QArrayDataPointer moved(std::move(other)); - swap(moved); - return *this; - } + QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QArrayDataPointer) DataOps &operator*() noexcept { @@ -132,7 +107,7 @@ public: { if (!deref()) { (*this)->destroyAll(); - Data::deallocate(d); + free(d); } } @@ -144,18 +119,18 @@ public: T *data() noexcept { return ptr; } const T *data() const noexcept { return ptr; } - iterator begin(iterator = iterator()) noexcept { return data(); } - iterator end(iterator = iterator()) noexcept { return data() + size; } - const_iterator begin(const_iterator = const_iterator()) const noexcept { return data(); } - const_iterator end(const_iterator = const_iterator()) const noexcept { return data() + size; } - const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return data(); } - const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return data() + size; } + T *begin() noexcept { return data(); } + T *end() noexcept { return data() + size; } + const T *begin() const noexcept { return data(); } + const T *end() const noexcept { return data() + size; } + const T *constBegin() const noexcept { return data(); } + const T *constEnd() const noexcept { return data() + size; } void swap(QArrayDataPointer &other) noexcept { - qSwap(d, other.d); - qSwap(ptr, other.ptr); - qSwap(size, other.size); + qt_ptr_swap(d, other.d); + qt_ptr_swap(ptr, other.ptr); + std::swap(size, other.size); } void clear() noexcept(std::is_nothrow_destructible<T>::value) @@ -164,33 +139,312 @@ public: swap(tmp); } - bool detach() + void detach(QArrayDataPointer *old = nullptr) + { + if (needsDetach()) + reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old); + } + + /*! \internal + + Reinterprets the data of this QArrayDataPointer to type X. It's the + caller's responsibility to ensure that the data contents are valid and + properly aligned, particularly if T and X are not trivial types (i.e, + don't do that). The current size is kept and the allocated capacity is + updated to account for the difference in the element type's size. + + This is used in QString::fromLatin1 to perform in-place conversion of + QString to QByteArray. + */ + template <typename X> QArrayDataPointer<X> reinterpreted() && + { + if (sizeof(T) != sizeof(X)) { + Q_ASSERT(!d->isShared()); + d->alloc = d->alloc * sizeof(T) / sizeof(X); + } + auto od = reinterpret_cast<QTypedArrayData<X> *>(std::exchange(d, nullptr)); + auto optr = reinterpret_cast<X *>(std::exchange(ptr, nullptr)); + return { od, optr, std::exchange(size, 0) }; + } + + /*! \internal + + Detaches this (optionally) and grows to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + \a data pointer can be provided when the caller knows that \a data + points into range [this->begin(), this->end()). In case it is, *data + would be updated so that it continues to point to the element it was + pointing to before the data move. if \a data does not point into range, + one can/should pass \c nullptr. + + Similarly to \a data, \a old, pointer to a default-constructed QADP, can + be provided when the caller expects to e.g. copy the data from this to + itself: + \code + QList<T> list(5); + qsizetype pos = getArbitraryPos(); + list.insert(pos, list.begin(), list.end()); + \endcode + + The default rule would be: \a data and \a old must either both be valid + pointers, or both equal to \c nullptr. + */ + void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data, + QArrayDataPointer *old) + { + const bool detach = needsDetach(); + bool readjusted = false; + if (!detach) { + if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)) + return; + readjusted = tryReadjustFreeSpace(where, n, data); + Q_ASSERT(!readjusted + || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) + || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n)); + } + + if (!readjusted) + reallocateAndGrow(where, n, old); + } + + /*! \internal + + Reallocates to accommodate the free space for \a n elements at the + required side. The side is determined from \a pos. Might also shrink + when n < 0. + */ + Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, + QArrayDataPointer *old = nullptr) + { + if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) { + if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) { + (*this)->reallocate(constAllocatedCapacity() - freeSpaceAtEnd() + n, QArrayData::Grow); // fast path + return; + } + } + + QArrayDataPointer dp(allocateGrow(*this, n, where)); + if (n > 0) + Q_CHECK_PTR(dp.data()); + if (where == QArrayData::GrowsAtBeginning) { + Q_ASSERT(dp.freeSpaceAtBegin() >= n); + } else { + Q_ASSERT(dp.freeSpaceAtEnd() >= n); + } + if (size) { + qsizetype toCopy = size; + if (n < 0) + toCopy += n; + if (needsDetach() || old) + dp->copyAppend(begin(), begin() + toCopy); + else + dp->moveAppend(begin(), begin() + toCopy); + Q_ASSERT(dp.size == toCopy); + } + + swap(dp); + if (old) + old->swap(dp); + } + + /*! \internal + + Attempts to relocate [begin(), end()) to accommodate the free space for + \a n elements at the required side. The side is determined from \a pos. + + Returns \c true if the internal data is moved. Returns \c false when + there is no point in moving the data or the move is impossible. If \c + false is returned, it is the responsibility of the caller to figure out + how to accommodate the free space for \a n elements at \a pos. + + This function expects that certain preconditions are met, e.g. the + detach is not needed, n > 0 and so on. This is intentional to reduce the + number of if-statements when the caller knows that preconditions would + be satisfied. + + \sa reallocateAndGrow + */ + bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr) + { + Q_ASSERT(!this->needsDetach()); + Q_ASSERT(n > 0); + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n)); + + const qsizetype capacity = this->constAllocatedCapacity(); + const qsizetype freeAtBegin = this->freeSpaceAtBegin(); + const qsizetype freeAtEnd = this->freeSpaceAtEnd(); + + qsizetype dataStartOffset = 0; + // algorithm: + // a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3 + // [all goes to free space at end]: + // new free space at begin = 0 + // + // b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3 + // [balance the free space]: + // new free space at begin = n + (total free space - n) / 2 + if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n + && ((3 * this->size) < (2 * capacity))) { + // dataStartOffset = 0; - done in declaration + } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n + && ((3 * this->size) < capacity)) { + // total free space == capacity - size + dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2); + } else { + // nothing to do otherwise + return false; + } + + relocate(dataStartOffset - freeAtBegin, data); + + Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n) + || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n)); + return true; + } + + /*! \internal + + Relocates [begin(), end()) by \a offset and updates \a data if it is not + \c nullptr and points into [begin(), end()). + */ + void relocate(qsizetype offset, const T **data = nullptr) + { + T *res = this->ptr + offset; + QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res); + // first update data pointer, then this->ptr + if (data && QtPrivate::q_points_into_range(*data, *this)) + *data += offset; + this->ptr = res; + } + + template <typename InputIterator, typename Projection = q20::identity> + void assign(InputIterator first, InputIterator last, Projection proj = {}) { - if (needsDetach()) { - QPair<Data *, T *> copy = clone(detachFlags()); - QArrayDataPointer old(d, ptr, size); - d = copy.first; - ptr = copy.second; - return true; + // This function only provides the basic exception guarantee. + constexpr bool IsFwdIt = std::is_convertible_v< + typename std::iterator_traits<InputIterator>::iterator_category, + std::forward_iterator_tag>; + constexpr bool IsIdentity = std::is_same_v<Projection, q20::identity>; + + if constexpr (IsFwdIt) { + const qsizetype n = std::distance(first, last); + if (needsDetach() || n > constAllocatedCapacity()) { + QArrayDataPointer allocated(detachCapacity(n)); + swap(allocated); + } + } else if (needsDetach()) { + QArrayDataPointer allocated(allocatedCapacity()); + swap(allocated); + // We don't want to copy data that we know we'll overwrite + } + + auto offset = freeSpaceAtBegin(); + const auto capacityBegin = begin() - offset; + const auto prependBufferEnd = begin(); + + if constexpr (!std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>) { + // If construction can throw, and we have freeSpaceAtBegin(), + // it's easiest to just clear the container and start fresh. + // The alternative would be to keep track of two active, disjoint ranges. + if (offset) { + (*this)->truncate(0); + setBegin(capacityBegin); + offset = 0; + } } - return false; + auto dst = capacityBegin; + const auto dend = end(); + if (offset) { // avoids dead stores + setBegin(capacityBegin); // undo prepend optimization + + // By construction, the following loop is nothrow! + // (otherwise, we can't reach here) + // Assumes InputIterator operations don't throw. + // (but we can't statically assert that, as these operations + // have preconditons, so typically aren't noexcept) + while (true) { + if (dst == prependBufferEnd) { // ran out of prepend buffer space + size += offset; + // we now have a contiguous buffer, continue with the main loop: + break; + } + if (first == last) { // ran out of elements to assign + std::destroy(prependBufferEnd, dend); + size = dst - begin(); + return; + } + // construct element in prepend buffer + q20::construct_at(dst, std::invoke(proj, *first)); + ++dst; + ++first; + } + } + + while (true) { + if (first == last) { // ran out of elements to assign + std::destroy(dst, dend); + break; + } + if (dst == dend) { // ran out of existing elements to overwrite + if constexpr (IsFwdIt && IsIdentity) { + dst = std::uninitialized_copy(first, last, dst); + break; + } else if constexpr (IsFwdIt && !IsIdentity + && std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>) { + for (; first != last; ++dst, ++first) // uninitialized_copy with projection + q20::construct_at(dst, std::invoke(proj, *first)); + break; + } else { + do { + (*this)->emplace(size, std::invoke(proj, *first)); + } while (++first != last); + return; // size() is already correct (and dst invalidated)! + } + } + *dst = std::invoke(proj, *first); // overwrite existing element + ++dst; + ++first; + } + size = dst - begin(); + } + + QArrayDataPointer sliced(qsizetype pos, qsizetype n) const & + { + QArrayDataPointer result(n); + std::uninitialized_copy_n(begin() + pos, n, result.begin()); + result.size = n; + return result; + } + + QArrayDataPointer sliced(qsizetype pos, qsizetype n) && + { + if (needsDetach()) + return sliced(pos, n); + T *newBeginning = begin() + pos; + std::destroy(begin(), newBeginning); + std::destroy(newBeginning + n, end()); + setBegin(newBeginning); + size = n; + return std::move(*this); } // forwards from QArrayData - size_t allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; } - size_t constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; } + qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; } + qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; } void ref() noexcept { if (d) d->ref(); } bool deref() noexcept { return !d || d->deref(); } bool isMutable() const noexcept { return d; } bool isShared() const noexcept { return !d || d->isShared(); } bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; } bool needsDetach() const noexcept { return !d || d->needsDetach(); } - size_t detachCapacity(size_t newSize) const noexcept { return d ? d->detachCapacity(newSize) : newSize; } - const typename Data::ArrayOptions flags() const noexcept { return d ? typename Data::ArrayOption(d->flags) : Data::DefaultAllocationFlags; } + qsizetype detachCapacity(qsizetype newSize) const noexcept { return d ? d->detachCapacity(newSize) : newSize; } + const typename Data::ArrayOptions flags() const noexcept { return d ? d->flags : Data::ArrayOptionDefault; } void setFlag(typename Data::ArrayOptions f) noexcept { Q_ASSERT(d); d->flags |= f; } - void clearFlag(typename Data::ArrayOptions f) noexcept { Q_ASSERT(d); d->flags &= ~f; } - typename Data::ArrayOptions detachFlags() const noexcept { return d ? d->detachFlags() : Data::DefaultAllocationFlags; } + void clearFlag(typename Data::ArrayOptions f) noexcept { if (d) d->flags &= ~f; } Data *d_ptr() noexcept { return d; } void setBegin(T *begin) noexcept { ptr = begin; } @@ -209,75 +463,50 @@ public: return d->constAllocatedCapacity() - freeSpaceAtBegin() - this->size; } - static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, - qsizetype newSize, QArrayData::ArrayOptions options) + // allocate and grow. Ensure that at the minimum requiredSpace is available at the requested end + static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype n, QArrayData::GrowthPosition position) { - return allocateGrow(from, from.detachCapacity(newSize), newSize, options); - } - - static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype capacity, - qsizetype newSize, QArrayData::ArrayOptions options) - { - auto [header, dataPtr] = Data::allocate(capacity, options); + // calculate new capacity. We keep the free capacity at the side that does not have to grow + // to avoid quadratic behavior with mixed append/prepend cases + + // use qMax below, because constAllocatedCapacity() can be 0 when using fromRawData() + qsizetype minimalCapacity = qMax(from.size, from.constAllocatedCapacity()) + n; + // subtract the free space at the side we want to allocate. This ensures that the total size requested is + // the existing allocation at the other side + size + n. + minimalCapacity -= (position == QArrayData::GrowsAtEnd) ? from.freeSpaceAtEnd() : from.freeSpaceAtBegin(); + qsizetype capacity = from.detachCapacity(minimalCapacity); + const bool grows = capacity > from.constAllocatedCapacity(); + auto [header, dataPtr] = Data::allocate(capacity, grows ? QArrayData::Grow : QArrayData::KeepSize); const bool valid = header != nullptr && dataPtr != nullptr; - const bool grows = (options & (Data::GrowsForward | Data::GrowsBackwards)); - if (!valid || !grows) + if (!valid) return QArrayDataPointer(header, dataPtr); - // when growing, special rules apply to memory layout - - if (from.needsDetach()) { - // When detaching: the free space reservation is biased towards - // append as in Qt5 QList. If we're growing backwards, put the data - // in the middle instead of at the end - assuming that prepend is - // uncommon and even initial prepend will eventually be followed by - // at least some appends. - if (options & Data::GrowsBackwards) - dataPtr += (header->alloc - newSize) / 2; - } else { - // When not detaching: fake ::realloc() policy - preserve existing - // free space at beginning. - dataPtr += from.freeSpaceAtBegin(); - } + // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning + // * when growing forward, adjust by the previous data pointer offset + dataPtr += (position == QArrayData::GrowsAtBeginning) + ? n + qMax(0, (header->alloc - from.size - n) / 2) + : from.freeSpaceAtBegin(); + header->flags = from.flags(); return QArrayDataPointer(header, dataPtr); } -private: - Q_REQUIRED_RESULT QPair<Data *, T *> clone(QArrayData::ArrayOptions options) const + friend bool operator==(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept { - QPair<Data *, T *> pair = Data::allocate(detachCapacity(size), options); - QArrayDataPointer copy(pair.first, pair.second, 0); - if (size) - copy->copyAppend(begin(), end()); - - pair.first = copy.d; - copy.d = nullptr; - copy.ptr = nullptr; - return pair; + return lhs.data() == rhs.data() && lhs.size == rhs.size; + } + + friend bool operator!=(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept + { + return lhs.data() != rhs.data() || lhs.size != rhs.size; } -protected: Data *d; T *ptr; - -public: qsizetype size; }; template <class T> -inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept -{ - return lhs.data() == rhs.data() && lhs.size == rhs.size; -} - -template <class T> -inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept -{ - return lhs.data() != rhs.data() || lhs.size != rhs.size; -} - -template <class T> -inline void qSwap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept +inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept { p1.swap(p2); } |