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 QLINKEDLIST_H
41#define QLINKEDLIST_H
42
43#include <QtCore/qglobal.h>
44
45#ifndef QT_NO_LINKED_LIST
46
47#include <QtCore/qiterator.h>
48#include <QtCore/qrefcount.h>
49#include <QtCore/qcontainertools_impl.h>
50#include <QtCore/qdatastream.h>
51#include <QtCore/qtypeinfo.h>
52
53#include <algorithm>
54#include <initializer_list>
55#include <iterator>
56#include <list>
57
58
59#if 0
60// This is needed because of QTBUG-80347
61#pragma qt_class(QLinkedList)
62#pragma qt_class(QLinkedListData)
63#pragma qt_class(QLinkedListNode)
64#endif
65
66#if QT_DEPRECATED_SINCE(5, 15)
67
68QT_WARNING_PUSH
69QT_WARNING_DISABLE_DEPRECATED
70
71QT_BEGIN_NAMESPACE
72
73struct QT_DEPRECATED_VERSION_5_15 QLinkedListData
74{
75 QLinkedListData *n, *p;
76 QtPrivate::RefCount ref;
77 int size;
78 uint sharable : 1;
79
80 Q_CORE_EXPORT static const QLinkedListData shared_null;
81};
82
83template <typename T>
84struct QT_DEPRECATED_VERSION_5_15 QLinkedListNode
85{
86 inline QLinkedListNode(const T &arg): t(arg) { }
87 QLinkedListNode *n, *p;
88 T t;
89};
90
91template <class T>
92class QT_DEPRECATED_VERSION_X_5_15("Use std::list instead") QLinkedList
93{
94 typedef QLinkedListNode<T> Node;
95 union { QLinkedListData *d; QLinkedListNode<T> *e; };
96
97public:
98 inline QLinkedList() noexcept : d(const_cast<QLinkedListData *>(&QLinkedListData::shared_null)) { }
99 inline QLinkedList(const QLinkedList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach(); }
100 inline QLinkedList(std::initializer_list<T> list)
101 : QLinkedList(list.begin(), list.end()) {}
102 template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
103 inline QLinkedList(InputIterator first, InputIterator last)
104 : QLinkedList()
105 {
106 std::copy(first, last, std::back_inserter(*this));
107 }
108 ~QLinkedList();
109 QLinkedList<T> &operator=(const QLinkedList<T> &);
110 QLinkedList(QLinkedList<T> &&other) noexcept
111 : d(other.d) { other.d = const_cast<QLinkedListData *>(&QLinkedListData::shared_null); }
112 QLinkedList<T> &operator=(QLinkedList<T> &&other) noexcept
113 { QLinkedList moved(std::move(other)); swap(moved); return *this; }
114 inline void swap(QLinkedList<T> &other) noexcept { qSwap(d, other.d); }
115 bool operator==(const QLinkedList<T> &l) const;
116 inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
117
118 inline int size() const { return d->size; }
119 inline void detach()
120 { if (d->ref.isShared()) detach_helper2(this->e); }
121 inline bool isDetached() const { return !d->ref.isShared(); }
122#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
123 inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QLinkedListData::shared_null) d->sharable = sharable; }
124#endif
125 inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
126
127 inline bool isEmpty() const { return d->size == 0; }
128
129 void clear();
130
131 void append(const T &);
132 void prepend(const T &);
133 T takeFirst();
134 T takeLast();
135 int removeAll(const T &t);
136 bool removeOne(const T &t);
137 bool contains(const T &t) const;
138 int count(const T &t) const;
139
140 class const_iterator;
141
142 class iterator
143 {
144 public:
145 typedef std::bidirectional_iterator_tag iterator_category;
146 typedef qptrdiff difference_type;
147 typedef T value_type;
148 typedef T *pointer;
149 typedef T &reference;
150 Node *i;
151 inline iterator() : i(nullptr) {}
152 inline iterator(Node *n) : i(n) {}
153#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
154 iterator(const iterator &other) noexcept : i(other.i) {}
155 iterator &operator=(const iterator &other) noexcept { i = other.i; return *this; }
156 iterator(iterator &&other) noexcept : i(other.i) {}
157 iterator &operator=(iterator &&other) noexcept { return *this = other; }
158#endif
159 inline T &operator*() const { return i->t; }
160 inline T *operator->() const { return &i->t; }
161 inline bool operator==(const iterator &o) const { return i == o.i; }
162 inline bool operator!=(const iterator &o) const { return i != o.i; }
163 inline bool operator==(const const_iterator &o) const
164 { return i == o.i; }
165 inline bool operator!=(const const_iterator &o) const
166 { return i != o.i; }
167 inline iterator &operator++() { i = i->n; return *this; }
168 inline iterator operator++(int) { Node *n = i; i = i->n; return n; }
169 inline iterator &operator--() { i = i->p; return *this; }
170 inline iterator operator--(int) { Node *n = i; i = i->p; return n; }
171 inline iterator operator+(int j) const
172 { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
173 inline iterator operator-(int j) const { return operator+(-j); }
174 inline iterator &operator+=(int j) { return *this = *this + j; }
175 inline iterator &operator-=(int j) { return *this = *this - j; }
176 friend inline iterator operator+(int j, iterator k) { return k + j; }
177 };
178 friend class iterator;
179
180 class const_iterator
181 {
182 public:
183 typedef std::bidirectional_iterator_tag iterator_category;
184 typedef qptrdiff difference_type;
185 typedef T value_type;
186 typedef const T *pointer;
187 typedef const T &reference;
188 Node *i;
189 inline const_iterator() : i(nullptr) {}
190 inline const_iterator(Node *n) : i(n) {}
191 inline const_iterator(iterator ci) : i(ci.i){}
192#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
193 const_iterator(const const_iterator &other) noexcept : i(other.i) {}
194 const_iterator &operator=(const const_iterator &other) noexcept { i = other.i; return *this; }
195 const_iterator(const_iterator &&other) noexcept : i(other.i) {}
196 const_iterator &operator=(const_iterator &&other) noexcept { return *this = other; }
197#endif
198 inline const T &operator*() const { return i->t; }
199 inline const T *operator->() const { return &i->t; }
200 inline bool operator==(const const_iterator &o) const { return i == o.i; }
201 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
202 inline const_iterator &operator++() { i = i->n; return *this; }
203 inline const_iterator operator++(int) { Node *n = i; i = i->n; return n; }
204 inline const_iterator &operator--() { i = i->p; return *this; }
205 inline const_iterator operator--(int) { Node *n = i; i = i->p; return n; }
206 inline const_iterator operator+(int j) const
207 { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
208 inline const_iterator operator-(int j) const { return operator+(-j); }
209 inline const_iterator &operator+=(int j) { return *this = *this + j; }
210 inline const_iterator &operator-=(int j) { return *this = *this - j; }
211 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
212 };
213 friend class const_iterator;
214
215 // stl style
216 typedef std::reverse_iterator<iterator> reverse_iterator;
217 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
218
219 inline iterator begin() { detach(); return e->n; }
220 inline const_iterator begin() const noexcept { return e->n; }
221 inline const_iterator cbegin() const noexcept { return e->n; }
222 inline const_iterator constBegin() const noexcept { return e->n; }
223 inline iterator end() { detach(); return e; }
224 inline const_iterator end() const noexcept { return e; }
225 inline const_iterator cend() const noexcept { return e; }
226 inline const_iterator constEnd() const noexcept { return e; }
227
228 reverse_iterator rbegin() { return reverse_iterator(end()); }
229 reverse_iterator rend() { return reverse_iterator(begin()); }
230 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
231 const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
232 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
233 const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
234
235 iterator insert(iterator before, const T &t);
236 iterator erase(iterator pos);
237 iterator erase(iterator first, iterator last);
238
239 // more Qt
240 typedef iterator Iterator;
241 typedef const_iterator ConstIterator;
242 inline int count() const { return d->size; }
243 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
244 inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
245 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
246 const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
247 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
248 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
249 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
250 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
251
252 // stl compatibility
253 inline void push_back(const T &t) { append(t); }
254 inline void push_front(const T &t) { prepend(t); }
255 inline T& front() { return first(); }
256 inline const T& front() const { return first(); }
257 inline T& back() { return last(); }
258 inline const T& back() const { return last(); }
259 inline void pop_front() { removeFirst(); }
260 inline void pop_back() { removeLast(); }
261 inline bool empty() const { return isEmpty(); }
262 typedef int size_type;
263 typedef T value_type;
264 typedef value_type *pointer;
265 typedef const value_type *const_pointer;
266 typedef value_type &reference;
267 typedef const value_type &const_reference;
268 typedef qptrdiff difference_type;
269
270 static inline QLinkedList<T> fromStdList(const std::list<T> &list)
271 { QLinkedList<T> tmp; std::copy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
272 inline std::list<T> toStdList() const
273 { std::list<T> tmp; std::copy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
274
275 // comfort
276 QLinkedList<T> &operator+=(const QLinkedList<T> &l);
277 QLinkedList<T> operator+(const QLinkedList<T> &l) const;
278 inline QLinkedList<T> &operator+=(const T &t) { append(t); return *this; }
279 inline QLinkedList<T> &operator<< (const T &t) { append(t); return *this; }
280 inline QLinkedList<T> &operator<<(const QLinkedList<T> &l) { *this += l; return *this; }
281
282private:
283 void detach_helper();
284 iterator detach_helper2(iterator);
285 void freeData(QLinkedListData*);
286};
287template <typename T>
288Q_DECLARE_TYPEINFO_BODY(QLinkedList<T>, Q_MOVABLE_TYPE|Q_RELOCATABLE_TYPE);
289
290#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
291template <typename InputIterator,
292 typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
293 QtPrivate::IfIsInputIterator<InputIterator> = true>
294QLinkedList(InputIterator, InputIterator) -> QLinkedList<ValueType>;
295#endif
296
297template <typename T>
298inline QLinkedList<T>::~QLinkedList()
299{
300 if (!d->ref.deref())
301 freeData(d);
302}
303
304template <typename T>
305void QLinkedList<T>::detach_helper()
306{
307 detach_helper2(this->e);
308}
309
310template <typename T>
311typename QLinkedList<T>::iterator QLinkedList<T>::detach_helper2(iterator orgite)
312{
313 // detach and convert orgite to an iterator in the detached instance
314 bool isEndIterator = (orgite.i == this->e);
315 union { QLinkedListData *d; Node *e; } x;
316 x.d = new QLinkedListData;
317 x.d->ref.initializeOwned();
318 x.d->size = d->size;
319 x.d->sharable = true;
320 Node *original = e->n;
321 Node *copy = x.e;
322 Node *org = orgite.i;
323
324 while (original != org) {
325 QT_TRY {
326 copy->n = new Node(original->t);
327 copy->n->p = copy;
328 original = original->n;
329 copy = copy->n;
330 } QT_CATCH(...) {
331 copy->n = x.e;
332 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
333 freeData(x.d);
334 QT_RETHROW;
335 }
336 }
337 iterator r(copy);
338 while (original != e) {
339 QT_TRY {
340 copy->n = new Node(original->t);
341 copy->n->p = copy;
342 original = original->n;
343 copy = copy->n;
344 } QT_CATCH(...) {
345 copy->n = x.e;
346 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
347 freeData(x.d);
348 QT_RETHROW;
349 }
350 }
351 copy->n = x.e;
352 x.e->p = copy;
353 if (!d->ref.deref())
354 freeData(d);
355 d = x.d;
356 if (!isEndIterator)
357 ++r; // since we stored the element right before the original node.
358 return r;
359}
360
361template <typename T>
362void QLinkedList<T>::freeData(QLinkedListData *x)
363{
364 Node *y = reinterpret_cast<Node*>(x);
365 Node *i = y->n;
366 Q_ASSERT(x->ref.atomic.loadRelaxed() == 0);
367 while (i != y) {
368 Node *n = i;
369 i = i->n;
370 delete n;
371 }
372 delete x;
373}
374
375template <typename T>
376void QLinkedList<T>::clear()
377{
378 *this = QLinkedList<T>();
379}
380
381template <typename T>
382QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
383{
384 if (d != l.d) {
385 QLinkedListData *o = l.d;
386 o->ref.ref();
387 if (!d->ref.deref())
388 freeData(d);
389 d = o;
390 if (!d->sharable)
391 detach_helper();
392 }
393 return *this;
394}
395
396template <typename T>
397bool QLinkedList<T>::operator== (const QLinkedList<T> &l) const
398{
399 if (d->size != l.d->size)
400 return false;
401 if (e == l.e)
402 return true;
403 Node *i = e->n;
404 Node *il = l.e->n;
405 while (i != e) {
406 if (! (i->t == il->t))
407 return false;
408 i = i->n;
409 il = il->n;
410 }
411 return true;
412}
413
414template <typename T>
415void QLinkedList<T>::append(const T &t)
416{
417 detach();
418 Node *i = new Node(t);
419 i->n = e;
420 i->p = e->p;
421 i->p->n = i;
422 e->p = i;
423 d->size++;
424}
425
426template <typename T>
427void QLinkedList<T>::prepend(const T &t)
428{
429 detach();
430 Node *i = new Node(t);
431 i->n = e->n;
432 i->p = e;
433 i->n->p = i;
434 e->n = i;
435 d->size++;
436}
437
438template <typename T>
439int QLinkedList<T>::removeAll(const T &_t)
440{
441 detach();
442 const T t = _t;
443 Node *i = e->n;
444 int c = 0;
445 while (i != e) {
446 if (i->t == t) {
447 Node *n = i;
448 i->n->p = i->p;
449 i->p->n = i->n;
450 i = i->n;
451 delete n;
452 c++;
453 } else {
454 i = i->n;
455 }
456 }
457 d->size-=c;
458 return c;
459}
460
461template <typename T>
462bool QLinkedList<T>::removeOne(const T &_t)
463{
464 detach();
465 iterator it = std::find(begin(), end(), _t);
466 if (it != end()) {
467 erase(it);
468 return true;
469 }
470 return false;
471}
472
473template <typename T>
474inline T QLinkedList<T>::takeFirst()
475{
476 T t = std::move(first());
477 removeFirst();
478 return t;
479}
480
481template <typename T>
482inline T QLinkedList<T>::takeLast()
483{
484 T t = std::move(last());
485 removeLast();
486 return t;
487}
488
489template <typename T>
490bool QLinkedList<T>::contains(const T &t) const
491{
492 Node *i = e;
493 while ((i = i->n) != e)
494 if (i->t == t)
495 return true;
496 return false;
497}
498
499template <typename T>
500int QLinkedList<T>::count(const T &t) const
501{
502 Node *i = e;
503 int c = 0;
504 while ((i = i->n) != e)
505 if (i->t == t)
506 c++;
507 return c;
508}
509
510
511template <typename T>
512typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
513{
514 if (d->ref.isShared())
515 before = detach_helper2(before);
516
517 Node *i = before.i;
518 Node *m = new Node(t);
519 m->n = i;
520 m->p = i->p;
521 m->p->n = m;
522 i->p = m;
523 d->size++;
524 return m;
525}
526
527template <typename T>
528typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
529 typename QLinkedList<T>::iterator alast)
530{
531 while (afirst != alast)
532 erase(afirst++);
533 return alast;
534}
535
536
537template <typename T>
538typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
539{
540 if (d->ref.isShared())
541 pos = detach_helper2(pos);
542
543 Node *i = pos.i;
544 if (i != e) {
545 Node *n = i;
546 i->n->p = i->p;
547 i->p->n = i->n;
548 i = i->n;
549 delete n;
550 d->size--;
551 }
552 return i;
553}
554
555template <typename T>
556QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
557{
558 detach();
559 int n = l.d->size;
560 d->size += n;
561 Node *original = l.e->n;
562 while (n--) {
563 QT_TRY {
564 Node *copy = new Node(original->t);
565 original = original->n;
566 copy->n = e;
567 copy->p = e->p;
568 copy->p->n = copy;
569 e->p = copy;
570 } QT_CATCH(...) {
571 // restore the original list
572 while (n++<d->size)
573 removeLast();
574 QT_RETHROW;
575 }
576 }
577 return *this;
578}
579
580template <typename T>
581QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
582{
583 QLinkedList<T> n = *this;
584 n += l;
585 return n;
586}
587
588Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
589Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
590
591#ifndef QT_NO_DATASTREAM
592template <typename T>
593inline QDataStream &operator>>(QDataStream &s, QLinkedList<T> &l)
594{
595 return QtPrivate::readListBasedContainer(s, l);
596}
597
598template <typename T>
599inline QDataStream &operator<<(QDataStream &s, const QLinkedList<T> &l)
600{
601 return QtPrivate::writeSequentialContainer(s, l);
602}
603#endif
604
605QT_END_NAMESPACE
606
607Q_DECLARE_SEQUENTIAL_CONTAINER_METATYPE(QLinkedList)
608
609QT_WARNING_POP
610
611#endif // QT_DEPRECATED_SINCE(5, 15)
612
613#endif // QT_NO_LINKED_LIST
614
615#endif // QLINKEDLIST_H
616