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 QVECTOR_H |
41 | #define QVECTOR_H |
42 | |
43 | #include <QtCore/qalgorithms.h> |
44 | #include <QtCore/qiterator.h> |
45 | #include <QtCore/qlist.h> |
46 | #include <QtCore/qrefcount.h> |
47 | #include <QtCore/qarraydata.h> |
48 | #include <QtCore/qhashfunctions.h> |
49 | |
50 | #include <iterator> |
51 | #include <vector> |
52 | #include <stdlib.h> |
53 | #include <string.h> |
54 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
55 | #include <initializer_list> |
56 | #endif |
57 | |
58 | #include <algorithm> |
59 | |
60 | QT_BEGIN_NAMESPACE |
61 | |
62 | template <typename T> |
63 | class QVector |
64 | { |
65 | typedef QTypedArrayData<T> Data; |
66 | Data *d; |
67 | |
68 | public: |
69 | inline QVector() Q_DECL_NOTHROW : d(Data::sharedNull()) { } |
70 | explicit QVector(int size); |
71 | QVector(int size, const T &t); |
72 | inline QVector(const QVector<T> &v); |
73 | inline ~QVector() { if (!d->ref.deref()) freeData(d); } |
74 | QVector<T> &operator=(const QVector<T> &v); |
75 | #if defined(Q_COMPILER_RVALUE_REFS) || defined(Q_CLANG_QDOC) |
76 | QVector(QVector<T> &&other) Q_DECL_NOTHROW : d(other.d) { other.d = Data::sharedNull(); } |
77 | QVector<T> &operator=(QVector<T> &&other) Q_DECL_NOTHROW |
78 | { QVector moved(std::move(other)); swap(moved); return *this; } |
79 | #endif |
80 | void swap(QVector<T> &other) Q_DECL_NOTHROW { qSwap(d, other.d); } |
81 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
82 | inline QVector(std::initializer_list<T> args); |
83 | #endif |
84 | bool operator==(const QVector<T> &v) const; |
85 | inline bool operator!=(const QVector<T> &v) const { return !(*this == v); } |
86 | |
87 | inline int size() const { return d->size; } |
88 | |
89 | inline bool isEmpty() const { return d->size == 0; } |
90 | |
91 | void resize(int size); |
92 | |
93 | inline int capacity() const { return int(d->alloc); } |
94 | void reserve(int size); |
95 | inline void squeeze() |
96 | { |
97 | reallocData(d->size, d->size); |
98 | if (d->capacityReserved) { |
99 | // capacity reserved in a read only memory would be useless |
100 | // this checks avoid writing to such memory. |
101 | d->capacityReserved = 0; |
102 | } |
103 | } |
104 | |
105 | inline void detach(); |
106 | inline bool isDetached() const { return !d->ref.isShared(); } |
107 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
108 | inline void setSharable(bool sharable) |
109 | { |
110 | if (sharable == d->ref.isSharable()) |
111 | return; |
112 | if (!sharable) |
113 | detach(); |
114 | |
115 | if (d == Data::unsharableEmpty()) { |
116 | if (sharable) |
117 | d = Data::sharedNull(); |
118 | } else { |
119 | d->ref.setSharable(sharable); |
120 | } |
121 | Q_ASSERT(d->ref.isSharable() == sharable); |
122 | } |
123 | #endif |
124 | |
125 | inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; } |
126 | |
127 | inline T *data() { detach(); return d->begin(); } |
128 | inline const T *data() const { return d->begin(); } |
129 | inline const T *constData() const { return d->begin(); } |
130 | void clear(); |
131 | |
132 | const T &at(int i) const; |
133 | T &operator[](int i); |
134 | const T &operator[](int i) const; |
135 | void append(const T &t); |
136 | #if defined(Q_COMPILER_RVALUE_REFS) || defined(Q_CLANG_QDOC) |
137 | void append(T &&t); |
138 | #endif |
139 | inline void append(const QVector<T> &l) { *this += l; } |
140 | void prepend(T &&t); |
141 | void prepend(const T &t); |
142 | void insert(int i, T &&t); |
143 | void insert(int i, const T &t); |
144 | void insert(int i, int n, const T &t); |
145 | void replace(int i, const T &t); |
146 | void remove(int i); |
147 | void remove(int i, int n); |
148 | inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); } |
149 | inline void removeLast(); |
150 | T takeFirst() { Q_ASSERT(!isEmpty()); T r = std::move(first()); removeFirst(); return r; } |
151 | T takeLast() { Q_ASSERT(!isEmpty()); T r = std::move(last()); removeLast(); return r; } |
152 | |
153 | QVector<T> &fill(const T &t, int size = -1); |
154 | |
155 | int indexOf(const T &t, int from = 0) const; |
156 | int lastIndexOf(const T &t, int from = -1) const; |
157 | bool contains(const T &t) const; |
158 | int count(const T &t) const; |
159 | |
160 | // QList compatibility |
161 | void removeAt(int i) { remove(i); } |
162 | int removeAll(const T &t) |
163 | { |
164 | const const_iterator ce = this->cend(), cit = std::find(this->cbegin(), ce, t); |
165 | if (cit == ce) |
166 | return 0; |
167 | // next operation detaches, so ce, cit, t may become invalidated: |
168 | const T tCopy = t; |
169 | const int firstFoundIdx = std::distance(this->cbegin(), cit); |
170 | const iterator e = end(), it = std::remove(begin() + firstFoundIdx, e, tCopy); |
171 | const int result = std::distance(it, e); |
172 | erase(it, e); |
173 | return result; |
174 | } |
175 | bool removeOne(const T &t) |
176 | { |
177 | const int i = indexOf(t); |
178 | if (i < 0) |
179 | return false; |
180 | remove(i); |
181 | return true; |
182 | } |
183 | int length() const { return size(); } |
184 | T takeAt(int i) { T t = std::move((*this)[i]); remove(i); return t; } |
185 | void move(int from, int to) |
186 | { |
187 | Q_ASSERT_X(from >= 0 && from < size(), "QVector::move(int,int)" , "'from' is out-of-range" ); |
188 | Q_ASSERT_X(to >= 0 && to < size(), "QVector::move(int,int)" , "'to' is out-of-range" ); |
189 | if (from == to) // don't detach when no-op |
190 | return; |
191 | detach(); |
192 | T * const b = d->begin(); |
193 | if (from < to) |
194 | std::rotate(b + from, b + from + 1, b + to + 1); |
195 | else |
196 | std::rotate(b + to, b + from, b + from + 1); |
197 | } |
198 | |
199 | // STL-style |
200 | typedef typename Data::iterator iterator; |
201 | typedef typename Data::const_iterator const_iterator; |
202 | typedef std::reverse_iterator<iterator> reverse_iterator; |
203 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
204 | #if !defined(QT_STRICT_ITERATORS) || defined(Q_CLANG_QDOC) |
205 | inline iterator begin() { detach(); return d->begin(); } |
206 | inline const_iterator begin() const Q_DECL_NOTHROW { return d->constBegin(); } |
207 | inline const_iterator cbegin() const Q_DECL_NOTHROW { return d->constBegin(); } |
208 | inline const_iterator constBegin() const Q_DECL_NOTHROW { return d->constBegin(); } |
209 | inline iterator end() { detach(); return d->end(); } |
210 | inline const_iterator end() const Q_DECL_NOTHROW { return d->constEnd(); } |
211 | inline const_iterator cend() const Q_DECL_NOTHROW { return d->constEnd(); } |
212 | inline const_iterator constEnd() const Q_DECL_NOTHROW { return d->constEnd(); } |
213 | #else |
214 | inline iterator begin(iterator = iterator()) { detach(); return d->begin(); } |
215 | inline const_iterator begin(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constBegin(); } |
216 | inline const_iterator cbegin(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constBegin(); } |
217 | inline const_iterator constBegin(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constBegin(); } |
218 | inline iterator end(iterator = iterator()) { detach(); return d->end(); } |
219 | inline const_iterator end(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constEnd(); } |
220 | inline const_iterator cend(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constEnd(); } |
221 | inline const_iterator constEnd(const_iterator = const_iterator()) const Q_DECL_NOTHROW { return d->constEnd(); } |
222 | #endif |
223 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
224 | reverse_iterator rend() { return reverse_iterator(begin()); } |
225 | const_reverse_iterator rbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); } |
226 | const_reverse_iterator rend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); } |
227 | const_reverse_iterator crbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); } |
228 | const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); } |
229 | iterator insert(iterator before, int n, const T &x); |
230 | inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); } |
231 | inline iterator insert(iterator before, T &&x); |
232 | iterator erase(iterator begin, iterator end); |
233 | inline iterator erase(iterator pos) { return erase(pos, pos+1); } |
234 | |
235 | // more Qt |
236 | inline int count() const { return d->size; } |
237 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } |
238 | inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); } |
239 | inline const T &constFirst() const { Q_ASSERT(!isEmpty()); return *begin(); } |
240 | inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); } |
241 | inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); } |
242 | inline const T &constLast() const { Q_ASSERT(!isEmpty()); return *(end()-1); } |
243 | inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } |
244 | inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } |
245 | QVector<T> mid(int pos, int len = -1) const; |
246 | |
247 | T value(int i) const; |
248 | T value(int i, const T &defaultValue) const; |
249 | |
250 | // STL compatibility |
251 | typedef T value_type; |
252 | typedef value_type* pointer; |
253 | typedef const value_type* const_pointer; |
254 | typedef value_type& reference; |
255 | typedef const value_type& const_reference; |
256 | typedef qptrdiff difference_type; |
257 | typedef iterator Iterator; |
258 | typedef const_iterator ConstIterator; |
259 | typedef int size_type; |
260 | inline void push_back(const T &t) { append(t); } |
261 | #if defined(Q_COMPILER_RVALUE_REFS) || defined(Q_CLANG_QDOC) |
262 | void push_back(T &&t) { append(std::move(t)); } |
263 | void push_front(T &&t) { prepend(std::move(t)); } |
264 | #endif |
265 | inline void push_front(const T &t) { prepend(t); } |
266 | void pop_back() { removeLast(); } |
267 | void pop_front() { removeFirst(); } |
268 | inline bool empty() const |
269 | { return d->size == 0; } |
270 | inline T& front() { return first(); } |
271 | inline const_reference front() const { return first(); } |
272 | inline reference back() { return last(); } |
273 | inline const_reference back() const { return last(); } |
274 | void shrink_to_fit() { squeeze(); } |
275 | |
276 | // comfort |
277 | QVector<T> &operator+=(const QVector<T> &l); |
278 | inline QVector<T> operator+(const QVector<T> &l) const |
279 | { QVector n = *this; n += l; return n; } |
280 | inline QVector<T> &operator+=(const T &t) |
281 | { append(t); return *this; } |
282 | inline QVector<T> &operator<< (const T &t) |
283 | { append(t); return *this; } |
284 | inline QVector<T> &operator<<(const QVector<T> &l) |
285 | { *this += l; return *this; } |
286 | inline QVector<T> &operator+=(T &&t) |
287 | { append(std::move(t)); return *this; } |
288 | inline QVector<T> &operator<<(T &&t) |
289 | { append(std::move(t)); return *this; } |
290 | |
291 | QList<T> toList() const; |
292 | |
293 | static QVector<T> fromList(const QList<T> &list); |
294 | |
295 | static inline QVector<T> fromStdVector(const std::vector<T> &vector) |
296 | { QVector<T> tmp; tmp.reserve(int(vector.size())); std::copy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; } |
297 | inline std::vector<T> toStdVector() const |
298 | { return std::vector<T>(d->begin(), d->end()); } |
299 | private: |
300 | // ### Qt6: remove const from int parameters |
301 | void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default); |
302 | void reallocData(const int sz) { reallocData(sz, d->alloc); } |
303 | void freeData(Data *d); |
304 | void defaultConstruct(T *from, T *to); |
305 | void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom); |
306 | void destruct(T *from, T *to); |
307 | bool isValidIterator(const iterator &i) const |
308 | { |
309 | const std::less<const T*> less = {}; |
310 | return !less(d->end(), i) && !less(i, d->begin()); |
311 | } |
312 | class AlignmentDummy { Data ; T array[1]; }; |
313 | }; |
314 | |
315 | #ifdef Q_CC_MSVC |
316 | // behavior change: an object of POD type constructed with an initializer of the form () |
317 | // will be default-initialized |
318 | # pragma warning ( push ) |
319 | # pragma warning ( disable : 4345 ) |
320 | # pragma warning(disable : 4127) // conditional expression is constant |
321 | #endif |
322 | |
323 | template <typename T> |
324 | void QVector<T>::defaultConstruct(T *from, T *to) |
325 | { |
326 | if (QTypeInfo<T>::isComplex) { |
327 | while (from != to) { |
328 | new (from++) T(); |
329 | } |
330 | } else { |
331 | ::memset(static_cast<void *>(from), 0, (to - from) * sizeof(T)); |
332 | } |
333 | } |
334 | |
335 | template <typename T> |
336 | void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom) |
337 | { |
338 | if (QTypeInfo<T>::isComplex) { |
339 | while (srcFrom != srcTo) |
340 | new (dstFrom++) T(*srcFrom++); |
341 | } else { |
342 | ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T)); |
343 | } |
344 | } |
345 | |
346 | template <typename T> |
347 | void QVector<T>::destruct(T *from, T *to) |
348 | { |
349 | if (QTypeInfo<T>::isComplex) { |
350 | while (from != to) { |
351 | from++->~T(); |
352 | } |
353 | } |
354 | } |
355 | |
356 | template <typename T> |
357 | inline QVector<T>::QVector(const QVector<T> &v) |
358 | { |
359 | if (v.d->ref.ref()) { |
360 | d = v.d; |
361 | } else { |
362 | if (v.d->capacityReserved) { |
363 | d = Data::allocate(v.d->alloc); |
364 | Q_CHECK_PTR(d); |
365 | d->capacityReserved = true; |
366 | } else { |
367 | d = Data::allocate(v.d->size); |
368 | Q_CHECK_PTR(d); |
369 | } |
370 | if (d->alloc) { |
371 | copyConstruct(v.d->begin(), v.d->end(), d->begin()); |
372 | d->size = v.d->size; |
373 | } |
374 | } |
375 | } |
376 | |
377 | #if defined(Q_CC_MSVC) |
378 | #pragma warning( pop ) |
379 | #endif |
380 | |
381 | template <typename T> |
382 | void QVector<T>::detach() |
383 | { |
384 | if (!isDetached()) { |
385 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
386 | if (!d->alloc) |
387 | d = Data::unsharableEmpty(); |
388 | else |
389 | #endif |
390 | reallocData(d->size, int(d->alloc)); |
391 | } |
392 | Q_ASSERT(isDetached()); |
393 | } |
394 | |
395 | template <typename T> |
396 | void QVector<T>::reserve(int asize) |
397 | { |
398 | if (asize > int(d->alloc)) |
399 | reallocData(d->size, asize); |
400 | if (isDetached() |
401 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
402 | && d != Data::unsharableEmpty() |
403 | #endif |
404 | ) |
405 | d->capacityReserved = 1; |
406 | Q_ASSERT(capacity() >= asize); |
407 | } |
408 | |
409 | template <typename T> |
410 | void QVector<T>::resize(int asize) |
411 | { |
412 | int newAlloc; |
413 | const int oldAlloc = int(d->alloc); |
414 | QArrayData::AllocationOptions opt; |
415 | |
416 | if (asize > oldAlloc) { // there is not enough space |
417 | newAlloc = asize; |
418 | opt = QArrayData::Grow; |
419 | } else { |
420 | newAlloc = oldAlloc; |
421 | } |
422 | reallocData(asize, newAlloc, opt); |
423 | } |
424 | template <typename T> |
425 | inline void QVector<T>::clear() |
426 | { resize(0); } |
427 | template <typename T> |
428 | inline const T &QVector<T>::at(int i) const |
429 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at" , "index out of range" ); |
430 | return d->begin()[i]; } |
431 | template <typename T> |
432 | inline const T &QVector<T>::operator[](int i) const |
433 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
434 | return d->begin()[i]; } |
435 | template <typename T> |
436 | inline T &QVector<T>::operator[](int i) |
437 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
438 | return data()[i]; } |
439 | template <typename T> |
440 | inline void QVector<T>::insert(int i, const T &t) |
441 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
442 | insert(begin() + i, 1, t); } |
443 | template <typename T> |
444 | inline void QVector<T>::insert(int i, int n, const T &t) |
445 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
446 | insert(begin() + i, n, t); } |
447 | template <typename T> |
448 | inline void QVector<T>::insert(int i, T &&t) |
449 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
450 | insert(begin() + i, std::move(t)); } |
451 | template <typename T> |
452 | inline void QVector<T>::remove(int i, int n) |
453 | { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove" , "index out of range" ); |
454 | erase(d->begin() + i, d->begin() + i + n); } |
455 | template <typename T> |
456 | inline void QVector<T>::remove(int i) |
457 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove" , "index out of range" ); |
458 | erase(d->begin() + i, d->begin() + i + 1); } |
459 | template <typename T> |
460 | inline void QVector<T>::prepend(const T &t) |
461 | { insert(begin(), 1, t); } |
462 | template <typename T> |
463 | inline void QVector<T>::prepend(T &&t) |
464 | { insert(begin(), std::move(t)); } |
465 | |
466 | template <typename T> |
467 | inline void QVector<T>::replace(int i, const T &t) |
468 | { |
469 | Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace" , "index out of range" ); |
470 | const T copy(t); |
471 | data()[i] = copy; |
472 | } |
473 | |
474 | template <typename T> |
475 | QVector<T> &QVector<T>::operator=(const QVector<T> &v) |
476 | { |
477 | if (v.d != d) { |
478 | QVector<T> tmp(v); |
479 | tmp.swap(*this); |
480 | } |
481 | return *this; |
482 | } |
483 | |
484 | template <typename T> |
485 | QVector<T>::QVector(int asize) |
486 | { |
487 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
488 | if (Q_LIKELY(asize > 0)) { |
489 | d = Data::allocate(asize); |
490 | Q_CHECK_PTR(d); |
491 | d->size = asize; |
492 | defaultConstruct(d->begin(), d->end()); |
493 | } else { |
494 | d = Data::sharedNull(); |
495 | } |
496 | } |
497 | |
498 | template <typename T> |
499 | QVector<T>::QVector(int asize, const T &t) |
500 | { |
501 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
502 | if (asize > 0) { |
503 | d = Data::allocate(asize); |
504 | Q_CHECK_PTR(d); |
505 | d->size = asize; |
506 | T* i = d->end(); |
507 | while (i != d->begin()) |
508 | new (--i) T(t); |
509 | } else { |
510 | d = Data::sharedNull(); |
511 | } |
512 | } |
513 | |
514 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
515 | # if defined(Q_CC_MSVC) |
516 | QT_WARNING_PUSH |
517 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
518 | # endif // Q_CC_MSVC |
519 | |
520 | template <typename T> |
521 | QVector<T>::QVector(std::initializer_list<T> args) |
522 | { |
523 | if (args.size() > 0) { |
524 | d = Data::allocate(args.size()); |
525 | Q_CHECK_PTR(d); |
526 | // std::initializer_list<T>::iterator is guaranteed to be |
527 | // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct |
528 | copyConstruct(args.begin(), args.end(), d->begin()); |
529 | d->size = int(args.size()); |
530 | } else { |
531 | d = Data::sharedNull(); |
532 | } |
533 | } |
534 | # if defined(Q_CC_MSVC) |
535 | QT_WARNING_POP |
536 | # endif // Q_CC_MSVC |
537 | #endif // Q_COMPILER_INITALIZER_LISTS |
538 | |
539 | template <typename T> |
540 | void QVector<T>::freeData(Data *x) |
541 | { |
542 | destruct(x->begin(), x->end()); |
543 | Data::deallocate(x); |
544 | } |
545 | |
546 | #if defined(Q_CC_MSVC) |
547 | QT_WARNING_PUSH |
548 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
549 | #endif |
550 | |
551 | template <typename T> |
552 | void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options) |
553 | { |
554 | Q_ASSERT(asize >= 0 && asize <= aalloc); |
555 | Data *x = d; |
556 | |
557 | const bool isShared = d->ref.isShared(); |
558 | |
559 | if (aalloc != 0) { |
560 | if (aalloc != int(d->alloc) || isShared) { |
561 | QT_TRY { |
562 | // allocate memory |
563 | x = Data::allocate(aalloc, options); |
564 | Q_CHECK_PTR(x); |
565 | // aalloc is bigger then 0 so it is not [un]sharedEmpty |
566 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
567 | Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable)); |
568 | #endif |
569 | Q_ASSERT(!x->ref.isStatic()); |
570 | x->size = asize; |
571 | |
572 | T *srcBegin = d->begin(); |
573 | T *srcEnd = asize > d->size ? d->end() : d->begin() + asize; |
574 | T *dst = x->begin(); |
575 | |
576 | if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { |
577 | QT_TRY { |
578 | if (isShared || !std::is_nothrow_move_constructible<T>::value) { |
579 | // we can not move the data, we need to copy construct it |
580 | while (srcBegin != srcEnd) |
581 | new (dst++) T(*srcBegin++); |
582 | } else { |
583 | while (srcBegin != srcEnd) |
584 | new (dst++) T(std::move(*srcBegin++)); |
585 | } |
586 | } QT_CATCH (...) { |
587 | // destruct already copied objects |
588 | destruct(x->begin(), dst); |
589 | QT_RETHROW; |
590 | } |
591 | } else { |
592 | ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); |
593 | dst += srcEnd - srcBegin; |
594 | |
595 | // destruct unused / not moved data |
596 | if (asize < d->size) |
597 | destruct(d->begin() + asize, d->end()); |
598 | } |
599 | |
600 | if (asize > d->size) { |
601 | // construct all new objects when growing |
602 | if (!QTypeInfo<T>::isComplex) { |
603 | ::memset(static_cast<void *>(dst), 0, (static_cast<T *>(x->end()) - dst) * sizeof(T)); |
604 | } else { |
605 | QT_TRY { |
606 | while (dst != x->end()) |
607 | new (dst++) T(); |
608 | } QT_CATCH (...) { |
609 | // destruct already copied objects |
610 | destruct(x->begin(), dst); |
611 | QT_RETHROW; |
612 | } |
613 | } |
614 | } |
615 | } QT_CATCH (...) { |
616 | Data::deallocate(x); |
617 | QT_RETHROW; |
618 | } |
619 | x->capacityReserved = d->capacityReserved; |
620 | } else { |
621 | Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size |
622 | Q_ASSERT(isDetached()); // can be done only on detached d |
623 | Q_ASSERT(x == d); // in this case we do not need to allocate anything |
624 | if (asize <= d->size) { |
625 | destruct(x->begin() + asize, x->end()); // from future end to current end |
626 | } else { |
627 | defaultConstruct(x->end(), x->begin() + asize); // from current end to future end |
628 | } |
629 | x->size = asize; |
630 | } |
631 | } else { |
632 | x = Data::sharedNull(); |
633 | } |
634 | if (d != x) { |
635 | if (!d->ref.deref()) { |
636 | if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { |
637 | // data was copy constructed, we need to call destructors |
638 | // or if !alloc we did nothing to the old 'd'. |
639 | freeData(d); |
640 | } else { |
641 | Data::deallocate(d); |
642 | } |
643 | } |
644 | d = x; |
645 | } |
646 | |
647 | Q_ASSERT(d->data()); |
648 | Q_ASSERT(uint(d->size) <= d->alloc); |
649 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
650 | Q_ASSERT(d != Data::unsharableEmpty()); |
651 | #endif |
652 | Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull()); |
653 | Q_ASSERT(d->alloc >= uint(aalloc)); |
654 | Q_ASSERT(d->size == asize); |
655 | } |
656 | |
657 | #if defined(Q_CC_MSVC) |
658 | QT_WARNING_POP |
659 | #endif |
660 | |
661 | template<typename T> |
662 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const |
663 | { |
664 | if (uint(i) >= uint(d->size)) { |
665 | return T(); |
666 | } |
667 | return d->begin()[i]; |
668 | } |
669 | template<typename T> |
670 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const |
671 | { |
672 | return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i]; |
673 | } |
674 | |
675 | template <typename T> |
676 | void QVector<T>::append(const T &t) |
677 | { |
678 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
679 | if (!isDetached() || isTooSmall) { |
680 | T copy(t); |
681 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
682 | reallocData(d->size, isTooSmall ? d->size + 1 : d->alloc, opt); |
683 | |
684 | if (QTypeInfo<T>::isComplex) |
685 | new (d->end()) T(qMove(copy)); |
686 | else |
687 | *d->end() = qMove(copy); |
688 | |
689 | } else { |
690 | if (QTypeInfo<T>::isComplex) |
691 | new (d->end()) T(t); |
692 | else |
693 | *d->end() = t; |
694 | } |
695 | ++d->size; |
696 | } |
697 | |
698 | #ifdef Q_COMPILER_RVALUE_REFS |
699 | template <typename T> |
700 | void QVector<T>::append(T &&t) |
701 | { |
702 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
703 | if (!isDetached() || isTooSmall) { |
704 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
705 | reallocData(d->size, isTooSmall ? d->size + 1 : d->alloc, opt); |
706 | } |
707 | |
708 | new (d->end()) T(std::move(t)); |
709 | |
710 | ++d->size; |
711 | } |
712 | #endif |
713 | |
714 | template <typename T> |
715 | void QVector<T>::removeLast() |
716 | { |
717 | Q_ASSERT(!isEmpty()); |
718 | Q_ASSERT(d->alloc); |
719 | |
720 | if (!d->ref.isShared()) { |
721 | --d->size; |
722 | if (QTypeInfo<T>::isComplex) |
723 | (d->data() + d->size)->~T(); |
724 | } else { |
725 | reallocData(d->size - 1); |
726 | } |
727 | } |
728 | |
729 | template <typename T> |
730 | typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t) |
731 | { |
732 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
733 | |
734 | const auto offset = std::distance(d->begin(), before); |
735 | if (n != 0) { |
736 | const T copy(t); |
737 | if (!isDetached() || d->size + n > int(d->alloc)) |
738 | reallocData(d->size, d->size + n, QArrayData::Grow); |
739 | if (!QTypeInfoQuery<T>::isRelocatable) { |
740 | T *b = d->end(); |
741 | T *i = d->end() + n; |
742 | while (i != b) |
743 | new (--i) T; |
744 | i = d->end(); |
745 | T *j = i + n; |
746 | b = d->begin() + offset; |
747 | while (i != b) |
748 | *--j = *--i; |
749 | i = b+n; |
750 | while (i != b) |
751 | *--i = copy; |
752 | } else { |
753 | T *b = d->begin() + offset; |
754 | T *i = b + n; |
755 | memmove(static_cast<void *>(i), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
756 | while (i != b) |
757 | new (--i) T(copy); |
758 | } |
759 | d->size += n; |
760 | } |
761 | return d->begin() + offset; |
762 | } |
763 | |
764 | template <typename T> |
765 | typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t) |
766 | { |
767 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
768 | |
769 | const auto offset = std::distance(d->begin(), before); |
770 | if (!isDetached() || d->size + 1 > int(d->alloc)) |
771 | reallocData(d->size, d->size + 1, QArrayData::Grow); |
772 | if (!QTypeInfoQuery<T>::isRelocatable) { |
773 | T *i = d->end(); |
774 | T *j = i + 1; |
775 | T *b = d->begin() + offset; |
776 | // The new end-element needs to be constructed, the rest must be move assigned |
777 | if (i != b) { |
778 | new (--j) T(std::move(*--i)); |
779 | while (i != b) |
780 | *--j = std::move(*--i); |
781 | *b = std::move(t); |
782 | } else { |
783 | new (b) T(std::move(t)); |
784 | } |
785 | } else { |
786 | T *b = d->begin() + offset; |
787 | memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
788 | new (b) T(std::move(t)); |
789 | } |
790 | d->size += 1; |
791 | return d->begin() + offset; |
792 | } |
793 | |
794 | template <typename T> |
795 | typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend) |
796 | { |
797 | Q_ASSERT_X(isValidIterator(abegin), "QVector::erase" , "The specified iterator argument 'abegin' is invalid" ); |
798 | Q_ASSERT_X(isValidIterator(aend), "QVector::erase" , "The specified iterator argument 'aend' is invalid" ); |
799 | |
800 | const auto itemsToErase = aend - abegin; |
801 | |
802 | if (!itemsToErase) |
803 | return abegin; |
804 | |
805 | Q_ASSERT(abegin >= d->begin()); |
806 | Q_ASSERT(aend <= d->end()); |
807 | Q_ASSERT(abegin <= aend); |
808 | |
809 | const auto itemsUntouched = abegin - d->begin(); |
810 | |
811 | // FIXME we could do a proper realloc, which copy constructs only needed data. |
812 | // FIXME we are about to delete data - maybe it is good time to shrink? |
813 | // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this. |
814 | if (d->alloc) { |
815 | detach(); |
816 | abegin = d->begin() + itemsUntouched; |
817 | aend = abegin + itemsToErase; |
818 | if (!QTypeInfoQuery<T>::isRelocatable) { |
819 | iterator moveBegin = abegin + itemsToErase; |
820 | iterator moveEnd = d->end(); |
821 | while (moveBegin != moveEnd) { |
822 | if (QTypeInfo<T>::isComplex) |
823 | static_cast<T *>(abegin)->~T(); |
824 | new (abegin++) T(*moveBegin++); |
825 | } |
826 | if (abegin < d->end()) { |
827 | // destroy rest of instances |
828 | destruct(abegin, d->end()); |
829 | } |
830 | } else { |
831 | destruct(abegin, aend); |
832 | // QTBUG-53605: static_cast<void *> masks clang errors of the form |
833 | // error: destination for this 'memmove' call is a pointer to class containing a dynamic class |
834 | // FIXME maybe use std::is_polymorphic (as soon as allowed) to avoid the memmove |
835 | memmove(static_cast<void *>(abegin), static_cast<void *>(aend), |
836 | (d->size - itemsToErase - itemsUntouched) * sizeof(T)); |
837 | } |
838 | d->size -= int(itemsToErase); |
839 | } |
840 | return d->begin() + itemsUntouched; |
841 | } |
842 | |
843 | template <typename T> |
844 | bool QVector<T>::operator==(const QVector<T> &v) const |
845 | { |
846 | if (d == v.d) |
847 | return true; |
848 | if (d->size != v.d->size) |
849 | return false; |
850 | const T *vb = v.d->begin(); |
851 | const T *b = d->begin(); |
852 | const T *e = d->end(); |
853 | return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(vb, v.d->size)); |
854 | } |
855 | |
856 | template <typename T> |
857 | QVector<T> &QVector<T>::fill(const T &from, int asize) |
858 | { |
859 | const T copy(from); |
860 | resize(asize < 0 ? d->size : asize); |
861 | if (d->size) { |
862 | T *i = d->end(); |
863 | T *b = d->begin(); |
864 | while (i != b) |
865 | *--i = copy; |
866 | } |
867 | return *this; |
868 | } |
869 | |
870 | template <typename T> |
871 | QVector<T> &QVector<T>::operator+=(const QVector &l) |
872 | { |
873 | if (d == Data::sharedNull()) { |
874 | *this = l; |
875 | } else { |
876 | uint newSize = d->size + l.d->size; |
877 | const bool isTooSmall = newSize > d->alloc; |
878 | if (!isDetached() || isTooSmall) { |
879 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
880 | reallocData(d->size, isTooSmall ? newSize : d->alloc, opt); |
881 | } |
882 | |
883 | if (d->alloc) { |
884 | T *w = d->begin() + newSize; |
885 | T *i = l.d->end(); |
886 | T *b = l.d->begin(); |
887 | while (i != b) { |
888 | if (QTypeInfo<T>::isComplex) |
889 | new (--w) T(*--i); |
890 | else |
891 | *--w = *--i; |
892 | } |
893 | d->size = newSize; |
894 | } |
895 | } |
896 | return *this; |
897 | } |
898 | |
899 | template <typename T> |
900 | int QVector<T>::indexOf(const T &t, int from) const |
901 | { |
902 | if (from < 0) |
903 | from = qMax(from + d->size, 0); |
904 | if (from < d->size) { |
905 | T* n = d->begin() + from - 1; |
906 | T* e = d->end(); |
907 | while (++n != e) |
908 | if (*n == t) |
909 | return n - d->begin(); |
910 | } |
911 | return -1; |
912 | } |
913 | |
914 | template <typename T> |
915 | int QVector<T>::lastIndexOf(const T &t, int from) const |
916 | { |
917 | if (from < 0) |
918 | from += d->size; |
919 | else if (from >= d->size) |
920 | from = d->size-1; |
921 | if (from >= 0) { |
922 | T* b = d->begin(); |
923 | T* n = d->begin() + from + 1; |
924 | while (n != b) { |
925 | if (*--n == t) |
926 | return n - b; |
927 | } |
928 | } |
929 | return -1; |
930 | } |
931 | |
932 | template <typename T> |
933 | bool QVector<T>::contains(const T &t) const |
934 | { |
935 | const T *b = d->begin(); |
936 | const T *e = d->end(); |
937 | return std::find(b, e, t) != e; |
938 | } |
939 | |
940 | template <typename T> |
941 | int QVector<T>::count(const T &t) const |
942 | { |
943 | const T *b = d->begin(); |
944 | const T *e = d->end(); |
945 | return int(std::count(b, e, t)); |
946 | } |
947 | |
948 | template <typename T> |
949 | Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const |
950 | { |
951 | using namespace QtPrivate; |
952 | switch (QContainerImplHelper::mid(d->size, &pos, &len)) { |
953 | case QContainerImplHelper::Null: |
954 | case QContainerImplHelper::Empty: |
955 | return QVector<T>(); |
956 | case QContainerImplHelper::Full: |
957 | return *this; |
958 | case QContainerImplHelper::Subset: |
959 | break; |
960 | } |
961 | |
962 | QVector<T> midResult; |
963 | midResult.reallocData(0, len); |
964 | T *srcFrom = d->begin() + pos; |
965 | T *srcTo = d->begin() + pos + len; |
966 | midResult.copyConstruct(srcFrom, srcTo, midResult.data()); |
967 | midResult.d->size = len; |
968 | return midResult; |
969 | } |
970 | |
971 | template <typename T> |
972 | Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const |
973 | { |
974 | QList<T> result; |
975 | result.reserve(size()); |
976 | for (int i = 0; i < size(); ++i) |
977 | result.append(at(i)); |
978 | return result; |
979 | } |
980 | |
981 | template <typename T> |
982 | Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const |
983 | { |
984 | QVector<T> result(size()); |
985 | for (int i = 0; i < size(); ++i) |
986 | result[i] = at(i); |
987 | return result; |
988 | } |
989 | |
990 | template <typename T> |
991 | QVector<T> QVector<T>::fromList(const QList<T> &list) |
992 | { |
993 | return list.toVector(); |
994 | } |
995 | |
996 | template <typename T> |
997 | QList<T> QList<T>::fromVector(const QVector<T> &vector) |
998 | { |
999 | return vector.toList(); |
1000 | } |
1001 | |
1002 | Q_DECLARE_SEQUENTIAL_ITERATOR(Vector) |
1003 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector) |
1004 | |
1005 | template <typename T> |
1006 | uint qHash(const QVector<T> &key, uint seed = 0) |
1007 | Q_DECL_NOEXCEPT_EXPR(noexcept(qHashRange(key.cbegin(), key.cend(), seed))) |
1008 | { |
1009 | return qHashRange(key.cbegin(), key.cend(), seed); |
1010 | } |
1011 | |
1012 | template <typename T> |
1013 | bool operator<(const QVector<T> &lhs, const QVector<T> &rhs) |
1014 | Q_DECL_NOEXCEPT_EXPR(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(), |
1015 | rhs.begin(), rhs.end()))) |
1016 | { |
1017 | return std::lexicographical_compare(lhs.begin(), lhs.end(), |
1018 | rhs.begin(), rhs.end()); |
1019 | } |
1020 | |
1021 | template <typename T> |
1022 | inline bool operator>(const QVector<T> &lhs, const QVector<T> &rhs) |
1023 | Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs)) |
1024 | { |
1025 | return rhs < lhs; |
1026 | } |
1027 | |
1028 | template <typename T> |
1029 | inline bool operator<=(const QVector<T> &lhs, const QVector<T> &rhs) |
1030 | Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs)) |
1031 | { |
1032 | return !(lhs > rhs); |
1033 | } |
1034 | |
1035 | template <typename T> |
1036 | inline bool operator>=(const QVector<T> &lhs, const QVector<T> &rhs) |
1037 | Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs)) |
1038 | { |
1039 | return !(lhs < rhs); |
1040 | } |
1041 | |
1042 | /* |
1043 | ### Qt 5: |
1044 | ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because |
1045 | ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and |
1046 | ### QVector<QPointF> respectively. |
1047 | */ |
1048 | |
1049 | #ifdef Q_CC_MSVC |
1050 | QT_BEGIN_INCLUDE_NAMESPACE |
1051 | #include <QtCore/qpoint.h> |
1052 | QT_END_INCLUDE_NAMESPACE |
1053 | |
1054 | #ifndef Q_TEMPLATE_EXTERN |
1055 | #if defined(QT_BUILD_CORE_LIB) |
1056 | #define Q_TEMPLATE_EXTERN |
1057 | #else |
1058 | #define Q_TEMPLATE_EXTERN extern |
1059 | #endif |
1060 | #endif |
1061 | Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPointF>; |
1062 | Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPoint>; |
1063 | #endif |
1064 | |
1065 | QVector<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(*this); } |
1066 | |
1067 | QT_END_NAMESPACE |
1068 | |
1069 | #endif // QVECTOR_H |
1070 | |