Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-09-05 09:19:26 

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