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