diff options
Diffstat (limited to 'src/corelib/tools')
24 files changed, 2880 insertions, 1288 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index b01ce0db58..aa79e0d4a9 100644 --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -535,7 +535,7 @@ QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessItera # define QT_HAS_BUILTIN_CTZS Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept { -# if QT_HAS_BUILTIN(__builtin_ctzs) +# if __has_builtin(__builtin_ctzs) return __builtin_ctzs(v); # else return __builtin_ctz(v); @@ -544,7 +544,7 @@ Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept #define QT_HAS_BUILTIN_CLZS Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept { -# if QT_HAS_BUILTIN(__builtin_clzs) +# if __has_builtin(__builtin_clzs) return __builtin_clzs(v); # else return __builtin_clz(v) - 16U; diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp index ed7dfe2e41..497eae1f7f 100644 --- a/src/corelib/tools/qarraydata.cpp +++ b/src/corelib/tools/qarraydata.cpp @@ -153,24 +153,24 @@ QT_WARNING_PUSH QT_WARNING_DISABLE_GCC("-Wmissing-field-initializers") const QArrayData QArrayData::shared_null[2] = { - { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null + { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared null /* zero initialized terminator */}; -static const QArrayData qt_array[3] = { - { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared empty - { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, sizeof(QArrayData) }, // unsharable empty +static const QArrayData emptyNotNullShared[2] = { + { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared empty /* zero initialized terminator */}; QT_WARNING_POP -static const QArrayData &qt_array_empty = qt_array[0]; +static const QArrayData &qt_array_empty = emptyNotNullShared[0]; + static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t headerSize, uint options) { // Calculate the byte size // allocSize = objectSize * capacity + headerSize, but checked for overflow // plus padded to grow in size - if (options & QArrayData::Grow) { + if (options & QArrayData::GrowsForward) { auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize); capacity = r.elementCount; return r.size; @@ -179,66 +179,93 @@ static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, siz } } +static QArrayData *allocateData(size_t allocSize, uint options) +{ + QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize)); + if (header) { + header->ref_.storeRelaxed(1); + header->flags = options; + header->alloc = 0; + } + return header; +} + static QArrayData *reallocateData(QArrayData *header, size_t allocSize, uint options) { header = static_cast<QArrayData *>(::realloc(header, allocSize)); if (header) - header->capacityReserved = bool(options & QArrayData::CapacityReserved); + header->flags = options; return header; } -QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment, - size_t capacity, AllocationOptions options) noexcept +void *QArrayData::allocate(QArrayData **dptr, size_t objectSize, size_t alignment, + size_t capacity, ArrayOptions options) noexcept { + Q_ASSERT(dptr); // Alignment is a power of two Q_ASSERT(alignment >= alignof(QArrayData) && !(alignment & (alignment - 1))); - // Don't allocate empty headers - if (!(options & RawData) && !capacity) - return const_cast<QArrayData *>(&qt_array_empty); + if (capacity == 0) { + // optimization for empty headers + *dptr = const_cast<QArrayData *>(&qt_array_empty); + return sharedNullData(); + } size_t headerSize = sizeof(QArrayData); - // Allocate extra (alignment - alignof(QArrayData)) padding bytes so we - // can properly align the data array. This assumes malloc is able to - // provide appropriate alignment for the header -- as it should! - // Padding is skipped when allocating a header for RawData. - if (!(options & RawData)) - headerSize += (alignment - alignof(QArrayData)); + if (alignment > alignof(QArrayData)) { + // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we + // can properly align the data array. This assumes malloc is able to + // provide appropriate alignment for the header -- as it should! + headerSize += alignment - alignof(QArrayData); + } if (headerSize > size_t(MaxAllocSize)) return nullptr; size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); - QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize)); + options |= AllocatedDataType | MutableData; + options &= ~ImmutableHeader; + QArrayData *header = allocateData(allocSize, options); + quintptr data = 0; if (header) { - quintptr data = (quintptr(header) + sizeof(QArrayData) + alignment - 1) + // find where offset should point to so that data() is aligned to alignment bytes + data = (quintptr(header) + sizeof(QArrayData) + alignment - 1) & ~(alignment - 1); - - header->ref.atomic.storeRelaxed(1); - header->size = 0; - header->alloc = capacity; - header->capacityReserved = bool(options & CapacityReserved); - header->offset = data - quintptr(header); + header->alloc = uint(capacity); } + *dptr = header; + return reinterpret_cast<void *>(data); +} + +QArrayData *QArrayData::prepareRawData(ArrayOptions options) Q_DECL_NOTHROW +{ + QArrayData *header = allocateData(sizeof(QArrayData), (options & ~DataTypeBits) | RawDataType); + if (header) + header->alloc = 0; return header; } -QArrayData *QArrayData::reallocateUnaligned(QArrayData *data, size_t objectSize, size_t capacity, - AllocationOptions options) noexcept +QPair<QArrayData *, void *> +QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, + size_t objectSize, size_t capacity, ArrayOptions options) noexcept { Q_ASSERT(data); Q_ASSERT(data->isMutable()); - Q_ASSERT(!data->ref.isShared()); + Q_ASSERT(!data->isShared()); size_t headerSize = sizeof(QArrayData); size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); - QArrayData *header = static_cast<QArrayData *>(reallocateData(data, allocSize, options)); - if (header) - header->alloc = capacity; - return header; + qptrdiff offset = reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data); + options |= AllocatedDataType | MutableData; + QArrayData *header = reallocateData(data, allocSize, options); + if (header) { + header->alloc = uint(capacity); + dataPointer = reinterpret_cast<char *>(header) + offset; + } + return qMakePair(static_cast<QArrayData *>(header), dataPointer); } void QArrayData::deallocate(QArrayData *data, size_t objectSize, @@ -249,7 +276,7 @@ void QArrayData::deallocate(QArrayData *data, size_t objectSize, && !(alignment & (alignment - 1))); Q_UNUSED(objectSize) Q_UNUSED(alignment) - Q_ASSERT_X(data == 0 || !data->ref.isStatic(), "QArrayData::deallocate", + Q_ASSERT_X(data == nullptr || !data->isStatic(), "QArrayData::deallocate", "Static data cannot be deleted"); ::free(data); } diff --git a/src/corelib/tools/qarraydata.h b/src/corelib/tools/qarraydata.h index 0063cf046f..483f6d5edb 100644 --- a/src/corelib/tools/qarraydata.h +++ b/src/corelib/tools/qarraydata.h @@ -1,6 +1,7 @@ /**************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. +** Copyright (C) 2019 Intel Corporation. ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -40,32 +41,64 @@ #ifndef QARRAYDATA_H #define QARRAYDATA_H -#include <QtCore/qrefcount.h> +#include <QtCore/qpair.h> +#include <QtCore/qatomic.h> #include <string.h> QT_BEGIN_NAMESPACE +template <class T> struct QTypedArrayData; + struct Q_CORE_EXPORT QArrayData { - QtPrivate::RefCount ref; - int size; - uint alloc : 31; - uint capacityReserved : 1; + enum ArrayOption { + RawDataType = 0x0001, //!< this class is really a QArrayData + AllocatedDataType = 0x0002, //!< this class is really a QArrayAllocatedData + DataTypeBits = 0x000f, + + CapacityReserved = 0x0010, //!< the capacity was reserved by the user, try to keep it + GrowsForward = 0x0020, //!< allocate with eyes towards growing through append() + GrowsBackwards = 0x0040, //!< allocate with eyes towards growing through prepend() + MutableData = 0x0080, //!< the data can be changed; doesn't say anything about the header + ImmutableHeader = 0x0100, //!< the header is static, it can't be changed + + /// this option is used by the Q_ARRAY_LITERAL and similar macros + StaticDataFlags = RawDataType | ImmutableHeader, + /// this option is used by the allocate() function + DefaultAllocationFlags = MutableData, + /// this option is used by the prepareRawData() function + DefaultRawFlags = 0 + }; + Q_DECLARE_FLAGS(ArrayOptions, ArrayOption) - qptrdiff offset; // in bytes from beginning of header + QBasicAtomicInt ref_; + uint flags; + uint alloc; + + inline size_t allocatedCapacity() + { + return alloc; + } + + inline size_t constAllocatedCapacity() const + { + return alloc; + } - void *data() + /// Returns true if sharing took place + bool ref() { - Q_ASSERT(size == 0 - || offset < 0 || size_t(offset) >= sizeof(QArrayData)); - return reinterpret_cast<char *>(this) + offset; + if (!isStatic()) + ref_.ref(); + return true; } - const void *data() const + /// Returns false if deallocation is necessary + bool deref() { - Q_ASSERT(size == 0 - || offset < 0 || size_t(offset) >= sizeof(QArrayData)); - return reinterpret_cast<const char *>(this) + offset; + if (isStatic()) + return true; + return ref_.deref(); } // This refers to array data mutability, not "header data" represented by @@ -73,54 +106,93 @@ struct Q_CORE_EXPORT QArrayData // follow COW principles. bool isMutable() const { - return alloc != 0; + return flags & MutableData; } - enum AllocationOption { - CapacityReserved = 0x1, - RawData = 0x4, - Grow = 0x8, + bool isStatic() const + { + return flags & ImmutableHeader; + } - Default = 0 - }; + bool isShared() const + { + return ref_.loadRelaxed() != 1; + } - Q_DECLARE_FLAGS(AllocationOptions, AllocationOption) + // 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() + { + // requires two conditionals + return !isMutable() || isShared(); + } size_t detachCapacity(size_t newSize) const { - if (capacityReserved && newSize < alloc) - return alloc; + if (flags & CapacityReserved && newSize < constAllocatedCapacity()) + return constAllocatedCapacity(); return newSize; } - AllocationOptions detachFlags() const + ArrayOptions detachFlags() const { - AllocationOptions result; - if (capacityReserved) + ArrayOptions result = DefaultAllocationFlags; + if (flags & CapacityReserved) result |= CapacityReserved; return result; } - AllocationOptions cloneFlags() const + ArrayOptions cloneFlags() const { - AllocationOptions result; - if (capacityReserved) + ArrayOptions result = DefaultAllocationFlags; + if (flags & CapacityReserved) result |= CapacityReserved; return result; } - Q_REQUIRED_RESULT static QArrayData *allocate(size_t objectSize, size_t alignment, - size_t capacity, AllocationOptions options = Default) noexcept; + Q_REQUIRED_RESULT +#if defined(Q_CC_GNU) + __attribute__((__malloc__)) +#endif + static void *allocate(QArrayData **pdata, size_t objectSize, size_t alignment, + size_t capacity, ArrayOptions options = DefaultAllocationFlags) noexcept; Q_REQUIRED_RESULT static QArrayData *reallocateUnaligned(QArrayData *data, size_t objectSize, - size_t newCapacity, AllocationOptions newOptions = Default) noexcept; + size_t newCapacity, ArrayOptions newOptions = DefaultAllocationFlags) noexcept; + Q_REQUIRED_RESULT static QPair<QArrayData *, void *> reallocateUnaligned(QArrayData *data, void *dataPointer, + size_t objectSize, size_t newCapacity, ArrayOptions newOptions = DefaultAllocationFlags) Q_DECL_NOTHROW; + Q_REQUIRED_RESULT static QArrayData *prepareRawData(ArrayOptions options = ArrayOptions(RawDataType)) + Q_DECL_NOTHROW; static void deallocate(QArrayData *data, size_t objectSize, size_t alignment) noexcept; static const QArrayData shared_null[2]; static QArrayData *sharedNull() noexcept { return const_cast<QArrayData*>(shared_null); } + static void *sharedNullData() + { + QArrayData *const null = const_cast<QArrayData *>(&shared_null[1]); + return null; + } +}; + +Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::ArrayOptions) + +template <class T, size_t N> +struct QStaticArrayData +{ + // static arrays are of type RawDataType + QArrayData header; + T data[N]; }; -Q_DECLARE_OPERATORS_FOR_FLAGS(QArrayData::AllocationOptions) +// Support for returning QArrayDataPointer<T> from functions +template <class T> +struct QArrayDataPointerRef +{ + QTypedArrayData<T> *ptr; + T *data; + uint size; +}; template <class T> struct QTypedArrayData @@ -202,32 +274,28 @@ struct QTypedArrayData typedef const T* const_iterator; #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; } - class AlignmentDummy { QArrayData header; T data; }; - Q_REQUIRED_RESULT static QTypedArrayData *allocate(size_t capacity, - AllocationOptions options = Default) + Q_REQUIRED_RESULT static QPair<QTypedArrayData *, T *> allocate(size_t capacity, + ArrayOptions options = DefaultAllocationFlags) { Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return static_cast<QTypedArrayData *>(QArrayData::allocate(sizeof(T), - alignof(AlignmentDummy), capacity, options)); + QArrayData *d; + void *result = QArrayData::allocate(&d, sizeof(T), alignof(AlignmentDummy), capacity, options); +#if (defined(Q_CC_GNU) && Q_CC_GNU >= 407) || QT_HAS_BUILTIN(__builtin_assume_aligned) + result = __builtin_assume_aligned(result, Q_ALIGNOF(AlignmentDummy)); +#endif + return qMakePair(static_cast<QTypedArrayData *>(d), static_cast<T *>(result)); } - static QTypedArrayData *reallocateUnaligned(QTypedArrayData *data, size_t capacity, - AllocationOptions options = Default) + static QPair<QTypedArrayData *, T *> + reallocateUnaligned(QTypedArrayData *data, T *dataPointer, size_t capacity, + ArrayOptions options = DefaultAllocationFlags) { Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); - return static_cast<QTypedArrayData *>(QArrayData::reallocateUnaligned(data, sizeof(T), - capacity, options)); + QPair<QArrayData *, void *> pair = + QArrayData::reallocateUnaligned(data, dataPointer, sizeof(T), capacity, options); + return qMakePair(static_cast<QTypedArrayData *>(pair.first), static_cast<T *>(pair.second)); } static void deallocate(QArrayData *data) @@ -236,17 +304,15 @@ struct QTypedArrayData QArrayData::deallocate(data, sizeof(T), alignof(AlignmentDummy)); } - static QTypedArrayData *fromRawData(const T *data, size_t n, - AllocationOptions options = Default) + static QArrayDataPointerRef<T> fromRawData(const T *data, size_t n, + ArrayOptions options = DefaultRawFlags) { 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); + QArrayDataPointerRef<T> result = { + static_cast<QTypedArrayData *>(prepareRawData(options)), const_cast<T *>(data), uint(n) + }; + if (result.ptr) { + Q_ASSERT(!result.ptr->isShared()); // No shared empty, please! } return result; } @@ -262,31 +328,14 @@ struct QTypedArrayData Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); return allocate(/* capacity */ 0); } -}; - -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; + static T *sharedNullData() + { + Q_STATIC_ASSERT(sizeof(QTypedArrayData) == sizeof(QArrayData)); + return static_cast<T *>(QArrayData::sharedNullData()); + } }; -#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 @@ -322,15 +371,16 @@ struct QArrayDataPointerRef Q_ARRAY_LITERAL_CHECK_LITERAL_TYPE(Type); \ \ /* Portable compile-time array size computation */ \ - Q_CONSTEXPR Type data[] = { __VA_ARGS__ }; Q_UNUSED(data); \ + static Type const data[] = { __VA_ARGS__ }; \ enum { Size = sizeof(data) / sizeof(data[0]) }; \ \ - static const QStaticArrayData<Type, Size> literal = { \ - Q_STATIC_ARRAY_DATA_HEADER_INITIALIZER(Type, Size), { __VA_ARGS__ } }; \ + static const QArrayData literal = { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }; \ \ QArrayDataPointerRef<Type> ref = \ { static_cast<QTypedArrayData<Type> *>( \ - const_cast<QArrayData *>(&literal.header)) }; \ + const_cast<QArrayData *>(&literal)), \ + const_cast<Type *>(data), \ + Size }; \ /**/ namespace QtPrivate { diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h index 8e19525f07..0d2be5d51c 100644 --- a/src/corelib/tools/qarraydataops.h +++ b/src/corelib/tools/qarraydataops.h @@ -1,6 +1,7 @@ /**************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. +** Copyright (C) 2016 Intel Corporation. ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -41,12 +42,15 @@ #define QARRAYDATAOPS_H #include <QtCore/qarraydata.h> +#include <QtCore/qcontainertools_impl.h> #include <new> #include <string.h> QT_BEGIN_NAMESPACE +template <class T> struct QArrayDataPointer; + namespace QtPrivate { QT_WARNING_PUSH @@ -56,48 +60,67 @@ QT_WARNING_DISABLE_GCC("-Wstringop-overflow") template <class T> struct QPodArrayOps - : QTypedArrayData<T> + : public QArrayDataPointer<T> { + typedef typename QArrayDataPointer<T>::parameter_type parameter_type; + void appendInitialize(size_t newSize) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->alloc); + Q_ASSERT(newSize <= this->allocatedCapacity()); ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T)); this->size = int(newSize); } + template<typename iterator> + void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true) + { + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size); + + T *iter = this->end(); + for (; b != e; ++iter, ++b) { + new (iter) T(*b); + ++this->size; + } + } + void copyAppend(const T *b, const T *e) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(b < e); - Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size)); + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(b <= e); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); ::memcpy(static_cast<void *>(this->end()), static_cast<const void *>(b), (e - b) * sizeof(T)); this->size += e - b; } - void copyAppend(size_t n, const T &t) + void moveAppend(T *b, T *e) + { copyAppend(b, e); } + + void copyAppend(size_t n, parameter_type t) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(n <= this->alloc - uint(this->size)); + Q_ASSERT(this->isMutable() || n == 0); + Q_ASSERT(!this->isShared() || n == 0); + Q_ASSERT(n <= uint(this->allocatedCapacity() - this->size)); T *iter = this->end(); const T *const end = iter + n; for (; iter != end; ++iter) - ::memcpy(iter, &t, sizeof(T)); + *iter = t; this->size += int(n); } void truncate(size_t newSize) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(newSize < size_t(this->size)); this->size = int(newSize); @@ -106,7 +129,7 @@ struct QPodArrayOps void destroyAll() // Call from destructors, ONLY! { Q_ASSERT(this->isMutable()); - Q_ASSERT(this->ref.atomic.loadRelaxed() == 0); + Q_ASSERT(this->d->ref_.loadRelaxed() == 0); // As this is to be called only from destructor, it doesn't need to be // exception safe; size not updated. @@ -115,11 +138,11 @@ struct QPodArrayOps void insert(T *where, const T *b, const T *e) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end - Q_ASSERT(b < e); + Q_ASSERT(b <= e); Q_ASSERT(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size)); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); ::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where), (static_cast<const T*>(this->end()) - where) * sizeof(T)); @@ -127,43 +150,97 @@ struct QPodArrayOps this->size += (e - b); } + void insert(T *where, size_t n, parameter_type t) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end + Q_ASSERT(this->allocatedCapacity() - this->size >= n); + + ::memmove(static_cast<void *>(where + n), static_cast<void *>(where), + (static_cast<const T*>(this->end()) - where) * sizeof(T)); + this->size += int(n); // PODs can't throw on copy + while (n--) + *where++ = t; + } + + void insert(T *where, T &&t) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->allocatedCapacity() - this->size >= 1); + + ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where), + (static_cast<const T*>(this->end()) - where) * sizeof(T)); + this->size += 1; + new (where) T(std::move(t)); + } + + void erase(T *b, T *e) { Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < this->end()); - Q_ASSERT(e > this->begin() && e < this->end()); + Q_ASSERT(e > this->begin() && e <= this->end()); ::memmove(static_cast<void *>(b), static_cast<void *>(e), (static_cast<T *>(this->end()) - e) * sizeof(T)); this->size -= (e - b); } + + void assign(T *b, T *e, parameter_type t) + { + Q_ASSERT(b <= e); + Q_ASSERT(b >= this->begin() && e <= this->end()); + + while (b != e) + ::memcpy(static_cast<void *>(b++), static_cast<const void *>(&t), sizeof(T)); + } + + bool compare(const T *begin1, const T *begin2, size_t n) const + { + // only use memcmp for fundamental types or pointers. + // Other types could have padding in the data structure or custom comparison + // operators that would break the comparison using memcmp + if (QArrayDataPointer<T>::pass_parameter_by_value) + return ::memcmp(begin1, begin2, n * sizeof(T)) == 0; + const T *end1 = begin1 + n; + while (begin1 != end1) { + if (*begin1 == *begin2) + ++begin1, ++begin2; + else + return false; + } + return true; + } }; QT_WARNING_POP template <class T> struct QGenericArrayOps - : QTypedArrayData<T> + : public QArrayDataPointer<T> { + typedef typename QArrayDataPointer<T>::parameter_type parameter_type; + void appendInitialize(size_t newSize) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(newSize > uint(this->size)); - Q_ASSERT(newSize <= this->alloc); + Q_ASSERT(newSize <= this->allocatedCapacity()); - T *const begin = this->begin(); + T *const b = this->begin(); do { - new (begin + this->size) T; + new (b + this->size) T; } while (uint(++this->size) != newSize); } - void copyAppend(const T *b, const T *e) + template<typename iterator> + void copyAppend(iterator b, iterator e, QtPrivate::IfIsForwardIterator<iterator> = true) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(b < e); - Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size)); + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size); T *iter = this->end(); for (; b != e; ++iter, ++b) { @@ -172,11 +249,37 @@ struct QGenericArrayOps } } - void copyAppend(size_t n, const T &t) + void copyAppend(const T *b, const T *e) { - Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); - Q_ASSERT(n <= this->alloc - uint(this->size)); + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(std::distance(b, e) >= 0 && size_t(std::distance(b, e)) <= this->allocatedCapacity() - this->size); + + T *iter = this->end(); + this->size += e - b; + for (; b != e; ++iter, ++b) + new (iter) T(*b); + } + + void moveAppend(T *b, T *e) + { + Q_ASSERT(this->isMutable() || b == e); + Q_ASSERT(!this->isShared() || b == e); + Q_ASSERT(b <= e); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); + + T *iter = this->end(); + for (; b != e; ++iter, ++b) { + new (iter) T(std::move(*b)); + ++this->size; + } + } + + void copyAppend(size_t n, parameter_type t) + { + Q_ASSERT(this->isMutable() || n == 0); + Q_ASSERT(!this->isShared() || n == 0); + Q_ASSERT(n <= size_t(this->allocatedCapacity() - this->size)); T *iter = this->end(); const T *const end = iter + n; @@ -189,7 +292,7 @@ struct QGenericArrayOps void truncate(size_t newSize) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(newSize < size_t(this->size)); const T *const b = this->begin(); @@ -204,7 +307,7 @@ struct QGenericArrayOps // As this is to be called only from destructor, it doesn't need to be // exception safe; size not updated. - Q_ASSERT(this->ref.atomic.loadRelaxed() == 0); + Q_ASSERT(this->d->ref_.loadRelaxed() == 0); const T *const b = this->begin(); const T *i = this->end(); @@ -216,11 +319,11 @@ struct QGenericArrayOps void insert(T *where, const T *b, const T *e) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end - Q_ASSERT(b < e); + Q_ASSERT(b <= e); Q_ASSERT(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size)); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); // Array may be truncated at where in case of exceptions @@ -279,25 +382,139 @@ struct QGenericArrayOps } } + void insert(T *where, size_t n, parameter_type t) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->allocatedCapacity() - this->size >= n); + + // Array may be truncated at where in case of exceptions + T *const end = this->end(); + const T *readIter = end; + T *writeIter = end + n; + + const T *const step1End = where + qMax<size_t>(n, end - where); + + struct Destructor + { + Destructor(T *&it) + : iter(&it) + , end(it) + { + } + + void commit() + { + iter = &end; + } + + ~Destructor() + { + for (; *iter != end; --*iter) + (*iter)->~T(); + } + + T **iter; + T *end; + } destroyer(writeIter); + + // Construct new elements in array + do { + --readIter, --writeIter; + new (writeIter) T(*readIter); + } while (writeIter != step1End); + + while (writeIter != end) { + --n, --writeIter; + new (writeIter) T(t); + } + + destroyer.commit(); + this->size += destroyer.end - end; + + // Copy assign over existing elements + while (readIter != where) { + --readIter, --writeIter; + *writeIter = *readIter; + } + + while (writeIter != where) { + --n, --writeIter; + *writeIter = t; + } + } + + void insert(T *where, T &&t) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->allocatedCapacity() - this->size >= 1); + + // Array may be truncated at where in case of exceptions + T *const end = this->end(); + + if (where != end) { + // Move elements in array + T *readIter = end - 1; + T *writeIter = end; + new (writeIter) T(std::move(*readIter)); + while (readIter > where) { + --readIter; + --writeIter; + *writeIter = std::move(*readIter); + } + *where = std::move(t); + } else { + new (where) T(std::move(t)); + } + + ++this->size; + } + void erase(T *b, T *e) { Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < this->end()); - Q_ASSERT(e > this->begin() && e < this->end()); + Q_ASSERT(e > this->begin() && e <= this->end()); const T *const end = this->end(); - do { + // move (by assignment) the elements from e to end + // onto b to the new end + while (e != end) { *b = *e; ++b, ++e; - } while (e != end); + } + // destroy the final elements at the end + // here, b points to the new end and e to the actual end do { (--e)->~T(); --this->size; } while (e != b); } + + void assign(T *b, T *e, parameter_type t) + { + Q_ASSERT(b <= e); + Q_ASSERT(b >= this->begin() && e <= this->end()); + + while (b != e) + *b++ = t; + } + + bool compare(const T *begin1, const T *begin2, size_t n) const + { + const T *end1 = begin1 + n; + while (begin1 != end1) { + if (*begin1 == *begin2) + ++begin1, ++begin2; + else + return false; + } + return true; + } }; template <class T> @@ -308,15 +525,16 @@ struct QMovableArrayOps // using QGenericArrayOps<T>::copyAppend; // using QGenericArrayOps<T>::truncate; // using QGenericArrayOps<T>::destroyAll; + typedef typename QGenericArrayOps<T>::parameter_type parameter_type; void insert(T *where, const T *b, const T *e) { Q_ASSERT(this->isMutable()); - Q_ASSERT(!this->ref.isShared()); + Q_ASSERT(!this->isShared()); Q_ASSERT(where >= this->begin() && where < this->end()); // Use copyAppend at end - Q_ASSERT(b < e); + Q_ASSERT(b <= e); Q_ASSERT(e <= where || b > this->end()); // No overlap - Q_ASSERT(size_t(e - b) <= this->alloc - uint(this->size)); + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); // Provides strong exception safety guarantee, // provided T::~T() nothrow @@ -376,12 +594,79 @@ struct QMovableArrayOps this->size += (e - b); } + void insert(T *where, size_t n, parameter_type t) + { + Q_ASSERT(!this->isShared()); + Q_ASSERT(where >= this->begin() && where <= this->end()); + Q_ASSERT(this->allocatedCapacity() - this->size >= n); + + // Provides strong exception safety guarantee, + // provided T::~T() nothrow + + struct ReversibleDisplace + { + ReversibleDisplace(T *start, T *finish, size_t diff) + : begin(start) + , end(finish) + , displace(diff) + { + ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin), + (end - begin) * sizeof(T)); + } + + void commit() { displace = 0; } + + ~ReversibleDisplace() + { + if (displace) + ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace), + (end - begin) * sizeof(T)); + } + + T *const begin; + T *const end; + size_t displace; + + } displace(where, this->end(), n); + + struct CopyConstructor + { + CopyConstructor(T *w) : where(w) {} + + void copy(size_t count, parameter_type proto) + { + n = 0; + while (count--) { + new (where + n) T(proto); + ++n; + } + n = 0; + } + + ~CopyConstructor() + { + while (n) + where[--n].~T(); + } + + T *const where; + size_t n; + } copier(where); + + copier.copy(n, t); + displace.commit(); + this->size += int(n); + } + + // use moving insert + using QGenericArrayOps<T>::insert; + void erase(T *b, T *e) { Q_ASSERT(this->isMutable()); Q_ASSERT(b < e); Q_ASSERT(b >= this->begin() && b < this->end()); - Q_ASSERT(e > this->begin() && e < this->end()); + Q_ASSERT(e > this->begin() && e <= this->end()); struct Mover { @@ -405,11 +690,51 @@ struct QMovableArrayOps int &size; } mover(e, this->end(), this->size); + // destroy the elements we're erasing do { // Exceptions or not, dtor called once per instance (--e)->~T(); } while (e != b); } + + void moveAppend(T *b, T *e) + { + Q_ASSERT(this->isMutable()); + Q_ASSERT(!this->isShared()); + Q_ASSERT(b <= e); + Q_ASSERT(e <= this->begin() || b > this->end()); // No overlap + Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size); + + // Provides strong exception safety guarantee, + // provided T::~T() nothrow + + struct CopyConstructor + { + CopyConstructor(T *w) : where(w) {} + + void copy(T *src, const T *const srcEnd) + { + n = 0; + for (; src != srcEnd; ++src) { + new (where + n) T(std::move(*src)); + ++n; + } + n = 0; + } + + ~CopyConstructor() + { + while (n) + where[--n].~T(); + } + + T *const where; + size_t n; + } copier(this->end()); + + copier.copy(b, e); + this->size += (e - b); + } }; template <class T, class = void> diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index b8a1ef5d68..a17cf4a101 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -41,6 +41,7 @@ #define QARRAYDATAPOINTER_H #include <QtCore/qarraydataops.h> +#include <QtCore/qcontainertools_impl.h> QT_BEGIN_NAMESPACE @@ -52,30 +53,40 @@ private: typedef QArrayDataOps<T> DataOps; public: + typedef typename Data::iterator iterator; + typedef typename Data::const_iterator const_iterator; + enum { pass_parameter_by_value = std::is_fundamental<T>::value || std::is_pointer<T>::value }; + + typedef typename std::conditional<pass_parameter_by_value, T, const T &>::type parameter_type; + QArrayDataPointer() noexcept - : d(Data::sharedNull()) + : d(Data::sharedNull()), ptr(Data::sharedNullData()), size(0) + { + } + + QArrayDataPointer(const QArrayDataPointer &other) noexcept + : d(other.d), ptr(other.ptr), size(other.size) { + other.d->ref(); } - QArrayDataPointer(const QArrayDataPointer &other) - : d(other.d->ref.ref() - ? other.d - : other.clone(other.d->cloneFlags())) + QArrayDataPointer(Data *header, T *adata, size_t n = 0) noexcept + : d(header), ptr(adata), size(int(n)) { } - explicit QArrayDataPointer(QTypedArrayData<T> *ptr) - : d(ptr) + explicit QArrayDataPointer(QPair<QTypedArrayData<T> *, T *> adata, size_t n = 0) + : d(adata.first), ptr(adata.second), size(int(n)) { - Q_CHECK_PTR(ptr); + Q_CHECK_PTR(d); } - QArrayDataPointer(QArrayDataPointerRef<T> ref) - : d(ref.ptr) + QArrayDataPointer(QArrayDataPointerRef<T> dd) noexcept + : d(dd.ptr), ptr(dd.data), size(dd.size) { } - QArrayDataPointer &operator=(const QArrayDataPointer &other) + QArrayDataPointer &operator=(const QArrayDataPointer &other) noexcept { QArrayDataPointer tmp(other); this->swap(tmp); @@ -83,9 +94,11 @@ public: } QArrayDataPointer(QArrayDataPointer &&other) noexcept - : d(other.d) + : d(other.d), ptr(other.ptr), size(other.size) { other.d = Data::sharedNull(); + other.ptr = Data::sharedNullData(); + other.size = 0; } QArrayDataPointer &operator=(QArrayDataPointer &&other) noexcept @@ -95,97 +108,142 @@ public: return *this; } - DataOps &operator*() const + DataOps &operator*() noexcept + { + Q_ASSERT(d); + return *static_cast<DataOps *>(this); + } + + DataOps *operator->() noexcept + { + Q_ASSERT(d); + return static_cast<DataOps *>(this); + } + + const DataOps &operator*() const noexcept { Q_ASSERT(d); - return *static_cast<DataOps *>(d); + return *static_cast<const DataOps *>(this); } - DataOps *operator->() const + const DataOps *operator->() const noexcept { Q_ASSERT(d); - return static_cast<DataOps *>(d); + return static_cast<const DataOps *>(this); } ~QArrayDataPointer() { - if (!d->ref.deref()) { - if (d->isMutable()) + if (!deref()) { + if (isMutable()) (*this)->destroyAll(); Data::deallocate(d); } } - bool isNull() const + bool isNull() const noexcept { return d == Data::sharedNull(); } - Data *data() const - { - return d; - } + T *data() noexcept { return ptr; } + const T *data() const noexcept { return ptr; } - bool needsDetach() const - { - return (!d->isMutable() || d->ref.isShared()); - } + iterator begin(iterator = iterator()) noexcept { return data(); } + iterator end(iterator = iterator()) noexcept { return data() + size; } + const_iterator begin(const_iterator = const_iterator()) const noexcept { return data(); } + const_iterator end(const_iterator = const_iterator()) const noexcept { return data() + size; } + const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return data(); } + const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return data() + size; } void swap(QArrayDataPointer &other) noexcept { qSwap(d, other.d); + qSwap(ptr, other.ptr); + qSwap(size, other.size); } - void clear() + void clear() Q_DECL_NOEXCEPT_EXPR(std::is_nothrow_destructible<T>::value) { - QArrayDataPointer tmp(d); - d = Data::sharedNull(); + QArrayDataPointer tmp; + swap(tmp); } bool detach() { - if (needsDetach()) { - Data *copy = clone(d->detachFlags()); - QArrayDataPointer old(d); - d = copy; + if (d->needsDetach()) { + QPair<Data *, T *> copy = clone(d->detachFlags()); + QArrayDataPointer old(d, ptr, size); + d = copy.first; + ptr = copy.second; return true; } return false; } -private: - Q_REQUIRED_RESULT Data *clone(QArrayData::AllocationOptions options) const + // forwards from QArrayData + size_t allocatedCapacity() noexcept { return d->allocatedCapacity(); } + size_t constAllocatedCapacity() const noexcept { return d->constAllocatedCapacity(); } + int refCounterValue() const noexcept { return d->refCounterValue(); } + bool ref() noexcept { return d->ref(); } + bool deref() noexcept { return d->deref(); } + bool isMutable() const noexcept { return d->isMutable(); } + bool isStatic() const noexcept { return d->isStatic(); } + bool isShared() const noexcept { return d->isShared(); } + bool isSharedWith(const QArrayDataPointer &other) const noexcept { return d && d == other.d; } + bool needsDetach() const noexcept { return d->needsDetach(); } + size_t detachCapacity(size_t newSize) const noexcept { return d->detachCapacity(newSize); } + typename Data::ArrayOptions &flags() noexcept { return reinterpret_cast<typename Data::ArrayOptions &>(d->flags); } + typename Data::ArrayOptions flags() const noexcept { return typename Data::ArrayOption(d->flags); } + typename Data::ArrayOptions detachFlags() const noexcept { return d->detachFlags(); } + typename Data::ArrayOptions cloneFlags() const noexcept { return d->cloneFlags(); } + + void reallocate(uint alloc, typename Data::ArrayOptions options) { - Data *x = Data::allocate(d->detachCapacity(d->size), options); - Q_CHECK_PTR(x); - QArrayDataPointer copy(x); + auto pair = Data::reallocateUnaligned(d, ptr, alloc, options); + d = pair.first; + ptr = pair.second; + } + Data *d_ptr() { return d; } - if (d->size) - copy->copyAppend(d->begin(), d->end()); +private: + Q_REQUIRED_RESULT QPair<Data *, T *> clone(QArrayData::ArrayOptions options) const + { + QPair<Data *, T *> pair = Data::allocate(d->detachCapacity(size), + options); + Q_CHECK_PTR(pair.first); + QArrayDataPointer copy(pair.first, pair.second, 0); + if (size) + copy->copyAppend(begin(), end()); - Data *result = copy.d; + pair.first = copy.d; copy.d = Data::sharedNull(); - return result; + return pair; } +protected: Data *d; + T *ptr; + +public: + int size; }; template <class T> -inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) +inline bool operator==(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept { - return lhs.data() == rhs.data(); + return lhs.data() == rhs.data() && lhs.size == rhs.size; } template <class T> -inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) +inline bool operator!=(const QArrayDataPointer<T> &lhs, const QArrayDataPointer<T> &rhs) noexcept { - return lhs.data() != rhs.data(); + return lhs.data() != rhs.data() || lhs.size != rhs.size; } template <class T> -inline void swap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) +inline void qSwap(QArrayDataPointer<T> &p1, QArrayDataPointer<T> &p2) noexcept { p1.swap(p2); } diff --git a/src/corelib/tools/qbitarray.cpp b/src/corelib/tools/qbitarray.cpp index f0b81cce66..a1dd537d4d 100644 --- a/src/corelib/tools/qbitarray.cpp +++ b/src/corelib/tools/qbitarray.cpp @@ -342,6 +342,38 @@ QBitArray QBitArray::fromBits(const char *data, qsizetype size) return result; } +/*! + \since 6.0 + + Returns the array of bit converted to an int. The conversion is based on \a endianness. + Converts up to the first 32 bits of the array to \c quint32 and returns it, + obeying \a endianness. If \a ok is not a null pointer, and the array has more + than 32 bits, \a ok is set to false and this function returns zero; otherwise, + it's set to true. +*/ +quint32 QBitArray::toUInt32(QSysInfo::Endian endianness, bool *ok) const noexcept +{ + const qsizetype _size = size(); + if (_size > 32) { + if (ok) + *ok = false; + return 0; + } + + if (ok) + *ok = true; + + quint32 factor = 1; + quint32 total = 0; + for (qsizetype i = 0; i < _size; ++i, factor *= 2) { + const auto index = endianness == QSysInfo::Endian::LittleEndian ? i : (_size - i - 1); + if (testBit(index)) + total += factor; + } + + return total; +} + /*! \fn bool QBitArray::isDetached() const \internal diff --git a/src/corelib/tools/qbitarray.h b/src/corelib/tools/qbitarray.h index 9b0e931aca..ac3a8771d9 100644 --- a/src/corelib/tools/qbitarray.h +++ b/src/corelib/tools/qbitarray.h @@ -105,8 +105,10 @@ public: const char *bits() const { return isEmpty() ? nullptr : d.constData() + 1; } static QBitArray fromBits(const char *data, qsizetype len); + quint32 toUInt32(QSysInfo::Endian endianness, bool *ok = nullptr) const noexcept; + public: - typedef QByteArray::DataPtr DataPtr; + typedef QByteArray::DataPointer DataPtr; inline DataPtr &data_ptr() { return d.data_ptr(); } }; diff --git a/src/corelib/tools/qeasingcurve.cpp b/src/corelib/tools/qeasingcurve.cpp index d7f69d3e0a..1207ce0659 100644 --- a/src/corelib/tools/qeasingcurve.cpp +++ b/src/corelib/tools/qeasingcurve.cpp @@ -443,12 +443,12 @@ class QEasingCurvePrivate public: QEasingCurvePrivate() : type(QEasingCurve::Linear), - config(0), + config(nullptr), func(&easeNone) { } QEasingCurvePrivate(const QEasingCurvePrivate &other) : type(other.type), - config(other.config ? other.config->copy() : 0), + config(other.config ? other.config->copy() : nullptr), func(other.func) { } ~QEasingCurvePrivate() { delete config; } @@ -590,7 +590,7 @@ struct BezierEase : public QEasingCurveFunction if (!(x < 1)) return 1; - SingleCubicBezier *singleCubicBezier = 0; + SingleCubicBezier *singleCubicBezier = nullptr; getBezierSegment(singleCubicBezier, x); return evaluateSegmentForY(*singleCubicBezier, findTForX(*singleCubicBezier, x)); @@ -1097,7 +1097,7 @@ static QEasingCurve::EasingFunction curveToFunc(QEasingCurve::Type curve) case QEasingCurve::CosineCurve: return &easeCosineCurve; default: - return 0; + return nullptr; }; } @@ -1127,7 +1127,7 @@ static QEasingCurveFunction *curveToFunctionObject(QEasingCurve::Type type) return new QEasingCurveFunction(type, qreal(0.3), qreal(1.0), qreal(1.70158)); } - return 0; + return nullptr; } /*! @@ -1417,7 +1417,7 @@ void QEasingCurvePrivate::setType_helper(QEasingCurve::Type newType) tcbPoints = std::move(config->_tcbPoints); delete config; - config = 0; + config = nullptr; } if (isConfigFunction(newType) || (amp != -1.0) || (period != -1.0) || (overshoot != -1.0) || @@ -1431,11 +1431,11 @@ void QEasingCurvePrivate::setType_helper(QEasingCurve::Type newType) config->_o = overshoot; config->_bezierCurves = std::move(bezierCurves); config->_tcbPoints = std::move(tcbPoints); - func = 0; + func = nullptr; } else if (newType != QEasingCurve::Custom) { func = curveToFunc(newType); } - Q_ASSERT((func == 0) == (config != 0)); + Q_ASSERT((func == nullptr) == (config != nullptr)); type = newType; } @@ -1482,7 +1482,7 @@ void QEasingCurve::setCustomType(EasingFunction func) */ QEasingCurve::EasingFunction QEasingCurve::customType() const { - return d_ptr->type == Custom ? d_ptr->func : 0; + return d_ptr->type == Custom ? d_ptr->func : nullptr; } /*! @@ -1507,7 +1507,7 @@ QDebug operator<<(QDebug debug, const QEasingCurve &item) { QDebugStateSaver saver(debug); debug << "type:" << item.d_ptr->type - << "func:" << item.d_ptr->func; + << "func:" << reinterpret_cast<const void *>(item.d_ptr->func); if (item.d_ptr->config) { debug << QString::fromLatin1("period:%1").arg(item.d_ptr->config->_p, 0, 'f', 20) << QString::fromLatin1("amp:%1").arg(item.d_ptr->config->_a, 0, 'f', 20) diff --git a/src/corelib/tools/qflatmap_p.h b/src/corelib/tools/qflatmap_p.h new file mode 100644 index 0000000000..590b0d942f --- /dev/null +++ b/src/corelib/tools/qflatmap_p.h @@ -0,0 +1,982 @@ +/**************************************************************************** +** +** Copyright (C) 2020 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$ +** +****************************************************************************/ + +#ifndef QFLATMAP_P_H +#define QFLATMAP_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of a number of Qt sources files. This header file may change from +// version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qvector.h" + +#include <algorithm> +#include <functional> +#include <initializer_list> +#include <iterator> +#include <numeric> +#include <type_traits> +#include <utility> + +QT_BEGIN_NAMESPACE + +/* + QFlatMap provides an associative container backed by sorted sequential + containers. By default, QVector is used. + + Keys and values are stored in two separate containers. This provides improved + cache locality for key iteration and makes keys() and values() fast + operations. + + One can customize the underlying container type by passing the KeyContainer + and MappedContainer template arguments: + QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>> +*/ + +namespace Qt { + +struct OrderedUniqueRange_t {}; +constexpr OrderedUniqueRange_t OrderedUniqueRange = {}; + +} // namespace Qt + +template <class Key, class T, class Compare> +class QFlatMapValueCompare : protected Compare +{ +public: + QFlatMapValueCompare() = default; + QFlatMapValueCompare(const Compare &key_compare) + : Compare(key_compare) + { + } + + using value_type = std::pair<const Key, T>; + static constexpr bool is_comparator_noexcept = noexcept( + std::declval<Compare>()(std::declval<Key>(), std::declval<Key>())); + + bool operator()(const value_type &lhs, const value_type &rhs) const + noexcept(is_comparator_noexcept) + { + return Compare::operator()(lhs.first, rhs.first); + } +}; + +template <class Key, class T, + class Compare = std::less<Key>, + class KeyContainer = QVector<Key>, + class MappedContainer = QVector<T>> +class QFlatMap : private QFlatMapValueCompare<Key, T, Compare> +{ + using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>; + + template <class U> + class mock_pointer + { + U ref; + public: + mock_pointer(U r) + : ref(r) + { + } + + U *operator->() + { + return &ref; + } + }; + +public: + using key_type = Key; + using mapped_type = T; + using value_compare = QFlatMapValueCompare<Key, T, Compare>; + using value_type = typename value_compare::value_type; + using key_container_type = KeyContainer; + using mapped_container_type = MappedContainer; + using size_type = typename key_container_type::size_type; + using key_compare = Compare; + + struct containers + { + key_container_type keys; + mapped_container_type values; + }; + + class iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, T>; + using reference = std::pair<const Key &, T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + iterator() = default; + + iterator(containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + reference operator*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + return { operator*() }; + } + + bool operator==(const iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const iterator &o) const + { + return !operator==(o); + } + + iterator &operator++() + { + ++i; + return *this; + } + + iterator operator++(int) + { + + iterator r = *this; + i++; + return r; + } + + iterator &operator--() + { + --i; + return *this; + } + + iterator operator--(int) + { + iterator r = *this; + i--; + return r; + } + + iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend iterator operator+(size_type n, const iterator a) + { + iterator ret = a; + return ret += n; + } + + friend iterator operator+(const iterator a, size_type n) + { + return n + a; + } + + iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend iterator operator-(const iterator a, size_type n) + { + iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const iterator b, const iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const iterator &other) const + { + return i < other.i; + } + + bool operator>(const iterator &other) const + { + return i > other.i; + } + + bool operator<=(const iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + T &value() { return c->values[i]; } + + private: + containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + + class const_iterator + { + public: + using difference_type = ptrdiff_t; + using value_type = std::pair<const Key, const T>; + using reference = std::pair<const Key &, const T &>; + using pointer = mock_pointer<reference>; + using iterator_category = std::random_access_iterator_tag; + + const_iterator() = default; + + const_iterator(const containers *ac, size_type ai) + : c(ac), i(ai) + { + } + + const_iterator(iterator o) + : c(o.c), i(o.i) + { + } + + reference operator*() + { + return { c->keys[i], c->values[i] }; + } + + pointer operator->() + { + return { operator*() }; + } + + bool operator==(const const_iterator &o) const + { + return c == o.c && i == o.i; + } + + bool operator!=(const const_iterator &o) const + { + return !operator==(o); + } + + const_iterator &operator++() + { + ++i; + return *this; + } + + const_iterator operator++(int) + { + + const_iterator r = *this; + i++; + return r; + } + + const_iterator &operator--() + { + --i; + return *this; + } + + const_iterator operator--(int) + { + const_iterator r = *this; + i--; + return r; + } + + const_iterator &operator+=(size_type n) + { + i += n; + return *this; + } + + friend const_iterator operator+(size_type n, const const_iterator a) + { + const_iterator ret = a; + return ret += n; + } + + friend const_iterator operator+(const const_iterator a, size_type n) + { + return n + a; + } + + const_iterator &operator-=(size_type n) + { + i -= n; + return *this; + } + + friend const_iterator operator-(const const_iterator a, size_type n) + { + const_iterator ret = a; + return ret -= n; + } + + friend difference_type operator-(const const_iterator b, const const_iterator a) + { + return b.i - a.i; + } + + reference operator[](size_type n) + { + size_type k = i + n; + return { c->keys[k], c->values[k] }; + } + + bool operator<(const const_iterator &other) const + { + return i < other.i; + } + + bool operator>(const const_iterator &other) const + { + return i > other.i; + } + + bool operator<=(const const_iterator &other) const + { + return i <= other.i; + } + + bool operator>=(const const_iterator &other) const + { + return i >= other.i; + } + + const Key &key() const { return c->keys[i]; } + const T &value() { return c->values[i]; } + + private: + const containers *c = nullptr; + size_type i = 0; + friend full_map_t; + }; + +private: + template <class, class = void> + struct is_marked_transparent_type : std::false_type { }; + + template <class X> + struct is_marked_transparent_type<X, typename X::is_transparent> : std::true_type { }; + + template <class X> + using is_marked_transparent = typename std::enable_if< + is_marked_transparent_type<X>::value>::type *; + + template <typename It> + using is_compatible_iterator = typename std::enable_if< + std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *; + +public: + QFlatMap() = default; + + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values) + : c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values) + { + c.keys = std::move(keys); + c.values = values; + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = std::move(values); + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst) + : QFlatMap(lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last) + { + initWithRange(first, last); + ensureOrderedUnique(); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values) + { + c.keys = keys; + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values) + { + c.keys = std::move(keys); + c.values = values; + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values) + { + c.keys = keys; + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values) + { + c.keys = std::move(keys); + c.values = std::move(values); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst) + : QFlatMap(lst.begin(), lst.end()) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + initWithRange(first, last); + } + + explicit QFlatMap(const Compare &compare) + : value_compare(compare) + { + } + + explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{keys, values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values, + const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + ensureOrderedUnique(); + } + + explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare) + : QFlatMap(lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + ensureOrderedUnique(); + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{keys, values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + const mapped_container_type &values, const Compare &compare) + : value_compare(compare), c{std::move(keys), values} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{keys, std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys, + mapped_container_type &&values, const Compare &compare) + : value_compare(compare), c{std::move(keys), std::move(values)} + { + } + + explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst, + const Compare &compare) + : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare) + { + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare) + : value_compare(compare) + { + initWithRange(first, last); + } + + size_type count() const noexcept { return c.keys.size(); } + size_type size() const noexcept { return c.keys.size(); } + size_type capacity() const noexcept { return c.keys.capacity(); } + bool isEmpty() const noexcept { return c.keys.empty(); } + bool empty() const noexcept { return c.keys.empty(); } + containers extract() && { return std::move(c); } + const key_container_type &keys() const noexcept { return c.keys; } + const mapped_container_type &values() const noexcept { return c.values; } + + void reserve(size_type s) + { + c.keys.reserve(s); + c.values.reserve(s); + } + + void clear() + { + c.keys.clear(); + c.values.clear(); + } + + bool remove(const Key &key) + { + auto it = binary_find(key); + if (it != end()) { + c.keys.erase(toKeysIterator(it)); + c.values.erase(toValuesIterator(it)); + return true; + } + return false; + } + + iterator erase(iterator it) + { + c.values.erase(toValuesIterator(it)); + return fromKeysIterator(c.keys.erase(toKeysIterator(it))); + } + + T take(const Key &key) + { + auto it = binary_find(key); + if (it != end()) { + T result = std::move(it.value()); + erase(it); + return result; + } + return {}; + } + + bool contains(const Key &key) const + { + return binary_find(key) != end(); + } + + T value(const Key &key, const T &defaultValue) const + { + auto it = binary_find(key); + return it == end() ? defaultValue : it.value(); + } + + T value(const Key &key) const + { + auto it = binary_find(key); + return it == end() ? T() : it.value(); + } + + T &operator[](const Key &key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T &operator[](Key &&key) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.keys.insert(toKeysIterator(it), key); + return *c.values.insert(toValuesIterator(it), T()); + } + return it.value(); + } + + T operator[](const Key &key) const + { + return value(key); + } + + std::pair<iterator, bool> insert(const Key &key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + auto k = c.keys.insert(toKeysIterator(it), key); + return { fromKeysIterator(k), true }; + } else { + it.value() = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, const T &value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), value); + return { c.keys.insert(it, std::move(key)), true }; + } else { + *toValuesIterator(it) = value; + return {it, false}; + } + } + + std::pair<iterator, bool> insert(const Key &key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { c.keys.insert(it, key), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + std::pair<iterator, bool> insert(Key &&key, T &&value) + { + auto it = lower_bound(key); + if (it == end() || key_compare::operator()(key, it.key())) { + c.values.insert(toValuesIterator(it), std::move(value)); + return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true }; + } else { + *toValuesIterator(it) = std::move(value); + return {it, false}; + } + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(InputIt first, InputIt last) + { + insertRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(const value_type *first, const value_type *last) + { + insertRange(first, last); + } + + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last) + { + insertOrderedUniqueRange(first, last); + } + + // ### Merge with the templated version above + // once we can use std::disjunction in is_compatible_iterator. + void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last) + { + insertOrderedUniqueRange(first, last); + } + + iterator begin() { return { &c, 0 }; } + const_iterator begin() const { return { &c, 0 }; } + const_iterator cbegin() const { return begin(); } + const_iterator constBegin() const { return cbegin(); } + iterator end() { return { &c, c.keys.size() }; } + const_iterator end() const { return { &c, c.keys.size() }; } + const_iterator cend() const { return end(); } + const_iterator constEnd() const { return cend(); } + std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); } + std::reverse_iterator<const_iterator> rbegin() const + { + return std::reverse_iterator<const_iterator>(end()); + } + std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); } + std::reverse_iterator<iterator> rend() { + return std::reverse_iterator<iterator>(begin()); + } + std::reverse_iterator<const_iterator> rend() const + { + return std::reverse_iterator<const_iterator>(begin()); + } + std::reverse_iterator<const_iterator> crend() const { return rend(); } + + iterator lower_bound(const Key &key) + { + auto cit = const_cast<const full_map_t *>(this)->lower_bound(key); + return { &c, cit.i }; + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + iterator lower_bound(const X &key) + { + auto cit = const_cast<const full_map_t *>(this)->lower_bound(key); + return { &c, cit.i }; + } + + const_iterator lower_bound(const Key &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr> + const_iterator lower_bound(const X &key) const + { + return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp())); + } + + iterator find(const key_type &k) + { + return binary_find(k); + } + + const_iterator find(const key_type &k) const + { + return binary_find(k); + } + + key_compare key_comp() const noexcept + { + return static_cast<key_compare>(*this); + } + + value_compare value_comp() const noexcept + { + return static_cast<value_compare>(*this); + } + +private: + template <class InputIt, is_compatible_iterator<InputIt> = nullptr> + void initWithRange(InputIt first, InputIt last) + { + QtPrivate::reserveIfForwardIterator(this, first, last); + while (first != last) { + c.keys.push_back(first->first); + c.values.push_back(first->second); + ++first; + } + } + + iterator fromKeysIterator(typename key_container_type::iterator kit) + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const + { + return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) }; + } + + typename key_container_type::iterator toKeysIterator(iterator it) + { + return c.keys.begin() + it.i; + } + + typename mapped_container_type::iterator toValuesIterator(iterator it) + { + return c.values.begin() + it.i; + } + + template <class InputIt> + void insertRange(InputIt first, InputIt last) + { + size_type i = c.keys.size(); + c.keys.resize(i + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + ensureOrderedUnique(); + } + + class IndexedKeyComparator + { + public: + IndexedKeyComparator(const full_map_t *am) + : m(am) + { + } + + bool operator()(size_type i, size_type k) const + { + return m->key_comp()(m->c.keys[i], m->c.keys[k]); + } + + private: + const full_map_t *m; + }; + + template <class InputIt> + void insertOrderedUniqueRange(InputIt first, InputIt last) + { + const size_type s = c.keys.size(); + c.keys.resize(s + std::distance(first, last)); + c.values.resize(c.keys.size()); + for (size_type i = s; first != last; ++first, ++i) { + c.keys[i] = first->first; + c.values[i] = first->second; + } + + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + iterator binary_find(const Key &key) + { + return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i }; + } + + const_iterator binary_find(const Key &key) const + { + auto it = lower_bound(key); + if (it != end()) { + if (!key_compare::operator()(key, it.key())) + return it; + it = end(); + } + return it; + } + + void ensureOrderedUnique() + { + std::vector<size_type> p(size_t(c.keys.size())); + std::iota(p.begin(), p.end(), 0); + std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this)); + applyPermutation(p); + makeUnique(); + } + + void applyPermutation(const std::vector<size_type> &p) + { + const size_type s = c.keys.size(); + std::vector<bool> done(s); + for (size_type i = 0; i < s; ++i) { + if (done[i]) + continue; + done[i] = true; + size_type j = i; + size_type k = p[i]; + while (i != k) { + qSwap(c.keys[j], c.keys[k]); + qSwap(c.values[j], c.values[k]); + done[k] = true; + j = k; + k = p[j]; + } + } + } + + void makeUnique() + { + if (c.keys.size() < 2) + return; + auto k = std::end(c.keys) - 1; + auto i = k - 1; + for (;;) { + if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) { + if (i == std::begin(c.keys)) + break; + --i; + --k; + } else { + c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i)); + i = c.keys.erase(i); + if (i == std::begin(c.keys)) + break; + k = i + 1; + } + } + c.keys.shrink_to_fit(); + c.values.shrink_to_fit(); + } + + containers c; +}; + +QT_END_NAMESPACE + +#endif // QFLATMAP_P_H diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index a53d6db997..15f731a603 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1120,21 +1120,6 @@ uint qHash(long double key, uint seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 9 - However, you can store multiple values per key by using - insertMulti() instead of insert() (or using the convenience - subclass QMultiHash). If you want to retrieve all - the values for a single key, you can use values(const Key &key), - which returns a QList<T>: - - \snippet code/src_corelib_tools_qhash.cpp 10 - - The items that share the same key are available from most - recently to least recently inserted. A more efficient approach is - to call find() to get the iterator for the first item with a key - and iterate from there: - - \snippet code/src_corelib_tools_qhash.cpp 11 - If you only need to extract the values from a hash (not the keys), you can also use \l{foreach}: @@ -1435,9 +1420,8 @@ uint qHash(long double key, uint seed) noexcept /*! \fn template <class Key, class T> int QHash<Key, T>::remove(const Key &key) Removes all the items that have the \a key from the hash. - Returns the number of items removed which is usually 1 but will - be 0 if the key isn't in the hash, or greater than 1 if - insertMulti() has been used with the \a key. + Returns the number of items removed which is 1 if the key exists in the hash, + and 0 otherwise. \sa clear(), take(), QMultiHash::remove() */ @@ -1507,27 +1491,25 @@ uint qHash(long double key, uint seed) noexcept /*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::uniqueKeys() const \since 4.2 + \obsolete Returns a list containing all the keys in the map. Keys that occur multiple times in the map (because items were inserted with insertMulti(), or unite() was used) occur only once in the returned list. - \sa keys(), values() + \sa QMultiHash::uniqueKeys() */ /*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys() const Returns a list containing all the keys in the hash, in an arbitrary order. Keys that occur multiple times in the hash - (because items were inserted with insertMulti(), or unite() was - used) also occur multiple times in the list. - - To obtain a list of unique keys, where each key from the map only - occurs once, use uniqueKeys(). + (because the method is operating on a QMultiHash) also occur + multiple times in the list. The order is guaranteed to be the same as that used by values(). - \sa uniqueKeys(), values(), key() + \sa QMultiMap::uniqueKeys(), values(), key() */ /*! \fn template <class Key, class T> QList<Key> QHash<Key, T>::keys(const T &value) const @@ -1555,7 +1537,7 @@ uint qHash(long double key, uint seed) noexcept */ /*! \fn template <class Key, class T> QList<T> QHash<Key, T>::values(const Key &key) const - + \obsolete \overload Returns a list of all the values associated with the \a key, @@ -1592,6 +1574,7 @@ uint qHash(long double key, uint seed) noexcept */ /*! \fn template <class Key, class T> int QHash<Key, T>::count(const Key &key) const + \obsolete Returns the number of items associated with the \a key. @@ -1803,11 +1786,22 @@ uint qHash(long double key, uint seed) noexcept If there are multiple items with the \a key, the most recently inserted item's value is replaced with \a value. +*/ + +/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other) + \since 5.15 + + Inserts all the items in the \a other hash into this hash. + + If a key is common to both hashes, its value will be replaced with the + value stored in \a other. - \sa insertMulti() + \note If \a other contains multiple entries with the same key then the + final value of the key is undefined. */ /*! \fn template <class Key, class T> QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) + \obsolete Inserts a new item with the \a key and a value of \a value. @@ -1816,16 +1810,17 @@ uint qHash(long double key, uint seed) noexcept different from insert(), which overwrites the value of an existing item.) + This function is obsolete. Use QMultiHash or QMultiMap instead. + \sa insert(), values() */ /*! \fn template <class Key, class T> QHash &QHash<Key, T>::unite(const QHash &other) + \obsolete Inserts all the items in the \a other hash into this hash. If a key is common to both hashes, the resulting hash will contain the key multiple times. - - \sa insertMulti() */ /*! \fn template <class Key, class T> bool QHash<Key, T>::empty() const @@ -1966,10 +1961,7 @@ uint qHash(long double key, uint seed) noexcept \snippet code/src_corelib_tools_qhash.cpp 17 Unlike QMap, which orders its items by key, QHash stores its - items in an arbitrary order. The only guarantee is that items that - share the same key (because they were inserted using - QHash::insertMulti()) will appear consecutively, from the most - recently to the least recently inserted value. + items in an arbitrary order. Let's see a few examples of things we can do with a QHash::iterator that we cannot do with a QHash::const_iterator. @@ -2036,7 +2028,7 @@ uint qHash(long double key, uint seed) noexcept There is no direct way of changing an item's key through an iterator, although it can be done by calling QHash::erase() - followed by QHash::insert() or QHash::insertMulti(). + followed by QHash::insert(). \sa value() */ @@ -2198,7 +2190,7 @@ uint qHash(long double key, uint seed) noexcept Unlike QMap, which orders its items by key, QHash stores its items in an arbitrary order. The only guarantee is that items that share the same key (because they were inserted using - QHash::insertMulti()) will appear consecutively, from the most + a QMultiHash) will appear consecutively, from the most recently to the least recently inserted value. Multiple iterators can be used on the same hash. However, be aware @@ -2531,18 +2523,22 @@ uint qHash(long double key, uint seed) noexcept It inherits QHash and extends it with a few convenience functions that make it more suitable than QHash for storing multi-valued hashes. A multi-valued hash is a hash that allows multiple values - with the same key; QHash normally doesn't allow that, unless you - call QHash::insertMulti(). + with the same key. Because QMultiHash inherits QHash, all of QHash's functionality also applies to QMultiHash. For example, you can use isEmpty() to test whether the hash is empty, and you can traverse a QMultiHash using - QHash's iterator classes (for example, QHashIterator). But in - addition, it provides an insert() function that corresponds to - QHash::insertMulti(), and a replace() function that corresponds to + QHash's iterator classes (for example, QHashIterator). But opposed to + QHash, it provides an insert() function will allow the insertion of + multiple items with the same key. The replace() function corresponds to QHash::insert(). It also provides convenient operator+() and operator+=(). + Unlike QMultiMap, QMultiHash does not provide and ordering of the + inserted items. The only guarantee is that items that + share the same key will appear consecutively, from the most + recently to the least recently inserted value. + Example: \snippet code/src_corelib_tools_qhash.cpp 24 @@ -2597,7 +2593,7 @@ uint qHash(long double key, uint seed) noexcept \sa operator=() */ -/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash::QMultiHash(InputIterator begin, InputIterator end) +/*! \fn template <class Key, class T> template <class InputIterator> QMultiHash<Key, T>::QMultiHash(InputIterator begin, InputIterator end) \since 5.14 Constructs a multi-hash with a copy of each of the elements in the iterator range @@ -2633,7 +2629,8 @@ uint qHash(long double key, uint seed) noexcept \sa replace() */ -/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other) +/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other) + \since 5.13 Inserts all the items in the \a other hash into this hash and returns a reference to this hash. @@ -2641,6 +2638,32 @@ uint qHash(long double key, uint seed) noexcept \sa insert() */ +/*! \fn template <class Key, class T> QList<Key> QMultiHash<Key, T>::uniqueKeys() const + \since 5.13 + + Returns a list containing all the keys in the map. Keys that occur multiple + times in the map occur only once in the returned list. + + \sa keys(), values() +*/ + +/*! \fn template <class Key, class T> QList<T> QMultiHash<Key, T>::values(const Key &key) const + \overload + + Returns a list of all the values associated with the \a key, + from the most recently inserted to the least recently inserted. + + \sa count(), insert() +*/ + +/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::operator+=(const QMultiHash &other) + + Inserts all the items in the \a other hash into this hash + and returns a reference to this hash. + + \sa unite(), insert() +*/ + /*! \fn template <class Key, class T> QMultiHash QMultiHash<Key, T>::operator+(const QMultiHash &other) const Returns a hash that contains all the items in this hash in @@ -2670,6 +2693,13 @@ uint qHash(long double key, uint seed) noexcept \sa QHash::remove() */ +/*! \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key) const + + Returns the number of items associated with the \a key. + + \sa contains(), insert() +*/ + /*! \fn template <class Key, class T> int QMultiHash<Key, T>::count(const Key &key, const T &value) const \since 4.3 diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 9fd96686f5..c56324eef7 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -305,12 +305,14 @@ public: T &operator[](const Key &key); const T operator[](const Key &key) const; - QList<Key> uniqueKeys() const; QList<Key> keys() const; QList<Key> keys(const T &value) const; QList<T> values() const; - QList<T> values(const Key &key) const; - int count(const Key &key) const; +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QList<Key> uniqueKeys() const; + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QList<T> values(const Key &key) const; + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") int count(const Key &key) const; +#endif class const_iterator; @@ -322,7 +324,11 @@ public: QHashData::Node *i; public: +#if QT_DEPRECATED_SINCE(5, 15) typedef std::bidirectional_iterator_tag iterator_category; +#else + typedef std::forward_iterator_tag iterator_category; +#endif typedef qptrdiff difference_type; typedef T value_type; typedef T *pointer; @@ -347,21 +353,25 @@ public: i = QHashData::nextNode(i); return r; } - inline iterator &operator--() { +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED iterator &operator--() + { i = QHashData::previousNode(i); return *this; } - inline iterator operator--(int) { + inline QT_DEPRECATED iterator operator--(int) + { iterator r = *this; i = QHashData::previousNode(i); return r; } - inline iterator operator+(int j) const + inline QT_DEPRECATED iterator operator+(int j) const { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline iterator operator-(int j) const { return operator+(-j); } - inline iterator &operator+=(int j) { return *this = *this + j; } - inline iterator &operator-=(int j) { return *this = *this - j; } - friend inline iterator operator+(int j, iterator k) { return k + j; } + inline QT_DEPRECATED iterator operator-(int j) const { return operator+(-j); } + inline QT_DEPRECATED iterator &operator+=(int j) { return *this = *this + j; } + inline QT_DEPRECATED iterator &operator-=(int j) { return *this = *this - j; } + friend inline QT_DEPRECATED iterator operator+(int j, iterator k) { return k + j; } +#endif inline bool operator==(const const_iterator &o) const { return i == o.i; } inline bool operator!=(const const_iterator &o) const { return i != o.i; } @@ -372,11 +382,16 @@ public: { friend class iterator; friend class QHash<Key, T>; + friend class QMultiHash<Key, T>; friend class QSet<Key>; QHashData::Node *i; public: +#if QT_DEPRECATED_SINCE(5, 15) typedef std::bidirectional_iterator_tag iterator_category; +#else + typedef std::forward_iterator_tag iterator_category; +#endif typedef qptrdiff difference_type; typedef T value_type; typedef const T *pointer; @@ -404,21 +419,28 @@ public: i = QHashData::nextNode(i); return r; } - inline const_iterator &operator--() { +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED const_iterator &operator--() + { i = QHashData::previousNode(i); return *this; } - inline const_iterator operator--(int) { + inline QT_DEPRECATED const_iterator operator--(int) + { const_iterator r = *this; i = QHashData::previousNode(i); return r; } - inline const_iterator operator+(int j) const + inline QT_DEPRECATED const_iterator operator+(int j) const { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } - inline const_iterator operator-(int j) const { return operator+(-j); } - inline const_iterator &operator+=(int j) { return *this = *this + j; } - inline const_iterator &operator-=(int j) { return *this = *this - j; } - friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } + inline QT_DEPRECATED const_iterator operator-(int j) const { return operator+(-j); } + inline QT_DEPRECATED const_iterator &operator+=(int j) { return *this = *this + j; } + inline QT_DEPRECATED const_iterator &operator-=(int j) { return *this = *this - j; } + friend inline QT_DEPRECATED const_iterator operator+(int j, const_iterator k) + { + return k + j; + } +#endif }; friend class const_iterator; @@ -443,8 +465,14 @@ public: inline key_iterator &operator++() { ++i; return *this; } inline key_iterator operator++(int) { return key_iterator(i++);} - inline key_iterator &operator--() { --i; return *this; } - inline key_iterator operator--(int) { return key_iterator(i--); } +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED key_iterator &operator--() + { + --i; + return *this; + } + inline QT_DEPRECATED key_iterator operator--(int) { return key_iterator(i--); } +#endif const_iterator base() const { return i; } }; @@ -482,8 +510,11 @@ public: const_iterator find(const Key &key) const; const_iterator constFind(const Key &key) const; iterator insert(const Key &key, const T &value); - iterator insertMulti(const Key &key, const T &value); - QHash &unite(const QHash &other); + void insert(const QHash &hash); +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); + QT_DEPRECATED_X("Use QMultiHash for hashes storing multiple values with the same key.") QHash &unite(const QHash &other); +#endif // STL compatibility typedef T mapped_type; @@ -525,6 +556,7 @@ private: #endif } friend class QSet<Key>; + friend class QMultiHash<Key, T>; }; @@ -563,22 +595,6 @@ QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anex } template <class Key, class T> -Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) -{ - if (d == &QHashData::shared_null) { - *this = other; - } else { - QHash copy(other); - const_iterator it = copy.constEnd(); - while (it != copy.constBegin()) { - --it; - insertMulti(it.key(), it.value()); - } - } - return *this; -} - -template <class Key, class T> Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) { x->free_helper(deleteNode2); @@ -637,26 +653,6 @@ Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaul } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - const_iterator i = begin(); - if (i != end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == end()) - goto break_out_of_outer_loop; - } while (aKey == i.key()); - } - } -break_out_of_outer_loop: - return res; -} - -template <class Key, class T> Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const { QList<Key> res; @@ -715,32 +711,6 @@ Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *node = *findNode(akey); - if (node != e) { - do { - res.append(node->value); - } while ((node = node->next) != e && node->key == akey); - } - return res; -} - -template <class Key, class T> -Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const -{ - int cnt = 0; - Node *node = *findNode(akey); - if (node != e) { - do { - ++cnt; - } while ((node = node->next) != e && node->key == akey); - } - return cnt; -} - -template <class Key, class T> Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const { return value(akey); @@ -781,15 +751,28 @@ Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const K } template <class Key, class T> -Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey, - const T &avalue) +Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash) { + if (d == hash.d) + return; + detach(); - d->willGrow(); - uint h; - Node **nextNode = findNode(akey, &h); - return iterator(createNode(h, akey, avalue, nextNode)); + QHashData::Node *i = hash.d->firstNode(); + QHashData::Node *end = reinterpret_cast<QHashData::Node *>(hash.e); + while (i != end) { + Node *n = concrete(i); + Node **node = findNode(n->key, n->h); + if (*node == e) { + if (d->willGrow()) + node = findNode(n->key, n->h); + createNode(n->h, n->key, n->value, node); + } else { + if (!std::is_same<T, QHashDummyValue>::value) + (*node)->value = n->value; + } + i = QHashData::nextNode(i); + } } template <class Key, class T> @@ -1042,11 +1025,12 @@ public: inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) { return QHash<Key, T>::insert(key, value); } - inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value) - { return QHash<Key, T>::insertMulti(key, value); } + typename QHash<Key, T>::iterator insert(const Key &key, const T &value); + + inline QMultiHash &unite(const QMultiHash &other); inline QMultiHash &operator+=(const QMultiHash &other) - { this->unite(other); return *this; } + { return unite(other); } inline QMultiHash operator+(const QMultiHash &other) const { QMultiHash result = *this; result += other; return result; } @@ -1055,13 +1039,27 @@ public: using QHash<Key, T>::count; using QHash<Key, T>::find; using QHash<Key, T>::constFind; + using QHash<Key, T>::values; + using QHash<Key, T>::findNode; + using QHash<Key, T>::createNode; + using QHash<Key, T>::concrete; + using QHash<Key, T>::detach; + + using typename QHash<Key, T>::Node; + using typename QHash<Key, T>::iterator; + using typename QHash<Key, T>::const_iterator; bool contains(const Key &key, const T &value) const; int remove(const Key &key, const T &value); + int count(const Key &key) const; int count(const Key &key, const T &value) const; + QList<Key> uniqueKeys() const; + + QList<T> values(const Key &akey) const; + typename QHash<Key, T>::iterator find(const Key &key, const T &value) { typename QHash<Key, T>::iterator i(find(key)); typename QHash<Key, T>::iterator end(this->end()); @@ -1090,6 +1088,50 @@ private: }; template <class Key, class T> +Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &akey, const T &avalue) +{ + detach(); + this->d->willGrow(); + + uint h; + Node **nextNode = findNode(akey, &h); + return iterator(createNode(h, akey, avalue, nextNode)); +} + +template <class Key, class T> +Q_INLINE_TEMPLATE QMultiHash<Key, T> &QMultiHash<Key, T>::unite(const QMultiHash &other) +{ + if (this->d == &QHashData::shared_null) { + *this = other; + } else { +#if QT_DEPRECATED_SINCE(5, 15) + QMultiHash copy(other); + const_iterator it = copy.constEnd(); + while (it != copy.constBegin()) { + it.i = QHashData::previousNode(it.i); + insert(it.key(), it.value()); + } +#else + const QMultiHash copy(other); + const_iterator it = copy.cbegin(); + const const_iterator end = copy.cend(); + while (it != end) { + const auto rangeStart = it++; + while (it != end && rangeStart.key() == it.key()) + ++it; + const qint64 last = std::distance(rangeStart, it) - 1; + for (qint64 i = last; i >= 0; --i) { + auto next = std::next(rangeStart, i); + insert(next.key(), next.value()); + } + } +#endif + } + return *this; +} + + +template <class Key, class T> Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const { return constFind(key, value) != QHash<Key, T>::constEnd(); @@ -1126,8 +1168,257 @@ Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) return n; } -Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash) -Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash) +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<Key> QMultiHash<Key, T>::uniqueKeys() const +{ + QList<Key> res; + res.reserve(QHash<Key, T>::size()); // May be too much, but assume short lifetime + typename QHash<Key, T>::const_iterator i = QHash<Key, T>::begin(); + if (i != QHash<Key, T>::end()) { + for (;;) { + const Key &aKey = i.key(); + res.append(aKey); + do { + if (++i == QHash<Key, T>::end()) + goto break_out_of_outer_loop; + } while (aKey == i.key()); + } + } +break_out_of_outer_loop: + return res; +} + +#if QT_DEPRECATED_SINCE(5, 15) + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) { + return static_cast<QMultiHash<Key, T> *>(this)->insert(key, value); +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) { + return static_cast<QMultiHash<Key, T> *>(this)->unite(other); +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const +{ + return static_cast<const QMultiHash<Key, T> *>(this)->values(akey); +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const +{ + return static_cast<const QMultiHash<Key, T> *>(this)->count(akey); +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const +{ + return static_cast<const QMultiHash<Key, T> *>(this)->uniqueKeys(); +} +#endif + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<T> QMultiHash<Key, T>::values(const Key &akey) const +{ + QList<T> res; + Node *node = *findNode(akey); + if (node != this->e) { + do { + res.append(node->value); + } while ((node = node->next) != this->e && node->key == akey); + } + return res; +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &akey) const +{ + int cnt = 0; + Node *node = *findNode(akey); + if (node != this->e) { + do { + ++cnt; + } while ((node = node->next) != this->e && node->key == akey); + } + return cnt; +} + +template <class Key, class T> +class QHashIterator +{ + typedef typename QHash<Key, T>::const_iterator const_iterator; + typedef const_iterator Item; + QHash<Key, T> c; + const_iterator i, n; + inline bool item_exists() const { return n != c.constEnd(); } + +public: + inline QHashIterator(const QHash<Key, T> &container) + : c(container), i(c.constBegin()), n(c.constEnd()) + { + } + inline QHashIterator &operator=(const QHash<Key, T> &container) + { + c = container; + i = c.constBegin(); + n = c.constEnd(); + return *this; + } + inline void toFront() + { + i = c.constBegin(); + n = c.constEnd(); + } + inline void toBack() + { + i = c.constEnd(); + n = c.constEnd(); + } + inline bool hasNext() const { return i != c.constEnd(); } + inline Item next() + { + n = i++; + return n; + } + inline Item peekNext() const { return i; } + inline const T &value() const + { + Q_ASSERT(item_exists()); + return *n; + } + inline const Key &key() const + { + Q_ASSERT(item_exists()); + return n.key(); + } + inline bool findNext(const T &t) + { + while ((n = i) != c.constEnd()) + if (*i++ == t) + return true; + return false; + } +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED bool hasPrevious() const { return i != c.constBegin(); } + inline QT_DEPRECATED Item previous() + { + n = --i; + return n; + } + inline QT_DEPRECATED Item peekPrevious() const + { + const_iterator p = i; + return --p; + } + inline bool QT_DEPRECATED findPrevious(const T &t) + { + while (i != c.constBegin()) + if (*(n = --i) == t) + return true; + n = c.constEnd(); + return false; + } +#endif +}; + +template<class Key, class T> +class QMutableHashIterator +{ + typedef typename QHash<Key, T>::iterator iterator; + typedef typename QHash<Key, T>::const_iterator const_iterator; + typedef iterator Item; + QHash<Key, T> *c; + iterator i, n; + inline bool item_exists() const { return const_iterator(n) != c->constEnd(); } + +public: + inline QMutableHashIterator(QHash<Key, T> &container) : c(&container) + { + i = c->begin(); + n = c->end(); + } + inline QMutableHashIterator &operator=(QHash<Key, T> &container) + { + c = &container; + i = c->begin(); + n = c->end(); + return *this; + } + inline void toFront() + { + i = c->begin(); + n = c->end(); + } + inline void toBack() + { + i = c->end(); + n = c->end(); + } + inline bool hasNext() const { return const_iterator(i) != c->constEnd(); } + inline Item next() + { + n = i++; + return n; + } + inline Item peekNext() const { return i; } + inline void remove() + { + if (const_iterator(n) != c->constEnd()) { + i = c->erase(n); + n = c->end(); + } + } + inline void setValue(const T &t) + { + if (const_iterator(n) != c->constEnd()) + *n = t; + } + inline T &value() + { + Q_ASSERT(item_exists()); + return *n; + } + inline const T &value() const + { + Q_ASSERT(item_exists()); + return *n; + } + inline const Key &key() const + { + Q_ASSERT(item_exists()); + return n.key(); + } + inline bool findNext(const T &t) + { + while (const_iterator(n = i) != c->constEnd()) + if (*i++ == t) + return true; + return false; + } +#if QT_DEPRECATED_SINCE(5, 15) + inline QT_DEPRECATED bool hasPrevious() const { return const_iterator(i) != c->constBegin(); } + inline QT_DEPRECATED Item previous() + { + n = --i; + return n; + } + inline QT_DEPRECATED Item peekPrevious() const + { + iterator p = i; + return --p; + } + inline QT_DEPRECATED bool findPrevious(const T &t) + { + while (const_iterator(i) != c->constBegin()) + if (*(n = --i) == t) + return true; + n = c->end(); + return false; + } +#endif +}; template <class Key, class T> uint qHash(const QHash<Key, T> &key, uint seed = 0) diff --git a/src/corelib/tools/qline.cpp b/src/corelib/tools/qline.cpp index 3afd23d76b..dde66ed093 100644 --- a/src/corelib/tools/qline.cpp +++ b/src/corelib/tools/qline.cpp @@ -374,7 +374,7 @@ QDataStream &operator>>(QDataStream &stream, QLine &line) */ /*! - \enum QLineF::IntersectionType + \enum QLineF::IntersectType Describes the intersection between two lines. diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index a0ec372f9a..d747a8cda4 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -468,10 +468,9 @@ void QMapDataBase::freeData(QMapDataBase *d) \snippet code/src_corelib_tools_qmap.cpp 9 However, you can store multiple values per key by using - insertMulti() instead of insert() (or using the convenience - subclass QMultiMap). If you want to retrieve all the values for a - single key, you can use values(const Key &key), which returns a - QList<T>: + using the subclass QMultiMap. If you want + to retrieve all the values for a single key, you can use + values(const Key &key), which returns a QList<T>: \snippet code/src_corelib_tools_qmap.cpp 10 @@ -676,9 +675,8 @@ void QMapDataBase::freeData(QMapDataBase *d) /*! \fn template <class Key, class T> int QMap<Key, T>::remove(const Key &key) Removes all the items that have the key \a key from the map. - Returns the number of items removed which is usually 1 but will be - 0 if the key isn't in the map, or \> 1 if insertMulti() has been - used with the \a key. + Returns the number of items removed which will be 1 if the key + exists in the map, and 0 otherwise. \sa clear(), take(), QMultiMap::remove() */ @@ -742,28 +740,26 @@ void QMapDataBase::freeData(QMapDataBase *d) /*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const \since 4.2 + \obsolete Returns a list containing all the keys in the map in ascending order. Keys that occur multiple times in the map (because items were inserted with insertMulti(), or unite() was used) occur only once in the returned list. - \sa keys(), values() + \sa QMultiMap::uniqueKeys() */ /*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const Returns a list containing all the keys in the map in ascending - order. Keys that occur multiple times in the map (because items - were inserted with insertMulti(), or unite() was used) also - occur multiple times in the list. - - To obtain a list of unique keys, where each key from the map only - occurs once, use uniqueKeys(). + order. Keys that occur multiple times in the map (because the + method is operating on a QMultiMap) also occur multiple times + in the list. The order is guaranteed to be the same as that used by values(). - \sa uniqueKeys(), values(), key() + \sa QMultiMap::uniqueKeys(), values(), key() */ /*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys(const T &value) const @@ -806,6 +802,7 @@ void QMapDataBase::freeData(QMapDataBase *d) */ /*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const + \obsolete \overload @@ -813,14 +810,15 @@ void QMapDataBase::freeData(QMapDataBase *d) \a key, from the most recently inserted to the least recently inserted one. - \sa count(), insertMulti() + \sa QMultiMap::values() */ /*! \fn template <class Key, class T> int QMap<Key, T>::count(const Key &key) const + \obsolete Returns the number of items associated with key \a key. - \sa contains(), insertMulti(), QMultiMap::count() + \sa QMultiMap::count() */ /*! \fn template <class Key, class T> int QMap<Key, T>::count() const @@ -1118,7 +1116,7 @@ void QMapDataBase::freeData(QMapDataBase *d) If there are multiple items with the key \a key, the most recently inserted item's value is replaced with \a value. - \sa insertMulti() + \sa QMultiMap::insert() */ /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value) @@ -1147,10 +1145,25 @@ void QMapDataBase::freeData(QMapDataBase *d) \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might crash but there is also a risk that it will silently corrupt both the map and the \a pos map. - \sa insertMulti() + \sa QMultiMap::insert() +*/ + +/*! \fn template <class Key, class T> void QMap<Key, T>::insert(const QMap<Key, T> &map) + \since 5.15 + + Inserts all the items in \a map into this map. + + If a key is common to both maps, its value will be replaced with + the value stored in \a map. + + \note If \a map contains multiple entries with the same key then the + final value of the key is undefined. + + \sa QMultiMap::insert() */ /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) + \obsolete Inserts a new item with the key \a key and a value of \a value. @@ -1159,12 +1172,13 @@ void QMapDataBase::freeData(QMapDataBase *d) different from insert(), which overwrites the value of an existing item.) - \sa insert(), values() + \sa QMultiMap::insert() */ /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value) \overload \since 5.1 + \obsolete Inserts a new item with the key \a key and value \a value and with hint \a pos suggesting where to do the insert. @@ -1178,17 +1192,18 @@ void QMapDataBase::freeData(QMapDataBase *d) \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might crash but there is also a risk that it will silently corrupt both the map and the \a pos map. - \sa insert() + \sa QMultiMap::insert() */ /*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) + \obsolete Inserts all the items in the \a other map into this map. If a key is common to both maps, the resulting map will contain the key multiple times. - \sa insertMulti() + \sa QMultiMap::unite() */ /*! \typedef QMap::Iterator @@ -1271,9 +1286,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Unlike QHash, which stores its items in an arbitrary order, QMap stores its items ordered by key. Items that share the same key - (because they were inserted using QMap::insertMulti(), or due to a - unite()) will appear consecutively, from the most recently to the - least recently inserted value. + (because the map is a QMultiMap) will appear consecutively, + from the most recently to the least recently inserted value. Let's see a few examples of things we can do with a QMap::iterator that we cannot do with a QMap::const_iterator. @@ -1519,9 +1533,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Unlike QHash, which stores its items in an arbitrary order, QMap stores its items ordered by key. Items that share the same key - (because they were inserted using QMap::insertMulti()) will - appear consecutively, from the most recently to the least - recently inserted value. + (because the map is a QMultiMap) will appear consecutively, + from the most recently to the least recently inserted value. Multiple iterators can be used on the same map. If you add items to the map, existing iterators will remain valid. If you remove @@ -1893,20 +1906,20 @@ void QMapDataBase::freeData(QMapDataBase *d) \reentrant QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}. - It inherits QMap and extends it with a few convenience functions - that make it more suitable than QMap for storing multi-valued - maps. A multi-valued map is a map that allows multiple values - with the same key; QMap normally doesn't allow that, unless you - call QMap::insertMulti(). + It inherits QMap and extends it with a few functions + that make it able to store multi-valued maps. A multi-valued map + is a map that allows multiple values with the same key; QMap + doesn't allow that. Because QMultiMap inherits QMap, all of QMap's functionality also applies to QMultiMap. For example, you can use isEmpty() to test whether the map is empty, and you can traverse a QMultiMap using QMap's iterator classes (for example, QMapIterator). But in - addition, it provides an insert() function that corresponds to - QMap::insertMulti(), and a replace() function that corresponds to - QMap::insert(). It also provides convenient operator+() and - operator+=(). + addition, it provides an insert() function that inserts but does + not overwrite any previous value if the key already exists, + and a replace() function that corresponds which does overwite + an existing value if they key is already in the map. + It also provides convenient operator+() and operator+=(). Example: \snippet code/src_corelib_tools_qmap.cpp 25 @@ -2095,4 +2108,24 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa QMap::constFind() */ +/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const + + Returns a list containing all the values associated with key + \a key, from the most recently inserted to the least recently + inserted one. +*/ + +/*! \fn template <class Key, class T> int QMultiMap<Key, T>::count(const Key &key) const + + Returns the number of items associated with key \a key. +*/ + +/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const + \since 4.2 + + Returns a list containing all the keys in the map in ascending + order. Keys that occur multiple times in the map occur only + once in the returned list. +*/ + QT_END_NAMESPACE diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index f169ed5e49..a70b355c67 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -369,12 +369,15 @@ public: T &operator[](const Key &key); const T operator[](const Key &key) const; - QList<Key> uniqueKeys() const; QList<Key> keys() const; QList<Key> keys(const T &value) const; QList<T> values() const; - QList<T> values(const Key &key) const; - int count(const Key &key) const; +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QList<Key> uniqueKeys() const; + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QList<T> values(const Key &key) const; + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") int count(const Key &key) const; +#endif + inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); } @@ -436,6 +439,7 @@ public: inline bool operator==(const const_iterator &o) const { return i == o.i; } inline bool operator!=(const const_iterator &o) const { return i != o.i; } friend class QMap<Key, T>; + friend class QMultiMap<Key, T>; }; friend class iterator; @@ -488,6 +492,7 @@ public: friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } friend class QMap<Key, T>; + friend class QMultiMap<Key, T>; }; friend class const_iterator; @@ -552,9 +557,12 @@ public: const_iterator upperBound(const Key &key) const; iterator insert(const Key &key, const T &value); iterator insert(const_iterator pos, const Key &key, const T &value); - iterator insertMulti(const Key &key, const T &value); - iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); - QMap<Key, T> &unite(const QMap<Key, T> &other); + void insert(const QMap<Key, T> &map); +#if QT_DEPRECATED_SINCE(5, 15) + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value); + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); + QT_DEPRECATED_X("Use QMultiMap for maps storing multiple values with the same key.") QMap<Key, T> &unite(const QMap<Key, T> &other); +#endif // STL compatibility typedef Key key_type; @@ -583,6 +591,8 @@ private: return true; #endif } + + friend class QMultiMap<Key, T>; }; template <class Key, class T> @@ -645,23 +655,6 @@ Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey) } template <class Key, class T> -Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const -{ - Node *firstNode; - Node *lastNode; - d->nodeRange(akey, &firstNode, &lastNode); - - const_iterator ci_first(firstNode); - const const_iterator ci_last(lastNode); - int cnt = 0; - while (ci_first != ci_last) { - ++cnt; - ++ci_first; - } - return cnt; -} - -template <class Key, class T> Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const { return d->findNode(akey) != nullptr; @@ -763,70 +756,44 @@ typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const K } template <class Key, class T> -Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey, - const T &avalue) +Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map) { - detach(); - Node* y = d->end(); - Node* x = static_cast<Node *>(d->root()); - bool left = true; - while (x != nullptr) { - left = !qMapLessThanKey(x->key, akey); - y = x; - x = left ? x->leftNode() : x->rightNode(); - } - Node *z = d->createNode(akey, avalue, y, left); - return iterator(z); -} + if (d == map.d) + return; -template <class Key, class T> -typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) -{ - if (d->ref.isShared()) - return this->insertMulti(akey, avalue); - - Q_ASSERT_X(isValidIterator(pos), "QMap::insertMulti", "The specified const_iterator argument 'pos' is invalid"); - - if (pos == constEnd()) { - // Hint is that the Node is larger than (or equal to) the largest value. - Node *n = static_cast<Node *>(pos.i->left); - if (n) { - while (n->right) - n = static_cast<Node *>(n->right); + detach(); - if (!qMapLessThanKey(n->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - Node *z = d->createNode(akey, avalue, n, false); // insert right most - return iterator(z); + Node *n = d->root(); + auto it = map.cbegin(); + const auto e = map.cend(); + while (it != e) { + // Insertion here is based on insert(Key, T) + auto parent = d->end(); + bool left = true; + Node *lastNode = nullptr; + while (n) { + parent = n; + if (!qMapLessThanKey(n->key, it.key())) { + lastNode = n; + n = n->leftNode(); + left = true; + } else { + n = n->rightNode(); + left = false; + } } - return this->insertMulti(akey, avalue); - } else { - // Hint indicates that the node should be less (or equal to) the hint given - // but larger than the previous value. - Node *next = const_cast<Node*>(pos.i); - if (qMapLessThanKey(next->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - - if (pos == constBegin()) { - // There is no previous value (insert left most) - Node *z = d->createNode(akey, avalue, begin().i, true); - return iterator(z); + if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) { + lastNode->value = it.value(); + n = lastNode; } else { - Node *prev = const_cast<Node*>(pos.i->previousNode()); - if (!qMapLessThanKey(prev->key, akey)) - return this->insertMulti(akey, avalue); // ignore hint - - // Hint is ok - do insert - if (prev->right == nullptr) { - Node *z = d->createNode(akey, avalue, prev, false); - return iterator(z); - } - if (next->left == nullptr) { - Node *z = d->createNode(akey, avalue, next, true); - return iterator(z); - } - Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. - return this->insertMulti(akey, avalue); + n = d->createNode(it.key(), it.value(), parent, left); + } + ++it; + if (it != e) { + // Move back up the tree until we find the next branch or node which is + // relevant for the next key. + while (n != d->root() && qMapLessThanKey(n->key, it.key())) + n = static_cast<Node *>(n->parent()); } } } @@ -854,19 +821,6 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key & } template <class Key, class T> -Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) -{ - QMap<Key, T> copy(other); - const_iterator it = copy.constEnd(); - const const_iterator b = copy.constBegin(); - while (it != b) { - --it; - insertMulti(it.key(), it.value()); - } - return *this; -} - -template <class Key, class T> QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey) { detach(); @@ -982,26 +936,6 @@ Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const -{ - QList<Key> res; - res.reserve(size()); // May be too much, but assume short lifetime - const_iterator i = begin(); - if (i != end()) { - for (;;) { - const Key &aKey = i.key(); - res.append(aKey); - do { - if (++i == end()) - goto break_out_of_outer_loop; - } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) - } - } -break_out_of_outer_loop: - return res; -} - -template <class Key, class T> Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const { QList<Key> res; @@ -1054,21 +988,6 @@ Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const } template <class Key, class T> -Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const -{ - QList<T> res; - Node *n = d->findNode(akey); - if (n) { - const_iterator it(n); - do { - res.append(*it); - ++it; - } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key())); - } - return res; -} - -template <class Key, class T> Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const { Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; @@ -1164,15 +1083,20 @@ public: QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {} void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); } + QList<Key> uniqueKeys() const; + QList<T> values(const Key &key) const; + + using typename QMap<Key, T>::iterator; + using typename QMap<Key, T>::const_iterator; + inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value) { return QMap<Key, T>::insert(key, value); } - inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value) - { return QMap<Key, T>::insertMulti(key, value); } - inline typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value) - { return QMap<Key, T>::insertMulti(pos, key, value); } + iterator insert(const Key &key, const T &value); + iterator insert(const_iterator pos, const Key &key, const T &value); + QMultiMap &unite(const QMultiMap &other); inline QMultiMap &operator+=(const QMultiMap &other) - { this->unite(other); return *this; } + { return unite(other); } inline QMultiMap operator+(const QMultiMap &other) const { QMultiMap result = *this; result += other; return result; } @@ -1181,11 +1105,18 @@ public: using QMap<Key, T>::count; using QMap<Key, T>::find; using QMap<Key, T>::constFind; + using QMap<Key, T>::values; + using QMap<Key, T>::size; + using QMap<Key, T>::detach; + using QMap<Key, T>::erase; + using QMap<Key, T>::isValidIterator; + using typename QMap<Key, T>::Node; bool contains(const Key &key, const T &value) const; int remove(const Key &key, const T &value); + int count(const Key &key) const; int count(const Key &key, const T &value) const; typename QMap<Key, T>::iterator find(const Key &key, const T &value) { @@ -1216,6 +1147,123 @@ private: }; template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const +{ + QList<Key> res; + res.reserve(size()); // May be too much, but assume short lifetime + const_iterator i = this->begin(); + if (i != this->end()) { + for (;;) { + const Key &aKey = i.key(); + res.append(aKey); + do { + if (++i == this->end()) + goto break_out_of_outer_loop; + } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) + } + } +break_out_of_outer_loop: + return res; +} + +template <class Key, class T> +Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const +{ + QList<T> res; + Node *n = this->d->findNode(akey); + if (n) { + const_iterator it(n); + do { + res.append(*it); + ++it; + } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key())); + } + return res; +} + +template <class Key, class T> +Q_INLINE_TEMPLATE typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey, + const T &avalue) +{ + detach(); + Node* y = this->d->end(); + Node* x = static_cast<Node *>(this->d->root()); + bool left = true; + while (x != nullptr) { + left = !qMapLessThanKey(x->key, akey); + y = x; + x = left ? x->leftNode() : x->rightNode(); + } + Node *z = this->d->createNode(akey, avalue, y, left); + return iterator(z); +} + +template <class Key, class T> +typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue) +{ + if (this->d->ref.isShared()) + return insert(akey, avalue); + + Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'pos' is invalid"); + + if (pos == this->constEnd()) { + // Hint is that the Node is larger than (or equal to) the largest value. + Node *n = static_cast<Node *>(pos.i->left); + if (n) { + while (n->right) + n = static_cast<Node *>(n->right); + + if (!qMapLessThanKey(n->key, akey)) + return insert(akey, avalue); // ignore hint + Node *z = this->d->createNode(akey, avalue, n, false); // insert right most + return iterator(z); + } + return insert(akey, avalue); + } else { + // Hint indicates that the node should be less (or equal to) the hint given + // but larger than the previous value. + Node *next = const_cast<Node*>(pos.i); + if (qMapLessThanKey(next->key, akey)) + return insert(akey, avalue); // ignore hint + + if (pos == this->constBegin()) { + // There is no previous value (insert left most) + Node *z = this->d->createNode(akey, avalue, this->begin().i, true); + return iterator(z); + } else { + Node *prev = const_cast<Node*>(pos.i->previousNode()); + if (!qMapLessThanKey(prev->key, akey)) + return insert(akey, avalue); // ignore hint + + // Hint is ok - do insert + if (prev->right == nullptr) { + Node *z = this->d->createNode(akey, avalue, prev, false); + return iterator(z); + } + if (next->left == nullptr) { + Node *z = this->d->createNode(akey, avalue, next, true); + return iterator(z); + } + Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. + return insert(akey, avalue); + } + } +} + +template <class Key, class T> +Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) +{ + QMultiMap<Key, T> copy(other); + const_iterator it = copy.constEnd(); + const const_iterator b = copy.constBegin(); + while (it != b) { + --it; + insert(it.key(), it.value()); + } + return *this; +} + +template <class Key, class T> Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const { return constFind(key, value) != QMap<Key, T>::constEnd(); @@ -1229,7 +1277,7 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); while (i != end && !qMapLessThanKey<Key>(key, i.key())) { if (i.value() == value) { - i = this->erase(i); + i = erase(i); ++n; } else { ++i; @@ -1239,6 +1287,23 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) } template <class Key, class T> +Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &akey) const +{ + QMultiMap::Node *firstNode; + QMultiMap::Node *lastNode; + this->d->nodeRange(akey, &firstNode, &lastNode); + + const_iterator ci_first(firstNode); + const const_iterator ci_last(lastNode); + int cnt = 0; + while (ci_first != ci_last) { + ++cnt; + ++ci_first; + } + return cnt; +} + +template <class Key, class T> Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const { int n = 0; @@ -1252,6 +1317,44 @@ Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) c return n; } +#if QT_DEPRECATED_SINCE(5, 15) +template<class Key, class T> +QList<Key> QMap<Key, T>::uniqueKeys() const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys(); +} + +template<class Key, class T> +QList<T> QMap<Key, T>::values(const Key &key) const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->values(key); +} + +template<class Key, class T> +int QMap<Key, T>::count(const Key &key) const +{ + return static_cast<const QMultiMap<Key, T> *>(this)->count(key); +} + +template<class Key, class T> +typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) +{ + return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value); +} + +template<class Key, class T> +typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) +{ + return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue); +} + +template<class Key, class T> +QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) +{ + return static_cast<QMultiMap<Key, T> *>(this)->unite(other); +} +#endif + Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) diff --git a/src/corelib/tools/qpoint.h b/src/corelib/tools/qpoint.h index fe952f95da..f0a91c4ff8 100644 --- a/src/corelib/tools/qpoint.h +++ b/src/corelib/tools/qpoint.h @@ -352,6 +352,7 @@ Q_DECL_RELAXED_CONSTEXPR inline QPointF &QPointF::operator*=(qreal c) QT_WARNING_PUSH QT_WARNING_DISABLE_CLANG("-Wfloat-equal") QT_WARNING_DISABLE_GCC("-Wfloat-equal") +QT_WARNING_DISABLE_INTEL(1572) Q_DECL_CONSTEXPR inline bool operator==(const QPointF &p1, const QPointF &p2) { diff --git a/src/corelib/tools/qrect.h b/src/corelib/tools/qrect.h index 7aa2312f38..c6bfc1a50d 100644 --- a/src/corelib/tools/qrect.h +++ b/src/corelib/tools/qrect.h @@ -665,6 +665,7 @@ Q_DECL_CONSTEXPR inline QRectF::QRectF(const QRect &r) noexcept QT_WARNING_PUSH QT_WARNING_DISABLE_CLANG("-Wfloat-equal") QT_WARNING_DISABLE_GCC("-Wfloat-equal") +QT_WARNING_DISABLE_INTEL(1572) Q_DECL_CONSTEXPR inline bool QRectF::isNull() const noexcept { return w == 0. && h == 0.; } diff --git a/src/corelib/tools/qscopedvaluerollback.h b/src/corelib/tools/qscopedvaluerollback.h index f904b8dfcb..b8ceff6665 100644 --- a/src/corelib/tools/qscopedvaluerollback.h +++ b/src/corelib/tools/qscopedvaluerollback.h @@ -45,7 +45,11 @@ QT_BEGIN_NAMESPACE template <typename T> -class QScopedValueRollback +class +#if QT_HAS_CPP_ATTRIBUTE(nodiscard) && __cplusplus >= 201703L +[[nodiscard]] +#endif +QScopedValueRollback { public: explicit QScopedValueRollback(T &var) diff --git a/src/corelib/tools/qscopeguard.h b/src/corelib/tools/qscopeguard.h index 45c3f93da4..40d2747b1d 100644 --- a/src/corelib/tools/qscopeguard.h +++ b/src/corelib/tools/qscopeguard.h @@ -51,7 +51,7 @@ template <typename F> QScopeGuard<F> qScopeGuard(F f); template <typename F> class -#if QT_HAS_CPP_ATTRIBUTE(nodiscard) +#if __has_cpp_attribute(nodiscard) // Q_REQUIRED_RESULT can be defined as __warn_unused_result__ or as [[nodiscard]] // but the 1st one has some limitations for example can be placed only on functions. Q_REQUIRED_RESULT @@ -91,7 +91,7 @@ private: template <typename F> -#if QT_HAS_CPP_ATTRIBUTE(nodiscard) +#if __has_cpp_attribute(nodiscard) Q_REQUIRED_RESULT #endif QScopeGuard<F> qScopeGuard(F f) diff --git a/src/corelib/tools/qscopeguard.qdoc b/src/corelib/tools/qscopeguard.qdoc index 5a9b7fd210..6b3c942e84 100644 --- a/src/corelib/tools/qscopeguard.qdoc +++ b/src/corelib/tools/qscopeguard.qdoc @@ -51,10 +51,10 @@ QT_BEGIN_NAMESPACE of the scope. \ingroup misc - QScopeGuard<F> is a class which sole purpose is to run a function \e F in - its destructor. This is useful for guaranteeing your cleanup code is - executed, whether the function is exited normally, exited early by a return - statement, or exited by an exception. + QScopeGuard<F> is a class of which the sole purpose is to run the function + \a f in its destructor. This is useful for guaranteeing + your cleanup code is executed, whether the function is exited normally, + exited early by a return statement, or exited by an exception. If \e F is a lambda then you cannot instantiate the template directly, therefore the qScopeGuard() helper is provided and QScopeGuard<F> is made a diff --git a/src/corelib/tools/qsharedpointer.cpp b/src/corelib/tools/qsharedpointer.cpp index f185d2f23f..0576fb2bd0 100644 --- a/src/corelib/tools/qsharedpointer.cpp +++ b/src/corelib/tools/qsharedpointer.cpp @@ -1285,6 +1285,8 @@ \relates QSharedPointer \since 5.14 + Returns a shared pointer to the pointer held by \a src. + Same as qSharedPointerObjectCast(). This function is provided for STL compatibility. */ diff --git a/src/corelib/tools/qsimd.cpp b/src/corelib/tools/qsimd.cpp index d7c1d8c4a9..75c380ee8a 100644 --- a/src/corelib/tools/qsimd.cpp +++ b/src/corelib/tools/qsimd.cpp @@ -685,7 +685,7 @@ static QT_FUNCTION_TARGET(RDRND) Q_DECL_COLD_FUNCTION bool checkRdrndWorks() noe // Check the results for equality if (testBuffer[0] == testBuffer[1] && testBuffer[0] == testBuffer[2] - && end == testBuffer + TestBufferSize && testBuffer[0] == testBuffer[3]) { + && (end < testBuffer + TestBufferSize || testBuffer[0] == testBuffer[3])) { fprintf(stderr, "WARNING: CPU random generator seem to be failing, " "disabling hardware random number generation\n" "WARNING: RDRND generated:"); diff --git a/src/corelib/tools/qsimd_p.h b/src/corelib/tools/qsimd_p.h index c28624a25e..26e98c4542 100644 --- a/src/corelib/tools/qsimd_p.h +++ b/src/corelib/tools/qsimd_p.h @@ -346,7 +346,7 @@ extern Q_CORE_EXPORT QBasicAtomicInteger<unsigned> qt_cpu_features[2]; #endif Q_CORE_EXPORT quint64 qDetectCpuFeatures(); -#if defined(Q_PROCESSOR_X86) && QT_COMPILER_SUPPORTS_HERE(RDRND) +#if defined(Q_PROCESSOR_X86) && QT_COMPILER_SUPPORTS_HERE(RDRND) && !defined(QT_BOOTSTRAPPED) Q_CORE_EXPORT qsizetype qRandomCpu(void *, qsizetype) noexcept; #else static inline qsizetype qRandomCpu(void *, qsizetype) noexcept diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h index 5def2eceb2..3e98de41f4 100644 --- a/src/corelib/tools/qvector.h +++ b/src/corelib/tools/qvector.h @@ -1,6 +1,7 @@ /**************************************************************************** ** ** Copyright (C) 2016 The Qt Company Ltd. +** Copyright (C) 2019 Intel Corporation ** Contact: https://www.qt.io/licensing/ ** ** This file is part of the QtCore module of the Qt Toolkit. @@ -40,22 +41,15 @@ #ifndef QVECTOR_H #define QVECTOR_H -#include <QtCore/qalgorithms.h> -#include <QtCore/qiterator.h> -#include <QtCore/qrefcount.h> -#include <QtCore/qarraydata.h> +#include <QtCore/qarraydatapointer.h> +#include <QtCore/qnamespace.h> #include <QtCore/qhashfunctions.h> -#include <QtCore/qcontainertools_impl.h> +#include <QtCore/qiterator.h> -#include <iterator> +#include <functional> +#include <limits> #include <initializer_list> -#if QT_VERSION < QT_VERSION_CHECK(6,0,0) -#include <vector> -#endif -#include <stdlib.h> -#include <string.h> - -#include <algorithm> +#include <type_traits> QT_BEGIN_NAMESPACE @@ -79,90 +73,234 @@ class QVector #endif { typedef QTypedArrayData<T> Data; - Data *d; + typedef QArrayDataOps<T> DataOps; + typedef QArrayDataPointer<T> DataPointer; + class DisableRValueRefs {}; + + DataPointer d; template <typename V, typename U> friend int QtPrivate::indexOf(const QVector<V> &list, const U &u, int from); template <typename V, typename U> friend int QtPrivate::lastIndexOf(const QVector<V> &list, const U &u, int from); public: - inline QVector() noexcept : d(Data::sharedNull()) { } - explicit QVector(int size); - QVector(int size, const T &t); - inline QVector(const QVector<T> &v); - inline ~QVector() { if (!d->ref.deref()) freeData(d); } - QVector<T> &operator=(const QVector<T> &v); - QVector(QVector<T> &&other) noexcept : d(other.d) { other.d = Data::sharedNull(); } - QVector<T> &operator=(QVector<T> &&other) noexcept - { QVector moved(std::move(other)); swap(moved); return *this; } + typedef T Type; + typedef T value_type; + typedef value_type *pointer; + typedef const value_type *const_pointer; + typedef value_type &reference; + typedef const value_type &const_reference; + typedef int size_type; + typedef qptrdiff difference_type; + typedef typename Data::iterator iterator; + typedef typename Data::const_iterator const_iterator; + typedef iterator Iterator; + typedef const_iterator ConstIterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef typename DataPointer::parameter_type parameter_type; + using rvalue_ref = typename std::conditional<DataPointer::pass_parameter_by_value, DisableRValueRefs, T &&>::type; + +private: + void resize_internal(int i, Qt::Initialization); + bool isValidIterator(const_iterator i) const + { + const std::less<const T*> less = {}; + return !less(d->end(), i) && !less(i, d->begin()); + } +public: + QVector(DataPointer dd) noexcept + : d(dd) + { + } + +public: + inline QVector() noexcept { } + explicit QVector(int size) + : d(Data::allocate(size)) + { + if (size) + d->appendInitialize(size); + } + QVector(int size, const T &t) + : d(Data::allocate(size)) + { + if (size) + d->copyAppend(size, t); + } + + inline QVector(const QVector<T> &other) noexcept : d(other.d) {} + QVector(QVector<T> &&other) noexcept : d(std::move(other.d)) {} + inline QVector(std::initializer_list<T> args) + : d(Data::allocate(args.size())) + { + if (args.size()) + d->copyAppend(args.begin(), args.end()); + } + + ~QVector() /*noexcept(std::is_nothrow_destructible<T>::value)*/ {} + QVector<T> &operator=(const QVector<T> &other) { d = other.d; return *this; } + QVector &operator=(QVector &&other) noexcept(std::is_nothrow_destructible<T>::value) + { + d = std::move(other.d); + return *this; + } + QVector<T> &operator=(std::initializer_list<T> args) + { + d = DataPointer(Data::allocate(args.size())); + if (args.size()) + d->copyAppend(args.begin(), args.end()); + return *this; + } + template <typename InputIterator, QtPrivate::IfIsForwardIterator<InputIterator> = true> + QVector(InputIterator i1, InputIterator i2) + : d(Data::allocate(std::distance(i1, i2))) + { + if (std::distance(i1, i2)) + d->copyAppend(i1, i2); + } + + template <typename InputIterator, QtPrivate::IfIsNotForwardIterator<InputIterator> = true> + QVector(InputIterator i1, InputIterator i2) + : QVector() + { + QtPrivate::reserveIfForwardIterator(this, i1, i2); + std::copy(i1, i2, std::back_inserter(*this)); + } + void swap(QVector<T> &other) noexcept { qSwap(d, other.d); } - inline QVector(std::initializer_list<T> args); - QVector<T> &operator=(std::initializer_list<T> args); - template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> - inline QVector(InputIterator first, InputIterator last); - explicit QVector(QArrayDataPointerRef<T> ref) noexcept : d(ref.ptr) {} - bool operator==(const QVector<T> &v) const; - inline bool operator!=(const QVector<T> &v) const { return !(*this == v); } + friend bool operator==(const QVector &l, const QVector &r) + { + if (l.size() != r.size()) + return false; + if (l.begin() == r.begin()) + return true; - inline int size() const { return d->size; } + // do element-by-element comparison + return l.d->compare(l.begin(), r.begin(), l.size()); + } + friend bool operator!=(const QVector &l, const QVector &r) + { + return !(l == r); + } - inline bool isEmpty() const { return d->size == 0; } + int size() const noexcept { return int(d->size); } + int count() const noexcept { return size(); } + int length() const noexcept { return size(); } - void resize(int size); + inline bool isEmpty() const noexcept { return d->size == 0; } - inline int capacity() const { return int(d->alloc); } - void reserve(int size); - inline void squeeze() + void resize(int size) { - if (d->size < int(d->alloc)) { - if (!d->size) { - *this = QVector<T>(); - return; - } - realloc(d->size); - } - if (d->capacityReserved) { - // capacity reserved in a read only memory would be useless - // this checks avoid writing to such memory. - d->capacityReserved = 0; - } + resize_internal(size, Qt::Uninitialized); + if (size > this->size()) + d->appendInitialize(size); + } + void resize(int size, parameter_type c) + { + resize_internal(size, Qt::Uninitialized); + if (size > this->size()) + d->copyAppend(size - this->size(), c); } - inline void detach(); - inline bool isDetached() const { return !d->ref.isShared(); } + inline int capacity() const { return int(d->constAllocatedCapacity()); } + void reserve(int size); + inline void squeeze(); + + void detach() { d.detach(); } + bool isDetached() const noexcept { return !d->isShared(); } inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; } - inline T *data() { detach(); return d->begin(); } - inline const T *data() const { return d->begin(); } - inline const T *constData() const { return d->begin(); } - void clear(); - - const T &at(int i) const; - T &operator[](int i); - const T &operator[](int i) const; - void append(const T &t); - void append(T &&t); - inline void append(const QVector<T> &l) { *this += l; } - void prepend(T &&t); + pointer data() { detach(); return d->data(); } + const_pointer data() const noexcept { return d->data(); } + const_pointer constData() const noexcept { return d->data(); } + void clear() { + if (!size()) + return; + if (d->needsDetach()) { + // must allocate memory + DataPointer detached(Data::allocate(d.allocatedCapacity(), d->detachFlags())); + d.swap(detached); + } else { + d->truncate(0); + } + } + + const_reference at(int i) const noexcept + { + Q_ASSERT_X(size_t(i) < size_t(d->size), "QVector::at", "index out of range"); + return data()[i]; + } + reference operator[](int i) + { + Q_ASSERT_X(size_t(i) < size_t(d->size), "QVector::operator[]", "index out of range"); + detach(); + return data()[i]; + } + const_reference operator[](int i) const noexcept { return at(i); } + void append(const_reference t) + { append(const_iterator(std::addressof(t)), const_iterator(std::addressof(t)) + 1); } + void append(const_iterator i1, const_iterator i2); + void append(value_type &&t); + void append(const QVector<T> &l) { append(l.constBegin(), l.constEnd()); } + void prepend(rvalue_ref t); void prepend(const T &t); - void insert(int i, T &&t); - void insert(int i, const T &t); - void insert(int i, int n, const T &t); - void replace(int i, const T &t); - void remove(int i); - void remove(int i, int n); - inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); } - inline void removeLast(); - T takeFirst() { Q_ASSERT(!isEmpty()); T r = std::move(first()); removeFirst(); return r; } - T takeLast() { Q_ASSERT(!isEmpty()); T r = std::move(last()); removeLast(); return r; } - - QVector<T> &fill(const T &t, int size = -1); - - int indexOf(const T &t, int from = 0) const; - int lastIndexOf(const T &t, int from = -1) const; - bool contains(const T &t) const; - int count(const T &t) const; + iterator insert(int i, parameter_type t) + { return insert(i, 1, t); } + iterator insert(int i, int n, parameter_type t); + iterator insert(const_iterator before, parameter_type t) + { + Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid"); + return insert(before, 1, t); + } + iterator insert(const_iterator before, int n, parameter_type t) + { + Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid"); + return insert(std::distance(constBegin(), before), n, t); + } + iterator insert(const_iterator before, rvalue_ref t) + { + Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid"); + return insert(std::distance(constBegin(), before), std::move(t)); + } + iterator insert(int i, rvalue_ref t); +#if 0 + template< class InputIt > + iterator insert( const_iterator pos, InputIt first, InputIt last ); + iterator insert( const_iterator pos, std::initializer_list<T> ilist ); +#endif + void replace(int i, const T &t) + { + Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range"); + const T copy(t); + data()[i] = copy; + } + void replace(int i, rvalue_ref t) + { + Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range"); + const T copy(std::move(t)); + data()[i] = std::move(copy); + } + + void remove(int i, int n = 1); + void removeFirst() { Q_ASSERT(!isEmpty()); remove(0); } + void removeLast() { Q_ASSERT(!isEmpty()); remove(size() - 1); } + value_type takeFirst() { Q_ASSERT(!isEmpty()); value_type v = std::move(first()); remove(0); return v; } + value_type takeLast() { Q_ASSERT(!isEmpty()); value_type v = std::move(last()); remove(size() - 1); return v; } + + QVector<T> &fill(parameter_type t, int size = -1); + + int indexOf(const T &t, int from = 0) const noexcept; + int lastIndexOf(const T &t, int from = -1) const noexcept; + bool contains(const T &t) const noexcept + { + return indexOf(t) != -1; + } + int count(const T &t) const noexcept + { + return int(std::count(&*cbegin(), &*cend(), t)); + } // QList compatibility void removeAt(int i) { remove(i); } @@ -171,10 +309,10 @@ public: const const_iterator ce = this->cend(), cit = std::find(this->cbegin(), ce, t); if (cit == ce) return 0; + int index = cit - this->cbegin(); // next operation detaches, so ce, cit, t may become invalidated: const T tCopy = t; - const int firstFoundIdx = std::distance(this->cbegin(), cit); - const iterator e = end(), it = std::remove(begin() + firstFoundIdx, e, tCopy); + const iterator e = end(), it = std::remove(begin() + index, e, tCopy); const int result = std::distance(it, e); erase(it, e); return result; @@ -187,7 +325,6 @@ public: remove(i); return true; } - int length() const { return size(); } T takeAt(int i) { T t = std::move((*this)[i]); remove(i); return t; } void move(int from, int to) { @@ -204,32 +341,26 @@ public: } // STL-style - typedef typename Data::iterator iterator; - typedef typename Data::const_iterator const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - inline iterator begin() { detach(); return d->begin(); } - inline const_iterator begin() const noexcept { return d->constBegin(); } - inline const_iterator cbegin() const noexcept { return d->constBegin(); } - inline const_iterator constBegin() const noexcept { return d->constBegin(); } - inline iterator end() { detach(); return d->end(); } - inline const_iterator end() const noexcept { return d->constEnd(); } - inline const_iterator cend() const noexcept { return d->constEnd(); } - inline const_iterator constEnd() const noexcept { return d->constEnd(); } + iterator begin() { detach(); return d->begin(); } + iterator end() { detach(); return d->end(); } + + const_iterator begin() const noexcept { return d->constBegin(); } + const_iterator end() const noexcept { return d->constEnd(); } + const_iterator cbegin() const noexcept { return d->constBegin(); } + const_iterator cend() const noexcept { return d->constEnd(); } + const_iterator constBegin() const noexcept { return d->constBegin(); } + const_iterator constEnd() const noexcept { return d->constEnd(); } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } - iterator insert(iterator before, int n, const T &x); - inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); } - inline iterator insert(iterator before, T &&x); + iterator erase(iterator begin, iterator end); inline iterator erase(iterator pos) { return erase(pos, pos+1); } // more Qt - inline int count() const { return d->size; } inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); } inline const T &constFirst() const { Q_ASSERT(!isEmpty()); return *begin(); } @@ -240,7 +371,7 @@ public: inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } QVector<T> mid(int pos, int len = -1) const; - T value(int i) const; + T value(int i) const { return value(i, T()); } T value(int i, const T &defaultValue) const; void swapItemsAt(int i, int j) { @@ -251,31 +382,22 @@ public: } // STL compatibility - typedef T value_type; - typedef value_type* pointer; - typedef const value_type* const_pointer; - typedef value_type& reference; - typedef const value_type& const_reference; - typedef qptrdiff difference_type; - typedef iterator Iterator; - typedef const_iterator ConstIterator; - typedef int size_type; inline void push_back(const T &t) { append(t); } - void push_back(T &&t) { append(std::move(t)); } - void push_front(T &&t) { prepend(std::move(t)); } + void push_back(rvalue_ref t) { append(std::move(t)); } + void push_front(rvalue_ref t) { prepend(std::move(t)); } inline void push_front(const T &t) { prepend(t); } void pop_back() { removeLast(); } void pop_front() { removeFirst(); } inline bool empty() const { return d->size == 0; } - inline T& front() { return first(); } + inline reference front() { return first(); } inline const_reference front() const { return first(); } inline reference back() { return last(); } inline const_reference back() const { return last(); } void shrink_to_fit() { squeeze(); } // comfort - QVector<T> &operator+=(const QVector<T> &l); + QVector<T> &operator+=(const QVector<T> &l) { append(l.cbegin(), l.cend()); return *this; } inline QVector<T> operator+(const QVector<T> &l) const { QVector n = *this; n += l; return n; } inline QVector<T> &operator+=(const T &t) @@ -284,42 +406,17 @@ public: { append(t); return *this; } inline QVector<T> &operator<<(const QVector<T> &l) { *this += l; return *this; } - inline QVector<T> &operator+=(T &&t) + inline QVector<T> &operator+=(rvalue_ref t) { append(std::move(t)); return *this; } - inline QVector<T> &operator<<(T &&t) + inline QVector<T> &operator<<(rvalue_ref t) { append(std::move(t)); return *this; } -#if QT_VERSION < QT_VERSION_CHECK(6,0,0) - Q_DECL_DEPRECATED_X("Use QVector<T>(vector.begin(), vector.end()) instead.") - static inline QVector<T> fromStdVector(const std::vector<T> &vector) - { return QVector<T>(vector.begin(), vector.end()); } - Q_DECL_DEPRECATED_X("Use std::vector<T>(vector.begin(), vector.end()) instead.") - inline std::vector<T> toStdVector() const - { return std::vector<T>(d->begin(), d->end()); } -#endif - // Consider deprecating in 6.4 or later static QVector<T> fromList(const QVector<T> &list) { return list; } QVector<T> toList() const { return *this; } static inline QVector<T> fromVector(const QVector<T> &vector) { return vector; } inline QVector<T> toVector() const { return *this; } - -private: - // ### Qt6: remove methods, they are unused - void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default); - void reallocData(const int sz) { reallocData(sz, d->alloc); } - void realloc(int alloc, QArrayData::AllocationOptions options = QArrayData::Default); - void freeData(Data *d); - void defaultConstruct(T *from, T *to); - void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom); - void destruct(T *from, T *to); - bool isValidIterator(const iterator &i) const - { - const std::less<const T*> less = {}; - return !less(d->end(), i) && !less(i, d->begin()); - } - class AlignmentDummy { Data header; T array[1]; }; }; #if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606 @@ -329,654 +426,227 @@ template <typename InputIterator, QVector(InputIterator, InputIterator) -> QVector<ValueType>; #endif -#ifdef Q_CC_MSVC -// behavior change: an object of POD type constructed with an initializer of the form () -// will be default-initialized -# pragma warning ( push ) -# pragma warning ( disable : 4345 ) -# pragma warning(disable : 4127) // conditional expression is constant -#endif - template <typename T> -void QVector<T>::defaultConstruct(T *from, T *to) +inline void QVector<T>::resize_internal(int newSize, Qt::Initialization) { - if (QTypeInfo<T>::isComplex) { - while (from != to) { - new (from++) T(); + Q_ASSERT(newSize >= 0); + + if (d->needsDetach() || newSize > capacity()) { + // must allocate memory + DataPointer detached(Data::allocate(d->detachCapacity(newSize), + d->detachFlags())); + if (size() && newSize) { + detached->copyAppend(constBegin(), constBegin() + qMin(newSize, size())); } - } else { - ::memset(static_cast<void *>(from), 0, (to - from) * sizeof(T)); + d.swap(detached); } -} -template <typename T> -void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom) -{ - if (QTypeInfo<T>::isComplex) { - while (srcFrom != srcTo) - new (dstFrom++) T(*srcFrom++); - } else { - ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T)); - } + if (newSize < size()) + d->truncate(newSize); } template <typename T> -void QVector<T>::destruct(T *from, T *to) +void QVector<T>::reserve(int asize) { - if (QTypeInfo<T>::isComplex) { - while (from != to) { - from++->~T(); + // capacity() == 0 for immutable data, so this will force a detaching below + if (asize <= capacity()) { + if (d->flags() & Data::CapacityReserved) + return; // already reserved, don't shrink + if (!d->isShared()) { + // accept current allocation, don't shrink + d->flags() |= Data::CapacityReserved; + return; } } + + DataPointer detached(Data::allocate(qMax(asize, size()), + d->detachFlags() | Data::CapacityReserved)); + detached->copyAppend(constBegin(), constEnd()); + d.swap(detached); } template <typename T> -inline QVector<T>::QVector(const QVector<T> &v) +inline void QVector<T>::squeeze() { - if (v.d->ref.ref()) { - d = v.d; - } else { - if (v.d->capacityReserved) { - d = Data::allocate(v.d->alloc); - Q_CHECK_PTR(d); - d->capacityReserved = true; - } else { - d = Data::allocate(v.d->size); - Q_CHECK_PTR(d); - } - if (d->alloc) { - copyConstruct(v.d->begin(), v.d->end(), d->begin()); - d->size = v.d->size; + if (d->needsDetach() || size() != capacity()) { + // must allocate memory + DataPointer detached(Data::allocate(size(), d->detachFlags() & ~Data::CapacityReserved)); + if (size()) { + detached->copyAppend(constBegin(), constEnd()); } + d.swap(detached); } } -#if defined(Q_CC_MSVC) -#pragma warning( pop ) -#endif - template <typename T> -void QVector<T>::detach() +inline void QVector<T>::remove(int i, int n) { - if (d->ref.isStatic()) - return; - - if (!isDetached()) - realloc(int(d->alloc)); - Q_ASSERT(isDetached()); -} + Q_ASSERT_X(size_t(i) + size_t(n) <= size_t(d->size), "QVector::remove", "index out of range"); + Q_ASSERT_X(n >= 0, "QVector::remove", "invalid count"); -template <typename T> -void QVector<T>::reserve(int asize) -{ - if (asize > int(d->alloc)) - realloc(asize); - if (isDetached()) - d->capacityReserved = 1; - Q_ASSERT(capacity() >= asize); -} + if (n == 0) + return; -template <typename T> -void QVector<T>::resize(int asize) -{ - if (asize == d->size) - return detach(); - if (asize > int(d->alloc) || !isDetached()) { // there is not enough space - QArrayData::AllocationOptions opt = asize > int(d->alloc) ? QArrayData::Grow : QArrayData::Default; - realloc(qMax(int(d->alloc), asize), opt); + const size_t newSize = size() - n; + if (d->needsDetach() || + ((d->flags() & Data::CapacityReserved) == 0 + && newSize < d->allocatedCapacity()/2)) { + // allocate memory + DataPointer detached(Data::allocate(d->detachCapacity(newSize), + d->detachFlags() & ~(Data::GrowsBackwards | Data::GrowsForward))); + const_iterator where = constBegin() + i; + if (newSize) { + detached->copyAppend(constBegin(), where); + detached->copyAppend(where + n, constEnd()); + } + d.swap(detached); + } else { + // we're detached and we can just move data around + d->erase(d->begin() + i, d->begin() + i + n); } - if (asize < d->size) - destruct(begin() + asize, end()); - else - defaultConstruct(end(), begin() + asize); - d->size = asize; -} -template <typename T> -inline void QVector<T>::clear() -{ - if (!d->size) - return; - destruct(begin(), end()); - d->size = 0; } -template <typename T> -inline const T &QVector<T>::at(int i) const -{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range"); - return d->begin()[i]; } -template <typename T> -inline const T &QVector<T>::operator[](int i) const -{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range"); - return d->begin()[i]; } -template <typename T> -inline T &QVector<T>::operator[](int i) -{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range"); - return data()[i]; } -template <typename T> -inline void QVector<T>::insert(int i, const T &t) -{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range"); - insert(begin() + i, 1, t); } -template <typename T> -inline void QVector<T>::insert(int i, int n, const T &t) -{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range"); - insert(begin() + i, n, t); } -template <typename T> -inline void QVector<T>::insert(int i, T &&t) -{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range"); - insert(begin() + i, std::move(t)); } -template <typename T> -inline void QVector<T>::remove(int i, int n) -{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range"); - erase(d->begin() + i, d->begin() + i + n); } -template <typename T> -inline void QVector<T>::remove(int i) -{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range"); - erase(d->begin() + i, d->begin() + i + 1); } + template <typename T> inline void QVector<T>::prepend(const T &t) -{ insert(begin(), 1, t); } -template <typename T> -inline void QVector<T>::prepend(T &&t) -{ insert(begin(), std::move(t)); } - +{ insert(0, 1, t); } template <typename T> -inline void QVector<T>::replace(int i, const T &t) -{ - Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range"); - const T copy(t); - data()[i] = copy; -} +void QVector<T>::prepend(rvalue_ref t) +{ insert(0, std::move(t)); } -template <typename T> -QVector<T> &QVector<T>::operator=(const QVector<T> &v) +template<typename T> +inline T QVector<T>::value(int i, const T &defaultValue) const { - if (v.d != d) { - QVector<T> tmp(v); - tmp.swap(*this); - } - return *this; + return size_t(i) < size_t(d->size) ? at(i) : defaultValue; } template <typename T> -QVector<T>::QVector(int asize) +inline void QVector<T>::append(const_iterator i1, const_iterator i2) { - Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0."); - if (Q_LIKELY(asize > 0)) { - d = Data::allocate(asize); - Q_CHECK_PTR(d); - d->size = asize; - defaultConstruct(d->begin(), d->end()); + if (i1 == i2) + return; + const size_t newSize = size() + std::distance(i1, i2); + if (d->needsDetach() || newSize > d->allocatedCapacity()) { + DataPointer detached(Data::allocate(d->detachCapacity(newSize), + d->detachFlags() | Data::GrowsForward)); + detached->copyAppend(constBegin(), constEnd()); + detached->copyAppend(i1, i2); + d.swap(detached); } else { - d = Data::sharedNull(); + // we're detached and we can just move data around + d->copyAppend(i1, i2); } } template <typename T> -QVector<T>::QVector(int asize, const T &t) +inline void QVector<T>::append(value_type &&t) { - Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0."); - if (asize > 0) { - d = Data::allocate(asize); - Q_CHECK_PTR(d); - d->size = asize; - T* i = d->end(); - while (i != d->begin()) - new (--i) T(t); + const size_t newSize = size() + 1; + const bool isTooSmall = newSize > d->allocatedCapacity(); + const bool isOverlapping = std::addressof(*d->begin()) <= std::addressof(t) + && std::addressof(t) < std::addressof(*d->end()); + if (isTooSmall || d->needsDetach() || Q_UNLIKELY(isOverlapping)) { + typename Data::ArrayOptions flags = d->detachFlags(); + if (isTooSmall) + flags |= Data::GrowsForward; + DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags)); + detached->copyAppend(constBegin(), constEnd()); + detached->moveAppend(std::addressof(t), std::addressof(t) + 1); + d.swap(detached); } else { - d = Data::sharedNull(); + // we're detached and we can just move data around + d->moveAppend(std::addressof(t), std::addressof(t) + 1); } } -#if defined(Q_CC_MSVC) -QT_WARNING_PUSH -QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant -#endif // Q_CC_MSVC - template <typename T> -QVector<T>::QVector(std::initializer_list<T> args) +inline typename QVector<T>::iterator +QVector<T>::insert(int i, int n, parameter_type t) { - if (args.size() > 0) { - d = Data::allocate(args.size()); - Q_CHECK_PTR(d); - // std::initializer_list<T>::iterator is guaranteed to be - // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct - copyConstruct(args.begin(), args.end(), d->begin()); - d->size = int(args.size()); - } else { - d = Data::sharedNull(); - } -} + Q_ASSERT_X(size_t(i) <= size_t(d->size), "QVector<T>::insert", "index out of range"); -template <typename T> -QVector<T> &QVector<T>::operator=(std::initializer_list<T> args) -{ - QVector<T> tmp(args); - tmp.swap(*this); - return *this; -} + // we don't have a quick exit for n == 0 + // it's not worth wasting CPU cycles for that -#if defined(Q_CC_MSVC) -QT_WARNING_POP -#endif // Q_CC_MSVC + const size_t newSize = size() + n; + if (d->needsDetach() || newSize > d->allocatedCapacity()) { + typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward; + if (size_t(i) <= newSize / 4) + flags |= Data::GrowsBackwards; -template <typename T> -template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>> -QVector<T>::QVector(InputIterator first, InputIterator last) - : QVector() -{ - QtPrivate::reserveIfForwardIterator(this, first, last); - std::copy(first, last, std::back_inserter(*this)); -} - -template <typename T> -void QVector<T>::freeData(Data *x) -{ - destruct(x->begin(), x->end()); - Data::deallocate(x); -} - -#if defined(Q_CC_MSVC) -QT_WARNING_PUSH -QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant -#endif - -template <typename T> -void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options) -{ - Q_ASSERT(asize >= 0 && asize <= aalloc); - Data *x = d; - - const bool isShared = d->ref.isShared(); - - if (aalloc != 0) { - if (aalloc != int(d->alloc) || isShared) { - QT_TRY { - // allocate memory - x = Data::allocate(aalloc, options); - Q_CHECK_PTR(x); - // aalloc is bigger then 0 so it is not [un]sharedEmpty - Q_ASSERT(!x->ref.isStatic()); - x->size = asize; - - T *srcBegin = d->begin(); - T *srcEnd = asize > d->size ? d->end() : d->begin() + asize; - T *dst = x->begin(); - - if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { - QT_TRY { - if (isShared || !std::is_nothrow_move_constructible<T>::value) { - // we can not move the data, we need to copy construct it - while (srcBegin != srcEnd) - new (dst++) T(*srcBegin++); - } else { - while (srcBegin != srcEnd) - new (dst++) T(std::move(*srcBegin++)); - } - } QT_CATCH (...) { - // destruct already copied objects - destruct(x->begin(), dst); - QT_RETHROW; - } - } else { - ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); - dst += srcEnd - srcBegin; - - // destruct unused / not moved data - if (asize < d->size) - destruct(d->begin() + asize, d->end()); - } - - if (asize > d->size) { - // construct all new objects when growing - if (!QTypeInfo<T>::isComplex) { - ::memset(static_cast<void *>(dst), 0, (static_cast<T *>(x->end()) - dst) * sizeof(T)); - } else { - QT_TRY { - while (dst != x->end()) - new (dst++) T(); - } QT_CATCH (...) { - // destruct already copied objects - destruct(x->begin(), dst); - QT_RETHROW; - } - } - } - } QT_CATCH (...) { - Data::deallocate(x); - QT_RETHROW; - } - x->capacityReserved = d->capacityReserved; - } else { - Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size - Q_ASSERT(isDetached()); // can be done only on detached d - Q_ASSERT(x == d); // in this case we do not need to allocate anything - if (asize <= d->size) { - destruct(x->begin() + asize, x->end()); // from future end to current end - } else { - defaultConstruct(x->end(), x->begin() + asize); // from current end to future end - } - x->size = asize; - } + DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags)); + const_iterator where = constBegin() + i; + detached->copyAppend(constBegin(), where); + detached->copyAppend(n, t); + detached->copyAppend(where, constEnd()); + d.swap(detached); } else { - x = Data::sharedNull(); - } - if (d != x) { - if (!d->ref.deref()) { - if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { - // data was copy constructed, we need to call destructors - // or if !alloc we did nothing to the old 'd'. - freeData(d); - } else { - Data::deallocate(d); - } - } - d = x; - } - - Q_ASSERT(d->data()); - Q_ASSERT(uint(d->size) <= d->alloc); - Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull()); - Q_ASSERT(d->alloc >= uint(aalloc)); - Q_ASSERT(d->size == asize); -} - -template<typename T> -void QVector<T>::realloc(int aalloc, QArrayData::AllocationOptions options) -{ - Q_ASSERT(aalloc >= d->size); - Data *x = d; - - const bool isShared = d->ref.isShared(); - - QT_TRY { - // allocate memory - x = Data::allocate(aalloc, options); - Q_CHECK_PTR(x); - // aalloc is bigger then 0 so it is not [un]sharedEmpty - Q_ASSERT(!x->ref.isStatic()); - x->size = d->size; - - T *srcBegin = d->begin(); - T *srcEnd = d->end(); - T *dst = x->begin(); - - if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { - QT_TRY { - if (isShared || !std::is_nothrow_move_constructible<T>::value) { - // we can not move the data, we need to copy construct it - while (srcBegin != srcEnd) - new (dst++) T(*srcBegin++); - } else { - while (srcBegin != srcEnd) - new (dst++) T(std::move(*srcBegin++)); - } - } QT_CATCH (...) { - // destruct already copied objects - destruct(x->begin(), dst); - QT_RETHROW; - } - } else { - ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); - dst += srcEnd - srcBegin; - } - - } QT_CATCH (...) { - Data::deallocate(x); - QT_RETHROW; - } - x->capacityReserved = d->capacityReserved; - - Q_ASSERT(d != x); - if (!d->ref.deref()) { - if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { - // data was copy constructed, we need to call destructors - // or if !alloc we did nothing to the old 'd'. - freeData(d); + // we're detached and we can just move data around + if (i == size()) { + d->copyAppend(n, t); } else { - Data::deallocate(d); + T copy(t); + d->insert(d.begin() + i, n, copy); } } - d = x; - - Q_ASSERT(d->data()); - Q_ASSERT(uint(d->size) <= d->alloc); - Q_ASSERT(d != Data::sharedNull()); - Q_ASSERT(d->alloc >= uint(aalloc)); -} - -#if defined(Q_CC_MSVC) -QT_WARNING_POP -#endif - -template<typename T> -Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const -{ - if (uint(i) >= uint(d->size)) { - return T(); - } - return d->begin()[i]; -} -template<typename T> -Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const -{ - return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i]; + return d.begin() + i; } template <typename T> -void QVector<T>::append(const T &t) +typename QVector<T>::iterator +QVector<T>::insert(int i, rvalue_ref t) { - const bool isTooSmall = uint(d->size + 1) > d->alloc; - if (!isDetached() || isTooSmall) { - T copy(t); - QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); - realloc(isTooSmall ? d->size + 1 : d->alloc, opt); - - if (QTypeInfo<T>::isComplex) - new (d->end()) T(std::move(copy)); - else - *d->end() = std::move(copy); + Q_ASSERT_X(size_t(i) <= size_t(d->size), "QVector<T>::insert", "index out of range"); - } else { - if (QTypeInfo<T>::isComplex) - new (d->end()) T(t); - else - *d->end() = t; - } - ++d->size; -} - -template <typename T> -void QVector<T>::append(T &&t) -{ - const bool isTooSmall = uint(d->size + 1) > d->alloc; - if (!isDetached() || isTooSmall) { - QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); - realloc(isTooSmall ? d->size + 1 : d->alloc, opt); - } - - new (d->end()) T(std::move(t)); - - ++d->size; -} + const size_t newSize = size() + 1; + if (d->needsDetach() || newSize > d->allocatedCapacity()) { + typename Data::ArrayOptions flags = d->detachFlags() | Data::GrowsForward; + if (size_t(i) <= newSize / 4) + flags |= Data::GrowsBackwards; -template <typename T> -void QVector<T>::removeLast() -{ - Q_ASSERT(!isEmpty()); - Q_ASSERT(d->alloc); - - if (d->ref.isShared()) - detach(); - --d->size; - if (QTypeInfo<T>::isComplex) - (d->data() + d->size)->~T(); -} - -template <typename T> -typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t) -{ - Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid"); - - const auto offset = std::distance(d->begin(), before); - if (n != 0) { - const T copy(t); - if (!isDetached() || d->size + n > int(d->alloc)) - realloc(d->size + n, QArrayData::Grow); - if (!QTypeInfoQuery<T>::isRelocatable) { - T *b = d->end(); - T *i = d->end() + n; - while (i != b) - new (--i) T; - i = d->end(); - T *j = i + n; - b = d->begin() + offset; - while (i != b) - *--j = *--i; - i = b+n; - while (i != b) - *--i = copy; - } else { - T *b = d->begin() + offset; - T *i = b + n; - memmove(static_cast<void *>(i), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); - while (i != b) - new (--i) T(copy); - } - d->size += n; - } - return d->begin() + offset; -} - -template <typename T> -typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t) -{ - Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid"); - - const auto offset = std::distance(d->begin(), before); - if (!isDetached() || d->size + 1 > int(d->alloc)) - realloc(d->size + 1, QArrayData::Grow); - if (!QTypeInfoQuery<T>::isRelocatable) { - T *i = d->end(); - T *j = i + 1; - T *b = d->begin() + offset; - // The new end-element needs to be constructed, the rest must be move assigned - if (i != b) { - new (--j) T(std::move(*--i)); - while (i != b) - *--j = std::move(*--i); - *b = std::move(t); - } else { - new (b) T(std::move(t)); - } + DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags)); + const_iterator where = constBegin() + i; + detached->copyAppend(constBegin(), where); + detached->moveAppend(std::addressof(t), std::addressof(t) + 1); + detached->copyAppend(where, constEnd()); + d.swap(detached); } else { - T *b = d->begin() + offset; - memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); - new (b) T(std::move(t)); + d->insert(d.begin() + i, std::move(t)); } - d->size += 1; - return d->begin() + offset; + return d.begin() + i; } template <typename T> typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend) { - Q_ASSERT_X(isValidIterator(abegin), "QVector::erase", "The specified iterator argument 'abegin' is invalid"); - Q_ASSERT_X(isValidIterator(aend), "QVector::erase", "The specified iterator argument 'aend' is invalid"); - - const auto itemsToErase = aend - abegin; - - if (!itemsToErase) - return abegin; + Q_ASSERT_X(isValidIterator(const_iterator(abegin)), "QVector::erase", "The specified iterator argument 'abegin' is invalid"); + Q_ASSERT_X(isValidIterator(const_iterator(aend)), "QVector::erase", "The specified iterator argument 'aend' is invalid"); + Q_ASSERT(aend >= abegin); - Q_ASSERT(abegin >= d->begin()); - Q_ASSERT(aend <= d->end()); - Q_ASSERT(abegin <= aend); + // d.begin() so we don't detach just yet + int i = std::distance(d.begin(), abegin); + int n = std::distance(abegin, aend); + remove(i, n); - const auto itemsUntouched = abegin - d->begin(); - - // FIXME we could do a proper realloc, which copy constructs only needed data. - // FIXME we are about to delete data - maybe it is good time to shrink? - // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this. - if (d->alloc) { - detach(); - abegin = d->begin() + itemsUntouched; - aend = abegin + itemsToErase; - if (!QTypeInfoQuery<T>::isRelocatable) { - iterator moveBegin = abegin + itemsToErase; - iterator moveEnd = d->end(); - while (moveBegin != moveEnd) { - if (QTypeInfo<T>::isComplex) - static_cast<T *>(abegin)->~T(); - new (abegin++) T(*moveBegin++); - } - if (abegin < d->end()) { - // destroy rest of instances - destruct(abegin, d->end()); - } - } else { - destruct(abegin, aend); - // QTBUG-53605: static_cast<void *> masks clang errors of the form - // error: destination for this 'memmove' call is a pointer to class containing a dynamic class - // FIXME maybe use std::is_polymorphic (as soon as allowed) to avoid the memmove - memmove(static_cast<void *>(abegin), static_cast<void *>(aend), - (d->size - itemsToErase - itemsUntouched) * sizeof(T)); - } - d->size -= int(itemsToErase); - } - return d->begin() + itemsUntouched; -} - -template <typename T> -bool QVector<T>::operator==(const QVector<T> &v) const -{ - if (d == v.d) - return true; - if (d->size != v.d->size) - return false; - const T *vb = v.d->begin(); - const T *b = d->begin(); - const T *e = d->end(); - return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(vb, v.d->size)); + return d.begin() + i; } template <typename T> -QVector<T> &QVector<T>::fill(const T &from, int asize) +inline QVector<T> &QVector<T>::fill(parameter_type t, int newSize) { - const T copy(from); - resize(asize < 0 ? d->size : asize); - if (d->size) { - T *i = d->end(); - T *b = d->begin(); - while (i != b) - *--i = copy; - } - return *this; -} - -template <typename T> -QVector<T> &QVector<T>::operator+=(const QVector &l) -{ - if (d->size == 0) { - *this = l; + if (newSize == -1) + newSize = size(); + if (d->needsDetach() || newSize > capacity()) { + // must allocate memory + DataPointer detached(Data::allocate(d->detachCapacity(newSize), + d->detachFlags())); + detached->copyAppend(newSize, t); + d.swap(detached); } else { - uint newSize = d->size + l.d->size; - const bool isTooSmall = newSize > d->alloc; - if (!isDetached() || isTooSmall) { - QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); - realloc(isTooSmall ? newSize : d->alloc, opt); - } - - if (d->alloc) { - T *w = d->begin() + newSize; - T *i = l.d->end(); - T *b = l.d->begin(); - while (i != b) { - if (QTypeInfo<T>::isComplex) - new (--w) T(*--i); - else - *--w = *--i; - } - d->size = newSize; - } + // we're detached + const T copy(t); + d->assign(d.begin(), d.begin() + qMin(size(), newSize), t); + if (newSize > size()) + d->copyAppend(newSize - size(), copy); } return *this; } @@ -1017,54 +687,35 @@ int lastIndexOf(const QVector<T> &vector, const U &u, int from) } template <typename T> -int QVector<T>::indexOf(const T &t, int from) const +int QVector<T>::indexOf(const T &t, int from) const noexcept { return QtPrivate::indexOf<T, T>(*this, t, from); } template <typename T> -int QVector<T>::lastIndexOf(const T &t, int from) const +int QVector<T>::lastIndexOf(const T &t, int from) const noexcept { return QtPrivate::lastIndexOf(*this, t, from); } template <typename T> -bool QVector<T>::contains(const T &t) const -{ - const T *b = d->begin(); - const T *e = d->end(); - return std::find(b, e, t) != e; -} - -template <typename T> -int QVector<T>::count(const T &t) const -{ - const T *b = d->begin(); - const T *e = d->end(); - return int(std::count(b, e, t)); -} - -template <typename T> -Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const +inline QVector<T> QVector<T>::mid(int pos, int len) const { using namespace QtPrivate; - switch (QContainerImplHelper::mid(d->size, &pos, &len)) { + switch (QContainerImplHelper::mid(d.size, &pos, &len)) { case QContainerImplHelper::Null: case QContainerImplHelper::Empty: - return QVector<T>(); + return QVector(); case QContainerImplHelper::Full: return *this; case QContainerImplHelper::Subset: break; } - QVector<T> midResult; - midResult.realloc(len); - T *srcFrom = d->begin() + pos; - T *srcTo = d->begin() + pos + len; - midResult.copyConstruct(srcFrom, srcTo, midResult.data()); - midResult.d->size = len; - return midResult; + // Allocate memory + DataPointer copied(Data::allocate(len)); + copied->copyAppend(constBegin() + pos, constBegin() + pos + len); + return copied; } Q_DECLARE_SEQUENTIAL_ITERATOR(Vector) diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri index 40c84157cd..230456bef9 100644 --- a/src/corelib/tools/tools.pri +++ b/src/corelib/tools/tools.pri @@ -12,6 +12,7 @@ HEADERS += \ tools/qcontainerfwd.h \ tools/qcontainertools_impl.h \ tools/qcryptographichash.h \ + tools/qflatmap_p.h \ tools/qfreelist_p.h \ tools/qhash.h \ tools/qhashfunctions.h \ @@ -47,7 +48,6 @@ HEADERS += \ tools/qvector.h \ tools/qversionnumber.h - SOURCES += \ tools/qarraydata.cpp \ tools/qbitarray.cpp \ |