2 Copyright (C) 2004-2012 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
5 This file is part of GDB.
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.
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.
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/>. */
20 #if !defined (GDB_VEC_H)
26 #include "gdb_string.h"
27 #include "gdb_assert.h"
30 /* The macros here implement a set of templated vector types and
31 associated interfaces. These templates are implemented with
32 macros, as we're not in C++ land. The interface functions are
33 typesafe and use static inline functions, sometimes backed by
34 out-of-line generic functions.
36 Because of the different behavior of structure objects, scalar
37 objects and of pointers, there are three flavors, one for each of
38 these variants. Both the structure object and pointer variants
39 pass pointers to objects around -- in the former case the pointers
40 are stored into the vector and in the latter case the pointers are
41 dereferenced and the objects copied into the vector. The scalar
42 object variant is suitable for int-like objects, and the vector
43 elements are returned by value.
45 There are both 'index' and 'iterate' accessors. The iterator
46 returns a boolean iteration condition and updates the iteration
47 variable passed by reference. Because the iterator will be
48 inlined, the address-of can be optimized away.
50 The vectors are implemented using the trailing array idiom, thus
51 they are not resizeable without changing the address of the vector
52 object itself. This means you cannot have variables or fields of
53 vector type -- always use a pointer to a vector. The one exception
54 is the final field of a structure, which could be a vector type.
55 You will have to use the embedded_size & embedded_init calls to
56 create such objects, and they will probably not be resizeable (so
57 don't use the 'safe' allocation variants). The trailing array
58 idiom is used (rather than a pointer to an array of data), because,
59 if we allow NULL to also represent an empty vector, empty vectors
60 occupy minimal space in the structure containing them.
62 Each operation that increases the number of active elements is
63 available in 'quick' and 'safe' variants. The former presumes that
64 there is sufficient allocated space for the operation to succeed
65 (it dies if there is not). The latter will reallocate the
66 vector, if needed. Reallocation causes an exponential increase in
67 vector size. If you know you will be adding N elements, it would
68 be more efficient to use the reserve operation before adding the
69 elements with the 'quick' operation. This will ensure there are at
70 least as many elements as you ask for, it will exponentially
71 increase if there are too few spare slots. If you want reserve a
72 specific number of slots, but do not want the exponential increase
73 (for instance, you know this is the last allocation), use a
74 negative number for reservation. You can also create a vector of a
75 specific size from the get go.
77 You should prefer the push and pop operations, as they append and
78 remove from the end of the vector. If you need to remove several
79 items in one go, use the truncate operation. The insert and remove
80 operations allow you to change elements in the middle of the
81 vector. There are two remove operations, one which preserves the
82 element ordering 'ordered_remove', and one which does not
83 'unordered_remove'. The latter function copies the end element
84 into the removed slot, rather than invoke a memmove operation. The
85 'lower_bound' function will determine where to place an item in the
86 array using insert that will maintain sorted order.
88 If you need to directly manipulate a vector, then the 'address'
89 accessor will return the address of the start of the vector. Also
90 the 'space' predicate will tell you whether there is spare capacity
91 in the vector. You will not normally need to use these two functions.
93 Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro.
94 Variables of vector type are declared using a VEC(TYPEDEF) macro.
95 The characters O, P and I indicate whether TYPEDEF is a pointer
96 (P), object (O) or integral (I) type. Be careful to pick the
97 correct one, as you'll get an awkward and inefficient API if you
98 use the wrong one. There is a check, which results in a
99 compile-time warning, for the P and I versions, but there is no
100 check for the O versions, as that is not possible in plain C.
102 An example of their use would be,
104 DEF_VEC_P(tree); // non-managed tree vector.
107 VEC(tree) *v; // A (pointer to) a vector of tree pointers.
112 if (VEC_length(tree, s->v)) { we have some contents }
113 VEC_safe_push(tree, s->v, decl); // append some decl onto the end
114 for (ix = 0; VEC_iterate(tree, s->v, ix, elt); ix++)
115 { do something with elt }
119 /* Macros to invoke API calls. A single macro works for both pointer
120 and object vectors, but the argument and return types might well be
121 different. In each macro, T is the typedef of the vector elements.
122 Some of these macros pass the vector, V, by reference (by taking
123 its address), this is noted in the descriptions. */
126 unsigned VEC_T_length(const VEC(T) *v);
128 Return the number of active elements in V. V can be NULL, in which
129 case zero is returned. */
131 #define VEC_length(T,V) (VEC_OP(T,length)(V))
134 /* Check if vector is empty
135 int VEC_T_empty(const VEC(T) *v);
137 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
139 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
142 /* Get the final element of the vector.
143 T VEC_T_last(VEC(T) *v); // Integer
144 T VEC_T_last(VEC(T) *v); // Pointer
145 T *VEC_T_last(VEC(T) *v); // Object
147 Return the final element. V must not be empty. */
149 #define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO))
152 T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
153 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
154 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
156 Return the IX'th element. If IX must be in the domain of V. */
158 #define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO))
160 /* Iterate over vector
161 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
162 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
163 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
165 Return iteration condition and update PTR to point to the IX'th
166 element. At the end of iteration, sets PTR to NULL. Use this to
167 iterate over the elements of a vector as follows,
169 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
172 #define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P)))
174 /* Allocate new vector.
175 VEC(T,A) *VEC_T_alloc(int reserve);
177 Allocate a new vector with space for RESERVE objects. If RESERVE
178 is zero, NO vector is created. */
180 #define VEC_alloc(T,N) (VEC_OP(T,alloc)(N))
183 void VEC_T_free(VEC(T,A) *&);
185 Free a vector and set it to NULL. */
187 #define VEC_free(T,V) (VEC_OP(T,free)(&V))
189 /* A cleanup function for a vector.
190 void VEC_T_cleanup(void *);
192 Clean up a vector. */
194 #define VEC_cleanup(T) (VEC_OP(T,cleanup))
196 /* Use these to determine the required size and initialization of a
197 vector embedded within another structure (as the final member).
199 size_t VEC_T_embedded_size(int reserve);
200 void VEC_T_embedded_init(VEC(T) *v, int reserve);
202 These allow the caller to perform the memory allocation. */
204 #define VEC_embedded_size(T,N) (VEC_OP(T,embedded_size)(N))
205 #define VEC_embedded_init(T,O,N) (VEC_OP(T,embedded_init)(VEC_BASE(O),N))
208 VEC(T,A) *VEC_T_copy(VEC(T) *);
210 Copy the live elements of a vector into a new vector. The new and
211 old vectors need not be allocated by the same mechanism. */
213 #define VEC_copy(T,V) (VEC_OP(T,copy)(V))
215 /* Determine if a vector has additional capacity.
217 int VEC_T_space (VEC(T) *v,int reserve)
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
225 #define VEC_space(T,V,R) (VEC_OP(T,space)(V,R VEC_ASSERT_INFO))
228 int VEC_T_reserve(VEC(T,A) *&v, int reserve);
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. */
237 #define VEC_reserve(T,V,R) (VEC_OP(T,reserve)(&(V),R VEC_ASSERT_INFO))
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
244 Push a new element onto the end, returns a pointer to the slot
245 filled in. For object vectors, the new value can be NULL, in which
246 case NO initialization is performed. There must
247 be sufficient space in the vector. */
249 #define VEC_quick_push(T,V,O) (VEC_OP(T,quick_push)(V,O VEC_ASSERT_INFO))
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
256 Push a new element onto the end, returns a pointer to the slot
257 filled in. For object vectors, the new value can be NULL, in which
258 case NO initialization is performed. Reallocates V, if needed. */
260 #define VEC_safe_push(T,V,O) (VEC_OP(T,safe_push)(&(V),O VEC_ASSERT_INFO))
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
267 Pop the last element off the end. Returns the element popped, for
270 #define VEC_pop(T,V) (VEC_OP(T,pop)(V VEC_ASSERT_INFO))
272 /* Truncate to specific length
273 void VEC_T_truncate (VEC(T) *v, unsigned len);
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. */
278 #define VEC_truncate(T,V,I) \
279 (VEC_OP(T,truncate)(V,I VEC_ASSERT_INFO))
281 /* Grow to a specific length.
282 void VEC_T_safe_grow (VEC(T,A) *&v, int len);
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
288 #define VEC_safe_grow(T,V,I) \
289 (VEC_OP(T,safe_grow)(&(V),I VEC_ASSERT_INFO))
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
296 Replace the IXth element of V with a new value, VAL. For pointer
297 vectors returns the original value. For object vectors returns a
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
302 #define VEC_replace(T,V,I,O) (VEC_OP(T,replace)(V,I,O VEC_ASSERT_INFO))
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
309 Insert an element, VAL, at the IXth position of V. Return a pointer
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
312 place. There must be sufficient space. */
314 #define VEC_quick_insert(T,V,I,O) \
315 (VEC_OP(T,quick_insert)(V,I,O VEC_ASSERT_INFO))
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
322 Insert an element, VAL, at the IXth position of V. Return a pointer
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
325 place. Reallocate V, if necessary. */
327 #define VEC_safe_insert(T,V,I,O) \
328 (VEC_OP(T,safe_insert)(&(V),I,O VEC_ASSERT_INFO))
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
335 Remove an element from the IXth position of V. Ordering of
336 remaining elements is preserved. For pointer vectors returns the
337 removed object. This is an O(N) operation due to a memmove. */
339 #define VEC_ordered_remove(T,V,I) \
340 (VEC_OP(T,ordered_remove)(V,I VEC_ASSERT_INFO))
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
347 Remove an element from the IXth position of V. Ordering of
348 remaining elements is destroyed. For pointer vectors returns the
349 removed object. This is an O(1) operation. */
351 #define VEC_unordered_remove(T,V,I) \
352 (VEC_OP(T,unordered_remove)(V,I VEC_ASSERT_INFO))
354 /* Remove a block of elements
355 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
357 Remove LEN elements starting at the IXth. Ordering is retained.
358 This is an O(N) operation due to memmove. */
360 #define VEC_block_remove(T,V,I,L) \
361 (VEC_OP(T,block_remove)(V,I,L VEC_ASSERT_INFO))
363 /* Get the address of the array of elements
364 T *VEC_T_address (VEC(T) v)
366 If you need to directly manipulate the array (for instance, you
367 want to feed it to qsort), use this accessor. */
369 #define VEC_address(T,V) (VEC_OP(T,address)(V))
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
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. */
383 #define VEC_lower_bound(T,V,O,LT) \
384 (VEC_OP(T,lower_bound)(V,O,LT VEC_ASSERT_INFO))
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);
389 #define vec_free_(V) xfree (V)
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) \
395 ((void)((expr) ? 0 : (gdb_assert_fail (op, file_, line_, \
396 ASSERT_FUNCTION), 0)))
398 #define VEC(T) VEC_##T
399 #define VEC_OP(T,OP) VEC_##T##_##OP
402 typedef struct VEC(T) \
409 /* Vector of integer-like object. */
410 #define DEF_VEC_I(T) \
411 static inline void VEC_OP (T,must_be_integral_type) (void) \
418 DEF_VEC_ALLOC_FUNC_I(T) \
419 struct vec_swallow_trailing_semi
421 /* Vector of pointer to object. */
422 #define DEF_VEC_P(T) \
423 static inline void VEC_OP (T,must_be_pointer_type) (void) \
425 (void)((T)1 == (void *)1); \
430 DEF_VEC_ALLOC_FUNC_P(T) \
431 struct vec_swallow_trailing_semi
433 /* Vector of object. */
434 #define DEF_VEC_O(T) \
437 DEF_VEC_ALLOC_FUNC_O(T) \
438 struct vec_swallow_trailing_semi
440 #define DEF_VEC_ALLOC_FUNC_I(T) \
441 static inline VEC(T) *VEC_OP (T,alloc) \
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)); \
449 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
451 size_t len_ = vec_ ? vec_->num : 0; \
452 VEC (T) *new_vec_ = NULL; \
456 /* We must request exact size allocation, hence the negation. */ \
457 new_vec_ = (VEC (T) *) \
458 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
460 new_vec_->num = len_; \
461 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
466 static inline void VEC_OP (T,free) \
474 static inline void VEC_OP (T,cleanup) \
477 VEC(T) **vec_ = arg_; \
483 static inline int VEC_OP (T,reserve) \
484 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
486 int extend = !VEC_OP (T,space) \
487 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
490 *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \
491 offsetof (VEC(T),vec), sizeof (T)); \
496 static inline void VEC_OP (T,safe_grow) \
497 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
499 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
501 VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \
503 (*vec_)->num = size_; \
506 static inline T *VEC_OP (T,safe_push) \
507 (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \
509 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
511 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
514 static inline T *VEC_OP (T,safe_insert) \
515 (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \
517 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
519 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
522 #define DEF_VEC_FUNC_P(T) \
523 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
525 return vec_ ? vec_->num : 0; \
528 static inline T VEC_OP (T,last) \
529 (const VEC(T) *vec_ VEC_ASSERT_DECL) \
531 vec_assert (vec_ && vec_->num, "last"); \
533 return vec_->vec[vec_->num - 1]; \
536 static inline T VEC_OP (T,index) \
537 (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
539 vec_assert (vec_ && ix_ < vec_->num, "index"); \
541 return vec_->vec[ix_]; \
544 static inline int VEC_OP (T,iterate) \
545 (const VEC(T) *vec_, unsigned ix_, T *ptr) \
547 if (vec_ && ix_ < vec_->num) \
549 *ptr = vec_->vec[ix_]; \
559 static inline size_t VEC_OP (T,embedded_size) \
562 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
565 static inline void VEC_OP (T,embedded_init) \
566 (VEC(T) *vec_, int alloc_) \
569 vec_->alloc = alloc_; \
572 static inline int VEC_OP (T,space) \
573 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
575 vec_assert (alloc_ >= 0, "space"); \
576 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
579 static inline T *VEC_OP (T,quick_push) \
580 (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \
584 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
585 slot_ = &vec_->vec[vec_->num++]; \
591 static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
595 vec_assert (vec_->num, "pop"); \
596 obj_ = vec_->vec[--vec_->num]; \
601 static inline void VEC_OP (T,truncate) \
602 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
604 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
609 static inline T VEC_OP (T,replace) \
610 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
614 vec_assert (ix_ < vec_->num, "replace"); \
615 old_obj_ = vec_->vec[ix_]; \
616 vec_->vec[ix_] = obj_; \
621 static inline T *VEC_OP (T,quick_insert) \
622 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
626 vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \
627 slot_ = &vec_->vec[ix_]; \
628 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
634 static inline T VEC_OP (T,ordered_remove) \
635 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
640 vec_assert (ix_ < vec_->num, "ordered_remove"); \
641 slot_ = &vec_->vec[ix_]; \
643 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
648 static inline T VEC_OP (T,unordered_remove) \
649 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
654 vec_assert (ix_ < vec_->num, "unordered_remove"); \
655 slot_ = &vec_->vec[ix_]; \
657 *slot_ = vec_->vec[--vec_->num]; \
662 static inline void VEC_OP (T,block_remove) \
663 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
667 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
668 slot_ = &vec_->vec[ix_]; \
670 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
673 static inline T *VEC_OP (T,address) \
676 return vec_ ? vec_->vec : 0; \
679 static inline unsigned VEC_OP (T,lower_bound) \
680 (VEC(T) *vec_, const T obj_, \
681 int (*lessthan_)(const T, const T) VEC_ASSERT_DECL) \
683 unsigned int len_ = VEC_OP (T, length) (vec_); \
684 unsigned int half_, middle_; \
685 unsigned int first_ = 0; \
692 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
693 if (lessthan_ (middle_elem_, obj_)) \
697 len_ = len_ - half_ - 1; \
705 #define DEF_VEC_ALLOC_FUNC_P(T) \
706 static inline VEC(T) *VEC_OP (T,alloc) \
709 /* We must request exact size allocation, hence the negation. */ \
710 return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \
713 static inline void VEC_OP (T,free) \
721 static inline void VEC_OP (T,cleanup) \
724 VEC(T) **vec_ = arg_; \
730 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
732 size_t len_ = vec_ ? vec_->num : 0; \
733 VEC (T) *new_vec_ = NULL; \
737 /* We must request exact size allocation, hence the negation. */ \
738 new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \
740 new_vec_->num = len_; \
741 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
746 static inline int VEC_OP (T,reserve) \
747 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
749 int extend = !VEC_OP (T,space) \
750 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
753 *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \
758 static inline void VEC_OP (T,safe_grow) \
759 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
761 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
764 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
765 (*vec_)->num = size_; \
768 static inline T *VEC_OP (T,safe_push) \
769 (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \
771 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
773 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
776 static inline T *VEC_OP (T,safe_insert) \
777 (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
779 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
781 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
784 #define DEF_VEC_FUNC_O(T) \
785 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
787 return vec_ ? vec_->num : 0; \
790 static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \
792 vec_assert (vec_ && vec_->num, "last"); \
794 return &vec_->vec[vec_->num - 1]; \
797 static inline T *VEC_OP (T,index) \
798 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
800 vec_assert (vec_ && ix_ < vec_->num, "index"); \
802 return &vec_->vec[ix_]; \
805 static inline int VEC_OP (T,iterate) \
806 (VEC(T) *vec_, unsigned ix_, T **ptr) \
808 if (vec_ && ix_ < vec_->num) \
810 *ptr = &vec_->vec[ix_]; \
820 static inline size_t VEC_OP (T,embedded_size) \
823 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
826 static inline void VEC_OP (T,embedded_init) \
827 (VEC(T) *vec_, int alloc_) \
830 vec_->alloc = alloc_; \
833 static inline int VEC_OP (T,space) \
834 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
836 vec_assert (alloc_ >= 0, "space"); \
837 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
840 static inline T *VEC_OP (T,quick_push) \
841 (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \
845 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
846 slot_ = &vec_->vec[vec_->num++]; \
853 static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
855 vec_assert (vec_->num, "pop"); \
859 static inline void VEC_OP (T,truncate) \
860 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
862 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
867 static inline T *VEC_OP (T,replace) \
868 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
872 vec_assert (ix_ < vec_->num, "replace"); \
873 slot_ = &vec_->vec[ix_]; \
880 static inline T *VEC_OP (T,quick_insert) \
881 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
885 vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \
886 slot_ = &vec_->vec[ix_]; \
887 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
894 static inline void VEC_OP (T,ordered_remove) \
895 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
899 vec_assert (ix_ < vec_->num, "ordered_remove"); \
900 slot_ = &vec_->vec[ix_]; \
901 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
904 static inline void VEC_OP (T,unordered_remove) \
905 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
907 vec_assert (ix_ < vec_->num, "unordered_remove"); \
908 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
911 static inline void VEC_OP (T,block_remove) \
912 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
916 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
917 slot_ = &vec_->vec[ix_]; \
919 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
922 static inline T *VEC_OP (T,address) \
925 return vec_ ? vec_->vec : 0; \
928 static inline unsigned VEC_OP (T,lower_bound) \
929 (VEC(T) *vec_, const T *obj_, \
930 int (*lessthan_)(const T *, const T *) VEC_ASSERT_DECL) \
932 unsigned int len_ = VEC_OP (T, length) (vec_); \
933 unsigned int half_, middle_; \
934 unsigned int first_ = 0; \
941 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
942 if (lessthan_ (middle_elem_, obj_)) \
946 len_ = len_ - half_ - 1; \
954 #define DEF_VEC_ALLOC_FUNC_O(T) \
955 static inline VEC(T) *VEC_OP (T,alloc) \
958 /* We must request exact size allocation, hence the negation. */ \
959 return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \
960 offsetof (VEC(T),vec), sizeof (T)); \
963 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
965 size_t len_ = vec_ ? vec_->num : 0; \
966 VEC (T) *new_vec_ = NULL; \
970 /* We must request exact size allocation, hence the negation. */ \
971 new_vec_ = (VEC (T) *) \
972 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
974 new_vec_->num = len_; \
975 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
980 static inline void VEC_OP (T,free) \
988 static inline void VEC_OP (T,cleanup) \
991 VEC(T) **vec_ = arg_; \
997 static inline int VEC_OP (T,reserve) \
998 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
1000 int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \
1004 *vec_ = (VEC(T) *) \
1005 vec_o_reserve (*vec_, alloc_, offsetof (VEC(T),vec), sizeof (T)); \
1010 static inline void VEC_OP (T,safe_grow) \
1011 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
1013 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
1015 VEC_OP (T,reserve) \
1016 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
1017 (*vec_)->num = size_; \
1020 static inline T *VEC_OP (T,safe_push) \
1021 (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \
1023 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1025 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
1028 static inline T *VEC_OP (T,safe_insert) \
1029 (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
1031 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1033 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
1036 #endif /* GDB_VEC_H */
This page took 0.05036 seconds and 4 git commands to generate.