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