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