gcc/vec.h

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