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