IntrusiveList.hpp

Go to the documentation of this file.

#ifndef ESTD_INTRUSIVELIST_HPP_
#define ESTD_INTRUSIVELIST_HPP_

#include <iterator>

#include <cstddef>

namespace estd
{

namespace internal
{

class IntrusiveListBase;

}

class IntrusiveListNode
{
public:

    class LinkAccessKey
    {
        friend internal::IntrusiveListBase;

        constexpr LinkAccessKey()
        {

        }

        LinkAccessKey(const LinkAccessKey&) = delete;
        LinkAccessKey(LinkAccessKey&&) = delete;
        const LinkAccessKey& operator=(const LinkAccessKey&) = delete;
        LinkAccessKey& operator=(LinkAccessKey&&) = delete;
    };

    constexpr IntrusiveListNode() :
            nextNode_{this},
            previousNode_{this}
    {

    }

    IntrusiveListNode(IntrusiveListNode&& other)
    {
        if (other.isLinked() == false)
        {
            reset();
            return;
        }

        nextNode_ = other.nextNode_;
        previousNode_ = other.previousNode_;
        nextNode_->previousNode_ = previousNode_->nextNode_ = this;
        other.reset();
    }

    ~IntrusiveListNode()
    {
        unlink();
    }

    IntrusiveListNode& getNextNode() const
    {
        return *nextNode_;
    }

    IntrusiveListNode& getPreviousNode() const
    {
        return *previousNode_;
    }

    bool isLinked() const
    {
        return nextNode_ != this;
    }

    void link(IntrusiveListNode& position, LinkAccessKey)
    {
        unlink();

        nextNode_ = &position;
        previousNode_ = position.previousNode_;
        position.previousNode_->nextNode_ = this;
        position.previousNode_ = this;
    }

    void swap(IntrusiveListNode& other)
    {
        const auto thisWasLinked = isLinked();
        const auto otherWasLinked = other.isLinked();

        if (thisWasLinked == true || otherWasLinked == true)
        {
            using std::swap;
            swap(nextNode_, other.nextNode_);
            swap(previousNode_, other.previousNode_);

            if (thisWasLinked == true)
                other.nextNode_->previousNode_ = other.previousNode_->nextNode_ = &other;
            else
                other.reset();

            if (otherWasLinked == true)
                nextNode_->previousNode_ = previousNode_->nextNode_ = this;
            else
                reset();
        }
    }

    void unlink()
    {
        previousNode_->nextNode_ = nextNode_;
        nextNode_->previousNode_ = previousNode_;

        reset();
    }

    IntrusiveListNode(const IntrusiveListNode&) = delete;
    const IntrusiveListNode& operator=(const IntrusiveListNode&) = delete;
    IntrusiveListNode& operator=(IntrusiveListNode&&) = delete;

private:

    void reset()
    {
        nextNode_ = this;
        previousNode_ = this;
    }

    IntrusiveListNode* nextNode_;

    IntrusiveListNode* previousNode_;
};

namespace internal
{

class IntrusiveListBase
{
public:

    constexpr IntrusiveListBase() :
            rootNode_{}
    {

    }

    ~IntrusiveListBase()
    {
        clear();
    }

    IntrusiveListNode& begin()
    {
        return rootNode_.getNextNode();
    }

    const IntrusiveListNode& begin() const
    {
        return rootNode_.getNextNode();
    }

    const IntrusiveListNode& cbegin() const
    {
        return begin();
    }

    const IntrusiveListNode& cend() const
    {
        return end();
    }

    void clear()
    {
        while (empty() == false)
            pop_front();
    }

    bool empty() const
    {
        return &begin() == &end();
    }

    IntrusiveListNode& end()
    {
        return rootNode_;
    }

    const IntrusiveListNode& end() const
    {
        return rootNode_;
    }

    void pop_back()
    {
        erase(end().getPreviousNode());
    }

    void pop_front()
    {
        erase(begin());
    }

    void push_back(IntrusiveListNode& newNode)
    {
        insert(end(), newNode);
    }

    void push_front(IntrusiveListNode& newNode)
    {
        insert(begin(), newNode);
    }

    void swap(IntrusiveListBase& other)
    {
        rootNode_.swap(other.rootNode_);
    }

    static IntrusiveListNode& erase(IntrusiveListNode& position)
    {
        auto& next = position.getNextNode();
        position.unlink();
        return next;
    }

    static void insert(IntrusiveListNode& position, IntrusiveListNode& newNode)
    {
        newNode.link(position, {});
    }

    static void splice(IntrusiveListNode& position, IntrusiveListNode& splicedNode)
    {
        insert(position, splicedNode);
    }

    IntrusiveListBase(const IntrusiveListBase&) = delete;
    IntrusiveListBase(IntrusiveListBase&&) = default;
    const IntrusiveListBase& operator=(const IntrusiveListBase&) = delete;
    IntrusiveListBase& operator=(IntrusiveListBase&&) = delete;

private:

    IntrusiveListNode rootNode_;
};

inline void swap(IntrusiveListBase& left, IntrusiveListBase& right)
{
    left.swap(right);
}

}   // namespace internal

template<typename T, IntrusiveListNode T::* NodePointer, typename U = T>
class IntrusiveListIterator
{
public:

    using difference_type = ptrdiff_t;

    using iterator_category = std::bidirectional_iterator_tag;

    using pointer = U*;

    using reference = U&;

    using value_type = U;

    constexpr IntrusiveListIterator() :
            node_{}
    {

    }

    constexpr explicit IntrusiveListIterator(IntrusiveListNode* const node) :
            node_{node}
    {

    }

    constexpr explicit IntrusiveListIterator(reference element) :
            node_{&(element.*NodePointer)}
    {
        static_assert(std::is_same<U, T>::value == true || std::is_convertible<U*, T*>::value == true,
                "U* must be implicitly convertible to T*!");
    }

    pointer operator->() const
    {
        return getPointer();
    }

    reference operator*() const
    {
        return *getPointer();
    }

    IntrusiveListIterator& operator++()
    {
        node_ = &node_->getNextNode();
        return *this;
    }

    IntrusiveListIterator operator++(int)
    {
        const auto temporary = *this;
        node_ = &node_->getNextNode();
        return temporary;
    }

    IntrusiveListIterator& operator--()
    {
        node_ = &node_->getPreviousNode();
        return *this;
    }

    IntrusiveListIterator operator--(int)
    {
        const auto temporary = *this;
        node_ = &node_->getPreviousNode();
        return temporary;
    }

    bool operator==(const IntrusiveListIterator& other) const
    {
        return node_ == other.node_;
    }

private:

    pointer getPointer() const
    {
        static_assert(std::is_same<U, T>::value == true || std::is_convertible<U*, T*>::value == true,
                "U* must be implicitly convertible to T*!");

        const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
        return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
    }

    IntrusiveListNode* node_;
};

template<typename T, IntrusiveListNode T::* NodePointer, typename U = T>
inline bool operator!=(const IntrusiveListIterator<T, NodePointer, U>& left,
        const IntrusiveListIterator<T, NodePointer, U>& right)
{
    return (left == right) == false;
}

template<typename T, const IntrusiveListNode T::* NodePointer, typename U = T>
class IntrusiveListConstIterator
{
public:

    using difference_type = ptrdiff_t;

    using iterator_category = std::bidirectional_iterator_tag;

    using pointer = const U*;

    using reference = const U&;

    using value_type = U;

    constexpr IntrusiveListConstIterator() :
            node_{}
    {

    }

    constexpr explicit IntrusiveListConstIterator(const IntrusiveListNode* const node) :
            node_{node}
    {

    }

    constexpr explicit IntrusiveListConstIterator(reference element) :
            node_{&(element.*NodePointer)}
    {
        static_assert(std::is_same<U, T>::value == true || std::is_convertible<U*, T*>::value == true,
                "U* must be implicitly convertible to T*!");
    }

    template<IntrusiveListNode T::* NonConstNodePointer>
    constexpr IntrusiveListConstIterator(const IntrusiveListIterator<T, NonConstNodePointer, U>& iterator) :
            IntrusiveListConstIterator{*iterator}
    {

    }

    pointer operator->() const
    {
        return getPointer();
    }

    reference operator*() const
    {
        return *getPointer();
    }

    IntrusiveListConstIterator& operator++()
    {
        node_ = &node_->getNextNode();
        return *this;
    }

    IntrusiveListConstIterator operator++(int)
    {
        const auto temporary = *this;
        node_ = &node_->getNextNode();
        return temporary;
    }

    IntrusiveListConstIterator& operator--()
    {
        node_ = &node_->getPreviousNode();
        return *this;
    }

    IntrusiveListConstIterator operator--(int)
    {
        const auto temporary = *this;
        node_ = &node_->getPreviousNode();
        return temporary;
    }

    bool operator==(const IntrusiveListConstIterator& other) const
    {
        return node_ == other.node_;
    }

private:

    pointer getPointer() const
    {
        static_assert(std::is_same<U, T>::value == true || std::is_convertible<U*, T*>::value == true,
                "U* must be implicitly convertible to T*!");

        const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
        return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
    }

    const IntrusiveListNode* node_;
};

template<typename T, const IntrusiveListNode T::* NodePointer, typename U = T>
inline bool operator!=(const IntrusiveListConstIterator<T, NodePointer, U>& left,
        const IntrusiveListConstIterator<T, NodePointer, U>& right)
{
    return (left == right) == false;
}

template<typename T, IntrusiveListNode T::* NodePointer, const IntrusiveListNode T::* ConstNodePointer, typename U = T>
inline bool operator==(const IntrusiveListIterator<T, NodePointer, U>& left,
        const IntrusiveListConstIterator<T, ConstNodePointer, U>& right)
{
    return decltype(right){left} == right;
}

template<typename T, IntrusiveListNode T::* NodePointer, const IntrusiveListNode T::* ConstNodePointer, typename U = T>
inline bool operator!=(const IntrusiveListIterator<T, NodePointer, U>& left,
        const IntrusiveListConstIterator<T, ConstNodePointer, U>& right)
{
    return (left == right) == false;
}

template<typename T, IntrusiveListNode T::* NodePointer, const IntrusiveListNode T::* ConstNodePointer, typename U = T>
inline bool operator!=(const IntrusiveListConstIterator<T, ConstNodePointer, U>& left,
        const IntrusiveListIterator<T, NodePointer, U>& right)
{
    return right != left;
}

template<typename T, IntrusiveListNode T::* NodePointer, typename U = T>
class IntrusiveList
{
public:

    using const_iterator = IntrusiveListConstIterator<T, NodePointer, U>;

    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    using const_pointer = const U*;

    using const_reference = const U&;

    using iterator = IntrusiveListIterator<T, NodePointer, U>;

    using reverse_iterator = std::reverse_iterator<iterator>;

    using pointer = U*;

    using reference = U&;

    using value_type = U;

    constexpr IntrusiveList() :
            intrusiveListBase_{}
    {

    }

    reference back()
    {
        return *--end();
    }

    const_reference back() const
    {
        return *--end();
    }

    iterator begin()
    {
        return iterator{&intrusiveListBase_.begin()};
    }

    const_iterator begin() const
    {
        return const_iterator{&intrusiveListBase_.begin()};
    }

    const_iterator cbegin() const
    {
        return begin();
    }

    const_iterator cend() const
    {
        return end();
    }

    void clear()
    {
        intrusiveListBase_.clear();
    }

    const_reverse_iterator crbegin() const
    {
        return rbegin();
    }

    const_reverse_iterator crend() const
    {
        return rend();
    }

    bool empty() const
    {
        return intrusiveListBase_.empty();
    }

    iterator end()
    {
        return iterator{&intrusiveListBase_.end()};
    }

    const_iterator end() const
    {
        return const_iterator{&intrusiveListBase_.end()};
    }

    reference front()
    {
        return *begin();
    }

    const_reference front() const
    {
        return *begin();
    }

    void pop_back()
    {
        erase(--end());
    }

    void pop_front()
    {
        erase(begin());
    }

    void push_back(reference newElement)
    {
        insert(end(), newElement);
    }

    void push_front(reference newElement)
    {
        insert(begin(), newElement);
    }

    reverse_iterator rbegin()
    {
        return reverse_iterator{end()};
    }

    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator{end()};
    }

    reverse_iterator rend()
    {
        return reverse_iterator{begin()};
    }

    const_reverse_iterator rend() const
    {
        return const_reverse_iterator{begin()};
    }

    void swap(IntrusiveList& other)
    {
        intrusiveListBase_.swap(other.intrusiveListBase_);
    }

    static iterator erase(const iterator position)
    {
        auto& positionNode = (*position).*NodePointer;
        auto& nextNode = internal::IntrusiveListBase::erase(positionNode);
        return iterator{&nextNode};
    }

    static iterator insert(const iterator position, reference newElement)
    {
        static_assert(std::is_same<U, T>::value == true || std::is_convertible<U*, T*>::value == true,
                "U* must be implicitly convertible to T*!");

        auto& positionNode = (*position).*NodePointer;
        auto& newElementNode = newElement.*NodePointer;
        internal::IntrusiveListBase::insert(positionNode, newElementNode);
        return iterator{&newElementNode};
    }

    static void splice(const iterator position, const iterator splicedElement)
    {
        auto& positionNode = (*position).*NodePointer;
        auto& splicedElementNode = (*splicedElement).*NodePointer;
        internal::IntrusiveListBase::splice(positionNode, splicedElementNode);
    }

    IntrusiveList(const IntrusiveList&) = delete;
    IntrusiveList(IntrusiveList&&) = default;
    const IntrusiveList& operator=(const IntrusiveList&) = delete;
    IntrusiveList& operator=(IntrusiveList&&) = delete;

private:

    internal::IntrusiveListBase intrusiveListBase_;
};

template<typename T, IntrusiveListNode T::* NodePointer, typename U = T>
inline void swap(IntrusiveList<T, NodePointer, U>& left, IntrusiveList<T, NodePointer, U>& right)
{
    left.swap(right);
}

}   // namespace estd

#endif  // ESTD_INTRUSIVELIST_HPP_