Add zone allocation, internal data structures, and README

Implement mmap-based zone allocation for TINY (<=128B) and SMALL
(<=1024B) categories. malloc now creates zones on demand and
returns a pointer to the first chunk.

2 files changed, 80 insertions, 5 deletions

diff --git a/src/malloc.c b/src/malloc.c
index 8982de0..268e0d1 100644
--- a/src/malloc.c
+++ b/src/malloc.c
@@ -1,15 +1,48 @@
 /**
  * @file   malloc.c
- * @brief  Stub implementation of malloc.
+ * @brief  malloc implementation.
  */
 
 #include "malloc.h"
-#include "libft.h"
+#include "malloc_internal.h"
+
+t_heap g_heap = { 0 };
 
 void *
 malloc (size_t size)
 {
-  (void)size;
-  ft_putendl_fd ("MALLOC", 1);
-  return (NULL);
+  t_zone **zone_list;
+  t_zone *zone;
+  t_chunk *chunk;
+  size_t alloc_max;
+
+  if (size == 0)
+    size = 1;
+  if (size <= TINY_MAX)
+    {
+      zone_list = &g_heap.tiny;
+      alloc_max = TINY_MAX;
+    }
+  else if (size <= SMALL_MAX)
+    {
+      zone_list = &g_heap.small;
+      alloc_max = SMALL_MAX;
+    }
+  else
+    {
+      zone_list = &g_heap.large;
+      alloc_max = size;
+    }
+  if (*zone_list == NULL)
+    {
+      zone = zone_new (alloc_max);
+      if (zone == NULL)
+        return (NULL);
+      *zone_list = zone;
+    }
+  else
+    zone = *zone_list;
+  chunk = (t_chunk *)((char *)zone + ALIGN (sizeof (t_zone)));
+  chunk->is_free = 0;
+  return ((char *)chunk + ALIGN (sizeof (t_chunk)));
 }
diff --git a/src/zone.c b/src/zone.c
new file mode 100644
index 0000000..724237b
--- /dev/null
+++ b/src/zone.c
@@ -0,0 +1,42 @@
+/**
+ * @file   zone.c
+ * @brief  Zone allocation via mmap.
+ */
+
+#include "malloc_internal.h"
+#include <sys/mman.h>
+#include <unistd.h>
+
+static size_t
+_s_zone_size (size_t alloc_max)
+{
+  size_t chunk_size;
+  size_t total;
+  size_t page_size;
+
+  chunk_size = ALIGN (sizeof (t_chunk)) + ALIGN (alloc_max);
+  total = ALIGN (sizeof (t_zone)) + MIN_ALLOC_COUNT * chunk_size;
+  page_size = (size_t)getpagesize ();
+  return ((total + page_size - 1) & ~(page_size - 1));
+}
+
+t_zone *
+zone_new (size_t alloc_max)
+{
+  size_t zone_size;
+  t_zone *zone;
+  t_chunk *chunk;
+
+  zone_size = _s_zone_size (alloc_max);
+  zone = mmap (NULL, zone_size, PROT_READ | PROT_WRITE,
+               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+  if (zone == MAP_FAILED)
+    return (NULL);
+  zone->next = NULL;
+  zone->size = zone_size;
+  chunk = (t_chunk *)((char *)zone + ALIGN (sizeof (t_zone)));
+  chunk->size = zone_size - ALIGN (sizeof (t_zone)) - ALIGN (sizeof (t_chunk));
+  chunk->next = NULL;
+  chunk->is_free = 1;
+  return (zone);
+}