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