1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
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 Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/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 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
36 | ** |
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 | { |
72 | 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: |
84 | inline QLinkedList() : d(&QLinkedListData::shared_null) { d->ref.ref(); } |
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 |
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 | |
96 | inline int size() const { return d->size; } |
97 | inline void detach() |
98 | { if (d->ref != 1) detach_helper(); } |
99 | inline bool isDetached() const { return d->ref == 1; } |
100 | inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
101 | inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; } |
102 | |
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; |
127 | inline iterator() : i(0) {} |
128 | inline iterator(Node *n) : i(n) {} |
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; |
160 | inline const_iterator() : i(0) {} |
161 | inline const_iterator(Node *n) : i(n) {} |
162 | inline const_iterator(const const_iterator &o) : i(o.i){} |
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 |
182 | inline iterator begin() { detach(); return e->n; } |
183 | inline const_iterator begin() const { return e->n; } |
184 | inline const_iterator constBegin() const { return e->n; } |
185 | inline iterator end() { detach(); return e; } |
186 | inline const_iterator end() const { return e; } |
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; |
195 | inline int count() const { return d->size; } |
196 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } |
197 | inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); } |
198 | T& last() { Q_ASSERT(!isEmpty()); return *(--end()); } |
199 | const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); } |
200 | inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); } |
201 | inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); } |
202 | inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } |
203 | inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } |
204 | |
205 | // stl compatibility |
206 | inline void push_back(const T &t) { append(t); } |
207 | inline void push_front(const T &t) { prepend(t); } |
208 | inline T& front() { return first(); } |
209 | inline const T& front() const { return first(); } |
210 | inline T& back() { return last(); } |
211 | inline const T& back() const { return last(); } |
212 | inline void pop_front() { removeFirst(); } |
213 | inline void pop_back() { removeLast(); } |
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 |
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; } |
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 |
232 | inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); } |
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;} |
235 | inline QT3_SUPPORT iterator find(iterator from, const T& t) |
236 | { while (from != end() && !(*from == t)) ++from; return from; } |
237 | inline QT3_SUPPORT iterator find(const T& t) |
238 | { return find(begin(), t); } |
239 | inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const |
240 | { while (from != end() && !(*from == t)) ++from; return from; } |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
409 | inline T QLinkedList<T>::takeFirst() |
410 | { |
411 | T t = first(); |
412 | removeFirst(); |
413 | return t; |
414 | } |
415 | |
416 | template <typename T> |
417 | inline T QLinkedList<T>::takeLast() |
418 | { |
419 | T t = last(); |
420 | removeLast(); |
421 | return t; |
422 | } |
423 | |
424 | template <typename 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> |
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> |
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> |
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> |
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; |
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 | |