w

12 files changed, 342 insertions, 1 deletions

diff --git a/src/handle-fwd.hpp b/src/handle-fwd.hpp
new file mode 100644
index 00000000..919461f5
--- /dev/null
+++ b/src/handle-fwd.hpp
@@ -0,0 +1,36 @@
+#pragma once
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize> struct Item;
+
+template<typename OBJ, uint32_t PAGE_SIZE>
+struct Handle
+{
+    uint32_t index = (uint32_t)-1;
+    uint32_t counter = 0;
+
+#if 0
+    using Obj = OBJ;
+    static constexpr auto PageSize = PAGE_SIZE;
+#endif
+
+    const OBJ& get() const;
+    OBJ& get();
+
+    bool operator==(const Handle& other) const noexcept;
+
+    explicit operator bool() const noexcept;
+
+private:
+    static Item<OBJ, PAGE_SIZE>& get_from_pool(uint32_t index, uint32_t counter);
+};
+
+} // namespace floormat::Handle
+
+namespace floormat {
+
+template<typename Obj, uint32_t PageSize>
+using handle = struct Handle::Handle<Obj, PageSize>;
+
+} // namespace floormat
diff --git a/src/handle-page.hpp b/src/handle-page.hpp
new file mode 100644
index 00000000..dee35a9e
--- /dev/null
+++ b/src/handle-page.hpp
@@ -0,0 +1,40 @@
+#pragma once
+#include "handle-fwd.hpp"
+#include "compat/defs.hpp"
+#include <array>
+#include <cr/BitArray.h>
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize>
+struct Item
+{
+    union { Obj object; };
+    Handle<Obj, PageSize> handle;
+    uint32_t next;
+};
+
+template<typename Obj, uint32_t PageSize>
+class Page
+{
+    friend class Handle<Obj, PageSize>;
+
+    std::array<Item<Obj, PageSize>, PageSize> storage;
+    BitArray used_map; // todo replace with a rewrite of std::bitset
+    uint32_t start_index;
+    uint32_t used_count = 0;
+    uint32_t first_free = (uint32_t)-1;
+
+public:
+    fm_DECLARE_DELETED_COPY_MOVE_ASSIGNMENTS(Page);
+
+    explicit Page(uint32_t start_index);
+    ~Page() noexcept;
+
+    [[nodiscard]] Item<Obj, PageSize>& allocate();
+    void deallocate(Handle<Obj, PageSize> obj);
+    bool is_empty();
+    bool is_full();
+};
+
+} // namespace floormat::Handle
diff --git a/src/handle-page.inl b/src/handle-page.inl
new file mode 100644
index 00000000..7c9d5a39
--- /dev/null
+++ b/src/handle-page.inl
@@ -0,0 +1,73 @@
+#pragma once
+#include "handle-page.hpp"
+#include "compat/assert.hpp"
+#include "compat/pretty-function.hpp"
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize>
+Page<Obj, PageSize>::~Page() noexcept
+{
+    fm_assert(used_count == 0);
+}
+
+template<typename Obj, uint32_t PageSize>
+Page<Obj, PageSize>::Page(uint32_t start_index):
+    used_map{ValueInit, PageSize},
+    start_index{start_index},
+    first_free{start_index}
+{
+    fm_assert(size_t{start_index} + size_t{PageSize} <= 1<<31 && start_index + PageSize > start_index);
+    auto val = start_index;
+    for (auto i = 0u; i < PageSize; i++)
+    {
+        auto& o = storage.data()[i];
+        o.handle = {val++, 0};
+        o.next = val;
+    }
+}
+
+template<typename Obj, uint32_t PageSize>
+Item<Obj, PageSize>& Page<Obj, PageSize>::allocate()
+{
+    fm_assert(used_count < PageSize);
+    auto first_freeʹ = first_free - start_index;
+    fm_debug_assert(first_freeʹ < PageSize);
+    fm_debug_assert(!used_map[first_freeʹ]);
+    auto& item = storage[first_freeʹ];
+    first_free = item.next;
+    used_count++;
+    used_map.set(first_freeʹ, true);
+    return item;
+}
+
+template<typename Obj, uint32_t PageSize>
+void Page<Obj, PageSize>::deallocate(Handle<Obj, PageSize> obj)
+{
+    auto index = obj.index - start_index;
+    fm_debug_assert(index < PageSize);
+    fm_assert(used_map[index]);
+    fm_debug_assert(used_count > 0);
+    fm_debug_assert(first_free != (uint32_t)-1);
+    auto& item = storage[index];
+    auto ctr = ++item.handle.counter;
+    if (ctr == uint32_t{0}) [[unlikely]]
+        Debug{} << "counter" << FM_PRETTY_FUNCTION << "overflowed";
+    item.next = first_free;
+    used_count--;
+    first_free = obj.index;
+}
+
+template<typename Obj, uint32_t PageSize>
+bool Page<Obj, PageSize>::is_empty()
+{
+    return used_count == 0;
+}
+
+template<typename Obj, uint32_t PageSize>
+bool Page<Obj, PageSize>::is_full()
+{
+    return used_count == PageSize;
+}
+
+} // namespace floormat::Handle
diff --git a/src/handle-pool.hpp b/src/handle-pool.hpp
new file mode 100644
index 00000000..da7a2538
--- /dev/null
+++ b/src/handle-pool.hpp
@@ -0,0 +1,36 @@
+#pragma once
+#include "compat/defs.hpp"
+#include <cr/Array.h>
+#include <cr/Pointer.h>
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize> class Page;
+
+template<typename Obj, uint32_t PageSize>
+class Pool
+{
+    friend class Handle<Obj, PageSize>;
+
+    static Pointer<Pool<Obj, PageSize>> make_pool();
+    static Page<Obj, PageSize>& find_page();
+
+    Array<Pointer<Page<Obj, PageSize>>> pages;
+    size_t next_page_offset = 0;
+
+    static Pointer<Pool<Obj, PageSize>> pool = make_pool();
+
+public:
+    fm_DECLARE_DELETED_COPY_MOVE_ASSIGNMENTS(Pool);
+
+    explicit Pool();
+    ~Pool() noexcept;
+
+    template<typename... Xs>
+    requires requires (Xs&&... xs) {
+        Obj{forward<Xs>(xs)...};
+    }
+    static Handle<Obj, PageSize> make_object(Xs&&... xs);
+};
+
+} // namespace floormat::Handle
diff --git a/src/handle-pool.inl b/src/handle-pool.inl
new file mode 100644
index 00000000..5fe63c88
--- /dev/null
+++ b/src/handle-pool.inl
@@ -0,0 +1,47 @@
+#pragma once
+#include "handle-pool.hpp"
+#include "handle-page.hpp"
+#include "compat/move.hpp"
+#include <cr/GrowableArray.h>
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize>
+template<typename... Xs>
+requires requires (Xs&&... xs) {
+    Obj{forward<Xs>(xs)...};
+}
+Handle<Obj, PageSize> Pool<Obj, PageSize>::make_object(Xs&&... xs)
+{
+    auto ret = std::shared_ptr<T>(new Obj{forward<Xs>(xs)...});
+    do_make_object(std::static_pointer_cast<object>(ret));
+    return ret;
+}
+
+template<typename Obj, uint32_t PageSize>
+Pointer<Pool<Obj, PageSize>>
+Pool<Obj, PageSize>::make_pool()
+{
+    auto pool = Pointer<Pool<Obj, PageSize>>{InPlace};
+    arrayReserve(pool->pages, 16);
+    return pool;
+}
+
+template<typename Obj, uint32_t PageSize>
+Page<Obj, PageSize>&
+Pool<Obj, PageSize>::find_page()
+{
+    auto& P = *pool;
+    auto sz = P.pages.size();
+    for (auto i = 0uz; i < sz; i++)
+    {
+        auto& p = *P.pages.data()[i];
+        if (!p.is_full())
+            return p;
+    }
+    arrayAppend(P.pages, InPlace, InPlace, P.next_page_offset);
+    P.next_page_offset += PageSize;
+    return P.pages.back();
+}
+
+} // namespace floormat::Handle
diff --git a/src/handle.cpp b/src/handle.cpp
new file mode 100644
index 00000000..af0220f6
--- /dev/null
+++ b/src/handle.cpp
@@ -0,0 +1,14 @@
+#include "handle.inl"
+
+namespace floormat::Handle {
+
+static_assert(sizeof(Handle) == sizeof(HandleType));
+
+} // namespace floormat::Handle
+
+
+namespace floormat {
+
+
+
+} // namespace floormat
diff --git a/src/handle.hpp b/src/handle.hpp
new file mode 100644
index 00000000..7620e69b
--- /dev/null
+++ b/src/handle.hpp
@@ -0,0 +1,13 @@
+#pragma once
+#include "handle-fwd.hpp"
+#include "compat/assert.hpp"
+
+namespace floormat::Handle {
+
+
+
+} // namespace floormat::Handle
+
+namespace floormat {
+
+} // namespace floormat
diff --git a/src/handle.inl b/src/handle.inl
new file mode 100644
index 00000000..2f6daa20
--- /dev/null
+++ b/src/handle.inl
@@ -0,0 +1,57 @@
+#pragma once
+#include "handle.hpp"
+//#include "handle-pool.inl"
+#include "compat/assert.hpp"
+#include <cr/Pointer.h>
+
+namespace floormat::Handle {
+
+template<typename Obj, uint32_t PageSize> class Pool;
+
+template<typename Obj, uint32_t PageSize>
+bool Handle<Obj, PageSize>::operator==(const Handle& other) const noexcept
+{
+    bool ret = index == other.index;
+    fm_debug_assert(!ret || counter == other.counter);
+    return ret;
+}
+
+template<typename Obj, uint32_t PageSize>
+Handle<Obj, PageSize>::operator bool() const noexcept
+{
+    return index != (uint32_t)-1;
+}
+
+template<typename Obj, uint32_t PageSize>
+const Obj& Handle<Obj, PageSize>::get() const
+{
+    return get_from_pool(index, counter).object;
+}
+
+template<typename Obj, uint32_t PageSize>
+Obj& Handle<Obj, PageSize>::get()
+{
+    return get_from_pool(index, counter).object;
+}
+
+template<typename Obj, uint32_t PageSize>
+Item<Obj, PageSize>& Handle<Obj, PageSize>::get_from_pool(uint32_t index, uint32_t counter)
+{
+    auto page_idx = index / PageSize;
+    auto obj_idx = index % PageSize;
+    fm_assert(Pool<Obj, PageSize>::pages.size() < page_idx);
+    auto& page = Pool<Obj, PageSize>::pages.data()[page_idx];
+    auto& item = page->storage[obj_idx];
+    fm_debug_assert(page.used_map[obj_idx]);
+    fm_assert(item.handle.counter == counter);
+    fm_debug_assert(item.handle == index + page.start_index);
+    return item.object;
+}
+
+} // namespace floormat::Handle
+
+namespace floormat {
+
+
+
+} // namespace floormat
diff --git a/test/app.cpp b/test/app.cpp
index 6ace3ca5..47b019c7 100644
--- a/test/app.cpp
+++ b/test/app.cpp
@@ -62,6 +62,7 @@ int App::exec()
         FM_TEST(test_astar_pool),
         FM_TEST(test_coords),
         FM_TEST(test_hole),
+        FM_TEST(test_handle),
         FM_TEST(test_bptr),
         FM_TEST(test_iptr),
         FM_TEST(test_entity),
diff --git a/test/app.hpp b/test/app.hpp
index b1995e77..d32b9759 100644
--- a/test/app.hpp
+++ b/test/app.hpp
@@ -23,6 +23,7 @@ void test_coords();
 void test_critter();
 void test_dijkstra();
 void test_entity();
+void test_handle();
 void test_hash();
 void test_hole();
 void test_iptr();
diff --git a/test/bptr.cpp b/test/bptr.cpp
index b254f295..303bf027 100644
--- a/test/bptr.cpp
+++ b/test/bptr.cpp
@@ -48,7 +48,7 @@ struct A
 {
     int val, serial;
     explicit A(int val) : val{val}, serial{++A_total} { ++A_alive; }
-    ~A() noexcept { --A_alive; fm_assert(A_alive >= 0); }
+    ~A() noexcept override { --A_alive; fm_assert(A_alive >= 0); }
 
     fm_DECLARE_DELETED_COPY_MOVE_ASSIGNMENTS(A);
 };
diff --git a/test/handle.cpp b/test/handle.cpp
new file mode 100644
index 00000000..79416c2c
--- /dev/null
+++ b/test/handle.cpp
@@ -0,0 +1,23 @@
+#include "app.hpp"
+#include "src/handle.inl"
+#include "src/handle-page.inl"
+//#include "src/handle-pool.inl"
+
+namespace floormat::Test {
+
+namespace {
+
+void test1()
+{
+
+}
+
+} // namespace
+
+
+void test_handle()
+{
+    test1();
+}
+
+} // namespace floormat::Test