gcc/vec.h

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