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: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/qatomic.h>
47
48#ifndef QT_NO_STL
49#include <iterator>
50#include <list>
51#endif
52
53QT_BEGIN_HEADER
54
55QT_BEGIN_NAMESPACE
56
57QT_MODULE(Core)
58
59struct Q_CORE_EXPORT QLinkedListData
60{
61 QLinkedListData *n, *p;
62 QBasicAtomicInt ref;
63 int size;
64 uint sharable : 1;
65
66 static QLinkedListData shared_null;
67};
68
69template <typename T>
70struct QLinkedListNode
71{
72 inline QLinkedListNode(const T &arg): t(arg) { }
73 QLinkedListNode *n, *p;
74 T t;
75};
76
77template <class T>
78class QLinkedList
79{
80 typedef QLinkedListNode<T> Node;
81 union { QLinkedListData *d; QLinkedListNode<T> *e; };
82
83public:
84 inline QLinkedList() : d(&QLinkedListData::shared_null) { d->ref.ref(); }
85 inline QLinkedList(const QLinkedList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach(); }
86 ~QLinkedList();
87 QLinkedList<T> &operator=(const QLinkedList<T> &);
88#ifdef Q_COMPILER_RVALUE_REFS
89 inline QLinkedList<T> &operator=(QLinkedList<T> &&other)
90 { qSwap(d, other.d); return *this; }
91#endif
92 inline void swap(QLinkedList<T> &other) { qSwap(d, other.d); }
93 bool operator==(const QLinkedList<T> &l) const;
94 inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
95
96 inline int size() const { return d->size; }
97 inline void detach()
98 { if (d->ref != 1) detach_helper(); }
99 inline bool isDetached() const { return d->ref == 1; }
100 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
101 inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
102
103 inline bool isEmpty() const { return d->size == 0; }
104
105 void clear();
106
107 void append(const T &);
108 void prepend(const T &);
109 T takeFirst();
110 T takeLast();
111 int removeAll(const T &t);
112 bool removeOne(const T &t);
113 bool contains(const T &t) const;
114 int count(const T &t) const;
115
116 class const_iterator;
117
118 class iterator
119 {
120 public:
121 typedef std::bidirectional_iterator_tag iterator_category;
122 typedef qptrdiff difference_type;
123 typedef T value_type;
124 typedef T *pointer;
125 typedef T &reference;
126 Node *i;
127 inline iterator() : i(0) {}
128 inline iterator(Node *n) : i(n) {}
129 inline iterator(const iterator &o) : i(o.i) {}
130 inline iterator &operator=(const iterator &o) { i = o.i; return *this; }
131 inline T &operator*() const { return i->t; }
132 inline T *operator->() const { return &i->t; }
133 inline bool operator==(const iterator &o) const { return i == o.i; }
134 inline bool operator!=(const iterator &o) const { return i != o.i; }
135 inline bool operator==(const const_iterator &o) const
136 { return i == o.i; }
137 inline bool operator!=(const const_iterator &o) const
138 { return i != o.i; }
139 inline iterator &operator++() { i = i->n; return *this; }
140 inline iterator operator++(int) { Node *n = i; i = i->n; return n; }
141 inline iterator &operator--() { i = i->p; return *this; }
142 inline iterator operator--(int) { Node *n = i; i = i->p; return n; }
143 inline iterator operator+(int j) const
144 { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
145 inline iterator operator-(int j) const { return operator+(-j); }
146 inline iterator &operator+=(int j) { return *this = *this + j; }
147 inline iterator &operator-=(int j) { return *this = *this - j; }
148 };
149 friend class iterator;
150
151 class const_iterator
152 {
153 public:
154 typedef std::bidirectional_iterator_tag iterator_category;
155 typedef qptrdiff difference_type;
156 typedef T value_type;
157 typedef const T *pointer;
158 typedef const T &reference;
159 Node *i;
160 inline const_iterator() : i(0) {}
161 inline const_iterator(Node *n) : i(n) {}
162 inline const_iterator(const const_iterator &o) : i(o.i){}
163 inline const_iterator(iterator ci) : i(ci.i){}
164 inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }
165 inline const T &operator*() const { return i->t; }
166 inline const T *operator->() const { return &i->t; }
167 inline bool operator==(const const_iterator &o) const { return i == o.i; }
168 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
169 inline const_iterator &operator++() { i = i->n; return *this; }
170 inline const_iterator operator++(int) { Node *n = i; i = i->n; return n; }
171 inline const_iterator &operator--() { i = i->p; return *this; }
172 inline const_iterator operator--(int) { Node *n = i; i = i->p; return n; }
173 inline const_iterator operator+(int j) const
174 { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
175 inline const_iterator operator-(int j) const { return operator+(-j); }
176 inline const_iterator &operator+=(int j) { return *this = *this + j; }
177 inline const_iterator &operator-=(int j) { return *this = *this - j; }
178 };
179 friend class const_iterator;
180
181 // stl style
182 inline iterator begin() { detach(); return e->n; }
183 inline const_iterator begin() const { return e->n; }
184 inline const_iterator constBegin() const { return e->n; }
185 inline iterator end() { detach(); return e; }
186 inline const_iterator end() const { return e; }
187 inline const_iterator constEnd() const { return e; }
188 iterator insert(iterator before, const T &t);
189 iterator erase(iterator pos);
190 iterator erase(iterator first, iterator last);
191
192 // more Qt
193 typedef iterator Iterator;
194 typedef const_iterator ConstIterator;
195 inline int count() const { return d->size; }
196 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
197 inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
198 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
199 const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
200 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
201 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
202 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
203 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
204
205 // stl compatibility
206 inline void push_back(const T &t) { append(t); }
207 inline void push_front(const T &t) { prepend(t); }
208 inline T& front() { return first(); }
209 inline const T& front() const { return first(); }
210 inline T& back() { return last(); }
211 inline const T& back() const { return last(); }
212 inline void pop_front() { removeFirst(); }
213 inline void pop_back() { removeLast(); }
214 inline bool empty() const { return isEmpty(); }
215 typedef int size_type;
216 typedef T value_type;
217 typedef value_type *pointer;
218 typedef const value_type *const_pointer;
219 typedef value_type &reference;
220 typedef const value_type &const_reference;
221 typedef qptrdiff difference_type;
222
223#ifndef QT_NO_STL
224 static inline QLinkedList<T> fromStdList(const std::list<T> &list)
225 { QLinkedList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
226 inline std::list<T> toStdList() const
227 { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
228#endif
229
230#ifdef QT3_SUPPORT
231 // compatibility
232 inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }
233 inline QT3_SUPPORT int findIndex(const T& t) const
234 { int i=0; for (const_iterator it = begin(); it != end(); ++it, ++i) if(*it == t) return i; return -1;}
235 inline QT3_SUPPORT iterator find(iterator from, const T& t)
236 { while (from != end() && !(*from == t)) ++from; return from; }
237 inline QT3_SUPPORT iterator find(const T& t)
238 { return find(begin(), t); }
239 inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const
240 { while (from != end() && !(*from == t)) ++from; return from; }
241 inline QT3_SUPPORT const_iterator find(const T& t) const
242 { return find(begin(), t); }
243#endif
244
245 // comfort
246 QLinkedList<T> &operator+=(const QLinkedList<T> &l);
247 QLinkedList<T> operator+(const QLinkedList<T> &l) const;
248 inline QLinkedList<T> &operator+=(const T &t) { append(t); return *this; }
249 inline QLinkedList<T> &operator<< (const T &t) { append(t); return *this; }
250 inline QLinkedList<T> &operator<<(const QLinkedList<T> &l) { *this += l; return *this; }
251
252private:
253 void detach_helper();
254 void free(QLinkedListData*);
255};
256
257template <typename T>
258inline QLinkedList<T>::~QLinkedList()
259{
260 if (!d)
261 return;
262 if (!d->ref.deref())
263 free(d);
264}
265
266template <typename T>
267void QLinkedList<T>::detach_helper()
268{
269 union { QLinkedListData *d; Node *e; } x;
270 x.d = new QLinkedListData;
271 x.d->ref = 1;
272 x.d->size = d->size;
273 x.d->sharable = true;
274 Node *original = e->n;
275 Node *copy = x.e;
276 while (original != e) {
277 QT_TRY {
278 copy->n = new Node(original->t);
279 copy->n->p = copy;
280 original = original->n;
281 copy = copy->n;
282 } QT_CATCH(...) {
283 copy->n = x.e;
284 free(x.d);
285 QT_RETHROW;
286 }
287 }
288 copy->n = x.e;
289 x.e->p = copy;
290 if (!d->ref.deref())
291 free(d);
292 d = x.d;
293}
294
295template <typename T>
296void QLinkedList<T>::free(QLinkedListData *x)
297{
298 Node *y = reinterpret_cast<Node*>(x);
299 Node *i = y->n;
300 if (x->ref == 0) {
301 while(i != y) {
302 Node *n = i;
303 i = i->n;
304 delete n;
305 }
306 delete x;
307 }
308}
309
310template <typename T>
311void QLinkedList<T>::clear()
312{
313 *this = QLinkedList<T>();
314}
315
316template <typename T>
317QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
318{
319 if (d != l.d) {
320 QLinkedListData *o = l.d;
321 o->ref.ref();
322 if (!d->ref.deref())
323 free(d);
324 d = o;
325 if (!d->sharable)
326 detach_helper();
327 }
328 return *this;
329}
330
331template <typename T>
332bool QLinkedList<T>::operator== (const QLinkedList<T> &l) const
333{
334 if (d->size != l.d->size)
335 return false;
336 if (e == l.e)
337 return true;
338 Node *i = e->n;
339 Node *il = l.e->n;
340 while (i != e) {
341 if (! (i->t == il->t))
342 return false;
343 i = i->n;
344 il = il->n;
345 }
346 return true;
347}
348
349template <typename T>
350void QLinkedList<T>::append(const T &t)
351{
352 detach();
353 Node *i = new Node(t);
354 i->n = e;
355 i->p = e->p;
356 i->p->n = i;
357 e->p = i;
358 d->size++;
359}
360
361template <typename T>
362void QLinkedList<T>::prepend(const T &t)
363{
364 detach();
365 Node *i = new Node(t);
366 i->n = e->n;
367 i->p = e;
368 i->n->p = i;
369 e->n = i;
370 d->size++;
371}
372
373template <typename T>
374int QLinkedList<T>::removeAll(const T &_t)
375{
376 detach();
377 const T t = _t;
378 Node *i = e->n;
379 int c = 0;
380 while (i != e) {
381 if (i->t == t) {
382 Node *n = i;
383 i->n->p = i->p;
384 i->p->n = i->n;
385 i = i->n;
386 delete n;
387 c++;
388 } else {
389 i = i->n;
390 }
391 }
392 d->size-=c;
393 return c;
394}
395
396template <typename T>
397bool QLinkedList<T>::removeOne(const T &_t)
398{
399 detach();
400 iterator it = qFind(begin(), end(), _t);
401 if (it != end()) {
402 erase(it);
403 return true;
404 }
405 return false;
406}
407
408template <typename T>
409inline T QLinkedList<T>::takeFirst()
410{
411 T t = first();
412 removeFirst();
413 return t;
414}
415
416template <typename T>
417inline T QLinkedList<T>::takeLast()
418{
419 T t = last();
420 removeLast();
421 return t;
422}
423
424template <typename T>
425bool QLinkedList<T>::contains(const T &t) const
426{
427 Node *i = e;
428 while ((i = i->n) != e)
429 if (i->t == t)
430 return true;
431 return false;
432}
433
434template <typename T>
435int QLinkedList<T>::count(const T &t) const
436{
437 Node *i = e;
438 int c = 0;
439 while ((i = i->n) != e)
440 if (i->t == t)
441 c++;
442 return c;
443}
444
445
446template <typename T>
447typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
448{
449 Node *i = before.i;
450 Node *m = new Node(t);
451 m->n = i;
452 m->p = i->p;
453 m->p->n = m;
454 i->p = m;
455 d->size++;
456 return m;
457}
458
459template <typename T>
460typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
461 typename QLinkedList<T>::iterator alast)
462{
463 while (afirst != alast)
464 erase(afirst++);
465 return alast;
466}
467
468
469template <typename T>
470typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
471{
472 detach();
473 Node *i = pos.i;
474 if (i != e) {
475 Node *n = i;
476 i->n->p = i->p;
477 i->p->n = i->n;
478 i = i->n;
479 delete n;
480 d->size--;
481 }
482 return i;
483}
484
485template <typename T>
486QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
487{
488 detach();
489 int n = l.d->size;
490 d->size += n;
491 Node *original = l.e->n;
492 while (n--) {
493 QT_TRY {
494 Node *copy = new Node(original->t);
495 original = original->n;
496 copy->n = e;
497 copy->p = e->p;
498 copy->p->n = copy;
499 e->p = copy;
500 } QT_CATCH(...) {
501 // restore the original list
502 while (n++<d->size)
503 removeLast();
504 QT_RETHROW;
505 }
506 }
507 return *this;
508}
509
510template <typename T>
511QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
512{
513 QLinkedList<T> n = *this;
514 n += l;
515 return n;
516}
517
518Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
519Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
520
521QT_END_NAMESPACE
522
523QT_END_HEADER
524
525#endif // QLINKEDLIST_H
526