diff options
Diffstat (limited to 'asl/handle_pool/index_pool.hpp')
| -rw-r--r-- | asl/handle_pool/index_pool.hpp | 264 |
1 files changed, 257 insertions, 7 deletions
diff --git a/asl/handle_pool/index_pool.hpp b/asl/handle_pool/index_pool.hpp index 1d359d5..2e9ea0f 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,247 @@ 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; + + using internal_handle = index_pool_handle< + kIndexBits_, + kGenBits_, + typename config::PrimitiveUserType, + kUserBits_>; + + static constexpr bool kHasPayload = !same_as<Payload, empty>; + + // @Todo Remove need for default constructible & trivially destructible for payload + // Use maybe_uninit for it + + 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; + + internal_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. + internal_handle m_first_available; + + void allocate_new_slot() + { + const auto new_index = static_cast<uint64_t>(m_slots.size()); + if (new_index > config::kMaxIndex) { return; } + + const internal_handle new_handle = internal_handle(new_index, 0, 0); + + m_slots.push(Slot{ + .is_end_of_list = true, + .is_active = false, + .handle = new_handle, + .payload = Payload{} + }); + + m_first_available = new_handle; + } + + option<internal_handle> acquire_handle(const Payload& payload) + { + if (m_first_available.is_null()) + { + allocate_new_slot(); + } + + 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 ? internal_handle{} : slot.handle; + + slot.is_active = true; + slot.payload = payload; + + return internal_handle(index, slot.handle.gen(), 0); + } + + auto get_slot_if_valid(this auto&& self, handle h) + -> copy_const_t<decltype(self), Slot>* + { + if (h.is_null()) { return nullptr; } + + 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() + requires (!kHasPayload && !config::kHasUser) + { + return acquire_handle({}).transform([](internal_handle h) + { + return handle(h.index(), h.gen()); + }); + } + + handle acquire_ensure() + requires (!kHasPayload && !config::kHasUser) + { + auto opt = acquire(); + ASL_ASSERT_RELEASE(opt.has_value()); + return opt.value(); + } + + option<handle> acquire(const Payload& payload) + requires (kHasPayload && !config::kHasUser) + { + return acquire_handle(payload).transform([](internal_handle h) + { + return handle(h.index(), h.gen()); + }); + } + + handle acquire_ensure(const Payload& payload) + requires (kHasPayload && !config::kHasUser) + { + auto opt = acquire(payload); + ASL_ASSERT_RELEASE(opt.has_value()); + return opt.value(); + } + + option<handle> acquire(config::UserType user) + requires (!kHasPayload && config::kHasUser) + { + return acquire_handle({}).transform([user](internal_handle h) + { + return handle(h.index(), h.gen(), user); + }); + } + + handle acquire_ensure(config::UserType user) + requires (!kHasPayload && config::kHasUser) + { + auto opt = acquire(user); + ASL_ASSERT_RELEASE(opt.has_value()); + return opt.value(); + } + + option<handle> acquire(config::UserType user, const Payload& payload) + requires (kHasPayload && config::kHasUser) + { + return acquire_handle(payload).transform([user](internal_handle h) + { + return handle(h.index(), h.gen(), user); + }); + } + + handle acquire_ensure(config::UserType user, const Payload& payload) + requires (kHasPayload && config::kHasUser) + { + auto opt = acquire(user, 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 = internal_handle(h.index(), next_gen, 0); + } + else + { + slot->is_end_of_list = false; + slot->handle = internal_handle(m_first_available.index(), next_gen, 0); + } + + m_first_available = internal_handle(h.index(), 0, 0); + } + } + + bool is_valid(handle h) const + { + return get_slot_if_valid(h) != nullptr; + } + + const Payload* get_payload(handle h) const + { + if (const Slot* slot = get_slot_if_valid(h); slot != nullptr) + { + return &slot->payload; + } + return nullptr; + } + + option<Payload> exchange_payload(handle h, Payload new_payload) + { + if (Slot* slot = get_slot_if_valid(h); slot != nullptr) + { + return asl::exchange(slot->payload, new_payload); + } + return nullopt; + } }; } // namespace asl |