Back to home page

EIC code displayed by LXR
 
 

    

Warning, file /include/QtCore/qvarlengtharray.h was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).

0001 // Copyright (C) 2021 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003 
0004 #ifndef QVARLENGTHARRAY_H
0005 #define QVARLENGTHARRAY_H
0006 
0007 #if 0
0008 #pragma qt_class(QVarLengthArray)
0009 #pragma qt_sync_stop_processing
0010 #endif
0011 
0012 #include <QtCore/qcompare.h>
0013 #include <QtCore/qcontainerfwd.h>
0014 #include <QtCore/qglobal.h>
0015 #include <QtCore/qalgorithms.h>
0016 #include <QtCore/qcontainertools_impl.h>
0017 #include <QtCore/qhashfunctions.h>
0018 #include <QtCore/qttypetraits.h>
0019 
0020 #include <algorithm>
0021 #include <initializer_list>
0022 #include <iterator>
0023 #include <QtCore/q20memory.h>
0024 #include <new>
0025 
0026 #include <string.h>
0027 #include <stdlib.h>
0028 
0029 QT_BEGIN_NAMESPACE
0030 
0031 template <size_t Size, size_t Align, qsizetype Prealloc>
0032 class QVLAStorage
0033 {
0034     template <size_t> class print;
0035 protected:
0036     QVLAStorage() = default;
0037     QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLAStorage)
0038 
0039     alignas(Align) char array[Prealloc * (Align > Size ? Align : Size)];
0040     QT_WARNING_PUSH
0041     QT_WARNING_DISABLE_DEPRECATED
0042     // ensure we maintain BC: std::aligned_storage_t was only specified by a
0043     // minimum size, but for BC we need the substitution to be exact in size:
0044     static_assert(std::is_same_v<print<sizeof(std::aligned_storage_t<Size, Align>[Prealloc])>,
0045                                  print<sizeof(array)>>);
0046     QT_WARNING_POP
0047 };
0048 
0049 class QVLABaseBase
0050 {
0051 protected:
0052     QVLABaseBase() = default;
0053     QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLABaseBase)
0054 
0055     qsizetype a;      // capacity
0056     qsizetype s;      // size
0057     void *ptr;     // data
0058 
0059     Q_ALWAYS_INLINE constexpr void verify([[maybe_unused]] qsizetype pos = 0,
0060                                           [[maybe_unused]] qsizetype n = 1) const
0061     {
0062         Q_ASSERT(pos >= 0);
0063         Q_ASSERT(pos <= size());
0064         Q_ASSERT(n >= 0);
0065         Q_ASSERT(n <= size() - pos);
0066     }
0067 
0068     struct free_deleter {
0069         void operator()(void *p) const noexcept { free(p); }
0070     };
0071     using malloced_ptr = std::unique_ptr<void, free_deleter>;
0072 
0073 public:
0074     using size_type = qsizetype;
0075 
0076     constexpr size_type capacity() const noexcept { return a; }
0077     constexpr size_type size() const noexcept { return s; }
0078     constexpr bool empty() const noexcept { return size() == 0; }
0079 };
0080 
0081 template<class T>
0082 class QVLABase : public QVLABaseBase
0083 {
0084 protected:
0085     QVLABase() = default;
0086     QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLABase)
0087 
0088 public:
0089     T *data() noexcept { return static_cast<T *>(ptr); }
0090     const T *data() const noexcept { return static_cast<T *>(ptr); }
0091 
0092     using iterator = T*;
0093     using const_iterator = const T*;
0094 
0095     iterator begin() noexcept { return data(); }
0096     const_iterator begin() const noexcept { return data(); }
0097     const_iterator cbegin() const noexcept { return begin(); }
0098     iterator end() noexcept { return data() + size(); }
0099     const_iterator end() const noexcept { return data() + size(); }
0100     const_iterator cend() const noexcept { return end(); }
0101 
0102     using reverse_iterator = std::reverse_iterator<iterator>;
0103     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
0104 
0105     reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
0106     const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{end()}; }
0107     const_reverse_iterator crbegin() const noexcept { return rbegin(); }
0108     reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
0109     const_reverse_iterator rend() const noexcept { return const_reverse_iterator{begin()}; }
0110     const_reverse_iterator crend() const noexcept { return rend(); }
0111 
0112     using value_type = T;
0113     using reference = value_type&;
0114     using const_reference = const value_type&;
0115     using pointer = value_type*;
0116     using const_pointer = const value_type*;
0117     using difference_type = qptrdiff;
0118 
0119     reference front()
0120     {
0121         verify();
0122         return *begin();
0123     }
0124 
0125     const_reference front() const
0126     {
0127         verify();
0128         return *begin();
0129     }
0130 
0131     reference back()
0132     {
0133         verify();
0134         return *rbegin();
0135     }
0136 
0137     const_reference back() const
0138     {
0139         verify();
0140         return *rbegin();
0141     }
0142 
0143     void pop_back()
0144     {
0145         verify();
0146         if constexpr (QTypeInfo<T>::isComplex)
0147             data()[size() - 1].~T();
0148         --s;
0149     }
0150 
0151     template <typename AT = T>
0152     qsizetype indexOf(const AT &t, qsizetype from = 0) const;
0153     template <typename AT = T>
0154     qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const;
0155     template <typename AT = T>
0156     bool contains(const AT &t) const;
0157 
0158     reference operator[](qsizetype idx)
0159     {
0160         verify(idx);
0161         return data()[idx];
0162     }
0163     const_reference operator[](qsizetype idx) const
0164     {
0165         verify(idx);
0166         return data()[idx];
0167     }
0168 
0169     value_type value(qsizetype i) const;
0170     value_type value(qsizetype i, const T& defaultValue) const;
0171 
0172     void replace(qsizetype i, const T &t);
0173     void remove(qsizetype i, qsizetype n = 1);
0174     template <typename AT = T>
0175     qsizetype removeAll(const AT &t);
0176     template <typename AT = T>
0177     bool removeOne(const AT &t);
0178     template <typename Predicate>
0179     qsizetype removeIf(Predicate pred);
0180 
0181     void clear()
0182     {
0183         if constexpr (QTypeInfo<T>::isComplex)
0184             std::destroy_n(data(), size());
0185         s = 0;
0186     }
0187 
0188     iterator erase(const_iterator begin, const_iterator end);
0189     iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
0190 
0191     static constexpr qsizetype maxSize() noexcept
0192     {
0193         // -1 to deal with the pointer one-past-the-end
0194         return (QtPrivate::MaxAllocSize / sizeof(T)) - 1;
0195     }
0196     constexpr qsizetype max_size() const noexcept
0197     {
0198         return maxSize();
0199     }
0200 
0201     size_t hash(size_t seed) const noexcept(QtPrivate::QNothrowHashable_v<T>)
0202     {
0203         return qHashRange(begin(), end(), seed);
0204     }
0205 protected:
0206     void growBy(qsizetype prealloc, void *array, qsizetype increment)
0207     { reallocate_impl(prealloc, array, size(), (std::max)(size() * 2, size() + increment)); }
0208     template <typename...Args>
0209     reference emplace_back_impl(qsizetype prealloc, void *array, Args&&...args)
0210     {
0211         if (size() == capacity()) // ie. size() != 0
0212             growBy(prealloc, array, 1);
0213         reference r = *q20::construct_at(end(), std::forward<Args>(args)...);
0214         ++s;
0215         return r;
0216     }
0217     template <typename...Args>
0218     iterator emplace_impl(qsizetype prealloc, void *array, const_iterator pos, Args&&...arg);
0219 
0220     iterator insert_impl(qsizetype prealloc, void *array, const_iterator pos, qsizetype n, const T &t);
0221 
0222     template <typename S>
0223     bool equal(const QVLABase<S> &other) const
0224     {
0225         return std::equal(begin(), end(), other.begin(), other.end());
0226     }
0227     template <typename S>
0228     bool less_than(const QVLABase<S> &other) const
0229     {
0230         return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
0231     }
0232 
0233     void append_impl(qsizetype prealloc, void *array, const T *buf, qsizetype n);
0234     void reallocate_impl(qsizetype prealloc, void *array, qsizetype size, qsizetype alloc);
0235     void resize_impl(qsizetype prealloc, void *array, qsizetype sz, const T &v)
0236     {
0237         if (QtPrivate::q_points_into_range(&v, begin(), end())) {
0238             resize_impl(prealloc, array, sz, T(v));
0239             return;
0240         }
0241         reallocate_impl(prealloc, array, sz, qMax(sz, capacity()));
0242         while (size() < sz) {
0243             q20::construct_at(data() + size(), v);
0244             ++s;
0245         }
0246     }
0247     void resize_impl(qsizetype prealloc, void *array, qsizetype sz)
0248     {
0249         reallocate_impl(prealloc, array, sz, qMax(sz, capacity()));
0250         if constexpr (QTypeInfo<T>::isComplex) {
0251             // call default constructor for new objects (which can throw)
0252             while (size() < sz) {
0253                 q20::construct_at(data() + size());
0254                 ++s;
0255             }
0256         } else {
0257             s = sz;
0258         }
0259     }
0260 
0261     void assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t);
0262     template <typename Iterator>
0263     void assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last);
0264 
0265     bool isValidIterator(const const_iterator &i) const
0266     {
0267         const std::less<const T *> less = {};
0268         return !less(cend(), i) && !less(i, cbegin());
0269     }
0270 };
0271 
0272 // Prealloc = 256 by default, specified in qcontainerfwd.h
0273 template<class T, qsizetype Prealloc>
0274 class QVarLengthArray
0275 #if QT_VERSION >= QT_VERSION_CHECK(7,0,0) || defined(QT_BOOTSTRAPPED)
0276     : public QVLAStorage<sizeof(T), alignof(T), Prealloc>,
0277       public QVLABase<T>
0278 #else
0279     : public QVLABase<T>,
0280       public QVLAStorage<sizeof(T), alignof(T), Prealloc>
0281 #endif
0282 {
0283     template <class S, qsizetype Prealloc2>
0284     friend class QVarLengthArray;
0285     using Base = QVLABase<T>;
0286     using Storage = QVLAStorage<sizeof(T), alignof(T), Prealloc>;
0287     static_assert(Prealloc > 0, "QVarLengthArray Prealloc must be greater than 0.");
0288     static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
0289     using Base::verify;
0290 
0291     template <typename U>
0292     using if_copyable = std::enable_if_t<std::is_copy_constructible_v<U>, bool>;
0293     template <typename InputIterator>
0294     using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>;
0295 public:
0296     static constexpr qsizetype PreallocatedSize = Prealloc;
0297 
0298     using size_type = typename Base::size_type;
0299     using value_type = typename Base::value_type;
0300     using pointer = typename Base::pointer;
0301     using const_pointer = typename Base::const_pointer;
0302     using reference = typename Base::reference;
0303     using const_reference = typename Base::const_reference;
0304     using difference_type = typename Base::difference_type;
0305 
0306     using iterator = typename Base::iterator;
0307     using const_iterator = typename Base::const_iterator;
0308     using reverse_iterator = typename Base::reverse_iterator;
0309     using const_reverse_iterator = typename Base::const_reverse_iterator;
0310 
0311     QVarLengthArray() noexcept
0312     {
0313         this->a = Prealloc;
0314         this->s = 0;
0315         this->ptr = this->array;
0316     }
0317 
0318     inline explicit QVarLengthArray(qsizetype size);
0319 
0320 #ifndef Q_QDOC
0321     template <typename U = T, if_copyable<U> = true>
0322 #endif
0323     explicit QVarLengthArray(qsizetype sz, const T &v)
0324         : QVarLengthArray{}
0325     {
0326         resize(sz, v);
0327     }
0328 
0329     QVarLengthArray(const QVarLengthArray &other)
0330         : QVarLengthArray{}
0331     {
0332         append(other.constData(), other.size());
0333     }
0334 
0335     QVarLengthArray(QVarLengthArray &&other)
0336             noexcept(std::is_nothrow_move_constructible_v<T>)
0337         : Base(other)
0338     {
0339         const auto otherInlineStorage = reinterpret_cast<T*>(other.array);
0340         if (data() == otherInlineStorage) {
0341             // inline buffer - move into our inline buffer:
0342             this->ptr = this->array;
0343             QtPrivate::q_uninitialized_relocate_n(otherInlineStorage, size(), data());
0344         } else {
0345             // heap buffer - we just stole the memory
0346         }
0347         // reset other to internal storage:
0348         other.a = Prealloc;
0349         other.s = 0;
0350         other.ptr = otherInlineStorage;
0351     }
0352 
0353     QVarLengthArray(std::initializer_list<T> args)
0354         : QVarLengthArray(args.begin(), args.end())
0355     {
0356     }
0357 
0358     template <typename InputIterator, if_input_iterator<InputIterator> = true>
0359     inline QVarLengthArray(InputIterator first, InputIterator last)
0360         : QVarLengthArray()
0361     {
0362         QtPrivate::reserveIfForwardIterator(this, first, last);
0363         std::copy(first, last, std::back_inserter(*this));
0364     }
0365 
0366     inline ~QVarLengthArray()
0367     {
0368         if constexpr (QTypeInfo<T>::isComplex)
0369             std::destroy_n(data(), size());
0370         if (data() != reinterpret_cast<T *>(this->array))
0371             free(data());
0372     }
0373     inline QVarLengthArray<T, Prealloc> &operator=(const QVarLengthArray<T, Prealloc> &other)
0374     {
0375         if (this != &other) {
0376             clear();
0377             append(other.constData(), other.size());
0378         }
0379         return *this;
0380     }
0381 
0382     QVarLengthArray &operator=(QVarLengthArray &&other)
0383         noexcept(std::is_nothrow_move_constructible_v<T>)
0384     {
0385         // we're only required to be self-move-assignment-safe
0386         // when we're in the moved-from state (Hinnant criterion)
0387         // the moved-from state is the empty state, so we're good with the clear() here:
0388         clear();
0389         Q_ASSERT(capacity() >= Prealloc);
0390         const auto otherInlineStorage = other.array;
0391         if (other.ptr != otherInlineStorage) {
0392             // heap storage: steal the external buffer, reset other to otherInlineStorage
0393             this->a = std::exchange(other.a, Prealloc);
0394             this->ptr = std::exchange(other.ptr, otherInlineStorage);
0395         } else {
0396             // inline storage: move into our storage (doesn't matter whether inline or external)
0397             QtPrivate::q_uninitialized_relocate_n(other.data(), other.size(), data());
0398         }
0399         this->s = std::exchange(other.s, 0);
0400         return *this;
0401     }
0402 
0403     QVarLengthArray<T, Prealloc> &operator=(std::initializer_list<T> list)
0404     {
0405         assign(list);
0406         return *this;
0407     }
0408 
0409     inline void removeLast()
0410     {
0411         Base::pop_back();
0412     }
0413 #ifdef Q_QDOC
0414     inline qsizetype size() const { return this->s; }
0415     static constexpr qsizetype maxSize() noexcept { return QVLABase<T>::maxSize(); }
0416     constexpr qsizetype max_size() const noexcept { return QVLABase<T>::max_size(); }
0417 #endif
0418     using Base::size;
0419     using Base::max_size;
0420     inline qsizetype count() const { return size(); }
0421     inline qsizetype length() const { return size(); }
0422     inline T &first()
0423     {
0424         return front();
0425     }
0426     inline const T &first() const
0427     {
0428         return front();
0429     }
0430     T &last()
0431     {
0432         return back();
0433     }
0434     const T &last() const
0435     {
0436         return back();
0437     }
0438     bool isEmpty() const { return empty(); }
0439     void resize(qsizetype sz) { Base::resize_impl(Prealloc, this->array, sz); }
0440 #ifndef Q_QDOC
0441     template <typename U = T, if_copyable<U> = true>
0442 #endif
0443     void resize(qsizetype sz, const T &v)
0444     { Base::resize_impl(Prealloc, this->array, sz, v); }
0445     using Base::clear;
0446 #ifdef Q_QDOC
0447     inline void clear() { resize(0); }
0448 #endif
0449     void squeeze() { reallocate(size(), size()); }
0450 
0451     using Base::capacity;
0452 #ifdef Q_QDOC
0453     qsizetype capacity() const { return this->a; }
0454 #endif
0455     void reserve(qsizetype sz) { if (sz > capacity()) reallocate(size(), sz); }
0456 
0457 #ifdef Q_QDOC
0458     template <typename AT = T>
0459     inline qsizetype indexOf(const AT &t, qsizetype from = 0) const;
0460     template <typename AT = T>
0461     inline qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const;
0462     template <typename AT = T>
0463     inline bool contains(const AT &t) const;
0464 #endif
0465     using Base::indexOf;
0466     using Base::lastIndexOf;
0467     using Base::contains;
0468 
0469 #ifdef Q_QDOC
0470     inline T &operator[](qsizetype idx)
0471     {
0472         verify(idx);
0473         return data()[idx];
0474     }
0475     inline const T &operator[](qsizetype idx) const
0476     {
0477         verify(idx);
0478         return data()[idx];
0479     }
0480 #endif
0481     using Base::operator[];
0482     inline const T &at(qsizetype idx) const { return operator[](idx); }
0483 
0484 #ifdef Q_QDOC
0485     T value(qsizetype i) const;
0486     T value(qsizetype i, const T &defaultValue) const;
0487 #endif
0488     using Base::value;
0489 
0490     inline void append(const T &t)
0491     {
0492         if (size() == capacity())
0493             emplace_back(T(t));
0494         else
0495             emplace_back(t);
0496     }
0497 
0498     void append(T &&t)
0499     {
0500         emplace_back(std::move(t));
0501     }
0502 
0503     void append(const T *buf, qsizetype sz)
0504     { Base::append_impl(Prealloc, this->array, buf, sz); }
0505     inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
0506     { append(t); return *this; }
0507     inline QVarLengthArray<T, Prealloc> &operator<<(T &&t)
0508     { append(std::move(t)); return *this; }
0509     inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
0510     { append(t); return *this; }
0511     inline QVarLengthArray<T, Prealloc> &operator+=(T &&t)
0512     { append(std::move(t)); return *this; }
0513 
0514 #if QT_DEPRECATED_SINCE(6, 3)
0515     QT_DEPRECATED_VERSION_X_6_3("This is slow. If you must, use insert(cbegin(), ~~~) instead.")
0516     void prepend(T &&t);
0517     QT_DEPRECATED_VERSION_X_6_3("This is slow. If you must, use insert(cbegin(), ~~~) instead.")
0518     void prepend(const T &t);
0519 #endif
0520     void insert(qsizetype i, T &&t);
0521     void insert(qsizetype i, const T &t);
0522     void insert(qsizetype i, qsizetype n, const T &t);
0523 
0524     QVarLengthArray &assign(qsizetype n, const T &t)
0525     { Base::assign_impl(Prealloc, this->array, n, t); return *this; }
0526     template <typename InputIterator, if_input_iterator<InputIterator> = true>
0527     QVarLengthArray &assign(InputIterator first, InputIterator last)
0528     { Base::assign_impl(Prealloc, this->array, first, last); return *this; }
0529     QVarLengthArray &assign(std::initializer_list<T> list)
0530     { assign(list.begin(), list.end()); return *this; }
0531 
0532 #ifdef Q_QDOC
0533     void replace(qsizetype i, const T &t);
0534     void remove(qsizetype i, qsizetype n = 1);
0535     template <typename AT = T>
0536     qsizetype removeAll(const AT &t);
0537     template <typename AT = T>
0538     bool removeOne(const AT &t);
0539     template <typename Predicate>
0540     qsizetype removeIf(Predicate pred);
0541 #endif
0542     using Base::replace;
0543     using Base::remove;
0544     using Base::removeAll;
0545     using Base::removeOne;
0546     using Base::removeIf;
0547 
0548 #ifdef Q_QDOC
0549     inline T *data() { return this->ptr; }
0550     inline const T *data() const { return this->ptr; }
0551 #endif
0552     using Base::data;
0553     inline const T *constData() const { return data(); }
0554 #ifdef Q_QDOC
0555     inline iterator begin() { return data(); }
0556     inline const_iterator begin() const { return data(); }
0557     inline const_iterator cbegin() const { return begin(); }
0558     inline const_iterator constBegin() const { return begin(); }
0559     inline iterator end() { return data() + size(); }
0560     inline const_iterator end() const { return data() + size(); }
0561     inline const_iterator cend() const { return end(); }
0562 #endif
0563 
0564     using Base::begin;
0565     using Base::cbegin;
0566     auto constBegin() const -> const_iterator { return begin(); }
0567     using Base::end;
0568     using Base::cend;
0569     inline const_iterator constEnd() const { return end(); }
0570 #ifdef Q_QDOC
0571     reverse_iterator rbegin() { return reverse_iterator(end()); }
0572     reverse_iterator rend() { return reverse_iterator(begin()); }
0573     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
0574     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
0575     const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
0576     const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
0577 #endif
0578     using Base::rbegin;
0579     using Base::crbegin;
0580     using Base::rend;
0581     using Base::crend;
0582 
0583     iterator insert(const_iterator before, qsizetype n, const T &x)
0584     { return Base::insert_impl(Prealloc, this->array, before, n, x); }
0585     iterator insert(const_iterator before, T &&x) { return emplace(before, std::move(x)); }
0586     inline iterator insert(const_iterator before, const T &x) { return insert(before, 1, x); }
0587 #ifdef Q_QDOC
0588     iterator erase(const_iterator begin, const_iterator end);
0589     inline iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
0590 #endif
0591     using Base::erase;
0592 
0593     // STL compatibility:
0594 #ifdef Q_QDOC
0595     inline bool empty() const { return isEmpty(); }
0596 #endif
0597     using Base::empty;
0598     inline void push_back(const T &t) { append(t); }
0599     void push_back(T &&t) { append(std::move(t)); }
0600 #ifdef Q_QDOC
0601     inline void pop_back() { removeLast(); }
0602     inline T &front() { return first(); }
0603     inline const T &front() const { return first(); }
0604     inline T &back() { return last(); }
0605     inline const T &back() const { return last(); }
0606 #endif
0607     using Base::pop_back;
0608     using Base::front;
0609     using Base::back;
0610     void shrink_to_fit() { squeeze(); }
0611     template <typename...Args>
0612     iterator emplace(const_iterator pos, Args &&...args)
0613     { return Base::emplace_impl(Prealloc, this->array, pos, std::forward<Args>(args)...); }
0614     template <typename...Args>
0615     T &emplace_back(Args &&...args)
0616     { return Base::emplace_back_impl(Prealloc, this->array, std::forward<Args>(args)...); }
0617 
0618 
0619 #ifdef Q_QDOC
0620     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0621     friend inline bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0622     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0623     friend inline bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0624     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0625     friend inline bool operator< (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0626     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0627     friend inline bool operator> (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0628     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0629     friend inline bool operator<=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0630     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0631     friend inline bool operator>=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0632     template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
0633     friend inline auto operator<=>(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
0634 #else
0635 private:
0636     template <typename U = T, qsizetype Prealloc2 = Prealloc,
0637               Qt::if_has_qt_compare_three_way<U, U> = true>
0638     friend auto
0639     compareThreeWay(const QVarLengthArray &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0640     {
0641         return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.begin(), lhs.end(),
0642                                                                  rhs.begin(), rhs.end());
0643     }
0644 
0645 #if defined(__cpp_lib_three_way_comparison) && defined(__cpp_lib_concepts)
0646     template <typename U = T, qsizetype Prealloc2 = Prealloc,
0647               QtOrderingPrivate::if_has_op_less_or_op_compare_three_way<QVarLengthArray, U> = true>
0648     friend auto
0649     operator<=>(const QVarLengthArray &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0650     {
0651         return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
0652                                                       rhs.begin(), rhs.end(),
0653                                                       QtOrderingPrivate::synthThreeWay);
0654     }
0655 #endif // __cpp_lib_three_way_comparison && __cpp_lib_concepts
0656 
0657 public:
0658     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0659     QTypeTraits::compare_eq_result<U> operator==(const QVarLengthArray<T, Prealloc> &l, const QVarLengthArray<T, Prealloc2> &r)
0660     {
0661         return l.equal(r);
0662     }
0663 
0664     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0665     QTypeTraits::compare_eq_result<U> operator!=(const QVarLengthArray<T, Prealloc> &l, const QVarLengthArray<T, Prealloc2> &r)
0666     {
0667         return !(l == r);
0668     }
0669 
0670 #ifndef __cpp_lib_three_way_comparison
0671     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0672     QTypeTraits::compare_lt_result<U> operator<(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0673         noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(),
0674                                                        rhs.begin(), rhs.end())))
0675     {
0676         return lhs.less_than(rhs);
0677     }
0678 
0679     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0680     QTypeTraits::compare_lt_result<U> operator>(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0681         noexcept(noexcept(lhs < rhs))
0682     {
0683         return rhs < lhs;
0684     }
0685 
0686     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0687     QTypeTraits::compare_lt_result<U> operator<=(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0688         noexcept(noexcept(lhs < rhs))
0689     {
0690         return !(lhs > rhs);
0691     }
0692 
0693     template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
0694     QTypeTraits::compare_lt_result<U> operator>=(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
0695         noexcept(noexcept(lhs < rhs))
0696     {
0697         return !(lhs < rhs);
0698     }
0699 #endif // __cpp_lib_three_way_comparison
0700 #endif // Q_QDOC
0701 
0702 private:
0703     template <typename U, qsizetype Prealloc2>
0704     bool equal(const QVarLengthArray<U, Prealloc2> &other) const
0705     { return Base::equal(other); }
0706     template <typename U, qsizetype Prealloc2>
0707     bool less_than(const QVarLengthArray<U, Prealloc2> &other) const
0708     { return Base::less_than(other); }
0709 
0710     void reallocate(qsizetype sz, qsizetype alloc)
0711     { Base::reallocate_impl(Prealloc, this->array, sz, alloc); }
0712 
0713     using Base::isValidIterator;
0714 };
0715 
0716 template <typename InputIterator,
0717           typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
0718           QtPrivate::IfIsInputIterator<InputIterator> = true>
0719 QVarLengthArray(InputIterator, InputIterator) -> QVarLengthArray<ValueType>;
0720 
0721 template <class T, qsizetype Prealloc>
0722 Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(qsizetype asize)
0723     : QVarLengthArray()
0724 {
0725     Q_ASSERT_X(asize >= 0, "QVarLengthArray::QVarLengthArray(qsizetype)",
0726                "Size must be greater than or equal to 0.");
0727 
0728     // historically, this ctor worked for non-copyable/non-movable T, so keep it working, why not?
0729     // resize(asize) // this requires a movable or copyable T, can't use, need to do it by hand
0730 
0731     if (asize > Prealloc) {
0732         this->ptr = malloc(asize * sizeof(T));
0733         Q_CHECK_PTR(this->ptr);
0734         this->a = asize;
0735     }
0736     if constexpr (QTypeInfo<T>::isComplex)
0737         std::uninitialized_default_construct_n(data(), asize);
0738     this->s = asize;
0739 }
0740 
0741 template <class T>
0742 template <typename AT>
0743 Q_INLINE_TEMPLATE qsizetype QVLABase<T>::indexOf(const AT &t, qsizetype from) const
0744 {
0745     if (from < 0)
0746         from = qMax(from + size(), qsizetype(0));
0747     if (from < size()) {
0748         const T *n = data() + from - 1;
0749         const T *e = end();
0750         while (++n != e)
0751             if (*n == t)
0752                 return n - data();
0753     }
0754     return -1;
0755 }
0756 
0757 template <class T>
0758 template <typename AT>
0759 Q_INLINE_TEMPLATE qsizetype QVLABase<T>::lastIndexOf(const AT &t, qsizetype from) const
0760 {
0761     if (from < 0)
0762         from += size();
0763     else if (from >= size())
0764         from = size() - 1;
0765     if (from >= 0) {
0766         const T *b = begin();
0767         const T *n = b + from + 1;
0768         while (n != b) {
0769             if (*--n == t)
0770                 return n - b;
0771         }
0772     }
0773     return -1;
0774 }
0775 
0776 template <class T>
0777 template <typename AT>
0778 Q_INLINE_TEMPLATE bool QVLABase<T>::contains(const AT &t) const
0779 {
0780     const T *b = begin();
0781     const T *i = end();
0782     while (i != b) {
0783         if (*--i == t)
0784             return true;
0785     }
0786     return false;
0787 }
0788 
0789 template <class T>
0790 Q_OUTOFLINE_TEMPLATE void QVLABase<T>::append_impl(qsizetype prealloc, void *array, const T *abuf, qsizetype increment)
0791 {
0792     Q_ASSERT(abuf || increment == 0);
0793     if (increment <= 0)
0794         return;
0795 
0796     const qsizetype asize = size() + increment;
0797 
0798     if (asize >= capacity())
0799         growBy(prealloc, array, increment);
0800 
0801     if constexpr (QTypeInfo<T>::isComplex)
0802         std::uninitialized_copy_n(abuf, increment, end());
0803     else
0804         memcpy(static_cast<void *>(end()), static_cast<const void *>(abuf), increment * sizeof(T));
0805 
0806     this->s = asize;
0807 }
0808 
0809 template <class T>
0810 Q_OUTOFLINE_TEMPLATE void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t)
0811 {
0812     Q_ASSERT(n >= 0);
0813     if (n > capacity()) {
0814         reallocate_impl(prealloc, array, 0, capacity()); // clear
0815         resize_impl(prealloc, array, n, t);
0816     } else {
0817         auto mid = (std::min)(n, size());
0818         std::fill(data(), data() + mid, t);
0819         std::uninitialized_fill(data() + mid, data() + n, t);
0820         s = n;
0821         erase(data() + n, data() + size());
0822     }
0823 }
0824 
0825 template <class T>
0826 template <typename Iterator>
0827 Q_OUTOFLINE_TEMPLATE void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last)
0828 {
0829     // This function only provides the basic exception guarantee.
0830     constexpr bool IsFwdIt =
0831             std::is_convertible_v<typename std::iterator_traits<Iterator>::iterator_category,
0832                                   std::forward_iterator_tag>;
0833     if constexpr (IsFwdIt) {
0834         const qsizetype n = std::distance(first, last);
0835         if (n > capacity())
0836             reallocate_impl(prealloc, array, 0, n); // clear & reserve n
0837     }
0838 
0839     auto dst = begin();
0840     const auto dend = end();
0841     while (true) {
0842         if (first == last) {          // ran out of elements to assign
0843             std::destroy(dst, dend);
0844             break;
0845         }
0846         if (dst == dend) {            // ran out of existing elements to overwrite
0847             if constexpr (IsFwdIt) {
0848                 dst = std::uninitialized_copy(first, last, dst);
0849                 break;
0850             } else {
0851                 do {
0852                     emplace_back_impl(prealloc, array, *first);
0853                 } while (++first != last);
0854                 return; // size() is already correct (and dst invalidated)!
0855             }
0856         }
0857         *dst = *first;                // overwrite existing element
0858         ++dst;
0859         ++first;
0860     }
0861     this->s = dst - begin();
0862 }
0863 
0864 template <class T>
0865 Q_OUTOFLINE_TEMPLATE void QVLABase<T>::reallocate_impl(qsizetype prealloc, void *array, qsizetype asize, qsizetype aalloc)
0866 {
0867     Q_ASSERT(aalloc >= asize);
0868     Q_ASSERT(data());
0869     T *oldPtr = data();
0870     qsizetype osize = size();
0871 
0872     const qsizetype copySize = qMin(asize, osize);
0873     Q_ASSERT(copySize >= 0);
0874 
0875     if (aalloc != capacity()) {
0876         QVLABaseBase::malloced_ptr guard;
0877         void *newPtr;
0878         qsizetype newA;
0879         if (aalloc > prealloc) {
0880             newPtr = malloc(aalloc * sizeof(T));
0881             guard.reset(newPtr);
0882             Q_CHECK_PTR(newPtr); // could throw
0883             // by design: in case of QT_NO_EXCEPTIONS malloc must not fail or it crashes here
0884             newA = aalloc;
0885         } else {
0886             newPtr = array;
0887             newA = prealloc;
0888         }
0889         QtPrivate::q_uninitialized_relocate_n(oldPtr, copySize,
0890                                               reinterpret_cast<T *>(newPtr));
0891         // commit:
0892         ptr = newPtr;
0893         guard.release();
0894         a = newA;
0895     }
0896     s = copySize;
0897 
0898     // destroy remaining old objects
0899     if constexpr (QTypeInfo<T>::isComplex) {
0900         if (osize > asize)
0901             std::destroy(oldPtr + asize, oldPtr + osize);
0902     }
0903 
0904     if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != data())
0905         free(oldPtr);
0906 }
0907 
0908 template <class T>
0909 Q_OUTOFLINE_TEMPLATE T QVLABase<T>::value(qsizetype i) const
0910 {
0911     if (size_t(i) >= size_t(size()))
0912         return T();
0913     return operator[](i);
0914 }
0915 template <class T>
0916 Q_OUTOFLINE_TEMPLATE T QVLABase<T>::value(qsizetype i, const T &defaultValue) const
0917 {
0918     return (size_t(i) >= size_t(size())) ? defaultValue : operator[](i);
0919 }
0920 
0921 template <class T, qsizetype Prealloc>
0922 inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, T &&t)
0923 { verify(i, 0);
0924   insert(cbegin() + i, std::move(t)); }
0925 template <class T, qsizetype Prealloc>
0926 inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, const T &t)
0927 { verify(i, 0);
0928   insert(begin() + i, 1, t); }
0929 template <class T, qsizetype Prealloc>
0930 inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, qsizetype n, const T &t)
0931 { verify(i, 0);
0932   insert(begin() + i, n, t); }
0933 template <class T>
0934 inline void QVLABase<T>::remove(qsizetype i, qsizetype n)
0935 { verify(i, n);
0936   erase(begin() + i, begin() + i + n); }
0937 template <class T>
0938 template <typename AT>
0939 inline qsizetype QVLABase<T>::removeAll(const AT &t)
0940 { return QtPrivate::sequential_erase_with_copy(*this, t); }
0941 template <class T>
0942 template <typename AT>
0943 inline bool QVLABase<T>::removeOne(const AT &t)
0944 { return QtPrivate::sequential_erase_one(*this, t); }
0945 template <class T>
0946 template <typename Predicate>
0947 inline qsizetype QVLABase<T>::removeIf(Predicate pred)
0948 { return QtPrivate::sequential_erase_if(*this, pred); }
0949 #if QT_DEPRECATED_SINCE(6, 3)
0950 template <class T, qsizetype Prealloc>
0951 inline void QVarLengthArray<T, Prealloc>::prepend(T &&t)
0952 { insert(cbegin(), std::move(t)); }
0953 template <class T, qsizetype Prealloc>
0954 inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
0955 { insert(begin(), 1, t); }
0956 #endif
0957 
0958 template <class T>
0959 inline void QVLABase<T>::replace(qsizetype i, const T &t)
0960 {
0961     verify(i);
0962     data()[i] = t;
0963 }
0964 
0965 template <class T>
0966 template <typename...Args>
0967 Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::emplace_impl(qsizetype prealloc, void *array, const_iterator before, Args &&...args) -> iterator
0968 {
0969     Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
0970     Q_ASSERT(size() <= capacity());
0971     Q_ASSERT(capacity() > 0);
0972 
0973     const qsizetype offset = qsizetype(before - cbegin());
0974     emplace_back_impl(prealloc, array, std::forward<Args>(args)...);
0975     const auto b = begin() + offset;
0976     const auto e = end();
0977     QtPrivate::q_rotate(b, e - 1, e);
0978     return b;
0979 }
0980 
0981 template <class T>
0982 Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::insert_impl(qsizetype prealloc, void *array, const_iterator before, qsizetype n, const T &t) -> iterator
0983 {
0984     Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
0985 
0986     const qsizetype offset = qsizetype(before - cbegin());
0987     resize_impl(prealloc, array, size() + n, t);
0988     const auto b = begin() + offset;
0989     const auto e = end();
0990     QtPrivate::q_rotate(b, e - n, e);
0991     return b;
0992 }
0993 
0994 template <class T>
0995 Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::erase(const_iterator abegin, const_iterator aend) -> iterator
0996 {
0997     Q_ASSERT_X(isValidIterator(abegin), "QVarLengthArray::erase", "The specified const_iterator argument 'abegin' is invalid");
0998     Q_ASSERT_X(isValidIterator(aend), "QVarLengthArray::erase", "The specified const_iterator argument 'aend' is invalid");
0999 
1000     qsizetype f = qsizetype(abegin - cbegin());
1001     qsizetype l = qsizetype(aend - cbegin());
1002     qsizetype n = l - f;
1003 
1004     if (n == 0) // avoid UB in std::move() below
1005         return data() + f;
1006 
1007     Q_ASSERT(n > 0); // aend must be reachable from abegin
1008 
1009     if constexpr (!QTypeInfo<T>::isRelocatable) {
1010         std::move(begin() + l, end(), QT_MAKE_CHECKED_ARRAY_ITERATOR(begin() + f, size() - f));
1011         std::destroy(end() - n, end());
1012     } else {
1013         std::destroy(abegin, aend);
1014         memmove(static_cast<void *>(data() + f), static_cast<const void *>(data() + l), (size() - l) * sizeof(T));
1015     }
1016     this->s -= n;
1017     return data() + f;
1018 }
1019 
1020 #ifdef Q_QDOC
1021 // Fake definitions for qdoc, only the redeclaration is used.
1022 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1023 bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1024 { return bool{}; }
1025 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1026 bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1027 { return bool{}; }
1028 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1029 bool operator< (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1030 { return bool{}; }
1031 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1032 bool operator> (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1033 { return bool{}; }
1034 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1035 bool operator<=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1036 { return bool{}; }
1037 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1038 bool operator>=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1039 { return bool{}; }
1040 #endif
1041 
1042 template <typename T, qsizetype Prealloc>
1043 size_t qHash(const QVarLengthArray<T, Prealloc> &key, size_t seed = 0)
1044     noexcept(QtPrivate::QNothrowHashable_v<T>)
1045 {
1046     return key.hash(seed);
1047 }
1048 
1049 template <typename T, qsizetype Prealloc, typename AT>
1050 qsizetype erase(QVarLengthArray<T, Prealloc> &array, const AT &t)
1051 {
1052     return array.removeAll(t);
1053 }
1054 
1055 template <typename T, qsizetype Prealloc, typename Predicate>
1056 qsizetype erase_if(QVarLengthArray<T, Prealloc> &array, Predicate pred)
1057 {
1058     return array.removeIf(pred);
1059 }
1060 
1061 QT_END_NAMESPACE
1062 
1063 #endif // QVARLENGTHARRAY_H
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!