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 "toplev.h"
  34
  35 struct vec_prefix
  36 {
  37   unsigned num;
  38   unsigned alloc;
  39   void *vec[1];
  40 };
  41
  42 /* Calculate the new ALLOC value, making sure that RESERVE slots are
  43    free.  If EXACT grow exactly, otherwise grow exponentially.  */
  44
  45 static inline unsigned
  46 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
  47 {
  48   unsigned alloc = 0;
  49   unsigned num = 0;
  50
  51   gcc_assert (reserve >= 0);
  52
  53   if (pfx)
  54     {
  55       alloc = pfx->alloc;
  56       num = pfx->num;
  57     }
  58   else if (!reserve)
  59     /* If there's no prefix, and we've not requested anything, then we
  60        will create a NULL vector.  */
  61     return 0;
  62
  63   /* We must have run out of room.  */
  64   gcc_assert (alloc - num < (unsigned) reserve);
  65
  66   if (exact)
  67     /* Exact size.  */
  68     alloc = num + reserve;
  69   else
  70     {
  71       /* Exponential growth. */
  72       if (!alloc)
  73         alloc = 4;
  74       else if (alloc < 16)
  75         /* Double when small.  */
  76         alloc = alloc * 2;
  77       else
  78         /* Grow slower when large.  */
  79         alloc = (alloc * 3 / 2);
  80
  81       /* If this is still too small, set it to the right size. */
  82       if (alloc < num + reserve)
  83         alloc = num + reserve;
  84     }
  85   return alloc;
  86 }
  87
  88 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
  89    exactly, else grow exponentially.  As a special case, if VEC is
  90    NULL and RESERVE is 0, no vector will be created.  The vector's
  91    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
  92    sized elements.  */
  93
  94 static void *
  95 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
  96                     bool exact MEM_STAT_DECL)
  97 {
  98   struct vec_prefix *pfx = vec;
  99   unsigned alloc = alloc = calculate_allocation (pfx, reserve, exact);
 100
 101   if (!alloc)
 102     return NULL;
 103
 104   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 105   ((struct vec_prefix *)vec)->alloc = alloc;
 106   if (!pfx)
 107     ((struct vec_prefix *)vec)->num = 0;
 108
 109   return vec;
 110 }
 111
 112 /* Ensure there are at least RESERVE free slots in VEC, growing
 113    exponentially.  If RESERVE < 0 grow exactly, else grow
 114    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 115    0, no vector will be created. */
 116
 117 void *
 118 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 119 {
 120   return vec_gc_o_reserve_1 (vec, reserve,
 121                              offsetof (struct vec_prefix, vec),
 122                              sizeof (void *), false
 123                              PASS_MEM_STAT);
 124 }
 125
 126 /* Ensure there are at least RESERVE free slots in VEC, growing
 127    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 128    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 129    created. */
 130
 131 void *
 132 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 133 {
 134   return vec_gc_o_reserve_1 (vec, reserve,
 135                              offsetof (struct vec_prefix, vec),
 136                              sizeof (void *), true
 137                              PASS_MEM_STAT);
 138 }
 139
 140 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 141    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 142    sized elements.  */
 143
 144 void *
 145 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 146                   MEM_STAT_DECL)
 147 {
 148   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 149                              PASS_MEM_STAT);
 150 }
 151
 152 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 153    vector's trailing array is at VEC_OFFSET offset and consists of
 154    ELT_SIZE sized elements.  */
 155
 156 void *
 157 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 158                         size_t elt_size MEM_STAT_DECL)
 159 {
 160   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 161                              PASS_MEM_STAT);
 162 }
 163
 164 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 165
 166 static void *
 167 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 168                       size_t elt_size, bool exact MEM_STAT_DECL)
 169 {
 170   struct vec_prefix *pfx = vec;
 171   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 172
 173   if (!alloc)
 174     return NULL;
 175
 176   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 177   ((struct vec_prefix *)vec)->alloc = alloc;
 178   if (!pfx)
 179     ((struct vec_prefix *)vec)->num = 0;
 180
 181   return vec;
 182 }
 183
 184 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 185
 186 void *
 187 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 188 {
 189   return vec_heap_o_reserve_1 (vec, reserve,
 190                                offsetof (struct vec_prefix, vec),
 191                                sizeof (void *), false
 192                                PASS_MEM_STAT);
 193 }
 194
 195 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 196
 197 void *
 198 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 199 {
 200   return vec_heap_o_reserve_1 (vec, reserve,
 201                                offsetof (struct vec_prefix, vec),
 202                                sizeof (void *), true
 203                                PASS_MEM_STAT);
 204 }
 205
 206 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 207
 208 void *
 209 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 210                     MEM_STAT_DECL)
 211 {
 212   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 213                                PASS_MEM_STAT);
 214 }
 215
 216 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 217
 218 void *
 219 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 220                           size_t elt_size MEM_STAT_DECL)
 221 {
 222   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 223                                PASS_MEM_STAT);
 224 }
 225
 226 #if ENABLE_CHECKING
 227 /* Issue a vector domain error, and then fall over.  */
 228
 229 void
 230 vec_assert_fail (const char *op, const char *struct_name,
 231                  const char *file, unsigned int line, const char *function)
 232 {
 233   internal_error ("vector %s %s domain error, in %s at %s:%u",
 234                   struct_name, op, function, trim_filename (file), line);
 235 }
 236 #endif