source: arduino-1-6-7/trunk/fuentes/arduino-ide-amd64/hardware/tools/avr/lib/gcc/avr/4.8.1/plugin/include/vec.h @ 46

Last change on this file since 46 was 46, checked in by jrpelegrina, 4 years ago

First release to Xenial

File size: 48.6 KB
Line 
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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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.  */
208extern 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
214struct 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
242template<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.  */
249struct vl_embed { };
250struct 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.  */
262struct 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
282template<typename T>
283inline void
284va_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
310template<typename T>
311void
312va_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
327struct 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
349template<typename T, typename A>
350void
351va_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.  */
387struct va_gc_atomic : va_gc
388{
389};
390
391
392/* Allocator type for stack vectors.  */
393struct 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.  */
411void register_stack_vec (void *);
412int stack_vec_register_index (void *);
413void 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
419template<typename T>
420void
421va_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
436template<typename T>
437void
438va_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
471template<typename T>
472void
473va_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).  */
504template<typename T,
505         typename A = va_heap,
506         typename L = typename A::default_layout>
507struct 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.  */
515struct vnull
516{
517  template <typename T, typename A, typename L>
518  operator vec<T, A, L> () { return vec<T, A, L>(); }
519};
520extern 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
549template<typename T, typename A>
550struct GTY((user)) vec<T, A, vl_embed>
551{
552public:
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.  */
612template<typename T, typename A>
613inline bool
614vec_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().  */
621template<typename T, typename A>
622inline unsigned
623vec_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().  */
630template<typename T, typename A>
631inline T *
632vec_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().  */
639template<typename T, typename A>
640inline bool
641vec_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).  */
649template<typename T, typename A>
650inline bool
651vec_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
660template<typename T, typename A>
661inline bool
662vec_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
672template<typename T, typename A>
673inline void
674vec_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
683template<typename T, typename A>
684inline void
685vec_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.  */
692template<typename T, typename A>
693inline void
694vec_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).  */
704template<typename T, typename A>
705inline void
706vec_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).  */
715template<typename T, typename A>
716inline bool
717vec_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
728template<typename T, typename A>
729inline bool
730vec_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).  */
744template<typename T, typename A>
745inline T *
746vec_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).  */
755template<typename T, typename A>
756inline void
757vec_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).  */
766template<typename T, typename A>
767inline void
768vec_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.  */
776template<typename T, typename A>
777inline vec<T, A, vl_embed> *
778vec_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.  */
785template<typename T, typename A>
786inline void
787vec_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
803template<typename T, typename A>
804inline const T &
805vec<T, A, vl_embed>::operator[] (unsigned ix) const
806{
807  gcc_checking_assert (ix < vecpfx_.num_);
808  return vecdata_[ix];
809}
810
811template<typename T, typename A>
812inline T &
813vec<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
822template<typename T, typename A>
823inline T &
824vec<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
837template<typename T, typename A>
838inline bool
839vec<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
852template<typename T, typename A>
853inline bool
854vec<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
878template<typename T, typename A>
879inline bool
880vec<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
897template<typename T, typename A>
898inline vec<T, A, vl_embed> *
899vec<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
916template<typename T, typename A>
917inline void
918vec<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
929template<typename T, typename A>
930inline void
931vec<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
942template<typename T, typename A>
943inline T *
944vec<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
955template<typename T, typename A>
956inline T &
957vec<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
967template<typename T, typename A>
968inline void
969vec<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
979template<typename T, typename A>
980inline void
981vec<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
995template<typename T, typename A>
996inline void
997vec<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
1008template<typename T, typename A>
1009inline void
1010vec<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
1020template<typename T, typename A>
1021inline void
1022vec<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
1034template<typename T, typename A>
1035inline void
1036vec<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
1047template<typename T, typename A>
1048unsigned
1049vec<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
1086template<typename T, typename A>
1087inline size_t
1088vec<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
1098template<typename T, typename A>
1099inline void
1100vec<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
1110template<typename T, typename A>
1111inline void
1112vec<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
1122template<typename T, typename A>
1123inline void
1124vec<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
1134template<typename T>
1135void
1136gt_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
1143template<typename T>
1144void
1145gt_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
1154template<typename T, typename A>
1155void
1156gt_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
1163template<typename T, typename A>
1164void
1165gt_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
1171template<typename T, typename A>
1172void
1173gt_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
1209template<typename T, typename A>
1210struct vec<T, A, vl_ptr>
1211{
1212public:
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
1289template<typename T>
1290struct 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
1299template<typename T>
1300inline void
1301vec_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
1310template<typename T>
1311inline void
1312vec_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
1321template<typename T>
1322inline void
1323vec_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
1380template<typename T, typename A>
1381inline bool
1382vec<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
1403template<typename T, typename A>
1404inline bool
1405vec<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
1442template<typename T, typename A>
1443inline vec<T, A, vl_ptr>
1444vec<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
1462template<typename T, typename A>
1463inline bool
1464vec<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
1478template<typename T, typename A>
1479inline bool
1480vec<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
1491template<typename T, typename A>
1492inline void
1493vec<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
1503template<typename T, typename A>
1504inline void
1505vec<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
1517template<typename T, typename A>
1518inline void
1519vec<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
1531template<typename T, typename A>
1532inline void
1533vec<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
1547template<typename T, typename A>
1548inline T *
1549vec<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
1559template<typename T, typename A>
1560inline T *
1561vec<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
1570template<typename T, typename A>
1571inline T &
1572vec<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
1581template<typename T, typename A>
1582inline void
1583vec<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
1596template<typename T, typename A>
1597inline void
1598vec<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
1611template<typename T, typename A>
1612inline void
1613vec<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
1624template<typename T, typename A>
1625inline void
1626vec<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
1637template<typename T, typename A>
1638inline void
1639vec<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
1649template<typename T, typename A>
1650inline void
1651vec<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
1660template<typename T, typename A>
1661inline void
1662vec<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
1673template<typename T, typename A>
1674inline void
1675vec<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
1684template<typename T, typename A>
1685inline void
1686vec<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
1695template<typename T, typename A>
1696inline void
1697vec<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
1706template<typename T, typename A>
1707inline void
1708vec<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
1720template<typename T, typename A>
1721inline unsigned
1722vec<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
Note: See TracBrowser for help on using the repository browser.