qintrusivelist_p.h

Go to the documentation of this file.

// Copyright (C) 2021 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
 
#ifndef QINTRUSIVELIST_P_H
#define QINTRUSIVELIST_P_H
 
//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//
 
#include <QtCore/private/qglobal_p.h>
 
QT_BEGIN_NAMESPACE
 
class QIntrusiveListNode
{
public:
    ~QIntrusiveListNode() { remove(); }
 
    void remove()
    {
        if (_prev) *_prev = _next;
        if (_next) _next->_prev = _prev;
        _prev = nullptr;
        _next = nullptr;
    }
 
    bool isInList() const { return _prev != nullptr; }
 
private:
    template<class N, QIntrusiveListNode N::*member>
    friend class QIntrusiveList;
 
    QIntrusiveListNode *_next = nullptr;
    QIntrusiveListNode**_prev = nullptr;
};
 
template<class N, QIntrusiveListNode N::*member>
class QIntrusiveList
{
private:
    template<typename O>
    class iterator_impl {
    public:
        iterator_impl() = default;
        iterator_impl(O value) : _value(value) {}
 
        O operator*() const { return _value; }
        O operator->() const { return _value; }
        bool operator==(const iterator_impl &other) const { return other._value == _value; }
        bool operator!=(const iterator_impl &other) const { return other._value != _value; }
        iterator_impl &operator++()
        {
            _value = QIntrusiveList<N, member>::next(_value);
            return *this;
        }
 
    protected:
        O _value = nullptr;
    };
 
public:
    class iterator : public iterator_impl<N *>
    {
    public:
        iterator() = default;
        iterator(N *value) : iterator_impl<N *>(value) {}
 
        iterator &erase()
        {
            N *old = this->_value;
            this->_value = QIntrusiveList<N, member>::next(this->_value);
            (old->*member).remove();
            return *this;
        }
    };
 
    using const_iterator = iterator_impl<const N *>;
 
    using Iterator = iterator;
    using ConstIterator = const_iterator;
 
    ~QIntrusiveList() { while (__first) __first->remove(); }
 
    bool isEmpty() const { return __first == nullptr; }
 
    void insert(N *n)
    {
        QIntrusiveListNode *nnode = &(n->*member);
        nnode->remove();
 
        nnode->_next = __first;
        if (nnode->_next) nnode->_next->_prev = &nnode->_next;
        __first = nnode;
        nnode->_prev = &__first;
    }
 
    void remove(N *n)
    {
        QIntrusiveListNode *nnode = &(n->*member);
        nnode->remove();
    }
 
    bool contains(const N *n) const
    {
        QIntrusiveListNode *nnode = __first;
        while (nnode) {
            if (nodeToN(nnode) == n)
                return true;
            nnode = nnode->_next;
        }
        return false;
    }
 
    const N *first() const { return __first ? nodeToN(__first) : nullptr; }
    N *first() { return __first ? nodeToN(__first) : nullptr; }
 
    template<typename O>
    static O next(O current)
    {
        QIntrusiveListNode *nextnode = (current->*member)._next;
        return nextnode ? nodeToN(nextnode) : nullptr;
    }
 
    iterator begin() { return __first ? iterator(nodeToN(__first)) : iterator(); }
    iterator end() { return iterator(); }
 
    const_iterator begin() const
    {
        return __first ? const_iterator(nodeToN(__first)) : const_iterator();
    }
 
    const_iterator end() const { return const_iterator(); }
 
private:
 
    static N *nodeToN(QIntrusiveListNode *node)
    {
        QT_WARNING_PUSH
#if defined(Q_CC_CLANG) && Q_CC_CLANG >= 1300
        QT_WARNING_DISABLE_CLANG("-Wnull-pointer-subtraction")
#endif
        return (N *)((char *)node - ((char *)&(((N *)nullptr)->*member) - (char *)nullptr));
        QT_WARNING_POP
    }
 
    QIntrusiveListNode *__first = nullptr;
};
 
QT_END_NAMESPACE
 
#endif // QINTRUSIVELIST_P_H