GDBserver
vec.h
Go to the documentation of this file.
1 /* Vector API for GDB.
2  Copyright (C) 2004-2018 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 #if !defined (GDB_VEC_H)
21 #define GDB_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 /* GDB_VEC_H */
vec_o_reserve
void * vec_o_reserve(void *, int, size_t, size_t)
Definition: vec.c:91
vec_p_reserve
void * vec_p_reserve(void *, int)
Definition: vec.c:80
Generated by   doxygen 1.8.14