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 HEADER_SIZE sizeof(MEMHEADER)
 143
 144             MEMHEADER xdata * _sdcc_first_memheader;
 145
 146             void init_dynamic_memory(void xdata * heap, unsigned int size)
 147             {
 148
 149             //This function MUST be called after the RESET.
 150             //Parameters: heap - pointer to memory allocated by the linker
 151             //            size - size of this memory pool
 152             //Example:
 153             //     #define DYNAMIC_MEMORY_SIZE 0x2000
 154             //     .....
 155             //     unsigned char xdata dynamic_memory_pool[DYNAMIC_MEMORY_SIZE];
 156             //     unsigned char xdata * current_buffer;
 157             //     .....
 158             //     void main(void)
 159             //     {
 160             //         ...
 161             //         init_dynamic_memory(dynamic_memory_pool,DYNAMIC_MEMORY_SIZE);
 162             //         Now it is possible to use malloc.
 163             //         ...
 164             //         current_buffer = malloc(0x100);
 165             //
 166             //
 167               char xdata * array = (char xdata *)heap;
 168
 169               if ( !array ) //Reserved memory starts at 0x0000 but that's NULL...
 170               {             //So, we lost one byte!
 171                  array++;
 172                  size--;
 173               }
 174               _sdcc_first_memheader = (MEMHEADER xdata * ) array;
 175               //Reserve a mem for last header
 176               _sdcc_first_memheader->next = (MEMHEADER xdata * )(array + size - sizeof(MEMHEADER xdata *));
 177               _sdcc_first_memheader->next->next = (MEMHEADER xdata * ) NULL; //And mark it as last
 178               _sdcc_first_memheader->len        = 0;    //Empty and ready.
 179             }
 180
 181             void xdata * malloc (unsigned int size)
 182             {
 183               register MEMHEADER xdata * current_header;
 184               register MEMHEADER xdata * new_header;
 185               register void xdata * ret;
 186
 187               if (size>(0xFFFF-HEADER_SIZE)) return (void xdata *) NULL; //To prevent overflow in next line
 188               size += HEADER_SIZE; //We need a memory for header too
 189               current_header = _sdcc_first_memheader;
 190               CRITICAL
 191               {
 192                 while (1)
 193                 {
 194
 195                   //    current
 196                   //    |   len       next
 197                   //    v   v         v
 198                   //....*****.........******....
 199                   //         ^^^^^^^^^
 200                   //           spare
 201
 202                   if ((((unsigned int)current_header->next) -
 203                        ((unsigned int)current_header) -
 204                        current_header->len) >= size)
 205                   { //if spare is more than needed
 206                     ret = current_header->mem;
 207                     break;
 208                   }
 209                   current_header = current_header->next;    //else try next
 210                   if (!current_header->next)
 211                   { //if end_of_list reached
 212                     ret = (void xdata *) NULL;
 213                     break;
 214                   }
 215                 }
 216                 if (ret)
 217                 {
 218                   if (!current_header->len)
 219                   { //This code works only for first_header in the list and only
 220                      current_header->len = size; //for first allocation
 221                   }
 222                   else
 223                   { //else create new header at the begin of spare
 224                     new_header = (MEMHEADER xdata * )((char xdata *)current_header + current_header->len);
 225                     new_header->next = current_header->next; //and plug it into the chain
 226                     current_header->next  = new_header;
 227                     new_header->len  = size; //mark as used
 228                     ret = new_header->mem;
 229                   }
 230                 }
 231               }
 232               return ret;
 233             }
 234
 235             //END OF MODULE
 236 #endif