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
61/*!
62 \internal
63
64 This class provides basic building blocks to do reversible operations. This
65 in turn allows to reason about exception safety under certain conditions.
66
67 This class is not part of the Qt API. It exists for the convenience of other
68 Qt classes. This class may change from version to version without notice,
69 or even be removed.
70
71 We mean it.
72 */
73template<typename T>
74struct QArrayExceptionSafetyPrimitives
75{
76 using parameter_type = typename QArrayDataPointer<T>::parameter_type;
77 using iterator = typename QArrayDataPointer<T>::iterator;
78
79 // Constructs a range of elements at the specified position. If an exception
80 // is thrown during construction, already constructed elements are
81 // destroyed. By design, only one function (create/copy/clone/move) and only
82 // once is supposed to be called per class instance.
83 struct Constructor
84 {
85 T *const where;
86 size_t n = 0;
87
88 template<typename It>
89 using iterator_copy_value = decltype(*std::declval<It>());
90 template<typename It>
91 using iterator_move_value = decltype(std::move(*std::declval<It>()));
92
93 Constructor(T *w) noexcept : where(w) {}
94 qsizetype create(size_t size) noexcept(std::is_nothrow_default_constructible_v<T>)
95 {
96 n = 0;
97 while (n != size) {
98 new (where + n) T;
99 ++n;
100 }
101 return qsizetype(std::exchange(n, 0));
102 }
103 template<typename ForwardIt>
104 qsizetype copy(ForwardIt first, ForwardIt last)
105 noexcept(std::is_nothrow_constructible_v<T, iterator_copy_value<ForwardIt>>)
106 {
107 n = 0;
108 for (; first != last; ++first) {
109 new (where + n) T(*first);
110 ++n;
111 }
112 return qsizetype(std::exchange(n, 0));
113 }
114 qsizetype clone(size_t size, parameter_type t)
115 noexcept(std::is_nothrow_constructible_v<T, parameter_type>)
116 {
117 n = 0;
118 while (n != size) {
119 new (where + n) T(t);
120 ++n;
121 }
122 return qsizetype(std::exchange(n, 0));
123 }
124 template<typename ForwardIt>
125 qsizetype move(ForwardIt first, ForwardIt last)
126 noexcept(std::is_nothrow_constructible_v<T, iterator_move_value<ForwardIt>>)
127 {
128 n = 0;
129 for (; first != last; ++first) {
130 new (where + n) T(std::move(*first));
131 ++n;
132 }
133 return qsizetype(std::exchange(n, 0));
134 }
135 ~Constructor() noexcept(std::is_nothrow_destructible_v<T>)
136 {
137 while (n)
138 where[--n].~T();
139 }
140 };
141
142 // Watches passed iterator. Unless commit() is called, all the elements that
143 // the watched iterator passes through are deleted at the end of object
144 // lifetime.
145 //
146 // Requirements: when not at starting position, the iterator is expected to
147 // point to a valid object (to initialized memory)
148 template<typename It = iterator>
149 struct Destructor
150 {
151 It *iter;
152 It end;
153 It intermediate;
154
155 Destructor(It &it) noexcept(std::is_nothrow_copy_constructible_v<It>)
156 : iter(std::addressof(it)), end(it)
157 { }
158 void commit() noexcept
159 {
160 iter = std::addressof(end);
161 }
162 void freeze() noexcept(std::is_nothrow_copy_constructible_v<It>)
163 {
164 intermediate = *iter; iter = std::addressof(intermediate);
165 }
166 ~Destructor() noexcept(std::is_nothrow_destructible_v<T>)
167 {
168 // Step is either 1 or -1 and depends on the interposition of *iter
169 // and end. Note that *iter is expected to point to a valid object
170 // (see the logic below).
171 for (const int step = *iter < end ? 1 : -1; *iter != end; std::advance(*iter, step))
172 (*iter)->~T();
173 }
174 };
175
176 // Moves the data range in memory by the specified amount. Unless commit()
177 // is called, the data is moved back to the original place at the end of
178 // object lifetime.
179 struct Displacer
180 {
181 T *const begin;
182 T *const end;
183 qsizetype displace;
184
185 static_assert(QTypeInfo<T>::isRelocatable, "Type must be relocatable");
186
187 Displacer(T *start, T *finish, qsizetype diff) noexcept
188 : begin(start), end(finish), displace(diff)
189 {
190 ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
191 (end - begin) * sizeof(T));
192 }
193 void commit() noexcept { displace = 0; }
194 ~Displacer() noexcept
195 {
196 if (displace)
197 ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
198 (end - begin) * sizeof(T));
199 }
200 };
201
202 // Watches passed iterator. Moves the data range (defined as a start
203 // iterator and a length) to the new starting position at the end of object
204 // lifetime.
205 struct Mover
206 {
207 T *&destination;
208 const T *const source;
209 size_t n;
210 qsizetype &size;
211
212 static_assert(QTypeInfo<T>::isRelocatable, "Type must be relocatable");
213
214 Mover(T *&start, size_t length, qsizetype &sz) noexcept
215 : destination(start), source(start), n(length), size(sz)
216 { }
217 ~Mover() noexcept
218 {
219 ::memmove(static_cast<void *>(destination), static_cast<const void *>(source),
220 n * sizeof(T));
221 size -= source > destination ? source - destination : destination - source;
222 }
223 };
224};
225
226// Tags for compile-time dispatch based on backwards vs forward growing policy
227struct GrowsForwardTag {};
228struct GrowsBackwardsTag {};
229template<typename> struct InverseTag;
230template<> struct InverseTag<GrowsForwardTag> { using tag = GrowsBackwardsTag; };
231template<> struct InverseTag<GrowsBackwardsTag> { using tag = GrowsForwardTag; };
232
233QT_WARNING_PUSH
234#if defined(Q_CC_GNU) && Q_CC_GNU >= 700
235QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
236#endif
237
238template <class T>
239struct QPodArrayOps
240 : public QArrayDataPointer<T>
241{
242protected:
243 typedef QTypedArrayData<T> Data;
244
245 template <typename ...Args>
246 void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); }
247
248public:
249 typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
250
251 void appendInitialize(size_t newSize)
252 {
253 Q_ASSERT(this->isMutable());
254 Q_ASSERT(!this->isShared());
255 Q_ASSERT(newSize > size_t(this->size));
256 Q_ASSERT(newSize - this->size <= size_t(this->freeSpaceAtEnd()));
257
258 ::memset(static_cast<void *>(this->end()), 0, (newSize - this->size) * sizeof(T));
259 this->size = qsizetype(newSize);
260 }
261
262 void moveAppend(T *b, T *e)
263 { insert(this->end(), b, e); }
264
265 void truncate(size_t newSize)
266 {
267 Q_ASSERT(this->isMutable());
268 Q_ASSERT(!this->isShared());
269 Q_ASSERT(newSize < size_t(this->size));
270
271 this->size = qsizetype(newSize);
272 }
273
274 void destroyAll() // Call from destructors, ONLY!
275 {
276 Q_ASSERT(this->d);
277 Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
278
279 // As this is to be called only from destructor, it doesn't need to be
280 // exception safe; size not updated.
281 }
282
283 void insert(T *where, const T *b, const T *e)
284 { insert(GrowsForwardTag{}, where, b, e); }
285
286 void insert(GrowsForwardTag, T *where, const T *b, const T *e)
287 {
288 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
289 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
290 Q_ASSERT(where >= this->begin() && where <= this->end());
291 Q_ASSERT(b <= e);
292 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
293 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
294
295 ::memmove(static_cast<void *>(where + (e - b)), static_cast<void *>(where),
296 (static_cast<const T*>(this->end()) - where) * sizeof(T));
297 ::memcpy(static_cast<void *>(where), static_cast<const void *>(b), (e - b) * sizeof(T));
298 this->size += (e - b);
299 }
300
301 void insert(GrowsBackwardsTag, T *where, const T *b, const T *e)
302 {
303 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
304 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
305 Q_ASSERT(where >= this->begin() && where <= this->end());
306 Q_ASSERT(b <= e);
307 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
308 Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
309
310 auto oldBegin = this->begin();
311 this->ptr -= (e - b);
312 ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
313 (where - static_cast<const T*>(oldBegin)) * sizeof(T));
314 ::memcpy(static_cast<void *>(where - (e - b)), static_cast<const void *>(b),
315 (e - b) * sizeof(T));
316 this->size += (e - b);
317 }
318
319 void insert(T *where, size_t n, parameter_type t)
320 { insert(GrowsForwardTag{}, where, n, t); }
321
322 void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
323 {
324 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
325 Q_ASSERT(where >= this->begin() && where <= this->end());
326 Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
327
328 ::memmove(static_cast<void *>(where + n), static_cast<void *>(where),
329 (static_cast<const T*>(this->end()) - where) * sizeof(T));
330 this->size += qsizetype(n); // PODs can't throw on copy
331 while (n--)
332 *where++ = t;
333 }
334
335 void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
336 {
337 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
338 Q_ASSERT(where >= this->begin() && where <= this->end());
339 Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
340
341 auto oldBegin = this->begin();
342 this->ptr -= n;
343 ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
344 (where - static_cast<const T*>(oldBegin)) * sizeof(T));
345 this->size += qsizetype(n); // PODs can't throw on copy
346 where -= n;
347 while (n--)
348 *where++ = t;
349 }
350
351
352 template <typename ...Args>
353 void emplace(T *where, Args&&... args)
354 { emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...); }
355
356 template <typename ...Args>
357 void emplace(GrowsForwardTag, T *where, Args&&... args)
358 {
359 Q_ASSERT(!this->isShared());
360 Q_ASSERT(where >= this->begin() && where <= this->end());
361 Q_ASSERT(this->freeSpaceAtEnd() >= 1);
362
363 if (where == this->end()) {
364 new (this->end()) T(std::forward<Args>(args)...);
365 } else {
366 // Preserve the value, because it might be a reference to some part of the moved chunk
367 T t(std::forward<Args>(args)...);
368
369 ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where),
370 (static_cast<const T*>(this->end()) - where) * sizeof(T));
371 *where = t;
372 }
373
374 ++this->size;
375 }
376
377 template <typename ...Args>
378 void emplace(GrowsBackwardsTag, T *where, Args&&... args)
379 {
380 Q_ASSERT(!this->isShared());
381 Q_ASSERT(where >= this->begin() && where <= this->end());
382 Q_ASSERT(this->freeSpaceAtBegin() >= 1);
383
384 if (where == this->begin()) {
385 new (this->begin() - 1) T(std::forward<Args>(args)...);
386 --this->ptr;
387 } else {
388 // Preserve the value, because it might be a reference to some part of the moved chunk
389 T t(std::forward<Args>(args)...);
390
391 auto oldBegin = this->begin();
392 --this->ptr;
393 ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
394 (where - oldBegin) * sizeof(T));
395 *(where - 1) = t;
396 }
397
398 ++this->size;
399 }
400
401 void erase(T *b, T *e)
402 { erase(GrowsForwardTag{}, b, e); }
403
404 void erase(GrowsForwardTag, T *b, T *e)
405 {
406 Q_ASSERT(this->isMutable());
407 Q_ASSERT(b < e);
408 Q_ASSERT(b >= this->begin() && b < this->end());
409 Q_ASSERT(e > this->begin() && e <= this->end());
410
411 ::memmove(static_cast<void *>(b), static_cast<void *>(e),
412 (static_cast<T *>(this->end()) - e) * sizeof(T));
413 this->size -= (e - b);
414 }
415
416 void erase(GrowsBackwardsTag, T *b, T *e)
417 {
418 Q_ASSERT(this->isMutable());
419 Q_ASSERT(b < e);
420 Q_ASSERT(b >= this->begin() && b < this->end());
421 Q_ASSERT(e > this->begin() && e <= this->end());
422
423 const auto oldBegin = this->begin();
424 this->ptr += (e - b);
425 ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
426 (b - static_cast<T *>(oldBegin)) * sizeof(T));
427 this->size -= (e - b);
428 }
429
430 void assign(T *b, T *e, parameter_type t)
431 {
432 Q_ASSERT(b <= e);
433 Q_ASSERT(b >= this->begin() && e <= this->end());
434
435 while (b != e)
436 ::memcpy(static_cast<void *>(b++), static_cast<const void *>(&t), sizeof(T));
437 }
438
439 bool compare(const T *begin1, const T *begin2, size_t n) const
440 {
441 // only use memcmp for fundamental types or pointers.
442 // Other types could have padding in the data structure or custom comparison
443 // operators that would break the comparison using memcmp
444 if constexpr (QArrayDataPointer<T>::pass_parameter_by_value) {
445 return ::memcmp(begin1, begin2, n * sizeof(T)) == 0;
446 } else {
447 const T *end1 = begin1 + n;
448 while (begin1 != end1) {
449 if (*begin1 == *begin2) {
450 ++begin1;
451 ++begin2;
452 } else {
453 return false;
454 }
455 }
456 return true;
457 }
458 }
459
460 void reallocate(qsizetype alloc, typename Data::ArrayOptions options)
461 {
462 // when reallocating, take care of the situation when no growth is
463 // happening - need to move the data in this case, unfortunately
464 const bool grows = options & (Data::GrowsForward | Data::GrowsBackwards);
465
466 // ### optimize me: there may be cases when moving is not obligatory
467 if (const auto gap = this->freeSpaceAtBegin(); this->d && !grows && gap) {
468 auto oldBegin = this->begin();
469 this->ptr -= gap;
470 ::memmove(static_cast<void *>(this->begin()), static_cast<void *>(oldBegin),
471 this->size * sizeof(T));
472 }
473
474 auto pair = Data::reallocateUnaligned(this->d, this->ptr, alloc, options);
475 this->d = pair.first;
476 this->ptr = pair.second;
477 }
478};
479QT_WARNING_POP
480
481template <class T>
482struct QGenericArrayOps
483 : public QArrayDataPointer<T>
484{
485protected:
486 typedef QTypedArrayData<T> Data;
487
488 template <typename ...Args>
489 void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); }
490
491public:
492 typedef typename QArrayDataPointer<T>::parameter_type parameter_type;
493
494 void appendInitialize(size_t newSize)
495 {
496 Q_ASSERT(this->isMutable());
497 Q_ASSERT(!this->isShared());
498 Q_ASSERT(newSize > size_t(this->size));
499 Q_ASSERT(newSize - this->size <= size_t(this->freeSpaceAtEnd()));
500
501 T *const b = this->begin();
502 do {
503 new (b + this->size) T;
504 } while (size_t(++this->size) != newSize);
505 }
506
507 void moveAppend(T *b, T *e)
508 {
509 Q_ASSERT(this->isMutable() || b == e);
510 Q_ASSERT(!this->isShared() || b == e);
511 Q_ASSERT(b <= e);
512 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
513
514 typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
515
516 // Provides strong exception safety guarantee,
517 // provided T::~T() nothrow
518
519 CopyConstructor copier(this->end());
520 this->size += copier.move(b, e);
521 }
522
523 void truncate(size_t newSize)
524 {
525 Q_ASSERT(this->isMutable());
526 Q_ASSERT(!this->isShared());
527 Q_ASSERT(newSize < size_t(this->size));
528
529 const T *const b = this->begin();
530 do {
531 (b + --this->size)->~T();
532 } while (size_t(this->size) != newSize);
533 }
534
535 void destroyAll() // Call from destructors, ONLY
536 {
537 Q_ASSERT(this->d);
538 // As this is to be called only from destructor, it doesn't need to be
539 // exception safe; size not updated.
540
541 Q_ASSERT(this->d->ref_.loadRelaxed() == 0);
542
543 const T *const b = this->begin();
544 const T *i = this->end();
545
546 while (i != b)
547 (--i)->~T();
548 }
549
550 void insert(T *where, const T *b, const T *e)
551 { insert(GrowsForwardTag{}, where, b, e); }
552
553 void insert(GrowsForwardTag, T *where, const T *b, const T *e)
554 {
555 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
556 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
557 Q_ASSERT(where >= this->begin() && where <= this->end());
558 Q_ASSERT(b <= e);
559 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
560 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
561
562 typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
563
564 // Array may be truncated at where in case of exceptions
565
566 T *const end = this->end();
567 const T *readIter = end;
568 T *writeIter = end + (e - b);
569
570 const T *const step1End = where + qMax(e - b, end - where);
571
572 Destructor destroyer(writeIter);
573
574 // Construct new elements in array
575 while (writeIter != step1End) {
576 --readIter;
577 // If exception happens on construction, we should not call ~T()
578 new (writeIter - 1) T(*readIter);
579 --writeIter;
580 }
581
582 while (writeIter != end) {
583 --e;
584 // If exception happens on construction, we should not call ~T()
585 new (writeIter - 1) T(*e);
586 --writeIter;
587 }
588
589 destroyer.commit();
590 this->size += destroyer.end - end;
591
592 // Copy assign over existing elements
593 while (readIter != where) {
594 --readIter;
595 --writeIter;
596 *writeIter = *readIter;
597 }
598
599 while (writeIter != where) {
600 --e;
601 --writeIter;
602 *writeIter = *e;
603 }
604 }
605
606 void insert(GrowsBackwardsTag, T *where, const T *b, const T *e)
607 {
608 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
609 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
610 Q_ASSERT(where >= this->begin() && where <= this->end());
611 Q_ASSERT(b <= e);
612 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
613 Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
614
615 typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
616
617 T *const begin = this->begin();
618 const T *readIter = begin;
619 T *writeIter = begin - (e - b);
620
621 const T *const step1End = where - qMax(e - b, where - begin);
622
623 Destructor destroyer(writeIter);
624
625 // Construct new elements in array
626 while (writeIter != step1End) {
627 new (writeIter) T(*readIter);
628 ++readIter;
629 ++writeIter;
630 }
631
632 while (writeIter != begin) {
633 new (writeIter) T(*b);
634 ++b;
635 ++writeIter;
636 }
637
638 destroyer.commit();
639 this->size += begin - destroyer.end;
640 this->ptr -= begin - destroyer.end;
641
642 // Copy assign over existing elements
643 while (readIter != where) {
644 *writeIter = *readIter;
645 ++readIter;
646 ++writeIter;
647 }
648
649 while (writeIter != where) {
650 *writeIter = *b;
651 ++b;
652 ++writeIter;
653 }
654 }
655
656 void insert(T *where, size_t n, parameter_type t)
657 { insert(GrowsForwardTag{}, where, n, t); }
658
659 void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
660 {
661 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
662 Q_ASSERT(where >= this->begin() && where <= this->end());
663 Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
664
665 typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
666
667 // Array may be truncated at where in case of exceptions
668 T *const end = this->end();
669 const T *readIter = end;
670 T *writeIter = end + n;
671
672 const T *const step1End = where + qMax<size_t>(n, end - where);
673
674 Destructor destroyer(writeIter);
675
676 // Construct new elements in array
677 while (writeIter != step1End) {
678 --readIter;
679 // If exception happens on construction, we should not call ~T()
680 new (writeIter - 1) T(*readIter);
681 --writeIter;
682 }
683
684 while (writeIter != end) {
685 --n;
686 // If exception happens on construction, we should not call ~T()
687 new (writeIter - 1) T(t);
688 --writeIter;
689 }
690
691 destroyer.commit();
692 this->size += destroyer.end - end;
693
694 // Copy assign over existing elements
695 while (readIter != where) {
696 --readIter;
697 --writeIter;
698 *writeIter = *readIter;
699 }
700
701 while (writeIter != where) {
702 --n;
703 --writeIter;
704 *writeIter = t;
705 }
706 }
707
708 void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
709 {
710 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
711 Q_ASSERT(where >= this->begin() && where <= this->end());
712 Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
713
714 typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
715
716 T *const begin = this->begin();
717 const T *readIter = begin;
718 T *writeIter = begin - n;
719
720 const T *const step1End = where - qMax<size_t>(n, where - begin);
721
722 Destructor destroyer(writeIter);
723
724 // Construct new elements in array
725 while (writeIter != step1End) {
726 new (writeIter) T(*readIter);
727 ++readIter;
728 ++writeIter;
729 }
730
731 while (writeIter != begin) {
732 new (writeIter) T(t);
733 ++writeIter;
734 }
735
736 destroyer.commit();
737 this->size += begin - destroyer.end;
738 this->ptr -= begin - destroyer.end;
739
740 // Copy assign over existing elements
741 while (readIter != where) {
742 *writeIter = *readIter;
743 ++readIter;
744 ++writeIter;
745 }
746
747 while (writeIter != where) {
748 *writeIter = t;
749 ++writeIter;
750 }
751 }
752
753
754 template <typename iterator, typename ...Args>
755 void emplace(iterator where, Args&&... args)
756 { emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...); }
757
758 template <typename iterator, typename ...Args>
759 void emplace(GrowsForwardTag, iterator where, Args&&... args)
760 {
761 Q_ASSERT(!this->isShared());
762 Q_ASSERT(where >= this->begin() && where <= this->end());
763 Q_ASSERT(this->freeSpaceAtEnd() >= 1);
764
765 createInPlace(this->end(), std::forward<Args>(args)...);
766 ++this->size;
767
768 std::rotate(where, this->end() - 1, this->end());
769 }
770
771 template <typename iterator, typename ...Args>
772 void emplace(GrowsBackwardsTag, iterator where, Args&&... args)
773 {
774 Q_ASSERT(!this->isShared());
775 Q_ASSERT(where >= this->begin() && where <= this->end());
776 Q_ASSERT(this->freeSpaceAtBegin() >= 1);
777
778 createInPlace(this->begin() - 1, std::forward<Args>(args)...);
779 --this->ptr;
780 ++this->size;
781
782 std::rotate(this->begin(), this->begin() + 1, where);
783 }
784
785 void erase(T *b, T *e)
786 { erase(GrowsForwardTag{}, b, e); }
787
788 void erase(GrowsForwardTag, T *b, T *e)
789 {
790 Q_ASSERT(this->isMutable());
791 Q_ASSERT(b < e);
792 Q_ASSERT(b >= this->begin() && b < this->end());
793 Q_ASSERT(e > this->begin() && e <= this->end());
794
795 const T *const end = this->end();
796
797 // move (by assignment) the elements from e to end
798 // onto b to the new end
799 while (e != end) {
800 *b = *e;
801 ++b;
802 ++e;
803 }
804
805 // destroy the final elements at the end
806 // here, b points to the new end and e to the actual end
807 do {
808 // Exceptions or not, dtor called once per instance
809 --this->size;
810 (--e)->~T();
811 } while (e != b);
812 }
813
814 void erase(GrowsBackwardsTag, T *b, T *e)
815 {
816 Q_ASSERT(this->isMutable());
817 Q_ASSERT(b < e);
818 Q_ASSERT(b >= this->begin() && b < this->end());
819 Q_ASSERT(e > this->begin() && e <= this->end());
820
821 const T *const begin = this->begin();
822
823 // move (by assignment) the elements from begin to b
824 // onto the new begin to e
825 while (b != begin) {
826 --b;
827 --e;
828 *e = *b;
829 }
830
831 // destroy the final elements at the begin
832 // here, e points to the new begin and b to the actual begin
833 do {
834 // Exceptions or not, dtor called once per instance
835 ++this->ptr;
836 --this->size;
837 (b++)->~T();
838 } while (b != e);
839 }
840
841 void assign(T *b, T *e, parameter_type t)
842 {
843 Q_ASSERT(b <= e);
844 Q_ASSERT(b >= this->begin() && e <= this->end());
845
846 while (b != e)
847 *b++ = t;
848 }
849
850 bool compare(const T *begin1, const T *begin2, size_t n) const
851 {
852 const T *end1 = begin1 + n;
853 while (begin1 != end1) {
854 if (*begin1 == *begin2) {
855 ++begin1;
856 ++begin2;
857 } else {
858 return false;
859 }
860 }
861 return true;
862 }
863};
864
865template <class T>
866struct QMovableArrayOps
867 : QGenericArrayOps<T>
868{
869 // using QGenericArrayOps<T>::appendInitialize;
870 // using QGenericArrayOps<T>::copyAppend;
871 // using QGenericArrayOps<T>::moveAppend;
872 // using QGenericArrayOps<T>::truncate;
873 // using QGenericArrayOps<T>::destroyAll;
874 typedef typename QGenericArrayOps<T>::parameter_type parameter_type;
875
876 void insert(T *where, const T *b, const T *e)
877 { insert(GrowsForwardTag{}, where, b, e); }
878
879 void insert(GrowsForwardTag, T *where, const T *b, const T *e)
880 {
881 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
882 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
883 Q_ASSERT(where >= this->begin() && where <= this->end());
884 Q_ASSERT(b <= e);
885 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
886 Q_ASSERT((e - b) <= this->freeSpaceAtEnd());
887
888 typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
889 typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
890
891 // Provides strong exception safety guarantee,
892 // provided T::~T() nothrow
893
894 ReversibleDisplace displace(where, this->end(), e - b);
895 CopyConstructor copier(where);
896 const auto copiedSize = copier.copy(b, e);
897 displace.commit();
898 this->size += copiedSize;
899 }
900
901 void insert(GrowsBackwardsTag, T *where, const T *b, const T *e)
902 {
903 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
904 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
905 Q_ASSERT(where >= this->begin() && where <= this->end());
906 Q_ASSERT(b <= e);
907 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
908 Q_ASSERT((e - b) <= this->freeSpaceAtBegin());
909
910 typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
911 typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
912
913 // Provides strong exception safety guarantee,
914 // provided T::~T() nothrow
915
916 ReversibleDisplace displace(this->begin(), where, -(e - b));
917 CopyConstructor copier(where - (e - b));
918 const auto copiedSize = copier.copy(b, e);
919 displace.commit();
920 this->ptr -= copiedSize;
921 this->size += copiedSize;
922 }
923
924 void insert(T *where, size_t n, parameter_type t)
925 { insert(GrowsForwardTag{}, where, n, t); }
926
927 void insert(GrowsForwardTag, T *where, size_t n, parameter_type t)
928 {
929 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
930 Q_ASSERT(where >= this->begin() && where <= this->end());
931 Q_ASSERT(size_t(this->freeSpaceAtEnd()) >= n);
932
933 typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
934 typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
935
936 // Provides strong exception safety guarantee,
937 // provided T::~T() nothrow
938
939 ReversibleDisplace displace(where, this->end(), qsizetype(n));
940 CopyConstructor copier(where);
941 const auto copiedSize = copier.clone(n, t);
942 displace.commit();
943 this->size += copiedSize;
944 }
945
946 void insert(GrowsBackwardsTag, T *where, size_t n, parameter_type t)
947 {
948 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
949 Q_ASSERT(where >= this->begin() && where <= this->end());
950 Q_ASSERT(size_t(this->freeSpaceAtBegin()) >= n);
951
952 typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
953 typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
954
955 // Provides strong exception safety guarantee,
956 // provided T::~T() nothrow
957
958 ReversibleDisplace displace(this->begin(), where, -qsizetype(n));
959 CopyConstructor copier(where - n);
960 const auto copiedSize = copier.clone(n, t);
961 displace.commit();
962 this->ptr -= copiedSize;
963 this->size += copiedSize;
964 }
965
966 // use moving insert
967 using QGenericArrayOps<T>::insert;
968
969 void erase(T *b, T *e)
970 { erase(GrowsForwardTag{}, b, e); }
971
972 void erase(GrowsForwardTag, T *b, T *e)
973 {
974 Q_ASSERT(this->isMutable());
975 Q_ASSERT(b < e);
976 Q_ASSERT(b >= this->begin() && b < this->end());
977 Q_ASSERT(e > this->begin() && e <= this->end());
978
979 typedef typename QArrayExceptionSafetyPrimitives<T>::Mover Mover;
980
981 Mover mover(e, static_cast<const T *>(this->end()) - e, this->size);
982
983 // destroy the elements we're erasing
984 do {
985 // Exceptions or not, dtor called once per instance
986 (--e)->~T();
987 } while (e != b);
988 }
989
990 void erase(GrowsBackwardsTag, T *b, T *e)
991 {
992 Q_ASSERT(this->isMutable());
993 Q_ASSERT(b < e);
994 Q_ASSERT(b >= this->begin() && b < this->end());
995 Q_ASSERT(e > this->begin() && e <= this->end());
996
997 typedef typename QArrayExceptionSafetyPrimitives<T>::Mover Mover;
998
999 Mover mover(this->ptr, b - static_cast<const T *>(this->begin()), this->size);
1000
1001 // destroy the elements we're erasing
1002 do {
1003 // Exceptions or not, dtor called once per instance
1004 ++this->ptr;
1005 (b++)->~T();
1006 } while (b != e);
1007 }
1008};
1009
1010template <class T, class = void>
1011struct QArrayOpsSelector
1012{
1013 typedef QGenericArrayOps<T> Type;
1014};
1015
1016template <class T>
1017struct QArrayOpsSelector<T,
1018 typename std::enable_if<
1019 !QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
1020 >::type>
1021{
1022 typedef QPodArrayOps<T> Type;
1023};
1024
1025template <class T>
1026struct QArrayOpsSelector<T,
1027 typename std::enable_if<
1028 QTypeInfo<T>::isComplex && QTypeInfo<T>::isRelocatable
1029 >::type>
1030{
1031 typedef QMovableArrayOps<T> Type;
1032};
1033
1034template <class T>
1035struct QCommonArrayOps : QArrayOpsSelector<T>::Type
1036{
1037 using Base = typename QArrayOpsSelector<T>::Type;
1038 using parameter_type = typename Base::parameter_type;
1039 using iterator = typename Base::iterator;
1040 using const_iterator = typename Base::const_iterator;
1041
1042protected:
1043 using Self = QCommonArrayOps<T>;
1044
1045 // Tag dispatched helper functions
1046 inline void adjustPointer(GrowsBackwardsTag, size_t distance) noexcept
1047 {
1048 this->ptr -= distance;
1049 }
1050 inline void adjustPointer(GrowsForwardTag, size_t distance) noexcept
1051 {
1052 this->ptr += distance;
1053 }
1054 qsizetype freeSpace(GrowsBackwardsTag) const noexcept { return this->freeSpaceAtBegin(); }
1055 qsizetype freeSpace(GrowsForwardTag) const noexcept { return this->freeSpaceAtEnd(); }
1056
1057 struct RelocatableMoveOps
1058 {
1059 // The necessary evil. Performs move "to the left" when grows backwards and
1060 // move "to the right" when grows forward
1061 template<typename GrowthTag>
1062 static void moveInGrowthDirection(GrowthTag tag, Self *this_, size_t futureGrowth)
1063 {
1064 Q_ASSERT(this_->isMutable());
1065 Q_ASSERT(!this_->isShared());
1066 Q_ASSERT(futureGrowth <= size_t(this_->freeSpace(tag)));
1067
1068 const auto oldBegin = this_->begin();
1069 this_->adjustPointer(tag, futureGrowth);
1070
1071 // Note: move all elements!
1072 ::memmove(static_cast<void *>(this_->begin()), static_cast<const void *>(oldBegin),
1073 this_->size * sizeof(T));
1074 }
1075 };
1076
1077 struct GenericMoveOps
1078 {
1079 template <typename ...Args>
1080 static void createInPlace(T *where, Args&&... args)
1081 {
1082 new (where) T(std::forward<Args>(args)...);
1083 }
1084
1085 template <typename ...Args>
1086 static void createInPlace(std::reverse_iterator<iterator> where, Args&&... args)
1087 {
1088 // Note: instead of std::addressof(*where)
1089 createInPlace(where.base() - 1, std::forward<Args>(args)...);
1090 }
1091
1092 // Moves non-pod data range. Handles overlapping regions. By default, expect
1093 // this method to perform move to the _right_. When move to the _left_ is
1094 // needed, use reverse iterators.
1095 template<typename GrowthTag, typename It>
1096 static void moveNonPod(GrowthTag, Self *this_, It where, It begin, It end)
1097 {
1098 Q_ASSERT(begin <= end);
1099 Q_ASSERT(where > begin); // move to the right
1100
1101 using Destructor = typename QArrayExceptionSafetyPrimitives<T>::template Destructor<It>;
1102
1103 auto start = where + std::distance(begin, end);
1104 auto e = end;
1105
1106 Destructor destroyer(start); // Keep track of added items
1107
1108 auto [oldRangeEnd, overlapStart] = std::minmax(where, end);
1109
1110 // step 1. move-initialize elements in uninitialized memory region
1111 while (start != overlapStart) {
1112 --e;
1113 createInPlace(start - 1, std::move_if_noexcept(*e));
1114 // change tracked iterator only after creation succeeded - avoid
1115 // destructing partially constructed objects if exception thrown
1116 --start;
1117 }
1118
1119 // re-created the range. now there is an initialized memory region
1120 // somewhere in the allocated area. if something goes wrong, we must
1121 // clean it up, so "freeze" the position for now (cannot commit yet)
1122 destroyer.freeze();
1123
1124 // step 2. move assign over existing elements in the overlapping
1125 // region (if there's an overlap)
1126 while (e != begin) {
1127 --start;
1128 --e;
1129 *start = std::move_if_noexcept(*e);
1130 }
1131
1132 // step 3. destroy elements in the old range
1133 const qsizetype originalSize = this_->size;
1134 start = begin; // delete elements in reverse order to prevent any gaps
1135 while (start != oldRangeEnd) {
1136 // Exceptions or not, dtor called once per instance
1137 if constexpr (std::is_same_v<std::decay_t<GrowthTag>, GrowsForwardTag>)
1138 ++this_->ptr;
1139 --this_->size;
1140 (start++)->~T();
1141 }
1142
1143 destroyer.commit();
1144 // restore old size as we consider data move to be done, the pointer
1145 // still has to be adjusted!
1146 this_->size = originalSize;
1147 }
1148
1149 // Super inefficient function. The necessary evil. Performs move "to
1150 // the left" when grows backwards and move "to the right" when grows
1151 // forward
1152 template<typename GrowthTag>
1153 static void moveInGrowthDirection(GrowthTag tag, Self *this_, size_t futureGrowth)
1154 {
1155 Q_ASSERT(this_->isMutable());
1156 Q_ASSERT(!this_->isShared());
1157 Q_ASSERT(futureGrowth <= size_t(this_->freeSpace(tag)));
1158
1159 if (futureGrowth == 0) // avoid doing anything if there's no need
1160 return;
1161
1162 // Note: move all elements!
1163 if constexpr (std::is_same_v<std::decay_t<GrowthTag>, GrowsBackwardsTag>) {
1164 auto where = this_->begin() - futureGrowth;
1165 // here, magic happens. instead of having move to the right, we'll
1166 // have move to the left by using reverse iterators
1167 moveNonPod(tag, this_,
1168 std::make_reverse_iterator(where + this_->size), // rwhere
1169 std::make_reverse_iterator(this_->end()), // rbegin
1170 std::make_reverse_iterator(this_->begin())); // rend
1171 this_->ptr = where;
1172 } else {
1173 auto where = this_->begin() + futureGrowth;
1174 moveNonPod(tag, this_, where, this_->begin(), this_->end());
1175 this_->ptr = where;
1176 }
1177 }
1178 };
1179
1180 // Moves all elements in a specific direction by moveSize if available
1181 // free space at one of the ends is smaller than required. Free space
1182 // becomes available at the beginning if grows backwards and at the end
1183 // if grows forward
1184 template<typename GrowthTag>
1185 qsizetype prepareFreeSpace(GrowthTag tag, size_t required, size_t moveSize)
1186 {
1187 Q_ASSERT(this->isMutable() || required == 0);
1188 Q_ASSERT(!this->isShared() || required == 0);
1189 Q_ASSERT(required <= size_t(this->constAllocatedCapacity() - this->size));
1190
1191 using MoveOps = std::conditional_t<QTypeInfo<T>::isRelocatable,
1192 RelocatableMoveOps,
1193 GenericMoveOps>;
1194
1195 // if free space at the end is not enough, we need to move the data,
1196 // move is performed in an inverse direction
1197 if (size_t(freeSpace(tag)) < required) {
1198 using MoveTag = typename InverseTag<std::decay_t<GrowthTag>>::tag;
1199 MoveOps::moveInGrowthDirection(MoveTag{}, this, moveSize);
1200
1201 if constexpr (std::is_same_v<MoveTag, GrowsBackwardsTag>) {
1202 return -qsizetype(moveSize); // moving data to the left
1203 } else {
1204 return qsizetype(moveSize); // moving data to the right
1205 }
1206 }
1207 return 0;
1208 }
1209
1210 // Helper wrapper that adjusts passed iterators along with moving the data
1211 // around. The adjustment is necessary when iterators point inside the
1212 // to-be-moved range
1213 template<typename GrowthTag, typename It>
1214 void prepareFreeSpace(GrowthTag tag, size_t required, size_t moveSize, It &b, It &e) {
1215 // Returns whether passed iterators are inside [this->begin(), this->end()]
1216 const auto iteratorsInRange = [&] (const It &first, const It &last) {
1217 using DecayedIt = std::decay_t<It>;
1218 using RemovedConstVolatileIt = std::remove_cv_t<It>;
1219 constexpr bool selfIterator =
1220 // if passed type is an iterator type:
1221 std::is_same_v<DecayedIt, iterator>
1222 || std::is_same_v<DecayedIt, const_iterator>
1223 // if passed type is a pointer type:
1224 || std::is_same_v<RemovedConstVolatileIt, T *>
1225 || std::is_same_v<RemovedConstVolatileIt, const T *>
1226 || std::is_same_v<RemovedConstVolatileIt, const volatile T *>;
1227 if constexpr (selfIterator) {
1228 return (first >= this->begin() && last <= this->end());
1229 } else {
1230 return false;
1231 }
1232 };
1233
1234 const bool inRange = iteratorsInRange(b, e);
1235 const auto diff = prepareFreeSpace(tag, required, moveSize);
1236 if (inRange) {
1237 std::advance(b, diff);
1238 std::advance(e, diff);
1239 }
1240 }
1241
1242 size_t moveSizeForAppend(size_t)
1243 {
1244 // Qt5 QList in append: make 100% free space at end if not enough space
1245 // Now:
1246 return this->freeSpaceAtBegin();
1247 }
1248
1249 size_t moveSizeForPrepend(size_t required)
1250 {
1251 // Qt5 QList in prepend: make 33% of all space at front if not enough space
1252 // Now:
1253 qsizetype space = this->allocatedCapacity() / 3;
1254 space = qMax(space, qsizetype(required)); // in case required > 33% of all space
1255 return qMin(space, this->freeSpaceAtEnd());
1256 }
1257
1258 // Helper functions that reduce usage boilerplate
1259 void prepareSpaceForAppend(size_t required)
1260 {
1261 prepareFreeSpace(GrowsForwardTag{}, required, moveSizeForAppend(required));
1262 }
1263 void prepareSpaceForPrepend(size_t required)
1264 {
1265 prepareFreeSpace(GrowsBackwardsTag{}, required, moveSizeForPrepend(required));
1266 }
1267 template<typename It>
1268 void prepareSpaceForAppend(It &b, It &e, size_t required)
1269 {
1270 prepareFreeSpace(GrowsForwardTag{}, required, moveSizeForAppend(required), b, e);
1271 }
1272 template<typename It>
1273 void prepareSpaceForPrepend(It &b, It &e, size_t required)
1274 {
1275 prepareFreeSpace(GrowsBackwardsTag{}, required, moveSizeForPrepend(required), b, e);
1276 }
1277
1278 // Tells how much of the given size to insert at the beginning of the
1279 // container. This is insert-specific helper function
1280 qsizetype sizeToInsertAtBegin(const T *const where, qsizetype maxSize)
1281 {
1282 Q_ASSERT(maxSize <= this->allocatedCapacity() - this->size);
1283 Q_ASSERT(where >= this->begin() && where <= this->end()); // in range
1284
1285 const auto freeAtBegin = this->freeSpaceAtBegin();
1286 const auto freeAtEnd = this->freeSpaceAtEnd();
1287
1288 // Idea: * if enough space on both sides, try to affect less elements
1289 // * if enough space on one of the sides, use only that side
1290 // * otherwise, split between front and back (worst case)
1291 if (freeAtBegin >= maxSize && freeAtEnd >= maxSize) {
1292 if (where - this->begin() < this->end() - where) {
1293 return maxSize;
1294 } else {
1295 return 0;
1296 }
1297 } else if (freeAtBegin >= maxSize) {
1298 return maxSize;
1299 } else if (freeAtEnd >= maxSize) {
1300 return 0;
1301 } else {
1302 return maxSize - freeAtEnd;
1303 }
1304 }
1305
1306public:
1307 // Returns whether reallocation is desirable before adding more elements
1308 // into the container. This is a helper function that one can use to
1309 // theoretically improve average operations performance. Ignoring this
1310 // function does not affect the correctness of the array operations.
1311 bool shouldGrowBeforeInsert(const_iterator where, qsizetype n) const noexcept
1312 {
1313 if (this->d == nullptr)
1314 return true;
1315 if (this->d->flags & QArrayData::CapacityReserved)
1316 return false;
1317 if (!(this->d->flags & (QArrayData::GrowsForward | QArrayData::GrowsBackwards)))
1318 return false;
1319 Q_ASSERT(where >= this->begin() && where <= this->end()); // in range
1320
1321 const qsizetype freeAtBegin = this->freeSpaceAtBegin();
1322 const qsizetype freeAtEnd = this->freeSpaceAtEnd();
1323 const qsizetype capacity = this->constAllocatedCapacity();
1324
1325 if (this->size > 0 && where == this->begin()) { // prepend
1326 // Qt5 QList in prepend: not enough space at begin && 33% full
1327 // Now (below):
1328 return freeAtBegin < n && (this->size >= (capacity / 3));
1329 }
1330
1331 if (where == this->end()) { // append
1332 // Qt5 QList in append: not enough space at end && less than 66% free space at front
1333 // Now (below):
1334 return freeAtEnd < n && !((freeAtBegin - n) >= (2 * capacity / 3));
1335 }
1336
1337 // Qt5 QList in insert: no free space
1338 // Now: no free space OR not enough space on either of the sides (bad perf. case)
1339 return (freeAtBegin + freeAtEnd) < n || (freeAtBegin < n && freeAtEnd < n);
1340 }
1341
1342 // using Base::truncate;
1343 // using Base::destroyAll;
1344 // using Base::assign;
1345 // using Base::compare;
1346
1347 void appendInitialize(size_t newSize)
1348 {
1349 Q_ASSERT(this->isMutable());
1350 Q_ASSERT(!this->isShared());
1351 Q_ASSERT(newSize > size_t(this->size));
1352 Q_ASSERT(newSize <= size_t(this->allocatedCapacity()));
1353
1354 // Since this is mostly an initialization function, do not follow append
1355 // logic of space arrangement. Instead, only prepare as much free space
1356 // as needed for this specific operation
1357 const size_t n = newSize - this->size;
1358 prepareFreeSpace(GrowsForwardTag{}, n,
1359 qMin(n, size_t(this->freeSpaceAtBegin()))); // ### perf. loss
1360
1361 Base::appendInitialize(newSize);
1362 }
1363
1364 void copyAppend(const T *b, const T *e)
1365 {
1366 Q_ASSERT(this->isMutable() || b == e);
1367 Q_ASSERT(!this->isShared() || b == e);
1368 Q_ASSERT(b <= e);
1369 Q_ASSERT((e - b) <= this->allocatedCapacity() - this->size);
1370 if (b == e) // short-cut and handling the case b and e == nullptr
1371 return;
1372
1373 prepareSpaceForAppend(b, e, e - b); // ### perf. loss
1374 Base::insert(GrowsForwardTag{}, this->end(), b, e);
1375 }
1376
1377 template<typename It>
1378 void copyAppend(It b, It e, QtPrivate::IfIsForwardIterator<It> = true,
1379 QtPrivate::IfIsNotSame<std::decay_t<It>, iterator> = true,
1380 QtPrivate::IfIsNotSame<std::decay_t<It>, const_iterator> = true)
1381 {
1382 Q_ASSERT(this->isMutable() || b == e);
1383 Q_ASSERT(!this->isShared() || b == e);
1384 const qsizetype distance = std::distance(b, e);
1385 Q_ASSERT(distance >= 0 && distance <= this->allocatedCapacity() - this->size);
1386
1387 prepareSpaceForAppend(b, e, distance); // ### perf. loss
1388
1389 T *iter = this->end();
1390 for (; b != e; ++iter, ++b) {
1391 new (iter) T(*b);
1392 ++this->size;
1393 }
1394 }
1395
1396 void moveAppend(T *b, T *e)
1397 {
1398 Q_ASSERT(this->isMutable() || b == e);
1399 Q_ASSERT(!this->isShared() || b == e);
1400 Q_ASSERT(b <= e);
1401 Q_ASSERT((e - b) <= this->allocatedCapacity() - this->size);
1402 if (b == e) // short-cut and handling the case b and e == nullptr
1403 return;
1404
1405 prepareSpaceForAppend(b, e, e - b); // ### perf. loss
1406 Base::moveAppend(b, e);
1407 }
1408
1409 void copyAppend(size_t n, parameter_type t)
1410 {
1411 Q_ASSERT(!this->isShared() || n == 0);
1412 Q_ASSERT(size_t(this->allocatedCapacity() - this->size) >= n);
1413
1414 // Preserve the value, because it might be a reference to some part of the moved chunk
1415 T tmp(t);
1416 prepareSpaceForAppend(n); // ### perf. loss
1417 Base::insert(GrowsForwardTag{}, this->end(), n, tmp);
1418 }
1419
1420 void insert(T *where, const T *b, const T *e)
1421 {
1422 Q_ASSERT(this->isMutable() || (b == e && where == this->end()));
1423 Q_ASSERT(!this->isShared() || (b == e && where == this->end()));
1424 Q_ASSERT(where >= this->begin() && where <= this->end());
1425 Q_ASSERT(b <= e);
1426 Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
1427 Q_ASSERT((e - b) <= this->allocatedCapacity() - this->size);
1428 if (b == e) // short-cut and handling the case b and e == nullptr
1429 return;
1430
1431 if (this->size > 0 && where == this->begin()) { // prepend case - special space arrangement
1432 prepareSpaceForPrepend(b, e, e - b); // ### perf. loss
1433 Base::insert(GrowsBackwardsTag{}, this->begin(), b, e);
1434 return;
1435 } else if (where == this->end()) { // append case - special space arrangement
1436 copyAppend(b, e);
1437 return;
1438 }
1439
1440 // Insert elements based on the divided distance. Good case: only 1
1441 // insert happens (either to the front part or to the back part). Bad
1442 // case: both inserts happen, meaning that we touch all N elements in
1443 // the container (this should be handled "outside" by ensuring enough
1444 // free space by reallocating more frequently)
1445 const auto k = sizeToInsertAtBegin(where, e - b);
1446 Base::insert(GrowsBackwardsTag{}, where, b, b + k);
1447 Base::insert(GrowsForwardTag{}, where, b + k, e);
1448 }
1449
1450 void insert(T *where, size_t n, parameter_type t)
1451 {
1452 Q_ASSERT(!this->isShared() || (n == 0 && where == this->end()));
1453 Q_ASSERT(where >= this->begin() && where <= this->end());
1454 Q_ASSERT(size_t(this->allocatedCapacity() - this->size) >= n);
1455
1456 if (this->size > 0 && where == this->begin()) { // prepend case - special space arrangement
1457 // Preserve the value, because it might be a reference to some part of the moved chunk
1458 T tmp(t);
1459 prepareSpaceForPrepend(n); // ### perf. loss
1460 Base::insert(GrowsBackwardsTag{}, this->begin(), n, tmp);
1461 return;
1462 } else if (where == this->end()) { // append case - special space arrangement
1463 copyAppend(n, t);
1464 return;
1465 }
1466
1467 // Insert elements based on the divided distance. Good case: only 1
1468 // insert happens (either to the front part or to the back part). Bad
1469 // case: both inserts happen, meaning that we touch all N elements in
1470 // the container (this should be handled "outside" by ensuring enough
1471 // free space by reallocating more frequently)
1472 const auto beginSize = sizeToInsertAtBegin(where, qsizetype(n));
1473 Base::insert(GrowsBackwardsTag{}, where, beginSize, t);
1474 Base::insert(GrowsForwardTag{}, where, qsizetype(n) - beginSize, t);
1475 }
1476
1477 template <typename iterator, typename ...Args>
1478 void emplace(iterator where, Args&&... args)
1479 {
1480 Q_ASSERT(!this->isShared());
1481 Q_ASSERT(where >= this->begin() && where <= this->end());
1482 Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
1483
1484 // Qt5 QList in insert(1): try to move less data around
1485 // Now:
1486 const bool shouldInsertAtBegin = (where - this->begin()) < (this->end() - where)
1487 || this->freeSpaceAtEnd() <= 0;
1488 if (this->freeSpaceAtBegin() > 0 && shouldInsertAtBegin) {
1489 Base::emplace(GrowsBackwardsTag{}, where, std::forward<Args>(args)...);
1490 } else {
1491 Base::emplace(GrowsForwardTag{}, where, std::forward<Args>(args)...);
1492 }
1493 }
1494
1495 template <typename ...Args>
1496 void emplaceBack(Args&&... args)
1497 {
1498 this->emplace(this->end(), std::forward<Args>(args)...);
1499 }
1500
1501 void erase(T *b, T *e)
1502 {
1503 Q_ASSERT(this->isMutable());
1504 Q_ASSERT(b < e);
1505 Q_ASSERT(b >= this->begin() && b < this->end());
1506 Q_ASSERT(e > this->begin() && e <= this->end());
1507
1508 // Comply with std::vector::erase(): erased elements and all after them
1509 // are invalidated. However, erasing from the beginning effectively
1510 // means that all iterators are invalidated. We can use this freedom to
1511 // erase by moving towards the end.
1512 if (b == this->begin()) {
1513 Base::erase(GrowsBackwardsTag{}, b, e);
1514 } else {
1515 Base::erase(GrowsForwardTag{}, b, e);
1516 }
1517 }
1518};
1519
1520} // namespace QtPrivate
1521
1522template <class T>
1523struct QArrayDataOps
1524 : QtPrivate::QCommonArrayOps<T>
1525{
1526};
1527
1528QT_END_NAMESPACE
1529
1530#endif // include guard
1531