?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Parallelize in_ifaddrhead operation
[dragonfly.git] / contrib / gcc-4.1 / gcc / vec.h
blob586797a6eec7ad1d48cac26511ff8fafaf7ed615
1 /* Vector API for GNU compiler.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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
20 02110-1301, USA. */
21
22 #ifndef GCC_VEC_H
23 #define GCC_VEC_H
24
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.
31
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.
40
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.
45
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.
57
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 a
70 negative number for reservation. You can also create a vector of a
71 specific size from the get go.
72
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.
83
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.
90
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.
95
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
113 allocated variants.
114
115 An example of their use would be,
116
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.
120
121 struct my_struct {
122 VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers.
123 };
124
125 struct my_struct *s;
126
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 }
131
132 */
133
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
140 descriptions. */
141
142 /* Length of vector
143 unsigned VEC_T_length(const VEC(T) *v);
144
145 Return the number of active elements in V. V can be NULL, in which
146 case zero is returned. */
147
148 #define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
149
150
151 /* Check if vector is empty
152 int VEC_T_empty(const VEC(T) *v);
153
154 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
155
156 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
157
158
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
163
164 Return the final element. V must not be empty. */
165
166 #define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
167
168 /* Index into vector
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
172
173 Return the IX'th element. If IX must be in the domain of V. */
174
175 #define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
176
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
181
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,
185
186 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
187 continue; */
188
189 #define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
190
191 /* Allocate new vector.
192 VEC(T,A) *VEC_T_A_alloc(int reserve);
193
194 Allocate a new vector with space for RESERVE objects. If RESERVE
195 is zero, NO vector is created. */
196
197 #define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
198
199 /* Free a vector.
200 void VEC_T_A_free(VEC(T,A) *&);
201
202 Free a vector and set it to NULL. */
203
204 #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
205
206 /* Use these to determine the required size and initialization of a
207 vector embedded within another structure (as the final member).
208
209 size_t VEC_T_embedded_size(int reserve);
210 void VEC_T_embedded_init(VEC(T) *v, int reserve);
211
212 These allow the caller to perform the memory allocation. */
213
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))
216
217 /* Copy a vector.
218 VEC(T,A) *VEC_T_A_copy(VEC(T) *);
219
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. */
222
223 #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
224
225 /* Determine if a vector has additional capacity.
226
227 int VEC_T_space (VEC(T) *v,int reserve)
228
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
233 will. */
234
235 #define VEC_space(T,V,R) \
236 (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
237
238 /* Reserve space.
239 int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
240
241 Ensure that V has at least abs(RESERVE) slots available. The
242 signedness of RESERVE determines the reallocation behavior. A
243 negative value will not create additional headroom beyond that
244 requested. A positive value will create additional headroom. Note
245 this can cause V to be reallocated. Returns nonzero iff
246 reallocation actually 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 /* Push object with no reallocation
252 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
253 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
254 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
255
256 Push a new element onto the end, returns a pointer to the slot
257 filled in. For object vectors, the new value can be NULL, in which
258 case NO initialization is performed. There must
259 be sufficient space in the vector. */
260
261 #define VEC_quick_push(T,V,O) \
262 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
263
264 /* Push object with reallocation
265 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
266 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
267 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
268
269 Push a new element onto the end, returns a pointer to the slot
270 filled in. For object vectors, the new value can be NULL, in which
271 case NO initialization is performed. Reallocates V, if needed. */
272
273 #define VEC_safe_push(T,A,V,O) \
274 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
275
276 /* Pop element off end
277 T VEC_T_pop (VEC(T) *v); // Integer
278 T VEC_T_pop (VEC(T) *v); // Pointer
279 void VEC_T_pop (VEC(T) *v); // Object
280
281 Pop the last element off the end. Returns the element popped, for
282 pointer vectors. */
283
284 #define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
285
286 /* Truncate to specific length
287 void VEC_T_truncate (VEC(T) *v, unsigned len);
288
289 Set the length as specified. The new length must be less than or
290 equal to the current length. This is an O(1) operation. */
291
292 #define VEC_truncate(T,V,I) \
293 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
294
295 /* Grow to a specific length.
296 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
297
298 Grow the vector to a specific length. The LEN must be as
299 long or longer than the current length. The new elements are
300 uninitialized. */
301
302 #define VEC_safe_grow(T,A,V,I) \
303 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
304
305 /* Replace element
306 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
307 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
308 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
309
310 Replace the IXth element of V with a new value, VAL. For pointer
311 vectors returns the original value. For object vectors returns a
312 pointer to the new value. For object vectors the new value can be
313 NULL, in which case no overwriting of the slot is actually
314 performed. */
315
316 #define VEC_replace(T,V,I,O) \
317 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
318
319 /* Insert object with no reallocation
320 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
321 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
322 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
323
324 Insert an element, VAL, at the IXth position of V. Return a pointer
325 to the slot created. For vectors of object, the new value can be
326 NULL, in which case no initialization of the inserted slot takes
327 place. There must be sufficient space. */
328
329 #define VEC_quick_insert(T,V,I,O) \
330 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
331
332 /* Insert object with reallocation
333 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
334 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
335 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
336
337 Insert an element, VAL, at the IXth position of V. Return a pointer
338 to the slot created. For vectors of object, the new value can be
339 NULL, in which case no initialization of the inserted slot takes
340 place. Reallocate V, if necessary. */
341
342 #define VEC_safe_insert(T,A,V,I,O) \
343 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
344
345 /* Remove element retaining order
346 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
347 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
348 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
349
350 Remove an element from the IXth position of V. Ordering of
351 remaining elements is preserved. For pointer vectors returns the
352 removed object. This is an O(N) operation due to a memmove. */
353
354 #define VEC_ordered_remove(T,V,I) \
355 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
356
357 /* Remove element destroying order
358 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
359 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
360 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
361
362 Remove an element from the IXth position of V. Ordering of
363 remaining elements is destroyed. For pointer vectors returns the
364 removed object. This is an O(1) operation. */
365
366 #define VEC_unordered_remove(T,V,I) \
367 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
368
369 /* Get the address of the array of elements
370 T *VEC_T_address (VEC(T) v)
371
372 If you need to directly manipulate the array (for instance, you
373 want to feed it to qsort), use this accessor. */
374
375 #define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
376
377 /* Find the first index in the vector not less than the object.
378 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
379 bool (*lessthan) (const T, const T)); // Integer
380 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
381 bool (*lessthan) (const T, const T)); // Pointer
382 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
383 bool (*lessthan) (const T*, const T*)); // Object
384
385 Find the first position in which VAL could be inserted without
386 changing the ordering of V. LESSTHAN is a function that returns
387 true if the first argument is strictly less than the second. */
388
389 #define VEC_lower_bound(T,V,O,LT) \
390 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
391
392 #if !IN_GENGTYPE
393 /* Reallocate an array of elements with prefix. */
394 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
395 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
396 extern void ggc_free (void *);
397 #define vec_gc_free(V) ggc_free (V)
398 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
399 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
400 #define vec_heap_free(V) free (V)
401
402 #if ENABLE_CHECKING
403 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
404 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
405 #define VEC_CHECK_PASS ,file_,line_,function_
406
407 #define VEC_ASSERT(EXPR,OP,T,A) \
408 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
409
410 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
411 ATTRIBUTE_NORETURN;
412 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
413 #else
414 #define VEC_CHECK_INFO
415 #define VEC_CHECK_DECL
416 #define VEC_CHECK_PASS
417 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
418 #endif
419
420 #define VEC(T,A) VEC_##T##_##A
421 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
422 #else /* IN_GENGTYPE */
423 #define VEC(T,A) VEC_ T _ A
424 #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
425 #define VEC_STRINGIFY_(X) #X
426 #undef GTY
427 #endif /* IN_GENGTYPE */
428
429 /* Base of vector type, not user visible. */
430 #define VEC_T(T,B) \
431 typedef struct VEC(T,B) \
432 { \
433 unsigned num; \
434 unsigned alloc; \
435 T vec[1]; \
436 } VEC(T,B)
437
438 #define VEC_T_GTY(T,B) \
439 typedef struct VEC(T,B) GTY(()) \
440 { \
441 unsigned num; \
442 unsigned alloc; \
443 T GTY ((length ("%h.num"))) vec[1]; \
444 } VEC(T,B)
445
446 /* Derived vector type, user visible. */
447 #define VEC_TA_GTY(T,B,A,GTY) \
448 typedef struct VEC(T,A) GTY \
449 { \
450 VEC(T,B) base; \
451 } VEC(T,A)
452
453 /* Convert to base type. */
454 #define VEC_BASE(P) ((P) ? &(P)->base : 0)
455
456 /* Vector of integer-like object. */
457 #if IN_GENGTYPE
458 {"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"},
459 {"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL},
460 #else
461 #define DEF_VEC_I(T) \
462 static inline void VEC_OP (T,must_be,integral_type) (void) \
463 { \
464 (void)~(T)0; \
465 } \
466 \
467 VEC_T(T,base); \
468 VEC_TA_GTY(T,base,none,); \
469 DEF_VEC_FUNC_P(T) \
470 struct vec_swallow_trailing_semi
471 #define DEF_VEC_ALLOC_I(T,A) \
472 VEC_TA_GTY(T,base,A,); \
473 DEF_VEC_ALLOC_FUNC_P(T,A) \
474 struct vec_swallow_trailing_semi
475 #endif
476
477 /* Vector of pointer to object. */
478 #if IN_GENGTYPE
479 {"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
480 {"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL},
481 #else
482 #define DEF_VEC_P(T) \
483 static inline void VEC_OP (T,must_be,pointer_type) (void) \
484 { \
485 (void)((T)1 == (void *)1); \
486 } \
487 \
488 VEC_T_GTY(T,base); \
489 VEC_TA_GTY(T,base,none,); \
490 DEF_VEC_FUNC_P(T) \
491 struct vec_swallow_trailing_semi
492 #define DEF_VEC_ALLOC_P(T,A) \
493 VEC_TA_GTY(T,base,A,); \
494 DEF_VEC_ALLOC_FUNC_P(T,A) \
495 struct vec_swallow_trailing_semi
496 #endif
497
498 #define DEF_VEC_FUNC_P(T) \
499 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
500 { \
501 return vec_ ? vec_->num : 0; \
502 } \
503 \
504 static inline T VEC_OP (T,base,last) \
505 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
506 { \
507 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \
508 \
509 return vec_->vec[vec_->num - 1]; \
510 } \
511 \
512 static inline T VEC_OP (T,base,index) \
513 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
514 { \
515 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \
516 \
517 return vec_->vec[ix_]; \
518 } \
519 \
520 static inline int VEC_OP (T,base,iterate) \
521 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
522 { \
523 if (vec_ && ix_ < vec_->num) \
524 { \
525 *ptr = vec_->vec[ix_]; \
526 return 1; \
527 } \
528 else \
529 { \
530 *ptr = 0; \
531 return 0; \
532 } \
533 } \
534 \
535 static inline size_t VEC_OP (T,base,embedded_size) \
536 (int alloc_) \
537 { \
538 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
539 } \
540 \
541 static inline void VEC_OP (T,base,embedded_init) \
542 (VEC(T,base) *vec_, int alloc_) \
543 { \
544 vec_->num = 0; \
545 vec_->alloc = alloc_; \
546 } \
547 \
548 static inline int VEC_OP (T,base,space) \
549 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
550 { \
551 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
552 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
553 } \
554 \
555 static inline T *VEC_OP (T,base,quick_push) \
556 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
557 { \
558 T *slot_; \
559 \
560 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \
561 slot_ = &vec_->vec[vec_->num++]; \
562 *slot_ = obj_; \
563 \
564 return slot_; \
565 } \
566 \
567 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
568 { \
569 T obj_; \
570 \
571 VEC_ASSERT (vec_->num, "pop", T, base); \
572 obj_ = vec_->vec[--vec_->num]; \
573 \
574 return obj_; \
575 } \
576 \
577 static inline void VEC_OP (T,base,truncate) \
578 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
579 { \
580 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \
581 if (vec_) \
582 vec_->num = size_; \
583 } \
584 \
585 static inline T VEC_OP (T,base,replace) \
586 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
587 { \
588 T old_obj_; \
589 \
590 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \
591 old_obj_ = vec_->vec[ix_]; \
592 vec_->vec[ix_] = obj_; \
593 \
594 return old_obj_; \
595 } \
596 \
597 static inline T *VEC_OP (T,base,quick_insert) \
598 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
599 { \
600 T *slot_; \
601 \
602 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \
603 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \
604 slot_ = &vec_->vec[ix_]; \
605 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
606 *slot_ = obj_; \
607 \
608 return slot_; \
609 } \
610 \
611 static inline T VEC_OP (T,base,ordered_remove) \
612 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
613 { \
614 T *slot_; \
615 T obj_; \
616 \
617 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
618 slot_ = &vec_->vec[ix_]; \
619 obj_ = *slot_; \
620 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
621 \
622 return obj_; \
623 } \
624 \
625 static inline T VEC_OP (T,base,unordered_remove) \
626 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
627 { \
628 T *slot_; \
629 T obj_; \
630 \
631 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
632 slot_ = &vec_->vec[ix_]; \
633 obj_ = *slot_; \
634 *slot_ = vec_->vec[--vec_->num]; \
635 \
636 return obj_; \
637 } \
638 \
639 static inline T *VEC_OP (T,base,address) \
640 (VEC(T,base) *vec_) \
641 { \
642 return vec_ ? vec_->vec : 0; \
643 } \
644 \
645 static inline unsigned VEC_OP (T,base,lower_bound) \
646 (VEC(T,base) *vec_, const T obj_, \
647 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
648 { \
649 unsigned int len_ = VEC_OP (T,base, length) (vec_); \
650 unsigned int half_, middle_; \
651 unsigned int first_ = 0; \
652 while (len_ > 0) \
653 { \
654 T middle_elem_; \
655 half_ = len_ >> 1; \
656 middle_ = first_; \
657 middle_ += half_; \
658 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
659 if (lessthan_ (middle_elem_, obj_)) \
660 { \
661 first_ = middle_; \
662 ++first_; \
663 len_ = len_ - half_ - 1; \
664 } \
665 else \
666 len_ = half_; \
667 } \
668 return first_; \
669 }
670
671 #define DEF_VEC_ALLOC_FUNC_P(T,A) \
672 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
673 (int alloc_ MEM_STAT_DECL) \
674 { \
675 /* We must request exact size allocation, hence the negation. */ \
676 return (VEC(T,A) *) vec_##A##_p_reserve (NULL, -alloc_ PASS_MEM_STAT); \
677 } \
678 \
679 static inline void VEC_OP (T,A,free) \
680 (VEC(T,A) **vec_) \
681 { \
682 if (*vec_) \
683 vec_##A##_free (*vec_); \
684 *vec_ = NULL; \
685 } \
686 \
687 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
688 { \
689 size_t len_ = vec_ ? vec_->num : 0; \
690 VEC (T,A) *new_vec_ = NULL; \
691 \
692 if (len_) \
693 { \
694 /* We must request exact size allocation, hence the negation. */ \
695 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve \
696 (NULL, -len_ PASS_MEM_STAT)); \
697 \
698 new_vec_->base.num = len_; \
699 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
700 } \
701 return new_vec_; \
702 } \
703 \
704 static inline int VEC_OP (T,A,reserve) \
705 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
706 { \
707 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \
708 alloc_ < 0 ? -alloc_ : alloc_ \
709 VEC_CHECK_PASS); \
710 \
711 if (extend) \
712 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
713 \
714 return extend; \
715 } \
716 \
717 static inline void VEC_OP (T,A,safe_grow) \
718 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
719 { \
720 VEC_ASSERT (size_ >= 0 \
721 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
722 "grow", T, A); \
723 VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \
724 VEC_CHECK_PASS PASS_MEM_STAT); \
725 VEC_BASE (*vec_)->num = size_; \
726 } \
727 \
728 static inline T *VEC_OP (T,A,safe_push) \
729 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
730 { \
731 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
732 \
733 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
734 } \
735 \
736 static inline T *VEC_OP (T,A,safe_insert) \
737 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
738 { \
739 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
740 \
741 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
742 VEC_CHECK_PASS); \
743 }
744
745 /* Vector of object. */
746 #if IN_GENGTYPE
747 {"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
748 {"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL},
749 #else
750 #define DEF_VEC_O(T) \
751 VEC_T_GTY(T,base); \
752 VEC_TA_GTY(T,base,none,); \
753 DEF_VEC_FUNC_O(T) \
754 struct vec_swallow_trailing_semi
755 #define DEF_VEC_ALLOC_O(T,A) \
756 VEC_TA_GTY(T,base,A,); \
757 DEF_VEC_ALLOC_FUNC_O(T,A) \
758 struct vec_swallow_trailing_semi
759 #endif
760
761 #define DEF_VEC_FUNC_O(T) \
762 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
763 { \
764 return vec_ ? vec_->num : 0; \
765 } \
766 \
767 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
768 { \
769 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \
770 \
771 return &vec_->vec[vec_->num - 1]; \
772 } \
773 \
774 static inline T *VEC_OP (T,base,index) \
775 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
776 { \
777 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \
778 \
779 return &vec_->vec[ix_]; \
780 } \
781 \
782 static inline int VEC_OP (T,base,iterate) \
783 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
784 { \
785 if (vec_ && ix_ < vec_->num) \
786 { \
787 *ptr = &vec_->vec[ix_]; \
788 return 1; \
789 } \
790 else \
791 { \
792 *ptr = 0; \
793 return 0; \
794 } \
795 } \
796 \
797 static inline size_t VEC_OP (T,base,embedded_size) \
798 (int alloc_) \
799 { \
800 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
801 } \
802 \
803 static inline void VEC_OP (T,base,embedded_init) \
804 (VEC(T,base) *vec_, int alloc_) \
805 { \
806 vec_->num = 0; \
807 vec_->alloc = alloc_; \
808 } \
809 \
810 static inline int VEC_OP (T,base,space) \
811 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
812 { \
813 VEC_ASSERT (alloc_ >= 0, "space", T, base); \
814 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
815 } \
816 \
817 static inline T *VEC_OP (T,base,quick_push) \
818 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
819 { \
820 T *slot_; \
821 \
822 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \
823 slot_ = &vec_->vec[vec_->num++]; \
824 if (obj_) \
825 *slot_ = *obj_; \
826 \
827 return slot_; \
828 } \
829 \
830 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
831 { \
832 VEC_ASSERT (vec_->num, "pop", T, base); \
833 --vec_->num; \
834 } \
835 \
836 static inline void VEC_OP (T,base,truncate) \
837 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
838 { \
839 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \
840 if (vec_) \
841 vec_->num = size_; \
842 } \
843 \
844 static inline T *VEC_OP (T,base,replace) \
845 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
846 { \
847 T *slot_; \
848 \
849 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \
850 slot_ = &vec_->vec[ix_]; \
851 if (obj_) \
852 *slot_ = *obj_; \
853 \
854 return slot_; \
855 } \
856 \
857 static inline T *VEC_OP (T,base,quick_insert) \
858 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
859 { \
860 T *slot_; \
861 \
862 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \
863 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \
864 slot_ = &vec_->vec[ix_]; \
865 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
866 if (obj_) \
867 *slot_ = *obj_; \
868 \
869 return slot_; \
870 } \
871 \
872 static inline void VEC_OP (T,base,ordered_remove) \
873 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
874 { \
875 T *slot_; \
876 \
877 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
878 slot_ = &vec_->vec[ix_]; \
879 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
880 } \
881 \
882 static inline void VEC_OP (T,base,unordered_remove) \
883 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
884 { \
885 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \
886 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
887 } \
888 \
889 static inline T *VEC_OP (T,base,address) \
890 (VEC(T,base) *vec_) \
891 { \
892 return vec_ ? vec_->vec : 0; \
893 } \
894 \
895 static inline unsigned VEC_OP (T,base,lower_bound) \
896 (VEC(T,base) *vec_, const T *obj_, \
897 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
898 { \
899 unsigned int len_ = VEC_OP (T, base, length) (vec_); \
900 unsigned int half_, middle_; \
901 unsigned int first_ = 0; \
902 while (len_ > 0) \
903 { \
904 T *middle_elem_; \
905 half_ = len_ >> 1; \
906 middle_ = first_; \
907 middle_ += half_; \
908 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
909 if (lessthan_ (middle_elem_, obj_)) \
910 { \
911 first_ = middle_; \
912 ++first_; \
913 len_ = len_ - half_ - 1; \
914 } \
915 else \
916 len_ = half_; \
917 } \
918 return first_; \
919 }
920
921 #define DEF_VEC_ALLOC_FUNC_O(T,A) \
922 static inline VEC(T,A) *VEC_OP (T,A,alloc) \
923 (int alloc_ MEM_STAT_DECL) \
924 { \
925 /* We must request exact size allocation, hence the negation. */ \
926 return (VEC(T,A) *) vec_##A##_o_reserve (NULL, -alloc_, \
927 offsetof (VEC(T,A),base.vec), \
928 sizeof (T) \
929 PASS_MEM_STAT); \
930 } \
931 \
932 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
933 { \
934 size_t len_ = vec_ ? vec_->num : 0; \
935 VEC (T,A) *new_vec_ = NULL; \
936 \
937 if (len_) \
938 { \
939 /* We must request exact size allocation, hence the negation. */ \
940 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve \
941 (NULL, -len_, \
942 offsetof (VEC(T,A),base.vec), sizeof (T) \
943 PASS_MEM_STAT)); \
944 \
945 new_vec_->base.num = len_; \
946 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
947 } \
948 return new_vec_; \
949 } \
950 \
951 static inline void VEC_OP (T,A,free) \
952 (VEC(T,A) **vec_) \
953 { \
954 if (*vec_) \
955 vec_##A##_free (*vec_); \
956 *vec_ = NULL; \
957 } \
958 \
959 static inline int VEC_OP (T,A,reserve) \
960 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
961 { \
962 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \
963 alloc_ < 0 ? -alloc_ : alloc_ \
964 VEC_CHECK_PASS); \
965 \
966 if (extend) \
967 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
968 offsetof (VEC(T,A),base.vec),\
969 sizeof (T) \
970 PASS_MEM_STAT); \
971 \
972 return extend; \
973 } \
974 \
975 static inline void VEC_OP (T,A,safe_grow) \
976 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
977 { \
978 VEC_ASSERT (size_ >= 0 \
979 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
980 "grow", T, A); \
981 VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \
982 VEC_CHECK_PASS PASS_MEM_STAT); \
983 VEC_BASE (*vec_)->num = size_; \
984 VEC_BASE (*vec_)->num = size_; \
985 } \
986 \
987 static inline T *VEC_OP (T,A,safe_push) \
988 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
989 { \
990 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
991 \
992 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
993 } \
994 \
995 static inline T *VEC_OP (T,A,safe_insert) \
996 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
997 VEC_CHECK_DECL MEM_STAT_DECL) \
998 { \
999 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
1000 \
1001 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
1002 VEC_CHECK_PASS); \
1003 }
1004 #endif /* GCC_VEC_H */
DragonFly BSD