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_x(TYPEDEF) macro, and
  85    variables of vector type are declared using a VEC(TYPEDEF)
  86    macro. The 'x' letter indicates whether TYPEDEF is a pointer (P) or
  87    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,t); ix++)
 103      { do something with t }
 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    size_t 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, size_t ix); // Pointer
 131    T *VEC_T_index(VEC(T) *v, size_t 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_index(VEC(T) *v, size_t ix, T &ptr); // Pointer
 140    int VEC_T_index(VEC(T) *v, size_t 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, size_t 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, size_t ix, T val); // Pointer
 238    T *VEC_T_replace (VEC(T) *v, size_t 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, size_t ix, T val); // Pointer
 251    T *VEC_T_quick_insert (VEC(T) *v, size_t 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, size_t ix, T val); // Pointer
 263    T *VEC_T_safe_insert (VEC(T) *&v, size_t 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, size_t ix); // Pointer
 275    void VEC_T_ordered_remove (VEC(T) *v, size_t 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, size_t ix); // Pointer
 286    void VEC_T_unordered_remove (VEC(T) *v, size_t 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   size_t num;                                                             \
 341   size_t 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 size_t 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_, size_t 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_, size_t 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_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                  < (size_t)(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_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_, size_t 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_, size_t 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_, size_t 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_, size_t ix_, TDEF obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
 494 {                                                                         \
 495   VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT);                         \
 496                                                                           \
 497   return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS);    \
 498 }                                                                         \
 499                                                                           \
 500 static inline TDEF VEC_OP (TDEF,ordered_remove)                           \
 501      (VEC (TDEF) *vec_, size_t ix_ VEC_CHECK_DECL)                        \
 502 {                                                                         \
 503   TDEF *slot_;                                                            \
 504   TDEF obj_;                                                              \
 505                                                                           \
 506   VEC_ASSERT (ix_ < vec_->num, "remove", TDEF);                           \
 507   slot_ = &vec_->vec[ix_];                                                \
 508   obj_ = *slot_;                                                          \
 509   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF));        \
 510                                                                           \
 511   return obj_;                                                            \
 512 }                                                                         \
 513                                                                           \
 514 static inline TDEF VEC_OP (TDEF,unordered_remove)                         \
 515      (VEC (TDEF) *vec_, size_t ix_ VEC_CHECK_DECL)                        \
 516 {                                                                         \
 517   TDEF *slot_;                                                            \
 518   TDEF obj_;                                                              \
 519                                                                           \
 520   VEC_ASSERT (ix_ < vec_->num, "remove", TDEF);                           \
 521   slot_ = &vec_->vec[ix_];                                                \
 522   obj_ = *slot_;                                                          \
 523   *slot_ = vec_->vec[--vec_->num];                                        \
 524                                                                           \
 525   return obj_;                                                            \
 526 }                                                                         \
 527                                                                           \
 528 static inline TDEF *VEC_OP (TDEF,address)                                 \
 529      (VEC (TDEF) *vec_)                                                   \
 530 {                                                                         \
 531   return vec_ ? vec_->vec : 0;                                            \
 532 }                                                                         \
 533                                                                           \
 534 struct vec_swallow_trailing_semi
 535 #endif
 536
 537 /* Vector of object.  */
 538 #if IN_GENGTYPE
 539 {"DEF_VEC_O", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
 540 #else
 541
 542 #define DEF_VEC_O(TDEF)                                                   \
 543 VEC_TDEF (TDEF);                                                          \
 544                                                                           \
 545 static inline size_t VEC_OP (TDEF,length)                                 \
 546      (const VEC (TDEF) *vec_)                                             \
 547 {                                                                         \
 548   return vec_ ? vec_->num : 0;                                            \
 549 }                                                                         \
 550                                                                           \
 551 static inline TDEF *VEC_OP (TDEF,last)                                    \
 552      (VEC (TDEF) *vec_ VEC_CHECK_DECL)                                    \
 553 {                                                                         \
 554   VEC_ASSERT (vec_ && vec_->num, "last", TDEF);                           \
 555                                                                           \
 556   return &vec_->vec[vec_->num - 1];                                       \
 557 }                                                                         \
 558                                                                           \
 559 static inline TDEF *VEC_OP (TDEF,index)                                   \
 560      (VEC (TDEF) *vec_, size_t ix_ VEC_CHECK_DECL)                        \
 561 {                                                                         \
 562   VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF);                    \
 563                                                                           \
 564   return &vec_->vec[ix_];                                                 \
 565 }                                                                         \
 566                                                                           \
 567 static inline int VEC_OP (TDEF,iterate)                                   \
 568      (VEC (TDEF) *vec_, size_t ix_, TDEF **ptr)                           \
 569 {                                                                         \
 570   if (vec_ && ix_ < vec_->num)                                            \
 571     {                                                                     \
 572       *ptr = &vec_->vec[ix_];                                             \
 573       return 1;                                                           \
 574     }                                                                     \
 575   else                                                                    \
 576     {                                                                     \
 577       *ptr = 0;                                                           \
 578       return 0;                                                           \
 579     }                                                                     \
 580 }                                                                         \
 581                                                                           \
 582 static inline VEC (TDEF) *VEC_OP (TDEF,alloc)                             \
 583      (int alloc_ MEM_STAT_DECL)                                           \
 584 {                                                                         \
 585   return vec_o_reserve (NULL, alloc_ - !alloc_,                           \
 586                         offsetof (VEC(TDEF),vec), sizeof (TDEF)           \
 587                         PASS_MEM_STAT);                                   \
 588 }                                                                         \
 589                                                                           \
 590 static inline size_t VEC_OP (TDEF,embedded_size)                          \
 591      (int alloc_)                                                         \
 592 {                                                                         \
 593   return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF);                \
 594 }                                                                         \
 595                                                                           \
 596 static inline void VEC_OP (TDEF,embedded_init)                            \
 597      (VEC (TDEF) *vec_, int alloc_)                                       \
 598 {                                                                         \
 599   vec_->num = 0;                                                          \
 600   vec_->alloc = alloc_;                                                   \
 601 }                                                                         \
 602                                                                           \
 603 static inline int VEC_OP (TDEF,space)                                     \
 604      (VEC (TDEF) *vec_, int alloc_)                                       \
 605 {                                                                         \
 606   return vec_ ? ((vec_)->alloc - (vec_)->num                              \
 607                  < (size_t)(alloc_ < 0 ? 1 : alloc_)) : alloc_ != 0;      \
 608 }                                                                         \
 609                                                                           \
 610 static inline int VEC_OP (TDEF,reserve)                                   \
 611      (VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL)                        \
 612 {                                                                         \
 613   int extend = VEC_OP (TDEF,space) (*vec_, alloc_);                       \
 614                                                                           \
 615   if (extend)                                                             \
 616     *vec_ = vec_o_reserve (*vec_, alloc_,                                 \
 617                            offsetof (VEC(TDEF),vec), sizeof (TDEF)        \
 618                            PASS_MEM_STAT);                                \
 619                                                                           \
 620   return extend;                                                          \
 621 }                                                                         \
 622                                                                           \
 623 static inline TDEF *VEC_OP (TDEF,quick_push)                              \
 624      (VEC (TDEF) *vec_, const TDEF *obj_ VEC_CHECK_DECL)                  \
 625 {                                                                         \
 626   TDEF *slot_;                                                            \
 627                                                                           \
 628   VEC_ASSERT (vec_->num < vec_->alloc, "push", TDEF);                     \
 629   slot_ = &vec_->vec[vec_->num++];                                        \
 630   if (obj_)                                                               \
 631     *slot_ = *obj_;                                                       \
 632                                                                           \
 633   return slot_;                                                           \
 634 }                                                                         \
 635                                                                           \
 636 static inline TDEF *VEC_OP (TDEF,safe_push)                               \
 637      (VEC (TDEF) **vec_, const TDEF *obj_ VEC_CHECK_DECL MEM_STAT_DECL)   \
 638 {                                                                         \
 639   VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT);                         \
 640                                                                           \
 641   return VEC_OP (TDEF,quick_push) (*vec_, obj_ VEC_CHECK_PASS);           \
 642 }                                                                         \
 643                                                                           \
 644 static inline void VEC_OP (TDEF,pop)                                      \
 645      (VEC (TDEF) *vec_ VEC_CHECK_DECL)                                    \
 646 {                                                                         \
 647   VEC_ASSERT (vec_->num, "pop", TDEF);                                    \
 648   --vec_->num;                                                            \
 649 }                                                                         \
 650                                                                           \
 651 static inline void VEC_OP (TDEF,truncate)                                 \
 652      (VEC (TDEF) *vec_, size_t size_ VEC_CHECK_DECL)                      \
 653 {                                                                         \
 654   VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", TDEF);      \
 655   if (vec_)                                                               \
 656     vec_->num = size_;                                                    \
 657 }                                                                         \
 658                                                                           \
 659 static inline TDEF *VEC_OP (TDEF,replace)                                 \
 660      (VEC (TDEF) *vec_, size_t ix_, const TDEF *obj_ VEC_CHECK_DECL)      \
 661 {                                                                         \
 662   TDEF *slot_;                                                            \
 663                                                                           \
 664   VEC_ASSERT (ix_ < vec_->num, "replace", TDEF);                          \
 665   slot_ = &vec_->vec[ix_];                                                \
 666   if (obj_)                                                               \
 667     *slot_ = *obj_;                                                       \
 668                                                                           \
 669   return slot_;                                                           \
 670 }                                                                         \
 671                                                                           \
 672 static inline TDEF *VEC_OP (TDEF,quick_insert)                            \
 673      (VEC (TDEF) *vec_, size_t ix_, const TDEF *obj_ VEC_CHECK_DECL)      \
 674 {                                                                         \
 675   TDEF *slot_;                                                            \
 676                                                                           \
 677   VEC_ASSERT (vec_->num < vec_->alloc, "insert", TDEF);                   \
 678   VEC_ASSERT (ix_ <= vec_->num, "insert", TDEF);                          \
 679   slot_ = &vec_->vec[ix_];                                                \
 680   memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (TDEF));        \
 681   if (obj_)                                                               \
 682     *slot_ = *obj_;                                                       \
 683                                                                           \
 684   return slot_;                                                           \
 685 }                                                                         \
 686                                                                           \
 687 static inline TDEF *VEC_OP (TDEF,safe_insert)                             \
 688      (VEC (TDEF) **vec_, size_t ix_, const TDEF *obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
 689 {                                                                         \
 690   VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT);                         \
 691                                                                           \
 692   return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS);    \
 693 }                                                                         \
 694                                                                           \
 695 static inline void VEC_OP (TDEF,ordered_remove)                           \
 696      (VEC (TDEF) *vec_, size_t ix_ VEC_CHECK_DECL)                        \
 697 {                                                                         \
 698   TDEF *slot_;                                                            \
 699                                                                           \
 700   VEC_ASSERT (ix_ < vec_->num, "remove", TDEF);                           \
 701   slot_ = &vec_->vec[ix_];                                                \
 702   memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF));        \
 703 }                                                                         \
 704                                                                           \
 705 static inline void VEC_OP (TDEF,unordered_remove)                         \
 706      (VEC (TDEF) *vec_, size_t ix_ VEC_CHECK_DECL)                        \
 707 {                                                                         \
 708   VEC_ASSERT (ix_ < vec_->num, "remove", TDEF);                           \
 709   vec_->vec[ix_] = vec_->vec[--vec_->num];                                \
 710 }                                                                         \
 711                                                                           \
 712 static inline TDEF *VEC_OP (TDEF,address)                                 \
 713      (VEC (TDEF) *vec_)                                                   \
 714 {                                                                         \
 715   return vec_ ? vec_->vec : 0;                                            \
 716 }                                                                         \
 717                                                                           \
 718 struct vec_swallow_trailing_semi
 719 #endif
 720
 721 #endif /* GCC_VEC_H */