include/QtCore/qarraydatapointer.h

0001 // Copyright (C) 2020 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QARRAYDATAPOINTER_H
0005 #define QARRAYDATAPOINTER_H
0006
0007 #include <QtCore/qarraydataops.h>
0008 #include <QtCore/qcontainertools_impl.h>
0009
0010 #include <QtCore/q20functional.h>
0011 #include <QtCore/q20memory.h>
0012
0013 QT_BEGIN_NAMESPACE
0014
0015 template <class T>
0016 struct QArrayDataPointer
0017 {
0018 private:
0019     typedef QTypedArrayData<T> Data;
0020     typedef QArrayDataOps<T> DataOps;
0021
0022 public:
0023     enum {
0024         pass_parameter_by_value =
0025                 std::is_arithmetic<T>::value || std::is_pointer<T>::value || std::is_enum<T>::value
0026     };
0027
0028     typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type;
0029
0030     Q_NODISCARD_CTOR
0031     constexpr QArrayDataPointer() noexcept
0032         : d(nullptr), ptr(nullptr), size(0)
0033     {
0034     }
0035
0036     Q_NODISCARD_CTOR
0037     QArrayDataPointer(const QArrayDataPointer &other) noexcept
0038         : d(other.d), ptr(other.ptr), size(other.size)
0039     {
0040         ref();
0041     }
0042
0043     Q_NODISCARD_CTOR
0044     constexpr QArrayDataPointer(Data *header, T *adata, qsizetype n = 0) noexcept
0045         : d(header), ptr(adata), size(n)
0046     {
0047     }
0048
0049     Q_NODISCARD_CTOR
0050     explicit QArrayDataPointer(std::pair<QTypedArrayData<T> *, T *> adata, qsizetype n = 0) noexcept
0051         : d(adata.first), ptr(adata.second), size(n)
0052     {
0053     }
0054
0055     Q_NODISCARD_CTOR explicit
0056     QArrayDataPointer(qsizetype alloc, qsizetype n = 0,
0057                       QArrayData::AllocationOption option = QArrayData::KeepSize)
0058         : QArrayDataPointer(Data::allocate(alloc, option), n)
0059     {
0060     }
0061
0062     Q_NODISCARD_CTOR
0063     static QArrayDataPointer fromRawData(const T *rawData, qsizetype length) noexcept
0064     {
0065         Q_ASSERT(rawData || !length);
0066         return { nullptr, const_cast<T *>(rawData), length };
0067     }
0068
0069     QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept
0070     {
0071         QArrayDataPointer tmp(other);
0072         this->swap(tmp);
0073         return *this;
0074     }
0075
0076     Q_NODISCARD_CTOR
0077     QArrayDataPointer(QArrayDataPointer &&other) noexcept
0078         : d(std::exchange(other.d, nullptr)),
0079           ptr(std::exchange(other.ptr, nullptr)),
0080           size(std::exchange(other.size, 0))
0081     {
0082     }
0083
0084     QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_MOVE_AND_SWAP(QArrayDataPointer)
0085
0086     DataOps &operator*() noexcept
0087     {
0088         return *static_cast<DataOps *>(this);
0089     }
0090
0091     DataOps *operator->() noexcept
0092     {
0093         return static_cast<DataOps *>(this);
0094     }
0095
0096     const DataOps &operator*() const noexcept
0097     {
0098         return *static_cast<const DataOps *>(this);
0099     }
0100
0101     const DataOps *operator->() const noexcept
0102     {
0103         return static_cast<const DataOps *>(this);
0104     }
0105
0106     ~QArrayDataPointer()
0107     {
0108         if (!deref()) {
0109             (*this)->destroyAll();
0110             Data::deallocate(d);
0111         }
0112     }
0113
0114     constexpr bool isNull() const noexcept
0115     {
0116         return !ptr;
0117     }
0118
0119     T *data() noexcept { return ptr; }
0120     const T *data() const noexcept { return ptr; }
0121
0122     T *begin() noexcept { return data(); }
0123     T *end() noexcept { return data() + size; }
0124     const T *begin() const noexcept { return data(); }
0125     const T *end() const noexcept { return data() + size; }
0126     const T *constBegin() const noexcept { return data(); }
0127     const T *constEnd() const noexcept { return data() + size; }
0128
0129     void swap(QArrayDataPointer &other) noexcept
0130     {
0131         qt_ptr_swap(d, other.d);
0132         qt_ptr_swap(ptr, other.ptr);
0133         std::swap(size, other.size);
0134     }
0135
0136     void clear() noexcept(std::is_nothrow_destructible<T>::value)
0137     {
0138         QArrayDataPointer tmp;
0139         swap(tmp);
0140     }
0141
0142     void detach(QArrayDataPointer *old = nullptr)
0143     {
0144         if (needsDetach())
0145             reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old);
0146     }
0147
0148     /*! \internal
0149
0150         Reinterprets the data of this QArrayDataPointer to type X. It's the
0151         caller's responsibility to ensure that the data contents are valid and
0152         properly aligned, particularly if T and X are not trivial types (i.e,
0153         don't do that). The current size is kept and the allocated capacity is
0154         updated to account for the difference in the element type's size.
0155
0156         This is used in QString::fromLatin1 to perform in-place conversion of
0157         QString to QByteArray.
0158     */
0159     template <typename X> QArrayDataPointer<X> reinterpreted() &&
0160     {
0161         if (sizeof(T) != sizeof(X)) {
0162             Q_ASSERT(!d->isShared());
0163             d->alloc = d->alloc * sizeof(T) / sizeof(X);
0164         }
0165         auto od = reinterpret_cast<QTypedArrayData<X> *>(std::exchange(d, nullptr));
0166         auto optr = reinterpret_cast<X *>(std::exchange(ptr, nullptr));
0167         return { od, optr, std::exchange(size, 0) };
0168     }
0169
0170     /*! \internal
0171
0172         Detaches this (optionally) and grows to accommodate the free space for
0173         \a n elements at the required side. The side is determined from \a pos.
0174
0175         \a data pointer can be provided when the caller knows that \a data
0176         points into range [this->begin(), this->end()). In case it is, *data
0177         would be updated so that it continues to point to the element it was
0178         pointing to before the data move. if \a data does not point into range,
0179         one can/should pass \c nullptr.
0180
0181         Similarly to \a data, \a old, pointer to a default-constructed QADP, can
0182         be provided when the caller expects to e.g. copy the data from this to
0183         itself:
0184         \code
0185         QList<T> list(5);
0186         qsizetype pos = getArbitraryPos();
0187         list.insert(pos, list.begin(), list.end());
0188         \endcode
0189
0190         The default rule would be: \a data and \a old must either both be valid
0191         pointers, or both equal to \c nullptr.
0192     */
0193     void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data,
0194                        QArrayDataPointer *old)
0195     {
0196         const bool detach = needsDetach();
0197         bool readjusted = false;
0198         if (!detach) {
0199             if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
0200                 || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n))
0201                 return;
0202             readjusted = tryReadjustFreeSpace(where, n, data);
0203             Q_ASSERT(!readjusted
0204                      || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
0205                      || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n));
0206         }
0207
0208         if (!readjusted)
0209             reallocateAndGrow(where, n, old);
0210     }
0211
0212     /*! \internal
0213
0214         Reallocates to accommodate the free space for \a n elements at the
0215         required side. The side is determined from \a pos. Might also shrink
0216         when n < 0.
0217     */
0218     Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n,
0219                                           QArrayDataPointer *old = nullptr)
0220     {
0221         if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) {
0222             if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) {
0223                 (*this)->reallocate(constAllocatedCapacity() - freeSpaceAtEnd() + n, QArrayData::Grow); // fast path
0224                 return;
0225             }
0226         }
0227
0228         QArrayDataPointer dp(allocateGrow(*this, n, where));
0229         if (n > 0)
0230             Q_CHECK_PTR(dp.data());
0231         if (where == QArrayData::GrowsAtBeginning) {
0232             Q_ASSERT(dp.freeSpaceAtBegin() >= n);
0233         } else {
0234             Q_ASSERT(dp.freeSpaceAtEnd() >= n);
0235         }
0236         if (size) {
0237             qsizetype toCopy = size;
0238             if (n < 0)
0239                 toCopy += n;
0240             if (needsDetach() || old)
0241                 dp->copyAppend(begin(), begin() + toCopy);
0242             else
0243                 dp->moveAppend(begin(), begin() + toCopy);
0244             Q_ASSERT(dp.size == toCopy);
0245         }
0246
0247         swap(dp);
0248         if (old)
0249             old->swap(dp);
0250     }
0251
0252     /*! \internal
0253
0254         Attempts to relocate [begin(), end()) to accommodate the free space for
0255         \a n elements at the required side. The side is determined from \a pos.
0256
0257         Returns \c true if the internal data is moved. Returns \c false when
0258         there is no point in moving the data or the move is impossible. If \c
0259         false is returned, it is the responsibility of the caller to figure out
0260         how to accommodate the free space for \a n elements at \a pos.
0261
0262         This function expects that certain preconditions are met, e.g. the
0263         detach is not needed, n > 0 and so on. This is intentional to reduce the
0264         number of if-statements when the caller knows that preconditions would
0265         be satisfied.
0266
0267         \sa reallocateAndGrow
0268     */
0269     bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr)
0270     {
0271         Q_ASSERT(!this->needsDetach());
0272         Q_ASSERT(n > 0);
0273         Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n)
0274                  || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n));
0275
0276         const qsizetype capacity = this->constAllocatedCapacity();
0277         const qsizetype freeAtBegin = this->freeSpaceAtBegin();
0278         const qsizetype freeAtEnd = this->freeSpaceAtEnd();
0279
0280         qsizetype dataStartOffset = 0;
0281         // algorithm:
0282         //   a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3
0283         //      [all goes to free space at end]:
0284         //      new free space at begin = 0
0285         //
0286         //   b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3
0287         //      [balance the free space]:
0288         //      new free space at begin = n + (total free space - n) / 2
0289         if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n
0290             && ((3 * this->size) < (2 * capacity))) {
0291             // dataStartOffset = 0; - done in declaration
0292         } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n
0293                    && ((3 * this->size) < capacity)) {
0294             // total free space == capacity - size
0295             dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2);
0296         } else {
0297             // nothing to do otherwise
0298             return false;
0299         }
0300
0301         relocate(dataStartOffset - freeAtBegin, data);
0302
0303         Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n)
0304                  || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n));
0305         return true;
0306     }
0307
0308     /*! \internal
0309
0310         Relocates [begin(), end()) by \a offset and updates \a data if it is not
0311         \c nullptr and points into [begin(), end()).
0312     */
0313     void relocate(qsizetype offset, const T **data = nullptr)
0314     {
0315         T *res = this->ptr + offset;
0316         QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res);
0317         // first update data pointer, then this->ptr
0318         if (data && QtPrivate::q_points_into_range(*data, *this))
0319             *data += offset;
0320         this->ptr = res;
0321     }
0322
0323     template <typename InputIterator, typename Projection = q20::identity>
0324     void assign(InputIterator first, InputIterator last, Projection proj = {})
0325     {
0326         // This function only provides the basic exception guarantee.
0327         constexpr bool IsFwdIt = std::is_convertible_v<
0328                 typename std::iterator_traits<InputIterator>::iterator_category,
0329                 std::forward_iterator_tag>;
0330         constexpr bool IsIdentity = std::is_same_v<Projection, q20::identity>;
0331
0332         if constexpr (IsFwdIt) {
0333             const qsizetype n = std::distance(first, last);
0334             if (needsDetach() || n > constAllocatedCapacity()) {
0335                 QArrayDataPointer allocated(detachCapacity(n));
0336                 swap(allocated);
0337             }
0338         } else if (needsDetach()) {
0339             QArrayDataPointer allocated(allocatedCapacity());
0340             swap(allocated);
0341             // We don't want to copy data that we know we'll overwrite
0342         }
0343
0344         auto offset = freeSpaceAtBegin();
0345         const auto capacityBegin = begin() - offset;
0346         const auto prependBufferEnd = begin();
0347
0348         if constexpr (!std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>
0349                       || !std::is_nothrow_invocable_v<Projection, decltype(*first)>)
0350         {
0351             // If construction can throw, and we have freeSpaceAtBegin(),
0352             // it's easiest to just clear the container and start fresh.
0353             // The alternative would be to keep track of two active, disjoint ranges.
0354             if (offset) {
0355                 (*this)->truncate(0);
0356                 setBegin(capacityBegin);
0357                 offset = 0;
0358             }
0359         }
0360
0361         auto dst = capacityBegin;
0362         const auto dend = end();
0363         if (offset) { // avoids dead stores
0364             setBegin(capacityBegin); // undo prepend optimization
0365
0366             // By construction, the following loop is nothrow!
0367             // (otherwise, we can't reach here)
0368             // Assumes InputIterator operations don't throw.
0369             // (but we can't statically assert that, as these operations
0370             //  have preconditons, so typically aren't noexcept)
0371             while (true) {
0372                 if (dst == prependBufferEnd) {  // ran out of prepend buffer space
0373                     size += offset;
0374                     // we now have a contiguous buffer, continue with the main loop:
0375                     break;
0376                 }
0377                 if (first == last) {            // ran out of elements to assign
0378                     std::destroy(prependBufferEnd, dend);
0379                     size = dst - begin();
0380                     return;
0381                 }
0382                 // construct element in prepend buffer
0383                 q20::construct_at(dst, std::invoke(proj, *first));
0384                 ++dst;
0385                 ++first;
0386             }
0387         }
0388
0389         while (true) {
0390             if (first == last) {    // ran out of elements to assign
0391                 std::destroy(dst, dend);
0392                 break;
0393             }
0394             if (dst == dend) {      // ran out of existing elements to overwrite
0395                 if constexpr (IsFwdIt && IsIdentity) {
0396                     dst = std::uninitialized_copy(first, last, dst);
0397                     break;
0398                 } else if constexpr (IsFwdIt && !IsIdentity
0399                            && std::is_nothrow_constructible_v<T, decltype(std::invoke(proj, *first))>
0400                            && std::is_nothrow_invocable_v<Projection, decltype(*first)>)
0401                 {
0402                     for (; first != last; ++dst, ++first)   // uninitialized_copy with projection
0403                         q20::construct_at(dst, std::invoke(proj, *first));
0404                     break;
0405                 } else {
0406                     do {
0407                         (*this)->emplace(size, std::invoke(proj, *first));
0408                     } while (++first != last);
0409                     return;         // size() is already correct (and dst invalidated)!
0410                 }
0411             }
0412             *dst = std::invoke(proj, *first);    // overwrite existing element
0413             ++dst;
0414             ++first;
0415         }
0416         size = dst - begin();
0417     }
0418
0419     QArrayDataPointer sliced(qsizetype pos, qsizetype n) const &
0420     {
0421         QArrayDataPointer result(n);
0422         std::uninitialized_copy_n(begin() + pos, n, result.begin());
0423         result.size = n;
0424         return result;
0425     }
0426
0427     QArrayDataPointer sliced(qsizetype pos, qsizetype n) &&
0428     {
0429         if (needsDetach())
0430             return sliced(pos, n);
0431         T *newBeginning = begin() + pos;
0432         std::destroy(begin(), newBeginning);
0433         std::destroy(newBeginning + n, end());
0434         setBegin(newBeginning);
0435         size = n;
0436         return std::move(*this);
0437     }
0438
0439     void appendInitialize(qsizetype newSize)
0440     {
0441         Q_ASSERT(this->isMutable());
0442         Q_ASSERT(!this->isShared());
0443         Q_ASSERT(newSize > this->size);
0444         Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd());
0445
0446         T *const b = this->begin() + this->size;
0447         T *const e = this->begin() + newSize;
0448         q17::uninitialized_value_construct(b, e);
0449         this->size = newSize;
0450     }
0451
0452     // forwards from QArrayData
0453     qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; }
0454     qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; }
0455     void ref() noexcept { if (d) d->ref(); }
0456     bool deref() noexcept { return !d || d->deref(); }
0457     bool isMutable() const noexcept { return d; } // Returns false if this object is fromRawData()
0458     bool isShared() const noexcept { return !d || d->isShared(); }
0459     bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; }
0460     bool needsDetach() const noexcept { return !d || d->needsDetach(); }
0461     qsizetype detachCapacity(qsizetype newSize) const noexcept { return d ? d->detachCapacity(newSize) : newSize; }
0462     const typename Data::ArrayOptions flags() const noexcept { return d ? d->flags : Data::ArrayOptionDefault; }
0463     void setFlag(typename Data::ArrayOptions f) noexcept { Q_ASSERT(d); d->flags |= f; }
0464     void clearFlag(typename Data::ArrayOptions f) noexcept { if (d) d->flags &= ~f; }
0465
0466     Data *d_ptr() noexcept { return d; }
0467     void setBegin(T *begin) noexcept { ptr = begin; }
0468
0469     qsizetype freeSpaceAtBegin() const noexcept
0470     {
0471         if (d == nullptr)
0472             return 0;
0473         return this->ptr - Data::dataStart(d, alignof(typename Data::AlignmentDummy));
0474     }
0475
0476     qsizetype freeSpaceAtEnd() const noexcept
0477     {
0478         if (d == nullptr)
0479             return 0;
0480         return d->constAllocatedCapacity() - freeSpaceAtBegin() - this->size;
0481     }
0482
0483     // allocate and grow. Ensure that at the minimum requiredSpace is available at the requested end
0484     static QArrayDataPointer allocateGrow(const QArrayDataPointer &from, qsizetype n, QArrayData::GrowthPosition position)
0485     {
0486         // calculate new capacity. We keep the free capacity at the side that does not have to grow
0487         // to avoid quadratic behavior with mixed append/prepend cases
0488
0489         // use qMax below, because constAllocatedCapacity() can be 0 when using fromRawData()
0490         qsizetype minimalCapacity = qMax(from.size, from.constAllocatedCapacity()) + n;
0491         // subtract the free space at the side we want to allocate. This ensures that the total size requested is
0492         // the existing allocation at the other side + size + n.
0493         minimalCapacity -= (position == QArrayData::GrowsAtEnd) ? from.freeSpaceAtEnd() : from.freeSpaceAtBegin();
0494         qsizetype capacity = from.detachCapacity(minimalCapacity);
0495         const bool grows = capacity > from.constAllocatedCapacity();
0496         auto [header, dataPtr] = Data::allocate(capacity, grows ? QArrayData::Grow : QArrayData::KeepSize);
0497         const bool valid = header != nullptr && dataPtr != nullptr;
0498         if (!valid)
0499             return QArrayDataPointer(header, dataPtr);
0500
0501         // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning
0502         //       * when growing forward, adjust by the previous data pointer offset
0503         dataPtr += (position == QArrayData::GrowsAtBeginning)
0504                 ? n + qMax(0, (header->alloc - from.size - n) / 2)
0505                 : from.freeSpaceAtBegin();
0506         header->flags = from.flags();
0507         return QArrayDataPointer(header, dataPtr);
0508     }
0509
0510     friend bool operator==(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
0511     {
0512         return lhs.data() == rhs.data() && lhs.size == rhs.size;
0513     }
0514
0515     friend bool operator!=(const QArrayDataPointer &lhs, const QArrayDataPointer &rhs) noexcept
0516     {
0517         return lhs.data() != rhs.data() || lhs.size != rhs.size;
0518     }
0519
0520     Data *d;
0521     T *ptr;
0522     qsizetype size;
0523 };
0524
0525 template <class T>
0526 inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept
0527 {
0528     p1.swap(p2);
0529 }
0530
0531 ////////////////////////////////////////////////////////////////////////////////
0532 //  Q_ARRAY_LITERAL
0533
0534 // The idea here is to place a (read-only) copy of header and array data in an
0535 // mmappable portion of the executable (typically, .rodata section).
0536
0537 // Hide array inside a lambda
0538 #define Q_ARRAY_LITERAL(Type, ...) \
0539     ([]() -> QArrayDataPointer<Type> { \
0540         static Type const data[] = { __VA_ARGS__ }; \
0541         return QArrayDataPointer<Type>::fromRawData(const_cast<Type *>(data), std::size(data)); \
0542     }())
0543 /**/
0544
0545 QT_END_NAMESPACE
0546
0547 #endif // include guard