Merge remote branch 'origin/4.6' into integration-master-from-4.6
[qt:kenya888s-qt-palm-pre.git] / src / corelib / tools / qlinkedlist.h
1 /****************************************************************************
2 **
3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
6 **
7 ** This file is part of the QtCore module of the Qt Toolkit.
8 **
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** No Commercial Usage
11 ** This file contains pre-release code and may not be distributed.
12 ** You may use this file in accordance with the terms and conditions
13 ** contained in the Technology Preview License Agreement accompanying
14 ** this package.
15 **
16 ** GNU Lesser General Public License Usage
17 ** Alternatively, this file may be used under the terms of the GNU Lesser
18 ** General Public License version 2.1 as published by the Free Software
19 ** Foundation and appearing in the file LICENSE.LGPL included in the
20 ** packaging of this file.  Please review the following information to
21 ** ensure the GNU Lesser General Public License version 2.1 requirements
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23 **
24 ** In addition, as a special exception, Nokia gives you certain additional
25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27 **
28 ** If you have questions regarding the use of this file, please contact
29 ** Nokia at qt-info@nokia.com.
30 **
31 **
32 **
33 **
34 **
35 **
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     bool operator==(const QLinkedList<T> &l) const;
89     inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
90
91     inline int size() const { return d->size; }
92     inline void detach()
93     { if (d->ref != 1) detach_helper(); }
94     inline bool isDetached() const { return d->ref == 1; }
95     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
96     inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
97
98     inline bool isEmpty() const { return d->size == 0; }
99
100     void clear();
101
102     void append(const T &);
103     void prepend(const T &);
104     T takeFirst();
105     T takeLast();
106     int removeAll(const T &t);
107     bool removeOne(const T &t);
108     bool contains(const T &t) const;
109     int count(const T &t) const;
110
111     class const_iterator;
112
113     class iterator
114     {
115     public:
116         typedef std::bidirectional_iterator_tag  iterator_category;
117         typedef qptrdiff difference_type;
118         typedef T value_type;
119         typedef T *pointer;
120         typedef T &reference;
121         Node *i;
122         inline iterator() : i(0) {}
123         inline iterator(Node *n) : i(n) {}
124         inline iterator(const iterator &o) : i(o.i) {}
125         inline iterator &operator=(const iterator &o) { i = o.i; return *this; }
126         inline T &operator*() const { return i->t; }
127         inline T *operator->() const { return &i->t; }
128         inline bool operator==(const iterator &o) const { return i == o.i; }
129         inline bool operator!=(const iterator &o) const { return i != o.i; }
130         inline bool operator==(const const_iterator &o) const
131             { return i == o.i; }
132         inline bool operator!=(const const_iterator &o) const
133             { return i != o.i; }
134         inline iterator &operator++() { i = i->n; return *this; }
135         inline iterator operator++(int) { Node *n = i; i = i->n; return n; }
136         inline iterator &operator--() { i = i->p; return *this; }
137         inline iterator operator--(int) { Node *n = i; i = i->p; return n; }
138         inline iterator operator+(int j) const
139         { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
140         inline iterator operator-(int j) const { return operator+(-j); }
141         inline iterator &operator+=(int j) { return *this = *this + j; }
142         inline iterator &operator-=(int j) { return *this = *this - j; }
143     };
144     friend class iterator;
145
146     class const_iterator
147     {
148     public:
149         typedef std::bidirectional_iterator_tag  iterator_category;
150         typedef qptrdiff difference_type;
151         typedef T value_type;
152         typedef const T *pointer;
153         typedef const T &reference;
154         Node *i;
155         inline const_iterator() : i(0) {}
156         inline const_iterator(Node *n) : i(n) {}
157         inline const_iterator(const const_iterator &o) : i(o.i){}
158         inline const_iterator(iterator ci) : i(ci.i){}
159         inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }
160         inline const T &operator*() const { return i->t; }
161         inline const T *operator->() const { return &i->t; }
162         inline bool operator==(const const_iterator &o) const { return i == o.i; }
163         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
164         inline const_iterator &operator++() { i = i->n; return *this; }
165         inline const_iterator operator++(int) { Node *n = i; i = i->n; return n; }
166         inline const_iterator &operator--() { i = i->p; return *this; }
167         inline const_iterator operator--(int) { Node *n = i; i = i->p; return n; }
168         inline const_iterator operator+(int j) const
169         { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
170         inline const_iterator operator-(int j) const { return operator+(-j); }
171         inline const_iterator &operator+=(int j) { return *this = *this + j; }
172         inline const_iterator &operator-=(int j) { return *this = *this - j; }
173     };
174     friend class const_iterator;
175
176     // stl style
177     inline iterator begin() { detach(); return e->n; }
178     inline const_iterator begin() const { return e->n; }
179     inline const_iterator constBegin() const { return e->n; }
180     inline iterator end() { detach(); return e; }
181     inline const_iterator end() const { return e; }
182     inline const_iterator constEnd() const { return e; }
183     iterator insert(iterator before, const T &t);
184     iterator erase(iterator pos);
185     iterator erase(iterator first, iterator last);
186
187     // more Qt
188     typedef iterator Iterator;
189     typedef const_iterator ConstIterator;
190     inline int count() const { return d->size; }
191     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
192     inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
193     T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
194     const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
195     inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
196     inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
197     inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
198     inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
199
200     // stl compatibility
201     inline void push_back(const T &t) { append(t); }
202     inline void push_front(const T &t) { prepend(t); }
203     inline T& front() { return first(); }
204     inline const T& front() const { return first(); }
205     inline T& back() { return last(); }
206     inline const T& back() const { return last(); }
207     inline void pop_front() { removeFirst(); }
208     inline void pop_back() { removeLast(); }
209     inline bool empty() const { return isEmpty(); }
210     typedef int size_type;
211     typedef T value_type;
212     typedef value_type *pointer;
213     typedef const value_type *const_pointer;
214     typedef value_type &reference;
215     typedef const value_type &const_reference;
216     typedef qptrdiff difference_type;
217
218 #ifndef QT_NO_STL
219     static inline QLinkedList<T> fromStdList(const std::list<T> &list)
220     { QLinkedList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
221     inline std::list<T> toStdList() const
222     { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
223 #endif
224
225 #ifdef QT3_SUPPORT
226     // compatibility
227     inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }
228     inline QT3_SUPPORT int findIndex(const T& t) const
229     { int i=0; for (const_iterator it = begin(); it != end(); ++it, ++i) if(*it == t) return i; return -1;}
230     inline QT3_SUPPORT iterator find(iterator from, const T& t)
231     { while (from != end() && !(*from == t)) ++from; return from; }
232     inline QT3_SUPPORT iterator find(const T& t)
233     { return find(begin(), t); }
234     inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const
235     { while (from != end() && !(*from == t)) ++from; return from; }
236     inline QT3_SUPPORT const_iterator find(const T& t) const
237     { return find(begin(), t); }
238 #endif
239
240     // comfort
241     QLinkedList<T> &operator+=(const QLinkedList<T> &l);
242     QLinkedList<T> operator+(const QLinkedList<T> &l) const;
243     inline QLinkedList<T> &operator+=(const T &t) { append(t); return *this; }
244     inline QLinkedList<T> &operator<< (const T &t) { append(t); return *this; }
245     inline QLinkedList<T> &operator<<(const QLinkedList<T> &l) { *this += l; return *this; }
246
247 private:
248     void detach_helper();
249     void free(QLinkedListData*);
250 };
251
252 template <typename T>
253 inline QLinkedList<T>::~QLinkedList()
254 {
255     if (!d)
256         return;
257     if (!d->ref.deref())
258         free(d);
259 }
260
261 template <typename T>
262 void QLinkedList<T>::detach_helper()
263 {
264     union { QLinkedListData *d; Node *e; } x;
265     x.d = new QLinkedListData;
266     x.d->ref = 1;
267     x.d->size = d->size;
268     x.d->sharable = true;
269     Node *original = e->n;
270     Node *copy = x.e;
271     while (original != e) {
272         QT_TRY {
273             copy->n = new Node(original->t);
274             copy->n->p = copy;
275             original = original->n;
276             copy = copy->n;
277         } QT_CATCH(...) {
278             copy->n = x.e;
279             free(x.d);
280             QT_RETHROW;
281         }
282     }
283     copy->n = x.e;
284     x.e->p = copy;
285     if (!d->ref.deref())
286         free(d);
287     d = x.d;
288 }
289
290 template <typename T>
291 void QLinkedList<T>::free(QLinkedListData *x)
292 {
293     Node *y = reinterpret_cast<Node*>(x);
294     Node *i = y->n;
295     if (x->ref == 0) {
296         while(i != y) {
297             Node *n = i;
298             i = i->n;
299             delete n;
300         }
301         delete x;
302     }
303 }
304
305 template <typename T>
306 void QLinkedList<T>::clear()
307 {
308     *this = QLinkedList<T>();
309 }
310
311 template <typename T>
312 QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
313 {
314     if (d != l.d) {
315         l.d->ref.ref();
316         if (!d->ref.deref())
317             free(d);
318         d = l.d;
319         if (!d->sharable)
320             detach_helper();
321     }
322     return *this;
323 }
324
325 template <typename T>
326 bool QLinkedList<T>::operator== (const QLinkedList<T> &l) const
327 {
328     if (d->size != l.d->size)
329         return false;
330     if (e == l.e)
331         return true;
332     Node *i = e->n;
333     Node *il = l.e->n;
334     while (i != e) {
335         if (! (i->t == il->t))
336             return false;
337         i = i->n;
338         il = il->n;
339     }
340     return true;
341 }
342
343 template <typename T>
344 void QLinkedList<T>::append(const T &t)
345 {
346     detach();
347     Node *i = new Node(t);
348     i->n = e;
349     i->p = e->p;
350     i->p->n = i;
351     e->p = i;
352     d->size++;
353 }
354
355 template <typename T>
356 void QLinkedList<T>::prepend(const T &t)
357 {
358     detach();
359     Node *i = new Node(t);
360     i->n = e->n;
361     i->p = e;
362     i->n->p = i;
363     e->n = i;
364     d->size++;
365 }
366
367 template <typename T>
368 int QLinkedList<T>::removeAll(const T &_t)
369 {
370     detach();
371     const T t = _t;
372     Node *i = e->n;
373     int c = 0;
374     while (i != e) {
375         if (i->t == t) {
376             Node *n = i;
377             i->n->p = i->p;
378             i->p->n = i->n;
379             i = i->n;
380             delete n;
381             c++;
382         } else {
383             i = i->n;
384         }
385     }
386     d->size-=c;
387     return c;
388 }
389
390 template <typename T>
391 bool QLinkedList<T>::removeOne(const T &_t)
392 {
393     detach();
394     iterator it = qFind(begin(), end(), _t);
395     if (it != end()) {
396         erase(it);
397         return true;
398     }
399     return false;
400 }
401
402 template <typename T>
403 inline T QLinkedList<T>::takeFirst()
404 {
405     T t = first();
406     removeFirst();
407     return t;
408 }
409
410 template <typename T>
411 inline T QLinkedList<T>::takeLast()
412 {
413     T t = last();
414     removeLast();
415     return t;
416 }
417
418 template <typename T>
419 bool QLinkedList<T>::contains(const T &t) const
420 {
421     Node *i = e;
422     while ((i = i->n) != e)
423         if (i->t == t)
424             return true;
425     return false;
426 }
427
428 template <typename T>
429 int QLinkedList<T>::count(const T &t) const
430 {
431     Node *i = e;
432     int c = 0;
433     while ((i = i->n) != e)
434         if (i->t == t)
435             c++;
436     return c;
437 }
438
439
440 template <typename T>
441 typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
442 {
443     Node *i = before.i;
444     Node *m = new Node(t);
445     m->n = i;
446     m->p = i->p;
447     m->p->n = m;
448     i->p = m;
449     d->size++;
450     return m;
451 }
452
453 template <typename T>
454 typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
455                                                          typename QLinkedList<T>::iterator alast)
456 {
457     while (afirst != alast)
458         erase(afirst++);
459     return alast;
460 }
461
462
463 template <typename T>
464 typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
465 {
466     detach();
467     Node *i = pos.i;
468     if (i != e) {
469         Node *n = i;
470         i->n->p = i->p;
471         i->p->n = i->n;
472         i = i->n;
473         delete n;
474         d->size--;
475     }
476     return i;
477 }
478
479 template <typename T>
480 QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
481 {
482     detach();
483     int n = l.d->size;
484     d->size += n;
485     Node *original = l.e->n;
486     while (n--) {
487         QT_TRY {
488             Node *copy = new Node(original->t);
489             original = original->n;
490             copy->n = e;
491             copy->p = e->p;
492             copy->p->n = copy;
493             e->p = copy;
494         } QT_CATCH(...) {
495             // restore the original list
496             while (n++<d->size)
497                 removeLast();
498             QT_RETHROW;
499         }
500     }
501     return *this;
502 }
503
504 template <typename T>
505 QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
506 {
507     QLinkedList<T> n = *this;
508     n += l;
509     return n;
510 }
511
512 Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
513 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
514
515 QT_END_NAMESPACE
516
517 QT_END_HEADER
518
519 #endif // QLINKEDLIST_H