]>
Commit | Line | Data |
---|---|---|
ada55151 | 1 | /* Vector API for GNU compiler. |
fe9565ed | 2 | Copyright (C) 2004, 2005 Free Software Foundation, Inc. |
ada55151 NS |
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 | |
366ccddb KC |
19 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
20 | 02110-1301, USA. */ | |
ada55151 NS |
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 | ||
a0ef884f NS |
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. | |
ada55151 | 40 | |
9ba5ff0f NS |
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 | ||
ada55151 NS |
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. | |
a064479c NS |
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. | |
ada55151 NS |
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 | |
0e61db61 | 61 | (it dies if there is not). The latter will reallocate the |
ada55151 NS |
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 | |
d4e6fecb NS |
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. | |
ada55151 NS |
72 | |
73 | You should prefer the push and pop operations, as they append and | |
a064479c NS |
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 | |
ada55151 NS |
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 | |
d4e6fecb NS |
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 | |
58152808 | 82 | array using insert that will maintain sorted order. |
9ba5ff0f | 83 | |
d4e6fecb NS |
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. | |
4c254e68 | 90 | |
9ba5ff0f NS |
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. | |
ada55151 | 95 | |
a0ef884f | 96 | Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to |
d4e6fecb | 97 | get the non-memory allocation version, and then a |
a0ef884f | 98 | DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed |
d4e6fecb NS |
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 | |
a0ef884f NS |
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. | |
ada55151 NS |
114 | |
115 | An example of their use would be, | |
116 | ||
d4e6fecb NS |
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. | |
ada55151 NS |
120 | |
121 | struct my_struct { | |
d4e6fecb | 122 | VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers. |
ada55151 NS |
123 | }; |
124 | ||
125 | struct my_struct *s; | |
126 | ||
2272d9cf | 127 | if (VEC_length(tree,s->v)) { we have some contents } |
d4e6fecb | 128 | VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end |
2a68a7de BE |
129 | for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++) |
130 | { do something with elt } | |
ada55151 NS |
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 | |
d4e6fecb NS |
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. */ | |
ada55151 NS |
141 | |
142 | /* Length of vector | |
3cbf09de | 143 | unsigned VEC_T_length(const VEC(T) *v); |
ada55151 NS |
144 | |
145 | Return the number of active elements in V. V can be NULL, in which | |
146 | case zero is returned. */ | |
9ba5ff0f | 147 | |
d4e6fecb | 148 | #define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V))) |
ada55151 | 149 | |
4038c495 GB |
150 | |
151 | /* Check if vector is empty | |
152 | int VEC_T_empty(const VEC(T) *v); | |
153 | ||
a4d05547 | 154 | Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ |
4038c495 GB |
155 | |
156 | #define VEC_empty(T,V) (VEC_length (T,V) == 0) | |
157 | ||
158 | ||
ada55151 | 159 | /* Get the final element of the vector. |
a0ef884f | 160 | T VEC_T_last(VEC(T) *v); // Integer |
ada55151 NS |
161 | T VEC_T_last(VEC(T) *v); // Pointer |
162 | T *VEC_T_last(VEC(T) *v); // Object | |
163 | ||
0e61db61 | 164 | Return the final element. V must not be empty. */ |
9ba5ff0f | 165 | |
d4e6fecb | 166 | #define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) |
ada55151 NS |
167 | |
168 | /* Index into vector | |
a0ef884f | 169 | T VEC_T_index(VEC(T) *v, unsigned ix); // Integer |
3cbf09de NS |
170 | T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer |
171 | T *VEC_T_index(VEC(T) *v, unsigned ix); // Object | |
ada55151 | 172 | |
0e61db61 | 173 | Return the IX'th element. If IX must be in the domain of V. */ |
9ba5ff0f | 174 | |
d4e6fecb | 175 | #define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) |
ada55151 NS |
176 | |
177 | /* Iterate over vector | |
a0ef884f | 178 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer |
3cbf09de NS |
179 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer |
180 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object | |
ada55151 | 181 | |
9ba5ff0f NS |
182 | Return iteration condition and update PTR to point to the IX'th |
183 | element. At the end of iteration, sets PTR to NULL. Use this to | |
184 | iterate over the elements of a vector as follows, | |
ada55151 | 185 | |
9ba5ff0f | 186 | for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) |
ada55151 | 187 | continue; */ |
9ba5ff0f | 188 | |
d4e6fecb | 189 | #define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) |
ada55151 NS |
190 | |
191 | /* Allocate new vector. | |
d4e6fecb | 192 | VEC(T,A) *VEC_T_A_alloc(int reserve); |
ada55151 | 193 | |
7de5bccc | 194 | Allocate a new vector with space for RESERVE objects. If RESERVE |
d4e6fecb | 195 | is zero, NO vector is created. */ |
9ba5ff0f | 196 | |
d4e6fecb | 197 | #define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) |
ada55151 | 198 | |
4c254e68 | 199 | /* Free a vector. |
d4e6fecb | 200 | void VEC_T_A_free(VEC(T,A) *&); |
4c254e68 NS |
201 | |
202 | Free a vector and set it to NULL. */ | |
203 | ||
d4e6fecb | 204 | #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) |
4c254e68 | 205 | |
a064479c NS |
206 | /* Use these to determine the required size and initialization of a |
207 | vector embedded within another structure (as the final member). | |
208 | ||
7de5bccc NS |
209 | size_t VEC_T_embedded_size(int reserve); |
210 | void VEC_T_embedded_init(VEC(T) *v, int reserve); | |
a064479c NS |
211 | |
212 | These allow the caller to perform the memory allocation. */ | |
9ba5ff0f | 213 | |
d4e6fecb NS |
214 | #define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N)) |
215 | #define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N)) | |
9ba5ff0f | 216 | |
4038c495 GB |
217 | /* Copy a vector. |
218 | VEC(T,A) *VEC_T_A_copy(VEC(T) *); | |
219 | ||
220 | Copy the live elements of a vector into a new vector. The new and | |
a4174ebf | 221 | old vectors need not be allocated by the same mechanism. */ |
4038c495 GB |
222 | |
223 | #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) | |
224 | ||
9ba5ff0f NS |
225 | /* Determine if a vector has additional capacity. |
226 | ||
227 | int VEC_T_space (VEC(T) *v,int reserve) | |
228 | ||
d4e6fecb | 229 | If V has space for RESERVE additional entries, return nonzero. You |
9ba5ff0f NS |
230 | usually only need to use this if you are doing your own vector |
231 | reallocation, for instance on an embedded vector. This returns | |
8e3c61c5 | 232 | nonzero in exactly the same circumstances that VEC_T_reserve |
9ba5ff0f NS |
233 | will. */ |
234 | ||
d4e6fecb NS |
235 | #define VEC_space(T,V,R) \ |
236 | (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) | |
ada55151 NS |
237 | |
238 | /* Reserve space. | |
d4e6fecb | 239 | int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); |
ada55151 | 240 | |
d4e6fecb NS |
241 | Ensure that V has at least abs(RESERVE) slots available. The |
242 | signedness of RESERVE determines the reallocation behavior. A | |
243 | negative value will not create additional headroom beyond that | |
244 | requested. A positive value will create additional headroom. Note | |
245 | this can cause V to be reallocated. Returns nonzero iff | |
246 | reallocation actually occurred. */ | |
9ba5ff0f | 247 | |
d4e6fecb NS |
248 | #define VEC_reserve(T,A,V,R) \ |
249 | (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) | |
ada55151 NS |
250 | |
251 | /* Push object with no reallocation | |
a0ef884f | 252 | T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer |
ada55151 NS |
253 | T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer |
254 | T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object | |
255 | ||
256 | Push a new element onto the end, returns a pointer to the slot | |
257 | filled in. For object vectors, the new value can be NULL, in which | |
0e61db61 NS |
258 | case NO initialization is performed. There must |
259 | be sufficient space in the vector. */ | |
9ba5ff0f | 260 | |
d4e6fecb NS |
261 | #define VEC_quick_push(T,V,O) \ |
262 | (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) | |
ada55151 NS |
263 | |
264 | /* Push object with reallocation | |
a0ef884f | 265 | T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer |
d4e6fecb NS |
266 | T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer |
267 | T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object | |
ada55151 NS |
268 | |
269 | Push a new element onto the end, returns a pointer to the slot | |
270 | filled in. For object vectors, the new value can be NULL, in which | |
271 | case NO initialization is performed. Reallocates V, if needed. */ | |
9ba5ff0f | 272 | |
d4e6fecb NS |
273 | #define VEC_safe_push(T,A,V,O) \ |
274 | (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) | |
ada55151 NS |
275 | |
276 | /* Pop element off end | |
a0ef884f | 277 | T VEC_T_pop (VEC(T) *v); // Integer |
ada55151 NS |
278 | T VEC_T_pop (VEC(T) *v); // Pointer |
279 | void VEC_T_pop (VEC(T) *v); // Object | |
280 | ||
281 | Pop the last element off the end. Returns the element popped, for | |
282 | pointer vectors. */ | |
9ba5ff0f | 283 | |
d4e6fecb | 284 | #define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) |
ada55151 | 285 | |
a064479c | 286 | /* Truncate to specific length |
3cbf09de | 287 | void VEC_T_truncate (VEC(T) *v, unsigned len); |
a064479c | 288 | |
d4e6fecb NS |
289 | Set the length as specified. The new length must be less than or |
290 | equal to the current length. This is an O(1) operation. */ | |
9ba5ff0f | 291 | |
d4e6fecb NS |
292 | #define VEC_truncate(T,V,I) \ |
293 | (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) | |
294 | ||
295 | /* Grow to a specific length. | |
296 | void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); | |
297 | ||
298 | Grow the vector to a specific length. The LEN must be as | |
299 | long or longer than the current length. The new elements are | |
300 | uninitialized. */ | |
301 | ||
302 | #define VEC_safe_grow(T,A,V,I) \ | |
cdd5a1be | 303 | (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) |
a064479c | 304 | |
ada55151 | 305 | /* Replace element |
a0ef884f | 306 | T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer |
3cbf09de NS |
307 | T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer |
308 | T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object | |
ada55151 NS |
309 | |
310 | Replace the IXth element of V with a new value, VAL. For pointer | |
311 | vectors returns the original value. For object vectors returns a | |
312 | pointer to the new value. For object vectors the new value can be | |
313 | NULL, in which case no overwriting of the slot is actually | |
314 | performed. */ | |
9ba5ff0f | 315 | |
d4e6fecb NS |
316 | #define VEC_replace(T,V,I,O) \ |
317 | (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) | |
ada55151 NS |
318 | |
319 | /* Insert object with no reallocation | |
a0ef884f | 320 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer |
3cbf09de NS |
321 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer |
322 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object | |
ada55151 NS |
323 | |
324 | Insert an element, VAL, at the IXth position of V. Return a pointer | |
325 | to the slot created. For vectors of object, the new value can be | |
326 | NULL, in which case no initialization of the inserted slot takes | |
0e61db61 | 327 | place. There must be sufficient space. */ |
9ba5ff0f | 328 | |
d4e6fecb NS |
329 | #define VEC_quick_insert(T,V,I,O) \ |
330 | (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) | |
ada55151 NS |
331 | |
332 | /* Insert object with reallocation | |
a0ef884f | 333 | T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer |
d4e6fecb NS |
334 | T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer |
335 | T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object | |
ada55151 NS |
336 | |
337 | Insert an element, VAL, at the IXth position of V. Return a pointer | |
338 | to the slot created. For vectors of object, the new value can be | |
339 | NULL, in which case no initialization of the inserted slot takes | |
340 | place. Reallocate V, if necessary. */ | |
9ba5ff0f | 341 | |
d4e6fecb NS |
342 | #define VEC_safe_insert(T,A,V,I,O) \ |
343 | (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) | |
ada55151 NS |
344 | |
345 | /* Remove element retaining order | |
a0ef884f | 346 | T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer |
3cbf09de NS |
347 | T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer |
348 | void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object | |
ada55151 NS |
349 | |
350 | Remove an element from the IXth position of V. Ordering of | |
2a7e31df | 351 | remaining elements is preserved. For pointer vectors returns the |
ada55151 | 352 | removed object. This is an O(N) operation due to a memmove. */ |
9ba5ff0f | 353 | |
d4e6fecb NS |
354 | #define VEC_ordered_remove(T,V,I) \ |
355 | (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) | |
ada55151 NS |
356 | |
357 | /* Remove element destroying order | |
a0ef884f | 358 | T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer |
3cbf09de NS |
359 | T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer |
360 | void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object | |
ada55151 NS |
361 | |
362 | Remove an element from the IXth position of V. Ordering of | |
363 | remaining elements is destroyed. For pointer vectors returns the | |
364 | removed object. This is an O(1) operation. */ | |
9ba5ff0f | 365 | |
d4e6fecb NS |
366 | #define VEC_unordered_remove(T,V,I) \ |
367 | (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) | |
ada55151 | 368 | |
9e28024a NS |
369 | /* Remove a block of elements |
370 | void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); | |
371 | ||
372 | Remove LEN elements starting at the IXth. Ordering is retained. | |
373 | This is an O(1) operation. */ | |
374 | ||
375 | #define VEC_block_remove(T,V,I,L) \ | |
376 | (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO)) | |
377 | ||
aaaa46d2 MM |
378 | /* Get the address of the array of elements |
379 | T *VEC_T_address (VEC(T) v) | |
380 | ||
381 | If you need to directly manipulate the array (for instance, you | |
382 | want to feed it to qsort), use this accessor. */ | |
9ba5ff0f | 383 | |
d4e6fecb | 384 | #define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) |
aaaa46d2 | 385 | |
58152808 | 386 | /* Find the first index in the vector not less than the object. |
a0ef884f NS |
387 | unsigned VEC_T_lower_bound (VEC(T) *v, const T val, |
388 | bool (*lessthan) (const T, const T)); // Integer | |
58152808 DB |
389 | unsigned VEC_T_lower_bound (VEC(T) *v, const T val, |
390 | bool (*lessthan) (const T, const T)); // Pointer | |
391 | unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, | |
392 | bool (*lessthan) (const T*, const T*)); // Object | |
393 | ||
394 | Find the first position in which VAL could be inserted without | |
395 | changing the ordering of V. LESSTHAN is a function that returns | |
471854f8 | 396 | true if the first argument is strictly less than the second. */ |
58152808 | 397 | |
d4e6fecb NS |
398 | #define VEC_lower_bound(T,V,O,LT) \ |
399 | (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) | |
58152808 | 400 | |
ada55151 | 401 | #if !IN_GENGTYPE |
ada55151 | 402 | /* Reallocate an array of elements with prefix. */ |
4c254e68 NS |
403 | extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); |
404 | extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); | |
d4e6fecb NS |
405 | extern void ggc_free (void *); |
406 | #define vec_gc_free(V) ggc_free (V) | |
4c254e68 NS |
407 | extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); |
408 | extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); | |
d4e6fecb | 409 | #define vec_heap_free(V) free (V) |
ada55151 NS |
410 | |
411 | #if ENABLE_CHECKING | |
9ba5ff0f NS |
412 | #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ |
413 | #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ | |
414 | #define VEC_CHECK_PASS ,file_,line_,function_ | |
ada55151 | 415 | |
d4e6fecb NS |
416 | #define VEC_ASSERT(EXPR,OP,T,A) \ |
417 | (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) | |
9ba5ff0f NS |
418 | |
419 | extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) | |
420 | ATTRIBUTE_NORETURN; | |
421 | #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) | |
ada55151 | 422 | #else |
9ba5ff0f NS |
423 | #define VEC_CHECK_INFO |
424 | #define VEC_CHECK_DECL | |
425 | #define VEC_CHECK_PASS | |
d4e6fecb | 426 | #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) |
ada55151 NS |
427 | #endif |
428 | ||
d4e6fecb NS |
429 | #define VEC(T,A) VEC_##T##_##A |
430 | #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP | |
ada55151 | 431 | #else /* IN_GENGTYPE */ |
d4e6fecb | 432 | #define VEC(T,A) VEC_ T _ A |
ada55151 NS |
433 | #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X) |
434 | #define VEC_STRINGIFY_(X) #X | |
435 | #undef GTY | |
436 | #endif /* IN_GENGTYPE */ | |
437 | ||
d4e6fecb NS |
438 | /* Base of vector type, not user visible. */ |
439 | #define VEC_T(T,B) \ | |
a0ef884f NS |
440 | typedef struct VEC(T,B) \ |
441 | { \ | |
442 | unsigned num; \ | |
443 | unsigned alloc; \ | |
444 | T vec[1]; \ | |
445 | } VEC(T,B) | |
446 | ||
447 | #define VEC_T_GTY(T,B) \ | |
d4e6fecb | 448 | typedef struct VEC(T,B) GTY(()) \ |
ada55151 | 449 | { \ |
3cbf09de NS |
450 | unsigned num; \ |
451 | unsigned alloc; \ | |
d4e6fecb NS |
452 | T GTY ((length ("%h.num"))) vec[1]; \ |
453 | } VEC(T,B) | |
454 | ||
455 | /* Derived vector type, user visible. */ | |
a0ef884f | 456 | #define VEC_TA_GTY(T,B,A,GTY) \ |
d4e6fecb NS |
457 | typedef struct VEC(T,A) GTY \ |
458 | { \ | |
459 | VEC(T,B) base; \ | |
460 | } VEC(T,A) | |
461 | ||
462 | /* Convert to base type. */ | |
463 | #define VEC_BASE(P) ((P) ? &(P)->base : 0) | |
ada55151 | 464 | |
a0ef884f NS |
465 | /* Vector of integer-like object. */ |
466 | #if IN_GENGTYPE | |
467 | {"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"}, | |
468 | {"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL}, | |
469 | #else | |
470 | #define DEF_VEC_I(T) \ | |
471 | static inline void VEC_OP (T,must_be,integral_type) (void) \ | |
472 | { \ | |
473 | (void)~(T)0; \ | |
474 | } \ | |
475 | \ | |
476 | VEC_T(T,base); \ | |
477 | VEC_TA_GTY(T,base,none,); \ | |
478 | DEF_VEC_FUNC_P(T) \ | |
479 | struct vec_swallow_trailing_semi | |
480 | #define DEF_VEC_ALLOC_I(T,A) \ | |
481 | VEC_TA_GTY(T,base,A,); \ | |
68486bb3 | 482 | DEF_VEC_ALLOC_FUNC_I(T,A) \ |
a0ef884f NS |
483 | struct vec_swallow_trailing_semi |
484 | #endif | |
485 | ||
ada55151 NS |
486 | /* Vector of pointer to object. */ |
487 | #if IN_GENGTYPE | |
a0ef884f NS |
488 | {"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, |
489 | {"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL}, | |
ada55151 | 490 | #else |
d4e6fecb | 491 | #define DEF_VEC_P(T) \ |
a0ef884f | 492 | static inline void VEC_OP (T,must_be,pointer_type) (void) \ |
d4e6fecb | 493 | { \ |
a0ef884f | 494 | (void)((T)1 == (void *)1); \ |
d4e6fecb NS |
495 | } \ |
496 | \ | |
a0ef884f NS |
497 | VEC_T_GTY(T,base); \ |
498 | VEC_TA_GTY(T,base,none,); \ | |
499 | DEF_VEC_FUNC_P(T) \ | |
500 | struct vec_swallow_trailing_semi | |
501 | #define DEF_VEC_ALLOC_P(T,A) \ | |
502 | VEC_TA_GTY(T,base,A,); \ | |
503 | DEF_VEC_ALLOC_FUNC_P(T,A) \ | |
504 | struct vec_swallow_trailing_semi | |
505 | #endif | |
506 | ||
507 | #define DEF_VEC_FUNC_P(T) \ | |
d4e6fecb | 508 | static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ |
ada55151 NS |
509 | { \ |
510 | return vec_ ? vec_->num : 0; \ | |
511 | } \ | |
512 | \ | |
d4e6fecb NS |
513 | static inline T VEC_OP (T,base,last) \ |
514 | (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ | |
ada55151 | 515 | { \ |
d4e6fecb | 516 | VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ |
ada55151 | 517 | \ |
a301e965 | 518 | return vec_->vec[vec_->num - 1]; \ |
ada55151 NS |
519 | } \ |
520 | \ | |
d4e6fecb NS |
521 | static inline T VEC_OP (T,base,index) \ |
522 | (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 523 | { \ |
d4e6fecb | 524 | VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ |
ada55151 NS |
525 | \ |
526 | return vec_->vec[ix_]; \ | |
527 | } \ | |
528 | \ | |
d4e6fecb NS |
529 | static inline int VEC_OP (T,base,iterate) \ |
530 | (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ | |
ada55151 | 531 | { \ |
9ba5ff0f NS |
532 | if (vec_ && ix_ < vec_->num) \ |
533 | { \ | |
534 | *ptr = vec_->vec[ix_]; \ | |
535 | return 1; \ | |
536 | } \ | |
537 | else \ | |
538 | { \ | |
539 | *ptr = 0; \ | |
540 | return 0; \ | |
541 | } \ | |
ada55151 NS |
542 | } \ |
543 | \ | |
d4e6fecb | 544 | static inline size_t VEC_OP (T,base,embedded_size) \ |
7de5bccc | 545 | (int alloc_) \ |
ada55151 | 546 | { \ |
d4e6fecb | 547 | return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ |
a064479c NS |
548 | } \ |
549 | \ | |
d4e6fecb NS |
550 | static inline void VEC_OP (T,base,embedded_init) \ |
551 | (VEC(T,base) *vec_, int alloc_) \ | |
a064479c NS |
552 | { \ |
553 | vec_->num = 0; \ | |
554 | vec_->alloc = alloc_; \ | |
ada55151 NS |
555 | } \ |
556 | \ | |
d4e6fecb NS |
557 | static inline int VEC_OP (T,base,space) \ |
558 | (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ | |
9ba5ff0f | 559 | { \ |
d4e6fecb NS |
560 | VEC_ASSERT (alloc_ >= 0, "space", T, base); \ |
561 | return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ | |
ada55151 NS |
562 | } \ |
563 | \ | |
d4e6fecb NS |
564 | static inline T *VEC_OP (T,base,quick_push) \ |
565 | (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ | |
ada55151 | 566 | { \ |
d4e6fecb | 567 | T *slot_; \ |
ada55151 | 568 | \ |
d4e6fecb | 569 | VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ |
ada55151 NS |
570 | slot_ = &vec_->vec[vec_->num++]; \ |
571 | *slot_ = obj_; \ | |
572 | \ | |
573 | return slot_; \ | |
574 | } \ | |
575 | \ | |
d4e6fecb | 576 | static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ |
ada55151 | 577 | { \ |
d4e6fecb | 578 | T obj_; \ |
ada55151 | 579 | \ |
d4e6fecb | 580 | VEC_ASSERT (vec_->num, "pop", T, base); \ |
ada55151 NS |
581 | obj_ = vec_->vec[--vec_->num]; \ |
582 | \ | |
583 | return obj_; \ | |
584 | } \ | |
585 | \ | |
d4e6fecb NS |
586 | static inline void VEC_OP (T,base,truncate) \ |
587 | (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ | |
a064479c | 588 | { \ |
d4e6fecb | 589 | VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ |
40005366 NS |
590 | if (vec_) \ |
591 | vec_->num = size_; \ | |
a064479c NS |
592 | } \ |
593 | \ | |
d4e6fecb NS |
594 | static inline T VEC_OP (T,base,replace) \ |
595 | (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ | |
ada55151 | 596 | { \ |
d4e6fecb | 597 | T old_obj_; \ |
ada55151 | 598 | \ |
d4e6fecb | 599 | VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ |
ada55151 NS |
600 | old_obj_ = vec_->vec[ix_]; \ |
601 | vec_->vec[ix_] = obj_; \ | |
602 | \ | |
603 | return old_obj_; \ | |
604 | } \ | |
605 | \ | |
d4e6fecb NS |
606 | static inline T *VEC_OP (T,base,quick_insert) \ |
607 | (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ | |
608 | { \ | |
609 | T *slot_; \ | |
610 | \ | |
611 | VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ | |
612 | VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ | |
ada55151 | 613 | slot_ = &vec_->vec[ix_]; \ |
d4e6fecb | 614 | memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ |
ada55151 NS |
615 | *slot_ = obj_; \ |
616 | \ | |
617 | return slot_; \ | |
618 | } \ | |
619 | \ | |
d4e6fecb NS |
620 | static inline T VEC_OP (T,base,ordered_remove) \ |
621 | (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 622 | { \ |
d4e6fecb NS |
623 | T *slot_; \ |
624 | T obj_; \ | |
ada55151 | 625 | \ |
d4e6fecb | 626 | VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ |
ada55151 NS |
627 | slot_ = &vec_->vec[ix_]; \ |
628 | obj_ = *slot_; \ | |
d4e6fecb | 629 | memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ |
ada55151 NS |
630 | \ |
631 | return obj_; \ | |
632 | } \ | |
633 | \ | |
d4e6fecb NS |
634 | static inline T VEC_OP (T,base,unordered_remove) \ |
635 | (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 636 | { \ |
d4e6fecb NS |
637 | T *slot_; \ |
638 | T obj_; \ | |
ada55151 | 639 | \ |
d4e6fecb | 640 | VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ |
ada55151 NS |
641 | slot_ = &vec_->vec[ix_]; \ |
642 | obj_ = *slot_; \ | |
643 | *slot_ = vec_->vec[--vec_->num]; \ | |
644 | \ | |
645 | return obj_; \ | |
646 | } \ | |
647 | \ | |
9e28024a NS |
648 | static inline void VEC_OP (T,base,block_remove) \ |
649 | (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ | |
650 | { \ | |
651 | T *slot_; \ | |
652 | \ | |
653 | VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ | |
654 | slot_ = &vec_->vec[ix_]; \ | |
655 | vec_->num -= len_; \ | |
656 | memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ | |
657 | } \ | |
658 | \ | |
d4e6fecb NS |
659 | static inline T *VEC_OP (T,base,address) \ |
660 | (VEC(T,base) *vec_) \ | |
aaaa46d2 MM |
661 | { \ |
662 | return vec_ ? vec_->vec : 0; \ | |
663 | } \ | |
664 | \ | |
d4e6fecb NS |
665 | static inline unsigned VEC_OP (T,base,lower_bound) \ |
666 | (VEC(T,base) *vec_, const T obj_, \ | |
667 | bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ | |
668 | { \ | |
669 | unsigned int len_ = VEC_OP (T,base, length) (vec_); \ | |
670 | unsigned int half_, middle_; \ | |
671 | unsigned int first_ = 0; \ | |
672 | while (len_ > 0) \ | |
673 | { \ | |
674 | T middle_elem_; \ | |
675 | half_ = len_ >> 1; \ | |
676 | middle_ = first_; \ | |
677 | middle_ += half_; \ | |
678 | middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ | |
679 | if (lessthan_ (middle_elem_, obj_)) \ | |
680 | { \ | |
681 | first_ = middle_; \ | |
682 | ++first_; \ | |
683 | len_ = len_ - half_ - 1; \ | |
684 | } \ | |
685 | else \ | |
686 | len_ = half_; \ | |
687 | } \ | |
688 | return first_; \ | |
a0ef884f NS |
689 | } |
690 | ||
691 | #define DEF_VEC_ALLOC_FUNC_P(T,A) \ | |
d4e6fecb NS |
692 | static inline VEC(T,A) *VEC_OP (T,A,alloc) \ |
693 | (int alloc_ MEM_STAT_DECL) \ | |
694 | { \ | |
695 | /* We must request exact size allocation, hence the negation. */ \ | |
696 | return (VEC(T,A) *) vec_##A##_p_reserve (NULL, -alloc_ PASS_MEM_STAT); \ | |
697 | } \ | |
698 | \ | |
699 | static inline void VEC_OP (T,A,free) \ | |
700 | (VEC(T,A) **vec_) \ | |
701 | { \ | |
702 | if (*vec_) \ | |
703 | vec_##A##_free (*vec_); \ | |
704 | *vec_ = NULL; \ | |
705 | } \ | |
706 | \ | |
4038c495 GB |
707 | static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ |
708 | { \ | |
709 | size_t len_ = vec_ ? vec_->num : 0; \ | |
710 | VEC (T,A) *new_vec_ = NULL; \ | |
711 | \ | |
712 | if (len_) \ | |
713 | { \ | |
714 | /* We must request exact size allocation, hence the negation. */ \ | |
715 | new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve \ | |
716 | (NULL, -len_ PASS_MEM_STAT)); \ | |
717 | \ | |
718 | new_vec_->base.num = len_; \ | |
719 | memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ | |
720 | } \ | |
721 | return new_vec_; \ | |
722 | } \ | |
723 | \ | |
d4e6fecb NS |
724 | static inline int VEC_OP (T,A,reserve) \ |
725 | (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
726 | { \ | |
727 | int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \ | |
728 | alloc_ < 0 ? -alloc_ : alloc_ \ | |
729 | VEC_CHECK_PASS); \ | |
730 | \ | |
731 | if (extend) \ | |
732 | *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ | |
733 | \ | |
734 | return extend; \ | |
735 | } \ | |
736 | \ | |
737 | static inline void VEC_OP (T,A,safe_grow) \ | |
738 | (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
739 | { \ | |
740 | VEC_ASSERT (size_ >= 0 \ | |
741 | && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ | |
742 | "grow", T, A); \ | |
743 | VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \ | |
744 | VEC_CHECK_PASS PASS_MEM_STAT); \ | |
745 | VEC_BASE (*vec_)->num = size_; \ | |
746 | } \ | |
747 | \ | |
748 | static inline T *VEC_OP (T,A,safe_push) \ | |
749 | (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
750 | { \ | |
751 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
752 | \ | |
753 | return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ | |
754 | } \ | |
755 | \ | |
756 | static inline T *VEC_OP (T,A,safe_insert) \ | |
757 | (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
758 | { \ | |
759 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
760 | \ | |
761 | return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ | |
762 | VEC_CHECK_PASS); \ | |
a0ef884f | 763 | } |
ada55151 NS |
764 | |
765 | /* Vector of object. */ | |
766 | #if IN_GENGTYPE | |
a0ef884f NS |
767 | {"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, |
768 | {"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL}, | |
ada55151 | 769 | #else |
d4e6fecb | 770 | #define DEF_VEC_O(T) \ |
a0ef884f NS |
771 | VEC_T_GTY(T,base); \ |
772 | VEC_TA_GTY(T,base,none,); \ | |
773 | DEF_VEC_FUNC_O(T) \ | |
774 | struct vec_swallow_trailing_semi | |
775 | #define DEF_VEC_ALLOC_O(T,A) \ | |
776 | VEC_TA_GTY(T,base,A,); \ | |
777 | DEF_VEC_ALLOC_FUNC_O(T,A) \ | |
778 | struct vec_swallow_trailing_semi | |
779 | #endif | |
780 | ||
781 | #define DEF_VEC_FUNC_O(T) \ | |
d4e6fecb | 782 | static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ |
ada55151 NS |
783 | { \ |
784 | return vec_ ? vec_->num : 0; \ | |
785 | } \ | |
786 | \ | |
d4e6fecb | 787 | static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ |
ada55151 | 788 | { \ |
d4e6fecb | 789 | VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ |
ada55151 NS |
790 | \ |
791 | return &vec_->vec[vec_->num - 1]; \ | |
792 | } \ | |
793 | \ | |
d4e6fecb NS |
794 | static inline T *VEC_OP (T,base,index) \ |
795 | (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 796 | { \ |
d4e6fecb | 797 | VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ |
ada55151 NS |
798 | \ |
799 | return &vec_->vec[ix_]; \ | |
800 | } \ | |
801 | \ | |
d4e6fecb NS |
802 | static inline int VEC_OP (T,base,iterate) \ |
803 | (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ | |
ada55151 | 804 | { \ |
9ba5ff0f NS |
805 | if (vec_ && ix_ < vec_->num) \ |
806 | { \ | |
807 | *ptr = &vec_->vec[ix_]; \ | |
808 | return 1; \ | |
809 | } \ | |
810 | else \ | |
811 | { \ | |
812 | *ptr = 0; \ | |
813 | return 0; \ | |
814 | } \ | |
ada55151 NS |
815 | } \ |
816 | \ | |
d4e6fecb | 817 | static inline size_t VEC_OP (T,base,embedded_size) \ |
7de5bccc | 818 | (int alloc_) \ |
a064479c | 819 | { \ |
d4e6fecb | 820 | return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ |
ada55151 NS |
821 | } \ |
822 | \ | |
d4e6fecb NS |
823 | static inline void VEC_OP (T,base,embedded_init) \ |
824 | (VEC(T,base) *vec_, int alloc_) \ | |
ada55151 | 825 | { \ |
a064479c NS |
826 | vec_->num = 0; \ |
827 | vec_->alloc = alloc_; \ | |
ada55151 NS |
828 | } \ |
829 | \ | |
d4e6fecb NS |
830 | static inline int VEC_OP (T,base,space) \ |
831 | (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ | |
9ba5ff0f | 832 | { \ |
d4e6fecb NS |
833 | VEC_ASSERT (alloc_ >= 0, "space", T, base); \ |
834 | return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ | |
9ba5ff0f NS |
835 | } \ |
836 | \ | |
d4e6fecb NS |
837 | static inline T *VEC_OP (T,base,quick_push) \ |
838 | (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ | |
ada55151 | 839 | { \ |
d4e6fecb | 840 | T *slot_; \ |
ada55151 | 841 | \ |
d4e6fecb | 842 | VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ |
ada55151 NS |
843 | slot_ = &vec_->vec[vec_->num++]; \ |
844 | if (obj_) \ | |
845 | *slot_ = *obj_; \ | |
846 | \ | |
847 | return slot_; \ | |
848 | } \ | |
849 | \ | |
d4e6fecb | 850 | static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ |
ada55151 | 851 | { \ |
d4e6fecb | 852 | VEC_ASSERT (vec_->num, "pop", T, base); \ |
a064479c NS |
853 | --vec_->num; \ |
854 | } \ | |
855 | \ | |
d4e6fecb NS |
856 | static inline void VEC_OP (T,base,truncate) \ |
857 | (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ | |
a064479c | 858 | { \ |
d4e6fecb | 859 | VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ |
40005366 NS |
860 | if (vec_) \ |
861 | vec_->num = size_; \ | |
ada55151 NS |
862 | } \ |
863 | \ | |
d4e6fecb NS |
864 | static inline T *VEC_OP (T,base,replace) \ |
865 | (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ | |
ada55151 | 866 | { \ |
d4e6fecb | 867 | T *slot_; \ |
ada55151 | 868 | \ |
d4e6fecb | 869 | VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ |
ada55151 NS |
870 | slot_ = &vec_->vec[ix_]; \ |
871 | if (obj_) \ | |
872 | *slot_ = *obj_; \ | |
873 | \ | |
874 | return slot_; \ | |
875 | } \ | |
876 | \ | |
d4e6fecb NS |
877 | static inline T *VEC_OP (T,base,quick_insert) \ |
878 | (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ | |
879 | { \ | |
880 | T *slot_; \ | |
881 | \ | |
882 | VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ | |
883 | VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ | |
ada55151 | 884 | slot_ = &vec_->vec[ix_]; \ |
d4e6fecb | 885 | memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ |
ada55151 NS |
886 | if (obj_) \ |
887 | *slot_ = *obj_; \ | |
888 | \ | |
889 | return slot_; \ | |
890 | } \ | |
891 | \ | |
d4e6fecb NS |
892 | static inline void VEC_OP (T,base,ordered_remove) \ |
893 | (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 894 | { \ |
d4e6fecb | 895 | T *slot_; \ |
ada55151 | 896 | \ |
d4e6fecb NS |
897 | VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ |
898 | slot_ = &vec_->vec[ix_]; \ | |
899 | memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ | |
ada55151 NS |
900 | } \ |
901 | \ | |
d4e6fecb NS |
902 | static inline void VEC_OP (T,base,unordered_remove) \ |
903 | (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ | |
ada55151 | 904 | { \ |
d4e6fecb NS |
905 | VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ |
906 | vec_->vec[ix_] = vec_->vec[--vec_->num]; \ | |
907 | } \ | |
ada55151 | 908 | \ |
9e28024a NS |
909 | static inline void VEC_OP (T,base,block_remove) \ |
910 | (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ | |
911 | { \ | |
912 | T *slot_; \ | |
913 | \ | |
914 | VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ | |
915 | slot_ = &vec_->vec[ix_]; \ | |
916 | vec_->num -= len_; \ | |
917 | memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ | |
918 | } \ | |
919 | \ | |
d4e6fecb NS |
920 | static inline T *VEC_OP (T,base,address) \ |
921 | (VEC(T,base) *vec_) \ | |
922 | { \ | |
923 | return vec_ ? vec_->vec : 0; \ | |
ada55151 NS |
924 | } \ |
925 | \ | |
d4e6fecb NS |
926 | static inline unsigned VEC_OP (T,base,lower_bound) \ |
927 | (VEC(T,base) *vec_, const T *obj_, \ | |
928 | bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ | |
929 | { \ | |
930 | unsigned int len_ = VEC_OP (T, base, length) (vec_); \ | |
931 | unsigned int half_, middle_; \ | |
932 | unsigned int first_ = 0; \ | |
933 | while (len_ > 0) \ | |
934 | { \ | |
935 | T *middle_elem_; \ | |
936 | half_ = len_ >> 1; \ | |
937 | middle_ = first_; \ | |
938 | middle_ += half_; \ | |
939 | middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ | |
940 | if (lessthan_ (middle_elem_, obj_)) \ | |
941 | { \ | |
942 | first_ = middle_; \ | |
943 | ++first_; \ | |
944 | len_ = len_ - half_ - 1; \ | |
945 | } \ | |
946 | else \ | |
947 | len_ = half_; \ | |
948 | } \ | |
949 | return first_; \ | |
a0ef884f | 950 | } |
d4e6fecb | 951 | |
a0ef884f | 952 | #define DEF_VEC_ALLOC_FUNC_O(T,A) \ |
d4e6fecb NS |
953 | static inline VEC(T,A) *VEC_OP (T,A,alloc) \ |
954 | (int alloc_ MEM_STAT_DECL) \ | |
ada55151 | 955 | { \ |
d4e6fecb NS |
956 | /* We must request exact size allocation, hence the negation. */ \ |
957 | return (VEC(T,A) *) vec_##A##_o_reserve (NULL, -alloc_, \ | |
958 | offsetof (VEC(T,A),base.vec), \ | |
959 | sizeof (T) \ | |
960 | PASS_MEM_STAT); \ | |
ada55151 NS |
961 | } \ |
962 | \ | |
4038c495 GB |
963 | static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ |
964 | { \ | |
965 | size_t len_ = vec_ ? vec_->num : 0; \ | |
966 | VEC (T,A) *new_vec_ = NULL; \ | |
967 | \ | |
968 | if (len_) \ | |
969 | { \ | |
970 | /* We must request exact size allocation, hence the negation. */ \ | |
971 | new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve \ | |
972 | (NULL, -len_, \ | |
973 | offsetof (VEC(T,A),base.vec), sizeof (T) \ | |
974 | PASS_MEM_STAT)); \ | |
975 | \ | |
976 | new_vec_->base.num = len_; \ | |
977 | memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ | |
978 | } \ | |
979 | return new_vec_; \ | |
980 | } \ | |
981 | \ | |
d4e6fecb NS |
982 | static inline void VEC_OP (T,A,free) \ |
983 | (VEC(T,A) **vec_) \ | |
aaaa46d2 | 984 | { \ |
d4e6fecb NS |
985 | if (*vec_) \ |
986 | vec_##A##_free (*vec_); \ | |
987 | *vec_ = NULL; \ | |
988 | } \ | |
989 | \ | |
990 | static inline int VEC_OP (T,A,reserve) \ | |
991 | (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
992 | { \ | |
993 | int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \ | |
994 | alloc_ < 0 ? -alloc_ : alloc_ \ | |
995 | VEC_CHECK_PASS); \ | |
996 | \ | |
997 | if (extend) \ | |
998 | *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ | |
999 | offsetof (VEC(T,A),base.vec),\ | |
1000 | sizeof (T) \ | |
1001 | PASS_MEM_STAT); \ | |
1002 | \ | |
1003 | return extend; \ | |
1004 | } \ | |
1005 | \ | |
1006 | static inline void VEC_OP (T,A,safe_grow) \ | |
1007 | (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1008 | { \ | |
1009 | VEC_ASSERT (size_ >= 0 \ | |
1010 | && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ | |
1011 | "grow", T, A); \ | |
1012 | VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \ | |
1013 | VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1014 | VEC_BASE (*vec_)->num = size_; \ | |
d4e6fecb NS |
1015 | } \ |
1016 | \ | |
1017 | static inline T *VEC_OP (T,A,safe_push) \ | |
1018 | (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1019 | { \ | |
1020 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1021 | \ | |
1022 | return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ | |
1023 | } \ | |
1024 | \ | |
1025 | static inline T *VEC_OP (T,A,safe_insert) \ | |
1026 | (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ | |
1027 | VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1028 | { \ | |
1029 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1030 | \ | |
1031 | return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ | |
1032 | VEC_CHECK_PASS); \ | |
a0ef884f | 1033 | } |
68486bb3 ZW |
1034 | |
1035 | #define DEF_VEC_ALLOC_FUNC_I(T,A) \ | |
1036 | static inline VEC(T,A) *VEC_OP (T,A,alloc) \ | |
1037 | (int alloc_ MEM_STAT_DECL) \ | |
1038 | { \ | |
1039 | /* We must request exact size allocation, hence the negation. */ \ | |
1040 | return (VEC(T,A) *) vec_##A##_o_reserve (NULL, -alloc_, \ | |
1041 | offsetof (VEC(T,A),base.vec), \ | |
1042 | sizeof (T) \ | |
1043 | PASS_MEM_STAT); \ | |
1044 | } \ | |
1045 | \ | |
1046 | static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ | |
1047 | { \ | |
1048 | size_t len_ = vec_ ? vec_->num : 0; \ | |
1049 | VEC (T,A) *new_vec_ = NULL; \ | |
1050 | \ | |
1051 | if (len_) \ | |
1052 | { \ | |
1053 | /* We must request exact size allocation, hence the negation. */ \ | |
1054 | new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve \ | |
1055 | (NULL, -len_, \ | |
1056 | offsetof (VEC(T,A),base.vec), sizeof (T) \ | |
1057 | PASS_MEM_STAT)); \ | |
1058 | \ | |
1059 | new_vec_->base.num = len_; \ | |
1060 | memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ | |
1061 | } \ | |
1062 | return new_vec_; \ | |
1063 | } \ | |
1064 | \ | |
1065 | static inline void VEC_OP (T,A,free) \ | |
1066 | (VEC(T,A) **vec_) \ | |
1067 | { \ | |
1068 | if (*vec_) \ | |
1069 | vec_##A##_free (*vec_); \ | |
1070 | *vec_ = NULL; \ | |
1071 | } \ | |
1072 | \ | |
1073 | static inline int VEC_OP (T,A,reserve) \ | |
1074 | (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1075 | { \ | |
1076 | int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \ | |
1077 | alloc_ < 0 ? -alloc_ : alloc_ \ | |
1078 | VEC_CHECK_PASS); \ | |
1079 | \ | |
1080 | if (extend) \ | |
1081 | *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ | |
1082 | offsetof (VEC(T,A),base.vec),\ | |
1083 | sizeof (T) \ | |
1084 | PASS_MEM_STAT); \ | |
1085 | \ | |
1086 | return extend; \ | |
1087 | } \ | |
1088 | \ | |
1089 | static inline void VEC_OP (T,A,safe_grow) \ | |
1090 | (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1091 | { \ | |
1092 | VEC_ASSERT (size_ >= 0 \ | |
1093 | && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ | |
1094 | "grow", T, A); \ | |
1095 | VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \ | |
1096 | VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1097 | VEC_BASE (*vec_)->num = size_; \ | |
68486bb3 ZW |
1098 | } \ |
1099 | \ | |
1100 | static inline T *VEC_OP (T,A,safe_push) \ | |
1101 | (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1102 | { \ | |
1103 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1104 | \ | |
1105 | return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ | |
1106 | } \ | |
1107 | \ | |
1108 | static inline T *VEC_OP (T,A,safe_insert) \ | |
1109 | (VEC(T,A) **vec_, unsigned ix_, const T obj_ \ | |
1110 | VEC_CHECK_DECL MEM_STAT_DECL) \ | |
1111 | { \ | |
1112 | VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ | |
1113 | \ | |
1114 | return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ | |
1115 | VEC_CHECK_PASS); \ | |
1116 | } | |
1117 | ||
ada55151 | 1118 | #endif /* GCC_VEC_H */ |