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