Add intrusive_list

4 files changed, 380 insertions, 4 deletions

diff --git a/asl/containers/BUILD.bazel b/asl/containers/BUILD.bazel
index 2d2e057..792b812 100644
--- a/asl/containers/BUILD.bazel
+++ b/asl/containers/BUILD.bazel
@@ -40,6 +40,17 @@ cc_library(
     visibility = ["//visibility:public"],
 )
 
+cc_library(
+    name = "intrusive_list",
+    hdrs = [
+        "intrusive_list.hpp",
+    ],
+    deps = [
+        "//asl/base",
+    ],
+    visibility = ["//visibility:public"],
+)
+
 [cc_test(
     name = "%s_tests" % name,
     srcs = [
@@ -55,4 +66,5 @@ cc_library(
     "buffer",
     "hash_map",
     "hash_set",
+    "intrusive_list",
 ]]
diff --git a/asl/containers/intrusive_list.hpp b/asl/containers/intrusive_list.hpp
new file mode 100644
index 0000000..10dbe23
--- /dev/null
+++ b/asl/containers/intrusive_list.hpp
@@ -0,0 +1,141 @@
+#pragma once
+
+#include "asl/base/meta.hpp"
+#include "asl/base/assert.hpp"
+
+namespace asl
+{
+
+template<typename T>
+struct intrusive_list_node
+{
+    T* prev{};
+    T* next{};
+};
+
+template<typename T>
+concept is_intrusive_list_node = convertible_from<intrusive_list_node<T>*, T*>;
+
+
+template<is_intrusive_list_node T>
+class IntrusiveList
+{
+    struct sentinel: public intrusive_list_node<T> {};
+
+    sentinel m_sentinel{};
+
+    T* sentinel() { return reinterpret_cast<T*>(&m_sentinel); }
+    const T* sentinel() const { return reinterpret_cast<const T*>(&m_sentinel); }
+
+    constexpr T* head_inner() const { return m_sentinel.next; }
+
+    constexpr T* tail_inner() const { return m_sentinel.prev; }
+
+    void insert_after(T* before, T* after)
+    {
+        after->prev = before;
+        after->next = before->next;
+
+        before->next = after;
+        after->next->prev = after;
+    }
+
+public:
+    constexpr IntrusiveList() : m_sentinel{ sentinel(), sentinel() } {}
+
+    constexpr bool is_empty() const { return head_inner() == sentinel(); }
+
+    void push_front(T* node)
+    {
+        ASL_ASSERT(node->next == nullptr && node->prev == nullptr);
+        insert_after(head_inner()->prev, node);
+    }
+
+    void push_back(T* node)
+    {
+        ASL_ASSERT(node->next == nullptr && node->prev == nullptr);
+        insert_after(tail_inner(), node);
+    }
+
+    T* head() const
+    {
+        T* h = head_inner();
+        return (h == sentinel()) ? nullptr : h;
+    }
+
+    T* tail() const
+    {
+        T* t = tail_inner();
+        return (t == sentinel()) ? nullptr : t;
+    }
+
+    void detach(T* node)
+    {
+        ASL_ASSERT(node->next != nullptr && node->prev != nullptr);
+
+        node->prev->next = node->next;
+        node->next->prev = node->prev;
+
+        node->next = nullptr;
+        node->prev = nullptr;
+    }
+
+    T* pop_front()
+    {
+        if (T* h = head_inner(); h != sentinel())
+        {
+            detach(h);
+            return h;
+        }
+        return nullptr;
+    }
+
+    T* pop_back()
+    {
+        if (T* t = tail_inner(); t != sentinel())
+        {
+            detach(t);
+            return t;
+        }
+        return nullptr;
+    }
+
+    template<typename TT>
+    struct generic_iterator
+    {
+        TT* m_node;
+
+    public:
+        constexpr explicit generic_iterator(TT* node) : m_node{node} {}
+
+        constexpr bool operator==(const generic_iterator& other) const = default;
+
+        constexpr generic_iterator& operator++()
+        {
+            m_node = m_node->next;
+            return *this;
+        }
+
+        constexpr generic_iterator operator++(int)
+        {
+            return iterator{ exchange(m_node, m_node->next) };
+        }
+
+        constexpr TT& operator*() const { return *m_node; }
+
+        constexpr TT* operator->() const { return m_node; }
+    };
+
+    using iterator = generic_iterator<T>;
+    using const_iterator = generic_iterator<const T>;
+
+    // @Todo(C++23) Deduplicate with deducing-this maybe
+    const_iterator begin() const { return const_iterator{ head_inner() }; }
+    const_iterator end() const { return const_iterator{ sentinel() }; }
+
+    iterator begin() { return iterator{ head_inner() }; }
+    iterator end() { return iterator{ sentinel() }; }
+};
+
+}
+
diff --git a/asl/containers/intrusive_list_tests.cpp b/asl/containers/intrusive_list_tests.cpp
new file mode 100644
index 0000000..ceb54a6
--- /dev/null
+++ b/asl/containers/intrusive_list_tests.cpp
@@ -0,0 +1,226 @@
+#include "asl/containers/intrusive_list.hpp"
+#include "asl/testing/testing.hpp"
+
+struct IntNode : public asl::intrusive_list_node<IntNode>
+{
+    int value;
+
+    explicit IntNode(int v)
+        : asl::intrusive_list_node<IntNode>{}
+        , value{v}
+    {}
+};
+
+ASL_TEST(empty_list)
+{
+    asl::IntrusiveList<IntNode> list;
+    ASL_TEST_EXPECT(list.is_empty());
+    ASL_TEST_EXPECT(list.head() == nullptr);
+    ASL_TEST_EXPECT(list.tail() == nullptr);
+}
+
+ASL_TEST(push_front)
+{
+    IntNode one{1};
+    IntNode two{2};
+    IntNode three{3};
+    asl::IntrusiveList<IntNode> list;
+
+    list.push_front(&one);
+    ASL_TEST_EXPECT(!list.is_empty());
+    ASL_TEST_EXPECT(list.head() == &one);
+    ASL_TEST_EXPECT(list.tail() == &one);
+
+    auto it = list.begin();
+    auto end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.push_front(&two);
+    ASL_TEST_EXPECT(list.head() == &two);
+    ASL_TEST_EXPECT(list.tail() == &one);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 2);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.push_front(&three);
+    ASL_TEST_EXPECT(list.head() == &three);
+    ASL_TEST_EXPECT(list.tail() == &one);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 3);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 2);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+}
+
+ASL_TEST(push_back)
+{
+    IntNode one{1};
+    IntNode two{2};
+    IntNode three{3};
+    asl::IntrusiveList<IntNode> list;
+
+    list.push_back(&one);
+    ASL_TEST_EXPECT(!list.is_empty());
+    ASL_TEST_EXPECT(list.head() == &one);
+    ASL_TEST_EXPECT(list.tail() == &one);
+
+    auto it = list.begin();
+    auto end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.push_back(&two);
+    ASL_TEST_EXPECT(list.head() == &one);
+    ASL_TEST_EXPECT(list.tail() == &two);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 2);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.push_back(&three);
+    ASL_TEST_EXPECT(list.head() == &one);
+    ASL_TEST_EXPECT(list.tail() == &three);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 2);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 3);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+}
+
+ASL_TEST(detach)
+{
+    IntNode one{1};
+    IntNode two{2};
+    IntNode three{3};
+    asl::IntrusiveList<IntNode> list;
+
+    list.push_back(&one);
+    list.push_back(&two);
+    list.push_back(&three);
+
+    list.detach(&two);
+    auto it = list.begin();
+    auto end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 3);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.detach(&three);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(it != end);
+    ASL_TEST_EXPECT(it->value == 1);
+    it++;
+    ASL_TEST_ASSERT(it == end);
+
+    list.detach(&one);
+    it = list.begin();
+    end = list.end();
+
+    ASL_TEST_ASSERT(list.is_empty());
+    ASL_TEST_ASSERT(it == end);
+}
+
+ASL_TEST(pop_front)
+{
+    IntNode one{1};
+    IntNode two{2};
+    IntNode three{3};
+    asl::IntrusiveList<IntNode> list;
+
+    list.push_back(&one);
+    list.push_back(&two);
+    list.push_back(&three);
+
+    IntNode* n = list.pop_front();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(!list.is_empty());
+    ASL_TEST_EXPECT(n->value == 1);
+
+    n = list.pop_front();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(!list.is_empty());
+    ASL_TEST_EXPECT(n->value == 2);
+
+    n = list.pop_front();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(list.is_empty());
+    ASL_TEST_EXPECT(n->value == 3);
+
+    n = list.pop_front();
+    ASL_TEST_ASSERT(n == nullptr);
+    ASL_TEST_ASSERT(list.is_empty());
+}
+
+ASL_TEST(pop_back)
+{
+    IntNode one{1};
+    IntNode two{2};
+    IntNode three{3};
+    asl::IntrusiveList<IntNode> list;
+
+    list.push_back(&one);
+    list.push_back(&two);
+    list.push_back(&three);
+
+    IntNode* n = list.pop_back();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(!list.is_empty());
+    ASL_TEST_EXPECT(n->value == 3);
+
+    n = list.pop_back();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(!list.is_empty());
+    ASL_TEST_EXPECT(n->value == 2);
+
+    n = list.pop_back();
+    ASL_TEST_ASSERT(n != nullptr);
+    ASL_TEST_ASSERT(list.is_empty());
+    ASL_TEST_EXPECT(n->value == 1);
+
+    n = list.pop_back();
+    ASL_TEST_ASSERT(n == nullptr);
+    ASL_TEST_ASSERT(list.is_empty());
+}
diff --git a/asl/types/span.hpp b/asl/types/span.hpp
index b258708..648441a 100644
--- a/asl/types/span.hpp
+++ b/asl/types/span.hpp
@@ -18,10 +18,7 @@ class contiguous_iterator
 public:
     constexpr explicit contiguous_iterator(T* ptr) : m_ptr{ptr} {}
 
-    constexpr bool operator==(const contiguous_iterator& other) const
-    {
-        return other.m_ptr == m_ptr;
-    }
+    constexpr bool operator==(const contiguous_iterator& other) const = default;
 
     constexpr contiguous_iterator& operator++()
     {