qlinkedlist.h

上传用户:binglan008
上传日期:2007-01-28
资源大小:53508k
文件大小:14k
源码类别:Linux/Unix编程
开发平台:MultiPlatform
  1. /****************************************************************************
  2. **
  3. ** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
  4. **
  5. ** This file is part of the QtCore module of the Qt Toolkit.
  6. **
  7. ** This file may be used under the terms of the GNU General Public
  8. ** License version 2.0 as published by the Free Software Foundation
  9. ** and appearing in the file LICENSE.GPL included in the packaging of
  10. ** this file.  Please review the following information to ensure GNU
  11. ** General Public Licensing requirements will be met:
  12. ** http://trolltech.com/products/qt/licenses/licensing/opensource/
  13. **
  14. ** If you are unsure which license is appropriate for your use, please
  15. ** review the following information:
  16. ** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
  17. ** or contact the sales department at sales@trolltech.com.
  18. **
  19. ** In addition, as a special exception, Trolltech gives you certain
  20. ** additional rights. These rights are described in the Trolltech GPL
  21. ** Exception version 1.0, which can be found at
  22. ** http://www.trolltech.com/products/qt/gplexception/ and in the file
  23. ** GPL_EXCEPTION.txt in this package.
  24. **
  25. ** In addition, as a special exception, Trolltech, as the sole copyright
  26. ** holder for Qt Designer, grants users of the Qt/Eclipse Integration
  27. ** plug-in the right for the Qt/Eclipse Integration to link to
  28. ** functionality provided by Qt Designer and its related libraries.
  29. **
  30. ** Trolltech reserves all rights not expressly granted herein.
  31. **
  32. ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  33. ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  34. **
  35. ****************************************************************************/
  36. #ifndef QLINKEDLIST_H
  37. #define QLINKEDLIST_H
  38. #include <QtCore/qiterator.h>
  39. #include <QtCore/qatomic.h>
  40. #ifndef QT_NO_STL
  41. #include <iterator>
  42. #include <list>
  43. #endif
  44. QT_BEGIN_HEADER
  45. QT_MODULE(Core)
  46. struct Q_CORE_EXPORT QLinkedListData
  47. {
  48.     QLinkedListData *n, *p;
  49.     QBasicAtomic ref;
  50.     int size;
  51.     uint sharable : 1;
  52.     static QLinkedListData shared_null;
  53. };
  54. template <typename T>
  55. struct QLinkedListNode
  56. {
  57.     inline QLinkedListNode(const T &arg): t(arg) { }
  58.     QLinkedListNode *n, *p;
  59.     T t;
  60. };
  61. template <class T>
  62. class QLinkedList
  63. {
  64.     typedef QLinkedListNode<T> Node;
  65.     union { QLinkedListData *d; QLinkedListNode<T> *e; };
  66. public:
  67.     inline QLinkedList() : d(&QLinkedListData::shared_null) { d->ref.ref(); }
  68.     inline QLinkedList(const QLinkedList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach(); }
  69.     ~QLinkedList();
  70.     QLinkedList<T> &operator=(const QLinkedList<T> &);
  71.     bool operator==(const QLinkedList<T> &l) const;
  72.     inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
  73.     inline int size() const { return d->size; }
  74.     inline void detach()
  75.     { if (d->ref != 1) detach_helper(); }
  76.     inline bool isDetached() const { return d->ref == 1; }
  77.     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
  78.     inline bool isEmpty() const { return d->size == 0; }
  79.     void clear();
  80.     void append(const T &);
  81.     void prepend(const T &);
  82.     T takeFirst();
  83.     T takeLast();
  84.     int removeAll(const T &t);
  85.     bool contains(const T &t) const;
  86.     int count(const T &t) const;
  87.     class const_iterator;
  88.     class iterator
  89.     {
  90.     public:
  91.         typedef std::bidirectional_iterator_tag  iterator_category;
  92.         typedef ptrdiff_t  difference_type;
  93.         typedef T value_type;
  94.         typedef T *pointer;
  95.         typedef T &reference;
  96.         Node *i;
  97.         inline iterator() : i(0) {}
  98.         inline iterator(Node *n) : i(n) {}
  99.         inline iterator(const iterator &o) : i(o.i) {}
  100.         inline iterator &operator=(const iterator &o) { i = o.i; return *this; }
  101.         inline T &operator*() const { return i->t; }
  102.         inline T *operator->() const { return &i->t; }
  103.         inline bool operator==(const iterator &o) const { return i == o.i; }
  104.         inline bool operator!=(const iterator &o) const { return i != o.i; }
  105.         inline bool operator==(const const_iterator &o) const
  106.             { return i == reinterpret_cast<const iterator &>(o).i; }
  107.         inline bool operator!=(const const_iterator &o) const
  108.             { return i != reinterpret_cast<const iterator &>(o).i; }
  109.         inline iterator &operator++() { i = i->n; return *this; }
  110.         inline iterator operator++(int) { Node *n = i; i = i->n; return n; }
  111.         inline iterator &operator--() { i = i->p; return *this; }
  112.         inline iterator operator--(int) { Node *n = i; i = i->p; return n; }
  113.         inline iterator operator+(int j) const
  114.         { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
  115.         inline iterator operator-(int j) const { return operator+(-j); }
  116.         inline iterator &operator+=(int j) { return *this = *this + j; }
  117.         inline iterator &operator-=(int j) { return *this = *this - j; }
  118.     };
  119.     friend class iterator;
  120.     class const_iterator
  121.     {
  122.     public:
  123.         typedef std::bidirectional_iterator_tag  iterator_category;
  124.         typedef ptrdiff_t  difference_type;
  125.         typedef T value_type;
  126.         typedef const T *pointer;
  127.         typedef const T &reference;
  128.         Node *i;
  129.         inline const_iterator() : i(0) {}
  130.         inline const_iterator(Node *n) : i(n) {}
  131.         inline const_iterator(const const_iterator &o) : i(o.i){}
  132.         inline const_iterator(iterator ci) : i(ci.i){}
  133. inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }
  134.         inline const T &operator*() const { return i->t; }
  135.         inline const T *operator->() const { return &i->t; }
  136.         inline bool operator==(const const_iterator &o) const { return i == o.i; }
  137.         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
  138.         inline const_iterator &operator++() { i = i->n; return *this; }
  139.         inline const_iterator operator++(int) { Node *n = i; i = i->n; return n; }
  140.         inline const_iterator &operator--() { i = i->p; return *this; }
  141.         inline const_iterator operator--(int) { Node *n = i; i = i->p; return n; }
  142.         inline const_iterator operator+(int j) const
  143.         { Node *n = i; if (j > 0) while (j--) n = n->n; else while (j++) n = n->p; return n; }
  144.         inline const_iterator operator-(int j) const { return operator+(-j); }
  145.         inline const_iterator &operator+=(int j) { return *this = *this + j; }
  146.         inline const_iterator &operator-=(int j) { return *this = *this - j; }
  147.     };
  148.     friend class const_iterator;
  149.     // stl style
  150.     inline iterator begin() { detach(); return e->n; }
  151.     inline const_iterator begin() const { return e->n; }
  152.     inline const_iterator constBegin() const { return e->n; }
  153.     inline iterator end() { detach(); return e; }
  154.     inline const_iterator end() const { return e; }
  155.     inline const_iterator constEnd() const { return e; }
  156.     iterator insert(iterator before, const T &t);
  157.     iterator erase(iterator pos);
  158.     iterator erase(iterator first, iterator last);
  159.     // more Qt
  160.     typedef iterator Iterator;
  161.     typedef const_iterator ConstIterator;
  162.     inline int count() const { return d->size; }
  163.     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
  164.     inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
  165.     T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }
  166.     const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }
  167.     inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }
  168.     inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }
  169.     // stl compatibility
  170.     inline void push_back(const T &t) { append(t); }
  171.     inline void push_front(const T &t) { prepend(t); }
  172.     inline T& front() { return first(); }
  173.     inline const T& front() const { return first(); }
  174.     inline T& back() { return last(); }
  175.     inline const T& back() const { return last(); }
  176.     inline void pop_front() { removeFirst(); }
  177.     inline void pop_back() { removeLast(); }
  178.     inline bool empty() const { return isEmpty(); }
  179.     typedef int size_type;
  180.     typedef T value_type;
  181.     typedef value_type *pointer;
  182.     typedef const value_type *const_pointer;
  183.     typedef value_type &reference;
  184.     typedef const value_type &const_reference;
  185.     typedef ptrdiff_t difference_type;
  186. #ifndef QT_NO_STL
  187.     static inline QLinkedList<T> fromStdList(const std::list<T> &list)
  188.     { QLinkedList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }
  189.     inline std::list<T> toStdList() const
  190.     { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
  191. #endif
  192. #ifdef QT3_SUPPORT
  193.     // compatibility
  194.     inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }
  195.     inline QT3_SUPPORT int findIndex(const T& t) const
  196.     { int i=0; for (const_iterator it = begin(); it != end(); ++it, ++i) if(*it == t) return i; return -1;}
  197.     inline QT3_SUPPORT iterator find(iterator from, const T& t)
  198.     { while (from != end() && !(*from == t)) ++from; return from; }
  199.     inline QT3_SUPPORT iterator find(const T& t)
  200.     { return find(begin(), t); }
  201.     inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const
  202.     { while (from != end() && !(*from == t)) ++from; return from; }
  203.     inline QT3_SUPPORT const_iterator find(const T& t) const
  204.     { return find(begin(), t); }
  205. #endif
  206.     // comfort
  207.     QLinkedList<T> &operator+=(const QLinkedList<T> &l);
  208.     QLinkedList<T> operator+(const QLinkedList<T> &l) const;
  209.     inline QLinkedList<T> &operator+=(const T &t) { append(t); return *this; }
  210.     inline QLinkedList<T> &operator<< (const T &t) { append(t); return *this; }
  211.     inline QLinkedList<T> &operator<<(const QLinkedList<T> &l) { *this += l; return *this; }
  212. private:
  213.     void detach_helper();
  214.     void free(QLinkedListData*);
  215. };
  216. template <typename T>
  217. inline QLinkedList<T>::~QLinkedList()
  218. {
  219.     if (!d)
  220.         return;
  221.     if (!d->ref.deref())
  222.         free(d);
  223. }
  224. template <typename T>
  225. void QLinkedList<T>::detach_helper()
  226. {
  227.     union { QLinkedListData *d; Node *e; } x;
  228.     x.d = new QLinkedListData;
  229.     x.d->ref.init(1);
  230.     x.d->size = d->size;
  231.     x.d->sharable = true;
  232.     Node *i = e->n, *j = x.e;
  233.     while (i != e) {
  234.         j->n = new Node(i->t);
  235.         j->n->p = j;
  236.         i = i->n;
  237.         j = j->n;
  238.     }
  239.     j->n = x.e;
  240.     x.e->p = j;
  241.     x.d = qAtomicSetPtr(&d, x.d);
  242.     if (!x.d->ref.deref())
  243.         free(x.d);
  244. }
  245. template <typename T>
  246. void QLinkedList<T>::free(QLinkedListData *x)
  247. {
  248.     Node *y = reinterpret_cast<Node*>(x);
  249.     Node *i = y->n;
  250.     if (x->ref == 0) {
  251.         while(i != y) {
  252.             Node *n = i;
  253.             i = i->n;
  254.             delete n;
  255.         }
  256.         delete x;
  257.     }
  258. }
  259. template <typename T>
  260. void QLinkedList<T>::clear()
  261. {
  262.     *this = QLinkedList<T>();
  263. }
  264. template <typename T>
  265. QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
  266. {
  267.     if (d != l.d) {
  268.         QLinkedListData *x = l.d;
  269.         x->ref.ref();
  270.         x = qAtomicSetPtr(&d, x);
  271.         if (!x->ref.deref())
  272.             free(x);
  273.         if (!d->sharable)
  274.             detach_helper();
  275.     }
  276.     return *this;
  277. }
  278. template <typename T>
  279. bool QLinkedList<T>::operator== (const QLinkedList<T> &l) const
  280. {
  281.     if (d->size != l.d->size)
  282.         return false;
  283.     if (e == l.e)
  284.         return true;
  285.     Node *i = e->n;
  286.     Node *il = l.e->n;
  287.     while (i != e) {
  288.         if (! (i->t == il->t))
  289.             return false;
  290.         i = i->n;
  291.         il = il->n;
  292.     }
  293.     return true;
  294. }
  295. template <typename T>
  296. void QLinkedList<T>::append(const T &t)
  297. {
  298.     detach();
  299.     Node *i = new Node(t);
  300.     i->n = e;
  301.     i->p = e->p;
  302.     i->p->n = i;
  303.     e->p = i;
  304.     d->size++;
  305. }
  306. template <typename T>
  307. void QLinkedList<T>::prepend(const T &t)
  308. {
  309.     detach();
  310.     Node *i = new Node(t);
  311.     i->n = e->n;
  312.     i->p = e;
  313.     i->n->p = i;
  314.     e->n = i;
  315.     d->size++;
  316. }
  317. template <typename T>
  318. int QLinkedList<T>::removeAll(const T &_t)
  319. {
  320.     detach();
  321.     const T t = _t;
  322.     Node *i = e->n;
  323.     int c = 0;
  324.     while (i != e) {
  325.         if (i->t == t) {
  326.             Node *n = i;
  327.             i->n->p = i->p;
  328.             i->p->n = i->n;
  329.             i = i->n;
  330.             delete n;
  331.             c++;
  332.         } else {
  333.             i = i->n;
  334.         }
  335.     }
  336.     d->size-=c;
  337.     return c;
  338. }
  339. template <typename T>
  340. inline T QLinkedList<T>::takeFirst()
  341. {
  342.     T t = first();
  343.     removeFirst();
  344.     return t;
  345. }
  346. template <typename T>
  347. inline T QLinkedList<T>::takeLast()
  348. {
  349.     T t = last();
  350.     removeLast();
  351.     return t;
  352. }
  353. template <typename T>
  354. bool QLinkedList<T>::contains(const T &t) const
  355. {
  356.     Node *i = e;
  357.     while ((i = i->n) != e)
  358.         if (i->t == t)
  359.             return true;
  360.     return false;
  361. }
  362. template <typename T>
  363. int QLinkedList<T>::count(const T &t) const
  364. {
  365.     Node *i = e;
  366.     int c = 0;
  367.     while ((i = i->n) != e)
  368.         if (i->t == t)
  369.             c++;
  370.     return c;
  371. }
  372. template <typename T>
  373. typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
  374. {
  375.     Node *i = before.i;
  376.     Node *m = new Node(t);
  377.     m->n = i;
  378.     m->p = i->p;
  379.     m->p->n = m;
  380.     i->p = m;
  381.     d->size++;
  382.     return m;
  383. }
  384. template <typename T>
  385. typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
  386.                                                          typename QLinkedList<T>::iterator alast)
  387. {
  388.     while (afirst != alast)
  389.         erase(afirst++);
  390.     return alast;
  391. }
  392. template <typename T>
  393. typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
  394. {
  395.     detach();
  396.     Node *i = pos.i;
  397.     if (i != e) {
  398.         Node *n = i;
  399.         i->n->p = i->p;
  400.         i->p->n = i->n;
  401.         i = i->n;
  402.         delete n;
  403.         d->size--;
  404.     }
  405.     return i;
  406. }
  407. template <typename T>
  408. QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
  409. {
  410.     detach();
  411.     int n = l.d->size;
  412.     d->size += n;
  413.     Node *o = l.e->n;
  414.     while (n--) {
  415.         Node *i = new Node(o->t);
  416.         o = o->n;
  417.         i->n = e;
  418.         i->p = e->p;
  419.         i->p->n = i;
  420.         e->p = i;
  421.     }
  422.     return *this;
  423. }
  424. template <typename T>
  425. QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
  426. {
  427.     QLinkedList<T> n = *this;
  428.     n += l;
  429.     return n;
  430. }
  431. Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
  432. Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
  433. QT_END_HEADER
  434. #endif // QLINKEDLIST_H