1 files changed, 147 insertions, 7 deletions

diff --git a/lib/heap.c b/lib/heap.c
index 8331a17..03d5425 100644
--- a/lib/heap.c
+++ b/lib/heap.c
@@ -1,23 +1,143 @@
 #include <string.h>
 #include <stdlib.h>
+#include <sys/mman.h>
+
+#include "config.h"
 
 struct heap_node
 {
-	struct heap_node *next;
 	size_t size;
+	union
+	{
+		struct
+		{
+			struct heap_node *prev;
+			struct heap_node *next;
+		};
+		struct
+		{
+			char block;
+		};
+	};
 };
 
 struct heap_head
 {
-	struct heap_node *first;
-	size_t total_bytes;
-	size_t ready_bytes;
+	size_t allocated_size;
+	size_t maximum_size;
+	size_t minimum_alloc;
+	struct heap_node *root;
 };
 
+struct heap_head *heap;
+
+void *allocate_superblock(void)
+{
+	return mmap(nullptr, HEAP_SEGMENT_SIZE, 0, 0, -1, 0);
+}
+
+static struct heap_node *try_create_heap()
+{
+	if (heap != nullptr) return heap->root;
+
+	char *superblock = allocate_superblock();
+
+	heap = (struct heap_head *)superblock;
+	heap->root = (struct heap_node *)(superblock + sizeof(struct heap_head));
+
+	heap->allocated_size = HEAP_SEGMENT_SIZE;
+	heap->maximum_size = HEAP_MAX_SIZE;
+	heap->minimum_alloc = sizeof(heap->root);
+
+	heap->root->next = nullptr;
+	heap->root->prev = nullptr;
+	heap->root->size = HEAP_SEGMENT_SIZE - sizeof(superblock) - sizeof(heap->root->size);
+
+	return heap->root;
+}
+
+static struct heap_node *try_grow_heap(struct heap_node *prev)
+{
+	if (heap->allocated_size >= heap->maximum_size)
+	{
+		return nullptr;
+	}
+
+	struct heap_node *node = allocate_superblock();
+
+	if (node == nullptr)
+	{
+		return nullptr;
+	}
+
+	node->size = HEAP_SEGMENT_SIZE - sizeof(node->size);
+	node->prev = prev;
+	prev->next = node;
+
+	return node;
+}
+
+static inline size_t get_node_size(size_t size)
+{
+	return size + sizeof(size);
+}
+
+static inline bool can_divide_node(struct heap_node *parent)
+{
+	return parent->size <= heap->minimum_alloc + sizeof(struct heap_node);
+}
+
+static inline void *new_node_address(struct heap_node *parent, size_t size)
+{
+	return &parent->block + parent->size - get_node_size(size);
+}
+
+static inline struct heap_node *divide_node(struct heap_node *parent, size_t size)
+{
+	struct heap_node *child = new_node_address(parent, size);
+
+	parent->size -= get_node_size(size);
+	child->size = size;
+
+	return child;
+}
+
+static inline struct heap_node *try_divide_node(struct heap_node *node, size_t size)
+{
+	return can_divide_node(node) ? divide_node(node, size) : node;
+}
+
+static inline struct heap_node *allocate_node(size_t size)
+{
+	struct heap_node *node = try_create_heap();
+
+	while(node != nullptr)
+	{
+		if (node->size > size)
+		{
+			break;
+		}
+
+		node = node->next
+			? node->next
+			: try_grow_heap(node);
+	}
+
+	return node;
+}
+
 void *malloc(size_t size)
 {
-	(void)size;
-	return nullptr;
+	// TODO: min(heap->minimum_alloc, size);
+	size = size >= heap->minimum_alloc 
+		? size 
+		: heap->minimum_alloc;
+
+	struct heap_node *node = try_divide_node(allocate_node(size), size);
+
+	return node != nullptr
+		? &node->block
+		: nullptr;
 }
 
 void *calloc(size_t count, size_t size)
@@ -32,8 +152,28 @@ void *calloc(size_t count, size_t size)
 	return block;
 }
 
+static inline struct heap_node *block_to_node(char *block)
+{
+	return (struct heap_node *)(block - sizeof(size_t));
+}
+
 void free(void *block)
 {
-	(void)block;
+	// TODO: insertion sort by address of node
+	// TODO: coalesce adjacent nodes
+	if (block == nullptr)
+	{
+		return;
+	}
+
+	struct heap_node *node = block_to_node(block);
+	node->prev = nullptr;
+	node->next = heap->root;
+	heap->root = node;
+	
+	if (node->next != nullptr)
+	{
+		node->next->prev = node;
+	}
 }