1// Copyright (C) 2020 The Qt Company Ltd.
2// Copyright (C) 2016 Intel Corporation.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#ifndef QARRAYDATAOPS_H
6#define QARRAYDATAOPS_H
7
8#include <QtCore/qarraydata.h>
9#include <QtCore/qcontainertools_impl.h>
10#include <QtCore/qnamespace.h>
11
12#include <memory>
13#include <new>
14#include <string.h>
15#include <utility>
16#include <iterator>
17#include <tuple>
18#include <type_traits>
19
20QT_BEGIN_NAMESPACE
21
22template <class T> struct QArrayDataPointer;
23
24namespace QtPrivate {
25
26template <class T>
27struct QPodArrayOps
28 : public QArrayDataPointer<T>
29{
30 static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
31
32protected:
33 typedef QTypedArrayData<T> Data;
34 using DataPointer = QArrayDataPointer<T>;
35
36public:
37 typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
38
39 using QArrayDataPointer<T>::QArrayDataPointer;
40
41 void appendInitialize(qsizetype newSize) noexcept
42 {
43 Q_ASSERT(this->isMutable());
44 Q_ASSERT(!this->isShared());
45 Q_ASSERT(newSize > this->size);
46 Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd());
47
48 T *where = this->end();
49 this->size = newSize;
50 const T *e = this->end();
51 while (where != e)
52 *where++ = T();
53 }
54
55 void copyAppend(const T *b, const T *e) noexcept
56 {
57 Q_ASSERT(this->isMutable() || b == e);
58 Q_ASSERT(!this->isShared() || b == e);
59 Q_ASSERT(b <= e);
60 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
61
62 if (b == e)
63 return;
64
65 ::memcpy(dest: static_cast<void *>(this->end()), src: static_cast<const void *>(b), n: (e - b) * sizeof(T));
66 this->size += (e - b);
67 }
68
69 void copyAppend(qsizetype n, parameter_type t) noexcept
70 {
71 Q_ASSERT(!this->isShared() || n == 0);
72 Q_ASSERT(this->freeSpaceAtEnd() >= n);
73 if (!n)
74 return;
75
76 T *where = this->end();
77 this->size += qsizetype(n);
78 while (n--)
79 *where++ = t;
80 }
81
82 void moveAppend(T *b, T *e) noexcept
83 {
84 copyAppend(b, e);
85 }
86
87 void truncate(size_t newSize) noexcept
88 {
89 Q_ASSERT(this->isMutable());
90 Q_ASSERT(!this->isShared());
91 Q_ASSERT(newSize < size_t(this->size));
92
93 this->size = qsizetype(newSize);
94 }
95
96 void destroyAll() noexcept // Call from destructors, ONLY!
97 {
98 Q_ASSERT(this->d);
99 Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
100
101 // As this is to be called only from destructor, it doesn't need to be
102 // exception safe; size not updated.
103 }
104
105 T *createHole(QArrayData::GrowthPosition pos, qsizetype where, qsizetype n)
106 {
107 Q_ASSERT((pos == QArrayData::GrowsAtBeginning && n <= this->freeSpaceAtBegin()) ||
108 (pos == QArrayData::GrowsAtEnd && n <= this->freeSpaceAtEnd()));
109
110 T *insertionPoint = this->ptr + where;
111 if (pos == QArrayData::GrowsAtEnd) {
112 if (where < this->size)
113 ::memmove(dest: static_cast<void *>(insertionPoint + n), src: static_cast<void *>(insertionPoint), n: (this->size - where) * sizeof(T));
114 } else {
115 Q_ASSERT(where == 0);
116 this->ptr -= n;
117 insertionPoint -= n;
118 }
119 this->size += n;
120 return insertionPoint;
121 }
122
123 void insert(qsizetype i, const T *data, qsizetype n)
124 {
125 typename Data::GrowthPosition pos = Data::GrowsAtEnd;
126 if (this->size != 0 && i == 0)
127 pos = Data::GrowsAtBeginning;
128
129 DataPointer oldData;
130 this->detachAndGrow(pos, n, &data, &oldData);
131 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
132 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
133
134 T *where = createHole(pos, where: i, n);
135 ::memcpy(dest: static_cast<void *>(where), src: static_cast<const void *>(data), n: n * sizeof(T));
136 }
137
138 void insert(qsizetype i, qsizetype n, parameter_type t)
139 {
140 T copy(t);
141
142 typename Data::GrowthPosition pos = Data::GrowsAtEnd;
143 if (this->size != 0 && i == 0)
144 pos = Data::GrowsAtBeginning;
145
146 this->detachAndGrow(pos, n, nullptr, nullptr);
147 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
148 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
149
150 T *where = createHole(pos, where: i, n);
151 while (n--)
152 *where++ = copy;
153 }
154
155 template<typename... Args>
156 void emplace(qsizetype i, Args &&... args)
157 {
158 bool detach = this->needsDetach();
159 if (!detach) {
160 if (i == this->size && this->freeSpaceAtEnd()) {
161 new (this->end()) T(std::forward<Args>(args)...);
162 ++this->size;
163 return;
164 }
165 if (i == 0 && this->freeSpaceAtBegin()) {
166 new (this->begin() - 1) T(std::forward<Args>(args)...);
167 --this->ptr;
168 ++this->size;
169 return;
170 }
171 }
172 T tmp(std::forward<Args>(args)...);
173 typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd;
174 if (this->size != 0 && i == 0)
175 pos = QArrayData::GrowsAtBeginning;
176
177 this->detachAndGrow(pos, 1, nullptr, nullptr);
178
179 T *where = createHole(pos, where: i, n: 1);
180 new (where) T(std::move(tmp));
181 }
182
183 void erase(T *b, qsizetype n)
184 {
185 T *e = b + n;
186 Q_ASSERT(this->isMutable());
187 Q_ASSERT(b < e);
188 Q_ASSERT(b >= this->begin() && b < this->end());
189 Q_ASSERT(e > this->begin() && e <= this->end());
190
191 // Comply with std::vector::erase(): erased elements and all after them
192 // are invalidated. However, erasing from the beginning effectively
193 // means that all iterators are invalidated. We can use this freedom to
194 // erase by moving towards the end.
195 if (b == this->begin() && e != this->end()) {
196 this->ptr = e;
197 } else if (e != this->end()) {
198 ::memmove(dest: static_cast<void *>(b), src: static_cast<void *>(e),
199 n: (static_cast<T *>(this->end()) - e) * sizeof(T));
200 }
201 this->size -= n;
202 }
203
204 void eraseFirst() noexcept
205 {
206 Q_ASSERT(this->isMutable());
207 Q_ASSERT(this->size);
208 ++this->ptr;
209 --this->size;
210 }
211
212 void eraseLast() noexcept
213 {
214 Q_ASSERT(this->isMutable());
215 Q_ASSERT(this->size);
216 --this->size;
217 }
218
219 template <typename Predicate>
220 qsizetype eraseIf(Predicate pred)
221 {
222 qsizetype result = 0;
223 if (this->size == 0)
224 return result;
225
226 if (!this->needsDetach()) {
227 auto end = this->end();
228 auto it = std::remove_if(this->begin(), end, pred);
229 if (it != end) {
230 result = std::distance(it, end);
231 erase(b: it, n: result);
232 }
233 } else {
234 const auto begin = this->begin();
235 const auto end = this->end();
236 auto it = std::find_if(begin, end, pred);
237 if (it == end)
238 return result;
239
240 QPodArrayOps<T> other(this->size);
241 Q_CHECK_PTR(other.data());
242 auto dest = other.begin();
243 // std::uninitialized_copy will fallback to ::memcpy/memmove()
244 dest = std::uninitialized_copy(begin, it, dest);
245 dest = q_uninitialized_remove_copy_if(std::next(it), end, dest, pred);
246 other.size = std::distance(other.data(), dest);
247 result = this->size - other.size;
248 this->swap(other);
249 }
250 return result;
251 }
252
253 struct Span { T *begin; T *end; };
254
255 void copyRanges(std::initializer_list<Span> ranges)
256 {
257 auto it = this->begin();
258 std::for_each(ranges.begin(), ranges.end(), [&it](const auto &span) {
259 it = std::copy(span.begin, span.end, it);
260 });
261 this->size = std::distance(this->begin(), it);
262 }
263
264 void assign(T *b, T *e, parameter_type t) noexcept
265 {
266 Q_ASSERT(b <= e);
267 Q_ASSERT(b >= this->begin() && e <= this->end());
268
269 while (b != e)
270 ::memcpy(dest: static_cast<void *>(b++), src: static_cast<const void *>(&t), n: sizeof(T));
271 }
272
273 void reallocate(qsizetype alloc, QArrayData::AllocationOption option)
274 {
275 auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, option);
276 Q_CHECK_PTR(pair.second);
277 Q_ASSERT(pair.first != nullptr);
278 this->d = pair.first;
279 this->ptr = pair.second;
280 }
281};
282
283template <class T>
284struct QGenericArrayOps
285 : public QArrayDataPointer<T>
286{
287 static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
288
289protected:
290 typedef QTypedArrayData<T> Data;
291 using DataPointer = QArrayDataPointer<T>;
292
293public:
294 typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
295
296 void appendInitialize(qsizetype newSize)
297 {
298 Q_ASSERT(this->isMutable());
299 Q_ASSERT(!this->isShared());
300 Q_ASSERT(newSize > this->size);
301 Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd());
302
303 T *const b = this->begin();
304 do {
305 new (b + this->size) T;
306 } while (++this->size != newSize);
307 }
308
309 void copyAppend(const T *b, const T *e)
310 {
311 Q_ASSERT(this->isMutable() || b == e);
312 Q_ASSERT(!this->isShared() || b == e);
313 Q_ASSERT(b <= e);
314 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
315
316 if (b == e) // short-cut and handling the case b and e == nullptr
317 return;
318
319 T *data = this->begin();
320 while (b < e) {
321 new (data + this->size) T(*b);
322 ++b;
323 ++this->size;
324 }
325 }
326
327 void copyAppend(qsizetype n, parameter_type t)
328 {
329 Q_ASSERT(!this->isShared() || n == 0);
330 Q_ASSERT(this->freeSpaceAtEnd() >= n);
331 if (!n)
332 return;
333
334 T *data = this->begin();
335 while (n--) {
336 new (data + this->size) T(t);
337 ++this->size;
338 }
339 }
340
341 void moveAppend(T *b, T *e)
342 {
343 Q_ASSERT(this->isMutable() || b == e);
344 Q_ASSERT(!this->isShared() || b == e);
345 Q_ASSERT(b <= e);
346 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
347
348 if (b == e)
349 return;
350
351 T *data = this->begin();
352 while (b < e) {
353 new (data + this->size) T(std::move(*b));
354 ++b;
355 ++this->size;
356 }
357 }
358
359 void truncate(size_t newSize)
360 {
361 Q_ASSERT(this->isMutable());
362 Q_ASSERT(!this->isShared());
363 Q_ASSERT(newSize < size_t(this->size));
364
365 std::destroy(this->begin() + newSize, this->end());
366 this->size = newSize;
367 }
368
369 void destroyAll() // Call from destructors, ONLY
370 {
371 Q_ASSERT(this->d);
372 // As this is to be called only from destructor, it doesn't need to be
373 // exception safe; size not updated.
374
375 Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
376
377 std::destroy(this->begin(), this->end());
378 }
379
380 struct Inserter
381 {
382 QArrayDataPointer<T> *data;
383 T *begin;
384 qsizetype size;
385
386 qsizetype sourceCopyConstruct = 0, nSource = 0, move = 0, sourceCopyAssign = 0;
387 T *end = nullptr, *last = nullptr, *where = nullptr;
388
389 Inserter(QArrayDataPointer<T> *d) : data(d)
390 {
391 begin = d->ptr;
392 size = d->size;
393 }
394 ~Inserter() {
395 data->ptr = begin;
396 data->size = size;
397 }
398 Q_DISABLE_COPY(Inserter)
399
400 void setup(qsizetype pos, qsizetype n)
401 {
402 end = begin + size;
403 last = end - 1;
404 where = begin + pos;
405 qsizetype dist = size - pos;
406 sourceCopyConstruct = 0;
407 nSource = n;
408 move = n - dist; // smaller 0
409 sourceCopyAssign = n;
410 if (n > dist) {
411 sourceCopyConstruct = n - dist;
412 move = 0;
413 sourceCopyAssign -= sourceCopyConstruct;
414 }
415 }
416
417 void insert(qsizetype pos, const T *source, qsizetype n)
418 {
419 qsizetype oldSize = size;
420 Q_UNUSED(oldSize);
421
422 setup(pos, n);
423
424 // first create new elements at the end, by copying from elements
425 // to be inserted (if they extend past the current end of the array)
426 for (qsizetype i = 0; i != sourceCopyConstruct; ++i) {
427 new (end + i) T(source[nSource - sourceCopyConstruct + i]);
428 ++size;
429 }
430 Q_ASSERT(size <= oldSize + n);
431
432 // now move construct new elements at the end from existing elements inside
433 // the array.
434 for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) {
435 new (end + i) T(std::move(*(end + i - nSource)));
436 ++size;
437 }
438 // array has the new size now!
439 Q_ASSERT(size == oldSize + n);
440
441 // now move assign existing elements towards the end
442 for (qsizetype i = 0; i != move; --i)
443 last[i] = std::move(last[i - nSource]);
444
445 // finally copy the remaining elements from source over
446 for (qsizetype i = 0; i != sourceCopyAssign; ++i)
447 where[i] = source[i];
448 }
449
450 void insert(qsizetype pos, const T &t, qsizetype n)
451 {
452 const qsizetype oldSize = size;
453 Q_UNUSED(oldSize);
454
455 setup(pos, n);
456
457 // first create new elements at the end, by copying from elements
458 // to be inserted (if they extend past the current end of the array)
459 for (qsizetype i = 0; i != sourceCopyConstruct; ++i) {
460 new (end + i) T(t);
461 ++size;
462 }
463 Q_ASSERT(size <= oldSize + n);
464
465 // now move construct new elements at the end from existing elements inside
466 // the array.
467 for (qsizetype i = sourceCopyConstruct; i != nSource; ++i) {
468 new (end + i) T(std::move(*(end + i - nSource)));
469 ++size;
470 }
471 // array has the new size now!
472 Q_ASSERT(size == oldSize + n);
473
474 // now move assign existing elements towards the end
475 for (qsizetype i = 0; i != move; --i)
476 last[i] = std::move(last[i - nSource]);
477
478 // finally copy the remaining elements from source over
479 for (qsizetype i = 0; i != sourceCopyAssign; ++i)
480 where[i] = t;
481 }
482
483 void insertOne(qsizetype pos, T &&t)
484 {
485 setup(pos, n: 1);
486
487 if (sourceCopyConstruct) {
488 Q_ASSERT(sourceCopyConstruct == 1);
489 new (end) T(std::move(t));
490 ++size;
491 } else {
492 // create a new element at the end by move constructing one existing element
493 // inside the array.
494 new (end) T(std::move(*(end - 1)));
495 ++size;
496
497 // now move assign existing elements towards the end
498 for (qsizetype i = 0; i != move; --i)
499 last[i] = std::move(last[i - 1]);
500
501 // and move the new item into place
502 *where = std::move(t);
503 }
504 }
505 };
506
507 void insert(qsizetype i, const T *data, qsizetype n)
508 {
509 const bool growsAtBegin = this->size != 0 && i == 0;
510 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
511
512 DataPointer oldData;
513 this->detachAndGrow(pos, n, &data, &oldData);
514 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
515 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
516
517 if (growsAtBegin) {
518 // copy construct items in reverse order at the begin
519 Q_ASSERT(this->freeSpaceAtBegin() >= n);
520 while (n) {
521 --n;
522 new (this->begin() - 1) T(data[n]);
523 --this->ptr;
524 ++this->size;
525 }
526 } else {
527 Inserter(this).insert(i, data, n);
528 }
529 }
530
531 void insert(qsizetype i, qsizetype n, parameter_type t)
532 {
533 T copy(t);
534
535 const bool growsAtBegin = this->size != 0 && i == 0;
536 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
537
538 this->detachAndGrow(pos, n, nullptr, nullptr);
539 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
540 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
541
542 if (growsAtBegin) {
543 // copy construct items in reverse order at the begin
544 Q_ASSERT(this->freeSpaceAtBegin() >= n);
545 while (n--) {
546 new (this->begin() - 1) T(copy);
547 --this->ptr;
548 ++this->size;
549 }
550 } else {
551 Inserter(this).insert(i, copy, n);
552 }
553 }
554
555 template<typename... Args>
556 void emplace(qsizetype i, Args &&... args)
557 {
558 bool detach = this->needsDetach();
559 if (!detach) {
560 if (i == this->size && this->freeSpaceAtEnd()) {
561 new (this->end()) T(std::forward<Args>(args)...);
562 ++this->size;
563 return;
564 }
565 if (i == 0 && this->freeSpaceAtBegin()) {
566 new (this->begin() - 1) T(std::forward<Args>(args)...);
567 --this->ptr;
568 ++this->size;
569 return;
570 }
571 }
572 T tmp(std::forward<Args>(args)...);
573 const bool growsAtBegin = this->size != 0 && i == 0;
574 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
575
576 this->detachAndGrow(pos, 1, nullptr, nullptr);
577
578 if (growsAtBegin) {
579 Q_ASSERT(this->freeSpaceAtBegin());
580 new (this->begin() - 1) T(std::move(tmp));
581 --this->ptr;
582 ++this->size;
583 } else {
584 Inserter(this).insertOne(i, std::move(tmp));
585 }
586 }
587
588 void erase(T *b, qsizetype n)
589 {
590 T *e = b + n;
591 Q_ASSERT(this->isMutable());
592 Q_ASSERT(b < e);
593 Q_ASSERT(b >= this->begin() && b < this->end());
594 Q_ASSERT(e > this->begin() && e <= this->end());
595
596 // Comply with std::vector::erase(): erased elements and all after them
597 // are invalidated. However, erasing from the beginning effectively
598 // means that all iterators are invalidated. We can use this freedom to
599 // erase by moving towards the end.
600 if (b == this->begin() && e != this->end()) {
601 this->ptr = e;
602 } else {
603 const T *const end = this->end();
604
605 // move (by assignment) the elements from e to end
606 // onto b to the new end
607 while (e != end) {
608 *b = std::move(*e);
609 ++b;
610 ++e;
611 }
612 }
613 this->size -= n;
614 std::destroy(b, e);
615 }
616
617 void eraseFirst() noexcept
618 {
619 Q_ASSERT(this->isMutable());
620 Q_ASSERT(this->size);
621 this->begin()->~T();
622 ++this->ptr;
623 --this->size;
624 }
625
626 void eraseLast() noexcept
627 {
628 Q_ASSERT(this->isMutable());
629 Q_ASSERT(this->size);
630 (this->end() - 1)->~T();
631 --this->size;
632 }
633
634
635 void assign(T *b, T *e, parameter_type t)
636 {
637 Q_ASSERT(b <= e);
638 Q_ASSERT(b >= this->begin() && e <= this->end());
639
640 while (b != e)
641 *b++ = t;
642 }
643};
644
645template <class T>
646struct QMovableArrayOps
647 : QGenericArrayOps<T>
648{
649 static_assert (std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
650
651protected:
652 typedef QTypedArrayData<T> Data;
653 using DataPointer = QArrayDataPointer<T>;
654
655public:
656 // using QGenericArrayOps<T>::copyAppend;
657 // using QGenericArrayOps<T>::moveAppend;
658 // using QGenericArrayOps<T>::truncate;
659 // using QGenericArrayOps<T>::destroyAll;
660 typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
661
662 struct Inserter
663 {
664 QArrayDataPointer<T> *data;
665 T *displaceFrom;
666 T *displaceTo;
667 qsizetype nInserts = 0;
668 qsizetype bytes;
669
670 Inserter(QArrayDataPointer<T> *d) : data(d) { }
671 ~Inserter() {
672 if constexpr (!std::is_nothrow_copy_constructible_v<T>) {
673 if (displaceFrom != displaceTo) {
674 ::memmove(dest: static_cast<void *>(displaceFrom), src: static_cast<void *>(displaceTo), n: bytes);
675 nInserts -= qAbs(displaceFrom - displaceTo);
676 }
677 }
678 data->size += nInserts;
679 }
680 Q_DISABLE_COPY(Inserter)
681
682 T *displace(qsizetype pos, qsizetype n)
683 {
684 nInserts = n;
685 T *insertionPoint = data->ptr + pos;
686 displaceFrom = data->ptr + pos;
687 displaceTo = displaceFrom + n;
688 bytes = data->size - pos;
689 bytes *= sizeof(T);
690 ::memmove(dest: static_cast<void *>(displaceTo), src: static_cast<void *>(displaceFrom), n: bytes);
691 return insertionPoint;
692 }
693
694 void insert(qsizetype pos, const T *source, qsizetype n)
695 {
696 T *where = displace(pos, n);
697
698 while (n--) {
699 new (where) T(*source);
700 ++where;
701 ++source;
702 ++displaceFrom;
703 }
704 }
705
706 void insert(qsizetype pos, const T &t, qsizetype n)
707 {
708 T *where = displace(pos, n);
709
710 while (n--) {
711 new (where) T(t);
712 ++where;
713 ++displaceFrom;
714 }
715 }
716
717 void insertOne(qsizetype pos, T &&t)
718 {
719 T *where = displace(pos, n: 1);
720 new (where) T(std::move(t));
721 ++displaceFrom;
722 Q_ASSERT(displaceFrom == displaceTo);
723 }
724
725 };
726
727
728 void insert(qsizetype i, const T *data, qsizetype n)
729 {
730 const bool growsAtBegin = this->size != 0 && i == 0;
731 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
732
733 DataPointer oldData;
734 this->detachAndGrow(pos, n, &data, &oldData);
735 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
736 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
737
738 if (growsAtBegin) {
739 // copy construct items in reverse order at the begin
740 Q_ASSERT(this->freeSpaceAtBegin() >= n);
741 while (n) {
742 --n;
743 new (this->begin() - 1) T(data[n]);
744 --this->ptr;
745 ++this->size;
746 }
747 } else {
748 Inserter(this).insert(i, data, n);
749 }
750 }
751
752 void insert(qsizetype i, qsizetype n, parameter_type t)
753 {
754 T copy(t);
755
756 const bool growsAtBegin = this->size != 0 && i == 0;
757 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
758
759 this->detachAndGrow(pos, n, nullptr, nullptr);
760 Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
761 (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
762
763 if (growsAtBegin) {
764 // copy construct items in reverse order at the begin
765 Q_ASSERT(this->freeSpaceAtBegin() >= n);
766 while (n--) {
767 new (this->begin() - 1) T(copy);
768 --this->ptr;
769 ++this->size;
770 }
771 } else {
772 Inserter(this).insert(i, copy, n);
773 }
774 }
775
776 template<typename... Args>
777 void emplace(qsizetype i, Args &&... args)
778 {
779 bool detach = this->needsDetach();
780 if (!detach) {
781 if (i == this->size && this->freeSpaceAtEnd()) {
782 new (this->end()) T(std::forward<Args>(args)...);
783 ++this->size;
784 return;
785 }
786 if (i == 0 && this->freeSpaceAtBegin()) {
787 new (this->begin() - 1) T(std::forward<Args>(args)...);
788 --this->ptr;
789 ++this->size;
790 return;
791 }
792 }
793 T tmp(std::forward<Args>(args)...);
794 const bool growsAtBegin = this->size != 0 && i == 0;
795 const auto pos = growsAtBegin ? Data::GrowsAtBeginning : Data::GrowsAtEnd;
796
797 this->detachAndGrow(pos, 1, nullptr, nullptr);
798 if (growsAtBegin) {
799 Q_ASSERT(this->freeSpaceAtBegin());
800 new (this->begin() - 1) T(std::move(tmp));
801 --this->ptr;
802 ++this->size;
803 } else {
804 Inserter(this).insertOne(i, std::move(tmp));
805 }
806 }
807
808 void erase(T *b, qsizetype n)
809 {
810 T *e = b + n;
811
812 Q_ASSERT(this->isMutable());
813 Q_ASSERT(b < e);
814 Q_ASSERT(b >= this->begin() && b < this->end());
815 Q_ASSERT(e > this->begin() && e <= this->end());
816
817 // Comply with std::vector::erase(): erased elements and all after them
818 // are invalidated. However, erasing from the beginning effectively
819 // means that all iterators are invalidated. We can use this freedom to
820 // erase by moving towards the end.
821
822 std::destroy(b, e);
823 if (b == this->begin() && e != this->end()) {
824 this->ptr = e;
825 } else if (e != this->end()) {
826 memmove(static_cast<void *>(b), static_cast<const void *>(e), (static_cast<const T *>(this->end()) - e)*sizeof(T));
827 }
828 this->size -= n;
829 }
830
831 void reallocate(qsizetype alloc, QArrayData::AllocationOption option)
832 {
833 auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, option);
834 Q_CHECK_PTR(pair.second);
835 Q_ASSERT(pair.first != nullptr);
836 this->d = pair.first;
837 this->ptr = pair.second;
838 }
839};
840
841template <class T, class = void>
842struct QArrayOpsSelector
843{
844 typedef QGenericArrayOps<T> Type;
845};
846
847template <class T>
848struct QArrayOpsSelector<T,
849 typename std::enable_if<
850 !QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
851 >::type>
852{
853 typedef QPodArrayOps<T> Type;
854};
855
856template <class T>
857struct QArrayOpsSelector<T,
858 typename std::enable_if<
859 QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
860 >::type>
861{
862 typedef QMovableArrayOps<T> Type;
863};
864
865template <class T>
866struct QCommonArrayOps : QArrayOpsSelector<T>::Type
867{
868 using Base = typename QArrayOpsSelector<T>::Type;
869 using Data = QTypedArrayData<T>;
870 using DataPointer = QArrayDataPointer<T>;
871 using parameter_type = typename Base::parameter_type;
872
873protected:
874 using Self = QCommonArrayOps<T>;
875
876public:
877 // using Base::truncate;
878 // using Base::destroyAll;
879 // using Base::assign;
880
881 template<typename It>
882 void appendIteratorRange(It b, It e, QtPrivate::IfIsForwardIterator<It> = true)
883 {
884 Q_ASSERT(this->isMutable() || b == e);
885 Q_ASSERT(!this->isShared() || b == e);
886 const qsizetype distance = std::distance(b, e);
887 Q_ASSERT(distance >= 0 && distance <= this->allocatedCapacity() - this->size);
888 Q_UNUSED(distance);
889
890#if __cplusplus >= 202002L && defined(__cpp_concepts) && defined(__cpp_lib_concepts)
891 constexpr bool canUseCopyAppend =
892 std::contiguous_iterator<It> &&
893 std::is_same_v<
894 std::remove_cv_t<typename std::iterator_traits<It>::value_type>,
895 T
896 >;
897 if constexpr (canUseCopyAppend) {
898 this->copyAppend(std::to_address(b), std::to_address(e));
899 } else
900#endif
901 {
902 T *iter = this->end();
903 for (; b != e; ++iter, ++b) {
904 new (iter) T(*b);
905 ++this->size;
906 }
907 }
908 }
909
910 // slightly higher level API than copyAppend() that also preallocates space
911 void growAppend(const T *b, const T *e)
912 {
913 if (b == e)
914 return;
915 Q_ASSERT(b < e);
916 const qsizetype n = e - b;
917 DataPointer old;
918
919 // points into range:
920 if (QtPrivate::q_points_into_range(b, *this))
921 this->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old);
922 else
923 this->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr);
924 Q_ASSERT(this->freeSpaceAtEnd() >= n);
925 // b might be updated so use [b, n)
926 this->copyAppend(b, b + n);
927 }
928
929 void appendUninitialized(qsizetype newSize)
930 {
931 Q_ASSERT(this->isMutable());
932 Q_ASSERT(!this->isShared());
933 Q_ASSERT(newSize > this->size);
934 Q_ASSERT(newSize - this->size <= this->freeSpaceAtEnd());
935
936
937 T *const b = this->begin() + this->size;
938 T *const e = this->begin() + newSize;
939 if constexpr (std::is_constructible_v<T, Qt::Initialization>)
940 std::uninitialized_fill(b, e, Qt::Uninitialized);
941 else
942 std::uninitialized_default_construct(b, e);
943 this->size = newSize;
944 }
945};
946
947} // namespace QtPrivate
948
949template <class T>
950struct QArrayDataOps
951 : QtPrivate::QCommonArrayOps<T>
952{
953};
954
955QT_END_NAMESPACE
956
957#endif // include guard
958

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