com32/lib/free.c

   1 /*
   2  * free.c
   3  *
   4  * Very simple linked-list based malloc()/free().
   5  */
   6
   7 #include <stdlib.h>
   8 #include "malloc.h"
   9
  10 static struct free_arena_header *__free_block(struct free_arena_header *ah)
  11 {
  12     struct free_arena_header *pah, *nah;
  13
  14     pah = ah->a.prev;
  15     nah = ah->a.next;
  16     if (pah->a.type == ARENA_TYPE_FREE &&
  17         (char *)pah + pah->a.size == (char *)ah) {
  18         /* Coalesce into the previous block */
  19         pah->a.size += ah->a.size;
  20         pah->a.next = nah;
  21         nah->a.prev = pah;
  22
  23 #ifdef DEBUG_MALLOC
  24         ah->a.type = ARENA_TYPE_DEAD;
  25 #endif
  26
  27         ah = pah;
  28         pah = ah->a.prev;
  29     } else {
  30         /* Need to add this block to the free chain */
  31         ah->a.type = ARENA_TYPE_FREE;
  32
  33         ah->next_free = __malloc_head.next_free;
  34         ah->prev_free = &__malloc_head;
  35         __malloc_head.next_free = ah;
  36         ah->next_free->prev_free = ah;
  37     }
  38
  39     /* In either of the previous cases, we might be able to merge
  40        with the subsequent block... */
  41     if (nah->a.type == ARENA_TYPE_FREE &&
  42         (char *)ah + ah->a.size == (char *)nah) {
  43         ah->a.size += nah->a.size;
  44
  45         /* Remove the old block from the chains */
  46         nah->next_free->prev_free = nah->prev_free;
  47         nah->prev_free->next_free = nah->next_free;
  48         ah->a.next = nah->a.next;
  49         nah->a.next->a.prev = ah;
  50
  51 #ifdef DEBUG_MALLOC
  52         nah->a.type = ARENA_TYPE_DEAD;
  53 #endif
  54     }
  55
  56     /* Return the block that contains the called block */
  57     return ah;
  58 }
  59
  60 /*
  61  * This is used to insert a block which is not previously on the
  62  * free list.  Only the a.size field of the arena header is assumed
  63  * to be valid.
  64  */
  65 void __inject_free_block(struct free_arena_header *ah)
  66 {
  67     struct free_arena_header *nah;
  68     size_t a_end = (size_t) ah + ah->a.size;
  69     size_t n_end;
  70
  71     for (nah = __malloc_head.a.next; nah->a.type != ARENA_TYPE_HEAD;
  72          nah = nah->a.next) {
  73         n_end = (size_t) nah + nah->a.size;
  74
  75         /* Is nah entirely beyond this block? */
  76         if ((size_t) nah >= a_end)
  77             break;
  78
  79         /* Is this block entirely beyond nah? */
  80         if ((size_t) ah >= n_end)
  81             continue;
  82
  83         /* Otherwise we have some sort of overlap - reject this block */
  84         return;
  85     }
  86
  87     /* Now, nah should point to the successor block */
  88     ah->a.next = nah;
  89     ah->a.prev = nah->a.prev;
  90     nah->a.prev = ah;
  91     ah->a.prev->a.next = ah;
  92
  93     __free_block(ah);
  94 }
  95
  96 void free(void *ptr)
  97 {
  98     struct free_arena_header *ah;
  99
 100     if (!ptr)
 101         return;
 102
 103     ah = (struct free_arena_header *)
 104         ((struct arena_header *)ptr - 1);
 105
 106 #ifdef DEBUG_MALLOC
 107     assert(ah->a.type == ARENA_TYPE_USED);
 108 #endif
 109
 110     __free_block(ah);
 111
 112     /* Here we could insert code to return memory to the system. */
 113 }