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 #ifndef BROKEN_VALUE_INITIALIZATION
 494   for ( ; n; ++dst, --n)
 495     ::new (static_cast<void*>(dst)) T ();
 496 #else
 497   memset (dst, '\0', sizeof (T) * n);
 498 #endif
 499 }
 500
 501 /* Copy-construct N elements in DST from *SRC.  */
 502
 503 template <typename T>
 504 inline void
 505 vec_copy_construct (T *dst, const T *src, unsigned n)
 506 {
 507   for ( ; n; ++dst, ++src, --n)
 508     ::new (static_cast<void*>(dst)) T (*src);
 509 }
 510
 511 /* Type to provide NULL values for vec<T, A, L>.  This is used to
 512    provide nil initializers for vec instances.  Since vec must be
 513    a POD, we cannot have proper ctor/dtor for it.  To initialize
 514    a vec instance, you can assign it the value vNULL.  This isn't
 515    needed for file-scope and function-local static vectors, which
 516    are zero-initialized by default.  */
 517 struct vnull
 518 {
 519   template <typename T, typename A, typename L>
 520   CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); }
 521 };
 522 extern vnull vNULL;
 523
 524
 525 /* Embeddable vector.  These vectors are suitable to be embedded
 526    in other data structures so that they can be pre-allocated in a
 527    contiguous memory block.
 528
 529    Embeddable vectors are implemented using the trailing array idiom,
 530    thus they are not resizeable without changing the address of the
 531    vector object itself.  This means you cannot have variables or
 532    fields of embeddable vector type -- always use a pointer to a
 533    vector.  The one exception is the final field of a structure, which
 534    could be a vector type.
 535
 536    You will have to use the embedded_size & embedded_init calls to
 537    create such objects, and they will not be resizeable (so the 'safe'
 538    allocation variants are not available).
 539
 540    Properties:
 541
 542         - The whole vector and control data are allocated in a single
 543           contiguous block.  It uses the trailing-vector idiom, so
 544           allocation must reserve enough space for all the elements
 545           in the vector plus its control data.
 546         - The vector cannot be re-allocated.
 547         - The vector cannot grow nor shrink.
 548         - No indirections needed for access/manipulation.
 549         - It requires 2 words of storage (prior to vector allocation).  */
 550
 551 template<typename T, typename A>
 552 struct GTY((user)) vec<T, A, vl_embed>
 553 {
 554 public:
 555   unsigned allocated (void) const { return m_vecpfx.m_alloc; }
 556   unsigned length (void) const { return m_vecpfx.m_num; }
 557   bool is_empty (void) const { return m_vecpfx.m_num == 0; }
 558   T *address (void) { return m_vecdata; }
 559   const T *address (void) const { return m_vecdata; }
 560   T *begin () { return address (); }
 561   const T *begin () const { return address (); }
 562   T *end () { return address () + length (); }
 563   const T *end () const { return address () + length (); }
 564   const T &operator[] (unsigned) const;
 565   T &operator[] (unsigned);
 566   T &last (void);
 567   bool space (unsigned) const;
 568   bool iterate (unsigned, T *) const;
 569   bool iterate (unsigned, T **) const;
 570   vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
 571   void splice (const vec &);
 572   void splice (const vec *src);
 573   T *quick_push (const T &);
 574   T &pop (void);
 575   void truncate (unsigned);
 576   void quick_insert (unsigned, const T &);
 577   void ordered_remove (unsigned);
 578   void unordered_remove (unsigned);
 579   void block_remove (unsigned, unsigned);
 580   void qsort (int (*) (const void *, const void *));
 581   T *bsearch (const void *key, int (*compar)(const void *, const void *));
 582   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
 583   bool contains (const T &search) const;
 584   static size_t embedded_size (unsigned);
 585   void embedded_init (unsigned, unsigned = 0, unsigned = 0);
 586   void quick_grow (unsigned len);
 587   void quick_grow_cleared (unsigned len);
 588
 589   /* vec class can access our internal data and functions.  */
 590   template <typename, typename, typename> friend struct vec;
 591
 592   /* The allocator types also need access to our internals.  */
 593   friend struct va_gc;
 594   friend struct va_gc_atomic;
 595   friend struct va_heap;
 596
 597   /* FIXME - These fields should be private, but we need to cater to
 598              compilers that have stricter notions of PODness for types.  */
 599   vec_prefix m_vecpfx;
 600   T m_vecdata[1];
 601 };
 602
 603
 604 /* Convenience wrapper functions to use when dealing with pointers to
 605    embedded vectors.  Some functionality for these vectors must be
 606    provided via free functions for these reasons:
 607
 608         1- The pointer may be NULL (e.g., before initial allocation).
 609
 610         2- When the vector needs to grow, it must be reallocated, so
 611            the pointer will change its value.
 612
 613    Because of limitations with the current GC machinery, all vectors
 614    in GC memory *must* be pointers.  */
 615
 616
 617 /* If V contains no room for NELEMS elements, return false. Otherwise,
 618    return true.  */
 619 template<typename T, typename A>
 620 inline bool
 621 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
 622 {
 623   return v ? v->space (nelems) : nelems == 0;
 624 }
 625
 626
 627 /* If V is NULL, return 0.  Otherwise, return V->length().  */
 628 template<typename T, typename A>
 629 inline unsigned
 630 vec_safe_length (const vec<T, A, vl_embed> *v)
 631 {
 632   return v ? v->length () : 0;
 633 }
 634
 635
 636 /* If V is NULL, return NULL.  Otherwise, return V->address().  */
 637 template<typename T, typename A>
 638 inline T *
 639 vec_safe_address (vec<T, A, vl_embed> *v)
 640 {
 641   return v ? v->address () : NULL;
 642 }
 643
 644
 645 /* If V is NULL, return true.  Otherwise, return V->is_empty().  */
 646 template<typename T, typename A>
 647 inline bool
 648 vec_safe_is_empty (vec<T, A, vl_embed> *v)
 649 {
 650   return v ? v->is_empty () : true;
 651 }
 652
 653 /* If V does not have space for NELEMS elements, call
 654    V->reserve(NELEMS, EXACT).  */
 655 template<typename T, typename A>
 656 inline bool
 657 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
 658                   CXX_MEM_STAT_INFO)
 659 {
 660   bool extend = nelems ? !vec_safe_space (v, nelems) : false;
 661   if (extend)
 662     A::reserve (v, nelems, exact PASS_MEM_STAT);
 663   return extend;
 664 }
 665
 666 template<typename T, typename A>
 667 inline bool
 668 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
 669                         CXX_MEM_STAT_INFO)
 670 {
 671   return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
 672 }
 673
 674
 675 /* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
 676    is 0, V is initialized to NULL.  */
 677
 678 template<typename T, typename A>
 679 inline void
 680 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
 681 {
 682   v = NULL;
 683   vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
 684 }
 685
 686
 687 /* Free the GC memory allocated by vector V and set it to NULL.  */
 688
 689 template<typename T, typename A>
 690 inline void
 691 vec_free (vec<T, A, vl_embed> *&v)
 692 {
 693   A::release (v);
 694 }
 695
 696
 697 /* Grow V to length LEN.  Allocate it, if necessary.  */
 698 template<typename T, typename A>
 699 inline void
 700 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
 701 {
 702   unsigned oldlen = vec_safe_length (v);
 703   gcc_checking_assert (len >= oldlen);
 704   vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
 705   v->quick_grow (len);
 706 }
 707
 708
 709 /* If V is NULL, allocate it.  Call V->safe_grow_cleared(LEN).  */
 710 template<typename T, typename A>
 711 inline void
 712 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
 713 {
 714   unsigned oldlen = vec_safe_length (v);
 715   vec_safe_grow (v, len PASS_MEM_STAT);
 716   vec_default_construct (v->address () + oldlen, len - oldlen);
 717 }
 718
 719
 720 /* If V is NULL return false, otherwise return V->iterate(IX, PTR).  */
 721 template<typename T, typename A>
 722 inline bool
 723 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
 724 {
 725   if (v)
 726     return v->iterate (ix, ptr);
 727   else
 728     {
 729       *ptr = 0;
 730       return false;
 731     }
 732 }
 733
 734 template<typename T, typename A>
 735 inline bool
 736 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
 737 {
 738   if (v)
 739     return v->iterate (ix, ptr);
 740   else
 741     {
 742       *ptr = 0;
 743       return false;
 744     }
 745 }
 746
 747
 748 /* If V has no room for one more element, reallocate it.  Then call
 749    V->quick_push(OBJ).  */
 750 template<typename T, typename A>
 751 inline T *
 752 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
 753 {
 754   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 755   return v->quick_push (obj);
 756 }
 757
 758
 759 /* if V has no room for one more element, reallocate it.  Then call
 760    V->quick_insert(IX, OBJ).  */
 761 template<typename T, typename A>
 762 inline void
 763 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
 764                  CXX_MEM_STAT_INFO)
 765 {
 766   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 767   v->quick_insert (ix, obj);
 768 }
 769
 770
 771 /* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
 772 template<typename T, typename A>
 773 inline void
 774 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
 775 {
 776   if (v)
 777     v->truncate (size);
 778 }
 779
 780
 781 /* If SRC is not NULL, return a pointer to a copy of it.  */
 782 template<typename T, typename A>
 783 inline vec<T, A, vl_embed> *
 784 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
 785 {
 786   return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
 787 }
 788
 789 /* Copy the elements from SRC to the end of DST as if by memcpy.
 790    Reallocate DST, if necessary.  */
 791 template<typename T, typename A>
 792 inline void
 793 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
 794                  CXX_MEM_STAT_INFO)
 795 {
 796   unsigned src_len = vec_safe_length (src);
 797   if (src_len)
 798     {
 799       vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
 800                               PASS_MEM_STAT);
 801       dst->splice (*src);
 802     }
 803 }
 804
 805 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
 806    size of the vector and so should be used with care.  */
 807
 808 template<typename T, typename A>
 809 inline bool
 810 vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
 811 {
 812   return v ? v->contains (search) : false;
 813 }
 814
 815 /* Index into vector.  Return the IX'th element.  IX must be in the
 816    domain of the vector.  */
 817
 818 template<typename T, typename A>
 819 inline const T &
 820 vec<T, A, vl_embed>::operator[] (unsigned ix) const
 821 {
 822   gcc_checking_assert (ix < m_vecpfx.m_num);
 823   return m_vecdata[ix];
 824 }
 825
 826 template<typename T, typename A>
 827 inline T &
 828 vec<T, A, vl_embed>::operator[] (unsigned ix)
 829 {
 830   gcc_checking_assert (ix < m_vecpfx.m_num);
 831   return m_vecdata[ix];
 832 }
 833
 834
 835 /* Get the final element of the vector, which must not be empty.  */
 836
 837 template<typename T, typename A>
 838 inline T &
 839 vec<T, A, vl_embed>::last (void)
 840 {
 841   gcc_checking_assert (m_vecpfx.m_num > 0);
 842   return (*this)[m_vecpfx.m_num - 1];
 843 }
 844
 845
 846 /* If this vector has space for NELEMS additional entries, return
 847    true.  You usually only need to use this if you are doing your
 848    own vector reallocation, for instance on an embedded vector.  This
 849    returns true in exactly the same circumstances that vec::reserve
 850    will.  */
 851
 852 template<typename T, typename A>
 853 inline bool
 854 vec<T, A, vl_embed>::space (unsigned nelems) const
 855 {
 856   return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
 857 }
 858
 859
 860 /* Return iteration condition and update PTR to point to the IX'th
 861    element of this vector.  Use this to iterate over the elements of a
 862    vector as follows,
 863
 864      for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
 865        continue;  */
 866
 867 template<typename T, typename A>
 868 inline bool
 869 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
 870 {
 871   if (ix < m_vecpfx.m_num)
 872     {
 873       *ptr = m_vecdata[ix];
 874       return true;
 875     }
 876   else
 877     {
 878       *ptr = 0;
 879       return false;
 880     }
 881 }
 882
 883
 884 /* Return iteration condition and update *PTR to point to the
 885    IX'th element of this vector.  Use this to iterate over the
 886    elements of a vector as follows,
 887
 888      for (ix = 0; v->iterate (ix, &ptr); ix++)
 889        continue;
 890
 891    This variant is for vectors of objects.  */
 892
 893 template<typename T, typename A>
 894 inline bool
 895 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
 896 {
 897   if (ix < m_vecpfx.m_num)
 898     {
 899       *ptr = CONST_CAST (T *, &m_vecdata[ix]);
 900       return true;
 901     }
 902   else
 903     {
 904       *ptr = 0;
 905       return false;
 906     }
 907 }
 908
 909
 910 /* Return a pointer to a copy of this vector.  */
 911
 912 template<typename T, typename A>
 913 inline vec<T, A, vl_embed> *
 914 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
 915 {
 916   vec<T, A, vl_embed> *new_vec = NULL;
 917   unsigned len = length ();
 918   if (len)
 919     {
 920       vec_alloc (new_vec, len PASS_MEM_STAT);
 921       new_vec->embedded_init (len, len);
 922       vec_copy_construct (new_vec->address (), m_vecdata, len);
 923     }
 924   return new_vec;
 925 }
 926
 927
 928 /* Copy the elements from SRC to the end of this vector as if by memcpy.
 929    The vector must have sufficient headroom available.  */
 930
 931 template<typename T, typename A>
 932 inline void
 933 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
 934 {
 935   unsigned len = src.length ();
 936   if (len)
 937     {
 938       gcc_checking_assert (space (len));
 939       vec_copy_construct (end (), src.address (), len);
 940       m_vecpfx.m_num += len;
 941     }
 942 }
 943
 944 template<typename T, typename A>
 945 inline void
 946 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
 947 {
 948   if (src)
 949     splice (*src);
 950 }
 951
 952
 953 /* Push OBJ (a new element) onto the end of the vector.  There must be
 954    sufficient space in the vector.  Return a pointer to the slot
 955    where OBJ was inserted.  */
 956
 957 template<typename T, typename A>
 958 inline T *
 959 vec<T, A, vl_embed>::quick_push (const T &obj)
 960 {
 961   gcc_checking_assert (space (1));
 962   T *slot = &m_vecdata[m_vecpfx.m_num++];
 963   *slot = obj;
 964   return slot;
 965 }
 966
 967
 968 /* Pop and return the last element off the end of the vector.  */
 969
 970 template<typename T, typename A>
 971 inline T &
 972 vec<T, A, vl_embed>::pop (void)
 973 {
 974   gcc_checking_assert (length () > 0);
 975   return m_vecdata[--m_vecpfx.m_num];
 976 }
 977
 978
 979 /* Set the length of the vector to SIZE.  The new length must be less
 980    than or equal to the current length.  This is an O(1) operation.  */
 981
 982 template<typename T, typename A>
 983 inline void
 984 vec<T, A, vl_embed>::truncate (unsigned size)
 985 {
 986   gcc_checking_assert (length () >= size);
 987   m_vecpfx.m_num = size;
 988 }
 989
 990
 991 /* Insert an element, OBJ, at the IXth position of this vector.  There
 992    must be sufficient space.  */
 993
 994 template<typename T, typename A>
 995 inline void
 996 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
 997 {
 998   gcc_checking_assert (length () < allocated ());
 999   gcc_checking_assert (ix <= length ());
1000   T *slot = &m_vecdata[ix];
1001   memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1002   *slot = obj;
1003 }
1004
1005
1006 /* Remove an element from the IXth position of this vector.  Ordering of
1007    remaining elements is preserved.  This is an O(N) operation due to
1008    memmove.  */
1009
1010 template<typename T, typename A>
1011 inline void
1012 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1013 {
1014   gcc_checking_assert (ix < length ());
1015   T *slot = &m_vecdata[ix];
1016   memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1017 }
1018
1019
1020 /* Remove an element from the IXth position of this vector.  Ordering of
1021    remaining elements is destroyed.  This is an O(1) operation.  */
1022
1023 template<typename T, typename A>
1024 inline void
1025 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1026 {
1027   gcc_checking_assert (ix < length ());
1028   m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1029 }
1030
1031
1032 /* Remove LEN elements starting at the IXth.  Ordering is retained.
1033    This is an O(N) operation due to memmove.  */
1034
1035 template<typename T, typename A>
1036 inline void
1037 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1038 {
1039   gcc_checking_assert (ix + len <= length ());
1040   T *slot = &m_vecdata[ix];
1041   m_vecpfx.m_num -= len;
1042   memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1043 }
1044
1045
1046 /* Sort the contents of this vector with qsort.  CMP is the comparison
1047    function to pass to qsort.  */
1048
1049 template<typename T, typename A>
1050 inline void
1051 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1052 {
1053   if (length () > 1)
1054     ::qsort (address (), length (), sizeof (T), cmp);
1055 }
1056
1057
1058 /* Search the contents of the sorted vector with a binary search.
1059    CMP is the comparison function to pass to bsearch.  */
1060
1061 template<typename T, typename A>
1062 inline T *
1063 vec<T, A, vl_embed>::bsearch (const void *key,
1064                               int (*compar) (const void *, const void *))
1065 {
1066   const void *base = this->address ();
1067   size_t nmemb = this->length ();
1068   size_t size = sizeof (T);
1069   /* The following is a copy of glibc stdlib-bsearch.h.  */
1070   size_t l, u, idx;
1071   const void *p;
1072   int comparison;
1073
1074   l = 0;
1075   u = nmemb;
1076   while (l < u)
1077     {
1078       idx = (l + u) / 2;
1079       p = (const void *) (((const char *) base) + (idx * size));
1080       comparison = (*compar) (key, p);
1081       if (comparison < 0)
1082         u = idx;
1083       else if (comparison > 0)
1084         l = idx + 1;
1085       else
1086         return (T *)const_cast<void *>(p);
1087     }
1088
1089   return NULL;
1090 }
1091
1092 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
1093    size of the vector and so should be used with care.  */
1094
1095 template<typename T, typename A>
1096 inline bool
1097 vec<T, A, vl_embed>::contains (const T &search) const
1098 {
1099   unsigned int len = length ();
1100   for (unsigned int i = 0; i < len; i++)
1101     if ((*this)[i] == search)
1102       return true;
1103
1104   return false;
1105 }
1106
1107 /* Find and return the first position in which OBJ could be inserted
1108    without changing the ordering of this vector.  LESSTHAN is a
1109    function that returns true if the first argument is strictly less
1110    than the second.  */
1111
1112 template<typename T, typename A>
1113 unsigned
1114 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1115   const
1116 {
1117   unsigned int len = length ();
1118   unsigned int half, middle;
1119   unsigned int first = 0;
1120   while (len > 0)
1121     {
1122       half = len / 2;
1123       middle = first;
1124       middle += half;
1125       T middle_elem = (*this)[middle];
1126       if (lessthan (middle_elem, obj))
1127         {
1128           first = middle;
1129           ++first;
1130           len = len - half - 1;
1131         }
1132       else
1133         len = half;
1134     }
1135   return first;
1136 }
1137
1138
1139 /* Return the number of bytes needed to embed an instance of an
1140    embeddable vec inside another data structure.
1141
1142    Use these methods to determine the required size and initialization
1143    of a vector V of type T embedded within another structure (as the
1144    final member):
1145
1146    size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1147    void v->embedded_init (unsigned alloc, unsigned num);
1148
1149    These allow the caller to perform the memory allocation.  */
1150
1151 template<typename T, typename A>
1152 inline size_t
1153 vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1154 {
1155   typedef vec<T, A, vl_embed> vec_embedded;
1156   return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
1157 }
1158
1159
1160 /* Initialize the vector to contain room for ALLOC elements and
1161    NUM active elements.  */
1162
1163 template<typename T, typename A>
1164 inline void
1165 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1166 {
1167   m_vecpfx.m_alloc = alloc;
1168   m_vecpfx.m_using_auto_storage = aut;
1169   m_vecpfx.m_num = num;
1170 }
1171
1172
1173 /* Grow the vector to a specific length.  LEN must be as long or longer than
1174    the current length.  The new elements are uninitialized.  */
1175
1176 template<typename T, typename A>
1177 inline void
1178 vec<T, A, vl_embed>::quick_grow (unsigned len)
1179 {
1180   gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1181   m_vecpfx.m_num = len;
1182 }
1183
1184
1185 /* Grow the vector to a specific length.  LEN must be as long or longer than
1186    the current length.  The new elements are initialized to zero.  */
1187
1188 template<typename T, typename A>
1189 inline void
1190 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1191 {
1192   unsigned oldlen = length ();
1193   size_t growby = len - oldlen;
1194   quick_grow (len);
1195   if (growby != 0)
1196     vec_default_construct (address () + oldlen, growby);
1197 }
1198
1199 /* Garbage collection support for vec<T, A, vl_embed>.  */
1200
1201 template<typename T>
1202 void
1203 gt_ggc_mx (vec<T, va_gc> *v)
1204 {
1205   extern void gt_ggc_mx (T &);
1206   for (unsigned i = 0; i < v->length (); i++)
1207     gt_ggc_mx ((*v)[i]);
1208 }
1209
1210 template<typename T>
1211 void
1212 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1213 {
1214   /* Nothing to do.  Vectors of atomic types wrt GC do not need to
1215      be traversed.  */
1216 }
1217
1218
1219 /* PCH support for vec<T, A, vl_embed>.  */
1220
1221 template<typename T, typename A>
1222 void
1223 gt_pch_nx (vec<T, A, vl_embed> *v)
1224 {
1225   extern void gt_pch_nx (T &);
1226   for (unsigned i = 0; i < v->length (); i++)
1227     gt_pch_nx ((*v)[i]);
1228 }
1229
1230 template<typename T, typename A>
1231 void
1232 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1233 {
1234   for (unsigned i = 0; i < v->length (); i++)
1235     op (&((*v)[i]), cookie);
1236 }
1237
1238 template<typename T, typename A>
1239 void
1240 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1241 {
1242   extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1243   for (unsigned i = 0; i < v->length (); i++)
1244     gt_pch_nx (&((*v)[i]), op, cookie);
1245 }
1246
1247
1248 /* Space efficient vector.  These vectors can grow dynamically and are
1249    allocated together with their control data.  They are suited to be
1250    included in data structures.  Prior to initial allocation, they
1251    only take a single word of storage.
1252
1253    These vectors are implemented as a pointer to an embeddable vector.
1254    The semantics allow for this pointer to be NULL to represent empty
1255    vectors.  This way, empty vectors occupy minimal space in the
1256    structure containing them.
1257
1258    Properties:
1259
1260         - The whole vector and control data are allocated in a single
1261           contiguous block.
1262         - The whole vector may be re-allocated.
1263         - Vector data may grow and shrink.
1264         - Access and manipulation requires a pointer test and
1265           indirection.
1266         - It requires 1 word of storage (prior to vector allocation).
1267
1268
1269    Limitations:
1270
1271    These vectors must be PODs because they are stored in unions.
1272    (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1273    As long as we use C++03, we cannot have constructors nor
1274    destructors in classes that are stored in unions.  */
1275
1276 template<typename T>
1277 struct vec<T, va_heap, vl_ptr>
1278 {
1279 public:
1280   /* Memory allocation and deallocation for the embedded vector.
1281      Needed because we cannot have proper ctors/dtors defined.  */
1282   void create (unsigned nelems CXX_MEM_STAT_INFO);
1283   void release (void);
1284
1285   /* Vector operations.  */
1286   bool exists (void) const
1287   { return m_vec != NULL; }
1288
1289   bool is_empty (void) const
1290   { return m_vec ? m_vec->is_empty () : true; }
1291
1292   unsigned length (void) const
1293   { return m_vec ? m_vec->length () : 0; }
1294
1295   T *address (void)
1296   { return m_vec ? m_vec->m_vecdata : NULL; }
1297
1298   const T *address (void) const
1299   { return m_vec ? m_vec->m_vecdata : NULL; }
1300
1301   T *begin () { return address (); }
1302   const T *begin () const { return address (); }
1303   T *end () { return begin () + length (); }
1304   const T *end () const { return begin () + length (); }
1305   const T &operator[] (unsigned ix) const
1306   { return (*m_vec)[ix]; }
1307
1308   bool operator!=(const vec &other) const
1309   { return !(*this == other); }
1310
1311   bool operator==(const vec &other) const
1312   { return address () == other.address (); }
1313
1314   T &operator[] (unsigned ix)
1315   { return (*m_vec)[ix]; }
1316
1317   T &last (void)
1318   { return m_vec->last (); }
1319
1320   bool space (int nelems) const
1321   { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1322
1323   bool iterate (unsigned ix, T *p) const;
1324   bool iterate (unsigned ix, T **p) const;
1325   vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1326   bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1327   bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1328   void splice (const vec &);
1329   void safe_splice (const vec & CXX_MEM_STAT_INFO);
1330   T *quick_push (const T &);
1331   T *safe_push (const T &CXX_MEM_STAT_INFO);
1332   T &pop (void);
1333   void truncate (unsigned);
1334   void safe_grow (unsigned CXX_MEM_STAT_INFO);
1335   void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
1336   void quick_grow (unsigned);
1337   void quick_grow_cleared (unsigned);
1338   void quick_insert (unsigned, const T &);
1339   void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1340   void ordered_remove (unsigned);
1341   void unordered_remove (unsigned);
1342   void block_remove (unsigned, unsigned);
1343   void qsort (int (*) (const void *, const void *));
1344   T *bsearch (const void *key, int (*compar)(const void *, const void *));
1345   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1346   bool contains (const T &search) const;
1347
1348   bool using_auto_storage () const;
1349
1350   /* FIXME - This field should be private, but we need to cater to
1351              compilers that have stricter notions of PODness for types.  */
1352   vec<T, va_heap, vl_embed> *m_vec;
1353 };
1354
1355
1356 /* auto_vec is a subclass of vec that automatically manages creating and
1357    releasing the internal vector. If N is non zero then it has N elements of
1358    internal storage.  The default is no internal storage, and you probably only
1359    want to ask for internal storage for vectors on the stack because if the
1360    size of the vector is larger than the internal storage that space is wasted.
1361    */
1362 template<typename T, size_t N = 0>
1363 class auto_vec : public vec<T, va_heap>
1364 {
1365 public:
1366   auto_vec ()
1367   {
1368     m_auto.embedded_init (MAX (N, 2), 0, 1);
1369     this->m_vec = &m_auto;
1370   }
1371
1372   auto_vec (size_t s)
1373   {
1374     if (s > N)
1375       {
1376         this->create (s);
1377         return;
1378       }
1379
1380     m_auto.embedded_init (MAX (N, 2), 0, 1);
1381     this->m_vec = &m_auto;
1382   }
1383
1384   ~auto_vec ()
1385   {
1386     this->release ();
1387   }
1388
1389 private:
1390   vec<T, va_heap, vl_embed> m_auto;
1391   T m_data[MAX (N - 1, 1)];
1392 };
1393
1394 /* auto_vec is a sub class of vec whose storage is released when it is
1395   destroyed. */
1396 template<typename T>
1397 class auto_vec<T, 0> : public vec<T, va_heap>
1398 {
1399 public:
1400   auto_vec () { this->m_vec = NULL; }
1401   auto_vec (size_t n) { this->create (n); }
1402   ~auto_vec () { this->release (); }
1403 };
1404
1405
1406 /* Allocate heap memory for pointer V and create the internal vector
1407    with space for NELEMS elements.  If NELEMS is 0, the internal
1408    vector is initialized to empty.  */
1409
1410 template<typename T>
1411 inline void
1412 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1413 {
1414   v = new vec<T>;
1415   v->create (nelems PASS_MEM_STAT);
1416 }
1417
1418
1419 /* Conditionally allocate heap memory for VEC and its internal vector.  */
1420
1421 template<typename T>
1422 inline void
1423 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1424 {
1425   if (!vec)
1426     vec_alloc (vec, nelems PASS_MEM_STAT);
1427 }
1428
1429
1430 /* Free the heap memory allocated by vector V and set it to NULL.  */
1431
1432 template<typename T>
1433 inline void
1434 vec_free (vec<T> *&v)
1435 {
1436   if (v == NULL)
1437     return;
1438
1439   v->release ();
1440   delete v;
1441   v = NULL;
1442 }
1443
1444
1445 /* Return iteration condition and update PTR to point to the IX'th
1446    element of this vector.  Use this to iterate over the elements of a
1447    vector as follows,
1448
1449      for (ix = 0; v.iterate (ix, &ptr); ix++)
1450        continue;  */
1451
1452 template<typename T>
1453 inline bool
1454 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1455 {
1456   if (m_vec)
1457     return m_vec->iterate (ix, ptr);
1458   else
1459     {
1460       *ptr = 0;
1461       return false;
1462     }
1463 }
1464
1465
1466 /* Return iteration condition and update *PTR to point to the
1467    IX'th element of this vector.  Use this to iterate over the
1468    elements of a vector as follows,
1469
1470      for (ix = 0; v->iterate (ix, &ptr); ix++)
1471        continue;
1472
1473    This variant is for vectors of objects.  */
1474
1475 template<typename T>
1476 inline bool
1477 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1478 {
1479   if (m_vec)
1480     return m_vec->iterate (ix, ptr);
1481   else
1482     {
1483       *ptr = 0;
1484       return false;
1485     }
1486 }
1487
1488
1489 /* Convenience macro for forward iteration.  */
1490 #define FOR_EACH_VEC_ELT(V, I, P)                       \
1491   for (I = 0; (V).iterate ((I), &(P)); ++(I))
1492
1493 #define FOR_EACH_VEC_SAFE_ELT(V, I, P)                  \
1494   for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1495
1496 /* Likewise, but start from FROM rather than 0.  */
1497 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)            \
1498   for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1499
1500 /* Convenience macro for reverse iteration.  */
1501 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P)               \
1502   for (I = (V).length () - 1;                           \
1503        (V).iterate ((I), &(P));                         \
1504        (I)--)
1505
1506 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)          \
1507   for (I = vec_safe_length (V) - 1;                     \
1508        vec_safe_iterate ((V), (I), &(P));       \
1509        (I)--)
1510
1511
1512 /* Return a copy of this vector.  */
1513
1514 template<typename T>
1515 inline vec<T, va_heap, vl_ptr>
1516 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1517 {
1518   vec<T, va_heap, vl_ptr> new_vec = vNULL;
1519   if (length ())
1520     new_vec.m_vec = m_vec->copy ();
1521   return new_vec;
1522 }
1523
1524
1525 /* Ensure that the vector has at least RESERVE slots available (if
1526    EXACT is false), or exactly RESERVE slots available (if EXACT is
1527    true).
1528
1529    This may create additional headroom if EXACT is false.
1530
1531    Note that this can cause the embedded vector to be reallocated.
1532    Returns true iff reallocation actually occurred.  */
1533
1534 template<typename T>
1535 inline bool
1536 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1537 {
1538   if (space (nelems))
1539     return false;
1540
1541   /* For now play a game with va_heap::reserve to hide our auto storage if any,
1542      this is necessary because it doesn't have enough information to know the
1543      embedded vector is in auto storage, and so should not be freed.  */
1544   vec<T, va_heap, vl_embed> *oldvec = m_vec;
1545   unsigned int oldsize = 0;
1546   bool handle_auto_vec = m_vec && using_auto_storage ();
1547   if (handle_auto_vec)
1548     {
1549       m_vec = NULL;
1550       oldsize = oldvec->length ();
1551       nelems += oldsize;
1552     }
1553
1554   va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1555   if (handle_auto_vec)
1556     {
1557       vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1558       m_vec->m_vecpfx.m_num = oldsize;
1559     }
1560
1561   return true;
1562 }
1563
1564
1565 /* Ensure that this vector has exactly NELEMS slots available.  This
1566    will not create additional headroom.  Note this can cause the
1567    embedded vector to be reallocated.  Returns true iff reallocation
1568    actually occurred.  */
1569
1570 template<typename T>
1571 inline bool
1572 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1573 {
1574   return reserve (nelems, true PASS_MEM_STAT);
1575 }
1576
1577
1578 /* Create the internal vector and reserve NELEMS for it.  This is
1579    exactly like vec::reserve, but the internal vector is
1580    unconditionally allocated from scratch.  The old one, if it
1581    existed, is lost.  */
1582
1583 template<typename T>
1584 inline void
1585 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1586 {
1587   m_vec = NULL;
1588   if (nelems > 0)
1589     reserve_exact (nelems PASS_MEM_STAT);
1590 }
1591
1592
1593 /* Free the memory occupied by the embedded vector.  */
1594
1595 template<typename T>
1596 inline void
1597 vec<T, va_heap, vl_ptr>::release (void)
1598 {
1599   if (!m_vec)
1600     return;
1601
1602   if (using_auto_storage ())
1603     {
1604       m_vec->m_vecpfx.m_num = 0;
1605       return;
1606     }
1607
1608   va_heap::release (m_vec);
1609 }
1610
1611 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1612    SRC and this vector must be allocated with the same memory
1613    allocation mechanism. This vector is assumed to have sufficient
1614    headroom available.  */
1615
1616 template<typename T>
1617 inline void
1618 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1619 {
1620   if (src.m_vec)
1621     m_vec->splice (*(src.m_vec));
1622 }
1623
1624
1625 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1626    SRC and this vector must be allocated with the same mechanism.
1627    If there is not enough headroom in this vector, it will be reallocated
1628    as needed.  */
1629
1630 template<typename T>
1631 inline void
1632 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1633                                       MEM_STAT_DECL)
1634 {
1635   if (src.length ())
1636     {
1637       reserve_exact (src.length ());
1638       splice (src);
1639     }
1640 }
1641
1642
1643 /* Push OBJ (a new element) onto the end of the vector.  There must be
1644    sufficient space in the vector.  Return a pointer to the slot
1645    where OBJ was inserted.  */
1646
1647 template<typename T>
1648 inline T *
1649 vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1650 {
1651   return m_vec->quick_push (obj);
1652 }
1653
1654
1655 /* Push a new element OBJ onto the end of this vector.  Reallocates
1656    the embedded vector, if needed.  Return a pointer to the slot where
1657    OBJ was inserted.  */
1658
1659 template<typename T>
1660 inline T *
1661 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1662 {
1663   reserve (1, false PASS_MEM_STAT);
1664   return quick_push (obj);
1665 }
1666
1667
1668 /* Pop and return the last element off the end of the vector.  */
1669
1670 template<typename T>
1671 inline T &
1672 vec<T, va_heap, vl_ptr>::pop (void)
1673 {
1674   return m_vec->pop ();
1675 }
1676
1677
1678 /* Set the length of the vector to LEN.  The new length must be less
1679    than or equal to the current length.  This is an O(1) operation.  */
1680
1681 template<typename T>
1682 inline void
1683 vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1684 {
1685   if (m_vec)
1686     m_vec->truncate (size);
1687   else
1688     gcc_checking_assert (size == 0);
1689 }
1690
1691
1692 /* Grow the vector to a specific length.  LEN must be as long or
1693    longer than the current length.  The new elements are
1694    uninitialized.  Reallocate the internal vector, if needed.  */
1695
1696 template<typename T>
1697 inline void
1698 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
1699 {
1700   unsigned oldlen = length ();
1701   gcc_checking_assert (oldlen <= len);
1702   reserve_exact (len - oldlen PASS_MEM_STAT);
1703   if (m_vec)
1704     m_vec->quick_grow (len);
1705   else
1706     gcc_checking_assert (len == 0);
1707 }
1708
1709
1710 /* Grow the embedded vector to a specific length.  LEN must be as
1711    long or longer than the current length.  The new elements are
1712    initialized to zero.  Reallocate the internal vector, if needed.  */
1713
1714 template<typename T>
1715 inline void
1716 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
1717 {
1718   unsigned oldlen = length ();
1719   size_t growby = len - oldlen;
1720   safe_grow (len PASS_MEM_STAT);
1721   if (growby != 0)
1722     vec_default_construct (address () + oldlen, growby);
1723 }
1724
1725
1726 /* Same as vec::safe_grow but without reallocation of the internal vector.
1727    If the vector cannot be extended, a runtime assertion will be triggered.  */
1728
1729 template<typename T>
1730 inline void
1731 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
1732 {
1733   gcc_checking_assert (m_vec);
1734   m_vec->quick_grow (len);
1735 }
1736
1737
1738 /* Same as vec::quick_grow_cleared but without reallocation of the
1739    internal vector. If the vector cannot be extended, a runtime
1740    assertion will be triggered.  */
1741
1742 template<typename T>
1743 inline void
1744 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
1745 {
1746   gcc_checking_assert (m_vec);
1747   m_vec->quick_grow_cleared (len);
1748 }
1749
1750
1751 /* Insert an element, OBJ, at the IXth position of this vector.  There
1752    must be sufficient space.  */
1753
1754 template<typename T>
1755 inline void
1756 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
1757 {
1758   m_vec->quick_insert (ix, obj);
1759 }
1760
1761
1762 /* Insert an element, OBJ, at the IXth position of the vector.
1763    Reallocate the embedded vector, if necessary.  */
1764
1765 template<typename T>
1766 inline void
1767 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
1768 {
1769   reserve (1, false PASS_MEM_STAT);
1770   quick_insert (ix, obj);
1771 }
1772
1773
1774 /* Remove an element from the IXth position of this vector.  Ordering of
1775    remaining elements is preserved.  This is an O(N) operation due to
1776    a memmove.  */
1777
1778 template<typename T>
1779 inline void
1780 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
1781 {
1782   m_vec->ordered_remove (ix);
1783 }
1784
1785
1786 /* Remove an element from the IXth position of this vector.  Ordering
1787    of remaining elements is destroyed.  This is an O(1) operation.  */
1788
1789 template<typename T>
1790 inline void
1791 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
1792 {
1793   m_vec->unordered_remove (ix);
1794 }
1795
1796
1797 /* Remove LEN elements starting at the IXth.  Ordering is retained.
1798    This is an O(N) operation due to memmove.  */
1799
1800 template<typename T>
1801 inline void
1802 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
1803 {
1804   m_vec->block_remove (ix, len);
1805 }
1806
1807
1808 /* Sort the contents of this vector with qsort.  CMP is the comparison
1809    function to pass to qsort.  */
1810
1811 template<typename T>
1812 inline void
1813 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
1814 {
1815   if (m_vec)
1816     m_vec->qsort (cmp);
1817 }
1818
1819
1820 /* Search the contents of the sorted vector with a binary search.
1821    CMP is the comparison function to pass to bsearch.  */
1822
1823 template<typename T>
1824 inline T *
1825 vec<T, va_heap, vl_ptr>::bsearch (const void *key,
1826                                   int (*cmp) (const void *, const void *))
1827 {
1828   if (m_vec)
1829     return m_vec->bsearch (key, cmp);
1830   return NULL;
1831 }
1832
1833
1834 /* Find and return the first position in which OBJ could be inserted
1835    without changing the ordering of this vector.  LESSTHAN is a
1836    function that returns true if the first argument is strictly less
1837    than the second.  */
1838
1839 template<typename T>
1840 inline unsigned
1841 vec<T, va_heap, vl_ptr>::lower_bound (T obj,
1842                                       bool (*lessthan)(const T &, const T &))
1843     const
1844 {
1845   return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
1846 }
1847
1848 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
1849    size of the vector and so should be used with care.  */
1850
1851 template<typename T>
1852 inline bool
1853 vec<T, va_heap, vl_ptr>::contains (const T &search) const
1854 {
1855   return m_vec ? m_vec->contains (search) : false;
1856 }
1857
1858 template<typename T>
1859 inline bool
1860 vec<T, va_heap, vl_ptr>::using_auto_storage () const
1861 {
1862   return m_vec->m_vecpfx.m_using_auto_storage;
1863 }
1864
1865 /* Release VEC and call release of all element vectors.  */
1866
1867 template<typename T>
1868 inline void
1869 release_vec_vec (vec<vec<T> > &vec)
1870 {
1871   for (unsigned i = 0; i < vec.length (); i++)
1872     vec[i].release ();
1873
1874   vec.release ();
1875 }
1876
1877 #if (GCC_VERSION >= 3000)
1878 # pragma GCC poison m_vec m_vecpfx m_vecdata
1879 #endif
1880
1881 #endif // GCC_VEC_H