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