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