diff options
Diffstat (limited to 'src/corelib/tools/qarraydata.h')
| -rw-r--r-- | src/corelib/tools/qarraydata.h | 439 |
1 files changed, 158 insertions, 281 deletions
diff --git a/src/corelib/tools/qarraydata.h b/src/corelib/tools/qarraydata.h index 0063cf046f..da83fc1a21 100644 --- a/src/corelib/tools/qarraydata.h +++ b/src/corelib/tools/qarraydata.h @@ -1,346 +1,223 @@ -/**************************************************************************** -** -** Copyright (C) 2016 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. +// Copyright (C) 2019 Intel Corporation. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only #ifndef QARRAYDATA_H #define QARRAYDATA_H -#include <QtCore/qrefcount.h> +#include <QtCore/qpair.h> +#include <QtCore/qatomic.h> +#include <QtCore/qflags.h> +#include <QtCore/qcontainerfwd.h> #include <string.h> QT_BEGIN_NAMESPACE -struct Q_CORE_EXPORT QArrayData +#if __has_cpp_attribute(gnu::malloc) +# define Q_DECL_MALLOCLIKE [[nodiscard, gnu::malloc]] +#else +# define Q_DECL_MALLOCLIKE [[nodiscard]] +#endif + +template <class T> struct QTypedArrayData; + +struct QArrayData { - QtPrivate::RefCount ref; - int size; - uint alloc : 31; - uint capacityReserved : 1; + enum AllocationOption { + Grow, + KeepSize + }; - qptrdiff offset; // in bytes from beginning of header + enum GrowthPosition { + GrowsAtEnd, + GrowsAtBeginning + }; - void *data() + enum ArrayOption { + ArrayOptionDefault = 0, + CapacityReserved = 0x1 //!< the capacity was reserved by the user, try to keep it + }; + Q_DECLARE_FLAGS(ArrayOptions, ArrayOption) + + QBasicAtomicInt ref_; + ArrayOptions flags; + qsizetype alloc; + + qsizetype allocatedCapacity() noexcept { - Q_ASSERT(size == 0 - || offset < 0 || size_t(offset) >= sizeof(QArrayData)); - return reinterpret_cast<char *>(this) + offset; + return alloc; } - const void *data() const + qsizetype constAllocatedCapacity() const noexcept { - Q_ASSERT(size == 0 - || offset < 0 || size_t(offset) >= sizeof(QArrayData)); - return reinterpret_cast<const char *>(this) + offset; + return alloc; } - // This refers to array data mutability, not "header data" represented by - // data members in QArrayData. Shared data (array and header) must still - // follow COW principles. - bool isMutable() const + /// Returns true if sharing took place + bool ref() noexcept { - return alloc != 0; + ref_.ref(); + return true; } - enum AllocationOption { - CapacityReserved = 0x1, - RawData = 0x4, - Grow = 0x8, - - Default = 0 - }; - - Q_DECLARE_FLAGS(AllocationOptions, AllocationOption) - - size_t detachCapacity(size_t newSize) const + /// Returns false if deallocation is necessary + bool deref() noexcept { - if (capacityReserved && newSize < alloc) - return alloc; - return newSize; + return ref_.deref(); } - AllocationOptions detachFlags() const + bool isShared() const noexcept { - AllocationOptions result; - if (capacityReserved) - result |= CapacityReserved; - return result; + return ref_.loadRelaxed() != 1; } - AllocationOptions cloneFlags() const + // Returns true if a detach is necessary before modifying the data + // This method is intentionally not const: if you want to know whether + // detaching is necessary, you should be in a non-const function already + bool needsDetach() noexcept { - AllocationOptions result; - if (capacityReserved) - result |= CapacityReserved; - return result; + return ref_.loadRelaxed() > 1; } - Q_REQUIRED_RESULT static QArrayData *allocate(size_t objectSize, size_t alignment, - size_t capacity, AllocationOptions options = Default) noexcept; - Q_REQUIRED_RESULT static QArrayData *reallocateUnaligned(QArrayData *data, size_t objectSize, - size_t newCapacity, AllocationOptions newOptions = Default) noexcept; - static void deallocate(QArrayData *data, size_t objectSize, - size_t alignment) noexcept; + qsizetype detachCapacity(qsizetype newSize) const noexcept + { + if (flags & CapacityReserved && newSize < constAllocatedCapacity()) + return constAllocatedCapacity(); + return newSize; + } - static const QArrayData shared_null[2]; - static QArrayData *sharedNull() noexcept { return const_cast<QArrayData*>(shared_null); } + Q_DECL_MALLOCLIKE + static Q_CORE_EXPORT void *allocate(QArrayData **pdata, qsizetype objectSize, qsizetype alignment, + qsizetype capacity, AllocationOption option = QArrayData::KeepSize) noexcept; + Q_DECL_MALLOCLIKE + static Q_CORE_EXPORT void *allocate1(QArrayData **pdata, qsizetype capacity, + AllocationOption option = QArrayData::KeepSize) noexcept; + Q_DECL_MALLOCLIKE + static Q_CORE_EXPORT void *allocate2(QArrayData **pdata, qsizetype capacity, + AllocationOption option = QArrayData::KeepSize) noexcept; + + [[nodiscard]] static Q_CORE_EXPORT std::pair<QArrayData *, void *> reallocateUnaligned(QArrayData *data, void *dataPointer, + qsizetype objectSize, qsizetype newCapacity, AllocationOption option) noexcept; + static Q_CORE_EXPORT void deallocate(QArrayData *data, qsizetype objectSize, + qsizetype alignment) noexcept; }; -Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::AllocationOptions) +Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::ArrayOptions) -template <class T> -struct QTypedArrayData - : QArrayData -{ -#ifdef QT_STRICT_ITERATORS - class iterator { - public: - T *i; - typedef std::random_access_iterator_tag iterator_category; - typedef int difference_type; - typedef T value_type; - typedef T *pointer; - typedef T &reference; - - inline iterator() : i(nullptr) {} - inline iterator(T *n) : i(n) {} - inline iterator(const iterator &o): i(o.i){} // #### Qt 6: remove, the implicit version is fine - inline T &operator*() const { return *i; } - inline T *operator->() const { return i; } - inline T &operator[](int j) const { return *(i + j); } - inline bool operator==(const iterator &o) const { return i == o.i; } - inline bool operator!=(const iterator &o) const { return i != o.i; } - inline bool operator<(const iterator& other) const { return i < other.i; } - inline bool operator<=(const iterator& other) const { return i <= other.i; } - inline bool operator>(const iterator& other) const { return i > other.i; } - inline bool operator>=(const iterator& other) const { return i >= other.i; } - inline iterator &operator++() { ++i; return *this; } - inline iterator operator++(int) { T *n = i; ++i; return n; } - inline iterator &operator--() { i--; return *this; } - inline iterator operator--(int) { T *n = i; i--; return n; } - inline iterator &operator+=(int j) { i+=j; return *this; } - inline iterator &operator-=(int j) { i-=j; return *this; } - inline iterator operator+(int j) const { return iterator(i+j); } - inline iterator operator-(int j) const { return iterator(i-j); } - friend inline iterator operator+(int j, iterator k) { return k + j; } - inline int operator-(iterator j) const { return i - j.i; } - inline operator T*() const { return i; } - }; - friend class iterator; - - class const_iterator { - public: - const T *i; - typedef std::random_access_iterator_tag iterator_category; - typedef int difference_type; - typedef T value_type; - typedef const T *pointer; - typedef const T &reference; - - inline const_iterator() : i(nullptr) {} - inline const_iterator(const T *n) : i(n) {} - inline const_iterator(const const_iterator &o): i(o.i) {} // #### Qt 6: remove, the default version is fine - inline explicit const_iterator(const iterator &o): i(o.i) {} - inline const T &operator*() const { return *i; } - inline const T *operator->() const { return i; } - inline const T &operator[](int j) const { return *(i + j); } - inline bool operator==(const const_iterator &o) const { return i == o.i; } - inline bool operator!=(const const_iterator &o) const { return i != o.i; } - inline bool operator<(const const_iterator& other) const { return i < other.i; } - inline bool operator<=(const const_iterator& other) const { return i <= other.i; } - inline bool operator>(const const_iterator& other) const { return i > other.i; } - inline bool operator>=(const const_iterator& other) const { return i >= other.i; } - inline const_iterator &operator++() { ++i; return *this; } - inline const_iterator operator++(int) { const T *n = i; ++i; return n; } - inline const_iterator &operator--() { i--; return *this; } - inline const_iterator operator--(int) { const T *n = i; i--; return n; } - inline const_iterator &operator+=(int j) { i+=j; return *this; } - inline const_iterator &operator-=(int j) { i-=j; return *this; } - inline const_iterator operator+(int j) const { return const_iterator(i+j); } - inline const_iterator operator-(int j) const { return const_iterator(i-j); } - friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } - inline int operator-(const_iterator j) const { return i - j.i; } - inline operator const T*() const { return i; } - }; - friend class const_iterator; +namespace QtPrivate { +// QArrayData with strictest alignment requirements supported by malloc() +#if defined(Q_PROCESSOR_X86_32) && defined(Q_CC_GNU) +// GCC's definition is incorrect since GCC 8 (commit r240248 in SVN; commit +// 63012d9a57edc950c5f30242d1e19318b5708060 in Git). This is applied to all +// GCC-like compilers in case they decide to follow GCC's lead in being wrong. +constexpr size_t MaxPrimitiveAlignment = 2 * sizeof(void *); #else - typedef T* iterator; - typedef const T* const_iterator; +constexpr size_t MaxPrimitiveAlignment = alignof(std::max_align_t); #endif - T *data() { return static_cast<T *>(QArrayData::data()); } - const T *data() const { return static_cast<const T *>(QArrayData::data()); } - - iterator begin(iterator = iterator()) { return data(); } - iterator end(iterator = iterator()) { return data() + size; } - const_iterator begin(const_iterator = const_iterator()) const { return data(); } - const_iterator end(const_iterator = const_iterator()) const { return data() + size; } - const_iterator constBegin(const_iterator = const_iterator()) const { return data(); } - const_iterator constEnd(const_iterator = const_iterator()) const { return data() + size; } +struct alignas(MaxPrimitiveAlignment) AlignedQArrayData : QArrayData +{ +}; +} - class AlignmentDummy { QArrayData header; T data; }; +template <class T> +struct QTypedArrayData + : QArrayData +{ + struct AlignmentDummy { QtPrivate::AlignedQArrayData header; T data; }; - Q_REQUIRED_RESULT static QTypedArrayData *allocate(size_t capacity, - AllocationOptions options = Default) + [[nodiscard]] static std::pair<QTypedArrayData *, T *> allocate(qsizetype capacity, AllocationOption option = QArrayData::KeepSize) { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T), - alignof(AlignmentDummy), capacity, options)); + static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData)); + QArrayData *d; + void *result; + if constexpr (sizeof(T) == 1) { + // necessarily, alignof(T) == 1 + result = allocate1(&d, capacity, option); + } else if constexpr (sizeof(T) == 2) { + // alignof(T) may be 1, but that makes no difference + result = allocate2(&d, capacity, option); + } else { + result = QArrayData::allocate(&d, sizeof(T), alignof(AlignmentDummy), capacity, option); + } +#if __has_builtin(__builtin_assume_aligned) + // and yet we do offer results that have stricter alignment + result = __builtin_assume_aligned(result, Q_ALIGNOF(AlignmentDummy)); +#endif + return {static_cast<QTypedArrayData *>(d), static_cast<T *>(result)}; } - static QTypedArrayData *reallocateUnaligned(QTypedArrayData *data, size_t capacity, - AllocationOptions options = Default) + static std::pair<QTypedArrayData *, T *> + reallocateUnaligned(QTypedArrayData *data, T *dataPointer, qsizetype capacity, AllocationOption option) { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return static_cast<QTypedArrayData *>(QArrayData::reallocateUnaligned(data, sizeof(T), - capacity, options)); + static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData)); + std::pair<QArrayData *, void *> pair = + QArrayData::reallocateUnaligned(data, dataPointer, sizeof(T), capacity, option); + return {static_cast<QTypedArrayData *>(pair.first), static_cast<T *>(pair.second)}; } - static void deallocate(QArrayData *data) + static void deallocate(QArrayData *data) noexcept { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); + static_assert(sizeof(QTypedArrayData) == sizeof(QArrayData)); QArrayData::deallocate(data, sizeof(T), alignof(AlignmentDummy)); } - static QTypedArrayData *fromRawData(const T *data, size_t n, - AllocationOptions options = Default) + static T *dataStart(QArrayData *data, qsizetype alignment) noexcept { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - QTypedArrayData *result = allocate(0, options | RawData); - if (result) { - Q_ASSERT(!result->ref.isShared()); // No shared empty, please! - - result->offset = reinterpret_cast<const char *>(data) - - reinterpret_cast<const char *>(result); - result->size = int(n); - } - return result; + // Alignment is a power of two + Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) && !(alignment & (alignment - 1))); + void *start = reinterpret_cast<void *>( + (quintptr(data) + sizeof(QArrayData) + alignment - 1) & ~(alignment - 1)); + return static_cast<T *>(start); } - static QTypedArrayData *sharedNull() noexcept + constexpr static qsizetype max_size() noexcept { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return static_cast<QTypedArrayData *>(QArrayData::sharedNull()); - } - - static QTypedArrayData *sharedEmpty() - { - Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return allocate(/* capacity */ 0); + // -1 to deal with the pointer one-past-the-end + return (QtPrivate::MaxAllocSize - sizeof(QtPrivate::AlignedQArrayData) - 1) / sizeof(T); } }; -template <class T, size_t N> -struct QStaticArrayData -{ - QArrayData header; - T data[N]; -}; - -// Support for returning QArrayDataPointer<T> from functions -template <class T> -struct QArrayDataPointerRef -{ - QTypedArrayData<T> *ptr; -}; - -#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size, offset) \ - { Q_REFCOUNT_INITIALIZE_STATIC, size, 0, 0, offset } \ - /**/ - -#define Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(type, size) \ - Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER_WITH_OFFSET(size,\ - ((sizeof(QArrayData) + (alignof(type) - 1)) & ~(alignof(type) - 1) )) \ - /**/ - -//////////////////////////////////////////////////////////////////////////////// -// Q_ARRAY_LITERAL - -// The idea here is to place a (read-only) copy of header and array data in an -// mmappable portion of the executable (typically, .rodata section). This is -// accomplished by hiding a static const instance of QStaticArrayData, which is -// POD. - -// Hide array inside a lambda -#define Q_ARRAY_LITERAL(Type, ...) \ - ([]() -> QArrayDataPointerRef<Type> { \ - /* MSVC 2010 Doesn't support static variables in a lambda, but */ \ - /* happily accepts them in a static function of a lambda-local */ \ - /* struct :-) */ \ - struct StaticWrapper { \ - static QArrayDataPointerRef<Type> get() \ - { \ - Q_ARRAY_LITERAL_IMPL(Type, __VA_ARGS__) \ - return ref; \ - } \ - }; \ - return StaticWrapper::get(); \ - }()) \ - /**/ - -#ifdef Q_COMPILER_CONSTEXPR -#define Q_ARRAY_LITERAL_CHECK_LITERAL_TYPE(Type) Q_STATIC_ASSERT(std::is_literal_type<Type>::value) -#else -#define Q_ARRAY_LITERAL_CHECK_LITERAL_TYPE(Type) do {} while (0) -#endif - -#define Q_ARRAY_LITERAL_IMPL(Type, ...) \ - Q_ARRAY_LITERAL_CHECK_LITERAL_TYPE(Type); \ - \ - /* Portable compile-time array size computation */ \ - Q_CONSTEXPR Type data[] = { __VA_ARGS__ }; Q_UNUSED(data); \ - enum { Size = sizeof(data) / sizeof(data[0]) }; \ - \ - static const QStaticArrayData<Type, Size> literal = { \ - Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(Type, Size), { __VA_ARGS__ } }; \ - \ - QArrayDataPointerRef<Type> ref = \ - { static_cast<QTypedArrayData<Type> *>( \ - const_cast<QArrayData *>(&literal.header)) }; \ - /**/ - namespace QtPrivate { struct Q_CORE_EXPORT QContainerImplHelper { enum CutResult { Null, Empty, Full, Subset }; - static CutResult mid(int originalLength, int *position, int *length); + static constexpr CutResult mid(qsizetype originalLength, qsizetype *_position, qsizetype *_length) + { + qsizetype &position = *_position; + qsizetype &length = *_length; + if (position > originalLength) { + position = 0; + length = 0; + return Null; + } + + if (position < 0) { + if (length < 0 || length + position >= originalLength) { + position = 0; + length = originalLength; + return Full; + } + if (length + position <= 0) { + position = length = 0; + return Null; + } + length += position; + position = 0; + } else if (size_t(length) > size_t(originalLength - position)) { + length = originalLength - position; + } + + if (position == 0 && length == originalLength) + return Full; + + return length > 0 ? Subset : Empty; + } }; } +#undef Q_DECL_MALLOCLIKE + QT_END_NAMESPACE #endif // include guard |