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 #define vec_heap_free(V) free (V)
 433
 434 #if ENABLE_CHECKING
 435 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
 436 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
 437 #define VEC_CHECK_PASS ,file_,line_,function_
 438
 439 #define VEC_ASSERT(EXPR,OP,T,A) \
 440   (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
 441
 442 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
 443      ATTRIBUTE_NORETURN;
 444 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
 445 #else
 446 #define VEC_CHECK_INFO
 447 #define VEC_CHECK_DECL
 448 #define VEC_CHECK_PASS
 449 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
 450 #endif
 451
 452 /* Note: gengtype has hardwired knowledge of the expansions of the
 453    VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros.  If you change the
 454    expansions of these macros you may need to change gengtype too.  */
 455
 456 #define VEC(T,A) VEC_##T##_##A
 457 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
 458
 459 /* Base of vector type, not user visible.  */
 460 #define VEC_T(T,B)                                                        \
 461 typedef struct VEC(T,B)                                                   \
 462 {                                                                         \
 463   unsigned num;                                                           \
 464   unsigned alloc;                                                         \
 465   T vec[1];                                                               \
 466 } VEC(T,B)
 467
 468 #define VEC_T_GTY(T,B)                                                    \
 469 typedef struct VEC(T,B) GTY(())                                           \
 470 {                                                                         \
 471   unsigned num;                                                           \
 472   unsigned alloc;                                                         \
 473   T GTY ((length ("%h.num"))) vec[1];                                     \
 474 } VEC(T,B)
 475
 476 /* Derived vector type, user visible.  */
 477 #define VEC_TA_GTY(T,B,A,GTY)                                             \
 478 typedef struct VEC(T,A) GTY                                               \
 479 {                                                                         \
 480   VEC(T,B) base;                                                          \
 481 } VEC(T,A)
 482
 483 #define VEC_TA(T,B,A)                                                     \
 484 typedef struct VEC(T,A)                                                   \
 485 {                                                                         \
 486   VEC(T,B) base;                                                          \
 487 } VEC(T,A)
 488
 489 /* Convert to base type.  */
 490 #define VEC_BASE(P)  ((P) ? &(P)->base : 0)
 491
 492 /* Vector of integer-like object.  */
 493 #define DEF_VEC_I(T)                                                      \
 494 static inline void VEC_OP (T,must_be,integral_type) (void)                \
 495 {                                                                         \
 496   (void)~(T)0;                                                            \
 497 }                                                                         \
 498                                                                           \
 499 VEC_T(T,base);                                                            \
 500 VEC_TA(T,base,none);                                                      \
 501 DEF_VEC_FUNC_P(T)                                                         \
 502 struct vec_swallow_trailing_semi
 503 #define DEF_VEC_ALLOC_I(T,A)                                              \
 504 VEC_TA(T,base,A);                                                         \
 505 DEF_VEC_ALLOC_FUNC_I(T,A)                                                 \
 506 struct vec_swallow_trailing_semi
 507
 508 /* Vector of pointer to object.  */
 509 #define DEF_VEC_P(T)                                                      \
 510 static inline void VEC_OP (T,must_be,pointer_type) (void)                 \
 511 {                                                                         \
 512   (void)((T)1 == (void *)1);                                              \
 513 }                                                                         \
 514                                                                           \
 515 VEC_T_GTY(T,base);                                                        \
 516 VEC_TA(T,base,none);                                                      \
 517 DEF_VEC_FUNC_P(T)                                                         \
 518 struct vec_swallow_trailing_semi
 519 #define DEF_VEC_ALLOC_P(T,A)                                              \
 520 VEC_TA(T,base,A);                                                         \
 521 DEF_VEC_ALLOC_FUNC_P(T,A)                                                 \
 522 struct vec_swallow_trailing_semi
 523
 524 #define DEF_VEC_FUNC_P(T)                                                 \
 525 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 526 {                                                                         \
 527   return vec_ ? vec_->num : 0;                                            \
 528 }                                                                         \
 529                                                                           \
 530 static inline T VEC_OP (T,base,last)                                      \
 531      (const VEC(T,base) *vec_ VEC_CHECK_DECL)                             \
 532 {                                                                         \
 533   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 534                                                                           \
 535   return vec_->vec[vec_->num - 1];                                        \
 536 }                                                                         \
 537                                                                           \
 538 static inline T VEC_OP (T,base,index)                                     \
 539      (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)               \
 540 {                                                                         \
 541   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 542                                                                           \
 543   return vec_->vec[ix_];                                                  \
 544 }                                                                         \
 545                                                                           \
 546 static inline int VEC_OP (T,base,iterate)                                 \
 547      (const VEC(T,base) *vec_, unsigned ix_, T *ptr)                      \
 548 {                                                                         \
 549   if (vec_ && ix_ < vec_->num)                                            \
 550     {                                                                     \
 551       *ptr = vec_->vec[ix_];                                              \
 552       return 1;                                                           \
 553     }                                                                     \
 554   else                                                                    \
 555     {                                                                     \
 556       *ptr = 0;                                                           \
 557       return 0;                                                           \
 558     }                                                                     \
 559 }                                                                         \
 560                                                                           \
 561 static inline size_t VEC_OP (T,base,embedded_size)                        \
 562      (int alloc_)                                                         \
 563 {                                                                         \
 564   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 565 }                                                                         \
 566                                                                           \
 567 static inline void VEC_OP (T,base,embedded_init)                          \
 568      (VEC(T,base) *vec_, int alloc_)                                      \
 569 {                                                                         \
 570   vec_->num = 0;                                                          \
 571   vec_->alloc = alloc_;                                                   \
 572 }                                                                         \
 573                                                                           \
 574 static inline int VEC_OP (T,base,space)                                   \
 575      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 576 {                                                                         \
 577   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 578   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 579 }                                                                         \
 580                                                                           \
 581 static inline T *VEC_OP (T,base,quick_push)                               \
 582      (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)                           \
 583 {                                                                         \
 584   T *slot_;                                                               \
 585                                                                           \
 586   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 587   slot_ = &vec_->vec[vec_->num++];                                        \
 588   *slot_ = obj_;                                                          \
 589                                                                           \
 590   return slot_;                                                           \
 591 }                                                                         \
 592                                                                           \
 593 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)    \
 594 {                                                                         \
 595   T obj_;                                                                 \
 596                                                                           \
 597   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 598   obj_ = vec_->vec[--vec_->num];                                          \
 599                                                                           \
 600   return obj_;                                                            \
 601 }                                                                         \
 602                                                                           \
 603 static inline void VEC_OP (T,base,truncate)                               \
 604      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 605 {                                                                         \
 606   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 607   if (vec_)                                                               \
 608     vec_->num = size_;                                                    \
 609 }                                                                         \
 610                                                                           \
 611 static inline T VEC_OP (T,base,replace)                                   \
 612      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 613 {                                                                         \
 614   T old_obj_;                                                             \
 615                                                                           \
 616   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 617   old_obj_ = vec_->vec[ix_];                                              \
 618   vec_->vec[ix_] = obj_;                                                  \
 619                                                                           \
 620   return old_obj_;                                                        \
 621 }                                                                         \
 622                                                                           \
 623 static inline T *VEC_OP (T,base,quick_insert)                             \
 624      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 625 {                                                                         \
 626   T *slot_;                                                               \
 627                                                                           \
 628   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 629   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 630   slot_ = &vec_->vec[ix_];                                                \
 631   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 632   *slot_ = obj_;                                                          \
 633                                                                           \
 634   return slot_;                                                           \
 635 }                                                                         \
 636                                                                           \
 637 static inline T VEC_OP (T,base,ordered_remove)                            \
 638      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 639 {                                                                         \
 640   T *slot_;                                                               \
 641   T obj_;                                                                 \
 642                                                                           \
 643   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 644   slot_ = &vec_->vec[ix_];                                                \
 645   obj_ = *slot_;                                                          \
 646   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 647                                                                           \
 648   return obj_;                                                            \
 649 }                                                                         \
 650                                                                           \
 651 static inline T VEC_OP (T,base,unordered_remove)                          \
 652      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 653 {                                                                         \
 654   T *slot_;                                                               \
 655   T obj_;                                                                 \
 656                                                                           \
 657   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 658   slot_ = &vec_->vec[ix_];                                                \
 659   obj_ = *slot_;                                                          \
 660   *slot_ = vec_->vec[--vec_->num];                                        \
 661                                                                           \
 662   return obj_;                                                            \
 663 }                                                                         \
 664                                                                           \
 665 static inline void VEC_OP (T,base,block_remove)                           \
 666      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 667 {                                                                         \
 668   T *slot_;                                                               \
 669                                                                           \
 670   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 671   slot_ = &vec_->vec[ix_];                                                \
 672   vec_->num -= len_;                                                      \
 673   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 674 }                                                                         \
 675                                                                           \
 676 static inline T *VEC_OP (T,base,address)                                  \
 677      (VEC(T,base) *vec_)                                                  \
 678 {                                                                         \
 679   return vec_ ? vec_->vec : 0;                                            \
 680 }                                                                         \
 681                                                                           \
 682 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 683      (VEC(T,base) *vec_, const T obj_,                                    \
 684       bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)                 \
 685 {                                                                         \
 686    unsigned int len_ = VEC_OP (T,base, length) (vec_);                    \
 687    unsigned int half_, middle_;                                           \
 688    unsigned int first_ = 0;                                               \
 689    while (len_ > 0)                                                       \
 690      {                                                                    \
 691         T middle_elem_;                                                   \
 692         half_ = len_ >> 1;                                                \
 693         middle_ = first_;                                                 \
 694         middle_ += half_;                                                 \
 695         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 696         if (lessthan_ (middle_elem_, obj_))                               \
 697           {                                                               \
 698              first_ = middle_;                                            \
 699              ++first_;                                                    \
 700              len_ = len_ - half_ - 1;                                     \
 701           }                                                               \
 702         else                                                              \
 703           len_ = half_;                                                   \
 704      }                                                                    \
 705    return first_;                                                         \
 706 }
 707
 708 #define DEF_VEC_ALLOC_FUNC_P(T,A)                                         \
 709 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 710      (int alloc_ MEM_STAT_DECL)                                           \
 711 {                                                                         \
 712   return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_             \
 713                                                  PASS_MEM_STAT);          \
 714 }                                                                         \
 715                                                                           \
 716 static inline void VEC_OP (T,A,free)                                      \
 717      (VEC(T,A) **vec_)                                                    \
 718 {                                                                         \
 719   if (*vec_)                                                              \
 720     vec_##A##_free (*vec_);                                               \
 721   *vec_ = NULL;                                                           \
 722 }                                                                         \
 723                                                                           \
 724 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
 725 {                                                                         \
 726   size_t len_ = vec_ ? vec_->num : 0;                                     \
 727   VEC (T,A) *new_vec_ = NULL;                                             \
 728                                                                           \
 729   if (len_)                                                               \
 730     {                                                                     \
 731       new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact                  \
 732                                (NULL, len_ PASS_MEM_STAT));               \
 733                                                                           \
 734       new_vec_->base.num = len_;                                          \
 735       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
 736     }                                                                     \
 737   return new_vec_;                                                        \
 738 }                                                                         \
 739                                                                           \
 740 static inline int VEC_OP (T,A,reserve)                                    \
 741      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 742 {                                                                         \
 743   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 744                                        VEC_CHECK_PASS);                   \
 745                                                                           \
 746   if (extend)                                                             \
 747     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
 748                                                                           \
 749   return extend;                                                          \
 750 }                                                                         \
 751                                                                           \
 752 static inline int VEC_OP (T,A,reserve_exact)                              \
 753      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 754 {                                                                         \
 755   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 756                                        VEC_CHECK_PASS);                   \
 757                                                                           \
 758   if (extend)                                                             \
 759     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_         \
 760                                                     PASS_MEM_STAT);       \
 761                                                                           \
 762   return extend;                                                          \
 763 }                                                                         \
 764                                                                           \
 765 static inline void VEC_OP (T,A,safe_grow)                                 \
 766      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 767 {                                                                         \
 768   VEC_ASSERT (size_ >= 0                                                  \
 769               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
 770                                                  "grow", T, A);           \
 771   VEC_OP (T,A,reserve_exact) (vec_,                                       \
 772                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
 773                               VEC_CHECK_PASS PASS_MEM_STAT);              \
 774   VEC_BASE (*vec_)->num = size_;                                          \
 775 }                                                                         \
 776                                                                           \
 777 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
 778      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 779 {                                                                         \
 780   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
 781   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
 782   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
 783           sizeof (T) * (size_ - oldsize));                                \
 784 }                                                                         \
 785                                                                           \
 786 static inline T *VEC_OP (T,A,safe_push)                                   \
 787      (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)               \
 788 {                                                                         \
 789   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 790                                                                           \
 791   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
 792 }                                                                         \
 793                                                                           \
 794 static inline T *VEC_OP (T,A,safe_insert)                                 \
 795      (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
 796 {                                                                         \
 797   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 798                                                                           \
 799   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
 800                                        VEC_CHECK_PASS);                   \
 801 }
 802
 803 /* Vector of object.  */
 804 #define DEF_VEC_O(T)                                                      \
 805 VEC_T_GTY(T,base);                                                        \
 806 VEC_TA(T,base,none);                                              \
 807 DEF_VEC_FUNC_O(T)                                                         \
 808 struct vec_swallow_trailing_semi
 809 #define DEF_VEC_ALLOC_O(T,A)                                              \
 810 VEC_TA(T,base,A);                                                         \
 811 DEF_VEC_ALLOC_FUNC_O(T,A)                                                 \
 812 struct vec_swallow_trailing_semi
 813
 814 #define DEF_VEC_FUNC_O(T)                                                 \
 815 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 816 {                                                                         \
 817   return vec_ ? vec_->num : 0;                                            \
 818 }                                                                         \
 819                                                                           \
 820 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL)  \
 821 {                                                                         \
 822   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 823                                                                           \
 824   return &vec_->vec[vec_->num - 1];                                       \
 825 }                                                                         \
 826                                                                           \
 827 static inline T *VEC_OP (T,base,index)                                    \
 828      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 829 {                                                                         \
 830   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 831                                                                           \
 832   return &vec_->vec[ix_];                                                 \
 833 }                                                                         \
 834                                                                           \
 835 static inline int VEC_OP (T,base,iterate)                                 \
 836      (VEC(T,base) *vec_, unsigned ix_, T **ptr)                           \
 837 {                                                                         \
 838   if (vec_ && ix_ < vec_->num)                                            \
 839     {                                                                     \
 840       *ptr = &vec_->vec[ix_];                                             \
 841       return 1;                                                           \
 842     }                                                                     \
 843   else                                                                    \
 844     {                                                                     \
 845       *ptr = 0;                                                           \
 846       return 0;                                                           \
 847     }                                                                     \
 848 }                                                                         \
 849                                                                           \
 850 static inline size_t VEC_OP (T,base,embedded_size)                        \
 851      (int alloc_)                                                         \
 852 {                                                                         \
 853   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 854 }                                                                         \
 855                                                                           \
 856 static inline void VEC_OP (T,base,embedded_init)                          \
 857      (VEC(T,base) *vec_, int alloc_)                                      \
 858 {                                                                         \
 859   vec_->num = 0;                                                          \
 860   vec_->alloc = alloc_;                                                   \
 861 }                                                                         \
 862                                                                           \
 863 static inline int VEC_OP (T,base,space)                                   \
 864      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 865 {                                                                         \
 866   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 867   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 868 }                                                                         \
 869                                                                           \
 870 static inline T *VEC_OP (T,base,quick_push)                               \
 871      (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL)                    \
 872 {                                                                         \
 873   T *slot_;                                                               \
 874                                                                           \
 875   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 876   slot_ = &vec_->vec[vec_->num++];                                        \
 877   if (obj_)                                                               \
 878     *slot_ = *obj_;                                                       \
 879                                                                           \
 880   return slot_;                                                           \
 881 }                                                                         \
 882                                                                           \
 883 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
 884 {                                                                         \
 885   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 886   --vec_->num;                                                            \
 887 }                                                                         \
 888                                                                           \
 889 static inline void VEC_OP (T,base,truncate)                               \
 890      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 891 {                                                                         \
 892   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 893   if (vec_)                                                               \
 894     vec_->num = size_;                                                    \
 895 }                                                                         \
 896                                                                           \
 897 static inline T *VEC_OP (T,base,replace)                                  \
 898      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 899 {                                                                         \
 900   T *slot_;                                                               \
 901                                                                           \
 902   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 903   slot_ = &vec_->vec[ix_];                                                \
 904   if (obj_)                                                               \
 905     *slot_ = *obj_;                                                       \
 906                                                                           \
 907   return slot_;                                                           \
 908 }                                                                         \
 909                                                                           \
 910 static inline T *VEC_OP (T,base,quick_insert)                             \
 911      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 912 {                                                                         \
 913   T *slot_;                                                               \
 914                                                                           \
 915   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 916   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 917   slot_ = &vec_->vec[ix_];                                                \
 918   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 919   if (obj_)                                                               \
 920     *slot_ = *obj_;                                                       \
 921                                                                           \
 922   return slot_;                                                           \
 923 }                                                                         \
 924                                                                           \
 925 static inline void VEC_OP (T,base,ordered_remove)                         \
 926      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 927 {                                                                         \
 928   T *slot_;                                                               \
 929                                                                           \
 930   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 931   slot_ = &vec_->vec[ix_];                                                \
 932   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 933 }                                                                         \
 934                                                                           \
 935 static inline void VEC_OP (T,base,unordered_remove)                       \
 936      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 937 {                                                                         \
 938   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 939   vec_->vec[ix_] = vec_->vec[--vec_->num];                                \
 940 }                                                                         \
 941                                                                           \
 942 static inline void VEC_OP (T,base,block_remove)                           \
 943      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 944 {                                                                         \
 945   T *slot_;                                                               \
 946                                                                           \
 947   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 948   slot_ = &vec_->vec[ix_];                                                \
 949   vec_->num -= len_;                                                      \
 950   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 951 }                                                                         \
 952                                                                           \
 953 static inline T *VEC_OP (T,base,address)                                  \
 954      (VEC(T,base) *vec_)                                                  \
 955 {                                                                         \
 956   return vec_ ? vec_->vec : 0;                                            \
 957 }                                                                         \
 958                                                                           \
 959 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 960      (VEC(T,base) *vec_, const T *obj_,                                   \
 961       bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL)             \
 962 {                                                                         \
 963    unsigned int len_ = VEC_OP (T, base, length) (vec_);                   \
 964    unsigned int half_, middle_;                                           \
 965    unsigned int first_ = 0;                                               \
 966    while (len_ > 0)                                                       \
 967      {                                                                    \
 968         T *middle_elem_;                                                  \
 969         half_ = len_ >> 1;                                                \
 970         middle_ = first_;                                                 \
 971         middle_ += half_;                                                 \
 972         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 973         if (lessthan_ (middle_elem_, obj_))                               \
 974           {                                                               \
 975              first_ = middle_;                                            \
 976              ++first_;                                                    \
 977              len_ = len_ - half_ - 1;                                     \
 978           }                                                               \
 979         else                                                              \
 980           len_ = half_;                                                   \
 981      }                                                                    \
 982    return first_;                                                         \
 983 }
 984
 985 #define DEF_VEC_ALLOC_FUNC_O(T,A)                                         \
 986 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 987      (int alloc_ MEM_STAT_DECL)                                           \
 988 {                                                                         \
 989   return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_,            \
 990                                                  offsetof (VEC(T,A),base.vec), \
 991                                                  sizeof (T)               \
 992                                                  PASS_MEM_STAT);          \
 993 }                                                                         \
 994                                                                           \
 995 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
 996 {                                                                         \
 997   size_t len_ = vec_ ? vec_->num : 0;                                     \
 998   VEC (T,A) *new_vec_ = NULL;                                             \
 999                                                                           \
1000   if (len_)                                                               \
1001     {                                                                     \
1002       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1003                                (NULL, len_,                               \
1004                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1005                                 PASS_MEM_STAT));                          \
1006                                                                           \
1007       new_vec_->base.num = len_;                                          \
1008       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1009     }                                                                     \
1010   return new_vec_;                                                        \
1011 }                                                                         \
1012                                                                           \
1013 static inline void VEC_OP (T,A,free)                                      \
1014      (VEC(T,A) **vec_)                                                    \
1015 {                                                                         \
1016   if (*vec_)                                                              \
1017     vec_##A##_free (*vec_);                                               \
1018   *vec_ = NULL;                                                           \
1019 }                                                                         \
1020                                                                           \
1021 static inline int VEC_OP (T,A,reserve)                                    \
1022      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1023 {                                                                         \
1024   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1025                                        VEC_CHECK_PASS);                   \
1026                                                                           \
1027   if (extend)                                                             \
1028     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1029                                               offsetof (VEC(T,A),base.vec),\
1030                                               sizeof (T)                  \
1031                                               PASS_MEM_STAT);             \
1032                                                                           \
1033   return extend;                                                          \
1034 }                                                                         \
1035                                                                           \
1036 static inline int VEC_OP (T,A,reserve_exact)                              \
1037      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1038 {                                                                         \
1039   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1040                                        VEC_CHECK_PASS);                   \
1041                                                                           \
1042   if (extend)                                                             \
1043     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1044                          (*vec_, alloc_,                                  \
1045                           offsetof (VEC(T,A),base.vec),                   \
1046                           sizeof (T) PASS_MEM_STAT);                      \
1047                                                                           \
1048   return extend;                                                          \
1049 }                                                                         \
1050                                                                           \
1051 static inline void VEC_OP (T,A,safe_grow)                                 \
1052      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1053 {                                                                         \
1054   VEC_ASSERT (size_ >= 0                                                  \
1055               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1056                                                  "grow", T, A);           \
1057   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1058                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1059                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1060   VEC_BASE (*vec_)->num = size_;                                          \
1061 }                                                                         \
1062                                                                           \
1063 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1064      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1065 {                                                                         \
1066   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1067   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1068   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1069           sizeof (T) * (size_ - oldsize));                                \
1070 }                                                                         \
1071                                                                           \
1072 static inline T *VEC_OP (T,A,safe_push)                                   \
1073      (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)        \
1074 {                                                                         \
1075   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1076                                                                           \
1077   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1078 }                                                                         \
1079                                                                           \
1080 static inline T *VEC_OP (T,A,safe_insert)                                 \
1081      (VEC(T,A) **vec_, unsigned ix_, const T *obj_                        \
1082                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1083 {                                                                         \
1084   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1085                                                                           \
1086   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1087                                        VEC_CHECK_PASS);                   \
1088 }
1089
1090 #define DEF_VEC_ALLOC_FUNC_I(T,A)                                         \
1091 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1092      (int alloc_ MEM_STAT_DECL)                                           \
1093 {                                                                         \
1094   return (VEC(T,A) *) vec_##A##_o_reserve_exact                           \
1095                       (NULL, alloc_, offsetof (VEC(T,A),base.vec),        \
1096                        sizeof (T) PASS_MEM_STAT);                         \
1097 }                                                                         \
1098                                                                           \
1099 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1100 {                                                                         \
1101   size_t len_ = vec_ ? vec_->num : 0;                                     \
1102   VEC (T,A) *new_vec_ = NULL;                                             \
1103                                                                           \
1104   if (len_)                                                               \
1105     {                                                                     \
1106       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1107                                (NULL, len_,                               \
1108                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1109                                 PASS_MEM_STAT));                          \
1110                                                                           \
1111       new_vec_->base.num = len_;                                          \
1112       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1113     }                                                                     \
1114   return new_vec_;                                                        \
1115 }                                                                         \
1116                                                                           \
1117 static inline void VEC_OP (T,A,free)                                      \
1118      (VEC(T,A) **vec_)                                                    \
1119 {                                                                         \
1120   if (*vec_)                                                              \
1121     vec_##A##_free (*vec_);                                               \
1122   *vec_ = NULL;                                                           \
1123 }                                                                         \
1124                                                                           \
1125 static inline int VEC_OP (T,A,reserve)                                    \
1126      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1127 {                                                                         \
1128   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1129                                        VEC_CHECK_PASS);                   \
1130                                                                           \
1131   if (extend)                                                             \
1132     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1133                                               offsetof (VEC(T,A),base.vec),\
1134                                               sizeof (T)                  \
1135                                               PASS_MEM_STAT);             \
1136                                                                           \
1137   return extend;                                                          \
1138 }                                                                         \
1139                                                                           \
1140 static inline int VEC_OP (T,A,reserve_exact)                              \
1141      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1142 {                                                                         \
1143   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1144                                        VEC_CHECK_PASS);                   \
1145                                                                           \
1146   if (extend)                                                             \
1147     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1148                          (*vec_, alloc_, offsetof (VEC(T,A),base.vec),    \
1149                           sizeof (T) PASS_MEM_STAT);                      \
1150                                                                           \
1151   return extend;                                                          \
1152 }                                                                         \
1153                                                                           \
1154 static inline void VEC_OP (T,A,safe_grow)                                 \
1155      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1156 {                                                                         \
1157   VEC_ASSERT (size_ >= 0                                                  \
1158               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1159                                                  "grow", T, A);           \
1160   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1161                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1162                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1163   VEC_BASE (*vec_)->num = size_;                                          \
1164 }                                                                         \
1165                                                                           \
1166 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1167      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1168 {                                                                         \
1169   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1170   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1171   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1172           sizeof (T) * (size_ - oldsize));                                \
1173 }                                                                         \
1174                                                                           \
1175 static inline T *VEC_OP (T,A,safe_push)                                   \
1176      (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)         \
1177 {                                                                         \
1178   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1179                                                                           \
1180   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1181 }                                                                         \
1182                                                                           \
1183 static inline T *VEC_OP (T,A,safe_insert)                                 \
1184      (VEC(T,A) **vec_, unsigned ix_, const T obj_                         \
1185                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1186 {                                                                         \
1187   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1188                                                                           \
1189   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1190                                        VEC_CHECK_PASS);                   \
1191 }
1192
1193 #endif /* GCC_VEC_H */