"arenas"

alloc.h

#include <type_traits>
#include <memory>
#include <cstdint>

// Simple arena implementation. A linked-list of large stacks of bytes
class Allocator
{
public:
	Allocator() { Clear(); }
	Allocator(Allocator&& o) : m_head(std::move(o.m_head)) {}
	void Swap(Allocator& o) { m_head.swap(o.m_head); }
	void Clear()
	{
		if( !m_head )
			NewChunk(1);
		else
		{
			m_head->used = 0;
			m_head->prev.reset();
		}
	}

	template<class T> T* Alloc(size_t count=1)
	{
		if(!count)
			return 0;
		static_assert(std::is_trivially_constructible<T>::value);
		static_assert(std::is_trivially_destructible<T>::value);
		T* result = Alloc<T>(*m_head, count);
		if( !result )
			result = Alloc<T>(NewChunk(sizeof(T) * count), count);
		Assert(result);
		return result;
	}

	inline ByteView Clone(const ByteView& input)
	{
		if(!input.length)
			return {};
		ByteView result = Clone(*m_head, input);
		if( !result.length )
			result = Clone(NewChunk(input.length), input);
		Assert(result.length);
		return result;
	}

private:
	void operator=(const Allocator&) = delete; // non-copyable
	struct Chunk
	{
		~Chunk() { memset(a.get(), 0xcd, size); }
		Chunk(Chunk&& c) : a(std::move(c.a)), size(c.size), used(c.used) {}
		Chunk(std::unique_ptr<uint8_t[]>&& data, size_t size, std::unique_ptr<Chunk>&& p) : a(std::move(data)), size(size), used(0), prev(std::move(p)) {}
		std::unique_ptr<uint8_t[]> a;
		const size_t size = 0;
		size_t used = 0;
		std::unique_ptr<Chunk> prev;
	};
	std::unique_ptr<Chunk> m_head;

	Chunk& NewChunk(size_t required)
	{
		size_t chunkSize = ((required+65535)/65536)*65536; // round up to 64k chunk allocations
		m_head = std::make_unique<Chunk>( std::unique_ptr<uint8_t[]>{ new uint8_t[chunkSize] }, chunkSize, std::move(m_head) );
		return *m_head;
	}

	template<class T> static T* Alloc(Chunk& chunk, size_t count=1)
	{
		Assert(count > 0);
		const size_t prev = chunk.used;
		size_t required = sizeof(T) * count;
		size_t index = prev;
		uint8_t* const p = &chunk.a[prev];
		*p = 0;
		const uintptr_t original = (uintptr_t)p;
		const uintptr_t aligned = ((original+__alignof(T)-1) / __alignof(T)) * __alignof(T);
		if( original != aligned )
		{
			Assert(aligned > original);
			uintptr_t extra = aligned - original;
			required += extra;
			index += extra;
		}
		if( chunk.used + required > chunk.size )
			return 0;
		chunk.used += required;
		return (T*)&chunk.a[index];
	}

	inline static ByteView Clone(Chunk& chunk, const ByteView& input)
	{
		if( chunk.used + input.length > chunk.size )
			return {};
		size_t prev = chunk.used;
		chunk.used += input.length;
		uint8_t* p = &chunk.a[prev];
		memcpy(p, input.bytes, input.length);
		return { p, input.length };
	}
};