diff options
| -rw-r--r-- | MODULE.bazel.lock | 14 | ||||
| -rw-r--r-- | asl/handle_pool/BUILD.bazel | 23 | ||||
| -rw-r--r-- | asl/handle_pool/dense_handle_pool.hpp | 162 | ||||
| -rw-r--r-- | asl/handle_pool/dense_handle_pool_tests.cpp | 117 |
4 files changed, 309 insertions, 7 deletions
diff --git a/MODULE.bazel.lock b/MODULE.bazel.lock index 55c4990..9fb4fd8 100644 --- a/MODULE.bazel.lock +++ b/MODULE.bazel.lock @@ -20,7 +20,8 @@ "https://bcr.bazel.build/modules/bazel_features/1.18.0/MODULE.bazel": "1be0ae2557ab3a72a57aeb31b29be347bcdc5d2b1eb1e70f39e3851a7e97041a", "https://bcr.bazel.build/modules/bazel_features/1.19.0/MODULE.bazel": "59adcdf28230d220f0067b1f435b8537dd033bfff8db21335ef9217919c7fb58", "https://bcr.bazel.build/modules/bazel_features/1.21.0/MODULE.bazel": "675642261665d8eea09989aa3b8afb5c37627f1be178382c320d1b46afba5e3b", - "https://bcr.bazel.build/modules/bazel_features/1.21.0/source.json": "3e8379efaaef53ce35b7b8ba419df829315a880cb0a030e5bb45c96d6d5ecb5f", + "https://bcr.bazel.build/modules/bazel_features/1.30.0/MODULE.bazel": "a14b62d05969a293b80257e72e597c2da7f717e1e69fa8b339703ed6731bec87", + "https://bcr.bazel.build/modules/bazel_features/1.30.0/source.json": "b07e17f067fe4f69f90b03b36ef1e08fe0d1f3cac254c1241a1818773e3423bc", "https://bcr.bazel.build/modules/bazel_features/1.4.1/MODULE.bazel": "e45b6bb2350aff3e442ae1111c555e27eac1d915e77775f6fdc4b351b758b5d7", "https://bcr.bazel.build/modules/bazel_features/1.9.1/MODULE.bazel": "8f679097876a9b609ad1f60249c49d68bfab783dd9be012faf9d82547b14815a", "https://bcr.bazel.build/modules/bazel_skylib/1.0.3/MODULE.bazel": "bcb0fd896384802d1ad283b4e4eb4d718eebd8cb820b0a2c3a347fb971afd9d8", @@ -74,7 +75,6 @@ "https://bcr.bazel.build/modules/rules_cc/0.0.14/MODULE.bazel": "5e343a3aac88b8d7af3b1b6d2093b55c347b8eefc2e7d1442f7a02dc8fea48ac", "https://bcr.bazel.build/modules/rules_cc/0.0.15/MODULE.bazel": "6704c35f7b4a72502ee81f61bf88706b54f06b3cbe5558ac17e2e14666cd5dcc", "https://bcr.bazel.build/modules/rules_cc/0.0.16/MODULE.bazel": "7661303b8fc1b4d7f532e54e9d6565771fea666fbdf839e0a86affcd02defe87", - "https://bcr.bazel.build/modules/rules_cc/0.0.17/MODULE.bazel": "2ae1d8f4238ec67d7185d8861cb0a2cdf4bc608697c331b95bf990e69b62e64a", "https://bcr.bazel.build/modules/rules_cc/0.0.2/MODULE.bazel": "6915987c90970493ab97393024c156ea8fb9f3bea953b2f3ec05c34f19b5695c", "https://bcr.bazel.build/modules/rules_cc/0.0.6/MODULE.bazel": "abf360251023dfe3efcef65ab9d56beefa8394d4176dd29529750e1c57eaa33f", "https://bcr.bazel.build/modules/rules_cc/0.0.8/MODULE.bazel": "964c85c82cfeb6f3855e6a07054fdb159aced38e99a5eecf7bce9d53990afa3e", @@ -94,8 +94,8 @@ "https://bcr.bazel.build/modules/rules_java/7.2.0/MODULE.bazel": "06c0334c9be61e6cef2c8c84a7800cef502063269a5af25ceb100b192453d4ab", "https://bcr.bazel.build/modules/rules_java/7.3.2/MODULE.bazel": "50dece891cfdf1741ea230d001aa9c14398062f2b7c066470accace78e412bc2", "https://bcr.bazel.build/modules/rules_java/7.6.1/MODULE.bazel": "2f14b7e8a1aa2f67ae92bc69d1ec0fa8d9f827c4e17ff5e5f02e91caa3b2d0fe", - "https://bcr.bazel.build/modules/rules_java/8.11.0/MODULE.bazel": "c3d280bc5ff1038dcb3bacb95d3f6b83da8dd27bba57820ec89ea4085da767ad", - "https://bcr.bazel.build/modules/rules_java/8.11.0/source.json": "302b52a39259a85aa06ca3addb9787864ca3e03b432a5f964ea68244397e7544", + "https://bcr.bazel.build/modules/rules_java/8.12.0/MODULE.bazel": "8e6590b961f2defdfc2811c089c75716cb2f06c8a4edeb9a8d85eaa64ee2a761", + "https://bcr.bazel.build/modules/rules_java/8.12.0/source.json": "cbd5d55d9d38d4008a7d00bee5b5a5a4b6031fcd4a56515c9accbcd42c7be2ba", "https://bcr.bazel.build/modules/rules_java/8.3.2/MODULE.bazel": "7336d5511ad5af0b8615fdc7477535a2e4e723a357b6713af439fe8cf0195017", "https://bcr.bazel.build/modules/rules_java/8.5.1/MODULE.bazel": "d8a9e38cc5228881f7055a6079f6f7821a073df3744d441978e7a43e20226939", "https://bcr.bazel.build/modules/rules_jvm_external/4.4.2/MODULE.bazel": "a56b85e418c83eb1839819f0b515c431010160383306d13ec21959ac412d2fe7", @@ -140,15 +140,15 @@ "https://bcr.bazel.build/modules/stardoc/0.7.2/source.json": "58b029e5e901d6802967754adf0a9056747e8176f017cfe3607c0851f4d42216", "https://bcr.bazel.build/modules/upb/0.0.0-20220923-a547704/MODULE.bazel": "7298990c00040a0e2f121f6c32544bab27d4452f80d9ce51349b1a28f3005c43", "https://bcr.bazel.build/modules/zlib/1.2.11/MODULE.bazel": "07b389abc85fdbca459b69e2ec656ae5622873af3f845e1c9d80fe179f3effa0", - "https://bcr.bazel.build/modules/zlib/1.3.1.bcr.3/MODULE.bazel": "af322bc08976524477c79d1e45e241b6efbeb918c497e8840b8ab116802dda79", - "https://bcr.bazel.build/modules/zlib/1.3.1.bcr.3/source.json": "2be409ac3c7601245958cd4fcdff4288be79ed23bd690b4b951f500d54ee6e7d", + "https://bcr.bazel.build/modules/zlib/1.3.1.bcr.5/MODULE.bazel": "eec517b5bbe5492629466e11dae908d043364302283de25581e3eb944326c4ca", + "https://bcr.bazel.build/modules/zlib/1.3.1.bcr.5/source.json": "22bc55c47af97246cfc093d0acf683a7869377de362b5d1c552c2c2e16b7a806", "https://bcr.bazel.build/modules/zlib/1.3.1/MODULE.bazel": "751c9940dcfe869f5f7274e1295422a34623555916eb98c174c1e945594bf198" }, "selectedYankedVersions": {}, "moduleExtensions": { "@@rules_kotlin+//src/main/starlark/core/repositories:bzlmod_setup.bzl%rules_kotlin_extensions": { "general": { - "bzlTransitiveDigest": "sFhcgPbDQehmbD1EOXzX4H1q/CD5df8zwG4kp4jbvr8=", + "bzlTransitiveDigest": "hUTp2w+RUVdL7ma5esCXZJAFnX7vLbVfLd7FwnQI6bU=", "usagesDigest": "QI2z8ZUR+mqtbwsf2fLqYdJAkPOHdOV+tF2yVAUgRzw=", "recordedFileInputs": {}, "recordedDirentsInputs": {}, diff --git a/asl/handle_pool/BUILD.bazel b/asl/handle_pool/BUILD.bazel index bdaa711..08a41a9 100644 --- a/asl/handle_pool/BUILD.bazel +++ b/asl/handle_pool/BUILD.bazel @@ -21,6 +21,17 @@ cc_library( visibility = ["//visibility:public"], ) +cc_library( + name = "dense_handle_pool", + hdrs = [ + "dense_handle_pool.hpp", + ], + deps = [ + ":index_pool", + ], + visibility = ["//visibility:public"], +) + cc_test( name = "index_pool_tests", srcs = [ @@ -33,3 +44,15 @@ cc_test( "//asl/testing", ], ) + +cc_test( + name = "dense_handle_pool_tests", + srcs = [ + "dense_handle_pool_tests.cpp", + ], + deps = [ + ":dense_handle_pool", + "//asl/tests:utils", + "//asl/testing", + ], +) diff --git a/asl/handle_pool/dense_handle_pool.hpp b/asl/handle_pool/dense_handle_pool.hpp new file mode 100644 index 0000000..34cd04f --- /dev/null +++ b/asl/handle_pool/dense_handle_pool.hpp @@ -0,0 +1,162 @@ +// Copyright 2025 Steven Le Rouzic +// +// SPDX-License-Identifier: BSD-3-Clause + +#pragma once + +#include "asl/handle_pool/index_pool.hpp" +#include "asl/memory/allocator.hpp" +#include "asl/containers/chunked_buffer.hpp" + + +namespace asl +{ + +// @Todo If we want the allocator to be non-copyable, we could +// introduce a reference allocator type that is copyable, and store +// the "main" allocator in the pool. + +template< + is_object T, + int kIndexBits, + int kGenBits, + typename UserType = empty, + int kUserBits = 0, + isize_t kChunkSize = 32, + allocator Allocator = DefaultAllocator> +requires moveable<T> && copyable<Allocator> +class DenseHandlePool +{ + using ThisIndexPool = IndexPool<kIndexBits, kGenBits, UserType, kUserBits, isize_t, Allocator>; + + struct Slot + { + ThisIndexPool::handle h; + T obj; + + template<typename... Args> + explicit Slot(ThisIndexPool::handle h, Args&&... args) + : h{h} + , obj(std::forward<Args>(args)...) + {} + }; + + using Buffer = chunked_buffer<Slot, kChunkSize, Allocator>; + + ThisIndexPool m_index_pool{}; + Buffer m_buffer{}; + + using config = ThisIndexPool::handle::config; + + template<typename... Args> + isize_t push(Args&&... args) + requires constructible_from<T, Args&&...> + { + m_buffer.push(typename ThisIndexPool::handle{}, std::forward<Args>(args)...); + return m_buffer.size() - 1; + } + +public: + using handle = ThisIndexPool::handle; + + DenseHandlePool() requires default_constructible<Allocator> = default; + + explicit DenseHandlePool(const Allocator& allocator) + : m_index_pool(allocator) + , m_buffer(allocator) + {} + + ASL_DELETE_COPY(DenseHandlePool); + ASL_DEFAULT_MOVE(DenseHandlePool); + ~DenseHandlePool() = default; + + [[nodiscard]] bool is_full() const + { + return m_index_pool.is_full(); + } + + bool is_valid(handle h) const + { + return m_index_pool.is_valid(h); + } + + template<typename... Args> + option<handle> acquire(config::UserType user, Args&&... args) + requires config::kHasUser && constructible_from<T, Args&&...> + { + if (is_full()) { return nullopt; } + const isize_t obj_index = push(std::forward<Args>(args)...); + const auto handle = m_index_pool.acquire_ensure(user, obj_index); + m_buffer[obj_index].h = handle; + return handle; + } + + template<typename... Args> + option<handle> acquire(Args&&... args) + requires (!config::kHasUser) && constructible_from<T, Args&&...> + { + if (is_full()) { return nullopt; } + const isize_t obj_index = push(std::forward<Args>(args)...); + const auto handle = m_index_pool.acquire_ensure(obj_index); + m_buffer[obj_index].h = handle; + return handle; + } + + template<typename... Args> + handle acquire_ensure(config::UserType user, Args&&... args) + requires config::kHasUser && constructible_from<T, Args&&...> + { + ASL_ASSERT_RELEASE(!is_full()); + const isize_t obj_index = push(std::forward<Args>(args)...); + const auto handle = m_index_pool.acquire_ensure(user, obj_index); + m_buffer[obj_index].h = handle; + return handle; + } + + template<typename... Args> + handle acquire_ensure(Args&&... args) + requires (!config::kHasUser) && constructible_from<T, Args&&...> + { + ASL_ASSERT_RELEASE(!is_full()); + const isize_t obj_index = push(std::forward<Args>(args)...); + const auto handle = m_index_pool.acquire_ensure(obj_index); + m_buffer[obj_index].h = handle; + return handle; + } + + void release(handle to_release_handle) + { + if (!is_valid(to_release_handle)) { return; } + + const auto to_release_index = *m_index_pool.get_payload(to_release_handle); + if (to_release_index < m_buffer.size() - 1) + { + const auto to_swap_index = m_buffer.size() - 1; + const auto to_swap_handle = m_buffer[to_swap_index].h; + + m_buffer[to_release_index] = std::move(m_buffer[to_swap_index]); + m_index_pool.exchange_payload(to_swap_handle, to_release_index); + } + + m_buffer.pop(); + m_index_pool.release(to_release_handle); + } + + auto get(this auto&& self, handle h) + -> copy_const_t<un_ref_t<decltype(self)>, T>* + { + if (!self.is_valid(h)) { return nullptr; } + const auto index = *self.m_index_pool.get_payload(h); + return &self.m_buffer[index].obj; + } + + auto get_ensure(this auto&& self, handle h) + -> copy_cref_t<decltype(self), T> + { + ASL_ASSERT_RELEASE(self.is_valid(h)); + const auto index = *self.m_index_pool.get_payload(h); + return std::forward<decltype(self)>(self).m_buffer[index].obj; + } +}; + +} // namespace asl diff --git a/asl/handle_pool/dense_handle_pool_tests.cpp b/asl/handle_pool/dense_handle_pool_tests.cpp new file mode 100644 index 0000000..a98d1d8 --- /dev/null +++ b/asl/handle_pool/dense_handle_pool_tests.cpp @@ -0,0 +1,117 @@ +// Copyright 2025 Steven Le Rouzic +// +// SPDX-License-Identifier: BSD-3-Clause + +#include "asl/testing/testing.hpp" +#include "asl/tests/types.hpp" +#include "asl/handle_pool/dense_handle_pool.hpp" + +ASL_TEST(acquire_release) // NOLINT +{ + asl::DenseHandlePool<int, 1, 1> pool; + + ASL_TEST_EXPECT(!pool.is_full()); + + const auto a = pool.acquire_ensure(6); + const auto b = pool.acquire_ensure(7); + + ASL_TEST_EXPECT(pool.is_valid(a)); + ASL_TEST_EXPECT(pool.is_valid(b)); + ASL_TEST_EXPECT(pool.is_full()); + + ASL_TEST_EXPECT(pool.get_ensure(a) == 6); + ASL_TEST_EXPECT(pool.get_ensure(b) == 7); + + pool.release(a); + ASL_TEST_EXPECT(!pool.is_valid(a)); + ASL_TEST_EXPECT(pool.is_valid(b)); + ASL_TEST_EXPECT(!pool.is_full()); + ASL_TEST_EXPECT(pool.get(a) == nullptr); + ASL_TEST_EXPECT(*pool.get(b) == 7); + + const auto c = pool.acquire_ensure(8); + + ASL_TEST_EXPECT(!pool.is_valid(a)); + ASL_TEST_EXPECT(pool.is_valid(b)); + ASL_TEST_EXPECT(pool.is_valid(c)); + ASL_TEST_EXPECT(pool.is_full()); + + ASL_TEST_EXPECT(*pool.get(b) == 7); + ASL_TEST_EXPECT(*pool.get(c) == 8); + ASL_TEST_EXPECT(pool.get(a) == nullptr); +} + +ASL_TEST(element_destructor) +{ + asl::DenseHandlePool<DestructorObserver, 8, 8> pool; + bool d[3]{}; + + const auto d0 = pool.acquire_ensure(&d[0]); + const auto d1 = pool.acquire_ensure(&d[1]); + const auto d2 = pool.acquire_ensure(&d[2]); + + ASL_TEST_EXPECT(!d[0]); + ASL_TEST_EXPECT(!d[1]); + ASL_TEST_EXPECT(!d[2]); + + pool.release(d1); + ASL_TEST_EXPECT(!d[0]); + ASL_TEST_EXPECT(d[1]); + ASL_TEST_EXPECT(!d[2]); + + pool.release(d0); + ASL_TEST_EXPECT(d[0]); + ASL_TEST_EXPECT(d[1]); + ASL_TEST_EXPECT(!d[2]); + + pool.release(d2); + ASL_TEST_EXPECT(d[0]); + ASL_TEST_EXPECT(d[1]); + ASL_TEST_EXPECT(d[2]); +} + +ASL_TEST(destructor) +{ + bool d[3]{}; + + { + asl::DenseHandlePool<DestructorObserver, 8, 8> pool; + + pool.acquire_ensure(&d[0]); + const auto d1 = pool.acquire_ensure(&d[1]); + pool.acquire_ensure(&d[2]); + + ASL_TEST_EXPECT(!d[0]); + ASL_TEST_EXPECT(!d[1]); + ASL_TEST_EXPECT(!d[2]); + + pool.release(d1); + ASL_TEST_EXPECT(!d[0]); + ASL_TEST_EXPECT(d[1]); + ASL_TEST_EXPECT(!d[2]); + } + + ASL_TEST_EXPECT(d[0]); + ASL_TEST_EXPECT(d[1]); + ASL_TEST_EXPECT(d[2]); +} + +enum Flags : uint8_t +{ + kFlag1 = 1, + kFlag2 = 2, +}; + +ASL_TEST(user_type) +{ + asl::DenseHandlePool<int, 8, 8, Flags> pool; + + auto a = pool.acquire_ensure(kFlag2, 22); + auto b = pool.acquire_ensure(kFlag1, 11); + + ASL_TEST_EXPECT(pool.get_ensure(a) == 22); + ASL_TEST_EXPECT(pool.get_ensure(b) == 11); + + ASL_TEST_EXPECT(a.user() == kFlag2); + ASL_TEST_EXPECT(b.user() == kFlag1); +} |