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