1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QT5LINKEDLIST_H
5#define QT5LINKEDLIST_H
6
7#include <QtCore5Compat/qcore5global.h>
8
9#include <QtCore/qiterator.h>
10#include <QtCore/qrefcount.h>
11#include <QtCore/qcontainertools_impl.h>
12#include <QtCore/qdatastream.h>
13#include <QtCore/qmetatype.h>
14#include <QtCore/qtypeinfo.h>
15
16#include <algorithm>
17#include <initializer_list>
18#include <iterator>
19#include <list>
20
21QT_BEGIN_NAMESPACE
22
23struct Q_CORE5COMPAT_EXPORT QLinkedListData
24{
25 QLinkedListData *n, *p;
26 QtPrivate::RefCount ref;
27 int size;
28 uint sharable : 1;
29
30 static const QLinkedListData shared_null;
31};
32
33template<typename T>
34struct QLinkedListNode
35{
36 inline QLinkedListNode(const T &arg) : t(arg) {}
37 QLinkedListNode *n, *p;
38 T t;
39};
40
41template<class T>
42class QLinkedList
43{
44 typedef QLinkedListNode<T> Node;
45 union {
46 QLinkedListData *d;
47 QLinkedListNode<T> *e;
48 };
49
50public:
51 inline QLinkedList() noexcept : d(const_cast<QLinkedListData *>(&QLinkedListData::shared_null))
52 {
53 }
54 inline QLinkedList(const QLinkedList<T> &l) : d(l.d)
55 {
56 d->ref.ref();
57 if (!d->sharable)
58 detach();
59 }
60 inline QLinkedList(std::initializer_list<T> list) : QLinkedList(list.begin(), list.end()) {}
61 template<typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
62 inline QLinkedList(InputIterator first, InputIterator last) : QLinkedList()
63 {
64 std::copy(first, last, std::back_inserter(*this));
65 }
66 ~QLinkedList();
67 QLinkedList<T> &operator=(const QLinkedList<T> &);
68 QLinkedList(QLinkedList<T> &&other) noexcept : d(other.d)
69 {
70 other.d = const_cast<QLinkedListData *>(&QLinkedListData::shared_null);
71 }
72 QLinkedList<T> &operator=(QLinkedList<T> &&other) noexcept
73 {
74 QLinkedList moved(std::move(other));
75 swap(other&: moved);
76 return *this;
77 }
78 void swap(QLinkedList &other) noexcept { qt_ptr_swap(lhs&: d, rhs&: other.d); }
79 bool operator==(const QLinkedList<T> &l) const;
80 inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
81
82 inline int size() const { return d->size; }
83 inline void detach()
84 {
85 if (d->ref.isShared())
86 detach_helper2(this->e);
87 }
88 inline bool isDetached() const { return !d->ref.isShared(); }
89 inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
90
91 inline bool isEmpty() const { return d->size == 0; }
92
93 void clear();
94
95 void append(const T &);
96 void prepend(const T &);
97 T takeFirst();
98 T takeLast();
99 int removeAll(const T &t);
100 bool removeOne(const T &t);
101 bool contains(const T &t) const;
102 int count(const T &t) const;
103
104 class const_iterator;
105
106 class iterator
107 {
108 public:
109 typedef std::bidirectional_iterator_tag iterator_category;
110 typedef qptrdiff difference_type;
111 typedef T value_type;
112 typedef T *pointer;
113 typedef T &reference;
114 Node *i;
115 inline iterator() : i(nullptr) {}
116 inline iterator(Node *n) : i(n) {}
117#if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
118 iterator(const iterator &other) noexcept : i(other.i) {}
119 iterator &operator=(const iterator &other) noexcept
120 {
121 i = other.i;
122 return *this;
123 }
124 iterator(iterator &&other) noexcept : i(other.i) {}
125 iterator &operator=(iterator &&other) noexcept { return *this = other; }
126#endif
127 inline T &operator*() const { return i->t; }
128 inline T *operator->() const { return &i->t; }
129 inline bool operator==(const iterator &o) const { return i == o.i; }
130 inline bool operator!=(const iterator &o) const { return i != o.i; }
131 inline bool operator==(const const_iterator &o) const { return i == o.i; }
132 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
133 inline iterator &operator++()
134 {
135 i = i->n;
136 return *this;
137 }
138 inline iterator operator++(int)
139 {
140 Node *n = i;
141 i = i->n;
142 return n;
143 }
144 inline iterator &operator--()
145 {
146 i = i->p;
147 return *this;
148 }
149 inline iterator operator--(int)
150 {
151 Node *n = i;
152 i = i->p;
153 return n;
154 }
155 inline iterator operator+(int j) const
156 {
157 Node *n = i;
158 if (j > 0)
159 while (j--)
160 n = n->n;
161 else
162 while (j++)
163 n = n->p;
164 return n;
165 }
166 inline iterator operator-(int j) const { return operator+(j: -j); }
167 inline iterator &operator+=(int j) { return *this = *this + j; }
168 inline iterator &operator-=(int j) { return *this = *this - j; }
169 friend inline iterator operator+(int j, iterator k) { return k + j; }
170 };
171 friend class iterator;
172
173 class const_iterator
174 {
175 public:
176 typedef std::bidirectional_iterator_tag iterator_category;
177 typedef qptrdiff difference_type;
178 typedef T value_type;
179 typedef const T *pointer;
180 typedef const T &reference;
181 Node *i;
182 inline const_iterator() : i(nullptr) {}
183 inline const_iterator(Node *n) : i(n) {}
184 inline const_iterator(iterator ci) : i(ci.i) {}
185#if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
186 const_iterator(const const_iterator &other) noexcept : i(other.i) {}
187 const_iterator &operator=(const const_iterator &other) noexcept
188 {
189 i = other.i;
190 return *this;
191 }
192 const_iterator(const_iterator &&other) noexcept : i(other.i) {}
193 const_iterator &operator=(const_iterator &&other) noexcept { return *this = other; }
194#endif
195 inline const T &operator*() const { return i->t; }
196 inline const T *operator->() const { return &i->t; }
197 inline bool operator==(const const_iterator &o) const { return i == o.i; }
198 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
199 inline const_iterator &operator++()
200 {
201 i = i->n;
202 return *this;
203 }
204 inline const_iterator operator++(int)
205 {
206 Node *n = i;
207 i = i->n;
208 return n;
209 }
210 inline const_iterator &operator--()
211 {
212 i = i->p;
213 return *this;
214 }
215 inline const_iterator operator--(int)
216 {
217 Node *n = i;
218 i = i->p;
219 return n;
220 }
221 inline const_iterator operator+(int j) const
222 {
223 Node *n = i;
224 if (j > 0)
225 while (j--)
226 n = n->n;
227 else
228 while (j++)
229 n = n->p;
230 return n;
231 }
232 inline const_iterator operator-(int j) const { return operator+(j: -j); }
233 inline const_iterator &operator+=(int j) { return *this = *this + j; }
234 inline const_iterator &operator-=(int j) { return *this = *this - j; }
235 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
236 };
237 friend class const_iterator;
238
239 // stl style
240 typedef std::reverse_iterator<iterator> reverse_iterator;
241 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
242
243 inline iterator begin()
244 {
245 detach();
246 return e->n;
247 }
248 inline const_iterator begin() const noexcept { return e->n; }
249 inline const_iterator cbegin() const noexcept { return e->n; }
250 inline const_iterator constBegin() const noexcept { return e->n; }
251 inline iterator end()
252 {
253 detach();
254 return e;
255 }
256 inline const_iterator end() const noexcept { return e; }
257 inline const_iterator cend() const noexcept { return e; }
258 inline const_iterator constEnd() const noexcept { return e; }
259
260 reverse_iterator rbegin() { return reverse_iterator(end()); }
261 reverse_iterator rend() { return reverse_iterator(begin()); }
262 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
263 const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
264 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
265 const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
266
267 iterator insert(iterator before, const T &t);
268 iterator erase(iterator pos);
269 iterator erase(iterator first, iterator last);
270
271 // more Qt
272 typedef iterator Iterator;
273 typedef const_iterator ConstIterator;
274 inline int count() const { return d->size; }
275 inline T &first()
276 {
277 Q_ASSERT(!isEmpty());
278 return *begin();
279 }
280 inline const T &first() const
281 {
282 Q_ASSERT(!isEmpty());
283 return *begin();
284 }
285 T &last()
286 {
287 Q_ASSERT(!isEmpty());
288 return *(--end());
289 }
290 const T &last() const
291 {
292 Q_ASSERT(!isEmpty());
293 return *(--end());
294 }
295 inline void removeFirst()
296 {
297 Q_ASSERT(!isEmpty());
298 erase(begin());
299 }
300 inline void removeLast()
301 {
302 Q_ASSERT(!isEmpty());
303 erase(--end());
304 }
305 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
306 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
307
308 // stl compatibility
309 inline void push_back(const T &t) { append(t); }
310 inline void push_front(const T &t) { prepend(t); }
311 inline T &front() { return first(); }
312 inline const T &front() const { return first(); }
313 inline T &back() { return last(); }
314 inline const T &back() const { return last(); }
315 inline void pop_front() { removeFirst(); }
316 inline void pop_back() { removeLast(); }
317 inline bool empty() const { return isEmpty(); }
318 typedef int size_type;
319 typedef T value_type;
320 typedef value_type *pointer;
321 typedef const value_type *const_pointer;
322 typedef value_type &reference;
323 typedef const value_type &const_reference;
324 typedef qptrdiff difference_type;
325
326 static inline QLinkedList<T> fromStdList(const std::list<T> &list)
327 {
328 QLinkedList<T> tmp;
329 std::copy(list.begin(), list.end(), std::back_inserter(tmp));
330 return tmp;
331 }
332 inline std::list<T> toStdList() const
333 {
334 std::list<T> tmp;
335 std::copy(constBegin(), constEnd(), std::back_inserter(tmp));
336 return tmp;
337 }
338
339 // comfort
340 QLinkedList<T> &operator+=(const QLinkedList<T> &l);
341 QLinkedList<T> operator+(const QLinkedList<T> &l) const;
342 inline QLinkedList<T> &operator+=(const T &t)
343 {
344 append(t);
345 return *this;
346 }
347 inline QLinkedList<T> &operator<<(const T &t)
348 {
349 append(t);
350 return *this;
351 }
352 inline QLinkedList<T> &operator<<(const QLinkedList<T> &l)
353 {
354 *this += l;
355 return *this;
356 }
357
358private:
359 void detach_helper();
360 iterator detach_helper2(iterator);
361 void freeData(QLinkedListData *);
362};
363
364#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
365template<typename InputIterator,
366 typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
367 QtPrivate::IfIsInputIterator<InputIterator> = true>
368QLinkedList(InputIterator, InputIterator)->QLinkedList<ValueType>;
369#endif
370
371template<typename T>
372inline QLinkedList<T>::~QLinkedList()
373{
374 if (!d->ref.deref())
375 freeData(d);
376}
377
378template<typename T>
379void QLinkedList<T>::detach_helper()
380{
381 detach_helper2(this->e);
382}
383
384template<typename T>
385typename QLinkedList<T>::iterator QLinkedList<T>::detach_helper2(iterator orgite)
386{
387 // detach and convert orgite to an iterator in the detached instance
388 bool isEndIterator = (orgite.i == this->e);
389 union {
390 QLinkedListData *d;
391 Node *e;
392 } x;
393 x.d = new QLinkedListData;
394 x.d->ref.initializeOwned();
395 x.d->size = d->size;
396 x.d->sharable = true;
397 Node *original = e->n;
398 Node *copy = x.e;
399 Node *org = orgite.i;
400
401 while (original != org) {
402 QT_TRY
403 {
404 copy->n = new Node(original->t);
405 copy->n->p = copy;
406 original = original->n;
407 copy = copy->n;
408 }
409 QT_CATCH(...)
410 {
411 copy->n = x.e;
412 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
413 freeData(x.d);
414 QT_RETHROW;
415 }
416 }
417 iterator r(copy);
418 while (original != e) {
419 QT_TRY
420 {
421 copy->n = new Node(original->t);
422 copy->n->p = copy;
423 original = original->n;
424 copy = copy->n;
425 }
426 QT_CATCH(...)
427 {
428 copy->n = x.e;
429 Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
430 freeData(x.d);
431 QT_RETHROW;
432 }
433 }
434 copy->n = x.e;
435 x.e->p = copy;
436 if (!d->ref.deref())
437 freeData(d);
438 d = x.d;
439 if (!isEndIterator)
440 ++r; // since we stored the element right before the original node.
441 return r;
442}
443
444template<typename T>
445void QLinkedList<T>::freeData(QLinkedListData *x)
446{
447 Node *y = reinterpret_cast<Node *>(x);
448 Node *i = y->n;
449 Q_ASSERT(x->ref.atomic.loadRelaxed() == 0);
450 while (i != y) {
451 Node *n = i;
452 i = i->n;
453 delete n;
454 }
455 delete x;
456}
457
458template<typename T>
459void QLinkedList<T>::clear()
460{
461 *this = QLinkedList<T>();
462}
463
464template<typename T>
465QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
466{
467 if (d != l.d) {
468 QLinkedListData *o = l.d;
469 o->ref.ref();
470 if (!d->ref.deref())
471 freeData(x: d);
472 d = o;
473 if (!d->sharable)
474 detach_helper();
475 }
476 return *this;
477}
478
479template<typename T>
480bool QLinkedList<T>::operator==(const QLinkedList<T> &l) const
481{
482 if (d->size != l.d->size)
483 return false;
484 if (e == l.e)
485 return true;
486 Node *i = e->n;
487 Node *il = l.e->n;
488 while (i != e) {
489 if (!(i->t == il->t))
490 return false;
491 i = i->n;
492 il = il->n;
493 }
494 return true;
495}
496
497template<typename T>
498void QLinkedList<T>::append(const T &t)
499{
500 detach();
501 Node *i = new Node(t);
502 i->n = e;
503 i->p = e->p;
504 i->p->n = i;
505 e->p = i;
506 d->size++;
507}
508
509template<typename T>
510void QLinkedList<T>::prepend(const T &t)
511{
512 detach();
513 Node *i = new Node(t);
514 i->n = e->n;
515 i->p = e;
516 i->n->p = i;
517 e->n = i;
518 d->size++;
519}
520
521template<typename T>
522int QLinkedList<T>::removeAll(const T &_t)
523{
524 detach();
525 const T t = _t;
526 Node *i = e->n;
527 int c = 0;
528 while (i != e) {
529 if (i->t == t) {
530 Node *n = i;
531 i->n->p = i->p;
532 i->p->n = i->n;
533 i = i->n;
534 delete n;
535 c++;
536 } else {
537 i = i->n;
538 }
539 }
540 d->size -= c;
541 return c;
542}
543
544template<typename T>
545bool QLinkedList<T>::removeOne(const T &_t)
546{
547 detach();
548 iterator it = std::find(begin(), end(), _t);
549 if (it != end()) {
550 erase(it);
551 return true;
552 }
553 return false;
554}
555
556template<typename T>
557inline T QLinkedList<T>::takeFirst()
558{
559 T t = std::move(first());
560 removeFirst();
561 return t;
562}
563
564template<typename T>
565inline T QLinkedList<T>::takeLast()
566{
567 T t = std::move(last());
568 removeLast();
569 return t;
570}
571
572template<typename T>
573bool QLinkedList<T>::contains(const T &t) const
574{
575 Node *i = e;
576 while ((i = i->n) != e)
577 if (i->t == t)
578 return true;
579 return false;
580}
581
582template<typename T>
583int QLinkedList<T>::count(const T &t) const
584{
585 Node *i = e;
586 int c = 0;
587 while ((i = i->n) != e)
588 if (i->t == t)
589 c++;
590 return c;
591}
592
593template<typename T>
594typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
595{
596 if (d->ref.isShared())
597 before = detach_helper2(orgite: before);
598
599 Node *i = before.i;
600 Node *m = new Node(t);
601 m->n = i;
602 m->p = i->p;
603 m->p->n = m;
604 i->p = m;
605 d->size++;
606 return m;
607}
608
609template<typename T>
610typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
611 typename QLinkedList<T>::iterator alast)
612{
613 while (afirst != alast)
614 erase(afirst++);
615 return alast;
616}
617
618template<typename T>
619typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
620{
621 if (d->ref.isShared())
622 pos = detach_helper2(orgite: pos);
623
624 Node *i = pos.i;
625 if (i != e) {
626 Node *n = i;
627 i->n->p = i->p;
628 i->p->n = i->n;
629 i = i->n;
630 delete n;
631 d->size--;
632 }
633 return i;
634}
635
636template<typename T>
637QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
638{
639 detach();
640 int n = l.d->size;
641 d->size += n;
642 Node *original = l.e->n;
643 while (n--) {
644 QT_TRY
645 {
646 Node *copy = new Node(original->t);
647 original = original->n;
648 copy->n = e;
649 copy->p = e->p;
650 copy->p->n = copy;
651 e->p = copy;
652 }
653 QT_CATCH(...)
654 {
655 // restore the original list
656 while (n++ < d->size)
657 removeLast();
658 QT_RETHROW;
659 }
660 }
661 return *this;
662}
663
664template<typename T>
665QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
666{
667 QLinkedList<T> n = *this;
668 n += l;
669 return n;
670}
671
672Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
673Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
674
675#ifndef QT_NO_DATASTREAM
676template<typename T>
677inline QDataStreamIfHasIStreamOperatorsContainer<QLinkedList<T>, T>
678operator>>(QDataStream &s, QLinkedList<T> &l)
679{
680 return QtPrivate::readListBasedContainer(s, l);
681}
682
683template<typename T>
684inline QDataStreamIfHasOStreamOperatorsContainer<QLinkedList<T>, T>
685operator<<(QDataStream &s, const QLinkedList<T> &l)
686{
687 return QtPrivate::writeSequentialContainer(s, l);
688}
689#endif
690
691template<typename T>
692Q_DECLARE_TYPEINFO_BODY(QLinkedList<T>, Q_RELOCATABLE_TYPE);
693
694QT_END_NAMESPACE
695
696Q_DECLARE_SEQUENTIAL_CONTAINER_METATYPE(QLinkedList)
697
698#endif // QT5LINKEDLIST_H
699

source code of qt5compat/src/core5/tools/qlinkedlist.h