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