summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--asl/handle_pool/BUILD.bazel2
-rw-r--r--asl/handle_pool/index_pool.hpp196
-rw-r--r--asl/handle_pool/index_pool_tests.cpp162
3 files changed, 349 insertions, 11 deletions
diff --git a/asl/handle_pool/BUILD.bazel b/asl/handle_pool/BUILD.bazel
index e5048d3..bdaa711 100644
--- a/asl/handle_pool/BUILD.bazel
+++ b/asl/handle_pool/BUILD.bazel
@@ -16,6 +16,7 @@ cc_library(
"//asl/memory:allocator",
"//asl/base",
"//asl/containers:chunked_buffer",
+ "//asl/types:option",
],
visibility = ["//visibility:public"],
)
@@ -27,6 +28,7 @@ cc_test(
],
deps = [
":index_pool",
+ "//asl/hashing",
"//asl/tests:utils",
"//asl/testing",
],
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
diff --git a/asl/handle_pool/index_pool_tests.cpp b/asl/handle_pool/index_pool_tests.cpp
index 3156320..329fb4c 100644
--- a/asl/handle_pool/index_pool_tests.cpp
+++ b/asl/handle_pool/index_pool_tests.cpp
@@ -4,6 +4,7 @@
#include "asl/testing/testing.hpp"
#include "asl/handle_pool/index_pool.hpp"
+#include "asl/hashing/hash.hpp"
enum Flags: uint8_t {
kFlag0 = 0,
@@ -19,6 +20,8 @@ static_assert(Cfg1::kValidMask == uint8_t{0x80});
static_assert(Cfg1::kIndexMask == uint8_t{0x0f});
static_assert(Cfg1::kGenMask == uint8_t{0x70});
static_assert(Cfg1::kGenShift == 4);
+static_assert(Cfg1::kMaxGen == 7);
+static_assert(Cfg1::kMaxIndex == 15);
using Cfg2 = asl::index_pool_config<5, 5, Flags>;
static_assert(Cfg2::kHasUser);
@@ -31,6 +34,8 @@ static_assert(Cfg2::kGenMask == uint32_t{0x0000'03e0});
static_assert(Cfg2::kUserMask == uint32_t{0x0003'fc00});
static_assert(Cfg2::kGenShift == 5);
static_assert(Cfg2::kUserShift == 10);
+static_assert(Cfg2::kMaxGen == 31);
+static_assert(Cfg2::kMaxIndex == 31);
using Cfg3 = asl::index_pool_config<5, 6, Flags, 4>;
static_assert(Cfg3::kHasUser);
@@ -43,6 +48,8 @@ static_assert(Cfg3::kGenMask == uint16_t{0x07e0});
static_assert(Cfg3::kUserMask == uint16_t{0x7800});
static_assert(Cfg3::kGenShift == 5);
static_assert(Cfg3::kUserShift == 11);
+static_assert(Cfg3::kMaxGen == 63);
+static_assert(Cfg3::kMaxIndex == 31);
static_assert(asl::default_constructible<asl::index_pool_handle<5, 5, uint8_t>>);
static_assert(asl::trivially_copy_constructible<asl::index_pool_handle<5, 5, uint8_t>>);
@@ -51,16 +58,25 @@ static_assert(asl::trivially_copy_assignable<asl::index_pool_handle<5, 5, uint8_
static_assert(asl::trivially_move_assignable<asl::index_pool_handle<5, 5, uint8_t>>);
static_assert(asl::trivially_destructible<asl::index_pool_handle<5, 5, uint8_t>>);
+static_assert(asl::hashable<asl::index_pool_handle<5, 5, uint8_t>>);
+static_assert(asl::has_niche<asl::index_pool_handle<5, 5, uint8_t>>);
+
ASL_TEST(default_is_invalid)
{
const asl::index_pool_handle<5, 5, uint8_t> idx;
- ASL_TEST_EXPECT(!idx.is_valid());
+ ASL_TEST_EXPECT(idx.is_null());
+}
+
+ASL_TEST(niche_is_invalid)
+{
+ const asl::index_pool_handle<5, 5, uint8_t> idx{asl::niche_t{}};
+ ASL_TEST_EXPECT(idx.is_null());
}
ASL_TEST(construct)
{
const asl::index_pool_handle<5, 5> idx(9, 11);
- ASL_TEST_EXPECT(idx.is_valid());
+ ASL_TEST_EXPECT(!idx.is_null());
ASL_TEST_EXPECT(idx.index() == 9);
ASL_TEST_EXPECT(idx.gen() == 11);
}
@@ -68,14 +84,13 @@ ASL_TEST(construct)
ASL_TEST(construct_user)
{
const asl::index_pool_handle<5, 5, Flags, 4> idx(9, 11, kFlag2);
- ASL_TEST_EXPECT(idx.is_valid());
+ ASL_TEST_EXPECT(!idx.is_null());
ASL_TEST_EXPECT(idx.index() == 9);
ASL_TEST_EXPECT(idx.gen() == 11);
ASL_TEST_EXPECT(idx.user() == kFlag2);
static_assert(asl::same_as<Flags, decltype(idx.user())>);
}
-
ASL_TEST(compare) // NOLINT
{
const asl::index_pool_handle<5, 5, Flags, 4> idx_default;
@@ -108,3 +123,142 @@ ASL_TEST(compare) // NOLINT
ASL_TEST_EXPECT(idx4 != idx5);
}
+
+ASL_TEST(hashing) // NOLINT
+{
+ const asl::index_pool_handle<4, 4> idx0(asl::niche_t{});
+ const asl::index_pool_handle<4, 4> idx1{};
+ const asl::index_pool_handle<4, 4> idx2(1, 1);
+ const asl::index_pool_handle<4, 4> idx3(1, 1);
+ const asl::index_pool_handle<4, 4> idx4(2, 1);
+ const asl::index_pool_handle<4, 4> idx5(1, 2);
+
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx1));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx2));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx2));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx2) == asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx2) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx2) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx3) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx3) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx4) != asl::hash_value(idx5));
+}
+
+ASL_TEST(hashing_in_option) // NOLINT
+{
+ const asl::option<asl::index_pool_handle<4, 4>> idx0;
+ const asl::option<asl::index_pool_handle<4, 4>> idx1{asl::index_pool_handle<4, 4>()};
+ const asl::option<asl::index_pool_handle<4, 4>> idx2{asl::index_pool_handle<4, 4>(1, 1)};
+ const asl::option<asl::index_pool_handle<4, 4>> idx3{asl::index_pool_handle<4, 4>(1, 1)};
+ const asl::option<asl::index_pool_handle<4, 4>> idx4{asl::index_pool_handle<4, 4>(2, 1)};
+ const asl::option<asl::index_pool_handle<4, 4>> idx5{asl::index_pool_handle<4, 4>(1, 2)};
+
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx1));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx2));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx0) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx2));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx1) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx2) == asl::hash_value(idx3));
+ ASL_TEST_EXPECT(asl::hash_value(idx2) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx2) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx3) != asl::hash_value(idx4));
+ ASL_TEST_EXPECT(asl::hash_value(idx3) != asl::hash_value(idx5));
+
+ ASL_TEST_EXPECT(asl::hash_value(idx4) != asl::hash_value(idx5));
+}
+
+ASL_TEST(simple_pool) // NOLINT
+{
+ using Pool = asl::IndexPool<8, 8>;
+ Pool pool;
+
+ auto a = pool.acquire_ensure({});
+ auto b = pool.acquire_ensure({});
+
+ ASL_TEST_EXPECT(!a.is_null());
+ ASL_TEST_EXPECT(!b.is_null());
+ ASL_TEST_EXPECT(a.index() == 0);
+ ASL_TEST_EXPECT(b.index() == 1);
+ ASL_TEST_EXPECT(a.gen() == 0);
+ ASL_TEST_EXPECT(b.gen() == 0);
+
+ ASL_TEST_EXPECT(a != b);
+
+ ASL_TEST_EXPECT(pool.is_valid(a));
+ ASL_TEST_EXPECT(pool.is_valid(b));
+
+ pool.release(a);
+
+ ASL_TEST_EXPECT(!pool.is_valid(a));
+ ASL_TEST_EXPECT(pool.is_valid(b));
+
+ auto c = pool.acquire_ensure({});
+
+ ASL_TEST_EXPECT(!c.is_null());
+ ASL_TEST_EXPECT(c.index() == 0);
+ ASL_TEST_EXPECT(c.gen() == 1);
+
+ ASL_TEST_EXPECT(a != c);
+ ASL_TEST_EXPECT(b != c);
+
+ ASL_TEST_EXPECT(!pool.is_valid(a));
+ ASL_TEST_EXPECT(pool.is_valid(b));
+ ASL_TEST_EXPECT(pool.is_valid(c));
+
+ pool.release(b);
+
+ ASL_TEST_EXPECT(!pool.is_valid(a));
+ ASL_TEST_EXPECT(!pool.is_valid(b));
+ ASL_TEST_EXPECT(pool.is_valid(c));
+
+ pool.release(c);
+
+ ASL_TEST_EXPECT(!pool.is_valid(a));
+ ASL_TEST_EXPECT(!pool.is_valid(b));
+ ASL_TEST_EXPECT(!pool.is_valid(c));
+}
+
+ASL_TEST(pool_acquire_release_a_lot)
+{
+ using Pool = asl::IndexPool<3, 3>;
+ Pool pool;
+
+ for (int i = 0; i < 80; ++i)
+ {
+ pool.release(pool.acquire_ensure({}));
+ }
+}
+
+ASL_TEST(pool_acquire_past_capacity)
+{
+ using Pool = asl::IndexPool<3, 3>;
+ Pool pool;
+
+ for (int i = 0; i < 8; ++i)
+ {
+ ASL_TEST_EXPECT(pool.acquire({}).has_value());
+ }
+
+ for (int i = 0; i < 8; ++i)
+ {
+ ASL_TEST_EXPECT(!pool.acquire({}).has_value());
+ }
+}
+
generated by cgit (git 2.34.1) at 2025-06-18 15:38:07 +0000