include/QtCore/qarraydata.h

0001 // Copyright (C) 2020 The Qt Company Ltd.
0002 // Copyright (C) 2019 Intel Corporation.
0003 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0004
0005 #ifndef QARRAYDATA_H
0006 #define QARRAYDATA_H
0007
0008 #include <QtCore/qpair.h>
0009 #include <QtCore/qatomic.h>
0010 #include <QtCore/qflags.h>
0011 #include <string.h>
0012
0013 QT_BEGIN_NAMESPACE
0014
0015 #if __has_cpp_attribute(gnu::malloc)
0016 #  define Q_DECL_MALLOCLIKE [[nodiscard, gnu::malloc]]
0017 #else
0018 #  define Q_DECL_MALLOCLIKE [[nodiscard]]
0019 #endif
0020
0021 template <class T> struct QTypedArrayData;
0022
0023 struct QArrayData
0024 {
0025     enum AllocationOption {
0026         Grow,
0027         KeepSize
0028     };
0029
0030     enum GrowthPosition {
0031         GrowsAtEnd,
0032         GrowsAtBeginning
0033     };
0034
0035    enum ArrayOption {
0036         ArrayOptionDefault = 0,
0037         CapacityReserved     = 0x1  //!< the capacity was reserved by the user, try to keep it
0038     };
0039     Q_DECLARE_FLAGS(ArrayOptions, ArrayOption)
0040
0041     QBasicAtomicInt ref_;
0042     ArrayOptions flags;
0043     qsizetype alloc;
0044
0045     qsizetype allocatedCapacity() noexcept
0046     {
0047         return alloc;
0048     }
0049
0050     qsizetype constAllocatedCapacity() const noexcept
0051     {
0052         return alloc;
0053     }
0054
0055     /// Returns true if sharing took place
0056     bool ref() noexcept
0057     {
0058         ref_.ref();
0059         return true;
0060     }
0061
0062     /// Returns false if deallocation is necessary
0063     bool deref() noexcept
0064     {
0065         return ref_.deref();
0066     }
0067
0068     bool isShared() const noexcept
0069     {
0070         return ref_.loadRelaxed() != 1;
0071     }
0072
0073     // Returns true if a detach is necessary before modifying the data
0074     // This method is intentionally not const: if you want to know whether
0075     // detaching is necessary, you should be in a non-const function already
0076     bool needsDetach() noexcept
0077     {
0078         return ref_.loadRelaxed() > 1;
0079     }
0080
0081     qsizetype detachCapacity(qsizetype newSize) const noexcept
0082     {
0083         if (flags & CapacityReserved && newSize < constAllocatedCapacity())
0084             return constAllocatedCapacity();
0085         return newSize;
0086     }
0087
0088     Q_DECL_MALLOCLIKE
0089     static Q_CORE_EXPORT void *allocate(QArrayData **pdata, qsizetype objectSize, qsizetype alignment,
0090             qsizetype capacity, AllocationOption option = QArrayData::KeepSize) noexcept;
0091     Q_DECL_MALLOCLIKE
0092     static Q_CORE_EXPORT void *allocate1(QArrayData **pdata, qsizetype capacity,
0093                                          AllocationOption option = QArrayData::KeepSize) noexcept;
0094     Q_DECL_MALLOCLIKE
0095     static Q_CORE_EXPORT void *allocate2(QArrayData **pdata, qsizetype capacity,
0096                                          AllocationOption option = QArrayData::KeepSize) noexcept;
0097
0098     [[nodiscard]] static Q_CORE_EXPORT std::pair<QArrayData *, void *> reallocateUnaligned(QArrayData *data, void *dataPointer,
0099             qsizetype objectSize, qsizetype newCapacity, AllocationOption option) noexcept;
0100     static Q_CORE_EXPORT void deallocate(QArrayData *data, qsizetype objectSize,
0101             qsizetype alignment) noexcept;
0102 };
0103
0104 Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::ArrayOptions)
0105
0106 namespace QtPrivate {
0107 // QArrayData with strictest alignment requirements supported by malloc()
0108 #if defined(Q_PROCESSOR_X86_32) && defined(Q_CC_GNU)
0109 // GCC's definition is incorrect since GCC 8 (commit r240248 in SVN; commit
0110 // 63012d9a57edc950c5f30242d1e19318b5708060 in Git). This is applied to all
0111 // GCC-like compilers in case they decide to follow GCC's lead in being wrong.
0112 constexpr size_t MaxPrimitiveAlignment = 2 * sizeof(void *);
0113 #else
0114 constexpr size_t MaxPrimitiveAlignment = alignof(std::max_align_t);
0115 #endif
0116
0117 struct alignas(MaxPrimitiveAlignment) AlignedQArrayData : QArrayData
0118 {
0119 };
0120 }
0121
0122 template <class T>
0123 struct QTypedArrayData
0124     : QArrayData
0125 {
0126     struct AlignmentDummy { QtPrivate::AlignedQArrayData header; T data; };
0127
0128     [[nodiscard]] static std::pair<QTypedArrayData *, T *> allocate(qsizetype capacity, AllocationOption option = QArrayData::KeepSize)
0129     {
0130         static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData));
0131         QArrayData *d;
0132         void *result;
0133         if constexpr (sizeof(T) == 1) {
0134             // necessarily, alignof(T) == 1
0135             result = allocate1(&d, capacity, option);
0136         } else if constexpr (sizeof(T) == 2) {
0137             // alignof(T) may be 1, but that makes no difference
0138             result = allocate2(&d, capacity, option);
0139         } else {
0140             result = QArrayData::allocate(&d, sizeof(T), alignof(AlignmentDummy), capacity, option);
0141         }
0142 #if __has_builtin(__builtin_assume_aligned)
0143         // and yet we do offer results that have stricter alignment
0144         result = __builtin_assume_aligned(result, Q_ALIGNOF(AlignmentDummy));
0145 #endif
0146         return {static_cast<QTypedArrayData *>(d), static_cast<T *>(result)};
0147     }
0148
0149     static std::pair<QTypedArrayData *, T *>
0150     reallocateUnaligned(QTypedArrayData *data, T *dataPointer, qsizetype capacity, AllocationOption option)
0151     {
0152         static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData));
0153         std::pair<QArrayData *, void *> pair =
0154                 QArrayData::reallocateUnaligned(data, dataPointer, sizeof(T), capacity, option);
0155         return {static_cast<QTypedArrayData *>(pair.first), static_cast<T *>(pair.second)};
0156     }
0157
0158     static void deallocate(QArrayData *data) noexcept
0159     {
0160         static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData));
0161         QArrayData::deallocate(data, sizeof(T), alignof(AlignmentDummy));
0162     }
0163
0164     static T *dataStart(QArrayData *data, qsizetype alignment) noexcept
0165     {
0166         // Alignment is a power of two
0167         Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) && !(alignment & (alignment - 1)));
0168         void *start =  reinterpret_cast<void *>(
0169             (quintptr(data) + sizeof(QArrayData) + alignment - 1) & ~(alignment - 1));
0170         return static_cast<T *>(start);
0171     }
0172 };
0173
0174 namespace QtPrivate {
0175 struct Q_CORE_EXPORT QContainerImplHelper
0176 {
0177     enum CutResult { Null, Empty, Full, Subset };
0178     static constexpr CutResult mid(qsizetype originalLength, qsizetype *_position, qsizetype *_length)
0179     {
0180         qsizetype &position = *_position;
0181         qsizetype &length = *_length;
0182         if (position > originalLength) {
0183             position = 0;
0184             length = 0;
0185             return Null;
0186         }
0187
0188         if (position < 0) {
0189             if (length < 0 || length + position >= originalLength) {
0190                 position = 0;
0191                 length = originalLength;
0192                 return Full;
0193             }
0194             if (length + position <= 0) {
0195                 position = length = 0;
0196                 return Null;
0197             }
0198             length += position;
0199             position = 0;
0200         } else if (size_t(length) > size_t(originalLength - position)) {
0201             length = originalLength - position;
0202         }
0203
0204         if (position == 0 && length == originalLength)
0205             return Full;
0206
0207         return length > 0 ? Subset : Empty;
0208     }
0209 };
0210 }
0211
0212 #undef Q_DECL_MALLOCLIKE
0213
0214 QT_END_NAMESPACE
0215
0216 #endif // include guard