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