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