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