Changed the makefile system to autoconf/automake.

[cacao.git] / mm / allocator3.c

diff --git a/mm/allocator3.c b/mm/allocator3.c
new file mode 100644 (file)
index 0000000..e810559
--- /dev/null
+++ b/mm/allocator3.c
@@ -0,0 +1,117 @@
+/* First Fit FIFO */
+
+#include "allocator3.h"
+#include <stdlib.h>
+
+typedef struct cacao_freeblock_t { 
+  cacao_size_t               size;
+  struct cacao_freeblock_t*  next;
+  struct cacao_freeblock_t*  prev; /* now a double-linked list */
+} *cacao_freeblock_ptr_t;
+
+static cacao_freeblock_ptr_t first = NULL;
+static cacao_freeblock_ptr_t last  = NULL;
+
+void allocator_init()
+{
+}
+
+void allocator_close()
+{
+}
+
+void allocator_reset()
+{
+}
+
+void* allocator_alloc(cacao_size_t size)
+{
+  /* first fit */
+  cacao_freeblock_ptr_t curr = first;
+
+  while (curr) {
+    cacao_size_t  curr_size = curr->size & ~0x3;
+
+    if (curr_size > size) {
+      /* split */
+      cacao_freeblock_ptr_t  next = curr + size;
+      cacao_size_t           new_size = curr_size - size;
+
+      if (new_size >= sizeof(cacao_freeblock_ptr_t)) {
+       /* free block */
+       next->size = new_size | 0x3;
+       next->next = curr->next;
+       next->prev = curr;
+       curr->next = next;
+      } else {
+       /* small block */
+       next->size = curr->size - size | 0x1;
+      }
+    }
+
+    if (curr->size == size) {
+      curr->prev->next = curr->next;
+      curr->next->prev = curr->prev;
+      return curr;
+    }
+  }
+
+  return NULL;
+}
+
+void allocator_free_block(cacao_ptr_t block_addr, cacao_size_t size)
+{
+  cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
+
+  /* reject small free blocks */
+  if (size < sizeof(struct cacao_freeblock_t))
+    return;
+
+  /* store size in freeblock & flag it as free (2 least sign. bits) */
+  freeblock->size = size | 0x3;
+  /* prepend to list */
+  freeblock->next = NULL;
+  freeblock->prev = last;
+  if (last)
+    last->next = freeblock;
+
+  /* append (fifo) */
+  last = freeblock;
+  if (!first)
+    first = last;
+}
+
+void allocator_free_prejoin (cacao_ptr_t block_addr, cacao_ptr_t pre_addr, cacao_size_t pre_size)
+{
+  cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
+  cacao_freeblock_ptr_t  preblock = (cacao_freeblock_ptr_t)pre_addr;
+
+  preblock->size = freeblock->size + pre_size;
+  preblock->next = freeblock->next;
+  preblock->prev = freeblock->prev;
+  
+  if (preblock->next)
+    preblock->next->prev = preblock;
+  if (preblock->prev)
+    preblock->prev->next = preblock;
+}
+
+void allocator_free_postjoin(cacao_ptr_t block_addr, cacao_ptr_t post_addr, cacao_size_t post_size)
+{
+  cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
+
+  freeblock->size += post_size;
+}
+
+void allocator_free_blockjoin (cacao_ptr_t first_addr, cacao_ptr_t last_addr, cacao_size_t extra_size)
+{
+  cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)first_addr;
+  cacao_freeblock_ptr_t  endblock  = (cacao_freeblock_ptr_t)end_addr;
+  
+  freeblock->size += (endblock->size & ~0x3) + extra_size;
+
+  if (endblock->next)
+    endblock->next->prev = endblock->prev;
+  if (endblock->prev)
+    endblock->prev->next = endblock->next;
+}