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