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