1 files changed, 158 insertions, 0 deletions
diff --git a/include/freelist.hpp b/include/freelist.hpp
new file mode 100644
index 0000000..2df1ca5
--- /dev/null
+++ b/include/freelist.hpp
@@ -0,0 +1,158 @@
+#pragma once
+
+#include "utils.hpp"
+#include "handle.hpp"
+
+static constexpr u32 default_element_count = 1024U;
+
+template<typename T, const size_t initial_size = default_element_count>
+class freelist {
+    public:
+
+    freelist() {
+        grow(initial_size);
+    }
+
+    handle<T> add(const T& item) {
+        // auto id = elements[0U].next_free;
+        auto id = next_free_id;
+
+        if (id == freelist<T>::invalid_id) {
+            grow(elements.size());
+
+            // id = elements[0U].next_free;
+            id = next_free_id;
+        }
+
+        auto& element = elements[id];
+
+        next_free_id = element.next_free;
+        // elements[0U].next_free = element.next_free;
+        element.item = std::move(item);
+
+        assert(element.generation + 1 != UINT32_MAX);
+
+        return { id, ++element.generation };
+    }
+
+    void remove(handle<T> handle) {
+        assert(handle.generation == elements[handle.id].generation);
+        // elements[handle.id].next_free = elements[0U].next_free;
+        // elements[0U].next_free = handle.id;
+        elements[handle.id].next_free = next_free_id;
+        next_free_id = handle.id;
+    }
+
+    T& operator[](handle<T> handle) {
+        assert(handle.generation == elements[handle.id].generation);
+        return elements[handle.id].item;
+    }
+
+    const T& operator[](handle<T> handle) const {
+        assert(handle.generation == elements[handle.id].generation);
+        return elements[handle.id].item;
+    }
+
+    static constexpr uint32_t invalid_id = UINT32_MAX;
+
+    struct element {
+        union {
+            T item;
+            uint32_t next_free = freelist<T>::invalid_id;
+        };
+        uint32_t generation = 0U;
+    };
+
+    const std::vector<freelist::element>& get_list() const {
+        return elements;
+    }
+
+private:
+    void grow(size_t grow_size) {
+        size_t size = elements.size();
+        uint32_t next_free = static_cast<uint32_t>(size);
+        next_free_id = next_free;
+
+        elements.reserve(size + grow_size);
+
+        for (auto id { 0U }; id < initial_size; id++) {
+            elements.push_back(
+                {
+                    .next_free = static_cast<uint32_t>(++next_free % initial_size),
+                }
+            );
+        }
+
+        // this makes it impossible to know
+        elements.back().next_free = freelist<T>::invalid_id;
+        elements.back().next_free = freelist<T>::invalid_id;
+    }
+
+    std::vector<element>        elements;
+    uint32_t next_free_id;
+};
+
+template<const size_t initial_size = default_element_count>
+class idlist {
+    public:
+
+    idlist() {
+        grow(initial_size);
+    }
+
+    handle<void> add() {
+        // auto id = elements[0U].next_free;
+        auto id = next_free_id;
+
+        if (id == idlist::invalid_id) {
+            grow(elements.size());
+
+            // id = elements[0U].next_free;
+            id = next_free_id;
+        }
+
+        auto& element = elements[id];
+        next_free_id = element.next_free;
+        elements[0U].next_free = element.next_free;
+        element.next_free = idlist::invalid_id;
+
+        return { id, ++element.generation };
+    }
+
+    void remove(handle<void> handle) {
+        assert(handle.generation == elements[handle.id].generation);
+        // elements[handle.id].next_free = elements[0U].next_free;
+        // elements[0U].next_free = handle.id;
+        elements[handle.id].next_free = next_free_id;
+        next_free_id = handle.id;
+    }
+
+    static constexpr uint32_t invalid_id = UINT32_MAX;
+
+private:
+    void grow(size_t grow_size) {
+        auto size = elements.size();
+        uint32_t next_free = static_cast<uint32_t>(size);
+        next_free_id = next_free;
+
+        elements.reserve(size + grow_size);
+
+        for (auto id { 0U }; id < initial_size; id++) {
+            elements.push_back(
+                {
+                    .next_free = static_cast<uint32_t>(++next_free% initial_size),
+                }
+            );
+        }
+
+        elements.back().next_free = idlist::invalid_id;
+    }
+
+    struct element {
+        uint32_t next_free = idlist::invalid_id;
+        uint32_t generation = 0U;
+    };
+
+    std::vector<element>        elements;
+    uint32_t next_free_id;
+};