gcc/vec.h

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