git.gag.com Git - fw/sdcc/blob - device/lib/malloc.c

   1 /*-------------------------------------------------------------------------
   2    malloc.c - allocate memory.
   3
   4    Copyright (C) 2004 - Maarten Brock, sourceforge.brock@dse.nl
   5
   6    This library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    This library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with this library; if not, write to the Free Software
  18    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 -------------------------------------------------------------------------*/
  20
  21 #include <sdcc-lib.h>
  22 #include <malloc.h>
  23
  24 #if defined(SDCC_STACK_AUTO) || defined(SDCC_z80) || defined(SDCC_gbz80)
  25   #define CRITICAL critical
  26 #else
  27   #define CRITICAL
  28 #endif
  29
  30 #if _SDCC_MALLOC_TYPE_MLH
  31
  32 typedef struct _MEMHEADER MEMHEADER;
  33
  34 struct _MEMHEADER
  35 {
  36   MEMHEADER *    next;
  37   MEMHEADER *    prev;
  38   unsigned int   len;
  39   unsigned char  mem;
  40 };
  41
  42 #define HEADER_SIZE (sizeof(MEMHEADER)-sizeof(char))
  43
  44 /* These variables are defined through the crt0 functions. */
  45 /* Base of this variable is the first byte of the heap. */
  46 extern MEMHEADER _sdcc_heap_start;
  47 /* Address of this variable is the last byte of the heap. */
  48 extern char _sdcc_heap_end;
  49
  50 void
  51 _sdcc_heap_init(void)
  52 {
  53   MEMHEADER *pbase = &_sdcc_heap_start;
  54   unsigned int size = &_sdcc_heap_end - (char *)pbase;
  55
  56   pbase->next = (MEMHEADER *)((char *)pbase + size - HEADER_SIZE);
  57   pbase->next->next = NULL; //And mark it as last
  58   pbase->prev       = NULL; //and mark first as first
  59   pbase->len        = 0;    //Empty and ready.
  60 }
  61
  62 void *
  63 malloc (unsigned int size)
  64 {
  65   register MEMHEADER * current_header;
  66   register MEMHEADER * new_header;
  67   register void * ret;
  68
  69   if (size>(0xFFFF-HEADER_SIZE))
  70     {
  71       return NULL; //To prevent overflow in next line
  72     }
  73
  74   size += HEADER_SIZE; //We need a memory for header too
  75   current_header = &_sdcc_heap_start;
  76
  77   CRITICAL
  78     {
  79       while (1)
  80         {
  81           //    current
  82           //    |   len       next
  83           //    v   v         v
  84           //....*****.........******....
  85           //         ^^^^^^^^^
  86           //           spare
  87
  88           if ((((unsigned int)current_header->next) -
  89                ((unsigned int)current_header) -
  90                current_header->len) >= size)
  91             { //if spare is more than needed
  92               ret = &current_header->mem;
  93               break;
  94             }
  95           current_header = current_header->next;    //else try next
  96           if (!current_header->next)
  97             { //if end_of_list reached
  98               ret = NULL;
  99               break;
 100             }
 101         }
 102
 103       if (ret)
 104         {
 105           if (!current_header->len)
 106             { //This code works only for first_header in the list and only
 107               current_header->len = size; //for first allocation
 108             }
 109           else
 110             {
 111               //else create new header at the begin of spare
 112               new_header = (MEMHEADER * )((char *)current_header + current_header->len);
 113               new_header->next = current_header->next; //and plug it into the chain
 114               new_header->prev = current_header;
 115               current_header->next  = new_header;
 116               if (new_header->next)
 117                 {
 118                   new_header->next->prev = new_header;
 119                 }
 120               new_header->len  = size; //mark as used
 121               ret = &new_header->mem;
 122             }
 123         }
 124     }
 125   return ret;
 126 }
 127
 128 #else
 129
 130             //--------------------------------------------------------------------
 131             //Written by Dmitry S. Obukhov, 1997
 132             //dso@usa.net
 133             //--------------------------------------------------------------------
 134             //Modified for SDCC by Sandeep Dutta, 1999
 135             //sandeep.dutta@usa.net
 136             //--------------------------------------------------------------------
 137             //malloc and free functions implementation for embedded system
 138             //Non-ANSI keywords are C51 specific.
 139             // xdata - variable in external memory (just RAM)
 140             //--------------------------------------------------------------------
 141
 142             #define MEMHEADER   struct MAH// Memory Allocation Header
 143
 144             MEMHEADER
 145             {
 146               MEMHEADER __xdata *  next;
 147               unsigned int         len;
 148               unsigned char        mem[];
 149             };
 150
 151             #define HEADER_SIZE sizeof(MEMHEADER)
 152
 153             MEMHEADER xdata * _sdcc_first_memheader;
 154
 155             void init_dynamic_memory(void xdata * heap, unsigned int size)
 156             {
 157
 158             //This function MUST be called after the RESET.
 159             //Parameters: heap - pointer to memory allocated by the linker
 160             //            size - size of this memory pool
 161             //Example:
 162             //     #define DYNAMIC_MEMORY_SIZE 0x2000
 163             //     .....
 164             //     unsigned char xdata dynamic_memory_pool[DYNAMIC_MEMORY_SIZE];
 165             //     unsigned char xdata * current_buffer;
 166             //     .....
 167             //     void main(void)
 168             //     {
 169             //         ...
 170             //         init_dynamic_memory(dynamic_memory_pool,DYNAMIC_MEMORY_SIZE);
 171             //         Now it is possible to use malloc.
 172             //         ...
 173             //         current_buffer = malloc(0x100);
 174             //
 175             //
 176               char xdata * array = (char xdata *)heap;
 177
 178               if ( !array ) //Reserved memory starts at 0x0000 but that's NULL...
 179               {             //So, we lost one byte!
 180                 array++;
 181                 size--;
 182               }
 183               _sdcc_first_memheader = (MEMHEADER xdata * ) array;
 184               //Reserve a mem for last header
 185               _sdcc_first_memheader->next = (MEMHEADER xdata * )(array + size - sizeof(MEMHEADER xdata *));
 186               _sdcc_first_memheader->next->next = (MEMHEADER xdata * ) NULL; //And mark it as last
 187               _sdcc_first_memheader->len        = 0;    //Empty and ready.
 188             }
 189
 190             void xdata * malloc (unsigned int size)
 191             {
 192               register MEMHEADER xdata * current_header;
 193               register MEMHEADER xdata * new_header;
 194               register void xdata * ret;
 195
 196               if (size>(0xFFFF-HEADER_SIZE)) return (void xdata *) NULL; //To prevent overflow in next line
 197               size += HEADER_SIZE; //We need a memory for header too
 198               current_header = _sdcc_first_memheader;
 199               CRITICAL
 200               {
 201                 while (1)
 202                 {
 203
 204                   //    current
 205                   //    |   len       next
 206                   //    v   v         v
 207                   //....*****.........******....
 208                   //         ^^^^^^^^^
 209                   //           spare
 210
 211                   if ((((unsigned int)current_header->next) -
 212                        ((unsigned int)current_header) -
 213                        current_header->len) >= size)
 214                   { //if spare is more than needed
 215                     ret = current_header->mem;
 216                     break;
 217                   }
 218                   current_header = current_header->next;    //else try next
 219                   if (!current_header->next)
 220                   { //if end_of_list reached
 221                     ret = (void xdata *) NULL;
 222                     break;
 223                   }
 224                 }
 225                 if (ret)
 226                 {
 227                   if (!current_header->len)
 228                   { //This code works only for first_header in the list and only
 229                     current_header->len = size; //for first allocation
 230                   }
 231                   else
 232                   { //else create new header at the begin of spare
 233                     new_header = (MEMHEADER xdata * )((char xdata *)current_header + current_header->len);
 234                     new_header->next = current_header->next; //and plug it into the chain
 235                     current_header->next  = new_header;
 236                     new_header->len  = size; //mark as used
 237                     ret = new_header->mem;
 238                   }
 239                 }
 240               }
 241               return ret;
 242             }
 243
 244             //END OF MODULE
 245 #endif