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