Program Listing for File intrusive_list.h

↰ Return to documentation for file (utils/intrusive_list.h)

#pragma once

#include <spdlog/spdlog.h>

template <typename T>
struct Node {
public:
    Node(T* const obj_ptr) : prev(nullptr), next(nullptr), obj_ptr(obj_ptr) { }

    friend void swap(Node& a, Node& b) {
        using std::swap;
        swap(a.prev, b.prev);
        swap(a.next, b.next);
        swap(a.obj_ptr, b.obj_ptr);
    }

    const T& GetDataRef() const {
        return *obj_ptr;
    }
    T& GetDataRef() {
        return *obj_ptr;
    }

    const T* GetDataPtr() const {
        return obj_ptr;
    }
    T* GetDataPtr() {
        return obj_ptr;
    }

    template <typename R, Node<R> R::*Member>
    friend class IntrusiveList;

private:
    Node* prev;
    Node* next;

    T* obj_ptr;
};

template <typename T, Node<T> T::*Member>
class IntrusiveList {
public:
    IntrusiveList() : begin_node(nullptr), end_node(nullptr), num_elements(0) {
        begin_node.next = &end_node;
        end_node.prev = &begin_node;
    }

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

    friend void swap(IntrusiveList& a, IntrusiveList& b) {
        swap(a, b);
    }

    IntrusiveList(IntrusiveList&& o) : IntrusiveList() {
        swap(*this, o);
    }

    IntrusiveList& operator=(IntrusiveList&& o) {
        swap(*this, o);
        return *this;
    }

    void push_back(T& owner) {
        Node<T>& node = owner.*Member;
        // Skip inserting node into list when it's already inserted
        if (node.prev || node.next)
            return;

        node.next = &end_node;
        node.prev = end_node.prev;
        end_node.prev->next = &node;
        end_node.prev = &node;

        // Track number of elements in list
        num_elements++;
    }

    void delete_elem(T& owner) {
        Node<T>& node = owner.*Member;
        // Return if node is not in list altogether
        if (node.prev == nullptr && node.next == nullptr)
            return;

        node.next->prev = node.prev;
        node.prev->next = node.next;

        node.next = node.prev = nullptr;

        // Track number of elements in list
        num_elements--;
    }

    bool in_list(const T& owner) const {
        const Node<T>& node = owner.*Member;
        return node.next || node.prev;
    }

    size_t size() const {
        return num_elements;
    }

    template <typename It, typename NodeType>
    struct BaseIterator;

    using Iterator = BaseIterator<T, Node<T>>;
    using ConstIterator = BaseIterator<const T, const Node<T>>;

    Iterator begin() {
        return Iterator(begin_node.next);
    }
    Iterator end() {
        return Iterator(&end_node);
    }

    ConstIterator begin() const {
        return ConstIterator(begin_node.next);
    }
    ConstIterator end() const {
        return ConstIterator(&end_node);
    }

    Iterator erase(Iterator position) {
        delete_elem(*(position++));
        return position;
    }

private:
    Node<T> begin_node;
    Node<T> end_node;
    size_t num_elements;

    static void swap(IntrusiveList& a, IntrusiveList& b) {
        using std::swap;
        swap(a.begin_node, b.begin_node);
        swap(a.end_node, b.end_node);
        swap(a.num_elements, b.num_elements);

        const auto set_stack_nodes = [](IntrusiveList& l) {
            if (l.size() == 0)
                l.begin_node.next = &l.end_node;

            l.begin_node.next->prev = &l.begin_node;
            l.end_node.prev->next = &l.end_node;
        };

        set_stack_nodes(a);
        set_stack_nodes(b);
    }
};

template <typename T, Node<T> T::*Member>
template <typename It, typename NodeType>
struct IntrusiveList<T, Member>::BaseIterator {
    BaseIterator(NodeType* node_ptr) : node_ptr(node_ptr) { }

    It& operator*() const {
        return node_ptr->GetDataRef();
    }

    It* operator->() const {
        return node_ptr->GetDataPtr();
    }

    It& front() const {
        return node_ptr->GetDataRef();
    }

    BaseIterator& operator++() {
        node_ptr = node_ptr->next;
        return *this;
    }

    BaseIterator operator++(int) {
        Iterator tmp = *this;
        node_ptr = node_ptr->next;
        return tmp;
    }

    friend bool operator==(const BaseIterator& a, const BaseIterator& b) {
        return a.node_ptr == b.node_ptr;
    };
    friend bool operator!=(const BaseIterator& a, const BaseIterator& b) {
        return a.node_ptr != b.node_ptr;
    };

private:
    NodeType* node_ptr;
};