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