?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
freebsd64.h: Remove duplicated entries from last commit.
[official-gcc.git] / gcc / vec.h
blobd47795879f1834f0e6c2eec97ce888ec08b0b999
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 #if GCC_VERSION >= 4000
553 #define VEC_BASE(P) \
554 ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0)
555 #else
556 #define VEC_BASE(P) ((P) ? &(P)->base : 0)
557 #endif
558
559 /* Vector of integer-like object. */
560 #define DEF_VEC_I(T) \
561 static inline void VEC_OP (T,must_be,integral_type) (void) \
562 { \
563 (void)~(T)0; \
564 } \
565 \
566 VEC_T(T,base); \
567 VEC_TA(T,base,none); \
568 DEF_VEC_FUNC_P(T) \
569 struct vec_swallow_trailing_semi
570 #define DEF_VEC_ALLOC_I(T,A) \
571 VEC_TA(T,base,A); \
572 DEF_VEC_ALLOC_FUNC_I(T,A) \
573 DEF_VEC_NONALLOC_FUNCS_I(T,A) \
574 struct vec_swallow_trailing_semi
575
576 /* Vector of pointer to object. */
577 #define DEF_VEC_P(T) \
578 static inline void VEC_OP (T,must_be,pointer_type) (void) \
579 { \
580 (void)((T)1 == (void *)1); \
581 } \
582 \
583 VEC_T_GTY(T,base); \
584 VEC_TA(T,base,none); \
585 DEF_VEC_FUNC_P(T) \
586 struct vec_swallow_trailing_semi
587 #define DEF_VEC_ALLOC_P(T,A) \
588 VEC_TA(T,base,A); \
589 DEF_VEC_ALLOC_FUNC_P(T,A) \
590 DEF_VEC_NONALLOC_FUNCS_P(T,A) \
591 struct vec_swallow_trailing_semi
592
593 #define DEF_VEC_FUNC_P(T) \
594 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
595 { \
596 return vec_ ? vec_->prefix.num : 0; \
597 } \
598 \
599 static inline T VEC_OP (T,base,last) \
600 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
601 { \
602 VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
603 \
604 return vec_->vec[vec_->prefix.num - 1]; \
605 } \
606 \
607 static inline T VEC_OP (T,base,index) \
608 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
609 { \
610 VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
611 \
612 return vec_->vec[ix_]; \
613 } \
614 \
615 static inline int VEC_OP (T,base,iterate) \
616 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
617 { \
618 if (vec_ && ix_ < vec_->prefix.num) \
619 { \
620 *ptr = vec_->vec[ix_]; \
621 return 1; \
622 } \
623 else \
624 { \
625 *ptr = (T) 0; \
626 return 0; \
627 } \
628 } \
629 \
630 static inline size_t VEC_OP (T,base,embedded_size) \
631 (int alloc_) \
632 { \
633 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
634 } \
635 \
636 static inline void VEC_OP (T,base,embedded_init) \
637 (VEC(T,base) *vec_, int alloc_) \
638 { \
639 vec_->prefix.num = 0; \
640 vec_->prefix.alloc = alloc_; \
641 } \
642 \
643 static inline int VEC_OP (T,base,space) \
644 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
645 { \
646 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
647 return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
648 } \
649 \
650 static inline void VEC_OP(T,base,splice) \
651 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
652 { \
653 if (src_) \
654 { \
655 unsigned len_ = src_->prefix.num; \
656 VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
657 \
658 memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
659 dst_->prefix.num += len_; \
660 } \
661 } \
662 \
663 static inline T *VEC_OP (T,base,quick_push) \
664 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
665 { \
666 T *slot_; \
667 \
668 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
669 slot_ = &vec_->vec[vec_->prefix.num++]; \
670 *slot_ = obj_; \
671 \
672 return slot_; \
673 } \
674 \
675 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
676 { \
677 T obj_; \
678 \
679 VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
680 obj_ = vec_->vec[--vec_->prefix.num]; \
681 \
682 return obj_; \
683 } \
684 \
685 static inline void VEC_OP (T,base,truncate) \
686 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
687 { \
688 VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
689 if (vec_) \
690 vec_->prefix.num = size_; \
691 } \
692 \
693 static inline T VEC_OP (T,base,replace) \
694 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
695 { \
696 T old_obj_; \
697 \
698 VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
699 old_obj_ = vec_->vec[ix_]; \
700 vec_->vec[ix_] = obj_; \
701 \
702 return old_obj_; \
703 } \
704 \
705 static inline T *VEC_OP (T,base,quick_insert) \
706 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
707 { \
708 T *slot_; \
709 \
710 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
711 VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
712 slot_ = &vec_->vec[ix_]; \
713 memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
714 *slot_ = obj_; \
715 \
716 return slot_; \
717 } \
718 \
719 static inline T VEC_OP (T,base,ordered_remove) \
720 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
721 { \
722 T *slot_; \
723 T obj_; \
724 \
725 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
726 slot_ = &vec_->vec[ix_]; \
727 obj_ = *slot_; \
728 memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
729 \
730 return obj_; \
731 } \
732 \
733 static inline T VEC_OP (T,base,unordered_remove) \
734 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
735 { \
736 T *slot_; \
737 T obj_; \
738 \
739 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
740 slot_ = &vec_->vec[ix_]; \
741 obj_ = *slot_; \
742 *slot_ = vec_->vec[--vec_->prefix.num]; \
743 \
744 return obj_; \
745 } \
746 \
747 static inline void VEC_OP (T,base,block_remove) \
748 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
749 { \
750 T *slot_; \
751 \
752 VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
753 slot_ = &vec_->vec[ix_]; \
754 vec_->prefix.num -= len_; \
755 memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
756 } \
757 \
758 static inline T *VEC_OP (T,base,address) \
759 (VEC(T,base) *vec_) \
760 { \
761 return vec_ ? vec_->vec : 0; \
762 } \
763 \
764 static inline unsigned VEC_OP (T,base,lower_bound) \
765 (VEC(T,base) *vec_, const T obj_, \
766 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
767 { \
768 unsigned int len_ = VEC_OP (T,base, length) (vec_); \
769 unsigned int half_, middle_; \
770 unsigned int first_ = 0; \
771 while (len_ > 0) \
772 { \
773 T middle_elem_; \
774 half_ = len_ >> 1; \
775 middle_ = first_; \
776 middle_ += half_; \
777 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
778 if (lessthan_ (middle_elem_, obj_)) \
779 { \
780 first_ = middle_; \
781 ++first_; \
782 len_ = len_ - half_ - 1; \
783 } \
784 else \
785 len_ = half_; \
786 } \
787 return first_; \
788 }
789
790 #define DEF_VEC_ALLOC_FUNC_P(T,A) \
791 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
792 (int alloc_ MEM_STAT_DECL) \
793 { \
794 return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
795 PASS_MEM_STAT); \
796 }
797
798
799 #define DEF_VEC_NONALLOC_FUNCS_P(T,A) \
800 static inline void VEC_OP (T,A,free) \
801 (VEC(T,A) **vec_) \
802 { \
803 if (*vec_) \
804 vec_##A##_free (*vec_); \
805 *vec_ = NULL; \
806 } \
807 \
808 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
809 { \
810 size_t len_ = vec_ ? vec_->prefix.num : 0; \
811 VEC (T,A) *new_vec_ = NULL; \
812 \
813 if (len_) \
814 { \
815 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
816 (NULL, len_ PASS_MEM_STAT)); \
817 \
818 new_vec_->base.prefix.num = len_; \
819 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
820 } \
821 return new_vec_; \
822 } \
823 \
824 static inline int VEC_OP (T,A,reserve) \
825 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
826 { \
827 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
828 VEC_CHECK_PASS); \
829 \
830 if (extend) \
831 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
832 \
833 return extend; \
834 } \
835 \
836 static inline int VEC_OP (T,A,reserve_exact) \
837 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
838 { \
839 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
840 VEC_CHECK_PASS); \
841 \
842 if (extend) \
843 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
844 PASS_MEM_STAT); \
845 \
846 return extend; \
847 } \
848 \
849 static inline void VEC_OP (T,A,safe_grow) \
850 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
851 { \
852 VEC_ASSERT (size_ >= 0 \
853 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
854 "grow", T, A); \
855 VEC_OP (T,A,reserve_exact) (vec_, \
856 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
857 VEC_CHECK_PASS PASS_MEM_STAT); \
858 VEC_BASE (*vec_)->prefix.num = size_; \
859 } \
860 \
861 static inline void VEC_OP (T,A,safe_grow_cleared) \
862 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
863 { \
864 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
865 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
866 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
867 sizeof (T) * (size_ - oldsize)); \
868 } \
869 \
870 static inline void VEC_OP(T,A,safe_splice) \
871 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
872 { \
873 if (src_) \
874 { \
875 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
876 VEC_CHECK_PASS MEM_STAT_INFO); \
877 \
878 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
879 VEC_CHECK_PASS); \
880 } \
881 } \
882 \
883 static inline T *VEC_OP (T,A,safe_push) \
884 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
885 { \
886 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
887 \
888 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
889 } \
890 \
891 static inline T *VEC_OP (T,A,safe_insert) \
892 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
893 { \
894 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
895 \
896 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
897 VEC_CHECK_PASS); \
898 }
899
900 /* Vector of object. */
901 #define DEF_VEC_O(T) \
902 VEC_T_GTY(T,base); \
903 VEC_TA(T,base,none); \
904 DEF_VEC_FUNC_O(T) \
905 struct vec_swallow_trailing_semi
906 #define DEF_VEC_ALLOC_O(T,A) \
907 VEC_TA(T,base,A); \
908 DEF_VEC_ALLOC_FUNC_O(T,A) \
909 DEF_VEC_NONALLOC_FUNCS_O(T,A) \
910 struct vec_swallow_trailing_semi
911
912 #define DEF_VEC_FUNC_O(T) \
913 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
914 { \
915 return vec_ ? vec_->prefix.num : 0; \
916 } \
917 \
918 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
919 { \
920 VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
921 \
922 return &vec_->vec[vec_->prefix.num - 1]; \
923 } \
924 \
925 static inline T *VEC_OP (T,base,index) \
926 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
927 { \
928 VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
929 \
930 return &vec_->vec[ix_]; \
931 } \
932 \
933 static inline int VEC_OP (T,base,iterate) \
934 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
935 { \
936 if (vec_ && ix_ < vec_->prefix.num) \
937 { \
938 *ptr = &vec_->vec[ix_]; \
939 return 1; \
940 } \
941 else \
942 { \
943 *ptr = 0; \
944 return 0; \
945 } \
946 } \
947 \
948 static inline size_t VEC_OP (T,base,embedded_size) \
949 (int alloc_) \
950 { \
951 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
952 } \
953 \
954 static inline void VEC_OP (T,base,embedded_init) \
955 (VEC(T,base) *vec_, int alloc_) \
956 { \
957 vec_->prefix.num = 0; \
958 vec_->prefix.alloc = alloc_; \
959 } \
960 \
961 static inline int VEC_OP (T,base,space) \
962 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
963 { \
964 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
965 return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
966 } \
967 \
968 static inline void VEC_OP(T,base,splice) \
969 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
970 { \
971 if (src_) \
972 { \
973 unsigned len_ = src_->prefix.num; \
974 VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
975 \
976 memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
977 dst_->prefix.num += len_; \
978 } \
979 } \
980 \
981 static inline T *VEC_OP (T,base,quick_push) \
982 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
983 { \
984 T *slot_; \
985 \
986 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
987 slot_ = &vec_->vec[vec_->prefix.num++]; \
988 if (obj_) \
989 *slot_ = *obj_; \
990 \
991 return slot_; \
992 } \
993 \
994 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
995 { \
996 VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
997 --vec_->prefix.num; \
998 } \
999 \
1000 static inline void VEC_OP (T,base,truncate) \
1001 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
1002 { \
1003 VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
1004 if (vec_) \
1005 vec_->prefix.num = size_; \
1006 } \
1007 \
1008 static inline T *VEC_OP (T,base,replace) \
1009 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
1010 { \
1011 T *slot_; \
1012 \
1013 VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
1014 slot_ = &vec_->vec[ix_]; \
1015 if (obj_) \
1016 *slot_ = *obj_; \
1017 \
1018 return slot_; \
1019 } \
1020 \
1021 static inline T *VEC_OP (T,base,quick_insert) \
1022 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
1023 { \
1024 T *slot_; \
1025 \
1026 VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
1027 VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
1028 slot_ = &vec_->vec[ix_]; \
1029 memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
1030 if (obj_) \
1031 *slot_ = *obj_; \
1032 \
1033 return slot_; \
1034 } \
1035 \
1036 static inline void VEC_OP (T,base,ordered_remove) \
1037 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1038 { \
1039 T *slot_; \
1040 \
1041 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
1042 slot_ = &vec_->vec[ix_]; \
1043 memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
1044 } \
1045 \
1046 static inline void VEC_OP (T,base,unordered_remove) \
1047 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1048 { \
1049 VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
1050 vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \
1051 } \
1052 \
1053 static inline void VEC_OP (T,base,block_remove) \
1054 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
1055 { \
1056 T *slot_; \
1057 \
1058 VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
1059 slot_ = &vec_->vec[ix_]; \
1060 vec_->prefix.num -= len_; \
1061 memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
1062 } \
1063 \
1064 static inline T *VEC_OP (T,base,address) \
1065 (VEC(T,base) *vec_) \
1066 { \
1067 return vec_ ? vec_->vec : 0; \
1068 } \
1069 \
1070 static inline unsigned VEC_OP (T,base,lower_bound) \
1071 (VEC(T,base) *vec_, const T *obj_, \
1072 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
1073 { \
1074 unsigned int len_ = VEC_OP (T, base, length) (vec_); \
1075 unsigned int half_, middle_; \
1076 unsigned int first_ = 0; \
1077 while (len_ > 0) \
1078 { \
1079 T *middle_elem_; \
1080 half_ = len_ >> 1; \
1081 middle_ = first_; \
1082 middle_ += half_; \
1083 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
1084 if (lessthan_ (middle_elem_, obj_)) \
1085 { \
1086 first_ = middle_; \
1087 ++first_; \
1088 len_ = len_ - half_ - 1; \
1089 } \
1090 else \
1091 len_ = half_; \
1092 } \
1093 return first_; \
1094 }
1095
1096 #define DEF_VEC_ALLOC_FUNC_O(T,A) \
1097 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1098 (int alloc_ MEM_STAT_DECL) \
1099 { \
1100 return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
1101 offsetof (VEC(T,A),base.vec), \
1102 sizeof (T) \
1103 PASS_MEM_STAT); \
1104 }
1105
1106 #define DEF_VEC_NONALLOC_FUNCS_O(T,A) \
1107 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1108 { \
1109 size_t len_ = vec_ ? vec_->prefix.num : 0; \
1110 VEC (T,A) *new_vec_ = NULL; \
1111 \
1112 if (len_) \
1113 { \
1114 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1115 (NULL, len_, \
1116 offsetof (VEC(T,A),base.vec), sizeof (T) \
1117 PASS_MEM_STAT)); \
1118 \
1119 new_vec_->base.prefix.num = len_; \
1120 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1121 } \
1122 return new_vec_; \
1123 } \
1124 \
1125 static inline void VEC_OP (T,A,free) \
1126 (VEC(T,A) **vec_) \
1127 { \
1128 if (*vec_) \
1129 vec_##A##_free (*vec_); \
1130 *vec_ = NULL; \
1131 } \
1132 \
1133 static inline int VEC_OP (T,A,reserve) \
1134 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1135 { \
1136 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1137 VEC_CHECK_PASS); \
1138 \
1139 if (extend) \
1140 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1141 offsetof (VEC(T,A),base.vec),\
1142 sizeof (T) \
1143 PASS_MEM_STAT); \
1144 \
1145 return extend; \
1146 } \
1147 \
1148 static inline int VEC_OP (T,A,reserve_exact) \
1149 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1150 { \
1151 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1152 VEC_CHECK_PASS); \
1153 \
1154 if (extend) \
1155 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1156 (*vec_, alloc_, \
1157 offsetof (VEC(T,A),base.vec), \
1158 sizeof (T) PASS_MEM_STAT); \
1159 \
1160 return extend; \
1161 } \
1162 \
1163 static inline void VEC_OP (T,A,safe_grow) \
1164 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1165 { \
1166 VEC_ASSERT (size_ >= 0 \
1167 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1168 "grow", T, A); \
1169 VEC_OP (T,A,reserve_exact) (vec_, \
1170 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
1171 VEC_CHECK_PASS PASS_MEM_STAT); \
1172 VEC_BASE (*vec_)->prefix.num = size_; \
1173 } \
1174 \
1175 static inline void VEC_OP (T,A,safe_grow_cleared) \
1176 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1177 { \
1178 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1179 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1180 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1181 sizeof (T) * (size_ - oldsize)); \
1182 } \
1183 \
1184 static inline void VEC_OP(T,A,safe_splice) \
1185 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1186 { \
1187 if (src_) \
1188 { \
1189 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
1190 VEC_CHECK_PASS MEM_STAT_INFO); \
1191 \
1192 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1193 VEC_CHECK_PASS); \
1194 } \
1195 } \
1196 \
1197 static inline T *VEC_OP (T,A,safe_push) \
1198 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1199 { \
1200 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1201 \
1202 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1203 } \
1204 \
1205 static inline T *VEC_OP (T,A,safe_insert) \
1206 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
1207 VEC_CHECK_DECL MEM_STAT_DECL) \
1208 { \
1209 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1210 \
1211 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1212 VEC_CHECK_PASS); \
1213 }
1214
1215 #define DEF_VEC_ALLOC_FUNC_I(T,A) \
1216 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1217 (int alloc_ MEM_STAT_DECL) \
1218 { \
1219 return (VEC(T,A) *) vec_##A##_o_reserve_exact \
1220 (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
1221 sizeof (T) PASS_MEM_STAT); \
1222 }
1223
1224 #define DEF_VEC_NONALLOC_FUNCS_I(T,A) \
1225 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1226 { \
1227 size_t len_ = vec_ ? vec_->prefix.num : 0; \
1228 VEC (T,A) *new_vec_ = NULL; \
1229 \
1230 if (len_) \
1231 { \
1232 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1233 (NULL, len_, \
1234 offsetof (VEC(T,A),base.vec), sizeof (T) \
1235 PASS_MEM_STAT)); \
1236 \
1237 new_vec_->base.prefix.num = len_; \
1238 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1239 } \
1240 return new_vec_; \
1241 } \
1242 \
1243 static inline void VEC_OP (T,A,free) \
1244 (VEC(T,A) **vec_) \
1245 { \
1246 if (*vec_) \
1247 vec_##A##_free (*vec_); \
1248 *vec_ = NULL; \
1249 } \
1250 \
1251 static inline int VEC_OP (T,A,reserve) \
1252 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1253 { \
1254 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1255 VEC_CHECK_PASS); \
1256 \
1257 if (extend) \
1258 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1259 offsetof (VEC(T,A),base.vec),\
1260 sizeof (T) \
1261 PASS_MEM_STAT); \
1262 \
1263 return extend; \
1264 } \
1265 \
1266 static inline int VEC_OP (T,A,reserve_exact) \
1267 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1268 { \
1269 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1270 VEC_CHECK_PASS); \
1271 \
1272 if (extend) \
1273 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1274 (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
1275 sizeof (T) PASS_MEM_STAT); \
1276 \
1277 return extend; \
1278 } \
1279 \
1280 static inline void VEC_OP (T,A,safe_grow) \
1281 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1282 { \
1283 VEC_ASSERT (size_ >= 0 \
1284 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1285 "grow", T, A); \
1286 VEC_OP (T,A,reserve_exact) (vec_, \
1287 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
1288 VEC_CHECK_PASS PASS_MEM_STAT); \
1289 VEC_BASE (*vec_)->prefix.num = size_; \
1290 } \
1291 \
1292 static inline void VEC_OP (T,A,safe_grow_cleared) \
1293 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1294 { \
1295 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1296 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1297 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1298 sizeof (T) * (size_ - oldsize)); \
1299 } \
1300 \
1301 static inline void VEC_OP(T,A,safe_splice) \
1302 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1303 { \
1304 if (src_) \
1305 { \
1306 VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
1307 VEC_CHECK_PASS MEM_STAT_INFO); \
1308 \
1309 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1310 VEC_CHECK_PASS); \
1311 } \
1312 } \
1313 \
1314 static inline T *VEC_OP (T,A,safe_push) \
1315 (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1316 { \
1317 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1318 \
1319 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1320 } \
1321 \
1322 static inline T *VEC_OP (T,A,safe_insert) \
1323 (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
1324 VEC_CHECK_DECL MEM_STAT_DECL) \
1325 { \
1326 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1327 \
1328 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1329 VEC_CHECK_PASS); \
1330 }
1331
1332 /* We support a vector which starts out with space on the stack and
1333 switches to heap space when forced to reallocate. This works a
1334 little differently. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1335 DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial
1336 space; because alloca can not be usefully called in an inline
1337 function, and because a macro can not define a macro, you must then
1338 write a #define for each type:
1339
1340 #define VEC_{TYPE}_stack_alloc(alloc) \
1341 VEC_stack_alloc({TYPE}, alloc)
1342
1343 This is really a hack and perhaps can be made better. Note that
1344 this macro will wind up evaluating the ALLOC parameter twice.
1345
1346 Only the initial allocation will be made using alloca, so pass a
1347 reasonable estimate that doesn't use too much stack space; don't
1348 pass zero. Don't return a VEC(TYPE,stack) vector from the function
1349 which allocated it. */
1350
1351 extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
1352 extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
1353 extern void *vec_stack_p_reserve_exact_1 (int, void *);
1354 extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
1355 extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
1356 MEM_STAT_DECL);
1357 extern void vec_stack_free (void *);
1358
1359 #ifdef GATHER_STATISTICS
1360 #define VEC_stack_alloc(T,alloc,name,line,function) \
1361 (VEC_OP (T,stack,alloc1) \
1362 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1363 #else
1364 #define VEC_stack_alloc(T,alloc) \
1365 (VEC_OP (T,stack,alloc1) \
1366 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1367 #endif
1368
1369 #define DEF_VEC_ALLOC_P_STACK(T) \
1370 VEC_TA(T,base,stack); \
1371 DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1372 DEF_VEC_NONALLOC_FUNCS_P(T,stack) \
1373 struct vec_swallow_trailing_semi
1374
1375 #define DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1376 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1377 (int alloc_, VEC(T,stack)* space) \
1378 { \
1379 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1380 }
1381
1382 #define DEF_VEC_ALLOC_O_STACK(T) \
1383 VEC_TA(T,base,stack); \
1384 DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1385 DEF_VEC_NONALLOC_FUNCS_O(T,stack) \
1386 struct vec_swallow_trailing_semi
1387
1388 #define DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1389 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1390 (int alloc_, VEC(T,stack)* space) \
1391 { \
1392 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1393 }
1394
1395 #define DEF_VEC_ALLOC_I_STACK(T) \
1396 VEC_TA(T,base,stack); \
1397 DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1398 DEF_VEC_NONALLOC_FUNCS_I(T,stack) \
1399 struct vec_swallow_trailing_semi
1400
1401 #define DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1402 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1403 (int alloc_, VEC(T,stack)* space) \
1404 { \
1405 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1406 }
1407
1408 #endif /* GCC_VEC_H */
Mirror of the offical gcc git repository hosted at gcc.gnu.org