diff options
Diffstat (limited to 'src/corelib/tools/qlist.h')
| -rw-r--r-- | src/corelib/tools/qlist.h | 900 |
1 files changed, 900 insertions, 0 deletions
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h new file mode 100644 index 0000000000..da70b8003d --- /dev/null +++ b/src/corelib/tools/qlist.h @@ -0,0 +1,900 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QLIST_H +#define QLIST_H + +#include <QtCore/qiterator.h> +#include <QtCore/qatomic.h> +#include <QtCore/qalgorithms.h> + +#ifndef QT_NO_STL +#include <iterator> +#include <list> +#endif +#ifdef Q_COMPILER_INITIALIZER_LISTS +#include <iterator> +#include <initializer_list> +#endif + +#include <new> +#include <limits.h> +#include <string.h> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Core) + +template <typename T> class QVector; +template <typename T> class QSet; + +struct Q_CORE_EXPORT QListData { + struct Data { + QBasicAtomicInt ref; + int alloc, begin, end; + uint sharable : 1; + void *array[1]; + }; + enum { DataHeaderSize = sizeof(Data) - sizeof(void *) }; + + Data *detach(int alloc); + Data *detach_grow(int *i, int n); + Data *detach(); // remove in 5.0 + Data *detach2(); // remove in 5.0 + Data *detach3(); // remove in 5.0 + void realloc(int alloc); + static Data shared_null; + Data *d; + void **erase(void **xi); + void **append(int n); + void **append(); + void **append(const QListData &l); + void **append2(const QListData &l); // remove in 5.0 + void **prepend(); + void **insert(int i); + void remove(int i); + void remove(int i, int n); + void move(int from, int to); + inline int size() const { return d->end - d->begin; } + inline bool isEmpty() const { return d->end == d->begin; } + inline void **at(int i) const { return d->array + d->begin + i; } + inline void **begin() const { return d->array + d->begin; } + inline void **end() const { return d->array + d->end; } +}; + +template <typename T> +class QList +{ + struct Node { void *v; +#if defined(Q_CC_BOR) + Q_INLINE_TEMPLATE T &t(); +#else + Q_INLINE_TEMPLATE T &t() + { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic + ? v : this); } +#endif + }; + + union { QListData p; QListData::Data *d; }; + +public: + inline QList() : d(&QListData::shared_null) { d->ref.ref(); } + inline QList(const QList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } + ~QList(); + QList<T> &operator=(const QList<T> &l); +#ifdef Q_COMPILER_RVALUE_REFS + inline QList &operator=(QList &&other) + { qSwap(d, other.d); return *this; } +#endif + inline void swap(QList<T> &other) { qSwap(d, other.d); } +#ifdef Q_COMPILER_INITIALIZER_LISTS + inline QList(std::initializer_list<T> args) : d(&QListData::shared_null) + { d->ref.ref(); qCopy(args.begin(), args.end(), std::back_inserter(*this)); } +#endif + bool operator==(const QList<T> &l) const; + inline bool operator!=(const QList<T> &l) const { return !(*this == l); } + + inline int size() const { return p.size(); } + + inline void detach() { if (d->ref != 1) detach_helper(); } + + inline void detachShared() + { + // The "this->" qualification is needed for GCCE. + if (d->ref != 1 && this->d != &QListData::shared_null) + detach_helper(); + } + + inline bool isDetached() const { return d->ref == 1; } + inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } + inline bool isSharedWith(const QList<T> &other) const { return d == other.d; } + + inline bool isEmpty() const { return p.isEmpty(); } + + void clear(); + + const T &at(int i) const; + const T &operator[](int i) const; + T &operator[](int i); + + void reserve(int size); + void append(const T &t); + void append(const QList<T> &t); + void prepend(const T &t); + void insert(int i, const T &t); + void replace(int i, const T &t); + void removeAt(int i); + int removeAll(const T &t); + bool removeOne(const T &t); + T takeAt(int i); + T takeFirst(); + T takeLast(); + void move(int from, int to); + void swap(int i, int j); + int indexOf(const T &t, int from = 0) const; + int lastIndexOf(const T &t, int from = -1) const; + QBool contains(const T &t) const; + int count(const T &t) const; + + class const_iterator; + + class iterator { + public: + Node *i; + typedef std::random_access_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef T *pointer; + typedef T &reference; + + inline iterator() : i(0) {} + inline iterator(Node *n) : i(n) {} + inline iterator(const iterator &o): i(o.i){} + inline T &operator*() const { return i->t(); } + inline T *operator->() const { return &i->t(); } + inline T &operator[](int j) const { return i[j].t(); } + inline bool operator==(const iterator &o) const { return i == o.i; } + inline bool operator!=(const iterator &o) const { return i != o.i; } + inline bool operator<(const iterator& other) const { return i < other.i; } + inline bool operator<=(const iterator& other) const { return i <= other.i; } + inline bool operator>(const iterator& other) const { return i > other.i; } + inline bool operator>=(const iterator& other) const { return i >= other.i; } +#ifndef QT_STRICT_ITERATORS + inline bool operator==(const const_iterator &o) const + { return i == o.i; } + inline bool operator!=(const const_iterator &o) const + { return i != o.i; } + inline bool operator<(const const_iterator& other) const + { return i < other.i; } + inline bool operator<=(const const_iterator& other) const + { return i <= other.i; } + inline bool operator>(const const_iterator& other) const + { return i > other.i; } + inline bool operator>=(const const_iterator& other) const + { return i >= other.i; } +#endif + inline iterator &operator++() { ++i; return *this; } + inline iterator operator++(int) { Node *n = i; ++i; return n; } + inline iterator &operator--() { i--; return *this; } + inline iterator operator--(int) { Node *n = i; i--; return n; } + inline iterator &operator+=(int j) { i+=j; return *this; } + inline iterator &operator-=(int j) { i-=j; return *this; } + inline iterator operator+(int j) const { return iterator(i+j); } + inline iterator operator-(int j) const { return iterator(i-j); } + inline int operator-(iterator j) const { return int(i - j.i); } + }; + friend class iterator; + + class const_iterator { + public: + Node *i; + typedef std::random_access_iterator_tag iterator_category; + typedef qptrdiff difference_type; + typedef T value_type; + typedef const T *pointer; + typedef const T &reference; + + inline const_iterator() : i(0) {} + inline const_iterator(Node *n) : i(n) {} + inline const_iterator(const const_iterator &o): i(o.i) {} +#ifdef QT_STRICT_ITERATORS + inline explicit const_iterator(const iterator &o): i(o.i) {} +#else + inline const_iterator(const iterator &o): i(o.i) {} +#endif + inline const T &operator*() const { return i->t(); } + inline const T *operator->() const { return &i->t(); } + inline const T &operator[](int j) const { return i[j].t(); } + inline bool operator==(const const_iterator &o) const { return i == o.i; } + inline bool operator!=(const const_iterator &o) const { return i != o.i; } + inline bool operator<(const const_iterator& other) const { return i < other.i; } + inline bool operator<=(const const_iterator& other) const { return i <= other.i; } + inline bool operator>(const const_iterator& other) const { return i > other.i; } + inline bool operator>=(const const_iterator& other) const { return i >= other.i; } + inline const_iterator &operator++() { ++i; return *this; } + inline const_iterator operator++(int) { Node *n = i; ++i; return n; } + inline const_iterator &operator--() { i--; return *this; } + inline const_iterator operator--(int) { Node *n = i; i--; return n; } + inline const_iterator &operator+=(int j) { i+=j; return *this; } + inline const_iterator &operator-=(int j) { i-=j; return *this; } + inline const_iterator operator+(int j) const { return const_iterator(i+j); } + inline const_iterator operator-(int j) const { return const_iterator(i-j); } + inline int operator-(const_iterator j) const { return i - j.i; } + }; + friend class const_iterator; + + // stl style + inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); } + inline const_iterator begin() const { return reinterpret_cast<Node *>(p.begin()); } + inline const_iterator constBegin() const { return reinterpret_cast<Node *>(p.begin()); } + inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); } + inline const_iterator end() const { return reinterpret_cast<Node *>(p.end()); } + inline const_iterator constEnd() const { return reinterpret_cast<Node *>(p.end()); } + iterator insert(iterator before, const T &t); + iterator erase(iterator pos); + iterator erase(iterator first, iterator last); + + // more Qt + typedef iterator Iterator; + typedef const_iterator ConstIterator; + inline int count() const { return p.size(); } + inline int length() const { return p.size(); } // Same as count() + inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } + inline const T& first() const { Q_ASSERT(!isEmpty()); return at(0); } + T& last() { Q_ASSERT(!isEmpty()); return *(--end()); } + const T& last() const { Q_ASSERT(!isEmpty()); return at(count() - 1); } + inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); } + inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); } + inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } + inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } + QList<T> mid(int pos, int length = -1) const; + + T value(int i) const; + T value(int i, const T &defaultValue) const; + + // stl compatibility + inline void push_back(const T &t) { append(t); } + inline void push_front(const T &t) { prepend(t); } + inline T& front() { return first(); } + inline const T& front() const { return first(); } + inline T& back() { return last(); } + inline const T& back() const { return last(); } + inline void pop_front() { removeFirst(); } + inline void pop_back() { removeLast(); } + inline bool empty() const { return isEmpty(); } + typedef int size_type; + typedef T value_type; + typedef value_type *pointer; + typedef const value_type *const_pointer; + typedef value_type &reference; + typedef const value_type &const_reference; + typedef qptrdiff difference_type; + +#ifdef QT3_SUPPORT + inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); } + inline QT3_SUPPORT int remove(const T &t) { return removeAll(t); } + inline QT3_SUPPORT int findIndex(const T& t) const { return indexOf(t); } + inline QT3_SUPPORT iterator find(const T& t) + { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); } + inline QT3_SUPPORT const_iterator find (const T& t) const + { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); } + inline QT3_SUPPORT iterator find(iterator from, const T& t) + { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; } + inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const + { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; } +#endif + + // comfort + QList<T> &operator+=(const QList<T> &l); + inline QList<T> operator+(const QList<T> &l) const + { QList n = *this; n += l; return n; } + inline QList<T> &operator+=(const T &t) + { append(t); return *this; } + inline QList<T> &operator<< (const T &t) + { append(t); return *this; } + inline QList<T> &operator<<(const QList<T> &l) + { *this += l; return *this; } + + QVector<T> toVector() const; + QSet<T> toSet() const; + + static QList<T> fromVector(const QVector<T> &vector); + static QList<T> fromSet(const QSet<T> &set); + +#ifndef QT_NO_STL + static inline QList<T> fromStdList(const std::list<T> &list) + { QList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; } + inline std::list<T> toStdList() const + { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; } +#endif + +private: + Node *detach_helper_grow(int i, int n); + void detach_helper(int alloc); + void detach_helper(); + void free(QListData::Data *d); + + void node_construct(Node *n, const T &t); + void node_destruct(Node *n); + void node_copy(Node *from, Node *to, Node *src); + void node_destruct(Node *from, Node *to); +}; + +#if defined(Q_CC_BOR) +template <typename T> +Q_INLINE_TEMPLATE T &QList<T>::Node::t() +{ return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; } +#endif + +template <typename T> +Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t) +{ + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t); + else if (QTypeInfo<T>::isComplex) new (n) T(t); +#if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__) + // This violates pointer aliasing rules, but it is known to be safe (and silent) + // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which + // set the same define are assumed to be safe. + else *reinterpret_cast<T*>(n) = t; +#else + // This is always safe, but penaltizes unoptimized builds a lot. + else ::memcpy(n, &t, sizeof(T)); +#endif +} + +template <typename T> +Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n) +{ + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v); + else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T(); +} + +template <typename T> +Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src) +{ + Node *current = from; + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { + QT_TRY { + while(current != to) { + current->v = new T(*reinterpret_cast<T*>(src->v)); + ++current; + ++src; + } + } QT_CATCH(...) { + while (current-- != from) + delete reinterpret_cast<T*>(current->v); + QT_RETHROW; + } + + } else if (QTypeInfo<T>::isComplex) { + QT_TRY { + while(current != to) { + new (current) T(*reinterpret_cast<T*>(src)); + ++current; + ++src; + } + } QT_CATCH(...) { + while (current-- != from) + (reinterpret_cast<T*>(current))->~T(); + QT_RETHROW; + } + } else { + if (src != from && to - from > 0) + memcpy(from, src, (to - from) * sizeof(Node *)); + } +} + +template <typename T> +Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to) +{ + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) + while(from != to) --to, delete reinterpret_cast<T*>(to->v); + else if (QTypeInfo<T>::isComplex) + while (from != to) --to, reinterpret_cast<T*>(to)->~T(); +} + +template <typename T> +Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l) +{ + if (d != l.d) { + QListData::Data *o = l.d; + o->ref.ref(); + if (!d->ref.deref()) + free(d); + d = o; + if (!d->sharable) + detach_helper(); + } + return *this; +} +template <typename T> +inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t) +{ + int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin())); + Node *n = reinterpret_cast<Node *>(p.insert(iBefore)); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + p.remove(iBefore); + QT_RETHROW; + } + return n; +} +template <typename T> +inline typename QList<T>::iterator QList<T>::erase(iterator it) +{ node_destruct(it.i); + return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i))); } +template <typename T> +inline const T &QList<T>::at(int i) const +{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at", "index out of range"); + return reinterpret_cast<Node *>(p.at(i))->t(); } +template <typename T> +inline const T &QList<T>::operator[](int i) const +{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range"); + return reinterpret_cast<Node *>(p.at(i))->t(); } +template <typename T> +inline T &QList<T>::operator[](int i) +{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range"); + detach(); return reinterpret_cast<Node *>(p.at(i))->t(); } +template <typename T> +inline void QList<T>::removeAt(int i) +{ if(i >= 0 && i < p.size()) { detach(); + node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i); } } +template <typename T> +inline T QList<T>::takeAt(int i) +{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::take", "index out of range"); + detach(); Node *n = reinterpret_cast<Node *>(p.at(i)); T t = n->t(); node_destruct(n); + p.remove(i); return t; } +template <typename T> +inline T QList<T>::takeFirst() +{ T t = first(); removeFirst(); return t; } +template <typename T> +inline T QList<T>::takeLast() +{ T t = last(); removeLast(); return t; } + +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc) +{ + if (d->alloc < alloc) { + if (d->ref != 1) + detach_helper(alloc); + else + p.realloc(alloc); + } +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t) +{ + if (d->ref != 1) { + Node *n = detach_helper_grow(INT_MAX, 1); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + --d->end; + QT_RETHROW; + } + } else { + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { + Node *n = reinterpret_cast<Node *>(p.append()); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + --d->end; + QT_RETHROW; + } + } else { + Node *n, copy; + node_construct(©, t); // t might be a reference to an object in the array + QT_TRY { + n = reinterpret_cast<Node *>(p.append());; + } QT_CATCH(...) { + node_destruct(©); + QT_RETHROW; + } + *n = copy; + } + } +} + +template <typename T> +inline void QList<T>::prepend(const T &t) +{ + if (d->ref != 1) { + Node *n = detach_helper_grow(0, 1); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + ++d->begin; + QT_RETHROW; + } + } else { + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { + Node *n = reinterpret_cast<Node *>(p.prepend()); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + ++d->begin; + QT_RETHROW; + } + } else { + Node *n, copy; + node_construct(©, t); // t might be a reference to an object in the array + QT_TRY { + n = reinterpret_cast<Node *>(p.prepend());; + } QT_CATCH(...) { + node_destruct(©); + QT_RETHROW; + } + *n = copy; + } + } +} + +template <typename T> +inline void QList<T>::insert(int i, const T &t) +{ + if (d->ref != 1) { + Node *n = detach_helper_grow(i, 1); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + p.remove(i); + QT_RETHROW; + } + } else { + if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { + Node *n = reinterpret_cast<Node *>(p.insert(i)); + QT_TRY { + node_construct(n, t); + } QT_CATCH(...) { + p.remove(i); + QT_RETHROW; + } + } else { + Node *n, copy; + node_construct(©, t); // t might be a reference to an object in the array + QT_TRY { + n = reinterpret_cast<Node *>(p.insert(i));; + } QT_CATCH(...) { + node_destruct(©); + QT_RETHROW; + } + *n = copy; + } + } +} + +template <typename T> +inline void QList<T>::replace(int i, const T &t) +{ + Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range"); + detach(); + reinterpret_cast<Node *>(p.at(i))->t() = t; +} + +template <typename T> +inline void QList<T>::swap(int i, int j) +{ + Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(), + "QList<T>::swap", "index out of range"); + detach(); + void *t = d->array[d->begin + i]; + d->array[d->begin + i] = d->array[d->begin + j]; + d->array[d->begin + j] = t; +} + +template <typename T> +inline void QList<T>::move(int from, int to) +{ + Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(), + "QList<T>::move", "index out of range"); + detach(); + p.move(from, to); +} + +template<typename T> +Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const +{ + if (alength < 0 || pos + alength > size()) + alength = size() - pos; + if (pos == 0 && alength == size()) + return *this; + QList<T> cpy; + cpy.reserve(alength); + cpy.d->end = alength; + QT_TRY { + cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()), + reinterpret_cast<Node *>(cpy.p.end()), + reinterpret_cast<Node *>(p.begin() + pos)); + } QT_CATCH(...) { + // restore the old end + cpy.d->end = 0; + QT_RETHROW; + } + return cpy; +} + +template<typename T> +Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const +{ + if (i < 0 || i >= p.size()) { + return T(); + } + return reinterpret_cast<Node *>(p.at(i))->t(); +} + +template<typename T> +Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const +{ + return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t()); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c) +{ + Node *n = reinterpret_cast<Node *>(p.begin()); + QListData::Data *x = p.detach_grow(&i, c); + QT_TRY { + node_copy(reinterpret_cast<Node *>(p.begin()), + reinterpret_cast<Node *>(p.begin() + i), n); + } QT_CATCH(...) { + qFree(d); + d = x; + QT_RETHROW; + } + QT_TRY { + node_copy(reinterpret_cast<Node *>(p.begin() + i + c), + reinterpret_cast<Node *>(p.end()), n + i); + } QT_CATCH(...) { + node_destruct(reinterpret_cast<Node *>(p.begin()), + reinterpret_cast<Node *>(p.begin() + i)); + qFree(d); + d = x; + QT_RETHROW; + } + + if (!x->ref.deref()) + free(x); + + return reinterpret_cast<Node *>(p.begin() + i); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc) +{ + Node *n = reinterpret_cast<Node *>(p.begin()); + QListData::Data *x = p.detach(alloc); + QT_TRY { + node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n); + } QT_CATCH(...) { + qFree(d); + d = x; + QT_RETHROW; + } + + if (!x->ref.deref()) + free(x); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper() +{ + detach_helper(d->alloc); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE QList<T>::~QList() +{ + if (!d->ref.deref()) + free(d); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const +{ + if (p.size() != l.p.size()) + return false; + if (d == l.d) + return true; + Node *i = reinterpret_cast<Node *>(p.end()); + Node *b = reinterpret_cast<Node *>(p.begin()); + Node *li = reinterpret_cast<Node *>(l.p.end()); + while (i != b) { + --i; --li; + if (!(i->t() == li->t())) + return false; + } + return true; +} + +// ### Qt 5: rename freeData() to avoid confusion with std::free() +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::free(QListData::Data *data) +{ + node_destruct(reinterpret_cast<Node *>(data->array + data->begin), + reinterpret_cast<Node *>(data->array + data->end)); + qFree(data); +} + + +template <typename T> +Q_OUTOFLINE_TEMPLATE void QList<T>::clear() +{ + *this = QList<T>(); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t) +{ + detachShared(); + const T t = _t; + int removedCount=0, i=0; + Node *n; + while (i < p.size()) + if ((n = reinterpret_cast<Node *>(p.at(i)))->t() == t) { + node_destruct(n); + p.remove(i); + ++removedCount; + } else { + ++i; + } + return removedCount; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t) +{ + detachShared(); + int index = indexOf(_t); + if (index != -1) { + removeAt(index); + return true; + } + return false; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst, + typename QList<T>::iterator alast) +{ + for (Node *n = afirst.i; n < alast.i; ++n) + node_destruct(n); + int idx = afirst - begin(); + p.remove(idx, alast - afirst); + return begin() + idx; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l) +{ + if (!l.isEmpty()) { + if (isEmpty()) { + *this = l; + } else { + Node *n = (d->ref != 1) + ? detach_helper_grow(INT_MAX, l.size()) + : reinterpret_cast<Node *>(p.append2(l.p)); + QT_TRY { + node_copy(n, reinterpret_cast<Node *>(p.end()), + reinterpret_cast<Node *>(l.p.begin())); + } QT_CATCH(...) { + // restore the old end + d->end -= int(reinterpret_cast<Node *>(p.end()) - n); + QT_RETHROW; + } + } + } + return *this; +} + +template <typename T> +inline void QList<T>::append(const QList<T> &t) +{ + *this += t; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const +{ + if (from < 0) + from = qMax(from + p.size(), 0); + if (from < p.size()) { + Node *n = reinterpret_cast<Node *>(p.at(from -1)); + Node *e = reinterpret_cast<Node *>(p.end()); + while (++n != e) + if (n->t() == t) + return int(n - reinterpret_cast<Node *>(p.begin())); + } + return -1; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const +{ + if (from < 0) + from += p.size(); + else if (from >= p.size()) + from = p.size()-1; + if (from >= 0) { + Node *b = reinterpret_cast<Node *>(p.begin()); + Node *n = reinterpret_cast<Node *>(p.at(from + 1)); + while (n-- != b) { + if (n->t() == t) + return n - b; + } + } + return -1; +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE QBool QList<T>::contains(const T &t) const +{ + Node *b = reinterpret_cast<Node *>(p.begin()); + Node *i = reinterpret_cast<Node *>(p.end()); + while (i-- != b) + if (i->t() == t) + return QBool(true); + return QBool(false); +} + +template <typename T> +Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const +{ + int c = 0; + Node *b = reinterpret_cast<Node *>(p.begin()); + Node *i = reinterpret_cast<Node *>(p.end()); + while (i-- != b) + if (i->t() == t) + ++c; + return c; +} + +Q_DECLARE_SEQUENTIAL_ITERATOR(List) +Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List) + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QLIST_H |