?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
* arm.h (REVERSE_CONDITION): Define.
[official-gcc.git] / gcc / vec.h
bloba3eea311320e85c70f43e9c554ae37bcc83afa04
1 /* Vector API for GNU compiler.
2 Copyright (C) 2004 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 behaviour of objects and of pointers to
33 objects, there are two flavours. One to deal with a vector of
34 pointers to objects, and one to deal with a vector of objects
35 themselves. Both of these pass pointers to objects around -- in
36 the former case the pointers are stored into the vector and in the
37 latter case the pointers are dereferenced and the objects copied
38 into the vector. Therefore, when using a vector of pointers, the
39 objects pointed to must be long lived, but when dealing with a
40 vector of objects, the source objects need not be.
41
42 There are both 'index' and 'iterate' accessors. The iterator
43 returns a boolean iteration condition and updates the iteration
44 variable passed by reference. Because the iterator will be
45 inlined, the address-of can be optimized away.
46
47 The vectors are implemented using the trailing array idiom, thus
48 they are not resizeable without changing the address of the vector
49 object itself. This means you cannot have variables or fields of
50 vector type -- always use a pointer to a vector. The one exception
51 is the final field of a structure, which could be a vector type.
52 You will have to use the embedded_size & embedded_init calls to
53 create such objects, and they will probably not be resizeable (so
54 don't use the 'safe' allocation variants). The trailing array
55 idiom is used (rather than a pointer to an array of data), because,
56 if we allow NULL to also represent an empty vector, empty vectors
57 occupy minimal space in the structure containing them.
58
59 Each operation that increases the number of active elements is
60 available in 'quick' and 'safe' variants. The former presumes that
61 there is sufficient allocated space for the operation to succeed
62 (it aborts if there is not). The latter will reallocate the
63 vector, if needed. Reallocation causes an exponential increase in
64 vector size. If you know you will be adding N elements, it would
65 be more efficient to use the reserve operation before adding the
66 elements with the 'quick' operation. You may also use the reserve
67 operation with a -1 operand, to gain control over exactly when
68 reallocation occurs.
69
70 You should prefer the push and pop operations, as they append and
71 remove from the end of the vector. If you need to remove several
72 items in one go, use the truncate operation. The insert and remove
73 operations allow you to change elements in the middle of the
74 vector. There are two remove operations, one which preserves the
75 element ordering 'ordered_remove', and one which does not
76 'unordered_remove'. The latter function copies the end element
77 into the removed slot, rather than invoke a memmove operation.
78 The 'lower_bound' function will determine where to place an item in the
79 array using insert that will maintain sorted order.
80
81 If you need to directly manipulate a vector, then the 'address'
82 accessor will return the address of the start of the vector. Also
83 the 'space' predicate will tell you whether there is spare capacity
84 in the vector. You will not normally need to use these two functions.
85
86 Vector types are defined using a DEF_VEC_{O,P}(TYPEDEF) macro, and
87 variables of vector type are declared using a VEC(TYPEDEF)
88 macro. The characters O and P indicate whether TYPEDEF is a pointer
89 (P) or object (O) type.
90
91 An example of their use would be,
92
93 DEF_VEC_P(tree); // define a vector of tree pointers. This must
94 // appear at file scope.
95
96 struct my_struct {
97 VEC(tree) *v; // A (pointer to) a vector of tree pointers.
98 };
99
100 struct my_struct *s;
101
102 if (VEC_length(tree,s->v)) { we have some contents }
103 VEC_safe_push(tree,s->v,decl); // append some decl onto the end
104 for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
105 { do something with elt }
106
107 */
108
109 /* Macros to invoke API calls. A single macro works for both pointer
110 and object vectors, but the argument and return types might well be
111 different. In each macro, TDEF is the typedef of the vector
112 elements. Some of these macros pass the vector, V, by reference
113 (by taking its address), this is noted in the descriptions. */
114
115 /* Length of vector
116 unsigned VEC_T_length(const VEC(T) *v);
117
118 Return the number of active elements in V. V can be NULL, in which
119 case zero is returned. */
120
121 #define VEC_length(TDEF,V) (VEC_OP(TDEF,length)(V))
122
123 /* Get the final element of the vector.
124 T VEC_T_last(VEC(T) *v); // Pointer
125 T *VEC_T_last(VEC(T) *v); // Object
126
127 Return the final element. If V is empty, abort. */
128
129 #define VEC_last(TDEF,V) (VEC_OP(TDEF,last)(V VEC_CHECK_INFO))
130
131 /* Index into vector
132 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
133 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
134
135 Return the IX'th element. If IX is outside the domain of V,
136 abort. */
137
138 #define VEC_index(TDEF,V,I) (VEC_OP(TDEF,index)(V,I VEC_CHECK_INFO))
139
140 /* Iterate over vector
141 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
142 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
143
144 Return iteration condition and update PTR to point to the IX'th
145 element. At the end of iteration, sets PTR to NULL. Use this to
146 iterate over the elements of a vector as follows,
147
148 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
149 continue; */
150
151 #define VEC_iterate(TDEF,V,I,P) (VEC_OP(TDEF,iterate)(V,I,&(P)))
152
153 /* Allocate new vector.
154 VEC(T) *VEC_T_alloc(int reserve);
155
156 Allocate a new vector with space for RESERVE objects. If RESERVE
157 is <= 0, a default number of slots are created. */
158
159 #define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A MEM_STAT_INFO))
160
161 /* Use these to determine the required size and initialization of a
162 vector embedded within another structure (as the final member).
163
164 size_t VEC_T_embedded_size(int reserve);
165 void VEC_T_embedded_init(VEC(T) *v, int reserve);
166
167 These allow the caller to perform the memory allocation. */
168
169 #define VEC_embedded_size(TDEF,A) (VEC_OP(TDEF,embedded_size)(A))
170 #define VEC_embedded_init(TDEF,O,A) (VEC_OP(TDEF,embedded_init)(O,A))
171
172 /* Determine if a vector has additional capacity.
173
174 int VEC_T_space (VEC(T) *v,int reserve)
175
176 If V has space for RESERVE additional entries, return non-zero. If
177 RESERVE is < 0, ensure there is at least one space slot. You
178 usually only need to use this if you are doing your own vector
179 reallocation, for instance on an embedded vector. This returns
180 non-zero in exactly the same circumstances that VEC_T_reserve
181 will. */
182
183 #define VEC_space(TDEF,V,R) (VEC_OP(TDEF,space)(V,R))
184
185 /* Reserve space.
186 int VEC_T_reserve(VEC(T) *&v, int reserve);
187
188 Ensure that V has at least RESERVE slots available, if RESERVE is
189 >= 0. If RESERVE < 0, ensure that there is at least one spare
190 slot. These differ in their reallocation behaviour, the first will
191 not create additional headroom, but the second mechanism will
192 perform the usual exponential headroom increase. Note this can
193 cause V to be reallocated. Returns non-zero iff reallocation
194 actually occurred. */
195
196 #define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R MEM_STAT_INFO))
197
198 /* Push object with no reallocation
199 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
200 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
201
202 Push a new element onto the end, returns a pointer to the slot
203 filled in. For object vectors, the new value can be NULL, in which
204 case NO initialization is performed. Aborts if there is
205 insufficient space in the vector. */
206
207 #define VEC_quick_push(TDEF,V,O) \
208 (VEC_OP(TDEF,quick_push)(V,O VEC_CHECK_INFO))
209
210 /* Push object with reallocation
211 T *VEC_T_safe_push (VEC(T) *&v, T obj); // Pointer
212 T *VEC_T_safe_push (VEC(T) *&v, T *obj); // Object
213
214 Push a new element onto the end, returns a pointer to the slot
215 filled in. For object vectors, the new value can be NULL, in which
216 case NO initialization is performed. Reallocates V, if needed. */
217
218 #define VEC_safe_push(TDEF,V,O) \
219 (VEC_OP(TDEF,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
220
221 /* Pop element off end
222 T VEC_T_pop (VEC(T) *v); // Pointer
223 void VEC_T_pop (VEC(T) *v); // Object
224
225 Pop the last element off the end. Returns the element popped, for
226 pointer vectors. */
227
228 #define VEC_pop(TDEF,V) (VEC_OP(TDEF,pop)(V VEC_CHECK_INFO))
229
230 /* Truncate to specific length
231 void VEC_T_truncate (VEC(T) *v, unsigned len);
232
233 Set the length as specified. This is an O(1) operation. */
234
235 #define VEC_truncate(TDEF,V,I) \
236 (VEC_OP(TDEF,truncate)(V,I VEC_CHECK_INFO))
237
238 /* Replace element
239 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
240 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
241
242 Replace the IXth element of V with a new value, VAL. For pointer
243 vectors returns the original value. For object vectors returns a
244 pointer to the new value. For object vectors the new value can be
245 NULL, in which case no overwriting of the slot is actually
246 performed. */
247
248 #define VEC_replace(TDEF,V,I,O) \
249 (VEC_OP(TDEF,replace)(V,I,O VEC_CHECK_INFO))
250
251 /* Insert object with no reallocation
252 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
253 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
254
255 Insert an element, VAL, at the IXth position of V. Return a pointer
256 to the slot created. For vectors of object, the new value can be
257 NULL, in which case no initialization of the inserted slot takes
258 place. Aborts if there is insufficient space. */
259
260 #define VEC_quick_insert(TDEF,V,I,O) \
261 (VEC_OP(TDEF,quick_insert)(V,I,O VEC_CHECK_INFO))
262
263 /* Insert object with reallocation
264 T *VEC_T_safe_insert (VEC(T) *&v, unsigned ix, T val); // Pointer
265 T *VEC_T_safe_insert (VEC(T) *&v, unsigned ix, T *val); // Object
266
267 Insert an element, VAL, at the IXth position of V. Return a pointer
268 to the slot created. For vectors of object, the new value can be
269 NULL, in which case no initialization of the inserted slot takes
270 place. Reallocate V, if necessary. */
271
272 #define VEC_safe_insert(TDEF,V,I,O) \
273 (VEC_OP(TDEF,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
274
275 /* Remove element retaining order
276 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
277 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
278
279 Remove an element from the IXth position of V. Ordering of
280 remaining elements is preserverd. For pointer vectors returns the
281 removed object. This is an O(N) operation due to a memmove. */
282
283 #define VEC_ordered_remove(TDEF,V,I) \
284 (VEC_OP(TDEF,ordered_remove)(V,I VEC_CHECK_INFO))
285
286 /* Remove element destroying order
287 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
288 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
289
290 Remove an element from the IXth position of V. Ordering of
291 remaining elements is destroyed. For pointer vectors returns the
292 removed object. This is an O(1) operation. */
293
294 #define VEC_unordered_remove(TDEF,V,I) \
295 (VEC_OP(TDEF,unordered_remove)(V,I VEC_CHECK_INFO))
296
297 /* Get the address of the array of elements
298 T *VEC_T_address (VEC(T) v)
299
300 If you need to directly manipulate the array (for instance, you
301 want to feed it to qsort), use this accessor. */
302
303 #define VEC_address(TDEF,V) (VEC_OP(TDEF,address)(V))
304
305 /* Find the first index in the vector not less than the object.
306 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
307 bool (*lessthan) (const T, const T)); // Pointer
308 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
309 bool (*lessthan) (const T*, const T*)); // Object
310
311 Find the first position in which VAL could be inserted without
312 changing the ordering of V. LESSTHAN is a function that returns
313 true if the first argument is strictly less than the second. */
314
315 #define VEC_lower_bound(TDEF,V,O,LT) \
316 (VEC_OP(TDEF,lower_bound)(V,O,LT VEC_CHECK_INFO))
317
318 #if !IN_GENGTYPE
319 /* Reallocate an array of elements with prefix. */
320 extern void *vec_p_reserve (void *, int MEM_STAT_DECL);
321 extern void *vec_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
322
323 #if ENABLE_CHECKING
324 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
325 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
326 #define VEC_CHECK_PASS ,file_,line_,function_
327
328 #define VEC_ASSERT(EXPR,OP,TDEF) \
329 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(TDEF)), 0))
330
331 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
332 ATTRIBUTE_NORETURN;
333 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
334 #else
335 #define VEC_CHECK_INFO
336 #define VEC_CHECK_DECL
337 #define VEC_CHECK_PASS
338 #define VEC_ASSERT(EXPR,OP,TYPE) (void)(EXPR)
339 #endif
340
341 #define VEC(TDEF) VEC_##TDEF
342 #define VEC_OP(TDEF,OP) VEC_OP_(VEC(TDEF),OP)
343 #define VEC_OP_(VEC,OP) VEC_OP__(VEC,OP)
344 #define VEC_OP__(VEC,OP) VEC ## _ ## OP
345 #else /* IN_GENGTYPE */
346 #define VEC(TDEF) VEC_ TDEF
347 #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
348 #define VEC_STRINGIFY_(X) #X
349 #undef GTY
350 #endif /* IN_GENGTYPE */
351
352 #define VEC_TDEF(TDEF) \
353 typedef struct VEC (TDEF) GTY(()) \
354 { \
355 unsigned num; \
356 unsigned alloc; \
357 TDEF GTY ((length ("%h.num"))) vec[1]; \
358 } VEC (TDEF)
359
360 /* Vector of pointer to object. */
361 #if IN_GENGTYPE
362 {"DEF_VEC_P", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
363 #else
364
365 #define DEF_VEC_P(TDEF) \
366 VEC_TDEF (TDEF); \
367 \
368 static inline unsigned VEC_OP (TDEF,length) \
369 (const VEC (TDEF) *vec_) \
370 { \
371 return vec_ ? vec_->num : 0; \
372 } \
373 \
374 static inline TDEF VEC_OP (TDEF,last) \
375 (const VEC (TDEF) *vec_ VEC_CHECK_DECL) \
376 { \
377 VEC_ASSERT (vec_ && vec_->num, "last", TDEF); \
378 \
379 return vec_->vec[vec_->num - 1]; \
380 } \
381 \
382 static inline TDEF VEC_OP (TDEF,index) \
383 (const VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
384 { \
385 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
386 \
387 return vec_->vec[ix_]; \
388 } \
389 \
390 static inline int VEC_OP (TDEF,iterate) \
391 (const VEC (TDEF) *vec_, unsigned ix_, TDEF *ptr) \
392 { \
393 if (vec_ && ix_ < vec_->num) \
394 { \
395 *ptr = vec_->vec[ix_]; \
396 return 1; \
397 } \
398 else \
399 { \
400 *ptr = 0; \
401 return 0; \
402 } \
403 } \
404 \
405 static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
406 (int alloc_ MEM_STAT_DECL) \
407 { \
408 return (VEC (TDEF) *) vec_p_reserve (NULL, alloc_ - !alloc_ PASS_MEM_STAT);\
409 } \
410 \
411 static inline size_t VEC_OP (TDEF,embedded_size) \
412 (int alloc_) \
413 { \
414 return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
415 } \
416 \
417 static inline void VEC_OP (TDEF,embedded_init) \
418 (VEC (TDEF) *vec_, int alloc_) \
419 { \
420 vec_->num = 0; \
421 vec_->alloc = alloc_; \
422 } \
423 \
424 static inline int VEC_OP (TDEF,space) \
425 (VEC (TDEF) *vec_, int alloc_) \
426 { \
427 return vec_ ? ((vec_)->alloc - (vec_)->num \
428 < (unsigned)(alloc_ < 0 ? 1 : alloc_)) : alloc_ != 0; \
429 } \
430 \
431 static inline int VEC_OP (TDEF,reserve) \
432 (VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
433 { \
434 int extend = VEC_OP (TDEF,space) (*vec_, alloc_); \
435 \
436 if (extend) \
437 *vec_ = (VEC (TDEF) *) vec_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
438 \
439 return extend; \
440 } \
441 \
442 static inline TDEF *VEC_OP (TDEF,quick_push) \
443 (VEC (TDEF) *vec_, TDEF obj_ VEC_CHECK_DECL) \
444 { \
445 TDEF *slot_; \
446 \
447 VEC_ASSERT (vec_->num < vec_->alloc, "push", TDEF); \
448 slot_ = &vec_->vec[vec_->num++]; \
449 *slot_ = obj_; \
450 \
451 return slot_; \
452 } \
453 \
454 static inline TDEF *VEC_OP (TDEF,safe_push) \
455 (VEC (TDEF) **vec_, TDEF obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
456 { \
457 VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
458 \
459 return VEC_OP (TDEF,quick_push) (*vec_, obj_ VEC_CHECK_PASS); \
460 } \
461 \
462 static inline TDEF VEC_OP (TDEF,pop) \
463 (VEC (TDEF) *vec_ VEC_CHECK_DECL) \
464 { \
465 TDEF obj_; \
466 \
467 VEC_ASSERT (vec_->num, "pop", TDEF); \
468 obj_ = vec_->vec[--vec_->num]; \
469 \
470 return obj_; \
471 } \
472 \
473 static inline void VEC_OP (TDEF,truncate) \
474 (VEC (TDEF) *vec_, unsigned size_ VEC_CHECK_DECL) \
475 { \
476 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", TDEF); \
477 if (vec_) \
478 vec_->num = size_; \
479 } \
480 \
481 static inline TDEF VEC_OP (TDEF,replace) \
482 (VEC (TDEF) *vec_, unsigned ix_, TDEF obj_ VEC_CHECK_DECL) \
483 { \
484 TDEF old_obj_; \
485 \
486 VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
487 old_obj_ = vec_->vec[ix_]; \
488 vec_->vec[ix_] = obj_; \
489 \
490 return old_obj_; \
491 } \
492 \
493 static inline unsigned VEC_OP (TDEF,lower_bound) \
494 (VEC (TDEF) *vec_, const TDEF obj_, bool (*lessthan_)(const TDEF, const TDEF) VEC_CHECK_DECL) \
495 { \
496 unsigned int len_ = VEC_OP (TDEF, length) (vec_); \
497 unsigned int half_, middle_; \
498 unsigned int first_ = 0; \
499 while (len_ > 0) \
500 { \
501 TDEF middle_elem_; \
502 half_ = len_ >> 1; \
503 middle_ = first_; \
504 middle_ += half_; \
505 middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
506 if (lessthan_ (middle_elem_, obj_)) \
507 { \
508 first_ = middle_; \
509 ++first_; \
510 len_ = len_ - half_ - 1; \
511 } \
512 else \
513 len_ = half_; \
514 } \
515 return first_; \
516 } \
517 \
518 static inline TDEF *VEC_OP (TDEF,quick_insert) \
519 (VEC (TDEF) *vec_, unsigned ix_, TDEF obj_ VEC_CHECK_DECL) \
520 { \
521 TDEF *slot_; \
522 \
523 VEC_ASSERT (vec_->num < vec_->alloc, "insert", TDEF); \
524 VEC_ASSERT (ix_ <= vec_->num, "insert", TDEF); \
525 slot_ = &vec_->vec[ix_]; \
526 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (TDEF)); \
527 *slot_ = obj_; \
528 \
529 return slot_; \
530 } \
531 \
532 static inline TDEF *VEC_OP (TDEF,safe_insert) \
533 (VEC (TDEF) **vec_, unsigned ix_, TDEF obj_ \
534 VEC_CHECK_DECL MEM_STAT_DECL) \
535 { \
536 VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
537 \
538 return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS); \
539 } \
540 \
541 static inline TDEF VEC_OP (TDEF,ordered_remove) \
542 (VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
543 { \
544 TDEF *slot_; \
545 TDEF obj_; \
546 \
547 VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
548 slot_ = &vec_->vec[ix_]; \
549 obj_ = *slot_; \
550 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF)); \
551 \
552 return obj_; \
553 } \
554 \
555 static inline TDEF VEC_OP (TDEF,unordered_remove) \
556 (VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
557 { \
558 TDEF *slot_; \
559 TDEF obj_; \
560 \
561 VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
562 slot_ = &vec_->vec[ix_]; \
563 obj_ = *slot_; \
564 *slot_ = vec_->vec[--vec_->num]; \
565 \
566 return obj_; \
567 } \
568 \
569 static inline TDEF *VEC_OP (TDEF,address) \
570 (VEC (TDEF) *vec_) \
571 { \
572 return vec_ ? vec_->vec : 0; \
573 } \
574 \
575 struct vec_swallow_trailing_semi
576 #endif
577
578 /* Vector of object. */
579 #if IN_GENGTYPE
580 {"DEF_VEC_O", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
581 #else
582
583 #define DEF_VEC_O(TDEF) \
584 VEC_TDEF (TDEF); \
585 \
586 static inline unsigned VEC_OP (TDEF,length) \
587 (const VEC (TDEF) *vec_) \
588 { \
589 return vec_ ? vec_->num : 0; \
590 } \
591 \
592 static inline TDEF *VEC_OP (TDEF,last) \
593 (VEC (TDEF) *vec_ VEC_CHECK_DECL) \
594 { \
595 VEC_ASSERT (vec_ && vec_->num, "last", TDEF); \
596 \
597 return &vec_->vec[vec_->num - 1]; \
598 } \
599 \
600 static inline TDEF *VEC_OP (TDEF,index) \
601 (VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
602 { \
603 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
604 \
605 return &vec_->vec[ix_]; \
606 } \
607 \
608 static inline int VEC_OP (TDEF,iterate) \
609 (VEC (TDEF) *vec_, unsigned ix_, TDEF **ptr) \
610 { \
611 if (vec_ && ix_ < vec_->num) \
612 { \
613 *ptr = &vec_->vec[ix_]; \
614 return 1; \
615 } \
616 else \
617 { \
618 *ptr = 0; \
619 return 0; \
620 } \
621 } \
622 \
623 static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
624 (int alloc_ MEM_STAT_DECL) \
625 { \
626 return (VEC (TDEF) *) vec_o_reserve (NULL, alloc_ - !alloc_, \
627 offsetof (VEC(TDEF),vec), sizeof (TDEF)\
628 PASS_MEM_STAT); \
629 } \
630 \
631 static inline size_t VEC_OP (TDEF,embedded_size) \
632 (int alloc_) \
633 { \
634 return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
635 } \
636 \
637 static inline void VEC_OP (TDEF,embedded_init) \
638 (VEC (TDEF) *vec_, int alloc_) \
639 { \
640 vec_->num = 0; \
641 vec_->alloc = alloc_; \
642 } \
643 \
644 static inline int VEC_OP (TDEF,space) \
645 (VEC (TDEF) *vec_, int alloc_) \
646 { \
647 return vec_ ? ((vec_)->alloc - (vec_)->num \
648 < (unsigned)(alloc_ < 0 ? 1 : alloc_)) : alloc_ != 0; \
649 } \
650 \
651 static inline int VEC_OP (TDEF,reserve) \
652 (VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
653 { \
654 int extend = VEC_OP (TDEF,space) (*vec_, alloc_); \
655 \
656 if (extend) \
657 *vec_ = (VEC (TDEF) *) vec_o_reserve (*vec_, alloc_, \
658 offsetof (VEC(TDEF),vec), sizeof (TDEF) \
659 PASS_MEM_STAT); \
660 \
661 return extend; \
662 } \
663 \
664 static inline TDEF *VEC_OP (TDEF,quick_push) \
665 (VEC (TDEF) *vec_, const TDEF *obj_ VEC_CHECK_DECL) \
666 { \
667 TDEF *slot_; \
668 \
669 VEC_ASSERT (vec_->num < vec_->alloc, "push", TDEF); \
670 slot_ = &vec_->vec[vec_->num++]; \
671 if (obj_) \
672 *slot_ = *obj_; \
673 \
674 return slot_; \
675 } \
676 \
677 static inline TDEF *VEC_OP (TDEF,safe_push) \
678 (VEC (TDEF) **vec_, const TDEF *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
679 { \
680 VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
681 \
682 return VEC_OP (TDEF,quick_push) (*vec_, obj_ VEC_CHECK_PASS); \
683 } \
684 \
685 static inline void VEC_OP (TDEF,pop) \
686 (VEC (TDEF) *vec_ VEC_CHECK_DECL) \
687 { \
688 VEC_ASSERT (vec_->num, "pop", TDEF); \
689 --vec_->num; \
690 } \
691 \
692 static inline void VEC_OP (TDEF,truncate) \
693 (VEC (TDEF) *vec_, unsigned size_ VEC_CHECK_DECL) \
694 { \
695 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", TDEF); \
696 if (vec_) \
697 vec_->num = size_; \
698 } \
699 \
700 static inline TDEF *VEC_OP (TDEF,replace) \
701 (VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL) \
702 { \
703 TDEF *slot_; \
704 \
705 VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
706 slot_ = &vec_->vec[ix_]; \
707 if (obj_) \
708 *slot_ = *obj_; \
709 \
710 return slot_; \
711 } \
712 \
713 static inline unsigned VEC_OP (TDEF,lower_bound) \
714 (VEC (TDEF) *vec_, const TDEF *obj_, bool (*lessthan_)(const TDEF *, const TDEF *) VEC_CHECK_DECL) \
715 { \
716 unsigned int len_ = VEC_OP (TDEF, length) (vec_); \
717 unsigned int half_, middle_; \
718 unsigned int first_ = 0; \
719 while (len_ > 0) \
720 { \
721 TDEF *middle_elem_; \
722 half_ = len_ >> 1; \
723 middle_ = first_; \
724 middle_ += half_; \
725 middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
726 if (lessthan_ (middle_elem_, obj_)) \
727 { \
728 first_ = middle_; \
729 ++first_; \
730 len_ = len_ - half_ - 1; \
731 } \
732 else \
733 len_ = half_; \
734 } \
735 return first_; \
736 } \
737 \
738 static inline TDEF *VEC_OP (TDEF,quick_insert) \
739 (VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL) \
740 { \
741 TDEF *slot_; \
742 \
743 VEC_ASSERT (vec_->num < vec_->alloc, "insert", TDEF); \
744 VEC_ASSERT (ix_ <= vec_->num, "insert", TDEF); \
745 slot_ = &vec_->vec[ix_]; \
746 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (TDEF)); \
747 if (obj_) \
748 *slot_ = *obj_; \
749 \
750 return slot_; \
751 } \
752 \
753 static inline TDEF *VEC_OP (TDEF,safe_insert) \
754 (VEC (TDEF) **vec_, unsigned ix_, const TDEF *obj_ \
755 VEC_CHECK_DECL MEM_STAT_DECL) \
756 { \
757 VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
758 \
759 return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS); \
760 } \
761 \
762 static inline void VEC_OP (TDEF,ordered_remove) \
763 (VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
764 { \
765 TDEF *slot_; \
766 \
767 VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
768 slot_ = &vec_->vec[ix_]; \
769 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF)); \
770 } \
771 \
772 static inline void VEC_OP (TDEF,unordered_remove) \
773 (VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
774 { \
775 VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
776 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
777 } \
778 \
779 static inline TDEF *VEC_OP (TDEF,address) \
780 (VEC (TDEF) *vec_) \
781 { \
782 return vec_ ? vec_->vec : 0; \
783 } \
784 \
785 struct vec_swallow_trailing_semi
786 #endif
787
788 #endif /* GCC_VEC_H */
Mirror of the offical gcc git repository hosted at gcc.gnu.org