1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2019 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
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
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/>. */
25 /* Some gen* file have no ggc support as the header file gtype-desc.h is
26 missing. Provide these definitions in case ggc.h has not been included.
27 This is not a problem because any code that runs before gengtype is built
28 will never need to use GC vectors.*/
30 extern void ggc_free (void *);
31 extern size_t ggc_round_alloc_size (size_t requested_size
);
32 extern void *ggc_realloc (void *, size_t MEM_STAT_DECL
);
34 /* Templated vector type and associated interfaces.
36 The interface functions are typesafe and use inline functions,
37 sometimes backed by out-of-line generic functions. The vectors are
38 designed to interoperate with the GTY machinery.
40 There are both 'index' and 'iterate' accessors. The index accessor
41 is implemented by operator[]. The iterator returns a boolean
42 iteration condition and updates the iteration variable passed by
43 reference. Because the iterator will be inlined, the address-of
44 can be optimized away.
46 Each operation that increases the number of active elements is
47 available in 'quick' and 'safe' variants. The former presumes that
48 there is sufficient allocated space for the operation to succeed
49 (it dies if there is not). The latter will reallocate the
50 vector, if needed. Reallocation causes an exponential increase in
51 vector size. If you know you will be adding N elements, it would
52 be more efficient to use the reserve operation before adding the
53 elements with the 'quick' operation. This will ensure there are at
54 least as many elements as you ask for, it will exponentially
55 increase if there are too few spare slots. If you want reserve a
56 specific number of slots, but do not want the exponential increase
57 (for instance, you know this is the last allocation), use the
58 reserve_exact operation. You can also create a vector of a
59 specific size from the get go.
61 You should prefer the push and pop operations, as they append and
62 remove from the end of the vector. If you need to remove several
63 items in one go, use the truncate operation. The insert and remove
64 operations allow you to change elements in the middle of the
65 vector. There are two remove operations, one which preserves the
66 element ordering 'ordered_remove', and one which does not
67 'unordered_remove'. The latter function copies the end element
68 into the removed slot, rather than invoke a memmove operation. The
69 'lower_bound' function will determine where to place an item in the
70 array using insert that will maintain sorted order.
72 Vectors are template types with three arguments: the type of the
73 elements in the vector, the allocation strategy, and the physical
76 Four allocation strategies are supported:
78 - Heap: allocation is done using malloc/free. This is the
79 default allocation strategy.
81 - GC: allocation is done using ggc_alloc/ggc_free.
83 - GC atomic: same as GC with the exception that the elements
84 themselves are assumed to be of an atomic type that does
85 not need to be garbage collected. This means that marking
86 routines do not need to traverse the array marking the
87 individual elements. This increases the performance of
90 Two physical layouts are supported:
92 - Embedded: The vector is structured using the trailing array
93 idiom. The last member of the structure is an array of size
94 1. When the vector is initially allocated, a single memory
95 block is created to hold the vector's control data and the
96 array of elements. These vectors cannot grow without
97 reallocation (see discussion on embeddable vectors below).
99 - Space efficient: The vector is structured as a pointer to an
100 embedded vector. This is the default layout. It means that
101 vectors occupy a single word of storage before initial
102 allocation. Vectors are allowed to grow (the internal
103 pointer is reallocated but the main vector instance does not
106 The type, allocation and layout are specified when the vector is
109 If you need to directly manipulate a vector, then the 'address'
110 accessor will return the address of the start of the vector. Also
111 the 'space' predicate will tell you whether there is spare capacity
112 in the vector. You will not normally need to use these two functions.
114 Notes on the different layout strategies
116 * Embeddable vectors (vec<T, A, vl_embed>)
118 These vectors are suitable to be embedded in other data
119 structures so that they can be pre-allocated in a contiguous
122 Embeddable vectors are implemented using the trailing array
123 idiom, thus they are not resizeable without changing the address
124 of the vector object itself. This means you cannot have
125 variables or fields of embeddable vector type -- always use a
126 pointer to a vector. The one exception is the final field of a
127 structure, which could be a vector type.
129 You will have to use the embedded_size & embedded_init calls to
130 create such objects, and they will not be resizeable (so the
131 'safe' allocation variants are not available).
133 Properties of embeddable vectors:
135 - The whole vector and control data are allocated in a single
136 contiguous block. It uses the trailing-vector idiom, so
137 allocation must reserve enough space for all the elements
138 in the vector plus its control data.
139 - The vector cannot be re-allocated.
140 - The vector cannot grow nor shrink.
141 - No indirections needed for access/manipulation.
142 - It requires 2 words of storage (prior to vector allocation).
145 * Space efficient vector (vec<T, A, vl_ptr>)
147 These vectors can grow dynamically and are allocated together
148 with their control data. They are suited to be included in data
149 structures. Prior to initial allocation, they only take a single
152 These vectors are implemented as a pointer to embeddable vectors.
153 The semantics allow for this pointer to be NULL to represent
154 empty vectors. This way, empty vectors occupy minimal space in
155 the structure containing them.
159 - The whole vector and control data are allocated in a single
161 - The whole vector may be re-allocated.
162 - Vector data may grow and shrink.
163 - Access and manipulation requires a pointer test and
165 - It requires 1 word of storage (prior to vector allocation).
167 An example of their use would be,
170 // A space-efficient vector of tree pointers in GC memory.
171 vec<tree, va_gc, vl_ptr> v;
176 if (s->v.length ()) { we have some contents }
177 s->v.safe_push (decl); // append some decl onto the end
178 for (ix = 0; s->v.iterate (ix, &elt); ix++)
179 { do something with elt }
182 /* Support function for statistics. */
183 extern void dump_vec_loc_statistics (void);
185 /* Hashtable mapping vec addresses to descriptors. */
186 extern htab_t vec_mem_usage_hash
;
188 /* Control data for vectors. This contains the number of allocated
189 and used slots inside a vector. */
193 /* FIXME - These fields should be private, but we need to cater to
194 compilers that have stricter notions of PODness for types. */
196 /* Memory allocation support routines in vec.c. */
197 void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO
);
198 void release_overhead (void *, size_t, size_t, bool CXX_MEM_STAT_INFO
);
199 static unsigned calculate_allocation (vec_prefix
*, unsigned, bool);
200 static unsigned calculate_allocation_1 (unsigned, unsigned);
202 /* Note that vec_prefix should be a base class for vec, but we use
203 offsetof() on vector fields of tree structures (e.g.,
204 tree_binfo::base_binfos), and offsetof only supports base types.
206 To compensate, we make vec_prefix a field inside vec and make
207 vec a friend class of vec_prefix so it can access its fields. */
208 template <typename
, typename
, typename
> friend struct vec
;
210 /* The allocator types also need access to our internals. */
212 friend struct va_gc_atomic
;
213 friend struct va_heap
;
215 unsigned m_alloc
: 31;
216 unsigned m_using_auto_storage
: 1;
220 /* Calculate the number of slots to reserve a vector, making sure that
221 RESERVE slots are free. If EXACT grow exactly, otherwise grow
222 exponentially. PFX is the control data for the vector. */
225 vec_prefix::calculate_allocation (vec_prefix
*pfx
, unsigned reserve
,
229 return (pfx
? pfx
->m_num
: 0) + reserve
;
231 return MAX (4, reserve
);
232 return calculate_allocation_1 (pfx
->m_alloc
, pfx
->m_num
+ reserve
);
235 template<typename
, typename
, typename
> struct vec
;
237 /* Valid vector layouts
239 vl_embed - Embeddable vector that uses the trailing array idiom.
240 vl_ptr - Space efficient vector that uses a pointer to an
241 embeddable vector. */
246 /* Types of supported allocations
248 va_heap - Allocation uses malloc/free.
249 va_gc - Allocation uses ggc_alloc.
250 va_gc_atomic - Same as GC, but individual elements of the array
251 do not need to be marked during collection. */
253 /* Allocator type for heap vectors. */
256 /* Heap vectors are frequently regular instances, so use the vl_ptr
258 typedef vl_ptr default_layout
;
261 static void reserve (vec
<T
, va_heap
, vl_embed
> *&, unsigned, bool
265 static void release (vec
<T
, va_heap
, vl_embed
> *&);
269 /* Allocator for heap memory. Ensure there are at least RESERVE free
270 slots in V. If EXACT is true, grow exactly, else grow
271 exponentially. As a special case, if the vector had not been
272 allocated and RESERVE is 0, no vector will be created. */
276 va_heap::reserve (vec
<T
, va_heap
, vl_embed
> *&v
, unsigned reserve
, bool exact
279 size_t elt_size
= sizeof (T
);
281 = vec_prefix::calculate_allocation (v
? &v
->m_vecpfx
: 0, reserve
, exact
);
282 gcc_checking_assert (alloc
);
284 if (GATHER_STATISTICS
&& v
)
285 v
->m_vecpfx
.release_overhead (v
, elt_size
* v
->allocated (),
286 v
->allocated (), false);
288 size_t size
= vec
<T
, va_heap
, vl_embed
>::embedded_size (alloc
);
289 unsigned nelem
= v
? v
->length () : 0;
290 v
= static_cast <vec
<T
, va_heap
, vl_embed
> *> (xrealloc (v
, size
));
291 v
->embedded_init (alloc
, nelem
);
293 if (GATHER_STATISTICS
)
294 v
->m_vecpfx
.register_overhead (v
, alloc
, elt_size PASS_MEM_STAT
);
298 #if GCC_VERSION >= 4007
299 #pragma GCC diagnostic push
300 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
303 /* Free the heap space allocated for vector V. */
307 va_heap::release (vec
<T
, va_heap
, vl_embed
> *&v
)
309 size_t elt_size
= sizeof (T
);
313 if (GATHER_STATISTICS
)
314 v
->m_vecpfx
.release_overhead (v
, elt_size
* v
->allocated (),
315 v
->allocated (), true);
320 #if GCC_VERSION >= 4007
321 #pragma GCC diagnostic pop
324 /* Allocator type for GC vectors. Notice that we need the structure
325 declaration even if GC is not enabled. */
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
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
>
348 va_gc::release (vec
<T
, A
, vl_embed
> *&v
)
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 RESERVE is 0, no vector will be created. */
361 template<typename T
, typename A
>
363 va_gc::reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned reserve
, bool exact
367 = vec_prefix::calculate_allocation (v
? &v
->m_vecpfx
: 0, reserve
, exact
);
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 (v
, size
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 /* Generic vector template. Default values for A and L indicate the
405 most commonly used strategies.
407 FIXME - Ideally, they would all be vl_ptr to encourage using regular
408 instances for vectors, but the existing GTY machinery is limited
409 in that it can only deal with GC objects that are pointers
412 This means that vector operations that need to deal with
413 potentially NULL pointers, must be provided as free
414 functions (see the vec_safe_* functions above). */
416 typename A
= va_heap
,
417 typename L
= typename
A::default_layout
>
418 struct GTY((user
)) vec
422 /* Generic vec<> debug helpers.
424 These need to be instantiated for each vec<TYPE> used throughout
425 the compiler like this:
427 DEFINE_DEBUG_VEC (TYPE)
429 The reason we have a debug_helper() is because GDB can't
430 disambiguate a plain call to debug(some_vec), and it must be called
431 like debug<TYPE>(some_vec). */
435 debug_helper (vec
<T
> &ref
)
438 for (i
= 0; i
< ref
.length (); ++i
)
440 fprintf (stderr
, "[%d] = ", i
);
442 fputc ('\n', stderr
);
446 /* We need a separate va_gc variant here because default template
447 argument for functions cannot be used in c++-98. Once this
448 restriction is removed, those variant should be folded with the
449 above debug_helper. */
453 debug_helper (vec
<T
, va_gc
> &ref
)
456 for (i
= 0; i
< ref
.length (); ++i
)
458 fprintf (stderr
, "[%d] = ", i
);
460 fputc ('\n', stderr
);
464 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
465 functions for a type T. */
467 #define DEFINE_DEBUG_VEC(T) \
468 template void debug_helper (vec<T> &); \
469 template void debug_helper (vec<T, va_gc> &); \
470 /* Define the vec<T> debug functions. */ \
471 DEBUG_FUNCTION void \
472 debug (vec<T> &ref) \
474 debug_helper <T> (ref); \
476 DEBUG_FUNCTION void \
477 debug (vec<T> *ptr) \
482 fprintf (stderr, "<nil>\n"); \
484 /* Define the vec<T, va_gc> debug functions. */ \
485 DEBUG_FUNCTION void \
486 debug (vec<T, va_gc> &ref) \
488 debug_helper <T> (ref); \
490 DEBUG_FUNCTION void \
491 debug (vec<T, va_gc> *ptr) \
496 fprintf (stderr, "<nil>\n"); \
499 /* Default-construct N elements in DST. */
501 template <typename T
>
503 vec_default_construct (T
*dst
, unsigned n
)
505 #ifdef BROKEN_VALUE_INITIALIZATION
506 /* Versions of GCC before 4.4 sometimes leave certain objects
507 uninitialized when value initialized, though if the type has
508 user defined default ctor, that ctor is invoked. As a workaround
509 perform clearing first and then the value initialization, which
510 fixes the case when value initialization doesn't initialize due to
511 the bugs and should initialize to all zeros, but still allows
512 vectors for types with user defined default ctor that initializes
513 some or all elements to non-zero. If T has no user defined
514 default ctor and some non-static data members have user defined
515 default ctors that initialize to non-zero the workaround will
516 still not work properly; in that case we just need to provide
517 user defined default ctor. */
518 memset (dst
, '\0', sizeof (T
) * n
);
520 for ( ; n
; ++dst
, --n
)
521 ::new (static_cast<void*>(dst
)) T ();
524 /* Copy-construct N elements in DST from *SRC. */
526 template <typename T
>
528 vec_copy_construct (T
*dst
, const T
*src
, unsigned n
)
530 for ( ; n
; ++dst
, ++src
, --n
)
531 ::new (static_cast<void*>(dst
)) T (*src
);
534 /* Type to provide NULL values for vec<T, A, L>. This is used to
535 provide nil initializers for vec instances. Since vec must be
536 a POD, we cannot have proper ctor/dtor for it. To initialize
537 a vec instance, you can assign it the value vNULL. This isn't
538 needed for file-scope and function-local static vectors, which
539 are zero-initialized by default. */
542 template <typename T
, typename A
, typename L
>
543 CONSTEXPR
operator vec
<T
, A
, L
> () { return vec
<T
, A
, L
>(); }
548 /* Embeddable vector. These vectors are suitable to be embedded
549 in other data structures so that they can be pre-allocated in a
550 contiguous memory block.
552 Embeddable vectors are implemented using the trailing array idiom,
553 thus they are not resizeable without changing the address of the
554 vector object itself. This means you cannot have variables or
555 fields of embeddable vector type -- always use a pointer to a
556 vector. The one exception is the final field of a structure, which
557 could be a vector type.
559 You will have to use the embedded_size & embedded_init calls to
560 create such objects, and they will not be resizeable (so the 'safe'
561 allocation variants are not available).
565 - The whole vector and control data are allocated in a single
566 contiguous block. It uses the trailing-vector idiom, so
567 allocation must reserve enough space for all the elements
568 in the vector plus its control data.
569 - The vector cannot be re-allocated.
570 - The vector cannot grow nor shrink.
571 - No indirections needed for access/manipulation.
572 - It requires 2 words of storage (prior to vector allocation). */
574 template<typename T
, typename A
>
575 struct GTY((user
)) vec
<T
, A
, vl_embed
>
578 unsigned allocated (void) const { return m_vecpfx
.m_alloc
; }
579 unsigned length (void) const { return m_vecpfx
.m_num
; }
580 bool is_empty (void) const { return m_vecpfx
.m_num
== 0; }
581 T
*address (void) { return m_vecdata
; }
582 const T
*address (void) const { return m_vecdata
; }
583 T
*begin () { return address (); }
584 const T
*begin () const { return address (); }
585 T
*end () { return address () + length (); }
586 const T
*end () const { return address () + length (); }
587 const T
&operator[] (unsigned) const;
588 T
&operator[] (unsigned);
590 bool space (unsigned) const;
591 bool iterate (unsigned, T
*) const;
592 bool iterate (unsigned, T
**) const;
593 vec
*copy (ALONE_CXX_MEM_STAT_INFO
) const;
594 void splice (const vec
&);
595 void splice (const vec
*src
);
596 T
*quick_push (const T
&);
598 void truncate (unsigned);
599 void quick_insert (unsigned, const T
&);
600 void ordered_remove (unsigned);
601 void unordered_remove (unsigned);
602 void block_remove (unsigned, unsigned);
603 void qsort (int (*) (const void *, const void *));
604 void sort (int (*) (const void *, const void *, void *), void *);
605 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
606 T
*bsearch (const void *key
,
607 int (*compar
)(const void *, const void *, void *), void *);
608 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
609 bool contains (const T
&search
) const;
610 static size_t embedded_size (unsigned);
611 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
612 void quick_grow (unsigned len
);
613 void quick_grow_cleared (unsigned len
);
615 /* vec class can access our internal data and functions. */
616 template <typename
, typename
, typename
> friend struct vec
;
618 /* The allocator types also need access to our internals. */
620 friend struct va_gc_atomic
;
621 friend struct va_heap
;
623 /* FIXME - These fields should be private, but we need to cater to
624 compilers that have stricter notions of PODness for types. */
630 /* Convenience wrapper functions to use when dealing with pointers to
631 embedded vectors. Some functionality for these vectors must be
632 provided via free functions for these reasons:
634 1- The pointer may be NULL (e.g., before initial allocation).
636 2- When the vector needs to grow, it must be reallocated, so
637 the pointer will change its value.
639 Because of limitations with the current GC machinery, all vectors
640 in GC memory *must* be pointers. */
643 /* If V contains no room for NELEMS elements, return false. Otherwise,
645 template<typename T
, typename A
>
647 vec_safe_space (const vec
<T
, A
, vl_embed
> *v
, unsigned nelems
)
649 return v
? v
->space (nelems
) : nelems
== 0;
653 /* If V is NULL, return 0. Otherwise, return V->length(). */
654 template<typename T
, typename A
>
656 vec_safe_length (const vec
<T
, A
, vl_embed
> *v
)
658 return v
? v
->length () : 0;
662 /* If V is NULL, return NULL. Otherwise, return V->address(). */
663 template<typename T
, typename A
>
665 vec_safe_address (vec
<T
, A
, vl_embed
> *v
)
667 return v
? v
->address () : NULL
;
671 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
672 template<typename T
, typename A
>
674 vec_safe_is_empty (vec
<T
, A
, vl_embed
> *v
)
676 return v
? v
->is_empty () : true;
679 /* If V does not have space for NELEMS elements, call
680 V->reserve(NELEMS, EXACT). */
681 template<typename T
, typename A
>
683 vec_safe_reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
, bool exact
= false
686 bool extend
= nelems
? !vec_safe_space (v
, nelems
) : false;
688 A::reserve (v
, nelems
, exact PASS_MEM_STAT
);
692 template<typename T
, typename A
>
694 vec_safe_reserve_exact (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
697 return vec_safe_reserve (v
, nelems
, true PASS_MEM_STAT
);
701 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
702 is 0, V is initialized to NULL. */
704 template<typename T
, typename A
>
706 vec_alloc (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
709 vec_safe_reserve (v
, nelems
, false PASS_MEM_STAT
);
713 /* Free the GC memory allocated by vector V and set it to NULL. */
715 template<typename T
, typename A
>
717 vec_free (vec
<T
, A
, vl_embed
> *&v
)
723 /* Grow V to length LEN. Allocate it, if necessary. */
724 template<typename T
, typename A
>
726 vec_safe_grow (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
728 unsigned oldlen
= vec_safe_length (v
);
729 gcc_checking_assert (len
>= oldlen
);
730 vec_safe_reserve_exact (v
, len
- oldlen PASS_MEM_STAT
);
735 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
736 template<typename T
, typename A
>
738 vec_safe_grow_cleared (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
740 unsigned oldlen
= vec_safe_length (v
);
741 vec_safe_grow (v
, len PASS_MEM_STAT
);
742 vec_default_construct (v
->address () + oldlen
, len
- oldlen
);
746 /* Assume V is not NULL. */
750 vec_safe_grow_cleared (vec
<T
, va_heap
, vl_ptr
> *&v
,
751 unsigned len CXX_MEM_STAT_INFO
)
753 v
->safe_grow_cleared (len PASS_MEM_STAT
);
757 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
758 template<typename T
, typename A
>
760 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
**ptr
)
763 return v
->iterate (ix
, ptr
);
771 template<typename T
, typename A
>
773 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
*ptr
)
776 return v
->iterate (ix
, ptr
);
785 /* If V has no room for one more element, reallocate it. Then call
786 V->quick_push(OBJ). */
787 template<typename T
, typename A
>
789 vec_safe_push (vec
<T
, A
, vl_embed
> *&v
, const T
&obj CXX_MEM_STAT_INFO
)
791 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
792 return v
->quick_push (obj
);
796 /* if V has no room for one more element, reallocate it. Then call
797 V->quick_insert(IX, OBJ). */
798 template<typename T
, typename A
>
800 vec_safe_insert (vec
<T
, A
, vl_embed
> *&v
, unsigned ix
, const T
&obj
803 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
804 v
->quick_insert (ix
, obj
);
808 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
809 template<typename T
, typename A
>
811 vec_safe_truncate (vec
<T
, A
, vl_embed
> *v
, unsigned size
)
818 /* If SRC is not NULL, return a pointer to a copy of it. */
819 template<typename T
, typename A
>
820 inline vec
<T
, A
, vl_embed
> *
821 vec_safe_copy (vec
<T
, A
, vl_embed
> *src CXX_MEM_STAT_INFO
)
823 return src
? src
->copy (ALONE_PASS_MEM_STAT
) : NULL
;
826 /* Copy the elements from SRC to the end of DST as if by memcpy.
827 Reallocate DST, if necessary. */
828 template<typename T
, typename A
>
830 vec_safe_splice (vec
<T
, A
, vl_embed
> *&dst
, const vec
<T
, A
, vl_embed
> *src
833 unsigned src_len
= vec_safe_length (src
);
836 vec_safe_reserve_exact (dst
, vec_safe_length (dst
) + src_len
842 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
843 size of the vector and so should be used with care. */
845 template<typename T
, typename A
>
847 vec_safe_contains (vec
<T
, A
, vl_embed
> *v
, const T
&search
)
849 return v
? v
->contains (search
) : false;
852 /* Index into vector. Return the IX'th element. IX must be in the
853 domain of the vector. */
855 template<typename T
, typename A
>
857 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
) const
859 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
860 return m_vecdata
[ix
];
863 template<typename T
, typename A
>
865 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
)
867 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
868 return m_vecdata
[ix
];
872 /* Get the final element of the vector, which must not be empty. */
874 template<typename T
, typename A
>
876 vec
<T
, A
, vl_embed
>::last (void)
878 gcc_checking_assert (m_vecpfx
.m_num
> 0);
879 return (*this)[m_vecpfx
.m_num
- 1];
883 /* If this vector has space for NELEMS additional entries, return
884 true. You usually only need to use this if you are doing your
885 own vector reallocation, for instance on an embedded vector. This
886 returns true in exactly the same circumstances that vec::reserve
889 template<typename T
, typename A
>
891 vec
<T
, A
, vl_embed
>::space (unsigned nelems
) const
893 return m_vecpfx
.m_alloc
- m_vecpfx
.m_num
>= nelems
;
897 /* Return iteration condition and update PTR to point to the IX'th
898 element of this vector. Use this to iterate over the elements of a
901 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
904 template<typename T
, typename A
>
906 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
*ptr
) const
908 if (ix
< m_vecpfx
.m_num
)
910 *ptr
= m_vecdata
[ix
];
921 /* Return iteration condition and update *PTR to point to the
922 IX'th element of this vector. Use this to iterate over the
923 elements of a vector as follows,
925 for (ix = 0; v->iterate (ix, &ptr); ix++)
928 This variant is for vectors of objects. */
930 template<typename T
, typename A
>
932 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
**ptr
) const
934 if (ix
< m_vecpfx
.m_num
)
936 *ptr
= CONST_CAST (T
*, &m_vecdata
[ix
]);
947 /* Return a pointer to a copy of this vector. */
949 template<typename T
, typename A
>
950 inline vec
<T
, A
, vl_embed
> *
951 vec
<T
, A
, vl_embed
>::copy (ALONE_MEM_STAT_DECL
) const
953 vec
<T
, A
, vl_embed
> *new_vec
= NULL
;
954 unsigned len
= length ();
957 vec_alloc (new_vec
, len PASS_MEM_STAT
);
958 new_vec
->embedded_init (len
, len
);
959 vec_copy_construct (new_vec
->address (), m_vecdata
, len
);
965 /* Copy the elements from SRC to the end of this vector as if by memcpy.
966 The vector must have sufficient headroom available. */
968 template<typename T
, typename A
>
970 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> &src
)
972 unsigned len
= src
.length ();
975 gcc_checking_assert (space (len
));
976 vec_copy_construct (end (), src
.address (), len
);
977 m_vecpfx
.m_num
+= len
;
981 template<typename T
, typename A
>
983 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> *src
)
990 /* Push OBJ (a new element) onto the end of the vector. There must be
991 sufficient space in the vector. Return a pointer to the slot
992 where OBJ was inserted. */
994 template<typename T
, typename A
>
996 vec
<T
, A
, vl_embed
>::quick_push (const T
&obj
)
998 gcc_checking_assert (space (1));
999 T
*slot
= &m_vecdata
[m_vecpfx
.m_num
++];
1005 /* Pop and return the last element off the end of the vector. */
1007 template<typename T
, typename A
>
1009 vec
<T
, A
, vl_embed
>::pop (void)
1011 gcc_checking_assert (length () > 0);
1012 return m_vecdata
[--m_vecpfx
.m_num
];
1016 /* Set the length of the vector to SIZE. The new length must be less
1017 than or equal to the current length. This is an O(1) operation. */
1019 template<typename T
, typename A
>
1021 vec
<T
, A
, vl_embed
>::truncate (unsigned size
)
1023 gcc_checking_assert (length () >= size
);
1024 m_vecpfx
.m_num
= size
;
1028 /* Insert an element, OBJ, at the IXth position of this vector. There
1029 must be sufficient space. */
1031 template<typename T
, typename A
>
1033 vec
<T
, A
, vl_embed
>::quick_insert (unsigned ix
, const T
&obj
)
1035 gcc_checking_assert (length () < allocated ());
1036 gcc_checking_assert (ix
<= length ());
1037 T
*slot
= &m_vecdata
[ix
];
1038 memmove (slot
+ 1, slot
, (m_vecpfx
.m_num
++ - ix
) * sizeof (T
));
1043 /* Remove an element from the IXth position of this vector. Ordering of
1044 remaining elements is preserved. This is an O(N) operation due to
1047 template<typename T
, typename A
>
1049 vec
<T
, A
, vl_embed
>::ordered_remove (unsigned ix
)
1051 gcc_checking_assert (ix
< length ());
1052 T
*slot
= &m_vecdata
[ix
];
1053 memmove (slot
, slot
+ 1, (--m_vecpfx
.m_num
- ix
) * sizeof (T
));
1057 /* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1058 remaining elements is preserved. This is an O(N) operation. */
1060 #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1061 elem_ptr, start, end, cond) \
1063 gcc_assert ((end) <= (vec).length ()); \
1064 for (read_index = write_index = (start); read_index < (end); \
1067 elem_ptr = &(vec)[read_index]; \
1068 bool remove_p = (cond); \
1072 if (read_index != write_index) \
1073 (vec)[write_index] = (vec)[read_index]; \
1078 if (read_index - write_index > 0) \
1079 (vec).block_remove (write_index, read_index - write_index); \
1083 /* Remove elements from VEC for which COND holds. Ordering of remaining
1084 elements is preserved. This is an O(N) operation. */
1086 #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1088 VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1089 elem_ptr, 0, (vec).length (), (cond))
1091 /* Remove an element from the IXth position of this vector. Ordering of
1092 remaining elements is destroyed. This is an O(1) operation. */
1094 template<typename T
, typename A
>
1096 vec
<T
, A
, vl_embed
>::unordered_remove (unsigned ix
)
1098 gcc_checking_assert (ix
< length ());
1099 m_vecdata
[ix
] = m_vecdata
[--m_vecpfx
.m_num
];
1103 /* Remove LEN elements starting at the IXth. Ordering is retained.
1104 This is an O(N) operation due to memmove. */
1106 template<typename T
, typename A
>
1108 vec
<T
, A
, vl_embed
>::block_remove (unsigned ix
, unsigned len
)
1110 gcc_checking_assert (ix
+ len
<= length ());
1111 T
*slot
= &m_vecdata
[ix
];
1112 m_vecpfx
.m_num
-= len
;
1113 memmove (slot
, slot
+ len
, (m_vecpfx
.m_num
- ix
) * sizeof (T
));
1117 /* Sort the contents of this vector with qsort. CMP is the comparison
1118 function to pass to qsort. */
1120 template<typename T
, typename A
>
1122 vec
<T
, A
, vl_embed
>::qsort (int (*cmp
) (const void *, const void *))
1125 gcc_qsort (address (), length (), sizeof (T
), cmp
);
1128 /* Sort the contents of this vector with qsort. CMP is the comparison
1129 function to pass to qsort. */
1131 template<typename T
, typename A
>
1133 vec
<T
, A
, vl_embed
>::sort (int (*cmp
) (const void *, const void *, void *),
1137 gcc_sort_r (address (), length (), sizeof (T
), cmp
, data
);
1141 /* Search the contents of the sorted vector with a binary search.
1142 CMP is the comparison function to pass to bsearch. */
1144 template<typename T
, typename A
>
1146 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
1147 int (*compar
) (const void *, const void *))
1149 const void *base
= this->address ();
1150 size_t nmemb
= this->length ();
1151 size_t size
= sizeof (T
);
1152 /* The following is a copy of glibc stdlib-bsearch.h. */
1162 p
= (const void *) (((const char *) base
) + (idx
* size
));
1163 comparison
= (*compar
) (key
, p
);
1166 else if (comparison
> 0)
1169 return (T
*)const_cast<void *>(p
);
1175 /* Search the contents of the sorted vector with a binary search.
1176 CMP is the comparison function to pass to bsearch. */
1178 template<typename T
, typename A
>
1180 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
1181 int (*compar
) (const void *, const void *,
1182 void *), void *data
)
1184 const void *base
= this->address ();
1185 size_t nmemb
= this->length ();
1186 size_t size
= sizeof (T
);
1187 /* The following is a copy of glibc stdlib-bsearch.h. */
1197 p
= (const void *) (((const char *) base
) + (idx
* size
));
1198 comparison
= (*compar
) (key
, p
, data
);
1201 else if (comparison
> 0)
1204 return (T
*)const_cast<void *>(p
);
1210 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1211 size of the vector and so should be used with care. */
1213 template<typename T
, typename A
>
1215 vec
<T
, A
, vl_embed
>::contains (const T
&search
) const
1217 unsigned int len
= length ();
1218 for (unsigned int i
= 0; i
< len
; i
++)
1219 if ((*this)[i
] == search
)
1225 /* Find and return the first position in which OBJ could be inserted
1226 without changing the ordering of this vector. LESSTHAN is a
1227 function that returns true if the first argument is strictly less
1230 template<typename T
, typename A
>
1232 vec
<T
, A
, vl_embed
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&))
1235 unsigned int len
= length ();
1236 unsigned int half
, middle
;
1237 unsigned int first
= 0;
1243 T middle_elem
= (*this)[middle
];
1244 if (lessthan (middle_elem
, obj
))
1248 len
= len
- half
- 1;
1257 /* Return the number of bytes needed to embed an instance of an
1258 embeddable vec inside another data structure.
1260 Use these methods to determine the required size and initialization
1261 of a vector V of type T embedded within another structure (as the
1264 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1265 void v->embedded_init (unsigned alloc, unsigned num);
1267 These allow the caller to perform the memory allocation. */
1269 template<typename T
, typename A
>
1271 vec
<T
, A
, vl_embed
>::embedded_size (unsigned alloc
)
1273 typedef vec
<T
, A
, vl_embed
> vec_embedded
;
1274 return offsetof (vec_embedded
, m_vecdata
) + alloc
* sizeof (T
);
1278 /* Initialize the vector to contain room for ALLOC elements and
1279 NUM active elements. */
1281 template<typename T
, typename A
>
1283 vec
<T
, A
, vl_embed
>::embedded_init (unsigned alloc
, unsigned num
, unsigned aut
)
1285 m_vecpfx
.m_alloc
= alloc
;
1286 m_vecpfx
.m_using_auto_storage
= aut
;
1287 m_vecpfx
.m_num
= num
;
1291 /* Grow the vector to a specific length. LEN must be as long or longer than
1292 the current length. The new elements are uninitialized. */
1294 template<typename T
, typename A
>
1296 vec
<T
, A
, vl_embed
>::quick_grow (unsigned len
)
1298 gcc_checking_assert (length () <= len
&& len
<= m_vecpfx
.m_alloc
);
1299 m_vecpfx
.m_num
= len
;
1303 /* Grow the vector to a specific length. LEN must be as long or longer than
1304 the current length. The new elements are initialized to zero. */
1306 template<typename T
, typename A
>
1308 vec
<T
, A
, vl_embed
>::quick_grow_cleared (unsigned len
)
1310 unsigned oldlen
= length ();
1311 size_t growby
= len
- oldlen
;
1314 vec_default_construct (address () + oldlen
, growby
);
1317 /* Garbage collection support for vec<T, A, vl_embed>. */
1319 template<typename T
>
1321 gt_ggc_mx (vec
<T
, va_gc
> *v
)
1323 extern void gt_ggc_mx (T
&);
1324 for (unsigned i
= 0; i
< v
->length (); i
++)
1325 gt_ggc_mx ((*v
)[i
]);
1328 template<typename T
>
1330 gt_ggc_mx (vec
<T
, va_gc_atomic
, vl_embed
> *v ATTRIBUTE_UNUSED
)
1332 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1337 /* PCH support for vec<T, A, vl_embed>. */
1339 template<typename T
, typename A
>
1341 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
)
1343 extern void gt_pch_nx (T
&);
1344 for (unsigned i
= 0; i
< v
->length (); i
++)
1345 gt_pch_nx ((*v
)[i
]);
1348 template<typename T
, typename A
>
1350 gt_pch_nx (vec
<T
*, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1352 for (unsigned i
= 0; i
< v
->length (); i
++)
1353 op (&((*v
)[i
]), cookie
);
1356 template<typename T
, typename A
>
1358 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1360 extern void gt_pch_nx (T
*, gt_pointer_operator
, void *);
1361 for (unsigned i
= 0; i
< v
->length (); i
++)
1362 gt_pch_nx (&((*v
)[i
]), op
, cookie
);
1366 /* Space efficient vector. These vectors can grow dynamically and are
1367 allocated together with their control data. They are suited to be
1368 included in data structures. Prior to initial allocation, they
1369 only take a single word of storage.
1371 These vectors are implemented as a pointer to an embeddable vector.
1372 The semantics allow for this pointer to be NULL to represent empty
1373 vectors. This way, empty vectors occupy minimal space in the
1374 structure containing them.
1378 - The whole vector and control data are allocated in a single
1380 - The whole vector may be re-allocated.
1381 - Vector data may grow and shrink.
1382 - Access and manipulation requires a pointer test and
1384 - It requires 1 word of storage (prior to vector allocation).
1389 These vectors must be PODs because they are stored in unions.
1390 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1391 As long as we use C++03, we cannot have constructors nor
1392 destructors in classes that are stored in unions. */
1394 template<typename T
>
1395 struct vec
<T
, va_heap
, vl_ptr
>
1398 /* Memory allocation and deallocation for the embedded vector.
1399 Needed because we cannot have proper ctors/dtors defined. */
1400 void create (unsigned nelems CXX_MEM_STAT_INFO
);
1401 void release (void);
1403 /* Vector operations. */
1404 bool exists (void) const
1405 { return m_vec
!= NULL
; }
1407 bool is_empty (void) const
1408 { return m_vec
? m_vec
->is_empty () : true; }
1410 unsigned length (void) const
1411 { return m_vec
? m_vec
->length () : 0; }
1414 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1416 const T
*address (void) const
1417 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1419 T
*begin () { return address (); }
1420 const T
*begin () const { return address (); }
1421 T
*end () { return begin () + length (); }
1422 const T
*end () const { return begin () + length (); }
1423 const T
&operator[] (unsigned ix
) const
1424 { return (*m_vec
)[ix
]; }
1426 bool operator!=(const vec
&other
) const
1427 { return !(*this == other
); }
1429 bool operator==(const vec
&other
) const
1430 { return address () == other
.address (); }
1432 T
&operator[] (unsigned ix
)
1433 { return (*m_vec
)[ix
]; }
1436 { return m_vec
->last (); }
1438 bool space (int nelems
) const
1439 { return m_vec
? m_vec
->space (nelems
) : nelems
== 0; }
1441 bool iterate (unsigned ix
, T
*p
) const;
1442 bool iterate (unsigned ix
, T
**p
) const;
1443 vec
copy (ALONE_CXX_MEM_STAT_INFO
) const;
1444 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO
);
1445 bool reserve_exact (unsigned CXX_MEM_STAT_INFO
);
1446 void splice (const vec
&);
1447 void safe_splice (const vec
& CXX_MEM_STAT_INFO
);
1448 T
*quick_push (const T
&);
1449 T
*safe_push (const T
&CXX_MEM_STAT_INFO
);
1451 void truncate (unsigned);
1452 void safe_grow (unsigned CXX_MEM_STAT_INFO
);
1453 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO
);
1454 void quick_grow (unsigned);
1455 void quick_grow_cleared (unsigned);
1456 void quick_insert (unsigned, const T
&);
1457 void safe_insert (unsigned, const T
& CXX_MEM_STAT_INFO
);
1458 void ordered_remove (unsigned);
1459 void unordered_remove (unsigned);
1460 void block_remove (unsigned, unsigned);
1461 void qsort (int (*) (const void *, const void *));
1462 void sort (int (*) (const void *, const void *, void *), void *);
1463 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
1464 T
*bsearch (const void *key
,
1465 int (*compar
)(const void *, const void *, void *), void *);
1466 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
1467 bool contains (const T
&search
) const;
1468 void reverse (void);
1470 bool using_auto_storage () const;
1472 /* FIXME - This field should be private, but we need to cater to
1473 compilers that have stricter notions of PODness for types. */
1474 vec
<T
, va_heap
, vl_embed
> *m_vec
;
1478 /* auto_vec is a subclass of vec that automatically manages creating and
1479 releasing the internal vector. If N is non zero then it has N elements of
1480 internal storage. The default is no internal storage, and you probably only
1481 want to ask for internal storage for vectors on the stack because if the
1482 size of the vector is larger than the internal storage that space is wasted.
1484 template<typename T
, size_t N
= 0>
1485 class auto_vec
: public vec
<T
, va_heap
>
1490 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1491 this->m_vec
= &m_auto
;
1502 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1503 this->m_vec
= &m_auto
;
1512 vec
<T
, va_heap
, vl_embed
> m_auto
;
1513 T m_data
[MAX (N
- 1, 1)];
1516 /* auto_vec is a sub class of vec whose storage is released when it is
1518 template<typename T
>
1519 class auto_vec
<T
, 0> : public vec
<T
, va_heap
>
1522 auto_vec () { this->m_vec
= NULL
; }
1523 auto_vec (size_t n
) { this->create (n
); }
1524 ~auto_vec () { this->release (); }
1528 /* Allocate heap memory for pointer V and create the internal vector
1529 with space for NELEMS elements. If NELEMS is 0, the internal
1530 vector is initialized to empty. */
1532 template<typename T
>
1534 vec_alloc (vec
<T
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
1537 v
->create (nelems PASS_MEM_STAT
);
1541 /* A subclass of auto_vec <char *> that frees all of its elements on
1544 class auto_string_vec
: public auto_vec
<char *>
1547 ~auto_string_vec ();
1550 /* Conditionally allocate heap memory for VEC and its internal vector. */
1552 template<typename T
>
1554 vec_check_alloc (vec
<T
, va_heap
> *&vec
, unsigned nelems CXX_MEM_STAT_INFO
)
1557 vec_alloc (vec
, nelems PASS_MEM_STAT
);
1561 /* Free the heap memory allocated by vector V and set it to NULL. */
1563 template<typename T
>
1565 vec_free (vec
<T
> *&v
)
1576 /* Return iteration condition and update PTR to point to the IX'th
1577 element of this vector. Use this to iterate over the elements of a
1580 for (ix = 0; v.iterate (ix, &ptr); ix++)
1583 template<typename T
>
1585 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
*ptr
) const
1588 return m_vec
->iterate (ix
, ptr
);
1597 /* Return iteration condition and update *PTR to point to the
1598 IX'th element of this vector. Use this to iterate over the
1599 elements of a vector as follows,
1601 for (ix = 0; v->iterate (ix, &ptr); ix++)
1604 This variant is for vectors of objects. */
1606 template<typename T
>
1608 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
**ptr
) const
1611 return m_vec
->iterate (ix
, ptr
);
1620 /* Convenience macro for forward iteration. */
1621 #define FOR_EACH_VEC_ELT(V, I, P) \
1622 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1624 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1625 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1627 /* Likewise, but start from FROM rather than 0. */
1628 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1629 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1631 /* Convenience macro for reverse iteration. */
1632 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1633 for (I = (V).length () - 1; \
1634 (V).iterate ((I), &(P)); \
1637 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1638 for (I = vec_safe_length (V) - 1; \
1639 vec_safe_iterate ((V), (I), &(P)); \
1642 /* auto_string_vec's dtor, freeing all contained strings, automatically
1643 chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1646 auto_string_vec::~auto_string_vec ()
1650 FOR_EACH_VEC_ELT (*this, i
, str
)
1655 /* Return a copy of this vector. */
1657 template<typename T
>
1658 inline vec
<T
, va_heap
, vl_ptr
>
1659 vec
<T
, va_heap
, vl_ptr
>::copy (ALONE_MEM_STAT_DECL
) const
1661 vec
<T
, va_heap
, vl_ptr
> new_vec
= vNULL
;
1663 new_vec
.m_vec
= m_vec
->copy ();
1668 /* Ensure that the vector has at least RESERVE slots available (if
1669 EXACT is false), or exactly RESERVE slots available (if EXACT is
1672 This may create additional headroom if EXACT is false.
1674 Note that this can cause the embedded vector to be reallocated.
1675 Returns true iff reallocation actually occurred. */
1677 template<typename T
>
1679 vec
<T
, va_heap
, vl_ptr
>::reserve (unsigned nelems
, bool exact MEM_STAT_DECL
)
1684 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1685 this is necessary because it doesn't have enough information to know the
1686 embedded vector is in auto storage, and so should not be freed. */
1687 vec
<T
, va_heap
, vl_embed
> *oldvec
= m_vec
;
1688 unsigned int oldsize
= 0;
1689 bool handle_auto_vec
= m_vec
&& using_auto_storage ();
1690 if (handle_auto_vec
)
1693 oldsize
= oldvec
->length ();
1697 va_heap::reserve (m_vec
, nelems
, exact PASS_MEM_STAT
);
1698 if (handle_auto_vec
)
1700 vec_copy_construct (m_vec
->address (), oldvec
->address (), oldsize
);
1701 m_vec
->m_vecpfx
.m_num
= oldsize
;
1708 /* Ensure that this vector has exactly NELEMS slots available. This
1709 will not create additional headroom. Note this can cause the
1710 embedded vector to be reallocated. Returns true iff reallocation
1711 actually occurred. */
1713 template<typename T
>
1715 vec
<T
, va_heap
, vl_ptr
>::reserve_exact (unsigned nelems MEM_STAT_DECL
)
1717 return reserve (nelems
, true PASS_MEM_STAT
);
1721 /* Create the internal vector and reserve NELEMS for it. This is
1722 exactly like vec::reserve, but the internal vector is
1723 unconditionally allocated from scratch. The old one, if it
1724 existed, is lost. */
1726 template<typename T
>
1728 vec
<T
, va_heap
, vl_ptr
>::create (unsigned nelems MEM_STAT_DECL
)
1732 reserve_exact (nelems PASS_MEM_STAT
);
1736 /* Free the memory occupied by the embedded vector. */
1738 template<typename T
>
1740 vec
<T
, va_heap
, vl_ptr
>::release (void)
1745 if (using_auto_storage ())
1747 m_vec
->m_vecpfx
.m_num
= 0;
1751 va_heap::release (m_vec
);
1754 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1755 SRC and this vector must be allocated with the same memory
1756 allocation mechanism. This vector is assumed to have sufficient
1757 headroom available. */
1759 template<typename T
>
1761 vec
<T
, va_heap
, vl_ptr
>::splice (const vec
<T
, va_heap
, vl_ptr
> &src
)
1764 m_vec
->splice (*(src
.m_vec
));
1768 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1769 SRC and this vector must be allocated with the same mechanism.
1770 If there is not enough headroom in this vector, it will be reallocated
1773 template<typename T
>
1775 vec
<T
, va_heap
, vl_ptr
>::safe_splice (const vec
<T
, va_heap
, vl_ptr
> &src
1780 reserve_exact (src
.length ());
1786 /* Push OBJ (a new element) onto the end of the vector. There must be
1787 sufficient space in the vector. Return a pointer to the slot
1788 where OBJ was inserted. */
1790 template<typename T
>
1792 vec
<T
, va_heap
, vl_ptr
>::quick_push (const T
&obj
)
1794 return m_vec
->quick_push (obj
);
1798 /* Push a new element OBJ onto the end of this vector. Reallocates
1799 the embedded vector, if needed. Return a pointer to the slot where
1800 OBJ was inserted. */
1802 template<typename T
>
1804 vec
<T
, va_heap
, vl_ptr
>::safe_push (const T
&obj MEM_STAT_DECL
)
1806 reserve (1, false PASS_MEM_STAT
);
1807 return quick_push (obj
);
1811 /* Pop and return the last element off the end of the vector. */
1813 template<typename T
>
1815 vec
<T
, va_heap
, vl_ptr
>::pop (void)
1817 return m_vec
->pop ();
1821 /* Set the length of the vector to LEN. The new length must be less
1822 than or equal to the current length. This is an O(1) operation. */
1824 template<typename T
>
1826 vec
<T
, va_heap
, vl_ptr
>::truncate (unsigned size
)
1829 m_vec
->truncate (size
);
1831 gcc_checking_assert (size
== 0);
1835 /* Grow the vector to a specific length. LEN must be as long or
1836 longer than the current length. The new elements are
1837 uninitialized. Reallocate the internal vector, if needed. */
1839 template<typename T
>
1841 vec
<T
, va_heap
, vl_ptr
>::safe_grow (unsigned len MEM_STAT_DECL
)
1843 unsigned oldlen
= length ();
1844 gcc_checking_assert (oldlen
<= len
);
1845 reserve_exact (len
- oldlen PASS_MEM_STAT
);
1847 m_vec
->quick_grow (len
);
1849 gcc_checking_assert (len
== 0);
1853 /* Grow the embedded vector to a specific length. LEN must be as
1854 long or longer than the current length. The new elements are
1855 initialized to zero. Reallocate the internal vector, if needed. */
1857 template<typename T
>
1859 vec
<T
, va_heap
, vl_ptr
>::safe_grow_cleared (unsigned len MEM_STAT_DECL
)
1861 unsigned oldlen
= length ();
1862 size_t growby
= len
- oldlen
;
1863 safe_grow (len PASS_MEM_STAT
);
1865 vec_default_construct (address () + oldlen
, growby
);
1869 /* Same as vec::safe_grow but without reallocation of the internal vector.
1870 If the vector cannot be extended, a runtime assertion will be triggered. */
1872 template<typename T
>
1874 vec
<T
, va_heap
, vl_ptr
>::quick_grow (unsigned len
)
1876 gcc_checking_assert (m_vec
);
1877 m_vec
->quick_grow (len
);
1881 /* Same as vec::quick_grow_cleared but without reallocation of the
1882 internal vector. If the vector cannot be extended, a runtime
1883 assertion will be triggered. */
1885 template<typename T
>
1887 vec
<T
, va_heap
, vl_ptr
>::quick_grow_cleared (unsigned len
)
1889 gcc_checking_assert (m_vec
);
1890 m_vec
->quick_grow_cleared (len
);
1894 /* Insert an element, OBJ, at the IXth position of this vector. There
1895 must be sufficient space. */
1897 template<typename T
>
1899 vec
<T
, va_heap
, vl_ptr
>::quick_insert (unsigned ix
, const T
&obj
)
1901 m_vec
->quick_insert (ix
, obj
);
1905 /* Insert an element, OBJ, at the IXth position of the vector.
1906 Reallocate the embedded vector, if necessary. */
1908 template<typename T
>
1910 vec
<T
, va_heap
, vl_ptr
>::safe_insert (unsigned ix
, const T
&obj MEM_STAT_DECL
)
1912 reserve (1, false PASS_MEM_STAT
);
1913 quick_insert (ix
, obj
);
1917 /* Remove an element from the IXth position of this vector. Ordering of
1918 remaining elements is preserved. This is an O(N) operation due to
1921 template<typename T
>
1923 vec
<T
, va_heap
, vl_ptr
>::ordered_remove (unsigned ix
)
1925 m_vec
->ordered_remove (ix
);
1929 /* Remove an element from the IXth position of this vector. Ordering
1930 of remaining elements is destroyed. This is an O(1) operation. */
1932 template<typename T
>
1934 vec
<T
, va_heap
, vl_ptr
>::unordered_remove (unsigned ix
)
1936 m_vec
->unordered_remove (ix
);
1940 /* Remove LEN elements starting at the IXth. Ordering is retained.
1941 This is an O(N) operation due to memmove. */
1943 template<typename T
>
1945 vec
<T
, va_heap
, vl_ptr
>::block_remove (unsigned ix
, unsigned len
)
1947 m_vec
->block_remove (ix
, len
);
1951 /* Sort the contents of this vector with qsort. CMP is the comparison
1952 function to pass to qsort. */
1954 template<typename T
>
1956 vec
<T
, va_heap
, vl_ptr
>::qsort (int (*cmp
) (const void *, const void *))
1962 /* Sort the contents of this vector with qsort. CMP is the comparison
1963 function to pass to qsort. */
1965 template<typename T
>
1967 vec
<T
, va_heap
, vl_ptr
>::sort (int (*cmp
) (const void *, const void *,
1968 void *), void *data
)
1971 m_vec
->sort (cmp
, data
);
1975 /* Search the contents of the sorted vector with a binary search.
1976 CMP is the comparison function to pass to bsearch. */
1978 template<typename T
>
1980 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
1981 int (*cmp
) (const void *, const void *))
1984 return m_vec
->bsearch (key
, cmp
);
1988 /* Search the contents of the sorted vector with a binary search.
1989 CMP is the comparison function to pass to bsearch. */
1991 template<typename T
>
1993 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
1994 int (*cmp
) (const void *, const void *,
1995 void *), void *data
)
1998 return m_vec
->bsearch (key
, cmp
, data
);
2003 /* Find and return the first position in which OBJ could be inserted
2004 without changing the ordering of this vector. LESSTHAN is a
2005 function that returns true if the first argument is strictly less
2008 template<typename T
>
2010 vec
<T
, va_heap
, vl_ptr
>::lower_bound (T obj
,
2011 bool (*lessthan
)(const T
&, const T
&))
2014 return m_vec
? m_vec
->lower_bound (obj
, lessthan
) : 0;
2017 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
2018 size of the vector and so should be used with care. */
2020 template<typename T
>
2022 vec
<T
, va_heap
, vl_ptr
>::contains (const T
&search
) const
2024 return m_vec
? m_vec
->contains (search
) : false;
2027 /* Reverse content of the vector. */
2029 template<typename T
>
2031 vec
<T
, va_heap
, vl_ptr
>::reverse (void)
2033 unsigned l
= length ();
2034 T
*ptr
= address ();
2036 for (unsigned i
= 0; i
< l
/ 2; i
++)
2037 std::swap (ptr
[i
], ptr
[l
- i
- 1]);
2040 template<typename T
>
2042 vec
<T
, va_heap
, vl_ptr
>::using_auto_storage () const
2044 return m_vec
->m_vecpfx
.m_using_auto_storage
;
2047 /* Release VEC and call release of all element vectors. */
2049 template<typename T
>
2051 release_vec_vec (vec
<vec
<T
> > &vec
)
2053 for (unsigned i
= 0; i
< vec
.length (); i
++)
2059 #if (GCC_VERSION >= 3000)
2060 # pragma GCC poison m_vec m_vecpfx m_vecdata