pd.if.org Git - pdclib/blob - functions/stdlib/malloc.c

   1 /* ----------------------------------------------------------------------------
   2  * $Id$
   3  * ----------------------------------------------------------------------------
   4  * Public Domain C Library - http://pdclib.sourceforge.net
   5  * This code is Public Domain. Use, modify, and redistribute at will.
   6  * --------------------------------------------------------------------------*/
   7
   8 #include <__size_t.h>
   9
  10 void * malloc( size_t size ) { /* TODO */ };
  11
  12 /* This is a simple best-fit / first-fit implementation heavily based on
  13  * Thomas "Beyond Infinity" Kreitner's code
  14  */
  15
  16 /* memory list element */
  17 struct chunk_t
  18 {
  19     void *    address;
  20     size_t    size;
  21     chunk_t * next;
  22 };
  23
  24 struct memlist_t
  25 {
  26     chunk_t * start;
  27     chunk_t * last;
  28 };
  29
  30 size_t heap_start = 0xa0000000;
  31 size_t heap_used  = 0x00000050; /* HEAP in use. Holds the next FREE address (?) */
  32 size_t heap_max   = 0xfffffff;  /* max. HEAP */
  33
  34 static struct memlist_t free_mem = { (struct memlist_t *) heap_start,
  35                                      (struct memlist_t *) heap_start };
  36 /* free_mem.start->next = NULL; */
  37
  38 static struct memlist_t used_mem = { (struct memlist_t *) heap_start + sizeof( chunk_t ),
  39                                      (struct memlist_t *) heap_start + sizeof( chunk_t ) };
  40 /* used_mem.start->next = NULL; */
  41
  42 void * malloc( size_t size )
  43 {
  44     chunk_t * chunk = 0;
  45     chunk_t * prev_chunk;
  46     if ( free_mem.start != free_mem.last )
  47     {
  48         /* first pass: exact fit */
  49         chunk = free_mem.start;
  50         while ( 1 )
  51         {
  52             prev_chunk = chunk;
  53             chunk = chunk->next;
  54             if ( ( chunk == NULL ) || ( chunk->size == size ) )
  55             {
  56                 break;
  57             }
  58         }
  59     }
  60     if ( chunk == NULL )
  61     {
  62         /* second pass - first fit */
  63         chunk = free_mem.start;
  64         while ( 1 )
  65         {
  66             prev_chunk = chunk;
  67             chunk = chunk-> next;
  68             if ( ( chunk == NULL ) || ( chunk->size > size ) )
  69             {
  70                 break;
  71             }
  72         }
  73     }
  74     if ( chunk != NULL )
  75     {
  76         /* remove chunk from free_mem list */
  77         if ( free_mem.start->next->next == NULL )
  78         {
  79             /* free_mem list has only one entry */
  80             free_mem.last = free_mem.start;
  81         }
  82         else if ( chunk == free_mem.last )
  83         {
  84             /* chunk is last element of free_mem list */
  85             prev_chunk->next = NULL;
  86             free_mem.last = prev_chunk;
  87         }
  88         else
  89         {
  90             /* chunk is neither only nor last in free_mem list */
  91             prev_chunk->next = prev_chunk->next->next;
  92         }
  93         /* append chunk to used_mem list */
  94         chunk->next = NULL;
  95         used_mem.last->next = chunk;
  96         used_mem.last = chunk;
  97     }
  98     /* append new chunk to end of used_mem list (if there's space) */
  99     if ( chunk == NULL )
 100     {
 101         if ( ( heap_used + size ) <= heap_max )
 102         {
 103             /* building the header */
 104             chunk = (chunk_t *) heap_start + heap_used + 1;
 105             chunk->size    = size;
 106             chunk->next    = NULL;
 107             chunk->address = chunk + sizeof( chunk_t );
 108             /* push heap_used past allocated area */
 109             heap_used += sizeof( chunk_t ) + size;
 110             used_mem.last->next = chunk;
 111             used_mem.last = chunk;
 112         }
 113         else
 114         {
 115             /* allocation would exceed max. heap size -
 116             /* demand more memory from kernel - not implemented */
 117             return 0;
 118         }
 119     }
 120     return (void *) chunk->address;
 121 }