?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
make __stl_prime_list in comdat
[official-gcc.git] / gcc / vec.h
blob789e8e2d4df6444cf89d2b3dbbbd276ce32f5dba
1 /* Vector API for GNU compiler.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Nathan Sidwell <nathan@codesourcery.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #ifndef GCC_VEC_H
23 #define GCC_VEC_H
24
25 #include "statistics.h" /* For MEM_STAT_DECL. */
26
27 /* The macros here implement a set of templated vector types and
28 associated interfaces. These templates are implemented with
29 macros, as we're not in C++ land. The interface functions are
30 typesafe and use static inline functions, sometimes backed by
31 out-of-line generic functions. The vectors are designed to
32 interoperate with the GTY machinery.
33
34 Because of the different behavior of structure objects, scalar
35 objects and of pointers, there are three flavors, one for each of
36 these variants. Both the structure object and pointer variants
37 pass pointers to objects around -- in the former case the pointers
38 are stored into the vector and in the latter case the pointers are
39 dereferenced and the objects copied into the vector. The scalar
40 object variant is suitable for int-like objects, and the vector
41 elements are returned by value.
42
43 There are both 'index' and 'iterate' accessors. The iterator
44 returns a boolean iteration condition and updates the iteration
45 variable passed by reference. Because the iterator will be
46 inlined, the address-of can be optimized away.
47
48 The vectors are implemented using the trailing array idiom, thus
49 they are not resizeable without changing the address of the vector
50 object itself. This means you cannot have variables or fields of
51 vector type -- always use a pointer to a vector. The one exception
52 is the final field of a structure, which could be a vector type.
53 You will have to use the embedded_size & embedded_init calls to
54 create such objects, and they will probably not be resizeable (so
55 don't use the 'safe' allocation variants). The trailing array
56 idiom is used (rather than a pointer to an array of data), because,
57 if we allow NULL to also represent an empty vector, empty vectors
58 occupy minimal space in the structure containing them.
59
60 Each operation that increases the number of active elements is
61 available in 'quick' and 'safe' variants. The former presumes that
62 there is sufficient allocated space for the operation to succeed
63 (it dies if there is not). The latter will reallocate the
64 vector, if needed. Reallocation causes an exponential increase in
65 vector size. If you know you will be adding N elements, it would
66 be more efficient to use the reserve operation before adding the
67 elements with the 'quick' operation. This will ensure there are at
68 least as many elements as you ask for, it will exponentially
69 increase if there are too few spare slots. If you want reserve a
70 specific number of slots, but do not want the exponential increase
71 (for instance, you know this is the last allocation), use the
72 reserve_exact operation. You can also create a vector of a
73 specific size from the get go.
74
75 You should prefer the push and pop operations, as they append and
76 remove from the end of the vector. If you need to remove several
77 items in one go, use the truncate operation. The insert and remove
78 operations allow you to change elements in the middle of the
79 vector. There are two remove operations, one which preserves the
80 element ordering 'ordered_remove', and one which does not
81 'unordered_remove'. The latter function copies the end element
82 into the removed slot, rather than invoke a memmove operation. The
83 'lower_bound' function will determine where to place an item in the
84 array using insert that will maintain sorted order.
85
86 When a vector type is defined, first a non-memory managed version
87 is created. You can then define either or both garbage collected
88 and heap allocated versions. The allocation mechanism is specified
89 when the type is defined, and is therefore part of the type. If
90 you need both gc'd and heap allocated versions, you still must have
91 *exactly* one definition of the common non-memory managed base vector.
92
93 If you need to directly manipulate a vector, then the 'address'
94 accessor will return the address of the start of the vector. Also
95 the 'space' predicate will tell you whether there is spare capacity
96 in the vector. You will not normally need to use these two functions.
97
98 Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to
99 get the non-memory allocation version, and then a
100 DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed
101 vectors. Variables of vector type are declared using a
102 VEC(TYPEDEF,ALLOC) macro. The ALLOC argument specifies the
103 allocation strategy, and can be either 'gc' or 'heap' for garbage
104 collected and heap allocated respectively. It can be 'none' to get
105 a vector that must be explicitly allocated (for instance as a
106 trailing array of another structure). The characters O, P and I
107 indicate whether TYPEDEF is a pointer (P), object (O) or integral
108 (I) type. Be careful to pick the correct one, as you'll get an
109 awkward and inefficient API if you use the wrong one. There is a
110 check, which results in a compile-time warning, for the P and I
111 versions, but there is no check for the O versions, as that is not
112 possible in plain C. Due to the way GTY works, you must annotate
113 any structures you wish to insert or reference from a vector with a
114 GTY(()) tag. You need to do this even if you never declare the GC
115 allocated variants.
116
117 An example of their use would be,
118
119 DEF_VEC_P(tree); // non-managed tree vector.
120 DEF_VEC_ALLOC_P(tree,gc); // gc'd vector of tree pointers. This must
121 // appear at file scope.
122
123 struct my_struct {
124 VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers.
125 };
126
127 struct my_struct *s;
128
129 if (VEC_length(tree,s->v)) { we have some contents }
130 VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
131 for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
132 { do something with elt }
133
134 */
135
136 /* Macros to invoke API calls. A single macro works for both pointer
137 and object vectors, but the argument and return types might well be
138 different. In each macro, T is the typedef of the vector elements,
139 and A is the allocation strategy. The allocation strategy is only
140 present when it is required. Some of these macros pass the vector,
141 V, by reference (by taking its address), this is noted in the
142 descriptions. */
143
144 /* Length of vector
145 unsigned VEC_T_length(const VEC(T) *v);
146
147 Return the number of active elements in V. V can be NULL, in which
148 case zero is returned. */
149
150 #define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
151
152
153 /* Check if vector is empty
154 int VEC_T_empty(const VEC(T) *v);
155
156 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
157
158 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
159
160
161 /* Get the final element of the vector.
162 T VEC_T_last(VEC(T) *v); // Integer
163 T VEC_T_last(VEC(T) *v); // Pointer
164 T *VEC_T_last(VEC(T) *v); // Object
165
166 Return the final element. V must not be empty. */
167
168 #define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
169
170 /* Index into vector
171 T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
172 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
173 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
174
175 Return the IX'th element. If IX must be in the domain of V. */
176
177 #define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
178
179 /* Iterate over vector
180 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
181 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
182 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
183
184 Return iteration condition and update PTR to point to the IX'th
185 element. At the end of iteration, sets PTR to NULL. Use this to
186 iterate over the elements of a vector as follows,
187
188 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
189 continue; */
190
191 #define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
192
193 /* Convenience macro for forward iteration. */
194
195 #define FOR_EACH_VEC_ELT(T, V, I, P) \
196 for (I = 0; VEC_iterate (T, (V), (I), (P)); ++(I))
197
198 /* Likewise, but start from FROM rather than 0. */
199
200 #define FOR_EACH_VEC_ELT_FROM(T, V, I, P, FROM) \
201 for (I = (FROM); VEC_iterate (T, (V), (I), (P)); ++(I))
202
203 /* Convenience macro for reverse iteration. */
204
205 #define FOR_EACH_VEC_ELT_REVERSE(T,V,I,P) \
206 for (I = VEC_length (T, (V)) - 1; \
207 VEC_iterate (T, (V), (I), (P)); \
208 (I)--)
209
210 /* Allocate new vector.
211 VEC(T,A) *VEC_T_A_alloc(int reserve);
212
213 Allocate a new vector with space for RESERVE objects. If RESERVE
214 is zero, NO vector is created. */
215
216 #define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
217
218 /* Free a vector.
219 void VEC_T_A_free(VEC(T,A) *&);
220
221 Free a vector and set it to NULL. */
222
223 #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
224
225 /* Use these to determine the required size and initialization of a
226 vector embedded within another structure (as the final member).
227
228 size_t VEC_T_embedded_size(int reserve);
229 void VEC_T_embedded_init(VEC(T) *v, int reserve);
230
231 These allow the caller to perform the memory allocation. */
232
233 #define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N))
234 #define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
235
236 /* Copy a vector.
237 VEC(T,A) *VEC_T_A_copy(VEC(T) *);
238
239 Copy the live elements of a vector into a new vector. The new and
240 old vectors need not be allocated by the same mechanism. */
241
242 #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
243
244 /* Determine if a vector has additional capacity.
245
246 int VEC_T_space (VEC(T) *v,int reserve)
247
248 If V has space for RESERVE additional entries, return nonzero. You
249 usually only need to use this if you are doing your own vector
250 reallocation, for instance on an embedded vector. This returns
251 nonzero in exactly the same circumstances that VEC_T_reserve
252 will. */
253
254 #define VEC_space(T,V,R) \
255 (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
256
257 /* Reserve space.
258 int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
259
260 Ensure that V has at least RESERVE slots available. This will
261 create additional headroom. Note this can cause V to be
262 reallocated. Returns nonzero iff reallocation actually
263 occurred. */
264
265 #define VEC_reserve(T,A,V,R) \
266 (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
267
268 /* Reserve space exactly.
269 int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
270
271 Ensure that V has at least RESERVE slots available. This will not
272 create additional headroom. Note this can cause V to be
273 reallocated. Returns nonzero iff reallocation actually
274 occurred. */
275
276 #define VEC_reserve_exact(T,A,V,R) \
277 (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
278
279 /* Copy elements with no reallocation
280 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
281 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Pointer
282 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Object
283
284 Copy the elements in SRC to the end of DST as if by memcpy. DST and
285 SRC need not be allocated with the same mechanism, although they most
286 often will be. DST is assumed to have sufficient headroom
287 available. */
288
289 #define VEC_splice(T,DST,SRC) \
290 (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
291
292 /* Copy elements with reallocation
293 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
294 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Pointer
295 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Object
296
297 Copy the elements in SRC to the end of DST as if by memcpy. DST and
298 SRC need not be allocated with the same mechanism, although they most
299 often will be. DST need not have sufficient headroom and will be
300 reallocated if needed. */
301
302 #define VEC_safe_splice(T,A,DST,SRC) \
303 (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO))
304
305 /* Push object with no reallocation
306 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
307 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
308 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
309
310 Push a new element onto the end, returns a pointer to the slot
311 filled in. For object vectors, the new value can be NULL, in which
312 case NO initialization is performed. There must
313 be sufficient space in the vector. */
314
315 #define VEC_quick_push(T,V,O) \
316 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
317
318 /* Push object with reallocation
319 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
320 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
321 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
322
323 Push a new element onto the end, returns a pointer to the slot
324 filled in. For object vectors, the new value can be NULL, in which
325 case NO initialization is performed. Reallocates V, if needed. */
326
327 #define VEC_safe_push(T,A,V,O) \
328 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
329
330 /* Pop element off end
331 T VEC_T_pop (VEC(T) *v); // Integer
332 T VEC_T_pop (VEC(T) *v); // Pointer
333 void VEC_T_pop (VEC(T) *v); // Object
334
335 Pop the last element off the end. Returns the element popped, for
336 pointer vectors. */
337
338 #define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
339
340 /* Truncate to specific length
341 void VEC_T_truncate (VEC(T) *v, unsigned len);
342
343 Set the length as specified. The new length must be less than or
344 equal to the current length. This is an O(1) operation. */
345
346 #define VEC_truncate(T,V,I) \
347 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
348
349 /* Grow to a specific length.
350 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
351
352 Grow the vector to a specific length. The LEN must be as
353 long or longer than the current length. The new elements are
354 uninitialized. */
355
356 #define VEC_safe_grow(T,A,V,I) \
357 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
358
359 /* Grow to a specific length.
360 void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
361
362 Grow the vector to a specific length. The LEN must be as
363 long or longer than the current length. The new elements are
364 initialized to zero. */
365
366 #define VEC_safe_grow_cleared(T,A,V,I) \
367 (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
368
369 /* Replace element
370 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
371 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
372 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
373
374 Replace the IXth element of V with a new value, VAL. For pointer
375 vectors returns the original value. For object vectors returns a
376 pointer to the new value. For object vectors the new value can be
377 NULL, in which case no overwriting of the slot is actually
378 performed. */
379
380 #define VEC_replace(T,V,I,O) \
381 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
382
383 /* Insert object with no reallocation
384 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
385 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
386 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
387
388 Insert an element, VAL, at the IXth position of V. Return a pointer
389 to the slot created. For vectors of object, the new value can be
390 NULL, in which case no initialization of the inserted slot takes
391 place. There must be sufficient space. */
392
393 #define VEC_quick_insert(T,V,I,O) \
394 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
395
396 /* Insert object with reallocation
397 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
398 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
399 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
400
401 Insert an element, VAL, at the IXth position of V. Return a pointer
402 to the slot created. For vectors of object, the new value can be
403 NULL, in which case no initialization of the inserted slot takes
404 place. Reallocate V, if necessary. */
405
406 #define VEC_safe_insert(T,A,V,I,O) \
407 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
408
409 /* Remove element retaining order
410 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
411 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
412 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
413
414 Remove an element from the IXth position of V. Ordering of
415 remaining elements is preserved. For pointer vectors returns the
416 removed object. This is an O(N) operation due to a memmove. */
417
418 #define VEC_ordered_remove(T,V,I) \
419 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
420
421 /* Remove element destroying order
422 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
423 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
424 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
425
426 Remove an element from the IXth position of V. Ordering of
427 remaining elements is destroyed. For pointer vectors returns the
428 removed object. This is an O(1) operation. */
429
430 #define VEC_unordered_remove(T,V,I) \
431 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
432
433 /* Remove a block of elements
434 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
435
436 Remove LEN elements starting at the IXth. Ordering is retained.
437 This is an O(N) operation due to memmove. */
438
439 #define VEC_block_remove(T,V,I,L) \
440 (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
441
442 /* Get the address of the array of elements
443 T *VEC_T_address (VEC(T) v)
444
445 If you need to directly manipulate the array (for instance, you
446 want to feed it to qsort), use this accessor. */
447
448 #define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
449
450 /* Conveniently sort the contents of the vector with qsort.
451 void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */
452
453 #define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V), \
454 sizeof (T), CMP)
455
456 /* Find the first index in the vector not less than the object.
457 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
458 bool (*lessthan) (const T, const T)); // Integer
459 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
460 bool (*lessthan) (const T, const T)); // Pointer
461 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
462 bool (*lessthan) (const T*, const T*)); // Object
463
464 Find the first position in which VAL could be inserted without
465 changing the ordering of V. LESSTHAN is a function that returns
466 true if the first argument is strictly less than the second. */
467
468 #define VEC_lower_bound(T,V,O,LT) \
469 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
470
471 /* Reallocate an array of elements with prefix. */
472 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
473 extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
474 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
475 extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
476 MEM_STAT_DECL);
477 extern void ggc_free (void *);
478 #define vec_gc_free(V) ggc_free (V)
479 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
480 extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
481 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
482 extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
483 MEM_STAT_DECL);
484 extern void dump_vec_loc_statistics (void);
485 #ifdef GATHER_STATISTICS
486 void vec_heap_free (void *);
487 #else
488 /* Avoid problems with frontends that #define free(x). */
489 #define vec_heap_free(V) (free) (V)
490 #endif
491
492 #if ENABLE_CHECKING
493 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
494 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
495 #define VEC_CHECK_PASS ,file_,line_,function_
496
497 #define VEC_ASSERT(EXPR,OP,T,A) \
498 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
499
500 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
501 ATTRIBUTE_NORETURN;
502 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
503 #else
504 #define VEC_CHECK_INFO
505 #define VEC_CHECK_DECL
506 #define VEC_CHECK_PASS
507 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
508 #endif
509
510 /* Note: gengtype has hardwired knowledge of the expansions of the
511 VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the
512 expansions of these macros you may need to change gengtype too. */
513
514 typedef struct GTY(()) vec_prefix
515 {
516 unsigned num;
517 unsigned alloc;
518 } vec_prefix;
519
520 #define VEC(T,A) VEC_##T##_##A
521 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
522
523 /* Base of vector type, not user visible. */
524 #define VEC_T(T,B) \
525 typedef struct VEC(T,B) \
526 { \
527 struct vec_prefix prefix; \
528 T vec[1]; \
529 } VEC(T,B)
530
531 #define VEC_T_GTY(T,B) \
532 typedef struct GTY(()) VEC(T,B) \
533 { \
534 struct vec_prefix prefix; \
535 T GTY ((length ("%h.prefix.num"))) vec[1]; \
536 } VEC(T,B)
537
538 /* Derived vector type, user visible. */
539 #define VEC_TA_GTY(T,B,A,GTY) \
540 typedef struct GTY VEC(T,A) \
541 { \
542 VEC(T,B) base; \
543 } VEC(T,A)
544
545 #define VEC_TA(T,B,A) \
546 typedef struct VEC(T,A) \
547 { \
548 VEC(T,B) base; \
549 } VEC(T,A)
550
551 /* Convert to base type. */
552 #define VEC_BASE(P) ((P) ? &(P)->base : 0)
553
554 /* Vector of integer-like object. */
555 #define DEF_VEC_I(T) \
556 static inline void VEC_OP (T,must_be,integral_type) (void) \
557 { \
558 (void)~(T)0; \
559 } \
560 \
561 VEC_T(T,base); \
562 VEC_TA(T,base,none); \
563 DEF_VEC_FUNC_P(T) \
564 struct vec_swallow_trailing_semi
565 #define DEF_VEC_ALLOC_I(T,A) \
566 VEC_TA(T,base,A); \
567 DEF_VEC_ALLOC_FUNC_I(T,A) \
568 DEF_VEC_NONALLOC_FUNCS_I(T,A) \
569 struct vec_swallow_trailing_semi
570
571 /* Vector of pointer to object. */
572 #define DEF_VEC_P(T) \
573 static inline void VEC_OP (T,must_be,pointer_type) (void) \
574 { \
575 (void)((T)1 == (void *)1); \
576 } \
577 \
578 VEC_T_GTY(T,base); \
579 VEC_TA(T,base,none); \
580 DEF_VEC_FUNC_P(T) \
581 struct vec_swallow_trailing_semi
582 #define DEF_VEC_ALLOC_P(T,A) \
583 VEC_TA(T,base,A); \
584 DEF_VEC_ALLOC_FUNC_P(T,A) \
585 DEF_VEC_NONALLOC_FUNCS_P(T,A) \
586 struct vec_swallow_trailing_semi
587
588 #define DEF_VEC_FUNC_P(T) \
589 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
590 { \
591 return vec_ ? vec_->prefix.num : 0; \
592 } \
593 \
594 static inline T VEC_OP (T,base,last) \
595 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
596 { \
597 VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
598 \
599 return vec_->vec[vec_->prefix.num - 1]; \
600 } \
601 \
602 static inline T VEC_OP (T,base,index) \
603 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
604 { \
605 VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
606 \
607 return vec_->vec[ix_]; \
608 } \
609 \
610 static inline int VEC_OP (T,base,iterate) \
611 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
612 { \
613 if (vec_ && ix_ < vec_->prefix.num) \
614 { \
615 *ptr = vec_->vec[ix_]; \
616 return 1; \
617 } \
618 else \
619 { \
620 *ptr = (T) 0; \
621 return 0; \
622 } \
623 } \
624 \
625 static inline size_t VEC_OP (T,base,embedded_size) \
626 (int alloc_) \
627 { \
628 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
629 } \
630 \
631 static inline void VEC_OP (T,base,embedded_init) \
632 (VEC(T,base) *vec_, int alloc_) \
633 { \
634 vec_->prefix.num = 0; \
635 vec_->prefix.alloc = alloc_; \
636 } \
637 \
638 static inline int VEC_OP (T,base,space) \
639 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
640 { \
641 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
642 return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
643 } \
644 \
645 static inline void VEC_OP(T,base,splice) \
646 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
647 { \
648 if (src_) \
649 { \
650 unsigned len_ = src_->prefix.num; \
651 VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
652 \
653 memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
654 dst_->prefix.num += len_; \
655 } \
656 } \
657 \
658 static inline T *VEC_OP (T,base,quick_push) \
659 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
660 { \
661 T *slot_; \
662 \
663 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
664 slot_ = &vec_->vec[vec_->prefix.num++]; \
665 *slot_ = obj_; \
666 \
667 return slot_; \
668 } \
669 \
670 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
671 { \
672 T obj_; \
673 \
674 VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
675 obj_ = vec_->vec[--vec_->prefix.num]; \
676 \
677 return obj_; \
678 } \
679 \
680 static inline void VEC_OP (T,base,truncate) \
681 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
682 { \
683 VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
684 if (vec_) \
685 vec_->prefix.num = size_; \
686 } \
687 \
688 static inline T VEC_OP (T,base,replace) \
689 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
690 { \
691 T old_obj_; \
692 \
693 VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
694 old_obj_ = vec_->vec[ix_]; \
695 vec_->vec[ix_] = obj_; \
696 \
697 return old_obj_; \
698 } \
699 \
700 static inline T *VEC_OP (T,base,quick_insert) \
701 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
702 { \
703 T *slot_; \
704 \
705 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
706 VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
707 slot_ = &vec_->vec[ix_]; \
708 memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
709 *slot_ = obj_; \
710 \
711 return slot_; \
712 } \
713 \
714 static inline T VEC_OP (T,base,ordered_remove) \
715 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
716 { \
717 T *slot_; \
718 T obj_; \
719 \
720 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
721 slot_ = &vec_->vec[ix_]; \
722 obj_ = *slot_; \
723 memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
724 \
725 return obj_; \
726 } \
727 \
728 static inline T VEC_OP (T,base,unordered_remove) \
729 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
730 { \
731 T *slot_; \
732 T obj_; \
733 \
734 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
735 slot_ = &vec_->vec[ix_]; \
736 obj_ = *slot_; \
737 *slot_ = vec_->vec[--vec_->prefix.num]; \
738 \
739 return obj_; \
740 } \
741 \
742 static inline void VEC_OP (T,base,block_remove) \
743 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
744 { \
745 T *slot_; \
746 \
747 VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
748 slot_ = &vec_->vec[ix_]; \
749 vec_->prefix.num -= len_; \
750 memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
751 } \
752 \
753 static inline T *VEC_OP (T,base,address) \
754 (VEC(T,base) *vec_) \
755 { \
756 return vec_ ? vec_->vec : 0; \
757 } \
758 \
759 static inline unsigned VEC_OP (T,base,lower_bound) \
760 (VEC(T,base) *vec_, const T obj_, \
761 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
762 { \
763 unsigned int len_ = VEC_OP (T,base, length) (vec_); \
764 unsigned int half_, middle_; \
765 unsigned int first_ = 0; \
766 while (len_ > 0) \
767 { \
768 T middle_elem_; \
769 half_ = len_ >> 1; \
770 middle_ = first_; \
771 middle_ += half_; \
772 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
773 if (lessthan_ (middle_elem_, obj_)) \
774 { \
775 first_ = middle_; \
776 ++first_; \
777 len_ = len_ - half_ - 1; \
778 } \
779 else \
780 len_ = half_; \
781 } \
782 return first_; \
783 }
784
785 #define DEF_VEC_ALLOC_FUNC_P(T,A) \
786 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
787 (int alloc_ MEM_STAT_DECL) \
788 { \
789 return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
790 PASS_MEM_STAT); \
791 }
792
793
794 #define DEF_VEC_NONALLOC_FUNCS_P(T,A) \
795 static inline void VEC_OP (T,A,free) \
796 (VEC(T,A) **vec_) \
797 { \
798 if (*vec_) \
799 vec_##A##_free (*vec_); \
800 *vec_ = NULL; \
801 } \
802 \
803 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
804 { \
805 size_t len_ = vec_ ? vec_->prefix.num : 0; \
806 VEC (T,A) *new_vec_ = NULL; \
807 \
808 if (len_) \
809 { \
810 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
811 (NULL, len_ PASS_MEM_STAT)); \
812 \
813 new_vec_->base.prefix.num = len_; \
814 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
815 } \
816 return new_vec_; \
817 } \
818 \
819 static inline int VEC_OP (T,A,reserve) \
820 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
821 { \
822 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
823 VEC_CHECK_PASS); \
824 \
825 if (extend) \
826 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
827 \
828 return extend; \
829 } \
830 \
831 static inline int VEC_OP (T,A,reserve_exact) \
832 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
833 { \
834 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
835 VEC_CHECK_PASS); \
836 \
837 if (extend) \
838 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
839 PASS_MEM_STAT); \
840 \
841 return extend; \
842 } \
843 \
844 static inline void VEC_OP (T,A,safe_grow) \
845 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
846 { \
847 VEC_ASSERT (size_ >= 0 \
848 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
849 "grow", T, A); \
850 VEC_OP (T,A,reserve_exact) (vec_, \
851 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
852 VEC_CHECK_PASS PASS_MEM_STAT); \
853 VEC_BASE (*vec_)->prefix.num = size_; \
854 } \
855 \
856 static inline void VEC_OP (T,A,safe_grow_cleared) \
857 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
858 { \
859 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
860 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
861 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
862 sizeof (T) * (size_ - oldsize)); \
863 } \
864 \
865 static inline void VEC_OP(T,A,safe_splice) \
866 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
867 { \
868 if (src_) \
869 { \
870 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
871 VEC_CHECK_PASS MEM_STAT_INFO); \
872 \
873 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
874 VEC_CHECK_PASS); \
875 } \
876 } \
877 \
878 static inline T *VEC_OP (T,A,safe_push) \
879 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
880 { \
881 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
882 \
883 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
884 } \
885 \
886 static inline T *VEC_OP (T,A,safe_insert) \
887 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
888 { \
889 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
890 \
891 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
892 VEC_CHECK_PASS); \
893 }
894
895 /* Vector of object. */
896 #define DEF_VEC_O(T) \
897 VEC_T_GTY(T,base); \
898 VEC_TA(T,base,none); \
899 DEF_VEC_FUNC_O(T) \
900 struct vec_swallow_trailing_semi
901 #define DEF_VEC_ALLOC_O(T,A) \
902 VEC_TA(T,base,A); \
903 DEF_VEC_ALLOC_FUNC_O(T,A) \
904 DEF_VEC_NONALLOC_FUNCS_O(T,A) \
905 struct vec_swallow_trailing_semi
906
907 #define DEF_VEC_FUNC_O(T) \
908 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
909 { \
910 return vec_ ? vec_->prefix.num : 0; \
911 } \
912 \
913 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
914 { \
915 VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
916 \
917 return &vec_->vec[vec_->prefix.num - 1]; \
918 } \
919 \
920 static inline T *VEC_OP (T,base,index) \
921 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
922 { \
923 VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
924 \
925 return &vec_->vec[ix_]; \
926 } \
927 \
928 static inline int VEC_OP (T,base,iterate) \
929 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
930 { \
931 if (vec_ && ix_ < vec_->prefix.num) \
932 { \
933 *ptr = &vec_->vec[ix_]; \
934 return 1; \
935 } \
936 else \
937 { \
938 *ptr = 0; \
939 return 0; \
940 } \
941 } \
942 \
943 static inline size_t VEC_OP (T,base,embedded_size) \
944 (int alloc_) \
945 { \
946 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
947 } \
948 \
949 static inline void VEC_OP (T,base,embedded_init) \
950 (VEC(T,base) *vec_, int alloc_) \
951 { \
952 vec_->prefix.num = 0; \
953 vec_->prefix.alloc = alloc_; \
954 } \
955 \
956 static inline int VEC_OP (T,base,space) \
957 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
958 { \
959 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
960 return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
961 } \
962 \
963 static inline void VEC_OP(T,base,splice) \
964 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
965 { \
966 if (src_) \
967 { \
968 unsigned len_ = src_->prefix.num; \
969 VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
970 \
971 memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
972 dst_->prefix.num += len_; \
973 } \
974 } \
975 \
976 static inline T *VEC_OP (T,base,quick_push) \
977 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
978 { \
979 T *slot_; \
980 \
981 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
982 slot_ = &vec_->vec[vec_->prefix.num++]; \
983 if (obj_) \
984 *slot_ = *obj_; \
985 \
986 return slot_; \
987 } \
988 \
989 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
990 { \
991 VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
992 --vec_->prefix.num; \
993 } \
994 \
995 static inline void VEC_OP (T,base,truncate) \
996 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
997 { \
998 VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
999 if (vec_) \
1000 vec_->prefix.num = size_; \
1001 } \
1002 \
1003 static inline T *VEC_OP (T,base,replace) \
1004 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
1005 { \
1006 T *slot_; \
1007 \
1008 VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
1009 slot_ = &vec_->vec[ix_]; \
1010 if (obj_) \
1011 *slot_ = *obj_; \
1012 \
1013 return slot_; \
1014 } \
1015 \
1016 static inline T *VEC_OP (T,base,quick_insert) \
1017 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
1018 { \
1019 T *slot_; \
1020 \
1021 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
1022 VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
1023 slot_ = &vec_->vec[ix_]; \
1024 memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
1025 if (obj_) \
1026 *slot_ = *obj_; \
1027 \
1028 return slot_; \
1029 } \
1030 \
1031 static inline void VEC_OP (T,base,ordered_remove) \
1032 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1033 { \
1034 T *slot_; \
1035 \
1036 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
1037 slot_ = &vec_->vec[ix_]; \
1038 memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
1039 } \
1040 \
1041 static inline void VEC_OP (T,base,unordered_remove) \
1042 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1043 { \
1044 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
1045 vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \
1046 } \
1047 \
1048 static inline void VEC_OP (T,base,block_remove) \
1049 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
1050 { \
1051 T *slot_; \
1052 \
1053 VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
1054 slot_ = &vec_->vec[ix_]; \
1055 vec_->prefix.num -= len_; \
1056 memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
1057 } \
1058 \
1059 static inline T *VEC_OP (T,base,address) \
1060 (VEC(T,base) *vec_) \
1061 { \
1062 return vec_ ? vec_->vec : 0; \
1063 } \
1064 \
1065 static inline unsigned VEC_OP (T,base,lower_bound) \
1066 (VEC(T,base) *vec_, const T *obj_, \
1067 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
1068 { \
1069 unsigned int len_ = VEC_OP (T, base, length) (vec_); \
1070 unsigned int half_, middle_; \
1071 unsigned int first_ = 0; \
1072 while (len_ > 0) \
1073 { \
1074 T *middle_elem_; \
1075 half_ = len_ >> 1; \
1076 middle_ = first_; \
1077 middle_ += half_; \
1078 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
1079 if (lessthan_ (middle_elem_, obj_)) \
1080 { \
1081 first_ = middle_; \
1082 ++first_; \
1083 len_ = len_ - half_ - 1; \
1084 } \
1085 else \
1086 len_ = half_; \
1087 } \
1088 return first_; \
1089 }
1090
1091 #define DEF_VEC_ALLOC_FUNC_O(T,A) \
1092 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1093 (int alloc_ MEM_STAT_DECL) \
1094 { \
1095 return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
1096 offsetof (VEC(T,A),base.vec), \
1097 sizeof (T) \
1098 PASS_MEM_STAT); \
1099 }
1100
1101 #define DEF_VEC_NONALLOC_FUNCS_O(T,A) \
1102 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1103 { \
1104 size_t len_ = vec_ ? vec_->prefix.num : 0; \
1105 VEC (T,A) *new_vec_ = NULL; \
1106 \
1107 if (len_) \
1108 { \
1109 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1110 (NULL, len_, \
1111 offsetof (VEC(T,A),base.vec), sizeof (T) \
1112 PASS_MEM_STAT)); \
1113 \
1114 new_vec_->base.prefix.num = len_; \
1115 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1116 } \
1117 return new_vec_; \
1118 } \
1119 \
1120 static inline void VEC_OP (T,A,free) \
1121 (VEC(T,A) **vec_) \
1122 { \
1123 if (*vec_) \
1124 vec_##A##_free (*vec_); \
1125 *vec_ = NULL; \
1126 } \
1127 \
1128 static inline int VEC_OP (T,A,reserve) \
1129 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1130 { \
1131 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1132 VEC_CHECK_PASS); \
1133 \
1134 if (extend) \
1135 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1136 offsetof (VEC(T,A),base.vec),\
1137 sizeof (T) \
1138 PASS_MEM_STAT); \
1139 \
1140 return extend; \
1141 } \
1142 \
1143 static inline int VEC_OP (T,A,reserve_exact) \
1144 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1145 { \
1146 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1147 VEC_CHECK_PASS); \
1148 \
1149 if (extend) \
1150 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1151 (*vec_, alloc_, \
1152 offsetof (VEC(T,A),base.vec), \
1153 sizeof (T) PASS_MEM_STAT); \
1154 \
1155 return extend; \
1156 } \
1157 \
1158 static inline void VEC_OP (T,A,safe_grow) \
1159 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1160 { \
1161 VEC_ASSERT (size_ >= 0 \
1162 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1163 "grow", T, A); \
1164 VEC_OP (T,A,reserve_exact) (vec_, \
1165 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
1166 VEC_CHECK_PASS PASS_MEM_STAT); \
1167 VEC_BASE (*vec_)->prefix.num = size_; \
1168 } \
1169 \
1170 static inline void VEC_OP (T,A,safe_grow_cleared) \
1171 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1172 { \
1173 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1174 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1175 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1176 sizeof (T) * (size_ - oldsize)); \
1177 } \
1178 \
1179 static inline void VEC_OP(T,A,safe_splice) \
1180 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1181 { \
1182 if (src_) \
1183 { \
1184 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
1185 VEC_CHECK_PASS MEM_STAT_INFO); \
1186 \
1187 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1188 VEC_CHECK_PASS); \
1189 } \
1190 } \
1191 \
1192 static inline T *VEC_OP (T,A,safe_push) \
1193 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1194 { \
1195 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1196 \
1197 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1198 } \
1199 \
1200 static inline T *VEC_OP (T,A,safe_insert) \
1201 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
1202 VEC_CHECK_DECL MEM_STAT_DECL) \
1203 { \
1204 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1205 \
1206 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1207 VEC_CHECK_PASS); \
1208 }
1209
1210 #define DEF_VEC_ALLOC_FUNC_I(T,A) \
1211 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1212 (int alloc_ MEM_STAT_DECL) \
1213 { \
1214 return (VEC(T,A) *) vec_##A##_o_reserve_exact \
1215 (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
1216 sizeof (T) PASS_MEM_STAT); \
1217 }
1218
1219 #define DEF_VEC_NONALLOC_FUNCS_I(T,A) \
1220 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1221 { \
1222 size_t len_ = vec_ ? vec_->prefix.num : 0; \
1223 VEC (T,A) *new_vec_ = NULL; \
1224 \
1225 if (len_) \
1226 { \
1227 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1228 (NULL, len_, \
1229 offsetof (VEC(T,A),base.vec), sizeof (T) \
1230 PASS_MEM_STAT)); \
1231 \
1232 new_vec_->base.prefix.num = len_; \
1233 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1234 } \
1235 return new_vec_; \
1236 } \
1237 \
1238 static inline void VEC_OP (T,A,free) \
1239 (VEC(T,A) **vec_) \
1240 { \
1241 if (*vec_) \
1242 vec_##A##_free (*vec_); \
1243 *vec_ = NULL; \
1244 } \
1245 \
1246 static inline int VEC_OP (T,A,reserve) \
1247 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1248 { \
1249 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1250 VEC_CHECK_PASS); \
1251 \
1252 if (extend) \
1253 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1254 offsetof (VEC(T,A),base.vec),\
1255 sizeof (T) \
1256 PASS_MEM_STAT); \
1257 \
1258 return extend; \
1259 } \
1260 \
1261 static inline int VEC_OP (T,A,reserve_exact) \
1262 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1263 { \
1264 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1265 VEC_CHECK_PASS); \
1266 \
1267 if (extend) \
1268 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1269 (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
1270 sizeof (T) PASS_MEM_STAT); \
1271 \
1272 return extend; \
1273 } \
1274 \
1275 static inline void VEC_OP (T,A,safe_grow) \
1276 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1277 { \
1278 VEC_ASSERT (size_ >= 0 \
1279 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1280 "grow", T, A); \
1281 VEC_OP (T,A,reserve_exact) (vec_, \
1282 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
1283 VEC_CHECK_PASS PASS_MEM_STAT); \
1284 VEC_BASE (*vec_)->prefix.num = size_; \
1285 } \
1286 \
1287 static inline void VEC_OP (T,A,safe_grow_cleared) \
1288 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1289 { \
1290 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1291 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1292 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1293 sizeof (T) * (size_ - oldsize)); \
1294 } \
1295 \
1296 static inline void VEC_OP(T,A,safe_splice) \
1297 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1298 { \
1299 if (src_) \
1300 { \
1301 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
1302 VEC_CHECK_PASS MEM_STAT_INFO); \
1303 \
1304 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1305 VEC_CHECK_PASS); \
1306 } \
1307 } \
1308 \
1309 static inline T *VEC_OP (T,A,safe_push) \
1310 (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1311 { \
1312 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1313 \
1314 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1315 } \
1316 \
1317 static inline T *VEC_OP (T,A,safe_insert) \
1318 (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
1319 VEC_CHECK_DECL MEM_STAT_DECL) \
1320 { \
1321 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1322 \
1323 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1324 VEC_CHECK_PASS); \
1325 }
1326
1327 /* We support a vector which starts out with space on the stack and
1328 switches to heap space when forced to reallocate. This works a
1329 little differently. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1330 DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial
1331 space; because alloca can not be usefully called in an inline
1332 function, and because a macro can not define a macro, you must then
1333 write a #define for each type:
1334
1335 #define VEC_{TYPE}_stack_alloc(alloc) \
1336 VEC_stack_alloc({TYPE}, alloc)
1337
1338 This is really a hack and perhaps can be made better. Note that
1339 this macro will wind up evaluating the ALLOC parameter twice.
1340
1341 Only the initial allocation will be made using alloca, so pass a
1342 reasonable estimate that doesn't use too much stack space; don't
1343 pass zero. Don't return a VEC(TYPE,stack) vector from the function
1344 which allocated it. */
1345
1346 extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
1347 extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
1348 extern void *vec_stack_p_reserve_exact_1 (int, void *);
1349 extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
1350 extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
1351 MEM_STAT_DECL);
1352 extern void vec_stack_free (void *);
1353
1354 #ifdef GATHER_STATISTICS
1355 #define VEC_stack_alloc(T,alloc,name,line,function) \
1356 (VEC_OP (T,stack,alloc1) \
1357 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1358 #else
1359 #define VEC_stack_alloc(T,alloc) \
1360 (VEC_OP (T,stack,alloc1) \
1361 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1362 #endif
1363
1364 #define DEF_VEC_ALLOC_P_STACK(T) \
1365 VEC_TA(T,base,stack); \
1366 DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1367 DEF_VEC_NONALLOC_FUNCS_P(T,stack) \
1368 struct vec_swallow_trailing_semi
1369
1370 #define DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1371 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1372 (int alloc_, VEC(T,stack)* space) \
1373 { \
1374 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1375 }
1376
1377 #define DEF_VEC_ALLOC_O_STACK(T) \
1378 VEC_TA(T,base,stack); \
1379 DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1380 DEF_VEC_NONALLOC_FUNCS_O(T,stack) \
1381 struct vec_swallow_trailing_semi
1382
1383 #define DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1384 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1385 (int alloc_, VEC(T,stack)* space) \
1386 { \
1387 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1388 }
1389
1390 #define DEF_VEC_ALLOC_I_STACK(T) \
1391 VEC_TA(T,base,stack); \
1392 DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1393 DEF_VEC_NONALLOC_FUNCS_I(T,stack) \
1394 struct vec_swallow_trailing_semi
1395
1396 #define DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1397 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1398 (int alloc_, VEC(T,stack)* space) \
1399 { \
1400 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1401 }
1402
1403 #endif /* GCC_VEC_H */
Mirror of the offical gcc git repository hosted at gcc.gnu.org