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