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