gcc/vec.h

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