src/corelib/tools/qlinkedlist.h

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