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