LCOV - code coverage report
Current view: top level - gcc - vec.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.6 % 563 538
Test Date: 2024-03-23 14:05:01 Functions: 88.6 % 4801 4255
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

Generated by: LCOV version 2.0-1

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.