1 #ifndef DONUT_LINEAR_BUFFER_HPP
2 #define DONUT_LINEAR_BUFFER_HPP
16 #include <type_traits>
22 template <
typename... Ts>
27 template <
typename T, std::size_t Index,
typename... Ts>
28 struct LinearBufferIndexImpl;
30 template <
typename T, std::size_t Index,
typename First,
typename... Rest>
31 struct LinearBufferIndexImpl<T, Index, First, Rest...> : LinearBufferIndexImpl<T, Index + 1, Rest...> {};
33 template <
typename T, std::size_t Index,
typename... Rest>
34 struct LinearBufferIndexImpl<T, Index, T, Rest...> : std::integral_constant<std::size_t, Index> {};
37 struct LinearBufferMinElementSize : std::integral_constant<std::size_t, sizeof(T)> {};
40 struct LinearBufferMinElementSize<T[]> : std::integral_constant<std::size_t, sizeof(std::size_t)> {};
43 struct LinearBufferVisitorParameterType {
48 struct LinearBufferVisitorParameterType<T[]> {
49 using type = std::span<const T>;
55 template <
typename T,
typename B>
56 struct linear_buffer_has_alternative;
58 template <
typename T,
typename First,
typename... Rest>
59 struct linear_buffer_has_alternative<T, LinearBuffer<First, Rest...>> : linear_buffer_has_alternative<T, LinearBuffer<Rest...>> {};
62 struct linear_buffer_has_alternative<T, LinearBuffer<>> : std::false_type {};
64 template <
typename T,
typename... Rest>
65 struct linear_buffer_has_alternative<T, LinearBuffer<T, Rest...>> : std::true_type {};
68 template <
typename T,
typename B>
72 template <
typename T,
typename B>
73 struct linear_buffer_index;
75 template <
typename T,
typename... Ts>
76 struct linear_buffer_index<T,
LinearBuffer<Ts...>> : detail::LinearBufferIndexImpl<T, 0, Ts...> {};
79 template <
typename T,
typename B>
83 template <std::
size_t Index,
typename B>
84 struct linear_buffer_alternative;
86 template <std::size_t Index,
typename First,
typename... Rest>
87 struct linear_buffer_alternative<Index,
LinearBuffer<First, Rest...>> : linear_buffer_alternative<Index - 1, LinearBuffer<Rest...>> {};
89 template <
typename T,
typename... Rest>
90 struct linear_buffer_alternative<0, LinearBuffer<T, Rest...>> {
95 template <std::
size_t Index,
typename B>
100 struct linear_buffer_size;
102 template <
typename... Ts>
103 struct linear_buffer_size<
LinearBuffer<Ts...>> : std::integral_constant<std::size_t, sizeof...(Ts)> {};
106 template <
typename B>
109 template <
typename... Ts>
112 static_assert((std::is_trivially_copyable_v<std::remove_extent_t<Ts>> && ...),
"LinearBuffer requires all element types to be trivially copyable.");
116 std::conditional_t<
sizeof...(Ts) < 255ull, std::uint8_t,
117 std::conditional_t<
sizeof...(Ts) < 65535ull, std::uint16_t,
118 std::conditional_t<
sizeof...(Ts) < 4294967295ull, std::uint32_t,
125 : memoryResource(memoryResource)
126 , nextChunkSize(std::max(nextChunkSize, MIN_CHUNK_SIZE)) {
127 assert(memoryResource);
130 template <
typename T>
131 void push_back(
const T& value) requires(!std::is_unbounded_array_v<T> && linear_buffer_has_alternative_v<T, LinearBuffer>) {
132 constexpr std::size_t HEADER_SIZE =
sizeof(
index_type);
133 constexpr std::size_t requiredSize = HEADER_SIZE +
sizeof(T) +
sizeof(
index_type) +
sizeof(std::byte*);
137 const std::size_t newChunkSize = std::max(requiredSize, nextChunkSize);
141 std::byte*
const newChunk = allocateChunk(newChunkSize);
146 head = allocateChunk(newChunkSize);
155 template <
typename T,
typename... Args>
156 void emplace_back(Args&&... args) requires(!std::is_unbounded_array_v<T> && linear_buffer_has_alternative_v<T, LinearBuffer> && std::is_constructible_v<T, Args...>) {
157 return push_back<T>(T{std::forward<Args>(args)...});
160 template <
typename T>
162 constexpr std::size_t HEADER_SIZE =
sizeof(
index_type) +
sizeof(std::size_t);
169 const std::size_t requiredSize = HEADER_SIZE +
alignof(T) - 1 + values.size_bytes() +
sizeof(
index_type) +
sizeof(std::byte*);
170 const std::size_t newChunkSize = std::max(requiredSize, nextChunkSize);
174 std::byte*
const newChunk = allocateChunk(newChunkSize);
179 head = allocateChunk(newChunkSize);
183 [[maybe_unused]]
void*
const aligned = std::align(
alignof(T), values.size_bytes(),
alignedPointer,
space);
187 const std::size_t
count = values.size();
195 template <
typename Visitor>
196 auto visit(Visitor&& visitor)
const {
197 using R = std::common_type_t<decltype(std::invoke(std::forward<Visitor>(visitor), std::declval<typename detail::LinearBufferVisitorParameterType<Ts>::type>()))...>;
199 for (
const std::byte* pointer = head; pointer != end;) {
203 const auto apply = [&]<std::size_t Index>(std::in_place_index_t<Index>) ->
void {
205 if constexpr (std::is_unbounded_array_v<RawType>) {
206 using T = std::remove_extent_t<RawType>;
209 pointer +=
sizeof(std::size_t);
210 if constexpr (
alignof(T) > 1) {
212 void*
alignedPointer =
const_cast<void*
>(
static_cast<const void*
>(pointer));
219 const std::span<const T> values{
reinterpret_cast<const T*
>(pointer),
count};
220 if constexpr (std::is_void_v<R>) {
221 std::invoke(std::forward<Visitor>(visitor), values);
222 pointer +=
count *
sizeof(T);
224 if (std::invoke(std::forward<Visitor>(visitor), values)) {
225 pointer +=
count *
sizeof(T);
232 alignas(T) std::array<std::byte,
sizeof(T)> storage;
234 const T& value = *std::launder(
reinterpret_cast<const T*
>(storage.data()));
235 if constexpr (std::is_void_v<R>) {
236 std::invoke(std::forward<Visitor>(visitor), value);
237 pointer +=
sizeof(T);
239 if (std::invoke(std::forward<Visitor>(visitor), value)) {
240 pointer +=
sizeof(T);
247 [&]<std::size_t... Indices>(std::index_sequence<Indices...>) ->
void {
248 if (!(((
index == Indices) ? (apply(std::in_place_index<Indices>),
true) :
false) || ...)) {
250 std::memcpy(&pointer, pointer,
sizeof(std::byte*));
252 }(std::make_index_sequence<
sizeof...(Ts)>{});
254 if constexpr (!std::is_void_v<R>) {
260 static constexpr std::size_t MIN_CHUNK_SIZE = std::max({(
sizeof(
index_type) + detail::LinearBufferMinElementSize<Ts>::value +
sizeof(
index_type) +
sizeof(std::byte*))...});
262 [[nodiscard]] std::byte* allocateChunk(std::size_t newChunkSize) {
263 assert(memoryResource);
264 std::byte*
const newChunk =
static_cast<std::byte*
>(memoryResource->
allocate(newChunkSize, 1));
266 remainingMemoryEnd = newChunk + newChunkSize;
267 nextChunkSize += nextChunkSize / 2;
271 LinearMemoryResource* memoryResource;
272 std::byte* head =
nullptr;
274 std::byte* remainingMemoryEnd =
nullptr;
275 std::size_t nextChunkSize;
Definition: LinearBuffer.hpp:110
void emplace_back(Args &&... args) requires(!std
Definition: LinearBuffer.hpp:156
auto visit(Visitor &&visitor) const
Definition: LinearBuffer.hpp:196
const std::size_t minRequiredSize
Definition: LinearBuffer.hpp:165
LinearBuffer(LinearMemoryResource *memoryResource, std::size_t nextChunkSize=64) noexcept
Definition: LinearBuffer.hpp:124
remainingMemoryBegin
Definition: LinearBuffer.hpp:191
std::memcpy(remainingMemoryBegin, &index, sizeof(index_type))
void * alignedPointer
Definition: LinearBuffer.hpp:164
void push_back(const T &value) requires(!std
Definition: LinearBuffer.hpp:131
const std::size_t count
Definition: LinearBuffer.hpp:187
std::size_t space
Definition: LinearBuffer.hpp:166
std::conditional_t< sizeof...(Ts)< 255ull, std::uint8_t, std::conditional_t< sizeof...(Ts)< 65535ull, std::uint16_t, std::conditional_t< sizeof...(Ts)< 4294967295ull, std::uint32_t, std::uint64_t > >> index_type
Definition: LinearBuffer.hpp:119
static constexpr index_type npos
Definition: LinearBuffer.hpp:122
std::span< const T > append(std::span< const T > values) requires(linear_buffer_has_alternative_v< T[]
const std::size_t remainingMemorySize
Definition: LinearBuffer.hpp:163
constexpr index_type index
Definition: LinearBuffer.hpp:186
Definition: LinearAllocator.hpp:15
void * allocate(std::size_t size, std::size_t alignment)
Definition: LinearAllocator.hpp:25
Definition: Application.hpp:9
constexpr bool linear_buffer_has_alternative_v
Definition: LinearBuffer.hpp:69
constexpr std::size_t linear_buffer_size_v
Definition: LinearBuffer.hpp:107
typename linear_buffer_alternative< Index, B >::type linear_buffer_alternative_t
Definition: LinearBuffer.hpp:96
constexpr std::size_t linear_buffer_index_v
Definition: LinearBuffer.hpp:80