GDBserver
vec.h
Go to the documentation of this file.
1 /* Vector API for GDB.
2  Copyright (C) 2004-2015 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 /* The macros here implement a set of templated vector types and
24  associated interfaces. These templates are implemented with
25  macros, as we're not in C++ land. The interface functions are
26  typesafe and use static inline functions, sometimes backed by
27  out-of-line generic functions.
28 
29  Because of the different behavior of structure objects, scalar
30  objects and of pointers, there are three flavors, one for each of
31  these variants. Both the structure object and pointer variants
32  pass pointers to objects around -- in the former case the pointers
33  are stored into the vector and in the latter case the pointers are
34  dereferenced and the objects copied into the vector. The scalar
35  object variant is suitable for int-like objects, and the vector
36  elements are returned by value.
37 
38  There are both 'index' and 'iterate' accessors. The iterator
39  returns a boolean iteration condition and updates the iteration
40  variable passed by reference. Because the iterator will be
41  inlined, the address-of can be optimized away.
42 
43  The vectors are implemented using the trailing array idiom, thus
44  they are not resizeable without changing the address of the vector
45  object itself. This means you cannot have variables or fields of
46  vector type -- always use a pointer to a vector. The one exception
47  is the final field of a structure, which could be a vector type.
48  You will have to use the embedded_size & embedded_init calls to
49  create such objects, and they will probably not be resizeable (so
50  don't use the 'safe' allocation variants). The trailing array
51  idiom is used (rather than a pointer to an array of data), because,
52  if we allow NULL to also represent an empty vector, empty vectors
53  occupy minimal space in the structure containing them.
54 
55  Each operation that increases the number of active elements is
56  available in 'quick' and 'safe' variants. The former presumes that
57  there is sufficient allocated space for the operation to succeed
58  (it dies if there is not). The latter will reallocate the
59  vector, if needed. Reallocation causes an exponential increase in
60  vector size. If you know you will be adding N elements, it would
61  be more efficient to use the reserve operation before adding the
62  elements with the 'quick' operation. This will ensure there are at
63  least as many elements as you ask for, it will exponentially
64  increase if there are too few spare slots. If you want reserve a
65  specific number of slots, but do not want the exponential increase
66  (for instance, you know this is the last allocation), use a
67  negative number for reservation. You can also create a vector of a
68  specific size from the get go.
69 
70  You should prefer the push and pop operations, as they append and
71  remove from the end of the vector. If you need to remove several
72  items in one go, use the truncate operation. The insert and remove
73  operations allow you to change elements in the middle of the
74  vector. There are two remove operations, one which preserves the
75  element ordering 'ordered_remove', and one which does not
76  'unordered_remove'. The latter function copies the end element
77  into the removed slot, rather than invoke a memmove operation. The
78  'lower_bound' function will determine where to place an item in the
79  array using insert that will maintain sorted order.
80 
81  If you need to directly manipulate a vector, then the 'address'
82  accessor will return the address of the start of the vector. Also
83  the 'space' predicate will tell you whether there is spare capacity
84  in the vector. You will not normally need to use these two functions.
85 
86  Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro.
87  Variables of vector type are declared using a VEC(TYPEDEF) macro.
88  The characters O, P and I indicate whether TYPEDEF is a pointer
89  (P), object (O) or integral (I) type. Be careful to pick the
90  correct one, as you'll get an awkward and inefficient API if you
91  use the wrong one. There is a check, which results in a
92  compile-time warning, for the P and I versions, but there is no
93  check for the O versions, as that is not possible in plain C.
94 
95  An example of their use would be,
96 
97  DEF_VEC_P(tree); // non-managed tree vector.
98 
99  struct my_struct {
100  VEC(tree) *v; // A (pointer to) a vector of tree pointers.
101  };
102 
103  struct my_struct *s;
104 
105  if (VEC_length(tree, s->v)) { we have some contents }
106  VEC_safe_push(tree, s->v, decl); // append some decl onto the end
107  for (ix = 0; VEC_iterate(tree, s->v, ix, elt); ix++)
108  { do something with elt }
109 
110 */
111 
112 /* Macros to invoke API calls. A single macro works for both pointer
113  and object vectors, but the argument and return types might well be
114  different. In each macro, T is the typedef of the vector elements.
115  Some of these macros pass the vector, V, by reference (by taking
116  its address), this is noted in the descriptions. */
117 
118 /* Length of vector
119  unsigned VEC_T_length(const VEC(T) *v);
120 
121  Return the number of active elements in V. V can be NULL, in which
122  case zero is returned. */
123 
124 #define VEC_length(T,V) (VEC_OP(T,length)(V))
125 
126 
127 /* Check if vector is empty
128  int VEC_T_empty(const VEC(T) *v);
129 
130  Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
131 
132 #define VEC_empty(T,V) (VEC_length (T,V) == 0)
133 
134 
135 /* Get the final element of the vector.
136  T VEC_T_last(VEC(T) *v); // Integer
137  T VEC_T_last(VEC(T) *v); // Pointer
138  T *VEC_T_last(VEC(T) *v); // Object
139 
140  Return the final element. V must not be empty. */
141 
142 #define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO))
143 
144 /* Index into vector
145  T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
146  T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
147  T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
148 
149  Return the IX'th element. If IX must be in the domain of V. */
150 
151 #define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO))
152 
153 /* Iterate over vector
154  int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
155  int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
156  int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
157 
158  Return iteration condition and update PTR to point to the IX'th
159  element. At the end of iteration, sets PTR to NULL. Use this to
160  iterate over the elements of a vector as follows,
161 
162  for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
163  continue; */
164 
165 #define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P)))
166 
167 /* Allocate new vector.
168  VEC(T,A) *VEC_T_alloc(int reserve);
169 
170  Allocate a new vector with space for RESERVE objects. If RESERVE
171  is zero, NO vector is created. */
172 
173 #define VEC_alloc(T,N) (VEC_OP(T,alloc)(N))
174 
175 /* Free a vector.
176  void VEC_T_free(VEC(T,A) *&);
177 
178  Free a vector and set it to NULL. */
179 
180 #define VEC_free(T,V) (VEC_OP(T,free)(&V))
181 
182 /* A cleanup function for a vector.
183  void VEC_T_cleanup(void *);
184 
185  Clean up a vector. */
186 
187 #define VEC_cleanup(T) (VEC_OP(T,cleanup))
188 
189 /* Use these to determine the required size and initialization of a
190  vector embedded within another structure (as the final member).
191 
192  size_t VEC_T_embedded_size(int reserve);
193  void VEC_T_embedded_init(VEC(T) *v, int reserve);
194 
195  These allow the caller to perform the memory allocation. */
196 
197 #define VEC_embedded_size(T,N) (VEC_OP(T,embedded_size)(N))
198 #define VEC_embedded_init(T,O,N) (VEC_OP(T,embedded_init)(VEC_BASE(O),N))
199 
200 /* Copy a vector.
201  VEC(T,A) *VEC_T_copy(VEC(T) *);
202 
203  Copy the live elements of a vector into a new vector. The new and
204  old vectors need not be allocated by the same mechanism. */
205 
206 #define VEC_copy(T,V) (VEC_OP(T,copy)(V))
207 
208 /* Merge two vectors.
209  VEC(T,A) *VEC_T_merge(VEC(T) *, VEC(T) *);
210 
211  Copy the live elements of both vectors into a new vector. The new
212  and old vectors need not be allocated by the same mechanism. */
213 #define VEC_merge(T,V1,V2) (VEC_OP(T,merge)(V1, V2))
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
245  filled in. For object vectors, the new value can be NULL, in which
246  case NO initialization is performed. There must
247  be sufficient space in the vector. */
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
257  filled in. For object vectors, the new value can be NULL, in which
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 
267  Pop the last element off the end. Returns the element popped, for
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
297  vectors returns the original value. For object vectors returns a
298  pointer to the new value. For object vectors the new value can be
299  NULL, in which case no overwriting of the slot is actually
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 
309  Insert an element, VAL, at the IXth position of V. Return a pointer
310  to the slot created. For vectors of object, the new value can be
311  NULL, in which case no initialization of the inserted slot takes
312  place. There must be sufficient space. */
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 
322  Insert an element, VAL, at the IXth position of V. Return a pointer
323  to the slot created. For vectors of object, the new value can be
324  NULL, in which case no initialization of the inserted slot takes
325  place. Reallocate V, if necessary. */
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 
335  Remove an element from the IXth position of V. Ordering of
336  remaining elements is preserved. For pointer vectors returns the
337  removed object. This is an O(N) operation due to a memmove. */
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 
347  Remove an element from the IXth position of V. Ordering of
348  remaining elements is destroyed. For pointer vectors returns the
349  removed object. This is an O(1) operation. */
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.
358  This is an O(N) operation due to memmove. */
359 
360 #define VEC_block_remove(T,V,I,L) \
361  (VEC_OP(T,block_remove)(V,I,L VEC_ASSERT_INFO))
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. */
387 extern void *vec_p_reserve (void *, int);
388 extern void *vec_o_reserve (void *, int, size_t, size_t);
389 #define vec_free_(V) xfree (V)
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) \
395  ((void)((expr) ? 0 : (gdb_assert_fail (op, file_, line_, \
396  FUNCTION_NAME), 0)))
397 
398 #define VEC(T) VEC_##T
399 #define VEC_OP(T,OP) VEC_##T##_##OP
400 
401 #define VEC_T(T) \
402 typedef 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) \
411 static inline void VEC_OP (T,must_be_integral_type) (void) \
412 { \
413  (void)~(T)0; \
414 } \
415  \
416 VEC_T(T); \
417 DEF_VEC_FUNC_P(T) \
418 DEF_VEC_ALLOC_FUNC_I(T) \
419 struct vec_swallow_trailing_semi
420 
421 /* Vector of pointer to object. */
422 #define DEF_VEC_P(T) \
423 static inline void VEC_OP (T,must_be_pointer_type) (void) \
424 { \
425  (void)((T)1 == (void *)1); \
426 } \
427  \
428 VEC_T(T); \
429 DEF_VEC_FUNC_P(T) \
430 DEF_VEC_ALLOC_FUNC_P(T) \
431 struct vec_swallow_trailing_semi
432 
433 /* Vector of object. */
434 #define DEF_VEC_O(T) \
435 VEC_T(T); \
436 DEF_VEC_FUNC_O(T) \
437 DEF_VEC_ALLOC_FUNC_O(T) \
438 struct vec_swallow_trailing_semi
439 
440 #define DEF_VEC_ALLOC_FUNC_I(T) \
441 static 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  \
449 static 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  { \
456  /* We must request exact size allocation, hence the negation. */ \
457  new_vec_ = (VEC (T) *) \
458  vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
459  \
460  new_vec_->num = len_; \
461  memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
462  } \
463  return new_vec_; \
464 } \
465  \
466 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \
467 { \
468  if (vec1_ && vec2_) \
469  { \
470  size_t len_ = vec1_->num + vec2_->num; \
471  VEC (T) *new_vec_ = NULL; \
472  \
473  /* We must request exact size allocation, hence the negation. */ \
474  new_vec_ = (VEC (T) *) \
475  vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
476  \
477  new_vec_->num = len_; \
478  memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \
479  memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \
480  sizeof (T) * vec2_->num); \
481  \
482  return new_vec_; \
483  } \
484  else \
485  return VEC_copy (T, vec1_ ? vec1_ : vec2_); \
486 } \
487  \
488 static inline void VEC_OP (T,free) \
489  (VEC(T) **vec_) \
490 { \
491  if (*vec_) \
492  vec_free_ (*vec_); \
493  *vec_ = NULL; \
494 } \
495  \
496 static inline void VEC_OP (T,cleanup) \
497  (void *arg_) \
498 { \
499  VEC(T) **vec_ = arg_; \
500  if (*vec_) \
501  vec_free_ (*vec_); \
502  *vec_ = NULL; \
503 } \
504  \
505 static inline int VEC_OP (T,reserve) \
506  (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
507 { \
508  int extend = !VEC_OP (T,space) \
509  (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
510  \
511  if (extend) \
512  *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \
513  offsetof (VEC(T),vec), sizeof (T)); \
514  \
515  return extend; \
516 } \
517  \
518 static inline void VEC_OP (T,safe_grow) \
519  (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
520 { \
521  vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
522  "safe_grow"); \
523  VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \
524  VEC_ASSERT_PASS); \
525  (*vec_)->num = size_; \
526 } \
527  \
528 static inline T *VEC_OP (T,safe_push) \
529  (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \
530 { \
531  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
532  \
533  return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
534 } \
535  \
536 static inline T *VEC_OP (T,safe_insert) \
537  (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \
538 { \
539  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
540  \
541  return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
542 }
543 
544 #define DEF_VEC_FUNC_P(T) \
545 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
546 { \
547  return vec_ ? vec_->num : 0; \
548 } \
549  \
550 static inline T VEC_OP (T,last) \
551  (const VEC(T) *vec_ VEC_ASSERT_DECL) \
552 { \
553  vec_assert (vec_ && vec_->num, "last"); \
554  \
555  return vec_->vec[vec_->num - 1]; \
556 } \
557  \
558 static inline T VEC_OP (T,index) \
559  (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
560 { \
561  vec_assert (vec_ && ix_ < vec_->num, "index"); \
562  \
563  return vec_->vec[ix_]; \
564 } \
565  \
566 static inline int VEC_OP (T,iterate) \
567  (const VEC(T) *vec_, unsigned ix_, T *ptr) \
568 { \
569  if (vec_ && ix_ < vec_->num) \
570  { \
571  *ptr = vec_->vec[ix_]; \
572  return 1; \
573  } \
574  else \
575  { \
576  *ptr = 0; \
577  return 0; \
578  } \
579 } \
580  \
581 static inline size_t VEC_OP (T,embedded_size) \
582  (int alloc_) \
583 { \
584  return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
585 } \
586  \
587 static inline void VEC_OP (T,embedded_init) \
588  (VEC(T) *vec_, int alloc_) \
589 { \
590  vec_->num = 0; \
591  vec_->alloc = alloc_; \
592 } \
593  \
594 static inline int VEC_OP (T,space) \
595  (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
596 { \
597  vec_assert (alloc_ >= 0, "space"); \
598  return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
599 } \
600  \
601 static inline T *VEC_OP (T,quick_push) \
602  (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \
603 { \
604  T *slot_; \
605  \
606  vec_assert (vec_->num < vec_->alloc, "quick_push"); \
607  slot_ = &vec_->vec[vec_->num++]; \
608  *slot_ = obj_; \
609  \
610  return slot_; \
611 } \
612  \
613 static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
614 { \
615  T obj_; \
616  \
617  vec_assert (vec_->num, "pop"); \
618  obj_ = vec_->vec[--vec_->num]; \
619  \
620  return obj_; \
621 } \
622  \
623 static inline void VEC_OP (T,truncate) \
624  (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
625 { \
626  vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
627  if (vec_) \
628  vec_->num = size_; \
629 } \
630  \
631 static inline T VEC_OP (T,replace) \
632  (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
633 { \
634  T old_obj_; \
635  \
636  vec_assert (ix_ < vec_->num, "replace"); \
637  old_obj_ = vec_->vec[ix_]; \
638  vec_->vec[ix_] = obj_; \
639  \
640  return old_obj_; \
641 } \
642  \
643 static inline T *VEC_OP (T,quick_insert) \
644  (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
645 { \
646  T *slot_; \
647  \
648  vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \
649  slot_ = &vec_->vec[ix_]; \
650  memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
651  *slot_ = obj_; \
652  \
653  return slot_; \
654 } \
655  \
656 static inline T VEC_OP (T,ordered_remove) \
657  (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
658 { \
659  T *slot_; \
660  T obj_; \
661  \
662  vec_assert (ix_ < vec_->num, "ordered_remove"); \
663  slot_ = &vec_->vec[ix_]; \
664  obj_ = *slot_; \
665  memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
666  \
667  return obj_; \
668 } \
669  \
670 static inline T VEC_OP (T,unordered_remove) \
671  (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
672 { \
673  T *slot_; \
674  T obj_; \
675  \
676  vec_assert (ix_ < vec_->num, "unordered_remove"); \
677  slot_ = &vec_->vec[ix_]; \
678  obj_ = *slot_; \
679  *slot_ = vec_->vec[--vec_->num]; \
680  \
681  return obj_; \
682 } \
683  \
684 static inline void VEC_OP (T,block_remove) \
685  (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
686 { \
687  T *slot_; \
688  \
689  vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
690  slot_ = &vec_->vec[ix_]; \
691  vec_->num -= len_; \
692  memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
693 } \
694  \
695 static inline T *VEC_OP (T,address) \
696  (VEC(T) *vec_) \
697 { \
698  return vec_ ? vec_->vec : 0; \
699 } \
700  \
701 static inline unsigned VEC_OP (T,lower_bound) \
702  (VEC(T) *vec_, const T obj_, \
703  int (*lessthan_)(const T, const T) VEC_ASSERT_DECL) \
704 { \
705  unsigned int len_ = VEC_OP (T, length) (vec_); \
706  unsigned int half_, middle_; \
707  unsigned int first_ = 0; \
708  while (len_ > 0) \
709  { \
710  T middle_elem_; \
711  half_ = len_ >> 1; \
712  middle_ = first_; \
713  middle_ += half_; \
714  middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
715  if (lessthan_ (middle_elem_, obj_)) \
716  { \
717  first_ = middle_; \
718  ++first_; \
719  len_ = len_ - half_ - 1; \
720  } \
721  else \
722  len_ = half_; \
723  } \
724  return first_; \
725 }
726 
727 #define DEF_VEC_ALLOC_FUNC_P(T) \
728 static inline VEC(T) *VEC_OP (T,alloc) \
729  (int alloc_) \
730 { \
731  /* We must request exact size allocation, hence the negation. */ \
732  return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \
733 } \
734  \
735 static inline void VEC_OP (T,free) \
736  (VEC(T) **vec_) \
737 { \
738  if (*vec_) \
739  vec_free_ (*vec_); \
740  *vec_ = NULL; \
741 } \
742  \
743 static inline void VEC_OP (T,cleanup) \
744  (void *arg_) \
745 { \
746  VEC(T) **vec_ = arg_; \
747  if (*vec_) \
748  vec_free_ (*vec_); \
749  *vec_ = NULL; \
750 } \
751  \
752 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
753 { \
754  size_t len_ = vec_ ? vec_->num : 0; \
755  VEC (T) *new_vec_ = NULL; \
756  \
757  if (len_) \
758  { \
759  /* We must request exact size allocation, hence the negation. */ \
760  new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \
761  \
762  new_vec_->num = len_; \
763  memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
764  } \
765  return new_vec_; \
766 } \
767  \
768 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \
769 { \
770  if (vec1_ && vec2_) \
771  { \
772  size_t len_ = vec1_->num + vec2_->num; \
773  VEC (T) *new_vec_ = NULL; \
774  \
775  /* We must request exact size allocation, hence the negation. */ \
776  new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \
777  \
778  new_vec_->num = len_; \
779  memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \
780  memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \
781  sizeof (T) * vec2_->num); \
782  \
783  return new_vec_; \
784  } \
785  else \
786  return VEC_copy (T, vec1_ ? vec1_ : vec2_); \
787 } \
788  \
789 static inline int VEC_OP (T,reserve) \
790  (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
791 { \
792  int extend = !VEC_OP (T,space) \
793  (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \
794  \
795  if (extend) \
796  *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \
797  \
798  return extend; \
799 } \
800  \
801 static inline void VEC_OP (T,safe_grow) \
802  (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
803 { \
804  vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
805  "safe_grow"); \
806  VEC_OP (T,reserve) \
807  (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
808  (*vec_)->num = size_; \
809 } \
810  \
811 static inline T *VEC_OP (T,safe_push) \
812  (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \
813 { \
814  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
815  \
816  return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
817 } \
818  \
819 static inline T *VEC_OP (T,safe_insert) \
820  (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \
821 { \
822  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
823  \
824  return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
825 }
826 
827 #define DEF_VEC_FUNC_O(T) \
828 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \
829 { \
830  return vec_ ? vec_->num : 0; \
831 } \
832  \
833 static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \
834 { \
835  vec_assert (vec_ && vec_->num, "last"); \
836  \
837  return &vec_->vec[vec_->num - 1]; \
838 } \
839  \
840 static inline T *VEC_OP (T,index) \
841  (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
842 { \
843  vec_assert (vec_ && ix_ < vec_->num, "index"); \
844  \
845  return &vec_->vec[ix_]; \
846 } \
847  \
848 static inline int VEC_OP (T,iterate) \
849  (VEC(T) *vec_, unsigned ix_, T **ptr) \
850 { \
851  if (vec_ && ix_ < vec_->num) \
852  { \
853  *ptr = &vec_->vec[ix_]; \
854  return 1; \
855  } \
856  else \
857  { \
858  *ptr = 0; \
859  return 0; \
860  } \
861 } \
862  \
863 static inline size_t VEC_OP (T,embedded_size) \
864  (int alloc_) \
865 { \
866  return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \
867 } \
868  \
869 static inline void VEC_OP (T,embedded_init) \
870  (VEC(T) *vec_, int alloc_) \
871 { \
872  vec_->num = 0; \
873  vec_->alloc = alloc_; \
874 } \
875  \
876 static inline int VEC_OP (T,space) \
877  (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \
878 { \
879  vec_assert (alloc_ >= 0, "space"); \
880  return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \
881 } \
882  \
883 static inline T *VEC_OP (T,quick_push) \
884  (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \
885 { \
886  T *slot_; \
887  \
888  vec_assert (vec_->num < vec_->alloc, "quick_push"); \
889  slot_ = &vec_->vec[vec_->num++]; \
890  if (obj_) \
891  *slot_ = *obj_; \
892  \
893  return slot_; \
894 } \
895  \
896 static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \
897 { \
898  vec_assert (vec_->num, "pop"); \
899  --vec_->num; \
900 } \
901  \
902 static inline void VEC_OP (T,truncate) \
903  (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \
904 { \
905  vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \
906  if (vec_) \
907  vec_->num = size_; \
908 } \
909  \
910 static inline T *VEC_OP (T,replace) \
911  (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
912 { \
913  T *slot_; \
914  \
915  vec_assert (ix_ < vec_->num, "replace"); \
916  slot_ = &vec_->vec[ix_]; \
917  if (obj_) \
918  *slot_ = *obj_; \
919  \
920  return slot_; \
921 } \
922  \
923 static inline T *VEC_OP (T,quick_insert) \
924  (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
925 { \
926  T *slot_; \
927  \
928  vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \
929  slot_ = &vec_->vec[ix_]; \
930  memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \
931  if (obj_) \
932  *slot_ = *obj_; \
933  \
934  return slot_; \
935 } \
936  \
937 static inline void VEC_OP (T,ordered_remove) \
938  (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
939 { \
940  T *slot_; \
941  \
942  vec_assert (ix_ < vec_->num, "ordered_remove"); \
943  slot_ = &vec_->vec[ix_]; \
944  memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \
945 } \
946  \
947 static inline void VEC_OP (T,unordered_remove) \
948  (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \
949 { \
950  vec_assert (ix_ < vec_->num, "unordered_remove"); \
951  vec_->vec[ix_] = vec_->vec[--vec_->num]; \
952 } \
953  \
954 static inline void VEC_OP (T,block_remove) \
955  (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \
956 { \
957  T *slot_; \
958  \
959  vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \
960  slot_ = &vec_->vec[ix_]; \
961  vec_->num -= len_; \
962  memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \
963 } \
964  \
965 static inline T *VEC_OP (T,address) \
966  (VEC(T) *vec_) \
967 { \
968  return vec_ ? vec_->vec : 0; \
969 } \
970  \
971 static inline unsigned VEC_OP (T,lower_bound) \
972  (VEC(T) *vec_, const T *obj_, \
973  int (*lessthan_)(const T *, const T *) VEC_ASSERT_DECL) \
974 { \
975  unsigned int len_ = VEC_OP (T, length) (vec_); \
976  unsigned int half_, middle_; \
977  unsigned int first_ = 0; \
978  while (len_ > 0) \
979  { \
980  T *middle_elem_; \
981  half_ = len_ >> 1; \
982  middle_ = first_; \
983  middle_ += half_; \
984  middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \
985  if (lessthan_ (middle_elem_, obj_)) \
986  { \
987  first_ = middle_; \
988  ++first_; \
989  len_ = len_ - half_ - 1; \
990  } \
991  else \
992  len_ = half_; \
993  } \
994  return first_; \
995 }
996 
997 #define DEF_VEC_ALLOC_FUNC_O(T) \
998 static inline VEC(T) *VEC_OP (T,alloc) \
999  (int alloc_) \
1000 { \
1001  /* We must request exact size allocation, hence the negation. */ \
1002  return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \
1003  offsetof (VEC(T),vec), sizeof (T)); \
1004 } \
1005  \
1006 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \
1007 { \
1008  size_t len_ = vec_ ? vec_->num : 0; \
1009  VEC (T) *new_vec_ = NULL; \
1010  \
1011  if (len_) \
1012  { \
1013  /* We must request exact size allocation, hence the negation. */ \
1014  new_vec_ = (VEC (T) *) \
1015  vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
1016  \
1017  new_vec_->num = len_; \
1018  memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \
1019  } \
1020  return new_vec_; \
1021 } \
1022  \
1023 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \
1024 { \
1025  if (vec1_ && vec2_) \
1026  { \
1027  size_t len_ = vec1_->num + vec2_->num; \
1028  VEC (T) *new_vec_ = NULL; \
1029  \
1030  /* We must request exact size allocation, hence the negation. */ \
1031  new_vec_ = (VEC (T) *) \
1032  vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \
1033  \
1034  new_vec_->num = len_; \
1035  memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \
1036  memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \
1037  sizeof (T) * vec2_->num); \
1038  \
1039  return new_vec_; \
1040  } \
1041  else \
1042  return VEC_copy (T, vec1_ ? vec1_ : vec2_); \
1043 } \
1044  \
1045 static inline void VEC_OP (T,free) \
1046  (VEC(T) **vec_) \
1047 { \
1048  if (*vec_) \
1049  vec_free_ (*vec_); \
1050  *vec_ = NULL; \
1051 } \
1052  \
1053 static inline void VEC_OP (T,cleanup) \
1054  (void *arg_) \
1055 { \
1056  VEC(T) **vec_ = arg_; \
1057  if (*vec_) \
1058  vec_free_ (*vec_); \
1059  *vec_ = NULL; \
1060 } \
1061  \
1062 static inline int VEC_OP (T,reserve) \
1063  (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \
1064 { \
1065  int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \
1066  VEC_ASSERT_PASS); \
1067  \
1068  if (extend) \
1069  *vec_ = (VEC(T) *) \
1070  vec_o_reserve (*vec_, alloc_, offsetof (VEC(T),vec), sizeof (T)); \
1071  \
1072  return extend; \
1073 } \
1074  \
1075 static inline void VEC_OP (T,safe_grow) \
1076  (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \
1077 { \
1078  vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \
1079  "safe_grow"); \
1080  VEC_OP (T,reserve) \
1081  (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \
1082  (*vec_)->num = size_; \
1083 } \
1084  \
1085 static inline T *VEC_OP (T,safe_push) \
1086  (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \
1087 { \
1088  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1089  \
1090  return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \
1091 } \
1092  \
1093 static inline T *VEC_OP (T,safe_insert) \
1094  (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \
1095 { \
1096  VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \
1097  \
1098  return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \
1099 }
1100 
1101 #endif /* GDB_VEC_H */
void * vec_o_reserve(void *, int, size_t, size_t)
Definition: vec.c:91
void * vec_p_reserve(void *, int)
Definition: vec.c:80