Back to index

cell-binutils  2.17cvs20070401
objalloc.c
Go to the documentation of this file.
00001 /* objalloc.c -- routines to allocate memory for objects
00002    Copyright 1997 Free Software Foundation, Inc.
00003    Written by Ian Lance Taylor, Cygnus Solutions.
00004 
00005 This program is free software; you can redistribute it and/or modify it
00006 under the terms of the GNU General Public License as published by the
00007 Free Software Foundation; either version 2, or (at your option) any
00008 later version.
00009 
00010 This program is distributed in the hope that it will be useful,
00011 but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013 GNU General Public License for more details.
00014 
00015 You should have received a copy of the GNU General Public License
00016 along with this program; if not, write to the Free Software
00017 Foundation, 51 Franklin Street - Fifth Floor,
00018 Boston, MA 02110-1301, USA.  */
00019 
00020 #include "config.h"
00021 #include "ansidecl.h"
00022 
00023 #include "objalloc.h"
00024 
00025 /* Get a definition for NULL.  */
00026 #include <stdio.h>
00027 
00028 #if VMS
00029 #include <stdlib.h>
00030 #include <unixlib.h>
00031 #else
00032 
00033 /* Get a definition for size_t.  */
00034 #include <stddef.h>
00035 
00036 #ifdef HAVE_STDLIB_H
00037 #include <stdlib.h>
00038 #else
00039 /* For systems with larger pointers than ints, this must be declared.  */
00040 extern PTR malloc (size_t);
00041 extern void free (PTR);
00042 #endif
00043 
00044 #endif
00045 
00046 /* These routines allocate space for an object.  Freeing allocated
00047    space may or may not free all more recently allocated space.
00048 
00049    We handle large and small allocation requests differently.  If we
00050    don't have enough space in the current block, and the allocation
00051    request is for more than 512 bytes, we simply pass it through to
00052    malloc.  */
00053 
00054 /* The objalloc structure is defined in objalloc.h.  */
00055 
00056 /* This structure appears at the start of each chunk.  */
00057 
00058 struct objalloc_chunk
00059 {
00060   /* Next chunk.  */
00061   struct objalloc_chunk *next;
00062   /* If this chunk contains large objects, this is the value of
00063      current_ptr when this chunk was allocated.  If this chunk
00064      contains small objects, this is NULL.  */
00065   char *current_ptr;
00066 };
00067 
00068 /* The aligned size of objalloc_chunk.  */
00069 
00070 #define CHUNK_HEADER_SIZE                               \
00071   ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1)       \
00072    &~ (OBJALLOC_ALIGN - 1))
00073 
00074 /* We ask for this much memory each time we create a chunk which is to
00075    hold small objects.  */
00076 
00077 #define CHUNK_SIZE (4096 - 32)
00078 
00079 /* A request for this amount or more is just passed through to malloc.  */
00080 
00081 #define BIG_REQUEST (512)
00082 
00083 /* Create an objalloc structure.  */
00084 
00085 struct objalloc *
00086 objalloc_create (void)
00087 {
00088   struct objalloc *ret;
00089   struct objalloc_chunk *chunk;
00090 
00091   ret = (struct objalloc *) malloc (sizeof *ret);
00092   if (ret == NULL)
00093     return NULL;
00094 
00095   ret->chunks = (PTR) malloc (CHUNK_SIZE);
00096   if (ret->chunks == NULL)
00097     {
00098       free (ret);
00099       return NULL;
00100     }
00101 
00102   chunk = (struct objalloc_chunk *) ret->chunks;
00103   chunk->next = NULL;
00104   chunk->current_ptr = NULL;
00105 
00106   ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
00107   ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
00108 
00109   return ret;
00110 }
00111 
00112 /* Allocate space from an objalloc structure.  */
00113 
00114 PTR
00115 _objalloc_alloc (struct objalloc *o, unsigned long len)
00116 {
00117   /* We avoid confusion from zero sized objects by always allocating
00118      at least 1 byte.  */
00119   if (len == 0)
00120     len = 1;
00121 
00122   len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
00123 
00124   if (len <= o->current_space)
00125     {
00126       o->current_ptr += len;
00127       o->current_space -= len;
00128       return (PTR) (o->current_ptr - len);
00129     }
00130 
00131   if (len >= BIG_REQUEST)
00132     {
00133       char *ret;
00134       struct objalloc_chunk *chunk;
00135 
00136       ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
00137       if (ret == NULL)
00138        return NULL;
00139 
00140       chunk = (struct objalloc_chunk *) ret;
00141       chunk->next = (struct objalloc_chunk *) o->chunks;
00142       chunk->current_ptr = o->current_ptr;
00143 
00144       o->chunks = (PTR) chunk;
00145 
00146       return (PTR) (ret + CHUNK_HEADER_SIZE);
00147     }
00148   else
00149     {
00150       struct objalloc_chunk *chunk;
00151 
00152       chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
00153       if (chunk == NULL)
00154        return NULL;
00155       chunk->next = (struct objalloc_chunk *) o->chunks;
00156       chunk->current_ptr = NULL;
00157 
00158       o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
00159       o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
00160 
00161       o->chunks = (PTR) chunk;
00162 
00163       return objalloc_alloc (o, len);
00164     }
00165 }
00166 
00167 /* Free an entire objalloc structure.  */
00168 
00169 void
00170 objalloc_free (struct objalloc *o)
00171 {
00172   struct objalloc_chunk *l;
00173 
00174   l = (struct objalloc_chunk *) o->chunks;
00175   while (l != NULL)
00176     {
00177       struct objalloc_chunk *next;
00178 
00179       next = l->next;
00180       free (l);
00181       l = next;
00182     }
00183 
00184   free (o);
00185 }
00186 
00187 /* Free a block from an objalloc structure.  This also frees all more
00188    recently allocated blocks.  */
00189 
00190 void
00191 objalloc_free_block (struct objalloc *o, PTR block)
00192 {
00193   struct objalloc_chunk *p, *small;
00194   char *b = (char *) block;
00195 
00196   /* First set P to the chunk which contains the block we are freeing,
00197      and set Q to the last small object chunk we see before P.  */
00198   small = NULL;
00199   for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
00200     {
00201       if (p->current_ptr == NULL)
00202        {
00203          if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
00204            break;
00205          small = p;
00206        }
00207       else
00208        {
00209          if (b == (char *) p + CHUNK_HEADER_SIZE)
00210            break;
00211        }
00212     }
00213 
00214   /* If we can't find the chunk, the caller has made a mistake.  */
00215   if (p == NULL)
00216     abort ();
00217 
00218   if (p->current_ptr == NULL)
00219     {
00220       struct objalloc_chunk *q;
00221       struct objalloc_chunk *first;
00222 
00223       /* The block is in a chunk containing small objects.  We can
00224         free every chunk through SMALL, because they have certainly
00225         been allocated more recently.  After SMALL, we will not see
00226         any chunks containing small objects; we can free any big
00227         chunk if the current_ptr is greater than or equal to B.  We
00228         can then reset the new current_ptr to B.  */
00229 
00230       first = NULL;
00231       q = (struct objalloc_chunk *) o->chunks;
00232       while (q != p)
00233        {
00234          struct objalloc_chunk *next;
00235 
00236          next = q->next;
00237          if (small != NULL)
00238            {
00239              if (small == q)
00240               small = NULL;
00241              free (q);
00242            }
00243          else if (q->current_ptr > b)
00244            free (q);
00245          else if (first == NULL)
00246            first = q;
00247 
00248          q = next;
00249        }
00250 
00251       if (first == NULL)
00252        first = p;
00253       o->chunks = (PTR) first;
00254 
00255       /* Now start allocating from this small block again.  */
00256       o->current_ptr = b;
00257       o->current_space = ((char *) p + CHUNK_SIZE) - b;
00258     }
00259   else
00260     {
00261       struct objalloc_chunk *q;
00262       char *current_ptr;
00263 
00264       /* This block is in a large chunk by itself.  We can free
00265          everything on the list up to and including this block.  We
00266          then start allocating from the next chunk containing small
00267          objects, setting current_ptr from the value stored with the
00268          large chunk we are freeing.  */
00269 
00270       current_ptr = p->current_ptr;
00271       p = p->next;
00272 
00273       q = (struct objalloc_chunk *) o->chunks;
00274       while (q != p)
00275        {
00276          struct objalloc_chunk *next;
00277 
00278          next = q->next;
00279          free (q);
00280          q = next;
00281        }
00282 
00283       o->chunks = (PTR) p;
00284 
00285       while (p->current_ptr != NULL)
00286        p = p->next;
00287 
00288       o->current_ptr = current_ptr;
00289       o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
00290     }
00291 }