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