contrib/gcc/vec.c

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