1 files changed, 117 insertions, 0 deletions
diff --git a/prism/arena.c b/prism/arena.c
new file mode 100644
index 0000000000..64a731649d
--- /dev/null
+++ b/prism/arena.c
@@ -0,0 +1,117 @@
+#include "prism/internal/arena.h"
+
+#include "prism/internal/allocator.h"
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/**
+ * Compute the block allocation size using offsetof so it is correct regardless
+ * of PM_FLEX_ARRAY_LENGTH.
+ */
+#define PM_ARENA_BLOCK_SIZE(data_size) (offsetof(pm_arena_block_t, data) + (data_size))
+
+/** Initial block data size: 8 KB. */
+#define PM_ARENA_INITIAL_SIZE 8192
+
+/** Double the block size every this many blocks. */
+#define PM_ARENA_GROWTH_INTERVAL 8
+
+/** Maximum block data size: 1 MB. */
+#define PM_ARENA_MAX_SIZE (1024 * 1024)
+
+/**
+ * Compute the data size for the next block.
+ */
+static size_t
+pm_arena_next_block_size(const pm_arena_t *arena, size_t min_size) {
+    size_t size = PM_ARENA_INITIAL_SIZE;
+
+    for (size_t exp = PM_ARENA_GROWTH_INTERVAL; exp <= arena->block_count; exp += PM_ARENA_GROWTH_INTERVAL) {
+        if (size < PM_ARENA_MAX_SIZE) size *= 2;
+    }
+
+    return size > min_size ? size : min_size;
+}
+
+/**
+ * Allocate a new block with the given data capacity and initial usage, link it
+ * into the arena, and return it. Aborts on allocation failure.
+ */
+static pm_arena_block_t *
+pm_arena_block_new(pm_arena_t *arena, size_t data_size, size_t initial_used) {
+    assert(initial_used <= data_size);
+    pm_arena_block_t *block = (pm_arena_block_t *) xmalloc(PM_ARENA_BLOCK_SIZE(data_size));
+
+    if (block == NULL) {
+        fprintf(stderr, "prism: out of memory; aborting\n");
+        abort();
+    }
+
+    block->capacity = data_size;
+    block->used = initial_used;
+    block->prev = arena->current;
+    arena->current = block;
+    arena->block_count++;
+
+    return block;
+}
+
+/**
+ * Ensure the arena has at least `capacity` bytes available in its current
+ * block, allocating a new block if necessary. This allows callers to
+ * pre-size the arena to avoid repeated small block allocations.
+ */
+void
+pm_arena_reserve(pm_arena_t *arena, size_t capacity) {
+    if (capacity <= PM_ARENA_INITIAL_SIZE) return;
+    if (arena->current != NULL && (arena->current->capacity - arena->current->used) >= capacity) return;
+    pm_arena_block_new(arena, capacity, 0);
+}
+
+/**
+ * Slow path for pm_arena_alloc: allocate a new block and return a pointer to
+ * the first `size` bytes. Called when the current block has insufficient space.
+ */
+void *
+pm_arena_alloc_slow(pm_arena_t *arena, size_t size) {
+    size_t block_data_size = pm_arena_next_block_size(arena, size);
+    pm_arena_block_t *block = pm_arena_block_new(arena, block_data_size, size);
+    return block->data;
+}
+
+/**
+ * Returns a newly allocated and initialized arena.
+ */
+pm_arena_t *
+pm_arena_new(void) {
+    pm_arena_t *arena = (pm_arena_t *) xcalloc(1, sizeof(pm_arena_t));
+    if (arena == NULL) abort();
+    return arena;
+}
+
+/**
+ * Free all blocks in the arena.
+ */
+void
+pm_arena_cleanup(pm_arena_t *arena) {
+    pm_arena_block_t *block = arena->current;
+
+    while (block != NULL) {
+        pm_arena_block_t *prev = block->prev;
+        xfree_sized(block, PM_ARENA_BLOCK_SIZE(block->capacity));
+        block = prev;
+    }
+
+    *arena = (pm_arena_t) { 0 };
+}
+
+/**
+ * Frees both the held memory and the arena itself.
+ */
+void
+pm_arena_free(pm_arena_t *arena) {
+    pm_arena_cleanup(arena);
+    xfree_sized(arena, sizeof(pm_arena_t));
+}