| blob | 1d2f067d8d5b77303112106f600290232ead0cba |
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>
6 This file is part of GCC.
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.
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.
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/>. */
22 #ifndef GCC_VEC_H
23 #define GCC_VEC_H
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.
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.
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.
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.
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.
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.
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.
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.
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.
117 An example of their use would be,
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.
123 struct my_struct {
124 VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers.
125 };
127 struct my_struct *s;
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 }
134 */
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. */
144 /* Length of vector
145 unsigned VEC_T_length(const VEC(T) *v);
147 Return the number of active elements in V. V can be NULL, in which
148 case zero is returned. */
150 #define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
153 /* Check if vector is empty
154 int VEC_T_empty(const VEC(T) *v);
156 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
158 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
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
166 Return the final element. V must not be empty. */
168 #define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
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
175 Return the IX'th element. If IX must be in the domain of V. */
177 #define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
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
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,
188 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
189 continue; */
191 #define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
193 /* Convenience macro for forward iteration. */
195 #define FOR_EACH_VEC_ELT(T, V, I, P) \
196 for (I = 0; VEC_iterate (T, (V), (I), (P)); ++(I))
198 /* Convenience macro for reverse iteration. */
200 #define FOR_EACH_VEC_ELT_REVERSE(T,V,I,P) \
201 for (I = VEC_length (T, (V)) - 1; \
202 VEC_iterate (T, (V), (I), (P)); \
203 (I)--)
205 /* Allocate new vector.
206 VEC(T,A) *VEC_T_A_alloc(int reserve);
208 Allocate a new vector with space for RESERVE objects. If RESERVE
209 is zero, NO vector is created. */
211 #define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
213 /* Free a vector.
214 void VEC_T_A_free(VEC(T,A) *&);
216 Free a vector and set it to NULL. */
218 #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
220 /* Use these to determine the required size and initialization of a
221 vector embedded within another structure (as the final member).
223 size_t VEC_T_embedded_size(int reserve);
224 void VEC_T_embedded_init(VEC(T) *v, int reserve);
226 These allow the caller to perform the memory allocation. */
228 #define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N))
229 #define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
231 /* Copy a vector.
232 VEC(T,A) *VEC_T_A_copy(VEC(T) *);
234 Copy the live elements of a vector into a new vector. The new and
235 old vectors need not be allocated by the same mechanism. */
237 #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
239 /* Determine if a vector has additional capacity.
241 int VEC_T_space (VEC(T) *v,int reserve)
243 If V has space for RESERVE additional entries, return nonzero. You
244 usually only need to use this if you are doing your own vector
245 reallocation, for instance on an embedded vector. This returns
246 nonzero in exactly the same circumstances that VEC_T_reserve
247 will. */
249 #define VEC_space(T,V,R) \
250 (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
252 /* Reserve space.
253 int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
255 Ensure that V has at least RESERVE slots available. This will
256 create additional headroom. Note this can cause V to be
257 reallocated. Returns nonzero iff reallocation actually
258 occurred. */
260 #define VEC_reserve(T,A,V,R) \
261 (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
263 /* Reserve space exactly.
264 int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
266 Ensure that V has at least RESERVE slots available. This will not
267 create additional headroom. Note this can cause V to be
268 reallocated. Returns nonzero iff reallocation actually
269 occurred. */
271 #define VEC_reserve_exact(T,A,V,R) \
272 (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
274 /* Copy elements with no reallocation
275 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
276 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Pointer
277 void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Object
279 Copy the elements in SRC to the end of DST as if by memcpy. DST and
280 SRC need not be allocated with the same mechanism, although they most
281 often will be. DST is assumed to have sufficient headroom
282 available. */
284 #define VEC_splice(T,DST,SRC) \
285 (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
287 /* Copy elements with reallocation
288 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
289 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Pointer
290 void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Object
292 Copy the elements in SRC to the end of DST as if by memcpy. DST and
293 SRC need not be allocated with the same mechanism, although they most
294 often will be. DST need not have sufficient headroom and will be
295 reallocated if needed. */
297 #define VEC_safe_splice(T,A,DST,SRC) \
298 (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO))
300 /* Push object with no reallocation
301 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
302 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
303 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
305 Push a new element onto the end, returns a pointer to the slot
306 filled in. For object vectors, the new value can be NULL, in which
307 case NO initialization is performed. There must
308 be sufficient space in the vector. */
310 #define VEC_quick_push(T,V,O) \
311 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
313 /* Push object with reallocation
314 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
315 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
316 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
318 Push a new element onto the end, returns a pointer to the slot
319 filled in. For object vectors, the new value can be NULL, in which
320 case NO initialization is performed. Reallocates V, if needed. */
322 #define VEC_safe_push(T,A,V,O) \
323 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
325 /* Pop element off end
326 T VEC_T_pop (VEC(T) *v); // Integer
327 T VEC_T_pop (VEC(T) *v); // Pointer
328 void VEC_T_pop (VEC(T) *v); // Object
330 Pop the last element off the end. Returns the element popped, for
331 pointer vectors. */
333 #define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
335 /* Truncate to specific length
336 void VEC_T_truncate (VEC(T) *v, unsigned len);
338 Set the length as specified. The new length must be less than or
339 equal to the current length. This is an O(1) operation. */
341 #define VEC_truncate(T,V,I) \
342 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
344 /* Grow to a specific length.
345 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
347 Grow the vector to a specific length. The LEN must be as
348 long or longer than the current length. The new elements are
349 uninitialized. */
351 #define VEC_safe_grow(T,A,V,I) \
352 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
354 /* Grow to a specific length.
355 void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
357 Grow the vector to a specific length. The LEN must be as
358 long or longer than the current length. The new elements are
359 initialized to zero. */
361 #define VEC_safe_grow_cleared(T,A,V,I) \
362 (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
364 /* Replace element
365 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
366 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
367 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
369 Replace the IXth element of V with a new value, VAL. For pointer
370 vectors returns the original value. For object vectors returns a
371 pointer to the new value. For object vectors the new value can be
372 NULL, in which case no overwriting of the slot is actually
373 performed. */
375 #define VEC_replace(T,V,I,O) \
376 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
378 /* Insert object with no reallocation
379 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
380 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
381 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
383 Insert an element, VAL, at the IXth position of V. Return a pointer
384 to the slot created. For vectors of object, the new value can be
385 NULL, in which case no initialization of the inserted slot takes
386 place. There must be sufficient space. */
388 #define VEC_quick_insert(T,V,I,O) \
389 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
391 /* Insert object with reallocation
392 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
393 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
394 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
396 Insert an element, VAL, at the IXth position of V. Return a pointer
397 to the slot created. For vectors of object, the new value can be
398 NULL, in which case no initialization of the inserted slot takes
399 place. Reallocate V, if necessary. */
401 #define VEC_safe_insert(T,A,V,I,O) \
402 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
404 /* Remove element retaining order
405 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
406 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
407 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
409 Remove an element from the IXth position of V. Ordering of
410 remaining elements is preserved. For pointer vectors returns the
411 removed object. This is an O(N) operation due to a memmove. */
413 #define VEC_ordered_remove(T,V,I) \
414 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
416 /* Remove element destroying order
417 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
418 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
419 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
421 Remove an element from the IXth position of V. Ordering of
422 remaining elements is destroyed. For pointer vectors returns the
423 removed object. This is an O(1) operation. */
425 #define VEC_unordered_remove(T,V,I) \
426 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
428 /* Remove a block of elements
429 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
431 Remove LEN elements starting at the IXth. Ordering is retained.
432 This is an O(N) operation due to memmove. */
434 #define VEC_block_remove(T,V,I,L) \
435 (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
437 /* Get the address of the array of elements
438 T *VEC_T_address (VEC(T) v)
440 If you need to directly manipulate the array (for instance, you
441 want to feed it to qsort), use this accessor. */
443 #define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
445 /* Find the first index in the vector not less than the object.
446 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
447 bool (*lessthan) (const T, const T)); // Integer
448 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
449 bool (*lessthan) (const T, const T)); // Pointer
450 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
451 bool (*lessthan) (const T*, const T*)); // Object
453 Find the first position in which VAL could be inserted without
454 changing the ordering of V. LESSTHAN is a function that returns
455 true if the first argument is strictly less than the second. */
457 #define VEC_lower_bound(T,V,O,LT) \
458 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
460 /* Reallocate an array of elements with prefix. */
465 MEM_STAT_DECL);
467 #define vec_gc_free(V) ggc_free (V)
472 MEM_STAT_DECL);
474 #ifdef GATHER_STATISTICS
476 #else
477 /* Avoid problems with frontends that #define free(x). */
478 #define vec_heap_free(V) (free) (V)
479 #endif
481 #if ENABLE_CHECKING
482 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
483 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
484 #define VEC_CHECK_PASS ,file_,line_,function_
486 #define VEC_ASSERT(EXPR,OP,T,A) \
487 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
490 ATTRIBUTE_NORETURN;
491 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
492 #else
493 #define VEC_CHECK_INFO
494 #define VEC_CHECK_DECL
495 #define VEC_CHECK_PASS
496 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
497 #endif
499 /* Note: gengtype has hardwired knowledge of the expansions of the
500 VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the
501 expansions of these macros you may need to change gengtype too. */
503 #define VEC(T,A) VEC_##T##_##A
504 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
506 /* Base of vector type, not user visible. */
507 #define VEC_T(T,B) \
508 typedef struct VEC(T,B) \
509 { \
510 unsigned num; \
511 unsigned alloc; \
512 T vec[1]; \
513 } VEC(T,B)
515 #define VEC_T_GTY(T,B) \
516 typedef struct GTY(()) VEC(T,B) \
517 { \
518 unsigned num; \
519 unsigned alloc; \
521 } VEC(T,B)
523 /* Derived vector type, user visible. */
524 #define VEC_TA_GTY(T,B,A,GTY) \
525 typedef struct GTY VEC(T,A) \
526 { \
527 VEC(T,B) base; \
528 } VEC(T,A)
530 #define VEC_TA(T,B,A) \
531 typedef struct VEC(T,A) \
532 { \
533 VEC(T,B) base; \
534 } VEC(T,A)
536 /* Convert to base type. */
537 #define VEC_BASE(P) ((P) ? &(P)->base : 0)
539 /* Vector of integer-like object. */
540 #define DEF_VEC_I(T) \
541 static inline void VEC_OP (T,must_be,integral_type) (void) \
542 { \
543 (void)~(T)0; \
544 } \
545 \
546 VEC_T(T,base); \
547 VEC_TA(T,base,none); \
548 DEF_VEC_FUNC_P(T) \
549 struct vec_swallow_trailing_semi
550 #define DEF_VEC_ALLOC_I(T,A) \
551 VEC_TA(T,base,A); \
552 DEF_VEC_ALLOC_FUNC_I(T,A) \
553 DEF_VEC_NONALLOC_FUNCS_I(T,A) \
554 struct vec_swallow_trailing_semi
556 /* Vector of pointer to object. */
557 #define DEF_VEC_P(T) \
558 static inline void VEC_OP (T,must_be,pointer_type) (void) \
559 { \
560 (void)((T)1 == (void *)1); \
561 } \
562 \
563 VEC_T_GTY(T,base); \
564 VEC_TA(T,base,none); \
565 DEF_VEC_FUNC_P(T) \
566 struct vec_swallow_trailing_semi
567 #define DEF_VEC_ALLOC_P(T,A) \
568 VEC_TA(T,base,A); \
569 DEF_VEC_ALLOC_FUNC_P(T,A) \
570 DEF_VEC_NONALLOC_FUNCS_P(T,A) \
571 struct vec_swallow_trailing_semi
573 #define DEF_VEC_FUNC_P(T) \
574 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
575 { \
576 return vec_ ? vec_->num : 0; \
577 } \
578 \
579 static inline T VEC_OP (T,base,last) \
580 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
581 { \
583 \
584 return vec_->vec[vec_->num - 1]; \
585 } \
586 \
587 static inline T VEC_OP (T,base,index) \
588 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
589 { \
591 \
592 return vec_->vec[ix_]; \
593 } \
594 \
595 static inline int VEC_OP (T,base,iterate) \
596 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
597 { \
598 if (vec_ && ix_ < vec_->num) \
599 { \
600 *ptr = vec_->vec[ix_]; \
601 return 1; \
602 } \
603 else \
604 { \
605 *ptr = (T) 0; \
606 return 0; \
607 } \
608 } \
609 \
610 static inline size_t VEC_OP (T,base,embedded_size) \
611 (int alloc_) \
612 { \
613 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
614 } \
615 \
616 static inline void VEC_OP (T,base,embedded_init) \
617 (VEC(T,base) *vec_, int alloc_) \
618 { \
619 vec_->num = 0; \
620 vec_->alloc = alloc_; \
621 } \
622 \
623 static inline int VEC_OP (T,base,space) \
624 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
625 { \
627 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
628 } \
629 \
630 static inline void VEC_OP(T,base,splice) \
631 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
632 { \
633 if (src_) \
634 { \
635 unsigned len_ = src_->num; \
637 \
638 memcpy (&dst_->vec[dst_->num], &src_->vec[0], len_ * sizeof (T)); \
639 dst_->num += len_; \
640 } \
641 } \
642 \
643 static inline T *VEC_OP (T,base,quick_push) \
644 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
645 { \
646 T *slot_; \
647 \
649 slot_ = &vec_->vec[vec_->num++]; \
650 *slot_ = obj_; \
651 \
652 return slot_; \
653 } \
654 \
655 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
656 { \
657 T obj_; \
658 \
660 obj_ = vec_->vec[--vec_->num]; \
661 \
662 return obj_; \
663 } \
664 \
665 static inline void VEC_OP (T,base,truncate) \
666 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
667 { \
669 if (vec_) \
670 vec_->num = size_; \
671 } \
672 \
673 static inline T VEC_OP (T,base,replace) \
674 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
675 { \
676 T old_obj_; \
677 \
679 old_obj_ = vec_->vec[ix_]; \
680 vec_->vec[ix_] = obj_; \
681 \
682 return old_obj_; \
683 } \
684 \
685 static inline T *VEC_OP (T,base,quick_insert) \
686 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
687 { \
688 T *slot_; \
689 \
692 slot_ = &vec_->vec[ix_]; \
693 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
694 *slot_ = obj_; \
695 \
696 return slot_; \
697 } \
698 \
699 static inline T VEC_OP (T,base,ordered_remove) \
700 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
701 { \
702 T *slot_; \
703 T obj_; \
704 \
706 slot_ = &vec_->vec[ix_]; \
707 obj_ = *slot_; \
708 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
709 \
710 return obj_; \
711 } \
712 \
713 static inline T VEC_OP (T,base,unordered_remove) \
714 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
715 { \
716 T *slot_; \
717 T obj_; \
718 \
720 slot_ = &vec_->vec[ix_]; \
721 obj_ = *slot_; \
722 *slot_ = vec_->vec[--vec_->num]; \
723 \
724 return obj_; \
725 } \
726 \
727 static inline void VEC_OP (T,base,block_remove) \
728 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
729 { \
730 T *slot_; \
731 \
733 slot_ = &vec_->vec[ix_]; \
734 vec_->num -= len_; \
735 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
736 } \
737 \
738 static inline T *VEC_OP (T,base,address) \
739 (VEC(T,base) *vec_) \
740 { \
741 return vec_ ? vec_->vec : 0; \
742 } \
743 \
744 static inline unsigned VEC_OP (T,base,lower_bound) \
745 (VEC(T,base) *vec_, const T obj_, \
746 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
747 { \
748 unsigned int len_ = VEC_OP (T,base, length) (vec_); \
749 unsigned int half_, middle_; \
750 unsigned int first_ = 0; \
751 while (len_ > 0) \
752 { \
753 T middle_elem_; \
754 half_ = len_ >> 1; \
755 middle_ = first_; \
756 middle_ += half_; \
757 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
758 if (lessthan_ (middle_elem_, obj_)) \
759 { \
760 first_ = middle_; \
761 ++first_; \
762 len_ = len_ - half_ - 1; \
763 } \
764 else \
765 len_ = half_; \
766 } \
767 return first_; \
768 }
770 #define DEF_VEC_ALLOC_FUNC_P(T,A) \
771 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
772 (int alloc_ MEM_STAT_DECL) \
773 { \
774 return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
775 PASS_MEM_STAT); \
776 }
779 #define DEF_VEC_NONALLOC_FUNCS_P(T,A) \
780 static inline void VEC_OP (T,A,free) \
781 (VEC(T,A) **vec_) \
782 { \
783 if (*vec_) \
784 vec_##A##_free (*vec_); \
785 *vec_ = NULL; \
786 } \
787 \
788 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
789 { \
790 size_t len_ = vec_ ? vec_->num : 0; \
791 VEC (T,A) *new_vec_ = NULL; \
792 \
793 if (len_) \
794 { \
795 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
796 (NULL, len_ PASS_MEM_STAT)); \
797 \
798 new_vec_->base.num = len_; \
799 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
800 } \
801 return new_vec_; \
802 } \
803 \
804 static inline int VEC_OP (T,A,reserve) \
805 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
806 { \
807 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
808 VEC_CHECK_PASS); \
809 \
810 if (extend) \
811 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
812 \
813 return extend; \
814 } \
815 \
816 static inline int VEC_OP (T,A,reserve_exact) \
817 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
818 { \
819 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
820 VEC_CHECK_PASS); \
821 \
822 if (extend) \
823 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
824 PASS_MEM_STAT); \
825 \
826 return extend; \
827 } \
828 \
829 static inline void VEC_OP (T,A,safe_grow) \
830 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
831 { \
832 VEC_ASSERT (size_ >= 0 \
833 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
835 VEC_OP (T,A,reserve_exact) (vec_, \
836 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
837 VEC_CHECK_PASS PASS_MEM_STAT); \
838 VEC_BASE (*vec_)->num = size_; \
839 } \
840 \
841 static inline void VEC_OP (T,A,safe_grow_cleared) \
842 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
843 { \
844 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
845 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
846 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
847 sizeof (T) * (size_ - oldsize)); \
848 } \
849 \
850 static inline void VEC_OP(T,A,safe_splice) \
851 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
852 { \
853 if (src_) \
854 { \
855 VEC_OP (T,A,reserve_exact) (dst_, src_->num \
856 VEC_CHECK_PASS MEM_STAT_INFO); \
857 \
858 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
859 VEC_CHECK_PASS); \
860 } \
861 } \
862 \
863 static inline T *VEC_OP (T,A,safe_push) \
864 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
865 { \
866 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
867 \
868 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
869 } \
870 \
871 static inline T *VEC_OP (T,A,safe_insert) \
872 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
873 { \
874 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
875 \
876 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
877 VEC_CHECK_PASS); \
878 }
880 /* Vector of object. */
881 #define DEF_VEC_O(T) \
882 VEC_T_GTY(T,base); \
883 VEC_TA(T,base,none); \
884 DEF_VEC_FUNC_O(T) \
885 struct vec_swallow_trailing_semi
886 #define DEF_VEC_ALLOC_O(T,A) \
887 VEC_TA(T,base,A); \
888 DEF_VEC_ALLOC_FUNC_O(T,A) \
889 DEF_VEC_NONALLOC_FUNCS_O(T,A) \
890 struct vec_swallow_trailing_semi
892 #define DEF_VEC_FUNC_O(T) \
893 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
894 { \
895 return vec_ ? vec_->num : 0; \
896 } \
897 \
898 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
899 { \
901 \
902 return &vec_->vec[vec_->num - 1]; \
903 } \
904 \
905 static inline T *VEC_OP (T,base,index) \
906 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
907 { \
909 \
910 return &vec_->vec[ix_]; \
911 } \
912 \
913 static inline int VEC_OP (T,base,iterate) \
914 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
915 { \
916 if (vec_ && ix_ < vec_->num) \
917 { \
918 *ptr = &vec_->vec[ix_]; \
919 return 1; \
920 } \
921 else \
922 { \
923 *ptr = 0; \
924 return 0; \
925 } \
926 } \
927 \
928 static inline size_t VEC_OP (T,base,embedded_size) \
929 (int alloc_) \
930 { \
931 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
932 } \
933 \
934 static inline void VEC_OP (T,base,embedded_init) \
935 (VEC(T,base) *vec_, int alloc_) \
936 { \
937 vec_->num = 0; \
938 vec_->alloc = alloc_; \
939 } \
940 \
941 static inline int VEC_OP (T,base,space) \
942 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
943 { \
945 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
946 } \
947 \
948 static inline void VEC_OP(T,base,splice) \
949 (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
950 { \
951 if (src_) \
952 { \
953 unsigned len_ = src_->num; \
955 \
956 memcpy (&dst_->vec[dst_->num], &src_->vec[0], len_ * sizeof (T)); \
957 dst_->num += len_; \
958 } \
959 } \
960 \
961 static inline T *VEC_OP (T,base,quick_push) \
962 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
963 { \
964 T *slot_; \
965 \
967 slot_ = &vec_->vec[vec_->num++]; \
968 if (obj_) \
969 *slot_ = *obj_; \
970 \
971 return slot_; \
972 } \
973 \
974 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
975 { \
977 --vec_->num; \
978 } \
979 \
980 static inline void VEC_OP (T,base,truncate) \
981 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
982 { \
984 if (vec_) \
985 vec_->num = size_; \
986 } \
987 \
988 static inline T *VEC_OP (T,base,replace) \
989 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
990 { \
991 T *slot_; \
992 \
994 slot_ = &vec_->vec[ix_]; \
995 if (obj_) \
996 *slot_ = *obj_; \
997 \
998 return slot_; \
999 } \
1000 \
1001 static inline T *VEC_OP (T,base,quick_insert) \
1002 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
1003 { \
1004 T *slot_; \
1005 \
1008 slot_ = &vec_->vec[ix_]; \
1009 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
1010 if (obj_) \
1011 *slot_ = *obj_; \
1012 \
1013 return slot_; \
1014 } \
1015 \
1016 static inline void VEC_OP (T,base,ordered_remove) \
1017 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1018 { \
1019 T *slot_; \
1020 \
1022 slot_ = &vec_->vec[ix_]; \
1023 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
1024 } \
1025 \
1026 static inline void VEC_OP (T,base,unordered_remove) \
1027 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
1028 { \
1030 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
1031 } \
1032 \
1033 static inline void VEC_OP (T,base,block_remove) \
1034 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
1035 { \
1036 T *slot_; \
1037 \
1039 slot_ = &vec_->vec[ix_]; \
1040 vec_->num -= len_; \
1041 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
1042 } \
1043 \
1044 static inline T *VEC_OP (T,base,address) \
1045 (VEC(T,base) *vec_) \
1046 { \
1047 return vec_ ? vec_->vec : 0; \
1048 } \
1049 \
1050 static inline unsigned VEC_OP (T,base,lower_bound) \
1051 (VEC(T,base) *vec_, const T *obj_, \
1052 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
1053 { \
1054 unsigned int len_ = VEC_OP (T, base, length) (vec_); \
1055 unsigned int half_, middle_; \
1056 unsigned int first_ = 0; \
1057 while (len_ > 0) \
1058 { \
1059 T *middle_elem_; \
1060 half_ = len_ >> 1; \
1061 middle_ = first_; \
1062 middle_ += half_; \
1063 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
1064 if (lessthan_ (middle_elem_, obj_)) \
1065 { \
1066 first_ = middle_; \
1067 ++first_; \
1068 len_ = len_ - half_ - 1; \
1069 } \
1070 else \
1071 len_ = half_; \
1072 } \
1073 return first_; \
1074 }
1076 #define DEF_VEC_ALLOC_FUNC_O(T,A) \
1077 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1078 (int alloc_ MEM_STAT_DECL) \
1079 { \
1080 return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
1081 offsetof (VEC(T,A),base.vec), \
1082 sizeof (T) \
1083 PASS_MEM_STAT); \
1084 }
1086 #define DEF_VEC_NONALLOC_FUNCS_O(T,A) \
1087 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1088 { \
1089 size_t len_ = vec_ ? vec_->num : 0; \
1090 VEC (T,A) *new_vec_ = NULL; \
1091 \
1092 if (len_) \
1093 { \
1094 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1095 (NULL, len_, \
1096 offsetof (VEC(T,A),base.vec), sizeof (T) \
1097 PASS_MEM_STAT)); \
1098 \
1099 new_vec_->base.num = len_; \
1100 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1101 } \
1102 return new_vec_; \
1103 } \
1104 \
1105 static inline void VEC_OP (T,A,free) \
1106 (VEC(T,A) **vec_) \
1107 { \
1108 if (*vec_) \
1109 vec_##A##_free (*vec_); \
1110 *vec_ = NULL; \
1111 } \
1112 \
1113 static inline int VEC_OP (T,A,reserve) \
1114 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1115 { \
1116 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1117 VEC_CHECK_PASS); \
1118 \
1119 if (extend) \
1120 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1121 offsetof (VEC(T,A),base.vec),\
1122 sizeof (T) \
1123 PASS_MEM_STAT); \
1124 \
1125 return extend; \
1126 } \
1127 \
1128 static inline int VEC_OP (T,A,reserve_exact) \
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_exact \
1136 (*vec_, alloc_, \
1137 offsetof (VEC(T,A),base.vec), \
1138 sizeof (T) PASS_MEM_STAT); \
1139 \
1140 return extend; \
1141 } \
1142 \
1143 static inline void VEC_OP (T,A,safe_grow) \
1144 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1145 { \
1146 VEC_ASSERT (size_ >= 0 \
1147 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1149 VEC_OP (T,A,reserve_exact) (vec_, \
1150 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1151 VEC_CHECK_PASS PASS_MEM_STAT); \
1152 VEC_BASE (*vec_)->num = size_; \
1153 } \
1154 \
1155 static inline void VEC_OP (T,A,safe_grow_cleared) \
1156 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1157 { \
1158 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1159 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1160 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1161 sizeof (T) * (size_ - oldsize)); \
1162 } \
1163 \
1164 static inline void VEC_OP(T,A,safe_splice) \
1165 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1166 { \
1167 if (src_) \
1168 { \
1169 VEC_OP (T,A,reserve_exact) (dst_, src_->num \
1170 VEC_CHECK_PASS MEM_STAT_INFO); \
1171 \
1172 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1173 VEC_CHECK_PASS); \
1174 } \
1175 } \
1176 \
1177 static inline T *VEC_OP (T,A,safe_push) \
1178 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1179 { \
1180 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1181 \
1182 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1183 } \
1184 \
1185 static inline T *VEC_OP (T,A,safe_insert) \
1186 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
1187 VEC_CHECK_DECL MEM_STAT_DECL) \
1188 { \
1189 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1190 \
1191 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1192 VEC_CHECK_PASS); \
1193 }
1195 #define DEF_VEC_ALLOC_FUNC_I(T,A) \
1196 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1197 (int alloc_ MEM_STAT_DECL) \
1198 { \
1199 return (VEC(T,A) *) vec_##A##_o_reserve_exact \
1200 (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
1201 sizeof (T) PASS_MEM_STAT); \
1202 }
1204 #define DEF_VEC_NONALLOC_FUNCS_I(T,A) \
1205 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1206 { \
1207 size_t len_ = vec_ ? vec_->num : 0; \
1208 VEC (T,A) *new_vec_ = NULL; \
1209 \
1210 if (len_) \
1211 { \
1212 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1213 (NULL, len_, \
1214 offsetof (VEC(T,A),base.vec), sizeof (T) \
1215 PASS_MEM_STAT)); \
1216 \
1217 new_vec_->base.num = len_; \
1218 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1219 } \
1220 return new_vec_; \
1221 } \
1222 \
1223 static inline void VEC_OP (T,A,free) \
1224 (VEC(T,A) **vec_) \
1225 { \
1226 if (*vec_) \
1227 vec_##A##_free (*vec_); \
1228 *vec_ = NULL; \
1229 } \
1230 \
1231 static inline int VEC_OP (T,A,reserve) \
1232 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1233 { \
1234 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1235 VEC_CHECK_PASS); \
1236 \
1237 if (extend) \
1238 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1239 offsetof (VEC(T,A),base.vec),\
1240 sizeof (T) \
1241 PASS_MEM_STAT); \
1242 \
1243 return extend; \
1244 } \
1245 \
1246 static inline int VEC_OP (T,A,reserve_exact) \
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_exact \
1254 (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
1255 sizeof (T) PASS_MEM_STAT); \
1256 \
1257 return extend; \
1258 } \
1259 \
1260 static inline void VEC_OP (T,A,safe_grow) \
1261 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1262 { \
1263 VEC_ASSERT (size_ >= 0 \
1264 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1266 VEC_OP (T,A,reserve_exact) (vec_, \
1267 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1268 VEC_CHECK_PASS PASS_MEM_STAT); \
1269 VEC_BASE (*vec_)->num = size_; \
1270 } \
1271 \
1272 static inline void VEC_OP (T,A,safe_grow_cleared) \
1273 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1274 { \
1275 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
1276 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
1277 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
1278 sizeof (T) * (size_ - oldsize)); \
1279 } \
1280 \
1281 static inline void VEC_OP(T,A,safe_splice) \
1282 (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
1283 { \
1284 if (src_) \
1285 { \
1286 VEC_OP (T,A,reserve_exact) (dst_, src_->num \
1287 VEC_CHECK_PASS MEM_STAT_INFO); \
1288 \
1289 VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
1290 VEC_CHECK_PASS); \
1291 } \
1292 } \
1293 \
1294 static inline T *VEC_OP (T,A,safe_push) \
1295 (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1296 { \
1297 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1298 \
1299 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1300 } \
1301 \
1302 static inline T *VEC_OP (T,A,safe_insert) \
1303 (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
1304 VEC_CHECK_DECL MEM_STAT_DECL) \
1305 { \
1306 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1307 \
1308 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1309 VEC_CHECK_PASS); \
1310 }
1312 /* We support a vector which starts out with space on the stack and
1313 switches to heap space when forced to reallocate. This works a
1314 little differently. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1315 DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial
1316 space; because alloca can not be usefully called in an inline
1317 function, and because a macro can not define a macro, you must then
1318 write a #define for each type:
1320 #define VEC_{TYPE}_stack_alloc(alloc) \
1321 VEC_stack_alloc({TYPE}, alloc)
1323 This is really a hack and perhaps can be made better. Note that
1324 this macro will wind up evaluating the ALLOC parameter twice.
1326 Only the initial allocation will be made using alloca, so pass a
1327 reasonable estimate that doesn't use too much stack space; don't
1328 pass zero. Don't return a VEC(TYPE,stack) vector from the function
1329 which allocated it. */
1336 MEM_STAT_DECL);
1339 #ifdef GATHER_STATISTICS
1340 #define VEC_stack_alloc(T,alloc,name,line,function) \
1341 (VEC_OP (T,stack,alloc1) \
1342 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1343 #else
1344 #define VEC_stack_alloc(T,alloc) \
1345 (VEC_OP (T,stack,alloc1) \
1346 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1347 #endif
1349 #define DEF_VEC_ALLOC_P_STACK(T) \
1350 VEC_TA(T,base,stack); \
1351 DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1352 DEF_VEC_NONALLOC_FUNCS_P(T,stack) \
1353 struct vec_swallow_trailing_semi
1355 #define DEF_VEC_ALLOC_FUNC_P_STACK(T) \
1356 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1357 (int alloc_, VEC(T,stack)* space) \
1358 { \
1359 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1360 }
1362 #define DEF_VEC_ALLOC_O_STACK(T) \
1363 VEC_TA(T,base,stack); \
1364 DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1365 DEF_VEC_NONALLOC_FUNCS_O(T,stack) \
1366 struct vec_swallow_trailing_semi
1368 #define DEF_VEC_ALLOC_FUNC_O_STACK(T) \
1369 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1370 (int alloc_, VEC(T,stack)* space) \
1371 { \
1372 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1373 }
1375 #define DEF_VEC_ALLOC_I_STACK(T) \
1376 VEC_TA(T,base,stack); \
1377 DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1378 DEF_VEC_NONALLOC_FUNCS_I(T,stack) \
1379 struct vec_swallow_trailing_semi
1381 #define DEF_VEC_ALLOC_FUNC_I_STACK(T) \
1382 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
1383 (int alloc_, VEC(T,stack)* space) \
1384 { \
1385 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
1386 }