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