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 | QT_BEGIN_NAMESPACE |
59 | |
60 | |
61 | struct 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 | |
71 | template <typename T> |
72 | struct QLinkedListNode |
73 | { |
74 | inline QLinkedListNode(const T &arg): t(arg) { } |
75 | QLinkedListNode *n, *p; |
76 | T t; |
77 | }; |
78 | |
79 | template <class T> |
80 | class QLinkedList |
81 | { |
82 | typedef QLinkedListNode<T> Node; |
83 | union { QLinkedListData *d; QLinkedListNode<T> *e; }; |
84 | |
85 | public: |
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 | |
270 | private: |
271 | void detach_helper(); |
272 | iterator detach_helper2(iterator); |
273 | void freeData(QLinkedListData*); |
274 | }; |
275 | template <typename T> |
276 | Q_DECLARE_TYPEINFO_BODY(QLinkedList<T>, Q_MOVABLE_TYPE|Q_RELOCATABLE_TYPE); |
277 | |
278 | template <typename T> |
279 | inline QLinkedList<T>::~QLinkedList() |
280 | { |
281 | if (!d->ref.deref()) |
282 | freeData(d); |
283 | } |
284 | |
285 | template <typename T> |
286 | void QLinkedList<T>::detach_helper() |
287 | { |
288 | detach_helper2(this->e); |
289 | } |
290 | |
291 | template <typename T> |
292 | typename 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 | |
342 | template <typename T> |
343 | void 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 | |
356 | template <typename T> |
357 | void QLinkedList<T>::clear() |
358 | { |
359 | *this = QLinkedList<T>(); |
360 | } |
361 | |
362 | template <typename T> |
363 | QLinkedList<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 | |
377 | template <typename T> |
378 | bool 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 | |
395 | template <typename T> |
396 | void 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 | |
407 | template <typename T> |
408 | void 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 | |
419 | template <typename T> |
420 | int 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 | |
442 | template <typename T> |
443 | bool 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 | |
454 | template <typename T> |
455 | inline T QLinkedList<T>::takeFirst() |
456 | { |
457 | T t = std::move(first()); |
458 | removeFirst(); |
459 | return t; |
460 | } |
461 | |
462 | template <typename T> |
463 | inline T QLinkedList<T>::takeLast() |
464 | { |
465 | T t = std::move(last()); |
466 | removeLast(); |
467 | return t; |
468 | } |
469 | |
470 | template <typename T> |
471 | bool 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 | |
480 | template <typename T> |
481 | int 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 | |
492 | template <typename T> |
493 | typename 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 | |
508 | template <typename T> |
509 | typename 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 | |
518 | template <typename T> |
519 | typename 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 | |
536 | template <typename T> |
537 | QLinkedList<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 | |
561 | template <typename T> |
562 | QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const |
563 | { |
564 | QLinkedList<T> n = *this; |
565 | n += l; |
566 | return n; |
567 | } |
568 | |
569 | Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList) |
570 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList) |
571 | |
572 | #ifndef QT_NO_DATASTREAM |
573 | template <typename T> |
574 | inline QDataStream &operator>>(QDataStream &s, QLinkedList<T> &l) |
575 | { |
576 | return QtPrivate::readListBasedContainer(s, l); |
577 | } |
578 | |
579 | template <typename T> |
580 | inline QDataStream &operator<<(QDataStream &s, const QLinkedList<T> &l) |
581 | { |
582 | return QtPrivate::writeSequentialContainer(s, l); |
583 | } |
584 | #endif |
585 | |
586 | QT_END_NAMESPACE |
587 | |
588 | Q_DECLARE_SEQUENTIAL_CONTAINER_METATYPE(QLinkedList) |
589 | |
590 | #endif // QT_NO_LINKED_LIST |
591 | |
592 | #endif // QLINKEDLIST_H |
593 | |