2 Copyright (C) 2004, 2005, 2006, 2007 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 2 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, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
22 #if !defined (GDB_VEC_H)
26 #include "gdb_string.h"
27 #include "gdb_assert.h"
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.
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.
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.
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.
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.
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.
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.
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.
101 An example of their use would be,
103 DEF_VEC_P(tree); // non-managed tree vector.
106 VEC(tree) *v; // A (pointer to) a vector of tree pointers.
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 }
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. */
125 unsigned VEC_T_length(const VEC(T) *v);
127 Return the number of active elements in V. V can be NULL, in which
128 case zero is returned. */
130 #define VEC_length(T,V) (VEC_OP(T,length)(V))
133 /* Check if vector is empty
134 int VEC_T_empty(const VEC(T) *v);
136 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
138 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
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
146 Return the final element. V must not be empty. */
148 #define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO))
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
155 Return the IX'th element. If IX must be in the domain of V. */
157 #define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO))
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
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,
168 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
171 #define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P)))
173 /* Allocate new vector.
174 VEC(T,A) *VEC_T_alloc(int reserve);
176 Allocate a new vector with space for RESERVE objects. If RESERVE
177 is zero, NO vector is created. */
179 #define VEC_alloc(T,N) (VEC_OP(T,alloc)(N))
182 void VEC_T_free(VEC(T,A) *&);
184 Free a vector and set it to NULL. */
186 #define VEC_free(T,V) (VEC_OP(T,free)(&V))
188 /* Use these to determine the required size and initialization of a
189 vector embedded within another structure (as the final member).
191 size_t VEC_T_embedded_size(int reserve);
192 void VEC_T_embedded_init(VEC(T) *v, int reserve);
194 These allow the caller to perform the memory allocation. */
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))
200 VEC(T,A) *VEC_T_copy(VEC(T) *);
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. */
205 #define VEC_copy(T,V) (VEC_OP(T,copy)(V))
207 /* Determine if a vector has additional capacity.
209 int VEC_T_space (VEC(T) *v,int reserve)
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
217 #define VEC_space(T,V,R) (VEC_OP(T,space)(V,R VEC_ASSERT_INFO))
220 int VEC_T_reserve(VEC(T,A) *&v, int reserve);
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. */
229 #define VEC_reserve(T,V,R) (VEC_OP(T,reserve)(&(V),R VEC_ASSERT_INFO))
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
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. */
241 #define VEC_quick_push(T,V,O) (VEC_OP(T,quick_push)(V,O VEC_ASSERT_INFO))
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
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. */
252 #define VEC_safe_push(T,V,O) (VEC_OP(T,safe_push)(&(V),O VEC_ASSERT_INFO))
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
259 Pop the last element off the end. Returns the element popped, for
262 #define VEC_pop(T,V) (VEC_OP(T,pop)(V VEC_ASSERT_INFO))
264 /* Truncate to specific length
265 void VEC_T_truncate (VEC(T) *v, unsigned len);
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. */
270 #define VEC_truncate(T,V,I) \
271 (VEC_OP(T,truncate)(V,I VEC_ASSERT_INFO))
273 /* Grow to a specific length.
274 void VEC_T_safe_grow (VEC(T,A) *&v, int len);
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
280 #define VEC_safe_grow(T,V,I) \
281 (VEC_OP(T,safe_grow)(&(V),I VEC_ASSERT_INFO))
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
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
294 #define VEC_replace(T,V,I,O) (VEC_OP(T,replace)(V,I,O VEC_ASSERT_INFO))
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
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. */
306 #define VEC_quick_insert(T,V,I,O) \
307 (VEC_OP(T,quick_insert)(V,I,O VEC_ASSERT_INFO))
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
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. */
319 #define VEC_safe_insert(T,V,I,O) \
320 (VEC_OP(T,safe_insert)(&(V),I,O VEC_ASSERT_INFO))
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
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. */
331 #define VEC_ordered_remove(T,V,I) \
332 (VEC_OP(T,ordered_remove)(V,I VEC_ASSERT_INFO))
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
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. */
343 #define VEC_unordered_remove(T,V,I) \
344 (VEC_OP(T,unordered_remove)(V,I VEC_ASSERT_INFO))
346 /* Remove a block of elements
347 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
349 Remove LEN elements starting at the IXth. Ordering is retained.
350 This is an O(1) operation. */
352 #define VEC_block_remove(T,V,I,L) \
353 (VEC_OP(T,block_remove)(V,I,L) VEC_ASSERT_INFO)
355 /* Get the address of the array of elements
356 T *VEC_T_address (VEC(T) v)
358 If you need to directly manipulate the array (for instance, you
359 want to feed it to qsort), use this accessor. */
361 #define VEC_address(T,V) (VEC_OP(T,address)(V))
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
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. */
375 #define VEC_lower_bound(T,V,O,LT) \
376 (VEC_OP(T,lower_bound)(V,O,LT VEC_ASSERT_INFO))
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)
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)))
389 #define VEC(T) VEC_##T
390 #define VEC_OP(T,OP) VEC_##T##_##OP
393 typedef struct VEC(T) \
400 /* Vector of integer-like object. */
401 #define DEF_VEC_I(T) \
402 static inline void VEC_OP (T,must_be_integral_type) (void) \
409 DEF_VEC_ALLOC_FUNC_I(T) \
410 struct vec_swallow_trailing_semi
412 /* Vector of pointer to object. */
413 #define DEF_VEC_P(T) \
414 static inline void VEC_OP (T,must_be_pointer_type) (void) \
416 (void)((T)1 == (void *)1); \
421 DEF_VEC_ALLOC_FUNC_P(T) \
422 struct vec_swallow_trailing_semi
424 /* Vector of object. */
425 #define DEF_VEC_O(T) \
428 DEF_VEC_ALLOC_FUNC_O(T) \
429 struct vec_swallow_trailing_semi
431 #define DEF_VEC_ALLOC_FUNC_I(T) \
432 static inline VEC(T) *VEC_OP (T,alloc) \
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)); \
440 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
442 size_t len_ = vec_ ? vec_->num : 0; \
443 VEC (T) *new_vec_ = NULL; \
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)); \
451 new_vec_->num = len_; \
452 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
457 static inline void VEC_OP (T,free) \
465 static inline int VEC_OP (T,reserve) \
466 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
468 int extend = !VEC_OP (T,space) \
469 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
472 *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \
473 offsetof (VEC(T),vec), sizeof (T)); \
478 static inline void VEC_OP (T,safe_grow) \
479 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
481 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
483 VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \
485 (*vec_)->num = size_; \
488 static inline T *VEC_OP (T,safe_push) \
489 (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \
491 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
493 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
496 static inline T *VEC_OP (T,safe_insert) \
497 (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \
499 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
501 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
504 #define DEF_VEC_FUNC_P(T) \
505 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
507 return vec_ ? vec_->num : 0; \
510 static inline T VEC_OP (T,last) \
511 (const VEC(T) *vec_ VEC_ASSERT_DECL) \
513 vec_assert (vec_ && vec_->num, "last"); \
515 return vec_->vec[vec_->num - 1]; \
518 static inline T VEC_OP (T,index) \
519 (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
521 vec_assert (vec_ && ix_ < vec_->num, "index"); \
523 return vec_->vec[ix_]; \
526 static inline int VEC_OP (T,iterate) \
527 (const VEC(T) *vec_, unsigned ix_, T *ptr) \
529 if (vec_ && ix_ < vec_->num) \
531 *ptr = vec_->vec[ix_]; \
541 static inline size_t VEC_OP (T,embedded_size) \
544 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
547 static inline void VEC_OP (T,embedded_init) \
548 (VEC(T) *vec_, int alloc_) \
551 vec_->alloc = alloc_; \
554 static inline int VEC_OP (T,space) \
555 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
557 vec_assert (alloc_ >= 0, "space"); \
558 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
561 static inline T *VEC_OP (T,quick_push) \
562 (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \
566 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
567 slot_ = &vec_->vec[vec_->num++]; \
573 static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
577 vec_assert (vec_->num, "pop"); \
578 obj_ = vec_->vec[--vec_->num]; \
583 static inline void VEC_OP (T,truncate) \
584 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
586 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
591 static inline T VEC_OP (T,replace) \
592 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
596 vec_assert (ix_ < vec_->num, "replace"); \
597 old_obj_ = vec_->vec[ix_]; \
598 vec_->vec[ix_] = obj_; \
603 static inline T *VEC_OP (T,quick_insert) \
604 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
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)); \
616 static inline T VEC_OP (T,ordered_remove) \
617 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
622 vec_assert (ix_ < vec_->num, "ordered_remove"); \
623 slot_ = &vec_->vec[ix_]; \
625 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
630 static inline T VEC_OP (T,unordered_remove) \
631 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
636 vec_assert (ix_ < vec_->num, "unordered_remove"); \
637 slot_ = &vec_->vec[ix_]; \
639 *slot_ = vec_->vec[--vec_->num]; \
644 static inline void VEC_OP (T,block_remove) \
645 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
649 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
650 slot_ = &vec_->vec[ix_]; \
652 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
655 static inline T *VEC_OP (T,address) \
658 return vec_ ? vec_->vec : 0; \
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) \
665 unsigned int len_ = VEC_OP (T, length) (vec_); \
666 unsigned int half_, middle_; \
667 unsigned int first_ = 0; \
674 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
675 if (lessthan_ (middle_elem_, obj_)) \
679 len_ = len_ - half_ - 1; \
687 #define DEF_VEC_ALLOC_FUNC_P(T) \
688 static inline VEC(T) *VEC_OP (T,alloc) \
691 /* We must request exact size allocation, hence the negation. */ \
692 return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \
695 static inline void VEC_OP (T,free) \
703 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
705 size_t len_ = vec_ ? vec_->num : 0; \
706 VEC (T) *new_vec_ = NULL; \
710 /* We must request exact size allocation, hence the negation. */ \
711 new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \
713 new_vec_->num = len_; \
714 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
719 static inline int VEC_OP (T,reserve) \
720 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
722 int extend = !VEC_OP (T,space) \
723 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
726 *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \
731 static inline void VEC_OP (T,safe_grow) \
732 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
734 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
737 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
738 (*vec_)->num = size_; \
741 static inline T *VEC_OP (T,safe_push) \
742 (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \
744 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
746 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
749 static inline T *VEC_OP (T,safe_insert) \
750 (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
752 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
754 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
757 #define DEF_VEC_FUNC_O(T) \
758 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
760 return vec_ ? vec_->num : 0; \
763 static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \
765 vec_assert (vec_ && vec_->num, "last"); \
767 return &vec_->vec[vec_->num - 1]; \
770 static inline T *VEC_OP (T,index) \
771 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
773 vec_assert (vec_ && ix_ < vec_->num, "index"); \
775 return &vec_->vec[ix_]; \
778 static inline int VEC_OP (T,iterate) \
779 (VEC(T) *vec_, unsigned ix_, T **ptr) \
781 if (vec_ && ix_ < vec_->num) \
783 *ptr = &vec_->vec[ix_]; \
793 static inline size_t VEC_OP (T,embedded_size) \
796 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
799 static inline void VEC_OP (T,embedded_init) \
800 (VEC(T) *vec_, int alloc_) \
803 vec_->alloc = alloc_; \
806 static inline int VEC_OP (T,space) \
807 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
809 vec_assert (alloc_ >= 0, "space"); \
810 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
813 static inline T *VEC_OP (T,quick_push) \
814 (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \
818 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
819 slot_ = &vec_->vec[vec_->num++]; \
826 static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
828 vec_assert (vec_->num, "pop"); \
832 static inline void VEC_OP (T,truncate) \
833 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
835 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
840 static inline T *VEC_OP (T,replace) \
841 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
845 vec_assert (ix_ < vec_->num, "replace"); \
846 slot_ = &vec_->vec[ix_]; \
853 static inline T *VEC_OP (T,quick_insert) \
854 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
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)); \
867 static inline void VEC_OP (T,ordered_remove) \
868 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
872 vec_assert (ix_ < vec_->num, "ordered_remove"); \
873 slot_ = &vec_->vec[ix_]; \
874 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
877 static inline void VEC_OP (T,unordered_remove) \
878 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
880 vec_assert (ix_ < vec_->num, "unordered_remove"); \
881 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
884 static inline void VEC_OP (T,block_remove) \
885 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
889 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
890 slot_ = &vec_->vec[ix_]; \
892 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
895 static inline T *VEC_OP (T,address) \
898 return vec_ ? vec_->vec : 0; \
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) \
905 unsigned int len_ = VEC_OP (T, length) (vec_); \
906 unsigned int half_, middle_; \
907 unsigned int first_ = 0; \
914 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
915 if (lessthan_ (middle_elem_, obj_)) \
919 len_ = len_ - half_ - 1; \
927 #define DEF_VEC_ALLOC_FUNC_O(T) \
928 static inline VEC(T) *VEC_OP (T,alloc) \
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)); \
936 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
938 size_t len_ = vec_ ? vec_->num : 0; \
939 VEC (T) *new_vec_ = NULL; \
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)); \
947 new_vec_->num = len_; \
948 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
953 static inline void VEC_OP (T,free) \
961 static inline int VEC_OP (T,reserve) \
962 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
964 int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \
969 vec_o_reserve (*vec_, alloc_, offsetof (VEC(T),vec), sizeof (T)); \
974 static inline void VEC_OP (T,safe_grow) \
975 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
977 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
980 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
981 (*vec_)->num = size_; \
984 static inline T *VEC_OP (T,safe_push) \
985 (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \
987 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
989 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
992 static inline T *VEC_OP (T,safe_insert) \
993 (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
995 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
997 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
1000 #endif /* GDB_VEC_H */
This page took 0.048811 seconds and 4 git commands to generate.