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

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.