Implement chunked_buffer

1 files changed, 399 insertions, 0 deletions

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
+