gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "ggc.h"
  25 #include "vec.h"
  26 #include "errors.h"
  27 #include "coretypes.h"
  28 #include "tree.h"
  29
  30 struct vec_prefix
  31 {
  32   unsigned num;
  33   unsigned alloc;
  34   void *vec[1];
  35 };
  36
  37 /* Calculate the new ALLOC value, making sure that abs(RESERVE) slots
  38    are free.  If RESERVE < 0 grow exactly, otherwise grow
  39    exponentially.  */
  40
  41 static inline unsigned
  42 calculate_allocation (const struct vec_prefix *pfx, int reserve)
  43 {
  44   unsigned alloc = 0;
  45   unsigned num = 0;
  46
  47   if (pfx)
  48     {
  49       alloc = pfx->alloc;
  50       num = pfx->num;
  51     }
  52   else if (!reserve)
  53     /* If there's no prefix, and we've not requested anything, then we
  54        will create a NULL vector.  */
  55     return 0;
  56
  57   /* We must have run out of room.  */
  58   gcc_assert (alloc - num < (unsigned)(reserve < 0 ? -reserve : reserve));
  59
  60   if (reserve < 0)
  61     /* Exact size.  */
  62     alloc = num + -reserve;
  63   else
  64     {
  65       /* Exponential growth. */
  66       if (!alloc)
  67         alloc = 4;
  68       else if (alloc < 16)
  69         /* Double when small.  */
  70         alloc = alloc * 2;
  71       else
  72         /* Grow slower when large.  */
  73         alloc = (alloc * 3 / 2);
  74
  75       /* If this is still too small, set it to the right size. */
  76       if (alloc < num + reserve)
  77         alloc = num + reserve;
  78     }
  79   return alloc;
  80 }
  81
  82 /* Ensure there are at least abs(RESERVE) free slots in VEC.  If
  83    RESERVE < 0 grow exactly, else grow exponentially.  As a special
  84    case, if VEC is NULL, and RESERVE is 0, no vector will be created. */
  85
  86 void *
  87 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
  88 {
  89   return vec_gc_o_reserve (vec, reserve,
  90                            offsetof (struct vec_prefix, vec), sizeof (void *)
  91                            PASS_MEM_STAT);
  92 }
  93
  94 /* As vec_gc_p_reserve, but for object vectors.  The vector's trailing
  95    array is at VEC_OFFSET offset and consists of ELT_SIZE sized
  96    elements.  */
  97
  98 void *
  99 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 100                    MEM_STAT_DECL)
 101 {
 102   struct vec_prefix *pfx = vec;
 103   unsigned alloc = alloc = calculate_allocation (pfx, reserve);
 104
 105   if (!alloc)
 106     return NULL;
 107
 108   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 109   ((struct vec_prefix *)vec)->alloc = alloc;
 110   if (!pfx)
 111     ((struct vec_prefix *)vec)->num = 0;
 112
 113   return vec;
 114 }
 115
 116 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 117
 118 void *
 119 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 120 {
 121   return vec_heap_o_reserve (vec, reserve,
 122                              offsetof (struct vec_prefix, vec), sizeof (void *)
 123                              PASS_MEM_STAT);
 124 }
 125
 126 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 127
 128 void *
 129 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 130                     MEM_STAT_DECL)
 131 {
 132   struct vec_prefix *pfx = vec;
 133   unsigned alloc = calculate_allocation (pfx, reserve);
 134
 135   if (!alloc)
 136     return NULL;
 137
 138   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 139   ((struct vec_prefix *)vec)->alloc = alloc;
 140   if (!pfx)
 141     ((struct vec_prefix *)vec)->num = 0;
 142
 143   return vec;
 144 }
 145
 146 #if ENABLE_CHECKING
 147 /* Issue a vector domain error, and then fall over.  */
 148
 149 void
 150 vec_assert_fail (const char *op, const char *struct_name,
 151                  const char *file, unsigned int line, const char *function)
 152 {
 153   internal_error ("vector %s %s domain error, in %s at %s:%u",
 154                   struct_name, op, function, trim_filename (file), line);
 155 }
 156 #endif