1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QVARLENGTHARRAY_H
41#define QVARLENGTHARRAY_H
42
43#include <QtCore/qcontainerfwd.h>
44#include <QtCore/qglobal.h>
45#include <QtCore/qalgorithms.h>
46
47#include <new>
48#include <string.h>
49#include <stdlib.h>
50#include <algorithm>
51#ifdef Q_COMPILER_INITIALIZER_LISTS
52#include <initializer_list>
53#endif
54#include <iterator>
55
56QT_BEGIN_NAMESPACE
57
58
59// Prealloc = 256 by default, specified in qcontainerfwd.h
60template<class T, int Prealloc>
61class QVarLengthArray
62{
63public:
64 inline explicit QVarLengthArray(int size = 0);
65
66 inline QVarLengthArray(const QVarLengthArray<T, Prealloc> &other)
67 : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
68 {
69 append(other.constData(), other.size());
70 }
71
72#ifdef Q_COMPILER_INITIALIZER_LISTS
73 QVarLengthArray(std::initializer_list<T> args)
74 : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
75 {
76 if (args.size())
77 append(args.begin(), int(args.size()));
78 }
79#endif
80
81 inline ~QVarLengthArray() {
82 if (QTypeInfo<T>::isComplex) {
83 T *i = ptr + s;
84 while (i-- != ptr)
85 i->~T();
86 }
87 if (ptr != reinterpret_cast<T *>(array))
88 free(ptr);
89 }
90 inline QVarLengthArray<T, Prealloc> &operator=(const QVarLengthArray<T, Prealloc> &other)
91 {
92 if (this != &other) {
93 clear();
94 append(other.constData(), other.size());
95 }
96 return *this;
97 }
98
99#ifdef Q_COMPILER_INITIALIZER_LISTS
100 QVarLengthArray<T, Prealloc> &operator=(std::initializer_list<T> list)
101 {
102 resize(list.size());
103 std::copy(list.begin(), list.end(),
104 QT_MAKE_CHECKED_ARRAY_ITERATOR(this->begin(), this->size()));
105 return *this;
106 }
107#endif
108
109 inline void removeLast() {
110 Q_ASSERT(s > 0);
111 realloc(s - 1, a);
112 }
113 inline int size() const { return s; }
114 inline int count() const { return s; }
115 inline int length() const { return s; }
116 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
117 inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
118 T& last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
119 const T& last() const { Q_ASSERT(!isEmpty()); return *(end() - 1); }
120 inline bool isEmpty() const { return (s == 0); }
121 inline void resize(int size);
122 inline void clear() { resize(0); }
123 inline void squeeze();
124
125 inline int capacity() const { return a; }
126 inline void reserve(int size);
127
128 inline int indexOf(const T &t, int from = 0) const;
129 inline int lastIndexOf(const T &t, int from = -1) const;
130 inline bool contains(const T &t) const;
131
132 inline T &operator[](int idx) {
133 Q_ASSERT(idx >= 0 && idx < s);
134 return ptr[idx];
135 }
136 inline const T &operator[](int idx) const {
137 Q_ASSERT(idx >= 0 && idx < s);
138 return ptr[idx];
139 }
140 inline const T &at(int idx) const { return operator[](idx); }
141
142 T value(int i) const;
143 T value(int i, const T &defaultValue) const;
144
145 inline void append(const T &t) {
146 if (s == a) { // i.e. s != 0
147 T copy(t);
148 realloc(s, s<<1);
149 const int idx = s++;
150 if (QTypeInfo<T>::isComplex) {
151 new (ptr + idx) T(std::move(copy));
152 } else {
153 ptr[idx] = std::move(copy);
154 }
155 } else {
156 const int idx = s++;
157 if (QTypeInfo<T>::isComplex) {
158 new (ptr + idx) T(t);
159 } else {
160 ptr[idx] = t;
161 }
162 }
163 }
164
165 void append(T &&t) {
166 if (s == a)
167 realloc(s, s << 1);
168 const int idx = s++;
169 if (QTypeInfo<T>::isComplex)
170 new (ptr + idx) T(std::move(t));
171 else
172 ptr[idx] = std::move(t);
173 }
174
175 void append(const T *buf, int size);
176 inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
177 { append(t); return *this; }
178 inline QVarLengthArray<T, Prealloc> &operator<<(T &&t)
179 { append(std::move(t)); return *this; }
180 inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
181 { append(t); return *this; }
182 inline QVarLengthArray<T, Prealloc> &operator+=(T &&t)
183 { append(std::move(t)); return *this; }
184
185 void prepend(T &&t);
186 void prepend(const T &t);
187 void insert(int i, T &&t);
188 void insert(int i, const T &t);
189 void insert(int i, int n, const T &t);
190 void replace(int i, const T &t);
191 void remove(int i);
192 void remove(int i, int n);
193
194
195 inline T *data() { return ptr; }
196 inline const T *data() const { return ptr; }
197 inline const T * constData() const { return ptr; }
198 typedef int size_type;
199 typedef T value_type;
200 typedef value_type *pointer;
201 typedef const value_type *const_pointer;
202 typedef value_type &reference;
203 typedef const value_type &const_reference;
204 typedef qptrdiff difference_type;
205
206
207 typedef T* iterator;
208 typedef const T* const_iterator;
209 typedef std::reverse_iterator<iterator> reverse_iterator;
210 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
211
212 inline iterator begin() { return ptr; }
213 inline const_iterator begin() const { return ptr; }
214 inline const_iterator cbegin() const { return ptr; }
215 inline const_iterator constBegin() const { return ptr; }
216 inline iterator end() { return ptr + s; }
217 inline const_iterator end() const { return ptr + s; }
218 inline const_iterator cend() const { return ptr + s; }
219 inline const_iterator constEnd() const { return ptr + s; }
220 reverse_iterator rbegin() { return reverse_iterator(end()); }
221 reverse_iterator rend() { return reverse_iterator(begin()); }
222 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
223 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
224 const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
225 const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
226 iterator insert(const_iterator before, int n, const T &x);
227 iterator insert(const_iterator before, T &&x);
228 inline iterator insert(const_iterator before, const T &x) { return insert(before, 1, x); }
229 iterator erase(const_iterator begin, const_iterator end);
230 inline iterator erase(const_iterator pos) { return erase(pos, pos+1); }
231
232 // STL compatibility:
233 inline bool empty() const { return isEmpty(); }
234 inline void push_back(const T &t) { append(t); }
235 void push_back(T &&t) { append(std::move(t)); }
236 inline void pop_back() { removeLast(); }
237 inline T &front() { return first(); }
238 inline const T &front() const { return first(); }
239 inline T &back() { return last(); }
240 inline const T &back() const { return last(); }
241 void shrink_to_fit() { squeeze(); }
242
243private:
244 void realloc(int size, int alloc);
245
246 int a; // capacity
247 int s; // size
248 T *ptr; // data
249 union {
250 char array[Prealloc * sizeof(T)];
251 qint64 q_for_alignment_1;
252 double q_for_alignment_2;
253 };
254
255 bool isValidIterator(const const_iterator &i) const
256 {
257 const std::less<const T*> less = {};
258 return !less(cend(), i) && !less(i, cbegin());
259 }
260};
261
262template <class T, int Prealloc>
263Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(int asize)
264 : s(asize) {
265 Q_STATIC_ASSERT_X(Prealloc > 0, "QVarLengthArray Prealloc must be greater than 0.");
266 Q_ASSERT_X(s >= 0, "QVarLengthArray::QVarLengthArray()", "Size must be greater than or equal to 0.");
267 if (s > Prealloc) {
268 ptr = reinterpret_cast<T *>(malloc(s * sizeof(T)));
269 Q_CHECK_PTR(ptr);
270 a = s;
271 } else {
272 ptr = reinterpret_cast<T *>(array);
273 a = Prealloc;
274 }
275 if (QTypeInfo<T>::isComplex) {
276 T *i = ptr + s;
277 while (i != ptr)
278 new (--i) T;
279 }
280}
281
282template <class T, int Prealloc>
283Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::resize(int asize)
284{ realloc(asize, qMax(asize, a)); }
285
286template <class T, int Prealloc>
287Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::reserve(int asize)
288{ if (asize > a) realloc(s, asize); }
289
290template <class T, int Prealloc>
291Q_INLINE_TEMPLATE int QVarLengthArray<T, Prealloc>::indexOf(const T &t, int from) const
292{
293 if (from < 0)
294 from = qMax(from + s, 0);
295 if (from < s) {
296 T *n = ptr + from - 1;
297 T *e = ptr + s;
298 while (++n != e)
299 if (*n == t)
300 return n - ptr;
301 }
302 return -1;
303}
304
305template <class T, int Prealloc>
306Q_INLINE_TEMPLATE int QVarLengthArray<T, Prealloc>::lastIndexOf(const T &t, int from) const
307{
308 if (from < 0)
309 from += s;
310 else if (from >= s)
311 from = s - 1;
312 if (from >= 0) {
313 T *b = ptr;
314 T *n = ptr + from + 1;
315 while (n != b) {
316 if (*--n == t)
317 return n - b;
318 }
319 }
320 return -1;
321}
322
323template <class T, int Prealloc>
324Q_INLINE_TEMPLATE bool QVarLengthArray<T, Prealloc>::contains(const T &t) const
325{
326 T *b = ptr;
327 T *i = ptr + s;
328 while (i != b) {
329 if (*--i == t)
330 return true;
331 }
332 return false;
333}
334
335template <class T, int Prealloc>
336Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::append(const T *abuf, int increment)
337{
338 Q_ASSERT(abuf);
339 if (increment <= 0)
340 return;
341
342 const int asize = s + increment;
343
344 if (asize >= a)
345 realloc(s, qMax(s*2, asize));
346
347 if (QTypeInfo<T>::isComplex) {
348 // call constructor for new objects (which can throw)
349 while (s < asize)
350 new (ptr+(s++)) T(*abuf++);
351 } else {
352 memcpy(static_cast<void *>(&ptr[s]), static_cast<const void *>(abuf), increment * sizeof(T));
353 s = asize;
354 }
355}
356
357template <class T, int Prealloc>
358Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::squeeze()
359{ realloc(s, s); }
360
361template <class T, int Prealloc>
362Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
363{
364 Q_ASSERT(aalloc >= asize);
365 T *oldPtr = ptr;
366 int osize = s;
367
368 const int copySize = qMin(asize, osize);
369 Q_ASSUME(copySize >= 0);
370 if (aalloc != a) {
371 if (aalloc > Prealloc) {
372 T* newPtr = reinterpret_cast<T *>(malloc(aalloc * sizeof(T)));
373 Q_CHECK_PTR(newPtr); // could throw
374 // by design: in case of QT_NO_EXCEPTIONS malloc must not fail or it crashes here
375 ptr = newPtr;
376 a = aalloc;
377 } else {
378 ptr = reinterpret_cast<T *>(array);
379 a = Prealloc;
380 }
381 s = 0;
382 if (!QTypeInfoQuery<T>::isRelocatable) {
383 QT_TRY {
384 // move all the old elements
385 while (s < copySize) {
386 new (ptr+s) T(std::move(*(oldPtr+s)));
387 (oldPtr+s)->~T();
388 s++;
389 }
390 } QT_CATCH(...) {
391 // clean up all the old objects and then free the old ptr
392 int sClean = s;
393 while (sClean < osize)
394 (oldPtr+(sClean++))->~T();
395 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
396 free(oldPtr);
397 QT_RETHROW;
398 }
399 } else {
400 memcpy(static_cast<void *>(ptr), static_cast<const void *>(oldPtr), copySize * sizeof(T));
401 }
402 }
403 s = copySize;
404
405 if (QTypeInfo<T>::isComplex) {
406 // destroy remaining old objects
407 while (osize > asize)
408 (oldPtr+(--osize))->~T();
409 }
410
411 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
412 free(oldPtr);
413
414 if (QTypeInfo<T>::isComplex) {
415 // call default constructor for new objects (which can throw)
416 while (s < asize)
417 new (ptr+(s++)) T;
418 } else {
419 s = asize;
420 }
421}
422
423template <class T, int Prealloc>
424Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i) const
425{
426 if (uint(i) >= uint(size())) {
427 return T();
428 }
429 return at(i);
430}
431template <class T, int Prealloc>
432Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defaultValue) const
433{
434 return (uint(i) >= uint(size())) ? defaultValue : at(i);
435}
436
437template <class T, int Prealloc>
438inline void QVarLengthArray<T, Prealloc>::insert(int i, T &&t)
439{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
440 insert(cbegin() + i, std::move(t)); }
441template <class T, int Prealloc>
442inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
443{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
444 insert(begin() + i, 1, t); }
445template <class T, int Prealloc>
446inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
447{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
448 insert(begin() + i, n, t); }
449template <class T, int Prealloc>
450inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
451{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
452 erase(begin() + i, begin() + i + n); }
453template <class T, int Prealloc>
454inline void QVarLengthArray<T, Prealloc>::remove(int i)
455{ Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
456 erase(begin() + i, begin() + i + 1); }
457template <class T, int Prealloc>
458inline void QVarLengthArray<T, Prealloc>::prepend(T &&t)
459{ insert(cbegin(), std::move(t)); }
460template <class T, int Prealloc>
461inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
462{ insert(begin(), 1, t); }
463
464template <class T, int Prealloc>
465inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
466{
467 Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
468 const T copy(t);
469 data()[i] = copy;
470}
471
472template <class T, int Prealloc>
473Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(const_iterator before, T &&t)
474{
475 Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
476
477 int offset = int(before - ptr);
478 reserve(s + 1);
479 if (!QTypeInfo<T>::isRelocatable) {
480 T *b = ptr + offset;
481 T *i = ptr + s;
482 T *j = i + 1;
483 // The new end-element needs to be constructed, the rest must be move assigned
484 if (i != b) {
485 new (--j) T(std::move(*--i));
486 while (i != b)
487 *--j = std::move(*--i);
488 *b = std::move(t);
489 } else {
490 new (b) T(std::move(t));
491 }
492 } else {
493 T *b = ptr + offset;
494 memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (s - offset) * sizeof(T));
495 new (b) T(std::move(t));
496 }
497 s += 1;
498 return ptr + offset;
499}
500
501template <class T, int Prealloc>
502Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(const_iterator before, size_type n, const T &t)
503{
504 Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
505
506 int offset = int(before - ptr);
507 if (n != 0) {
508 resize(s + n);
509 const T copy(t);
510 if (!QTypeInfoQuery<T>::isRelocatable) {
511 T *b = ptr + offset;
512 T *j = ptr + s;
513 T *i = j - n;
514 while (i != b)
515 *--j = *--i;
516 i = b + n;
517 while (i != b)
518 *--i = copy;
519 } else {
520 T *b = ptr + offset;
521 T *i = b + n;
522 memmove(static_cast<void *>(i), static_cast<const void *>(b), (s - offset - n) * sizeof(T));
523 while (i != b)
524 new (--i) T(copy);
525 }
526 }
527 return ptr + offset;
528}
529
530template <class T, int Prealloc>
531Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::erase(const_iterator abegin, const_iterator aend)
532{
533 Q_ASSERT_X(isValidIterator(abegin), "QVarLengthArray::insert", "The specified const_iterator argument 'abegin' is invalid");
534 Q_ASSERT_X(isValidIterator(aend), "QVarLengthArray::insert", "The specified const_iterator argument 'aend' is invalid");
535
536 int f = int(abegin - ptr);
537 int l = int(aend - ptr);
538 int n = l - f;
539 if (QTypeInfo<T>::isComplex) {
540 std::copy(ptr + l, ptr + s, QT_MAKE_CHECKED_ARRAY_ITERATOR(ptr + f, s - f));
541 T *i = ptr + s;
542 T *b = ptr + s - n;
543 while (i != b) {
544 --i;
545 i->~T();
546 }
547 } else {
548 memmove(static_cast<void *>(ptr + f), static_cast<const void *>(ptr + l), (s - l) * sizeof(T));
549 }
550 s -= n;
551 return ptr + f;
552}
553
554template <typename T, int Prealloc1, int Prealloc2>
555bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
556{
557 if (l.size() != r.size())
558 return false;
559 const T *rb = r.begin();
560 const T *b = l.begin();
561 const T *e = l.end();
562 return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(rb, r.size()));
563}
564
565template <typename T, int Prealloc1, int Prealloc2>
566bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
567{
568 return !(l == r);
569}
570
571template <typename T, int Prealloc1, int Prealloc2>
572bool operator<(const QVarLengthArray<T, Prealloc1> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
573 Q_DECL_NOEXCEPT_EXPR(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(),
574 rhs.begin(), rhs.end())))
575{
576 return std::lexicographical_compare(lhs.begin(), lhs.end(),
577 rhs.begin(), rhs.end());
578}
579
580template <typename T, int Prealloc1, int Prealloc2>
581inline bool operator>(const QVarLengthArray<T, Prealloc1> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
582 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
583{
584 return rhs < lhs;
585}
586
587template <typename T, int Prealloc1, int Prealloc2>
588inline bool operator<=(const QVarLengthArray<T, Prealloc1> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
589 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
590{
591 return !(lhs > rhs);
592}
593
594template <typename T, int Prealloc1, int Prealloc2>
595inline bool operator>=(const QVarLengthArray<T, Prealloc1> &lhs, const QVarLengthArray<T, Prealloc2> &rhs)
596 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
597{
598 return !(lhs < rhs);
599}
600
601QT_END_NAMESPACE
602
603#endif // QVARLENGTHARRAY_H
604