Add IndexPool

1 files changed, 189 insertions, 7 deletions

diff --git a/asl/handle_pool/index_pool.hpp b/asl/handle_pool/index_pool.hpp
index 1d359d5..56345e8 100644
--- a/asl/handle_pool/index_pool.hpp
+++ b/asl/handle_pool/index_pool.hpp
@@ -6,12 +6,11 @@
 #include "asl/base/meta.hpp"
 #include "asl/containers/chunked_buffer.hpp"
 #include "asl/memory/allocator.hpp"
+#include "asl/types/option.hpp"
 
 namespace asl
 {
 
-// @Todo Uniquely represented for the handle?
-
 template<
     int kIndexBits_,
     int kGenBits_,
@@ -27,6 +26,7 @@ struct index_pool_config
     using PrimitiveUserType = smallest_unsigned_integer_type_for_width<size_of<UserType> * 8>;
 
     static_assert(trivially_copy_constructible<UserType>);
+    static_assert(trivially_destructible<UserType>);
     static_assert(size_of<UserType> == size_of<PrimitiveUserType>, "UserType should be of size 1, 2 or 4");
 
     static constexpr int kUserBits = []() static -> int {
@@ -43,13 +43,17 @@ struct index_pool_config
 
     using HandleType = smallest_unsigned_integer_type_for_width<kIndexBits + kGenBits + kUserBits + 1>;
 
-    static constexpr int kGenShift  = kIndexBits;
-    static constexpr int kUserShift = kIndexBits + kGenBits;
+    static constexpr int        kGenShift  = kIndexBits;
+    static constexpr int        kUserShift = kIndexBits + kGenBits;
 
     static constexpr HandleType kValidMask = HandleType{1} << (size_of<HandleType> * 8 - 1);
     static constexpr HandleType kIndexMask = (HandleType{1} << kIndexBits) - 1;
     static constexpr HandleType kGenMask   = ((HandleType{1} << kGenBits) - 1) << kGenShift;
     static constexpr HandleType kUserMask  = ((HandleType{1} << kUserBits) - 1) << kUserShift;
+    static constexpr HandleType kNiche     = static_cast<HandleType>(~uint64_t{kValidMask});
+
+    static constexpr uint64_t   kMaxGen    = (uint64_t{1} << kGenBits) - 1;
+    static constexpr uint64_t   kMaxIndex  = (uint64_t{1} << kIndexBits) - 1;
 };
 
 template<
@@ -60,14 +64,19 @@ template<
 >
 class index_pool_handle
 {
-    // using config = index_pool_config<5, 5>;
+public:
     using config = index_pool_config<kIndexBits_, kGenBits_, UserType_, kUserBits_>;
 
+private:
     config::HandleType m_handle{};
 
 public:
     constexpr index_pool_handle() = default;
 
+    constexpr explicit index_pool_handle(niche_t)
+        : m_handle{config::kNiche}
+    {}
+
     constexpr index_pool_handle(uint64_t index, uint64_t gen)
         requires (!config::kHasUser)
         : m_handle{static_cast<config::HandleType>(
@@ -92,9 +101,9 @@ public:
         ASL_ASSERT((bit_cast<typename config::PrimitiveUserType>(user) & (uint64_t{config::kUserMask} >> config::kUserShift)) == bit_cast<typename config::PrimitiveUserType>(user));
     }
 
-    constexpr bool is_valid(this index_pool_handle self)
+    constexpr bool is_null(this index_pool_handle self)
     {
-        return self.m_handle & config::kValidMask;
+        return !(self.m_handle & config::kValidMask);
     }
 
     constexpr uint64_t index(this index_pool_handle self)
@@ -114,6 +123,179 @@ public:
     }
 
     constexpr bool operator==(this index_pool_handle self, index_pool_handle other) = default;
+
+    constexpr bool operator==(this index_pool_handle self, niche_t)
+    {
+        return self.m_handle == config::kNiche;
+    }
+};
+
+template<
+    int kIndexBits_,
+    int kGenBits_,
+    typename UserType_,
+    int kUserBits_
+>
+struct is_uniquely_represented<index_pool_handle<kIndexBits_, kGenBits_, UserType_, kUserBits_>> : true_type {};
+
+template<
+    int kIndexBits_,
+    int kGenBits_,
+    typename UserType_ = empty,
+    int kUserBits_ = 0,
+    typename Payload = empty,
+    allocator Allocator = DefaultAllocator
+>
+class IndexPool
+{
+public:
+    using handle = index_pool_handle<kIndexBits_, kGenBits_, UserType_, kUserBits_>;
+
+private:
+    using config = handle::config;
+
+    static constexpr bool kHasPayload = !same_as<Payload, empty>;
+
+    // @Todo Remove need for default constructible & trivially destructible for payload
+    // Use maybe_uninit for it
+
+    // @Todo Use dummy user type with inner handle type -> no need to set user data when allocating handle
+
+    static_assert(default_constructible<Payload>);
+    static_assert(copy_constructible<Payload>);
+    static_assert(trivially_destructible<Payload>);
+
+    struct Slot
+    {
+        bool is_end_of_list : 1;
+        bool is_active      : 1;
+
+        handle handle;
+
+        ASL_NO_UNIQUE_ADDRESS Payload payload;
+    };
+
+    chunked_buffer<Slot, 256, Allocator> m_slots;
+
+    // We only use the index, this is essentially the head of the linked
+    // list to the first available slot.
+    // Then the index of each slot points to the next available one.
+    handle m_first_available;
+
+    static constexpr handle make_handle(uint64_t index, uint64_t gen, [[maybe_unused]] config::UserType user_data)
+    {
+        if constexpr (config::kHasUser)
+        {
+            return handle(index, gen, user_data);
+        }
+        else
+        {
+            return handle(index, gen);
+        }
+    };
+
+    void allocate_new_slot(config::UserType user)
+    {
+        const auto new_index = static_cast<uint64_t>(m_slots.size());
+        if (new_index > config::kMaxIndex) { return; }
+
+        const handle new_handle = make_handle(new_index, 0, user);
+
+        m_slots.push(Slot{
+            .is_end_of_list = true,
+            .is_active      = false,
+            .handle         = new_handle,
+            .payload        = Payload{}
+        });
+
+        m_first_available = new_handle;
+    }
+
+    option<handle> acquire_handle(const Payload& payload, config::UserType user)
+    {
+        if (m_first_available.is_null())
+        {
+            allocate_new_slot(user);
+        }
+
+        if (m_first_available.is_null())
+        {
+            return nullopt;
+        }
+
+        auto index = m_first_available.index();
+
+        Slot& slot = m_slots[static_cast<isize_t>(index)];
+        ASL_ASSERT(!slot.is_active);
+
+        m_first_available = slot.is_end_of_list ? handle{} : slot.handle;
+
+        slot.is_active = true;
+        slot.payload   = payload;
+
+        return make_handle(index, slot.handle.gen(), user);
+    }
+
+    auto get_slot_if_valid(this auto&& self, handle h)
+        -> copy_const_t<decltype(self), Slot>*
+    {
+        auto index = static_cast<isize_t>(h.index());
+        if (index < 0 || index >= self.m_slots.size()) { return nullptr; }
+
+        auto& slot = self.m_slots[index];
+        if (!slot.is_active || slot.handle.gen() != h.gen())
+        {
+            return nullptr;
+        }
+
+        return &slot;
+    }
+
+public:
+    IndexPool() requires default_constructible<Allocator> = default;
+
+    explicit IndexPool(Allocator allocator) : m_slots{std::move(allocator)} {}
+
+    option<handle> acquire(const Payload& payload)
+    {
+        return acquire_handle(payload, {});
+    }
+
+    handle acquire_ensure(const Payload& payload)
+    {
+        auto opt = acquire(payload);
+        ASL_ASSERT_RELEASE(opt.has_value());
+        return opt.value();
+    }
+
+    // @Todo Add a policy to abandon slots that reached max generation
+    void release(handle h)
+    {
+        if (Slot* slot = get_slot_if_valid(h); slot != nullptr)
+        {
+            const uint64_t next_gen = h.gen() == config::kMaxGen ? 0 : h.gen() + 1;
+
+            slot->is_active = false;
+
+            if (m_first_available.is_null())
+            {
+                slot->is_end_of_list = true;
+                slot->handle = make_handle(h.index(), next_gen, {});
+            }
+            else
+            {
+                slot->is_end_of_list = false;
+                slot->handle = make_handle(m_first_available.index(), next_gen, {});
+            }
+
+            m_first_available = h;
+        }
+    }
+
+    bool is_valid(handle h) const
+    {
+        return get_slot_if_valid(h) != nullptr;
+    }
 };
 
 } // namespace asl