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

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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