gdb/vec.h

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