diff options
Diffstat (limited to 'src/corelib/tools/qvarlengtharray.h')
-rw-r--r-- | src/corelib/tools/qvarlengtharray.h | 207 |
1 files changed, 134 insertions, 73 deletions
diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h index 27083442c5..78d5a27627 100644 --- a/src/corelib/tools/qvarlengtharray.h +++ b/src/corelib/tools/qvarlengtharray.h @@ -14,11 +14,12 @@ #include <QtCore/qalgorithms.h> #include <QtCore/qcontainertools_impl.h> #include <QtCore/qhashfunctions.h> +#include <QtCore/qttypetraits.h> #include <algorithm> #include <initializer_list> #include <iterator> -#include <memory> +#include <QtCore/q20memory.h> #include <new> #include <string.h> @@ -52,7 +53,8 @@ protected: qsizetype s; // size void *ptr; // data - Q_ALWAYS_INLINE constexpr void verify(qsizetype pos = 0, qsizetype n = 1) const + Q_ALWAYS_INLINE constexpr void verify([[maybe_unused]] qsizetype pos = 0, + [[maybe_unused]] qsizetype n = 1) const { Q_ASSERT(pos >= 0); Q_ASSERT(pos <= size()); @@ -172,9 +174,22 @@ public: template <typename Predicate> qsizetype removeIf(Predicate pred); + void clear() + { + if constexpr (QTypeInfo<T>::isComplex) + std::destroy_n(data(), size()); + s = 0; + } + iterator erase(const_iterator begin, const_iterator end); iterator erase(const_iterator pos) { return erase(pos, pos + 1); } + static constexpr qsizetype max_size() noexcept + { + // -1 to deal with the pointer one-past-the-end + return (QtPrivate::MaxAllocSize / sizeof(T)) - 1; + } + size_t hash(size_t seed) const noexcept(QtPrivate::QNothrowHashable_v<T>) { return qHashRange(begin(), end(), seed); @@ -187,7 +202,7 @@ protected: { if (size() == capacity()) // ie. size() != 0 growBy(prealloc, array, 1); - reference r = *new (end()) T(std::forward<Args>(args)...); + reference r = *q20::construct_at(end(), std::forward<Args>(args)...); ++s; return r; } @@ -211,9 +226,13 @@ protected: void reallocate_impl(qsizetype prealloc, void *array, qsizetype size, qsizetype alloc); void resize_impl(qsizetype prealloc, void *array, qsizetype sz, const T &v) { + if (QtPrivate::q_points_into_range(&v, begin(), end())) { + resize_impl(prealloc, array, sz, T(v)); + return; + } reallocate_impl(prealloc, array, sz, qMax(sz, capacity())); while (size() < sz) { - new (data() + size()) T(v); + q20::construct_at(data() + size(), v); ++s; } } @@ -223,7 +242,7 @@ protected: if constexpr (QTypeInfo<T>::isComplex) { // call default constructor for new objects (which can throw) while (size() < sz) { - new (data() + size()) T; + q20::construct_at(data() + size()); ++s; } } else { @@ -231,6 +250,10 @@ protected: } } + void assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t); + template <typename Iterator> + void assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last); + bool isValidIterator(const const_iterator &i) const { const std::less<const T *> less = {}; @@ -253,12 +276,17 @@ class QVarLengthArray friend class QVarLengthArray; using Base = QVLABase<T>; using Storage = QVLAStorage<sizeof(T), alignof(T), Prealloc>; + static_assert(Prealloc > 0, "QVarLengthArray Prealloc must be greater than 0."); static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers."); using Base::verify; template <typename U> using if_copyable = std::enable_if_t<std::is_copy_constructible_v<U>, bool>; + template <typename InputIterator> + using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>; public: + static constexpr qsizetype PreallocatedSize = Prealloc; + using size_type = typename Base::size_type; using value_type = typename Base::value_type; using pointer = typename Base::pointer; @@ -319,7 +347,7 @@ public: { } - template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> + template <typename InputIterator, if_input_iterator<InputIterator> = true> inline QVarLengthArray(InputIterator first, InputIterator last) : QVarLengthArray() { @@ -366,9 +394,7 @@ public: QVarLengthArray<T, Prealloc> &operator=(std::initializer_list<T> list) { - resize(qsizetype(list.size())); - std::copy(list.begin(), list.end(), - QT_MAKE_CHECKED_ARRAY_ITERATOR(begin(), size())); + assign(list); return *this; } @@ -378,6 +404,7 @@ public: } #ifdef Q_QDOC inline qsizetype size() const { return this->s; } + static constexpr qsizetype max_size() noexcept { return QVLABase<T>::max_size(); } #endif using Base::size; inline qsizetype count() const { return size(); } @@ -405,7 +432,10 @@ public: #endif void resize(qsizetype sz, const T &v) { Base::resize_impl(Prealloc, this->array, sz, v); } + using Base::clear; +#ifdef Q_QDOC inline void clear() { resize(0); } +#endif void squeeze() { reallocate(size(), size()); } using Base::capacity; @@ -480,6 +510,15 @@ public: void insert(qsizetype i, T &&t); void insert(qsizetype i, const T &t); void insert(qsizetype i, qsizetype n, const T &t); + + QVarLengthArray &assign(qsizetype n, const T &t) + { Base::assign_impl(Prealloc, this->array, n, t); return *this; } + template <typename InputIterator, if_input_iterator<InputIterator> = true> + QVarLengthArray &assign(InputIterator first, InputIterator last) + { Base::assign_impl(Prealloc, this->array, first, last); return *this; } + QVarLengthArray &assign(std::initializer_list<T> list) + { assign(list.begin(), list.end()); return *this; } + #ifdef Q_QDOC void replace(qsizetype i, const T &t); void remove(qsizetype i, qsizetype n = 1); @@ -644,23 +683,22 @@ QVarLengthArray(InputIterator, InputIterator) -> QVarLengthArray<ValueType>; template <class T, qsizetype Prealloc> Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(qsizetype asize) + : QVarLengthArray() { - this->s = asize; - static_assert(Prealloc > 0, "QVarLengthArray Prealloc must be greater than 0."); - Q_ASSERT_X(size() >= 0, "QVarLengthArray::QVarLengthArray()", "Size must be greater than or equal to 0."); - if (size() > Prealloc) { - this->ptr = malloc(size() * sizeof(T)); - Q_CHECK_PTR(data()); - this->a = size(); - } else { - this->ptr = this->array; - this->a = Prealloc; - } - if constexpr (QTypeInfo<T>::isComplex) { - T *i = end(); - while (i != begin()) - new (--i) T; + Q_ASSERT_X(asize >= 0, "QVarLengthArray::QVarLengthArray(qsizetype)", + "Size must be greater than or equal to 0."); + + // historically, this ctor worked for non-copyable/non-movable T, so keep it working, why not? + // resize(asize) // this requires a movable or copyable T, can't use, need to do it by hand + + if (asize > Prealloc) { + this->ptr = malloc(asize * sizeof(T)); + Q_CHECK_PTR(this->ptr); + this->a = asize; } + if constexpr (QTypeInfo<T>::isComplex) + std::uninitialized_default_construct_n(data(), asize); + this->s = asize; } template <class T> @@ -732,6 +770,61 @@ Q_OUTOFLINE_TEMPLATE void QVLABase<T>::append_impl(qsizetype prealloc, void *arr } template <class T> +Q_OUTOFLINE_TEMPLATE void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t) +{ + Q_ASSERT(n >= 0); + if (n > capacity()) { + reallocate_impl(prealloc, array, 0, capacity()); // clear + resize_impl(prealloc, array, n, t); + } else { + auto mid = (std::min)(n, size()); + std::fill(data(), data() + mid, t); + std::uninitialized_fill(data() + mid, data() + n, t); + s = n; + erase(data() + n, data() + size()); + } +} + +template <class T> +template <typename Iterator> +Q_OUTOFLINE_TEMPLATE void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last) +{ + // This function only provides the basic exception guarantee. + constexpr bool IsFwdIt = + std::is_convertible_v<typename std::iterator_traits<Iterator>::iterator_category, + std::forward_iterator_tag>; + if constexpr (IsFwdIt) { + const qsizetype n = std::distance(first, last); + if (n > capacity()) + reallocate_impl(prealloc, array, 0, n); // clear & reserve n + } + + auto dst = begin(); + const auto dend = end(); + while (true) { + if (first == last) { // ran out of elements to assign + std::destroy(dst, dend); + break; + } + if (dst == dend) { // ran out of existing elements to overwrite + if constexpr (IsFwdIt) { + dst = std::uninitialized_copy(first, last, dst); + break; + } else { + do { + emplace_back_impl(prealloc, array, *first); + } while (++first != last); + return; // size() is already correct (and dst invalidated)! + } + } + *dst = *first; // overwrite existing element + ++dst; + ++first; + } + this->s = dst - begin(); +} + +template <class T> Q_OUTOFLINE_TEMPLATE void QVLABase<T>::reallocate_impl(qsizetype prealloc, void *array, qsizetype asize, qsizetype aalloc) { Q_ASSERT(aalloc >= asize); @@ -740,7 +833,7 @@ Q_OUTOFLINE_TEMPLATE void QVLABase<T>::reallocate_impl(qsizetype prealloc, void qsizetype osize = size(); const qsizetype copySize = qMin(asize, osize); - Q_ASSUME(copySize >= 0); + Q_ASSERT(copySize >= 0); if (aalloc != capacity()) { QVLABaseBase::malloced_ptr guard; @@ -840,29 +933,12 @@ Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::emplace_impl(qsizetype prealloc, void *ar Q_ASSERT(size() <= capacity()); Q_ASSERT(capacity() > 0); - qsizetype offset = qsizetype(before - cbegin()); - if (size() == capacity()) - growBy(prealloc, array, 1); - if constexpr (!QTypeInfo<T>::isRelocatable) { - T *b = begin() + offset; - T *i = end(); - T *j = i + 1; - // 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 = T(std::forward<Args>(args)...); - } else { - new (b) T(std::forward<Args>(args)...); - } - } else { - T *b = begin() + offset; - memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (size() - offset) * sizeof(T)); - new (b) T(std::forward<Args>(args)...); - } - this->s += 1; - return data() + offset; + const qsizetype offset = qsizetype(before - cbegin()); + emplace_back_impl(prealloc, array, std::forward<Args>(args)...); + const auto b = begin() + offset; + const auto e = end(); + QtPrivate::q_rotate(b, e - 1, e); + return b; } template <class T> @@ -870,35 +946,19 @@ Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::insert_impl(qsizetype prealloc, void *arr { Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid"); - qsizetype offset = qsizetype(before - cbegin()); - if (n != 0) { - const T copy(t); // `t` could alias an element in [begin(), end()[ - resize_impl(prealloc, array, size() + n); - if constexpr (!QTypeInfo<T>::isRelocatable) { - T *b = begin() + offset; - T *j = end(); - T *i = j - n; - while (i != b) - *--j = *--i; - i = b + n; - while (i != b) - *--i = copy; - } else { - T *b = begin() + offset; - T *i = b + n; - memmove(static_cast<void *>(i), static_cast<const void *>(b), (size() - offset - n) * sizeof(T)); - while (i != b) - new (--i) T(copy); - } - } - return data() + offset; + const qsizetype offset = qsizetype(before - cbegin()); + resize_impl(prealloc, array, size() + n, t); + const auto b = begin() + offset; + const auto e = end(); + QtPrivate::q_rotate(b, e - n, e); + return b; } template <class T> Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::erase(const_iterator abegin, const_iterator aend) -> iterator { - Q_ASSERT_X(isValidIterator(abegin), "QVarLengthArray::insert", "The specified const_iterator argument 'abegin' is invalid"); - Q_ASSERT_X(isValidIterator(aend), "QVarLengthArray::insert", "The specified const_iterator argument 'aend' is invalid"); + Q_ASSERT_X(isValidIterator(abegin), "QVarLengthArray::erase", "The specified const_iterator argument 'abegin' is invalid"); + Q_ASSERT_X(isValidIterator(aend), "QVarLengthArray::erase", "The specified const_iterator argument 'aend' is invalid"); qsizetype f = qsizetype(abegin - cbegin()); qsizetype l = qsizetype(aend - cbegin()); @@ -909,10 +969,11 @@ Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::erase(const_iterator abegin, const_iterat Q_ASSERT(n > 0); // aend must be reachable from abegin - if constexpr (QTypeInfo<T>::isComplex) { + if constexpr (!QTypeInfo<T>::isRelocatable) { std::move(begin() + l, end(), QT_MAKE_CHECKED_ARRAY_ITERATOR(begin() + f, size() - f)); std::destroy(end() - n, end()); } else { + std::destroy(abegin, aend); memmove(static_cast<void *>(data() + f), static_cast<const void *>(data() + l), (size() - l) * sizeof(T)); } this->s -= n; |