gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Nathan Sidwell <nathan@codesourcery.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file is compiled twice: once for the generator programs
  22    once for the compiler.  */
  23 #ifdef GENERATOR_FILE
  24 #include "bconfig.h"
  25 #else
  26 #include "config.h"
  27 #endif
  28
  29 #include "system.h"
  30 #include "ggc.h"
  31 #include "vec.h"
  32 #include "coretypes.h"
  33 #include "tree.h"
  34 #include "toplev.h"
  35
  36 struct vec_prefix
  37 {
  38   unsigned num;
  39   unsigned alloc;
  40   void *vec[1];
  41 };
  42
  43 /* Calculate the new ALLOC value, making sure that RESERVE slots are
  44    free.  If EXACT grow exactly, otherwise grow exponentially.  */
  45
  46 static inline unsigned
  47 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
  48 {
  49   unsigned alloc = 0;
  50   unsigned num = 0;
  51
  52   gcc_assert (reserve >= 0);
  53
  54   if (pfx)
  55     {
  56       alloc = pfx->alloc;
  57       num = pfx->num;
  58     }
  59   else if (!reserve)
  60     /* If there's no prefix, and we've not requested anything, then we
  61        will create a NULL vector.  */
  62     return 0;
  63
  64   /* We must have run out of room.  */
  65   gcc_assert (alloc - num < (unsigned) reserve);
  66
  67   if (exact)
  68     /* Exact size.  */
  69     alloc = num + reserve;
  70   else
  71     {
  72       /* Exponential growth. */
  73       if (!alloc)
  74         alloc = 4;
  75       else if (alloc < 16)
  76         /* Double when small.  */
  77         alloc = alloc * 2;
  78       else
  79         /* Grow slower when large.  */
  80         alloc = (alloc * 3 / 2);
  81
  82       /* If this is still too small, set it to the right size. */
  83       if (alloc < num + reserve)
  84         alloc = num + reserve;
  85     }
  86   return alloc;
  87 }
  88
  89 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
  90    exactly, else grow exponentially.  As a special case, if VEC is
  91    NULL and RESERVE is 0, no vector will be created.  The vector's
  92    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
  93    sized elements.  */
  94
  95 static void *
  96 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
  97                     bool exact MEM_STAT_DECL)
  98 {
  99   struct vec_prefix *pfx = vec;
 100   unsigned alloc = alloc = calculate_allocation (pfx, reserve, exact);
 101
 102   if (!alloc)
 103     return NULL;
 104
 105   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 106   ((struct vec_prefix *)vec)->alloc = alloc;
 107   if (!pfx)
 108     ((struct vec_prefix *)vec)->num = 0;
 109
 110   return vec;
 111 }
 112
 113 /* Ensure there are at least RESERVE free slots in VEC, growing
 114    exponentially.  If RESERVE < 0 grow exactly, else grow
 115    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 116    0, no vector will be created. */
 117
 118 void *
 119 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 120 {
 121   return vec_gc_o_reserve_1 (vec, reserve,
 122                              offsetof (struct vec_prefix, vec),
 123                              sizeof (void *), false
 124                              PASS_MEM_STAT);
 125 }
 126
 127 /* Ensure there are at least RESERVE free slots in VEC, growing
 128    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 129    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 130    created. */
 131
 132 void *
 133 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 134 {
 135   return vec_gc_o_reserve_1 (vec, reserve,
 136                              offsetof (struct vec_prefix, vec),
 137                              sizeof (void *), true
 138                              PASS_MEM_STAT);
 139 }
 140
 141 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 142    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 143    sized elements.  */
 144
 145 void *
 146 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 147                   MEM_STAT_DECL)
 148 {
 149   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 150                              PASS_MEM_STAT);
 151 }
 152
 153 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 154    vector's trailing array is at VEC_OFFSET offset and consists of
 155    ELT_SIZE sized elements.  */
 156
 157 void *
 158 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 159                         size_t elt_size MEM_STAT_DECL)
 160 {
 161   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 162                              PASS_MEM_STAT);
 163 }
 164
 165 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 166
 167 static void *
 168 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 169                       size_t elt_size, bool exact MEM_STAT_DECL)
 170 {
 171   struct vec_prefix *pfx = vec;
 172   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 173
 174   if (!alloc)
 175     return NULL;
 176
 177   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 178   ((struct vec_prefix *)vec)->alloc = alloc;
 179   if (!pfx)
 180     ((struct vec_prefix *)vec)->num = 0;
 181
 182   return vec;
 183 }
 184
 185 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 186
 187 void *
 188 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 189 {
 190   return vec_heap_o_reserve_1 (vec, reserve,
 191                                offsetof (struct vec_prefix, vec),
 192                                sizeof (void *), false
 193                                PASS_MEM_STAT);
 194 }
 195
 196 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 197
 198 void *
 199 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 200 {
 201   return vec_heap_o_reserve_1 (vec, reserve,
 202                                offsetof (struct vec_prefix, vec),
 203                                sizeof (void *), true
 204                                PASS_MEM_STAT);
 205 }
 206
 207 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 208
 209 void *
 210 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 211                     MEM_STAT_DECL)
 212 {
 213   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 214                                PASS_MEM_STAT);
 215 }
 216
 217 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 218
 219 void *
 220 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 221                           size_t elt_size MEM_STAT_DECL)
 222 {
 223   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 224                                PASS_MEM_STAT);
 225 }
 226
 227 #if ENABLE_CHECKING
 228 /* Issue a vector domain error, and then fall over.  */
 229
 230 void
 231 vec_assert_fail (const char *op, const char *struct_name,
 232                  const char *file, unsigned int line, const char *function)
 233 {
 234   internal_error ("vector %s %s domain error, in %s at %s:%u",
 235                   struct_name, op, function, trim_filename (file), line);
 236 }
 237 #endif