contrib/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 the
  70    reserve_exact operation.  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 RESERVE slots available.  This will
 242    create additional headroom.  Note this can cause V to be
 243    reallocated.  Returns nonzero iff reallocation actually
 244    occurred.  */
 245
 246 #define VEC_reserve(T,A,V,R)    \
 247         (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
 248
 249 /* Reserve space exactly.
 250    int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
 251
 252    Ensure that V has at least RESERVE slots available.  This will not
 253    create additional headroom.  Note this can cause V to be
 254    reallocated.  Returns nonzero iff reallocation actually
 255    occurred.  */
 256
 257 #define VEC_reserve_exact(T,A,V,R)      \
 258         (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
 259
 260 /* Push object with no reallocation
 261    T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
 262    T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
 263    T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
 264
 265    Push a new element onto the end, returns a pointer to the slot
 266    filled in. For object vectors, the new value can be NULL, in which
 267    case NO initialization is performed.  There must
 268    be sufficient space in the vector.  */
 269
 270 #define VEC_quick_push(T,V,O)   \
 271         (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
 272
 273 /* Push object with reallocation
 274    T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
 275    T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
 276    T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
 277
 278    Push a new element onto the end, returns a pointer to the slot
 279    filled in. For object vectors, the new value can be NULL, in which
 280    case NO initialization is performed.  Reallocates V, if needed.  */
 281
 282 #define VEC_safe_push(T,A,V,O)          \
 283         (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
 284
 285 /* Pop element off end
 286    T VEC_T_pop (VEC(T) *v);             // Integer
 287    T VEC_T_pop (VEC(T) *v);             // Pointer
 288    void VEC_T_pop (VEC(T) *v);          // Object
 289
 290    Pop the last element off the end. Returns the element popped, for
 291    pointer vectors.  */
 292
 293 #define VEC_pop(T,V)    (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
 294
 295 /* Truncate to specific length
 296    void VEC_T_truncate (VEC(T) *v, unsigned len);
 297
 298    Set the length as specified.  The new length must be less than or
 299    equal to the current length.  This is an O(1) operation.  */
 300
 301 #define VEC_truncate(T,V,I)             \
 302         (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
 303
 304 /* Grow to a specific length.
 305    void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
 306
 307    Grow the vector to a specific length.  The LEN must be as
 308    long or longer than the current length.  The new elements are
 309    uninitialized.  */
 310
 311 #define VEC_safe_grow(T,A,V,I)          \
 312         (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
 313
 314 /* Replace element
 315    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
 316    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
 317    T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val);  // Object
 318
 319    Replace the IXth element of V with a new value, VAL.  For pointer
 320    vectors returns the original value. For object vectors returns a
 321    pointer to the new value.  For object vectors the new value can be
 322    NULL, in which case no overwriting of the slot is actually
 323    performed.  */
 324
 325 #define VEC_replace(T,V,I,O)            \
 326         (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 327
 328 /* Insert object with no reallocation
 329    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
 330    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
 331    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
 332
 333    Insert an element, VAL, at the IXth position of V. Return a pointer
 334    to the slot created.  For vectors of object, the new value can be
 335    NULL, in which case no initialization of the inserted slot takes
 336    place. There must be sufficient space.  */
 337
 338 #define VEC_quick_insert(T,V,I,O)       \
 339         (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 340
 341 /* Insert object with reallocation
 342    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
 343    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
 344    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
 345
 346    Insert an element, VAL, at the IXth position of V. Return a pointer
 347    to the slot created.  For vectors of object, the new value can be
 348    NULL, in which case no initialization of the inserted slot takes
 349    place. Reallocate V, if necessary.  */
 350
 351 #define VEC_safe_insert(T,A,V,I,O)      \
 352         (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
 353
 354 /* Remove element retaining order
 355    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
 356    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
 357    void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
 358
 359    Remove an element from the IXth position of V. Ordering of
 360    remaining elements is preserved.  For pointer vectors returns the
 361    removed object.  This is an O(N) operation due to a memmove.  */
 362
 363 #define VEC_ordered_remove(T,V,I)       \
 364         (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 365
 366 /* Remove element destroying order
 367    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
 368    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
 369    void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
 370
 371    Remove an element from the IXth position of V. Ordering of
 372    remaining elements is destroyed.  For pointer vectors returns the
 373    removed object.  This is an O(1) operation.  */
 374
 375 #define VEC_unordered_remove(T,V,I)     \
 376         (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 377
 378 /* Remove a block of elements
 379    void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
 380
 381    Remove LEN elements starting at the IXth.  Ordering is retained.
 382    This is an O(1) operation.  */
 383
 384 #define VEC_block_remove(T,V,I,L)       \
 385         (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
 386
 387 /* Get the address of the array of elements
 388    T *VEC_T_address (VEC(T) v)
 389
 390    If you need to directly manipulate the array (for instance, you
 391    want to feed it to qsort), use this accessor.  */
 392
 393 #define VEC_address(T,V)                (VEC_OP(T,base,address)(VEC_BASE(V)))
 394
 395 /* Find the first index in the vector not less than the object.
 396    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 397                                bool (*lessthan) (const T, const T)); // Integer
 398    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 399                                bool (*lessthan) (const T, const T)); // Pointer
 400    unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
 401                                bool (*lessthan) (const T*, const T*)); // Object
 402
 403    Find the first position in which VAL could be inserted without
 404    changing the ordering of V.  LESSTHAN is a function that returns
 405    true if the first argument is strictly less than the second.  */
 406
 407 #define VEC_lower_bound(T,V,O,LT)    \
 408        (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
 409
 410 #if !IN_GENGTYPE
 411 /* Reallocate an array of elements with prefix.  */
 412 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
 413 extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
 414 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 415 extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
 416                                      MEM_STAT_DECL);
 417 extern void ggc_free (void *);
 418 #define vec_gc_free(V) ggc_free (V)
 419 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
 420 extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
 421 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 422 extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
 423                                        MEM_STAT_DECL);
 424 #define vec_heap_free(V) free (V)
 425
 426 #if ENABLE_CHECKING
 427 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
 428 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
 429 #define VEC_CHECK_PASS ,file_,line_,function_
 430
 431 #define VEC_ASSERT(EXPR,OP,T,A) \
 432   (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
 433
 434 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
 435      ATTRIBUTE_NORETURN;
 436 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
 437 #else
 438 #define VEC_CHECK_INFO
 439 #define VEC_CHECK_DECL
 440 #define VEC_CHECK_PASS
 441 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
 442 #endif
 443
 444 #define VEC(T,A) VEC_##T##_##A
 445 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
 446 #else  /* IN_GENGTYPE */
 447 #define VEC(T,A) VEC_ T _ A
 448 #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
 449 #define VEC_STRINGIFY_(X) #X
 450 #undef GTY
 451 #endif /* IN_GENGTYPE */
 452
 453 /* Base of vector type, not user visible.  */
 454 #define VEC_T(T,B)                                                        \
 455 typedef struct VEC(T,B)                                                   \
 456 {                                                                         \
 457   unsigned num;                                                           \
 458   unsigned alloc;                                                         \
 459   T vec[1];                                                               \
 460 } VEC(T,B)
 461
 462 #define VEC_T_GTY(T,B)                                                    \
 463 typedef struct VEC(T,B) GTY(())                                           \
 464 {                                                                         \
 465   unsigned num;                                                           \
 466   unsigned alloc;                                                         \
 467   T GTY ((length ("%h.num"))) vec[1];                                     \
 468 } VEC(T,B)
 469
 470 /* Derived vector type, user visible.  */
 471 #define VEC_TA_GTY(T,B,A,GTY)                                             \
 472 typedef struct VEC(T,A) GTY                                               \
 473 {                                                                         \
 474   VEC(T,B) base;                                                          \
 475 } VEC(T,A)
 476
 477 /* Convert to base type.  */
 478 #define VEC_BASE(P)  ((P) ? &(P)->base : 0)
 479
 480 /* Vector of integer-like object.  */
 481 #if IN_GENGTYPE
 482 {"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"},
 483 {"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL},
 484 #else
 485 #define DEF_VEC_I(T)                                                      \
 486 static inline void VEC_OP (T,must_be,integral_type) (void)                \
 487 {                                                                         \
 488   (void)~(T)0;                                                            \
 489 }                                                                         \
 490                                                                           \
 491 VEC_T(T,base);                                                            \
 492 VEC_TA_GTY(T,base,none,);                                                 \
 493 DEF_VEC_FUNC_P(T)                                                         \
 494 struct vec_swallow_trailing_semi
 495 #define DEF_VEC_ALLOC_I(T,A)                                              \
 496 VEC_TA_GTY(T,base,A,);                                                    \
 497 DEF_VEC_ALLOC_FUNC_I(T,A)                                                 \
 498 struct vec_swallow_trailing_semi
 499 #endif
 500
 501 /* Vector of pointer to object.  */
 502 #if IN_GENGTYPE
 503 {"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
 504 {"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL},
 505 #else
 506 #define DEF_VEC_P(T)                                                      \
 507 static inline void VEC_OP (T,must_be,pointer_type) (void)                 \
 508 {                                                                         \
 509   (void)((T)1 == (void *)1);                                              \
 510 }                                                                         \
 511                                                                           \
 512 VEC_T_GTY(T,base);                                                        \
 513 VEC_TA_GTY(T,base,none,);                                                 \
 514 DEF_VEC_FUNC_P(T)                                                         \
 515 struct vec_swallow_trailing_semi
 516 #define DEF_VEC_ALLOC_P(T,A)                                              \
 517 VEC_TA_GTY(T,base,A,);                                                    \
 518 DEF_VEC_ALLOC_FUNC_P(T,A)                                                 \
 519 struct vec_swallow_trailing_semi
 520 #endif
 521
 522 #define DEF_VEC_FUNC_P(T)                                                 \
 523 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 524 {                                                                         \
 525   return vec_ ? vec_->num : 0;                                            \
 526 }                                                                         \
 527                                                                           \
 528 static inline T VEC_OP (T,base,last)                                      \
 529      (const VEC(T,base) *vec_ VEC_CHECK_DECL)                             \
 530 {                                                                         \
 531   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 532                                                                           \
 533   return vec_->vec[vec_->num - 1];                                        \
 534 }                                                                         \
 535                                                                           \
 536 static inline T VEC_OP (T,base,index)                                     \
 537      (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)               \
 538 {                                                                         \
 539   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 540                                                                           \
 541   return vec_->vec[ix_];                                                  \
 542 }                                                                         \
 543                                                                           \
 544 static inline int VEC_OP (T,base,iterate)                                 \
 545      (const VEC(T,base) *vec_, unsigned ix_, T *ptr)                      \
 546 {                                                                         \
 547   if (vec_ && ix_ < vec_->num)                                            \
 548     {                                                                     \
 549       *ptr = vec_->vec[ix_];                                              \
 550       return 1;                                                           \
 551     }                                                                     \
 552   else                                                                    \
 553     {                                                                     \
 554       *ptr = 0;                                                           \
 555       return 0;                                                           \
 556     }                                                                     \
 557 }                                                                         \
 558                                                                           \
 559 static inline size_t VEC_OP (T,base,embedded_size)                        \
 560      (int alloc_)                                                         \
 561 {                                                                         \
 562   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 563 }                                                                         \
 564                                                                           \
 565 static inline void VEC_OP (T,base,embedded_init)                          \
 566      (VEC(T,base) *vec_, int alloc_)                                      \
 567 {                                                                         \
 568   vec_->num = 0;                                                          \
 569   vec_->alloc = alloc_;                                                   \
 570 }                                                                         \
 571                                                                           \
 572 static inline int VEC_OP (T,base,space)                                   \
 573      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 574 {                                                                         \
 575   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 576   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 577 }                                                                         \
 578                                                                           \
 579 static inline T *VEC_OP (T,base,quick_push)                               \
 580      (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)                           \
 581 {                                                                         \
 582   T *slot_;                                                               \
 583                                                                           \
 584   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 585   slot_ = &vec_->vec[vec_->num++];                                        \
 586   *slot_ = obj_;                                                          \
 587                                                                           \
 588   return slot_;                                                           \
 589 }                                                                         \
 590                                                                           \
 591 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)    \
 592 {                                                                         \
 593   T obj_;                                                                 \
 594                                                                           \
 595   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 596   obj_ = vec_->vec[--vec_->num];                                          \
 597                                                                           \
 598   return obj_;                                                            \
 599 }                                                                         \
 600                                                                           \
 601 static inline void VEC_OP (T,base,truncate)                               \
 602      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 603 {                                                                         \
 604   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 605   if (vec_)                                                               \
 606     vec_->num = size_;                                                    \
 607 }                                                                         \
 608                                                                           \
 609 static inline T VEC_OP (T,base,replace)                                   \
 610      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 611 {                                                                         \
 612   T old_obj_;                                                             \
 613                                                                           \
 614   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 615   old_obj_ = vec_->vec[ix_];                                              \
 616   vec_->vec[ix_] = obj_;                                                  \
 617                                                                           \
 618   return old_obj_;                                                        \
 619 }                                                                         \
 620                                                                           \
 621 static inline T *VEC_OP (T,base,quick_insert)                             \
 622      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 623 {                                                                         \
 624   T *slot_;                                                               \
 625                                                                           \
 626   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 627   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 628   slot_ = &vec_->vec[ix_];                                                \
 629   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 630   *slot_ = obj_;                                                          \
 631                                                                           \
 632   return slot_;                                                           \
 633 }                                                                         \
 634                                                                           \
 635 static inline T VEC_OP (T,base,ordered_remove)                            \
 636      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 637 {                                                                         \
 638   T *slot_;                                                               \
 639   T obj_;                                                                 \
 640                                                                           \
 641   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 642   slot_ = &vec_->vec[ix_];                                                \
 643   obj_ = *slot_;                                                          \
 644   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 645                                                                           \
 646   return obj_;                                                            \
 647 }                                                                         \
 648                                                                           \
 649 static inline T VEC_OP (T,base,unordered_remove)                          \
 650      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 651 {                                                                         \
 652   T *slot_;                                                               \
 653   T obj_;                                                                 \
 654                                                                           \
 655   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 656   slot_ = &vec_->vec[ix_];                                                \
 657   obj_ = *slot_;                                                          \
 658   *slot_ = vec_->vec[--vec_->num];                                        \
 659                                                                           \
 660   return obj_;                                                            \
 661 }                                                                         \
 662                                                                           \
 663 static inline void VEC_OP (T,base,block_remove)                           \
 664      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 665 {                                                                         \
 666   T *slot_;                                                               \
 667                                                                           \
 668   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 669   slot_ = &vec_->vec[ix_];                                                \
 670   vec_->num -= len_;                                                      \
 671   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 672 }                                                                         \
 673                                                                           \
 674 static inline T *VEC_OP (T,base,address)                                  \
 675      (VEC(T,base) *vec_)                                                  \
 676 {                                                                         \
 677   return vec_ ? vec_->vec : 0;                                            \
 678 }                                                                         \
 679                                                                           \
 680 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 681      (VEC(T,base) *vec_, const T obj_,                                    \
 682       bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)                 \
 683 {                                                                         \
 684    unsigned int len_ = VEC_OP (T,base, length) (vec_);                    \
 685    unsigned int half_, middle_;                                           \
 686    unsigned int first_ = 0;                                               \
 687    while (len_ > 0)                                                       \
 688      {                                                                    \
 689         T middle_elem_;                                                   \
 690         half_ = len_ >> 1;                                                \
 691         middle_ = first_;                                                 \
 692         middle_ += half_;                                                 \
 693         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 694         if (lessthan_ (middle_elem_, obj_))                               \
 695           {                                                               \
 696              first_ = middle_;                                            \
 697              ++first_;                                                    \
 698              len_ = len_ - half_ - 1;                                     \
 699           }                                                               \
 700         else                                                              \
 701           len_ = half_;                                                   \
 702      }                                                                    \
 703    return first_;                                                         \
 704 }
 705
 706 #define DEF_VEC_ALLOC_FUNC_P(T,A)                                         \
 707 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 708      (int alloc_ MEM_STAT_DECL)                                           \
 709 {                                                                         \
 710   return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_             \
 711                                                  PASS_MEM_STAT);          \
 712 }                                                                         \
 713                                                                           \
 714 static inline void VEC_OP (T,A,free)                                      \
 715      (VEC(T,A) **vec_)                                                    \
 716 {                                                                         \
 717   if (*vec_)                                                              \
 718     vec_##A##_free (*vec_);                                               \
 719   *vec_ = NULL;                                                           \
 720 }                                                                         \
 721                                                                           \
 722 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
 723 {                                                                         \
 724   size_t len_ = vec_ ? vec_->num : 0;                                     \
 725   VEC (T,A) *new_vec_ = NULL;                                             \
 726                                                                           \
 727   if (len_)                                                               \
 728     {                                                                     \
 729       new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact                  \
 730                                (NULL, len_ PASS_MEM_STAT));               \
 731                                                                           \
 732       new_vec_->base.num = len_;                                          \
 733       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
 734     }                                                                     \
 735   return new_vec_;                                                        \
 736 }                                                                         \
 737                                                                           \
 738 static inline int VEC_OP (T,A,reserve)                                    \
 739      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 740 {                                                                         \
 741   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 742                                        VEC_CHECK_PASS);                   \
 743                                                                           \
 744   if (extend)                                                             \
 745     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
 746                                                                           \
 747   return extend;                                                          \
 748 }                                                                         \
 749                                                                           \
 750 static inline int VEC_OP (T,A,reserve_exact)                              \
 751      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 752 {                                                                         \
 753   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 754                                        VEC_CHECK_PASS);                   \
 755                                                                           \
 756   if (extend)                                                             \
 757     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_         \
 758                                                     PASS_MEM_STAT);       \
 759                                                                           \
 760   return extend;                                                          \
 761 }                                                                         \
 762                                                                           \
 763 static inline void VEC_OP (T,A,safe_grow)                                 \
 764      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 765 {                                                                         \
 766   VEC_ASSERT (size_ >= 0                                                  \
 767               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
 768                                                  "grow", T, A);           \
 769   VEC_OP (T,A,reserve_exact) (vec_,                                       \
 770                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
 771                               VEC_CHECK_PASS PASS_MEM_STAT);              \
 772   VEC_BASE (*vec_)->num = size_;                                          \
 773 }                                                                         \
 774                                                                           \
 775 static inline T *VEC_OP (T,A,safe_push)                                   \
 776      (VEC(T,A) **vec_, 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_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
 781 }                                                                         \
 782                                                                           \
 783 static inline T *VEC_OP (T,A,safe_insert)                                 \
 784      (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
 785 {                                                                         \
 786   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 787                                                                           \
 788   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
 789                                        VEC_CHECK_PASS);                   \
 790 }
 791
 792 /* Vector of object.  */
 793 #if IN_GENGTYPE
 794 {"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"},
 795 {"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL},
 796 #else
 797 #define DEF_VEC_O(T)                                                      \
 798 VEC_T_GTY(T,base);                                                        \
 799 VEC_TA_GTY(T,base,none,);                                                 \
 800 DEF_VEC_FUNC_O(T)                                                         \
 801 struct vec_swallow_trailing_semi
 802 #define DEF_VEC_ALLOC_O(T,A)                                              \
 803 VEC_TA_GTY(T,base,A,);                                                    \
 804 DEF_VEC_ALLOC_FUNC_O(T,A)                                                 \
 805 struct vec_swallow_trailing_semi
 806 #endif
 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 T *VEC_OP (T,A,safe_push)                                   \
1058      (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)        \
1059 {                                                                         \
1060   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1061                                                                           \
1062   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1063 }                                                                         \
1064                                                                           \
1065 static inline T *VEC_OP (T,A,safe_insert)                                 \
1066      (VEC(T,A) **vec_, unsigned ix_, const T *obj_                        \
1067                 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_insert) (VEC_BASE(*vec_), ix_, obj_         \
1072                                        VEC_CHECK_PASS);                   \
1073 }
1074
1075 #define DEF_VEC_ALLOC_FUNC_I(T,A)                                         \
1076 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1077      (int alloc_ MEM_STAT_DECL)                                           \
1078 {                                                                         \
1079   return (VEC(T,A) *) vec_##A##_o_reserve_exact                           \
1080                       (NULL, alloc_, offsetof (VEC(T,A),base.vec),        \
1081                        sizeof (T) PASS_MEM_STAT);                         \
1082 }                                                                         \
1083                                                                           \
1084 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1085 {                                                                         \
1086   size_t len_ = vec_ ? vec_->num : 0;                                     \
1087   VEC (T,A) *new_vec_ = NULL;                                             \
1088                                                                           \
1089   if (len_)                                                               \
1090     {                                                                     \
1091       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1092                                (NULL, len_,                               \
1093                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1094                                 PASS_MEM_STAT));                          \
1095                                                                           \
1096       new_vec_->base.num = len_;                                          \
1097       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1098     }                                                                     \
1099   return new_vec_;                                                        \
1100 }                                                                         \
1101                                                                           \
1102 static inline void VEC_OP (T,A,free)                                      \
1103      (VEC(T,A) **vec_)                                                    \
1104 {                                                                         \
1105   if (*vec_)                                                              \
1106     vec_##A##_free (*vec_);                                               \
1107   *vec_ = NULL;                                                           \
1108 }                                                                         \
1109                                                                           \
1110 static inline int VEC_OP (T,A,reserve)                                    \
1111      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1112 {                                                                         \
1113   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1114                                        VEC_CHECK_PASS);                   \
1115                                                                           \
1116   if (extend)                                                             \
1117     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1118                                               offsetof (VEC(T,A),base.vec),\
1119                                               sizeof (T)                  \
1120                                               PASS_MEM_STAT);             \
1121                                                                           \
1122   return extend;                                                          \
1123 }                                                                         \
1124                                                                           \
1125 static inline int VEC_OP (T,A,reserve_exact)                              \
1126      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1127 {                                                                         \
1128   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1129                                        VEC_CHECK_PASS);                   \
1130                                                                           \
1131   if (extend)                                                             \
1132     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1133                          (*vec_, alloc_, offsetof (VEC(T,A),base.vec),    \
1134                           sizeof (T) PASS_MEM_STAT);                      \
1135                                                                           \
1136   return extend;                                                          \
1137 }                                                                         \
1138                                                                           \
1139 static inline void VEC_OP (T,A,safe_grow)                                 \
1140      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1141 {                                                                         \
1142   VEC_ASSERT (size_ >= 0                                                  \
1143               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1144                                                  "grow", T, A);           \
1145   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1146                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1147                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1148   VEC_BASE (*vec_)->num = size_;                                          \
1149 }                                                                         \
1150                                                                           \
1151 static inline T *VEC_OP (T,A,safe_push)                                   \
1152      (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)         \
1153 {                                                                         \
1154   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1155                                                                           \
1156   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1157 }                                                                         \
1158                                                                           \
1159 static inline T *VEC_OP (T,A,safe_insert)                                 \
1160      (VEC(T,A) **vec_, unsigned ix_, const T obj_                         \
1161                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1162 {                                                                         \
1163   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1164                                                                           \
1165   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1166                                        VEC_CHECK_PASS);                   \
1167 }
1168
1169 #endif /* GCC_VEC_H */