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(Q_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 };
163 friend class iterator;
164
165 class const_iterator
166 {
167 public:
168 typedef std::bidirectional_iterator_tag iterator_category;
169 typedef qptrdiff difference_type;
170 typedef T value_type;
171 typedef const T *pointer;
172 typedef const T &reference;
173 Node *i;
174 inline const_iterator() : i(Q_NULLPTR) {}
175 inline const_iterator(Node *n) : i(n) {}
176 inline const_iterator(iterator ci) : i(ci.i){}
177#if QT_VERSION < QT_VERSION_CHECK(6,0,0)
178 const_iterator(const const_iterator &other) Q_DECL_NOTHROW : i(other.i) {}
179 const_iterator &operator=(const const_iterator &other) Q_DECL_NOTHROW { i = other.i; return *this; }
180 const_iterator(const_iterator &&other) Q_DECL_NOTHROW : i(other.i) {}
181 const_iterator &operator=(const_iterator &&other) Q_DECL_NOTHROW { return *this = other; }
182#endif
183 inline const T &operator*() const { return i->t; }
184 inline const T *operator->() const { return &i->t; }
185 inline bool operator==(const const_iterator &o) const { return i == o.i; }
186 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
187 inline const_iterator &operator++() { i = i->n; return *this; }
188 inline const_iterator operator++(int) { Node *n = i; i = i->n; return n; }
189 inline const_iterator &operator--() { i = i->p; return *this; }
190 inline const_iterator operator--(int) { Node *n = i; i = i->p; return n; }
191 inline const_iterator operator+(int j) const
192 { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
193 inline const_iterator operator-(int j) const { return operator+(-j); }
194 inline const_iterator &operator+=(int j) { return *this = *this + j; }
195 inline const_iterator &operator-=(int j) { return *this = *this - j; }
196 };
197 friend class const_iterator;
198
199 // stl style
200 typedef std::reverse_iterator<iterator> reverse_iterator;
201 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
202
203 inline iterator begin() { detach(); return e->n; }
204 inline const_iterator begin() const Q_DECL_NOTHROW { return e->n; }
205 inline const_iterator cbegin() const Q_DECL_NOTHROW { return e->n; }
206 inline const_iterator constBegin() const Q_DECL_NOTHROW { return e->n; }
207 inline iterator end() { detach(); return e; }
208 inline const_iterator end() const Q_DECL_NOTHROW { return e; }
209 inline const_iterator cend() const Q_DECL_NOTHROW { return e; }
210 inline const_iterator constEnd() const Q_DECL_NOTHROW { return e; }
211
212 reverse_iterator rbegin() { return reverse_iterator(end()); }
213 reverse_iterator rend() { return reverse_iterator(begin()); }
214 const_reverse_iterator rbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
215 const_reverse_iterator rend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
216 const_reverse_iterator crbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
217 const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
218
219 iterator insert(iterator before, const T &t);
220 iterator erase(iterator pos);
221 iterator erase(iterator first, iterator last);
222
223 // more Qt
224 typedef iterator Iterator;
225 typedef const_iterator ConstIterator;
226 inline int count() const { return d->size; }
227 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
228 inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
229 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
230 const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
231 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
232 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
233 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
234 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
235
236 // stl compatibility
237 inline void push_back(const T &t) { append(t); }
238 inline void push_front(const T &t) { prepend(t); }
239 inline T& front() { return first(); }
240 inline const T& front() const { return first(); }
241 inline T& back() { return last(); }
242 inline const T& back() const { return last(); }
243 inline void pop_front() { removeFirst(); }
244 inline void pop_back() { removeLast(); }
245 inline bool empty() const { return isEmpty(); }
246 typedef int size_type;
247 typedef T value_type;
248 typedef value_type *pointer;
249 typedef const value_type *const_pointer;
250 typedef value_type &reference;
251 typedef const value_type &const_reference;
252 typedef qptrdiff difference_type;
253
254 static inline QLinkedList<T> fromStdList(const std::list<T> &list)
255 { QLinkedList<T> tmp; std::copy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
256 inline std::list<T> toStdList() const
257 { std::list<T> tmp; std::copy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
258
259 // comfort
260 QLinkedList<T> &operator+=(const QLinkedList<T> &l);
261 QLinkedList<T> operator+(const QLinkedList<T> &l) const;
262 inline QLinkedList<T> &operator+=(const T &t) { append(t); return *this; }
263 inline QLinkedList<T> &operator<< (const T &t) { append(t); return *this; }
264 inline QLinkedList<T> &operator<<(const QLinkedList<T> &l) { *this += l; return *this; }
265
266private:
267 void detach_helper();
268 iterator detach_helper2(iterator);
269 void freeData(QLinkedListData*);
270};
271
272template <typename T>
273inline QLinkedList<T>::~QLinkedList()
274{
275 if (!d->ref.deref())
276 freeData(d);
277}
278
279template <typename T>
280void QLinkedList<T>::detach_helper()
281{
282 detach_helper2(this->e);
283}
284
285template <typename T>
286typename QLinkedList<T>::iterator QLinkedList<T>::detach_helper2(iterator orgite)
287{
288 // detach and convert orgite to an iterator in the detached instance
289 bool isEndIterator = (orgite.i == this->e);
290 union { QLinkedListData *d; Node *e; } x;
291 x.d = new QLinkedListData;
292 x.d->ref.initializeOwned();
293 x.d->size = d->size;
294 x.d->sharable = true;
295 Node *original = e->n;
296 Node *copy = x.e;
297 Node *org = orgite.i;
298
299 while (original != org) {
300 QT_TRY {
301 copy->n = new Node(original->t);
302 copy->n->p = copy;
303 original = original->n;
304 copy = copy->n;
305 } QT_CATCH(...) {
306 copy->n = x.e;
307 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
308 freeData(x.d);
309 QT_RETHROW;
310 }
311 }
312 iterator r(copy);
313 while (original != e) {
314 QT_TRY {
315 copy->n = new Node(original->t);
316 copy->n->p = copy;
317 original = original->n;
318 copy = copy->n;
319 } QT_CATCH(...) {
320 copy->n = x.e;
321 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
322 freeData(x.d);
323 QT_RETHROW;
324 }
325 }
326 copy->n = x.e;
327 x.e->p = copy;
328 if (!d->ref.deref())
329 freeData(d);
330 d = x.d;
331 if (!isEndIterator)
332 ++r; // since we stored the element right before the original node.
333 return r;
334}
335
336template <typename T>
337void QLinkedList<T>::freeData(QLinkedListData *x)
338{
339 Node *y = reinterpret_cast<Node*>(x);
340 Node *i = y->n;
341 Q_ASSERT(x->ref.atomic.load() == 0);
342 while (i != y) {
343 Node *n = i;
344 i = i->n;
345 delete n;
346 }
347 delete x;
348}
349
350template <typename T>
351void QLinkedList<T>::clear()
352{
353 *this = QLinkedList<T>();
354}
355
356template <typename T>
357QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
358{
359 if (d != l.d) {
360 QLinkedListData *o = l.d;
361 o->ref.ref();
362 if (!d->ref.deref())
363 freeData(d);
364 d = o;
365 if (!d->sharable)
366 detach_helper();
367 }
368 return *this;
369}
370
371template <typename T>
372bool QLinkedList<T>::operator== (const QLinkedList<T> &l) const
373{
374 if (d->size != l.d->size)
375 return false;
376 if (e == l.e)
377 return true;
378 Node *i = e->n;
379 Node *il = l.e->n;
380 while (i != e) {
381 if (! (i->t == il->t))
382 return false;
383 i = i->n;
384 il = il->n;
385 }
386 return true;
387}
388
389template <typename T>
390void QLinkedList<T>::append(const T &t)
391{
392 detach();
393 Node *i = new Node(t);
394 i->n = e;
395 i->p = e->p;
396 i->p->n = i;
397 e->p = i;
398 d->size++;
399}
400
401template <typename T>
402void QLinkedList<T>::prepend(const T &t)
403{
404 detach();
405 Node *i = new Node(t);
406 i->n = e->n;
407 i->p = e;
408 i->n->p = i;
409 e->n = i;
410 d->size++;
411}
412
413template <typename T>
414int QLinkedList<T>::removeAll(const T &_t)
415{
416 detach();
417 const T t = _t;
418 Node *i = e->n;
419 int c = 0;
420 while (i != e) {
421 if (i->t == t) {
422 Node *n = i;
423 i->n->p = i->p;
424 i->p->n = i->n;
425 i = i->n;
426 delete n;
427 c++;
428 } else {
429 i = i->n;
430 }
431 }
432 d->size-=c;
433 return c;
434}
435
436template <typename T>
437bool QLinkedList<T>::removeOne(const T &_t)
438{
439 detach();
440 iterator it = std::find(begin(), end(), _t);
441 if (it != end()) {
442 erase(it);
443 return true;
444 }
445 return false;
446}
447
448template <typename T>
449inline T QLinkedList<T>::takeFirst()
450{
451 T t = std::move(first());
452 removeFirst();
453 return t;
454}
455
456template <typename T>
457inline T QLinkedList<T>::takeLast()
458{
459 T t = std::move(last());
460 removeLast();
461 return t;
462}
463
464template <typename T>
465bool QLinkedList<T>::contains(const T &t) const
466{
467 Node *i = e;
468 while ((i = i->n) != e)
469 if (i->t == t)
470 return true;
471 return false;
472}
473
474template <typename T>
475int QLinkedList<T>::count(const T &t) const
476{
477 Node *i = e;
478 int c = 0;
479 while ((i = i->n) != e)
480 if (i->t == t)
481 c++;
482 return c;
483}
484
485
486template <typename T>
487typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
488{
489 if (d->ref.isShared())
490 before = detach_helper2(before);
491
492 Node *i = before.i;
493 Node *m = new Node(t);
494 m->n = i;
495 m->p = i->p;
496 m->p->n = m;
497 i->p = m;
498 d->size++;
499 return m;
500}
501
502template <typename T>
503typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
504 typename QLinkedList<T>::iterator alast)
505{
506 while (afirst != alast)
507 erase(afirst++);
508 return alast;
509}
510
511
512template <typename T>
513typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
514{
515 if (d->ref.isShared())
516 pos = detach_helper2(pos);
517
518 Node *i = pos.i;
519 if (i != e) {
520 Node *n = i;
521 i->n->p = i->p;
522 i->p->n = i->n;
523 i = i->n;
524 delete n;
525 d->size--;
526 }
527 return i;
528}
529
530template <typename T>
531QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
532{
533 detach();
534 int n = l.d->size;
535 d->size += n;
536 Node *original = l.e->n;
537 while (n--) {
538 QT_TRY {
539 Node *copy = new Node(original->t);
540 original = original->n;
541 copy->n = e;
542 copy->p = e->p;
543 copy->p->n = copy;
544 e->p = copy;
545 } QT_CATCH(...) {
546 // restore the original list
547 while (n++<d->size)
548 removeLast();
549 QT_RETHROW;
550 }
551 }
552 return *this;
553}
554
555template <typename T>
556QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
557{
558 QLinkedList<T> n = *this;
559 n += l;
560 return n;
561}
562
563Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
564Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
565
566QT_END_NAMESPACE
567
568#endif // QLINKEDLIST_H
569