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 QLIST_H
41#define QLIST_H
42
43#include <QtCore/qalgorithms.h>
44#include <QtCore/qiterator.h>
45#include <QtCore/qrefcount.h>
46#include <QtCore/qarraydata.h>
47#include <QtCore/qhashfunctions.h>
48#include <QtCore/qvector.h>
49
50#include <iterator>
51#include <list>
52#include <algorithm>
53#ifdef Q_COMPILER_INITIALIZER_LISTS
54#include <initializer_list>
55#endif
56
57#include <stdlib.h>
58#include <new>
59#include <limits.h>
60#include <string.h>
61
62#ifdef Q_CC_MSVC
63#pragma warning( push )
64#pragma warning( disable : 4127 ) // "conditional expression is constant"
65#endif
66
67QT_BEGIN_NAMESPACE
68
69
70template <typename T> class QVector;
71template <typename T> class QSet;
72
73template <typename T> struct QListSpecialMethods
74{
75protected:
76 ~QListSpecialMethods() {}
77};
78template <> struct QListSpecialMethods<QByteArray>;
79template <> struct QListSpecialMethods<QString>;
80
81struct Q_CORE_EXPORT QListData {
82 // tags for tag-dispatching of QList implementations,
83 // based on QList's three different memory layouts:
84 struct NotArrayCompatibleLayout {};
85 struct NotIndirectLayout {};
86 struct ArrayCompatibleLayout : NotIndirectLayout {}; // data laid out like a C array
87 struct InlineWithPaddingLayout : NotArrayCompatibleLayout, NotIndirectLayout {}; // data laid out like a C array with padding
88 struct IndirectLayout : NotArrayCompatibleLayout {}; // data allocated on the heap
89
90 struct Data {
91 QtPrivate::RefCount ref;
92 int alloc, begin, end;
93 void *array[1];
94 };
95 enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };
96
97 Data *detach(int alloc);
98 Data *detach_grow(int *i, int n);
99 void realloc(int alloc);
100 void realloc_grow(int growth);
101 inline void dispose() { dispose(d); }
102 static void dispose(Data *d);
103 static const Data shared_null;
104 Data *d;
105 void **erase(void **xi);
106 void **append(int n);
107 void **append();
108 void **append(const QListData &l);
109 void **prepend();
110 void **insert(int i);
111 void remove(int i);
112 void remove(int i, int n);
113 void move(int from, int to);
114 inline int size() const Q_DECL_NOTHROW { return d->end - d->begin; }
115 inline bool isEmpty() const Q_DECL_NOTHROW { return d->end == d->begin; }
116 inline void **at(int i) const Q_DECL_NOTHROW { return d->array + d->begin + i; }
117 inline void **begin() const Q_DECL_NOTHROW { return d->array + d->begin; }
118 inline void **end() const Q_DECL_NOTHROW { return d->array + d->end; }
119};
120
121template <typename T>
122class QList
123#ifndef Q_QDOC
124 : public QListSpecialMethods<T>
125#endif
126{
127public:
128 struct MemoryLayout
129 : std::conditional<
130 // must stay isStatic until ### Qt 6 for BC reasons (don't use !isRelocatable)!
131 QTypeInfo<T>::isStatic || QTypeInfo<T>::isLarge,
132 QListData::IndirectLayout,
133 typename std::conditional<
134 sizeof(T) == sizeof(void*),
135 QListData::ArrayCompatibleLayout,
136 QListData::InlineWithPaddingLayout
137 >::type>::type {};
138private:
139 struct Node { void *v;
140#if defined(Q_CC_BOR)
141 Q_INLINE_TEMPLATE T &t();
142#else
143 Q_INLINE_TEMPLATE T &t()
144 { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic
145 ? v : this); }
146#endif
147 };
148
149 union { QListData p; QListData::Data *d; };
150
151public:
152 inline QList() Q_DECL_NOTHROW : d(const_cast<QListData::Data *>(&QListData::shared_null)) { }
153 QList(const QList<T> &l);
154 ~QList();
155 QList<T> &operator=(const QList<T> &l);
156#ifdef Q_COMPILER_RVALUE_REFS
157 inline QList(QList<T> &&other) Q_DECL_NOTHROW
158 : d(other.d) { other.d = const_cast<QListData::Data *>(&QListData::shared_null); }
159 inline QList &operator=(QList<T> &&other) Q_DECL_NOTHROW
160 { QList moved(std::move(other)); swap(moved); return *this; }
161#endif
162 inline void swap(QList<T> &other) Q_DECL_NOTHROW { qSwap(d, other.d); }
163#ifdef Q_COMPILER_INITIALIZER_LISTS
164 inline QList(std::initializer_list<T> args)
165 : d(const_cast<QListData::Data *>(&QListData::shared_null))
166 { reserve(int(args.size())); std::copy(args.begin(), args.end(), std::back_inserter(*this)); }
167#endif
168 bool operator==(const QList<T> &l) const;
169 inline bool operator!=(const QList<T> &l) const { return !(*this == l); }
170
171 inline int size() const Q_DECL_NOTHROW { return p.size(); }
172
173 inline void detach() { if (d->ref.isShared()) detach_helper(); }
174
175 inline void detachShared()
176 {
177 // The "this->" qualification is needed for GCCE.
178 if (d->ref.isShared() && this->d != &QListData::shared_null)
179 detach_helper();
180 }
181
182 inline bool isDetached() const { return !d->ref.isShared(); }
183#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
184 inline void setSharable(bool sharable)
185 {
186 if (sharable == d->ref.isSharable())
187 return;
188 if (!sharable)
189 detach();
190 if (d != &QListData::shared_null)
191 d->ref.setSharable(sharable);
192 }
193#endif
194 inline bool isSharedWith(const QList<T> &other) const Q_DECL_NOTHROW { return d == other.d; }
195
196 inline bool isEmpty() const Q_DECL_NOTHROW { return p.isEmpty(); }
197
198 void clear();
199
200 const T &at(int i) const;
201 const T &operator[](int i) const;
202 T &operator[](int i);
203
204 void reserve(int size);
205 void append(const T &t);
206 void append(const QList<T> &t);
207 void prepend(const T &t);
208 void insert(int i, const T &t);
209 void replace(int i, const T &t);
210 void removeAt(int i);
211 int removeAll(const T &t);
212 bool removeOne(const T &t);
213 T takeAt(int i);
214 T takeFirst();
215 T takeLast();
216 void move(int from, int to);
217 void swapItemsAt(int i, int j);
218#if QT_DEPRECATED_SINCE(5, 13) && QT_VERSION < QT_VERSION_CHECK(6,0,0)
219 QT_DEPRECATED_X("Use QList<T>::swapItemsAt()")
220 void swap(int i, int j) { swapItemsAt(i, j); }
221#endif
222 int indexOf(const T &t, int from = 0) const;
223 int lastIndexOf(const T &t, int from = -1) const;
224 bool contains(const T &t) const;
225 int count(const T &t) const;
226
227 class const_iterator;
228
229 class iterator {
230 public:
231 Node *i;
232 typedef std::random_access_iterator_tag iterator_category;
233 // ### Qt6: use int
234 typedef qptrdiff difference_type;
235 typedef T value_type;
236 typedef T *pointer;
237 typedef T &reference;
238
239 inline iterator() Q_DECL_NOTHROW : i(nullptr) {}
240 inline iterator(Node *n) Q_DECL_NOTHROW : i(n) {}
241#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
242 // can't remove it in Qt 5, since doing so would make the type trivial,
243 // which changes the way it's passed to functions by value.
244 inline iterator(const iterator &o) Q_DECL_NOTHROW : i(o.i){}
245#endif
246 inline T &operator*() const { return i->t(); }
247 inline T *operator->() const { return &i->t(); }
248 inline T &operator[](difference_type j) const { return i[j].t(); }
249 inline bool operator==(const iterator &o) const Q_DECL_NOTHROW { return i == o.i; }
250 inline bool operator!=(const iterator &o) const Q_DECL_NOTHROW { return i != o.i; }
251 inline bool operator<(const iterator& other) const Q_DECL_NOTHROW { return i < other.i; }
252 inline bool operator<=(const iterator& other) const Q_DECL_NOTHROW { return i <= other.i; }
253 inline bool operator>(const iterator& other) const Q_DECL_NOTHROW { return i > other.i; }
254 inline bool operator>=(const iterator& other) const Q_DECL_NOTHROW { return i >= other.i; }
255#ifndef QT_STRICT_ITERATORS
256 inline bool operator==(const const_iterator &o) const Q_DECL_NOTHROW
257 { return i == o.i; }
258 inline bool operator!=(const const_iterator &o) const Q_DECL_NOTHROW
259 { return i != o.i; }
260 inline bool operator<(const const_iterator& other) const Q_DECL_NOTHROW
261 { return i < other.i; }
262 inline bool operator<=(const const_iterator& other) const Q_DECL_NOTHROW
263 { return i <= other.i; }
264 inline bool operator>(const const_iterator& other) const Q_DECL_NOTHROW
265 { return i > other.i; }
266 inline bool operator>=(const const_iterator& other) const Q_DECL_NOTHROW
267 { return i >= other.i; }
268#endif
269 inline iterator &operator++() { ++i; return *this; }
270 inline iterator operator++(int) { Node *n = i; ++i; return n; }
271 inline iterator &operator--() { i--; return *this; }
272 inline iterator operator--(int) { Node *n = i; i--; return n; }
273 inline iterator &operator+=(difference_type j) { i+=j; return *this; }
274 inline iterator &operator-=(difference_type j) { i-=j; return *this; }
275 inline iterator operator+(difference_type j) const { return iterator(i+j); }
276 inline iterator operator-(difference_type j) const { return iterator(i-j); }
277 friend inline iterator operator+(difference_type j, iterator k) { return k + j; }
278 inline int operator-(iterator j) const { return int(i - j.i); }
279 };
280 friend class iterator;
281
282 class const_iterator {
283 public:
284 Node *i;
285 typedef std::random_access_iterator_tag iterator_category;
286 // ### Qt6: use int
287 typedef qptrdiff difference_type;
288 typedef T value_type;
289 typedef const T *pointer;
290 typedef const T &reference;
291
292 inline const_iterator() Q_DECL_NOTHROW : i(nullptr) {}
293 inline const_iterator(Node *n) Q_DECL_NOTHROW : i(n) {}
294#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
295 // can't remove it in Qt 5, since doing so would make the type trivial,
296 // which changes the way it's passed to functions by value.
297 inline const_iterator(const const_iterator &o) Q_DECL_NOTHROW : i(o.i) {}
298#endif
299#ifdef QT_STRICT_ITERATORS
300 inline explicit const_iterator(const iterator &o) Q_DECL_NOTHROW : i(o.i) {}
301#else
302 inline const_iterator(const iterator &o) Q_DECL_NOTHROW : i(o.i) {}
303#endif
304 inline const T &operator*() const { return i->t(); }
305 inline const T *operator->() const { return &i->t(); }
306 inline const T &operator[](difference_type j) const { return i[j].t(); }
307 inline bool operator==(const const_iterator &o) const Q_DECL_NOTHROW { return i == o.i; }
308 inline bool operator!=(const const_iterator &o) const Q_DECL_NOTHROW { return i != o.i; }
309 inline bool operator<(const const_iterator& other) const Q_DECL_NOTHROW { return i < other.i; }
310 inline bool operator<=(const const_iterator& other) const Q_DECL_NOTHROW { return i <= other.i; }
311 inline bool operator>(const const_iterator& other) const Q_DECL_NOTHROW { return i > other.i; }
312 inline bool operator>=(const const_iterator& other) const Q_DECL_NOTHROW { return i >= other.i; }
313 inline const_iterator &operator++() { ++i; return *this; }
314 inline const_iterator operator++(int) { Node *n = i; ++i; return n; }
315 inline const_iterator &operator--() { i--; return *this; }
316 inline const_iterator operator--(int) { Node *n = i; i--; return n; }
317 inline const_iterator &operator+=(difference_type j) { i+=j; return *this; }
318 inline const_iterator &operator-=(difference_type j) { i-=j; return *this; }
319 inline const_iterator operator+(difference_type j) const { return const_iterator(i+j); }
320 inline const_iterator operator-(difference_type j) const { return const_iterator(i-j); }
321 friend inline const_iterator operator+(difference_type j, const_iterator k) { return k + j; }
322 inline int operator-(const_iterator j) const { return int(i - j.i); }
323 };
324 friend class const_iterator;
325
326 // stl style
327 typedef std::reverse_iterator<iterator> reverse_iterator;
328 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
329 inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); }
330 inline const_iterator begin() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.begin()); }
331 inline const_iterator cbegin() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.begin()); }
332 inline const_iterator constBegin() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.begin()); }
333 inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); }
334 inline const_iterator end() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.end()); }
335 inline const_iterator cend() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.end()); }
336 inline const_iterator constEnd() const Q_DECL_NOTHROW { return reinterpret_cast<Node *>(p.end()); }
337 reverse_iterator rbegin() { return reverse_iterator(end()); }
338 reverse_iterator rend() { return reverse_iterator(begin()); }
339 const_reverse_iterator rbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
340 const_reverse_iterator rend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
341 const_reverse_iterator crbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
342 const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
343 iterator insert(iterator before, const T &t);
344 iterator erase(iterator pos);
345 iterator erase(iterator first, iterator last);
346
347 // more Qt
348 typedef iterator Iterator;
349 typedef const_iterator ConstIterator;
350 inline int count() const { return p.size(); }
351 inline int length() const { return p.size(); } // Same as count()
352 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
353 inline const T& constFirst() const { return first(); }
354 inline const T& first() const { Q_ASSERT(!isEmpty()); return at(0); }
355 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
356 const T& last() const { Q_ASSERT(!isEmpty()); return at(count() - 1); }
357 inline const T& constLast() const { return last(); }
358 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
359 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
360 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
361 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
362 QList<T> mid(int pos, int length = -1) const;
363
364 T value(int i) const;
365 T value(int i, const T &defaultValue) const;
366
367 // stl compatibility
368 inline void push_back(const T &t) { append(t); }
369 inline void push_front(const T &t) { prepend(t); }
370 inline T& front() { return first(); }
371 inline const T& front() const { return first(); }
372 inline T& back() { return last(); }
373 inline const T& back() const { return last(); }
374 inline void pop_front() { removeFirst(); }
375 inline void pop_back() { removeLast(); }
376 inline bool empty() const { return isEmpty(); }
377 typedef int size_type;
378 typedef T value_type;
379 typedef value_type *pointer;
380 typedef const value_type *const_pointer;
381 typedef value_type &reference;
382 typedef const value_type &const_reference;
383 // ### Qt6: use int
384 typedef qptrdiff difference_type;
385
386 // comfort
387 QList<T> &operator+=(const QList<T> &l);
388 inline QList<T> operator+(const QList<T> &l) const
389 { QList n = *this; n += l; return n; }
390 inline QList<T> &operator+=(const T &t)
391 { append(t); return *this; }
392 inline QList<T> &operator<< (const T &t)
393 { append(t); return *this; }
394 inline QList<T> &operator<<(const QList<T> &l)
395 { *this += l; return *this; }
396
397 QVector<T> toVector() const;
398 QSet<T> toSet() const;
399
400 static QList<T> fromVector(const QVector<T> &vector);
401 static QList<T> fromSet(const QSet<T> &set);
402
403 static inline QList<T> fromStdList(const std::list<T> &list)
404 { QList<T> tmp; std::copy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
405 inline std::list<T> toStdList() const
406 { std::list<T> tmp; std::copy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
407
408private:
409 Node *detach_helper_grow(int i, int n);
410 void detach_helper(int alloc);
411 void detach_helper();
412 void dealloc(QListData::Data *d);
413
414 void node_construct(Node *n, const T &t);
415 void node_destruct(Node *n);
416 void node_copy(Node *from, Node *to, Node *src);
417 void node_destruct(Node *from, Node *to);
418
419 bool isValidIterator(const iterator &i) const Q_DECL_NOTHROW
420 {
421 const std::less<const Node *> less = {};
422 return !less(i.i, cbegin().i) && !less(cend().i, i.i);
423 }
424
425private:
426 inline bool op_eq_impl(const QList &other, QListData::NotArrayCompatibleLayout) const;
427 inline bool op_eq_impl(const QList &other, QListData::ArrayCompatibleLayout) const;
428 inline bool contains_impl(const T &, QListData::NotArrayCompatibleLayout) const;
429 inline bool contains_impl(const T &, QListData::ArrayCompatibleLayout) const;
430 inline int count_impl(const T &, QListData::NotArrayCompatibleLayout) const;
431 inline int count_impl(const T &, QListData::ArrayCompatibleLayout) const;
432};
433
434#if defined(Q_CC_BOR)
435template <typename T>
436Q_INLINE_TEMPLATE T &QList<T>::Node::t()
437{ return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; }
438#endif
439
440template <typename T>
441Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t)
442{
443 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t);
444 else if (QTypeInfo<T>::isComplex) new (n) T(t);
445#if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__)
446 // This violates pointer aliasing rules, but it is known to be safe (and silent)
447 // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which
448 // set the same define are assumed to be safe.
449 else *reinterpret_cast<T*>(n) = t;
450#else
451 // This is always safe, but penaltizes unoptimized builds a lot.
452 else ::memcpy(n, static_cast<const void *>(&t), sizeof(T));
453#endif
454}
455
456template <typename T>
457Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n)
458{
459 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v);
460 else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T();
461}
462
463template <typename T>
464Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src)
465{
466 Node *current = from;
467 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
468 QT_TRY {
469 while(current != to) {
470 current->v = new T(*reinterpret_cast<T*>(src->v));
471 ++current;
472 ++src;
473 }
474 } QT_CATCH(...) {
475 while (current-- != from)
476 delete reinterpret_cast<T*>(current->v);
477 QT_RETHROW;
478 }
479
480 } else if (QTypeInfo<T>::isComplex) {
481 QT_TRY {
482 while(current != to) {
483 new (current) T(*reinterpret_cast<T*>(src));
484 ++current;
485 ++src;
486 }
487 } QT_CATCH(...) {
488 while (current-- != from)
489 (reinterpret_cast<T*>(current))->~T();
490 QT_RETHROW;
491 }
492 } else {
493 if (src != from && to - from > 0)
494 memcpy(from, src, (to - from) * sizeof(Node));
495 }
496}
497
498template <typename T>
499Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to)
500{
501 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic)
502 while(from != to) --to, delete reinterpret_cast<T*>(to->v);
503 else if (QTypeInfo<T>::isComplex)
504 while (from != to) --to, reinterpret_cast<T*>(to)->~T();
505}
506
507template <typename T>
508Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l)
509{
510 if (d != l.d) {
511 QList<T> tmp(l);
512 tmp.swap(*this);
513 }
514 return *this;
515}
516template <typename T>
517inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t)
518{
519 Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
520
521 int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin()));
522 Node *n = 0;
523 if (d->ref.isShared())
524 n = detach_helper_grow(iBefore, 1);
525 else
526 n = reinterpret_cast<Node *>(p.insert(iBefore));
527 QT_TRY {
528 node_construct(n, t);
529 } QT_CATCH(...) {
530 p.remove(iBefore);
531 QT_RETHROW;
532 }
533 return n;
534}
535template <typename T>
536inline typename QList<T>::iterator QList<T>::erase(iterator it)
537{
538 Q_ASSERT_X(isValidIterator(it), "QList::erase", "The specified iterator argument 'it' is invalid");
539 if (d->ref.isShared()) {
540 int offset = int(it.i - reinterpret_cast<Node *>(p.begin()));
541 it = begin(); // implies detach()
542 it += offset;
543 }
544 node_destruct(it.i);
545 return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i)));
546}
547template <typename T>
548inline const T &QList<T>::at(int i) const
549{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at", "index out of range");
550 return reinterpret_cast<Node *>(p.at(i))->t(); }
551template <typename T>
552inline const T &QList<T>::operator[](int i) const
553{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
554 return reinterpret_cast<Node *>(p.at(i))->t(); }
555template <typename T>
556inline T &QList<T>::operator[](int i)
557{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
558 detach(); return reinterpret_cast<Node *>(p.at(i))->t(); }
559template <typename T>
560inline void QList<T>::removeAt(int i)
561{ if(i >= 0 && i < p.size()) { detach();
562 node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i); } }
563template <typename T>
564inline T QList<T>::takeAt(int i)
565{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::take", "index out of range");
566 detach(); Node *n = reinterpret_cast<Node *>(p.at(i)); T t = std::move(n->t()); node_destruct(n);
567 p.remove(i); return t; }
568template <typename T>
569inline T QList<T>::takeFirst()
570{ T t = std::move(first()); removeFirst(); return t; }
571template <typename T>
572inline T QList<T>::takeLast()
573{ T t = std::move(last()); removeLast(); return t; }
574
575template <typename T>
576Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc)
577{
578 if (d->alloc < alloc) {
579 if (d->ref.isShared())
580 detach_helper(alloc);
581 else
582 p.realloc(alloc);
583 }
584}
585
586template <typename T>
587Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t)
588{
589 if (d->ref.isShared()) {
590 Node *n = detach_helper_grow(INT_MAX, 1);
591 QT_TRY {
592 node_construct(n, t);
593 } QT_CATCH(...) {
594 --d->end;
595 QT_RETHROW;
596 }
597 } else {
598 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
599 Node *n = reinterpret_cast<Node *>(p.append());
600 QT_TRY {
601 node_construct(n, t);
602 } QT_CATCH(...) {
603 --d->end;
604 QT_RETHROW;
605 }
606 } else {
607 Node *n, copy;
608 node_construct(&copy, t); // t might be a reference to an object in the array
609 QT_TRY {
610 n = reinterpret_cast<Node *>(p.append());;
611 } QT_CATCH(...) {
612 node_destruct(&copy);
613 QT_RETHROW;
614 }
615 *n = copy;
616 }
617 }
618}
619
620template <typename T>
621inline void QList<T>::prepend(const T &t)
622{
623 if (d->ref.isShared()) {
624 Node *n = detach_helper_grow(0, 1);
625 QT_TRY {
626 node_construct(n, t);
627 } QT_CATCH(...) {
628 ++d->begin;
629 QT_RETHROW;
630 }
631 } else {
632 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
633 Node *n = reinterpret_cast<Node *>(p.prepend());
634 QT_TRY {
635 node_construct(n, t);
636 } QT_CATCH(...) {
637 ++d->begin;
638 QT_RETHROW;
639 }
640 } else {
641 Node *n, copy;
642 node_construct(&copy, t); // t might be a reference to an object in the array
643 QT_TRY {
644 n = reinterpret_cast<Node *>(p.prepend());;
645 } QT_CATCH(...) {
646 node_destruct(&copy);
647 QT_RETHROW;
648 }
649 *n = copy;
650 }
651 }
652}
653
654template <typename T>
655inline void QList<T>::insert(int i, const T &t)
656{
657 if (d->ref.isShared()) {
658 Node *n = detach_helper_grow(i, 1);
659 QT_TRY {
660 node_construct(n, t);
661 } QT_CATCH(...) {
662 p.remove(i);
663 QT_RETHROW;
664 }
665 } else {
666 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) {
667 Node *n = reinterpret_cast<Node *>(p.insert(i));
668 QT_TRY {
669 node_construct(n, t);
670 } QT_CATCH(...) {
671 p.remove(i);
672 QT_RETHROW;
673 }
674 } else {
675 Node *n, copy;
676 node_construct(&copy, t); // t might be a reference to an object in the array
677 QT_TRY {
678 n = reinterpret_cast<Node *>(p.insert(i));;
679 } QT_CATCH(...) {
680 node_destruct(&copy);
681 QT_RETHROW;
682 }
683 *n = copy;
684 }
685 }
686}
687
688template <typename T>
689inline void QList<T>::replace(int i, const T &t)
690{
691 Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range");
692 detach();
693 reinterpret_cast<Node *>(p.at(i))->t() = t;
694}
695
696template <typename T>
697inline void QList<T>::swapItemsAt(int i, int j)
698{
699 Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(),
700 "QList<T>::swap", "index out of range");
701 detach();
702 std::swap(d->array[d->begin + i], d->array[d->begin + j]);
703}
704
705template <typename T>
706inline void QList<T>::move(int from, int to)
707{
708 Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(),
709 "QList<T>::move", "index out of range");
710 detach();
711 p.move(from, to);
712}
713
714template<typename T>
715Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const
716{
717 using namespace QtPrivate;
718 switch (QContainerImplHelper::mid(size(), &pos, &alength)) {
719 case QContainerImplHelper::Null:
720 case QContainerImplHelper::Empty:
721 return QList<T>();
722 case QContainerImplHelper::Full:
723 return *this;
724 case QContainerImplHelper::Subset:
725 break;
726 }
727
728 QList<T> cpy;
729 if (alength <= 0)
730 return cpy;
731 cpy.reserve(alength);
732 cpy.d->end = alength;
733 QT_TRY {
734 cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()),
735 reinterpret_cast<Node *>(cpy.p.end()),
736 reinterpret_cast<Node *>(p.begin() + pos));
737 } QT_CATCH(...) {
738 // restore the old end
739 cpy.d->end = 0;
740 QT_RETHROW;
741 }
742 return cpy;
743}
744
745template<typename T>
746Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const
747{
748 if (i < 0 || i >= p.size()) {
749 return T();
750 }
751 return reinterpret_cast<Node *>(p.at(i))->t();
752}
753
754template<typename T>
755Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const
756{
757 return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t());
758}
759
760template <typename T>
761Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c)
762{
763 Node *n = reinterpret_cast<Node *>(p.begin());
764 QListData::Data *x = p.detach_grow(&i, c);
765 QT_TRY {
766 node_copy(reinterpret_cast<Node *>(p.begin()),
767 reinterpret_cast<Node *>(p.begin() + i), n);
768 } QT_CATCH(...) {
769 p.dispose();
770 d = x;
771 QT_RETHROW;
772 }
773 QT_TRY {
774 node_copy(reinterpret_cast<Node *>(p.begin() + i + c),
775 reinterpret_cast<Node *>(p.end()), n + i);
776 } QT_CATCH(...) {
777 node_destruct(reinterpret_cast<Node *>(p.begin()),
778 reinterpret_cast<Node *>(p.begin() + i));
779 p.dispose();
780 d = x;
781 QT_RETHROW;
782 }
783
784 if (!x->ref.deref())
785 dealloc(x);
786
787 return reinterpret_cast<Node *>(p.begin() + i);
788}
789
790template <typename T>
791Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc)
792{
793 Node *n = reinterpret_cast<Node *>(p.begin());
794 QListData::Data *x = p.detach(alloc);
795 QT_TRY {
796 node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n);
797 } QT_CATCH(...) {
798 p.dispose();
799 d = x;
800 QT_RETHROW;
801 }
802
803 if (!x->ref.deref())
804 dealloc(x);
805}
806
807template <typename T>
808Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper()
809{
810 detach_helper(d->alloc);
811}
812
813template <typename T>
814Q_OUTOFLINE_TEMPLATE QList<T>::QList(const QList<T> &l)
815 : QListSpecialMethods<T>(l), d(l.d)
816{
817 if (!d->ref.ref()) {
818 p.detach(d->alloc);
819
820 QT_TRY {
821 node_copy(reinterpret_cast<Node *>(p.begin()),
822 reinterpret_cast<Node *>(p.end()),
823 reinterpret_cast<Node *>(l.p.begin()));
824 } QT_CATCH(...) {
825 QListData::dispose(d);
826 QT_RETHROW;
827 }
828 }
829}
830
831template <typename T>
832Q_OUTOFLINE_TEMPLATE QList<T>::~QList()
833{
834 if (!d->ref.deref())
835 dealloc(d);
836}
837
838template <typename T>
839Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
840{
841 if (d == l.d)
842 return true;
843 if (p.size() != l.p.size())
844 return false;
845 return this->op_eq_impl(l, MemoryLayout());
846}
847
848template <typename T>
849inline bool QList<T>::op_eq_impl(const QList &l, QListData::NotArrayCompatibleLayout) const
850{
851 Node *i = reinterpret_cast<Node *>(p.begin());
852 Node *e = reinterpret_cast<Node *>(p.end());
853 Node *li = reinterpret_cast<Node *>(l.p.begin());
854 for (; i != e; ++i, ++li) {
855 if (!(i->t() == li->t()))
856 return false;
857 }
858 return true;
859}
860
861template <typename T>
862inline bool QList<T>::op_eq_impl(const QList &l, QListData::ArrayCompatibleLayout) const
863{
864 const T *lb = reinterpret_cast<const T*>(l.p.begin());
865 const T *b = reinterpret_cast<const T*>(p.begin());
866 const T *e = reinterpret_cast<const T*>(p.end());
867 return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(lb, l.p.size()));
868}
869
870template <typename T>
871Q_OUTOFLINE_TEMPLATE void QList<T>::dealloc(QListData::Data *data)
872{
873 node_destruct(reinterpret_cast<Node *>(data->array + data->begin),
874 reinterpret_cast<Node *>(data->array + data->end));
875 QListData::dispose(data);
876}
877
878
879template <typename T>
880Q_OUTOFLINE_TEMPLATE void QList<T>::clear()
881{
882 *this = QList<T>();
883}
884
885template <typename T>
886Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t)
887{
888 int index = indexOf(_t);
889 if (index == -1)
890 return 0;
891
892 const T t = _t;
893 detach();
894
895 Node *i = reinterpret_cast<Node *>(p.at(index));
896 Node *e = reinterpret_cast<Node *>(p.end());
897 Node *n = i;
898 node_destruct(i);
899 while (++i != e) {
900 if (i->t() == t)
901 node_destruct(i);
902 else
903 *n++ = *i;
904 }
905
906 int removedCount = int(e - n);
907 d->end -= removedCount;
908 return removedCount;
909}
910
911template <typename T>
912Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t)
913{
914 int index = indexOf(_t);
915 if (index != -1) {
916 removeAt(index);
917 return true;
918 }
919 return false;
920}
921
922template <typename T>
923Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst,
924 typename QList<T>::iterator alast)
925{
926 Q_ASSERT_X(isValidIterator(afirst), "QList::erase", "The specified iterator argument 'afirst' is invalid");
927 Q_ASSERT_X(isValidIterator(alast), "QList::erase", "The specified iterator argument 'alast' is invalid");
928
929 if (d->ref.isShared()) {
930 // ### A block is erased and a detach is needed. We should shrink and only copy relevant items.
931 int offsetfirst = int(afirst.i - reinterpret_cast<Node *>(p.begin()));
932 int offsetlast = int(alast.i - reinterpret_cast<Node *>(p.begin()));
933 afirst = begin(); // implies detach()
934 alast = afirst;
935 afirst += offsetfirst;
936 alast += offsetlast;
937 }
938
939 for (Node *n = afirst.i; n < alast.i; ++n)
940 node_destruct(n);
941 int idx = afirst - begin();
942 p.remove(idx, alast - afirst);
943 return begin() + idx;
944}
945
946template <typename T>
947Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l)
948{
949 if (!l.isEmpty()) {
950 if (d == &QListData::shared_null) {
951 *this = l;
952 } else {
953 Node *n = (d->ref.isShared())
954 ? detach_helper_grow(INT_MAX, l.size())
955 : reinterpret_cast<Node *>(p.append(l.p));
956 QT_TRY {
957 node_copy(n, reinterpret_cast<Node *>(p.end()),
958 reinterpret_cast<Node *>(l.p.begin()));
959 } QT_CATCH(...) {
960 // restore the old end
961 d->end -= int(reinterpret_cast<Node *>(p.end()) - n);
962 QT_RETHROW;
963 }
964 }
965 }
966 return *this;
967}
968
969template <typename T>
970inline void QList<T>::append(const QList<T> &t)
971{
972 *this += t;
973}
974
975template <typename T>
976Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const
977{
978 if (from < 0)
979 from = qMax(from + p.size(), 0);
980 if (from < p.size()) {
981 Node *n = reinterpret_cast<Node *>(p.at(from -1));
982 Node *e = reinterpret_cast<Node *>(p.end());
983 while (++n != e)
984 if (n->t() == t)
985 return int(n - reinterpret_cast<Node *>(p.begin()));
986 }
987 return -1;
988}
989
990template <typename T>
991Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const
992{
993 if (from < 0)
994 from += p.size();
995 else if (from >= p.size())
996 from = p.size()-1;
997 if (from >= 0) {
998 Node *b = reinterpret_cast<Node *>(p.begin());
999 Node *n = reinterpret_cast<Node *>(p.at(from + 1));
1000 while (n-- != b) {
1001 if (n->t() == t)
1002 return n - b;
1003 }
1004 }
1005 return -1;
1006}
1007
1008template <typename T>
1009Q_OUTOFLINE_TEMPLATE bool QList<T>::contains(const T &t) const
1010{
1011 return contains_impl(t, MemoryLayout());
1012}
1013
1014template <typename T>
1015inline bool QList<T>::contains_impl(const T &t, QListData::NotArrayCompatibleLayout) const
1016{
1017 Node *e = reinterpret_cast<Node *>(p.end());
1018 Node *i = reinterpret_cast<Node *>(p.begin());
1019 for (; i != e; ++i)
1020 if (i->t() == t)
1021 return true;
1022 return false;
1023}
1024
1025template <typename T>
1026inline bool QList<T>::contains_impl(const T &t, QListData::ArrayCompatibleLayout) const
1027{
1028 const T *b = reinterpret_cast<const T*>(p.begin());
1029 const T *e = reinterpret_cast<const T*>(p.end());
1030 return std::find(b, e, t) != e;
1031}
1032
1033template <typename T>
1034Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const
1035{
1036 return this->count_impl(t, MemoryLayout());
1037}
1038
1039template <typename T>
1040inline int QList<T>::count_impl(const T &t, QListData::NotArrayCompatibleLayout) const
1041{
1042 int c = 0;
1043 Node *e = reinterpret_cast<Node *>(p.end());
1044 Node *i = reinterpret_cast<Node *>(p.begin());
1045 for (; i != e; ++i)
1046 if (i->t() == t)
1047 ++c;
1048 return c;
1049}
1050
1051template <typename T>
1052inline int QList<T>::count_impl(const T &t, QListData::ArrayCompatibleLayout) const
1053{
1054 return int(std::count(reinterpret_cast<const T*>(p.begin()),
1055 reinterpret_cast<const T*>(p.end()),
1056 t));
1057}
1058
1059template <typename T>
1060Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const
1061{
1062 QVector<T> result(size());
1063 for (int i = 0; i < size(); ++i)
1064 result[i] = at(i);
1065 return result;
1066}
1067
1068template <typename T>
1069QList<T> QList<T>::fromVector(const QVector<T> &vector)
1070{
1071 return vector.toList();
1072}
1073
1074template <typename T>
1075Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const
1076{
1077 QList<T> result;
1078 result.reserve(size());
1079 for (int i = 0; i < size(); ++i)
1080 result.append(at(i));
1081 return result;
1082}
1083
1084template <typename T>
1085QVector<T> QVector<T>::fromList(const QList<T> &list)
1086{
1087 return list.toVector();
1088}
1089
1090Q_DECLARE_SEQUENTIAL_ITERATOR(List)
1091Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List)
1092
1093template <typename T>
1094uint qHash(const QList<T> &key, uint seed = 0)
1095 Q_DECL_NOEXCEPT_EXPR(noexcept(qHashRange(key.cbegin(), key.cend(), seed)))
1096{
1097 return qHashRange(key.cbegin(), key.cend(), seed);
1098}
1099
1100template <typename T>
1101bool operator<(const QList<T> &lhs, const QList<T> &rhs)
1102 Q_DECL_NOEXCEPT_EXPR(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(),
1103 rhs.begin(), rhs.end())))
1104{
1105 return std::lexicographical_compare(lhs.begin(), lhs.end(),
1106 rhs.begin(), rhs.end());
1107}
1108
1109template <typename T>
1110inline bool operator>(const QList<T> &lhs, const QList<T> &rhs)
1111 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
1112{
1113 return rhs < lhs;
1114}
1115
1116template <typename T>
1117inline bool operator<=(const QList<T> &lhs, const QList<T> &rhs)
1118 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
1119{
1120 return !(lhs > rhs);
1121}
1122
1123template <typename T>
1124inline bool operator>=(const QList<T> &lhs, const QList<T> &rhs)
1125 Q_DECL_NOEXCEPT_EXPR(noexcept(lhs < rhs))
1126{
1127 return !(lhs < rhs);
1128}
1129
1130QT_END_NAMESPACE
1131
1132#include <QtCore/qbytearraylist.h>
1133#include <QtCore/qstringlist.h>
1134
1135#ifdef Q_CC_MSVC
1136#pragma warning( pop )
1137#endif
1138
1139#endif // QLIST_H
1140