arena.h

/** C++ implementation of a memory arena with no knowledge of the CPython API.
 */
#pragma once

#include <algorithm>
#include <array>
#include <exception>
#include <forward_list>
#include <iterator>
#include <new>
#include <optional>
#include <type_traits>

namespace qb {

// this is only for config; we undef it after putting the value into a
// constexpr std::size_t
#ifndef QB_DEFAULT_BLOCK_SIZE
#define QB_DEFAULT_BLOCK_SIZE 65536  // 64kb
#endif

/** The default number of bytes in a block.

    This can be configured at build time with `-DQB_DEFAULT_BLOCK_SIZE`
 */
constexpr std::size_t default_block_size = QB_DEFAULT_BLOCK_SIZE;

// use the non-macro name everywhere
#undef QB_DEFAULT_BLOCK_SIZE

namespace detail {
/** A concept that constrains that a type to be a plain old data type.

    `block` and `arena` can only store POD types because destructors will not be
    invoked when the arena or block is destroyed.
 */
template<typename T>
concept bool pod_type = std::is_pod_v<T>;
}  // namespace detail

/** A single, contiguous block of data which supports constant time allocations.

    Blocks cannot deallocate single objects, they only grow in size.

    @tparam cap The capacity of this block.
*/
template<std::size_t cap = default_block_size>
struct block {
private:
    using buffer_type = std::array<char, cap>;

public:
    // inner types are defined to look like a container
    using value_type = typename buffer_type::value_type;
    using size_type = typename buffer_type::size_type;
    using difference_type = typename buffer_type::difference_type;
    using reference = typename buffer_type::reference;
    using const_reference = typename buffer_type::const_reference;
    using pointer = typename buffer_type::pointer;
    using const_pointer = typename buffer_type::const_pointer;

    /** The default constructor creates an empty block with no data allocated
        in it.
    */
    constexpr block() noexcept : m_size(0) {}

    constexpr block(const block& cpfrom)
        : m_data(cpfrom.m_data), m_size(cpfrom.m_size) {}

    constexpr block& operator=(const block& cpfrom) {
        m_data = cpfrom.m_data;
        m_size = cpfrom.m_size;
        return *this;
    }

    /** Return a raw pointer to the underlying data of this block.

        @return The raw bytes backing this block.
     */
    constexpr inline pointer data() noexcept {
        return m_data.data();
    }

    /** Return a const raw pointer to the underlying data of this block.

        @return The raw bytes backing this block.
     */
    constexpr inline const_pointer data() const noexcept {
        return m_data.data();
    }

    /** An iterator over elements of type `T`.
     */
    template<typename T>
    using typed_iterator = T*;

    /** A constant iterator over elemenents of type `T`.
     */
    template<typename T>
    using const_typed_iterator = const T*;

    /** An object which implements the iterator protocol with iterators for
        `data()` cast to some particular type.

        @tparam T The type to iterate as.
        @see iter
     */
    template<typename T>
    struct typed_iterable {
    private:
        block& m_block;

    protected:
        /** Create the iterable view over the block.

            @param block The block to create a view over.
        */
        typed_iterable(block& block) : m_block(block) {
            if (block.size() % alignof(T)) {
                // the data is not actually aligned for a type T
                throw std::bad_cast{};
            }
        }

    public:
        using iterator = typed_iterator<T>;
        using const_iterator = const_typed_iterator<T>;

        iterator begin() {
            return reinterpret_cast<T*>(m_block.first()());
        }

        const_iterator begin() const {
            return reinterpret_cast<const T*>(&m_block.front());
        }

        const_iterator cbegin() const {
            return reinterpret_cast<const T*>(&m_block.front());
        }

        iterator end() {
            return reinterpret_cast<T*>(&m_block[m_block.size() + 1]);
        }

        const_iterator end() const {
            return reinterpret_cast<const T*>(&m_block[m_block.size() + 1]);
        }

        const_iterator cend() const {
            return reinterpret_cast<const T*>(&m_block[m_block.size().end()]);
        }
    };

    /** Create an object which iterates as `T` instead of `value_type`.

        This is useful for iterating over fixed type blocks.

        @tparam T The type to iterate as.
        @throws std::bad_cast if the data cannot be cast to `T` because it
                would be misaligned.
     */
    template<typename T>
    typed_iterable<T> iter() {
        return typed_iterable(*this);
    }

    template<typename T>
    const typed_iterable<T> iter() const {
        return typed_iterable(*const_cast<block>(this));
    }

    auto begin() {
        return m_data.begin();
    }

    auto begin() const {
        return m_data.begin();
    }

    auto cbegin() const {
        return m_data.cbegin();
    }

    auto end() {
        return m_data.end();
    }

    auto end() const {
        return m_data.end();
    }

    auto cend() const {
        return m_data.cend();
    }

    /** Get a reference to the first allocated byte in the block.
     */
    inline value_type& front() {
        return m_data.front();
    }

    /** Get a reference to the first allocated byte in the block.
     */
    inline const value_type& front() const {
        return m_data.front();
    }

    /** Get a reference to the last allocated byte in the block.
     */
    inline value_type& back() {
        return &m_data[m_size];
    }

    /** Get a reference to the last allocated byte in the block.
     */
    inline const value_type& back() const {
        return &m_data[m_size];
    }

    /** Lookup a byte by index without bounds checking.
     */
    inline value_type& operator[](size_type pos) {
        return m_data[pos];
    }

    /** Lookup a byte by index without bounds checking.
     */
    inline const value_type& operator[](size_type pos) const {
        return m_data[pos];
    }

    /** Check if this block does not hold any data.

        This is the same as `size() == 0`.

        @return Is this block empty?
    */
    inline bool empty() const noexcept {
        return m_size == 0;
    }

    /** Check if this block cannot hold any more data.

        This is the same as `size() == capacity()`.

        @return Is this block full.
    */
    inline bool full() const noexcept {
        return m_size == cap;
    }

    /** How many bytes are stored in this block.

        @return The number of bytes stored in this block.
     */
    inline size_type size() const noexcept {
        return m_size;
    }

    /** The maximum number of bytes that can be stored in this block.

        @return The capacity of this block.
     */
    constexpr inline size_type capacity() const noexcept {
        return cap;
    }

    /** Reset this block back to empty.
     */
    inline void clear() noexcept {
        m_size = 0;
    }

    /** Check if this block can hold `size` more bytes.

        @param size The number of bytes to see if this block has room for.
        @return `true` if calling `allocate(size)` will not throw `bad_alloc`;
                otherwise `false`.
     */
    inline void has_room_for(std::size_t size) const noexcept {
        return m_size + size > cap;
    }

    /** Check if this block can hold a new object of type `T`.

        @tparam T The POD type to see if this could hold.
        @return `true` if calling `allocate(size)` will not throw `bad_alloc`;
                otherwise `false`.
     */
    template<detail::pod_type T>
    inline void has_room_for() const noexcept {
        return has_room_for(sizeof(T));
    }

    /** Request `size` bytes from this block.

        This operation is `O(c)`.

        @param size The number of bytes to allocate from this block.
        @return A pointer to the newly allocated data.
        @throws bad_alloc if the block's size would exceed its capacity after
                this allocation.
     */
    char* allocate(size_type size) {
        if (!has_room_for(size)) {
            throw std::bad_alloc{};
        }

        char* reference = &m_data[m_size];
        m_size += size;
        return reference;
    }

    /** Request storage for a particular object. The object must be a POD type.

        @tparam T The POD type to allocate.
        @return A pointer to the allocated object.
        @throws bad_alloc if the block's size would exceed its capacity after
                this allocation.
     */
    template<detail::pod_type T>
    inline T* allocate() {
        return allocate(sizeof(T));
    }

private:
    /** The underlying data for this block.
     */
    buffer_type m_data;

    /** The number of bytes allocated from `m_data`.

        This must be less than or equal to `capacity()`.
     */
    size_type m_size;
};

/** Different policies for allocating new blocks and searching for space in
    existing blocks.
 */
namespace allocation_policy {
namespace detail {
struct policy {
    // no constructor, this is just a marker type
    policy() = delete;
};
}  // namespace detail

/** A concept that constrains that a type to be a valid allocation policy.
 */
template<typename T>
concept bool policy = std::is_base_of_v<detail::policy, T>;

/** The compact allocation policy will attempt to pack each block with as much
    data as possible. When allocating new data in the arena, each block is
    searched in age-order for space for the new object. Only if there is no
    space in *any* of the existing blocks will a new block be created.

    This allocation policy is designed for arenas which will be allocating
    objects of different sizes.
 */
struct compact : public detail::policy {};

/** The fixed allocation policy only checks the newest block for space before
    falling back to allocating a new block.

    This allocating policy is designed as an optimizations for arenas that will
    only make allocations of a fixed size. When all allocations are the same
    size, only the most recent block must be checked because all of the older
    blocks will already have been filled before the newest block was created.

    @warning This policy can cause memory fragmentation if used with non-fixed
             allocation sizes leading to a degredation and increased memory
             usage.
 */
struct fixed : public detail::policy {};
}  // namespace allocation_policy

template<std::size_t block_size,
         allocation_policy::policy policy = allocation_policy::compact>
struct arena {
private:
    using block_type = block<block_size>;
    using block_list = std::forward_list<block_type>;

public:
    using allocation_policy = policy;

    /** An iterator over the data in the arena that casts the data to some
        particular type.
     */
    template<typename T = typename block_type::value_type>
    struct typed_iterator : public std::forward_iterator_tag {
    private:
        typename block_list::iterator m_block_list_iter;
        typename block_type::template typed_iterator<T> m_block_iter;
        typename block_type::template typed_iterator<T> m_block_end;

    public:
        using value_type = T;

    protected:
        typed_iterator(typename block_list::iterator& block_list_iter)
            : m_block_list_iter(block_list_iter),
              m_block_list_iter(block_list_iter->template iter<T>().begin()),
              m_block_list_iter(block_list_iter->template iter<T>().end()) {}
    public:
        typed_iterator() = default;

        typed_iterator& operator=(const typed_iterator& cpfrom) {
            m_block_list_iter = cpfrom.m_block_list_iter;
        }

        typed_iterator& operator++() {
        }
    };

    /** Request `size` bytes from this arena.

        The rules for searching for space and allocating new blocks are
        described on the different `allocation_policy` marker types.

        @param size The number of bytes to allocate from this block.
        @return A pointer to the newly allocated data.
        @throws bad_alloc if `size > block_size`.
     */
    char* allocate(std::size_t size) {
        if (size > block_size) {
            // we cannot store this in our arena because our blocks are not
            // large enough
            throw std::bad_alloc{};
        }

        if constexpr (std::is_same_v<policy, allocation_policy::compact>) {
            // The `compact` allocation policy will search for space in *any*
            // of the available blocks. We search the blocks in forward order
            // because the blocks are ordered by age. The newest block is the
            // head of the block list.

            for (block_type& block : m_blocks) {
                // scan all of the blocks in the arena and allocate in the first
                // block that can hold `size` bytes
                if (block.has_room_for(size)) {
                    return block.allocate(size);
                }
            }
        }
        else if constexpr (std::is_same_v<policy, allocation_policy::fixed>) {
            // The `fixed` allocation policy only checks the head of the block
            // list for space before allocating a new block. We only check the
            // head of the block list because it is the newest block.

            block_type& current_block = m_blocks.first();

            if (current_block.has_room_for(size)) {
                return current_block.allocate(size);
            }
        }
        else {
            // we should never get here but this keeps us safe if we add a new
            // policy and forget to update the dispatches above
            __builtin_unreachable();
            std::abort();
        }

        // There was not enough room in the existing blocks. We need to allocate
        // a new block and then allocate the space in that block. Our new block
        // always goes at the head of the block list, and the allocation
        // policies depend on that. We know that `size` will fit in the new
        // block because `size <= block`
        return m_blocks.emplace_front().allocate(size);
    }

    /** Request storage for a particular object. The object must be a POD type.

        @tparam T The POD type to allocate.
        @return A pointer to the allocated object.
        @throws bad_alloc if `size > block_size`.
     */
    template<detail::pod_type T>
    inline T* allocate() {
        return allocate(sizeof(T));
    }
private:
    /** A list of blocks to allocate in.

        We use a singly linked list over a vector for two reasons:

        1. We cannot relocate a block.
        2. We do not want to over allocate blocks.

        With those constraints in mind, the only options are `std::list` or
        `std::forward_list`. We only iterate forward over the list and we will
        never remove a block so we can save one pointer per block by using
        `std::forward_list` with no downsides.
     */
    block_list m_blocks;
};
}  // namespace qb