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