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 | |
52 | QT_BEGIN_HEADER |
53 | |
54 | QT_BEGIN_NAMESPACE |
55 | |
56 | QT_MODULE(Core) |
57 | |
58 | template<class T, int Prealloc> |
59 | class QPodList; |
60 | |
61 | // Prealloc = 256 by default, specified in qcontainerfwd.h |
62 | template<class T, int Prealloc> |
63 | class QVarLengthArray |
64 | { |
65 | public: |
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 | |
168 | private: |
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 | |
183 | template <class T, int Prealloc> |
184 | Q_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 | |
201 | template <class T, int Prealloc> |
202 | Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::resize(int asize) |
203 | { realloc(asize, qMax(asize, a)); } |
204 | |
205 | template <class T, int Prealloc> |
206 | Q_INLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::reserve(int asize) |
207 | { if (asize > a) realloc(s, asize); } |
208 | |
209 | template <class T, int Prealloc> |
210 | Q_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 | |
231 | template <class T, int Prealloc> |
232 | Q_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 | |
291 | template <class T, int Prealloc> |
292 | Q_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 | } |
299 | template <class T, int Prealloc> |
300 | Q_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 | |
305 | template <class T, int Prealloc> |
306 | inline 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); } |
309 | template <class T, int Prealloc> |
310 | inline 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); } |
313 | template <class T, int Prealloc> |
314 | inline 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); } |
317 | template <class T, int Prealloc> |
318 | inline 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); } |
321 | template <class T, int Prealloc> |
322 | inline void QVarLengthArray<T, Prealloc>::prepend(const T &t) |
323 | { insert(begin(), 1, t); } |
324 | |
325 | template <class T, int Prealloc> |
326 | inline 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 | |
334 | template <class T, int Prealloc> |
335 | Q_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 | |
361 | template <class T, int Prealloc> |
362 | Q_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 | |
382 | template <typename T, int Prealloc1, int Prealloc2> |
383 | bool 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 | |
394 | template <typename T, int Prealloc1, int Prealloc2> |
395 | bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r) |
396 | { |
397 | return !(l == r); |
398 | } |
399 | |
400 | QT_END_NAMESPACE |
401 | |
402 | QT_END_HEADER |
403 | |
404 | #endif // QVARLENGTHARRAY_H |
405 | |