projects / deliverable / binutils-gdb.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
gdb:
[deliverable/binutils-gdb.git] / gdb / common / vec.h
CommitLineData
350da6ee 1/* Vector API for GDB.
c5a57081 2 Copyright (C) 2004-2012 Free Software Foundation, Inc.
350da6ee
DJ		 3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4
5 This file is part of GDB.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
a9762ec7 9 the Free Software Foundation; either version 3 of the License, or
350da6ee
DJ		 10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
a9762ec7 18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
350da6ee
DJ		 19
20#if !defined (GDB_VEC_H)
21#define GDB_VEC_H
22
23#include <stddef.h>
aad9eab9
YQ		 24
25#ifndef GDBSERVER
350da6ee
DJ		 26#include "gdb_string.h"
27#include "gdb_assert.h"
aad9eab9 28#endif
350da6ee
DJ		 29
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.
35
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.
44
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.
49
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.
61
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.
76
77 You should prefer the push and pop operations, as they append and
581e13c1 78 remove from the end of the vector. If you need to remove several
350da6ee
DJ		 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.
87
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.
92
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.
101
102 An example of their use would be,
103
104 DEF_VEC_P(tree); // non-managed tree vector.
105
106 struct my_struct {
107 VEC(tree) *v; // A (pointer to) a vector of tree pointers.
108 };
109
110 struct my_struct *s;
111
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 }
116
117*/
118
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. */
124
125/* Length of vector
126 unsigned VEC_T_length(const VEC(T) *v);
127
128 Return the number of active elements in V. V can be NULL, in which
129 case zero is returned. */
130
131#define VEC_length(T,V) (VEC_OP(T,length)(V))
132
133
134/* Check if vector is empty
135 int VEC_T_empty(const VEC(T) *v);
136
137 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
138
139#define VEC_empty(T,V) (VEC_length (T,V) == 0)
140
141
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
146
147 Return the final element. V must not be empty. */
148
149#define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO))
150
151/* Index into vector
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
155
156 Return the IX'th element. If IX must be in the domain of V. */
157
158#define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO))
159
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
164
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,
168
169 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
170 continue; */
171
172#define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P)))
173
174/* Allocate new vector.
175 VEC(T,A) *VEC_T_alloc(int reserve);
176
177 Allocate a new vector with space for RESERVE objects. If RESERVE
178 is zero, NO vector is created. */
179
180#define VEC_alloc(T,N) (VEC_OP(T,alloc)(N))
181
182/* Free a vector.
183 void VEC_T_free(VEC(T,A) *&);
184
185 Free a vector and set it to NULL. */
186
187#define VEC_free(T,V) (VEC_OP(T,free)(&V))
188
3cf03773
TT		 189/* A cleanup function for a vector.
190 void VEC_T_cleanup(void *);
191
192 Clean up a vector. */
193
194#define VEC_cleanup(T) (VEC_OP(T,cleanup))
195
350da6ee
DJ		 196/* Use these to determine the required size and initialization of a
197 vector embedded within another structure (as the final member).
198
199 size_t VEC_T_embedded_size(int reserve);
200 void VEC_T_embedded_init(VEC(T) *v, int reserve);
201
202 These allow the caller to perform the memory allocation. */
203
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))
206
207/* Copy a vector.
208 VEC(T,A) *VEC_T_copy(VEC(T) *);
209
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. */
212
213#define VEC_copy(T,V) (VEC_OP(T,copy)(V))
214
215/* Determine if a vector has additional capacity.
216
217 int VEC_T_space (VEC(T) *v,int reserve)
218
219 If V has space for RESERVE additional entries, return nonzero. You
220 usually only need to use this if you are doing your own vector
221 reallocation, for instance on an embedded vector. This returns
222 nonzero in exactly the same circumstances that VEC_T_reserve
223 will. */
224
225#define VEC_space(T,V,R) (VEC_OP(T,space)(V,R VEC_ASSERT_INFO))
226
227/* Reserve space.
228 int VEC_T_reserve(VEC(T,A) *&v, int reserve);
229
230 Ensure that V has at least abs(RESERVE) slots available. The
231 signedness of RESERVE determines the reallocation behavior. A
232 negative value will not create additional headroom beyond that
233 requested. A positive value will create additional headroom. Note
234 this can cause V to be reallocated. Returns nonzero iff
235 reallocation actually occurred. */
236
237#define VEC_reserve(T,V,R) (VEC_OP(T,reserve)(&(V),R VEC_ASSERT_INFO))
238
239/* Push object with no reallocation
240 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
241 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
242 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
243
244 Push a new element onto the end, returns a pointer to the slot
581e13c1 245 filled in. For object vectors, the new value can be NULL, in which
350da6ee
DJ		 246 case NO initialization is performed. There must
247 be sufficient space in the vector. */
248
249#define VEC_quick_push(T,V,O) (VEC_OP(T,quick_push)(V,O VEC_ASSERT_INFO))
250
251/* Push object with reallocation
252 T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Integer
253 T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Pointer
254 T *VEC_T_safe_push (VEC(T,A) *&v, T *obj); // Object
255
256 Push a new element onto the end, returns a pointer to the slot
581e13c1 257 filled in. For object vectors, the new value can be NULL, in which
350da6ee
DJ		 258 case NO initialization is performed. Reallocates V, if needed. */
259
260#define VEC_safe_push(T,V,O) (VEC_OP(T,safe_push)(&(V),O VEC_ASSERT_INFO))
261
262/* Pop element off end
263 T VEC_T_pop (VEC(T) *v); // Integer
264 T VEC_T_pop (VEC(T) *v); // Pointer
265 void VEC_T_pop (VEC(T) *v); // Object
266
581e13c1 267 Pop the last element off the end. Returns the element popped, for
350da6ee
DJ		 268 pointer vectors. */
269
270#define VEC_pop(T,V) (VEC_OP(T,pop)(V VEC_ASSERT_INFO))
271
272/* Truncate to specific length
273 void VEC_T_truncate (VEC(T) *v, unsigned len);
274
275 Set the length as specified. The new length must be less than or
276 equal to the current length. This is an O(1) operation. */
277
278#define VEC_truncate(T,V,I) \
279 (VEC_OP(T,truncate)(V,I VEC_ASSERT_INFO))
280
281/* Grow to a specific length.
282 void VEC_T_safe_grow (VEC(T,A) *&v, int len);
283
284 Grow the vector to a specific length. The LEN must be as
285 long or longer than the current length. The new elements are
286 uninitialized. */
287
288#define VEC_safe_grow(T,V,I) \
289 (VEC_OP(T,safe_grow)(&(V),I VEC_ASSERT_INFO))
290
291/* Replace element
292 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
293 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
294 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
295
296 Replace the IXth element of V with a new value, VAL. For pointer
581e13c1 297 vectors returns the original value. For object vectors returns a
350da6ee
DJ		 298 pointer to the new value. For object vectors the new value can be
299 NULL, in which case no overwriting of the slot is actually
300 performed. */
301
302#define VEC_replace(T,V,I,O) (VEC_OP(T,replace)(V,I,O VEC_ASSERT_INFO))
303
304/* Insert object with no reallocation
305 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
306 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
307 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
308
581e13c1 309 Insert an element, VAL, at the IXth position of V. Return a pointer
350da6ee
DJ		 310 to the slot created. For vectors of object, the new value can be
311 NULL, in which case no initialization of the inserted slot takes
581e13c1 312 place. There must be sufficient space. */
350da6ee
DJ		 313
314#define VEC_quick_insert(T,V,I,O) \
315 (VEC_OP(T,quick_insert)(V,I,O VEC_ASSERT_INFO))
316
317/* Insert object with reallocation
318 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
319 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
320 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
321
581e13c1 322 Insert an element, VAL, at the IXth position of V. Return a pointer
350da6ee
DJ		 323 to the slot created. For vectors of object, the new value can be
324 NULL, in which case no initialization of the inserted slot takes
581e13c1 325 place. Reallocate V, if necessary. */
350da6ee
DJ		 326
327#define VEC_safe_insert(T,V,I,O) \
328 (VEC_OP(T,safe_insert)(&(V),I,O VEC_ASSERT_INFO))
329
330/* Remove element retaining order
331 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
332 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
333 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
334
581e13c1 335 Remove an element from the IXth position of V. Ordering of
350da6ee
DJ		 336 remaining elements is preserved. For pointer vectors returns the
337 removed object. This is an O(N) operation due to a memmove. */
338
339#define VEC_ordered_remove(T,V,I) \
340 (VEC_OP(T,ordered_remove)(V,I VEC_ASSERT_INFO))
341
342/* Remove element destroying order
343 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
344 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
345 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
346
581e13c1 347 Remove an element from the IXth position of V. Ordering of
350da6ee
DJ		 348 remaining elements is destroyed. For pointer vectors returns the
349 removed object. This is an O(1) operation. */
350
351#define VEC_unordered_remove(T,V,I) \
352 (VEC_OP(T,unordered_remove)(V,I VEC_ASSERT_INFO))
353
354/* Remove a block of elements
355 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
356
357 Remove LEN elements starting at the IXth. Ordering is retained.
2287cc7e 358 This is an O(N) operation due to memmove. */
350da6ee
DJ		 359
360#define VEC_block_remove(T,V,I,L) \
2287cc7e 361 (VEC_OP(T,block_remove)(V,I,L VEC_ASSERT_INFO))
350da6ee
DJ		 362
363/* Get the address of the array of elements
364 T *VEC_T_address (VEC(T) v)
365
366 If you need to directly manipulate the array (for instance, you
367 want to feed it to qsort), use this accessor. */
368
369#define VEC_address(T,V) (VEC_OP(T,address)(V))
370
371/* Find the first index in the vector not less than the object.
372 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
373 int (*lessthan) (const T, const T)); // Integer
374 unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
375 int (*lessthan) (const T, const T)); // Pointer
376 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
377 int (*lessthan) (const T*, const T*)); // Object
378
379 Find the first position in which VAL could be inserted without
380 changing the ordering of V. LESSTHAN is a function that returns
381 true if the first argument is strictly less than the second. */
382
383#define VEC_lower_bound(T,V,O,LT) \
384 (VEC_OP(T,lower_bound)(V,O,LT VEC_ASSERT_INFO))
385
386/* Reallocate an array of elements with prefix. */
387extern void *vec_p_reserve (void *, int);
388extern void *vec_o_reserve (void *, int, size_t, size_t);
1e8877aa 389#define vec_free_(V) xfree (V)
350da6ee
DJ		 390
391#define VEC_ASSERT_INFO ,__FILE__,__LINE__
392#define VEC_ASSERT_DECL ,const char *file_,unsigned line_
393#define VEC_ASSERT_PASS ,file_,line_
394#define vec_assert(expr, op) \
3e43a32a
MS		 395 ((void)((expr) ? 0 : (gdb_assert_fail (op, file_, line_, \
396 ASSERT_FUNCTION), 0)))
350da6ee
DJ		 397
398#define VEC(T) VEC_##T
399#define VEC_OP(T,OP) VEC_##T##_##OP
400
401#define VEC_T(T) \
402typedef struct VEC(T) \
403{ \
404 unsigned num; \
405 unsigned alloc; \
406 T vec[1]; \
407} VEC(T)
408
409/* Vector of integer-like object. */
410#define DEF_VEC_I(T) \
411static inline void VEC_OP (T,must_be_integral_type) (void) \
412{ \
413 (void)~(T)0; \
414} \
415 \
416VEC_T(T); \
417DEF_VEC_FUNC_P(T) \
418DEF_VEC_ALLOC_FUNC_I(T) \
419struct vec_swallow_trailing_semi
420
421/* Vector of pointer to object. */
422#define DEF_VEC_P(T) \
423static inline void VEC_OP (T,must_be_pointer_type) (void) \
424{ \
425 (void)((T)1 == (void *)1); \
426} \
427 \
428VEC_T(T); \
429DEF_VEC_FUNC_P(T) \
430DEF_VEC_ALLOC_FUNC_P(T) \
431struct vec_swallow_trailing_semi
432
433/* Vector of object. */
434#define DEF_VEC_O(T) \
435VEC_T(T); \
436DEF_VEC_FUNC_O(T) \
437DEF_VEC_ALLOC_FUNC_O(T) \
438struct vec_swallow_trailing_semi
439
440#define DEF_VEC_ALLOC_FUNC_I(T) \
441static inline VEC(T) *VEC_OP (T,alloc) \
442 (int alloc_) \
443{ \
444 /* We must request exact size allocation, hence the negation. */ \
445 return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \
446 offsetof (VEC(T),vec), sizeof (T)); \
447} \
448 \
449static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
450{ \
451 size_t len_ = vec_ ? vec_->num : 0; \
452 VEC (T) *new_vec_ = NULL; \
453 \
454 if (len_) \
455 { \
581e13c1 456 /* We must request exact size allocation, hence the negation. */ \
350da6ee
DJ		 457 new_vec_ = (VEC (T) *) \
458 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
459 \
460 new_vec_->num = len_; \
461 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
462 } \
463 return new_vec_; \
464} \
465 \
466static inline void VEC_OP (T,free) \
467 (VEC(T) **vec_) \
468{ \
469 if (*vec_) \
1e8877aa 470 vec_free_ (*vec_); \
350da6ee
DJ		 471 *vec_ = NULL; \
472} \
473 \
3cf03773
TT		 474static inline void VEC_OP (T,cleanup) \
475 (void *arg_) \
476{ \
477 VEC(T) **vec_ = arg_; \
478 if (*vec_) \
479 vec_free_ (*vec_); \
480 *vec_ = NULL; \
481} \
482 \
350da6ee
DJ		 483static inline int VEC_OP (T,reserve) \
484 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
485{ \
486 int extend = !VEC_OP (T,space) \
487 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
488 \
489 if (extend) \
490 *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \
491 offsetof (VEC(T),vec), sizeof (T)); \
492 \
493 return extend; \
494} \
495 \
496static inline void VEC_OP (T,safe_grow) \
497 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
498{ \
499 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
500 "safe_grow"); \
501 VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \
502 VEC_ASSERT_PASS); \
503 (*vec_)->num = size_; \
504} \
505 \
506static inline T *VEC_OP (T,safe_push) \
507 (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \
508{ \
509 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
510 \
511 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
512} \
513 \
514static inline T *VEC_OP (T,safe_insert) \
515 (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \
516{ \
517 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
518 \
519 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
520}
521
522#define DEF_VEC_FUNC_P(T) \
523static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
524{ \
525 return vec_ ? vec_->num : 0; \
526} \
527 \
528static inline T VEC_OP (T,last) \
529 (const VEC(T) *vec_ VEC_ASSERT_DECL) \
530{ \
531 vec_assert (vec_ && vec_->num, "last"); \
532 \
533 return vec_->vec[vec_->num - 1]; \
534} \
535 \
536static inline T VEC_OP (T,index) \
537 (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
538{ \
539 vec_assert (vec_ && ix_ < vec_->num, "index"); \
540 \
541 return vec_->vec[ix_]; \
542} \
543 \
544static inline int VEC_OP (T,iterate) \
545 (const VEC(T) *vec_, unsigned ix_, T *ptr) \
546{ \
547 if (vec_ && ix_ < vec_->num) \
548 { \
549 *ptr = vec_->vec[ix_]; \
550 return 1; \
551 } \
552 else \
553 { \
554 *ptr = 0; \
555 return 0; \
556 } \
557} \
558 \
559static inline size_t VEC_OP (T,embedded_size) \
560 (int alloc_) \
561{ \
562 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
563} \
564 \
565static inline void VEC_OP (T,embedded_init) \
566 (VEC(T) *vec_, int alloc_) \
567{ \
568 vec_->num = 0; \
569 vec_->alloc = alloc_; \
570} \
571 \
572static inline int VEC_OP (T,space) \
573 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
574{ \
575 vec_assert (alloc_ >= 0, "space"); \
576 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
577} \
578 \
579static inline T *VEC_OP (T,quick_push) \
580 (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \
581{ \
582 T *slot_; \
583 \
584 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
585 slot_ = &vec_->vec[vec_->num++]; \
586 *slot_ = obj_; \
587 \
588 return slot_; \
589} \
590 \
591static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
592{ \
593 T obj_; \
594 \
595 vec_assert (vec_->num, "pop"); \
596 obj_ = vec_->vec[--vec_->num]; \
597 \
598 return obj_; \
599} \
600 \
601static inline void VEC_OP (T,truncate) \
602 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
603{ \
604 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
605 if (vec_) \
606 vec_->num = size_; \
607} \
608 \
609static inline T VEC_OP (T,replace) \
610 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
611{ \
612 T old_obj_; \
613 \
614 vec_assert (ix_ < vec_->num, "replace"); \
615 old_obj_ = vec_->vec[ix_]; \
616 vec_->vec[ix_] = obj_; \
617 \
618 return old_obj_; \
619} \
620 \
621static inline T *VEC_OP (T,quick_insert) \
622 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
623{ \
624 T *slot_; \
625 \
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)); \
629 *slot_ = obj_; \
630 \
631 return slot_; \
632} \
633 \
634static inline T VEC_OP (T,ordered_remove) \
635 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
636{ \
637 T *slot_; \
638 T obj_; \
639 \
640 vec_assert (ix_ < vec_->num, "ordered_remove"); \
641 slot_ = &vec_->vec[ix_]; \
642 obj_ = *slot_; \
643 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
644 \
645 return obj_; \
646} \
647 \
648static inline T VEC_OP (T,unordered_remove) \
649 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
650{ \
651 T *slot_; \
652 T obj_; \
653 \
654 vec_assert (ix_ < vec_->num, "unordered_remove"); \
655 slot_ = &vec_->vec[ix_]; \
656 obj_ = *slot_; \
657 *slot_ = vec_->vec[--vec_->num]; \
658 \
659 return obj_; \
660} \
661 \
662static inline void VEC_OP (T,block_remove) \
663 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
664{ \
665 T *slot_; \
666 \
667 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
668 slot_ = &vec_->vec[ix_]; \
669 vec_->num -= len_; \
670 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
671} \
672 \
673static inline T *VEC_OP (T,address) \
674 (VEC(T) *vec_) \
675{ \
676 return vec_ ? vec_->vec : 0; \
677} \
678 \
679static inline unsigned VEC_OP (T,lower_bound) \
680 (VEC(T) *vec_, const T obj_, \
681 int (*lessthan_)(const T, const T) VEC_ASSERT_DECL) \
682{ \
683 unsigned int len_ = VEC_OP (T, length) (vec_); \
684 unsigned int half_, middle_; \
685 unsigned int first_ = 0; \
686 while (len_ > 0) \
687 { \
688 T middle_elem_; \
689 half_ = len_ >> 1; \
690 middle_ = first_; \
691 middle_ += half_; \
692 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
693 if (lessthan_ (middle_elem_, obj_)) \
694 { \
695 first_ = middle_; \
696 ++first_; \
697 len_ = len_ - half_ - 1; \
698 } \
699 else \
700 len_ = half_; \
701 } \
702 return first_; \
703}
704
705#define DEF_VEC_ALLOC_FUNC_P(T) \
706static inline VEC(T) *VEC_OP (T,alloc) \
707 (int alloc_) \
708{ \
709 /* We must request exact size allocation, hence the negation. */ \
710 return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \
711} \
712 \
713static inline void VEC_OP (T,free) \
714 (VEC(T) **vec_) \
715{ \
716 if (*vec_) \
1e8877aa 717 vec_free_ (*vec_); \
350da6ee
DJ		 718 *vec_ = NULL; \
719} \
720 \
3cf03773
TT		 721static inline void VEC_OP (T,cleanup) \
722 (void *arg_) \
723{ \
724 VEC(T) **vec_ = arg_; \
725 if (*vec_) \
726 vec_free_ (*vec_); \
727 *vec_ = NULL; \
728} \
729 \
350da6ee
DJ		 730static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
731{ \
732 size_t len_ = vec_ ? vec_->num : 0; \
733 VEC (T) *new_vec_ = NULL; \
734 \
735 if (len_) \
736 { \
581e13c1 737 /* We must request exact size allocation, hence the negation. */ \
350da6ee
DJ		 738 new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \
739 \
740 new_vec_->num = len_; \
741 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
742 } \
743 return new_vec_; \
744} \
745 \
746static inline int VEC_OP (T,reserve) \
747 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
748{ \
749 int extend = !VEC_OP (T,space) \
750 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
751 \
752 if (extend) \
753 *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \
754 \
755 return extend; \
756} \
757 \
758static inline void VEC_OP (T,safe_grow) \
759 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
760{ \
761 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
762 "safe_grow"); \
763 VEC_OP (T,reserve) \
764 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
765 (*vec_)->num = size_; \
766} \
767 \
768static inline T *VEC_OP (T,safe_push) \
769 (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \
770{ \
771 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
772 \
773 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
774} \
775 \
776static inline T *VEC_OP (T,safe_insert) \
777 (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
778{ \
779 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
780 \
781 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
782}
783
784#define DEF_VEC_FUNC_O(T) \
785static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
786{ \
787 return vec_ ? vec_->num : 0; \
788} \
789 \
790static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \
791{ \
792 vec_assert (vec_ && vec_->num, "last"); \
793 \
794 return &vec_->vec[vec_->num - 1]; \
795} \
796 \
797static inline T *VEC_OP (T,index) \
798 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
799{ \
800 vec_assert (vec_ && ix_ < vec_->num, "index"); \
801 \
802 return &vec_->vec[ix_]; \
803} \
804 \
805static inline int VEC_OP (T,iterate) \
806 (VEC(T) *vec_, unsigned ix_, T **ptr) \
807{ \
808 if (vec_ && ix_ < vec_->num) \
809 { \
810 *ptr = &vec_->vec[ix_]; \
811 return 1; \
812 } \
813 else \
814 { \
815 *ptr = 0; \
816 return 0; \
817 } \
818} \
819 \
820static inline size_t VEC_OP (T,embedded_size) \
821 (int alloc_) \
822{ \
823 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
824} \
825 \
826static inline void VEC_OP (T,embedded_init) \
827 (VEC(T) *vec_, int alloc_) \
828{ \
829 vec_->num = 0; \
830 vec_->alloc = alloc_; \
831} \
832 \
833static inline int VEC_OP (T,space) \
834 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
835{ \
836 vec_assert (alloc_ >= 0, "space"); \
837 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
838} \
839 \
840static inline T *VEC_OP (T,quick_push) \
841 (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \
842{ \
843 T *slot_; \
844 \
845 vec_assert (vec_->num < vec_->alloc, "quick_push"); \
846 slot_ = &vec_->vec[vec_->num++]; \
847 if (obj_) \
848 *slot_ = *obj_; \
849 \
850 return slot_; \
851} \
852 \
853static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
854{ \
855 vec_assert (vec_->num, "pop"); \
856 --vec_->num; \
857} \
858 \
859static inline void VEC_OP (T,truncate) \
860 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
861{ \
862 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
863 if (vec_) \
864 vec_->num = size_; \
865} \
866 \
867static inline T *VEC_OP (T,replace) \
868 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
869{ \
870 T *slot_; \
871 \
872 vec_assert (ix_ < vec_->num, "replace"); \
873 slot_ = &vec_->vec[ix_]; \
874 if (obj_) \
875 *slot_ = *obj_; \
876 \
877 return slot_; \
878} \
879 \
880static inline T *VEC_OP (T,quick_insert) \
881 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
882{ \
883 T *slot_; \
884 \
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)); \
888 if (obj_) \
889 *slot_ = *obj_; \
890 \
891 return slot_; \
892} \
893 \
894static inline void VEC_OP (T,ordered_remove) \
895 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
896{ \
897 T *slot_; \
898 \
899 vec_assert (ix_ < vec_->num, "ordered_remove"); \
900 slot_ = &vec_->vec[ix_]; \
901 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
902} \
903 \
904static inline void VEC_OP (T,unordered_remove) \
905 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
906{ \
907 vec_assert (ix_ < vec_->num, "unordered_remove"); \
908 vec_->vec[ix_] = vec_->vec[--vec_->num]; \
909} \
910 \
911static inline void VEC_OP (T,block_remove) \
912 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
913{ \
914 T *slot_; \
915 \
916 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
917 slot_ = &vec_->vec[ix_]; \
918 vec_->num -= len_; \
919 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
920} \
921 \
922static inline T *VEC_OP (T,address) \
923 (VEC(T) *vec_) \
924{ \
925 return vec_ ? vec_->vec : 0; \
926} \
927 \
928static inline unsigned VEC_OP (T,lower_bound) \
929 (VEC(T) *vec_, const T *obj_, \
930 int (*lessthan_)(const T *, const T *) VEC_ASSERT_DECL) \
931{ \
932 unsigned int len_ = VEC_OP (T, length) (vec_); \
933 unsigned int half_, middle_; \
934 unsigned int first_ = 0; \
935 while (len_ > 0) \
936 { \
937 T *middle_elem_; \
938 half_ = len_ >> 1; \
939 middle_ = first_; \
940 middle_ += half_; \
941 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
942 if (lessthan_ (middle_elem_, obj_)) \
943 { \
944 first_ = middle_; \
945 ++first_; \
946 len_ = len_ - half_ - 1; \
947 } \
948 else \
949 len_ = half_; \
950 } \
951 return first_; \
952}
953
954#define DEF_VEC_ALLOC_FUNC_O(T) \
955static inline VEC(T) *VEC_OP (T,alloc) \
956 (int alloc_) \
957{ \
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)); \
961} \
962 \
963static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
964{ \
965 size_t len_ = vec_ ? vec_->num : 0; \
966 VEC (T) *new_vec_ = NULL; \
967 \
968 if (len_) \
969 { \
581e13c1 970 /* We must request exact size allocation, hence the negation. */ \
350da6ee
DJ		 971 new_vec_ = (VEC (T) *) \
972 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
973 \
974 new_vec_->num = len_; \
975 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
976 } \
977 return new_vec_; \
978} \
979 \
980static inline void VEC_OP (T,free) \
981 (VEC(T) **vec_) \
982{ \
983 if (*vec_) \
1e8877aa 984 vec_free_ (*vec_); \
350da6ee
DJ		 985 *vec_ = NULL; \
986} \
987 \
3cf03773
TT		 988static inline void VEC_OP (T,cleanup) \
989 (void *arg_) \
990{ \
991 VEC(T) **vec_ = arg_; \
992 if (*vec_) \
993 vec_free_ (*vec_); \
994 *vec_ = NULL; \
995} \
996 \
350da6ee
DJ		 997static inline int VEC_OP (T,reserve) \
998 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
999{ \
1000 int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \
1001 VEC_ASSERT_PASS); \
1002 \
1003 if (extend) \
1004 *vec_ = (VEC(T) *) \
1005 vec_o_reserve (*vec_, alloc_, offsetof (VEC(T),vec), sizeof (T)); \
1006 \
1007 return extend; \
1008} \
1009 \
1010static inline void VEC_OP (T,safe_grow) \
1011 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
1012{ \
1013 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
1014 "safe_grow"); \
1015 VEC_OP (T,reserve) \
1016 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
1017 (*vec_)->num = size_; \
1018} \
1019 \
1020static inline T *VEC_OP (T,safe_push) \
1021 (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \
1022{ \
1023 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1024 \
1025 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
1026} \
1027 \
1028static inline T *VEC_OP (T,safe_insert) \
1029 (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
1030{ \
1031 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1032 \
1033 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
1034}
1035
1036#endif /* GDB_VEC_H */
GDB Binutils - Deliverables
This page took 0.882434 seconds and 4 git commands to generate.