contrib/gdb-7/gdb/vec.h

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