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