Skip to content

Instantly share code, notes, and snippets.

@Reedbeta

Reedbeta/nrr_ill.h

Created January 18, 2020 22:37
Show Gist options
  • Save Reedbeta/ef71234df2b3679fc5860340ddfd66aa to your computer and use it in GitHub Desktop.
Save Reedbeta/ef71234df2b3679fc5860340ddfd66aa to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Reedbeta created this gist Jan 18, 2020.
    363 changes: 363 additions & 0 deletions nrr_ill.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,363 @@
    #pragma once

    // Intrusive Linked List (or Internal Linked List, etc)
    // by Nathan Reed, 2020-01-18. Licensed CC0 https://creativecommons.org/publicdomain/zero/1.0/
    //
    // Use it like:
    //
    // class MyClass
    // {
    // ...
    // ILL<MyClass>::Node node;
    // };
    //
    // ILL<MyClass> list(&MyClass::node);
    //
    // list.Append(...)
    // list.Insert(...)
    // list.Remove(...)
    // for (MyClass& myclass : list)
    // {
    // ...
    // }

    #include <nrr_assert.h>

    namespace nrr
    {
    template <typename T>
    class ILL
    {
    public:
    class Node;
    class Iterator;
    class ConstIterator;

    explicit ILL(Node T::* offset);
    ~ILL();
    ILL(ILL&) = delete;
    ILL(ILL&&);
    ILL& operator = (ILL&) = delete;
    ILL& operator = (ILL&&);

    bool IsEmpty() const;
    void Append(T&);
    void Insert(T& before, T& elem);
    void Remove(T&);
    void Clear();

    Iterator begin();
    Iterator end();
    ConstIterator begin() const;
    ConstIterator end() const;

    class Node
    {
    public:
    Node() = default;
    ~Node();
    Node(const Node&);
    Node& operator = (const Node&);

    private:
    friend class ILL;
    T* next = nullptr;
    T* prev = nullptr;
    };

    class Iterator
    {
    public:
    bool operator == (const Iterator&);
    bool operator != (const Iterator&);
    Iterator& operator ++ ();
    T& operator * () const;
    T& operator -> () const;

    private:
    friend class ILL;
    Iterator(T*, Node T::* offset);
    T* head;
    T* elem;
    Node T::* offset;
    };

    class ConstIterator
    {
    public:
    bool operator == (const ConstIterator&);
    bool operator != (const ConstIterator&);
    ConstIterator& operator ++ ();
    const T& operator * () const;
    const T& operator -> () const;

    private:
    friend class ILL;
    ConstIterator(T*, Node T::* offset);
    const T* head;
    const T* elem;
    Node T::* offset;
    };

    private:
    T* head;
    Node T::* offset;
    };



    // Implementation

    template <typename T>
    ILL<T>::ILL(ILL<T>::Node T::* offset_)
    : head(nullptr),
    offset(offset_)
    {
    NRR_ASSERT(offset != nullptr);
    }

    template <typename T>
    ILL<T>::~ILL()
    {
    Clear();
    }

    template <typename T>
    ILL<T>::ILL(ILL&& other)
    : head(other.head), offset(other.offset)
    {
    other.head = nullptr;
    }

    template <typename T>
    ILL<T>& ILL<T>::operator = (ILL&& other)
    {
    head = other.head;
    offset = other.offset;
    other.head = nullptr;
    return *this;
    }

    template <typename T>
    bool ILL<T>::IsEmpty() const
    {
    return (head == nullptr);
    }

    template <typename T>
    void ILL<T>::Append(T& elem)
    {
    auto& node = elem.*offset;
    NRR_ASSERTF(node.next == nullptr && node.prev == nullptr, "Can't append an item that's already on a list");

    if (head)
    {
    auto& headNode = head->*offset;
    (headNode.prev->*offset).next = &elem;
    node.prev = headNode.prev;
    node.next = head;
    headNode.prev = &elem;
    }
    else
    {
    head = &elem;
    node.next = &elem;
    node.prev = &elem;
    }
    }

    template <typename T>
    void ILL<T>::Insert(T& before, T& elem)
    {
    auto& beforeNode = before.*offset;
    NRR_ASSERTF(beforeNode.next != nullptr && beforeNode.prev != nullptr, "Can't insert before an item that's not on a list");
    auto& node = elem.*offset;
    NRR_ASSERTF(node.next == nullptr && node.prev == nullptr, "Can't insert an item that's already on a list");

    (beforeNode.prev->*offset).next = &elem;
    node.prev = beforeNode.prev;
    node.next = &before;
    beforeNode.prev = &elem;
    }

    template <typename T>
    void ILL<T>::Remove(T& elem)
    {
    auto& node = elem.*offset;
    NRR_ASSERTF(node.next != nullptr && node.prev != nullptr, "Can't remove an item that's not on a list");

    if (node.next == &elem && node.prev == &elem)
    {
    NRR_ASSERT(head == &elem);
    head = nullptr;
    }
    else
    {
    (node.next->*offset).prev = node.prev;
    (node.prev->*offset).next = node.next;

    if (head == &elem)
    {
    head = node.next;
    }
    }

    node.next = nullptr;
    node.prev = nullptr;
    }

    template <typename T>
    void ILL<T>::Clear()
    {
    if (!head)
    return;

    for (T* elem = head;;)
    {
    T* next = (elem->*offset).next;
    (elem->*offset).next = nullptr;
    (elem->*offset).prev = nullptr;
    if (next == head)
    break;
    elem = next;
    }

    head = nullptr;
    }

    template <typename T>
    typename ILL<T>::Iterator ILL<T>::begin()
    {
    return Iterator(head, offset);
    }

    template <typename T>
    typename ILL<T>::Iterator ILL<T>::end()
    {
    return Iterator(nullptr, offset);
    }

    template <typename T>
    typename ILL<T>::ConstIterator ILL<T>::begin() const
    {
    return ConstIterator(head, offset);
    }

    template <typename T>
    typename ILL<T>::ConstIterator ILL<T>::end() const
    {
    return ConstIterator(nullptr, offset);
    }

    template <typename T>
    ILL<T>::Node::~Node()
    {
    // Remove(*this);
    NRR_ASSERTF(next == nullptr && prev == nullptr, "Destroying an object that's still on a linked list");
    }

    template <typename T>
    ILL<T>::Node::Node(const Node&)
    : Node() // Don't copy the next & prev pointers from the source Node
    {
    }

    template <typename T>
    typename ILL<T>::Node& ILL<T>::Node::operator = (const Node&)
    {
    // Don't copy the next & prev pointers from the source Node
    return *this;
    }

    template <typename T>
    ILL<T>::Iterator::Iterator(T* elem_, Node T::* offset_)
    : head(elem_), elem(elem_), offset(offset_)
    {
    }

    template <typename T>
    bool ILL<T>::Iterator::operator == (const Iterator& other)
    {
    return (head == other.head && elem == other.elem);
    }

    template <typename T>
    bool ILL<T>::Iterator::operator != (const Iterator& other)
    {
    return (head != other.head || elem != other.elem);
    }

    template <typename T>
    typename ILL<T>::Iterator& ILL<T>::Iterator::operator ++ ()
    {
    if (elem)
    {
    elem = (elem->*offset).next;
    if (elem == head)
    {
    head = nullptr;
    elem = nullptr;
    }
    }

    return *this;
    }

    template <typename T>
    T& ILL<T>::Iterator::operator * () const
    {
    return *elem;
    }

    template <typename T>
    T& ILL<T>::Iterator::operator -> () const
    {
    return *elem;
    }

    template <typename T>
    ILL<T>::ConstIterator::ConstIterator(T* elem_, Node T::* offset_)
    : head(elem_), elem(elem_), offset(offset_)
    {
    }

    template <typename T>
    bool ILL<T>::ConstIterator::operator == (const ConstIterator& other)
    {
    return (head == other.head && elem == other.elem);
    }

    template <typename T>
    bool ILL<T>::ConstIterator::operator != (const ConstIterator& other)
    {
    return (head != other.head || elem != other.elem);
    }

    template <typename T>
    typename ILL<T>::ConstIterator& ILL<T>::ConstIterator::operator ++ ()
    {
    if (elem)
    {
    elem = (elem->*offset).next;
    if (elem == head)
    {
    head = nullptr;
    elem = nullptr;
    }
    }

    return *this;
    }

    template <typename T>
    const T& ILL<T>::ConstIterator::operator * () const
    {
    return *elem;
    }

    template <typename T>
    const T& ILL<T>::ConstIterator::operator -> () const
    {
    return *elem;
    }
    }