gcc/vec.h

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004-2018 Free Software Foundation, Inc.
   3    Contributed by Nathan Sidwell <nathan@codesourcery.com>
   4    Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #ifndef GCC_VEC_H
  23 #define GCC_VEC_H
  24
  25 /* Some gen* file have no ggc support as the header file gtype-desc.h is
  26    missing.  Provide these definitions in case ggc.h has not been included.
  27    This is not a problem because any code that runs before gengtype is built
  28    will never need to use GC vectors.*/
  29
  30 extern void ggc_free (void *);
  31 extern size_t ggc_round_alloc_size (size_t requested_size);
  32 extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
  33
  34 /* Templated vector type and associated interfaces.
  35
  36    The interface functions are typesafe and use inline functions,
  37    sometimes backed by out-of-line generic functions.  The vectors are
  38    designed to interoperate with the GTY machinery.
  39
  40    There are both 'index' and 'iterate' accessors.  The index accessor
  41    is implemented by operator[].  The iterator returns a boolean
  42    iteration condition and updates the iteration variable passed by
  43    reference.  Because the iterator will be inlined, the address-of
  44    can be optimized away.
  45
  46    Each operation that increases the number of active elements is
  47    available in 'quick' and 'safe' variants.  The former presumes that
  48    there is sufficient allocated space for the operation to succeed
  49    (it dies if there is not).  The latter will reallocate the
  50    vector, if needed.  Reallocation causes an exponential increase in
  51    vector size.  If you know you will be adding N elements, it would
  52    be more efficient to use the reserve operation before adding the
  53    elements with the 'quick' operation.  This will ensure there are at
  54    least as many elements as you ask for, it will exponentially
  55    increase if there are too few spare slots.  If you want reserve a
  56    specific number of slots, but do not want the exponential increase
  57    (for instance, you know this is the last allocation), use the
  58    reserve_exact operation.  You can also create a vector of a
  59    specific size from the get go.
  60
  61    You should prefer the push and pop operations, as they append and
  62    remove from the end of the vector. If you need to remove several
  63    items in one go, use the truncate operation.  The insert and remove
  64    operations allow you to change elements in the middle of the
  65    vector.  There are two remove operations, one which preserves the
  66    element ordering 'ordered_remove', and one which does not
  67    'unordered_remove'.  The latter function copies the end element
  68    into the removed slot, rather than invoke a memmove operation.  The
  69    'lower_bound' function will determine where to place an item in the
  70    array using insert that will maintain sorted order.
  71
  72    Vectors are template types with three arguments: the type of the
  73    elements in the vector, the allocation strategy, and the physical
  74    layout to use
  75
  76    Four allocation strategies are supported:
  77
  78         - Heap: allocation is done using malloc/free.  This is the
  79           default allocation strategy.
  80
  81         - GC: allocation is done using ggc_alloc/ggc_free.
  82
  83         - GC atomic: same as GC with the exception that the elements
  84           themselves are assumed to be of an atomic type that does
  85           not need to be garbage collected.  This means that marking
  86           routines do not need to traverse the array marking the
  87           individual elements.  This increases the performance of
  88           GC activities.
  89
  90    Two physical layouts are supported:
  91
  92         - Embedded: The vector is structured using the trailing array
  93           idiom.  The last member of the structure is an array of size
  94           1.  When the vector is initially allocated, a single memory
  95           block is created to hold the vector's control data and the
  96           array of elements.  These vectors cannot grow without
  97           reallocation (see discussion on embeddable vectors below).
  98
  99         - Space efficient: The vector is structured as a pointer to an
 100           embedded vector.  This is the default layout.  It means that
 101           vectors occupy a single word of storage before initial
 102           allocation.  Vectors are allowed to grow (the internal
 103           pointer is reallocated but the main vector instance does not
 104           need to relocate).
 105
 106    The type, allocation and layout are specified when the vector is
 107    declared.
 108
 109    If you need to directly manipulate a vector, then the 'address'
 110    accessor will return the address of the start of the vector.  Also
 111    the 'space' predicate will tell you whether there is spare capacity
 112    in the vector.  You will not normally need to use these two functions.
 113
 114    Notes on the different layout strategies
 115
 116    * Embeddable vectors (vec<T, A, vl_embed>)
 117
 118      These vectors are suitable to be embedded in other data
 119      structures so that they can be pre-allocated in a contiguous
 120      memory block.
 121
 122      Embeddable vectors are implemented using the trailing array
 123      idiom, thus they are not resizeable without changing the address
 124      of the vector object itself.  This means you cannot have
 125      variables or fields of embeddable vector type -- always use a
 126      pointer to a vector.  The one exception is the final field of a
 127      structure, which could be a vector type.
 128
 129      You will have to use the embedded_size & embedded_init calls to
 130      create such objects, and they will not be resizeable (so the
 131      'safe' allocation variants are not available).
 132
 133      Properties of embeddable vectors:
 134
 135           - The whole vector and control data are allocated in a single
 136             contiguous block.  It uses the trailing-vector idiom, so
 137             allocation must reserve enough space for all the elements
 138             in the vector plus its control data.
 139           - The vector cannot be re-allocated.
 140           - The vector cannot grow nor shrink.
 141           - No indirections needed for access/manipulation.
 142           - It requires 2 words of storage (prior to vector allocation).
 143
 144
 145    * Space efficient vector (vec<T, A, vl_ptr>)
 146
 147      These vectors can grow dynamically and are allocated together
 148      with their control data.  They are suited to be included in data
 149      structures.  Prior to initial allocation, they only take a single
 150      word of storage.
 151
 152      These vectors are implemented as a pointer to embeddable vectors.
 153      The semantics allow for this pointer to be NULL to represent
 154      empty vectors.  This way, empty vectors occupy minimal space in
 155      the structure containing them.
 156
 157      Properties:
 158
 159         - The whole vector and control data are allocated in a single
 160           contiguous block.
 161         - The whole vector may be re-allocated.
 162         - Vector data may grow and shrink.
 163         - Access and manipulation requires a pointer test and
 164           indirection.
 165         - It requires 1 word of storage (prior to vector allocation).
 166
 167    An example of their use would be,
 168
 169    struct my_struct {
 170      // A space-efficient vector of tree pointers in GC memory.
 171      vec<tree, va_gc, vl_ptr> v;
 172    };
 173
 174    struct my_struct *s;
 175
 176    if (s->v.length ()) { we have some contents }
 177    s->v.safe_push (decl); // append some decl onto the end
 178    for (ix = 0; s->v.iterate (ix, &elt); ix++)
 179      { do something with elt }
 180 */
 181
 182 /* Support function for statistics.  */
 183 extern void dump_vec_loc_statistics (void);
 184
 185 /* Hashtable mapping vec addresses to descriptors.  */
 186 extern htab_t vec_mem_usage_hash;
 187
 188 /* Control data for vectors.  This contains the number of allocated
 189    and used slots inside a vector.  */
 190
 191 struct vec_prefix
 192 {
 193   /* FIXME - These fields should be private, but we need to cater to
 194              compilers that have stricter notions of PODness for types.  */
 195
 196   /* Memory allocation support routines in vec.c.  */
 197   void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
 198   void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO);
 199   static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
 200   static unsigned calculate_allocation_1 (unsigned, unsigned);
 201
 202   /* Note that vec_prefix should be a base class for vec, but we use
 203      offsetof() on vector fields of tree structures (e.g.,
 204      tree_binfo::base_binfos), and offsetof only supports base types.
 205
 206      To compensate, we make vec_prefix a field inside vec and make
 207      vec a friend class of vec_prefix so it can access its fields.  */
 208   template <typename, typename, typename> friend struct vec;
 209
 210   /* The allocator types also need access to our internals.  */
 211   friend struct va_gc;
 212   friend struct va_gc_atomic;
 213   friend struct va_heap;
 214
 215   unsigned m_alloc : 31;
 216   unsigned m_using_auto_storage : 1;
 217   unsigned m_num;
 218 };
 219
 220 /* Calculate the number of slots to reserve a vector, making sure that
 221    RESERVE slots are free.  If EXACT grow exactly, otherwise grow
 222    exponentially.  PFX is the control data for the vector.  */
 223
 224 inline unsigned
 225 vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
 226                                   bool exact)
 227 {
 228   if (exact)
 229     return (pfx ? pfx->m_num : 0) + reserve;
 230   else if (!pfx)
 231     return MAX (4, reserve);
 232   return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
 233 }
 234
 235 template<typename, typename, typename> struct vec;
 236
 237 /* Valid vector layouts
 238
 239    vl_embed     - Embeddable vector that uses the trailing array idiom.
 240    vl_ptr       - Space efficient vector that uses a pointer to an
 241                   embeddable vector.  */
 242 struct vl_embed { };
 243 struct vl_ptr { };
 244
 245
 246 /* Types of supported allocations
 247
 248    va_heap      - Allocation uses malloc/free.
 249    va_gc        - Allocation uses ggc_alloc.
 250    va_gc_atomic - Same as GC, but individual elements of the array
 251                   do not need to be marked during collection.  */
 252
 253 /* Allocator type for heap vectors.  */
 254 struct va_heap
 255 {
 256   /* Heap vectors are frequently regular instances, so use the vl_ptr
 257      layout for them.  */
 258   typedef vl_ptr default_layout;
 259
 260   template<typename T>
 261   static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
 262                        CXX_MEM_STAT_INFO);
 263
 264   template<typename T>
 265   static void release (vec<T, va_heap, vl_embed> *&);
 266 };
 267
 268
 269 /* Allocator for heap memory.  Ensure there are at least RESERVE free
 270    slots in V.  If EXACT is true, grow exactly, else grow
 271    exponentially.  As a special case, if the vector had not been
 272    allocated and RESERVE is 0, no vector will be created.  */
 273
 274 template<typename T>
 275 inline void
 276 va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
 277                   MEM_STAT_DECL)
 278 {
 279   unsigned alloc
 280     = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
 281   gcc_checking_assert (alloc);
 282
 283   if (GATHER_STATISTICS && v)
 284     v->m_vecpfx.release_overhead (v, v->allocated (), false);
 285
 286   size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
 287   unsigned nelem = v ? v->length () : 0;
 288   v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
 289   v->embedded_init (alloc, nelem);
 290
 291   if (GATHER_STATISTICS)
 292     v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT);
 293 }
 294
 295
 296 /* Free the heap space allocated for vector V.  */
 297
 298 template<typename T>
 299 void
 300 va_heap::release (vec<T, va_heap, vl_embed> *&v)
 301 {
 302   if (v == NULL)
 303     return;
 304
 305   if (GATHER_STATISTICS)
 306     v->m_vecpfx.release_overhead (v, v->allocated (), true);
 307   ::free (v);
 308   v = NULL;
 309 }
 310
 311
 312 /* Allocator type for GC vectors.  Notice that we need the structure
 313    declaration even if GC is not enabled.  */
 314
 315 struct va_gc
 316 {
 317   /* Use vl_embed as the default layout for GC vectors.  Due to GTY
 318      limitations, GC vectors must always be pointers, so it is more
 319      efficient to use a pointer to the vl_embed layout, rather than
 320      using a pointer to a pointer as would be the case with vl_ptr.  */
 321   typedef vl_embed default_layout;
 322
 323   template<typename T, typename A>
 324   static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
 325                        CXX_MEM_STAT_INFO);
 326
 327   template<typename T, typename A>
 328   static void release (vec<T, A, vl_embed> *&v);
 329 };
 330
 331
 332 /* Free GC memory used by V and reset V to NULL.  */
 333
 334 template<typename T, typename A>
 335 inline void
 336 va_gc::release (vec<T, A, vl_embed> *&v)
 337 {
 338   if (v)
 339     ::ggc_free (v);
 340   v = NULL;
 341 }
 342
 343
 344 /* Allocator for GC memory.  Ensure there are at least RESERVE free
 345    slots in V.  If EXACT is true, grow exactly, else grow
 346    exponentially.  As a special case, if the vector had not been
 347    allocated and RESERVE is 0, no vector will be created.  */
 348
 349 template<typename T, typename A>
 350 void
 351 va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
 352                 MEM_STAT_DECL)
 353 {
 354   unsigned alloc
 355     = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
 356   if (!alloc)
 357     {
 358       ::ggc_free (v);
 359       v = NULL;
 360       return;
 361     }
 362
 363   /* Calculate the amount of space we want.  */
 364   size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
 365
 366   /* Ask the allocator how much space it will really give us.  */
 367   size = ::ggc_round_alloc_size (size);
 368
 369   /* Adjust the number of slots accordingly.  */
 370   size_t vec_offset = sizeof (vec_prefix);
 371   size_t elt_size = sizeof (T);
 372   alloc = (size - vec_offset) / elt_size;
 373
 374   /* And finally, recalculate the amount of space we ask for.  */
 375   size = vec_offset + alloc * elt_size;
 376
 377   unsigned nelem = v ? v->length () : 0;
 378   v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
 379                                                                PASS_MEM_STAT));
 380   v->embedded_init (alloc, nelem);
 381 }
 382
 383
 384 /* Allocator type for GC vectors.  This is for vectors of types
 385    atomics w.r.t. collection, so allocation and deallocation is
 386    completely inherited from va_gc.  */
 387 struct va_gc_atomic : va_gc
 388 {
 389 };
 390
 391
 392 /* Generic vector template.  Default values for A and L indicate the
 393    most commonly used strategies.
 394
 395    FIXME - Ideally, they would all be vl_ptr to encourage using regular
 396            instances for vectors, but the existing GTY machinery is limited
 397            in that it can only deal with GC objects that are pointers
 398            themselves.
 399
 400            This means that vector operations that need to deal with
 401            potentially NULL pointers, must be provided as free
 402            functions (see the vec_safe_* functions above).  */
 403 template<typename T,
 404          typename A = va_heap,
 405          typename L = typename A::default_layout>
 406 struct GTY((user)) vec
 407 {
 408 };
 409
 410 /* Generic vec<> debug helpers.
 411
 412    These need to be instantiated for each vec<TYPE> used throughout
 413    the compiler like this:
 414
 415     DEFINE_DEBUG_VEC (TYPE)
 416
 417    The reason we have a debug_helper() is because GDB can't
 418    disambiguate a plain call to debug(some_vec), and it must be called
 419    like debug<TYPE>(some_vec).  */
 420
 421 template<typename T>
 422 void
 423 debug_helper (vec<T> &ref)
 424 {
 425   unsigned i;
 426   for (i = 0; i < ref.length (); ++i)
 427     {
 428       fprintf (stderr, "[%d] = ", i);
 429       debug_slim (ref[i]);
 430       fputc ('\n', stderr);
 431     }
 432 }
 433
 434 /* We need a separate va_gc variant here because default template
 435    argument for functions cannot be used in c++-98.  Once this
 436    restriction is removed, those variant should be folded with the
 437    above debug_helper.  */
 438
 439 template<typename T>
 440 void
 441 debug_helper (vec<T, va_gc> &ref)
 442 {
 443   unsigned i;
 444   for (i = 0; i < ref.length (); ++i)
 445     {
 446       fprintf (stderr, "[%d] = ", i);
 447       debug_slim (ref[i]);
 448       fputc ('\n', stderr);
 449     }
 450 }
 451
 452 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
 453    functions for a type T.  */
 454
 455 #define DEFINE_DEBUG_VEC(T) \
 456   template void debug_helper (vec<T> &);                \
 457   template void debug_helper (vec<T, va_gc> &);         \
 458   /* Define the vec<T> debug functions.  */             \
 459   DEBUG_FUNCTION void                                   \
 460   debug (vec<T> &ref)                                   \
 461   {                                                     \
 462     debug_helper <T> (ref);                             \
 463   }                                                     \
 464   DEBUG_FUNCTION void                                   \
 465   debug (vec<T> *ptr)                                   \
 466   {                                                     \
 467     if (ptr)                                            \
 468       debug (*ptr);                                     \
 469     else                                                \
 470       fprintf (stderr, "<nil>\n");                      \
 471   }                                                     \
 472   /* Define the vec<T, va_gc> debug functions.  */      \
 473   DEBUG_FUNCTION void                                   \
 474   debug (vec<T, va_gc> &ref)                            \
 475   {                                                     \
 476     debug_helper <T> (ref);                             \
 477   }                                                     \
 478   DEBUG_FUNCTION void                                   \
 479   debug (vec<T, va_gc> *ptr)                            \
 480   {                                                     \
 481     if (ptr)                                            \
 482       debug (*ptr);                                     \
 483     else                                                \
 484       fprintf (stderr, "<nil>\n");                      \
 485   }
 486
 487 /* Default-construct N elements in DST.  */
 488
 489 template <typename T>
 490 inline void
 491 vec_default_construct (T *dst, unsigned n)
 492 {
 493   for ( ; n; ++dst, --n)
 494     ::new (static_cast<void*>(dst)) T ();
 495 }
 496
 497 /* Copy-construct N elements in DST from *SRC.  */
 498
 499 template <typename T>
 500 inline void
 501 vec_copy_construct (T *dst, const T *src, unsigned n)
 502 {
 503   for ( ; n; ++dst, ++src, --n)
 504     ::new (static_cast<void*>(dst)) T (*src);
 505 }
 506
 507 /* Type to provide NULL values for vec<T, A, L>.  This is used to
 508    provide nil initializers for vec instances.  Since vec must be
 509    a POD, we cannot have proper ctor/dtor for it.  To initialize
 510    a vec instance, you can assign it the value vNULL.  This isn't
 511    needed for file-scope and function-local static vectors, which
 512    are zero-initialized by default.  */
 513 struct vnull
 514 {
 515   template <typename T, typename A, typename L>
 516   CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); }
 517 };
 518 extern vnull vNULL;
 519
 520
 521 /* Embeddable vector.  These vectors are suitable to be embedded
 522    in other data structures so that they can be pre-allocated in a
 523    contiguous memory block.
 524
 525    Embeddable vectors are implemented using the trailing array idiom,
 526    thus they are not resizeable without changing the address of the
 527    vector object itself.  This means you cannot have variables or
 528    fields of embeddable vector type -- always use a pointer to a
 529    vector.  The one exception is the final field of a structure, which
 530    could be a vector type.
 531
 532    You will have to use the embedded_size & embedded_init calls to
 533    create such objects, and they will not be resizeable (so the 'safe'
 534    allocation variants are not available).
 535
 536    Properties:
 537
 538         - The whole vector and control data are allocated in a single
 539           contiguous block.  It uses the trailing-vector idiom, so
 540           allocation must reserve enough space for all the elements
 541           in the vector plus its control data.
 542         - The vector cannot be re-allocated.
 543         - The vector cannot grow nor shrink.
 544         - No indirections needed for access/manipulation.
 545         - It requires 2 words of storage (prior to vector allocation).  */
 546
 547 template<typename T, typename A>
 548 struct GTY((user)) vec<T, A, vl_embed>
 549 {
 550 public:
 551   unsigned allocated (void) const { return m_vecpfx.m_alloc; }
 552   unsigned length (void) const { return m_vecpfx.m_num; }
 553   bool is_empty (void) const { return m_vecpfx.m_num == 0; }
 554   T *address (void) { return m_vecdata; }
 555   const T *address (void) const { return m_vecdata; }
 556   T *begin () { return address (); }
 557   const T *begin () const { return address (); }
 558   T *end () { return address () + length (); }
 559   const T *end () const { return address () + length (); }
 560   const T &operator[] (unsigned) const;
 561   T &operator[] (unsigned);
 562   T &last (void);
 563   bool space (unsigned) const;
 564   bool iterate (unsigned, T *) const;
 565   bool iterate (unsigned, T **) const;
 566   vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
 567   void splice (const vec &);
 568   void splice (const vec *src);
 569   T *quick_push (const T &);
 570   T &pop (void);
 571   void truncate (unsigned);
 572   void quick_insert (unsigned, const T &);
 573   void ordered_remove (unsigned);
 574   void unordered_remove (unsigned);
 575   void block_remove (unsigned, unsigned);
 576   void qsort (int (*) (const void *, const void *));
 577   T *bsearch (const void *key, int (*compar)(const void *, const void *));
 578   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
 579   bool contains (const T &search) const;
 580   static size_t embedded_size (unsigned);
 581   void embedded_init (unsigned, unsigned = 0, unsigned = 0);
 582   void quick_grow (unsigned len);
 583   void quick_grow_cleared (unsigned len);
 584
 585   /* vec class can access our internal data and functions.  */
 586   template <typename, typename, typename> friend struct vec;
 587
 588   /* The allocator types also need access to our internals.  */
 589   friend struct va_gc;
 590   friend struct va_gc_atomic;
 591   friend struct va_heap;
 592
 593   /* FIXME - These fields should be private, but we need to cater to
 594              compilers that have stricter notions of PODness for types.  */
 595   vec_prefix m_vecpfx;
 596   T m_vecdata[1];
 597 };
 598
 599
 600 /* Convenience wrapper functions to use when dealing with pointers to
 601    embedded vectors.  Some functionality for these vectors must be
 602    provided via free functions for these reasons:
 603
 604         1- The pointer may be NULL (e.g., before initial allocation).
 605
 606         2- When the vector needs to grow, it must be reallocated, so
 607            the pointer will change its value.
 608
 609    Because of limitations with the current GC machinery, all vectors
 610    in GC memory *must* be pointers.  */
 611
 612
 613 /* If V contains no room for NELEMS elements, return false. Otherwise,
 614    return true.  */
 615 template<typename T, typename A>
 616 inline bool
 617 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
 618 {
 619   return v ? v->space (nelems) : nelems == 0;
 620 }
 621
 622
 623 /* If V is NULL, return 0.  Otherwise, return V->length().  */
 624 template<typename T, typename A>
 625 inline unsigned
 626 vec_safe_length (const vec<T, A, vl_embed> *v)
 627 {
 628   return v ? v->length () : 0;
 629 }
 630
 631
 632 /* If V is NULL, return NULL.  Otherwise, return V->address().  */
 633 template<typename T, typename A>
 634 inline T *
 635 vec_safe_address (vec<T, A, vl_embed> *v)
 636 {
 637   return v ? v->address () : NULL;
 638 }
 639
 640
 641 /* If V is NULL, return true.  Otherwise, return V->is_empty().  */
 642 template<typename T, typename A>
 643 inline bool
 644 vec_safe_is_empty (vec<T, A, vl_embed> *v)
 645 {
 646   return v ? v->is_empty () : true;
 647 }
 648
 649 /* If V does not have space for NELEMS elements, call
 650    V->reserve(NELEMS, EXACT).  */
 651 template<typename T, typename A>
 652 inline bool
 653 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
 654                   CXX_MEM_STAT_INFO)
 655 {
 656   bool extend = nelems ? !vec_safe_space (v, nelems) : false;
 657   if (extend)
 658     A::reserve (v, nelems, exact PASS_MEM_STAT);
 659   return extend;
 660 }
 661
 662 template<typename T, typename A>
 663 inline bool
 664 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
 665                         CXX_MEM_STAT_INFO)
 666 {
 667   return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
 668 }
 669
 670
 671 /* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
 672    is 0, V is initialized to NULL.  */
 673
 674 template<typename T, typename A>
 675 inline void
 676 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
 677 {
 678   v = NULL;
 679   vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
 680 }
 681
 682
 683 /* Free the GC memory allocated by vector V and set it to NULL.  */
 684
 685 template<typename T, typename A>
 686 inline void
 687 vec_free (vec<T, A, vl_embed> *&v)
 688 {
 689   A::release (v);
 690 }
 691
 692
 693 /* Grow V to length LEN.  Allocate it, if necessary.  */
 694 template<typename T, typename A>
 695 inline void
 696 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
 697 {
 698   unsigned oldlen = vec_safe_length (v);
 699   gcc_checking_assert (len >= oldlen);
 700   vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
 701   v->quick_grow (len);
 702 }
 703
 704
 705 /* If V is NULL, allocate it.  Call V->safe_grow_cleared(LEN).  */
 706 template<typename T, typename A>
 707 inline void
 708 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
 709 {
 710   unsigned oldlen = vec_safe_length (v);
 711   vec_safe_grow (v, len PASS_MEM_STAT);
 712   vec_default_construct (v->address () + oldlen, len - oldlen);
 713 }
 714
 715
 716 /* If V is NULL return false, otherwise return V->iterate(IX, PTR).  */
 717 template<typename T, typename A>
 718 inline bool
 719 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
 720 {
 721   if (v)
 722     return v->iterate (ix, ptr);
 723   else
 724     {
 725       *ptr = 0;
 726       return false;
 727     }
 728 }
 729
 730 template<typename T, typename A>
 731 inline bool
 732 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
 733 {
 734   if (v)
 735     return v->iterate (ix, ptr);
 736   else
 737     {
 738       *ptr = 0;
 739       return false;
 740     }
 741 }
 742
 743
 744 /* If V has no room for one more element, reallocate it.  Then call
 745    V->quick_push(OBJ).  */
 746 template<typename T, typename A>
 747 inline T *
 748 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
 749 {
 750   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 751   return v->quick_push (obj);
 752 }
 753
 754
 755 /* if V has no room for one more element, reallocate it.  Then call
 756    V->quick_insert(IX, OBJ).  */
 757 template<typename T, typename A>
 758 inline void
 759 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
 760                  CXX_MEM_STAT_INFO)
 761 {
 762   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 763   v->quick_insert (ix, obj);
 764 }
 765
 766
 767 /* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
 768 template<typename T, typename A>
 769 inline void
 770 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
 771 {
 772   if (v)
 773     v->truncate (size);
 774 }
 775
 776
 777 /* If SRC is not NULL, return a pointer to a copy of it.  */
 778 template<typename T, typename A>
 779 inline vec<T, A, vl_embed> *
 780 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
 781 {
 782   return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
 783 }
 784
 785 /* Copy the elements from SRC to the end of DST as if by memcpy.
 786    Reallocate DST, if necessary.  */
 787 template<typename T, typename A>
 788 inline void
 789 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
 790                  CXX_MEM_STAT_INFO)
 791 {
 792   unsigned src_len = vec_safe_length (src);
 793   if (src_len)
 794     {
 795       vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
 796                               PASS_MEM_STAT);
 797       dst->splice (*src);
 798     }
 799 }
 800
 801 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
 802    size of the vector and so should be used with care.  */
 803
 804 template<typename T, typename A>
 805 inline bool
 806 vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
 807 {
 808   return v ? v->contains (search) : false;
 809 }
 810
 811 /* Index into vector.  Return the IX'th element.  IX must be in the
 812    domain of the vector.  */
 813
 814 template<typename T, typename A>
 815 inline const T &
 816 vec<T, A, vl_embed>::operator[] (unsigned ix) const
 817 {
 818   gcc_checking_assert (ix < m_vecpfx.m_num);
 819   return m_vecdata[ix];
 820 }
 821
 822 template<typename T, typename A>
 823 inline T &
 824 vec<T, A, vl_embed>::operator[] (unsigned ix)
 825 {
 826   gcc_checking_assert (ix < m_vecpfx.m_num);
 827   return m_vecdata[ix];
 828 }
 829
 830
 831 /* Get the final element of the vector, which must not be empty.  */
 832
 833 template<typename T, typename A>
 834 inline T &
 835 vec<T, A, vl_embed>::last (void)
 836 {
 837   gcc_checking_assert (m_vecpfx.m_num > 0);
 838   return (*this)[m_vecpfx.m_num - 1];
 839 }
 840
 841
 842 /* If this vector has space for NELEMS additional entries, return
 843    true.  You usually only need to use this if you are doing your
 844    own vector reallocation, for instance on an embedded vector.  This
 845    returns true in exactly the same circumstances that vec::reserve
 846    will.  */
 847
 848 template<typename T, typename A>
 849 inline bool
 850 vec<T, A, vl_embed>::space (unsigned nelems) const
 851 {
 852   return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
 853 }
 854
 855
 856 /* Return iteration condition and update PTR to point to the IX'th
 857    element of this vector.  Use this to iterate over the elements of a
 858    vector as follows,
 859
 860      for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
 861        continue;  */
 862
 863 template<typename T, typename A>
 864 inline bool
 865 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
 866 {
 867   if (ix < m_vecpfx.m_num)
 868     {
 869       *ptr = m_vecdata[ix];
 870       return true;
 871     }
 872   else
 873     {
 874       *ptr = 0;
 875       return false;
 876     }
 877 }
 878
 879
 880 /* Return iteration condition and update *PTR to point to the
 881    IX'th element of this vector.  Use this to iterate over the
 882    elements of a vector as follows,
 883
 884      for (ix = 0; v->iterate (ix, &ptr); ix++)
 885        continue;
 886
 887    This variant is for vectors of objects.  */
 888
 889 template<typename T, typename A>
 890 inline bool
 891 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
 892 {
 893   if (ix < m_vecpfx.m_num)
 894     {
 895       *ptr = CONST_CAST (T *, &m_vecdata[ix]);
 896       return true;
 897     }
 898   else
 899     {
 900       *ptr = 0;
 901       return false;
 902     }
 903 }
 904
 905
 906 /* Return a pointer to a copy of this vector.  */
 907
 908 template<typename T, typename A>
 909 inline vec<T, A, vl_embed> *
 910 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
 911 {
 912   vec<T, A, vl_embed> *new_vec = NULL;
 913   unsigned len = length ();
 914   if (len)
 915     {
 916       vec_alloc (new_vec, len PASS_MEM_STAT);
 917       new_vec->embedded_init (len, len);
 918       vec_copy_construct (new_vec->address (), m_vecdata, len);
 919     }
 920   return new_vec;
 921 }
 922
 923
 924 /* Copy the elements from SRC to the end of this vector as if by memcpy.
 925    The vector must have sufficient headroom available.  */
 926
 927 template<typename T, typename A>
 928 inline void
 929 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
 930 {
 931   unsigned len = src.length ();
 932   if (len)
 933     {
 934       gcc_checking_assert (space (len));
 935       vec_copy_construct (end (), src.address (), len);
 936       m_vecpfx.m_num += len;
 937     }
 938 }
 939
 940 template<typename T, typename A>
 941 inline void
 942 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
 943 {
 944   if (src)
 945     splice (*src);
 946 }
 947
 948
 949 /* Push OBJ (a new element) onto the end of the vector.  There must be
 950    sufficient space in the vector.  Return a pointer to the slot
 951    where OBJ was inserted.  */
 952
 953 template<typename T, typename A>
 954 inline T *
 955 vec<T, A, vl_embed>::quick_push (const T &obj)
 956 {
 957   gcc_checking_assert (space (1));
 958   T *slot = &m_vecdata[m_vecpfx.m_num++];
 959   *slot = obj;
 960   return slot;
 961 }
 962
 963
 964 /* Pop and return the last element off the end of the vector.  */
 965
 966 template<typename T, typename A>
 967 inline T &
 968 vec<T, A, vl_embed>::pop (void)
 969 {
 970   gcc_checking_assert (length () > 0);
 971   return m_vecdata[--m_vecpfx.m_num];
 972 }
 973
 974
 975 /* Set the length of the vector to SIZE.  The new length must be less
 976    than or equal to the current length.  This is an O(1) operation.  */
 977
 978 template<typename T, typename A>
 979 inline void
 980 vec<T, A, vl_embed>::truncate (unsigned size)
 981 {
 982   gcc_checking_assert (length () >= size);
 983   m_vecpfx.m_num = size;
 984 }
 985
 986
 987 /* Insert an element, OBJ, at the IXth position of this vector.  There
 988    must be sufficient space.  */
 989
 990 template<typename T, typename A>
 991 inline void
 992 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
 993 {
 994   gcc_checking_assert (length () < allocated ());
 995   gcc_checking_assert (ix <= length ());
 996   T *slot = &m_vecdata[ix];
 997   memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
 998   *slot = obj;
 999 }
1000
1001
1002 /* Remove an element from the IXth position of this vector.  Ordering of
1003    remaining elements is preserved.  This is an O(N) operation due to
1004    memmove.  */
1005
1006 template<typename T, typename A>
1007 inline void
1008 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1009 {
1010   gcc_checking_assert (ix < length ());
1011   T *slot = &m_vecdata[ix];
1012   memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1013 }
1014
1015
1016 /* Remove an element from the IXth position of this vector.  Ordering of
1017    remaining elements is destroyed.  This is an O(1) operation.  */
1018
1019 template<typename T, typename A>
1020 inline void
1021 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1022 {
1023   gcc_checking_assert (ix < length ());
1024   m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1025 }
1026
1027
1028 /* Remove LEN elements starting at the IXth.  Ordering is retained.
1029    This is an O(N) operation due to memmove.  */
1030
1031 template<typename T, typename A>
1032 inline void
1033 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1034 {
1035   gcc_checking_assert (ix + len <= length ());
1036   T *slot = &m_vecdata[ix];
1037   m_vecpfx.m_num -= len;
1038   memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1039 }
1040
1041
1042 /* Sort the contents of this vector with qsort.  CMP is the comparison
1043    function to pass to qsort.  */
1044
1045 template<typename T, typename A>
1046 inline void
1047 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1048 {
1049   if (length () > 1)
1050     ::qsort (address (), length (), sizeof (T), cmp);
1051 }
1052
1053
1054 /* Search the contents of the sorted vector with a binary search.
1055    CMP is the comparison function to pass to bsearch.  */
1056
1057 template<typename T, typename A>
1058 inline T *
1059 vec<T, A, vl_embed>::bsearch (const void *key,
1060                               int (*compar) (const void *, const void *))
1061 {
1062   const void *base = this->address ();
1063   size_t nmemb = this->length ();
1064   size_t size = sizeof (T);
1065   /* The following is a copy of glibc stdlib-bsearch.h.  */
1066   size_t l, u, idx;
1067   const void *p;
1068   int comparison;
1069
1070   l = 0;
1071   u = nmemb;
1072   while (l < u)
1073     {
1074       idx = (l + u) / 2;
1075       p = (const void *) (((const char *) base) + (idx * size));
1076       comparison = (*compar) (key, p);
1077       if (comparison < 0)
1078         u = idx;
1079       else if (comparison > 0)
1080         l = idx + 1;
1081       else
1082         return (T *)const_cast<void *>(p);
1083     }
1084
1085   return NULL;
1086 }
1087
1088 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
1089    size of the vector and so should be used with care.  */
1090
1091 template<typename T, typename A>
1092 inline bool
1093 vec<T, A, vl_embed>::contains (const T &search) const
1094 {
1095   unsigned int len = length ();
1096   for (unsigned int i = 0; i < len; i++)
1097     if ((*this)[i] == search)
1098       return true;
1099
1100   return false;
1101 }
1102
1103 /* Find and return the first position in which OBJ could be inserted
1104    without changing the ordering of this vector.  LESSTHAN is a
1105    function that returns true if the first argument is strictly less
1106    than the second.  */
1107
1108 template<typename T, typename A>
1109 unsigned
1110 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1111   const
1112 {
1113   unsigned int len = length ();
1114   unsigned int half, middle;
1115   unsigned int first = 0;
1116   while (len > 0)
1117     {
1118       half = len / 2;
1119       middle = first;
1120       middle += half;
1121       T middle_elem = (*this)[middle];
1122       if (lessthan (middle_elem, obj))
1123         {
1124           first = middle;
1125           ++first;
1126           len = len - half - 1;
1127         }
1128       else
1129         len = half;
1130     }
1131   return first;
1132 }
1133
1134
1135 /* Return the number of bytes needed to embed an instance of an
1136    embeddable vec inside another data structure.
1137
1138    Use these methods to determine the required size and initialization
1139    of a vector V of type T embedded within another structure (as the
1140    final member):
1141
1142    size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1143    void v->embedded_init (unsigned alloc, unsigned num);
1144
1145    These allow the caller to perform the memory allocation.  */
1146
1147 template<typename T, typename A>
1148 inline size_t
1149 vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1150 {
1151   typedef vec<T, A, vl_embed> vec_embedded;
1152   return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
1153 }
1154
1155
1156 /* Initialize the vector to contain room for ALLOC elements and
1157    NUM active elements.  */
1158
1159 template<typename T, typename A>
1160 inline void
1161 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1162 {
1163   m_vecpfx.m_alloc = alloc;
1164   m_vecpfx.m_using_auto_storage = aut;
1165   m_vecpfx.m_num = num;
1166 }
1167
1168
1169 /* Grow the vector to a specific length.  LEN must be as long or longer than
1170    the current length.  The new elements are uninitialized.  */
1171
1172 template<typename T, typename A>
1173 inline void
1174 vec<T, A, vl_embed>::quick_grow (unsigned len)
1175 {
1176   gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1177   m_vecpfx.m_num = len;
1178 }
1179
1180
1181 /* Grow the vector to a specific length.  LEN must be as long or longer than
1182    the current length.  The new elements are initialized to zero.  */
1183
1184 template<typename T, typename A>
1185 inline void
1186 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1187 {
1188   unsigned oldlen = length ();
1189   size_t growby = len - oldlen;
1190   quick_grow (len);
1191   if (growby != 0)
1192     vec_default_construct (address () + oldlen, growby);
1193 }
1194
1195 /* Garbage collection support for vec<T, A, vl_embed>.  */
1196
1197 template<typename T>
1198 void
1199 gt_ggc_mx (vec<T, va_gc> *v)
1200 {
1201   extern void gt_ggc_mx (T &);
1202   for (unsigned i = 0; i < v->length (); i++)
1203     gt_ggc_mx ((*v)[i]);
1204 }
1205
1206 template<typename T>
1207 void
1208 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1209 {
1210   /* Nothing to do.  Vectors of atomic types wrt GC do not need to
1211      be traversed.  */
1212 }
1213
1214
1215 /* PCH support for vec<T, A, vl_embed>.  */
1216
1217 template<typename T, typename A>
1218 void
1219 gt_pch_nx (vec<T, A, vl_embed> *v)
1220 {
1221   extern void gt_pch_nx (T &);
1222   for (unsigned i = 0; i < v->length (); i++)
1223     gt_pch_nx ((*v)[i]);
1224 }
1225
1226 template<typename T, typename A>
1227 void
1228 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1229 {
1230   for (unsigned i = 0; i < v->length (); i++)
1231     op (&((*v)[i]), cookie);
1232 }
1233
1234 template<typename T, typename A>
1235 void
1236 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1237 {
1238   extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1239   for (unsigned i = 0; i < v->length (); i++)
1240     gt_pch_nx (&((*v)[i]), op, cookie);
1241 }
1242
1243
1244 /* Space efficient vector.  These vectors can grow dynamically and are
1245    allocated together with their control data.  They are suited to be
1246    included in data structures.  Prior to initial allocation, they
1247    only take a single word of storage.
1248
1249    These vectors are implemented as a pointer to an embeddable vector.
1250    The semantics allow for this pointer to be NULL to represent empty
1251    vectors.  This way, empty vectors occupy minimal space in the
1252    structure containing them.
1253
1254    Properties:
1255
1256         - The whole vector and control data are allocated in a single
1257           contiguous block.
1258         - The whole vector may be re-allocated.
1259         - Vector data may grow and shrink.
1260         - Access and manipulation requires a pointer test and
1261           indirection.
1262         - It requires 1 word of storage (prior to vector allocation).
1263
1264
1265    Limitations:
1266
1267    These vectors must be PODs because they are stored in unions.
1268    (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1269    As long as we use C++03, we cannot have constructors nor
1270    destructors in classes that are stored in unions.  */
1271
1272 template<typename T>
1273 struct vec<T, va_heap, vl_ptr>
1274 {
1275 public:
1276   /* Memory allocation and deallocation for the embedded vector.
1277      Needed because we cannot have proper ctors/dtors defined.  */
1278   void create (unsigned nelems CXX_MEM_STAT_INFO);
1279   void release (void);
1280
1281   /* Vector operations.  */
1282   bool exists (void) const
1283   { return m_vec != NULL; }
1284
1285   bool is_empty (void) const
1286   { return m_vec ? m_vec->is_empty () : true; }
1287
1288   unsigned length (void) const
1289   { return m_vec ? m_vec->length () : 0; }
1290
1291   T *address (void)
1292   { return m_vec ? m_vec->m_vecdata : NULL; }
1293
1294   const T *address (void) const
1295   { return m_vec ? m_vec->m_vecdata : NULL; }
1296
1297   T *begin () { return address (); }
1298   const T *begin () const { return address (); }
1299   T *end () { return begin () + length (); }
1300   const T *end () const { return begin () + length (); }
1301   const T &operator[] (unsigned ix) const
1302   { return (*m_vec)[ix]; }
1303
1304   bool operator!=(const vec &other) const
1305   { return !(*this == other); }
1306
1307   bool operator==(const vec &other) const
1308   { return address () == other.address (); }
1309
1310   T &operator[] (unsigned ix)
1311   { return (*m_vec)[ix]; }
1312
1313   T &last (void)
1314   { return m_vec->last (); }
1315
1316   bool space (int nelems) const
1317   { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1318
1319   bool iterate (unsigned ix, T *p) const;
1320   bool iterate (unsigned ix, T **p) const;
1321   vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1322   bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1323   bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1324   void splice (const vec &);
1325   void safe_splice (const vec & CXX_MEM_STAT_INFO);
1326   T *quick_push (const T &);
1327   T *safe_push (const T &CXX_MEM_STAT_INFO);
1328   T &pop (void);
1329   void truncate (unsigned);
1330   void safe_grow (unsigned CXX_MEM_STAT_INFO);
1331   void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
1332   void quick_grow (unsigned);
1333   void quick_grow_cleared (unsigned);
1334   void quick_insert (unsigned, const T &);
1335   void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1336   void ordered_remove (unsigned);
1337   void unordered_remove (unsigned);
1338   void block_remove (unsigned, unsigned);
1339   void qsort (int (*) (const void *, const void *));
1340   T *bsearch (const void *key, int (*compar)(const void *, const void *));
1341   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1342   bool contains (const T &search) const;
1343
1344   bool using_auto_storage () const;
1345
1346   /* FIXME - This field should be private, but we need to cater to
1347              compilers that have stricter notions of PODness for types.  */
1348   vec<T, va_heap, vl_embed> *m_vec;
1349 };
1350
1351
1352 /* auto_vec is a subclass of vec that automatically manages creating and
1353    releasing the internal vector. If N is non zero then it has N elements of
1354    internal storage.  The default is no internal storage, and you probably only
1355    want to ask for internal storage for vectors on the stack because if the
1356    size of the vector is larger than the internal storage that space is wasted.
1357    */
1358 template<typename T, size_t N = 0>
1359 class auto_vec : public vec<T, va_heap>
1360 {
1361 public:
1362   auto_vec ()
1363   {
1364     m_auto.embedded_init (MAX (N, 2), 0, 1);
1365     this->m_vec = &m_auto;
1366   }
1367
1368   auto_vec (size_t s)
1369   {
1370     if (s > N)
1371       {
1372         this->create (s);
1373         return;
1374       }
1375
1376     m_auto.embedded_init (MAX (N, 2), 0, 1);
1377     this->m_vec = &m_auto;
1378   }
1379
1380   ~auto_vec ()
1381   {
1382     this->release ();
1383   }
1384
1385 private:
1386   vec<T, va_heap, vl_embed> m_auto;
1387   T m_data[MAX (N - 1, 1)];
1388 };
1389
1390 /* auto_vec is a sub class of vec whose storage is released when it is
1391   destroyed. */
1392 template<typename T>
1393 class auto_vec<T, 0> : public vec<T, va_heap>
1394 {
1395 public:
1396   auto_vec () { this->m_vec = NULL; }
1397   auto_vec (size_t n) { this->create (n); }
1398   ~auto_vec () { this->release (); }
1399 };
1400
1401
1402 /* Allocate heap memory for pointer V and create the internal vector
1403    with space for NELEMS elements.  If NELEMS is 0, the internal
1404    vector is initialized to empty.  */
1405
1406 template<typename T>
1407 inline void
1408 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1409 {
1410   v = new vec<T>;
1411   v->create (nelems PASS_MEM_STAT);
1412 }
1413
1414
1415 /* Conditionally allocate heap memory for VEC and its internal vector.  */
1416
1417 template<typename T>
1418 inline void
1419 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1420 {
1421   if (!vec)
1422     vec_alloc (vec, nelems PASS_MEM_STAT);
1423 }
1424
1425
1426 /* Free the heap memory allocated by vector V and set it to NULL.  */
1427
1428 template<typename T>
1429 inline void
1430 vec_free (vec<T> *&v)
1431 {
1432   if (v == NULL)
1433     return;
1434
1435   v->release ();
1436   delete v;
1437   v = NULL;
1438 }
1439
1440
1441 /* Return iteration condition and update PTR to point to the IX'th
1442    element of this vector.  Use this to iterate over the elements of a
1443    vector as follows,
1444
1445      for (ix = 0; v.iterate (ix, &ptr); ix++)
1446        continue;  */
1447
1448 template<typename T>
1449 inline bool
1450 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1451 {
1452   if (m_vec)
1453     return m_vec->iterate (ix, ptr);
1454   else
1455     {
1456       *ptr = 0;
1457       return false;
1458     }
1459 }
1460
1461
1462 /* Return iteration condition and update *PTR to point to the
1463    IX'th element of this vector.  Use this to iterate over the
1464    elements of a vector as follows,
1465
1466      for (ix = 0; v->iterate (ix, &ptr); ix++)
1467        continue;
1468
1469    This variant is for vectors of objects.  */
1470
1471 template<typename T>
1472 inline bool
1473 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1474 {
1475   if (m_vec)
1476     return m_vec->iterate (ix, ptr);
1477   else
1478     {
1479       *ptr = 0;
1480       return false;
1481     }
1482 }
1483
1484
1485 /* Convenience macro for forward iteration.  */
1486 #define FOR_EACH_VEC_ELT(V, I, P)                       \
1487   for (I = 0; (V).iterate ((I), &(P)); ++(I))
1488
1489 #define FOR_EACH_VEC_SAFE_ELT(V, I, P)                  \
1490   for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1491
1492 /* Likewise, but start from FROM rather than 0.  */
1493 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)            \
1494   for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1495
1496 /* Convenience macro for reverse iteration.  */
1497 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P)               \
1498   for (I = (V).length () - 1;                           \
1499        (V).iterate ((I), &(P));                         \
1500        (I)--)
1501
1502 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)          \
1503   for (I = vec_safe_length (V) - 1;                     \
1504        vec_safe_iterate ((V), (I), &(P));       \
1505        (I)--)
1506
1507
1508 /* Return a copy of this vector.  */
1509
1510 template<typename T>
1511 inline vec<T, va_heap, vl_ptr>
1512 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1513 {
1514   vec<T, va_heap, vl_ptr> new_vec = vNULL;
1515   if (length ())
1516     new_vec.m_vec = m_vec->copy ();
1517   return new_vec;
1518 }
1519
1520
1521 /* Ensure that the vector has at least RESERVE slots available (if
1522    EXACT is false), or exactly RESERVE slots available (if EXACT is
1523    true).
1524
1525    This may create additional headroom if EXACT is false.
1526
1527    Note that this can cause the embedded vector to be reallocated.
1528    Returns true iff reallocation actually occurred.  */
1529
1530 template<typename T>
1531 inline bool
1532 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1533 {
1534   if (space (nelems))
1535     return false;
1536
1537   /* For now play a game with va_heap::reserve to hide our auto storage if any,
1538      this is necessary because it doesn't have enough information to know the
1539      embedded vector is in auto storage, and so should not be freed.  */
1540   vec<T, va_heap, vl_embed> *oldvec = m_vec;
1541   unsigned int oldsize = 0;
1542   bool handle_auto_vec = m_vec && using_auto_storage ();
1543   if (handle_auto_vec)
1544     {
1545       m_vec = NULL;
1546       oldsize = oldvec->length ();
1547       nelems += oldsize;
1548     }
1549
1550   va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1551   if (handle_auto_vec)
1552     {
1553       vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1554       m_vec->m_vecpfx.m_num = oldsize;
1555     }
1556
1557   return true;
1558 }
1559
1560
1561 /* Ensure that this vector has exactly NELEMS slots available.  This
1562    will not create additional headroom.  Note this can cause the
1563    embedded vector to be reallocated.  Returns true iff reallocation
1564    actually occurred.  */
1565
1566 template<typename T>
1567 inline bool
1568 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1569 {
1570   return reserve (nelems, true PASS_MEM_STAT);
1571 }
1572
1573
1574 /* Create the internal vector and reserve NELEMS for it.  This is
1575    exactly like vec::reserve, but the internal vector is
1576    unconditionally allocated from scratch.  The old one, if it
1577    existed, is lost.  */
1578
1579 template<typename T>
1580 inline void
1581 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1582 {
1583   m_vec = NULL;
1584   if (nelems > 0)
1585     reserve_exact (nelems PASS_MEM_STAT);
1586 }
1587
1588
1589 /* Free the memory occupied by the embedded vector.  */
1590
1591 template<typename T>
1592 inline void
1593 vec<T, va_heap, vl_ptr>::release (void)
1594 {
1595   if (!m_vec)
1596     return;
1597
1598   if (using_auto_storage ())
1599     {
1600       m_vec->m_vecpfx.m_num = 0;
1601       return;
1602     }
1603
1604   va_heap::release (m_vec);
1605 }
1606
1607 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1608    SRC and this vector must be allocated with the same memory
1609    allocation mechanism. This vector is assumed to have sufficient
1610    headroom available.  */
1611
1612 template<typename T>
1613 inline void
1614 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1615 {
1616   if (src.m_vec)
1617     m_vec->splice (*(src.m_vec));
1618 }
1619
1620
1621 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1622    SRC and this vector must be allocated with the same mechanism.
1623    If there is not enough headroom in this vector, it will be reallocated
1624    as needed.  */
1625
1626 template<typename T>
1627 inline void
1628 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1629                                       MEM_STAT_DECL)
1630 {
1631   if (src.length ())
1632     {
1633       reserve_exact (src.length ());
1634       splice (src);
1635     }
1636 }
1637
1638
1639 /* Push OBJ (a new element) onto the end of the vector.  There must be
1640    sufficient space in the vector.  Return a pointer to the slot
1641    where OBJ was inserted.  */
1642
1643 template<typename T>
1644 inline T *
1645 vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1646 {
1647   return m_vec->quick_push (obj);
1648 }
1649
1650
1651 /* Push a new element OBJ onto the end of this vector.  Reallocates
1652    the embedded vector, if needed.  Return a pointer to the slot where
1653    OBJ was inserted.  */
1654
1655 template<typename T>
1656 inline T *
1657 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1658 {
1659   reserve (1, false PASS_MEM_STAT);
1660   return quick_push (obj);
1661 }
1662
1663
1664 /* Pop and return the last element off the end of the vector.  */
1665
1666 template<typename T>
1667 inline T &
1668 vec<T, va_heap, vl_ptr>::pop (void)
1669 {
1670   return m_vec->pop ();
1671 }
1672
1673
1674 /* Set the length of the vector to LEN.  The new length must be less
1675    than or equal to the current length.  This is an O(1) operation.  */
1676
1677 template<typename T>
1678 inline void
1679 vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1680 {
1681   if (m_vec)
1682     m_vec->truncate (size);
1683   else
1684     gcc_checking_assert (size == 0);
1685 }
1686
1687
1688 /* Grow the vector to a specific length.  LEN must be as long or
1689    longer than the current length.  The new elements are
1690    uninitialized.  Reallocate the internal vector, if needed.  */
1691
1692 template<typename T>
1693 inline void
1694 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
1695 {
1696   unsigned oldlen = length ();
1697   gcc_checking_assert (oldlen <= len);
1698   reserve_exact (len - oldlen PASS_MEM_STAT);
1699   if (m_vec)
1700     m_vec->quick_grow (len);
1701   else
1702     gcc_checking_assert (len == 0);
1703 }
1704
1705
1706 /* Grow the embedded vector to a specific length.  LEN must be as
1707    long or longer than the current length.  The new elements are
1708    initialized to zero.  Reallocate the internal vector, if needed.  */
1709
1710 template<typename T>
1711 inline void
1712 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
1713 {
1714   unsigned oldlen = length ();
1715   size_t growby = len - oldlen;
1716   safe_grow (len PASS_MEM_STAT);
1717   if (growby != 0)
1718     vec_default_construct (address () + oldlen, growby);
1719 }
1720
1721
1722 /* Same as vec::safe_grow but without reallocation of the internal vector.
1723    If the vector cannot be extended, a runtime assertion will be triggered.  */
1724
1725 template<typename T>
1726 inline void
1727 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
1728 {
1729   gcc_checking_assert (m_vec);
1730   m_vec->quick_grow (len);
1731 }
1732
1733
1734 /* Same as vec::quick_grow_cleared but without reallocation of the
1735    internal vector. If the vector cannot be extended, a runtime
1736    assertion will be triggered.  */
1737
1738 template<typename T>
1739 inline void
1740 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
1741 {
1742   gcc_checking_assert (m_vec);
1743   m_vec->quick_grow_cleared (len);
1744 }
1745
1746
1747 /* Insert an element, OBJ, at the IXth position of this vector.  There
1748    must be sufficient space.  */
1749
1750 template<typename T>
1751 inline void
1752 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
1753 {
1754   m_vec->quick_insert (ix, obj);
1755 }
1756
1757
1758 /* Insert an element, OBJ, at the IXth position of the vector.
1759    Reallocate the embedded vector, if necessary.  */
1760
1761 template<typename T>
1762 inline void
1763 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
1764 {
1765   reserve (1, false PASS_MEM_STAT);
1766   quick_insert (ix, obj);
1767 }
1768
1769
1770 /* Remove an element from the IXth position of this vector.  Ordering of
1771    remaining elements is preserved.  This is an O(N) operation due to
1772    a memmove.  */
1773
1774 template<typename T>
1775 inline void
1776 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
1777 {
1778   m_vec->ordered_remove (ix);
1779 }
1780
1781
1782 /* Remove an element from the IXth position of this vector.  Ordering
1783    of remaining elements is destroyed.  This is an O(1) operation.  */
1784
1785 template<typename T>
1786 inline void
1787 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
1788 {
1789   m_vec->unordered_remove (ix);
1790 }
1791
1792
1793 /* Remove LEN elements starting at the IXth.  Ordering is retained.
1794    This is an O(N) operation due to memmove.  */
1795
1796 template<typename T>
1797 inline void
1798 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
1799 {
1800   m_vec->block_remove (ix, len);
1801 }
1802
1803
1804 /* Sort the contents of this vector with qsort.  CMP is the comparison
1805    function to pass to qsort.  */
1806
1807 template<typename T>
1808 inline void
1809 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
1810 {
1811   if (m_vec)
1812     m_vec->qsort (cmp);
1813 }
1814
1815
1816 /* Search the contents of the sorted vector with a binary search.
1817    CMP is the comparison function to pass to bsearch.  */
1818
1819 template<typename T>
1820 inline T *
1821 vec<T, va_heap, vl_ptr>::bsearch (const void *key,
1822                                   int (*cmp) (const void *, const void *))
1823 {
1824   if (m_vec)
1825     return m_vec->bsearch (key, cmp);
1826   return NULL;
1827 }
1828
1829
1830 /* Find and return the first position in which OBJ could be inserted
1831    without changing the ordering of this vector.  LESSTHAN is a
1832    function that returns true if the first argument is strictly less
1833    than the second.  */
1834
1835 template<typename T>
1836 inline unsigned
1837 vec<T, va_heap, vl_ptr>::lower_bound (T obj,
1838                                       bool (*lessthan)(const T &, const T &))
1839     const
1840 {
1841   return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
1842 }
1843
1844 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
1845    size of the vector and so should be used with care.  */
1846
1847 template<typename T>
1848 inline bool
1849 vec<T, va_heap, vl_ptr>::contains (const T &search) const
1850 {
1851   return m_vec ? m_vec->contains (search) : false;
1852 }
1853
1854 template<typename T>
1855 inline bool
1856 vec<T, va_heap, vl_ptr>::using_auto_storage () const
1857 {
1858   return m_vec->m_vecpfx.m_using_auto_storage;
1859 }
1860
1861 /* Release VEC and call release of all element vectors.  */
1862
1863 template<typename T>
1864 inline void
1865 release_vec_vec (vec<vec<T> > &vec)
1866 {
1867   for (unsigned i = 0; i < vec.length (); i++)
1868     vec[i].release ();
1869
1870   vec.release ();
1871 }
1872
1873 #if (GCC_VERSION >= 3000)
1874 # pragma GCC poison m_vec m_vecpfx m_vecdata
1875 #endif
1876
1877 #endif // GCC_VEC_H