Commit | Line | Data |
---|---|---|
350da6ee | 1 | /* Vector API for GDB. |
61baf725 | 2 | Copyright (C) 2004-2017 Free Software Foundation, Inc. |
350da6ee DJ |
3 | Contributed by Nathan Sidwell <nathan@codesourcery.com> |
4 | ||
5 | This file is part of GDB. | |
6 | ||
7 | This program is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
a9762ec7 | 9 | the Free Software Foundation; either version 3 of the License, or |
350da6ee DJ |
10 | (at your option) any later version. |
11 | ||
12 | This program is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
a9762ec7 | 18 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
350da6ee DJ |
19 | |
20 | #if !defined (GDB_VEC_H) | |
21 | #define GDB_VEC_H | |
22 | ||
8b5a7a6e SM |
23 | #include "diagnostics.h" |
24 | ||
25 | /* clang has a bug that makes it warn (-Wunused-function) about unused functions | |
26 | that are the result of the DEF_VEC_* macro expansion. See: | |
27 | ||
28 | https://bugs.llvm.org/show_bug.cgi?id=22712 | |
29 | ||
30 | We specifically ignore this warning for the vec functions when the compiler | |
31 | is clang. */ | |
32 | #ifdef __clang__ | |
33 | # define DIAGNOSTIC_IGNORE_UNUSED_VEC_FUNCTION \ | |
34 | DIAGNOSTIC_IGNORE_UNUSED_FUNCTION | |
35 | #else | |
36 | # define DIAGNOSTIC_IGNORE_UNUSED_VEC_FUNCTION | |
37 | #endif | |
38 | ||
350da6ee DJ |
39 | /* The macros here implement a set of templated vector types and |
40 | associated interfaces. These templates are implemented with | |
41 | macros, as we're not in C++ land. The interface functions are | |
42 | typesafe and use static inline functions, sometimes backed by | |
43 | out-of-line generic functions. | |
44 | ||
45 | Because of the different behavior of structure objects, scalar | |
46 | objects and of pointers, there are three flavors, one for each of | |
47 | these variants. Both the structure object and pointer variants | |
48 | pass pointers to objects around -- in the former case the pointers | |
49 | are stored into the vector and in the latter case the pointers are | |
50 | dereferenced and the objects copied into the vector. The scalar | |
51 | object variant is suitable for int-like objects, and the vector | |
52 | elements are returned by value. | |
53 | ||
54 | There are both 'index' and 'iterate' accessors. The iterator | |
55 | returns a boolean iteration condition and updates the iteration | |
56 | variable passed by reference. Because the iterator will be | |
57 | inlined, the address-of can be optimized away. | |
58 | ||
59 | The vectors are implemented using the trailing array idiom, thus | |
60 | they are not resizeable without changing the address of the vector | |
61 | object itself. This means you cannot have variables or fields of | |
62 | vector type -- always use a pointer to a vector. The one exception | |
63 | is the final field of a structure, which could be a vector type. | |
64 | You will have to use the embedded_size & embedded_init calls to | |
65 | create such objects, and they will probably not be resizeable (so | |
66 | don't use the 'safe' allocation variants). The trailing array | |
67 | idiom is used (rather than a pointer to an array of data), because, | |
68 | if we allow NULL to also represent an empty vector, empty vectors | |
69 | occupy minimal space in the structure containing them. | |
70 | ||
71 | Each operation that increases the number of active elements is | |
72 | available in 'quick' and 'safe' variants. The former presumes that | |
73 | there is sufficient allocated space for the operation to succeed | |
74 | (it dies if there is not). The latter will reallocate the | |
75 | vector, if needed. Reallocation causes an exponential increase in | |
76 | vector size. If you know you will be adding N elements, it would | |
77 | be more efficient to use the reserve operation before adding the | |
78 | elements with the 'quick' operation. This will ensure there are at | |
79 | least as many elements as you ask for, it will exponentially | |
80 | increase if there are too few spare slots. If you want reserve a | |
81 | specific number of slots, but do not want the exponential increase | |
82 | (for instance, you know this is the last allocation), use a | |
83 | negative number for reservation. You can also create a vector of a | |
84 | specific size from the get go. | |
85 | ||
86 | You should prefer the push and pop operations, as they append and | |
581e13c1 | 87 | remove from the end of the vector. If you need to remove several |
350da6ee DJ |
88 | items in one go, use the truncate operation. The insert and remove |
89 | operations allow you to change elements in the middle of the | |
90 | vector. There are two remove operations, one which preserves the | |
91 | element ordering 'ordered_remove', and one which does not | |
92 | 'unordered_remove'. The latter function copies the end element | |
93 | into the removed slot, rather than invoke a memmove operation. The | |
94 | 'lower_bound' function will determine where to place an item in the | |
95 | array using insert that will maintain sorted order. | |
96 | ||
97 | If you need to directly manipulate a vector, then the 'address' | |
98 | accessor will return the address of the start of the vector. Also | |
99 | the 'space' predicate will tell you whether there is spare capacity | |
100 | in the vector. You will not normally need to use these two functions. | |
101 | ||
102 | Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro. | |
103 | Variables of vector type are declared using a VEC(TYPEDEF) macro. | |
104 | The characters O, P and I indicate whether TYPEDEF is a pointer | |
105 | (P), object (O) or integral (I) type. Be careful to pick the | |
106 | correct one, as you'll get an awkward and inefficient API if you | |
107 | use the wrong one. There is a check, which results in a | |
108 | compile-time warning, for the P and I versions, but there is no | |
109 | check for the O versions, as that is not possible in plain C. | |
110 | ||
111 | An example of their use would be, | |
112 | ||
113 | DEF_VEC_P(tree); // non-managed tree vector. | |
114 | ||
115 | struct my_struct { | |
116 | VEC(tree) *v; // A (pointer to) a vector of tree pointers. | |
117 | }; | |
118 | ||
119 | struct my_struct *s; | |
120 | ||
121 | if (VEC_length(tree, s->v)) { we have some contents } | |
122 | VEC_safe_push(tree, s->v, decl); // append some decl onto the end | |
123 | for (ix = 0; VEC_iterate(tree, s->v, ix, elt); ix++) | |
124 | { do something with elt } | |
125 | ||
126 | */ | |
127 | ||
128 | /* Macros to invoke API calls. A single macro works for both pointer | |
129 | and object vectors, but the argument and return types might well be | |
130 | different. In each macro, T is the typedef of the vector elements. | |
131 | Some of these macros pass the vector, V, by reference (by taking | |
132 | its address), this is noted in the descriptions. */ | |
133 | ||
134 | /* Length of vector | |
135 | unsigned VEC_T_length(const VEC(T) *v); | |
136 | ||
137 | Return the number of active elements in V. V can be NULL, in which | |
138 | case zero is returned. */ | |
139 | ||
140 | #define VEC_length(T,V) (VEC_OP(T,length)(V)) | |
141 | ||
142 | ||
143 | /* Check if vector is empty | |
144 | int VEC_T_empty(const VEC(T) *v); | |
145 | ||
146 | Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ | |
147 | ||
148 | #define VEC_empty(T,V) (VEC_length (T,V) == 0) | |
149 | ||
150 | ||
151 | /* Get the final element of the vector. | |
152 | T VEC_T_last(VEC(T) *v); // Integer | |
153 | T VEC_T_last(VEC(T) *v); // Pointer | |
154 | T *VEC_T_last(VEC(T) *v); // Object | |
155 | ||
156 | Return the final element. V must not be empty. */ | |
157 | ||
158 | #define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO)) | |
159 | ||
160 | /* Index into vector | |
161 | T VEC_T_index(VEC(T) *v, unsigned ix); // Integer | |
162 | T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer | |
163 | T *VEC_T_index(VEC(T) *v, unsigned ix); // Object | |
164 | ||
165 | Return the IX'th element. If IX must be in the domain of V. */ | |
166 | ||
167 | #define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO)) | |
168 | ||
169 | /* Iterate over vector | |
170 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer | |
171 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer | |
172 | int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object | |
173 | ||
174 | Return iteration condition and update PTR to point to the IX'th | |
175 | element. At the end of iteration, sets PTR to NULL. Use this to | |
176 | iterate over the elements of a vector as follows, | |
177 | ||
178 | for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) | |
179 | continue; */ | |
180 | ||
181 | #define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P))) | |
182 | ||
183 | /* Allocate new vector. | |
184 | VEC(T,A) *VEC_T_alloc(int reserve); | |
185 | ||
186 | Allocate a new vector with space for RESERVE objects. If RESERVE | |
187 | is zero, NO vector is created. */ | |
188 | ||
189 | #define VEC_alloc(T,N) (VEC_OP(T,alloc)(N)) | |
190 | ||
191 | /* Free a vector. | |
192 | void VEC_T_free(VEC(T,A) *&); | |
193 | ||
194 | Free a vector and set it to NULL. */ | |
195 | ||
196 | #define VEC_free(T,V) (VEC_OP(T,free)(&V)) | |
197 | ||
3cf03773 TT |
198 | /* A cleanup function for a vector. |
199 | void VEC_T_cleanup(void *); | |
200 | ||
201 | Clean up a vector. */ | |
202 | ||
203 | #define VEC_cleanup(T) (VEC_OP(T,cleanup)) | |
204 | ||
350da6ee DJ |
205 | /* Use these to determine the required size and initialization of a |
206 | vector embedded within another structure (as the final member). | |
207 | ||
208 | size_t VEC_T_embedded_size(int reserve); | |
209 | void VEC_T_embedded_init(VEC(T) *v, int reserve); | |
210 | ||
211 | These allow the caller to perform the memory allocation. */ | |
212 | ||
213 | #define VEC_embedded_size(T,N) (VEC_OP(T,embedded_size)(N)) | |
214 | #define VEC_embedded_init(T,O,N) (VEC_OP(T,embedded_init)(VEC_BASE(O),N)) | |
215 | ||
216 | /* Copy a vector. | |
217 | VEC(T,A) *VEC_T_copy(VEC(T) *); | |
218 | ||
219 | Copy the live elements of a vector into a new vector. The new and | |
220 | old vectors need not be allocated by the same mechanism. */ | |
221 | ||
222 | #define VEC_copy(T,V) (VEC_OP(T,copy)(V)) | |
223 | ||
de0bea00 MF |
224 | /* Merge two vectors. |
225 | VEC(T,A) *VEC_T_merge(VEC(T) *, VEC(T) *); | |
226 | ||
227 | Copy the live elements of both vectors into a new vector. The new | |
228 | and old vectors need not be allocated by the same mechanism. */ | |
229 | #define VEC_merge(T,V1,V2) (VEC_OP(T,merge)(V1, V2)) | |
230 | ||
350da6ee DJ |
231 | /* Determine if a vector has additional capacity. |
232 | ||
233 | int VEC_T_space (VEC(T) *v,int reserve) | |
234 | ||
235 | If V has space for RESERVE additional entries, return nonzero. You | |
236 | usually only need to use this if you are doing your own vector | |
237 | reallocation, for instance on an embedded vector. This returns | |
238 | nonzero in exactly the same circumstances that VEC_T_reserve | |
239 | will. */ | |
240 | ||
241 | #define VEC_space(T,V,R) (VEC_OP(T,space)(V,R VEC_ASSERT_INFO)) | |
242 | ||
243 | /* Reserve space. | |
244 | int VEC_T_reserve(VEC(T,A) *&v, int reserve); | |
245 | ||
246 | Ensure that V has at least abs(RESERVE) slots available. The | |
247 | signedness of RESERVE determines the reallocation behavior. A | |
248 | negative value will not create additional headroom beyond that | |
249 | requested. A positive value will create additional headroom. Note | |
250 | this can cause V to be reallocated. Returns nonzero iff | |
251 | reallocation actually occurred. */ | |
252 | ||
253 | #define VEC_reserve(T,V,R) (VEC_OP(T,reserve)(&(V),R VEC_ASSERT_INFO)) | |
254 | ||
255 | /* Push object with no reallocation | |
256 | T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer | |
257 | T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer | |
258 | T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object | |
259 | ||
260 | Push a new element onto the end, returns a pointer to the slot | |
581e13c1 | 261 | filled in. For object vectors, the new value can be NULL, in which |
350da6ee DJ |
262 | case NO initialization is performed. There must |
263 | be sufficient space in the vector. */ | |
264 | ||
265 | #define VEC_quick_push(T,V,O) (VEC_OP(T,quick_push)(V,O VEC_ASSERT_INFO)) | |
266 | ||
267 | /* Push object with reallocation | |
268 | T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Integer | |
269 | T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Pointer | |
270 | T *VEC_T_safe_push (VEC(T,A) *&v, T *obj); // Object | |
271 | ||
272 | Push a new element onto the end, returns a pointer to the slot | |
581e13c1 | 273 | filled in. For object vectors, the new value can be NULL, in which |
350da6ee DJ |
274 | case NO initialization is performed. Reallocates V, if needed. */ |
275 | ||
276 | #define VEC_safe_push(T,V,O) (VEC_OP(T,safe_push)(&(V),O VEC_ASSERT_INFO)) | |
277 | ||
278 | /* Pop element off end | |
279 | T VEC_T_pop (VEC(T) *v); // Integer | |
280 | T VEC_T_pop (VEC(T) *v); // Pointer | |
281 | void VEC_T_pop (VEC(T) *v); // Object | |
282 | ||
581e13c1 | 283 | Pop the last element off the end. Returns the element popped, for |
350da6ee DJ |
284 | pointer vectors. */ |
285 | ||
286 | #define VEC_pop(T,V) (VEC_OP(T,pop)(V VEC_ASSERT_INFO)) | |
287 | ||
288 | /* Truncate to specific length | |
289 | void VEC_T_truncate (VEC(T) *v, unsigned len); | |
290 | ||
291 | Set the length as specified. The new length must be less than or | |
292 | equal to the current length. This is an O(1) operation. */ | |
293 | ||
294 | #define VEC_truncate(T,V,I) \ | |
295 | (VEC_OP(T,truncate)(V,I VEC_ASSERT_INFO)) | |
296 | ||
297 | /* Grow to a specific length. | |
298 | void VEC_T_safe_grow (VEC(T,A) *&v, int len); | |
299 | ||
300 | Grow the vector to a specific length. The LEN must be as | |
301 | long or longer than the current length. The new elements are | |
302 | uninitialized. */ | |
303 | ||
304 | #define VEC_safe_grow(T,V,I) \ | |
305 | (VEC_OP(T,safe_grow)(&(V),I VEC_ASSERT_INFO)) | |
306 | ||
307 | /* Replace element | |
308 | T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer | |
309 | T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer | |
310 | T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object | |
311 | ||
312 | Replace the IXth element of V with a new value, VAL. For pointer | |
581e13c1 | 313 | vectors returns the original value. For object vectors returns a |
350da6ee DJ |
314 | pointer to the new value. For object vectors the new value can be |
315 | NULL, in which case no overwriting of the slot is actually | |
316 | performed. */ | |
317 | ||
318 | #define VEC_replace(T,V,I,O) (VEC_OP(T,replace)(V,I,O VEC_ASSERT_INFO)) | |
319 | ||
320 | /* Insert object with no reallocation | |
321 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer | |
322 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer | |
323 | T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object | |
324 | ||
581e13c1 | 325 | Insert an element, VAL, at the IXth position of V. Return a pointer |
350da6ee DJ |
326 | to the slot created. For vectors of object, the new value can be |
327 | NULL, in which case no initialization of the inserted slot takes | |
581e13c1 | 328 | place. There must be sufficient space. */ |
350da6ee DJ |
329 | |
330 | #define VEC_quick_insert(T,V,I,O) \ | |
331 | (VEC_OP(T,quick_insert)(V,I,O VEC_ASSERT_INFO)) | |
332 | ||
333 | /* Insert object with reallocation | |
334 | T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer | |
335 | T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer | |
336 | T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object | |
337 | ||
581e13c1 | 338 | Insert an element, VAL, at the IXth position of V. Return a pointer |
350da6ee DJ |
339 | to the slot created. For vectors of object, the new value can be |
340 | NULL, in which case no initialization of the inserted slot takes | |
581e13c1 | 341 | place. Reallocate V, if necessary. */ |
350da6ee DJ |
342 | |
343 | #define VEC_safe_insert(T,V,I,O) \ | |
344 | (VEC_OP(T,safe_insert)(&(V),I,O VEC_ASSERT_INFO)) | |
345 | ||
346 | /* Remove element retaining order | |
347 | T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer | |
348 | T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer | |
349 | void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object | |
350 | ||
581e13c1 | 351 | Remove an element from the IXth position of V. Ordering of |
350da6ee DJ |
352 | remaining elements is preserved. For pointer vectors returns the |
353 | removed object. This is an O(N) operation due to a memmove. */ | |
354 | ||
355 | #define VEC_ordered_remove(T,V,I) \ | |
356 | (VEC_OP(T,ordered_remove)(V,I VEC_ASSERT_INFO)) | |
357 | ||
358 | /* Remove element destroying order | |
359 | T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer | |
360 | T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer | |
361 | void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object | |
362 | ||
581e13c1 | 363 | Remove an element from the IXth position of V. Ordering of |
350da6ee DJ |
364 | remaining elements is destroyed. For pointer vectors returns the |
365 | removed object. This is an O(1) operation. */ | |
366 | ||
367 | #define VEC_unordered_remove(T,V,I) \ | |
368 | (VEC_OP(T,unordered_remove)(V,I VEC_ASSERT_INFO)) | |
369 | ||
370 | /* Remove a block of elements | |
371 | void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); | |
372 | ||
373 | Remove LEN elements starting at the IXth. Ordering is retained. | |
2287cc7e | 374 | This is an O(N) operation due to memmove. */ |
350da6ee DJ |
375 | |
376 | #define VEC_block_remove(T,V,I,L) \ | |
2287cc7e | 377 | (VEC_OP(T,block_remove)(V,I,L VEC_ASSERT_INFO)) |
350da6ee DJ |
378 | |
379 | /* Get the address of the array of elements | |
380 | T *VEC_T_address (VEC(T) v) | |
381 | ||
382 | If you need to directly manipulate the array (for instance, you | |
383 | want to feed it to qsort), use this accessor. */ | |
384 | ||
385 | #define VEC_address(T,V) (VEC_OP(T,address)(V)) | |
386 | ||
387 | /* Find the first index in the vector not less than the object. | |
388 | unsigned VEC_T_lower_bound (VEC(T) *v, const T val, | |
389 | int (*lessthan) (const T, const T)); // Integer | |
390 | unsigned VEC_T_lower_bound (VEC(T) *v, const T val, | |
391 | int (*lessthan) (const T, const T)); // Pointer | |
392 | unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, | |
393 | int (*lessthan) (const T*, const T*)); // Object | |
394 | ||
395 | Find the first position in which VAL could be inserted without | |
396 | changing the ordering of V. LESSTHAN is a function that returns | |
397 | true if the first argument is strictly less than the second. */ | |
398 | ||
399 | #define VEC_lower_bound(T,V,O,LT) \ | |
400 | (VEC_OP(T,lower_bound)(V,O,LT VEC_ASSERT_INFO)) | |
401 | ||
402 | /* Reallocate an array of elements with prefix. */ | |
403 | extern void *vec_p_reserve (void *, int); | |
404 | extern void *vec_o_reserve (void *, int, size_t, size_t); | |
1e8877aa | 405 | #define vec_free_(V) xfree (V) |
350da6ee DJ |
406 | |
407 | #define VEC_ASSERT_INFO ,__FILE__,__LINE__ | |
408 | #define VEC_ASSERT_DECL ,const char *file_,unsigned line_ | |
409 | #define VEC_ASSERT_PASS ,file_,line_ | |
410 | #define vec_assert(expr, op) \ | |
3e43a32a | 411 | ((void)((expr) ? 0 : (gdb_assert_fail (op, file_, line_, \ |
df049a58 | 412 | FUNCTION_NAME), 0))) |
350da6ee DJ |
413 | |
414 | #define VEC(T) VEC_##T | |
415 | #define VEC_OP(T,OP) VEC_##T##_##OP | |
416 | ||
417 | #define VEC_T(T) \ | |
418 | typedef struct VEC(T) \ | |
419 | { \ | |
420 | unsigned num; \ | |
421 | unsigned alloc; \ | |
422 | T vec[1]; \ | |
423 | } VEC(T) | |
424 | ||
425 | /* Vector of integer-like object. */ | |
426 | #define DEF_VEC_I(T) \ | |
8b5a7a6e SM |
427 | DIAGNOSTIC_PUSH \ |
428 | DIAGNOSTIC_IGNORE_UNUSED_VEC_FUNCTION \ | |
350da6ee DJ |
429 | static inline void VEC_OP (T,must_be_integral_type) (void) \ |
430 | { \ | |
431 | (void)~(T)0; \ | |
432 | } \ | |
433 | \ | |
434 | VEC_T(T); \ | |
435 | DEF_VEC_FUNC_P(T) \ | |
436 | DEF_VEC_ALLOC_FUNC_I(T) \ | |
8b5a7a6e | 437 | DIAGNOSTIC_POP \ |
350da6ee DJ |
438 | struct vec_swallow_trailing_semi |
439 | ||
440 | /* Vector of pointer to object. */ | |
441 | #define DEF_VEC_P(T) \ | |
8b5a7a6e SM |
442 | DIAGNOSTIC_PUSH \ |
443 | DIAGNOSTIC_IGNORE_UNUSED_VEC_FUNCTION \ | |
350da6ee DJ |
444 | static inline void VEC_OP (T,must_be_pointer_type) (void) \ |
445 | { \ | |
446 | (void)((T)1 == (void *)1); \ | |
447 | } \ | |
448 | \ | |
449 | VEC_T(T); \ | |
450 | DEF_VEC_FUNC_P(T) \ | |
451 | DEF_VEC_ALLOC_FUNC_P(T) \ | |
8b5a7a6e | 452 | DIAGNOSTIC_POP \ |
350da6ee DJ |
453 | struct vec_swallow_trailing_semi |
454 | ||
455 | /* Vector of object. */ | |
456 | #define DEF_VEC_O(T) \ | |
8b5a7a6e SM |
457 | DIAGNOSTIC_PUSH \ |
458 | DIAGNOSTIC_IGNORE_UNUSED_VEC_FUNCTION \ | |
350da6ee DJ |
459 | VEC_T(T); \ |
460 | DEF_VEC_FUNC_O(T) \ | |
461 | DEF_VEC_ALLOC_FUNC_O(T) \ | |
8b5a7a6e | 462 | DIAGNOSTIC_POP \ |
350da6ee DJ |
463 | struct vec_swallow_trailing_semi |
464 | ||
a4e22a5d PA |
465 | /* Avoid offsetof (or its usual C implementation) as it triggers |
466 | -Winvalid-offsetof warnings with enum_flags types with G++ <= 4.4, | |
467 | even though those types are memcpyable. This requires allocating a | |
468 | dummy local VEC in all routines that use this, but that has the | |
469 | advantage that it only works if T is default constructible, which | |
470 | is exactly a check we want, to keep C compatibility. */ | |
471 | #define vec_offset(T, VPTR) ((size_t) ((char *) &(VPTR)->vec - (char *) VPTR)) | |
472 | ||
350da6ee DJ |
473 | #define DEF_VEC_ALLOC_FUNC_I(T) \ |
474 | static inline VEC(T) *VEC_OP (T,alloc) \ | |
475 | (int alloc_) \ | |
476 | { \ | |
a4e22a5d PA |
477 | VEC(T) dummy; \ |
478 | \ | |
350da6ee DJ |
479 | /* We must request exact size allocation, hence the negation. */ \ |
480 | return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \ | |
a4e22a5d | 481 | vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
482 | } \ |
483 | \ | |
484 | static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ | |
485 | { \ | |
486 | size_t len_ = vec_ ? vec_->num : 0; \ | |
487 | VEC (T) *new_vec_ = NULL; \ | |
488 | \ | |
489 | if (len_) \ | |
490 | { \ | |
a4e22a5d PA |
491 | VEC(T) dummy; \ |
492 | \ | |
581e13c1 | 493 | /* We must request exact size allocation, hence the negation. */ \ |
350da6ee | 494 | new_vec_ = (VEC (T) *) \ |
a4e22a5d | 495 | vec_o_reserve (NULL, -len_, vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
496 | \ |
497 | new_vec_->num = len_; \ | |
498 | memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ | |
499 | } \ | |
500 | return new_vec_; \ | |
501 | } \ | |
502 | \ | |
de0bea00 MF |
503 | static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ |
504 | { \ | |
505 | if (vec1_ && vec2_) \ | |
506 | { \ | |
a4e22a5d | 507 | VEC(T) dummy; \ |
de0bea00 MF |
508 | size_t len_ = vec1_->num + vec2_->num; \ |
509 | VEC (T) *new_vec_ = NULL; \ | |
510 | \ | |
511 | /* We must request exact size allocation, hence the negation. */ \ | |
512 | new_vec_ = (VEC (T) *) \ | |
a4e22a5d | 513 | vec_o_reserve (NULL, -len_, vec_offset (T, &dummy), sizeof (T)); \ |
de0bea00 MF |
514 | \ |
515 | new_vec_->num = len_; \ | |
516 | memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ | |
517 | memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ | |
518 | sizeof (T) * vec2_->num); \ | |
519 | \ | |
520 | return new_vec_; \ | |
521 | } \ | |
522 | else \ | |
523 | return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ | |
524 | } \ | |
525 | \ | |
350da6ee DJ |
526 | static inline void VEC_OP (T,free) \ |
527 | (VEC(T) **vec_) \ | |
528 | { \ | |
529 | if (*vec_) \ | |
1e8877aa | 530 | vec_free_ (*vec_); \ |
350da6ee DJ |
531 | *vec_ = NULL; \ |
532 | } \ | |
533 | \ | |
3cf03773 TT |
534 | static inline void VEC_OP (T,cleanup) \ |
535 | (void *arg_) \ | |
536 | { \ | |
dd0a637a | 537 | VEC(T) **vec_ = (VEC(T) **) arg_; \ |
3cf03773 TT |
538 | if (*vec_) \ |
539 | vec_free_ (*vec_); \ | |
540 | *vec_ = NULL; \ | |
541 | } \ | |
542 | \ | |
350da6ee DJ |
543 | static inline int VEC_OP (T,reserve) \ |
544 | (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ | |
545 | { \ | |
a4e22a5d | 546 | VEC(T) dummy; \ |
350da6ee DJ |
547 | int extend = !VEC_OP (T,space) \ |
548 | (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \ | |
549 | \ | |
550 | if (extend) \ | |
551 | *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \ | |
a4e22a5d | 552 | vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
553 | \ |
554 | return extend; \ | |
555 | } \ | |
556 | \ | |
557 | static inline void VEC_OP (T,safe_grow) \ | |
558 | (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ | |
559 | { \ | |
560 | vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ | |
561 | "safe_grow"); \ | |
562 | VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \ | |
563 | VEC_ASSERT_PASS); \ | |
564 | (*vec_)->num = size_; \ | |
565 | } \ | |
566 | \ | |
567 | static inline T *VEC_OP (T,safe_push) \ | |
568 | (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \ | |
569 | { \ | |
570 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
571 | \ | |
572 | return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ | |
573 | } \ | |
574 | \ | |
575 | static inline T *VEC_OP (T,safe_insert) \ | |
576 | (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \ | |
577 | { \ | |
578 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
579 | \ | |
580 | return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ | |
581 | } | |
582 | ||
583 | #define DEF_VEC_FUNC_P(T) \ | |
584 | static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \ | |
585 | { \ | |
586 | return vec_ ? vec_->num : 0; \ | |
587 | } \ | |
588 | \ | |
589 | static inline T VEC_OP (T,last) \ | |
590 | (const VEC(T) *vec_ VEC_ASSERT_DECL) \ | |
591 | { \ | |
592 | vec_assert (vec_ && vec_->num, "last"); \ | |
593 | \ | |
594 | return vec_->vec[vec_->num - 1]; \ | |
595 | } \ | |
596 | \ | |
597 | static inline T VEC_OP (T,index) \ | |
598 | (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
599 | { \ | |
600 | vec_assert (vec_ && ix_ < vec_->num, "index"); \ | |
601 | \ | |
602 | return vec_->vec[ix_]; \ | |
603 | } \ | |
604 | \ | |
605 | static inline int VEC_OP (T,iterate) \ | |
606 | (const VEC(T) *vec_, unsigned ix_, T *ptr) \ | |
607 | { \ | |
608 | if (vec_ && ix_ < vec_->num) \ | |
609 | { \ | |
610 | *ptr = vec_->vec[ix_]; \ | |
611 | return 1; \ | |
612 | } \ | |
613 | else \ | |
614 | { \ | |
7535d5ed | 615 | *ptr = (T) 0; \ |
350da6ee DJ |
616 | return 0; \ |
617 | } \ | |
618 | } \ | |
619 | \ | |
620 | static inline size_t VEC_OP (T,embedded_size) \ | |
621 | (int alloc_) \ | |
622 | { \ | |
a4e22a5d PA |
623 | VEC(T) dummy; \ |
624 | \ | |
625 | return vec_offset (T, &dummy) + alloc_ * sizeof(T); \ | |
350da6ee DJ |
626 | } \ |
627 | \ | |
628 | static inline void VEC_OP (T,embedded_init) \ | |
629 | (VEC(T) *vec_, int alloc_) \ | |
630 | { \ | |
631 | vec_->num = 0; \ | |
632 | vec_->alloc = alloc_; \ | |
633 | } \ | |
634 | \ | |
635 | static inline int VEC_OP (T,space) \ | |
636 | (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \ | |
637 | { \ | |
638 | vec_assert (alloc_ >= 0, "space"); \ | |
639 | return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ | |
640 | } \ | |
641 | \ | |
642 | static inline T *VEC_OP (T,quick_push) \ | |
643 | (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \ | |
644 | { \ | |
645 | T *slot_; \ | |
646 | \ | |
647 | vec_assert (vec_->num < vec_->alloc, "quick_push"); \ | |
648 | slot_ = &vec_->vec[vec_->num++]; \ | |
649 | *slot_ = obj_; \ | |
650 | \ | |
651 | return slot_; \ | |
652 | } \ | |
653 | \ | |
654 | static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \ | |
655 | { \ | |
656 | T obj_; \ | |
657 | \ | |
658 | vec_assert (vec_->num, "pop"); \ | |
659 | obj_ = vec_->vec[--vec_->num]; \ | |
660 | \ | |
661 | return obj_; \ | |
662 | } \ | |
663 | \ | |
664 | static inline void VEC_OP (T,truncate) \ | |
665 | (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \ | |
666 | { \ | |
667 | vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \ | |
668 | if (vec_) \ | |
669 | vec_->num = size_; \ | |
670 | } \ | |
671 | \ | |
672 | static inline T VEC_OP (T,replace) \ | |
673 | (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ | |
674 | { \ | |
675 | T old_obj_; \ | |
676 | \ | |
677 | vec_assert (ix_ < vec_->num, "replace"); \ | |
678 | old_obj_ = vec_->vec[ix_]; \ | |
679 | vec_->vec[ix_] = obj_; \ | |
680 | \ | |
681 | return old_obj_; \ | |
682 | } \ | |
683 | \ | |
684 | static inline T *VEC_OP (T,quick_insert) \ | |
685 | (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ | |
686 | { \ | |
687 | T *slot_; \ | |
688 | \ | |
689 | vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \ | |
690 | slot_ = &vec_->vec[ix_]; \ | |
691 | memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ | |
692 | *slot_ = obj_; \ | |
693 | \ | |
694 | return slot_; \ | |
695 | } \ | |
696 | \ | |
697 | static inline T VEC_OP (T,ordered_remove) \ | |
698 | (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
699 | { \ | |
700 | T *slot_; \ | |
701 | T obj_; \ | |
702 | \ | |
703 | vec_assert (ix_ < vec_->num, "ordered_remove"); \ | |
704 | slot_ = &vec_->vec[ix_]; \ | |
705 | obj_ = *slot_; \ | |
706 | memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ | |
707 | \ | |
708 | return obj_; \ | |
709 | } \ | |
710 | \ | |
711 | static inline T VEC_OP (T,unordered_remove) \ | |
712 | (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
713 | { \ | |
714 | T *slot_; \ | |
715 | T obj_; \ | |
716 | \ | |
717 | vec_assert (ix_ < vec_->num, "unordered_remove"); \ | |
718 | slot_ = &vec_->vec[ix_]; \ | |
719 | obj_ = *slot_; \ | |
720 | *slot_ = vec_->vec[--vec_->num]; \ | |
721 | \ | |
722 | return obj_; \ | |
723 | } \ | |
724 | \ | |
725 | static inline void VEC_OP (T,block_remove) \ | |
726 | (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \ | |
727 | { \ | |
728 | T *slot_; \ | |
729 | \ | |
730 | vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \ | |
731 | slot_ = &vec_->vec[ix_]; \ | |
732 | vec_->num -= len_; \ | |
733 | memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ | |
734 | } \ | |
735 | \ | |
736 | static inline T *VEC_OP (T,address) \ | |
737 | (VEC(T) *vec_) \ | |
738 | { \ | |
739 | return vec_ ? vec_->vec : 0; \ | |
740 | } \ | |
741 | \ | |
742 | static inline unsigned VEC_OP (T,lower_bound) \ | |
743 | (VEC(T) *vec_, const T obj_, \ | |
744 | int (*lessthan_)(const T, const T) VEC_ASSERT_DECL) \ | |
745 | { \ | |
746 | unsigned int len_ = VEC_OP (T, length) (vec_); \ | |
747 | unsigned int half_, middle_; \ | |
748 | unsigned int first_ = 0; \ | |
749 | while (len_ > 0) \ | |
750 | { \ | |
751 | T middle_elem_; \ | |
752 | half_ = len_ >> 1; \ | |
753 | middle_ = first_; \ | |
754 | middle_ += half_; \ | |
755 | middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \ | |
756 | if (lessthan_ (middle_elem_, obj_)) \ | |
757 | { \ | |
758 | first_ = middle_; \ | |
759 | ++first_; \ | |
760 | len_ = len_ - half_ - 1; \ | |
761 | } \ | |
762 | else \ | |
763 | len_ = half_; \ | |
764 | } \ | |
765 | return first_; \ | |
766 | } | |
767 | ||
768 | #define DEF_VEC_ALLOC_FUNC_P(T) \ | |
769 | static inline VEC(T) *VEC_OP (T,alloc) \ | |
770 | (int alloc_) \ | |
771 | { \ | |
772 | /* We must request exact size allocation, hence the negation. */ \ | |
773 | return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \ | |
774 | } \ | |
775 | \ | |
776 | static inline void VEC_OP (T,free) \ | |
777 | (VEC(T) **vec_) \ | |
778 | { \ | |
779 | if (*vec_) \ | |
1e8877aa | 780 | vec_free_ (*vec_); \ |
350da6ee DJ |
781 | *vec_ = NULL; \ |
782 | } \ | |
783 | \ | |
3cf03773 TT |
784 | static inline void VEC_OP (T,cleanup) \ |
785 | (void *arg_) \ | |
786 | { \ | |
dd0a637a | 787 | VEC(T) **vec_ = (VEC(T) **) arg_; \ |
3cf03773 TT |
788 | if (*vec_) \ |
789 | vec_free_ (*vec_); \ | |
790 | *vec_ = NULL; \ | |
791 | } \ | |
792 | \ | |
350da6ee DJ |
793 | static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ |
794 | { \ | |
795 | size_t len_ = vec_ ? vec_->num : 0; \ | |
796 | VEC (T) *new_vec_ = NULL; \ | |
797 | \ | |
798 | if (len_) \ | |
799 | { \ | |
581e13c1 | 800 | /* We must request exact size allocation, hence the negation. */ \ |
350da6ee DJ |
801 | new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \ |
802 | \ | |
803 | new_vec_->num = len_; \ | |
804 | memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ | |
805 | } \ | |
806 | return new_vec_; \ | |
807 | } \ | |
808 | \ | |
de0bea00 MF |
809 | static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ |
810 | { \ | |
811 | if (vec1_ && vec2_) \ | |
812 | { \ | |
813 | size_t len_ = vec1_->num + vec2_->num; \ | |
814 | VEC (T) *new_vec_ = NULL; \ | |
815 | \ | |
816 | /* We must request exact size allocation, hence the negation. */ \ | |
817 | new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \ | |
818 | \ | |
819 | new_vec_->num = len_; \ | |
820 | memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ | |
821 | memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ | |
822 | sizeof (T) * vec2_->num); \ | |
823 | \ | |
824 | return new_vec_; \ | |
825 | } \ | |
826 | else \ | |
827 | return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ | |
828 | } \ | |
829 | \ | |
350da6ee DJ |
830 | static inline int VEC_OP (T,reserve) \ |
831 | (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ | |
832 | { \ | |
833 | int extend = !VEC_OP (T,space) \ | |
834 | (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \ | |
835 | \ | |
836 | if (extend) \ | |
837 | *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \ | |
838 | \ | |
839 | return extend; \ | |
840 | } \ | |
841 | \ | |
842 | static inline void VEC_OP (T,safe_grow) \ | |
843 | (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ | |
844 | { \ | |
845 | vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ | |
846 | "safe_grow"); \ | |
847 | VEC_OP (T,reserve) \ | |
848 | (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \ | |
849 | (*vec_)->num = size_; \ | |
850 | } \ | |
851 | \ | |
852 | static inline T *VEC_OP (T,safe_push) \ | |
853 | (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \ | |
854 | { \ | |
855 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
856 | \ | |
857 | return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ | |
858 | } \ | |
859 | \ | |
860 | static inline T *VEC_OP (T,safe_insert) \ | |
861 | (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ | |
862 | { \ | |
863 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
864 | \ | |
865 | return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ | |
866 | } | |
867 | ||
868 | #define DEF_VEC_FUNC_O(T) \ | |
869 | static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \ | |
870 | { \ | |
871 | return vec_ ? vec_->num : 0; \ | |
872 | } \ | |
873 | \ | |
874 | static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \ | |
875 | { \ | |
876 | vec_assert (vec_ && vec_->num, "last"); \ | |
877 | \ | |
878 | return &vec_->vec[vec_->num - 1]; \ | |
879 | } \ | |
880 | \ | |
881 | static inline T *VEC_OP (T,index) \ | |
882 | (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
883 | { \ | |
884 | vec_assert (vec_ && ix_ < vec_->num, "index"); \ | |
885 | \ | |
886 | return &vec_->vec[ix_]; \ | |
887 | } \ | |
888 | \ | |
889 | static inline int VEC_OP (T,iterate) \ | |
890 | (VEC(T) *vec_, unsigned ix_, T **ptr) \ | |
891 | { \ | |
892 | if (vec_ && ix_ < vec_->num) \ | |
893 | { \ | |
894 | *ptr = &vec_->vec[ix_]; \ | |
895 | return 1; \ | |
896 | } \ | |
897 | else \ | |
898 | { \ | |
899 | *ptr = 0; \ | |
900 | return 0; \ | |
901 | } \ | |
902 | } \ | |
903 | \ | |
904 | static inline size_t VEC_OP (T,embedded_size) \ | |
905 | (int alloc_) \ | |
906 | { \ | |
a4e22a5d PA |
907 | VEC(T) dummy; \ |
908 | \ | |
909 | return vec_offset (T, &dummy) + alloc_ * sizeof(T); \ | |
350da6ee DJ |
910 | } \ |
911 | \ | |
912 | static inline void VEC_OP (T,embedded_init) \ | |
913 | (VEC(T) *vec_, int alloc_) \ | |
914 | { \ | |
915 | vec_->num = 0; \ | |
916 | vec_->alloc = alloc_; \ | |
917 | } \ | |
918 | \ | |
919 | static inline int VEC_OP (T,space) \ | |
920 | (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \ | |
921 | { \ | |
922 | vec_assert (alloc_ >= 0, "space"); \ | |
923 | return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ | |
924 | } \ | |
925 | \ | |
926 | static inline T *VEC_OP (T,quick_push) \ | |
927 | (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \ | |
928 | { \ | |
929 | T *slot_; \ | |
930 | \ | |
931 | vec_assert (vec_->num < vec_->alloc, "quick_push"); \ | |
932 | slot_ = &vec_->vec[vec_->num++]; \ | |
933 | if (obj_) \ | |
934 | *slot_ = *obj_; \ | |
935 | \ | |
936 | return slot_; \ | |
937 | } \ | |
938 | \ | |
939 | static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \ | |
940 | { \ | |
941 | vec_assert (vec_->num, "pop"); \ | |
942 | --vec_->num; \ | |
943 | } \ | |
944 | \ | |
945 | static inline void VEC_OP (T,truncate) \ | |
946 | (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \ | |
947 | { \ | |
948 | vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \ | |
949 | if (vec_) \ | |
950 | vec_->num = size_; \ | |
951 | } \ | |
952 | \ | |
953 | static inline T *VEC_OP (T,replace) \ | |
954 | (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ | |
955 | { \ | |
956 | T *slot_; \ | |
957 | \ | |
958 | vec_assert (ix_ < vec_->num, "replace"); \ | |
959 | slot_ = &vec_->vec[ix_]; \ | |
960 | if (obj_) \ | |
961 | *slot_ = *obj_; \ | |
962 | \ | |
963 | return slot_; \ | |
964 | } \ | |
965 | \ | |
966 | static inline T *VEC_OP (T,quick_insert) \ | |
967 | (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ | |
968 | { \ | |
969 | T *slot_; \ | |
970 | \ | |
971 | vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \ | |
972 | slot_ = &vec_->vec[ix_]; \ | |
973 | memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ | |
974 | if (obj_) \ | |
975 | *slot_ = *obj_; \ | |
976 | \ | |
977 | return slot_; \ | |
978 | } \ | |
979 | \ | |
980 | static inline void VEC_OP (T,ordered_remove) \ | |
981 | (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
982 | { \ | |
983 | T *slot_; \ | |
984 | \ | |
985 | vec_assert (ix_ < vec_->num, "ordered_remove"); \ | |
986 | slot_ = &vec_->vec[ix_]; \ | |
987 | memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ | |
988 | } \ | |
989 | \ | |
990 | static inline void VEC_OP (T,unordered_remove) \ | |
991 | (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ | |
992 | { \ | |
993 | vec_assert (ix_ < vec_->num, "unordered_remove"); \ | |
994 | vec_->vec[ix_] = vec_->vec[--vec_->num]; \ | |
995 | } \ | |
996 | \ | |
997 | static inline void VEC_OP (T,block_remove) \ | |
998 | (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \ | |
999 | { \ | |
1000 | T *slot_; \ | |
1001 | \ | |
1002 | vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \ | |
1003 | slot_ = &vec_->vec[ix_]; \ | |
1004 | vec_->num -= len_; \ | |
1005 | memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ | |
1006 | } \ | |
1007 | \ | |
1008 | static inline T *VEC_OP (T,address) \ | |
1009 | (VEC(T) *vec_) \ | |
1010 | { \ | |
1011 | return vec_ ? vec_->vec : 0; \ | |
1012 | } \ | |
1013 | \ | |
1014 | static inline unsigned VEC_OP (T,lower_bound) \ | |
1015 | (VEC(T) *vec_, const T *obj_, \ | |
1016 | int (*lessthan_)(const T *, const T *) VEC_ASSERT_DECL) \ | |
1017 | { \ | |
1018 | unsigned int len_ = VEC_OP (T, length) (vec_); \ | |
1019 | unsigned int half_, middle_; \ | |
1020 | unsigned int first_ = 0; \ | |
1021 | while (len_ > 0) \ | |
1022 | { \ | |
1023 | T *middle_elem_; \ | |
1024 | half_ = len_ >> 1; \ | |
1025 | middle_ = first_; \ | |
1026 | middle_ += half_; \ | |
1027 | middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \ | |
1028 | if (lessthan_ (middle_elem_, obj_)) \ | |
1029 | { \ | |
1030 | first_ = middle_; \ | |
1031 | ++first_; \ | |
1032 | len_ = len_ - half_ - 1; \ | |
1033 | } \ | |
1034 | else \ | |
1035 | len_ = half_; \ | |
1036 | } \ | |
1037 | return first_; \ | |
1038 | } | |
1039 | ||
1040 | #define DEF_VEC_ALLOC_FUNC_O(T) \ | |
1041 | static inline VEC(T) *VEC_OP (T,alloc) \ | |
1042 | (int alloc_) \ | |
1043 | { \ | |
a4e22a5d PA |
1044 | VEC(T) dummy; \ |
1045 | \ | |
350da6ee DJ |
1046 | /* We must request exact size allocation, hence the negation. */ \ |
1047 | return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \ | |
a4e22a5d | 1048 | vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
1049 | } \ |
1050 | \ | |
1051 | static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ | |
1052 | { \ | |
1053 | size_t len_ = vec_ ? vec_->num : 0; \ | |
1054 | VEC (T) *new_vec_ = NULL; \ | |
1055 | \ | |
1056 | if (len_) \ | |
1057 | { \ | |
a4e22a5d PA |
1058 | VEC(T) dummy; \ |
1059 | \ | |
581e13c1 | 1060 | /* We must request exact size allocation, hence the negation. */ \ |
350da6ee | 1061 | new_vec_ = (VEC (T) *) \ |
a4e22a5d | 1062 | vec_o_reserve (NULL, -len_, vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
1063 | \ |
1064 | new_vec_->num = len_; \ | |
1065 | memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ | |
1066 | } \ | |
1067 | return new_vec_; \ | |
1068 | } \ | |
1069 | \ | |
de0bea00 MF |
1070 | static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ |
1071 | { \ | |
1072 | if (vec1_ && vec2_) \ | |
1073 | { \ | |
a4e22a5d | 1074 | VEC(T) dummy; \ |
de0bea00 MF |
1075 | size_t len_ = vec1_->num + vec2_->num; \ |
1076 | VEC (T) *new_vec_ = NULL; \ | |
1077 | \ | |
1078 | /* We must request exact size allocation, hence the negation. */ \ | |
1079 | new_vec_ = (VEC (T) *) \ | |
a4e22a5d | 1080 | vec_o_reserve (NULL, -len_, vec_offset (T, &dummy), sizeof (T)); \ |
de0bea00 MF |
1081 | \ |
1082 | new_vec_->num = len_; \ | |
1083 | memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ | |
1084 | memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ | |
1085 | sizeof (T) * vec2_->num); \ | |
1086 | \ | |
1087 | return new_vec_; \ | |
1088 | } \ | |
1089 | else \ | |
1090 | return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ | |
1091 | } \ | |
1092 | \ | |
350da6ee DJ |
1093 | static inline void VEC_OP (T,free) \ |
1094 | (VEC(T) **vec_) \ | |
1095 | { \ | |
1096 | if (*vec_) \ | |
1e8877aa | 1097 | vec_free_ (*vec_); \ |
350da6ee DJ |
1098 | *vec_ = NULL; \ |
1099 | } \ | |
1100 | \ | |
3cf03773 TT |
1101 | static inline void VEC_OP (T,cleanup) \ |
1102 | (void *arg_) \ | |
1103 | { \ | |
dd0a637a | 1104 | VEC(T) **vec_ = (VEC(T) **) arg_; \ |
3cf03773 TT |
1105 | if (*vec_) \ |
1106 | vec_free_ (*vec_); \ | |
1107 | *vec_ = NULL; \ | |
1108 | } \ | |
1109 | \ | |
350da6ee DJ |
1110 | static inline int VEC_OP (T,reserve) \ |
1111 | (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ | |
1112 | { \ | |
a4e22a5d | 1113 | VEC(T) dummy; \ |
350da6ee DJ |
1114 | int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \ |
1115 | VEC_ASSERT_PASS); \ | |
1116 | \ | |
1117 | if (extend) \ | |
1118 | *vec_ = (VEC(T) *) \ | |
a4e22a5d | 1119 | vec_o_reserve (*vec_, alloc_, vec_offset (T, &dummy), sizeof (T)); \ |
350da6ee DJ |
1120 | \ |
1121 | return extend; \ | |
1122 | } \ | |
1123 | \ | |
1124 | static inline void VEC_OP (T,safe_grow) \ | |
1125 | (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ | |
1126 | { \ | |
1127 | vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ | |
1128 | "safe_grow"); \ | |
1129 | VEC_OP (T,reserve) \ | |
1130 | (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \ | |
1131 | (*vec_)->num = size_; \ | |
1132 | } \ | |
1133 | \ | |
1134 | static inline T *VEC_OP (T,safe_push) \ | |
1135 | (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \ | |
1136 | { \ | |
1137 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
1138 | \ | |
1139 | return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ | |
1140 | } \ | |
1141 | \ | |
1142 | static inline T *VEC_OP (T,safe_insert) \ | |
1143 | (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ | |
1144 | { \ | |
1145 | VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ | |
1146 | \ | |
1147 | return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ | |
1148 | } | |
1149 | ||
1150 | #endif /* GDB_VEC_H */ |