Merge trunk version 193672 into gupc branch.

[official-gcc.git] / gcc / vec.h

/* Vector API for GNU compiler.
   Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
   Free Software Foundation, Inc.
   Contributed by Nathan Sidwell <nathan@codesourcery.com>
   Re-implemented in C++ by Diego Novillo <dnovillo@google.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_VEC_H
#define GCC_VEC_H

/* FIXME - When compiling some of the gen* binaries, we cannot enable GC
   support because the headers generated by gengtype are still not
   present.  In particular, the header file gtype-desc.h is missing,
   so compilation may fail if we try to include ggc.h.

   Since we use some of those declarations, we need to provide them
   (even if the GC-based templates are not used).  This is not a
   problem because the code that runs before gengtype is built will
   never need to use GC vectors.  But it does force us to declare
   these functions more than once.  */
#ifdef GENERATOR_FILE
#define VEC_GC_ENABLED  0
#else
#define VEC_GC_ENABLED  1
#endif  // GENERATOR_FILE

#include "statistics.h"         // For CXX_MEM_STAT_INFO.

#if VEC_GC_ENABLED
#include "ggc.h"
#else
# ifndef GCC_GGC_H
  /* Even if we think that GC is not enabled, the test that sets it is
     weak.  There are files compiled with -DGENERATOR_FILE that already
     include ggc.h.  We only need to provide these definitions if ggc.h
     has not been included.  Sigh.  */
  extern void ggc_free (void *);
  extern size_t ggc_round_alloc_size (size_t requested_size);
  extern void *ggc_internal_cleared_alloc_stat (size_t MEM_STAT_DECL)
    ATTRIBUTE_MALLOC;
  extern void *ggc_realloc_stat (void *, size_t MEM_STAT_DECL);
#  endif  // GCC_GGC_H
#endif  // VEC_GC_ENABLED

/* Templated vector type and associated interfaces.

   The interface functions are typesafe and use inline functions,
   sometimes backed by out-of-line generic functions.  The vectors are
   designed to interoperate with the GTY machinery.

   There are both 'index' and 'iterate' accessors.  The index accessor
   is implemented by operator[].  The iterator returns a boolean
   iteration condition and updates the iteration variable passed by
   reference.  Because the iterator will be inlined, the address-of
   can be optimized away.

   Each operation that increases the number of active elements is
   available in 'quick' and 'safe' variants.  The former presumes that
   there is sufficient allocated space for the operation to succeed
   (it dies if there is not).  The latter will reallocate the
   vector, if needed.  Reallocation causes an exponential increase in
   vector size.  If you know you will be adding N elements, it would
   be more efficient to use the reserve operation before adding the
   elements with the 'quick' operation.  This will ensure there are at
   least as many elements as you ask for, it will exponentially
   increase if there are too few spare slots.  If you want reserve a
   specific number of slots, but do not want the exponential increase
   (for instance, you know this is the last allocation), use the
   reserve_exact operation.  You can also create a vector of a
   specific size from the get go.

   You should prefer the push and pop operations, as they append and
   remove from the end of the vector. If you need to remove several
   items in one go, use the truncate operation.  The insert and remove
   operations allow you to change elements in the middle of the
   vector.  There are two remove operations, one which preserves the
   element ordering 'ordered_remove', and one which does not
   'unordered_remove'.  The latter function copies the end element
   into the removed slot, rather than invoke a memmove operation.  The
   'lower_bound' function will determine where to place an item in the
   array using insert that will maintain sorted order.

   Vectors are template types with three arguments: the type of the
   elements in the vector, the allocation strategy, and the physical
   layout to use

   Four allocation strategies are supported:

        - Heap: allocation is done using malloc/free.  This is the
          default allocation strategy.

        - Stack: allocation is done using alloca.

        - GC: allocation is done using ggc_alloc/ggc_free.

        - GC atomic: same as GC with the exception that the elements
          themselves are assumed to be of an atomic type that does
          not need to be garbage collected.  This means that marking
          routines do not need to traverse the array marking the
          individual elements.  This increases the performance of
          GC activities.

   Two physical layouts are supported:

        - Embedded: The vector is structured using the trailing array
          idiom.  The last member of the structure is an array of size
          1.  When the vector is initially allocated, a single memory
          block is created to hold the vector's control data and the
          array of elements.  These vectors cannot grow without
          reallocation (see discussion on embeddable vectors below).

        - Space efficient: The vector is structured as a pointer to an
          embedded vector.  This is the default layout.  It means that
          vectors occupy a single word of storage before initial
          allocation.  Vectors are allowed to grow (the internal
          pointer is reallocated but the main vector instance does not
          need to relocate).

   The type, allocation and layout are specified when the vector is
   declared.

   If you need to directly manipulate a vector, then the 'address'
   accessor will return the address of the start of the vector.  Also
   the 'space' predicate will tell you whether there is spare capacity
   in the vector.  You will not normally need to use these two functions.

   Notes on the different layout strategies

   * Embeddable vectors (vec<T, A, vl_embed>)
   
     These vectors are suitable to be embedded in other data
     structures so that they can be pre-allocated in a contiguous
     memory block.

     Embeddable vectors are implemented using the trailing array
     idiom, thus they are not resizeable without changing the address
     of the vector object itself.  This means you cannot have
     variables or fields of embeddable vector type -- always use a
     pointer to a vector.  The one exception is the final field of a
     structure, which could be a vector type.

     You will have to use the embedded_size & embedded_init calls to
     create such objects, and they will not be resizeable (so the
     'safe' allocation variants are not available).

     Properties of embeddable vectors:

          - The whole vector and control data are allocated in a single
            contiguous block.  It uses the trailing-vector idiom, so
            allocation must reserve enough space for all the elements
            in the vector plus its control data.
          - The vector cannot be re-allocated.
          - The vector cannot grow nor shrink.
          - No indirections needed for access/manipulation.
          - It requires 2 words of storage (prior to vector allocation).


   * Space efficient vector (vec<T, A, vl_ptr>)

     These vectors can grow dynamically and are allocated together
     with their control data.  They are suited to be included in data
     structures.  Prior to initial allocation, they only take a single
     word of storage.

     These vectors are implemented as a pointer to embeddable vectors.
     The semantics allow for this pointer to be NULL to represent
     empty vectors.  This way, empty vectors occupy minimal space in
     the structure containing them.

     Properties:

        - The whole vector and control data are allocated in a single
          contiguous block.
        - The whole vector may be re-allocated.
        - Vector data may grow and shrink.
        - Access and manipulation requires a pointer test and
          indirection.
        - It requires 1 word of storage (prior to vector allocation).

   An example of their use would be,

   struct my_struct {
     // A space-efficient vector of tree pointers in GC memory.
     vec<tree, va_gc, vl_ptr> v;
   };

   struct my_struct *s;

   if (s->v.length ()) { we have some contents }
   s->v.safe_push (decl); // append some decl onto the end
   for (ix = 0; s->v.iterate (ix, &elt); ix++)
     { do something with elt }
*/

/* Support function for statistics.  */
extern void dump_vec_loc_statistics (void);


/* Control data for vectors.  This contains the number of allocated
   and used slots inside a vector.  */

class vec_prefix
{
  /* FIXME - These fields should be private, but we need to cater to
             compilers that have stricter notions of PODness for types.  */
public:
  /* Memory allocation support routines in vec.c.  */
  void register_overhead_PRIVATE_ (size_t, const char *, int, const char *);
  void release_overhead_PRIVATE_ (void);
  static unsigned calculate_allocation_PRIVATE_ (vec_prefix *, unsigned, bool);

  /* Note that vec_prefix should be a base class for vec, but we use
     offsetof() on vector fields of tree structures (e.g.,
     tree_binfo::base_binfos), and offsetof only supports base types.

     To compensate, we make vec_prefix a field inside vec and make
     vec a friend class of vec_prefix so it can access its fields.  */
  template <typename, typename, typename> friend class vec;

  /* The allocator types also need access to our internals.  */
  friend struct va_gc;
  friend struct va_gc_atomic;
  friend struct va_heap;
  friend struct va_stack;

  unsigned alloc_PRIVATE_;
  unsigned num_PRIVATE_;
};

template<typename, typename, typename> class vec;

/* Valid vector layouts

   vl_embed     - Embeddable vector that uses the trailing array idiom.
   vl_ptr       - Space efficient vector that uses a pointer to an
                  embeddable vector.  */
struct vl_embed { };
struct vl_ptr { };


/* Types of supported allocations

   va_heap      - Allocation uses malloc/free.
   va_gc        - Allocation uses ggc_alloc.
   va_gc_atomic - Same as GC, but individual elements of the array
                  do not need to be marked during collection.
   va_stack     - Allocation uses alloca.  */

/* Allocator type for heap vectors.  */
struct va_heap
{
  /* Heap vectors are frequently regular instances, so use the vl_ptr
     layout for them.  */
  typedef vl_ptr default_layout;

  template<typename T>
  static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
                       CXX_MEM_STAT_INFO);

  template<typename T>
  static void release (vec<T, va_heap, vl_embed> *&);
};


/* Allocator for heap memory.  Ensure there are at least RESERVE free
   slots in V.  If EXACT is true, grow exactly, else grow
   exponentially.  As a special case, if the vector had not been
   allocated and and RESERVE is 0, no vector will be created.  */

template<typename T>
inline void
va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
                  MEM_STAT_DECL)
{
  unsigned alloc = vec_prefix::calculate_allocation_PRIVATE_ (
          v ? &v->pfx_PRIVATE_ : 0, reserve, exact);
  if (!alloc)
    {
      release (v);
      return;
    }

  if (GATHER_STATISTICS && v)
    v->pfx_PRIVATE_.release_overhead_PRIVATE_ ();

  size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
  unsigned nelem = v ? v->length () : 0;
  v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
  v->embedded_init (alloc, nelem);

  if (GATHER_STATISTICS)
    v->pfx_PRIVATE_.register_overhead_PRIVATE_ (size FINAL_PASS_MEM_STAT);
}


/* Free the heap space allocated for vector V.  */

template<typename T>
void
va_heap::release (vec<T, va_heap, vl_embed> *&v)
{
  if (v == NULL)
    return;

  if (GATHER_STATISTICS)
    v->pfx_PRIVATE_.release_overhead_PRIVATE_ ();
  ::free (v);
  v = NULL;
}


/* Allocator type for GC vectors.  Notice that we need the structure
   declaration even if GC is not enabled.  */

struct va_gc
{
  /* Use vl_embed as the default layout for GC vectors.  Due to GTY
     limitations, GC vectors must always be pointers, so it is more
     efficient to use a pointer to the vl_embed layout, rather than
     using a pointer to a pointer as would be the case with vl_ptr.  */
  typedef vl_embed default_layout;

  template<typename T, typename A>
  static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
                       CXX_MEM_STAT_INFO);

  template<typename T, typename A>
  static void release (vec<T, A, vl_embed> *&v) { v = NULL; }
};


/* Allocator for GC memory.  Ensure there are at least RESERVE free
   slots in V.  If EXACT is true, grow exactly, else grow
   exponentially.  As a special case, if the vector had not been
   allocated and and RESERVE is 0, no vector will be created.  */

template<typename T, typename A>
void
va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
                MEM_STAT_DECL)
{
  unsigned alloc = vec_prefix::calculate_allocation_PRIVATE_ (
          v ? &v->pfx_PRIVATE_ : 0, reserve, exact);
  if (!alloc)
    {
      ::ggc_free (v);
      v = NULL;
      return;
    }

  /* Calculate the amount of space we want.  */
  size_t size = vec<T, A, vl_embed>::embedded_size (alloc);

  /* Ask the allocator how much space it will really give us.  */
  size = ggc_round_alloc_size (size);

  /* Adjust the number of slots accordingly.  */
  size_t vec_offset = sizeof (vec_prefix);
  size_t elt_size = sizeof (T);
  alloc = (size - vec_offset) / elt_size;

  /* And finally, recalculate the amount of space we ask for.  */
  size = vec_offset + alloc * elt_size;

  unsigned nelem = v ? v->length () : 0;
  v = static_cast <vec<T, A, vl_embed> *> (ggc_realloc_stat (v, size));
  v->embedded_init (alloc, nelem);
}


/* Allocator type for GC vectors.  This is for vectors of types
   atomics w.r.t. collection, so allocation and deallocation is
   completely inherited from va_gc.  */
struct va_gc_atomic : va_gc
{
};


/* Allocator type for stack vectors.  */
struct va_stack
{
  /* Use vl_ptr as the default layout for stack vectors.  */
  typedef vl_ptr default_layout;

  template<typename T>
  static void alloc (vec<T, va_stack, vl_ptr>&, unsigned,
                     vec<T, va_stack, vl_embed> *);

  template <typename T>
  static void reserve (vec<T, va_stack, vl_embed> *&, unsigned, bool
                       CXX_MEM_STAT_INFO);

  template <typename T>
  static void release (vec<T, va_stack, vl_embed> *&);
};

/* Helper functions to keep track of vectors allocated on the stack.  */
void register_stack_vec (void *);
int stack_vec_register_index (void *);
void unregister_stack_vec (unsigned);

/* Allocate a vector V which uses alloca for the initial allocation.
   SPACE is space allocated using alloca.  NELEMS is the number of
   entries allocated.  */

template<typename T>
void
va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems,
                 vec<T, va_stack, vl_embed> *space)
{
  v.vec_PRIVATE_ = space;
  register_stack_vec (static_cast<void *> (v.vec_PRIVATE_));
  v.vec_PRIVATE_->embedded_init (nelems, 0);
}


/* Reserve NELEMS slots for a vector initially allocated on the stack.
   When this happens, we switch back to heap allocation.  We remove
   the vector from stack_vecs, if it is there, since we no longer need
   to avoid freeing it.  If EXACT is true, grow exactly, otherwise
   grow exponentially.  */

template<typename T>
void
va_stack::reserve (vec<T, va_stack, vl_embed> *&v, unsigned nelems, bool exact
                   MEM_STAT_DECL)
{
  int ix = stack_vec_register_index (static_cast<void *> (v));
  if (ix >= 0)
    unregister_stack_vec (ix);
  else
    {
      /* V is already on the heap.  */
      va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v),
                        nelems, exact);
      return;
    }

  /* Move VEC_ to the heap.  */
  nelems += v->pfx_PRIVATE_.num_PRIVATE_;
  vec<T, va_stack, vl_embed> *oldvec = v;
  v = NULL;
  va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&>(v), nelems,
                    exact);
  if (v && oldvec)
    {
      v->pfx_PRIVATE_.num_PRIVATE_ = oldvec->length ();
      memcpy (v->data_PRIVATE_,
              oldvec->data_PRIVATE_,
              oldvec->length () * sizeof (T));
    }
}


/* Free a vector allocated on the stack.  Don't actually free it if we
   find it in the hash table.  */

template<typename T>
void
va_stack::release (vec<T, va_stack, vl_embed> *&v)
{
  if (v == NULL)
    return;

  int ix = stack_vec_register_index (static_cast<void *> (v));
  if (ix >= 0)
    {
      unregister_stack_vec (ix);
      v = NULL;
    }
  else
    {
      /* The vector was not on the list of vectors allocated on the stack, so it
         must be allocated on the heap.  */
      va_heap::release (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v));
    }
}


/* Generic vector template.  Default values for A and L indicate the
   most commonly used strategies.

   FIXME - Ideally, they would all be vl_ptr to encourage using regular
           instances for vectors, but the existing GTY machinery is limited
           in that it can only deal with GC objects that are pointers
           themselves.

           This means that vector operations that need to deal with
           potentially NULL pointers, must be provided as free
           functions (see the vec_safe_* functions above).  */
template<typename T,
         typename A = va_heap,
         typename L = typename A::default_layout>
class GTY((user)) vec
{
};


/* Embeddable vector.  These vectors are suitable to be embedded
   in other data structures so that they can be pre-allocated in a
   contiguous memory block.

   Embeddable vectors are implemented using the trailing array idiom,
   thus they are not resizeable without changing the address of the
   vector object itself.  This means you cannot have variables or
   fields of embeddable vector type -- always use a pointer to a
   vector.  The one exception is the final field of a structure, which
   could be a vector type.

   You will have to use the embedded_size & embedded_init calls to
   create such objects, and they will not be resizeable (so the 'safe'
   allocation variants are not available).

   Properties:

        - The whole vector and control data are allocated in a single
          contiguous block.  It uses the trailing-vector idiom, so
          allocation must reserve enough space for all the elements
          in the vector plus its control data.
        - The vector cannot be re-allocated.
        - The vector cannot grow nor shrink.
        - No indirections needed for access/manipulation.
        - It requires 2 words of storage (prior to vector allocation).  */

template<typename T, typename A>
class GTY((user)) vec<T, A, vl_embed>
{
public:
  unsigned allocated (void) const { return pfx_PRIVATE_.alloc_PRIVATE_; }
  unsigned length (void) const { return pfx_PRIVATE_.num_PRIVATE_; }
  bool is_empty (void) const { return pfx_PRIVATE_.num_PRIVATE_ == 0; }
  T *address (void) { return data_PRIVATE_; }
  const T *address (void) const { return data_PRIVATE_; }
  const T &operator[] (unsigned) const;
  T &operator[] (unsigned);
  T &last (void);
  bool space (unsigned) const;
  bool iterate (unsigned, T *) const;
  bool iterate (unsigned, T **) const;
  vec *copy (ALONE_MEM_STAT_DECL) const;
  void splice (vec &);
  void splice (vec *src);
  T *quick_push (const T &);
  T &pop (void);
  void truncate (unsigned);
  void quick_insert (unsigned, const T &);
  void ordered_remove (unsigned);
  void unordered_remove (unsigned);
  void block_remove (unsigned, unsigned);
  void qsort (int (*) (const void *, const void *));
  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
  static size_t embedded_size (unsigned);
  void embedded_init (unsigned, unsigned = 0);
  void quick_grow (unsigned len);
  void quick_grow_cleared (unsigned len);

  /* vec class can access our internal data and functions.  */
  template <typename, typename, typename> friend class vec;

  /* The allocator types also need access to our internals.  */
  friend struct va_gc;
  friend struct va_gc_atomic;
  friend struct va_heap;
  friend struct va_stack;

  /* FIXME - These fields should be private, but we need to cater to
             compilers that have stricter notions of PODness for types.  */
  vec_prefix pfx_PRIVATE_;
  T data_PRIVATE_[1];
};


/* Convenience wrapper functions to use when dealing with pointers to
   embedded vectors.  Some functionality for these vectors must be
   provided via free functions for these reasons:

        1- The pointer may be NULL (e.g., before initial allocation).

        2- When the vector needs to grow, it must be reallocated, so
           the pointer will change its value.

   Because of limitations with the current GC machinery, all vectors
   in GC memory *must* be pointers.  */


/* If V contains no room for NELEMS elements, return false. Otherwise,
   return true.  */
template<typename T, typename A>
inline bool
vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
{
  return v ? v->space (nelems) : nelems == 0;
}


/* If V is NULL, return 0.  Otherwise, return V->length().  */
template<typename T, typename A>
inline unsigned
vec_safe_length (const vec<T, A, vl_embed> *v)
{
  return v ? v->length () : 0;
}


/* If V is NULL, return NULL.  Otherwise, return V->address().  */
template<typename T, typename A>
inline T *
vec_safe_address (vec<T, A, vl_embed> *v)
{
  return v ? v->address () : NULL;
}


/* If V is NULL, return true.  Otherwise, return V->is_empty().  */
template<typename T, typename A>
inline bool
vec_safe_is_empty (vec<T, A, vl_embed> *v)
{
  return v ? v->is_empty () : true;
}


/* If V does not have space for NELEMS elements, call
   V->reserve(NELEMS, EXACT).  */
template<typename T, typename A>
inline bool
vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
                  MEM_STAT_DECL)
{
  bool extend = nelems ? !vec_safe_space (v, nelems) : false;
  if (extend)
    A::reserve (v, nelems, exact PASS_MEM_STAT);
  return extend;
}

template<typename T, typename A>
inline bool
vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems MEM_STAT_DECL)
{
  return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
}


/* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
   is 0, V is initialized to NULL.  */

template<typename T, typename A>
inline void
vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems MEM_STAT_DECL)
{
  v = NULL;
  vec_safe_reserve (v, nelems);
}


/* Free the GC memory allocated by vector V and set it to NULL.  */

template<typename T, typename A>
inline void
vec_free (vec<T, A, vl_embed> *&v)
{
  A::release (v);
}


/* Grow V to length LEN.  Allocate it, if necessary.  */
template<typename T, typename A>
inline void
vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len MEM_STAT_DECL)
{
  unsigned oldlen = vec_safe_length (v);
  gcc_checking_assert (len >= oldlen);
  vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
  v->quick_grow (len PASS_MEM_STAT);
}


/* If V is NULL, allocate it.  Call V->safe_grow_cleared(LEN).  */
template<typename T, typename A>
inline void
vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len MEM_STAT_DECL)
{
  unsigned oldlen = vec_safe_length (v);
  vec_safe_grow (v, len PASS_MEM_STAT);
  memset (&(v->address()[oldlen]), 0, sizeof (T) * (len - oldlen));
}


/* If V is NULL return false, otherwise return V->iterate(IX, PTR).  */
template<typename T, typename A>
inline bool
vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
{
  if (v)
    return v->iterate (ix, ptr);
  else
    {
      *ptr = 0;
      return false;
    }
}

template<typename T, typename A>
inline bool
vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
{
  if (v)
    return v->iterate (ix, ptr);
  else
    {
      *ptr = 0;
      return false;
    }
}


/* If V has no room for one more element, reallocate it.  Then call
   V->quick_push(OBJ).  */
template<typename T, typename A>
inline T *
vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj MEM_STAT_DECL)
{
  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
  return v->quick_push (obj PASS_MEM_STAT);
}


/* if V has no room for one more element, reallocate it.  Then call
   V->quick_insert(IX, OBJ).  */
template<typename T, typename A>
inline void
vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
                 MEM_STAT_DECL)
{
  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
  v->quick_insert (ix, obj);
}


/* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
template<typename T, typename A>
inline void
vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
{
  if (v)
    v->truncate (size);
}


/* If SRC is not NULL, return a pointer to a copy of it.  */
template<typename T, typename A>
inline vec<T, A, vl_embed> *
vec_safe_copy (vec<T, A, vl_embed> *src)
{
  return src ? src->copy () : NULL;
}

/* Copy the elements from SRC to the end of DST as if by memcpy.
   Reallocate DST, if necessary.  */
template<typename T, typename A>
inline void
vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src
                 MEM_STAT_DECL)
{
  unsigned src_len = vec_safe_length (src);
  if (src_len)
    {
      vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len);
      dst->splice (*src);
    }
}


/* Index into vector.  Return the IX'th element.  IX must be in the
   domain of the vector.  */

template<typename T, typename A>
inline const T &
vec<T, A, vl_embed>::operator[] (unsigned ix) const
{
  gcc_checking_assert (ix < pfx_PRIVATE_.num_PRIVATE_);
  return data_PRIVATE_[ix];
}

template<typename T, typename A>
inline T &
vec<T, A, vl_embed>::operator[] (unsigned ix)
{
  gcc_checking_assert (ix < pfx_PRIVATE_.num_PRIVATE_);
  return data_PRIVATE_[ix];
}


/* Get the final element of the vector, which must not be empty.  */

template<typename T, typename A>
inline T &
vec<T, A, vl_embed>::last (void)
{
  gcc_checking_assert (pfx_PRIVATE_.num_PRIVATE_ > 0);
  return (*this)[pfx_PRIVATE_.num_PRIVATE_ - 1];
}


/* If this vector has space for NELEMS additional entries, return
   true.  You usually only need to use this if you are doing your
   own vector reallocation, for instance on an embedded vector.  This
   returns true in exactly the same circumstances that vec::reserve
   will.  */

template<typename T, typename A>
inline bool
vec<T, A, vl_embed>::space (unsigned nelems) const
{
  return pfx_PRIVATE_.alloc_PRIVATE_ - pfx_PRIVATE_.num_PRIVATE_ >= nelems;
}


/* Return iteration condition and update PTR to point to the IX'th
   element of this vector.  Use this to iterate over the elements of a
   vector as follows,

     for (ix = 0; vec<T, A>::iterate(v, ix, &ptr); ix++)
       continue;  */

template<typename T, typename A>
inline bool
vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
{
  if (ix < pfx_PRIVATE_.num_PRIVATE_)
    {
      *ptr = data_PRIVATE_[ix];
      return true;
    }
  else
    {
      *ptr = 0;
      return false;
    }
}


/* Return iteration condition and update *PTR to point to the
   IX'th element of this vector.  Use this to iterate over the
   elements of a vector as follows,

     for (ix = 0; v->iterate(ix, &ptr); ix++)
       continue;

   This variant is for vectors of objects.  */

template<typename T, typename A>
inline bool
vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
{
  if (ix < pfx_PRIVATE_.num_PRIVATE_)
    {
      *ptr = CONST_CAST (T *, &data_PRIVATE_[ix]);
      return true;
    }
  else
    {
      *ptr = 0;
      return false;
    }
}


/* Return a pointer to a copy of this vector.  */

template<typename T, typename A>
inline vec<T, A, vl_embed> *
vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
{
  vec<T, A, vl_embed> *new_vec = NULL;
  unsigned len = length ();
  if (len)
    {
      vec_alloc (new_vec, len PASS_MEM_STAT);
      new_vec->embedded_init (len, len);
      memcpy (new_vec->address(), data_PRIVATE_, sizeof (T) * len);
    }
  return new_vec;
}


/* Copy the elements from SRC to the end of this vector as if by memcpy.
   The vector must have sufficient headroom available.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src)
{
  unsigned len = src.length();
  if (len)
    {
      gcc_checking_assert (space (len));
      memcpy (address() + length(), src.address(), len * sizeof (T));
      pfx_PRIVATE_.num_PRIVATE_ += len;
    }
}

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src)
{
  if (src)
    splice (*src);
}


/* Push OBJ (a new element) onto the end of the vector.  There must be
   sufficient space in the vector.  Return a pointer to the slot
   where OBJ was inserted.  */

template<typename T, typename A>
inline T *
vec<T, A, vl_embed>::quick_push (const T &obj)
{
  gcc_checking_assert (space (1));
  T *slot = &data_PRIVATE_[pfx_PRIVATE_.num_PRIVATE_++];
  *slot = obj;
  return slot;
}


/* Pop and return the last element off the end of the vector.  */

template<typename T, typename A>
inline T &
vec<T, A, vl_embed>::pop (void)
{
  gcc_checking_assert (length () > 0);
  return data_PRIVATE_[--pfx_PRIVATE_.num_PRIVATE_];
}


/* Set the length of the vector to SIZE.  The new length must be less
   than or equal to the current length.  This is an O(1) operation.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::truncate (unsigned size)
{
  gcc_checking_assert (length () >= size);
  pfx_PRIVATE_.num_PRIVATE_ = size;
}


/* Insert an element, OBJ, at the IXth position of this vector.  There
   must be sufficient space.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
{
  gcc_checking_assert (length () < allocated ());
  gcc_checking_assert (ix <= length ());
  T *slot = &data_PRIVATE_[ix];
  memmove (slot + 1, slot, (pfx_PRIVATE_.num_PRIVATE_++ - ix) * sizeof (T));
  *slot = obj;
}


/* Remove an element from the IXth position of this vector.  Ordering of
   remaining elements is preserved.  This is an O(N) operation due to
   memmove.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::ordered_remove (unsigned ix)
{
  gcc_checking_assert (ix < length());
  T *slot = &data_PRIVATE_[ix];
  memmove (slot, slot + 1, (--pfx_PRIVATE_.num_PRIVATE_ - ix) * sizeof (T));
}


/* Remove an element from the IXth position of this vector.  Ordering of
   remaining elements is destroyed.  This is an O(1) operation.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::unordered_remove (unsigned ix)
{
  gcc_checking_assert (ix < length());
  data_PRIVATE_[ix] = data_PRIVATE_[--pfx_PRIVATE_.num_PRIVATE_];
}


/* Remove LEN elements starting at the IXth.  Ordering is retained.
   This is an O(N) operation due to memmove.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
{
  gcc_checking_assert (ix + len <= length());
  T *slot = &data_PRIVATE_[ix];
  pfx_PRIVATE_.num_PRIVATE_ -= len;
  memmove (slot, slot + len, (pfx_PRIVATE_.num_PRIVATE_ - ix) * sizeof (T));
}


/* Sort the contents of this vector with qsort.  CMP is the comparison
   function to pass to qsort.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
{
  ::qsort (address(), length(), sizeof (T), cmp);
}


/* Find and return the first position in which OBJ could be inserted
   without changing the ordering of this vector.  LESSTHAN is a
   function that returns true if the first argument is strictly less
   than the second.  */

template<typename T, typename A>
unsigned
vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
  const
{
  unsigned int len = length ();
  unsigned int half, middle;
  unsigned int first = 0;
  while (len > 0)
    {
      half = len / 2;
      middle = first;
      middle += half;
      T middle_elem = (*this)[middle];
      if (lessthan (middle_elem, obj))
        {
          first = middle;
          ++first;
          len = len - half - 1;
        }
      else
        len = half;
    }
  return first;
}


/* Return the number of bytes needed to embed an instance of an
   embeddable vec inside another data structure.

   Use these methods to determine the required size and initialization
   of a vector V of type T embedded within another structure (as the
   final member):

   size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
   void v->embedded_init(unsigned alloc, unsigned num);

   These allow the caller to perform the memory allocation.  */

template<typename T, typename A>
inline size_t
vec<T, A, vl_embed>::embedded_size (unsigned alloc)
{
  typedef vec<T, A, vl_embed> vec_embedded;
  return offsetof (vec_embedded, data_PRIVATE_) + alloc * sizeof (T);
}


/* Initialize the vector to contain room for ALLOC elements and
   NUM active elements.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num)
{
  pfx_PRIVATE_.alloc_PRIVATE_ = alloc;
  pfx_PRIVATE_.num_PRIVATE_ = num;
}


/* Grow the vector to a specific length.  LEN must be as long or longer than
   the current length.  The new elements are uninitialized.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::quick_grow (unsigned len)
{
  gcc_checking_assert (length () <= len && len <= pfx_PRIVATE_.alloc_PRIVATE_);
  pfx_PRIVATE_.num_PRIVATE_ = len;
}


/* Grow the vector to a specific length.  LEN must be as long or longer than
   the current length.  The new elements are initialized to zero.  */

template<typename T, typename A>
inline void
vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
{
  unsigned oldlen = length ();
  quick_grow (len);
  memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
}


/* Garbage collection support for vec<T, A, vl_embed>.  */

template<typename T>
void
gt_ggc_mx (vec<T, va_gc> *v)
{
  extern void gt_ggc_mx (T &);
  for (unsigned i = 0; i < v->length (); i++)
    gt_ggc_mx ((*v)[i]);
}

template<typename T>
void
gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
{
  /* Nothing to do.  Vectors of atomic types wrt GC do not need to
     be traversed.  */
}


/* PCH support for vec<T, A, vl_embed>.  */

template<typename T, typename A>
void
gt_pch_nx (vec<T, A, vl_embed> *v)
{
  extern void gt_pch_nx (T &);
  for (unsigned i = 0; i < v->length (); i++)
    gt_pch_nx ((*v)[i]);
}

template<typename T, typename A>
void
gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
{
  for (unsigned i = 0; i < v->length (); i++)
    op (&((*v)[i]), cookie);
}

template<typename T, typename A>
void
gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
{
  extern void gt_pch_nx (T *, gt_pointer_operator, void *);
  for (unsigned i = 0; i < v->length (); i++)
    gt_pch_nx (&((*v)[i]), op, cookie);
}


/* Space efficient vector.  These vectors can grow dynamically and are
   allocated together with their control data.  They are suited to be
   included in data structures.  Prior to initial allocation, they
   only take a single word of storage.

   These vectors are implemented as a pointer to an embeddable vector.
   The semantics allow for this pointer to be NULL to represent empty
   vectors.  This way, empty vectors occupy minimal space in the
   structure containing them.

   Properties:

        - The whole vector and control data are allocated in a single
          contiguous block.
        - The whole vector may be re-allocated.
        - Vector data may grow and shrink.
        - Access and manipulation requires a pointer test and
          indirection.
        - It requires 1 word of storage (prior to vector allocation).


   Limitations:

   These vectors must be PODs because they are stored in unions.
   (http://en.wikipedia.org/wiki/Plain_old_data_structures).
   As long as we use C++03, we cannot have constructors nor
   destructors in classes that are stored in unions.  */

template<typename T, typename A>
class vec<T, A, vl_ptr>
{
public:
  /* Memory allocation and deallocation for the embedded vector.
     Needed because we cannot have proper ctors/dtors defined.  */
  void create (unsigned nelems CXX_MEM_STAT_INFO);
  void release (void);

  /* Vector operations.  */
  bool exists (void) const
  { return vec_PRIVATE_ != NULL; }

  bool is_empty (void) const
  { return vec_PRIVATE_ ? vec_PRIVATE_->is_empty() : true; }

  unsigned length (void) const
  { return vec_PRIVATE_ ? vec_PRIVATE_->length() : 0; }

  T *address (void)
  { return vec_PRIVATE_ ? vec_PRIVATE_->data_PRIVATE_ : NULL; }

  const T *address (void) const
  { return vec_PRIVATE_ ? vec_PRIVATE_->data_PRIVATE_ : NULL; }

  const T &operator[] (unsigned ix) const
  { return (*vec_PRIVATE_)[ix]; }

  bool operator!=(const vec &other) const
  { return !(*this == other); }

  bool operator==(const vec &other) const
  { return address() == other.address(); }

  T &operator[] (unsigned ix)
  { return (*vec_PRIVATE_)[ix]; }

  T &last (void)
  { return vec_PRIVATE_->last(); }

  bool space (int nelems) const
  { return vec_PRIVATE_ ? vec_PRIVATE_->space (nelems) : nelems == 0; }

  bool iterate (unsigned ix, T *p) const;
  bool iterate (unsigned ix, T **p) const;
  vec copy (ALONE_CXX_MEM_STAT_INFO) const;
  bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
  bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
  void splice (vec &);
  void safe_splice (vec & CXX_MEM_STAT_INFO);
  T *quick_push (const T &);
  T *safe_push (const T &CXX_MEM_STAT_INFO);
  T &pop (void);
  void truncate (unsigned);
  void safe_grow (unsigned CXX_MEM_STAT_INFO);
  void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
  void quick_grow (unsigned);
  void quick_grow_cleared (unsigned);
  void quick_insert (unsigned, const T &);
  void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
  void ordered_remove (unsigned);
  void unordered_remove (unsigned);
  void block_remove (unsigned, unsigned);
  void qsort (int (*) (const void *, const void *));
  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;

  template<typename T1>
  friend void va_stack::alloc(vec<T1, va_stack, vl_ptr>&, unsigned,
                              vec<T1, va_stack, vl_embed> *);

  /* FIXME - This field should be private, but we need to cater to
             compilers that have stricter notions of PODness for types.  */
  vec<T, A, vl_embed> *vec_PRIVATE_;
};


/* Empty specialization for GC allocation.  This will prevent GC
   vectors from using the vl_ptr layout.  FIXME: This is needed to
   circumvent limitations in the GTY machinery.  */

template<typename T>
class vec<T, va_gc, vl_ptr>
{
};


/* Allocate heap memory for pointer V and create the internal vector
   with space for NELEMS elements.  If NELEMS is 0, the internal
   vector is initialized to empty.  */

template<typename T>
inline void
vec_alloc (vec<T> *&v, unsigned nelems MEM_STAT_DECL)
{
  v = new vec<T>;
  v->create (nelems PASS_MEM_STAT);
}


/* Conditionally allocate heap memory for VEC and its internal vector.  */

template<typename T>
inline void
vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems MEM_STAT_DECL)
{
  if (!vec)
    vec_alloc (vec, nelems PASS_MEM_STAT);
}


/* Free the heap memory allocated by vector V and set it to NULL.  */

template<typename T>
inline void
vec_free (vec<T> *&v)
{
  if (v == NULL)
    return;

  v->release ();
  delete v;
  v = NULL;
}


/* Allocate a new stack vector with space for exactly NELEMS objects.
   If NELEMS is zero, NO vector is created.

   For the stack allocator, no memory is really allocated.  The vector
   is initialized to be at address SPACE and contain NELEMS slots.
   Memory allocation actually occurs in the expansion of VEC_alloc.

   Usage notes:

   * This does not allocate an instance of vec<T, A>.  It allocates the
     actual vector of elements (i.e., vec<T, A, vl_embed>) inside a
     vec<T, A> instance.

   * This allocator must always be a macro:

     We support a vector which starts out with space on the stack and
     switches to heap space when forced to reallocate.  This works a
     little differently.  In the case of stack vectors, vec_alloc will
     expand to a call to vec_alloc_1 that calls XALLOCAVAR to request
     the initial allocation.  This uses alloca to get the initial
     space. Since alloca can not be usefully called in an inline
     function, vec_alloc must always be a macro.

     Important limitations of stack vectors:

     - Only the initial allocation will be made using alloca, so pass
       a reasonable estimate that doesn't use too much stack space;
       don't pass zero.

     - Don't return a stack-allocated vector from the function which
       allocated it.  */

#define vec_stack_alloc(T,V,N)                                          \
  do {                                                                  \
    typedef vec<T, va_stack, vl_embed> stackv;                          \
    va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\
  } while (0)


/* Return iteration condition and update PTR to point to the IX'th
   element of this vector.  Use this to iterate over the elements of a
   vector as follows,

     for (ix = 0; v.iterate(ix, &ptr); ix++)
       continue;  */

template<typename T, typename A>
inline bool
vec<T, A, vl_ptr>::iterate (unsigned ix, T *ptr) const
{
  if (vec_PRIVATE_)
    return vec_PRIVATE_->iterate (ix, ptr);
  else
    {
      *ptr = 0;
      return false;
    }
}


/* Return iteration condition and update *PTR to point to the
   IX'th element of this vector.  Use this to iterate over the
   elements of a vector as follows,

     for (ix = 0; v->iterate(ix, &ptr); ix++)
       continue;

   This variant is for vectors of objects.  */

template<typename T, typename A>
inline bool
vec<T, A, vl_ptr>::iterate (unsigned ix, T **ptr) const
{
  if (vec_PRIVATE_)
    return vec_PRIVATE_->iterate (ix, ptr);
  else
    {
      *ptr = 0;
      return false;
    }
}


/* Convenience macro for forward iteration.  */
#define FOR_EACH_VEC_ELT(V, I, P)                       \
  for (I = 0; (V).iterate ((I), &(P)); ++(I))

#define FOR_EACH_VEC_SAFE_ELT(V, I, P)                  \
  for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))

/* Likewise, but start from FROM rather than 0.  */
#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)            \
  for (I = (FROM); (V).iterate ((I), &(P)); ++(I))

/* Convenience macro for reverse iteration.  */
#define FOR_EACH_VEC_ELT_REVERSE(V, I, P)               \
  for (I = (V).length () - 1;                           \
       (V).iterate ((I), &(P));                         \
       (I)--)

#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)          \
  for (I = vec_safe_length (V) - 1;                     \
       vec_safe_iterate ((V), (I), &(P));       \
       (I)--)


/* Return a copy of this vector.  */

template<typename T, typename A>
inline vec<T, A, vl_ptr>
vec<T, A, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
{
  vec<T, A, vl_ptr> new_vec = vec<T, A, vl_ptr>();
  if (length ())
    new_vec.vec_PRIVATE_ = vec_PRIVATE_->copy ();
  return new_vec;
}


/* Ensure that the vector has at least RESERVE slots available (if
   EXACT is false), or exactly RESERVE slots available (if EXACT is
   true).

   This may create additional headroom if EXACT is false.

   Note that this can cause the embedded vector to be reallocated.
   Returns true iff reallocation actually occurred.  */

template<typename T, typename A>
inline bool
vec<T, A, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
{
  bool extend = nelems ? !space (nelems) : false;
  if (extend)
    A::reserve (vec_PRIVATE_, nelems, exact PASS_MEM_STAT);
  return extend;
}


/* Ensure that this vector has exactly NELEMS slots available.  This
   will not create additional headroom.  Note this can cause the
   embedded vector to be reallocated.  Returns true iff reallocation
   actually occurred.  */

template<typename T, typename A>
inline bool
vec<T, A, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
{
  return reserve (nelems, true PASS_MEM_STAT);
}


/* Create the internal vector and reserve NELEMS for it.  This is
   exactly like vec::reserve, but the internal vector is
   unconditionally allocated from scratch.  The old one, if it
   existed, is lost.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
{
  vec_PRIVATE_ = NULL;
  if (nelems > 0)
    reserve_exact (nelems PASS_MEM_STAT);
}


/* Free the memory occupied by the embedded vector.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::release (void)
{
  if (vec_PRIVATE_)
    A::release (vec_PRIVATE_);
}


/* Copy the elements from SRC to the end of this vector as if by memcpy.
   SRC and this vector must be allocated with the same memory
   allocation mechanism. This vector is assumed to have sufficient
   headroom available.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::splice (vec<T, A, vl_ptr> &src)
{
  if (src.vec_PRIVATE_)
    vec_PRIVATE_->splice (*(src.vec_PRIVATE_));
}


/* Copy the elements in SRC to the end of this vector as if by memcpy.
   SRC and this vector must be allocated with the same mechanism.
   If there is not enough headroom in this vector, it will be reallocated
   as needed.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::safe_splice (vec<T, A, vl_ptr> &src MEM_STAT_DECL)
{
  if (src.length())
    {
      reserve_exact (src.length());
      splice (src);
    }
}


/* Push OBJ (a new element) onto the end of the vector.  There must be
   sufficient space in the vector.  Return a pointer to the slot
   where OBJ was inserted.  */

template<typename T, typename A>
inline T *
vec<T, A, vl_ptr>::quick_push (const T &obj)
{
  return vec_PRIVATE_->quick_push (obj);
}


/* Push a new element OBJ onto the end of this vector.  Reallocates
   the embedded vector, if needed.  Return a pointer to the slot where
   OBJ was inserted.  */

template<typename T, typename A>
inline T *
vec<T, A, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
{
  reserve (1, false PASS_MEM_STAT);
  return quick_push (obj);
}


/* Pop and return the last element off the end of the vector.  */

template<typename T, typename A>
inline T &
vec<T, A, vl_ptr>::pop (void)
{
  return vec_PRIVATE_->pop ();
}


/* Set the length of the vector to LEN.  The new length must be less
   than or equal to the current length.  This is an O(1) operation.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::truncate (unsigned size)
{
  if (vec_PRIVATE_)
    vec_PRIVATE_->truncate (size);
  else
    gcc_checking_assert (size == 0);
}


/* Grow the vector to a specific length.  LEN must be as long or
   longer than the current length.  The new elements are
   uninitialized.  Reallocate the internal vector, if needed.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
{
  unsigned oldlen = length ();
  gcc_checking_assert (oldlen <= len);
  reserve_exact (len - oldlen PASS_MEM_STAT);
  vec_PRIVATE_->quick_grow (len);
}


/* Grow the embedded vector to a specific length.  LEN must be as
   long or longer than the current length.  The new elements are
   initialized to zero.  Reallocate the internal vector, if needed.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
{
  unsigned oldlen = length ();
  safe_grow (len PASS_MEM_STAT);
  memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
}


/* Same as vec::safe_grow but without reallocation of the internal vector.
   If the vector cannot be extended, a runtime assertion will be triggered.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::quick_grow (unsigned len)
{
  gcc_checking_assert (vec_PRIVATE_);
  vec_PRIVATE_->quick_grow (len);
}


/* Same as vec::quick_grow_cleared but without reallocation of the
   internal vector. If the vector cannot be extended, a runtime
   assertion will be triggered.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::quick_grow_cleared (unsigned len)
{
  gcc_checking_assert (vec_PRIVATE_);
  vec_PRIVATE_->quick_grow_cleared (len);
}


/* Insert an element, OBJ, at the IXth position of this vector.  There
   must be sufficient space.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::quick_insert (unsigned ix, const T &obj)
{
  vec_PRIVATE_->quick_insert (ix, obj);
}


/* Insert an element, OBJ, at the IXth position of the vector.
   Reallocate the embedded vector, if necessary.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
{
  reserve (1, false PASS_MEM_STAT);
  quick_insert (ix, obj);
}


/* Remove an element from the IXth position of this vector.  Ordering of
   remaining elements is preserved.  This is an O(N) operation due to
   a memmove.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::ordered_remove (unsigned ix)
{
  vec_PRIVATE_->ordered_remove (ix);
}


/* Remove an element from the IXth position of this vector.  Ordering
   of remaining elements is destroyed.  This is an O(1) operation.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::unordered_remove (unsigned ix)
{
  vec_PRIVATE_->unordered_remove (ix);
}


/* Remove LEN elements starting at the IXth.  Ordering is retained.
   This is an O(N) operation due to memmove.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::block_remove (unsigned ix, unsigned len)
{
  vec_PRIVATE_->block_remove (ix, len);
}


/* Sort the contents of this vector with qsort.  CMP is the comparison
   function to pass to qsort.  */

template<typename T, typename A>
inline void
vec<T, A, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
{
  if (vec_PRIVATE_)
    vec_PRIVATE_->qsort (cmp);
}


/* Find and return the first position in which OBJ could be inserted
   without changing the ordering of this vector.  LESSTHAN is a
   function that returns true if the first argument is strictly less
   than the second.  */

template<typename T, typename A>
inline unsigned
vec<T, A, vl_ptr>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
    const
{
  return vec_PRIVATE_ ? vec_PRIVATE_->lower_bound (obj, lessthan) : 0;
}

#endif // GCC_VEC_H