mm/allocator3.c

   1 /* First Fit FIFO */
   2
   3 #include "allocator3.h"
   4 #include <stdlib.h>
   5
   6 typedef struct cacao_freeblock_t {
   7   cacao_size_t               size;
   8   struct cacao_freeblock_t*  next;
   9   struct cacao_freeblock_t*  prev; /* now a double-linked list */
  10 } *cacao_freeblock_ptr_t;
  11
  12 static cacao_freeblock_ptr_t first = NULL;
  13 static cacao_freeblock_ptr_t last  = NULL;
  14
  15 void allocator_init()
  16 {
  17 }
  18
  19 void allocator_close()
  20 {
  21 }
  22
  23 void allocator_reset()
  24 {
  25 }
  26
  27 void* allocator_alloc(cacao_size_t size)
  28 {
  29   /* first fit */
  30   cacao_freeblock_ptr_t curr = first;
  31
  32   while (curr) {
  33     cacao_size_t  curr_size = curr->size & ~0x3;
  34
  35     if (curr_size > size) {
  36       /* split */
  37       cacao_freeblock_ptr_t  next = curr + size;
  38       cacao_size_t           new_size = curr_size - size;
  39
  40       if (new_size >= sizeof(cacao_freeblock_ptr_t)) {
  41         /* free block */
  42         next->size = new_size | 0x3;
  43         next->next = curr->next;
  44         next->prev = curr;
  45         curr->next = next;
  46       } else {
  47         /* small block */
  48         next->size = curr->size - size | 0x1;
  49       }
  50     }
  51
  52     if (curr->size == size) {
  53       curr->prev->next = curr->next;
  54       curr->next->prev = curr->prev;
  55       return curr;
  56     }
  57   }
  58
  59   return NULL;
  60 }
  61
  62 void allocator_free_block(cacao_ptr_t block_addr, cacao_size_t size)
  63 {
  64   cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
  65
  66   /* reject small free blocks */
  67   if (size < sizeof(struct cacao_freeblock_t))
  68     return;
  69
  70   /* store size in freeblock & flag it as free (2 least sign. bits) */
  71   freeblock->size = size | 0x3;
  72   /* prepend to list */
  73   freeblock->next = NULL;
  74   freeblock->prev = last;
  75   if (last)
  76     last->next = freeblock;
  77
  78   /* append (fifo) */
  79   last = freeblock;
  80   if (!first)
  81     first = last;
  82 }
  83
  84 void allocator_free_prejoin (cacao_ptr_t block_addr, cacao_ptr_t pre_addr, cacao_size_t pre_size)
  85 {
  86   cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
  87   cacao_freeblock_ptr_t  preblock = (cacao_freeblock_ptr_t)pre_addr;
  88
  89   preblock->size = freeblock->size + pre_size;
  90   preblock->next = freeblock->next;
  91   preblock->prev = freeblock->prev;
  92
  93   if (preblock->next)
  94     preblock->next->prev = preblock;
  95   if (preblock->prev)
  96     preblock->prev->next = preblock;
  97 }
  98
  99 void allocator_free_postjoin(cacao_ptr_t block_addr, cacao_ptr_t post_addr, cacao_size_t post_size)
 100 {
 101   cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)block_addr;
 102
 103   freeblock->size += post_size;
 104 }
 105
 106 void allocator_free_blockjoin (cacao_ptr_t first_addr, cacao_ptr_t last_addr, cacao_size_t extra_size)
 107 {
 108   cacao_freeblock_ptr_t  freeblock = (cacao_freeblock_ptr_t)first_addr;
 109   cacao_freeblock_ptr_t  endblock  = (cacao_freeblock_ptr_t)end_addr;
 110
 111   freeblock->size += (endblock->size & ~0x3) + extra_size;
 112
 113   if (endblock->next)
 114     endblock->next->prev = endblock->prev;
 115   if (endblock->prev)
 116     endblock->prev->next = endblock->next;
 117 }