2 files changed, 124 insertions, 0 deletions
diff --git a/lib/heap.c b/lib/heap.c
new file mode 100644
index 0000000..d4d9938
--- /dev/null
+++ b/lib/heap.c
@@ -0,0 +1,81 @@
+/* Copyright (C) 2023 Aryadev Chavali
+
+ * You may distribute and modify this code under the terms of the
+ * GPLv2 license.  You should have received a copy of the GPLv2
+ * license with this file.  If not, please write to:
+ * aryadev@aryadevchavali.com.
+
+ * Created: 2023-11-01
+ * Author: Aryadev Chavali
+ * Description: Arena allocator
+ */
+
+#include "./heap.h"
+
+page_t *page_create(size_t max, page_t *next)
+{
+  page_t *page    = calloc(1, sizeof(*page) + max);
+  page->used      = 0;
+  page->available = max;
+  page->next      = next;
+  return page;
+}
+
+size_t page_space_left(page_t *page)
+{
+  return WORD_SAFE_SUB(page->available, page->used);
+}
+
+void page_delete(page_t *page)
+{
+  free(page);
+}
+
+void heap_create(heap_t *heap)
+{
+  heap->beg   = page_create(PAGE_DEFAULT_SIZE, NULL);
+  heap->end   = heap->beg;
+  heap->pages = 1;
+}
+
+byte *heap_allocate(heap_t *heap, size_t requested)
+{
+  page_t *ptr = heap->beg;
+  while (page_space_left(ptr) < requested)
+    ptr = ptr->next;
+  if (ptr)
+  {
+    byte *data = ptr->used + ptr->data;
+    ptr->used += requested;
+    return data;
+  }
+  // Otherwise we are at the end of the heap, and we need to allocate
+  // a new page
+
+  // Create new page and get the pointer to the start of requested data
+  page_t *new_page = page_create(MAX(PAGE_DEFAULT_SIZE, requested), NULL);
+  byte *data       = new_page->used + new_page->data;
+
+  // Set the end of the heap to the new page (update linked list)
+  heap->end->next = new_page;
+  heap->end       = new_page;
+  new_page->used += requested;
+  ++heap->pages;
+
+  return data;
+}
+
+void heap_stop(heap_t *heap)
+{
+  page_t *ptr = heap->beg;
+  for (size_t i = 0; i < heap->pages; ++i)
+  {
+    page_t *cur  = ptr;
+    page_t *next = ptr->next;
+    page_delete(cur);
+    ptr = next;
+  }
+  heap->beg   = NULL;
+  heap->end   = NULL;
+  heap->pages = 0;
+}
diff --git a/lib/heap.h b/lib/heap.h
new file mode 100644
index 0000000..b84baf0
--- /dev/null
+++ b/lib/heap.h
@@ -0,0 +1,43 @@
+/* Copyright (C) 2023 Aryadev Chavali
+
+ * You may distribute and modify this code under the terms of the
+ * GPLv2 license.  You should have received a copy of the GPLv2
+ * license with this file.  If not, please write to:
+ * aryadev@aryadevchavali.com.
+
+ * Created: 2023-11-01
+ * Author: Aryadev Chavali
+ * Description: Arena allocator
+ */
+
+#ifndef HEAP_H
+#define HEAP_H
+
+#include "./base.h"
+
+#include <stdlib.h>
+
+#define PAGE_DEFAULT_SIZE 64
+
+typedef struct Page
+{
+  struct Page *next;
+  size_t used, available;
+  byte data[];
+} page_t;
+
+page_t *page_create(size_t, page_t *);
+size_t page_space_left(page_t *);
+void page_delete(page_t *);
+
+typedef struct
+{
+  page_t *beg, *end;
+  size_t pages;
+} heap_t;
+
+void heap_create(heap_t *);
+byte *heap_allocate(heap_t *, size_t);
+void heap_stop(heap_t *);
+
+#endif