1 /* Vector API for GNU compiler.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
25 /* The macros here implement a set of templated vector types and
26 associated interfaces. These templates are implemented with
27 macros, as we're not in C++ land. The interface functions are
28 typesafe and use static inline functions, sometimes backed by
29 out-of-line generic functions. The vectors are designed to
30 interoperate with the GTY machinery.
32 Because of the different behavior of structure objects, scalar
33 objects and of pointers, there are three flavors, one for each of
34 these variants. Both the structure object and pointer variants
35 pass pointers to objects around -- in the former case the pointers
36 are stored into the vector and in the latter case the pointers are
37 dereferenced and the objects copied into the vector. The scalar
38 object variant is suitable for int-like objects, and the vector
39 elements are returned by value.
41 There are both 'index' and 'iterate' accessors. The iterator
42 returns a boolean iteration condition and updates the iteration
43 variable passed by reference. Because the iterator will be
44 inlined, the address-of can be optimized away.
46 The vectors are implemented using the trailing array idiom, thus
47 they are not resizeable without changing the address of the vector
48 object itself. This means you cannot have variables or fields of
49 vector type -- always use a pointer to a vector. The one exception
50 is the final field of a structure, which could be a vector type.
51 You will have to use the embedded_size & embedded_init calls to
52 create such objects, and they will probably not be resizeable (so
53 don't use the 'safe' allocation variants). The trailing array
54 idiom is used (rather than a pointer to an array of data), because,
55 if we allow NULL to also represent an empty vector, empty vectors
56 occupy minimal space in the structure containing them.
58 Each operation that increases the number of active elements is
59 available in 'quick' and 'safe' variants. The former presumes that
60 there is sufficient allocated space for the operation to succeed
61 (it dies if there is not). The latter will reallocate the
62 vector, if needed. Reallocation causes an exponential increase in
63 vector size. If you know you will be adding N elements, it would
64 be more efficient to use the reserve operation before adding the
65 elements with the 'quick' operation. This will ensure there are at
66 least as many elements as you ask for, it will exponentially
67 increase if there are too few spare slots. If you want reserve a
68 specific number of slots, but do not want the exponential increase
69 (for instance, you know this is the last allocation), use the
70 reserve_exact operation. You can also create a vector of a
71 specific size from the get go.
73 You should prefer the push and pop operations, as they append and
74 remove from the end of the vector. If you need to remove several
75 items in one go, use the truncate operation. The insert and remove
76 operations allow you to change elements in the middle of the
77 vector. There are two remove operations, one which preserves the
78 element ordering 'ordered_remove', and one which does not
79 'unordered_remove'. The latter function copies the end element
80 into the removed slot, rather than invoke a memmove operation. The
81 'lower_bound' function will determine where to place an item in the
82 array using insert that will maintain sorted order.
84 When a vector type is defined, first a non-memory managed version
85 is created. You can then define either or both garbage collected
86 and heap allocated versions. The allocation mechanism is specified
87 when the type is defined, and is therefore part of the type. If
88 you need both gc'd and heap allocated versions, you still must have
89 *exactly* one definition of the common non-memory managed base vector.
91 If you need to directly manipulate a vector, then the 'address'
92 accessor will return the address of the start of the vector. Also
93 the 'space' predicate will tell you whether there is spare capacity
94 in the vector. You will not normally need to use these two functions.
96 Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to
97 get the non-memory allocation version, and then a
98 DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed
99 vectors. Variables of vector type are declared using a
100 VEC(TYPEDEF,ALLOC) macro. The ALLOC argument specifies the
101 allocation strategy, and can be either 'gc' or 'heap' for garbage
102 collected and heap allocated respectively. It can be 'none' to get
103 a vector that must be explicitly allocated (for instance as a
104 trailing array of another structure). The characters O, P and I
105 indicate whether TYPEDEF is a pointer (P), object (O) or integral
106 (I) type. Be careful to pick the correct one, as you'll get an
107 awkward and inefficient API if you use the wrong one. There is a
108 check, which results in a compile-time warning, for the P and I
109 versions, but there is no check for the O versions, as that is not
110 possible in plain C. Due to the way GTY works, you must annotate
111 any structures you wish to insert or reference from a vector with a
112 GTY(()) tag. You need to do this even if you never declare the GC
115 An example of their use would be,
117 DEF_VEC_P(tree); // non-managed tree vector.
118 DEF_VEC_ALLOC_P(tree,gc); // gc'd vector of tree pointers. This must
119 // appear at file scope.
122 VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers.
127 if (VEC_length(tree,s->v)) { we have some contents }
128 VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
129 for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
130 { do something with elt }
134 /* Macros to invoke API calls. A single macro works for both pointer
135 and object vectors, but the argument and return types might well be
136 different. In each macro, T is the typedef of the vector elements,
137 and A is the allocation strategy. The allocation strategy is only
138 present when it is required. Some of these macros pass the vector,
139 V, by reference (by taking its address), this is noted in the
143 unsigned VEC_T_length(const VEC(T) *v);
145 Return the number of active elements in V. V can be NULL, in which
146 case zero is returned. */
148 #define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
151 /* Check if vector is empty
152 int VEC_T_empty(const VEC(T) *v);
154 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
156 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
159 /* Get the final element of the vector.
160 T VEC_T_last(VEC(T) *v); // Integer
161 T VEC_T_last(VEC(T) *v); // Pointer
162 T *VEC_T_last(VEC(T) *v); // Object
164 Return the final element. V must not be empty. */
166 #define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
169 T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
170 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
171 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
173 Return the IX'th element. If IX must be in the domain of V. */
175 #define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
177 /* Iterate over vector
178 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
179 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
180 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
182 Return iteration condition and update PTR to point to the IX'th
183 element. At the end of iteration, sets PTR to NULL. Use this to
184 iterate over the elements of a vector as follows,
186 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
189 #define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
191 /* Allocate new vector.
192 VEC(T,A) *VEC_T_A_alloc(int reserve);
194 Allocate a new vector with space for RESERVE objects. If RESERVE
195 is zero, NO vector is created. */
197 #define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
200 void VEC_T_A_free(VEC(T,A) *&);
202 Free a vector and set it to NULL. */
204 #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
206 /* Use these to determine the required size and initialization of a
207 vector embedded within another structure (as the final member).
209 size_t VEC_T_embedded_size(int reserve);
210 void VEC_T_embedded_init(VEC(T) *v, int reserve);
212 These allow the caller to perform the memory allocation. */
214 #define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N))
215 #define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
218 VEC(T,A) *VEC_T_A_copy(VEC(T) *);
220 Copy the live elements of a vector into a new vector. The new and
221 old vectors need not be allocated by the same mechanism. */
223 #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
225 /* Determine if a vector has additional capacity.
227 int VEC_T_space (VEC(T) *v,int reserve)
229 If V has space for RESERVE additional entries, return nonzero. You
230 usually only need to use this if you are doing your own vector
231 reallocation, for instance on an embedded vector. This returns
232 nonzero in exactly the same circumstances that VEC_T_reserve
235 #define VEC_space(T,V,R) \
236 (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
239 int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
241 Ensure that V has at least RESERVE slots available. This will
242 create additional headroom. Note this can cause V to be
243 reallocated. Returns nonzero iff reallocation actually
246 #define VEC_reserve(T,A,V,R) \
247 (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
249 /* Reserve space exactly.
250 int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
252 Ensure that V has at least RESERVE slots available. This will not
253 create additional headroom. Note this can cause V to be
254 reallocated. Returns nonzero iff reallocation actually
257 #define VEC_reserve_exact(T,A,V,R) \
258 (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
260 /* Push object with no reallocation
261 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
262 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
263 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
265 Push a new element onto the end, returns a pointer to the slot
266 filled in. For object vectors, the new value can be NULL, in which
267 case NO initialization is performed. There must
268 be sufficient space in the vector. */
270 #define VEC_quick_push(T,V,O) \
271 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
273 /* Push object with reallocation
274 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
275 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
276 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
278 Push a new element onto the end, returns a pointer to the slot
279 filled in. For object vectors, the new value can be NULL, in which
280 case NO initialization is performed. Reallocates V, if needed. */
282 #define VEC_safe_push(T,A,V,O) \
283 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
285 /* Pop element off end
286 T VEC_T_pop (VEC(T) *v); // Integer
287 T VEC_T_pop (VEC(T) *v); // Pointer
288 void VEC_T_pop (VEC(T) *v); // Object
290 Pop the last element off the end. Returns the element popped, for
293 #define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
295 /* Truncate to specific length
296 void VEC_T_truncate (VEC(T) *v, unsigned len);
298 Set the length as specified. The new length must be less than or
299 equal to the current length. This is an O(1) operation. */
301 #define VEC_truncate(T,V,I) \
302 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
304 /* Grow to a specific length.
305 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
307 Grow the vector to a specific length. The LEN must be as
308 long or longer than the current length. The new elements are
311 #define VEC_safe_grow(T,A,V,I) \
312 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
315 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
316 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
317 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
319 Replace the IXth element of V with a new value, VAL. For pointer
320 vectors returns the original value. For object vectors returns a
321 pointer to the new value. For object vectors the new value can be
322 NULL, in which case no overwriting of the slot is actually
325 #define VEC_replace(T,V,I,O) \
326 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
328 /* Insert object with no reallocation
329 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
330 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
331 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
333 Insert an element, VAL, at the IXth position of V. Return a pointer
334 to the slot created. For vectors of object, the new value can be
335 NULL, in which case no initialization of the inserted slot takes
336 place. There must be sufficient space. */
338 #define VEC_quick_insert(T,V,I,O) \
339 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
341 /* Insert object with reallocation
342 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
343 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
344 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
346 Insert an element, VAL, at the IXth position of V. Return a pointer
347 to the slot created. For vectors of object, the new value can be
348 NULL, in which case no initialization of the inserted slot takes
349 place. Reallocate V, if necessary. */
351 #define VEC_safe_insert(T,A,V,I,O) \
352 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
354 /* Remove element retaining order
355 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
356 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
357 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
359 Remove an element from the IXth position of V. Ordering of
360 remaining elements is preserved. For pointer vectors returns the
361 removed object. This is an O(N) operation due to a memmove. */
363 #define VEC_ordered_remove(T,V,I) \
364 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
366 /* Remove element destroying order
367 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
368 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
369 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
371 Remove an element from the IXth position of V. Ordering of
372 remaining elements is destroyed. For pointer vectors returns the
373 removed object. This is an O(1) operation. */
375 #define VEC_unordered_remove(T,V,I) \
376 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
378 /* Remove a block of elements
379 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
381 Remove LEN elements starting at the IXth. Ordering is retained.
382 This is an O(1) operation. */
384 #define VEC_block_remove(T,V,I,L) \
385 (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
387 /* Get the address of the array of elements
388 T *VEC_T_address (VEC(T) v)
390 If you need to directly manipulate the array (for instance, you
391 want to feed it to qsort), use this accessor. */
393 #define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
395 /* Find the first index in the vector not less than the object.
396 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
397 bool (*lessthan) (const T, const T)); // Integer
398 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
399 bool (*lessthan) (const T, const T)); // Pointer
400 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
401 bool (*lessthan) (const T*, const T*)); // Object
403 Find the first position in which VAL could be inserted without
404 changing the ordering of V. LESSTHAN is a function that returns
405 true if the first argument is strictly less than the second. */
407 #define VEC_lower_bound(T,V,O,LT) \
408 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
411 /* Reallocate an array of elements with prefix. */
412 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
413 extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
414 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
415 extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
417 extern void ggc_free (void *);
418 #define vec_gc_free(V) ggc_free (V)
419 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
420 extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
421 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
422 extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
424 #define vec_heap_free(V) free (V)
427 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
428 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
429 #define VEC_CHECK_PASS ,file_,line_,function_
431 #define VEC_ASSERT(EXPR,OP,T,A) \
432 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
434 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
436 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
438 #define VEC_CHECK_INFO
439 #define VEC_CHECK_DECL
440 #define VEC_CHECK_PASS
441 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
444 #define VEC(T,A) VEC_##T##_##A
445 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
446 #else /* IN_GENGTYPE */
447 #define VEC(T,A) VEC_ T _ A
448 #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
449 #define VEC_STRINGIFY_(X) #X
451 #endif /* IN_GENGTYPE */
453 /* Base of vector type, not user visible. */
455 typedef struct VEC(T,B) \
462 #define VEC_T_GTY(T,B) \
463 typedef struct VEC(T,B) GTY(()) \
467 T GTY ((length ("%h.num"))) vec[1]; \
470 /* Derived vector type, user visible. */
471 #define VEC_TA_GTY(T,B,A,GTY) \
472 typedef struct VEC(T,A) GTY \
477 /* Convert to base type. */
478 #define VEC_BASE(P) ((P) ? &(P)->base : 0)
480 /* Vector of integer-like object. */
482 {"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"},
483 {"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL},
485 #define DEF_VEC_I(T) \
486 static inline void VEC_OP (T,must_be,integral_type) (void) \
492 VEC_TA_GTY(T,base,none,); \
494 struct vec_swallow_trailing_semi
495 #define DEF_VEC_ALLOC_I(T,A) \
496 VEC_TA_GTY(T,base,A,); \
497 DEF_VEC_ALLOC_FUNC_I(T,A) \
498 struct vec_swallow_trailing_semi
501 /* Vector of pointer to object. */
503 {"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
504 {"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL},
506 #define DEF_VEC_P(T) \
507 static inline void VEC_OP (T,must_be,pointer_type) (void) \
509 (void)((T)1 == (void *)1); \
513 VEC_TA_GTY(T,base,none,); \
515 struct vec_swallow_trailing_semi
516 #define DEF_VEC_ALLOC_P(T,A) \
517 VEC_TA_GTY(T,base,A,); \
518 DEF_VEC_ALLOC_FUNC_P(T,A) \
519 struct vec_swallow_trailing_semi
522 #define DEF_VEC_FUNC_P(T) \
523 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
525 return vec_ ? vec_->num : 0; \
528 static inline T VEC_OP (T,base,last) \
529 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
531 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \
533 return vec_->vec[vec_->num - 1]; \
536 static inline T VEC_OP (T,base,index) \
537 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
539 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \
541 return vec_->vec[ix_]; \
544 static inline int VEC_OP (T,base,iterate) \
545 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
547 if (vec_ && ix_ < vec_->num) \
549 *ptr = vec_->vec[ix_]; \
559 static inline size_t VEC_OP (T,base,embedded_size) \
562 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
565 static inline void VEC_OP (T,base,embedded_init) \
566 (VEC(T,base) *vec_, int alloc_) \
569 vec_->alloc = alloc_; \
572 static inline int VEC_OP (T,base,space) \
573 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
575 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
576 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
579 static inline T *VEC_OP (T,base,quick_push) \
580 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
584 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \
585 slot_ = &vec_->vec[vec_->num++]; \
591 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
595 VEC_ASSERT (vec_->num, "pop", T, base); \
596 obj_ = vec_->vec[--vec_->num]; \
601 static inline void VEC_OP (T,base,truncate) \
602 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
604 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \
609 static inline T VEC_OP (T,base,replace) \
610 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
614 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \
615 old_obj_ = vec_->vec[ix_]; \
616 vec_->vec[ix_] = obj_; \
621 static inline T *VEC_OP (T,base,quick_insert) \
622 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
626 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \
627 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \
628 slot_ = &vec_->vec[ix_]; \
629 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
635 static inline T VEC_OP (T,base,ordered_remove) \
636 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
641 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
642 slot_ = &vec_->vec[ix_]; \
644 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
649 static inline T VEC_OP (T,base,unordered_remove) \
650 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
655 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
656 slot_ = &vec_->vec[ix_]; \
658 *slot_ = vec_->vec[--vec_->num]; \
663 static inline void VEC_OP (T,base,block_remove) \
664 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
668 VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \
669 slot_ = &vec_->vec[ix_]; \
671 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
674 static inline T *VEC_OP (T,base,address) \
675 (VEC(T,base) *vec_) \
677 return vec_ ? vec_->vec : 0; \
680 static inline unsigned VEC_OP (T,base,lower_bound) \
681 (VEC(T,base) *vec_, const T obj_, \
682 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
684 unsigned int len_ = VEC_OP (T,base, length) (vec_); \
685 unsigned int half_, middle_; \
686 unsigned int first_ = 0; \
693 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
694 if (lessthan_ (middle_elem_, obj_)) \
698 len_ = len_ - half_ - 1; \
706 #define DEF_VEC_ALLOC_FUNC_P(T,A) \
707 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
708 (int alloc_ MEM_STAT_DECL) \
710 return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
714 static inline void VEC_OP (T,A,free) \
718 vec_##A##_free (*vec_); \
722 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
724 size_t len_ = vec_ ? vec_->num : 0; \
725 VEC (T,A) *new_vec_ = NULL; \
729 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
730 (NULL, len_ PASS_MEM_STAT)); \
732 new_vec_->base.num = len_; \
733 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
738 static inline int VEC_OP (T,A,reserve) \
739 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
741 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
745 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
750 static inline int VEC_OP (T,A,reserve_exact) \
751 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
753 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
757 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
763 static inline void VEC_OP (T,A,safe_grow) \
764 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
766 VEC_ASSERT (size_ >= 0 \
767 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
769 VEC_OP (T,A,reserve_exact) (vec_, \
770 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
771 VEC_CHECK_PASS PASS_MEM_STAT); \
772 VEC_BASE (*vec_)->num = size_; \
775 static inline T *VEC_OP (T,A,safe_push) \
776 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
778 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
780 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
783 static inline T *VEC_OP (T,A,safe_insert) \
784 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
786 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
788 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
792 /* Vector of object. */
794 {"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
795 {"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL},
797 #define DEF_VEC_O(T) \
799 VEC_TA_GTY(T,base,none,); \
801 struct vec_swallow_trailing_semi
802 #define DEF_VEC_ALLOC_O(T,A) \
803 VEC_TA_GTY(T,base,A,); \
804 DEF_VEC_ALLOC_FUNC_O(T,A) \
805 struct vec_swallow_trailing_semi
808 #define DEF_VEC_FUNC_O(T) \
809 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
811 return vec_ ? vec_->num : 0; \
814 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
816 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \
818 return &vec_->vec[vec_->num - 1]; \
821 static inline T *VEC_OP (T,base,index) \
822 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
824 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \
826 return &vec_->vec[ix_]; \
829 static inline int VEC_OP (T,base,iterate) \
830 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
832 if (vec_ && ix_ < vec_->num) \
834 *ptr = &vec_->vec[ix_]; \
844 static inline size_t VEC_OP (T,base,embedded_size) \
847 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
850 static inline void VEC_OP (T,base,embedded_init) \
851 (VEC(T,base) *vec_, int alloc_) \
854 vec_->alloc = alloc_; \
857 static inline int VEC_OP (T,base,space) \
858 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
860 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
861 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
864 static inline T *VEC_OP (T,base,quick_push) \
865 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
869 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \
870 slot_ = &vec_->vec[vec_->num++]; \
877 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
879 VEC_ASSERT (vec_->num, "pop", T, base); \
883 static inline void VEC_OP (T,base,truncate) \
884 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
886 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \
891 static inline T *VEC_OP (T,base,replace) \
892 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
896 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \
897 slot_ = &vec_->vec[ix_]; \
904 static inline T *VEC_OP (T,base,quick_insert) \
905 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
909 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \
910 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \
911 slot_ = &vec_->vec[ix_]; \
912 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
919 static inline void VEC_OP (T,base,ordered_remove) \
920 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
924 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
925 slot_ = &vec_->vec[ix_]; \
926 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
929 static inline void VEC_OP (T,base,unordered_remove) \
930 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
932 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
933 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
936 static inline void VEC_OP (T,base,block_remove) \
937 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
941 VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \
942 slot_ = &vec_->vec[ix_]; \
944 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
947 static inline T *VEC_OP (T,base,address) \
948 (VEC(T,base) *vec_) \
950 return vec_ ? vec_->vec : 0; \
953 static inline unsigned VEC_OP (T,base,lower_bound) \
954 (VEC(T,base) *vec_, const T *obj_, \
955 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
957 unsigned int len_ = VEC_OP (T, base, length) (vec_); \
958 unsigned int half_, middle_; \
959 unsigned int first_ = 0; \
966 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
967 if (lessthan_ (middle_elem_, obj_)) \
971 len_ = len_ - half_ - 1; \
979 #define DEF_VEC_ALLOC_FUNC_O(T,A) \
980 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
981 (int alloc_ MEM_STAT_DECL) \
983 return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
984 offsetof (VEC(T,A),base.vec), \
989 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
991 size_t len_ = vec_ ? vec_->num : 0; \
992 VEC (T,A) *new_vec_ = NULL; \
996 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
998 offsetof (VEC(T,A),base.vec), sizeof (T) \
1001 new_vec_->base.num = len_; \
1002 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1007 static inline void VEC_OP (T,A,free) \
1011 vec_##A##_free (*vec_); \
1015 static inline int VEC_OP (T,A,reserve) \
1016 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1018 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1022 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1023 offsetof (VEC(T,A),base.vec),\
1030 static inline int VEC_OP (T,A,reserve_exact) \
1031 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1033 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1037 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1039 offsetof (VEC(T,A),base.vec), \
1040 sizeof (T) PASS_MEM_STAT); \
1045 static inline void VEC_OP (T,A,safe_grow) \
1046 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1048 VEC_ASSERT (size_ >= 0 \
1049 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1051 VEC_OP (T,A,reserve_exact) (vec_, \
1052 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1053 VEC_CHECK_PASS PASS_MEM_STAT); \
1054 VEC_BASE (*vec_)->num = size_; \
1057 static inline T *VEC_OP (T,A,safe_push) \
1058 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1060 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1062 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1065 static inline T *VEC_OP (T,A,safe_insert) \
1066 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
1067 VEC_CHECK_DECL MEM_STAT_DECL) \
1069 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1071 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1075 #define DEF_VEC_ALLOC_FUNC_I(T,A) \
1076 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
1077 (int alloc_ MEM_STAT_DECL) \
1079 return (VEC(T,A) *) vec_##A##_o_reserve_exact \
1080 (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
1081 sizeof (T) PASS_MEM_STAT); \
1084 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1086 size_t len_ = vec_ ? vec_->num : 0; \
1087 VEC (T,A) *new_vec_ = NULL; \
1091 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
1093 offsetof (VEC(T,A),base.vec), sizeof (T) \
1096 new_vec_->base.num = len_; \
1097 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
1102 static inline void VEC_OP (T,A,free) \
1106 vec_##A##_free (*vec_); \
1110 static inline int VEC_OP (T,A,reserve) \
1111 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1113 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1117 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
1118 offsetof (VEC(T,A),base.vec),\
1125 static inline int VEC_OP (T,A,reserve_exact) \
1126 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
1128 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
1132 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
1133 (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
1134 sizeof (T) PASS_MEM_STAT); \
1139 static inline void VEC_OP (T,A,safe_grow) \
1140 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
1142 VEC_ASSERT (size_ >= 0 \
1143 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1145 VEC_OP (T,A,reserve_exact) (vec_, \
1146 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1147 VEC_CHECK_PASS PASS_MEM_STAT); \
1148 VEC_BASE (*vec_)->num = size_; \
1151 static inline T *VEC_OP (T,A,safe_push) \
1152 (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
1154 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1156 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
1159 static inline T *VEC_OP (T,A,safe_insert) \
1160 (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
1161 VEC_CHECK_DECL MEM_STAT_DECL) \
1163 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1165 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1169 #endif /* GCC_VEC_H */