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 /* Convenience macro for reverse iteration.  */
 194
 195 #define FOR_EACH_VEC_ELT_REVERSE(T,V,I,P) \
 196   for (I = VEC_length (T, (V)) - 1;           \
 197        VEC_iterate (T, (V), (I), (P));    \
 198        (I)--)
 199
 200 /* Allocate new vector.
 201    VEC(T,A) *VEC_T_A_alloc(int reserve);
 202
 203    Allocate a new vector with space for RESERVE objects.  If RESERVE
 204    is zero, NO vector is created.  */
 205
 206 #define VEC_alloc(T,A,N)        (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
 207
 208 /* Free a vector.
 209    void VEC_T_A_free(VEC(T,A) *&);
 210
 211    Free a vector and set it to NULL.  */
 212
 213 #define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
 214
 215 /* Use these to determine the required size and initialization of a
 216    vector embedded within another structure (as the final member).
 217
 218    size_t VEC_T_embedded_size(int reserve);
 219    void VEC_T_embedded_init(VEC(T) *v, int reserve);
 220
 221    These allow the caller to perform the memory allocation.  */
 222
 223 #define VEC_embedded_size(T,N)   (VEC_OP(T,base,embedded_size)(N))
 224 #define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
 225
 226 /* Copy a vector.
 227    VEC(T,A) *VEC_T_A_copy(VEC(T) *);
 228
 229    Copy the live elements of a vector into a new vector.  The new and
 230    old vectors need not be allocated by the same mechanism.  */
 231
 232 #define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
 233
 234 /* Determine if a vector has additional capacity.
 235
 236    int VEC_T_space (VEC(T) *v,int reserve)
 237
 238    If V has space for RESERVE additional entries, return nonzero.  You
 239    usually only need to use this if you are doing your own vector
 240    reallocation, for instance on an embedded vector.  This returns
 241    nonzero in exactly the same circumstances that VEC_T_reserve
 242    will.  */
 243
 244 #define VEC_space(T,V,R) \
 245         (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
 246
 247 /* Reserve space.
 248    int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
 249
 250    Ensure that V has at least RESERVE slots available.  This will
 251    create additional headroom.  Note this can cause V to be
 252    reallocated.  Returns nonzero iff reallocation actually
 253    occurred.  */
 254
 255 #define VEC_reserve(T,A,V,R)    \
 256         (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
 257
 258 /* Reserve space exactly.
 259    int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
 260
 261    Ensure that V has at least RESERVE slots available.  This will not
 262    create additional headroom.  Note this can cause V to be
 263    reallocated.  Returns nonzero iff reallocation actually
 264    occurred.  */
 265
 266 #define VEC_reserve_exact(T,A,V,R)      \
 267         (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
 268
 269 /* Copy elements with no reallocation
 270    void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
 271    void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Pointer
 272    void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Object
 273
 274    Copy the elements in SRC to the end of DST as if by memcpy.  DST and
 275    SRC need not be allocated with the same mechanism, although they most
 276    often will be.  DST is assumed to have sufficient headroom
 277    available.  */
 278
 279 #define VEC_splice(T,DST,SRC)                   \
 280   (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
 281
 282 /* Copy elements with reallocation
 283    void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
 284    void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Pointer
 285    void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Object
 286
 287    Copy the elements in SRC to the end of DST as if by memcpy.  DST and
 288    SRC need not be allocated with the same mechanism, although they most
 289    often will be.  DST need not have sufficient headroom and will be
 290    reallocated if needed.  */
 291
 292 #define VEC_safe_splice(T,A,DST,SRC)                                    \
 293   (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO))
 294
 295 /* Push object with no reallocation
 296    T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
 297    T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
 298    T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
 299
 300    Push a new element onto the end, returns a pointer to the slot
 301    filled in. For object vectors, the new value can be NULL, in which
 302    case NO initialization is performed.  There must
 303    be sufficient space in the vector.  */
 304
 305 #define VEC_quick_push(T,V,O)   \
 306         (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
 307
 308 /* Push object with reallocation
 309    T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
 310    T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
 311    T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
 312
 313    Push a new element onto the end, returns a pointer to the slot
 314    filled in. For object vectors, the new value can be NULL, in which
 315    case NO initialization is performed.  Reallocates V, if needed.  */
 316
 317 #define VEC_safe_push(T,A,V,O)          \
 318         (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
 319
 320 /* Pop element off end
 321    T VEC_T_pop (VEC(T) *v);             // Integer
 322    T VEC_T_pop (VEC(T) *v);             // Pointer
 323    void VEC_T_pop (VEC(T) *v);          // Object
 324
 325    Pop the last element off the end. Returns the element popped, for
 326    pointer vectors.  */
 327
 328 #define VEC_pop(T,V)    (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
 329
 330 /* Truncate to specific length
 331    void VEC_T_truncate (VEC(T) *v, unsigned len);
 332
 333    Set the length as specified.  The new length must be less than or
 334    equal to the current length.  This is an O(1) operation.  */
 335
 336 #define VEC_truncate(T,V,I)             \
 337         (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
 338
 339 /* Grow to a specific length.
 340    void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
 341
 342    Grow the vector to a specific length.  The LEN must be as
 343    long or longer than the current length.  The new elements are
 344    uninitialized.  */
 345
 346 #define VEC_safe_grow(T,A,V,I)          \
 347         (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
 348
 349 /* Grow to a specific length.
 350    void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
 351
 352    Grow the vector to a specific length.  The LEN must be as
 353    long or longer than the current length.  The new elements are
 354    initialized to zero.  */
 355
 356 #define VEC_safe_grow_cleared(T,A,V,I)          \
 357         (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
 358
 359 /* Replace element
 360    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
 361    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
 362    T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val);  // Object
 363
 364    Replace the IXth element of V with a new value, VAL.  For pointer
 365    vectors returns the original value. For object vectors returns a
 366    pointer to the new value.  For object vectors the new value can be
 367    NULL, in which case no overwriting of the slot is actually
 368    performed.  */
 369
 370 #define VEC_replace(T,V,I,O)            \
 371         (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 372
 373 /* Insert object with no reallocation
 374    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
 375    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
 376    T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
 377
 378    Insert an element, VAL, at the IXth position of V. Return a pointer
 379    to the slot created.  For vectors of object, the new value can be
 380    NULL, in which case no initialization of the inserted slot takes
 381    place. There must be sufficient space.  */
 382
 383 #define VEC_quick_insert(T,V,I,O)       \
 384         (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
 385
 386 /* Insert object with reallocation
 387    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
 388    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
 389    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
 390
 391    Insert an element, VAL, at the IXth position of V. Return a pointer
 392    to the slot created.  For vectors of object, the new value can be
 393    NULL, in which case no initialization of the inserted slot takes
 394    place. Reallocate V, if necessary.  */
 395
 396 #define VEC_safe_insert(T,A,V,I,O)      \
 397         (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
 398
 399 /* Remove element retaining order
 400    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
 401    T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
 402    void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
 403
 404    Remove an element from the IXth position of V. Ordering of
 405    remaining elements is preserved.  For pointer vectors returns the
 406    removed object.  This is an O(N) operation due to a memmove.  */
 407
 408 #define VEC_ordered_remove(T,V,I)       \
 409         (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 410
 411 /* Remove element destroying order
 412    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
 413    T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
 414    void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
 415
 416    Remove an element from the IXth position of V. Ordering of
 417    remaining elements is destroyed.  For pointer vectors returns the
 418    removed object.  This is an O(1) operation.  */
 419
 420 #define VEC_unordered_remove(T,V,I)     \
 421         (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
 422
 423 /* Remove a block of elements
 424    void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
 425
 426    Remove LEN elements starting at the IXth.  Ordering is retained.
 427    This is an O(N) operation due to memmove.  */
 428
 429 #define VEC_block_remove(T,V,I,L)       \
 430         (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
 431
 432 /* Get the address of the array of elements
 433    T *VEC_T_address (VEC(T) v)
 434
 435    If you need to directly manipulate the array (for instance, you
 436    want to feed it to qsort), use this accessor.  */
 437
 438 #define VEC_address(T,V)                (VEC_OP(T,base,address)(VEC_BASE(V)))
 439
 440 /* Find the first index in the vector not less than the object.
 441    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 442                                bool (*lessthan) (const T, const T)); // Integer
 443    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
 444                                bool (*lessthan) (const T, const T)); // Pointer
 445    unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
 446                                bool (*lessthan) (const T*, const T*)); // Object
 447
 448    Find the first position in which VAL could be inserted without
 449    changing the ordering of V.  LESSTHAN is a function that returns
 450    true if the first argument is strictly less than the second.  */
 451
 452 #define VEC_lower_bound(T,V,O,LT)    \
 453        (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
 454
 455 /* Reallocate an array of elements with prefix.  */
 456 extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
 457 extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
 458 extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 459 extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
 460                                      MEM_STAT_DECL);
 461 extern void ggc_free (void *);
 462 #define vec_gc_free(V) ggc_free (V)
 463 extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
 464 extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
 465 extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
 466 extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
 467                                        MEM_STAT_DECL);
 468 extern void dump_vec_loc_statistics (void);
 469 #ifdef GATHER_STATISTICS
 470 void vec_heap_free (void *);
 471 #else
 472 /* Avoid problems with frontends that #define free(x).  */
 473 #define vec_heap_free(V) (free) (V)
 474 #endif
 475
 476 #if ENABLE_CHECKING
 477 #define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
 478 #define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
 479 #define VEC_CHECK_PASS ,file_,line_,function_
 480
 481 #define VEC_ASSERT(EXPR,OP,T,A) \
 482   (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
 483
 484 extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
 485      ATTRIBUTE_NORETURN;
 486 #define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
 487 #else
 488 #define VEC_CHECK_INFO
 489 #define VEC_CHECK_DECL
 490 #define VEC_CHECK_PASS
 491 #define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
 492 #endif
 493
 494 /* Note: gengtype has hardwired knowledge of the expansions of the
 495    VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros.  If you change the
 496    expansions of these macros you may need to change gengtype too.  */
 497
 498 #define VEC(T,A) VEC_##T##_##A
 499 #define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
 500
 501 /* Base of vector type, not user visible.  */
 502 #define VEC_T(T,B)                                                        \
 503 typedef struct VEC(T,B)                                                   \
 504 {                                                                         \
 505   unsigned num;                                                           \
 506   unsigned alloc;                                                         \
 507   T vec[1];                                                               \
 508 } VEC(T,B)
 509
 510 #define VEC_T_GTY(T,B)                                                    \
 511 typedef struct GTY(()) VEC(T,B)                                           \
 512 {                                                                         \
 513   unsigned num;                                                           \
 514   unsigned alloc;                                                         \
 515   T GTY ((length ("%h.num"))) vec[1];                                     \
 516 } VEC(T,B)
 517
 518 /* Derived vector type, user visible.  */
 519 #define VEC_TA_GTY(T,B,A,GTY)                                             \
 520 typedef struct GTY VEC(T,A)                                               \
 521 {                                                                         \
 522   VEC(T,B) base;                                                          \
 523 } VEC(T,A)
 524
 525 #define VEC_TA(T,B,A)                                                     \
 526 typedef struct VEC(T,A)                                                   \
 527 {                                                                         \
 528   VEC(T,B) base;                                                          \
 529 } VEC(T,A)
 530
 531 /* Convert to base type.  */
 532 #define VEC_BASE(P)  ((P) ? &(P)->base : 0)
 533
 534 /* Vector of integer-like object.  */
 535 #define DEF_VEC_I(T)                                                      \
 536 static inline void VEC_OP (T,must_be,integral_type) (void)                \
 537 {                                                                         \
 538   (void)~(T)0;                                                            \
 539 }                                                                         \
 540                                                                           \
 541 VEC_T(T,base);                                                            \
 542 VEC_TA(T,base,none);                                                      \
 543 DEF_VEC_FUNC_P(T)                                                         \
 544 struct vec_swallow_trailing_semi
 545 #define DEF_VEC_ALLOC_I(T,A)                                              \
 546 VEC_TA(T,base,A);                                                         \
 547 DEF_VEC_ALLOC_FUNC_I(T,A)                                                 \
 548 DEF_VEC_NONALLOC_FUNCS_I(T,A)                                             \
 549 struct vec_swallow_trailing_semi
 550
 551 /* Vector of pointer to object.  */
 552 #define DEF_VEC_P(T)                                                      \
 553 static inline void VEC_OP (T,must_be,pointer_type) (void)                 \
 554 {                                                                         \
 555   (void)((T)1 == (void *)1);                                              \
 556 }                                                                         \
 557                                                                           \
 558 VEC_T_GTY(T,base);                                                        \
 559 VEC_TA(T,base,none);                                                      \
 560 DEF_VEC_FUNC_P(T)                                                         \
 561 struct vec_swallow_trailing_semi
 562 #define DEF_VEC_ALLOC_P(T,A)                                              \
 563 VEC_TA(T,base,A);                                                         \
 564 DEF_VEC_ALLOC_FUNC_P(T,A)                                                 \
 565 DEF_VEC_NONALLOC_FUNCS_P(T,A)                                             \
 566 struct vec_swallow_trailing_semi
 567
 568 #define DEF_VEC_FUNC_P(T)                                                 \
 569 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 570 {                                                                         \
 571   return vec_ ? vec_->num : 0;                                            \
 572 }                                                                         \
 573                                                                           \
 574 static inline T VEC_OP (T,base,last)                                      \
 575      (const VEC(T,base) *vec_ VEC_CHECK_DECL)                             \
 576 {                                                                         \
 577   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 578                                                                           \
 579   return vec_->vec[vec_->num - 1];                                        \
 580 }                                                                         \
 581                                                                           \
 582 static inline T VEC_OP (T,base,index)                                     \
 583      (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)               \
 584 {                                                                         \
 585   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 586                                                                           \
 587   return vec_->vec[ix_];                                                  \
 588 }                                                                         \
 589                                                                           \
 590 static inline int VEC_OP (T,base,iterate)                                 \
 591      (const VEC(T,base) *vec_, unsigned ix_, T *ptr)                      \
 592 {                                                                         \
 593   if (vec_ && ix_ < vec_->num)                                            \
 594     {                                                                     \
 595       *ptr = vec_->vec[ix_];                                              \
 596       return 1;                                                           \
 597     }                                                                     \
 598   else                                                                    \
 599     {                                                                     \
 600       *ptr = (T) 0;                                                       \
 601       return 0;                                                           \
 602     }                                                                     \
 603 }                                                                         \
 604                                                                           \
 605 static inline size_t VEC_OP (T,base,embedded_size)                        \
 606      (int alloc_)                                                         \
 607 {                                                                         \
 608   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 609 }                                                                         \
 610                                                                           \
 611 static inline void VEC_OP (T,base,embedded_init)                          \
 612      (VEC(T,base) *vec_, int alloc_)                                      \
 613 {                                                                         \
 614   vec_->num = 0;                                                          \
 615   vec_->alloc = alloc_;                                                   \
 616 }                                                                         \
 617                                                                           \
 618 static inline int VEC_OP (T,base,space)                                   \
 619      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 620 {                                                                         \
 621   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 622   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 623 }                                                                         \
 624                                                                           \
 625 static inline void VEC_OP(T,base,splice)                                  \
 626      (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL)                \
 627 {                                                                         \
 628   if (src_)                                                               \
 629     {                                                                     \
 630       unsigned len_ = src_->num;                                          \
 631       VEC_ASSERT (dst_->num + len_ <= dst_->alloc, "splice", T, base);    \
 632                                                                           \
 633       memcpy (&dst_->vec[dst_->num], &src_->vec[0], len_ * sizeof (T));   \
 634       dst_->num += len_;                                                  \
 635     }                                                                     \
 636 }                                                                         \
 637                                                                           \
 638 static inline T *VEC_OP (T,base,quick_push)                               \
 639      (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)                           \
 640 {                                                                         \
 641   T *slot_;                                                               \
 642                                                                           \
 643   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 644   slot_ = &vec_->vec[vec_->num++];                                        \
 645   *slot_ = obj_;                                                          \
 646                                                                           \
 647   return slot_;                                                           \
 648 }                                                                         \
 649                                                                           \
 650 static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)    \
 651 {                                                                         \
 652   T obj_;                                                                 \
 653                                                                           \
 654   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 655   obj_ = vec_->vec[--vec_->num];                                          \
 656                                                                           \
 657   return obj_;                                                            \
 658 }                                                                         \
 659                                                                           \
 660 static inline void VEC_OP (T,base,truncate)                               \
 661      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 662 {                                                                         \
 663   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 664   if (vec_)                                                               \
 665     vec_->num = size_;                                                    \
 666 }                                                                         \
 667                                                                           \
 668 static inline T VEC_OP (T,base,replace)                                   \
 669      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 670 {                                                                         \
 671   T old_obj_;                                                             \
 672                                                                           \
 673   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 674   old_obj_ = vec_->vec[ix_];                                              \
 675   vec_->vec[ix_] = obj_;                                                  \
 676                                                                           \
 677   return old_obj_;                                                        \
 678 }                                                                         \
 679                                                                           \
 680 static inline T *VEC_OP (T,base,quick_insert)                             \
 681      (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
 682 {                                                                         \
 683   T *slot_;                                                               \
 684                                                                           \
 685   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
 686   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
 687   slot_ = &vec_->vec[ix_];                                                \
 688   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
 689   *slot_ = obj_;                                                          \
 690                                                                           \
 691   return slot_;                                                           \
 692 }                                                                         \
 693                                                                           \
 694 static inline T VEC_OP (T,base,ordered_remove)                            \
 695      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 696 {                                                                         \
 697   T *slot_;                                                               \
 698   T obj_;                                                                 \
 699                                                                           \
 700   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 701   slot_ = &vec_->vec[ix_];                                                \
 702   obj_ = *slot_;                                                          \
 703   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
 704                                                                           \
 705   return obj_;                                                            \
 706 }                                                                         \
 707                                                                           \
 708 static inline T VEC_OP (T,base,unordered_remove)                          \
 709      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 710 {                                                                         \
 711   T *slot_;                                                               \
 712   T obj_;                                                                 \
 713                                                                           \
 714   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
 715   slot_ = &vec_->vec[ix_];                                                \
 716   obj_ = *slot_;                                                          \
 717   *slot_ = vec_->vec[--vec_->num];                                        \
 718                                                                           \
 719   return obj_;                                                            \
 720 }                                                                         \
 721                                                                           \
 722 static inline void VEC_OP (T,base,block_remove)                           \
 723      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
 724 {                                                                         \
 725   T *slot_;                                                               \
 726                                                                           \
 727   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
 728   slot_ = &vec_->vec[ix_];                                                \
 729   vec_->num -= len_;                                                      \
 730   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
 731 }                                                                         \
 732                                                                           \
 733 static inline T *VEC_OP (T,base,address)                                  \
 734      (VEC(T,base) *vec_)                                                  \
 735 {                                                                         \
 736   return vec_ ? vec_->vec : 0;                                            \
 737 }                                                                         \
 738                                                                           \
 739 static inline unsigned VEC_OP (T,base,lower_bound)                        \
 740      (VEC(T,base) *vec_, const T obj_,                                    \
 741       bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)                 \
 742 {                                                                         \
 743    unsigned int len_ = VEC_OP (T,base, length) (vec_);                    \
 744    unsigned int half_, middle_;                                           \
 745    unsigned int first_ = 0;                                               \
 746    while (len_ > 0)                                                       \
 747      {                                                                    \
 748         T middle_elem_;                                                   \
 749         half_ = len_ >> 1;                                                \
 750         middle_ = first_;                                                 \
 751         middle_ += half_;                                                 \
 752         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
 753         if (lessthan_ (middle_elem_, obj_))                               \
 754           {                                                               \
 755              first_ = middle_;                                            \
 756              ++first_;                                                    \
 757              len_ = len_ - half_ - 1;                                     \
 758           }                                                               \
 759         else                                                              \
 760           len_ = half_;                                                   \
 761      }                                                                    \
 762    return first_;                                                         \
 763 }
 764
 765 #define DEF_VEC_ALLOC_FUNC_P(T,A)                                         \
 766 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
 767      (int alloc_ MEM_STAT_DECL)                                           \
 768 {                                                                         \
 769   return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_             \
 770                                                  PASS_MEM_STAT);          \
 771 }
 772
 773
 774 #define DEF_VEC_NONALLOC_FUNCS_P(T,A)                                     \
 775 static inline void VEC_OP (T,A,free)                                      \
 776      (VEC(T,A) **vec_)                                                    \
 777 {                                                                         \
 778   if (*vec_)                                                              \
 779     vec_##A##_free (*vec_);                                               \
 780   *vec_ = NULL;                                                           \
 781 }                                                                         \
 782                                                                           \
 783 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
 784 {                                                                         \
 785   size_t len_ = vec_ ? vec_->num : 0;                                     \
 786   VEC (T,A) *new_vec_ = NULL;                                             \
 787                                                                           \
 788   if (len_)                                                               \
 789     {                                                                     \
 790       new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact                  \
 791                                (NULL, len_ PASS_MEM_STAT));               \
 792                                                                           \
 793       new_vec_->base.num = len_;                                          \
 794       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
 795     }                                                                     \
 796   return new_vec_;                                                        \
 797 }                                                                         \
 798                                                                           \
 799 static inline int VEC_OP (T,A,reserve)                                    \
 800      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 801 {                                                                         \
 802   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 803                                        VEC_CHECK_PASS);                   \
 804                                                                           \
 805   if (extend)                                                             \
 806     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
 807                                                                           \
 808   return extend;                                                          \
 809 }                                                                         \
 810                                                                           \
 811 static inline int VEC_OP (T,A,reserve_exact)                              \
 812      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
 813 {                                                                         \
 814   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
 815                                        VEC_CHECK_PASS);                   \
 816                                                                           \
 817   if (extend)                                                             \
 818     *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_         \
 819                                                     PASS_MEM_STAT);       \
 820                                                                           \
 821   return extend;                                                          \
 822 }                                                                         \
 823                                                                           \
 824 static inline void VEC_OP (T,A,safe_grow)                                 \
 825      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 826 {                                                                         \
 827   VEC_ASSERT (size_ >= 0                                                  \
 828               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
 829                                                  "grow", T, A);           \
 830   VEC_OP (T,A,reserve_exact) (vec_,                                       \
 831                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
 832                               VEC_CHECK_PASS PASS_MEM_STAT);              \
 833   VEC_BASE (*vec_)->num = size_;                                          \
 834 }                                                                         \
 835                                                                           \
 836 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
 837      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
 838 {                                                                         \
 839   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
 840   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
 841   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
 842           sizeof (T) * (size_ - oldsize));                                \
 843 }                                                                         \
 844                                                                           \
 845 static inline void VEC_OP(T,A,safe_splice)                                \
 846      (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)    \
 847 {                                                                         \
 848   if (src_)                                                               \
 849     {                                                                     \
 850       VEC_OP (T,A,reserve_exact) (dst_, src_->num                         \
 851                                   VEC_CHECK_PASS MEM_STAT_INFO);          \
 852                                                                           \
 853       VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_                      \
 854                               VEC_CHECK_PASS);                            \
 855     }                                                                     \
 856 }                                                                         \
 857                                                                           \
 858 static inline T *VEC_OP (T,A,safe_push)                                   \
 859      (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)               \
 860 {                                                                         \
 861   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 862                                                                           \
 863   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
 864 }                                                                         \
 865                                                                           \
 866 static inline T *VEC_OP (T,A,safe_insert)                                 \
 867      (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
 868 {                                                                         \
 869   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
 870                                                                           \
 871   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
 872                                        VEC_CHECK_PASS);                   \
 873 }
 874
 875 /* Vector of object.  */
 876 #define DEF_VEC_O(T)                                                      \
 877 VEC_T_GTY(T,base);                                                        \
 878 VEC_TA(T,base,none);                                              \
 879 DEF_VEC_FUNC_O(T)                                                         \
 880 struct vec_swallow_trailing_semi
 881 #define DEF_VEC_ALLOC_O(T,A)                                              \
 882 VEC_TA(T,base,A);                                                         \
 883 DEF_VEC_ALLOC_FUNC_O(T,A)                                                 \
 884 DEF_VEC_NONALLOC_FUNCS_O(T,A)                                             \
 885 struct vec_swallow_trailing_semi
 886
 887 #define DEF_VEC_FUNC_O(T)                                                 \
 888 static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
 889 {                                                                         \
 890   return vec_ ? vec_->num : 0;                                            \
 891 }                                                                         \
 892                                                                           \
 893 static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL)  \
 894 {                                                                         \
 895   VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
 896                                                                           \
 897   return &vec_->vec[vec_->num - 1];                                       \
 898 }                                                                         \
 899                                                                           \
 900 static inline T *VEC_OP (T,base,index)                                    \
 901      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
 902 {                                                                         \
 903   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
 904                                                                           \
 905   return &vec_->vec[ix_];                                                 \
 906 }                                                                         \
 907                                                                           \
 908 static inline int VEC_OP (T,base,iterate)                                 \
 909      (VEC(T,base) *vec_, unsigned ix_, T **ptr)                           \
 910 {                                                                         \
 911   if (vec_ && ix_ < vec_->num)                                            \
 912     {                                                                     \
 913       *ptr = &vec_->vec[ix_];                                             \
 914       return 1;                                                           \
 915     }                                                                     \
 916   else                                                                    \
 917     {                                                                     \
 918       *ptr = 0;                                                           \
 919       return 0;                                                           \
 920     }                                                                     \
 921 }                                                                         \
 922                                                                           \
 923 static inline size_t VEC_OP (T,base,embedded_size)                        \
 924      (int alloc_)                                                         \
 925 {                                                                         \
 926   return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
 927 }                                                                         \
 928                                                                           \
 929 static inline void VEC_OP (T,base,embedded_init)                          \
 930      (VEC(T,base) *vec_, int alloc_)                                      \
 931 {                                                                         \
 932   vec_->num = 0;                                                          \
 933   vec_->alloc = alloc_;                                                   \
 934 }                                                                         \
 935                                                                           \
 936 static inline int VEC_OP (T,base,space)                                   \
 937      (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
 938 {                                                                         \
 939   VEC_ASSERT (alloc_ >= 0, "space", T, base);                             \
 940   return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
 941 }                                                                         \
 942                                                                           \
 943 static inline void VEC_OP(T,base,splice)                                  \
 944      (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL)                \
 945 {                                                                         \
 946   if (src_)                                                               \
 947     {                                                                     \
 948       unsigned len_ = src_->num;                                          \
 949       VEC_ASSERT (dst_->num + len_ <= dst_->alloc, "splice", T, base);    \
 950                                                                           \
 951       memcpy (&dst_->vec[dst_->num], &src_->vec[0], len_ * sizeof (T));   \
 952       dst_->num += len_;                                                  \
 953     }                                                                     \
 954 }                                                                         \
 955                                                                           \
 956 static inline T *VEC_OP (T,base,quick_push)                               \
 957      (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL)                    \
 958 {                                                                         \
 959   T *slot_;                                                               \
 960                                                                           \
 961   VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
 962   slot_ = &vec_->vec[vec_->num++];                                        \
 963   if (obj_)                                                               \
 964     *slot_ = *obj_;                                                       \
 965                                                                           \
 966   return slot_;                                                           \
 967 }                                                                         \
 968                                                                           \
 969 static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
 970 {                                                                         \
 971   VEC_ASSERT (vec_->num, "pop", T, base);                                 \
 972   --vec_->num;                                                            \
 973 }                                                                         \
 974                                                                           \
 975 static inline void VEC_OP (T,base,truncate)                               \
 976      (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
 977 {                                                                         \
 978   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
 979   if (vec_)                                                               \
 980     vec_->num = size_;                                                    \
 981 }                                                                         \
 982                                                                           \
 983 static inline T *VEC_OP (T,base,replace)                                  \
 984      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 985 {                                                                         \
 986   T *slot_;                                                               \
 987                                                                           \
 988   VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
 989   slot_ = &vec_->vec[ix_];                                                \
 990   if (obj_)                                                               \
 991     *slot_ = *obj_;                                                       \
 992                                                                           \
 993   return slot_;                                                           \
 994 }                                                                         \
 995                                                                           \
 996 static inline T *VEC_OP (T,base,quick_insert)                             \
 997      (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
 998 {                                                                         \
 999   T *slot_;                                                               \
1000                                                                           \
1001   VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
1002   VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
1003   slot_ = &vec_->vec[ix_];                                                \
1004   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
1005   if (obj_)                                                               \
1006     *slot_ = *obj_;                                                       \
1007                                                                           \
1008   return slot_;                                                           \
1009 }                                                                         \
1010                                                                           \
1011 static inline void VEC_OP (T,base,ordered_remove)                         \
1012      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
1013 {                                                                         \
1014   T *slot_;                                                               \
1015                                                                           \
1016   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
1017   slot_ = &vec_->vec[ix_];                                                \
1018   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
1019 }                                                                         \
1020                                                                           \
1021 static inline void VEC_OP (T,base,unordered_remove)                       \
1022      (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
1023 {                                                                         \
1024   VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
1025   vec_->vec[ix_] = vec_->vec[--vec_->num];                                \
1026 }                                                                         \
1027                                                                           \
1028 static inline void VEC_OP (T,base,block_remove)                           \
1029      (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
1030 {                                                                         \
1031   T *slot_;                                                               \
1032                                                                           \
1033   VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
1034   slot_ = &vec_->vec[ix_];                                                \
1035   vec_->num -= len_;                                                      \
1036   memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
1037 }                                                                         \
1038                                                                           \
1039 static inline T *VEC_OP (T,base,address)                                  \
1040      (VEC(T,base) *vec_)                                                  \
1041 {                                                                         \
1042   return vec_ ? vec_->vec : 0;                                            \
1043 }                                                                         \
1044                                                                           \
1045 static inline unsigned VEC_OP (T,base,lower_bound)                        \
1046      (VEC(T,base) *vec_, const T *obj_,                                   \
1047       bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL)             \
1048 {                                                                         \
1049    unsigned int len_ = VEC_OP (T, base, length) (vec_);                   \
1050    unsigned int half_, middle_;                                           \
1051    unsigned int first_ = 0;                                               \
1052    while (len_ > 0)                                                       \
1053      {                                                                    \
1054         T *middle_elem_;                                                  \
1055         half_ = len_ >> 1;                                                \
1056         middle_ = first_;                                                 \
1057         middle_ += half_;                                                 \
1058         middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
1059         if (lessthan_ (middle_elem_, obj_))                               \
1060           {                                                               \
1061              first_ = middle_;                                            \
1062              ++first_;                                                    \
1063              len_ = len_ - half_ - 1;                                     \
1064           }                                                               \
1065         else                                                              \
1066           len_ = half_;                                                   \
1067      }                                                                    \
1068    return first_;                                                         \
1069 }
1070
1071 #define DEF_VEC_ALLOC_FUNC_O(T,A)                                         \
1072 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1073      (int alloc_ MEM_STAT_DECL)                                           \
1074 {                                                                         \
1075   return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_,            \
1076                                                  offsetof (VEC(T,A),base.vec), \
1077                                                  sizeof (T)               \
1078                                                  PASS_MEM_STAT);          \
1079 }
1080
1081 #define DEF_VEC_NONALLOC_FUNCS_O(T,A)                                     \
1082 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1083 {                                                                         \
1084   size_t len_ = vec_ ? vec_->num : 0;                                     \
1085   VEC (T,A) *new_vec_ = NULL;                                             \
1086                                                                           \
1087   if (len_)                                                               \
1088     {                                                                     \
1089       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1090                                (NULL, len_,                               \
1091                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1092                                 PASS_MEM_STAT));                          \
1093                                                                           \
1094       new_vec_->base.num = len_;                                          \
1095       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1096     }                                                                     \
1097   return new_vec_;                                                        \
1098 }                                                                         \
1099                                                                           \
1100 static inline void VEC_OP (T,A,free)                                      \
1101      (VEC(T,A) **vec_)                                                    \
1102 {                                                                         \
1103   if (*vec_)                                                              \
1104     vec_##A##_free (*vec_);                                               \
1105   *vec_ = NULL;                                                           \
1106 }                                                                         \
1107                                                                           \
1108 static inline int VEC_OP (T,A,reserve)                                    \
1109      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1110 {                                                                         \
1111   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1112                                        VEC_CHECK_PASS);                   \
1113                                                                           \
1114   if (extend)                                                             \
1115     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1116                                               offsetof (VEC(T,A),base.vec),\
1117                                               sizeof (T)                  \
1118                                               PASS_MEM_STAT);             \
1119                                                                           \
1120   return extend;                                                          \
1121 }                                                                         \
1122                                                                           \
1123 static inline int VEC_OP (T,A,reserve_exact)                              \
1124      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1125 {                                                                         \
1126   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1127                                        VEC_CHECK_PASS);                   \
1128                                                                           \
1129   if (extend)                                                             \
1130     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1131                          (*vec_, alloc_,                                  \
1132                           offsetof (VEC(T,A),base.vec),                   \
1133                           sizeof (T) PASS_MEM_STAT);                      \
1134                                                                           \
1135   return extend;                                                          \
1136 }                                                                         \
1137                                                                           \
1138 static inline void VEC_OP (T,A,safe_grow)                                 \
1139      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1140 {                                                                         \
1141   VEC_ASSERT (size_ >= 0                                                  \
1142               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1143                                                  "grow", T, A);           \
1144   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1145                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1146                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1147   VEC_BASE (*vec_)->num = size_;                                          \
1148 }                                                                         \
1149                                                                           \
1150 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1151      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1152 {                                                                         \
1153   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1154   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1155   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1156           sizeof (T) * (size_ - oldsize));                                \
1157 }                                                                         \
1158                                                                           \
1159 static inline void VEC_OP(T,A,safe_splice)                                \
1160      (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)    \
1161 {                                                                         \
1162   if (src_)                                                               \
1163     {                                                                     \
1164       VEC_OP (T,A,reserve_exact) (dst_, src_->num                         \
1165                                   VEC_CHECK_PASS MEM_STAT_INFO);          \
1166                                                                           \
1167       VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_                      \
1168                               VEC_CHECK_PASS);                            \
1169     }                                                                     \
1170 }                                                                         \
1171                                                                           \
1172 static inline T *VEC_OP (T,A,safe_push)                                   \
1173      (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)        \
1174 {                                                                         \
1175   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1176                                                                           \
1177   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1178 }                                                                         \
1179                                                                           \
1180 static inline T *VEC_OP (T,A,safe_insert)                                 \
1181      (VEC(T,A) **vec_, unsigned ix_, const T *obj_                        \
1182                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1183 {                                                                         \
1184   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1185                                                                           \
1186   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1187                                        VEC_CHECK_PASS);                   \
1188 }
1189
1190 #define DEF_VEC_ALLOC_FUNC_I(T,A)                                         \
1191 static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1192      (int alloc_ MEM_STAT_DECL)                                           \
1193 {                                                                         \
1194   return (VEC(T,A) *) vec_##A##_o_reserve_exact                           \
1195                       (NULL, alloc_, offsetof (VEC(T,A),base.vec),        \
1196                        sizeof (T) PASS_MEM_STAT);                         \
1197 }
1198
1199 #define DEF_VEC_NONALLOC_FUNCS_I(T,A)                                     \
1200 static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1201 {                                                                         \
1202   size_t len_ = vec_ ? vec_->num : 0;                                     \
1203   VEC (T,A) *new_vec_ = NULL;                                             \
1204                                                                           \
1205   if (len_)                                                               \
1206     {                                                                     \
1207       new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1208                                (NULL, len_,                               \
1209                                 offsetof (VEC(T,A),base.vec), sizeof (T)  \
1210                                 PASS_MEM_STAT));                          \
1211                                                                           \
1212       new_vec_->base.num = len_;                                          \
1213       memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1214     }                                                                     \
1215   return new_vec_;                                                        \
1216 }                                                                         \
1217                                                                           \
1218 static inline void VEC_OP (T,A,free)                                      \
1219      (VEC(T,A) **vec_)                                                    \
1220 {                                                                         \
1221   if (*vec_)                                                              \
1222     vec_##A##_free (*vec_);                                               \
1223   *vec_ = NULL;                                                           \
1224 }                                                                         \
1225                                                                           \
1226 static inline int VEC_OP (T,A,reserve)                                    \
1227      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1228 {                                                                         \
1229   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1230                                        VEC_CHECK_PASS);                   \
1231                                                                           \
1232   if (extend)                                                             \
1233     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1234                                               offsetof (VEC(T,A),base.vec),\
1235                                               sizeof (T)                  \
1236                                               PASS_MEM_STAT);             \
1237                                                                           \
1238   return extend;                                                          \
1239 }                                                                         \
1240                                                                           \
1241 static inline int VEC_OP (T,A,reserve_exact)                              \
1242      (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1243 {                                                                         \
1244   int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1245                                        VEC_CHECK_PASS);                   \
1246                                                                           \
1247   if (extend)                                                             \
1248     *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1249                          (*vec_, alloc_, offsetof (VEC(T,A),base.vec),    \
1250                           sizeof (T) PASS_MEM_STAT);                      \
1251                                                                           \
1252   return extend;                                                          \
1253 }                                                                         \
1254                                                                           \
1255 static inline void VEC_OP (T,A,safe_grow)                                 \
1256      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1257 {                                                                         \
1258   VEC_ASSERT (size_ >= 0                                                  \
1259               && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1260                                                  "grow", T, A);           \
1261   VEC_OP (T,A,reserve_exact) (vec_,                                       \
1262                               size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1263                               VEC_CHECK_PASS PASS_MEM_STAT);              \
1264   VEC_BASE (*vec_)->num = size_;                                          \
1265 }                                                                         \
1266                                                                           \
1267 static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1268      (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1269 {                                                                         \
1270   int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1271   VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1272   memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,         \
1273           sizeof (T) * (size_ - oldsize));                                \
1274 }                                                                         \
1275                                                                           \
1276 static inline void VEC_OP(T,A,safe_splice)                                \
1277      (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)    \
1278 {                                                                         \
1279   if (src_)                                                               \
1280     {                                                                     \
1281       VEC_OP (T,A,reserve_exact) (dst_, src_->num                         \
1282                                   VEC_CHECK_PASS MEM_STAT_INFO);          \
1283                                                                           \
1284       VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_                      \
1285                               VEC_CHECK_PASS);                            \
1286     }                                                                     \
1287 }                                                                         \
1288                                                                           \
1289 static inline T *VEC_OP (T,A,safe_push)                                   \
1290      (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)         \
1291 {                                                                         \
1292   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1293                                                                           \
1294   return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1295 }                                                                         \
1296                                                                           \
1297 static inline T *VEC_OP (T,A,safe_insert)                                 \
1298      (VEC(T,A) **vec_, unsigned ix_, const T obj_                         \
1299                 VEC_CHECK_DECL MEM_STAT_DECL)                             \
1300 {                                                                         \
1301   VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1302                                                                           \
1303   return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1304                                        VEC_CHECK_PASS);                   \
1305 }
1306
1307 /* We support a vector which starts out with space on the stack and
1308    switches to heap space when forced to reallocate.  This works a
1309    little differently.  Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1310    DEF_VEC_ALLOC_P_STACK(TYPE).  This uses alloca to get the initial
1311    space; because alloca can not be usefully called in an inline
1312    function, and because a macro can not define a macro, you must then
1313    write a #define for each type:
1314
1315    #define VEC_{TYPE}_stack_alloc(alloc)                          \
1316      VEC_stack_alloc({TYPE}, alloc)
1317
1318    This is really a hack and perhaps can be made better.  Note that
1319    this macro will wind up evaluating the ALLOC parameter twice.
1320
1321    Only the initial allocation will be made using alloca, so pass a
1322    reasonable estimate that doesn't use too much stack space; don't
1323    pass zero.  Don't return a VEC(TYPE,stack) vector from the function
1324    which allocated it.  */
1325
1326 extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
1327 extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
1328 extern void *vec_stack_p_reserve_exact_1 (int, void *);
1329 extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
1330 extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
1331                                          MEM_STAT_DECL);
1332 extern void vec_stack_free (void *);
1333
1334 #ifdef GATHER_STATISTICS
1335 #define VEC_stack_alloc(T,alloc,name,line,function)                       \
1336   (VEC_OP (T,stack,alloc1)                                                \
1337    (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1338 #else
1339 #define VEC_stack_alloc(T,alloc)                                          \
1340   (VEC_OP (T,stack,alloc1)                                                \
1341    (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1342 #endif
1343
1344 #define DEF_VEC_ALLOC_P_STACK(T)                                          \
1345 VEC_TA(T,base,stack);                                                     \
1346 DEF_VEC_ALLOC_FUNC_P_STACK(T)                                             \
1347 DEF_VEC_NONALLOC_FUNCS_P(T,stack)                                         \
1348 struct vec_swallow_trailing_semi
1349
1350 #define DEF_VEC_ALLOC_FUNC_P_STACK(T)                                     \
1351 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1352      (int alloc_, VEC(T,stack)* space)                                    \
1353 {                                                                         \
1354   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1355 }
1356
1357 #define DEF_VEC_ALLOC_O_STACK(T)                                          \
1358 VEC_TA(T,base,stack);                                                     \
1359 DEF_VEC_ALLOC_FUNC_O_STACK(T)                                             \
1360 DEF_VEC_NONALLOC_FUNCS_O(T,stack)                                         \
1361 struct vec_swallow_trailing_semi
1362
1363 #define DEF_VEC_ALLOC_FUNC_O_STACK(T)                                     \
1364 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1365      (int alloc_, VEC(T,stack)* space)                                    \
1366 {                                                                         \
1367   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1368 }
1369
1370 #define DEF_VEC_ALLOC_I_STACK(T)                                          \
1371 VEC_TA(T,base,stack);                                                     \
1372 DEF_VEC_ALLOC_FUNC_I_STACK(T)                                             \
1373 DEF_VEC_NONALLOC_FUNCS_I(T,stack)                                         \
1374 struct vec_swallow_trailing_semi
1375
1376 #define DEF_VEC_ALLOC_FUNC_I_STACK(T)                                     \
1377 static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1378      (int alloc_, VEC(T,stack)* space)                                    \
1379 {                                                                         \
1380   return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);   \
1381 }
1382
1383 #endif /* GCC_VEC_H */