From eb469ff58365517515d73827e70a9519436b5858 Mon Sep 17 00:00:00 2001 From: Stanislaw Halik Date: Fri, 12 Jul 2024 20:19:25 +0200 Subject: w --- src/handle-fwd.hpp | 36 ++++++++++++++++++++++++++ src/handle-page.hpp | 40 +++++++++++++++++++++++++++++ src/handle-page.inl | 73 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/handle-pool.hpp | 36 ++++++++++++++++++++++++++ src/handle-pool.inl | 47 ++++++++++++++++++++++++++++++++++ src/handle.cpp | 14 ++++++++++ src/handle.hpp | 13 ++++++++++ src/handle.inl | 57 +++++++++++++++++++++++++++++++++++++++++ test/app.cpp | 1 + test/app.hpp | 1 + test/bptr.cpp | 2 +- test/handle.cpp | 23 +++++++++++++++++ 12 files changed, 342 insertions(+), 1 deletion(-) create mode 100644 src/handle-fwd.hpp create mode 100644 src/handle-page.hpp create mode 100644 src/handle-page.inl create mode 100644 src/handle-pool.hpp create mode 100644 src/handle-pool.inl create mode 100644 src/handle.cpp create mode 100644 src/handle.hpp create mode 100644 src/handle.inl create mode 100644 test/handle.cpp 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 struct Item; + +template +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& get_from_pool(uint32_t index, uint32_t counter); +}; + +} // namespace floormat::Handle + +namespace floormat { + +template +using handle = struct Handle::Handle; + +} // 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 +#include + +namespace floormat::Handle { + +template +struct Item +{ + union { Obj object; }; + Handle handle; + uint32_t next; +}; + +template +class Page +{ + friend class Handle; + + std::array, 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& allocate(); + void deallocate(Handle 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 +Page::~Page() noexcept +{ + fm_assert(used_count == 0); +} + +template +Page::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 +Item& Page::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 +void Page::deallocate(Handle 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 +bool Page::is_empty() +{ + return used_count == 0; +} + +template +bool Page::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 +#include + +namespace floormat::Handle { + +template class Page; + +template +class Pool +{ + friend class Handle; + + static Pointer> make_pool(); + static Page& find_page(); + + Array>> pages; + size_t next_page_offset = 0; + + static Pointer> pool = make_pool(); + +public: + fm_DECLARE_DELETED_COPY_MOVE_ASSIGNMENTS(Pool); + + explicit Pool(); + ~Pool() noexcept; + + template + requires requires (Xs&&... xs) { + Obj{forward(xs)...}; + } + static Handle 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 + +namespace floormat::Handle { + +template +template +requires requires (Xs&&... xs) { + Obj{forward(xs)...}; +} +Handle Pool::make_object(Xs&&... xs) +{ + auto ret = std::shared_ptr(new Obj{forward(xs)...}); + do_make_object(std::static_pointer_cast(ret)); + return ret; +} + +template +Pointer> +Pool::make_pool() +{ + auto pool = Pointer>{InPlace}; + arrayReserve(pool->pages, 16); + return pool; +} + +template +Page& +Pool::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 + +namespace floormat::Handle { + +template class Pool; + +template +bool Handle::operator==(const Handle& other) const noexcept +{ + bool ret = index == other.index; + fm_debug_assert(!ret || counter == other.counter); + return ret; +} + +template +Handle::operator bool() const noexcept +{ + return index != (uint32_t)-1; +} + +template +const Obj& Handle::get() const +{ + return get_from_pool(index, counter).object; +} + +template +Obj& Handle::get() +{ + return get_from_pool(index, counter).object; +} + +template +Item& Handle::get_from_pool(uint32_t index, uint32_t counter) +{ + auto page_idx = index / PageSize; + auto obj_idx = index % PageSize; + fm_assert(Pool::pages.size() < page_idx); + auto& page = Pool::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 -- cgit v1.2.3