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