From 41ee6b43c89ce67808a684ba67f69e964b0636fa Mon Sep 17 00:00:00 2001
From: aqua <aqua@iserlohn-fortress.net>
Date: Sat, 18 Feb 2023 10:12:24 +0200
Subject: Move C stdlib to lib/libk

---
 lib/libk/stdlib/linked_list_allocator.c | 77 +++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 lib/libk/stdlib/linked_list_allocator.c

(limited to 'lib/libk/stdlib/linked_list_allocator.c')

diff --git a/lib/libk/stdlib/linked_list_allocator.c b/lib/libk/stdlib/linked_list_allocator.c
new file mode 100644
index 0000000..66c63d1
--- /dev/null
+++ b/lib/libk/stdlib/linked_list_allocator.c
@@ -0,0 +1,77 @@
+#include <stdint.h>
+#include <stdlib.h>
+
+struct Chunk {
+  struct Chunk *prev;
+  struct Chunk *next;
+  int used;
+  size_t size;
+};
+
+void
+Chunk_ctor(struct Chunk *self, size_t size)
+{
+  self->prev = NULL;
+  self->next = NULL;
+  self->used = 0;
+  self->size = size - sizeof(struct Chunk);
+}
+
+static struct Chunk *begin = NULL;
+
+void
+alloc_init(void *mem, size_t size)
+{
+  if (size < sizeof(struct Chunk)) return;
+
+  begin = (struct Chunk *)mem;
+  Chunk_ctor(begin, size);
+}
+
+void *
+malloc(size_t size)
+{
+  if (begin == NULL) return NULL;
+
+  // find free chunk that is at least (size + sizeof(struct Chunk))
+  for (struct Chunk *iter = begin; iter != NULL; iter = iter->next) {
+    if (iter->used != 0 || iter->size < size) continue;
+
+    // if there's at least sizeof(struct Chunk) bytes left over, create a new Chunk
+    if (iter->size >= (size + 2 * sizeof(struct Chunk))) {
+      struct Chunk *next = (struct Chunk *)((uintptr_t)iter + sizeof(struct Chunk) + size);
+      Chunk_ctor(next, iter->size - size - sizeof(struct Chunk));
+      next->prev = iter;
+
+      iter->size = size;
+      iter->next = next;
+    }
+
+    iter->used = 1;
+    return (void *)((uintptr_t)iter + sizeof(struct Chunk));
+  }
+
+  return NULL;
+}
+
+void
+free(void *ptr)
+{
+  if (ptr == NULL) return;
+  struct Chunk *chunk = (struct Chunk *)((uintptr_t)ptr - sizeof(struct Chunk));
+  chunk->used = 0;
+
+  // merge next chunk
+  if (chunk->next != NULL && chunk->next->used == 0) {
+    chunk->size += chunk->next->size + sizeof(struct Chunk);
+    chunk->next = chunk->next->next;
+    if (chunk->next != NULL) chunk->next->prev = chunk;
+  }
+
+  // merge into prev chunk
+  if (chunk->prev != NULL && chunk->prev->used == 0) {
+    chunk->prev->size += chunk->size + sizeof(struct Chunk);
+    chunk->prev->next = chunk->next;
+    if (chunk->next != NULL) chunk->next->prev = chunk->prev;
+  }
+}
-- 
cgit v1.2.1