examples

commit aa87d30d453a620a258fe759445a5aa0b9b7bf9b
parent 82f4a9b73624009ce791477574d386377c74c9b4
Author: Henry Wilson <henry@henryandlizzy.uk>
Date:   Mon,  6 Feb 2023 22:01:11 +0000

arena-tree: An example of a pool allocator for a tree data structure

Diffstat:
M
.gitignore
 | 
1
+
A
src/arena-tree.cpp
 | 
150
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 151 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -5,6 +5,7 @@
 /.gitignore
 /aio
 /alsa-simple
+/arena-tree
 /atexit
 /bit_cast
 /cat
diff --git a/src/arena-tree.cpp b/src/arena-tree.cpp
@@ -0,0 +1,150 @@
+#include <cstddef>
+#include <utility>
+#include <span>
+#include <stdexcept>
+#include <iostream>
+#include <iomanip>
+
+struct arena
+{
+	std::span<std::byte> buf;
+	unsigned top = 0;
+
+	std::byte* allocate(unsigned n, unsigned align)
+	{
+		auto start = top;
+		if (auto residual = start % align)
+			start += align - residual;
+
+		auto end = start + n;
+
+		if (end > buf.size())
+			throw std::bad_alloc();
+
+		top = end;
+		return buf.data() + start;
+	}
+
+	template <typename T, typename... Args>
+	T* construct(Args&&... args)
+	{
+		static_assert(std::is_trivially_destructible_v<T>);
+		return new(allocate(sizeof(T), alignof(T))) T{std::forward<Args>(args)...};
+	}
+
+	void free() noexcept
+	{
+		top = 0;
+	}
+
+	arena(std::span<std::byte> b)
+	:	buf(b)
+	{}
+	arena(arena const&) = delete;
+	arena& operator =(arena const&) = delete;
+};
+
+template <typename T>
+struct pool
+{
+	static_assert(std::is_trivially_destructible_v<T>);
+	arena &a;
+
+	struct freenode
+	{
+		freenode *next;
+	} *head = nullptr;
+
+	void free(T* ptr)
+	{
+		ptr->~T();
+		head = new(ptr) freenode{head};
+	}
+
+	void* allocate()
+	{
+		if (head)
+			return std::exchange(head, head->next);
+		else
+			return a.allocate(sizeof(T), alignof(T));
+	}
+
+	template <typename... Args>
+	T* construct(Args&&... args)
+	{
+		return new(allocate()) T{std::forward<Args>(args)...};
+	}
+
+	pool(arena& aa)
+	:	a{aa}
+	{}
+	pool(pool const&) = delete;
+	pool& operator =(pool const&) = delete;
+};
+
+struct treenode
+{
+	treenode *first_child, *next_sibling;
+
+	treenode(int v) : x{v} {}
+
+	int x;
+};
+
+treenode* make_tree(int v, pool<treenode>& a)
+{
+	return a.construct(v);
+}
+
+treenode* get_last_sibling(treenode* n)
+{
+	while (auto next = n->next_sibling)
+		n = next;
+	return n;
+}
+
+treenode* add_child(int v, treenode* parent, auto& a)
+{
+	auto node = make_tree(v, a);
+
+	node->next_sibling = std::exchange(parent->first_child, node);
+
+	return node;
+}
+
+unsigned count_nodes(treenode const* n)
+{
+	if (not n)
+		return 0;
+
+	return 1 + count_nodes(n->first_child) + count_nodes(n->next_sibling);
+}
+
+unsigned sum_nodes(treenode const* n)
+{
+	if (not n)
+		return 0;
+
+	return n->x + sum_nodes(n->first_child) + sum_nodes(n->next_sibling);
+}
+
+alignas(alignof(std::max_align_t)) std::byte buf[1024*1024];
+
+int main()
+{
+	arena a{buf};
+	pool<treenode> p{a};
+
+	auto head = make_tree(100, p);
+	add_child(10, head, p);
+	add_child(10, head, p);
+	add_child(10, head, p);
+	auto leaf = add_child(10, head, p);
+	add_child(1, leaf, p);
+	add_child(1, leaf, p);
+	add_child(10, head, p);
+	add_child(10, head, p);
+	add_child(10, head, p);
+
+	return sum_nodes(head);
+}