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