gcc/alloc-pool.c

   1 /* Functions to support a pool of allocatable objects.
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003
   3    Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin <dan@cgsoftware.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "alloc-pool.h"
  26
  27 /* Redefine abort to report an internal error w/o coredump, and
  28    reporting the location of the error in the source file.  This logic
  29    is duplicated in rtl.h and tree.h because every file that needs the
  30    special abort includes one or both.  toplev.h gets too few files,
  31    system.h gets too many.  */
  32
  33 extern void fancy_abort (const char *, int, const char *)
  34     ATTRIBUTE_NORETURN;
  35 #define abort() fancy_abort (__FILE__, __LINE__, __FUNCTION__)
  36
  37 #define align_four(x) (((x+3) >> 2) << 2)
  38 #define align_eight(x) (((x+7) >> 3) << 3)
  39
  40 /* The internal allocation object.  */
  41 typedef struct allocation_object_def
  42 {
  43 #ifdef ENABLE_CHECKING
  44   /* The ID of alloc pool which the object was allocated from.  */
  45   ALLOC_POOL_ID_TYPE id;
  46 #endif
  47
  48   union
  49     {
  50       /* The data of the object.  */
  51       char data[1];
  52
  53       /* Because we want any type of data to be well aligned after the ID,
  54          the following elements are here.  They are never accessed so
  55          the allocated object may be even smaller than this structure.  */
  56       char *align_p;
  57       double align_d;
  58       HOST_WIDEST_INT align_i;
  59 #ifdef HAVE_LONG_DOUBLE
  60       long double align_ld;
  61 #endif
  62     } u;
  63 } allocation_object;
  64
  65 /* Convert a pointer to allocation_object from a pointer to user data.  */
  66 #define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)                          \
  67    ((allocation_object *) (((char *) (X))                               \
  68                            - offsetof (allocation_object, u.data)))
  69
  70 /* Convert a pointer to user data from a pointer to allocation_object.  */
  71 #define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)                          \
  72    ((void *) (((allocation_object *) (X))->u.data))
  73
  74 #ifdef ENABLE_CHECKING
  75 /* Last used ID.  */
  76 static ALLOC_POOL_ID_TYPE last_id;
  77 #endif
  78
  79 /* Create a pool of things of size SIZE, with NUM in each block we
  80    allocate.  */
  81
  82 alloc_pool
  83 create_alloc_pool (const char *name, size_t size, size_t num)
  84 {
  85   alloc_pool pool;
  86   size_t pool_size, header_size;
  87
  88   if (!name)
  89     abort ();
  90
  91   /* Make size large enough to store the list header.  */
  92   if (size < sizeof (alloc_pool_list))
  93     size = sizeof (alloc_pool_list);
  94
  95   /* Now align the size to a multiple of 4.  */
  96   size = align_four (size);
  97
  98 #ifdef ENABLE_CHECKING
  99   /* Add the aligned size of ID.  */
 100   size += offsetof (allocation_object, u.data);
 101 #endif
 102
 103   /* Um, we can't really allocate 0 elements per block.  */
 104   if (num == 0)
 105     abort ();
 106
 107   /* Find the size of the pool structure, and the name.  */
 108   pool_size = sizeof (struct alloc_pool_def);
 109
 110   /* and allocate that much memory.  */
 111   pool = (alloc_pool) xmalloc (pool_size);
 112
 113   /* Now init the various pieces of our pool structure.  */
 114   pool->name = xstrdup (name);
 115   pool->elt_size = size;
 116   pool->elts_per_block = num;
 117
 118   /* List header size should be a multiple of 8 */
 119   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 120
 121   pool->block_size = (size * num) + header_size;
 122   pool->free_list = NULL;
 123   pool->elts_allocated = 0;
 124   pool->elts_free = 0;
 125   pool->blocks_allocated = 0;
 126   pool->block_list = NULL;
 127
 128 #ifdef ENABLE_CHECKING
 129   /* Increase the last used ID and use it for this pool.
 130      ID == 0 is used for free elements of pool so skip it.  */
 131   last_id++;
 132   if (last_id == 0)
 133     last_id++;
 134
 135   pool->id = last_id;
 136 #endif
 137
 138   return (pool);
 139 }
 140
 141 /* Free all memory allocated for the given memory pool.  */
 142 void
 143 free_alloc_pool (alloc_pool pool)
 144 {
 145   alloc_pool_list block, next_block;
 146
 147 #ifdef ENABLE_CHECKING
 148   if (!pool)
 149     abort ();
 150 #endif
 151
 152   /* Free each block allocated to the pool.  */
 153   for (block = pool->block_list; block != NULL; block = next_block)
 154     {
 155       next_block = block->next;
 156       free (block);
 157     }
 158   /* Lastly, free the pool and the name.  */
 159   free (pool->name);
 160   free (pool);
 161 }
 162
 163 /* Allocates one element from the pool specified.  */
 164 void *
 165 pool_alloc (alloc_pool pool)
 166 {
 167   alloc_pool_list header;
 168   char *block;
 169
 170 #ifdef ENABLE_CHECKING
 171   if (!pool)
 172     abort ();
 173 #endif
 174
 175   /* If there are no more free elements, make some more!.  */
 176   if (!pool->free_list)
 177     {
 178       size_t i;
 179       alloc_pool_list block_header;
 180
 181       /* Make the block */
 182       block = (char *) xmalloc (pool->block_size);
 183       block_header = (alloc_pool_list) block;
 184       block += align_eight (sizeof (struct alloc_pool_list_def));
 185
 186       /* Throw it on the block list */
 187       block_header->next = pool->block_list;
 188       pool->block_list = block_header;
 189
 190       /* Now put the actual block pieces onto the free list.  */
 191       for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
 192       {
 193 #ifdef ENABLE_CHECKING
 194         /* Mark the element to be free.  */
 195         ((allocation_object *) block)->id = 0;
 196 #endif
 197         header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 198         header->next = pool->free_list;
 199         pool->free_list = header;
 200       }
 201       /* Also update the number of elements we have free/allocated, and
 202          increment the allocated block count.  */
 203       pool->elts_allocated += pool->elts_per_block;
 204       pool->elts_free += pool->elts_per_block;
 205       pool->blocks_allocated += 1;
 206     }
 207
 208   /* Pull the first free element from the free list, and return it.  */
 209   header = pool->free_list;
 210   pool->free_list = header->next;
 211   pool->elts_free--;
 212
 213 #ifdef ENABLE_CHECKING
 214   /* Set the ID for element.  */
 215   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 216 #endif
 217
 218   return ((void *) header);
 219 }
 220
 221 /* Puts PTR back on POOL's free list.  */
 222 void
 223 pool_free (alloc_pool pool, void *ptr)
 224 {
 225   alloc_pool_list header;
 226
 227 #ifdef ENABLE_CHECKING
 228   if (!ptr)
 229     abort ();
 230
 231   /* Check whether the PTR was allocated from POOL.  */
 232   if (pool->id != ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id)
 233     abort ();
 234
 235   /* Mark the element to be free.  */
 236   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 237 #else
 238   /* Check if we free more than we allocated, which is Bad (TM).  */
 239   if (pool->elts_free + 1 > pool->elts_allocated)
 240     abort ();
 241 #endif
 242
 243   header = (alloc_pool_list) ptr;
 244   header->next = pool->free_list;
 245   pool->free_list = header;
 246   pool->elts_free++;
 247 }