1/****************************************************************************
2**
3** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4** Contact: http://www.qt-project.org/legal
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 Digia. For licensing terms and
14** conditions see http://qt.digia.com/licensing. For further information
15** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 2.1 requirements
23** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24**
25** In addition, as a special exception, Digia gives you certain additional
26** rights. These rights are described in the Digia Qt LGPL Exception
27** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28**
29** GNU General Public License Usage
30** Alternatively, this file may be used under the terms of the GNU
31** General Public License version 3.0 as published by the Free Software
32** Foundation and appearing in the file LICENSE.GPL included in the
33** packaging of this file. Please review the following information to
34** ensure the GNU General Public License version 3.0 requirements will be
35** met: http://www.gnu.org/copyleft/gpl.html.
36**
37**
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#ifndef QVARLENGTHARRAY_H
43#define QVARLENGTHARRAY_H
44
45#include <QtCore/qcontainerfwd.h>
46#include <QtCore/qglobal.h>
47#include <QtCore/qalgorithms.h>
48
49#include <new>
50#include <string.h>
51
52QT_BEGIN_HEADER
53
54QT_BEGIN_NAMESPACE
55
56QT_MODULE(Core)
57
58template<class T, int Prealloc>
59class QPodList;
60
61// Prealloc = 256 by default, specified in qcontainerfwd.h
62template<class T, int Prealloc>
63class QVarLengthArray
64{
65public:
66 inline explicit QVarLengthArray(int size = 0);
67
68 inline QVarLengthArray(const QVarLengthArray<T, Prealloc> &other)
69 : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
70 {
71 append(other.constData(), other.size());
72 }
73
74 inline ~QVarLengthArray() {
75 if (QTypeInfo<T>::isComplex) {
76 T *i = ptr + s;
77 while (i-- != ptr)
78 i->~T();
79 }
80 if (ptr != reinterpret_cast<T *>(array))
81 qFree(ptr);
82 }
83 inline QVarLengthArray<T, Prealloc> &operator=(const QVarLengthArray<T, Prealloc> &other)
84 {
85 if (this != &other) {
86 clear();
87 append(other.constData(), other.size());
88 }
89 return *this;
90 }
91
92 inline void removeLast() {
93 Q_ASSERT(s > 0);
94 realloc(s - 1, a);
95 }
96 inline int size() const { return s; }
97 inline int count() const { return s; }
98 inline bool isEmpty() const { return (s == 0); }
99 inline void resize(int size);
100 inline void clear() { resize(0); }
101
102 inline int capacity() const { return a; }
103 inline void reserve(int size);
104
105 inline T &operator[](int idx) {
106 Q_ASSERT(idx >= 0 && idx < s);
107 return ptr[idx];
108 }
109 inline const T &operator[](int idx) const {
110 Q_ASSERT(idx >= 0 && idx < s);
111 return ptr[idx];
112 }
113 inline const T &at(int idx) const { return operator[](idx); }
114
115 T value(int i) const;
116 T value(int i, const T &defaultValue) const;
117
118 inline void append(const T &t) {
119 if (s == a) // i.e. s != 0
120 realloc(s, s<<1);
121 const int idx = s++;
122 if (QTypeInfo<T>::isComplex) {
123 new (ptr + idx) T(t);
124 } else {
125 ptr[idx] = t;
126 }
127 }
128 void append(const T *buf, int size);
129 inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
130 { append(t); return *this; }
131 inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
132 { append(t); return *this; }
133
134 void prepend(const T &t);
135 void insert(int i, const T &t);
136 void insert(int i, int n, const T &t);
137 void replace(int i, const T &t);
138 void remove(int i);
139 void remove(int i, int n);
140
141
142 inline T *data() { return ptr; }
143 inline const T *data() const { return ptr; }
144 inline const T * constData() const { return ptr; }
145 typedef int size_type;
146 typedef T value_type;
147 typedef value_type *pointer;
148 typedef const value_type *const_pointer;
149 typedef value_type &reference;
150 typedef const value_type &const_reference;
151 typedef qptrdiff difference_type;
152
153
154 typedef T* iterator;
155 typedef const T* const_iterator;
156
157 inline iterator begin() { return ptr; }
158 inline const_iterator begin() const { return ptr; }
159 inline const_iterator constBegin() const { return ptr; }
160 inline iterator end() { return ptr + s; }
161 inline const_iterator end() const { return ptr + s; }
162 inline const_iterator constEnd() const { return ptr + s; }
163 iterator insert(iterator before, int n, const T &x);
164 inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
165 iterator erase(iterator begin, iterator end);
166 inline iterator erase(iterator pos) { return erase(pos, pos+1); }
167
168private:
169 friend class QPodList<T, Prealloc>;
170 void realloc(int size, int alloc);
171
172 int a; // capacity
173 int s; // size
174 T *ptr; // data
175 union {
176 // ### Qt 5: Use 'Prealloc * sizeof(T)' as array size
177 char array[sizeof(qint64) * (((Prealloc * sizeof(T)) / sizeof(qint64)) + 1)];
178 qint64 q_for_alignment_1;
179 double q_for_alignment_2;
180 };
181};
182
183template <class T, int Prealloc>
184Q_INLINE_TEMPLATE QVarLengthArray<T, Prealloc>::QVarLengthArray(int asize)
185 : s(asize) {
186 if (s > Prealloc) {
187 ptr = reinterpret_cast<T *>(qMalloc(s * sizeof(T)));
188 Q_CHECK_PTR(ptr);
189 a = s;
190 } else {
191 ptr = reinterpret_cast<T *>(array);
192 a = Prealloc;
193 }
194 if (QTypeInfo<T>::isComplex) {
195 T *i = ptr + s;
196 while (i != ptr)
197 new (--i) T;
198 }
199}
200
201template <class T, int Prealloc>
202Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::resize(int asize)
203{ realloc(asize, qMax(asize, a)); }
204
205template <class T, int Prealloc>
206Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::reserve(int asize)
207{ if (asize > a) realloc(s, asize); }
208
209template <class T, int Prealloc>
210Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::append(const T *abuf, int increment)
211{
212 Q_ASSERT(abuf);
213 if (increment <= 0)
214 return;
215
216 const int asize = s + increment;
217
218 if (asize >= a)
219 realloc(s, qMax(s*2, asize));
220
221 if (QTypeInfo<T>::isComplex) {
222 // call constructor for new objects (which can throw)
223 while (s < asize)
224 new (ptr+(s++)) T(*abuf++);
225 } else {
226 qMemCopy(&ptr[s], abuf, increment * sizeof(T));
227 s = asize;
228 }
229}
230
231template <class T, int Prealloc>
232Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int aalloc)
233{
234 Q_ASSERT(aalloc >= asize);
235 T *oldPtr = ptr;
236 int osize = s;
237
238 const int copySize = qMin(asize, osize);
239 if (aalloc != a) {
240 ptr = reinterpret_cast<T *>(qMalloc(aalloc * sizeof(T)));
241 Q_CHECK_PTR(ptr);
242 if (ptr) {
243 s = 0;
244 a = aalloc;
245
246 if (QTypeInfo<T>::isStatic) {
247 QT_TRY {
248 // copy all the old elements
249 while (s < copySize) {
250 new (ptr+s) T(*(oldPtr+s));
251 (oldPtr+s)->~T();
252 s++;
253 }
254 } QT_CATCH(...) {
255 // clean up all the old objects and then free the old ptr
256 int sClean = s;
257 while (sClean < osize)
258 (oldPtr+(sClean++))->~T();
259 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
260 qFree(oldPtr);
261 QT_RETHROW;
262 }
263 } else {
264 qMemCopy(ptr, oldPtr, copySize * sizeof(T));
265 }
266 } else {
267 ptr = oldPtr;
268 return;
269 }
270 }
271 s = copySize;
272
273 if (QTypeInfo<T>::isComplex) {
274 // destroy remaining old objects
275 while (osize > asize)
276 (oldPtr+(--osize))->~T();
277 }
278
279 if (oldPtr != reinterpret_cast<T *>(array) && oldPtr != ptr)
280 qFree(oldPtr);
281
282 if (QTypeInfo<T>::isComplex) {
283 // call default constructor for new objects (which can throw)
284 while (s < asize)
285 new (ptr+(s++)) T;
286 } else {
287 s = asize;
288 }
289}
290
291template <class T, int Prealloc>
292Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i) const
293{
294 if (i < 0 || i >= size()) {
295 return T();
296 }
297 return at(i);
298}
299template <class T, int Prealloc>
300Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defaultValue) const
301{
302 return (i < 0 || i >= size()) ? defaultValue : at(i);
303}
304
305template <class T, int Prealloc>
306inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
307{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
308 insert(begin() + i, 1, t); }
309template <class T, int Prealloc>
310inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
311{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
312 insert(begin() + i, n, t); }
313template <class T, int Prealloc>
314inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
315{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
316 erase(begin() + i, begin() + i + n); }
317template <class T, int Prealloc>
318inline void QVarLengthArray<T, Prealloc>::remove(int i)
319{ Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
320 erase(begin() + i, begin() + i + 1); }
321template <class T, int Prealloc>
322inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
323{ insert(begin(), 1, t); }
324
325template <class T, int Prealloc>
326inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
327{
328 Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
329 const T copy(t);
330 data()[i] = copy;
331}
332
333
334template <class T, int Prealloc>
335Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(iterator before, size_type n, const T &t)
336{
337 int offset = int(before - ptr);
338 if (n != 0) {
339 resize(s + n);
340 const T copy(t);
341 if (QTypeInfo<T>::isStatic) {
342 T *b = ptr + offset;
343 T *j = ptr + s;
344 T *i = j - n;
345 while (i != b)
346 *--j = *--i;
347 i = b + n;
348 while (i != b)
349 *--i = copy;
350 } else {
351 T *b = ptr + offset;
352 T *i = b + n;
353 memmove(i, b, (s - offset - n) * sizeof(T));
354 while (i != b)
355 new (--i) T(copy);
356 }
357 }
358 return ptr + offset;
359}
360
361template <class T, int Prealloc>
362Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::erase(iterator abegin, iterator aend)
363{
364 int f = int(abegin - ptr);
365 int l = int(aend - ptr);
366 int n = l - f;
367 if (QTypeInfo<T>::isComplex) {
368 qCopy(ptr + l, ptr + s, ptr + f);
369 T *i = ptr + s;
370 T *b = ptr + s - n;
371 while (i != b) {
372 --i;
373 i->~T();
374 }
375 } else {
376 memmove(ptr + f, ptr + l, (s - l) * sizeof(T));
377 }
378 s -= n;
379 return ptr + f;
380}
381
382template <typename T, int Prealloc1, int Prealloc2>
383bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
384{
385 if (l.size() != r.size())
386 return false;
387 for (int i = 0; i < l.size(); i++) {
388 if (l.at(i) != r.at(i))
389 return false;
390 }
391 return true;
392}
393
394template <typename T, int Prealloc1, int Prealloc2>
395bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
396{
397 return !(l == r);
398}
399
400QT_END_NAMESPACE
401
402QT_END_HEADER
403
404#endif // QVARLENGTHARRAY_H
405