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 PARAMS ((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 (name, size, num)
  84      const char *name;
  85      size_t size;
  86      size_t num;
  87 {
  88   alloc_pool pool;
  89   size_t pool_size, header_size;
  90
  91   if (!name)
  92     abort ();
  93
  94   /* Make size large enough to store the list header.  */
  95   if (size < sizeof (alloc_pool_list))
  96     size = sizeof (alloc_pool_list);
  97
  98   /* Now align the size to a multiple of 4.  */
  99   size = align_four (size);
 100
 101 #ifdef ENABLE_CHECKING
 102   /* Add the aligned size of ID.  */
 103   size += offsetof (allocation_object, u.data);
 104 #endif
 105
 106   /* Um, we can't really allocate 0 elements per block.  */
 107   if (num == 0)
 108     abort ();
 109
 110   /* Find the size of the pool structure, and the name.  */
 111   pool_size = sizeof (struct alloc_pool_def);
 112
 113   /* and allocate that much memory.  */
 114   pool = (alloc_pool) xmalloc (pool_size);
 115
 116   /* Now init the various pieces of our pool structure.  */
 117   pool->name = xstrdup (name);
 118   pool->elt_size = size;
 119   pool->elts_per_block = num;
 120
 121   /* List header size should be a multiple of 8 */
 122   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 123
 124   pool->block_size = (size * num) + header_size;
 125   pool->free_list = NULL;
 126   pool->elts_allocated = 0;
 127   pool->elts_free = 0;
 128   pool->blocks_allocated = 0;
 129   pool->block_list = NULL;
 130
 131 #ifdef ENABLE_CHECKING
 132   /* Increase the last used ID and use it for this pool.
 133      ID == 0 is used for free elements of pool so skip it.  */
 134   last_id++;
 135   if (last_id == 0)
 136     last_id++;
 137
 138   pool->id = last_id;
 139 #endif
 140
 141   return (pool);
 142 }
 143
 144 /* Free all memory allocated for the given memory pool.  */
 145 void
 146 free_alloc_pool (pool)
 147      alloc_pool pool;
 148 {
 149   alloc_pool_list block, next_block;
 150
 151 #ifdef ENABLE_CHECKING
 152   if (!pool)
 153     abort ();
 154 #endif
 155
 156   /* Free each block allocated to the pool.  */
 157   for (block = pool->block_list; block != NULL; block = next_block)
 158     {
 159       next_block = block->next;
 160       free (block);
 161     }
 162   /* Lastly, free the pool and the name.  */
 163   free (pool->name);
 164   free (pool);
 165 }
 166
 167 /* Allocates one element from the pool specified.  */
 168 void *
 169 pool_alloc (pool)
 170      alloc_pool pool;
 171 {
 172   alloc_pool_list header;
 173   char *block;
 174
 175 #ifdef ENABLE_CHECKING
 176   if (!pool)
 177     abort ();
 178 #endif
 179
 180   /* If there are no more free elements, make some more!.  */
 181   if (!pool->free_list)
 182     {
 183       size_t i;
 184       alloc_pool_list block_header;
 185
 186       /* Make the block */
 187       block = (char *) xmalloc (pool->block_size);
 188       block_header = (alloc_pool_list) block;
 189       block += align_eight (sizeof (struct alloc_pool_list_def));
 190
 191       /* Throw it on the block list */
 192       block_header->next = pool->block_list;
 193       pool->block_list = block_header;
 194
 195       /* Now put the actual block pieces onto the free list.  */
 196       for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
 197       {
 198 #ifdef ENABLE_CHECKING
 199         /* Mark the element to be free.  */
 200         ((allocation_object *) block)->id = 0;
 201 #endif
 202         header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 203         header->next = pool->free_list;
 204         pool->free_list = header;
 205       }
 206       /* Also update the number of elements we have free/allocated, and
 207          increment the allocated block count.  */
 208       pool->elts_allocated += pool->elts_per_block;
 209       pool->elts_free += pool->elts_per_block;
 210       pool->blocks_allocated += 1;
 211     }
 212
 213   /* Pull the first free element from the free list, and return it.  */
 214   header = pool->free_list;
 215   pool->free_list = header->next;
 216   pool->elts_free--;
 217
 218 #ifdef ENABLE_CHECKING
 219   /* Set the ID for element.  */
 220   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 221 #endif
 222
 223   return ((void *) header);
 224 }
 225
 226 /* Puts PTR back on POOL's free list.  */
 227 void
 228 pool_free (pool, ptr)
 229      alloc_pool pool;
 230      void *ptr;
 231 {
 232   alloc_pool_list header;
 233
 234 #ifdef ENABLE_CHECKING
 235   if (!ptr)
 236     abort ();
 237
 238   /* Check whether the PTR was allocated from POOL.  */
 239   if (pool->id != ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id)
 240     abort ();
 241
 242   /* Mark the element to be free.  */
 243   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 244 #else
 245   /* Check if we free more than we allocated, which is Bad (TM).  */
 246   if (pool->elts_free + 1 > pool->elts_allocated)
 247     abort ();
 248 #endif
 249
 250   header = (alloc_pool_list) ptr;
 251   header->next = pool->free_list;
 252   pool->free_list = header;
 253   pool->elts_free++;
 254 }