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 QLIST_H |
43 | #define QLIST_H |
44 | |
45 | #include <QtCore/qiterator.h> |
46 | #include <QtCore/qatomic.h> |
47 | #include <QtCore/qalgorithms.h> |
48 | |
49 | #ifndef QT_NO_STL |
50 | #include <iterator> |
51 | #include <list> |
52 | #endif |
53 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
54 | #include <iterator> |
55 | #include <initializer_list> |
56 | #endif |
57 | |
58 | #include <new> |
59 | #include <limits.h> |
60 | #include <string.h> |
61 | |
62 | QT_BEGIN_HEADER |
63 | |
64 | QT_BEGIN_NAMESPACE |
65 | |
66 | QT_MODULE(Core) |
67 | |
68 | template <typename T> class QVector; |
69 | template <typename T> class QSet; |
70 | |
71 | struct Q_CORE_EXPORT QListData { |
72 | struct Data { |
73 | QBasicAtomicInt ref; |
74 | int alloc, begin, end; |
75 | uint sharable : 1; |
76 | void *array[1]; |
77 | }; |
78 | enum { = sizeof(Data) - sizeof(void *) }; |
79 | |
80 | Data *detach(int alloc); |
81 | Data *detach_grow(int *i, int n); |
82 | Data *detach(); // remove in 5.0 |
83 | Data *detach2(); // remove in 5.0 |
84 | Data *detach3(); // remove in 5.0 |
85 | void realloc(int alloc); |
86 | static Data shared_null; |
87 | Data *d; |
88 | void **erase(void **xi); |
89 | void **append(int n); |
90 | void **append(); |
91 | void **append(const QListData &l); |
92 | void **append2(const QListData &l); // remove in 5.0 |
93 | void **prepend(); |
94 | void **insert(int i); |
95 | void remove(int i); |
96 | void remove(int i, int n); |
97 | void move(int from, int to); |
98 | inline int size() const { return d->end - d->begin; } |
99 | inline bool isEmpty() const { return d->end == d->begin; } |
100 | inline void **at(int i) const { return d->array + d->begin + i; } |
101 | inline void **begin() const { return d->array + d->begin; } |
102 | inline void **end() const { return d->array + d->end; } |
103 | }; |
104 | |
105 | template <typename T> |
106 | class QList |
107 | { |
108 | struct Node { void *v; |
109 | #if defined(Q_CC_BOR) |
110 | Q_INLINE_TEMPLATE T &t(); |
111 | #else |
112 | Q_INLINE_TEMPLATE T &t() |
113 | { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic |
114 | ? v : this); } |
115 | #endif |
116 | }; |
117 | |
118 | union { QListData p; QListData::Data *d; }; |
119 | |
120 | public: |
121 | inline QList() : d(&QListData::shared_null) { d->ref.ref(); } |
122 | inline QList(const QList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
123 | ~QList(); |
124 | QList<T> &operator=(const QList<T> &l); |
125 | #ifdef Q_COMPILER_RVALUE_REFS |
126 | inline QList &operator=(QList &&other) |
127 | { qSwap(d, other.d); return *this; } |
128 | #endif |
129 | inline void swap(QList<T> &other) { qSwap(d, other.d); } |
130 | #ifdef Q_COMPILER_INITIALIZER_LISTS |
131 | inline QList(std::initializer_list<T> args) : d(&QListData::shared_null) |
132 | { d->ref.ref(); qCopy(args.begin(), args.end(), std::back_inserter(*this)); } |
133 | #endif |
134 | bool operator==(const QList<T> &l) const; |
135 | inline bool operator!=(const QList<T> &l) const { return !(*this == l); } |
136 | |
137 | inline int size() const { return p.size(); } |
138 | |
139 | inline void detach() { if (d->ref != 1) detach_helper(); } |
140 | |
141 | inline void detachShared() |
142 | { |
143 | // The "this->" qualification is needed for GCCE. |
144 | if (d->ref != 1 && this->d != &QListData::shared_null) |
145 | detach_helper(); |
146 | } |
147 | |
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 QList<T> &other) const { return d == other.d; } |
151 | |
152 | inline bool isEmpty() const { return p.isEmpty(); } |
153 | |
154 | void clear(); |
155 | |
156 | const T &at(int i) const; |
157 | const T &operator[](int i) const; |
158 | T &operator[](int i); |
159 | |
160 | void reserve(int size); |
161 | void append(const T &t); |
162 | void append(const QList<T> &t); |
163 | void prepend(const T &t); |
164 | void insert(int i, const T &t); |
165 | void replace(int i, const T &t); |
166 | void removeAt(int i); |
167 | int removeAll(const T &t); |
168 | bool removeOne(const T &t); |
169 | T takeAt(int i); |
170 | T takeFirst(); |
171 | T takeLast(); |
172 | void move(int from, int to); |
173 | void swap(int i, int j); |
174 | int indexOf(const T &t, int from = 0) const; |
175 | int lastIndexOf(const T &t, int from = -1) const; |
176 | QBool contains(const T &t) const; |
177 | int count(const T &t) const; |
178 | |
179 | class const_iterator; |
180 | |
181 | class iterator { |
182 | public: |
183 | Node *i; |
184 | typedef std::random_access_iterator_tag iterator_category; |
185 | typedef qptrdiff difference_type; |
186 | typedef T value_type; |
187 | typedef T *pointer; |
188 | typedef T &reference; |
189 | |
190 | inline iterator() : i(0) {} |
191 | inline iterator(Node *n) : i(n) {} |
192 | inline iterator(const iterator &o): i(o.i){} |
193 | inline T &operator*() const { return i->t(); } |
194 | inline T *operator->() const { return &i->t(); } |
195 | inline T &operator[](int j) const { return i[j].t(); } |
196 | inline bool operator==(const iterator &o) const { return i == o.i; } |
197 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
198 | inline bool operator<(const iterator& other) const { return i < other.i; } |
199 | inline bool operator<=(const iterator& other) const { return i <= other.i; } |
200 | inline bool operator>(const iterator& other) const { return i > other.i; } |
201 | inline bool operator>=(const iterator& other) const { return i >= other.i; } |
202 | #ifndef QT_STRICT_ITERATORS |
203 | inline bool operator==(const const_iterator &o) const |
204 | { return i == o.i; } |
205 | inline bool operator!=(const const_iterator &o) const |
206 | { return i != o.i; } |
207 | inline bool operator<(const const_iterator& other) const |
208 | { return i < other.i; } |
209 | inline bool operator<=(const const_iterator& other) const |
210 | { return i <= other.i; } |
211 | inline bool operator>(const const_iterator& other) const |
212 | { return i > other.i; } |
213 | inline bool operator>=(const const_iterator& other) const |
214 | { return i >= other.i; } |
215 | #endif |
216 | inline iterator &operator++() { ++i; return *this; } |
217 | inline iterator operator++(int) { Node *n = i; ++i; return n; } |
218 | inline iterator &operator--() { i--; return *this; } |
219 | inline iterator operator--(int) { Node *n = i; i--; return n; } |
220 | inline iterator &operator+=(int j) { i+=j; return *this; } |
221 | inline iterator &operator-=(int j) { i-=j; return *this; } |
222 | inline iterator operator+(int j) const { return iterator(i+j); } |
223 | inline iterator operator-(int j) const { return iterator(i-j); } |
224 | inline int operator-(iterator j) const { return int(i - j.i); } |
225 | }; |
226 | friend class iterator; |
227 | |
228 | class const_iterator { |
229 | public: |
230 | Node *i; |
231 | typedef std::random_access_iterator_tag iterator_category; |
232 | typedef qptrdiff difference_type; |
233 | typedef T value_type; |
234 | typedef const T *pointer; |
235 | typedef const T &reference; |
236 | |
237 | inline const_iterator() : i(0) {} |
238 | inline const_iterator(Node *n) : i(n) {} |
239 | inline const_iterator(const const_iterator &o): i(o.i) {} |
240 | #ifdef QT_STRICT_ITERATORS |
241 | inline explicit const_iterator(const iterator &o): i(o.i) {} |
242 | #else |
243 | inline const_iterator(const iterator &o): i(o.i) {} |
244 | #endif |
245 | inline const T &operator*() const { return i->t(); } |
246 | inline const T *operator->() const { return &i->t(); } |
247 | inline const T &operator[](int j) const { return i[j].t(); } |
248 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
249 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
250 | inline bool operator<(const const_iterator& other) const { return i < other.i; } |
251 | inline bool operator<=(const const_iterator& other) const { return i <= other.i; } |
252 | inline bool operator>(const const_iterator& other) const { return i > other.i; } |
253 | inline bool operator>=(const const_iterator& other) const { return i >= other.i; } |
254 | inline const_iterator &operator++() { ++i; return *this; } |
255 | inline const_iterator operator++(int) { Node *n = i; ++i; return n; } |
256 | inline const_iterator &operator--() { i--; return *this; } |
257 | inline const_iterator operator--(int) { Node *n = i; i--; return n; } |
258 | inline const_iterator &operator+=(int j) { i+=j; return *this; } |
259 | inline const_iterator &operator-=(int j) { i-=j; return *this; } |
260 | inline const_iterator operator+(int j) const { return const_iterator(i+j); } |
261 | inline const_iterator operator-(int j) const { return const_iterator(i-j); } |
262 | inline int operator-(const_iterator j) const { return i - j.i; } |
263 | }; |
264 | friend class const_iterator; |
265 | |
266 | // stl style |
267 | inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); } |
268 | inline const_iterator begin() const { return reinterpret_cast<Node *>(p.begin()); } |
269 | inline const_iterator constBegin() const { return reinterpret_cast<Node *>(p.begin()); } |
270 | inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); } |
271 | inline const_iterator end() const { return reinterpret_cast<Node *>(p.end()); } |
272 | inline const_iterator constEnd() const { return reinterpret_cast<Node *>(p.end()); } |
273 | iterator insert(iterator before, const T &t); |
274 | iterator erase(iterator pos); |
275 | iterator erase(iterator first, iterator last); |
276 | |
277 | // more Qt |
278 | typedef iterator Iterator; |
279 | typedef const_iterator ConstIterator; |
280 | inline int count() const { return p.size(); } |
281 | inline int length() const { return p.size(); } // Same as count() |
282 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } |
283 | inline const T& first() const { Q_ASSERT(!isEmpty()); return at(0); } |
284 | T& last() { Q_ASSERT(!isEmpty()); return *(--end()); } |
285 | const T& last() const { Q_ASSERT(!isEmpty()); return at(count() - 1); } |
286 | inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); } |
287 | inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); } |
288 | inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } |
289 | inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } |
290 | QList<T> mid(int pos, int length = -1) const; |
291 | |
292 | T value(int i) const; |
293 | T value(int i, const T &defaultValue) const; |
294 | |
295 | // stl compatibility |
296 | inline void push_back(const T &t) { append(t); } |
297 | inline void push_front(const T &t) { prepend(t); } |
298 | inline T& front() { return first(); } |
299 | inline const T& front() const { return first(); } |
300 | inline T& back() { return last(); } |
301 | inline const T& back() const { return last(); } |
302 | inline void pop_front() { removeFirst(); } |
303 | inline void pop_back() { removeLast(); } |
304 | inline bool empty() const { return isEmpty(); } |
305 | typedef int size_type; |
306 | typedef T value_type; |
307 | typedef value_type *pointer; |
308 | typedef const value_type *const_pointer; |
309 | typedef value_type &reference; |
310 | typedef const value_type &const_reference; |
311 | typedef qptrdiff difference_type; |
312 | |
313 | #ifdef QT3_SUPPORT |
314 | inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); } |
315 | inline QT3_SUPPORT int remove(const T &t) { return removeAll(t); } |
316 | inline QT3_SUPPORT int findIndex(const T& t) const { return indexOf(t); } |
317 | inline QT3_SUPPORT iterator find(const T& t) |
318 | { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); } |
319 | inline QT3_SUPPORT const_iterator find (const T& t) const |
320 | { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); } |
321 | inline QT3_SUPPORT iterator find(iterator from, const T& t) |
322 | { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; } |
323 | inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const |
324 | { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; } |
325 | #endif |
326 | |
327 | // comfort |
328 | QList<T> &operator+=(const QList<T> &l); |
329 | inline QList<T> operator+(const QList<T> &l) const |
330 | { QList n = *this; n += l; return n; } |
331 | inline QList<T> &operator+=(const T &t) |
332 | { append(t); return *this; } |
333 | inline QList<T> &operator<< (const T &t) |
334 | { append(t); return *this; } |
335 | inline QList<T> &operator<<(const QList<T> &l) |
336 | { *this += l; return *this; } |
337 | |
338 | QVector<T> toVector() const; |
339 | QSet<T> toSet() const; |
340 | |
341 | static QList<T> fromVector(const QVector<T> &vector); |
342 | static QList<T> fromSet(const QSet<T> &set); |
343 | |
344 | #ifndef QT_NO_STL |
345 | static inline QList<T> fromStdList(const std::list<T> &list) |
346 | { QList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; } |
347 | inline std::list<T> toStdList() const |
348 | { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; } |
349 | #endif |
350 | |
351 | private: |
352 | Node *detach_helper_grow(int i, int n); |
353 | void detach_helper(int alloc); |
354 | void detach_helper(); |
355 | void free(QListData::Data *d); |
356 | |
357 | void node_construct(Node *n, const T &t); |
358 | void node_destruct(Node *n); |
359 | void node_copy(Node *from, Node *to, Node *src); |
360 | void node_destruct(Node *from, Node *to); |
361 | }; |
362 | |
363 | #if defined(Q_CC_BOR) |
364 | template <typename T> |
365 | Q_INLINE_TEMPLATE T &QList<T>::Node::t() |
366 | { return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; } |
367 | #endif |
368 | |
369 | template <typename T> |
370 | Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t) |
371 | { |
372 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t); |
373 | else if (QTypeInfo<T>::isComplex) new (n) T(t); |
374 | #if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__) |
375 | // This violates pointer aliasing rules, but it is known to be safe (and silent) |
376 | // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which |
377 | // set the same define are assumed to be safe. |
378 | else *reinterpret_cast<T*>(n) = t; |
379 | #else |
380 | // This is always safe, but penaltizes unoptimized builds a lot. |
381 | else ::memcpy(n, &t, sizeof(T)); |
382 | #endif |
383 | } |
384 | |
385 | template <typename T> |
386 | Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n) |
387 | { |
388 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v); |
389 | else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T(); |
390 | } |
391 | |
392 | template <typename T> |
393 | Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src) |
394 | { |
395 | Node *current = from; |
396 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { |
397 | QT_TRY { |
398 | while(current != to) { |
399 | current->v = new T(*reinterpret_cast<T*>(src->v)); |
400 | ++current; |
401 | ++src; |
402 | } |
403 | } QT_CATCH(...) { |
404 | while (current-- != from) |
405 | delete reinterpret_cast<T*>(current->v); |
406 | QT_RETHROW; |
407 | } |
408 | |
409 | } else if (QTypeInfo<T>::isComplex) { |
410 | QT_TRY { |
411 | while(current != to) { |
412 | new (current) T(*reinterpret_cast<T*>(src)); |
413 | ++current; |
414 | ++src; |
415 | } |
416 | } QT_CATCH(...) { |
417 | while (current-- != from) |
418 | (reinterpret_cast<T*>(current))->~T(); |
419 | QT_RETHROW; |
420 | } |
421 | } else { |
422 | if (src != from && to - from > 0) |
423 | memcpy(from, src, (to - from) * sizeof(Node *)); |
424 | } |
425 | } |
426 | |
427 | template <typename T> |
428 | Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to) |
429 | { |
430 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) |
431 | while(from != to) --to, delete reinterpret_cast<T*>(to->v); |
432 | else if (QTypeInfo<T>::isComplex) |
433 | while (from != to) --to, reinterpret_cast<T*>(to)->~T(); |
434 | } |
435 | |
436 | template <typename T> |
437 | Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l) |
438 | { |
439 | if (d != l.d) { |
440 | QListData::Data *o = l.d; |
441 | o->ref.ref(); |
442 | if (!d->ref.deref()) |
443 | free(d); |
444 | d = o; |
445 | if (!d->sharable) |
446 | detach_helper(); |
447 | } |
448 | return *this; |
449 | } |
450 | template <typename T> |
451 | inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t) |
452 | { |
453 | int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin())); |
454 | Node *n = reinterpret_cast<Node *>(p.insert(iBefore)); |
455 | QT_TRY { |
456 | node_construct(n, t); |
457 | } QT_CATCH(...) { |
458 | p.remove(iBefore); |
459 | QT_RETHROW; |
460 | } |
461 | return n; |
462 | } |
463 | template <typename T> |
464 | inline typename QList<T>::iterator QList<T>::erase(iterator it) |
465 | { node_destruct(it.i); |
466 | return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i))); } |
467 | template <typename T> |
468 | inline const T &QList<T>::at(int i) const |
469 | { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at" , "index out of range" ); |
470 | return reinterpret_cast<Node *>(p.at(i))->t(); } |
471 | template <typename T> |
472 | inline const T &QList<T>::operator[](int i) const |
473 | { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]" , "index out of range" ); |
474 | return reinterpret_cast<Node *>(p.at(i))->t(); } |
475 | template <typename T> |
476 | inline T &QList<T>::operator[](int i) |
477 | { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]" , "index out of range" ); |
478 | detach(); return reinterpret_cast<Node *>(p.at(i))->t(); } |
479 | template <typename T> |
480 | inline void QList<T>::removeAt(int i) |
481 | { if(i >= 0 && i < p.size()) { detach(); |
482 | node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i); } } |
483 | template <typename T> |
484 | inline T QList<T>::takeAt(int i) |
485 | { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::take" , "index out of range" ); |
486 | detach(); Node *n = reinterpret_cast<Node *>(p.at(i)); T t = n->t(); node_destruct(n); |
487 | p.remove(i); return t; } |
488 | template <typename T> |
489 | inline T QList<T>::takeFirst() |
490 | { T t = first(); removeFirst(); return t; } |
491 | template <typename T> |
492 | inline T QList<T>::takeLast() |
493 | { T t = last(); removeLast(); return t; } |
494 | |
495 | template <typename T> |
496 | Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc) |
497 | { |
498 | if (d->alloc < alloc) { |
499 | if (d->ref != 1) |
500 | detach_helper(alloc); |
501 | else |
502 | p.realloc(alloc); |
503 | } |
504 | } |
505 | |
506 | template <typename T> |
507 | Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t) |
508 | { |
509 | if (d->ref != 1) { |
510 | Node *n = detach_helper_grow(INT_MAX, 1); |
511 | QT_TRY { |
512 | node_construct(n, t); |
513 | } QT_CATCH(...) { |
514 | --d->end; |
515 | QT_RETHROW; |
516 | } |
517 | } else { |
518 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { |
519 | Node *n = reinterpret_cast<Node *>(p.append()); |
520 | QT_TRY { |
521 | node_construct(n, t); |
522 | } QT_CATCH(...) { |
523 | --d->end; |
524 | QT_RETHROW; |
525 | } |
526 | } else { |
527 | Node *n, copy; |
528 | node_construct(©, t); // t might be a reference to an object in the array |
529 | QT_TRY { |
530 | n = reinterpret_cast<Node *>(p.append());; |
531 | } QT_CATCH(...) { |
532 | node_destruct(©); |
533 | QT_RETHROW; |
534 | } |
535 | *n = copy; |
536 | } |
537 | } |
538 | } |
539 | |
540 | template <typename T> |
541 | inline void QList<T>::prepend(const T &t) |
542 | { |
543 | if (d->ref != 1) { |
544 | Node *n = detach_helper_grow(0, 1); |
545 | QT_TRY { |
546 | node_construct(n, t); |
547 | } QT_CATCH(...) { |
548 | ++d->begin; |
549 | QT_RETHROW; |
550 | } |
551 | } else { |
552 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { |
553 | Node *n = reinterpret_cast<Node *>(p.prepend()); |
554 | QT_TRY { |
555 | node_construct(n, t); |
556 | } QT_CATCH(...) { |
557 | ++d->begin; |
558 | QT_RETHROW; |
559 | } |
560 | } else { |
561 | Node *n, copy; |
562 | node_construct(©, t); // t might be a reference to an object in the array |
563 | QT_TRY { |
564 | n = reinterpret_cast<Node *>(p.prepend());; |
565 | } QT_CATCH(...) { |
566 | node_destruct(©); |
567 | QT_RETHROW; |
568 | } |
569 | *n = copy; |
570 | } |
571 | } |
572 | } |
573 | |
574 | template <typename T> |
575 | inline void QList<T>::insert(int i, const T &t) |
576 | { |
577 | if (d->ref != 1) { |
578 | Node *n = detach_helper_grow(i, 1); |
579 | QT_TRY { |
580 | node_construct(n, t); |
581 | } QT_CATCH(...) { |
582 | p.remove(i); |
583 | QT_RETHROW; |
584 | } |
585 | } else { |
586 | if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { |
587 | Node *n = reinterpret_cast<Node *>(p.insert(i)); |
588 | QT_TRY { |
589 | node_construct(n, t); |
590 | } QT_CATCH(...) { |
591 | p.remove(i); |
592 | QT_RETHROW; |
593 | } |
594 | } else { |
595 | Node *n, copy; |
596 | node_construct(©, t); // t might be a reference to an object in the array |
597 | QT_TRY { |
598 | n = reinterpret_cast<Node *>(p.insert(i));; |
599 | } QT_CATCH(...) { |
600 | node_destruct(©); |
601 | QT_RETHROW; |
602 | } |
603 | *n = copy; |
604 | } |
605 | } |
606 | } |
607 | |
608 | template <typename T> |
609 | inline void QList<T>::replace(int i, const T &t) |
610 | { |
611 | Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace" , "index out of range" ); |
612 | detach(); |
613 | reinterpret_cast<Node *>(p.at(i))->t() = t; |
614 | } |
615 | |
616 | template <typename T> |
617 | inline void QList<T>::swap(int i, int j) |
618 | { |
619 | Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(), |
620 | "QList<T>::swap" , "index out of range" ); |
621 | detach(); |
622 | void *t = d->array[d->begin + i]; |
623 | d->array[d->begin + i] = d->array[d->begin + j]; |
624 | d->array[d->begin + j] = t; |
625 | } |
626 | |
627 | template <typename T> |
628 | inline void QList<T>::move(int from, int to) |
629 | { |
630 | Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(), |
631 | "QList<T>::move" , "index out of range" ); |
632 | detach(); |
633 | p.move(from, to); |
634 | } |
635 | |
636 | template<typename T> |
637 | Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const |
638 | { |
639 | if (alength < 0 || pos + alength > size()) |
640 | alength = size() - pos; |
641 | if (pos == 0 && alength == size()) |
642 | return *this; |
643 | QList<T> cpy; |
644 | if (alength <= 0) |
645 | return cpy; |
646 | cpy.reserve(alength); |
647 | cpy.d->end = alength; |
648 | QT_TRY { |
649 | cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()), |
650 | reinterpret_cast<Node *>(cpy.p.end()), |
651 | reinterpret_cast<Node *>(p.begin() + pos)); |
652 | } QT_CATCH(...) { |
653 | // restore the old end |
654 | cpy.d->end = 0; |
655 | QT_RETHROW; |
656 | } |
657 | return cpy; |
658 | } |
659 | |
660 | template<typename T> |
661 | Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const |
662 | { |
663 | if (i < 0 || i >= p.size()) { |
664 | return T(); |
665 | } |
666 | return reinterpret_cast<Node *>(p.at(i))->t(); |
667 | } |
668 | |
669 | template<typename T> |
670 | Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const |
671 | { |
672 | return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t()); |
673 | } |
674 | |
675 | template <typename T> |
676 | Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c) |
677 | { |
678 | Node *n = reinterpret_cast<Node *>(p.begin()); |
679 | QListData::Data *x = p.detach_grow(&i, c); |
680 | QT_TRY { |
681 | node_copy(reinterpret_cast<Node *>(p.begin()), |
682 | reinterpret_cast<Node *>(p.begin() + i), n); |
683 | } QT_CATCH(...) { |
684 | qFree(d); |
685 | d = x; |
686 | QT_RETHROW; |
687 | } |
688 | QT_TRY { |
689 | node_copy(reinterpret_cast<Node *>(p.begin() + i + c), |
690 | reinterpret_cast<Node *>(p.end()), n + i); |
691 | } QT_CATCH(...) { |
692 | node_destruct(reinterpret_cast<Node *>(p.begin()), |
693 | reinterpret_cast<Node *>(p.begin() + i)); |
694 | qFree(d); |
695 | d = x; |
696 | QT_RETHROW; |
697 | } |
698 | |
699 | if (!x->ref.deref()) |
700 | free(x); |
701 | |
702 | return reinterpret_cast<Node *>(p.begin() + i); |
703 | } |
704 | |
705 | template <typename T> |
706 | Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc) |
707 | { |
708 | Node *n = reinterpret_cast<Node *>(p.begin()); |
709 | QListData::Data *x = p.detach(alloc); |
710 | QT_TRY { |
711 | node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n); |
712 | } QT_CATCH(...) { |
713 | qFree(d); |
714 | d = x; |
715 | QT_RETHROW; |
716 | } |
717 | |
718 | if (!x->ref.deref()) |
719 | free(x); |
720 | } |
721 | |
722 | template <typename T> |
723 | Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper() |
724 | { |
725 | detach_helper(d->alloc); |
726 | } |
727 | |
728 | template <typename T> |
729 | Q_OUTOFLINE_TEMPLATE QList<T>::~QList() |
730 | { |
731 | if (!d->ref.deref()) |
732 | free(d); |
733 | } |
734 | |
735 | template <typename T> |
736 | Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const |
737 | { |
738 | if (p.size() != l.p.size()) |
739 | return false; |
740 | if (d == l.d) |
741 | return true; |
742 | Node *i = reinterpret_cast<Node *>(p.end()); |
743 | Node *b = reinterpret_cast<Node *>(p.begin()); |
744 | Node *li = reinterpret_cast<Node *>(l.p.end()); |
745 | while (i != b) { |
746 | --i; --li; |
747 | if (!(i->t() == li->t())) |
748 | return false; |
749 | } |
750 | return true; |
751 | } |
752 | |
753 | // ### Qt 5: rename freeData() to avoid confusion with std::free() |
754 | template <typename T> |
755 | Q_OUTOFLINE_TEMPLATE void QList<T>::free(QListData::Data *data) |
756 | { |
757 | node_destruct(reinterpret_cast<Node *>(data->array + data->begin), |
758 | reinterpret_cast<Node *>(data->array + data->end)); |
759 | qFree(data); |
760 | } |
761 | |
762 | |
763 | template <typename T> |
764 | Q_OUTOFLINE_TEMPLATE void QList<T>::clear() |
765 | { |
766 | *this = QList<T>(); |
767 | } |
768 | |
769 | template <typename T> |
770 | Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t) |
771 | { |
772 | int index = indexOf(_t); |
773 | if (index == -1) |
774 | return 0; |
775 | |
776 | const T t = _t; |
777 | detach(); |
778 | |
779 | Node *i = reinterpret_cast<Node *>(p.at(index)); |
780 | Node *e = reinterpret_cast<Node *>(p.end()); |
781 | Node *n = i; |
782 | node_destruct(i); |
783 | while (++i != e) { |
784 | if (i->t() == t) |
785 | node_destruct(i); |
786 | else |
787 | *n++ = *i; |
788 | } |
789 | |
790 | int removedCount = e - n; |
791 | d->end -= removedCount; |
792 | return removedCount; |
793 | } |
794 | |
795 | template <typename T> |
796 | Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t) |
797 | { |
798 | int index = indexOf(_t); |
799 | if (index != -1) { |
800 | removeAt(index); |
801 | return true; |
802 | } |
803 | return false; |
804 | } |
805 | |
806 | template <typename T> |
807 | Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst, |
808 | typename QList<T>::iterator alast) |
809 | { |
810 | for (Node *n = afirst.i; n < alast.i; ++n) |
811 | node_destruct(n); |
812 | int idx = afirst - begin(); |
813 | p.remove(idx, alast - afirst); |
814 | return begin() + idx; |
815 | } |
816 | |
817 | template <typename T> |
818 | Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l) |
819 | { |
820 | if (!l.isEmpty()) { |
821 | if (isEmpty()) { |
822 | *this = l; |
823 | } else { |
824 | Node *n = (d->ref != 1) |
825 | ? detach_helper_grow(INT_MAX, l.size()) |
826 | : reinterpret_cast<Node *>(p.append2(l.p)); |
827 | QT_TRY { |
828 | node_copy(n, reinterpret_cast<Node *>(p.end()), |
829 | reinterpret_cast<Node *>(l.p.begin())); |
830 | } QT_CATCH(...) { |
831 | // restore the old end |
832 | d->end -= int(reinterpret_cast<Node *>(p.end()) - n); |
833 | QT_RETHROW; |
834 | } |
835 | } |
836 | } |
837 | return *this; |
838 | } |
839 | |
840 | template <typename T> |
841 | inline void QList<T>::append(const QList<T> &t) |
842 | { |
843 | *this += t; |
844 | } |
845 | |
846 | template <typename T> |
847 | Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const |
848 | { |
849 | if (from < 0) |
850 | from = qMax(from + p.size(), 0); |
851 | if (from < p.size()) { |
852 | Node *n = reinterpret_cast<Node *>(p.at(from -1)); |
853 | Node *e = reinterpret_cast<Node *>(p.end()); |
854 | while (++n != e) |
855 | if (n->t() == t) |
856 | return int(n - reinterpret_cast<Node *>(p.begin())); |
857 | } |
858 | return -1; |
859 | } |
860 | |
861 | template <typename T> |
862 | Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const |
863 | { |
864 | if (from < 0) |
865 | from += p.size(); |
866 | else if (from >= p.size()) |
867 | from = p.size()-1; |
868 | if (from >= 0) { |
869 | Node *b = reinterpret_cast<Node *>(p.begin()); |
870 | Node *n = reinterpret_cast<Node *>(p.at(from + 1)); |
871 | while (n-- != b) { |
872 | if (n->t() == t) |
873 | return n - b; |
874 | } |
875 | } |
876 | return -1; |
877 | } |
878 | |
879 | template <typename T> |
880 | Q_OUTOFLINE_TEMPLATE QBool QList<T>::contains(const T &t) const |
881 | { |
882 | Node *b = reinterpret_cast<Node *>(p.begin()); |
883 | Node *i = reinterpret_cast<Node *>(p.end()); |
884 | while (i-- != b) |
885 | if (i->t() == t) |
886 | return QBool(true); |
887 | return QBool(false); |
888 | } |
889 | |
890 | template <typename T> |
891 | Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const |
892 | { |
893 | int c = 0; |
894 | Node *b = reinterpret_cast<Node *>(p.begin()); |
895 | Node *i = reinterpret_cast<Node *>(p.end()); |
896 | while (i-- != b) |
897 | if (i->t() == t) |
898 | ++c; |
899 | return c; |
900 | } |
901 | |
902 | Q_DECLARE_SEQUENTIAL_ITERATOR(List) |
903 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List) |
904 | |
905 | QT_END_NAMESPACE |
906 | |
907 | QT_END_HEADER |
908 | |
909 | #endif // QLIST_H |
910 | |