Revision control
++ // Copyright (C) 2016 The Qt Company Ltd.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:significant reason:default
++
++ #ifndef QT5LINKEDLIST_H
++ #define QT5LINKEDLIST_H
++
++ #include <QtCore5Compat/qcore5global.h>
++
++ #include <QtCore/qiterator.h>
++ #include <QtCore/qrefcount.h>
++ #include <QtCore/qcontainertools_impl.h>
++ #include <QtCore/qdatastream.h>
++ #include <QtCore/qmetatype.h>
++ #include <QtCore/qscopeguard.h>
++ #include <QtCore/qtypeinfo.h>
++
++ #include <algorithm>
++ #include <initializer_list>
++ #include <iterator>
++ #include <list>
++
++ QT_BEGIN_NAMESPACE
++
++ struct Q_CORE5COMPAT_EXPORT QLinkedListData
++ {
++ QLinkedListData *n, *p;
++ QtPrivate::RefCount ref;
++ int size;
++ uint sharable : 1;
++
++ static const QLinkedListData shared_null;
++ };
++
++ template<typename T>
++ struct QLinkedListNode
++ {
++ inline QLinkedListNode(const T &arg) : t(arg) {}
++ QLinkedListNode *n, *p;
++ T t;
++ };
++
++ template<class T>
++ class QLinkedList
++ {
++ typedef QLinkedListNode<T> Node;
++ union {
++ QLinkedListData *d;
++ QLinkedListNode<T> *e;
++ };
++
++ public:
++ inline QLinkedList() noexcept : d(const_cast<QLinkedListData *>(&QLinkedListData::shared_null))
++ {
++ }
++ inline QLinkedList(const QLinkedList<T> &l) : d(l.d)
++ {
++ d->ref.ref();
++ if (!d->sharable)
++ detach();
++ }
++ inline QLinkedList(std::initializer_list<T> list) : QLinkedList(list.begin(), list.end()) {}
++ template<typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
++ inline QLinkedList(InputIterator first, InputIterator last) : QLinkedList()
++ {
++ std::copy(first, last, std::back_inserter(*this));
++ }
++ ~QLinkedList();
++ QLinkedList<T> &operator=(const QLinkedList<T> &);
++ QLinkedList(QLinkedList<T> &&other) noexcept : d(other.d)
++ {
++ other.d = const_cast<QLinkedListData *>(&QLinkedListData::shared_null);
++ }
++ QLinkedList<T> &operator=(QLinkedList<T> &&other) noexcept
++ {
++ QLinkedList moved(std::move(other));
++ swap(moved);
++ return *this;
++ }
++ void swap(QLinkedList &other) noexcept { qt_ptr_swap(d, other.d); }
++ bool operator==(const QLinkedList<T> &l) const;
++ inline bool operator!=(const QLinkedList<T> &l) const { return !(*this == l); }
++
++ inline int size() const { return d->size; }
++ inline void detach()
++ {
++ if (d->ref.isShared())
++ detach_helper2(this->e);
++ }
++ inline bool isDetached() const { return !d->ref.isShared(); }
++ inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
++
++ inline bool isEmpty() const { return d->size == 0; }
++
++ void clear();
++
++ void append(const T &);
++ void prepend(const T &);
++ T takeFirst();
++ T takeLast();
++ int removeAll(const T &t);
++ bool removeOne(const T &t);
++ bool contains(const T &t) const;
++ int count(const T &t) const;
++
++ class const_iterator;
++
++ class iterator
++ {
++ public:
++ typedef std::bidirectional_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef T *pointer;
++ typedef T &reference;
++ Node *i;
++ inline iterator() : i(nullptr) {}
++ inline iterator(Node *n) : i(n) {}
++ #if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
++ iterator(const iterator &other) noexcept : i(other.i) {}
++ iterator &operator=(const iterator &other) noexcept
++ {
++ i = other.i;
++ return *this;
++ }
++ iterator(iterator &&other) noexcept : i(other.i) {}
++ iterator &operator=(iterator &&other) noexcept { return *this = other; }
++ #endif
++ inline T &operator*() const { return i->t; }
++ inline T *operator->() const { return &i->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 const_iterator &o) const { return i == o.i; }
++ inline bool operator!=(const const_iterator &o) const { return i != o.i; }
++ inline iterator &operator++()
++ {
++ i = i->n;
++ return *this;
++ }
++ inline iterator operator++(int)
++ {
++ Node *n = i;
++ i = i->n;
++ return n;
++ }
++ inline iterator &operator--()
++ {
++ i = i->p;
++ return *this;
++ }
++ inline iterator operator--(int)
++ {
++ Node *n = i;
++ i = i->p;
++ return n;
++ }
++ inline iterator operator+(int j) const
++ {
++ Node *n = i;
++ if (j > 0)
++ while (j--)
++ n = n->n;
++ else
++ while (j++)
++ n = n->p;
++ return n;
++ }
++ inline iterator operator-(int j) const { return operator+(-j); }
++ inline iterator &operator+=(int j) { return *this = *this + j; }
++ inline iterator &operator-=(int j) { return *this = *this - j; }
++ friend inline iterator operator+(int j, iterator k) { return k + j; }
++ };
++ friend class iterator;
++
++ class const_iterator
++ {
++ public:
++ typedef std::bidirectional_iterator_tag iterator_category;
++ typedef qptrdiff difference_type;
++ typedef T value_type;
++ typedef const T *pointer;
++ typedef const T &reference;
++ Node *i;
++ inline const_iterator() : i(nullptr) {}
++ inline const_iterator(Node *n) : i(n) {}
++ inline const_iterator(iterator ci) : i(ci.i) {}
++ #if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
++ const_iterator(const const_iterator &other) noexcept : i(other.i) {}
++ const_iterator &operator=(const const_iterator &other) noexcept
++ {
++ i = other.i;
++ return *this;
++ }
++ const_iterator(const_iterator &&other) noexcept : i(other.i) {}
++ const_iterator &operator=(const_iterator &&other) noexcept { return *this = other; }
++ #endif
++ inline const T &operator*() const { return i->t; }
++ inline const T *operator->() const { return &i->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 const_iterator &operator++()
++ {
++ i = i->n;
++ return *this;
++ }
++ inline const_iterator operator++(int)
++ {
++ Node *n = i;
++ i = i->n;
++ return n;
++ }
++ inline const_iterator &operator--()
++ {
++ i = i->p;
++ return *this;
++ }
++ inline const_iterator operator--(int)
++ {
++ Node *n = i;
++ i = i->p;
++ return n;
++ }
++ inline const_iterator operator+(int j) const
++ {
++ Node *n = i;
++ if (j > 0)
++ while (j--)
++ n = n->n;
++ else
++ while (j++)
++ n = n->p;
++ return n;
++ }
++ inline const_iterator operator-(int j) const { return operator+(-j); }
++ inline const_iterator &operator+=(int j) { return *this = *this + j; }
++ inline const_iterator &operator-=(int j) { return *this = *this - j; }
++ friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
++ };
++ friend class const_iterator;
++
++ // stl style
++ typedef std::reverse_iterator<iterator> reverse_iterator;
++ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
++
++ inline iterator begin()
++ {
++ detach();
++ return e->n;
++ }
++ inline const_iterator begin() const noexcept { return e->n; }
++ inline const_iterator cbegin() const noexcept { return e->n; }
++ inline const_iterator constBegin() const noexcept { return e->n; }
++ inline iterator end()
++ {
++ detach();
++ return e;
++ }
++ inline const_iterator end() const noexcept { return e; }
++ inline const_iterator cend() const noexcept { return e; }
++ inline const_iterator constEnd() const noexcept { return e; }
++
++ reverse_iterator rbegin() { return reverse_iterator(end()); }
++ reverse_iterator rend() { return reverse_iterator(begin()); }
++ const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
++ const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
++ const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
++ const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
++
++ 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 d->size; }
++ inline T &first()
++ {
++ Q_ASSERT(!isEmpty());
++ return *begin();
++ }
++ inline const T &first() const
++ {
++ Q_ASSERT(!isEmpty());
++ return *begin();
++ }
++ T &last()
++ {
++ Q_ASSERT(!isEmpty());
++ return *(--end());
++ }
++ const T &last() const
++ {
++ Q_ASSERT(!isEmpty());
++ return *(--end());
++ }
++ 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; }
++
++ // 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;
++
++ static inline QLinkedList<T> fromStdList(const std::list<T> &list)
++ {
++ QLinkedList<T> tmp;
++ std::copy(list.begin(), list.end(), std::back_inserter(tmp));
++ return tmp;
++ }
++ inline std::list<T> toStdList() const
++ {
++ std::list<T> tmp;
++ std::copy(constBegin(), constEnd(), std::back_inserter(tmp));
++ return tmp;
++ }
++
++ // comfort
++ QLinkedList<T> &operator+=(const QLinkedList<T> &l);
++ QLinkedList<T> operator+(const QLinkedList<T> &l) const;
++ inline QLinkedList<T> &operator+=(const T &t)
++ {
++ append(t);
++ return *this;
++ }
++ inline QLinkedList<T> &operator<<(const T &t)
++ {
++ append(t);
++ return *this;
++ }
++ inline QLinkedList<T> &operator<<(const QLinkedList<T> &l)
++ {
++ *this += l;
++ return *this;
++ }
++
++ private:
++ void detach_helper();
++ iterator detach_helper2(iterator);
++ void freeData(QLinkedListData *);
++ };
++
++ #if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
++ template<typename InputIterator,
++ typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
++ QtPrivate::IfIsInputIterator<InputIterator> = true>
++ QLinkedList(InputIterator, InputIterator)->QLinkedList<ValueType>;
++ #endif
++
++ template<typename T>
++ inline QLinkedList<T>::~QLinkedList()
++ {
++ if (!d->ref.deref())
++ freeData(d);
++ }
++
++ template<typename T>
++ void QLinkedList<T>::detach_helper()
++ {
++ detach_helper2(this->e);
++ }
++
++ template<typename T>
++ typename QLinkedList<T>::iterator QLinkedList<T>::detach_helper2(iterator orgite)
++ {
++ // detach and convert orgite to an iterator in the detached instance
++ bool isEndIterator = (orgite.i == this->e);
++ union {
++ QLinkedListData *d;
++ Node *e;
++ } x;
++ x.d = new QLinkedListData;
++ x.d->ref.initializeOwned();
++ x.d->size = d->size;
++ x.d->sharable = true;
++ Node *original = e->n;
++ Node *copy = x.e;
++ Node *org = orgite.i;
++
++ while (original != org) {
++ QT_TRY
++ {
++ copy->n = new Node(original->t);
++ copy->n->p = copy;
++ original = original->n;
++ copy = copy->n;
++ }
++ QT_CATCH(...)
++ {
++ copy->n = x.e;
++ Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
++ freeData(x.d);
++ QT_RETHROW;
++ }
++ }
++ iterator r(copy);
++ while (original != e) {
++ QT_TRY
++ {
++ copy->n = new Node(original->t);
++ copy->n->p = copy;
++ original = original->n;
++ copy = copy->n;
++ }
++ QT_CATCH(...)
++ {
++ copy->n = x.e;
++ Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
++ freeData(x.d);
++ QT_RETHROW;
++ }
++ }
++ copy->n = x.e;
++ x.e->p = copy;
++ if (!d->ref.deref())
++ freeData(d);
++ d = x.d;
++ if (!isEndIterator)
++ ++r; // since we stored the element right before the original node.
++ return r;
++ }
++
++ template<typename T>
++ void QLinkedList<T>::freeData(QLinkedListData *x)
++ {
++ Node *y = reinterpret_cast<Node *>(x);
++ Node *i = y->n;
++ Q_ASSERT(x->ref.atomic.loadRelaxed() == 0);
++ while (i != y) {
++ Node *n = i;
++ i = i->n;
++ delete n;
++ }
++ delete x;
++ }
++
++ template<typename T>
++ void QLinkedList<T>::clear()
++ {
++ *this = QLinkedList<T>();
++ }
++
++ template<typename T>
++ QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &l)
++ {
++ if (d != l.d) {
++ QLinkedListData *o = l.d;
++ o->ref.ref();
++ if (!d->ref.deref())
++ freeData(d);
++ d = o;
++ if (!d->sharable)
++ detach_helper();
++ }
++ return *this;
++ }
++
++ template<typename T>
++ bool QLinkedList<T>::operator==(const QLinkedList<T> &l) const
++ {
++ if (d->size != l.d->size)
++ return false;
++ if (e == l.e)
++ return true;
++ Node *i = e->n;
++ Node *il = l.e->n;
++ while (i != e) {
++ if (!(i->t == il->t))
++ return false;
++ i = i->n;
++ il = il->n;
++ }
++ return true;
++ }
++
++ template<typename T>
++ void QLinkedList<T>::append(const T &t)
++ {
++ detach();
++ Node *i = new Node(t);
++ i->n = e;
++ i->p = e->p;
++ i->p->n = i;
++ e->p = i;
++ d->size++;
++ }
++
++ template<typename T>
++ void QLinkedList<T>::prepend(const T &t)
++ {
++ detach();
++ Node *i = new Node(t);
++ i->n = e->n;
++ i->p = e;
++ i->n->p = i;
++ e->n = i;
++ d->size++;
++ }
++
++ template<typename T>
++ int QLinkedList<T>::removeAll(const T &_t)
++ {
++ detach();
++ const T t = _t;
++ Node *i = e->n;
++ int c = 0;
++ while (i != e) {
++ if (i->t == t) {
++ Node *n = i;
++ i->n->p = i->p;
++ i->p->n = i->n;
++ i = i->n;
++ delete n;
++ c++;
++ } else {
++ i = i->n;
++ }
++ }
++ d->size -= c;
++ return c;
++ }
++
++ template<typename T>
++ bool QLinkedList<T>::removeOne(const T &_t)
++ {
++ detach();
++ iterator it = std::find(begin(), end(), _t);
++ if (it != end()) {
++ erase(it);
++ return true;
++ }
++ return false;
++ }
++
++ template<typename T>
++ inline T QLinkedList<T>::takeFirst()
++ {
++ const auto remover = qScopeGuard([&] { removeFirst(); });
++ return std::move(first());
++ }
++
++ template<typename T>
++ inline T QLinkedList<T>::takeLast()
++ {
++ const auto remover = qScopeGuard([&] { removeLast(); });
++ return std::move(last());
++ }
++
++ template<typename T>
++ bool QLinkedList<T>::contains(const T &t) const
++ {
++ Node *i = e;
++ while ((i = i->n) != e)
++ if (i->t == t)
++ return true;
++ return false;
++ }
++
++ template<typename T>
++ int QLinkedList<T>::count(const T &t) const
++ {
++ Node *i = e;
++ int c = 0;
++ while ((i = i->n) != e)
++ if (i->t == t)
++ c++;
++ return c;
++ }
++
++ template<typename T>
++ typename QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &t)
++ {
++ if (d->ref.isShared())
++ before = detach_helper2(before);
++
++ Node *i = before.i;
++ Node *m = new Node(t);
++ m->n = i;
++ m->p = i->p;
++ m->p->n = m;
++ i->p = m;
++ d->size++;
++ return m;
++ }
++
++ template<typename T>
++ typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>::iterator afirst,
++ typename QLinkedList<T>::iterator alast)
++ {
++ if (afirst == alast)
++ return alast; // no-op
++ if (!d->ref.isShared()) {
++ do {
++ erase(afirst++);
++ } while (afirst != alast);
++ return alast;
++ }
++ // When shared, don't detach; create a completely new QLinkedList and then swap()
++ const const_iterator cafirst = afirst;
++ const const_iterator calast = alast;
++ QLinkedList l{cbegin(), cafirst};
++ // QLinkedList has no range-insert :(
++ iterator r;
++ if (calast == cend()) {
++ r = l.end();
++ } else {
++ // end() appears to be a sentinel, so need to get an actual iterator:
++ auto it = calast;
++ l.append(*it);
++ ++it;
++ r = std::prev(l.end());
++ for (/* empty */; it != cend(); ++it)
++ l.append(*it);
++ }
++ swap(l);
++ return r;
++ }
++
++ template<typename T>
++ typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
++ {
++ if (d->ref.isShared())
++ pos = detach_helper2(pos);
++
++ Node *i = pos.i;
++ if (i != e) {
++ Node *n = i;
++ i->n->p = i->p;
++ i->p->n = i->n;
++ i = i->n;
++ delete n;
++ d->size--;
++ }
++ return i;
++ }
++
++ template<typename T>
++ QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &l)
++ {
++ detach();
++ const auto oldSize = d->size;
++ int n = l.d->size;
++ Node *original = l.e->n;
++ while (n--) {
++ QT_TRY
++ {
++ Node *copy = new Node(original->t);
++ original = original->n;
++ copy->n = e;
++ copy->p = e->p;
++ copy->p->n = copy;
++ e->p = copy;
++ ++d->size;
++ }
++ QT_CATCH(...)
++ {
++ // restore the original list
++ while (d->size != oldSize)
++ removeLast();
++ QT_RETHROW;
++ }
++ }
++ return *this;
++ }
++
++ template<typename T>
++ QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &l) const
++ {
++ QLinkedList<T> n = *this;
++ n += l;
++ return n;
++ }
++
++ Q_DECLARE_SEQUENTIAL_ITERATOR(LinkedList)
++ Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(LinkedList)
++
++ #ifndef QT_NO_DATASTREAM
++ template<typename T>
++ inline QDataStreamIfHasIStreamOperatorsContainer<QLinkedList<T>, T>
++ operator>>(QDataStream &s, QLinkedList<T> &l)
++ {
++ return QtPrivate::readListBasedContainer(s, l);
++ }
++
++ template<typename T>
++ inline QDataStreamIfHasOStreamOperatorsContainer<QLinkedList<T>, T>
++ operator<<(QDataStream &s, const QLinkedList<T> &l)
++ {
++ return QtPrivate::writeSequentialContainer(s, l);
++ }
++ #endif
++
++ template<typename T>
++ Q_DECLARE_TYPEINFO_BODY(QLinkedList<T>, Q_RELOCATABLE_TYPE);
++
++ QT_END_NAMESPACE
++
++ Q_DECLARE_SEQUENTIAL_CONTAINER_METATYPE(QLinkedList)
++
++ #endif // QT5LINKEDLIST_H