From a1db1cd9e22e77041d5f1360f1d1ccdc52b86306 Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Mon, 26 May 2025 00:47:54 +0200
Subject: Implement chunked_buffer
---
asl/base/bit_tests.cpp | 4 +
asl/base/meta.hpp | 20 +-
asl/base/numeric.hpp | 17 +-
asl/base/numeric_tests.cpp | 52 +++++
asl/containers/BUILD.bazel | 17 ++
asl/containers/buffer.hpp | 87 +++++--
asl/containers/buffer_tests.cpp | 69 ++----
asl/containers/chunked_buffer.hpp | 399 ++++++++++++++++++++++++++++++++
asl/containers/chunked_buffer_tests.cpp | 335 +++++++++++++++++++++++++++
asl/memory/allocator.hpp | 15 ++
asl/tests/BUILD.bazel | 2 +
asl/tests/counting_allocator.hpp | 48 ++++
asl/types/array.hpp | 8 +-
asl/types/maybe_uninit_tests.cpp | 4 +
14 files changed, 998 insertions(+), 79 deletions(-)
create mode 100644 asl/containers/chunked_buffer.hpp
create mode 100644 asl/containers/chunked_buffer_tests.cpp
create mode 100644 asl/tests/counting_allocator.hpp
(limited to 'asl')
diff --git a/asl/base/bit_tests.cpp b/asl/base/bit_tests.cpp
index fa05fab..972bc72 100644
--- a/asl/base/bit_tests.cpp
+++ b/asl/base/bit_tests.cpp
@@ -39,6 +39,10 @@ ASL_TEST(popcount) // NOLINT(*-cognitive-complexity)
ASL_TEST(countr_zero)
{
ASL_TEST_EXPECT(asl::countr_zero(uint8_t{0}) == 8);
+ ASL_TEST_EXPECT(asl::countr_zero(uint8_t{1}) == 0);
+ ASL_TEST_EXPECT(asl::countr_zero(uint8_t{2}) == 1);
+ ASL_TEST_EXPECT(asl::countr_zero(uint8_t{4}) == 2);
+ ASL_TEST_EXPECT(asl::countr_zero(uint8_t{8}) == 3);
ASL_TEST_EXPECT(asl::countr_zero(uint8_t{255}) == 0);
ASL_TEST_EXPECT(asl::countr_zero(uint8_t{0b00011100}) == 2);
ASL_TEST_EXPECT(asl::countr_zero(uint8_t{0b10101010}) == 1);
diff --git a/asl/base/meta.hpp b/asl/base/meta.hpp
index e050e69..b17d761 100644
--- a/asl/base/meta.hpp
+++ b/asl/base/meta.hpp
@@ -249,28 +249,32 @@ template<> struct _integer_traits<uint8_t>
{
static constexpr bool kSigned = false;
static constexpr bool kUnsigned = true;
- using as_signed = int8_t;
+ using as_signed = int8_t;
+ using as_unsigned = uint8_t;
};
template<> struct _integer_traits<uint16_t>
{
static constexpr bool kSigned = false;
static constexpr bool kUnsigned = true;
- using as_signed = int16_t;
+ using as_signed = int16_t;
+ using as_unsigned = uint16_t;
};
template<> struct _integer_traits<uint32_t>
{
static constexpr bool kSigned = false;
static constexpr bool kUnsigned = true;
- using as_signed = int32_t;
+ using as_signed = int32_t;
+ using as_unsigned = uint32_t;
};
template<> struct _integer_traits<uint64_t>
{
static constexpr bool kSigned = false;
static constexpr bool kUnsigned = true;
- using as_signed = int64_t;
+ using as_signed = int64_t;
+ using as_unsigned = uint64_t;
};
template<> struct _integer_traits<int8_t>
@@ -278,6 +282,7 @@ template<> struct _integer_traits<int8_t>
static constexpr bool kSigned = true;
static constexpr bool kUnsigned = false;
using as_unsigned = uint8_t;
+ using as_signed = int8_t;
};
template<> struct _integer_traits<int16_t>
@@ -285,6 +290,7 @@ template<> struct _integer_traits<int16_t>
static constexpr bool kSigned = true;
static constexpr bool kUnsigned = false;
using as_unsigned = uint16_t;
+ using as_signed = int16_t;
};
template<> struct _integer_traits<int32_t>
@@ -292,6 +298,7 @@ template<> struct _integer_traits<int32_t>
static constexpr bool kSigned = true;
static constexpr bool kUnsigned = false;
using as_unsigned = uint32_t;
+ using as_signed = int32_t;
};
template<> struct _integer_traits<int64_t>
@@ -299,6 +306,7 @@ template<> struct _integer_traits<int64_t>
static constexpr bool kSigned = true;
static constexpr bool kUnsigned = false;
using as_unsigned = uint64_t;
+ using as_signed = int64_t;
};
template<typename T> concept is_signed_integer = _integer_traits<T>::kSigned;
@@ -306,8 +314,8 @@ template<typename T> concept is_unsigned_integer = _integer_traits<T>::kUnsigned
template<typename T> concept is_integer = is_signed_integer<T> || is_unsigned_integer<T>;
-template<is_signed_integer T> using as_unsigned_integer = _integer_traits<T>::as_unsigned;
-template<is_unsigned_integer T> using as_signed_integer = _integer_traits<T>::as_signed;
+template<is_integer T> using as_unsigned_integer = _integer_traits<T>::as_unsigned;
+template<is_integer T> using as_signed_integer = _integer_traits<T>::as_signed;
template<typename T> concept is_enum = __is_enum(T);
diff --git a/asl/base/numeric.hpp b/asl/base/numeric.hpp
index bbd229d..8d3b8ef 100644
--- a/asl/base/numeric.hpp
+++ b/asl/base/numeric.hpp
@@ -7,6 +7,7 @@
#include "asl/base/integers.hpp"
#include "asl/base/bit.hpp"
#include "asl/base/meta.hpp"
+#include "asl/base/assert.hpp"
namespace asl
{
@@ -14,10 +15,24 @@ namespace asl
template<is_integer T>
constexpr bool is_pow2(T x)
{
- using unsigned_type = select_t<is_unsigned_integer<T>, T, as_unsigned_integer<T>>;
+ using unsigned_type = as_unsigned_integer<T>;
return x > 0 && has_single_bit(static_cast<unsigned_type>(x));
}
+template<is_integer T>
+constexpr T round_down_pow2(T x, T div)
+{
+ ASL_ASSERT(is_pow2(div));
+ return x & (-div);
+}
+
+template<is_integer T>
+constexpr T round_up_pow2(T x, T div)
+{
+ ASL_ASSERT(is_pow2(div));
+ return (x + (div - 1)) & (-div);
+}
+
template<typename T>
concept is_numeric = is_integer<T> || is_floating_point<T>;
diff --git a/asl/base/numeric_tests.cpp b/asl/base/numeric_tests.cpp
index cfbc1ac..afcc12a 100644
--- a/asl/base/numeric_tests.cpp
+++ b/asl/base/numeric_tests.cpp
@@ -13,4 +13,56 @@ ASL_TEST(is_pow2)
ASL_TEST_EXPECT(!asl::is_pow2(6));
ASL_TEST_EXPECT(!asl::is_pow2(1978));
ASL_TEST_EXPECT(!asl::is_pow2(0));
+ ASL_TEST_EXPECT(asl::is_pow2(4U));
+ ASL_TEST_EXPECT(asl::is_pow2(uint64_t{65536}));
+}
+
+ASL_TEST(round_down_pow2) // NOLINT
+{
+ ASL_TEST_EXPECT(asl::round_down_pow2(0, 1) == 0);
+ ASL_TEST_EXPECT(asl::round_down_pow2(1, 1) == 1);
+ ASL_TEST_EXPECT(asl::round_down_pow2(2, 1) == 2);
+ ASL_TEST_EXPECT(asl::round_down_pow2(3, 1) == 3);
+ ASL_TEST_EXPECT(asl::round_down_pow2(-1, 1) == -1);
+ ASL_TEST_EXPECT(asl::round_down_pow2(-2, 1) == -2);
+ ASL_TEST_EXPECT(asl::round_down_pow2(-3, 1) == -3);
+
+ ASL_TEST_EXPECT(asl::round_down_pow2(0U, 1U) == 0U);
+ ASL_TEST_EXPECT(asl::round_down_pow2(1U, 1U) == 1U);
+ ASL_TEST_EXPECT(asl::round_down_pow2(2U, 1U) == 2U);
+ ASL_TEST_EXPECT(asl::round_down_pow2(3U, 1U) == 3U);
+
+ ASL_TEST_EXPECT(asl::round_down_pow2(0, 16) == 0);
+ ASL_TEST_EXPECT(asl::round_down_pow2(1, 16) == 0);
+ ASL_TEST_EXPECT(asl::round_down_pow2(8, 16) == 0);
+ ASL_TEST_EXPECT(asl::round_down_pow2(15, 16) == 0);
+ ASL_TEST_EXPECT(asl::round_down_pow2(16, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_down_pow2(17, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_down_pow2(255, 16) == 240);
+ ASL_TEST_EXPECT(asl::round_down_pow2(-255, 16) == -256);
+}
+
+ASL_TEST(round_up_pow2) // NOLINT
+{
+ ASL_TEST_EXPECT(asl::round_up_pow2(0, 1) == 0);
+ ASL_TEST_EXPECT(asl::round_up_pow2(1, 1) == 1);
+ ASL_TEST_EXPECT(asl::round_up_pow2(2, 1) == 2);
+ ASL_TEST_EXPECT(asl::round_up_pow2(3, 1) == 3);
+ ASL_TEST_EXPECT(asl::round_up_pow2(-1, 1) == -1);
+ ASL_TEST_EXPECT(asl::round_up_pow2(-2, 1) == -2);
+ ASL_TEST_EXPECT(asl::round_up_pow2(-3, 1) == -3);
+
+ ASL_TEST_EXPECT(asl::round_up_pow2(0U, 1U) == 0U);
+ ASL_TEST_EXPECT(asl::round_up_pow2(1U, 1U) == 1U);
+ ASL_TEST_EXPECT(asl::round_up_pow2(2U, 1U) == 2U);
+ ASL_TEST_EXPECT(asl::round_up_pow2(3U, 1U) == 3U);
+
+ ASL_TEST_EXPECT(asl::round_up_pow2(0, 16) == 0);
+ ASL_TEST_EXPECT(asl::round_up_pow2(1, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_up_pow2(8, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_up_pow2(15, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_up_pow2(16, 16) == 16);
+ ASL_TEST_EXPECT(asl::round_up_pow2(17, 16) == 32);
+ ASL_TEST_EXPECT(asl::round_up_pow2(255, 16) == 256);
+ ASL_TEST_EXPECT(asl::round_up_pow2(-255, 16) == -240);
}
diff --git a/asl/containers/BUILD.bazel b/asl/containers/BUILD.bazel
index ba9c6f1..d27aedc 100644
--- a/asl/containers/BUILD.bazel
+++ b/asl/containers/BUILD.bazel
@@ -21,6 +21,22 @@ cc_library(
visibility = ["//visibility:public"],
)
+cc_library(
+ name = "chunked_buffer",
+ hdrs = [
+ "chunked_buffer.hpp",
+ ],
+ deps = [
+ "//asl/memory",
+ "//asl/memory:allocator",
+ "//asl/base",
+ "//asl/containers:buffer",
+ "//asl/types:array",
+ "//asl/types:maybe_uninit",
+ ],
+ visibility = ["//visibility:public"],
+)
+
cc_library(
name = "hash_set",
hdrs = [
@@ -75,6 +91,7 @@ cc_library(
],
) for name in [
"buffer",
+ "chunked_buffer",
"hash_map",
"hash_set",
"intrusive_list",
diff --git a/asl/containers/buffer.hpp b/asl/containers/buffer.hpp
index f554218..43339ca 100644
--- a/asl/containers/buffer.hpp
+++ b/asl/containers/buffer.hpp
@@ -91,7 +91,7 @@ private:
return is_on_heap(load_size_encoded());
}
- constexpr T* push_uninit()
+ constexpr void* push_uninit()
{
const isize_t sz = size();
resize_uninit_inner(sz + 1);
@@ -100,10 +100,13 @@ private:
constexpr void resize_uninit_inner(isize_t new_size)
{
- const isize_t old_size = size();
- if (!trivially_destructible<T> && new_size < old_size)
+ if constexpr (!trivially_destructible<T>)
{
- destroy_n(data() + new_size, old_size - new_size);
+ const isize_t old_size = size();
+ if (new_size < old_size)
+ {
+ destroy_n(data() + new_size, old_size - new_size);
+ }
}
reserve_capacity(new_size);
set_size(new_size);
@@ -136,18 +139,26 @@ private:
{
if (other.is_on_heap())
{
+ // If the other in on heap, destroy here and adopt their
+ // data. We'll soon adopt the allocator as well.
destroy();
m_data = other.m_data;
m_capacity = other.m_capacity;
store_size_encoded(other.load_size_encoded());
}
- else if (trivially_move_constructible<T>)
- {
- destroy();
- asl::memcpy(this, &other, kInlineRegionSize);
- }
else if (!assign || m_allocator == other.m_allocator)
{
+ // If allocators are compatible, we can move other's inline
+ // data here, even if it's on heap here, because that
+ // memory can be freed by other's allocator, which we will
+ // soon adopt.
+ //
+ // @Note There is an argument to be made for not doing this and
+ // instead destroying our data here and moving into inline
+ // storage, which frees one allocation. But also this avoids
+ // freeing. So I don't know.
+ // Maybe If this storage is much much larger than the inline
+ // data, it's worth freeing.
const isize_t other_n = other.size();
const isize_t this_n = size();
resize_uninit_inner(other_n);
@@ -163,11 +174,28 @@ private:
}
else
{
+ // Otherwise, if we have to free, because the allocators are
+ // not compatible, well we free and move into our inline
+ // storage region.
+ // There is an optimization here when the data is trivially
+ // move constructible (which implies trivially destructible),
+ // we copy the whole inline region, which includes the size.
+ // Very magic.
+
destroy();
- const isize_t n = other.size();
- ASL_ASSERT(n <= kInlineCapacity);
- relocate_uninit_n(data(), other.data(), n);
- set_size_inline(n);
+ if constexpr (trivially_move_constructible<T>)
+ {
+ ASL_ASSERT(!is_on_heap());
+ asl::memcpy(this, &other, kInlineRegionSize);
+ }
+ else
+ {
+ const isize_t n = other.size();
+ ASL_ASSERT(n <= kInlineCapacity);
+ resize_uninit_inner(n);
+ ASL_ASSERT(!is_on_heap());
+ relocate_uninit_n(data(), other.data(), n);
+ }
}
other.set_size_inline(0);
@@ -270,6 +298,14 @@ public:
destroy();
}
+ constexpr Allocator allocator_copy() const
+ requires copy_constructible<Allocator>
+ {
+ return m_allocator;
+ }
+
+ constexpr Allocator& allocator() { return m_allocator; }
+
[[nodiscard]] constexpr isize_t size() const
{
return decode_size(load_size_encoded());
@@ -315,7 +351,6 @@ public:
void reserve_capacity(isize_t new_capacity)
{
ASL_ASSERT(new_capacity >= 0);
- ASL_ASSERT_RELEASE(new_capacity <= 0x4000'0000'0000'0000);
if (new_capacity <= capacity()) { return; }
ASL_ASSERT(new_capacity > kInlineCapacity);
@@ -352,17 +387,16 @@ public:
}
constexpr void resize_uninit(isize_t new_size)
- requires trivially_default_constructible<T> && trivially_destructible<T>
+ requires trivially_default_constructible<T>
{
- reserve_capacity(new_size);
- set_size(new_size);
+ resize_uninit_inner(new_size);
}
constexpr void resize_zero(isize_t new_size)
- requires trivially_default_constructible<T> && trivially_destructible<T>
+ requires trivially_default_constructible<T>
{
const isize_t old_size = size();
- resize_uninit(new_size);
+ resize_uninit_inner(new_size);
if (new_size > old_size)
{
@@ -373,7 +407,14 @@ public:
void resize(isize_t new_size)
requires default_constructible<T>
{
- resize_inner(new_size);
+ if constexpr (trivially_default_constructible<T>)
+ {
+ resize_zero(new_size);
+ }
+ else
+ {
+ resize_inner(new_size);
+ }
}
void resize(isize_t new_size, const T& value)
@@ -384,14 +425,14 @@ public:
constexpr T& push(auto&&... args)
requires constructible_from<T, decltype(args)&&...>
{
- T* uninit = push_uninit();
+ void* uninit = push_uninit();
T* init = construct_at<T>(uninit, std::forward<decltype(args)>(args)...);
return *init;
}
auto data(this auto&& self)
{
- using return_type = copy_const_t<un_ref_t<decltype(self)>, T>*;
+ using return_type = as_ptr_t<copy_const_t<un_ref_t<decltype(self)>, T>>;
// NOLINTNEXTLINE(*-reinterpret-cast)
auto&& buffer = reinterpret_cast<copy_cref_t<decltype(self), class buffer>>(self);
if constexpr (kInlineCapacity == 0)
@@ -437,7 +478,7 @@ public:
constexpr auto&& operator[](this auto&& self, isize_t i)
{
- ASL_ASSERT(i >= 0 && i <= self.size());
+ ASL_ASSERT(i >= 0 && i < self.size());
return std::forward_like<decltype(self)>(std::forward<decltype(self)>(self).data()[i]);
}
diff --git a/asl/containers/buffer_tests.cpp b/asl/containers/buffer_tests.cpp
index eb95ffe..dbb8fa9 100644
--- a/asl/containers/buffer_tests.cpp
+++ b/asl/containers/buffer_tests.cpp
@@ -6,6 +6,7 @@
#include "asl/testing/testing.hpp"
#include "asl/tests/types.hpp"
+#include "asl/tests/counting_allocator.hpp"
struct Big
{
@@ -14,6 +15,7 @@ struct Big
static_assert(asl::buffer<int32_t>::kInlineCapacity == 5);
static_assert(asl::buffer<int64_t>::kInlineCapacity == 2);
+static_assert(asl::buffer<void*>::kInlineCapacity == 2);
static_assert(asl::buffer<char>::kInlineCapacity == 23);
static_assert(asl::buffer<Big>::kInlineCapacity == 0);
@@ -30,32 +32,6 @@ ASL_TEST(default_size)
ASL_TEST_EXPECT(b2.data() == nullptr);
}
-struct CounterAllocator
-{
- isize_t* count;
-
- [[nodiscard]]
- void* alloc(const asl::layout& layout) const
- {
- *count += 1;
- return asl::GlobalHeap::alloc(layout);
- }
-
- void* realloc(void* ptr, const asl::layout& old, const asl::layout& new_layout) const
- {
- *count += 1;
- return asl::GlobalHeap::realloc(ptr, old, new_layout);
- }
-
- static void dealloc(void* ptr, const asl::layout& layout)
- {
- asl::GlobalHeap::dealloc(ptr, layout);
- }
-
- constexpr bool operator==(const CounterAllocator&) const { return true; }
-};
-static_assert(asl::allocator<CounterAllocator>);
-
struct IncompatibleAllocator
{
static void* alloc(const asl::layout& layout)
@@ -80,31 +56,31 @@ static_assert(asl::allocator<IncompatibleAllocator>);
// NOLINTNEXTLINE(*-complexity)
ASL_TEST(reserve_capacity)
{
- isize_t count = 0;
- asl::buffer<int32_t, CounterAllocator> b(CounterAllocator{&count});
+ CountingAllocator::Stats stats;
+ asl::buffer<int32_t, CountingAllocator> b(CountingAllocator{&stats});
ASL_TEST_EXPECT(b.size() == 0);
ASL_TEST_EXPECT(b.capacity() == 5);
- ASL_TEST_EXPECT(count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 0);
b.reserve_capacity(4);
ASL_TEST_EXPECT(b.size() == 0);
ASL_TEST_EXPECT(b.capacity() == 5);
- ASL_TEST_EXPECT(count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 0);
b.reserve_capacity(12);
ASL_TEST_EXPECT(b.size() == 0);
ASL_TEST_EXPECT(b.capacity() >= 12);
- ASL_TEST_EXPECT(count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
b.reserve_capacity(13);
ASL_TEST_EXPECT(b.size() == 0);
ASL_TEST_EXPECT(b.capacity() >= 13);
- ASL_TEST_EXPECT(count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
b.reserve_capacity(130);
ASL_TEST_EXPECT(b.size() == 0);
ASL_TEST_EXPECT(b.capacity() >= 130);
- ASL_TEST_EXPECT(count == 2);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 2);
}
// NOLINTNEXTLINE(*-complexity)
@@ -399,21 +375,21 @@ ASL_TEST(move_assign_from_heap)
ASL_TEST(move_assign_trivial_heap_to_inline)
{
- isize_t alloc_count = 0;
- asl::buffer<int64_t, CounterAllocator> buf{CounterAllocator{&alloc_count}};
- asl::buffer<int64_t, CounterAllocator> buf2{CounterAllocator{&alloc_count}};
+ CountingAllocator::Stats stats;
+ asl::buffer<int64_t, CountingAllocator> buf{CountingAllocator{&stats}};
+ asl::buffer<int64_t, CountingAllocator> buf2{CountingAllocator{&stats}};
buf.push(1);
buf.push(2);
- ASL_TEST_EXPECT(alloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 0);
buf2.push(3);
buf2.push(4);
buf2.push(5);
- ASL_TEST_EXPECT(alloc_count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
buf = std::move(buf2);
- ASL_TEST_EXPECT(alloc_count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
ASL_TEST_EXPECT(buf.size() == 3);
ASL_TEST_EXPECT(buf[0] == 3);
@@ -423,21 +399,21 @@ ASL_TEST(move_assign_trivial_heap_to_inline)
ASL_TEST(move_assign_trivial_inline_to_heap)
{
- isize_t alloc_count = 0;
- asl::buffer<int64_t, CounterAllocator> buf{CounterAllocator{&alloc_count}};
- asl::buffer<int64_t, CounterAllocator> buf2{CounterAllocator{&alloc_count}};
+ CountingAllocator::Stats stats;
+ asl::buffer<int64_t, CountingAllocator> buf{CountingAllocator{&stats}};
+ asl::buffer<int64_t, CountingAllocator> buf2{CountingAllocator{&stats}};
buf.push(1);
buf.push(2);
- ASL_TEST_EXPECT(alloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 0);
buf2.push(3);
buf2.push(4);
buf2.push(5);
- ASL_TEST_EXPECT(alloc_count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
buf2 = std::move(buf);
- ASL_TEST_EXPECT(alloc_count == 1);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
ASL_TEST_EXPECT(buf2.size() == 2);
ASL_TEST_EXPECT(buf2[0] == 1);
@@ -635,3 +611,6 @@ ASL_TEST(resize_zero)
}
}
+static_assert(asl::same_as<decltype(asl::declval<asl::buffer<int>>().data()), int*>);
+static_assert(asl::same_as<decltype(asl::declval<const asl::buffer<int>>().data()), const int*>);
+
diff --git a/asl/containers/chunked_buffer.hpp b/asl/containers/chunked_buffer.hpp
new file mode 100644
index 0000000..3af7aa2
--- /dev/null
+++ b/asl/containers/chunked_buffer.hpp
@@ -0,0 +1,399 @@
+// Copyright 2025 Steven Le Rouzic
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+#pragma once
+
+#include "asl/base/utility.hpp"
+#include "asl/base/assert.hpp"
+#include "asl/base/numeric.hpp"
+#include "asl/containers/buffer.hpp"
+#include "asl/memory/allocator.hpp"
+#include "asl/types/array.hpp"
+#include "asl/types/maybe_uninit.hpp"
+
+namespace asl
+{
+
+template<
+ is_object T,
+ isize_t kChunkSize,
+ allocator Allocator = DefaultAllocator>
+class chunked_buffer
+{
+ static_assert(kChunkSize > 0 && is_pow2(kChunkSize));
+
+ using Chunk = array<maybe_uninit<T>, kChunkSize>;
+
+ static constexpr isize_t chunk_index(isize_t i)
+ {
+ static constexpr int kChunkSizeLog2 = countr_zero(uint64_t{kChunkSize});
+ return i >> kChunkSizeLog2;
+ }
+
+ static constexpr isize_t index_in_chunk(isize_t i)
+ {
+ static constexpr isize_t kMask = kChunkSize - 1;
+ return i & kMask;
+ }
+
+ struct PerChunkIterator
+ {
+ isize_t from_chunk;
+ isize_t to_chunk;
+
+ isize_t from_index_in_chunk;
+ isize_t to_index_in_chunk;
+
+ [[nodiscard]] constexpr bool has_more() const
+ {
+ return from_chunk <= to_chunk;
+ }
+
+ void advance()
+ {
+ from_chunk += 1;
+ from_index_in_chunk = 0;
+ }
+
+ [[nodiscard]] constexpr isize_t chunk() const { return from_chunk; }
+
+ span<maybe_uninit<T>> make_span(Chunk& chunk) const
+ {
+ isize_t from = from_index_in_chunk;
+ isize_t to = (from_chunk == to_chunk) ? to_index_in_chunk : kChunkSize - 1;
+ return chunk.as_span().subspan(from, to - from + 1);
+ }
+ };
+
+ PerChunkIterator make_index_iterator(isize_t from, isize_t to)
+ {
+ return PerChunkIterator {
+ chunk_index(from), chunk_index(to),
+ index_in_chunk(from), index_in_chunk(to)
+ };
+ }
+
+ buffer<Chunk*, Allocator> m_chunks;
+ isize_t m_size{};
+
+ void resize_uninit_inner(isize_t new_size)
+ {
+ ASL_ASSERT(new_size >= 0);
+
+ if constexpr (!trivially_destructible<T>)
+ {
+ const isize_t old_size = size();
+ if (new_size < old_size)
+ {
+ for (PerChunkIterator it = make_index_iterator(new_size, old_size - 1);
+ it.has_more();
+ it.advance())
+ {
+ auto span = it.make_span(*m_chunks[it.chunk()]);
+ for (auto& el: span)
+ {
+ el.destroy_unsafe();
+ }
+ }
+ }
+ }
+
+ reserve_capacity(new_size);
+ m_size = new_size;
+ }
+
+ template<typename... Args>
+ void resize_construct(isize_t new_size, Args&&... args)
+ requires constructible_from<T, Args&&...>
+ {
+ const isize_t old_size = m_size;
+ resize_uninit_inner(new_size);
+
+ if (new_size > old_size)
+ {
+ for (PerChunkIterator it = make_index_iterator(old_size, new_size - 1);
+ it.has_more();
+ it.advance())
+ {
+ auto span = it.make_span(*m_chunks[it.chunk()]);
+ for (auto& uninit: span)
+ {
+ uninit.construct_unsafe(std::forward<Args>(args)...);
+ }
+ }
+ }
+ }
+
+ void copy_from(const chunked_buffer& other)
+ requires copyable<T>
+ {
+ const isize_t this_size = size();
+ isize_t to_copy_assign = asl::min(other.size(), this_size);
+
+ resize_uninit_inner(other.size());
+
+ for (PerChunkIterator it = make_index_iterator(0, to_copy_assign - 1);
+ it.has_more();
+ it.advance())
+ {
+ auto to_span = it.make_span(*m_chunks[it.chunk()]);
+ auto from_span = it.make_span(*other.m_chunks[it.chunk()]);
+
+ copy_assign_n(
+ reinterpret_cast<T*>(to_span.data()), // NOLINT(*-reinterpret-cast)
+ reinterpret_cast<const T*>(from_span.data()), // NOLINT(*-reinterpret-cast)
+ to_span.size());
+ }
+
+ if (other.size() > this_size)
+ {
+ for (PerChunkIterator it = make_index_iterator(to_copy_assign, other.size() - 1);
+ it.has_more();
+ it.advance())
+ {
+ auto to_span = it.make_span(*m_chunks[it.chunk()]);
+ auto from_span = it.make_span(*other.m_chunks[it.chunk()]);
+
+ copy_uninit_n(
+ reinterpret_cast<T*>(to_span.data()), // NOLINT(*-reinterpret-cast)
+ reinterpret_cast<const T*>(from_span.data()), // NOLINT(*-reinterpret-cast)
+ to_span.size());
+ }
+ }
+
+ ASL_ASSERT(size() == other.size());
+ }
+
+public:
+ constexpr chunked_buffer()
+ requires default_constructible<Allocator>
+ = default;
+
+ explicit constexpr chunked_buffer(Allocator allocator)
+ : m_chunks{std::move(allocator)}
+ {}
+
+ constexpr chunked_buffer(const chunked_buffer& other)
+ requires copyable<T> && copy_constructible<Allocator>
+ : m_chunks{other.m_chunks.allocator_copy()}
+ {
+ copy_from(other);
+ }
+
+ constexpr chunked_buffer(chunked_buffer&& other)
+ : m_chunks{std::move(other.m_chunks)}
+ , m_size{asl::exchange(other.m_size, 0)}
+ {
+ ASL_ASSERT(other.m_chunks.size() == 0);
+ }
+
+ constexpr chunked_buffer& operator=(const chunked_buffer& other)
+ requires copyable<T>
+ {
+ if (&other == this) { return *this; }
+ copy_from(other);
+ return *this;
+ }
+
+ constexpr chunked_buffer& operator=(chunked_buffer&& other)
+ {
+ if (&other == this) { return *this; }
+ destroy();
+ m_chunks = std::move(other.m_chunks);
+ m_size = asl::exchange(other.m_size, 0);
+ ASL_ASSERT(other.m_chunks.size() == 0);
+ return *this;
+ }
+
+ ~chunked_buffer()
+ {
+ destroy();
+ }
+
+ void clear()
+ {
+ if constexpr (trivially_destructible<T>)
+ {
+ m_size = 0;
+ }
+ else if (m_size > 0)
+ {
+ resize_uninit_inner(0);
+ ASL_ASSERT(m_size == 0);
+ }
+ }
+
+ void destroy()
+ {
+ clear();
+ ASL_ASSERT(size() == 0);
+
+ for (Chunk* chunk: m_chunks)
+ {
+ alloc_delete(m_chunks.allocator(), chunk);
+ }
+
+ m_chunks.destroy();
+ }
+
+ [[nodiscard]] constexpr isize_t size() const { return m_size; }
+
+ [[nodiscard]] constexpr bool is_empty() const { return size() == 0; }
+
+ [[nodiscard]] constexpr isize_t capacity() const
+ {
+ return m_chunks.size() * kChunkSize;
+ }
+
+ constexpr auto&& operator[](this auto&& self, isize_t i)
+ {
+ ASL_ASSERT(i >= 0 && i < self.m_size);
+ return std::forward_like<decltype(self)>(
+ (*std::forward<decltype(self)>(self).m_chunks[chunk_index(i)])
+ [index_in_chunk(i)].as_init_unsafe()
+ );
+ }
+
+ constexpr T& push(auto&&... args)
+ requires constructible_from<T, decltype(args)&&...>
+ {
+ const isize_t chunk = chunk_index(m_size);
+ const isize_t in_chunk = index_in_chunk(m_size);
+
+ if (m_size == capacity())
+ {
+ resize_uninit_inner(m_size + 1);
+ }
+ else
+ {
+ m_size += 1;
+ }
+
+ void* uninit = &(*m_chunks[chunk])[in_chunk];
+ return *construct_at<T>(uninit, std::forward<decltype(args)>(args)...);
+ }
+
+ void reserve_capacity(isize_t new_capacity)
+ {
+ new_capacity = round_up_pow2(new_capacity, kChunkSize);
+ if (new_capacity <= capacity()) { return; }
+
+ const isize_t required_chunks = new_capacity / kChunkSize;
+ const isize_t additional_chunks = required_chunks - m_chunks.size();
+ ASL_ASSERT(additional_chunks > 0);
+
+ m_chunks.reserve_capacity(required_chunks);
+ for (isize_t i = 0; i < additional_chunks; ++i)
+ {
+ // @Todo(C++26) _unsafe shouldn't be needed with trivial unions
+ auto* chunk = alloc_uninit_unsafe<Chunk>(m_chunks.allocator());
+ m_chunks.push(chunk);
+ }
+ }
+
+ void resize(isize_t new_size)
+ requires default_constructible<T>
+ {
+ if constexpr (trivially_default_constructible<T>)
+ {
+ resize_zero(new_size);
+ }
+ else
+ {
+ resize_construct(new_size);
+ }
+ }
+
+ void resize(isize_t new_size, const T& value)
+ requires copy_constructible<T>
+ {
+ resize_construct(new_size, value);
+ }
+
+ void resize_zero(isize_t new_size)
+ requires trivially_default_constructible<T>
+ {
+ const isize_t old_size = m_size;
+ resize_uninit_inner(new_size);
+
+ if (new_size > old_size)
+ {
+ for (PerChunkIterator it = make_index_iterator(old_size, new_size - 1);
+ it.has_more();
+ it.advance())
+ {
+ auto span = it.make_span(*m_chunks[it.chunk()]);
+ asl::memzero(span.data(), span.size_bytes());
+ }
+ }
+ }
+
+ void resize_uninit(isize_t new_size)
+ requires trivially_default_constructible<T>
+ {
+ resize_uninit_inner(new_size);
+ }
+
+ template<typename Chunk>
+ class generic_iterator
+ {
+ isize_t m_index;
+ span<Chunk> m_chunks;
+
+ public:
+ constexpr generic_iterator(isize_t index, span<Chunk> chunks)
+ : m_index{index}
+ , m_chunks{chunks}
+ {}
+
+ constexpr generic_iterator& operator++()
+ {
+ m_index += 1;
+ return *this;
+ }
+
+ constexpr generic_iterator operator++(int)
+ {
+ auto tmp = *this;
+ m_index += 1;
+ return tmp;
+ }
+
+ constexpr bool operator==(this generic_iterator self, generic_iterator other)
+ {
+ ASL_ASSERT(self.m_chunks.data() == other.m_chunks.data());
+ return self.m_index == other.m_index;
+ }
+
+ constexpr auto& operator*(this generic_iterator self)
+ {
+ ASL_ASSERT(self.m_index >= 0);
+ return (*self.m_chunks[chunk_index(self.m_index)])[index_in_chunk(self.m_index)].as_init_unsafe();
+ }
+
+ constexpr auto* operator->(this generic_iterator self)
+ {
+ return &*self;
+ }
+ };
+
+ using iterator = generic_iterator<Chunk*>;
+ using const_iterator = generic_iterator<const Chunk* const>;
+
+ constexpr iterator begin() { return iterator{0, m_chunks}; }
+ constexpr iterator end() { return iterator{m_size, m_chunks}; }
+
+ constexpr const_iterator begin() const
+ {
+ return const_iterator{0, {m_chunks.data(), m_chunks.size()}};
+ }
+
+ constexpr const_iterator end() const
+ {
+ return const_iterator{m_size, {m_chunks.data(), m_chunks.size()}};
+ }
+};
+
+} // namespace asl
+
diff --git a/asl/containers/chunked_buffer_tests.cpp b/asl/containers/chunked_buffer_tests.cpp
new file mode 100644
index 0000000..797f7f1
--- /dev/null
+++ b/asl/containers/chunked_buffer_tests.cpp
@@ -0,0 +1,335 @@
+// Copyright 2025 Steven Le Rouzic
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+#include "asl/testing/testing.hpp"
+#include "asl/tests/types.hpp"
+#include "asl/tests/counting_allocator.hpp"
+#include "asl/containers/chunked_buffer.hpp"
+
+static_assert(asl::moveable<asl::chunked_buffer<int, 8>>);
+static_assert(asl::moveable<asl::chunked_buffer<Copyable, 8>>);
+static_assert(asl::moveable<asl::chunked_buffer<MoveableOnly, 8>>);
+static_assert(asl::moveable<asl::chunked_buffer<Pinned, 8>>);
+
+static_assert(asl::copyable<asl::chunked_buffer<int, 8>>);
+static_assert(asl::copyable<asl::chunked_buffer<Copyable, 8>>);
+static_assert(!asl::copyable<asl::chunked_buffer<MoveableOnly, 8>>);
+static_assert(!asl::copyable<asl::chunked_buffer<Pinned, 8>>);
+
+ASL_TEST(reserve)
+{
+ asl::chunked_buffer<int, 16> b;
+ ASL_TEST_EXPECT(b.capacity() == 0);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.reserve_capacity(1);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.reserve_capacity(5);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.reserve_capacity(16);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.reserve_capacity(35);
+ ASL_TEST_EXPECT(b.capacity() == 48);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.reserve_capacity(12);
+ ASL_TEST_EXPECT(b.capacity() == 48);
+ ASL_TEST_EXPECT(b.size() == 0);
+}
+
+ASL_TEST(resize_uninit)
+{
+ asl::chunked_buffer<int, 16> b;
+ ASL_TEST_EXPECT(b.capacity() == 0);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.resize_uninit(1);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 1);
+
+ b.resize_uninit(5);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 5);
+
+ b.resize_uninit(16);
+ ASL_TEST_EXPECT(b.capacity() == 16);
+ ASL_TEST_EXPECT(b.size() == 16);
+
+ b.resize_uninit(35);
+ ASL_TEST_EXPECT(b.capacity() == 48);
+ ASL_TEST_EXPECT(b.size() == 35);
+
+ b.resize_uninit(12);
+ ASL_TEST_EXPECT(b.capacity() == 48);
+ ASL_TEST_EXPECT(b.size() == 12);
+}
+
+ASL_TEST(resize_zero)
+{
+ asl::chunked_buffer<int, 4> b;
+ ASL_TEST_EXPECT(b.capacity() == 0);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.resize_zero(2);
+ for (isize_t i = 0; i < 2; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == 0);
+ }
+
+ b.resize_zero(18);
+ for (isize_t i = 0; i < 18; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == 0);
+ }
+}
+
+ASL_TEST(resize)
+{
+ asl::chunked_buffer<int, 4> b;
+ ASL_TEST_EXPECT(b.capacity() == 0);
+ ASL_TEST_EXPECT(b.size() == 0);
+
+ b.resize(10);
+ for (isize_t i = 0; i < 10; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == 0);
+ }
+
+ b.resize(20, 8);
+ for (isize_t i = 0; i < 10; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == 0);
+ }
+
+ for (isize_t i = 10; i < 20; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == 8);
+ }
+}
+
+ASL_TEST(push)
+{
+ asl::chunked_buffer<int, 4> b;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ b.push(i);
+ }
+
+ for (int i = 0; i < 100; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == i);
+ }
+
+ b.resize(1000);
+ for (int i = 0; i < 100; ++i)
+ {
+ ASL_TEST_EXPECT(b[i] == i);
+ }
+}
+
+ASL_TEST(clear_destroy)
+{
+ bool destroyed[5]{};
+ asl::chunked_buffer<DestructorObserver, 2> buf;
+
+ for (bool& d: destroyed)
+ {
+ buf.push(&d); // NOLINT
+ }
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(!d);
+ }
+
+ buf.clear();
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(d);
+ }
+}
+
+ASL_TEST(alloc_count) // NOLINT
+{
+ CountingAllocator::Stats stats;
+ asl::chunked_buffer<int, 4, CountingAllocator> buf{CountingAllocator{&stats}};
+
+ ASL_TEST_EXPECT(stats.alive_bytes == 0);
+ ASL_TEST_EXPECT(stats.alloc_count == 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 0);
+
+ buf.push(1);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
+
+ buf.push(2);
+ buf.push(3);
+ buf.push(4);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 1);
+
+ buf.push(5);
+ buf.push(6);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 2);
+
+ buf.resize(8, 8);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 2);
+
+ buf.resize(32, 8);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 9);
+
+ buf.resize(16, 0);
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 9);
+
+ buf.clear();
+ ASL_TEST_EXPECT(stats.alive_bytes > 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 0);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 9);
+
+ buf.destroy();
+ ASL_TEST_EXPECT(stats.alive_bytes == 0);
+ ASL_TEST_EXPECT(stats.dealloc_count == 9);
+ ASL_TEST_EXPECT(stats.any_alloc_count() == 9);
+}
+
+ASL_TEST(move)
+{
+ bool destroyed[5]{};
+
+ {
+ asl::chunked_buffer<DestructorObserver, 2> buf;
+
+ for (bool& d: destroyed)
+ {
+ buf.push(&d); // NOLINT
+ }
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(!d);
+ }
+
+ asl::chunked_buffer<DestructorObserver, 2> buf2 = std::move(buf);
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(!d);
+ }
+
+ buf = std::move(buf2);
+ buf2.destroy();
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(!d);
+ }
+ }
+
+ for (const bool d: destroyed)
+ {
+ ASL_TEST_EXPECT(d);
+ }
+}
+
+ASL_TEST(copy) // NOLINT
+{
+ asl::chunked_buffer<int, 4> buf;
+ for (int i = 0; i < 10; ++i) { buf.push(i); }
+
+ asl::chunked_buffer<int, 4> buf2 = buf;
+
+ ASL_TEST_EXPECT(buf.size() == 10);
+ ASL_TEST_EXPECT(buf2.size() == 10);
+ for (int i = 0; i < 10; ++i)
+ {
+ ASL_TEST_EXPECT(buf[i] == i);
+ ASL_TEST_EXPECT(buf2[i] == i);
+ }
+
+ buf2.resize(5);
+ buf = buf2;
+
+ ASL_TEST_EXPECT(buf.size() == 5);
+ ASL_TEST_EXPECT(buf2.size() == 5);
+ for (int i = 0; i < 5; ++i)
+ {
+ ASL_TEST_EXPECT(buf[i] == i);
+ ASL_TEST_EXPECT(buf2[i] == i);
+ }
+
+ buf.clear();
+ buf.resize(80, 12);
+ buf2 = buf;
+ ASL_TEST_EXPECT(buf.size() == 80);
+ ASL_TEST_EXPECT(buf2.size() == 80);
+ for (int i = 0; i < 80; ++i)
+ {
+ ASL_TEST_EXPECT(buf[i] == 12);
+ ASL_TEST_EXPECT(buf2[i] == 12);
+ }
+}
+
+ASL_TEST(iterator)
+{
+ asl::chunked_buffer<int, 4> buf;
+ for (int i = 0; i < 30; ++i) { buf.push(100 + i); }
+
+ auto it = buf.begin();
+ auto end = buf.end();
+ for (int i = 0; i < 30; ++i)
+ {
+ ASL_TEST_ASSERT(it != end);
+ ASL_TEST_EXPECT(*it == 100 + i);
+ it++;
+ }
+ ASL_TEST_EXPECT(it == end);
+
+ static_assert(asl::same_as<decltype(*it), int&>);
+
+ asl::chunked_buffer<int, 8> buf2;
+ ASL_TEST_EXPECT(buf2.begin() == buf2.end());
+}
+
+ASL_TEST(const_iterator)
+{
+ asl::chunked_buffer<int, 4> buf_value;
+ for (int i = 0; i < 30; ++i) { buf_value.push(100 + i); }
+
+ const auto& buf = buf_value;
+
+ auto it = buf.begin();
+ auto end = buf.end();
+ for (int i = 0; i < 30; ++i)
+ {
+ ASL_TEST_ASSERT(it != end);
+ ASL_TEST_EXPECT(*it == 100 + i);
+ ++it;
+ }
+ ASL_TEST_EXPECT(it == end);
+
+ static_assert(asl::same_as<decltype(*it), const int&>);
+
+ asl::chunked_buffer<int, 8> buf2;
+ ASL_TEST_EXPECT(buf2.begin() == buf2.end());
+}
+
diff --git a/asl/memory/allocator.hpp b/asl/memory/allocator.hpp
index a231558..f2e2dce 100644
--- a/asl/memory/allocator.hpp
+++ b/asl/memory/allocator.hpp
@@ -40,6 +40,21 @@ T* alloc_new(allocator auto& a, auto&&... args)
return construct_at<T>(ptr, std::forward<decltype(args)>(args)...);
}
+template<typename T>
+T* alloc_uninit(allocator auto& a)
+ requires trivially_default_constructible<T>
+{
+ void* ptr = a.alloc(layout::of<T>());
+ return reinterpret_cast<T*>(ptr); // NOLINT(*-reinterpret-cast)
+}
+
+template<typename T>
+T* alloc_uninit_unsafe(allocator auto& a)
+{
+ void* ptr = a.alloc(layout::of<T>());
+ return reinterpret_cast<T*>(ptr); // NOLINT(*-reinterpret-cast)
+}
+
template<typename T>
void alloc_delete(allocator auto& a, T* ptr)
{
diff --git a/asl/tests/BUILD.bazel b/asl/tests/BUILD.bazel
index 016f037..2970377 100644
--- a/asl/tests/BUILD.bazel
+++ b/asl/tests/BUILD.bazel
@@ -9,10 +9,12 @@ package(
cc_library(
name = "utils",
hdrs = [
+ "counting_allocator.hpp",
"types.hpp",
],
deps = [
"//asl/base",
+ "//asl/memory:allocator",
],
visibility = ["//asl:__subpackages__"],
)
diff --git a/asl/tests/counting_allocator.hpp b/asl/tests/counting_allocator.hpp
new file mode 100644
index 0000000..35dfcba
--- /dev/null
+++ b/asl/tests/counting_allocator.hpp
@@ -0,0 +1,48 @@
+// Copyright 2025 Steven Le Rouzic
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+#include "asl/memory/allocator.hpp"
+
+struct CountingAllocator
+{
+ struct Stats
+ {
+ isize_t alloc_count{};
+ isize_t realloc_count{};
+ isize_t dealloc_count{};
+ isize_t alive_bytes{};
+
+ [[nodiscard]] constexpr isize_t any_alloc_count() const
+ {
+ return alloc_count + realloc_count;
+ }
+ };
+
+ Stats* stats;
+
+ [[nodiscard]]
+ void* alloc(const asl::layout& layout) const
+ {
+ stats->alloc_count += 1;
+ stats->alive_bytes += layout.size;
+ return asl::GlobalHeap::alloc(layout);
+ }
+
+ void* realloc(void* ptr, const asl::layout& old, const asl::layout& new_layout) const
+ {
+ stats->realloc_count += 1;
+ stats->alive_bytes += new_layout.size - old.size;
+ return asl::GlobalHeap::realloc(ptr, old, new_layout);
+ }
+
+ void dealloc(void* ptr, const asl::layout& layout) const
+ {
+ stats->dealloc_count += 1;
+ stats->alive_bytes -= layout.size;
+ asl::GlobalHeap::dealloc(ptr, layout);
+ }
+
+ constexpr bool operator==(const CountingAllocator&) const { return true; }
+};
+static_assert(asl::allocator<CountingAllocator>);
diff --git a/asl/types/array.hpp b/asl/types/array.hpp
index 54c3fbe..1e722d9 100644
--- a/asl/types/array.hpp
+++ b/asl/types/array.hpp
@@ -12,7 +12,7 @@
namespace asl
{
-template<is_object T, int64_t kSize>
+template<is_object T, isize_t kSize>
requires (kSize > 0)
struct array
{
@@ -20,7 +20,7 @@ struct array
[[nodiscard]] constexpr bool is_empty() const { return false; }
- [[nodiscard]] constexpr int64_t size() const { return kSize; }
+ [[nodiscard]] constexpr isize_t size() const { return kSize; }
constexpr auto data(this auto&& self)
{
@@ -38,14 +38,14 @@ struct array
return contiguous_iterator{self.data() + kSize};
}
- template<int64_t kSpanSize>
+ template<isize_t kSpanSize>
requires (kSpanSize == kSize || kSpanSize == dynamic_size)
constexpr operator span<const T, kSpanSize>() const // NOLINT(*explicit*)
{
return as_span();
}
- template<int64_t kSpanSize>
+ template<isize_t kSpanSize>
requires (kSpanSize == kSize || kSpanSize == dynamic_size)
constexpr operator span<T, kSpanSize>() // NOLINT(*explicit*)
{
diff --git a/asl/types/maybe_uninit_tests.cpp b/asl/types/maybe_uninit_tests.cpp
index a525423..a4a851b 100644
--- a/asl/types/maybe_uninit_tests.cpp
+++ b/asl/types/maybe_uninit_tests.cpp
@@ -10,6 +10,8 @@ static_assert(asl::size_of<int> == asl::size_of<asl::maybe_uninit<int>>);
static_assert(asl::align_of<int> == asl::align_of<asl::maybe_uninit<int>>);
#define TEST_TYPE_PROPERTIES(PRP) \
+ static_assert(asl::PRP<asl::maybe_uninit<int>> == asl::PRP<int>); \
+ static_assert(asl::PRP<asl::maybe_uninit<void*>> == asl::PRP<void*>); \
static_assert(asl::PRP<asl::maybe_uninit<TrivialType>> == asl::PRP<TrivialType>); \
static_assert(asl::PRP<asl::maybe_uninit<TrivialTypeDefaultValue>> == asl::PRP<TrivialTypeDefaultValue>); \
static_assert(asl::PRP<asl::maybe_uninit<WithDestructor>> == asl::PRP<WithDestructor>); \
@@ -17,6 +19,8 @@ static_assert(asl::align_of<int> == asl::align_of<asl::maybe_uninit<int>>);
static_assert(asl::PRP<asl::maybe_uninit<MoveableOnly>> == asl::PRP<MoveableOnly>); \
static_assert(asl::PRP<asl::maybe_uninit<Pinned>> == asl::PRP<Pinned>);
+// @Todo(C++26) We expect this to break once trivial unions land.
+// https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3074r7.html#just-make-it-work
TEST_TYPE_PROPERTIES(trivially_default_constructible);
TEST_TYPE_PROPERTIES(trivially_copy_constructible);
TEST_TYPE_PROPERTIES(trivially_move_constructible);
--
cgit