LXR syslinux/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
  10static 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 */
  65void __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
  96void 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}
 114