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