1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://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 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 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
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
53 QT_BEGIN_HEADER
54
55 QT_BEGIN_NAMESPACE
56
57 QT_MODULE(Core)
58
59 struct 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
69 template <typename T>
70 struct QLinkedListNode
71 {
QLinkedListNodeQLinkedListNode72 inline QLinkedListNode(const T &arg): t(arg) { }
73 QLinkedListNode *n, *p;
74 T t;
75 };
76
77 template <class T>
78 class QLinkedList
79 {
80 typedef QLinkedListNode<T> Node;
81 union { QLinkedListData *d; QLinkedListNode<T> *e; };
82
83 public:
QLinkedList()84 inline QLinkedList() : d(&QLinkedListData::shared_null) { d->ref.ref(); }
QLinkedList(const QLinkedList<T> & l)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
swap(QLinkedList<T> & other)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
size()96 inline int size() const { return d->size; }
detach()97 inline void detach()
98 { if (d->ref != 1) detach_helper(); }
isDetached()99 inline bool isDetached() const { return d->ref == 1; }
setSharable(bool sharable)100 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
isSharedWith(const QLinkedList<T> & other)101 inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
102
isEmpty()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;
iterator()127 inline iterator() : i(0) {}
iterator(Node * n)128 inline iterator(Node *n) : i(n) {}
iterator(const iterator & o)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;
const_iterator()160 inline const_iterator() : i(0) {}
const_iterator(Node * n)161 inline const_iterator(Node *n) : i(n) {}
const_iterator(const const_iterator & o)162 inline const_iterator(const const_iterator &o) : i(o.i){}
const_iterator(iterator ci)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
begin()182 inline iterator begin() { detach(); return e->n; }
begin()183 inline const_iterator begin() const { return e->n; }
constBegin()184 inline const_iterator constBegin() const { return e->n; }
end()185 inline iterator end() { detach(); return e; }
end()186 inline const_iterator end() const { return e; }
constEnd()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;
count()195 inline int count() const { return d->size; }
first()196 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
first()197 inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
last()198 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
last()199 const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
removeFirst()200 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
removeLast()201 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
startsWith(const T & t)202 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
endsWith(const T & t)203 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
204
205 // stl compatibility
push_back(const T & t)206 inline void push_back(const T &t) { append(t); }
push_front(const T & t)207 inline void push_front(const T &t) { prepend(t); }
front()208 inline T& front() { return first(); }
front()209 inline const T& front() const { return first(); }
back()210 inline T& back() { return last(); }
back()211 inline const T& back() const { return last(); }
pop_front()212 inline void pop_front() { removeFirst(); }
pop_back()213 inline void pop_back() { removeLast(); }
empty()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
fromStdList(const std::list<T> & list)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; }
toStdList()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
remove(iterator pos)232 inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }
findIndex(const T & t)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;}
find(iterator from,const T & t)235 inline QT3_SUPPORT iterator find(iterator from, const T& t)
236 { while (from != end() && !(*from == t)) ++from; return from; }
find(const T & t)237 inline QT3_SUPPORT iterator find(const T& t)
238 { return find(begin(), t); }
find(const_iterator from,const T & t)239 inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const
240 { while (from != end() && !(*from == t)) ++from; return from; }
find(const T & t)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
252 private:
253 void detach_helper();
254 void free(QLinkedListData*);
255 };
256
257 template <typename T>
~QLinkedList()258 inline QLinkedList<T>::~QLinkedList()
259 {
260 if (!d)
261 return;
262 if (!d->ref.deref())
263 free(d);
264 }
265
266 template <typename T>
detach_helper()267 void 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
295 template <typename T>
free(QLinkedListData * x)296 void 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
310 template <typename T>
clear()311 void QLinkedList<T>::clear()
312 {
313 *this = QLinkedList<T>();
314 }
315
316 template <typename T>
317 QLinkedList<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
331 template <typename T>
332 bool 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
349 template <typename T>
append(const T & t)350 void 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
361 template <typename T>
prepend(const T & t)362 void 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
373 template <typename T>
removeAll(const T & _t)374 int 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
396 template <typename T>
removeOne(const T & _t)397 bool 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
408 template <typename T>
takeFirst()409 inline T QLinkedList<T>::takeFirst()
410 {
411 T t = first();
412 removeFirst();
413 return t;
414 }
415
416 template <typename T>
takeLast()417 inline T QLinkedList<T>::takeLast()
418 {
419 T t = last();
420 removeLast();
421 return t;
422 }
423
424 template <typename T>
contains(const T & t)425 bool 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
434 template <typename T>
count(const T & t)435 int 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
446 template <typename T>
insert(iterator before,const T & t)447 typename 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
459 template <typename T>
erase(typename QLinkedList<T>::iterator afirst,typename QLinkedList<T>::iterator alast)460 typename 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
469 template <typename T>
erase(iterator pos)470 typename 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
485 template <typename T>
486 QLinkedList<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;
QT_CATCH(...)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
510 template <typename T>
511 QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
512 {
513 QLinkedList<T> n = *this;
514 n += l;
515 return n;
516 }
517
518 Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
519 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
520
521 QT_END_NAMESPACE
522
523 QT_END_HEADER
524
525 #endif // QLINKEDLIST_H
526