git.gag.com Git - debian/cc1111/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 = NULL;
 154
 155             extern __xdata char _sdcc_heap[];
 156             extern const unsigned int _sdcc_heap_size;
 157
 158             static void init_dynamic_memory(void)
 159             {
 160               char __xdata * heap = (char __xdata *)_sdcc_heap;
 161               unsigned int size = _sdcc_heap_size;
 162
 163               if ( !heap ) //Reserved memory starts at 0x0000 but that's NULL...
 164               {             //So, we lost one byte!
 165                 heap++;
 166                 size--;
 167               }
 168               _sdcc_first_memheader = (MEMHEADER __xdata * ) heap;
 169               //Reserve a mem for last header
 170               _sdcc_first_memheader->next = (MEMHEADER __xdata * )(heap + size - sizeof(MEMHEADER __xdata *));
 171               _sdcc_first_memheader->next->next = (MEMHEADER __xdata * ) NULL; //And mark it as last
 172               _sdcc_first_memheader->len        = 0;    //Empty and ready.
 173             }
 174
 175             void __xdata * malloc (unsigned int size)
 176             {
 177               register MEMHEADER __xdata * current_header;
 178               register MEMHEADER __xdata * new_header;
 179               register void __xdata * ret;
 180
 181               if (size>(0xFFFF-HEADER_SIZE))
 182                 return (void __xdata *) NULL; //To prevent overflow in next line
 183               size += HEADER_SIZE; //We need a memory for header too
 184
 185               if (!_sdcc_first_memheader)
 186                 init_dynamic_memory();
 187
 188               current_header = _sdcc_first_memheader;
 189               CRITICAL
 190               {
 191                 while (1)
 192                 {
 193
 194                   //    current
 195                   //    |   len       next
 196                   //    v   v         v
 197                   //....*****.........******....
 198                   //         ^^^^^^^^^
 199                   //           spare
 200
 201                   if ((((unsigned int)current_header->next) -
 202                        ((unsigned int)current_header) -
 203                        current_header->len) >= size)
 204                   { //if spare is more than needed
 205                     ret = current_header->mem;
 206                     break;
 207                   }
 208                   current_header = current_header->next;    //else try next
 209                   if (!current_header->next)
 210                   { //if end_of_list reached
 211                     ret = (void __xdata *) NULL;
 212                     break;
 213                   }
 214                 }
 215                 if (ret)
 216                 {
 217                   if (!current_header->len)
 218                   { //This code works only for first_header in the list and only
 219                     current_header->len = size; //for first allocation
 220                   }
 221                   else
 222                   { //else create new header at the begin of spare
 223                     new_header = (MEMHEADER __xdata * )((char __xdata *)current_header + current_header->len);
 224                     new_header->next = current_header->next; //and plug it into the chain
 225                     current_header->next  = new_header;
 226                     new_header->len  = size; //mark as used
 227                     ret = new_header->mem;
 228                   }
 229                 }
 230               }
 231               return ret;
 232             }
 233
 234             //END OF MODULE
 235 #endif