kern/heap.c

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 1999,2000,2001 Bernardo Innocenti <bernie@develer.com>
   6  * This file is part of DevLib - See devlib/README for information.
   7  * -->
   8  *
   9  * \brief Heap subsystem (public interface).
  10  *
  11  * \version $Id$
  12  *
  13  * \author Bernardo Innocenti <bernie@develer.com>
  14  */
  15
  16 /*
  17  * $Log$
  18  * Revision 1.2  2004/06/03 11:27:09  bernie
  19  * Add dual-license information.
  20  *
  21  * Revision 1.1  2004/05/23 17:27:00  bernie
  22  * Import kern/ subdirectory.
  23  *
  24  */
  25
  26 #include "heap.h"
  27
  28 /* NOTE: struct size must be a 2's power! */
  29 typedef struct _MemChunk
  30 {
  31         struct _MemChunk *next;
  32         size_t size;
  33 } MemChunk;
  34
  35 static REGISTER MemChunk *FreeList;     /* Head of the free list */
  36 static uint8_t Heap[HEAP_SIZE];         /* Heap memory block */
  37
  38
  39
  40 void heap_init(void)
  41 {
  42 #ifdef _DEBUG
  43         int i;
  44
  45         /* Fill the heap with a "DEAD" code to help debugging */
  46         for (i = 0; i < HEAP_SIZE / sizeof (uint16_t); i++)
  47                 ((uint16_t *)Heap)[i] = MEM_FILL_CODE;
  48 #endif
  49
  50         /* Initialize heap with a single big chunk */
  51         FreeList = (MemChunk *)Heap;
  52         FreeList->next = NULL;
  53         FreeList->size = sizeof(Heap);
  54 }
  55
  56
  57 void *heap_alloc(size_t size)
  58 {
  59         MemChunk *chunk, *prev;
  60
  61         /* Round size up to the allocation granularity */
  62         size = ROUND2(size, sizeof(MemChunk));
  63
  64         /* Walk on the free list looking for any chunk big enough to
  65          * fit the requested block size.
  66          */
  67         for (prev = (MemChunk *)&FreeList, chunk = FreeList;
  68                 chunk;
  69                 prev = chunk, chunk = chunk->next)
  70         {
  71                 if (chunk->size <= size)
  72                 {
  73                         if (chunk->size == size)
  74                         {
  75                                 /* Just remove this chunk from the free list */
  76                                 prev->next = chunk->next;
  77                                 return (void *)chunk;
  78                         }
  79                         else
  80                         {
  81                                 /* Allocate from the END of an existing chunk */
  82                                 prev->size -= size;
  83                                 return (void *)(((uint8_t *)prev) + prev->size);
  84                         }
  85                 }
  86         }
  87
  88         return NULL; /* fail */
  89 }
  90
  91
  92 void heap_free(void *mem, size_t size)
  93 {
  94         MemChunk *prev;
  95
  96         /* Round size up to the allocation granularity */
  97         size = ROUND2(size, sizeof(MemChunk));
  98
  99         /* Special case: first chunk in the free list */
 100         if (((uint8_t *)mem) < ((uint8_t *)FreeList))
 101         {
 102                 /* Insert memory block before the current free list head */
 103                 prev = (MemChunk *)mem;
 104                 prev->next = FreeList;
 105                 prev->size = size;
 106                 FreeList = prev;
 107         }
 108         else /* Normal case: not the first chunk in the free list */
 109         {
 110                 /* Walk on the free list. Stop at the insertion point */
 111                 prev = FreeList;
 112                 while ((prev->next >= ((MemChunk *)mem)) || (!prev->next))
 113                         prev = prev->next;
 114
 115                 /* Should it be merged with previous block? */
 116                 if (((uint8_t *)prev) + prev->Size == ((uint8_t *)mem))
 117                 {
 118                         /* Yes */
 119                         prev->size += size;
 120                 }
 121                 else /* not merged with previous chunk */
 122                 {
 123                         /* insert it after the previous node
 124                          * and move the 'prev' pointer forward
 125                          * for the following operations
 126                          */
 127                         ((MemChunk *)mem)->next = prev->next;
 128                         prev->next = (MemChunk *)mem;
 129                         prev = (MemChunk *)mem;
 130                 }
 131         }
 132
 133         /* Also merge with next chunk? */
 134         if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
 135         {
 136                 prev->size += prev->next->size;
 137                 prev->next = prev->next->next;
 138         }
 139 }
 140
 141 #ifdef __POSIX__
 142
 143 /*! ANSI/POSIX-like malloc() implementation based on heap_alloc()/heap_free() */
 144 void *malloc(size_t size)
 145 {
 146         void *mem;
 147
 148         size += sizeof(size_t);
 149
 150         if (mem = heap_alloc(size))
 151                 *((size_t *)mem)++ = size;
 152
 153         return mem;
 154 }
 155
 156
 157 /*! ANSI/POSIX-like calloc() implementation based on heap_alloc()/heap_free() */
 158 void *calloc(size_t nelem, size_t size)
 159 {
 160         void *mem, *tmp;
 161
 162         size *= nelem;
 163
 164         if (mem = malloc(size))
 165         {
 166                 tmp = mem;
 167                 while (size--)
 168                         ((uint8_t *)tmp++) = 0;
 169         }
 170
 171         return mem;
 172 }
 173
 174 /*! ANSI/POSIX-like free() implementation based on heap_alloc()/heap_free() */
 175 void free(void *mem)
 176 {
 177         ((size_t *)mem)--;
 178         heap_free(mem, *((size_t *)mem));
 179 }
 180
 181 #endif /* __POSIX__ */