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