Daily bump.
[official-gcc.git] / gcc / vec.h
blob09a1d0a4d86f02cfafe0564b9c61ea7864b7d3d6
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>
6 This file is part of GCC.
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.
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.
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/>. */
22 #ifndef GCC_VEC_H
23 #define GCC_VEC_H
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.
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
41 #include "statistics.h" // For CXX_MEM_STAT_INFO.
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
57 /* Templated vector type and associated interfaces.
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.
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.
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.
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.
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
99 Four allocation strategies are supported:
101 - Heap: allocation is done using malloc/free. This is the
102 default allocation strategy.
104 - Stack: allocation is done using alloca.
106 - GC: allocation is done using ggc_alloc/ggc_free.
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.
115 Two physical layouts are supported:
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).
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).
131 The type, allocation and layout are specified when the vector is
132 declared.
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.
139 Notes on the different layout strategies
141 * Embeddable vectors (vec<T, A, vl_embed>)
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.
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.
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).
158 Properties of embeddable vectors:
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).
170 * Space efficient vector (vec<T, A, vl_ptr>)
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.
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.
182 Properties:
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).
192 An example of their use would be,
194 struct my_struct {
195 // A space-efficient vector of tree pointers in GC memory.
196 vec<tree, va_gc, vl_ptr> v;
199 struct my_struct *s;
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 }
207 /* Support function for statistics. */
208 extern void dump_vec_loc_statistics (void);
211 /* Control data for vectors. This contains the number of allocated
212 and used slots inside a vector. */
214 struct vec_prefix
216 /* FIXME - These fields should be private, but we need to cater to
217 compilers that have stricter notions of PODness for types. */
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);
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.
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;
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;
238 unsigned alloc_;
239 unsigned num_;
242 template<typename, typename, typename> struct vec;
244 /* Valid vector layouts
246 vl_embed - Embeddable vector that uses the trailing array idiom.
247 vl_ptr - Space efficient vector that uses a pointer to an
248 embeddable vector. */
249 struct vl_embed { };
250 struct vl_ptr { };
253 /* Types of supported allocations
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. */
261 /* Allocator type for heap vectors. */
262 struct va_heap
264 /* Heap vectors are frequently regular instances, so use the vl_ptr
265 layout for them. */
266 typedef vl_ptr default_layout;
268 template<typename T>
269 static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
270 CXX_MEM_STAT_INFO);
272 template<typename T>
273 static void release (vec<T, va_heap, vl_embed> *&);
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. */
282 template<typename T>
283 inline void
284 va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
285 MEM_STAT_DECL)
287 unsigned alloc
288 = vec_prefix::calculate_allocation (v ? &v->vecpfx_ : 0, reserve, exact);
289 if (!alloc)
291 release (v);
292 return;
295 if (GATHER_STATISTICS && v)
296 v->vecpfx_.release_overhead ();
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);
303 if (GATHER_STATISTICS)
304 v->vecpfx_.register_overhead (size FINAL_PASS_MEM_STAT);
308 /* Free the heap space allocated for vector V. */
310 template<typename T>
311 void
312 va_heap::release (vec<T, va_heap, vl_embed> *&v)
314 if (v == NULL)
315 return;
317 if (GATHER_STATISTICS)
318 v->vecpfx_.release_overhead ();
319 ::free (v);
320 v = NULL;
324 /* Allocator type for GC vectors. Notice that we need the structure
325 declaration even if GC is not enabled. */
327 struct va_gc
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;
335 template<typename T, typename A>
336 static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
337 CXX_MEM_STAT_INFO);
339 template<typename T, typename A>
340 static void release (vec<T, A, vl_embed> *&v);
344 /* Free GC memory used by V and reset V to NULL. */
346 template<typename T, typename A>
347 inline void
348 va_gc::release (vec<T, A, vl_embed> *&v)
350 if (v)
351 ::ggc_free (v);
352 v = NULL;
356 /* Allocator for GC memory. Ensure there are at least RESERVE free
357 slots in V. If EXACT is true, grow exactly, else grow
358 exponentially. As a special case, if the vector had not been
359 allocated and and RESERVE is 0, no vector will be created. */
361 template<typename T, typename A>
362 void
363 va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
364 MEM_STAT_DECL)
366 unsigned alloc
367 = vec_prefix::calculate_allocation (v ? &v->vecpfx_ : 0, reserve, exact);
368 if (!alloc)
370 ::ggc_free (v);
371 v = NULL;
372 return;
375 /* Calculate the amount of space we want. */
376 size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
378 /* Ask the allocator how much space it will really give us. */
379 size = ::ggc_round_alloc_size (size);
381 /* Adjust the number of slots accordingly. */
382 size_t vec_offset = sizeof (vec_prefix);
383 size_t elt_size = sizeof (T);
384 alloc = (size - vec_offset) / elt_size;
386 /* And finally, recalculate the amount of space we ask for. */
387 size = vec_offset + alloc * elt_size;
389 unsigned nelem = v ? v->length () : 0;
390 v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc_stat (v, size
391 PASS_MEM_STAT));
392 v->embedded_init (alloc, nelem);
396 /* Allocator type for GC vectors. This is for vectors of types
397 atomics w.r.t. collection, so allocation and deallocation is
398 completely inherited from va_gc. */
399 struct va_gc_atomic : va_gc
404 /* Allocator type for stack vectors. */
405 struct va_stack
407 /* Use vl_ptr as the default layout for stack vectors. */
408 typedef vl_ptr default_layout;
410 template<typename T>
411 static void alloc (vec<T, va_stack, vl_ptr>&, unsigned,
412 vec<T, va_stack, vl_embed> *);
414 template <typename T>
415 static void reserve (vec<T, va_stack, vl_embed> *&, unsigned, bool
416 CXX_MEM_STAT_INFO);
418 template <typename T>
419 static void release (vec<T, va_stack, vl_embed> *&);
422 /* Helper functions to keep track of vectors allocated on the stack. */
423 void register_stack_vec (void *);
424 int stack_vec_register_index (void *);
425 void unregister_stack_vec (unsigned);
427 /* Allocate a vector V which uses alloca for the initial allocation.
428 SPACE is space allocated using alloca. NELEMS is the number of
429 entries allocated. */
431 template<typename T>
432 void
433 va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems,
434 vec<T, va_stack, vl_embed> *space)
436 v.vec_ = space;
437 register_stack_vec (static_cast<void *> (v.vec_));
438 v.vec_->embedded_init (nelems, 0);
442 /* Reserve NELEMS slots for a vector initially allocated on the stack.
443 When this happens, we switch back to heap allocation. We remove
444 the vector from stack_vecs, if it is there, since we no longer need
445 to avoid freeing it. If EXACT is true, grow exactly, otherwise
446 grow exponentially. */
448 template<typename T>
449 void
450 va_stack::reserve (vec<T, va_stack, vl_embed> *&v, unsigned nelems, bool exact
451 MEM_STAT_DECL)
453 int ix = stack_vec_register_index (static_cast<void *> (v));
454 if (ix >= 0)
455 unregister_stack_vec (ix);
456 else
458 /* V is already on the heap. */
459 va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v),
460 nelems, exact PASS_MEM_STAT);
461 return;
464 /* Move VEC_ to the heap. */
465 nelems += v->vecpfx_.num_;
466 vec<T, va_stack, vl_embed> *oldvec = v;
467 v = NULL;
468 va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&>(v), nelems,
469 exact PASS_MEM_STAT);
470 if (v && oldvec)
472 v->vecpfx_.num_ = oldvec->length ();
473 memcpy (v->vecdata_,
474 oldvec->vecdata_,
475 oldvec->length () * sizeof (T));
480 /* Free a vector allocated on the stack. Don't actually free it if we
481 find it in the hash table. */
483 template<typename T>
484 void
485 va_stack::release (vec<T, va_stack, vl_embed> *&v)
487 if (v == NULL)
488 return;
490 int ix = stack_vec_register_index (static_cast<void *> (v));
491 if (ix >= 0)
493 unregister_stack_vec (ix);
494 v = NULL;
496 else
498 /* The vector was not on the list of vectors allocated on the stack, so it
499 must be allocated on the heap. */
500 va_heap::release (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v));
505 /* Generic vector template. Default values for A and L indicate the
506 most commonly used strategies.
508 FIXME - Ideally, they would all be vl_ptr to encourage using regular
509 instances for vectors, but the existing GTY machinery is limited
510 in that it can only deal with GC objects that are pointers
511 themselves.
513 This means that vector operations that need to deal with
514 potentially NULL pointers, must be provided as free
515 functions (see the vec_safe_* functions above). */
516 template<typename T,
517 typename A = va_heap,
518 typename L = typename A::default_layout>
519 struct GTY((user)) vec
523 /* Type to provide NULL values for vec<T, A, L>. This is used to
524 provide nil initializers for vec instances. Since vec must be
525 a POD, we cannot have proper ctor/dtor for it. To initialize
526 a vec instance, you can assign it the value vNULL. */
527 struct vnull
529 template <typename T, typename A, typename L>
530 operator vec<T, A, L> () { return vec<T, A, L>(); }
532 extern vnull vNULL;
535 /* Embeddable vector. These vectors are suitable to be embedded
536 in other data structures so that they can be pre-allocated in a
537 contiguous memory block.
539 Embeddable vectors are implemented using the trailing array idiom,
540 thus they are not resizeable without changing the address of the
541 vector object itself. This means you cannot have variables or
542 fields of embeddable vector type -- always use a pointer to a
543 vector. The one exception is the final field of a structure, which
544 could be a vector type.
546 You will have to use the embedded_size & embedded_init calls to
547 create such objects, and they will not be resizeable (so the 'safe'
548 allocation variants are not available).
550 Properties:
552 - The whole vector and control data are allocated in a single
553 contiguous block. It uses the trailing-vector idiom, so
554 allocation must reserve enough space for all the elements
555 in the vector plus its control data.
556 - The vector cannot be re-allocated.
557 - The vector cannot grow nor shrink.
558 - No indirections needed for access/manipulation.
559 - It requires 2 words of storage (prior to vector allocation). */
561 template<typename T, typename A>
562 struct GTY((user)) vec<T, A, vl_embed>
564 public:
565 unsigned allocated (void) const { return vecpfx_.alloc_; }
566 unsigned length (void) const { return vecpfx_.num_; }
567 bool is_empty (void) const { return vecpfx_.num_ == 0; }
568 T *address (void) { return vecdata_; }
569 const T *address (void) const { return vecdata_; }
570 const T &operator[] (unsigned) const;
571 T &operator[] (unsigned);
572 T &last (void);
573 bool space (unsigned) const;
574 bool iterate (unsigned, T *) const;
575 bool iterate (unsigned, T **) const;
576 vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
577 void splice (vec &);
578 void splice (vec *src);
579 T *quick_push (const T &);
580 T &pop (void);
581 void truncate (unsigned);
582 void quick_insert (unsigned, const T &);
583 void ordered_remove (unsigned);
584 void unordered_remove (unsigned);
585 void block_remove (unsigned, unsigned);
586 void qsort (int (*) (const void *, const void *));
587 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
588 static size_t embedded_size (unsigned);
589 void embedded_init (unsigned, unsigned = 0);
590 void quick_grow (unsigned len);
591 void quick_grow_cleared (unsigned len);
593 /* vec class can access our internal data and functions. */
594 template <typename, typename, typename> friend struct vec;
596 /* The allocator types also need access to our internals. */
597 friend struct va_gc;
598 friend struct va_gc_atomic;
599 friend struct va_heap;
600 friend struct va_stack;
602 /* FIXME - These fields should be private, but we need to cater to
603 compilers that have stricter notions of PODness for types. */
604 vec_prefix vecpfx_;
605 T vecdata_[1];
609 /* Convenience wrapper functions to use when dealing with pointers to
610 embedded vectors. Some functionality for these vectors must be
611 provided via free functions for these reasons:
613 1- The pointer may be NULL (e.g., before initial allocation).
615 2- When the vector needs to grow, it must be reallocated, so
616 the pointer will change its value.
618 Because of limitations with the current GC machinery, all vectors
619 in GC memory *must* be pointers. */
622 /* If V contains no room for NELEMS elements, return false. Otherwise,
623 return true. */
624 template<typename T, typename A>
625 inline bool
626 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
628 return v ? v->space (nelems) : nelems == 0;
632 /* If V is NULL, return 0. Otherwise, return V->length(). */
633 template<typename T, typename A>
634 inline unsigned
635 vec_safe_length (const vec<T, A, vl_embed> *v)
637 return v ? v->length () : 0;
641 /* If V is NULL, return NULL. Otherwise, return V->address(). */
642 template<typename T, typename A>
643 inline T *
644 vec_safe_address (vec<T, A, vl_embed> *v)
646 return v ? v->address () : NULL;
650 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
651 template<typename T, typename A>
652 inline bool
653 vec_safe_is_empty (vec<T, A, vl_embed> *v)
655 return v ? v->is_empty () : true;
659 /* If V does not have space for NELEMS elements, call
660 V->reserve(NELEMS, EXACT). */
661 template<typename T, typename A>
662 inline bool
663 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
664 CXX_MEM_STAT_INFO)
666 bool extend = nelems ? !vec_safe_space (v, nelems) : false;
667 if (extend)
668 A::reserve (v, nelems, exact PASS_MEM_STAT);
669 return extend;
672 template<typename T, typename A>
673 inline bool
674 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
675 CXX_MEM_STAT_INFO)
677 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
681 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
682 is 0, V is initialized to NULL. */
684 template<typename T, typename A>
685 inline void
686 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
688 v = NULL;
689 vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
693 /* Free the GC memory allocated by vector V and set it to NULL. */
695 template<typename T, typename A>
696 inline void
697 vec_free (vec<T, A, vl_embed> *&v)
699 A::release (v);
703 /* Grow V to length LEN. Allocate it, if necessary. */
704 template<typename T, typename A>
705 inline void
706 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
708 unsigned oldlen = vec_safe_length (v);
709 gcc_checking_assert (len >= oldlen);
710 vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
711 v->quick_grow (len);
715 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
716 template<typename T, typename A>
717 inline void
718 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
720 unsigned oldlen = vec_safe_length (v);
721 vec_safe_grow (v, len PASS_MEM_STAT);
722 memset (&(v->address()[oldlen]), 0, sizeof (T) * (len - oldlen));
726 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
727 template<typename T, typename A>
728 inline bool
729 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
731 if (v)
732 return v->iterate (ix, ptr);
733 else
735 *ptr = 0;
736 return false;
740 template<typename T, typename A>
741 inline bool
742 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
744 if (v)
745 return v->iterate (ix, ptr);
746 else
748 *ptr = 0;
749 return false;
754 /* If V has no room for one more element, reallocate it. Then call
755 V->quick_push(OBJ). */
756 template<typename T, typename A>
757 inline T *
758 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
760 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
761 return v->quick_push (obj);
765 /* if V has no room for one more element, reallocate it. Then call
766 V->quick_insert(IX, OBJ). */
767 template<typename T, typename A>
768 inline void
769 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
770 CXX_MEM_STAT_INFO)
772 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
773 v->quick_insert (ix, obj);
777 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
778 template<typename T, typename A>
779 inline void
780 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
782 if (v)
783 v->truncate (size);
787 /* If SRC is not NULL, return a pointer to a copy of it. */
788 template<typename T, typename A>
789 inline vec<T, A, vl_embed> *
790 vec_safe_copy (vec<T, A, vl_embed> *src)
792 return src ? src->copy () : NULL;
795 /* Copy the elements from SRC to the end of DST as if by memcpy.
796 Reallocate DST, if necessary. */
797 template<typename T, typename A>
798 inline void
799 vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src
800 CXX_MEM_STAT_INFO)
802 unsigned src_len = vec_safe_length (src);
803 if (src_len)
805 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
806 PASS_MEM_STAT);
807 dst->splice (*src);
812 /* Index into vector. Return the IX'th element. IX must be in the
813 domain of the vector. */
815 template<typename T, typename A>
816 inline const T &
817 vec<T, A, vl_embed>::operator[] (unsigned ix) const
819 gcc_checking_assert (ix < vecpfx_.num_);
820 return vecdata_[ix];
823 template<typename T, typename A>
824 inline T &
825 vec<T, A, vl_embed>::operator[] (unsigned ix)
827 gcc_checking_assert (ix < vecpfx_.num_);
828 return vecdata_[ix];
832 /* Get the final element of the vector, which must not be empty. */
834 template<typename T, typename A>
835 inline T &
836 vec<T, A, vl_embed>::last (void)
838 gcc_checking_assert (vecpfx_.num_ > 0);
839 return (*this)[vecpfx_.num_ - 1];
843 /* If this vector has space for NELEMS additional entries, return
844 true. You usually only need to use this if you are doing your
845 own vector reallocation, for instance on an embedded vector. This
846 returns true in exactly the same circumstances that vec::reserve
847 will. */
849 template<typename T, typename A>
850 inline bool
851 vec<T, A, vl_embed>::space (unsigned nelems) const
853 return vecpfx_.alloc_ - vecpfx_.num_ >= nelems;
857 /* Return iteration condition and update PTR to point to the IX'th
858 element of this vector. Use this to iterate over the elements of a
859 vector as follows,
861 for (ix = 0; vec<T, A>::iterate(v, ix, &ptr); ix++)
862 continue; */
864 template<typename T, typename A>
865 inline bool
866 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
868 if (ix < vecpfx_.num_)
870 *ptr = vecdata_[ix];
871 return true;
873 else
875 *ptr = 0;
876 return false;
881 /* Return iteration condition and update *PTR to point to the
882 IX'th element of this vector. Use this to iterate over the
883 elements of a vector as follows,
885 for (ix = 0; v->iterate(ix, &ptr); ix++)
886 continue;
888 This variant is for vectors of objects. */
890 template<typename T, typename A>
891 inline bool
892 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
894 if (ix < vecpfx_.num_)
896 *ptr = CONST_CAST (T *, &vecdata_[ix]);
897 return true;
899 else
901 *ptr = 0;
902 return false;
907 /* Return a pointer to a copy of this vector. */
909 template<typename T, typename A>
910 inline vec<T, A, vl_embed> *
911 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
913 vec<T, A, vl_embed> *new_vec = NULL;
914 unsigned len = length ();
915 if (len)
917 vec_alloc (new_vec, len PASS_MEM_STAT);
918 new_vec->embedded_init (len, len);
919 memcpy (new_vec->address(), vecdata_, sizeof (T) * len);
921 return new_vec;
925 /* Copy the elements from SRC to the end of this vector as if by memcpy.
926 The vector must have sufficient headroom available. */
928 template<typename T, typename A>
929 inline void
930 vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src)
932 unsigned len = src.length();
933 if (len)
935 gcc_checking_assert (space (len));
936 memcpy (address() + length(), src.address(), len * sizeof (T));
937 vecpfx_.num_ += len;
941 template<typename T, typename A>
942 inline void
943 vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src)
945 if (src)
946 splice (*src);
950 /* Push OBJ (a new element) onto the end of the vector. There must be
951 sufficient space in the vector. Return a pointer to the slot
952 where OBJ was inserted. */
954 template<typename T, typename A>
955 inline T *
956 vec<T, A, vl_embed>::quick_push (const T &obj)
958 gcc_checking_assert (space (1));
959 T *slot = &vecdata_[vecpfx_.num_++];
960 *slot = obj;
961 return slot;
965 /* Pop and return the last element off the end of the vector. */
967 template<typename T, typename A>
968 inline T &
969 vec<T, A, vl_embed>::pop (void)
971 gcc_checking_assert (length () > 0);
972 return vecdata_[--vecpfx_.num_];
976 /* Set the length of the vector to SIZE. The new length must be less
977 than or equal to the current length. This is an O(1) operation. */
979 template<typename T, typename A>
980 inline void
981 vec<T, A, vl_embed>::truncate (unsigned size)
983 gcc_checking_assert (length () >= size);
984 vecpfx_.num_ = size;
988 /* Insert an element, OBJ, at the IXth position of this vector. There
989 must be sufficient space. */
991 template<typename T, typename A>
992 inline void
993 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
995 gcc_checking_assert (length () < allocated ());
996 gcc_checking_assert (ix <= length ());
997 T *slot = &vecdata_[ix];
998 memmove (slot + 1, slot, (vecpfx_.num_++ - ix) * sizeof (T));
999 *slot = obj;
1003 /* Remove an element from the IXth position of this vector. Ordering of
1004 remaining elements is preserved. This is an O(N) operation due to
1005 memmove. */
1007 template<typename T, typename A>
1008 inline void
1009 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1011 gcc_checking_assert (ix < length());
1012 T *slot = &vecdata_[ix];
1013 memmove (slot, slot + 1, (--vecpfx_.num_ - ix) * sizeof (T));
1017 /* Remove an element from the IXth position of this vector. Ordering of
1018 remaining elements is destroyed. This is an O(1) operation. */
1020 template<typename T, typename A>
1021 inline void
1022 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1024 gcc_checking_assert (ix < length());
1025 vecdata_[ix] = vecdata_[--vecpfx_.num_];
1029 /* Remove LEN elements starting at the IXth. Ordering is retained.
1030 This is an O(N) operation due to memmove. */
1032 template<typename T, typename A>
1033 inline void
1034 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1036 gcc_checking_assert (ix + len <= length());
1037 T *slot = &vecdata_[ix];
1038 vecpfx_.num_ -= len;
1039 memmove (slot, slot + len, (vecpfx_.num_ - ix) * sizeof (T));
1043 /* Sort the contents of this vector with qsort. CMP is the comparison
1044 function to pass to qsort. */
1046 template<typename T, typename A>
1047 inline void
1048 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1050 ::qsort (address(), length(), sizeof (T), cmp);
1054 /* Find and return the first position in which OBJ could be inserted
1055 without changing the ordering of this vector. LESSTHAN is a
1056 function that returns true if the first argument is strictly less
1057 than the second. */
1059 template<typename T, typename A>
1060 unsigned
1061 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1062 const
1064 unsigned int len = length ();
1065 unsigned int half, middle;
1066 unsigned int first = 0;
1067 while (len > 0)
1069 half = len / 2;
1070 middle = first;
1071 middle += half;
1072 T middle_elem = (*this)[middle];
1073 if (lessthan (middle_elem, obj))
1075 first = middle;
1076 ++first;
1077 len = len - half - 1;
1079 else
1080 len = half;
1082 return first;
1086 /* Return the number of bytes needed to embed an instance of an
1087 embeddable vec inside another data structure.
1089 Use these methods to determine the required size and initialization
1090 of a vector V of type T embedded within another structure (as the
1091 final member):
1093 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1094 void v->embedded_init(unsigned alloc, unsigned num);
1096 These allow the caller to perform the memory allocation. */
1098 template<typename T, typename A>
1099 inline size_t
1100 vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1102 typedef vec<T, A, vl_embed> vec_embedded;
1103 return offsetof (vec_embedded, vecdata_) + alloc * sizeof (T);
1107 /* Initialize the vector to contain room for ALLOC elements and
1108 NUM active elements. */
1110 template<typename T, typename A>
1111 inline void
1112 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num)
1114 vecpfx_.alloc_ = alloc;
1115 vecpfx_.num_ = num;
1119 /* Grow the vector to a specific length. LEN must be as long or longer than
1120 the current length. The new elements are uninitialized. */
1122 template<typename T, typename A>
1123 inline void
1124 vec<T, A, vl_embed>::quick_grow (unsigned len)
1126 gcc_checking_assert (length () <= len && len <= vecpfx_.alloc_);
1127 vecpfx_.num_ = len;
1131 /* Grow the vector to a specific length. LEN must be as long or longer than
1132 the current length. The new elements are initialized to zero. */
1134 template<typename T, typename A>
1135 inline void
1136 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1138 unsigned oldlen = length ();
1139 quick_grow (len);
1140 memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
1144 /* Garbage collection support for vec<T, A, vl_embed>. */
1146 template<typename T>
1147 void
1148 gt_ggc_mx (vec<T, va_gc> *v)
1150 extern void gt_ggc_mx (T &);
1151 for (unsigned i = 0; i < v->length (); i++)
1152 gt_ggc_mx ((*v)[i]);
1155 template<typename T>
1156 void
1157 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1159 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1160 be traversed. */
1164 /* PCH support for vec<T, A, vl_embed>. */
1166 template<typename T, typename A>
1167 void
1168 gt_pch_nx (vec<T, A, vl_embed> *v)
1170 extern void gt_pch_nx (T &);
1171 for (unsigned i = 0; i < v->length (); i++)
1172 gt_pch_nx ((*v)[i]);
1175 template<typename T, typename A>
1176 void
1177 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1179 for (unsigned i = 0; i < v->length (); i++)
1180 op (&((*v)[i]), cookie);
1183 template<typename T, typename A>
1184 void
1185 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1187 extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1188 for (unsigned i = 0; i < v->length (); i++)
1189 gt_pch_nx (&((*v)[i]), op, cookie);
1193 /* Space efficient vector. These vectors can grow dynamically and are
1194 allocated together with their control data. They are suited to be
1195 included in data structures. Prior to initial allocation, they
1196 only take a single word of storage.
1198 These vectors are implemented as a pointer to an embeddable vector.
1199 The semantics allow for this pointer to be NULL to represent empty
1200 vectors. This way, empty vectors occupy minimal space in the
1201 structure containing them.
1203 Properties:
1205 - The whole vector and control data are allocated in a single
1206 contiguous block.
1207 - The whole vector may be re-allocated.
1208 - Vector data may grow and shrink.
1209 - Access and manipulation requires a pointer test and
1210 indirection.
1211 - It requires 1 word of storage (prior to vector allocation).
1214 Limitations:
1216 These vectors must be PODs because they are stored in unions.
1217 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1218 As long as we use C++03, we cannot have constructors nor
1219 destructors in classes that are stored in unions. */
1221 template<typename T, typename A>
1222 struct vec<T, A, vl_ptr>
1224 public:
1225 /* Memory allocation and deallocation for the embedded vector.
1226 Needed because we cannot have proper ctors/dtors defined. */
1227 void create (unsigned nelems CXX_MEM_STAT_INFO);
1228 void release (void);
1230 /* Vector operations. */
1231 bool exists (void) const
1232 { return vec_ != NULL; }
1234 bool is_empty (void) const
1235 { return vec_ ? vec_->is_empty() : true; }
1237 unsigned length (void) const
1238 { return vec_ ? vec_->length() : 0; }
1240 T *address (void)
1241 { return vec_ ? vec_->vecdata_ : NULL; }
1243 const T *address (void) const
1244 { return vec_ ? vec_->vecdata_ : NULL; }
1246 const T &operator[] (unsigned ix) const
1247 { return (*vec_)[ix]; }
1249 bool operator!=(const vec &other) const
1250 { return !(*this == other); }
1252 bool operator==(const vec &other) const
1253 { return address() == other.address(); }
1255 T &operator[] (unsigned ix)
1256 { return (*vec_)[ix]; }
1258 T &last (void)
1259 { return vec_->last(); }
1261 bool space (int nelems) const
1262 { return vec_ ? vec_->space (nelems) : nelems == 0; }
1264 bool iterate (unsigned ix, T *p) const;
1265 bool iterate (unsigned ix, T **p) const;
1266 vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1267 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1268 bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1269 void splice (vec &);
1270 void safe_splice (vec & CXX_MEM_STAT_INFO);
1271 T *quick_push (const T &);
1272 T *safe_push (const T &CXX_MEM_STAT_INFO);
1273 T &pop (void);
1274 void truncate (unsigned);
1275 void safe_grow (unsigned CXX_MEM_STAT_INFO);
1276 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
1277 void quick_grow (unsigned);
1278 void quick_grow_cleared (unsigned);
1279 void quick_insert (unsigned, const T &);
1280 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1281 void ordered_remove (unsigned);
1282 void unordered_remove (unsigned);
1283 void block_remove (unsigned, unsigned);
1284 void qsort (int (*) (const void *, const void *));
1285 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1287 template<typename T1>
1288 friend void va_stack::alloc(vec<T1, va_stack, vl_ptr>&, unsigned,
1289 vec<T1, va_stack, vl_embed> *);
1291 /* FIXME - This field should be private, but we need to cater to
1292 compilers that have stricter notions of PODness for types. */
1293 vec<T, A, vl_embed> *vec_;
1297 /* Empty specialization for GC allocation. This will prevent GC
1298 vectors from using the vl_ptr layout. FIXME: This is needed to
1299 circumvent limitations in the GTY machinery. */
1301 template<typename T>
1302 struct vec<T, va_gc, vl_ptr>
1307 /* Allocate heap memory for pointer V and create the internal vector
1308 with space for NELEMS elements. If NELEMS is 0, the internal
1309 vector is initialized to empty. */
1311 template<typename T>
1312 inline void
1313 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1315 v = new vec<T>;
1316 v->create (nelems PASS_MEM_STAT);
1320 /* Conditionally allocate heap memory for VEC and its internal vector. */
1322 template<typename T>
1323 inline void
1324 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1326 if (!vec)
1327 vec_alloc (vec, nelems PASS_MEM_STAT);
1331 /* Free the heap memory allocated by vector V and set it to NULL. */
1333 template<typename T>
1334 inline void
1335 vec_free (vec<T> *&v)
1337 if (v == NULL)
1338 return;
1340 v->release ();
1341 delete v;
1342 v = NULL;
1346 /* Allocate a new stack vector with space for exactly NELEMS objects.
1347 If NELEMS is zero, NO vector is created.
1349 For the stack allocator, no memory is really allocated. The vector
1350 is initialized to be at address SPACE and contain NELEMS slots.
1351 Memory allocation actually occurs in the expansion of VEC_alloc.
1353 Usage notes:
1355 * This does not allocate an instance of vec<T, A>. It allocates the
1356 actual vector of elements (i.e., vec<T, A, vl_embed>) inside a
1357 vec<T, A> instance.
1359 * This allocator must always be a macro:
1361 We support a vector which starts out with space on the stack and
1362 switches to heap space when forced to reallocate. This works a
1363 little differently. In the case of stack vectors, vec_alloc will
1364 expand to a call to vec_alloc_1 that calls XALLOCAVAR to request
1365 the initial allocation. This uses alloca to get the initial
1366 space. Since alloca can not be usefully called in an inline
1367 function, vec_alloc must always be a macro.
1369 Important limitations of stack vectors:
1371 - Only the initial allocation will be made using alloca, so pass
1372 a reasonable estimate that doesn't use too much stack space;
1373 don't pass zero.
1375 - Don't return a stack-allocated vector from the function which
1376 allocated it. */
1378 #define vec_stack_alloc(T,V,N) \
1379 do { \
1380 typedef vec<T, va_stack, vl_embed> stackv; \
1381 va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\
1382 } while (0)
1385 /* Return iteration condition and update PTR to point to the IX'th
1386 element of this vector. Use this to iterate over the elements of a
1387 vector as follows,
1389 for (ix = 0; v.iterate(ix, &ptr); ix++)
1390 continue; */
1392 template<typename T, typename A>
1393 inline bool
1394 vec<T, A, vl_ptr>::iterate (unsigned ix, T *ptr) const
1396 if (vec_)
1397 return vec_->iterate (ix, ptr);
1398 else
1400 *ptr = 0;
1401 return false;
1406 /* Return iteration condition and update *PTR to point to the
1407 IX'th element of this vector. Use this to iterate over the
1408 elements of a vector as follows,
1410 for (ix = 0; v->iterate(ix, &ptr); ix++)
1411 continue;
1413 This variant is for vectors of objects. */
1415 template<typename T, typename A>
1416 inline bool
1417 vec<T, A, vl_ptr>::iterate (unsigned ix, T **ptr) const
1419 if (vec_)
1420 return vec_->iterate (ix, ptr);
1421 else
1423 *ptr = 0;
1424 return false;
1429 /* Convenience macro for forward iteration. */
1430 #define FOR_EACH_VEC_ELT(V, I, P) \
1431 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1433 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1434 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1436 /* Likewise, but start from FROM rather than 0. */
1437 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1438 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1440 /* Convenience macro for reverse iteration. */
1441 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1442 for (I = (V).length () - 1; \
1443 (V).iterate ((I), &(P)); \
1444 (I)--)
1446 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1447 for (I = vec_safe_length (V) - 1; \
1448 vec_safe_iterate ((V), (I), &(P)); \
1449 (I)--)
1452 /* Return a copy of this vector. */
1454 template<typename T, typename A>
1455 inline vec<T, A, vl_ptr>
1456 vec<T, A, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1458 vec<T, A, vl_ptr> new_vec = vNULL;
1459 if (length ())
1460 new_vec.vec_ = vec_->copy ();
1461 return new_vec;
1465 /* Ensure that the vector has at least RESERVE slots available (if
1466 EXACT is false), or exactly RESERVE slots available (if EXACT is
1467 true).
1469 This may create additional headroom if EXACT is false.
1471 Note that this can cause the embedded vector to be reallocated.
1472 Returns true iff reallocation actually occurred. */
1474 template<typename T, typename A>
1475 inline bool
1476 vec<T, A, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1478 bool extend = nelems ? !space (nelems) : false;
1479 if (extend)
1480 A::reserve (vec_, nelems, exact PASS_MEM_STAT);
1481 return extend;
1485 /* Ensure that this vector has exactly NELEMS slots available. This
1486 will not create additional headroom. Note this can cause the
1487 embedded vector to be reallocated. Returns true iff reallocation
1488 actually occurred. */
1490 template<typename T, typename A>
1491 inline bool
1492 vec<T, A, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1494 return reserve (nelems, true PASS_MEM_STAT);
1498 /* Create the internal vector and reserve NELEMS for it. This is
1499 exactly like vec::reserve, but the internal vector is
1500 unconditionally allocated from scratch. The old one, if it
1501 existed, is lost. */
1503 template<typename T, typename A>
1504 inline void
1505 vec<T, A, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1507 vec_ = NULL;
1508 if (nelems > 0)
1509 reserve_exact (nelems PASS_MEM_STAT);
1513 /* Free the memory occupied by the embedded vector. */
1515 template<typename T, typename A>
1516 inline void
1517 vec<T, A, vl_ptr>::release (void)
1519 if (vec_)
1520 A::release (vec_);
1524 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1525 SRC and this vector must be allocated with the same memory
1526 allocation mechanism. This vector is assumed to have sufficient
1527 headroom available. */
1529 template<typename T, typename A>
1530 inline void
1531 vec<T, A, vl_ptr>::splice (vec<T, A, vl_ptr> &src)
1533 if (src.vec_)
1534 vec_->splice (*(src.vec_));
1538 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1539 SRC and this vector must be allocated with the same mechanism.
1540 If there is not enough headroom in this vector, it will be reallocated
1541 as needed. */
1543 template<typename T, typename A>
1544 inline void
1545 vec<T, A, vl_ptr>::safe_splice (vec<T, A, vl_ptr> &src MEM_STAT_DECL)
1547 if (src.length())
1549 reserve_exact (src.length());
1550 splice (src);
1555 /* Push OBJ (a new element) onto the end of the vector. There must be
1556 sufficient space in the vector. Return a pointer to the slot
1557 where OBJ was inserted. */
1559 template<typename T, typename A>
1560 inline T *
1561 vec<T, A, vl_ptr>::quick_push (const T &obj)
1563 return vec_->quick_push (obj);
1567 /* Push a new element OBJ onto the end of this vector. Reallocates
1568 the embedded vector, if needed. Return a pointer to the slot where
1569 OBJ was inserted. */
1571 template<typename T, typename A>
1572 inline T *
1573 vec<T, A, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1575 reserve (1, false PASS_MEM_STAT);
1576 return quick_push (obj);
1580 /* Pop and return the last element off the end of the vector. */
1582 template<typename T, typename A>
1583 inline T &
1584 vec<T, A, vl_ptr>::pop (void)
1586 return vec_->pop ();
1590 /* Set the length of the vector to LEN. The new length must be less
1591 than or equal to the current length. This is an O(1) operation. */
1593 template<typename T, typename A>
1594 inline void
1595 vec<T, A, vl_ptr>::truncate (unsigned size)
1597 if (vec_)
1598 vec_->truncate (size);
1599 else
1600 gcc_checking_assert (size == 0);
1604 /* Grow the vector to a specific length. LEN must be as long or
1605 longer than the current length. The new elements are
1606 uninitialized. Reallocate the internal vector, if needed. */
1608 template<typename T, typename A>
1609 inline void
1610 vec<T, A, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
1612 unsigned oldlen = length ();
1613 gcc_checking_assert (oldlen <= len);
1614 reserve_exact (len - oldlen PASS_MEM_STAT);
1615 vec_->quick_grow (len);
1619 /* Grow the embedded vector to a specific length. LEN must be as
1620 long or longer than the current length. The new elements are
1621 initialized to zero. Reallocate the internal vector, if needed. */
1623 template<typename T, typename A>
1624 inline void
1625 vec<T, A, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
1627 unsigned oldlen = length ();
1628 safe_grow (len PASS_MEM_STAT);
1629 memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
1633 /* Same as vec::safe_grow but without reallocation of the internal vector.
1634 If the vector cannot be extended, a runtime assertion will be triggered. */
1636 template<typename T, typename A>
1637 inline void
1638 vec<T, A, vl_ptr>::quick_grow (unsigned len)
1640 gcc_checking_assert (vec_);
1641 vec_->quick_grow (len);
1645 /* Same as vec::quick_grow_cleared but without reallocation of the
1646 internal vector. If the vector cannot be extended, a runtime
1647 assertion will be triggered. */
1649 template<typename T, typename A>
1650 inline void
1651 vec<T, A, vl_ptr>::quick_grow_cleared (unsigned len)
1653 gcc_checking_assert (vec_);
1654 vec_->quick_grow_cleared (len);
1658 /* Insert an element, OBJ, at the IXth position of this vector. There
1659 must be sufficient space. */
1661 template<typename T, typename A>
1662 inline void
1663 vec<T, A, vl_ptr>::quick_insert (unsigned ix, const T &obj)
1665 vec_->quick_insert (ix, obj);
1669 /* Insert an element, OBJ, at the IXth position of the vector.
1670 Reallocate the embedded vector, if necessary. */
1672 template<typename T, typename A>
1673 inline void
1674 vec<T, A, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
1676 reserve (1, false PASS_MEM_STAT);
1677 quick_insert (ix, obj);
1681 /* Remove an element from the IXth position of this vector. Ordering of
1682 remaining elements is preserved. This is an O(N) operation due to
1683 a memmove. */
1685 template<typename T, typename A>
1686 inline void
1687 vec<T, A, vl_ptr>::ordered_remove (unsigned ix)
1689 vec_->ordered_remove (ix);
1693 /* Remove an element from the IXth position of this vector. Ordering
1694 of remaining elements is destroyed. This is an O(1) operation. */
1696 template<typename T, typename A>
1697 inline void
1698 vec<T, A, vl_ptr>::unordered_remove (unsigned ix)
1700 vec_->unordered_remove (ix);
1704 /* Remove LEN elements starting at the IXth. Ordering is retained.
1705 This is an O(N) operation due to memmove. */
1707 template<typename T, typename A>
1708 inline void
1709 vec<T, A, vl_ptr>::block_remove (unsigned ix, unsigned len)
1711 vec_->block_remove (ix, len);
1715 /* Sort the contents of this vector with qsort. CMP is the comparison
1716 function to pass to qsort. */
1718 template<typename T, typename A>
1719 inline void
1720 vec<T, A, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
1722 if (vec_)
1723 vec_->qsort (cmp);
1727 /* Find and return the first position in which OBJ could be inserted
1728 without changing the ordering of this vector. LESSTHAN is a
1729 function that returns true if the first argument is strictly less
1730 than the second. */
1732 template<typename T, typename A>
1733 inline unsigned
1734 vec<T, A, vl_ptr>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1735 const
1737 return vec_ ? vec_->lower_bound (obj, lessthan) : 0;
1740 #if (GCC_VERSION >= 3000)
1741 # pragma GCC poison vec_ vecpfx_ vecdata_
1742 #endif
1744 #endif // GCC_VEC_H