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