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