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 QVECTOR_H |
43 | #define QVECTOR_H |
44 | |
45 | #include <QtCore/qiterator.h> |
46 | #include <QtCore/qatomic.h> |
47 | #include <QtCore/qalgorithms.h> |
48 | #include <QtCore/qlist.h> |
49 | |
50 | #ifndef QT_NO_STL |
51 | #include <iterator> |
52 | #include <vector> |
53 | #endif |
54 | #include <stdlib.h> |
55 | #include <string.h> |
56 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
57 | #include <initializer_list> |
58 | #endif |
59 | |
60 | QT_BEGIN_HEADER |
61 | |
62 | QT_BEGIN_NAMESPACE |
63 | |
64 | QT_MODULE(Core) |
65 | |
66 | struct Q_CORE_EXPORT QVectorData |
67 | { |
68 | QBasicAtomicInt ref; |
69 | int alloc; |
70 | int size; |
71 | #if defined(QT_ARCH_SPARC) && defined(Q_CC_GNU) && defined(__LP64__) && defined(QT_BOOTSTRAPPED) |
72 | // workaround for bug in gcc 3.4.2 |
73 | uint sharable; |
74 | uint capacity; |
75 | uint reserved; |
76 | #else |
77 | uint sharable : 1; |
78 | uint capacity : 1; |
79 | uint reserved : 30; |
80 | #endif |
81 | |
82 | static QVectorData shared_null; |
83 | // ### Qt 5: rename to 'allocate()'. The current name causes problems for |
84 | // some debugges when the QVector is member of a class within an unnamed namespace. |
85 | // ### Qt 5: can be removed completely. (Ralf) |
86 | static QVectorData *malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init); |
87 | static QVectorData *allocate(int size, int alignment); |
88 | static QVectorData *reallocate(QVectorData *old, int newsize, int oldsize, int alignment); |
89 | static void free(QVectorData *data, int alignment); |
90 | static int grow(int sizeofTypedData, int size, int sizeofT, bool excessive); |
91 | }; |
92 | |
93 | template <typename T> |
94 | struct QVectorTypedData : private QVectorData |
95 | { // private inheritance as we must not access QVectorData member thought QVectorTypedData |
96 | // as this would break strict aliasing rules. (in the case of shared_null) |
97 | T array[1]; |
98 | |
99 | static inline void free(QVectorTypedData<T> *x, int alignment) { QVectorData::free(static_cast<QVectorData *>(x), alignment); } |
100 | }; |
101 | |
102 | class QRegion; |
103 | |
104 | template <typename T> |
105 | class QVector |
106 | { |
107 | typedef QVectorTypedData<T> Data; |
108 | union { |
109 | QVectorData *d; |
110 | #if defined(Q_CC_SUN) && (__SUNPRO_CC <= 0x550) |
111 | QVectorTypedData<T> *p; |
112 | #else |
113 | Data *p; |
114 | #endif |
115 | }; |
116 | |
117 | public: |
118 | // ### Qt 5: Consider making QVector non-shared to get at least one |
119 | // "really fast" container. See tests/benchmarks/corelib/tools/qvector/ |
120 | inline QVector() : d(&QVectorData::shared_null) { d->ref.ref(); } |
121 | explicit QVector(int size); |
122 | QVector(int size, const T &t); |
123 | inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
124 | inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(p); } |
125 | QVector<T> &operator=(const QVector<T> &v); |
126 | #ifdef Q_COMPILER_RVALUE_REFS |
127 | inline QVector<T> operator=(QVector<T> &&other) |
128 | { qSwap(p, other.p); return *this; } |
129 | #endif |
130 | inline void swap(QVector<T> &other) { qSwap(d, other.d); } |
131 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
132 | inline QVector(std::initializer_list<T> args); |
133 | #endif |
134 | bool operator==(const QVector<T> &v) const; |
135 | inline bool operator!=(const QVector<T> &v) const { return !(*this == v); } |
136 | |
137 | inline int size() const { return d->size; } |
138 | |
139 | inline bool isEmpty() const { return d->size == 0; } |
140 | |
141 | void resize(int size); |
142 | |
143 | inline int capacity() const { return d->alloc; } |
144 | void reserve(int size); |
145 | inline void squeeze() { realloc(d->size, d->size); d->capacity = 0; } |
146 | |
147 | inline void detach() { if (d->ref != 1) detach_helper(); } |
148 | inline bool isDetached() const { return d->ref == 1; } |
149 | inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
150 | inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; } |
151 | |
152 | inline T *data() { detach(); return p->array; } |
153 | inline const T *data() const { return p->array; } |
154 | inline const T *constData() const { return p->array; } |
155 | void clear(); |
156 | |
157 | const T &at(int i) const; |
158 | T &operator[](int i); |
159 | const T &operator[](int i) const; |
160 | void append(const T &t); |
161 | void prepend(const T &t); |
162 | void insert(int i, const T &t); |
163 | void insert(int i, int n, const T &t); |
164 | void replace(int i, const T &t); |
165 | void remove(int i); |
166 | void remove(int i, int n); |
167 | |
168 | QVector<T> &fill(const T &t, int size = -1); |
169 | |
170 | int indexOf(const T &t, int from = 0) const; |
171 | int lastIndexOf(const T &t, int from = -1) const; |
172 | bool contains(const T &t) const; |
173 | int count(const T &t) const; |
174 | |
175 | #ifdef QT_STRICT_ITERATORS |
176 | class iterator { |
177 | public: |
178 | T *i; |
179 | typedef std::random_access_iterator_tag iterator_category; |
180 | typedef qptrdiff difference_type; |
181 | typedef T value_type; |
182 | typedef T *pointer; |
183 | typedef T &reference; |
184 | |
185 | inline iterator() : i(0) {} |
186 | inline iterator(T *n) : i(n) {} |
187 | inline iterator(const iterator &o): i(o.i){} |
188 | inline T &operator*() const { return *i; } |
189 | inline T *operator->() const { return i; } |
190 | inline T &operator[](int j) const { return *(i + j); } |
191 | inline bool operator==(const iterator &o) const { return i == o.i; } |
192 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
193 | inline bool operator<(const iterator& other) const { return i < other.i; } |
194 | inline bool operator<=(const iterator& other) const { return i <= other.i; } |
195 | inline bool operator>(const iterator& other) const { return i > other.i; } |
196 | inline bool operator>=(const iterator& other) const { return i >= other.i; } |
197 | inline iterator &operator++() { ++i; return *this; } |
198 | inline iterator operator++(int) { T *n = i; ++i; return n; } |
199 | inline iterator &operator--() { i--; return *this; } |
200 | inline iterator operator--(int) { T *n = i; i--; return n; } |
201 | inline iterator &operator+=(int j) { i+=j; return *this; } |
202 | inline iterator &operator-=(int j) { i-=j; return *this; } |
203 | inline iterator operator+(int j) const { return iterator(i+j); } |
204 | inline iterator operator-(int j) const { return iterator(i-j); } |
205 | inline int operator-(iterator j) const { return i - j.i; } |
206 | }; |
207 | friend class iterator; |
208 | |
209 | class const_iterator { |
210 | public: |
211 | T *i; |
212 | typedef std::random_access_iterator_tag iterator_category; |
213 | typedef qptrdiff difference_type; |
214 | typedef T value_type; |
215 | typedef const T *pointer; |
216 | typedef const T &reference; |
217 | |
218 | inline const_iterator() : i(0) {} |
219 | inline const_iterator(T *n) : i(n) {} |
220 | inline const_iterator(const const_iterator &o): i(o.i) {} |
221 | inline explicit const_iterator(const iterator &o): i(o.i) {} |
222 | inline const T &operator*() const { return *i; } |
223 | inline const T *operator->() const { return i; } |
224 | inline const T &operator[](int j) const { return *(i + j); } |
225 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
226 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
227 | inline bool operator<(const const_iterator& other) const { return i < other.i; } |
228 | inline bool operator<=(const const_iterator& other) const { return i <= other.i; } |
229 | inline bool operator>(const const_iterator& other) const { return i > other.i; } |
230 | inline bool operator>=(const const_iterator& other) const { return i >= other.i; } |
231 | inline const_iterator &operator++() { ++i; return *this; } |
232 | inline const_iterator operator++(int) { T *n = i; ++i; return n; } |
233 | inline const_iterator &operator--() { i--; return *this; } |
234 | inline const_iterator operator--(int) { T *n = i; i--; return n; } |
235 | inline const_iterator &operator+=(int j) { i+=j; return *this; } |
236 | inline const_iterator &operator-=(int j) { i-=j; return *this; } |
237 | inline const_iterator operator+(int j) const { return const_iterator(i+j); } |
238 | inline const_iterator operator-(int j) const { return const_iterator(i-j); } |
239 | inline int operator-(const_iterator j) const { return i - j.i; } |
240 | }; |
241 | friend class const_iterator; |
242 | #else |
243 | // STL-style |
244 | typedef T* iterator; |
245 | typedef const T* const_iterator; |
246 | #endif |
247 | inline iterator begin() { detach(); return p->array; } |
248 | inline const_iterator begin() const { return p->array; } |
249 | inline const_iterator constBegin() const { return p->array; } |
250 | inline iterator end() { detach(); return p->array + d->size; } |
251 | inline const_iterator end() const { return p->array + d->size; } |
252 | inline const_iterator constEnd() const { return p->array + d->size; } |
253 | iterator insert(iterator before, int n, const T &x); |
254 | inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); } |
255 | iterator erase(iterator begin, iterator end); |
256 | inline iterator erase(iterator pos) { return erase(pos, pos+1); } |
257 | |
258 | // more Qt |
259 | inline int count() const { return d->size; } |
260 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } |
261 | inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); } |
262 | inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); } |
263 | inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); } |
264 | inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } |
265 | inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } |
266 | QVector<T> mid(int pos, int length = -1) const; |
267 | |
268 | T value(int i) const; |
269 | T value(int i, const T &defaultValue) const; |
270 | |
271 | // STL compatibility |
272 | typedef T value_type; |
273 | typedef value_type* pointer; |
274 | typedef const value_type* const_pointer; |
275 | typedef value_type& reference; |
276 | typedef const value_type& const_reference; |
277 | typedef qptrdiff difference_type; |
278 | typedef iterator Iterator; |
279 | typedef const_iterator ConstIterator; |
280 | typedef int size_type; |
281 | inline void push_back(const T &t) { append(t); } |
282 | inline void push_front(const T &t) { prepend(t); } |
283 | void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); } |
284 | void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); } |
285 | inline bool empty() const |
286 | { return d->size == 0; } |
287 | inline T& front() { return first(); } |
288 | inline const_reference front() const { return first(); } |
289 | inline reference back() { return last(); } |
290 | inline const_reference back() const { return last(); } |
291 | |
292 | // comfort |
293 | QVector<T> &operator+=(const QVector<T> &l); |
294 | inline QVector<T> operator+(const QVector<T> &l) const |
295 | { QVector n = *this; n += l; return n; } |
296 | inline QVector<T> &operator+=(const T &t) |
297 | { append(t); return *this; } |
298 | inline QVector<T> &operator<< (const T &t) |
299 | { append(t); return *this; } |
300 | inline QVector<T> &operator<<(const QVector<T> &l) |
301 | { *this += l; return *this; } |
302 | |
303 | QList<T> toList() const; |
304 | |
305 | static QVector<T> fromList(const QList<T> &list); |
306 | |
307 | #ifndef QT_NO_STL |
308 | static inline QVector<T> fromStdVector(const std::vector<T> &vector) |
309 | { QVector<T> tmp; tmp.reserve(int(vector.size())); qCopy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; } |
310 | inline std::vector<T> toStdVector() const |
311 | { std::vector<T> tmp; tmp.reserve(size()); qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; } |
312 | #endif |
313 | private: |
314 | friend class QRegion; // Optimization for QRegion::rects() |
315 | |
316 | void detach_helper(); |
317 | QVectorData *malloc(int alloc); |
318 | void realloc(int size, int alloc); |
319 | void free(Data *d); |
320 | int sizeOfTypedData() { |
321 | // this is more or less the same as sizeof(Data), except that it doesn't |
322 | // count the padding at the end |
323 | return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); |
324 | } |
325 | inline int alignOfTypedData() const |
326 | { |
327 | #ifdef Q_ALIGNOF |
328 | return qMax<int>(sizeof(void*), Q_ALIGNOF(Data)); |
329 | #else |
330 | return 0; |
331 | #endif |
332 | } |
333 | }; |
334 | |
335 | template <typename T> |
336 | void QVector<T>::detach_helper() |
337 | { realloc(d->size, d->alloc); } |
338 | template <typename T> |
339 | void QVector<T>::reserve(int asize) |
340 | { if (asize > d->alloc) realloc(d->size, asize); if (d->ref == 1) d->capacity = 1; } |
341 | template <typename T> |
342 | void QVector<T>::resize(int asize) |
343 | { realloc(asize, (asize > d->alloc || (!d->capacity && asize < d->size && asize < (d->alloc >> 1))) ? |
344 | QVectorData::grow(sizeOfTypedData(), asize, sizeof(T), QTypeInfo<T>::isStatic) |
345 | : d->alloc); } |
346 | template <typename T> |
347 | inline void QVector<T>::clear() |
348 | { *this = QVector<T>(); } |
349 | template <typename T> |
350 | inline const T &QVector<T>::at(int i) const |
351 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at" , "index out of range" ); |
352 | return p->array[i]; } |
353 | template <typename T> |
354 | inline const T &QVector<T>::operator[](int i) const |
355 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
356 | return p->array[i]; } |
357 | template <typename T> |
358 | inline T &QVector<T>::operator[](int i) |
359 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
360 | return data()[i]; } |
361 | template <typename T> |
362 | inline void QVector<T>::insert(int i, const T &t) |
363 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
364 | insert(begin() + i, 1, t); } |
365 | template <typename T> |
366 | inline void QVector<T>::insert(int i, int n, const T &t) |
367 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
368 | insert(begin() + i, n, t); } |
369 | template <typename T> |
370 | inline void QVector<T>::remove(int i, int n) |
371 | { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove" , "index out of range" ); |
372 | erase(begin() + i, begin() + i + n); } |
373 | template <typename T> |
374 | inline void QVector<T>::remove(int i) |
375 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove" , "index out of range" ); |
376 | erase(begin() + i, begin() + i + 1); } |
377 | template <typename T> |
378 | inline void QVector<T>::prepend(const T &t) |
379 | { insert(begin(), 1, t); } |
380 | |
381 | template <typename T> |
382 | inline void QVector<T>::replace(int i, const T &t) |
383 | { |
384 | Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace" , "index out of range" ); |
385 | const T copy(t); |
386 | data()[i] = copy; |
387 | } |
388 | |
389 | template <typename T> |
390 | QVector<T> &QVector<T>::operator=(const QVector<T> &v) |
391 | { |
392 | QVectorData *o = v.d; |
393 | o->ref.ref(); |
394 | if (!d->ref.deref()) |
395 | free(p); |
396 | d = o; |
397 | if (!d->sharable) |
398 | detach_helper(); |
399 | return *this; |
400 | } |
401 | |
402 | template <typename T> |
403 | inline QVectorData *QVector<T>::malloc(int aalloc) |
404 | { |
405 | QVectorData *vectordata = QVectorData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); |
406 | Q_CHECK_PTR(vectordata); |
407 | return vectordata; |
408 | } |
409 | |
410 | template <typename T> |
411 | QVector<T>::QVector(int asize) |
412 | { |
413 | d = malloc(asize); |
414 | d->ref = 1; |
415 | d->alloc = d->size = asize; |
416 | d->sharable = true; |
417 | d->capacity = false; |
418 | if (QTypeInfo<T>::isComplex) { |
419 | T* b = p->array; |
420 | T* i = p->array + d->size; |
421 | while (i != b) |
422 | new (--i) T; |
423 | } else { |
424 | qMemSet(p->array, 0, asize * sizeof(T)); |
425 | } |
426 | } |
427 | |
428 | template <typename T> |
429 | QVector<T>::QVector(int asize, const T &t) |
430 | { |
431 | d = malloc(asize); |
432 | d->ref = 1; |
433 | d->alloc = d->size = asize; |
434 | d->sharable = true; |
435 | d->capacity = false; |
436 | T* i = p->array + d->size; |
437 | while (i != p->array) |
438 | new (--i) T(t); |
439 | } |
440 | |
441 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
442 | template <typename T> |
443 | QVector<T>::QVector(std::initializer_list<T> args) |
444 | { |
445 | d = malloc(int(args.size())); |
446 | d->ref = 1; |
447 | d->alloc = d->size = int(args.size()); |
448 | d->sharable = true; |
449 | d->capacity = false; |
450 | T* i = p->array + d->size; |
451 | auto it = args.end(); |
452 | while (i != p->array) |
453 | new (--i) T(*(--it)); |
454 | } |
455 | #endif |
456 | |
457 | template <typename T> |
458 | void QVector<T>::free(Data *x) |
459 | { |
460 | if (QTypeInfo<T>::isComplex) { |
461 | T* b = x->array; |
462 | union { QVectorData *d; Data *p; } u; |
463 | u.p = x; |
464 | T* i = b + u.d->size; |
465 | while (i-- != b) |
466 | i->~T(); |
467 | } |
468 | x->free(x, alignOfTypedData()); |
469 | } |
470 | |
471 | template <typename T> |
472 | void QVector<T>::realloc(int asize, int aalloc) |
473 | { |
474 | Q_ASSERT(asize <= aalloc); |
475 | T *pOld; |
476 | T *pNew; |
477 | union { QVectorData *d; Data *p; } x; |
478 | x.d = d; |
479 | |
480 | if (QTypeInfo<T>::isComplex && asize < d->size && d->ref == 1 ) { |
481 | // call the destructor on all objects that need to be |
482 | // destroyed when shrinking |
483 | pOld = p->array + d->size; |
484 | pNew = p->array + asize; |
485 | while (asize < d->size) { |
486 | (--pOld)->~T(); |
487 | d->size--; |
488 | } |
489 | } |
490 | |
491 | if (aalloc != d->alloc || d->ref != 1) { |
492 | // (re)allocate memory |
493 | if (QTypeInfo<T>::isStatic) { |
494 | x.d = malloc(aalloc); |
495 | Q_CHECK_PTR(x.p); |
496 | x.d->size = 0; |
497 | } else if (d->ref != 1) { |
498 | x.d = malloc(aalloc); |
499 | Q_CHECK_PTR(x.p); |
500 | if (QTypeInfo<T>::isComplex) { |
501 | x.d->size = 0; |
502 | } else { |
503 | ::memcpy(x.p, p, sizeOfTypedData() + (qMin(aalloc, d->alloc) - 1) * sizeof(T)); |
504 | x.d->size = d->size; |
505 | } |
506 | } else { |
507 | QT_TRY { |
508 | QVectorData *mem = QVectorData::reallocate(d, sizeOfTypedData() + (aalloc - 1) * sizeof(T), |
509 | sizeOfTypedData() + (d->alloc - 1) * sizeof(T), alignOfTypedData()); |
510 | Q_CHECK_PTR(mem); |
511 | x.d = d = mem; |
512 | x.d->size = d->size; |
513 | } QT_CATCH (const std::bad_alloc &) { |
514 | if (aalloc > d->alloc) // ignore the error in case we are just shrinking. |
515 | QT_RETHROW; |
516 | } |
517 | } |
518 | x.d->ref = 1; |
519 | x.d->alloc = aalloc; |
520 | x.d->sharable = true; |
521 | x.d->capacity = d->capacity; |
522 | x.d->reserved = 0; |
523 | } |
524 | |
525 | if (QTypeInfo<T>::isComplex) { |
526 | QT_TRY { |
527 | pOld = p->array + x.d->size; |
528 | pNew = x.p->array + x.d->size; |
529 | // copy objects from the old array into the new array |
530 | const int toMove = qMin(asize, d->size); |
531 | while (x.d->size < toMove) { |
532 | new (pNew++) T(*pOld++); |
533 | x.d->size++; |
534 | } |
535 | // construct all new objects when growing |
536 | while (x.d->size < asize) { |
537 | new (pNew++) T; |
538 | x.d->size++; |
539 | } |
540 | } QT_CATCH (...) { |
541 | free(x.p); |
542 | QT_RETHROW; |
543 | } |
544 | |
545 | } else if (asize > x.d->size) { |
546 | // initialize newly allocated memory to 0 |
547 | qMemSet(x.p->array + x.d->size, 0, (asize - x.d->size) * sizeof(T)); |
548 | } |
549 | x.d->size = asize; |
550 | |
551 | if (d != x.d) { |
552 | if (!d->ref.deref()) |
553 | free(p); |
554 | d = x.d; |
555 | } |
556 | } |
557 | |
558 | template<typename T> |
559 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const |
560 | { |
561 | if (i < 0 || i >= d->size) { |
562 | return T(); |
563 | } |
564 | return p->array[i]; |
565 | } |
566 | template<typename T> |
567 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const |
568 | { |
569 | return ((i < 0 || i >= d->size) ? defaultValue : p->array[i]); |
570 | } |
571 | |
572 | template <typename T> |
573 | void QVector<T>::append(const T &t) |
574 | { |
575 | if (d->ref != 1 || d->size + 1 > d->alloc) { |
576 | const T copy(t); |
577 | realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T), |
578 | QTypeInfo<T>::isStatic)); |
579 | if (QTypeInfo<T>::isComplex) |
580 | new (p->array + d->size) T(copy); |
581 | else |
582 | p->array[d->size] = copy; |
583 | } else { |
584 | if (QTypeInfo<T>::isComplex) |
585 | new (p->array + d->size) T(t); |
586 | else |
587 | p->array[d->size] = t; |
588 | } |
589 | ++d->size; |
590 | } |
591 | |
592 | template <typename T> |
593 | Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t) |
594 | { |
595 | int offset = int(before - p->array); |
596 | if (n != 0) { |
597 | const T copy(t); |
598 | if (d->ref != 1 || d->size + n > d->alloc) |
599 | realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T), |
600 | QTypeInfo<T>::isStatic)); |
601 | if (QTypeInfo<T>::isStatic) { |
602 | T *b = p->array + d->size; |
603 | T *i = p->array + d->size + n; |
604 | while (i != b) |
605 | new (--i) T; |
606 | i = p->array + d->size; |
607 | T *j = i + n; |
608 | b = p->array + offset; |
609 | while (i != b) |
610 | *--j = *--i; |
611 | i = b+n; |
612 | while (i != b) |
613 | *--i = copy; |
614 | } else { |
615 | T *b = p->array + offset; |
616 | T *i = b + n; |
617 | memmove(i, b, (d->size - offset) * sizeof(T)); |
618 | while (i != b) |
619 | new (--i) T(copy); |
620 | } |
621 | d->size += n; |
622 | } |
623 | return p->array + offset; |
624 | } |
625 | |
626 | template <typename T> |
627 | Q_TYPENAME QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend) |
628 | { |
629 | int f = int(abegin - p->array); |
630 | int l = int(aend - p->array); |
631 | int n = l - f; |
632 | detach(); |
633 | if (QTypeInfo<T>::isComplex) { |
634 | qCopy(p->array+l, p->array+d->size, p->array+f); |
635 | T *i = p->array+d->size; |
636 | T* b = p->array+d->size-n; |
637 | while (i != b) { |
638 | --i; |
639 | i->~T(); |
640 | } |
641 | } else { |
642 | memmove(p->array + f, p->array + l, (d->size-l)*sizeof(T)); |
643 | } |
644 | d->size -= n; |
645 | return p->array + f; |
646 | } |
647 | |
648 | template <typename T> |
649 | bool QVector<T>::operator==(const QVector<T> &v) const |
650 | { |
651 | if (d->size != v.d->size) |
652 | return false; |
653 | if (d == v.d) |
654 | return true; |
655 | T* b = p->array; |
656 | T* i = b + d->size; |
657 | T* j = v.p->array + d->size; |
658 | while (i != b) |
659 | if (!(*--i == *--j)) |
660 | return false; |
661 | return true; |
662 | } |
663 | |
664 | template <typename T> |
665 | QVector<T> &QVector<T>::fill(const T &from, int asize) |
666 | { |
667 | const T copy(from); |
668 | resize(asize < 0 ? d->size : asize); |
669 | if (d->size) { |
670 | T *i = p->array + d->size; |
671 | T *b = p->array; |
672 | while (i != b) |
673 | *--i = copy; |
674 | } |
675 | return *this; |
676 | } |
677 | |
678 | template <typename T> |
679 | QVector<T> &QVector<T>::operator+=(const QVector &l) |
680 | { |
681 | int newSize = d->size + l.d->size; |
682 | realloc(d->size, newSize); |
683 | |
684 | T *w = p->array + newSize; |
685 | T *i = l.p->array + l.d->size; |
686 | T *b = l.p->array; |
687 | while (i != b) { |
688 | if (QTypeInfo<T>::isComplex) |
689 | new (--w) T(*--i); |
690 | else |
691 | *--w = *--i; |
692 | } |
693 | d->size = newSize; |
694 | return *this; |
695 | } |
696 | |
697 | template <typename T> |
698 | int QVector<T>::indexOf(const T &t, int from) const |
699 | { |
700 | if (from < 0) |
701 | from = qMax(from + d->size, 0); |
702 | if (from < d->size) { |
703 | T* n = p->array + from - 1; |
704 | T* e = p->array + d->size; |
705 | while (++n != e) |
706 | if (*n == t) |
707 | return n - p->array; |
708 | } |
709 | return -1; |
710 | } |
711 | |
712 | template <typename T> |
713 | int QVector<T>::lastIndexOf(const T &t, int from) const |
714 | { |
715 | if (from < 0) |
716 | from += d->size; |
717 | else if (from >= d->size) |
718 | from = d->size-1; |
719 | if (from >= 0) { |
720 | T* b = p->array; |
721 | T* n = p->array + from + 1; |
722 | while (n != b) { |
723 | if (*--n == t) |
724 | return n - b; |
725 | } |
726 | } |
727 | return -1; |
728 | } |
729 | |
730 | template <typename T> |
731 | bool QVector<T>::contains(const T &t) const |
732 | { |
733 | T* b = p->array; |
734 | T* i = p->array + d->size; |
735 | while (i != b) |
736 | if (*--i == t) |
737 | return true; |
738 | return false; |
739 | } |
740 | |
741 | template <typename T> |
742 | int QVector<T>::count(const T &t) const |
743 | { |
744 | int c = 0; |
745 | T* b = p->array; |
746 | T* i = p->array + d->size; |
747 | while (i != b) |
748 | if (*--i == t) |
749 | ++c; |
750 | return c; |
751 | } |
752 | |
753 | template <typename T> |
754 | Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int length) const |
755 | { |
756 | if (length < 0) |
757 | length = size() - pos; |
758 | if (pos == 0 && length == size()) |
759 | return *this; |
760 | if (pos + length > size()) |
761 | length = size() - pos; |
762 | QVector<T> copy; |
763 | copy.reserve(length); |
764 | for (int i = pos; i < pos + length; ++i) |
765 | copy += at(i); |
766 | return copy; |
767 | } |
768 | |
769 | template <typename T> |
770 | Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const |
771 | { |
772 | QList<T> result; |
773 | result.reserve(size()); |
774 | for (int i = 0; i < size(); ++i) |
775 | result.append(at(i)); |
776 | return result; |
777 | } |
778 | |
779 | template <typename T> |
780 | Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const |
781 | { |
782 | QVector<T> result(size()); |
783 | for (int i = 0; i < size(); ++i) |
784 | result[i] = at(i); |
785 | return result; |
786 | } |
787 | |
788 | template <typename T> |
789 | QVector<T> QVector<T>::fromList(const QList<T> &list) |
790 | { |
791 | return list.toVector(); |
792 | } |
793 | |
794 | template <typename T> |
795 | QList<T> QList<T>::fromVector(const QVector<T> &vector) |
796 | { |
797 | return vector.toList(); |
798 | } |
799 | |
800 | Q_DECLARE_SEQUENTIAL_ITERATOR(Vector) |
801 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector) |
802 | |
803 | /* |
804 | ### Qt 5: |
805 | ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because |
806 | ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and |
807 | ### QVector<QPointF> respectively. |
808 | */ |
809 | |
810 | #ifdef Q_CC_MSVC |
811 | QT_BEGIN_INCLUDE_NAMESPACE |
812 | #include <QtCore/QPointF> |
813 | #include <QtCore/QPoint> |
814 | QT_END_INCLUDE_NAMESPACE |
815 | |
816 | #if defined(QT_BUILD_CORE_LIB) |
817 | #define Q_TEMPLATE_EXTERN |
818 | #else |
819 | #define Q_TEMPLATE_EXTERN extern |
820 | #endif |
821 | Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPointF>; |
822 | Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPoint>; |
823 | #endif |
824 | |
825 | QT_END_NAMESPACE |
826 | |
827 | QT_END_HEADER |
828 | |
829 | #endif // QVECTOR_H |
830 | |