1// Copyright (C) 2021 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QVARLENGTHARRAY_H
5#define QVARLENGTHARRAY_H
6
7#if 0
8#pragma qt_class(QVarLengthArray)
9#pragma qt_sync_stop_processing
10#endif
11
12#include <QtCore/qalloc.h>
13#include <QtCore/qcompare.h>
14#include <QtCore/qcontainerfwd.h>
15#include <QtCore/qglobal.h>
16#include <QtCore/qalgorithms.h>
17#include <QtCore/qcontainertools_impl.h>
18#include <QtCore/qhashfunctions.h>
19#include <QtCore/qttypetraits.h>
20
21#include <algorithm>
22#include <initializer_list>
23#include <iterator>
24#include <QtCore/q20memory.h>
25#include <new>
26
27#include <string.h>
28#include <stdlib.h>
29
30QT_BEGIN_NAMESPACE
31
32template <size_t Size, size_t Align, qsizetype Prealloc>
33class QVLAStorage
34{
35 template <size_t> class print;
36protected:
37 QVLAStorage() = default;
38 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLAStorage)
39
40 alignas(Align) char array[Prealloc * (Align > Size ? Align : Size)];
41 QT_WARNING_PUSH
42 QT_WARNING_DISABLE_DEPRECATED
43 // ensure we maintain BC: std::aligned_storage_t was only specified by a
44 // minimum size, but for BC we need the substitution to be exact in size:
45 static_assert(std::is_same_v<print<sizeof(std::aligned_storage_t<Size, Align>[Prealloc])>,
46 print<sizeof(array)>>);
47 QT_WARNING_POP
48};
49
50class QVLABaseBase
51{
52protected:
53 QVLABaseBase() = default;
54 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLABaseBase)
55
56 qsizetype a; // capacity
57 qsizetype s; // size
58 void *ptr; // data
59
60 Q_ALWAYS_INLINE constexpr void verify([[maybe_unused]] qsizetype pos = 0,
61 [[maybe_unused]] qsizetype n = 1) const
62 {
63 Q_ASSERT(pos >= 0);
64 Q_ASSERT(pos <= size());
65 Q_ASSERT(n >= 0);
66 Q_ASSERT(n <= size() - pos);
67 }
68
69 struct free_deleter {
70 void operator()(void *p) const noexcept { free(ptr: p); }
71 };
72 using malloced_ptr = std::unique_ptr<void, free_deleter>;
73
74public:
75 using size_type = qsizetype;
76
77 constexpr size_type capacity() const noexcept { return a; }
78 constexpr size_type size() const noexcept { return s; }
79 constexpr bool empty() const noexcept { return size() == 0; }
80};
81
82template<class T>
83class QVLABase : public QVLABaseBase
84{
85protected:
86 QVLABase() = default;
87 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QVLABase)
88
89public:
90 T *data() noexcept { return static_cast<T *>(ptr); }
91 const T *data() const noexcept { return static_cast<T *>(ptr); }
92
93 using iterator = T*;
94 using const_iterator = const T*;
95
96 iterator begin() noexcept { return data(); }
97 const_iterator begin() const noexcept { return data(); }
98 const_iterator cbegin() const noexcept { return begin(); }
99 iterator end() noexcept { return data() + size(); }
100 const_iterator end() const noexcept { return data() + size(); }
101 const_iterator cend() const noexcept { return end(); }
102
103 using reverse_iterator = std::reverse_iterator<iterator>;
104 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
105
106 reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
107 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{end()}; }
108 const_reverse_iterator crbegin() const noexcept { return rbegin(); }
109 reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
110 const_reverse_iterator rend() const noexcept { return const_reverse_iterator{begin()}; }
111 const_reverse_iterator crend() const noexcept { return rend(); }
112
113 using value_type = T;
114 using reference = value_type&;
115 using const_reference = const value_type&;
116 using pointer = value_type*;
117 using const_pointer = const value_type*;
118 using difference_type = qptrdiff;
119
120 reference front()
121 {
122 verify();
123 return *begin();
124 }
125
126 const_reference front() const
127 {
128 verify();
129 return *begin();
130 }
131
132 reference back()
133 {
134 verify();
135 return *rbegin();
136 }
137
138 const_reference back() const
139 {
140 verify();
141 return *rbegin();
142 }
143
144 void pop_back()
145 {
146 verify();
147 if constexpr (QTypeInfo<T>::isComplex)
148 data()[size() - 1].~T();
149 --s;
150 }
151
152 template <typename AT = T>
153 qsizetype indexOf(const AT &t, qsizetype from = 0) const;
154 template <typename AT = T>
155 qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const;
156 template <typename AT = T>
157 bool contains(const AT &t) const;
158
159 reference operator[](qsizetype idx)
160 {
161 verify(pos: idx);
162 return data()[idx];
163 }
164 const_reference operator[](qsizetype idx) const
165 {
166 verify(pos: idx);
167 return data()[idx];
168 }
169
170 value_type value(qsizetype i) const;
171 value_type value(qsizetype i, const T& defaultValue) const;
172
173 void replace(qsizetype i, const T &t);
174 void remove(qsizetype i, qsizetype n = 1);
175 template <typename AT = T>
176 qsizetype removeAll(const AT &t);
177 template <typename AT = T>
178 bool removeOne(const AT &t);
179 template <typename Predicate>
180 qsizetype removeIf(Predicate pred);
181
182 void clear()
183 {
184 if constexpr (QTypeInfo<T>::isComplex)
185 std::destroy_n(data(), size());
186 s = 0;
187 }
188
189 iterator erase(const_iterator begin, const_iterator end);
190 iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
191
192 static constexpr qsizetype maxSize() noexcept
193 {
194 // -1 to deal with the pointer one-past-the-end
195 return (QtPrivate::MaxAllocSize / sizeof(T)) - 1;
196 }
197 constexpr qsizetype max_size() const noexcept
198 {
199 return maxSize();
200 }
201
202 size_t hash(size_t seed) const noexcept(QtPrivate::QNothrowHashable_v<T>)
203 {
204 return qHashRange(begin(), end(), seed);
205 }
206protected:
207 void growBy(qsizetype prealloc, void *array, qsizetype increment)
208 { reallocate_impl(prealloc, array, size: size(), alloc: (std::max)(size() * 2, size() + increment)); }
209 template <typename...Args>
210 reference emplace_back_impl(qsizetype prealloc, void *array, Args&&...args)
211 {
212 if (size() == capacity()) // ie. size() != 0
213 growBy(prealloc, array, increment: 1);
214 reference r = *q20::construct_at(end(), std::forward<Args>(args)...);
215 ++s;
216 return r;
217 }
218 template <typename...Args>
219 iterator emplace_impl(qsizetype prealloc, void *array, const_iterator pos, Args&&...arg);
220
221 iterator insert_impl(qsizetype prealloc, void *array, const_iterator pos, qsizetype n, const T &t);
222
223 template <typename S>
224 bool equal(const QVLABase<S> &other) const
225 {
226 return std::equal(begin(), end(), other.begin(), other.end());
227 }
228 template <typename S>
229 bool less_than(const QVLABase<S> &other) const
230 {
231 return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
232 }
233
234 void append_impl(qsizetype prealloc, void *array, const T *buf, qsizetype n);
235 void reallocate_impl(qsizetype prealloc, void *array, qsizetype size, qsizetype alloc);
236 void resize_impl(qsizetype prealloc, void *array, qsizetype sz, const T &v)
237 {
238 if (QtPrivate::q_points_into_range(&v, begin(), end())) {
239 resize_impl(prealloc, array, sz, T(v));
240 return;
241 }
242 reallocate_impl(prealloc, array, size: sz, alloc: qMax(sz, capacity()));
243 while (size() < sz) {
244 q20::construct_at(data() + size(), v);
245 ++s;
246 }
247 }
248 void resize_impl(qsizetype prealloc, void *array, qsizetype sz)
249 {
250 reallocate_impl(prealloc, array, size: sz, alloc: qMax(sz, capacity()));
251 if constexpr (QTypeInfo<T>::isComplex) {
252 // call default constructor for new objects (which can throw)
253 while (size() < sz) {
254 q20::construct_at(data() + size());
255 ++s;
256 }
257 } else {
258 s = sz;
259 }
260 }
261
262 void assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t);
263 template <typename Iterator>
264 void assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last,
265 std::forward_iterator_tag);
266 template <typename Iterator>
267 void assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last,
268 std::input_iterator_tag);
269 template <typename Iterator>
270 void assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last);
271
272 bool isValidIterator(const const_iterator &i) const
273 {
274 const std::less<const T *> less = {};
275 return !less(cend(), i) && !less(i, cbegin());
276 }
277};
278
279// Prealloc = 256 by default, specified in qcontainerfwd.h
280template<class T, qsizetype Prealloc>
281class QVarLengthArray
282#if QT_VERSION >= QT_VERSION_CHECK(7,0,0) || defined(QT_BOOTSTRAPPED)
283 : public QVLAStorage<sizeof(T), alignof(T), Prealloc>,
284 public QVLABase<T>
285#else
286 : public QVLABase<T>,
287 public QVLAStorage<sizeof(T), alignof(T), Prealloc>
288#endif
289{
290 template <class S, qsizetype Prealloc2>
291 friend class QVarLengthArray;
292 using Base = QVLABase<T>;
293 using Storage = QVLAStorage<sizeof(T), alignof(T), Prealloc>;
294 static_assert(Prealloc > 0, "QVarLengthArray Prealloc must be greater than 0.");
295 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
296 using Base::verify;
297
298 template <typename U>
299 using if_copyable = std::enable_if_t<std::is_copy_constructible_v<U>, bool>;
300 template <typename InputIterator>
301 using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>;
302public:
303 static constexpr qsizetype PreallocatedSize = Prealloc;
304
305 using size_type = typename Base::size_type;
306 using value_type = typename Base::value_type;
307 using pointer = typename Base::pointer;
308 using const_pointer = typename Base::const_pointer;
309 using reference = typename Base::reference;
310 using const_reference = typename Base::const_reference;
311 using difference_type = typename Base::difference_type;
312
313 using iterator = typename Base::iterator;
314 using const_iterator = typename Base::const_iterator;
315 using reverse_iterator = typename Base::reverse_iterator;
316 using const_reverse_iterator = typename Base::const_reverse_iterator;
317
318 QVarLengthArray() noexcept
319 {
320 this->a = Prealloc;
321 this->s = 0;
322 this->ptr = this->array;
323 }
324
325 inline explicit QVarLengthArray(qsizetype size);
326
327#ifndef Q_QDOC
328 template <typename U = T, if_copyable<U> = true>
329#endif
330 explicit QVarLengthArray(qsizetype sz, const T &v)
331 : QVarLengthArray{}
332 {
333 resize(sz, v);
334 }
335
336 QVarLengthArray(const QVarLengthArray &other)
337 : QVarLengthArray{}
338 {
339 append(other.constData(), other.size());
340 }
341
342 QVarLengthArray(QVarLengthArray &&other)
343 noexcept(std::is_nothrow_move_constructible_v<T>)
344 : Base(other)
345 {
346 const auto otherInlineStorage = reinterpret_cast<T*>(other.array);
347 if (data() == otherInlineStorage) {
348 // inline buffer - move into our inline buffer:
349 this->ptr = this->array;
350 QtPrivate::q_uninitialized_relocate_n(otherInlineStorage, size(), data());
351 } else {
352 // heap buffer - we just stole the memory
353 }
354 // reset other to internal storage:
355 other.a = Prealloc;
356 other.s = 0;
357 other.ptr = otherInlineStorage;
358 }
359
360 QVarLengthArray(std::initializer_list<T> args)
361 : QVarLengthArray(args.begin(), args.end())
362 {
363 }
364
365 template <typename InputIterator, if_input_iterator<InputIterator> = true>
366 inline QVarLengthArray(InputIterator first, InputIterator last)
367 : QVarLengthArray()
368 {
369 assign(first, last);
370 }
371
372 inline ~QVarLengthArray()
373 {
374 if constexpr (QTypeInfo<T>::isComplex)
375 std::destroy_n(data(), size());
376 if (data() != reinterpret_cast<T *>(this->array))
377 QtPrivate::sizedFree(data(), capacity(), sizeof(T));
378 }
379 inline QVarLengthArray<T, Prealloc> &operator=(const QVarLengthArray<T, Prealloc> &other)
380 {
381 if (this != &other) {
382 clear();
383 append(other.constData(), other.size());
384 }
385 return *this;
386 }
387
388 QVarLengthArray &operator=(QVarLengthArray &&other)
389 noexcept(std::is_nothrow_move_constructible_v<T>)
390 {
391 // we're only required to be self-move-assignment-safe
392 // when we're in the moved-from state (Hinnant criterion)
393 // the moved-from state is the empty state, so we're good with the clear() here:
394 clear();
395 Q_ASSERT(capacity() >= Prealloc);
396 const auto otherInlineStorage = other.array;
397 if (other.ptr != otherInlineStorage) {
398 // heap storage: steal the external buffer, reset other to otherInlineStorage
399 this->a = std::exchange(other.a, Prealloc);
400 this->ptr = std::exchange(other.ptr, otherInlineStorage);
401 } else {
402 // inline storage: move into our storage (doesn't matter whether inline or external)
403 QtPrivate::q_uninitialized_relocate_n(other.data(), other.size(), data());
404 }
405 this->s = std::exchange(other.s, 0);
406 return *this;
407 }
408
409 QVarLengthArray<T, Prealloc> &operator=(std::initializer_list<T> list)
410 {
411 assign(list);
412 return *this;
413 }
414
415 inline void removeLast()
416 {
417 Base::pop_back();
418 }
419#ifdef Q_QDOC
420 inline qsizetype size() const { return this->s; }
421 static constexpr qsizetype maxSize() noexcept { return QVLABase<T>::maxSize(); }
422 constexpr qsizetype max_size() const noexcept { return QVLABase<T>::max_size(); }
423#endif
424 using Base::size;
425 using Base::max_size;
426 inline qsizetype count() const { return size(); }
427 inline qsizetype length() const { return size(); }
428 inline T &first()
429 {
430 return front();
431 }
432 inline const T &first() const
433 {
434 return front();
435 }
436 T &last()
437 {
438 return back();
439 }
440 const T &last() const
441 {
442 return back();
443 }
444 bool isEmpty() const { return empty(); }
445 void resize(qsizetype sz) { Base::resize_impl(Prealloc, this->array, sz); }
446#ifndef Q_QDOC
447 template <typename U = T, if_copyable<U> = true>
448#endif
449 void resize(qsizetype sz, const T &v)
450 { Base::resize_impl(Prealloc, this->array, sz, v); }
451 using Base::clear;
452#ifdef Q_QDOC
453 inline void clear() { resize(0); }
454#endif
455 void squeeze() { reallocate(sz: size(), alloc: size()); }
456
457 using Base::capacity;
458#ifdef Q_QDOC
459 qsizetype capacity() const { return this->a; }
460#endif
461 void reserve(qsizetype sz) { if (sz > capacity()) reallocate(sz: size(), alloc: sz); }
462
463#ifdef Q_QDOC
464 template <typename AT = T>
465 inline qsizetype indexOf(const AT &t, qsizetype from = 0) const;
466 template <typename AT = T>
467 inline qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const;
468 template <typename AT = T>
469 inline bool contains(const AT &t) const;
470#endif
471 using Base::indexOf;
472 using Base::lastIndexOf;
473 using Base::contains;
474
475#ifdef Q_QDOC
476 inline T &operator[](qsizetype idx)
477 {
478 verify(idx);
479 return data()[idx];
480 }
481 inline const T &operator[](qsizetype idx) const
482 {
483 verify(idx);
484 return data()[idx];
485 }
486#endif
487 using Base::operator[];
488 inline const T &at(qsizetype idx) const { return operator[](idx); }
489
490#ifdef Q_QDOC
491 T value(qsizetype i) const;
492 T value(qsizetype i, const T &defaultValue) const;
493#endif
494 using Base::value;
495
496 inline void append(const T &t)
497 {
498 if (size() == capacity())
499 emplace_back(T(t));
500 else
501 emplace_back(t);
502 }
503
504 void append(T &&t)
505 {
506 emplace_back(std::move(t));
507 }
508
509 void append(const T *buf, qsizetype sz)
510 { Base::append_impl(Prealloc, this->array, buf, sz); }
511 inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
512 { append(t); return *this; }
513 inline QVarLengthArray<T, Prealloc> &operator<<(T &&t)
514 { append(std::move(t)); return *this; }
515 inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
516 { append(t); return *this; }
517 inline QVarLengthArray<T, Prealloc> &operator+=(T &&t)
518 { append(std::move(t)); return *this; }
519
520#if QT_DEPRECATED_SINCE(6, 3)
521 QT_DEPRECATED_VERSION_X_6_3("This is slow. If you must, use insert(cbegin(), ~~~) instead.")
522 void prepend(T &&t);
523 QT_DEPRECATED_VERSION_X_6_3("This is slow. If you must, use insert(cbegin(), ~~~) instead.")
524 void prepend(const T &t);
525#endif
526 void insert(qsizetype i, T &&t);
527 void insert(qsizetype i, const T &t);
528 void insert(qsizetype i, qsizetype n, const T &t);
529
530 QVarLengthArray &assign(qsizetype n, const T &t)
531 { Base::assign_impl(Prealloc, this->array, n, t); return *this; }
532 template <typename InputIterator, if_input_iterator<InputIterator> = true>
533 QVarLengthArray &assign(InputIterator first, InputIterator last)
534 { Base::assign_impl(Prealloc, this->array, first, last); return *this; }
535 QVarLengthArray &assign(std::initializer_list<T> list)
536 { assign(list.begin(), list.end()); return *this; }
537
538#ifdef Q_QDOC
539 void replace(qsizetype i, const T &t);
540 void remove(qsizetype i, qsizetype n = 1);
541 template <typename AT = T>
542 qsizetype removeAll(const AT &t);
543 template <typename AT = T>
544 bool removeOne(const AT &t);
545 template <typename Predicate>
546 qsizetype removeIf(Predicate pred);
547#endif
548 using Base::replace;
549 using Base::remove;
550 using Base::removeAll;
551 using Base::removeOne;
552 using Base::removeIf;
553
554#ifdef Q_QDOC
555 inline T *data() { return this->ptr; }
556 inline const T *data() const { return this->ptr; }
557#endif
558 using Base::data;
559 inline const T *constData() const { return data(); }
560#ifdef Q_QDOC
561 inline iterator begin() { return data(); }
562 inline const_iterator begin() const { return data(); }
563 inline const_iterator cbegin() const { return begin(); }
564 inline const_iterator constBegin() const { return begin(); }
565 inline iterator end() { return data() + size(); }
566 inline const_iterator end() const { return data() + size(); }
567 inline const_iterator cend() const { return end(); }
568#endif
569
570 using Base::begin;
571 using Base::cbegin;
572 auto constBegin() const -> const_iterator { return begin(); }
573 using Base::end;
574 using Base::cend;
575 inline const_iterator constEnd() const { return end(); }
576#ifdef Q_QDOC
577 reverse_iterator rbegin() { return reverse_iterator(end()); }
578 reverse_iterator rend() { return reverse_iterator(begin()); }
579 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
580 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
581 const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
582 const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
583#endif
584 using Base::rbegin;
585 using Base::crbegin;
586 using Base::rend;
587 using Base::crend;
588
589 iterator insert(const_iterator before, qsizetype n, const T &x)
590 { return Base::insert_impl(Prealloc, this->array, before, n, x); }
591 iterator insert(const_iterator before, T &&x) { return emplace(before, std::move(x)); }
592 inline iterator insert(const_iterator before, const T &x) { return insert(before, 1, x); }
593#ifdef Q_QDOC
594 iterator erase(const_iterator begin, const_iterator end);
595 inline iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
596#endif
597 using Base::erase;
598
599 // STL compatibility:
600#ifdef Q_QDOC
601 inline bool empty() const { return isEmpty(); }
602#endif
603 using Base::empty;
604 inline void push_back(const T &t) { append(t); }
605 void push_back(T &&t) { append(std::move(t)); }
606#ifdef Q_QDOC
607 inline void pop_back() { removeLast(); }
608 inline T &front() { return first(); }
609 inline const T &front() const { return first(); }
610 inline T &back() { return last(); }
611 inline const T &back() const { return last(); }
612#endif
613 using Base::pop_back;
614 using Base::front;
615 using Base::back;
616 void shrink_to_fit() { squeeze(); }
617 template <typename...Args>
618 iterator emplace(const_iterator pos, Args &&...args)
619 { return Base::emplace_impl(Prealloc, this->array, pos, std::forward<Args>(args)...); }
620 template <typename...Args>
621 T &emplace_back(Args &&...args)
622 { return Base::emplace_back_impl(Prealloc, this->array, std::forward<Args>(args)...); }
623
624
625#ifdef Q_QDOC
626 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
627 friend inline bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
628 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
629 friend inline bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
630 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
631 friend inline bool operator< (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
632 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
633 friend inline bool operator> (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
634 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
635 friend inline bool operator<=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
636 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
637 friend inline bool operator>=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
638 template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
639 friend inline auto operator<=>(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r);
640#else
641private:
642 template <typename U = T, qsizetype Prealloc2 = Prealloc,
643 Qt::if_has_qt_compare_three_way<U, U> = true>
644 friend auto
645 compareThreeWay(const QVarLengthArray &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
646 {
647 return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.begin(), lhs.end(),
648 rhs.begin(), rhs.end());
649 }
650
651#if defined(__cpp_lib_three_way_comparison) && defined(__cpp_lib_concepts)
652 template <typename U = T, qsizetype Prealloc2 = Prealloc,
653 QtOrderingPrivate::if_has_op_less_or_op_compare_three_way<QVarLengthArray, U> = true>
654 friend auto
655 operator<=>(const QVarLengthArray &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
656 {
657 return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
658 rhs.begin(), rhs.end(),
659 QtOrderingPrivate::synthThreeWay);
660 }
661#endif // __cpp_lib_three_way_comparison && __cpp_lib_concepts
662
663public:
664 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
665 QTypeTraits::compare_eq_result<U> operator==(const QVarLengthArray<T, Prealloc> &l, const QVarLengthArray<T, Prealloc2> &r)
666 {
667 return l.equal(r);
668 }
669
670 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
671 QTypeTraits::compare_eq_result<U> operator!=(const QVarLengthArray<T, Prealloc> &l, const QVarLengthArray<T, Prealloc2> &r)
672 {
673 return !(l == r);
674 }
675
676#ifndef __cpp_lib_three_way_comparison
677 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
678 QTypeTraits::compare_lt_result<U> operator<(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
679 noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(),
680 rhs.begin(), rhs.end())))
681 {
682 return lhs.less_than(rhs);
683 }
684
685 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
686 QTypeTraits::compare_lt_result<U> operator>(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
687 noexcept(noexcept(lhs < rhs))
688 {
689 return rhs < lhs;
690 }
691
692 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
693 QTypeTraits::compare_lt_result<U> operator<=(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
694 noexcept(noexcept(lhs < rhs))
695 {
696 return !(lhs > rhs);
697 }
698
699 template <typename U = T, qsizetype Prealloc2 = Prealloc> friend
700 QTypeTraits::compare_lt_result<U> operator>=(const QVarLengthArray<T, Prealloc> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
701 noexcept(noexcept(lhs < rhs))
702 {
703 return !(lhs < rhs);
704 }
705#endif // __cpp_lib_three_way_comparison
706#endif // Q_QDOC
707
708private:
709 template <typename U, qsizetype Prealloc2>
710 bool equal(const QVarLengthArray<U, Prealloc2> &other) const
711 { return Base::equal(other); }
712 template <typename U, qsizetype Prealloc2>
713 bool less_than(const QVarLengthArray<U, Prealloc2> &other) const
714 { return Base::less_than(other); }
715
716 void reallocate(qsizetype sz, qsizetype alloc)
717 { Base::reallocate_impl(Prealloc, this->array, sz, alloc); }
718
719 using Base::isValidIterator;
720};
721
722template <typename InputIterator,
723 typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
724 QtPrivate::IfIsInputIterator<InputIterator> = true>
725QVarLengthArray(InputIterator, InputIterator) -> QVarLengthArray<ValueType>;
726
727template <class T, qsizetype Prealloc>
728Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(qsizetype asize)
729 : QVarLengthArray()
730{
731 Q_ASSERT_X(asize >= 0, "QVarLengthArray::QVarLengthArray(qsizetype)",
732 "Size must be greater than or equal to 0.");
733
734 // historically, this ctor worked for non-copyable/non-movable T, so keep it working, why not?
735 // resize(asize) // this requires a movable or copyable T, can't use, need to do it by hand
736
737 if (asize > Prealloc) {
738 this->a = asize;
739 this->ptr = QtPrivate::fittedMalloc(0, &this->a, sizeof(T));
740 Q_CHECK_PTR(this->ptr);
741 }
742 if constexpr (QTypeInfo<T>::isComplex)
743 std::uninitialized_default_construct_n(data(), asize);
744 this->s = asize;
745}
746
747template <class T>
748template <typename AT>
749Q_INLINE_TEMPLATE qsizetype QVLABase<T>::indexOf(const AT &t, qsizetype from) const
750{
751 if (from < 0)
752 from = qMax(from + size(), qsizetype(0));
753 if (from < size()) {
754 const T *n = data() + from - 1;
755 const T *e = end();
756 while (++n != e)
757 if (*n == t)
758 return n - data();
759 }
760 return -1;
761}
762
763template <class T>
764template <typename AT>
765Q_INLINE_TEMPLATE qsizetype QVLABase<T>::lastIndexOf(const AT &t, qsizetype from) const
766{
767 if (from < 0)
768 from += size();
769 else if (from >= size())
770 from = size() - 1;
771 if (from >= 0) {
772 const T *b = begin();
773 const T *n = b + from + 1;
774 while (n != b) {
775 if (*--n == t)
776 return n - b;
777 }
778 }
779 return -1;
780}
781
782template <class T>
783template <typename AT>
784Q_INLINE_TEMPLATE bool QVLABase<T>::contains(const AT &t) const
785{
786 const T *b = begin();
787 const T *i = end();
788 while (i != b) {
789 if (*--i == t)
790 return true;
791 }
792 return false;
793}
794
795template <class T>
796Q_OUTOFLINE_TEMPLATE void QVLABase<T>::append_impl(qsizetype prealloc, void *array, const T *abuf, qsizetype increment)
797{
798 Q_ASSERT(abuf || increment == 0);
799 if (increment <= 0)
800 return;
801
802 const qsizetype asize = size() + increment;
803
804 if (asize >= capacity())
805 growBy(prealloc, array, increment);
806
807 if constexpr (QTypeInfo<T>::isComplex)
808 std::uninitialized_copy_n(abuf, increment, end());
809 else
810 memcpy(dest: static_cast<void *>(end()), src: static_cast<const void *>(abuf), n: increment * sizeof(T));
811
812 this->s = asize;
813}
814
815template <class T>
816Q_OUTOFLINE_TEMPLATE void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, qsizetype n, const T &t)
817{
818 Q_ASSERT(n >= 0);
819 if (n > capacity()) {
820 reallocate_impl(prealloc, array, size: 0, alloc: capacity()); // clear
821 resize_impl(prealloc, array, n, t);
822 } else {
823 auto mid = (std::min)(n, size());
824 std::fill(data(), data() + mid, t);
825 std::uninitialized_fill(data() + mid, data() + n, t);
826 s = n;
827 erase(data() + n, data() + size());
828 }
829}
830
831template <class T>
832template <typename Iterator>
833Q_OUTOFLINE_TEMPLATE
834void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last,
835 std::forward_iterator_tag)
836{
837 // This function only provides the basic exception guarantee.
838 const qsizetype n = std::distance(first, last);
839 if (n > capacity())
840 reallocate_impl(prealloc, array, size: 0, alloc: n); // clear & reserve n
841
842 auto dst = begin();
843
844 if constexpr (!QTypeInfo<T>::isComplex) {
845 // For non-complex types, we prefer a single std::copy() -> memcpy()
846 // call. We can do that because either the default constructor is
847 // trivial (so the lifetime has started) or the copy constructor is
848 // (and won't care what the stored value is). Note that in some cases
849 // dst > end() after this.
850 dst = std::copy(first, last, dst);
851 } else if (n > this->s) {
852 // overwrite existing elements and create new
853 for (qsizetype i = 0; i < this->s; ++i) {
854 *dst = *first;
855 ++first;
856 ++dst;
857 }
858 std::uninitialized_copy_n(first, n - this->s, dst);
859 } else {
860 // overwrite existing elements and destroy tail
861 dst = std::copy(first, last, dst);
862 std::destroy(dst, end());
863 }
864 this->s = n;
865}
866
867template <class T>
868template <typename Iterator>
869Q_OUTOFLINE_TEMPLATE
870void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last,
871 std::input_iterator_tag)
872{
873 // This function only provides the basic exception guarantee.
874 auto dst = begin();
875 const auto dend = end();
876 while (true) {
877 if (first == last) { // ran out of elements to assign
878 std::destroy(dst, dend);
879 break;
880 }
881 if (dst == dend) { // ran out of existing elements to overwrite
882 do {
883 emplace_back_impl(prealloc, array, *first);
884 } while (++first != last);
885 return; // size() is already correct (and dst invalidated)!
886 }
887 *dst = *first; // overwrite existing element
888 ++dst;
889 ++first;
890 }
891 this->s = dst - begin();
892}
893
894template <class T>
895template <typename Iterator>
896Q_OUTOFLINE_TEMPLATE
897void QVLABase<T>::assign_impl(qsizetype prealloc, void *array, Iterator first, Iterator last)
898{
899 using Cat = typename std::iterator_traits<Iterator>::iterator_category;
900 assign_impl(prealloc, array, first, last, Cat{});
901}
902
903template <class T>
904Q_OUTOFLINE_TEMPLATE void QVLABase<T>::reallocate_impl(qsizetype prealloc, void *array, qsizetype asize, qsizetype aalloc)
905{
906 Q_ASSERT(aalloc >= asize);
907 Q_ASSERT(data());
908 T *oldPtr = data();
909 qsizetype osize = size();
910 const qsizetype oalloc = capacity();
911
912 const qsizetype copySize = qMin(a: asize, b: osize);
913 Q_ASSERT(copySize >= 0);
914
915 if (aalloc != oalloc) {
916 QVLABaseBase::malloced_ptr guard;
917 void *newPtr;
918 qsizetype newA;
919 if (aalloc > prealloc) {
920 newPtr = QtPrivate::fittedMalloc(headerSize: 0, capacity: &aalloc, elementSize: sizeof(T));
921 guard.reset(p: newPtr);
922 Q_CHECK_PTR(newPtr); // could throw
923 // by design: in case of QT_NO_EXCEPTIONS malloc must not fail or it crashes here
924 newA = aalloc;
925 } else {
926 newPtr = array;
927 newA = prealloc;
928 }
929 QtPrivate::q_uninitialized_relocate_n(oldPtr, copySize,
930 reinterpret_cast<T *>(newPtr));
931 // commit:
932 ptr = newPtr;
933 guard.release();
934 a = newA;
935 }
936 s = copySize;
937
938 // destroy remaining old objects
939 if constexpr (QTypeInfo<T>::isComplex) {
940 if (osize > asize)
941 std::destroy(oldPtr + asize, oldPtr + osize);
942 }
943
944 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != data())
945 QtPrivate::sizedFree(oldPtr, oalloc, sizeof(T));
946}
947
948template <class T>
949Q_OUTOFLINE_TEMPLATE T QVLABase<T>::value(qsizetype i) const
950{
951 if (size_t(i) >= size_t(size()))
952 return T();
953 return operator[](i);
954}
955template <class T>
956Q_OUTOFLINE_TEMPLATE T QVLABase<T>::value(qsizetype i, const T &defaultValue) const
957{
958 return (size_t(i) >= size_t(size())) ? defaultValue : operator[](i);
959}
960
961template <class T, qsizetype Prealloc>
962inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, T &&t)
963{ verify(i, 0);
964 insert(cbegin() + i, std::move(t)); }
965template <class T, qsizetype Prealloc>
966inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, const T &t)
967{ verify(i, 0);
968 insert(begin() + i, 1, t); }
969template <class T, qsizetype Prealloc>
970inline void QVarLengthArray<T, Prealloc>::insert(qsizetype i, qsizetype n, const T &t)
971{ verify(i, 0);
972 insert(begin() + i, n, t); }
973template <class T>
974inline void QVLABase<T>::remove(qsizetype i, qsizetype n)
975{ verify(pos: i, n);
976 erase(begin() + i, begin() + i + n); }
977template <class T>
978template <typename AT>
979inline qsizetype QVLABase<T>::removeAll(const AT &t)
980{ return QtPrivate::sequential_erase_with_copy(*this, t); }
981template <class T>
982template <typename AT>
983inline bool QVLABase<T>::removeOne(const AT &t)
984{ return QtPrivate::sequential_erase_one(*this, t); }
985template <class T>
986template <typename Predicate>
987inline qsizetype QVLABase<T>::removeIf(Predicate pred)
988{ return QtPrivate::sequential_erase_if(*this, pred); }
989#if QT_DEPRECATED_SINCE(6, 3)
990template <class T, qsizetype Prealloc>
991inline void QVarLengthArray<T, Prealloc>::prepend(T &&t)
992{ insert(cbegin(), std::move(t)); }
993template <class T, qsizetype Prealloc>
994inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
995{ insert(begin(), 1, t); }
996#endif
997
998template <class T>
999inline void QVLABase<T>::replace(qsizetype i, const T &t)
1000{
1001 verify(pos: i);
1002 data()[i] = t;
1003}
1004
1005template <class T>
1006template <typename...Args>
1007Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::emplace_impl(qsizetype prealloc, void *array, const_iterator before, Args &&...args) -> iterator
1008{
1009 Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
1010 Q_ASSERT(size() <= capacity());
1011 Q_ASSERT(capacity() > 0);
1012
1013 const qsizetype offset = qsizetype(before - cbegin());
1014 emplace_back_impl(prealloc, array, std::forward<Args>(args)...);
1015 const auto b = begin() + offset;
1016 const auto e = end();
1017 QtPrivate::q_rotate(b, e - 1, e);
1018 return b;
1019}
1020
1021template <class T>
1022Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::insert_impl(qsizetype prealloc, void *array, const_iterator before, qsizetype n, const T &t) -> iterator
1023{
1024 Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
1025
1026 const qsizetype offset = qsizetype(before - cbegin());
1027 resize_impl(prealloc, array, size() + n, t);
1028 const auto b = begin() + offset;
1029 const auto e = end();
1030 QtPrivate::q_rotate(b, e - n, e);
1031 return b;
1032}
1033
1034template <class T>
1035Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::erase(const_iterator abegin, const_iterator aend) -> iterator
1036{
1037 Q_ASSERT_X(isValidIterator(abegin), "QVarLengthArray::erase", "The specified const_iterator argument 'abegin' is invalid");
1038 Q_ASSERT_X(isValidIterator(aend), "QVarLengthArray::erase", "The specified const_iterator argument 'aend' is invalid");
1039
1040 qsizetype f = qsizetype(abegin - cbegin());
1041 qsizetype l = qsizetype(aend - cbegin());
1042 qsizetype n = l - f;
1043
1044 if (n == 0) // avoid UB in std::move() below
1045 return data() + f;
1046
1047 Q_ASSERT(n > 0); // aend must be reachable from abegin
1048
1049 if constexpr (!QTypeInfo<T>::isRelocatable) {
1050 std::move(begin() + l, end(), QT_MAKE_CHECKED_ARRAY_ITERATOR(begin() + f, size() - f));
1051 std::destroy(end() - n, end());
1052 } else {
1053 std::destroy(abegin, aend);
1054 memmove(static_cast<void *>(data() + f), static_cast<const void *>(data() + l), (size() - l) * sizeof(T));
1055 }
1056 this->s -= n;
1057 return data() + f;
1058}
1059
1060#ifdef Q_QDOC
1061// Fake definitions for qdoc, only the redeclaration is used.
1062template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1063bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1064{ return bool{}; }
1065template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1066bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1067{ return bool{}; }
1068template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1069bool operator< (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1070{ return bool{}; }
1071template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1072bool operator> (const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1073{ return bool{}; }
1074template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1075bool operator<=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1076{ return bool{}; }
1077template <typename T, qsizetype Prealloc1, qsizetype Prealloc2>
1078bool operator>=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
1079{ return bool{}; }
1080#endif
1081
1082template <typename T, qsizetype Prealloc>
1083size_t qHash(const QVarLengthArray<T, Prealloc> &key, size_t seed = 0)
1084 noexcept(QtPrivate::QNothrowHashable_v<T>)
1085{
1086 return key.hash(seed);
1087}
1088
1089template <typename T, qsizetype Prealloc, typename AT>
1090qsizetype erase(QVarLengthArray<T, Prealloc> &array, const AT &t)
1091{
1092 return array.removeAll(t);
1093}
1094
1095template <typename T, qsizetype Prealloc, typename Predicate>
1096qsizetype erase_if(QVarLengthArray<T, Prealloc> &array, Predicate pred)
1097{
1098 return array.removeIf(pred);
1099}
1100
1101QT_END_NAMESPACE
1102
1103#endif // QVARLENGTHARRAY_H
1104

source code of qtbase/src/corelib/tools/qvarlengtharray.h