gcc/vec.h

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Nathan Sidwell <nathan@codesourcery.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 /* Grow to a specific length.
 315    void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
 316
 317    Grow the vector to a specific length.  The LEN must be as
 318    long or longer than the current length.  The new elements are
 319    initialized to zero.  */
 320
 321 #define VEC_safe_grow_cleared(T,A,V,I)          \
 322         (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
 323
 324 /* Replace element
 325    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
 326    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
 327    T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val);  // Object
 328
 329    Replace the IXth element of V with a new value, VAL.  For pointer
 330    vectors returns the original value. For object vectors returns a
 331    pointer to the new value.  For object vectors the new value can be
 332    NULL, in which case no overwriting of the slot is actually
 333    performed.  */
 334
 335 #define VEC_replace(T,V,I,O)            \
 336         (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 337
 338 /* Insert object with no reallocation
 339    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
 340    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
 341    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
 342
 343    Insert an element, VAL, at the IXth position of V. Return a pointer
 344    to the slot created.  For vectors of object, the new value can be
 345    NULL, in which case no initialization of the inserted slot takes
 346    place. There must be sufficient space.  */
 347
 348 #define VEC_quick_insert(T,V,I,O)       \
 349         (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 350
 351 /* Insert object with reallocation
 352    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
 353    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
 354    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
 355
 356    Insert an element, VAL, at the IXth position of V. Return a pointer
 357    to the slot created.  For vectors of object, the new value can be
 358    NULL, in which case no initialization of the inserted slot takes
 359    place. Reallocate V, if necessary.  */
 360
 361 #define VEC_safe_insert(T,A,V,I,O)      \
 362         (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
 363
 364 /* Remove element retaining order
 365    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
 366    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
 367    void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
 368
 369    Remove an element from the IXth position of V. Ordering of
 370    remaining elements is preserved.  For pointer vectors returns the
 371    removed object.  This is an O(N) operation due to a memmove.  */
 372
 373 #define VEC_ordered_remove(T,V,I)       \
 374         (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 375
 376 /* Remove element destroying order
 377    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
 378    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
 379    void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
 380
 381    Remove an element from the IXth position of V. Ordering of
 382    remaining elements is destroyed.  For pointer vectors returns the
 383    removed object.  This is an O(1) operation.  */
 384
 385 #define VEC_unordered_remove(T,V,I)     \
 386         (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 387
 388 /* Remove a block of elements
 389    void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
 390
 391    Remove LEN elements starting at the IXth.  Ordering is retained.
 392    This is an O(1) operation.  */
 393
 394 #define VEC_block_remove(T,V,I,L)       \
 395         (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
 396
 397 /* Get the address of the array of elements
 398    T *VEC_T_address (VEC(T) v)
 399
 400    If you need to directly manipulate the array (for instance, you
 401    want to feed it to qsort), use this accessor.  */
 402
 403 #define VEC_address(T,V)                (VEC_OP(T,base,address)(VEC_BASE(V)))
 404
 405 /* Find the first index in the vector not less than the object.
 406    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 407                                bool (*lessthan) (const T, const T)); // Integer
 408    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 409                                bool (*lessthan) (const T, const T)); // Pointer
 410    unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
 411                                bool (*lessthan) (const T*, const T*)); // Object
 412
 413    Find the first position in which VAL could be inserted without
 414    changing the ordering of V.  LESSTHAN is a function that returns
 415    true if the first argument is strictly less than the second.  */
 416
 417 #define VEC_lower_bound(T,V,O,LT)    \
 418        (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
 419
 420 /* Reallocate an array of elements with prefix.  */
 421 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
 422 extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
 423 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 424 extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
 425                                      MEM_STAT_DECL);
 426 extern void ggc_free (void *);
 427 #define vec_gc_free(V) ggc_free (V)
 428 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
 429 extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
 430 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 431 extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
 432                                        MEM_STAT_DECL);
 433 extern void dump_vec_loc_statistics (void);
 434 #ifdef GATHER_STATISTICS
 435 void vec_heap_free (void *);
 436 #else
 437 #define vec_heap_free(V) free (V)
 438 #endif
 439
 440 #if ENABLE_CHECKING
 441 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
 442 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
 443 #define VEC_CHECK_PASS ,file_,line_,function_
 444
 445 #define VEC_ASSERT(EXPR,OP,T,A) \
 446   (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
 447
 448 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
 449      ATTRIBUTE_NORETURN;
 450 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
 451 #else
 452 #define VEC_CHECK_INFO
 453 #define VEC_CHECK_DECL
 454 #define VEC_CHECK_PASS
 455 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
 456 #endif
 457
 458 /* Note: gengtype has hardwired knowledge of the expansions of the
 459    VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros.  If you change the
 460    expansions of these macros you may need to change gengtype too.  */
 461
 462 #define VEC(T,A) VEC_##T##_##A
 463 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
 464
 465 /* Base of vector type, not user visible.  */
 466 #define VEC_T(T,B)                                                        \
 467 typedef struct VEC(T,B)                                                   \
 468 {                                                                         \
 469   unsigned num;                                                           \
 470   unsigned alloc;                                                         \
 471   T vec[1];                                                               \
 472 } VEC(T,B)
 473
 474 #define VEC_T_GTY(T,B)                                                    \
 475 typedef struct GTY(()) VEC(T,B)                                           \
 476 {                                                                         \
 477   unsigned num;                                                           \
 478   unsigned alloc;                                                         \
 479   T GTY ((length ("%h.num"))) vec[1];                                     \
 480 } VEC(T,B)
 481
 482 /* Derived vector type, user visible.  */
 483 #define VEC_TA_GTY(T,B,A,GTY)                                             \
 484 typedef struct GTY VEC(T,A)                                               \
 485 {                                                                         \
 486   VEC(T,B) base;                                                          \
 487 } VEC(T,A)
 488
 489 #define VEC_TA(T,B,A)                                                     \
 490 typedef struct VEC(T,A)                                                   \
 491 {                                                                         \
 492   VEC(T,B) base;                                                          \
 493 } VEC(T,A)
 494
 495 /* Convert to base type.  */
 496 #define VEC_BASE(P)  ((P) ? &(P)->base : 0)
 497
 498 /* Vector of integer-like object.  */
 499 #define DEF_VEC_I(T)                                                      \
 500 static inline void VEC_OP (T,must_be,integral_type) (void)                \
 501 {                                                                         \
 502   (void)~(T)0;                                                            \
 503 }                                                                         \
 504                                                                           \
 505 VEC_T(T,base);                                                            \
 506 VEC_TA(T,base,none);                                                      \
 507 DEF_VEC_FUNC_P(T)                                                         \
 508 struct vec_swallow_trailing_semi
 509 #define DEF_VEC_ALLOC_I(T,A)                                              \
 510 VEC_TA(T,base,A);                                                         \
 511 DEF_VEC_ALLOC_FUNC_I(T,A)                                                 \
 512 DEF_VEC_NONALLOC_FUNCS_I(T,A)                                             \
 513 struct vec_swallow_trailing_semi
 514
 515 /* Vector of pointer to object.  */
 516 #define DEF_VEC_P(T)                                                      \
 517 static inline void VEC_OP (T,must_be,pointer_type) (void)                 \
 518 {                                                                         \
 519   (void)((T)1 == (void *)1);                                              \
 520 }                                                                         \
 521                                                                           \
 522 VEC_T_GTY(T,base);                                                        \
 523 VEC_TA(T,base,none);                                                      \
 524 DEF_VEC_FUNC_P(T)                                                         \
 525 struct vec_swallow_trailing_semi
 526 #define DEF_VEC_ALLOC_P(T,A)                                              \
 527 VEC_TA(T,base,A);                                                         \
 528 DEF_VEC_ALLOC_FUNC_P(T,A)                                                 \
 529 DEF_VEC_NONALLOC_FUNCS_P(T,A)                                             \
 530 struct vec_swallow_trailing_semi
 531
 532 #define DEF_VEC_FUNC_P(T)                                                 \
 533 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 534 {                                                                         \
 535   return vec_ ? vec_->num : 0;                                            \
 536 }                                                                         \
 537                                                                           \
 538 static inline T VEC_OP (T,base,last)                                      \
 539      (const VEC(T,base) *vec_ VEC_CHECK_DECL)                             \
 540 {                                                                         \
 541   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 542                                                                           \
 543   return vec_->vec[vec_->num - 1];                                        \
 544 }                                                                         \
 545                                                                           \
 546 static inline T VEC_OP (T,base,index)                                     \
 547      (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)               \
 548 {                                                                         \
 549   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 550                                                                           \
 551   return vec_->vec[ix_];                                                  \
 552 }                                                                         \
 553                                                                           \
 554 static inline int VEC_OP (T,base,iterate)                                 \
 555      (const VEC(T,base) *vec_, unsigned ix_, T *ptr)                      \
 556 {                                                                         \
 557   if (vec_ && ix_ < vec_->num)                                            \
 558     {                                                                     \
 559       *ptr = vec_->vec[ix_];                                              \
 560       return 1;                                                           \
 561     }                                                                     \
 562   else                                                                    \
 563     {                                                                     \
 564       *ptr = (T) 0;                                                       \
 565       return 0;                                                           \
 566     }                                                                     \
 567 }                                                                         \
 568                                                                           \
 569 static inline size_t VEC_OP (T,base,embedded_size)                        \
 570      (int alloc_)                                                         \
 571 {                                                                         \
 572   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 573 }                                                                         \
 574                                                                           \
 575 static inline void VEC_OP (T,base,embedded_init)                          \
 576      (VEC(T,base) *vec_, int alloc_)                                      \
 577 {                                                                         \
 578   vec_->num = 0;                                                          \
 579   vec_->alloc = alloc_;                                                   \
 580 }                                                                         \
 581                                                                           \
 582 static inline int VEC_OP (T,base,space)                                   \
 583      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 584 {                                                                         \
 585   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 586   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 587 }                                                                         \
 588                                                                           \
 589 static inline T *VEC_OP (T,base,quick_push)                               \
 590      (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)                           \
 591 {                                                                         \
 592   T *slot_;                                                               \
 593                                                                           \
 594   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 595   slot_ = &vec_->vec[vec_->num++];                                        \
 596   *slot_ = obj_;                                                          \
 597                                                                           \
 598   return slot_;                                                           \
 599 }                                                                         \
 600                                                                           \
 601 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)    \
 602 {                                                                         \
 603   T obj_;                                                                 \
 604                                                                           \
 605   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 606   obj_ = vec_->vec[--vec_->num];                                          \
 607                                                                           \
 608   return obj_;                                                            \
 609 }                                                                         \
 610                                                                           \
 611 static inline void VEC_OP (T,base,truncate)                               \
 612      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 613 {                                                                         \
 614   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 615   if (vec_)                                                               \
 616     vec_->num = size_;                                                    \
 617 }                                                                         \
 618                                                                           \
 619 static inline T VEC_OP (T,base,replace)                                   \
 620      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 621 {                                                                         \
 622   T old_obj_;                                                             \
 623                                                                           \
 624   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 625   old_obj_ = vec_->vec[ix_];                                              \
 626   vec_->vec[ix_] = obj_;                                                  \
 627                                                                           \
 628   return old_obj_;                                                        \
 629 }                                                                         \
 630                                                                           \
 631 static inline T *VEC_OP (T,base,quick_insert)                             \
 632      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 633 {                                                                         \
 634   T *slot_;                                                               \
 635                                                                           \
 636   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 637   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 638   slot_ = &vec_->vec[ix_];                                                \
 639   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 640   *slot_ = obj_;                                                          \
 641                                                                           \
 642   return slot_;                                                           \
 643 }                                                                         \
 644                                                                           \
 645 static inline T VEC_OP (T,base,ordered_remove)                            \
 646      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 647 {                                                                         \
 648   T *slot_;                                                               \
 649   T obj_;                                                                 \
 650                                                                           \
 651   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 652   slot_ = &vec_->vec[ix_];                                                \
 653   obj_ = *slot_;                                                          \
 654   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 655                                                                           \
 656   return obj_;                                                            \
 657 }                                                                         \
 658                                                                           \
 659 static inline T VEC_OP (T,base,unordered_remove)                          \
 660      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 661 {                                                                         \
 662   T *slot_;                                                               \
 663   T obj_;                                                                 \
 664                                                                           \
 665   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 666   slot_ = &vec_->vec[ix_];                                                \
 667   obj_ = *slot_;                                                          \
 668   *slot_ = vec_->vec[--vec_->num];                                        \
 669                                                                           \
 670   return obj_;                                                            \
 671 }                                                                         \
 672                                                                           \
 673 static inline void VEC_OP (T,base,block_remove)                           \
 674      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 675 {                                                                         \
 676   T *slot_;                                                               \
 677                                                                           \
 678   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 679   slot_ = &vec_->vec[ix_];                                                \
 680   vec_->num -= len_;                                                      \
 681   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 682 }                                                                         \
 683                                                                           \
 684 static inline T *VEC_OP (T,base,address)                                  \
 685      (VEC(T,base) *vec_)                                                  \
 686 {                                                                         \
 687   return vec_ ? vec_->vec : 0;                                            \
 688 }                                                                         \
 689                                                                           \
 690 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 691      (VEC(T,base) *vec_, const T obj_,                                    \
 692       bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)                 \
 693 {                                                                         \
 694    unsigned int len_ = VEC_OP (T,base, length) (vec_);                    \
 695    unsigned int half_, middle_;                                           \
 696    unsigned int first_ = 0;                                               \
 697    while (len_ > 0)                                                       \
 698      {                                                                    \
 699         T middle_elem_;                                                   \
 700         half_ = len_ >> 1;                                                \
 701         middle_ = first_;                                                 \
 702         middle_ += half_;                                                 \
 703         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 704         if (lessthan_ (middle_elem_, obj_))                               \
 705           {                                                               \
 706              first_ = middle_;                                            \
 707              ++first_;                                                    \
 708              len_ = len_ - half_ - 1;                                     \
 709           }                                                               \
 710         else                                                              \
 711           len_ = half_;                                                   \
 712      }                                                                    \
 713    return first_;                                                         \
 714 }
 715
 716 #define DEF_VEC_ALLOC_FUNC_P(T,A)                                         \
 717 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 718      (int alloc_ MEM_STAT_DECL)                                           \
 719 {                                                                         \
 720   return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_             \
 721                                                  PASS_MEM_STAT);          \
 722 }
 723
 724
 725 #define DEF_VEC_NONALLOC_FUNCS_P(T,A)                                     \
 726 static inline void VEC_OP (T,A,free)                                      \
 727      (VEC(T,A) **vec_)                                                    \
 728 {                                                                         \
 729   if (*vec_)                                                              \
 730     vec_##A##_free (*vec_);                                               \
 731   *vec_ = NULL;                                                           \
 732 }                                                                         \
 733                                                                           \
 734 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
 735 {                                                                         \
 736   size_t len_ = vec_ ? vec_->num : 0;                                     \
 737   VEC (T,A) *new_vec_ = NULL;                                             \
 738                                                                           \
 739   if (len_)                                                               \
 740     {                                                                     \
 741       new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact                  \
 742                                (NULL, len_ PASS_MEM_STAT));               \
 743                                                                           \
 744       new_vec_->base.num = len_;                                          \
 745       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
 746     }                                                                     \
 747   return new_vec_;                                                        \
 748 }                                                                         \
 749                                                                           \
 750 static inline int VEC_OP (T,A,reserve)                                    \
 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 (*vec_, alloc_ PASS_MEM_STAT); \
 758                                                                           \
 759   return extend;                                                          \
 760 }                                                                         \
 761                                                                           \
 762 static inline int VEC_OP (T,A,reserve_exact)                              \
 763      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 764 {                                                                         \
 765   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 766                                        VEC_CHECK_PASS);                   \
 767                                                                           \
 768   if (extend)                                                             \
 769     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_         \
 770                                                     PASS_MEM_STAT);       \
 771                                                                           \
 772   return extend;                                                          \
 773 }                                                                         \
 774                                                                           \
 775 static inline void VEC_OP (T,A,safe_grow)                                 \
 776      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 777 {                                                                         \
 778   VEC_ASSERT (size_ >= 0                                                  \
 779               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
 780                                                  "grow", T, A);           \
 781   VEC_OP (T,A,reserve_exact) (vec_,                                       \
 782                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
 783                               VEC_CHECK_PASS PASS_MEM_STAT);              \
 784   VEC_BASE (*vec_)->num = size_;                                          \
 785 }                                                                         \
 786                                                                           \
 787 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
 788      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 789 {                                                                         \
 790   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
 791   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
 792   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
 793           sizeof (T) * (size_ - oldsize));                                \
 794 }                                                                         \
 795                                                                           \
 796 static inline T *VEC_OP (T,A,safe_push)                                   \
 797      (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)               \
 798 {                                                                         \
 799   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 800                                                                           \
 801   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
 802 }                                                                         \
 803                                                                           \
 804 static inline T *VEC_OP (T,A,safe_insert)                                 \
 805      (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
 806 {                                                                         \
 807   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 808                                                                           \
 809   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
 810                                        VEC_CHECK_PASS);                   \
 811 }
 812
 813 /* Vector of object.  */
 814 #define DEF_VEC_O(T)                                                      \
 815 VEC_T_GTY(T,base);                                                        \
 816 VEC_TA(T,base,none);                                              \
 817 DEF_VEC_FUNC_O(T)                                                         \
 818 struct vec_swallow_trailing_semi
 819 #define DEF_VEC_ALLOC_O(T,A)                                              \
 820 VEC_TA(T,base,A);                                                         \
 821 DEF_VEC_ALLOC_FUNC_O(T,A)                                                 \
 822 DEF_VEC_NONALLOC_FUNCS_O(T,A)                                             \
 823 struct vec_swallow_trailing_semi
 824
 825 #define DEF_VEC_FUNC_O(T)                                                 \
 826 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 827 {                                                                         \
 828   return vec_ ? vec_->num : 0;                                            \
 829 }                                                                         \
 830                                                                           \
 831 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL)  \
 832 {                                                                         \
 833   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 834                                                                           \
 835   return &vec_->vec[vec_->num - 1];                                       \
 836 }                                                                         \
 837                                                                           \
 838 static inline T *VEC_OP (T,base,index)                                    \
 839      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 840 {                                                                         \
 841   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 842                                                                           \
 843   return &vec_->vec[ix_];                                                 \
 844 }                                                                         \
 845                                                                           \
 846 static inline int VEC_OP (T,base,iterate)                                 \
 847      (VEC(T,base) *vec_, unsigned ix_, T **ptr)                           \
 848 {                                                                         \
 849   if (vec_ && ix_ < vec_->num)                                            \
 850     {                                                                     \
 851       *ptr = &vec_->vec[ix_];                                             \
 852       return 1;                                                           \
 853     }                                                                     \
 854   else                                                                    \
 855     {                                                                     \
 856       *ptr = 0;                                                           \
 857       return 0;                                                           \
 858     }                                                                     \
 859 }                                                                         \
 860                                                                           \
 861 static inline size_t VEC_OP (T,base,embedded_size)                        \
 862      (int alloc_)                                                         \
 863 {                                                                         \
 864   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 865 }                                                                         \
 866                                                                           \
 867 static inline void VEC_OP (T,base,embedded_init)                          \
 868      (VEC(T,base) *vec_, int alloc_)                                      \
 869 {                                                                         \
 870   vec_->num = 0;                                                          \
 871   vec_->alloc = alloc_;                                                   \
 872 }                                                                         \
 873                                                                           \
 874 static inline int VEC_OP (T,base,space)                                   \
 875      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 876 {                                                                         \
 877   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 878   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 879 }                                                                         \
 880                                                                           \
 881 static inline T *VEC_OP (T,base,quick_push)                               \
 882      (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL)                    \
 883 {                                                                         \
 884   T *slot_;                                                               \
 885                                                                           \
 886   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 887   slot_ = &vec_->vec[vec_->num++];                                        \
 888   if (obj_)                                                               \
 889     *slot_ = *obj_;                                                       \
 890                                                                           \
 891   return slot_;                                                           \
 892 }                                                                         \
 893                                                                           \
 894 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
 895 {                                                                         \
 896   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 897   --vec_->num;                                                            \
 898 }                                                                         \
 899                                                                           \
 900 static inline void VEC_OP (T,base,truncate)                               \
 901      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 902 {                                                                         \
 903   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 904   if (vec_)                                                               \
 905     vec_->num = size_;                                                    \
 906 }                                                                         \
 907                                                                           \
 908 static inline T *VEC_OP (T,base,replace)                                  \
 909      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 910 {                                                                         \
 911   T *slot_;                                                               \
 912                                                                           \
 913   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 914   slot_ = &vec_->vec[ix_];                                                \
 915   if (obj_)                                                               \
 916     *slot_ = *obj_;                                                       \
 917                                                                           \
 918   return slot_;                                                           \
 919 }                                                                         \
 920                                                                           \
 921 static inline T *VEC_OP (T,base,quick_insert)                             \
 922      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 923 {                                                                         \
 924   T *slot_;                                                               \
 925                                                                           \
 926   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 927   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 928   slot_ = &vec_->vec[ix_];                                                \
 929   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 930   if (obj_)                                                               \
 931     *slot_ = *obj_;                                                       \
 932                                                                           \
 933   return slot_;                                                           \
 934 }                                                                         \
 935                                                                           \
 936 static inline void VEC_OP (T,base,ordered_remove)                         \
 937      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 938 {                                                                         \
 939   T *slot_;                                                               \
 940                                                                           \
 941   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 942   slot_ = &vec_->vec[ix_];                                                \
 943   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 944 }                                                                         \
 945                                                                           \
 946 static inline void VEC_OP (T,base,unordered_remove)                       \
 947      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 948 {                                                                         \
 949   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 950   vec_->vec[ix_] = vec_->vec[--vec_->num];                                \
 951 }                                                                         \
 952                                                                           \
 953 static inline void VEC_OP (T,base,block_remove)                           \
 954      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 955 {                                                                         \
 956   T *slot_;                                                               \
 957                                                                           \
 958   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 959   slot_ = &vec_->vec[ix_];                                                \
 960   vec_->num -= len_;                                                      \
 961   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 962 }                                                                         \
 963                                                                           \
 964 static inline T *VEC_OP (T,base,address)                                  \
 965      (VEC(T,base) *vec_)                                                  \
 966 {                                                                         \
 967   return vec_ ? vec_->vec : 0;                                            \
 968 }                                                                         \
 969                                                                           \
 970 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 971      (VEC(T,base) *vec_, const T *obj_,                                   \
 972       bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL)             \
 973 {                                                                         \
 974    unsigned int len_ = VEC_OP (T, base, length) (vec_);                   \
 975    unsigned int half_, middle_;                                           \
 976    unsigned int first_ = 0;                                               \
 977    while (len_ > 0)                                                       \
 978      {                                                                    \
 979         T *middle_elem_;                                                  \
 980         half_ = len_ >> 1;                                                \
 981         middle_ = first_;                                                 \
 982         middle_ += half_;                                                 \
 983         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 984         if (lessthan_ (middle_elem_, obj_))                               \
 985           {                                                               \
 986              first_ = middle_;                                            \
 987              ++first_;                                                    \
 988              len_ = len_ - half_ - 1;                                     \
 989           }                                                               \
 990         else                                                              \
 991           len_ = half_;                                                   \
 992      }                                                                    \
 993    return first_;                                                         \
 994 }
 995
 996 #define DEF_VEC_ALLOC_FUNC_O(T,A)                                         \
 997 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 998      (int alloc_ MEM_STAT_DECL)                                           \
 999 {                                                                         \
1000   return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_,            \
1001                                                  offsetof (VEC(T,A),base.vec), \
1002                                                  sizeof (T)               \
1003                                                  PASS_MEM_STAT);          \
1004 }
1005
1006 #define DEF_VEC_NONALLOC_FUNCS_O(T,A)                                     \
1007 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1008 {                                                                         \
1009   size_t len_ = vec_ ? vec_->num : 0;                                     \
1010   VEC (T,A) *new_vec_ = NULL;                                             \
1011                                                                           \
1012   if (len_)                                                               \
1013     {                                                                     \
1014       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1015                                (NULL, len_,                               \
1016                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1017                                 PASS_MEM_STAT));                          \
1018                                                                           \
1019       new_vec_->base.num = len_;                                          \
1020       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1021     }                                                                     \
1022   return new_vec_;                                                        \
1023 }                                                                         \
1024                                                                           \
1025 static inline void VEC_OP (T,A,free)                                      \
1026      (VEC(T,A) **vec_)                                                    \
1027 {                                                                         \
1028   if (*vec_)                                                              \
1029     vec_##A##_free (*vec_);                                               \
1030   *vec_ = NULL;                                                           \
1031 }                                                                         \
1032                                                                           \
1033 static inline int VEC_OP (T,A,reserve)                                    \
1034      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1035 {                                                                         \
1036   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1037                                        VEC_CHECK_PASS);                   \
1038                                                                           \
1039   if (extend)                                                             \
1040     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1041                                               offsetof (VEC(T,A),base.vec),\
1042                                               sizeof (T)                  \
1043                                               PASS_MEM_STAT);             \
1044                                                                           \
1045   return extend;                                                          \
1046 }                                                                         \
1047                                                                           \
1048 static inline int VEC_OP (T,A,reserve_exact)                              \
1049      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1050 {                                                                         \
1051   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1052                                        VEC_CHECK_PASS);                   \
1053                                                                           \
1054   if (extend)                                                             \
1055     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1056                          (*vec_, alloc_,                                  \
1057                           offsetof (VEC(T,A),base.vec),                   \
1058                           sizeof (T) PASS_MEM_STAT);                      \
1059                                                                           \
1060   return extend;                                                          \
1061 }                                                                         \
1062                                                                           \
1063 static inline void VEC_OP (T,A,safe_grow)                                 \
1064      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1065 {                                                                         \
1066   VEC_ASSERT (size_ >= 0                                                  \
1067               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1068                                                  "grow", T, A);           \
1069   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1070                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1071                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1072   VEC_BASE (*vec_)->num = size_;                                          \
1073 }                                                                         \
1074                                                                           \
1075 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1076      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1077 {                                                                         \
1078   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1079   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1080   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1081           sizeof (T) * (size_ - oldsize));                                \
1082 }                                                                         \
1083                                                                           \
1084 static inline T *VEC_OP (T,A,safe_push)                                   \
1085      (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)        \
1086 {                                                                         \
1087   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1088                                                                           \
1089   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1090 }                                                                         \
1091                                                                           \
1092 static inline T *VEC_OP (T,A,safe_insert)                                 \
1093      (VEC(T,A) **vec_, unsigned ix_, const T *obj_                        \
1094                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1095 {                                                                         \
1096   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1097                                                                           \
1098   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1099                                        VEC_CHECK_PASS);                   \
1100 }
1101
1102 #define DEF_VEC_ALLOC_FUNC_I(T,A)                                         \
1103 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1104      (int alloc_ MEM_STAT_DECL)                                           \
1105 {                                                                         \
1106   return (VEC(T,A) *) vec_##A##_o_reserve_exact                           \
1107                       (NULL, alloc_, offsetof (VEC(T,A),base.vec),        \
1108                        sizeof (T) PASS_MEM_STAT);                         \
1109 }
1110
1111 #define DEF_VEC_NONALLOC_FUNCS_I(T,A)                                     \
1112 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1113 {                                                                         \
1114   size_t len_ = vec_ ? vec_->num : 0;                                     \
1115   VEC (T,A) *new_vec_ = NULL;                                             \
1116                                                                           \
1117   if (len_)                                                               \
1118     {                                                                     \
1119       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1120                                (NULL, len_,                               \
1121                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1122                                 PASS_MEM_STAT));                          \
1123                                                                           \
1124       new_vec_->base.num = len_;                                          \
1125       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1126     }                                                                     \
1127   return new_vec_;                                                        \
1128 }                                                                         \
1129                                                                           \
1130 static inline void VEC_OP (T,A,free)                                      \
1131      (VEC(T,A) **vec_)                                                    \
1132 {                                                                         \
1133   if (*vec_)                                                              \
1134     vec_##A##_free (*vec_);                                               \
1135   *vec_ = NULL;                                                           \
1136 }                                                                         \
1137                                                                           \
1138 static inline int VEC_OP (T,A,reserve)                                    \
1139      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1140 {                                                                         \
1141   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1142                                        VEC_CHECK_PASS);                   \
1143                                                                           \
1144   if (extend)                                                             \
1145     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1146                                               offsetof (VEC(T,A),base.vec),\
1147                                               sizeof (T)                  \
1148                                               PASS_MEM_STAT);             \
1149                                                                           \
1150   return extend;                                                          \
1151 }                                                                         \
1152                                                                           \
1153 static inline int VEC_OP (T,A,reserve_exact)                              \
1154      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1155 {                                                                         \
1156   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1157                                        VEC_CHECK_PASS);                   \
1158                                                                           \
1159   if (extend)                                                             \
1160     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1161                          (*vec_, alloc_, offsetof (VEC(T,A),base.vec),    \
1162                           sizeof (T) PASS_MEM_STAT);                      \
1163                                                                           \
1164   return extend;                                                          \
1165 }                                                                         \
1166                                                                           \
1167 static inline void VEC_OP (T,A,safe_grow)                                 \
1168      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1169 {                                                                         \
1170   VEC_ASSERT (size_ >= 0                                                  \
1171               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1172                                                  "grow", T, A);           \
1173   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1174                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1175                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1176   VEC_BASE (*vec_)->num = size_;                                          \
1177 }                                                                         \
1178                                                                           \
1179 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1180      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1181 {                                                                         \
1182   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1183   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1184   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1185           sizeof (T) * (size_ - oldsize));                                \
1186 }                                                                         \
1187                                                                           \
1188 static inline T *VEC_OP (T,A,safe_push)                                   \
1189      (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)         \
1190 {                                                                         \
1191   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1192                                                                           \
1193   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1194 }                                                                         \
1195                                                                           \
1196 static inline T *VEC_OP (T,A,safe_insert)                                 \
1197      (VEC(T,A) **vec_, unsigned ix_, const T obj_                         \
1198                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1199 {                                                                         \
1200   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1201                                                                           \
1202   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1203                                        VEC_CHECK_PASS);                   \
1204 }
1205
1206 /* We support a vector which starts out with space on the stack and
1207    switches to heap space when forced to reallocate.  This works a
1208    little differently.  Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1209    DEF_VEC_ALLOC_P_STACK(TYPE).  This uses alloca to get the initial
1210    space; because alloca can not be usefully called in an inline
1211    function, and because a macro can not define a macro, you must then
1212    write a #define for each type:
1213
1214    #define VEC_{TYPE}_stack_alloc(alloc)                          \
1215      VEC_stack_alloc({TYPE}, alloc)
1216
1217    This is really a hack and perhaps can be made better.  Note that
1218    this macro will wind up evaluating the ALLOC parameter twice.
1219
1220    Only the initial allocation will be made using alloca, so pass a
1221    reasonable estimate that doesn't use too much stack space; don't
1222    pass zero.  Don't return a VEC(TYPE,stack) vector from the function
1223    which allocated it.  */
1224
1225 extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
1226 extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
1227 extern void *vec_stack_p_reserve_exact_1 (int, void *);
1228 extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
1229 extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
1230                                          MEM_STAT_DECL);
1231 extern void vec_stack_free (void *);
1232
1233 #ifdef GATHER_STATISTICS
1234 #define VEC_stack_alloc(T,alloc,name,line,function)                       \
1235   (VEC_OP (T,stack,alloc1)                                                \
1236    (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1237 #else
1238 #define VEC_stack_alloc(T,alloc)                                          \
1239   (VEC_OP (T,stack,alloc1)                                                \
1240    (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1241 #endif
1242
1243 #define DEF_VEC_ALLOC_P_STACK(T)                                          \
1244 VEC_TA(T,base,stack);                                                     \
1245 DEF_VEC_ALLOC_FUNC_P_STACK(T)                                             \
1246 DEF_VEC_NONALLOC_FUNCS_P(T,stack)                                         \
1247 struct vec_swallow_trailing_semi
1248
1249 #define DEF_VEC_ALLOC_FUNC_P_STACK(T)                                     \
1250 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1251      (int alloc_, VEC(T,stack)* space)                                    \
1252 {                                                                         \
1253   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1254 }
1255
1256 #define DEF_VEC_ALLOC_O_STACK(T)                                          \
1257 VEC_TA(T,base,stack);                                                     \
1258 DEF_VEC_ALLOC_FUNC_O_STACK(T)                                             \
1259 DEF_VEC_NONALLOC_FUNCS_O(T,stack)                                         \
1260 struct vec_swallow_trailing_semi
1261
1262 #define DEF_VEC_ALLOC_FUNC_O_STACK(T)                                     \
1263 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1264      (int alloc_, VEC(T,stack)* space)                                    \
1265 {                                                                         \
1266   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1267 }
1268
1269 #define DEF_VEC_ALLOC_I_STACK(T)                                          \
1270 VEC_TA(T,base,stack);                                                     \
1271 DEF_VEC_ALLOC_FUNC_I_STACK(T)                                             \
1272 DEF_VEC_NONALLOC_FUNCS_I(T,stack)                                         \
1273 struct vec_swallow_trailing_semi
1274
1275 #define DEF_VEC_ALLOC_FUNC_I_STACK(T)                                     \
1276 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1277      (int alloc_, VEC(T,stack)* space)                                    \
1278 {                                                                         \
1279   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);   \
1280 }
1281
1282 #endif /* GCC_VEC_H */