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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-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
37struct 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
47static inline unsigned
48calculate_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
96static void *
97vec_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
119void *
120vec_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
133void *
134vec_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
146void *
147vec_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
158void *
159vec_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
168static void *
169vec_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
188void *
189vec_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
199void *
200vec_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
210void *
211vec_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
220void *
221vec_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
231void
232vec_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
239