gcc/vec.h

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004-2022 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.cc.  */
 197   void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
 198   void release_overhead (void *, size_t, 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   size_t elt_size = sizeof (T);
 280   unsigned alloc
 281     = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
 282   gcc_checking_assert (alloc);
 283
 284   if (GATHER_STATISTICS && v)
 285     v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
 286                                   v->allocated (), false);
 287
 288   size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
 289   unsigned nelem = v ? v->length () : 0;
 290   v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
 291   v->embedded_init (alloc, nelem);
 292
 293   if (GATHER_STATISTICS)
 294     v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
 295 }
 296
 297
 298 #if GCC_VERSION >= 4007
 299 #pragma GCC diagnostic push
 300 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
 301 #endif
 302
 303 /* Free the heap space allocated for vector V.  */
 304
 305 template<typename T>
 306 void
 307 va_heap::release (vec<T, va_heap, vl_embed> *&v)
 308 {
 309   size_t elt_size = sizeof (T);
 310   if (v == NULL)
 311     return;
 312
 313   if (GATHER_STATISTICS)
 314     v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
 315                                   v->allocated (), true);
 316   ::free (v);
 317   v = NULL;
 318 }
 319
 320 #if GCC_VERSION >= 4007
 321 #pragma GCC diagnostic pop
 322 #endif
 323
 324 /* Allocator type for GC vectors.  Notice that we need the structure
 325    declaration even if GC is not enabled.  */
 326
 327 struct va_gc
 328 {
 329   /* Use vl_embed as the default layout for GC vectors.  Due to GTY
 330      limitations, GC vectors must always be pointers, so it is more
 331      efficient to use a pointer to the vl_embed layout, rather than
 332      using a pointer to a pointer as would be the case with vl_ptr.  */
 333   typedef vl_embed default_layout;
 334
 335   template<typename T, typename A>
 336   static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
 337                        CXX_MEM_STAT_INFO);
 338
 339   template<typename T, typename A>
 340   static void release (vec<T, A, vl_embed> *&v);
 341 };
 342
 343
 344 /* Free GC memory used by V and reset V to NULL.  */
 345
 346 template<typename T, typename A>
 347 inline void
 348 va_gc::release (vec<T, A, vl_embed> *&v)
 349 {
 350   if (v)
 351     ::ggc_free (v);
 352   v = NULL;
 353 }
 354
 355
 356 /* Allocator for GC memory.  Ensure there are at least RESERVE free
 357    slots in V.  If EXACT is true, grow exactly, else grow
 358    exponentially.  As a special case, if the vector had not been
 359    allocated and RESERVE is 0, no vector will be created.  */
 360
 361 template<typename T, typename A>
 362 void
 363 va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
 364                 MEM_STAT_DECL)
 365 {
 366   unsigned alloc
 367     = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
 368   if (!alloc)
 369     {
 370       ::ggc_free (v);
 371       v = NULL;
 372       return;
 373     }
 374
 375   /* Calculate the amount of space we want.  */
 376   size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
 377
 378   /* Ask the allocator how much space it will really give us.  */
 379   size = ::ggc_round_alloc_size (size);
 380
 381   /* Adjust the number of slots accordingly.  */
 382   size_t vec_offset = sizeof (vec_prefix);
 383   size_t elt_size = sizeof (T);
 384   alloc = (size - vec_offset) / elt_size;
 385
 386   /* And finally, recalculate the amount of space we ask for.  */
 387   size = vec_offset + alloc * elt_size;
 388
 389   unsigned nelem = v ? v->length () : 0;
 390   v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
 391                                                                PASS_MEM_STAT));
 392   v->embedded_init (alloc, nelem);
 393 }
 394
 395
 396 /* Allocator type for GC vectors.  This is for vectors of types
 397    atomics w.r.t. collection, so allocation and deallocation is
 398    completely inherited from va_gc.  */
 399 struct va_gc_atomic : va_gc
 400 {
 401 };
 402
 403
 404 /* Generic vector template.  Default values for A and L indicate the
 405    most commonly used strategies.
 406
 407    FIXME - Ideally, they would all be vl_ptr to encourage using regular
 408            instances for vectors, but the existing GTY machinery is limited
 409            in that it can only deal with GC objects that are pointers
 410            themselves.
 411
 412            This means that vector operations that need to deal with
 413            potentially NULL pointers, must be provided as free
 414            functions (see the vec_safe_* functions above).  */
 415 template<typename T,
 416          typename A = va_heap,
 417          typename L = typename A::default_layout>
 418 struct GTY((user)) vec
 419 {
 420 };
 421
 422 /* Allow C++11 range-based 'for' to work directly on vec<T>*.  */
 423 template<typename T, typename A, typename L>
 424 T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
 425 template<typename T, typename A, typename L>
 426 T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
 427 template<typename T, typename A, typename L>
 428 const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
 429 template<typename T, typename A, typename L>
 430 const T* end (const vec<T,A,L> *v) { return v ? v->end () : nullptr; }
 431
 432 /* Generic vec<> debug helpers.
 433
 434    These need to be instantiated for each vec<TYPE> used throughout
 435    the compiler like this:
 436
 437     DEFINE_DEBUG_VEC (TYPE)
 438
 439    The reason we have a debug_helper() is because GDB can't
 440    disambiguate a plain call to debug(some_vec), and it must be called
 441    like debug<TYPE>(some_vec).  */
 442
 443 template<typename T>
 444 void
 445 debug_helper (vec<T> &ref)
 446 {
 447   unsigned i;
 448   for (i = 0; i < ref.length (); ++i)
 449     {
 450       fprintf (stderr, "[%d] = ", i);
 451       debug_slim (ref[i]);
 452       fputc ('\n', stderr);
 453     }
 454 }
 455
 456 /* We need a separate va_gc variant here because default template
 457    argument for functions cannot be used in c++-98.  Once this
 458    restriction is removed, those variant should be folded with the
 459    above debug_helper.  */
 460
 461 template<typename T>
 462 void
 463 debug_helper (vec<T, va_gc> &ref)
 464 {
 465   unsigned i;
 466   for (i = 0; i < ref.length (); ++i)
 467     {
 468       fprintf (stderr, "[%d] = ", i);
 469       debug_slim (ref[i]);
 470       fputc ('\n', stderr);
 471     }
 472 }
 473
 474 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
 475    functions for a type T.  */
 476
 477 #define DEFINE_DEBUG_VEC(T) \
 478   template void debug_helper (vec<T> &);                \
 479   template void debug_helper (vec<T, va_gc> &);         \
 480   /* Define the vec<T> debug functions.  */             \
 481   DEBUG_FUNCTION void                                   \
 482   debug (vec<T> &ref)                                   \
 483   {                                                     \
 484     debug_helper <T> (ref);                             \
 485   }                                                     \
 486   DEBUG_FUNCTION void                                   \
 487   debug (vec<T> *ptr)                                   \
 488   {                                                     \
 489     if (ptr)                                            \
 490       debug (*ptr);                                     \
 491     else                                                \
 492       fprintf (stderr, "<nil>\n");                      \
 493   }                                                     \
 494   /* Define the vec<T, va_gc> debug functions.  */      \
 495   DEBUG_FUNCTION void                                   \
 496   debug (vec<T, va_gc> &ref)                            \
 497   {                                                     \
 498     debug_helper <T> (ref);                             \
 499   }                                                     \
 500   DEBUG_FUNCTION void                                   \
 501   debug (vec<T, va_gc> *ptr)                            \
 502   {                                                     \
 503     if (ptr)                                            \
 504       debug (*ptr);                                     \
 505     else                                                \
 506       fprintf (stderr, "<nil>\n");                      \
 507   }
 508
 509 /* Default-construct N elements in DST.  */
 510
 511 template <typename T>
 512 inline void
 513 vec_default_construct (T *dst, unsigned n)
 514 {
 515 #ifdef BROKEN_VALUE_INITIALIZATION
 516   /* Versions of GCC before 4.4 sometimes leave certain objects
 517      uninitialized when value initialized, though if the type has
 518      user defined default ctor, that ctor is invoked.  As a workaround
 519      perform clearing first and then the value initialization, which
 520      fixes the case when value initialization doesn't initialize due to
 521      the bugs and should initialize to all zeros, but still allows
 522      vectors for types with user defined default ctor that initializes
 523      some or all elements to non-zero.  If T has no user defined
 524      default ctor and some non-static data members have user defined
 525      default ctors that initialize to non-zero the workaround will
 526      still not work properly; in that case we just need to provide
 527      user defined default ctor.  */
 528   memset (dst, '\0', sizeof (T) * n);
 529 #endif
 530   for ( ; n; ++dst, --n)
 531     ::new (static_cast<void*>(dst)) T ();
 532 }
 533
 534 /* Copy-construct N elements in DST from *SRC.  */
 535
 536 template <typename T>
 537 inline void
 538 vec_copy_construct (T *dst, const T *src, unsigned n)
 539 {
 540   for ( ; n; ++dst, ++src, --n)
 541     ::new (static_cast<void*>(dst)) T (*src);
 542 }
 543
 544 /* Type to provide zero-initialized values for vec<T, A, L>.  This is
 545    used to  provide nil initializers for vec instances.  Since vec must
 546    be a trivially copyable type that can be copied by memcpy and zeroed
 547    out by memset, it must have defaulted default and copy ctor and copy
 548    assignment.  To initialize a vec either use value initialization
 549    (e.g., vec() or vec v{ };) or assign it the value vNULL.  This isn't
 550    needed for file-scope and function-local static vectors, which are
 551    zero-initialized by default.  */
 552 struct vnull { };
 553 constexpr vnull vNULL{ };
 554
 555
 556 /* Embeddable vector.  These vectors are suitable to be embedded
 557    in other data structures so that they can be pre-allocated in a
 558    contiguous memory block.
 559
 560    Embeddable vectors are implemented using the trailing array idiom,
 561    thus they are not resizeable without changing the address of the
 562    vector object itself.  This means you cannot have variables or
 563    fields of embeddable vector type -- always use a pointer to a
 564    vector.  The one exception is the final field of a structure, which
 565    could be a vector type.
 566
 567    You will have to use the embedded_size & embedded_init calls to
 568    create such objects, and they will not be resizeable (so the 'safe'
 569    allocation variants are not available).
 570
 571    Properties:
 572
 573         - The whole vector and control data are allocated in a single
 574           contiguous block.  It uses the trailing-vector idiom, so
 575           allocation must reserve enough space for all the elements
 576           in the vector plus its control data.
 577         - The vector cannot be re-allocated.
 578         - The vector cannot grow nor shrink.
 579         - No indirections needed for access/manipulation.
 580         - It requires 2 words of storage (prior to vector allocation).  */
 581
 582 template<typename T, typename A>
 583 struct GTY((user)) vec<T, A, vl_embed>
 584 {
 585 public:
 586   unsigned allocated (void) const { return m_vecpfx.m_alloc; }
 587   unsigned length (void) const { return m_vecpfx.m_num; }
 588   bool is_empty (void) const { return m_vecpfx.m_num == 0; }
 589   T *address (void) { return m_vecdata; }
 590   const T *address (void) const { return m_vecdata; }
 591   T *begin () { return address (); }
 592   const T *begin () const { return address (); }
 593   T *end () { return address () + length (); }
 594   const T *end () const { return address () + length (); }
 595   const T &operator[] (unsigned) const;
 596   T &operator[] (unsigned);
 597   T &last (void);
 598   bool space (unsigned) const;
 599   bool iterate (unsigned, T *) const;
 600   bool iterate (unsigned, T **) const;
 601   vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
 602   void splice (const vec &);
 603   void splice (const vec *src);
 604   T *quick_push (const T &);
 605   T &pop (void);
 606   void truncate (unsigned);
 607   void quick_insert (unsigned, const T &);
 608   void ordered_remove (unsigned);
 609   void unordered_remove (unsigned);
 610   void block_remove (unsigned, unsigned);
 611   void qsort (int (*) (const void *, const void *));
 612   void sort (int (*) (const void *, const void *, void *), void *);
 613   void stablesort (int (*) (const void *, const void *, void *), void *);
 614   T *bsearch (const void *key, int (*compar)(const void *, const void *));
 615   T *bsearch (const void *key,
 616               int (*compar)(const void *, const void *, void *), void *);
 617   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
 618   bool contains (const T &search) const;
 619   static size_t embedded_size (unsigned);
 620   void embedded_init (unsigned, unsigned = 0, unsigned = 0);
 621   void quick_grow (unsigned len);
 622   void quick_grow_cleared (unsigned len);
 623
 624   /* vec class can access our internal data and functions.  */
 625   template <typename, typename, typename> friend struct vec;
 626
 627   /* The allocator types also need access to our internals.  */
 628   friend struct va_gc;
 629   friend struct va_gc_atomic;
 630   friend struct va_heap;
 631
 632   /* FIXME - These fields should be private, but we need to cater to
 633              compilers that have stricter notions of PODness for types.  */
 634   vec_prefix m_vecpfx;
 635   T m_vecdata[1];
 636 };
 637
 638
 639 /* Convenience wrapper functions to use when dealing with pointers to
 640    embedded vectors.  Some functionality for these vectors must be
 641    provided via free functions for these reasons:
 642
 643         1- The pointer may be NULL (e.g., before initial allocation).
 644
 645         2- When the vector needs to grow, it must be reallocated, so
 646            the pointer will change its value.
 647
 648    Because of limitations with the current GC machinery, all vectors
 649    in GC memory *must* be pointers.  */
 650
 651
 652 /* If V contains no room for NELEMS elements, return false. Otherwise,
 653    return true.  */
 654 template<typename T, typename A>
 655 inline bool
 656 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
 657 {
 658   return v ? v->space (nelems) : nelems == 0;
 659 }
 660
 661
 662 /* If V is NULL, return 0.  Otherwise, return V->length().  */
 663 template<typename T, typename A>
 664 inline unsigned
 665 vec_safe_length (const vec<T, A, vl_embed> *v)
 666 {
 667   return v ? v->length () : 0;
 668 }
 669
 670
 671 /* If V is NULL, return NULL.  Otherwise, return V->address().  */
 672 template<typename T, typename A>
 673 inline T *
 674 vec_safe_address (vec<T, A, vl_embed> *v)
 675 {
 676   return v ? v->address () : NULL;
 677 }
 678
 679
 680 /* If V is NULL, return true.  Otherwise, return V->is_empty().  */
 681 template<typename T, typename A>
 682 inline bool
 683 vec_safe_is_empty (vec<T, A, vl_embed> *v)
 684 {
 685   return v ? v->is_empty () : true;
 686 }
 687
 688 /* If V does not have space for NELEMS elements, call
 689    V->reserve(NELEMS, EXACT).  */
 690 template<typename T, typename A>
 691 inline bool
 692 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
 693                   CXX_MEM_STAT_INFO)
 694 {
 695   bool extend = nelems ? !vec_safe_space (v, nelems) : false;
 696   if (extend)
 697     A::reserve (v, nelems, exact PASS_MEM_STAT);
 698   return extend;
 699 }
 700
 701 template<typename T, typename A>
 702 inline bool
 703 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
 704                         CXX_MEM_STAT_INFO)
 705 {
 706   return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
 707 }
 708
 709
 710 /* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
 711    is 0, V is initialized to NULL.  */
 712
 713 template<typename T, typename A>
 714 inline void
 715 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
 716 {
 717   v = NULL;
 718   vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
 719 }
 720
 721
 722 /* Free the GC memory allocated by vector V and set it to NULL.  */
 723
 724 template<typename T, typename A>
 725 inline void
 726 vec_free (vec<T, A, vl_embed> *&v)
 727 {
 728   A::release (v);
 729 }
 730
 731
 732 /* Grow V to length LEN.  Allocate it, if necessary.  */
 733 template<typename T, typename A>
 734 inline void
 735 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
 736                bool exact = false CXX_MEM_STAT_INFO)
 737 {
 738   unsigned oldlen = vec_safe_length (v);
 739   gcc_checking_assert (len >= oldlen);
 740   vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
 741   v->quick_grow (len);
 742 }
 743
 744
 745 /* If V is NULL, allocate it.  Call V->safe_grow_cleared(LEN).  */
 746 template<typename T, typename A>
 747 inline void
 748 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
 749                        bool exact = false CXX_MEM_STAT_INFO)
 750 {
 751   unsigned oldlen = vec_safe_length (v);
 752   vec_safe_grow (v, len, exact PASS_MEM_STAT);
 753   vec_default_construct (v->address () + oldlen, len - oldlen);
 754 }
 755
 756
 757 /* Assume V is not NULL.  */
 758
 759 template<typename T>
 760 inline void
 761 vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
 762                        unsigned len, bool exact = false CXX_MEM_STAT_INFO)
 763 {
 764   v->safe_grow_cleared (len, exact PASS_MEM_STAT);
 765 }
 766
 767 /* If V does not have space for NELEMS elements, call
 768    V->reserve(NELEMS, EXACT).  */
 769
 770 template<typename T>
 771 inline bool
 772 vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
 773                   CXX_MEM_STAT_INFO)
 774 {
 775   return v->reserve (nelems, exact);
 776 }
 777
 778
 779 /* If V is NULL return false, otherwise return V->iterate(IX, PTR).  */
 780 template<typename T, typename A>
 781 inline bool
 782 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
 783 {
 784   if (v)
 785     return v->iterate (ix, ptr);
 786   else
 787     {
 788       *ptr = 0;
 789       return false;
 790     }
 791 }
 792
 793 template<typename T, typename A>
 794 inline bool
 795 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
 796 {
 797   if (v)
 798     return v->iterate (ix, ptr);
 799   else
 800     {
 801       *ptr = 0;
 802       return false;
 803     }
 804 }
 805
 806
 807 /* If V has no room for one more element, reallocate it.  Then call
 808    V->quick_push(OBJ).  */
 809 template<typename T, typename A>
 810 inline T *
 811 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
 812 {
 813   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 814   return v->quick_push (obj);
 815 }
 816
 817
 818 /* if V has no room for one more element, reallocate it.  Then call
 819    V->quick_insert(IX, OBJ).  */
 820 template<typename T, typename A>
 821 inline void
 822 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
 823                  CXX_MEM_STAT_INFO)
 824 {
 825   vec_safe_reserve (v, 1, false PASS_MEM_STAT);
 826   v->quick_insert (ix, obj);
 827 }
 828
 829
 830 /* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
 831 template<typename T, typename A>
 832 inline void
 833 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
 834 {
 835   if (v)
 836     v->truncate (size);
 837 }
 838
 839
 840 /* If SRC is not NULL, return a pointer to a copy of it.  */
 841 template<typename T, typename A>
 842 inline vec<T, A, vl_embed> *
 843 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
 844 {
 845   return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
 846 }
 847
 848 /* Copy the elements from SRC to the end of DST as if by memcpy.
 849    Reallocate DST, if necessary.  */
 850 template<typename T, typename A>
 851 inline void
 852 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
 853                  CXX_MEM_STAT_INFO)
 854 {
 855   unsigned src_len = vec_safe_length (src);
 856   if (src_len)
 857     {
 858       vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
 859                               PASS_MEM_STAT);
 860       dst->splice (*src);
 861     }
 862 }
 863
 864 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
 865    size of the vector and so should be used with care.  */
 866
 867 template<typename T, typename A>
 868 inline bool
 869 vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
 870 {
 871   return v ? v->contains (search) : false;
 872 }
 873
 874 /* Index into vector.  Return the IX'th element.  IX must be in the
 875    domain of the vector.  */
 876
 877 template<typename T, typename A>
 878 inline const T &
 879 vec<T, A, vl_embed>::operator[] (unsigned ix) const
 880 {
 881   gcc_checking_assert (ix < m_vecpfx.m_num);
 882   return m_vecdata[ix];
 883 }
 884
 885 template<typename T, typename A>
 886 inline T &
 887 vec<T, A, vl_embed>::operator[] (unsigned ix)
 888 {
 889   gcc_checking_assert (ix < m_vecpfx.m_num);
 890   return m_vecdata[ix];
 891 }
 892
 893
 894 /* Get the final element of the vector, which must not be empty.  */
 895
 896 template<typename T, typename A>
 897 inline T &
 898 vec<T, A, vl_embed>::last (void)
 899 {
 900   gcc_checking_assert (m_vecpfx.m_num > 0);
 901   return (*this)[m_vecpfx.m_num - 1];
 902 }
 903
 904
 905 /* If this vector has space for NELEMS additional entries, return
 906    true.  You usually only need to use this if you are doing your
 907    own vector reallocation, for instance on an embedded vector.  This
 908    returns true in exactly the same circumstances that vec::reserve
 909    will.  */
 910
 911 template<typename T, typename A>
 912 inline bool
 913 vec<T, A, vl_embed>::space (unsigned nelems) const
 914 {
 915   return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
 916 }
 917
 918
 919 /* Return iteration condition and update *PTR to (a copy of) the IX'th
 920    element of this vector.  Use this to iterate over the elements of a
 921    vector as follows,
 922
 923      for (ix = 0; v->iterate (ix, &val); ix++)
 924        continue;  */
 925
 926 template<typename T, typename A>
 927 inline bool
 928 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
 929 {
 930   if (ix < m_vecpfx.m_num)
 931     {
 932       *ptr = m_vecdata[ix];
 933       return true;
 934     }
 935   else
 936     {
 937       *ptr = 0;
 938       return false;
 939     }
 940 }
 941
 942
 943 /* Return iteration condition and update *PTR to point to the
 944    IX'th element of this vector.  Use this to iterate over the
 945    elements of a vector as follows,
 946
 947      for (ix = 0; v->iterate (ix, &ptr); ix++)
 948        continue;
 949
 950    This variant is for vectors of objects.  */
 951
 952 template<typename T, typename A>
 953 inline bool
 954 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
 955 {
 956   if (ix < m_vecpfx.m_num)
 957     {
 958       *ptr = CONST_CAST (T *, &m_vecdata[ix]);
 959       return true;
 960     }
 961   else
 962     {
 963       *ptr = 0;
 964       return false;
 965     }
 966 }
 967
 968
 969 /* Return a pointer to a copy of this vector.  */
 970
 971 template<typename T, typename A>
 972 inline vec<T, A, vl_embed> *
 973 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
 974 {
 975   vec<T, A, vl_embed> *new_vec = NULL;
 976   unsigned len = length ();
 977   if (len)
 978     {
 979       vec_alloc (new_vec, len PASS_MEM_STAT);
 980       new_vec->embedded_init (len, len);
 981       vec_copy_construct (new_vec->address (), m_vecdata, len);
 982     }
 983   return new_vec;
 984 }
 985
 986
 987 /* Copy the elements from SRC to the end of this vector as if by memcpy.
 988    The vector must have sufficient headroom available.  */
 989
 990 template<typename T, typename A>
 991 inline void
 992 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
 993 {
 994   unsigned len = src.length ();
 995   if (len)
 996     {
 997       gcc_checking_assert (space (len));
 998       vec_copy_construct (end (), src.address (), len);
 999       m_vecpfx.m_num += len;
1000     }
1001 }
1002
1003 template<typename T, typename A>
1004 inline void
1005 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1006 {
1007   if (src)
1008     splice (*src);
1009 }
1010
1011
1012 /* Push OBJ (a new element) onto the end of the vector.  There must be
1013    sufficient space in the vector.  Return a pointer to the slot
1014    where OBJ was inserted.  */
1015
1016 template<typename T, typename A>
1017 inline T *
1018 vec<T, A, vl_embed>::quick_push (const T &obj)
1019 {
1020   gcc_checking_assert (space (1));
1021   T *slot = &m_vecdata[m_vecpfx.m_num++];
1022   *slot = obj;
1023   return slot;
1024 }
1025
1026
1027 /* Pop and return the last element off the end of the vector.  */
1028
1029 template<typename T, typename A>
1030 inline T &
1031 vec<T, A, vl_embed>::pop (void)
1032 {
1033   gcc_checking_assert (length () > 0);
1034   return m_vecdata[--m_vecpfx.m_num];
1035 }
1036
1037
1038 /* Set the length of the vector to SIZE.  The new length must be less
1039    than or equal to the current length.  This is an O(1) operation.  */
1040
1041 template<typename T, typename A>
1042 inline void
1043 vec<T, A, vl_embed>::truncate (unsigned size)
1044 {
1045   gcc_checking_assert (length () >= size);
1046   m_vecpfx.m_num = size;
1047 }
1048
1049
1050 /* Insert an element, OBJ, at the IXth position of this vector.  There
1051    must be sufficient space.  */
1052
1053 template<typename T, typename A>
1054 inline void
1055 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1056 {
1057   gcc_checking_assert (length () < allocated ());
1058   gcc_checking_assert (ix <= length ());
1059   T *slot = &m_vecdata[ix];
1060   memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1061   *slot = obj;
1062 }
1063
1064
1065 /* Remove an element from the IXth position of this vector.  Ordering of
1066    remaining elements is preserved.  This is an O(N) operation due to
1067    memmove.  */
1068
1069 template<typename T, typename A>
1070 inline void
1071 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1072 {
1073   gcc_checking_assert (ix < length ());
1074   T *slot = &m_vecdata[ix];
1075   memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1076 }
1077
1078
1079 /* Remove elements in [START, END) from VEC for which COND holds.  Ordering of
1080    remaining elements is preserved.  This is an O(N) operation.  */
1081
1082 #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index,     \
1083                                       elem_ptr, start, end, cond)       \
1084   {                                                                     \
1085     gcc_assert ((end) <= (vec).length ());                              \
1086     for (read_index = write_index = (start); read_index < (end);        \
1087          ++read_index)                                                  \
1088       {                                                                 \
1089         elem_ptr = &(vec)[read_index];                                  \
1090         bool remove_p = (cond);                                         \
1091         if (remove_p)                                                   \
1092           continue;                                                     \
1093                                                                         \
1094         if (read_index != write_index)                                  \
1095           (vec)[write_index] = (vec)[read_index];                       \
1096                                                                         \
1097         write_index++;                                                  \
1098       }                                                                 \
1099                                                                         \
1100     if (read_index - write_index > 0)                                   \
1101       (vec).block_remove (write_index, read_index - write_index);       \
1102   }
1103
1104
1105 /* Remove elements from VEC for which COND holds.  Ordering of remaining
1106    elements is preserved.  This is an O(N) operation.  */
1107
1108 #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr,   \
1109                               cond)                                     \
1110   VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index,        \
1111                                  elem_ptr, 0, (vec).length (), (cond))
1112
1113 /* Remove an element from the IXth position of this vector.  Ordering of
1114    remaining elements is destroyed.  This is an O(1) operation.  */
1115
1116 template<typename T, typename A>
1117 inline void
1118 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1119 {
1120   gcc_checking_assert (ix < length ());
1121   m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1122 }
1123
1124
1125 /* Remove LEN elements starting at the IXth.  Ordering is retained.
1126    This is an O(N) operation due to memmove.  */
1127
1128 template<typename T, typename A>
1129 inline void
1130 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1131 {
1132   gcc_checking_assert (ix + len <= length ());
1133   T *slot = &m_vecdata[ix];
1134   m_vecpfx.m_num -= len;
1135   memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1136 }
1137
1138
1139 /* Sort the contents of this vector with qsort.  CMP is the comparison
1140    function to pass to qsort.  */
1141
1142 template<typename T, typename A>
1143 inline void
1144 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1145 {
1146   if (length () > 1)
1147     gcc_qsort (address (), length (), sizeof (T), cmp);
1148 }
1149
1150 /* Sort the contents of this vector with qsort.  CMP is the comparison
1151    function to pass to qsort.  */
1152
1153 template<typename T, typename A>
1154 inline void
1155 vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1156                            void *data)
1157 {
1158   if (length () > 1)
1159     gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1160 }
1161
1162 /* Sort the contents of this vector with gcc_stablesort_r.  CMP is the
1163    comparison function to pass to qsort.  */
1164
1165 template<typename T, typename A>
1166 inline void
1167 vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1168                                              void *), void *data)
1169 {
1170   if (length () > 1)
1171     gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1172 }
1173
1174 /* Search the contents of the sorted vector with a binary search.
1175    CMP is the comparison function to pass to bsearch.  */
1176
1177 template<typename T, typename A>
1178 inline T *
1179 vec<T, A, vl_embed>::bsearch (const void *key,
1180                               int (*compar) (const void *, const void *))
1181 {
1182   const void *base = this->address ();
1183   size_t nmemb = this->length ();
1184   size_t size = sizeof (T);
1185   /* The following is a copy of glibc stdlib-bsearch.h.  */
1186   size_t l, u, idx;
1187   const void *p;
1188   int comparison;
1189
1190   l = 0;
1191   u = nmemb;
1192   while (l < u)
1193     {
1194       idx = (l + u) / 2;
1195       p = (const void *) (((const char *) base) + (idx * size));
1196       comparison = (*compar) (key, p);
1197       if (comparison < 0)
1198         u = idx;
1199       else if (comparison > 0)
1200         l = idx + 1;
1201       else
1202         return (T *)const_cast<void *>(p);
1203     }
1204
1205   return NULL;
1206 }
1207
1208 /* Search the contents of the sorted vector with a binary search.
1209    CMP is the comparison function to pass to bsearch.  */
1210
1211 template<typename T, typename A>
1212 inline T *
1213 vec<T, A, vl_embed>::bsearch (const void *key,
1214                               int (*compar) (const void *, const void *,
1215                                              void *), void *data)
1216 {
1217   const void *base = this->address ();
1218   size_t nmemb = this->length ();
1219   size_t size = sizeof (T);
1220   /* The following is a copy of glibc stdlib-bsearch.h.  */
1221   size_t l, u, idx;
1222   const void *p;
1223   int comparison;
1224
1225   l = 0;
1226   u = nmemb;
1227   while (l < u)
1228     {
1229       idx = (l + u) / 2;
1230       p = (const void *) (((const char *) base) + (idx * size));
1231       comparison = (*compar) (key, p, data);
1232       if (comparison < 0)
1233         u = idx;
1234       else if (comparison > 0)
1235         l = idx + 1;
1236       else
1237         return (T *)const_cast<void *>(p);
1238     }
1239
1240   return NULL;
1241 }
1242
1243 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
1244    size of the vector and so should be used with care.  */
1245
1246 template<typename T, typename A>
1247 inline bool
1248 vec<T, A, vl_embed>::contains (const T &search) const
1249 {
1250   unsigned int len = length ();
1251   for (unsigned int i = 0; i < len; i++)
1252     if ((*this)[i] == search)
1253       return true;
1254
1255   return false;
1256 }
1257
1258 /* Find and return the first position in which OBJ could be inserted
1259    without changing the ordering of this vector.  LESSTHAN is a
1260    function that returns true if the first argument is strictly less
1261    than the second.  */
1262
1263 template<typename T, typename A>
1264 unsigned
1265 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1266   const
1267 {
1268   unsigned int len = length ();
1269   unsigned int half, middle;
1270   unsigned int first = 0;
1271   while (len > 0)
1272     {
1273       half = len / 2;
1274       middle = first;
1275       middle += half;
1276       T middle_elem = (*this)[middle];
1277       if (lessthan (middle_elem, obj))
1278         {
1279           first = middle;
1280           ++first;
1281           len = len - half - 1;
1282         }
1283       else
1284         len = half;
1285     }
1286   return first;
1287 }
1288
1289
1290 /* Return the number of bytes needed to embed an instance of an
1291    embeddable vec inside another data structure.
1292
1293    Use these methods to determine the required size and initialization
1294    of a vector V of type T embedded within another structure (as the
1295    final member):
1296
1297    size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1298    void v->embedded_init (unsigned alloc, unsigned num);
1299
1300    These allow the caller to perform the memory allocation.  */
1301
1302 template<typename T, typename A>
1303 inline size_t
1304 vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1305 {
1306   struct alignas (T) U { char data[sizeof (T)]; };
1307   typedef vec<U, A, vl_embed> vec_embedded;
1308   typedef typename std::conditional<std::is_standard_layout<T>::value,
1309                                     vec, vec_embedded>::type vec_stdlayout;
1310   static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1311   static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1312   return offsetof (vec_stdlayout, m_vecdata) + alloc * sizeof (T);
1313 }
1314
1315
1316 /* Initialize the vector to contain room for ALLOC elements and
1317    NUM active elements.  */
1318
1319 template<typename T, typename A>
1320 inline void
1321 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1322 {
1323   m_vecpfx.m_alloc = alloc;
1324   m_vecpfx.m_using_auto_storage = aut;
1325   m_vecpfx.m_num = num;
1326 }
1327
1328
1329 /* Grow the vector to a specific length.  LEN must be as long or longer than
1330    the current length.  The new elements are uninitialized.  */
1331
1332 template<typename T, typename A>
1333 inline void
1334 vec<T, A, vl_embed>::quick_grow (unsigned len)
1335 {
1336   gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1337   m_vecpfx.m_num = len;
1338 }
1339
1340
1341 /* Grow the vector to a specific length.  LEN must be as long or longer than
1342    the current length.  The new elements are initialized to zero.  */
1343
1344 template<typename T, typename A>
1345 inline void
1346 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1347 {
1348   unsigned oldlen = length ();
1349   size_t growby = len - oldlen;
1350   quick_grow (len);
1351   if (growby != 0)
1352     vec_default_construct (address () + oldlen, growby);
1353 }
1354
1355 /* Garbage collection support for vec<T, A, vl_embed>.  */
1356
1357 template<typename T>
1358 void
1359 gt_ggc_mx (vec<T, va_gc> *v)
1360 {
1361   extern void gt_ggc_mx (T &);
1362   for (unsigned i = 0; i < v->length (); i++)
1363     gt_ggc_mx ((*v)[i]);
1364 }
1365
1366 template<typename T>
1367 void
1368 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1369 {
1370   /* Nothing to do.  Vectors of atomic types wrt GC do not need to
1371      be traversed.  */
1372 }
1373
1374
1375 /* PCH support for vec<T, A, vl_embed>.  */
1376
1377 template<typename T, typename A>
1378 void
1379 gt_pch_nx (vec<T, A, vl_embed> *v)
1380 {
1381   extern void gt_pch_nx (T &);
1382   for (unsigned i = 0; i < v->length (); i++)
1383     gt_pch_nx ((*v)[i]);
1384 }
1385
1386 template<typename T, typename A>
1387 void
1388 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1389 {
1390   for (unsigned i = 0; i < v->length (); i++)
1391     op (&((*v)[i]), NULL, cookie);
1392 }
1393
1394 template<typename T, typename A>
1395 void
1396 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1397 {
1398   extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1399   for (unsigned i = 0; i < v->length (); i++)
1400     gt_pch_nx (&((*v)[i]), op, cookie);
1401 }
1402
1403
1404 /* Space efficient vector.  These vectors can grow dynamically and are
1405    allocated together with their control data.  They are suited to be
1406    included in data structures.  Prior to initial allocation, they
1407    only take a single word of storage.
1408
1409    These vectors are implemented as a pointer to an embeddable vector.
1410    The semantics allow for this pointer to be NULL to represent empty
1411    vectors.  This way, empty vectors occupy minimal space in the
1412    structure containing them.
1413
1414    Properties:
1415
1416         - The whole vector and control data are allocated in a single
1417           contiguous block.
1418         - The whole vector may be re-allocated.
1419         - Vector data may grow and shrink.
1420         - Access and manipulation requires a pointer test and
1421           indirection.
1422         - It requires 1 word of storage (prior to vector allocation).
1423
1424
1425    Limitations:
1426
1427    These vectors must be PODs because they are stored in unions.
1428    (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1429    As long as we use C++03, we cannot have constructors nor
1430    destructors in classes that are stored in unions.  */
1431
1432 template<typename T, size_t N = 0>
1433 class auto_vec;
1434
1435 template<typename T>
1436 struct vec<T, va_heap, vl_ptr>
1437 {
1438 public:
1439   /* Default ctors to ensure triviality.  Use value-initialization
1440      (e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1441      instance.  */
1442   vec () = default;
1443   vec (const vec &) = default;
1444   /* Initialization from the generic vNULL.  */
1445   vec (vnull): m_vec () { }
1446   /* Same as default ctor: vec storage must be released manually.  */
1447   ~vec () = default;
1448
1449   /* Defaulted same as copy ctor.  */
1450   vec& operator= (const vec &) = default;
1451
1452   /* Prevent implicit conversion from auto_vec.  Use auto_vec::to_vec()
1453      instead.  */
1454   template <size_t N>
1455   vec (auto_vec<T, N> &) = delete;
1456
1457   template <size_t N>
1458   void operator= (auto_vec<T, N> &) = delete;
1459
1460   /* Memory allocation and deallocation for the embedded vector.
1461      Needed because we cannot have proper ctors/dtors defined.  */
1462   void create (unsigned nelems CXX_MEM_STAT_INFO);
1463   void release (void);
1464
1465   /* Vector operations.  */
1466   bool exists (void) const
1467   { return m_vec != NULL; }
1468
1469   bool is_empty (void) const
1470   { return m_vec ? m_vec->is_empty () : true; }
1471
1472   unsigned allocated (void) const
1473   { return m_vec ? m_vec->allocated () : 0; }
1474
1475   unsigned length (void) const
1476   { return m_vec ? m_vec->length () : 0; }
1477
1478   T *address (void)
1479   { return m_vec ? m_vec->m_vecdata : NULL; }
1480
1481   const T *address (void) const
1482   { return m_vec ? m_vec->m_vecdata : NULL; }
1483
1484   T *begin () { return address (); }
1485   const T *begin () const { return address (); }
1486   T *end () { return begin () + length (); }
1487   const T *end () const { return begin () + length (); }
1488   const T &operator[] (unsigned ix) const
1489   { return (*m_vec)[ix]; }
1490
1491   bool operator!=(const vec &other) const
1492   { return !(*this == other); }
1493
1494   bool operator==(const vec &other) const
1495   { return address () == other.address (); }
1496
1497   T &operator[] (unsigned ix)
1498   { return (*m_vec)[ix]; }
1499
1500   T &last (void)
1501   { return m_vec->last (); }
1502
1503   bool space (int nelems) const
1504   { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1505
1506   bool iterate (unsigned ix, T *p) const;
1507   bool iterate (unsigned ix, T **p) const;
1508   vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1509   bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1510   bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1511   void splice (const vec &);
1512   void safe_splice (const vec & CXX_MEM_STAT_INFO);
1513   T *quick_push (const T &);
1514   T *safe_push (const T &CXX_MEM_STAT_INFO);
1515   T &pop (void);
1516   void truncate (unsigned);
1517   void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
1518   void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
1519   void quick_grow (unsigned);
1520   void quick_grow_cleared (unsigned);
1521   void quick_insert (unsigned, const T &);
1522   void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1523   void ordered_remove (unsigned);
1524   void unordered_remove (unsigned);
1525   void block_remove (unsigned, unsigned);
1526   void qsort (int (*) (const void *, const void *));
1527   void sort (int (*) (const void *, const void *, void *), void *);
1528   void stablesort (int (*) (const void *, const void *, void *), void *);
1529   T *bsearch (const void *key, int (*compar)(const void *, const void *));
1530   T *bsearch (const void *key,
1531               int (*compar)(const void *, const void *, void *), void *);
1532   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1533   bool contains (const T &search) const;
1534   void reverse (void);
1535
1536   bool using_auto_storage () const;
1537
1538   /* FIXME - This field should be private, but we need to cater to
1539              compilers that have stricter notions of PODness for types.  */
1540   vec<T, va_heap, vl_embed> *m_vec;
1541 };
1542
1543
1544 /* auto_vec is a subclass of vec that automatically manages creating and
1545    releasing the internal vector. If N is non zero then it has N elements of
1546    internal storage.  The default is no internal storage, and you probably only
1547    want to ask for internal storage for vectors on the stack because if the
1548    size of the vector is larger than the internal storage that space is wasted.
1549    */
1550 template<typename T, size_t N /* = 0 */>
1551 class auto_vec : public vec<T, va_heap>
1552 {
1553 public:
1554   auto_vec ()
1555   {
1556     m_auto.embedded_init (MAX (N, 2), 0, 1);
1557     this->m_vec = &m_auto;
1558   }
1559
1560   auto_vec (size_t s CXX_MEM_STAT_INFO)
1561   {
1562     if (s > N)
1563       {
1564         this->create (s PASS_MEM_STAT);
1565         return;
1566       }
1567
1568     m_auto.embedded_init (MAX (N, 2), 0, 1);
1569     this->m_vec = &m_auto;
1570   }
1571
1572   ~auto_vec ()
1573   {
1574     this->release ();
1575   }
1576
1577   /* Explicitly convert to the base class.  There is no conversion
1578      from a const auto_vec because a copy of the returned vec can
1579      be used to modify *THIS.
1580      This is a legacy function not to be used in new code.  */
1581   vec<T, va_heap> to_vec_legacy () {
1582     return *static_cast<vec<T, va_heap> *>(this);
1583   }
1584
1585 private:
1586   vec<T, va_heap, vl_embed> m_auto;
1587   T m_data[MAX (N - 1, 1)];
1588 };
1589
1590 /* auto_vec is a sub class of vec whose storage is released when it is
1591   destroyed. */
1592 template<typename T>
1593 class auto_vec<T, 0> : public vec<T, va_heap>
1594 {
1595 public:
1596   auto_vec () { this->m_vec = NULL; }
1597   auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); }
1598   ~auto_vec () { this->release (); }
1599
1600   auto_vec (vec<T, va_heap>&& r)
1601     {
1602       gcc_assert (!r.using_auto_storage ());
1603       this->m_vec = r.m_vec;
1604       r.m_vec = NULL;
1605     }
1606
1607   auto_vec (auto_vec<T> &&r)
1608     {
1609       gcc_assert (!r.using_auto_storage ());
1610       this->m_vec = r.m_vec;
1611       r.m_vec = NULL;
1612     }
1613
1614   auto_vec& operator= (vec<T, va_heap>&& r)
1615     {
1616             if (this == &r)
1617                     return *this;
1618
1619       gcc_assert (!r.using_auto_storage ());
1620       this->release ();
1621       this->m_vec = r.m_vec;
1622       r.m_vec = NULL;
1623       return *this;
1624     }
1625
1626   auto_vec& operator= (auto_vec<T> &&r)
1627     {
1628             if (this == &r)
1629                     return *this;
1630
1631       gcc_assert (!r.using_auto_storage ());
1632       this->release ();
1633       this->m_vec = r.m_vec;
1634       r.m_vec = NULL;
1635       return *this;
1636     }
1637
1638   /* Explicitly convert to the base class.  There is no conversion
1639      from a const auto_vec because a copy of the returned vec can
1640      be used to modify *THIS.
1641      This is a legacy function not to be used in new code.  */
1642   vec<T, va_heap> to_vec_legacy () {
1643     return *static_cast<vec<T, va_heap> *>(this);
1644   }
1645
1646   // You probably don't want to copy a vector, so these are deleted to prevent
1647   // unintentional use.  If you really need a copy of the vectors contents you
1648   // can use copy ().
1649   auto_vec(const auto_vec &) = delete;
1650   auto_vec &operator= (const auto_vec &) = delete;
1651 };
1652
1653
1654 /* Allocate heap memory for pointer V and create the internal vector
1655    with space for NELEMS elements.  If NELEMS is 0, the internal
1656    vector is initialized to empty.  */
1657
1658 template<typename T>
1659 inline void
1660 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1661 {
1662   v = new vec<T>;
1663   v->create (nelems PASS_MEM_STAT);
1664 }
1665
1666
1667 /* A subclass of auto_vec <char *> that frees all of its elements on
1668    deletion.  */
1669
1670 class auto_string_vec : public auto_vec <char *>
1671 {
1672  public:
1673   ~auto_string_vec ();
1674 };
1675
1676 /* A subclass of auto_vec <T *> that deletes all of its elements on
1677    destruction.
1678
1679    This is a crude way for a vec to "own" the objects it points to
1680    and clean up automatically.
1681
1682    For example, no attempt is made to delete elements when an item
1683    within the vec is overwritten.
1684
1685    We can't rely on gnu::unique_ptr within a container,
1686    since we can't rely on move semantics in C++98.  */
1687
1688 template <typename T>
1689 class auto_delete_vec : public auto_vec <T *>
1690 {
1691  public:
1692   auto_delete_vec () {}
1693   auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1694
1695   ~auto_delete_vec ();
1696
1697 private:
1698   DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1699 };
1700
1701 /* Conditionally allocate heap memory for VEC and its internal vector.  */
1702
1703 template<typename T>
1704 inline void
1705 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1706 {
1707   if (!vec)
1708     vec_alloc (vec, nelems PASS_MEM_STAT);
1709 }
1710
1711
1712 /* Free the heap memory allocated by vector V and set it to NULL.  */
1713
1714 template<typename T>
1715 inline void
1716 vec_free (vec<T> *&v)
1717 {
1718   if (v == NULL)
1719     return;
1720
1721   v->release ();
1722   delete v;
1723   v = NULL;
1724 }
1725
1726
1727 /* Return iteration condition and update PTR to point to the IX'th
1728    element of this vector.  Use this to iterate over the elements of a
1729    vector as follows,
1730
1731      for (ix = 0; v.iterate (ix, &ptr); ix++)
1732        continue;  */
1733
1734 template<typename T>
1735 inline bool
1736 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1737 {
1738   if (m_vec)
1739     return m_vec->iterate (ix, ptr);
1740   else
1741     {
1742       *ptr = 0;
1743       return false;
1744     }
1745 }
1746
1747
1748 /* Return iteration condition and update *PTR to point to the
1749    IX'th element of this vector.  Use this to iterate over the
1750    elements of a vector as follows,
1751
1752      for (ix = 0; v->iterate (ix, &ptr); ix++)
1753        continue;
1754
1755    This variant is for vectors of objects.  */
1756
1757 template<typename T>
1758 inline bool
1759 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1760 {
1761   if (m_vec)
1762     return m_vec->iterate (ix, ptr);
1763   else
1764     {
1765       *ptr = 0;
1766       return false;
1767     }
1768 }
1769
1770
1771 /* Convenience macro for forward iteration.  */
1772 #define FOR_EACH_VEC_ELT(V, I, P)                       \
1773   for (I = 0; (V).iterate ((I), &(P)); ++(I))
1774
1775 #define FOR_EACH_VEC_SAFE_ELT(V, I, P)                  \
1776   for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1777
1778 /* Likewise, but start from FROM rather than 0.  */
1779 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)            \
1780   for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1781
1782 /* Convenience macro for reverse iteration.  */
1783 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P)               \
1784   for (I = (V).length () - 1;                           \
1785        (V).iterate ((I), &(P));                         \
1786        (I)--)
1787
1788 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)          \
1789   for (I = vec_safe_length (V) - 1;                     \
1790        vec_safe_iterate ((V), (I), &(P));       \
1791        (I)--)
1792
1793 /* auto_string_vec's dtor, freeing all contained strings, automatically
1794    chaining up to ~auto_vec <char *>, which frees the internal buffer.  */
1795
1796 inline
1797 auto_string_vec::~auto_string_vec ()
1798 {
1799   int i;
1800   char *str;
1801   FOR_EACH_VEC_ELT (*this, i, str)
1802     free (str);
1803 }
1804
1805 /* auto_delete_vec's dtor, deleting all contained items, automatically
1806    chaining up to ~auto_vec <T*>, which frees the internal buffer.  */
1807
1808 template <typename T>
1809 inline
1810 auto_delete_vec<T>::~auto_delete_vec ()
1811 {
1812   int i;
1813   T *item;
1814   FOR_EACH_VEC_ELT (*this, i, item)
1815     delete item;
1816 }
1817
1818
1819 /* Return a copy of this vector.  */
1820
1821 template<typename T>
1822 inline vec<T, va_heap, vl_ptr>
1823 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1824 {
1825   vec<T, va_heap, vl_ptr> new_vec{ };
1826   if (length ())
1827     new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1828   return new_vec;
1829 }
1830
1831
1832 /* Ensure that the vector has at least RESERVE slots available (if
1833    EXACT is false), or exactly RESERVE slots available (if EXACT is
1834    true).
1835
1836    This may create additional headroom if EXACT is false.
1837
1838    Note that this can cause the embedded vector to be reallocated.
1839    Returns true iff reallocation actually occurred.  */
1840
1841 template<typename T>
1842 inline bool
1843 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1844 {
1845   if (space (nelems))
1846     return false;
1847
1848   /* For now play a game with va_heap::reserve to hide our auto storage if any,
1849      this is necessary because it doesn't have enough information to know the
1850      embedded vector is in auto storage, and so should not be freed.  */
1851   vec<T, va_heap, vl_embed> *oldvec = m_vec;
1852   unsigned int oldsize = 0;
1853   bool handle_auto_vec = m_vec && using_auto_storage ();
1854   if (handle_auto_vec)
1855     {
1856       m_vec = NULL;
1857       oldsize = oldvec->length ();
1858       nelems += oldsize;
1859     }
1860
1861   va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1862   if (handle_auto_vec)
1863     {
1864       vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1865       m_vec->m_vecpfx.m_num = oldsize;
1866     }
1867
1868   return true;
1869 }
1870
1871
1872 /* Ensure that this vector has exactly NELEMS slots available.  This
1873    will not create additional headroom.  Note this can cause the
1874    embedded vector to be reallocated.  Returns true iff reallocation
1875    actually occurred.  */
1876
1877 template<typename T>
1878 inline bool
1879 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1880 {
1881   return reserve (nelems, true PASS_MEM_STAT);
1882 }
1883
1884
1885 /* Create the internal vector and reserve NELEMS for it.  This is
1886    exactly like vec::reserve, but the internal vector is
1887    unconditionally allocated from scratch.  The old one, if it
1888    existed, is lost.  */
1889
1890 template<typename T>
1891 inline void
1892 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1893 {
1894   m_vec = NULL;
1895   if (nelems > 0)
1896     reserve_exact (nelems PASS_MEM_STAT);
1897 }
1898
1899
1900 /* Free the memory occupied by the embedded vector.  */
1901
1902 template<typename T>
1903 inline void
1904 vec<T, va_heap, vl_ptr>::release (void)
1905 {
1906   if (!m_vec)
1907     return;
1908
1909   if (using_auto_storage ())
1910     {
1911       m_vec->m_vecpfx.m_num = 0;
1912       return;
1913     }
1914
1915   va_heap::release (m_vec);
1916 }
1917
1918 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1919    SRC and this vector must be allocated with the same memory
1920    allocation mechanism. This vector is assumed to have sufficient
1921    headroom available.  */
1922
1923 template<typename T>
1924 inline void
1925 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1926 {
1927   if (src.length ())
1928     m_vec->splice (*(src.m_vec));
1929 }
1930
1931
1932 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1933    SRC and this vector must be allocated with the same mechanism.
1934    If there is not enough headroom in this vector, it will be reallocated
1935    as needed.  */
1936
1937 template<typename T>
1938 inline void
1939 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1940                                       MEM_STAT_DECL)
1941 {
1942   if (src.length ())
1943     {
1944       reserve_exact (src.length ());
1945       splice (src);
1946     }
1947 }
1948
1949
1950 /* Push OBJ (a new element) onto the end of the vector.  There must be
1951    sufficient space in the vector.  Return a pointer to the slot
1952    where OBJ was inserted.  */
1953
1954 template<typename T>
1955 inline T *
1956 vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1957 {
1958   return m_vec->quick_push (obj);
1959 }
1960
1961
1962 /* Push a new element OBJ onto the end of this vector.  Reallocates
1963    the embedded vector, if needed.  Return a pointer to the slot where
1964    OBJ was inserted.  */
1965
1966 template<typename T>
1967 inline T *
1968 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1969 {
1970   reserve (1, false PASS_MEM_STAT);
1971   return quick_push (obj);
1972 }
1973
1974
1975 /* Pop and return the last element off the end of the vector.  */
1976
1977 template<typename T>
1978 inline T &
1979 vec<T, va_heap, vl_ptr>::pop (void)
1980 {
1981   return m_vec->pop ();
1982 }
1983
1984
1985 /* Set the length of the vector to LEN.  The new length must be less
1986    than or equal to the current length.  This is an O(1) operation.  */
1987
1988 template<typename T>
1989 inline void
1990 vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1991 {
1992   if (m_vec)
1993     m_vec->truncate (size);
1994   else
1995     gcc_checking_assert (size == 0);
1996 }
1997
1998
1999 /* Grow the vector to a specific length.  LEN must be as long or
2000    longer than the current length.  The new elements are
2001    uninitialized.  Reallocate the internal vector, if needed.  */
2002
2003 template<typename T>
2004 inline void
2005 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2006 {
2007   unsigned oldlen = length ();
2008   gcc_checking_assert (oldlen <= len);
2009   reserve (len - oldlen, exact PASS_MEM_STAT);
2010   if (m_vec)
2011     m_vec->quick_grow (len);
2012   else
2013     gcc_checking_assert (len == 0);
2014 }
2015
2016
2017 /* Grow the embedded vector to a specific length.  LEN must be as
2018    long or longer than the current length.  The new elements are
2019    initialized to zero.  Reallocate the internal vector, if needed.  */
2020
2021 template<typename T>
2022 inline void
2023 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2024                                             MEM_STAT_DECL)
2025 {
2026   unsigned oldlen = length ();
2027   size_t growby = len - oldlen;
2028   safe_grow (len, exact PASS_MEM_STAT);
2029   if (growby != 0)
2030     vec_default_construct (address () + oldlen, growby);
2031 }
2032
2033
2034 /* Same as vec::safe_grow but without reallocation of the internal vector.
2035    If the vector cannot be extended, a runtime assertion will be triggered.  */
2036
2037 template<typename T>
2038 inline void
2039 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2040 {
2041   gcc_checking_assert (m_vec);
2042   m_vec->quick_grow (len);
2043 }
2044
2045
2046 /* Same as vec::quick_grow_cleared but without reallocation of the
2047    internal vector. If the vector cannot be extended, a runtime
2048    assertion will be triggered.  */
2049
2050 template<typename T>
2051 inline void
2052 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2053 {
2054   gcc_checking_assert (m_vec);
2055   m_vec->quick_grow_cleared (len);
2056 }
2057
2058
2059 /* Insert an element, OBJ, at the IXth position of this vector.  There
2060    must be sufficient space.  */
2061
2062 template<typename T>
2063 inline void
2064 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2065 {
2066   m_vec->quick_insert (ix, obj);
2067 }
2068
2069
2070 /* Insert an element, OBJ, at the IXth position of the vector.
2071    Reallocate the embedded vector, if necessary.  */
2072
2073 template<typename T>
2074 inline void
2075 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2076 {
2077   reserve (1, false PASS_MEM_STAT);
2078   quick_insert (ix, obj);
2079 }
2080
2081
2082 /* Remove an element from the IXth position of this vector.  Ordering of
2083    remaining elements is preserved.  This is an O(N) operation due to
2084    a memmove.  */
2085
2086 template<typename T>
2087 inline void
2088 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2089 {
2090   m_vec->ordered_remove (ix);
2091 }
2092
2093
2094 /* Remove an element from the IXth position of this vector.  Ordering
2095    of remaining elements is destroyed.  This is an O(1) operation.  */
2096
2097 template<typename T>
2098 inline void
2099 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2100 {
2101   m_vec->unordered_remove (ix);
2102 }
2103
2104
2105 /* Remove LEN elements starting at the IXth.  Ordering is retained.
2106    This is an O(N) operation due to memmove.  */
2107
2108 template<typename T>
2109 inline void
2110 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2111 {
2112   m_vec->block_remove (ix, len);
2113 }
2114
2115
2116 /* Sort the contents of this vector with qsort.  CMP is the comparison
2117    function to pass to qsort.  */
2118
2119 template<typename T>
2120 inline void
2121 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
2122 {
2123   if (m_vec)
2124     m_vec->qsort (cmp);
2125 }
2126
2127 /* Sort the contents of this vector with qsort.  CMP is the comparison
2128    function to pass to qsort.  */
2129
2130 template<typename T>
2131 inline void
2132 vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
2133                                            void *), void *data)
2134 {
2135   if (m_vec)
2136     m_vec->sort (cmp, data);
2137 }
2138
2139 /* Sort the contents of this vector with gcc_stablesort_r.  CMP is the
2140    comparison function to pass to qsort.  */
2141
2142 template<typename T>
2143 inline void
2144 vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *,
2145                                                  void *), void *data)
2146 {
2147   if (m_vec)
2148     m_vec->stablesort (cmp, data);
2149 }
2150
2151 /* Search the contents of the sorted vector with a binary search.
2152    CMP is the comparison function to pass to bsearch.  */
2153
2154 template<typename T>
2155 inline T *
2156 vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2157                                   int (*cmp) (const void *, const void *))
2158 {
2159   if (m_vec)
2160     return m_vec->bsearch (key, cmp);
2161   return NULL;
2162 }
2163
2164 /* Search the contents of the sorted vector with a binary search.
2165    CMP is the comparison function to pass to bsearch.  */
2166
2167 template<typename T>
2168 inline T *
2169 vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2170                                   int (*cmp) (const void *, const void *,
2171                                               void *), void *data)
2172 {
2173   if (m_vec)
2174     return m_vec->bsearch (key, cmp, data);
2175   return NULL;
2176 }
2177
2178
2179 /* Find and return the first position in which OBJ could be inserted
2180    without changing the ordering of this vector.  LESSTHAN is a
2181    function that returns true if the first argument is strictly less
2182    than the second.  */
2183
2184 template<typename T>
2185 inline unsigned
2186 vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2187                                       bool (*lessthan)(const T &, const T &))
2188     const
2189 {
2190   return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
2191 }
2192
2193 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
2194    size of the vector and so should be used with care.  */
2195
2196 template<typename T>
2197 inline bool
2198 vec<T, va_heap, vl_ptr>::contains (const T &search) const
2199 {
2200   return m_vec ? m_vec->contains (search) : false;
2201 }
2202
2203 /* Reverse content of the vector.  */
2204
2205 template<typename T>
2206 inline void
2207 vec<T, va_heap, vl_ptr>::reverse (void)
2208 {
2209   unsigned l = length ();
2210   T *ptr = address ();
2211
2212   for (unsigned i = 0; i < l / 2; i++)
2213     std::swap (ptr[i], ptr[l - i - 1]);
2214 }
2215
2216 template<typename T>
2217 inline bool
2218 vec<T, va_heap, vl_ptr>::using_auto_storage () const
2219 {
2220   return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2221 }
2222
2223 /* Release VEC and call release of all element vectors.  */
2224
2225 template<typename T>
2226 inline void
2227 release_vec_vec (vec<vec<T> > &vec)
2228 {
2229   for (unsigned i = 0; i < vec.length (); i++)
2230     vec[i].release ();
2231
2232   vec.release ();
2233 }
2234
2235 // Provide a subset of the std::span functionality.  (We can't use std::span
2236 // itself because it's a C++20 feature.)
2237 //
2238 // In addition, provide an invalid value that is distinct from all valid
2239 // sequences (including the empty sequence).  This can be used to return
2240 // failure without having to use std::optional.
2241 //
2242 // There is no operator bool because it would be ambiguous whether it is
2243 // testing for a valid value or an empty sequence.
2244 template<typename T>
2245 class array_slice
2246 {
2247   template<typename OtherT> friend class array_slice;
2248
2249 public:
2250   using value_type = T;
2251   using iterator = T *;
2252   using const_iterator = const T *;
2253
2254   array_slice () : m_base (nullptr), m_size (0) {}
2255
2256   template<typename OtherT>
2257   array_slice (array_slice<OtherT> other)
2258     : m_base (other.m_base), m_size (other.m_size) {}
2259
2260   array_slice (iterator base, unsigned int size)
2261     : m_base (base), m_size (size) {}
2262
2263   template<size_t N>
2264   array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2265
2266   template<typename OtherT>
2267   array_slice (const vec<OtherT> &v)
2268     : m_base (v.address ()), m_size (v.length ()) {}
2269
2270   template<typename OtherT>
2271   array_slice (vec<OtherT> &v)
2272     : m_base (v.address ()), m_size (v.length ()) {}
2273
2274   template<typename OtherT>
2275   array_slice (const vec<OtherT, va_gc> *v)
2276     : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2277
2278   template<typename OtherT>
2279   array_slice (vec<OtherT, va_gc> *v)
2280     : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2281
2282   iterator begin () { return m_base; }
2283   iterator end () { return m_base + m_size; }
2284
2285   const_iterator begin () const { return m_base; }
2286   const_iterator end () const { return m_base + m_size; }
2287
2288   value_type &front ();
2289   value_type &back ();
2290   value_type &operator[] (unsigned int i);
2291
2292   const value_type &front () const;
2293   const value_type &back () const;
2294   const value_type &operator[] (unsigned int i) const;
2295
2296   size_t size () const { return m_size; }
2297   size_t size_bytes () const { return m_size * sizeof (T); }
2298   bool empty () const { return m_size == 0; }
2299
2300   // An invalid array_slice that represents a failed operation.  This is
2301   // distinct from an empty slice, which is a valid result in some contexts.
2302   static array_slice invalid () { return { nullptr, ~0U }; }
2303
2304   // True if the array is valid, false if it is an array like INVALID.
2305   bool is_valid () const { return m_base || m_size == 0; }
2306
2307 private:
2308   iterator m_base;
2309   unsigned int m_size;
2310 };
2311
2312 template<typename T>
2313 inline typename array_slice<T>::value_type &
2314 array_slice<T>::front ()
2315 {
2316   gcc_checking_assert (m_size);
2317   return m_base[0];
2318 }
2319
2320 template<typename T>
2321 inline const typename array_slice<T>::value_type &
2322 array_slice<T>::front () const
2323 {
2324   gcc_checking_assert (m_size);
2325   return m_base[0];
2326 }
2327
2328 template<typename T>
2329 inline typename array_slice<T>::value_type &
2330 array_slice<T>::back ()
2331 {
2332   gcc_checking_assert (m_size);
2333   return m_base[m_size - 1];
2334 }
2335
2336 template<typename T>
2337 inline const typename array_slice<T>::value_type &
2338 array_slice<T>::back () const
2339 {
2340   gcc_checking_assert (m_size);
2341   return m_base[m_size - 1];
2342 }
2343
2344 template<typename T>
2345 inline typename array_slice<T>::value_type &
2346 array_slice<T>::operator[] (unsigned int i)
2347 {
2348   gcc_checking_assert (i < m_size);
2349   return m_base[i];
2350 }
2351
2352 template<typename T>
2353 inline const typename array_slice<T>::value_type &
2354 array_slice<T>::operator[] (unsigned int i) const
2355 {
2356   gcc_checking_assert (i < m_size);
2357   return m_base[i];
2358 }
2359
2360 template<typename T>
2361 array_slice<T>
2362 make_array_slice (T *base, unsigned int size)
2363 {
2364   return array_slice<T> (base, size);
2365 }
2366
2367 #if (GCC_VERSION >= 3000)
2368 # pragma GCC poison m_vec m_vecpfx m_vecdata
2369 #endif
2370
2371 #endif // GCC_VEC_H