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