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

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