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