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