1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2018 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 /* Free the heap space allocated for vector V. */
302 va_heap::release (vec
<T
, va_heap
, vl_embed
> *&v
)
304 size_t elt_size
= sizeof (T
);
308 if (GATHER_STATISTICS
)
309 v
->m_vecpfx
.release_overhead (v
, elt_size
* v
->allocated (),
310 v
->allocated (), true);
316 /* Allocator type for GC vectors. Notice that we need the structure
317 declaration even if GC is not enabled. */
321 /* Use vl_embed as the default layout for GC vectors. Due to GTY
322 limitations, GC vectors must always be pointers, so it is more
323 efficient to use a pointer to the vl_embed layout, rather than
324 using a pointer to a pointer as would be the case with vl_ptr. */
325 typedef vl_embed default_layout
;
327 template<typename T
, typename A
>
328 static void reserve (vec
<T
, A
, vl_embed
> *&, unsigned, bool
331 template<typename T
, typename A
>
332 static void release (vec
<T
, A
, vl_embed
> *&v
);
336 /* Free GC memory used by V and reset V to NULL. */
338 template<typename T
, typename A
>
340 va_gc::release (vec
<T
, A
, vl_embed
> *&v
)
348 /* Allocator for GC memory. Ensure there are at least RESERVE free
349 slots in V. If EXACT is true, grow exactly, else grow
350 exponentially. As a special case, if the vector had not been
351 allocated and RESERVE is 0, no vector will be created. */
353 template<typename T
, typename A
>
355 va_gc::reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned reserve
, bool exact
359 = vec_prefix::calculate_allocation (v
? &v
->m_vecpfx
: 0, reserve
, exact
);
367 /* Calculate the amount of space we want. */
368 size_t size
= vec
<T
, A
, vl_embed
>::embedded_size (alloc
);
370 /* Ask the allocator how much space it will really give us. */
371 size
= ::ggc_round_alloc_size (size
);
373 /* Adjust the number of slots accordingly. */
374 size_t vec_offset
= sizeof (vec_prefix
);
375 size_t elt_size
= sizeof (T
);
376 alloc
= (size
- vec_offset
) / elt_size
;
378 /* And finally, recalculate the amount of space we ask for. */
379 size
= vec_offset
+ alloc
* elt_size
;
381 unsigned nelem
= v
? v
->length () : 0;
382 v
= static_cast <vec
<T
, A
, vl_embed
> *> (::ggc_realloc (v
, size
384 v
->embedded_init (alloc
, nelem
);
388 /* Allocator type for GC vectors. This is for vectors of types
389 atomics w.r.t. collection, so allocation and deallocation is
390 completely inherited from va_gc. */
391 struct va_gc_atomic
: va_gc
396 /* Generic vector template. Default values for A and L indicate the
397 most commonly used strategies.
399 FIXME - Ideally, they would all be vl_ptr to encourage using regular
400 instances for vectors, but the existing GTY machinery is limited
401 in that it can only deal with GC objects that are pointers
404 This means that vector operations that need to deal with
405 potentially NULL pointers, must be provided as free
406 functions (see the vec_safe_* functions above). */
408 typename A
= va_heap
,
409 typename L
= typename
A::default_layout
>
410 struct GTY((user
)) vec
414 /* Generic vec<> debug helpers.
416 These need to be instantiated for each vec<TYPE> used throughout
417 the compiler like this:
419 DEFINE_DEBUG_VEC (TYPE)
421 The reason we have a debug_helper() is because GDB can't
422 disambiguate a plain call to debug(some_vec), and it must be called
423 like debug<TYPE>(some_vec). */
427 debug_helper (vec
<T
> &ref
)
430 for (i
= 0; i
< ref
.length (); ++i
)
432 fprintf (stderr
, "[%d] = ", i
);
434 fputc ('\n', stderr
);
438 /* We need a separate va_gc variant here because default template
439 argument for functions cannot be used in c++-98. Once this
440 restriction is removed, those variant should be folded with the
441 above debug_helper. */
445 debug_helper (vec
<T
, va_gc
> &ref
)
448 for (i
= 0; i
< ref
.length (); ++i
)
450 fprintf (stderr
, "[%d] = ", i
);
452 fputc ('\n', stderr
);
456 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
457 functions for a type T. */
459 #define DEFINE_DEBUG_VEC(T) \
460 template void debug_helper (vec<T> &); \
461 template void debug_helper (vec<T, va_gc> &); \
462 /* Define the vec<T> debug functions. */ \
463 DEBUG_FUNCTION void \
464 debug (vec<T> &ref) \
466 debug_helper <T> (ref); \
468 DEBUG_FUNCTION void \
469 debug (vec<T> *ptr) \
474 fprintf (stderr, "<nil>\n"); \
476 /* Define the vec<T, va_gc> debug functions. */ \
477 DEBUG_FUNCTION void \
478 debug (vec<T, va_gc> &ref) \
480 debug_helper <T> (ref); \
482 DEBUG_FUNCTION void \
483 debug (vec<T, va_gc> *ptr) \
488 fprintf (stderr, "<nil>\n"); \
491 /* Default-construct N elements in DST. */
493 template <typename T
>
495 vec_default_construct (T
*dst
, unsigned n
)
497 #ifdef BROKEN_VALUE_INITIALIZATION
498 /* Versions of GCC before 4.4 sometimes leave certain objects
499 uninitialized when value initialized, though if the type has
500 user defined default ctor, that ctor is invoked. As a workaround
501 perform clearing first and then the value initialization, which
502 fixes the case when value initialization doesn't initialize due to
503 the bugs and should initialize to all zeros, but still allows
504 vectors for types with user defined default ctor that initializes
505 some or all elements to non-zero. If T has no user defined
506 default ctor and some non-static data members have user defined
507 default ctors that initialize to non-zero the workaround will
508 still not work properly; in that case we just need to provide
509 user defined default ctor. */
510 memset (dst
, '\0', sizeof (T
) * n
);
512 for ( ; n
; ++dst
, --n
)
513 ::new (static_cast<void*>(dst
)) T ();
516 /* Copy-construct N elements in DST from *SRC. */
518 template <typename T
>
520 vec_copy_construct (T
*dst
, const T
*src
, unsigned n
)
522 for ( ; n
; ++dst
, ++src
, --n
)
523 ::new (static_cast<void*>(dst
)) T (*src
);
526 /* Type to provide NULL values for vec<T, A, L>. This is used to
527 provide nil initializers for vec instances. Since vec must be
528 a POD, we cannot have proper ctor/dtor for it. To initialize
529 a vec instance, you can assign it the value vNULL. This isn't
530 needed for file-scope and function-local static vectors, which
531 are zero-initialized by default. */
534 template <typename T
, typename A
, typename L
>
535 CONSTEXPR
operator vec
<T
, A
, L
> () { return vec
<T
, A
, L
>(); }
540 /* Embeddable vector. These vectors are suitable to be embedded
541 in other data structures so that they can be pre-allocated in a
542 contiguous memory block.
544 Embeddable vectors are implemented using the trailing array idiom,
545 thus they are not resizeable without changing the address of the
546 vector object itself. This means you cannot have variables or
547 fields of embeddable vector type -- always use a pointer to a
548 vector. The one exception is the final field of a structure, which
549 could be a vector type.
551 You will have to use the embedded_size & embedded_init calls to
552 create such objects, and they will not be resizeable (so the 'safe'
553 allocation variants are not available).
557 - The whole vector and control data are allocated in a single
558 contiguous block. It uses the trailing-vector idiom, so
559 allocation must reserve enough space for all the elements
560 in the vector plus its control data.
561 - The vector cannot be re-allocated.
562 - The vector cannot grow nor shrink.
563 - No indirections needed for access/manipulation.
564 - It requires 2 words of storage (prior to vector allocation). */
566 template<typename T
, typename A
>
567 struct GTY((user
)) vec
<T
, A
, vl_embed
>
570 unsigned allocated (void) const { return m_vecpfx
.m_alloc
; }
571 unsigned length (void) const { return m_vecpfx
.m_num
; }
572 bool is_empty (void) const { return m_vecpfx
.m_num
== 0; }
573 T
*address (void) { return m_vecdata
; }
574 const T
*address (void) const { return m_vecdata
; }
575 T
*begin () { return address (); }
576 const T
*begin () const { return address (); }
577 T
*end () { return address () + length (); }
578 const T
*end () const { return address () + length (); }
579 const T
&operator[] (unsigned) const;
580 T
&operator[] (unsigned);
582 bool space (unsigned) const;
583 bool iterate (unsigned, T
*) const;
584 bool iterate (unsigned, T
**) const;
585 vec
*copy (ALONE_CXX_MEM_STAT_INFO
) const;
586 void splice (const vec
&);
587 void splice (const vec
*src
);
588 T
*quick_push (const T
&);
590 void truncate (unsigned);
591 void quick_insert (unsigned, const T
&);
592 void ordered_remove (unsigned);
593 void unordered_remove (unsigned);
594 void block_remove (unsigned, unsigned);
595 void qsort (int (*) (const void *, const void *));
596 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
597 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
598 bool contains (const T
&search
) const;
599 static size_t embedded_size (unsigned);
600 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
601 void quick_grow (unsigned len
);
602 void quick_grow_cleared (unsigned len
);
604 /* vec class can access our internal data and functions. */
605 template <typename
, typename
, typename
> friend struct vec
;
607 /* The allocator types also need access to our internals. */
609 friend struct va_gc_atomic
;
610 friend struct va_heap
;
612 /* FIXME - These fields should be private, but we need to cater to
613 compilers that have stricter notions of PODness for types. */
619 /* Convenience wrapper functions to use when dealing with pointers to
620 embedded vectors. Some functionality for these vectors must be
621 provided via free functions for these reasons:
623 1- The pointer may be NULL (e.g., before initial allocation).
625 2- When the vector needs to grow, it must be reallocated, so
626 the pointer will change its value.
628 Because of limitations with the current GC machinery, all vectors
629 in GC memory *must* be pointers. */
632 /* If V contains no room for NELEMS elements, return false. Otherwise,
634 template<typename T
, typename A
>
636 vec_safe_space (const vec
<T
, A
, vl_embed
> *v
, unsigned nelems
)
638 return v
? v
->space (nelems
) : nelems
== 0;
642 /* If V is NULL, return 0. Otherwise, return V->length(). */
643 template<typename T
, typename A
>
645 vec_safe_length (const vec
<T
, A
, vl_embed
> *v
)
647 return v
? v
->length () : 0;
651 /* If V is NULL, return NULL. Otherwise, return V->address(). */
652 template<typename T
, typename A
>
654 vec_safe_address (vec
<T
, A
, vl_embed
> *v
)
656 return v
? v
->address () : NULL
;
660 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
661 template<typename T
, typename A
>
663 vec_safe_is_empty (vec
<T
, A
, vl_embed
> *v
)
665 return v
? v
->is_empty () : true;
668 /* If V does not have space for NELEMS elements, call
669 V->reserve(NELEMS, EXACT). */
670 template<typename T
, typename A
>
672 vec_safe_reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
, bool exact
= false
675 bool extend
= nelems
? !vec_safe_space (v
, nelems
) : false;
677 A::reserve (v
, nelems
, exact PASS_MEM_STAT
);
681 template<typename T
, typename A
>
683 vec_safe_reserve_exact (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
686 return vec_safe_reserve (v
, nelems
, true PASS_MEM_STAT
);
690 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
691 is 0, V is initialized to NULL. */
693 template<typename T
, typename A
>
695 vec_alloc (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
698 vec_safe_reserve (v
, nelems
, false PASS_MEM_STAT
);
702 /* Free the GC memory allocated by vector V and set it to NULL. */
704 template<typename T
, typename A
>
706 vec_free (vec
<T
, A
, vl_embed
> *&v
)
712 /* Grow V to length LEN. Allocate it, if necessary. */
713 template<typename T
, typename A
>
715 vec_safe_grow (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
717 unsigned oldlen
= vec_safe_length (v
);
718 gcc_checking_assert (len
>= oldlen
);
719 vec_safe_reserve_exact (v
, len
- oldlen PASS_MEM_STAT
);
724 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
725 template<typename T
, typename A
>
727 vec_safe_grow_cleared (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
729 unsigned oldlen
= vec_safe_length (v
);
730 vec_safe_grow (v
, len PASS_MEM_STAT
);
731 vec_default_construct (v
->address () + oldlen
, len
- oldlen
);
735 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
736 template<typename T
, typename A
>
738 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
**ptr
)
741 return v
->iterate (ix
, ptr
);
749 template<typename T
, typename A
>
751 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
*ptr
)
754 return v
->iterate (ix
, ptr
);
763 /* If V has no room for one more element, reallocate it. Then call
764 V->quick_push(OBJ). */
765 template<typename T
, typename A
>
767 vec_safe_push (vec
<T
, A
, vl_embed
> *&v
, const T
&obj CXX_MEM_STAT_INFO
)
769 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
770 return v
->quick_push (obj
);
774 /* if V has no room for one more element, reallocate it. Then call
775 V->quick_insert(IX, OBJ). */
776 template<typename T
, typename A
>
778 vec_safe_insert (vec
<T
, A
, vl_embed
> *&v
, unsigned ix
, const T
&obj
781 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
782 v
->quick_insert (ix
, obj
);
786 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
787 template<typename T
, typename A
>
789 vec_safe_truncate (vec
<T
, A
, vl_embed
> *v
, unsigned size
)
796 /* If SRC is not NULL, return a pointer to a copy of it. */
797 template<typename T
, typename A
>
798 inline vec
<T
, A
, vl_embed
> *
799 vec_safe_copy (vec
<T
, A
, vl_embed
> *src CXX_MEM_STAT_INFO
)
801 return src
? src
->copy (ALONE_PASS_MEM_STAT
) : NULL
;
804 /* Copy the elements from SRC to the end of DST as if by memcpy.
805 Reallocate DST, if necessary. */
806 template<typename T
, typename A
>
808 vec_safe_splice (vec
<T
, A
, vl_embed
> *&dst
, const vec
<T
, A
, vl_embed
> *src
811 unsigned src_len
= vec_safe_length (src
);
814 vec_safe_reserve_exact (dst
, vec_safe_length (dst
) + src_len
820 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
821 size of the vector and so should be used with care. */
823 template<typename T
, typename A
>
825 vec_safe_contains (vec
<T
, A
, vl_embed
> *v
, const T
&search
)
827 return v
? v
->contains (search
) : false;
830 /* Index into vector. Return the IX'th element. IX must be in the
831 domain of the vector. */
833 template<typename T
, typename A
>
835 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
) const
837 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
838 return m_vecdata
[ix
];
841 template<typename T
, typename A
>
843 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
)
845 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
846 return m_vecdata
[ix
];
850 /* Get the final element of the vector, which must not be empty. */
852 template<typename T
, typename A
>
854 vec
<T
, A
, vl_embed
>::last (void)
856 gcc_checking_assert (m_vecpfx
.m_num
> 0);
857 return (*this)[m_vecpfx
.m_num
- 1];
861 /* If this vector has space for NELEMS additional entries, return
862 true. You usually only need to use this if you are doing your
863 own vector reallocation, for instance on an embedded vector. This
864 returns true in exactly the same circumstances that vec::reserve
867 template<typename T
, typename A
>
869 vec
<T
, A
, vl_embed
>::space (unsigned nelems
) const
871 return m_vecpfx
.m_alloc
- m_vecpfx
.m_num
>= nelems
;
875 /* Return iteration condition and update PTR to point to the IX'th
876 element of this vector. Use this to iterate over the elements of a
879 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
882 template<typename T
, typename A
>
884 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
*ptr
) const
886 if (ix
< m_vecpfx
.m_num
)
888 *ptr
= m_vecdata
[ix
];
899 /* Return iteration condition and update *PTR to point to the
900 IX'th element of this vector. Use this to iterate over the
901 elements of a vector as follows,
903 for (ix = 0; v->iterate (ix, &ptr); ix++)
906 This variant is for vectors of objects. */
908 template<typename T
, typename A
>
910 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
**ptr
) const
912 if (ix
< m_vecpfx
.m_num
)
914 *ptr
= CONST_CAST (T
*, &m_vecdata
[ix
]);
925 /* Return a pointer to a copy of this vector. */
927 template<typename T
, typename A
>
928 inline vec
<T
, A
, vl_embed
> *
929 vec
<T
, A
, vl_embed
>::copy (ALONE_MEM_STAT_DECL
) const
931 vec
<T
, A
, vl_embed
> *new_vec
= NULL
;
932 unsigned len
= length ();
935 vec_alloc (new_vec
, len PASS_MEM_STAT
);
936 new_vec
->embedded_init (len
, len
);
937 vec_copy_construct (new_vec
->address (), m_vecdata
, len
);
943 /* Copy the elements from SRC to the end of this vector as if by memcpy.
944 The vector must have sufficient headroom available. */
946 template<typename T
, typename A
>
948 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> &src
)
950 unsigned len
= src
.length ();
953 gcc_checking_assert (space (len
));
954 vec_copy_construct (end (), src
.address (), len
);
955 m_vecpfx
.m_num
+= len
;
959 template<typename T
, typename A
>
961 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> *src
)
968 /* Push OBJ (a new element) onto the end of the vector. There must be
969 sufficient space in the vector. Return a pointer to the slot
970 where OBJ was inserted. */
972 template<typename T
, typename A
>
974 vec
<T
, A
, vl_embed
>::quick_push (const T
&obj
)
976 gcc_checking_assert (space (1));
977 T
*slot
= &m_vecdata
[m_vecpfx
.m_num
++];
983 /* Pop and return the last element off the end of the vector. */
985 template<typename T
, typename A
>
987 vec
<T
, A
, vl_embed
>::pop (void)
989 gcc_checking_assert (length () > 0);
990 return m_vecdata
[--m_vecpfx
.m_num
];
994 /* Set the length of the vector to SIZE. The new length must be less
995 than or equal to the current length. This is an O(1) operation. */
997 template<typename T
, typename A
>
999 vec
<T
, A
, vl_embed
>::truncate (unsigned size
)
1001 gcc_checking_assert (length () >= size
);
1002 m_vecpfx
.m_num
= size
;
1006 /* Insert an element, OBJ, at the IXth position of this vector. There
1007 must be sufficient space. */
1009 template<typename T
, typename A
>
1011 vec
<T
, A
, vl_embed
>::quick_insert (unsigned ix
, const T
&obj
)
1013 gcc_checking_assert (length () < allocated ());
1014 gcc_checking_assert (ix
<= length ());
1015 T
*slot
= &m_vecdata
[ix
];
1016 memmove (slot
+ 1, slot
, (m_vecpfx
.m_num
++ - ix
) * sizeof (T
));
1021 /* Remove an element from the IXth position of this vector. Ordering of
1022 remaining elements is preserved. This is an O(N) operation due to
1025 template<typename T
, typename A
>
1027 vec
<T
, A
, vl_embed
>::ordered_remove (unsigned ix
)
1029 gcc_checking_assert (ix
< length ());
1030 T
*slot
= &m_vecdata
[ix
];
1031 memmove (slot
, slot
+ 1, (--m_vecpfx
.m_num
- ix
) * sizeof (T
));
1035 /* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1036 remaining elements is preserved. This is an O(N) operation. */
1038 #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1039 elem_ptr, start, end, cond) \
1041 gcc_assert ((end) <= (vec).length ()); \
1042 for (read_index = write_index = (start); read_index < (end); \
1045 elem_ptr = &(vec)[read_index]; \
1046 bool remove_p = (cond); \
1050 if (read_index != write_index) \
1051 (vec)[write_index] = (vec)[read_index]; \
1056 if (read_index - write_index > 0) \
1057 (vec).block_remove (write_index, read_index - write_index); \
1061 /* Remove elements from VEC for which COND holds. Ordering of remaining
1062 elements is preserved. This is an O(N) operation. */
1064 #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1066 VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1067 elem_ptr, 0, (vec).length (), (cond))
1069 /* Remove an element from the IXth position of this vector. Ordering of
1070 remaining elements is destroyed. This is an O(1) operation. */
1072 template<typename T
, typename A
>
1074 vec
<T
, A
, vl_embed
>::unordered_remove (unsigned ix
)
1076 gcc_checking_assert (ix
< length ());
1077 m_vecdata
[ix
] = m_vecdata
[--m_vecpfx
.m_num
];
1081 /* Remove LEN elements starting at the IXth. Ordering is retained.
1082 This is an O(N) operation due to memmove. */
1084 template<typename T
, typename A
>
1086 vec
<T
, A
, vl_embed
>::block_remove (unsigned ix
, unsigned len
)
1088 gcc_checking_assert (ix
+ len
<= length ());
1089 T
*slot
= &m_vecdata
[ix
];
1090 m_vecpfx
.m_num
-= len
;
1091 memmove (slot
, slot
+ len
, (m_vecpfx
.m_num
- ix
) * sizeof (T
));
1095 /* Sort the contents of this vector with qsort. CMP is the comparison
1096 function to pass to qsort. */
1098 template<typename T
, typename A
>
1100 vec
<T
, A
, vl_embed
>::qsort (int (*cmp
) (const void *, const void *))
1103 ::qsort (address (), length (), sizeof (T
), cmp
);
1107 /* Search the contents of the sorted vector with a binary search.
1108 CMP is the comparison function to pass to bsearch. */
1110 template<typename T
, typename A
>
1112 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
1113 int (*compar
) (const void *, const void *))
1115 const void *base
= this->address ();
1116 size_t nmemb
= this->length ();
1117 size_t size
= sizeof (T
);
1118 /* The following is a copy of glibc stdlib-bsearch.h. */
1128 p
= (const void *) (((const char *) base
) + (idx
* size
));
1129 comparison
= (*compar
) (key
, p
);
1132 else if (comparison
> 0)
1135 return (T
*)const_cast<void *>(p
);
1141 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1142 size of the vector and so should be used with care. */
1144 template<typename T
, typename A
>
1146 vec
<T
, A
, vl_embed
>::contains (const T
&search
) const
1148 unsigned int len
= length ();
1149 for (unsigned int i
= 0; i
< len
; i
++)
1150 if ((*this)[i
] == search
)
1156 /* Find and return the first position in which OBJ could be inserted
1157 without changing the ordering of this vector. LESSTHAN is a
1158 function that returns true if the first argument is strictly less
1161 template<typename T
, typename A
>
1163 vec
<T
, A
, vl_embed
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&))
1166 unsigned int len
= length ();
1167 unsigned int half
, middle
;
1168 unsigned int first
= 0;
1174 T middle_elem
= (*this)[middle
];
1175 if (lessthan (middle_elem
, obj
))
1179 len
= len
- half
- 1;
1188 /* Return the number of bytes needed to embed an instance of an
1189 embeddable vec inside another data structure.
1191 Use these methods to determine the required size and initialization
1192 of a vector V of type T embedded within another structure (as the
1195 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1196 void v->embedded_init (unsigned alloc, unsigned num);
1198 These allow the caller to perform the memory allocation. */
1200 template<typename T
, typename A
>
1202 vec
<T
, A
, vl_embed
>::embedded_size (unsigned alloc
)
1204 typedef vec
<T
, A
, vl_embed
> vec_embedded
;
1205 return offsetof (vec_embedded
, m_vecdata
) + alloc
* sizeof (T
);
1209 /* Initialize the vector to contain room for ALLOC elements and
1210 NUM active elements. */
1212 template<typename T
, typename A
>
1214 vec
<T
, A
, vl_embed
>::embedded_init (unsigned alloc
, unsigned num
, unsigned aut
)
1216 m_vecpfx
.m_alloc
= alloc
;
1217 m_vecpfx
.m_using_auto_storage
= aut
;
1218 m_vecpfx
.m_num
= num
;
1222 /* Grow the vector to a specific length. LEN must be as long or longer than
1223 the current length. The new elements are uninitialized. */
1225 template<typename T
, typename A
>
1227 vec
<T
, A
, vl_embed
>::quick_grow (unsigned len
)
1229 gcc_checking_assert (length () <= len
&& len
<= m_vecpfx
.m_alloc
);
1230 m_vecpfx
.m_num
= len
;
1234 /* Grow the vector to a specific length. LEN must be as long or longer than
1235 the current length. The new elements are initialized to zero. */
1237 template<typename T
, typename A
>
1239 vec
<T
, A
, vl_embed
>::quick_grow_cleared (unsigned len
)
1241 unsigned oldlen
= length ();
1242 size_t growby
= len
- oldlen
;
1245 vec_default_construct (address () + oldlen
, growby
);
1248 /* Garbage collection support for vec<T, A, vl_embed>. */
1250 template<typename T
>
1252 gt_ggc_mx (vec
<T
, va_gc
> *v
)
1254 extern void gt_ggc_mx (T
&);
1255 for (unsigned i
= 0; i
< v
->length (); i
++)
1256 gt_ggc_mx ((*v
)[i
]);
1259 template<typename T
>
1261 gt_ggc_mx (vec
<T
, va_gc_atomic
, vl_embed
> *v ATTRIBUTE_UNUSED
)
1263 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1268 /* PCH support for vec<T, A, vl_embed>. */
1270 template<typename T
, typename A
>
1272 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
)
1274 extern void gt_pch_nx (T
&);
1275 for (unsigned i
= 0; i
< v
->length (); i
++)
1276 gt_pch_nx ((*v
)[i
]);
1279 template<typename T
, typename A
>
1281 gt_pch_nx (vec
<T
*, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1283 for (unsigned i
= 0; i
< v
->length (); i
++)
1284 op (&((*v
)[i
]), cookie
);
1287 template<typename T
, typename A
>
1289 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1291 extern void gt_pch_nx (T
*, gt_pointer_operator
, void *);
1292 for (unsigned i
= 0; i
< v
->length (); i
++)
1293 gt_pch_nx (&((*v
)[i
]), op
, cookie
);
1297 /* Space efficient vector. These vectors can grow dynamically and are
1298 allocated together with their control data. They are suited to be
1299 included in data structures. Prior to initial allocation, they
1300 only take a single word of storage.
1302 These vectors are implemented as a pointer to an embeddable vector.
1303 The semantics allow for this pointer to be NULL to represent empty
1304 vectors. This way, empty vectors occupy minimal space in the
1305 structure containing them.
1309 - The whole vector and control data are allocated in a single
1311 - The whole vector may be re-allocated.
1312 - Vector data may grow and shrink.
1313 - Access and manipulation requires a pointer test and
1315 - It requires 1 word of storage (prior to vector allocation).
1320 These vectors must be PODs because they are stored in unions.
1321 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1322 As long as we use C++03, we cannot have constructors nor
1323 destructors in classes that are stored in unions. */
1325 template<typename T
>
1326 struct vec
<T
, va_heap
, vl_ptr
>
1329 /* Memory allocation and deallocation for the embedded vector.
1330 Needed because we cannot have proper ctors/dtors defined. */
1331 void create (unsigned nelems CXX_MEM_STAT_INFO
);
1332 void release (void);
1334 /* Vector operations. */
1335 bool exists (void) const
1336 { return m_vec
!= NULL
; }
1338 bool is_empty (void) const
1339 { return m_vec
? m_vec
->is_empty () : true; }
1341 unsigned length (void) const
1342 { return m_vec
? m_vec
->length () : 0; }
1345 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1347 const T
*address (void) const
1348 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1350 T
*begin () { return address (); }
1351 const T
*begin () const { return address (); }
1352 T
*end () { return begin () + length (); }
1353 const T
*end () const { return begin () + length (); }
1354 const T
&operator[] (unsigned ix
) const
1355 { return (*m_vec
)[ix
]; }
1357 bool operator!=(const vec
&other
) const
1358 { return !(*this == other
); }
1360 bool operator==(const vec
&other
) const
1361 { return address () == other
.address (); }
1363 T
&operator[] (unsigned ix
)
1364 { return (*m_vec
)[ix
]; }
1367 { return m_vec
->last (); }
1369 bool space (int nelems
) const
1370 { return m_vec
? m_vec
->space (nelems
) : nelems
== 0; }
1372 bool iterate (unsigned ix
, T
*p
) const;
1373 bool iterate (unsigned ix
, T
**p
) const;
1374 vec
copy (ALONE_CXX_MEM_STAT_INFO
) const;
1375 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO
);
1376 bool reserve_exact (unsigned CXX_MEM_STAT_INFO
);
1377 void splice (const vec
&);
1378 void safe_splice (const vec
& CXX_MEM_STAT_INFO
);
1379 T
*quick_push (const T
&);
1380 T
*safe_push (const T
&CXX_MEM_STAT_INFO
);
1382 void truncate (unsigned);
1383 void safe_grow (unsigned CXX_MEM_STAT_INFO
);
1384 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO
);
1385 void quick_grow (unsigned);
1386 void quick_grow_cleared (unsigned);
1387 void quick_insert (unsigned, const T
&);
1388 void safe_insert (unsigned, const T
& CXX_MEM_STAT_INFO
);
1389 void ordered_remove (unsigned);
1390 void unordered_remove (unsigned);
1391 void block_remove (unsigned, unsigned);
1392 void qsort (int (*) (const void *, const void *));
1393 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
1394 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
1395 bool contains (const T
&search
) const;
1396 void reverse (void);
1398 bool using_auto_storage () const;
1400 /* FIXME - This field should be private, but we need to cater to
1401 compilers that have stricter notions of PODness for types. */
1402 vec
<T
, va_heap
, vl_embed
> *m_vec
;
1406 /* auto_vec is a subclass of vec that automatically manages creating and
1407 releasing the internal vector. If N is non zero then it has N elements of
1408 internal storage. The default is no internal storage, and you probably only
1409 want to ask for internal storage for vectors on the stack because if the
1410 size of the vector is larger than the internal storage that space is wasted.
1412 template<typename T
, size_t N
= 0>
1413 class auto_vec
: public vec
<T
, va_heap
>
1418 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1419 this->m_vec
= &m_auto
;
1430 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1431 this->m_vec
= &m_auto
;
1440 vec
<T
, va_heap
, vl_embed
> m_auto
;
1441 T m_data
[MAX (N
- 1, 1)];
1444 /* auto_vec is a sub class of vec whose storage is released when it is
1446 template<typename T
>
1447 class auto_vec
<T
, 0> : public vec
<T
, va_heap
>
1450 auto_vec () { this->m_vec
= NULL
; }
1451 auto_vec (size_t n
) { this->create (n
); }
1452 ~auto_vec () { this->release (); }
1456 /* Allocate heap memory for pointer V and create the internal vector
1457 with space for NELEMS elements. If NELEMS is 0, the internal
1458 vector is initialized to empty. */
1460 template<typename T
>
1462 vec_alloc (vec
<T
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
1465 v
->create (nelems PASS_MEM_STAT
);
1469 /* A subclass of auto_vec <char *> that frees all of its elements on
1472 class auto_string_vec
: public auto_vec
<char *>
1475 ~auto_string_vec ();
1478 /* Conditionally allocate heap memory for VEC and its internal vector. */
1480 template<typename T
>
1482 vec_check_alloc (vec
<T
, va_heap
> *&vec
, unsigned nelems CXX_MEM_STAT_INFO
)
1485 vec_alloc (vec
, nelems PASS_MEM_STAT
);
1489 /* Free the heap memory allocated by vector V and set it to NULL. */
1491 template<typename T
>
1493 vec_free (vec
<T
> *&v
)
1504 /* Return iteration condition and update PTR to point to the IX'th
1505 element of this vector. Use this to iterate over the elements of a
1508 for (ix = 0; v.iterate (ix, &ptr); ix++)
1511 template<typename T
>
1513 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
*ptr
) const
1516 return m_vec
->iterate (ix
, ptr
);
1525 /* Return iteration condition and update *PTR to point to the
1526 IX'th element of this vector. Use this to iterate over the
1527 elements of a vector as follows,
1529 for (ix = 0; v->iterate (ix, &ptr); ix++)
1532 This variant is for vectors of objects. */
1534 template<typename T
>
1536 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
**ptr
) const
1539 return m_vec
->iterate (ix
, ptr
);
1548 /* Convenience macro for forward iteration. */
1549 #define FOR_EACH_VEC_ELT(V, I, P) \
1550 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1552 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1553 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1555 /* Likewise, but start from FROM rather than 0. */
1556 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1557 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1559 /* Convenience macro for reverse iteration. */
1560 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1561 for (I = (V).length () - 1; \
1562 (V).iterate ((I), &(P)); \
1565 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1566 for (I = vec_safe_length (V) - 1; \
1567 vec_safe_iterate ((V), (I), &(P)); \
1570 /* auto_string_vec's dtor, freeing all contained strings, automatically
1571 chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1574 auto_string_vec::~auto_string_vec ()
1578 FOR_EACH_VEC_ELT (*this, i
, str
)
1583 /* Return a copy of this vector. */
1585 template<typename T
>
1586 inline vec
<T
, va_heap
, vl_ptr
>
1587 vec
<T
, va_heap
, vl_ptr
>::copy (ALONE_MEM_STAT_DECL
) const
1589 vec
<T
, va_heap
, vl_ptr
> new_vec
= vNULL
;
1591 new_vec
.m_vec
= m_vec
->copy ();
1596 /* Ensure that the vector has at least RESERVE slots available (if
1597 EXACT is false), or exactly RESERVE slots available (if EXACT is
1600 This may create additional headroom if EXACT is false.
1602 Note that this can cause the embedded vector to be reallocated.
1603 Returns true iff reallocation actually occurred. */
1605 template<typename T
>
1607 vec
<T
, va_heap
, vl_ptr
>::reserve (unsigned nelems
, bool exact MEM_STAT_DECL
)
1612 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1613 this is necessary because it doesn't have enough information to know the
1614 embedded vector is in auto storage, and so should not be freed. */
1615 vec
<T
, va_heap
, vl_embed
> *oldvec
= m_vec
;
1616 unsigned int oldsize
= 0;
1617 bool handle_auto_vec
= m_vec
&& using_auto_storage ();
1618 if (handle_auto_vec
)
1621 oldsize
= oldvec
->length ();
1625 va_heap::reserve (m_vec
, nelems
, exact PASS_MEM_STAT
);
1626 if (handle_auto_vec
)
1628 vec_copy_construct (m_vec
->address (), oldvec
->address (), oldsize
);
1629 m_vec
->m_vecpfx
.m_num
= oldsize
;
1636 /* Ensure that this vector has exactly NELEMS slots available. This
1637 will not create additional headroom. Note this can cause the
1638 embedded vector to be reallocated. Returns true iff reallocation
1639 actually occurred. */
1641 template<typename T
>
1643 vec
<T
, va_heap
, vl_ptr
>::reserve_exact (unsigned nelems MEM_STAT_DECL
)
1645 return reserve (nelems
, true PASS_MEM_STAT
);
1649 /* Create the internal vector and reserve NELEMS for it. This is
1650 exactly like vec::reserve, but the internal vector is
1651 unconditionally allocated from scratch. The old one, if it
1652 existed, is lost. */
1654 template<typename T
>
1656 vec
<T
, va_heap
, vl_ptr
>::create (unsigned nelems MEM_STAT_DECL
)
1660 reserve_exact (nelems PASS_MEM_STAT
);
1664 /* Free the memory occupied by the embedded vector. */
1666 template<typename T
>
1668 vec
<T
, va_heap
, vl_ptr
>::release (void)
1673 if (using_auto_storage ())
1675 m_vec
->m_vecpfx
.m_num
= 0;
1679 va_heap::release (m_vec
);
1682 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1683 SRC and this vector must be allocated with the same memory
1684 allocation mechanism. This vector is assumed to have sufficient
1685 headroom available. */
1687 template<typename T
>
1689 vec
<T
, va_heap
, vl_ptr
>::splice (const vec
<T
, va_heap
, vl_ptr
> &src
)
1692 m_vec
->splice (*(src
.m_vec
));
1696 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1697 SRC and this vector must be allocated with the same mechanism.
1698 If there is not enough headroom in this vector, it will be reallocated
1701 template<typename T
>
1703 vec
<T
, va_heap
, vl_ptr
>::safe_splice (const vec
<T
, va_heap
, vl_ptr
> &src
1708 reserve_exact (src
.length ());
1714 /* Push OBJ (a new element) onto the end of the vector. There must be
1715 sufficient space in the vector. Return a pointer to the slot
1716 where OBJ was inserted. */
1718 template<typename T
>
1720 vec
<T
, va_heap
, vl_ptr
>::quick_push (const T
&obj
)
1722 return m_vec
->quick_push (obj
);
1726 /* Push a new element OBJ onto the end of this vector. Reallocates
1727 the embedded vector, if needed. Return a pointer to the slot where
1728 OBJ was inserted. */
1730 template<typename T
>
1732 vec
<T
, va_heap
, vl_ptr
>::safe_push (const T
&obj MEM_STAT_DECL
)
1734 reserve (1, false PASS_MEM_STAT
);
1735 return quick_push (obj
);
1739 /* Pop and return the last element off the end of the vector. */
1741 template<typename T
>
1743 vec
<T
, va_heap
, vl_ptr
>::pop (void)
1745 return m_vec
->pop ();
1749 /* Set the length of the vector to LEN. The new length must be less
1750 than or equal to the current length. This is an O(1) operation. */
1752 template<typename T
>
1754 vec
<T
, va_heap
, vl_ptr
>::truncate (unsigned size
)
1757 m_vec
->truncate (size
);
1759 gcc_checking_assert (size
== 0);
1763 /* Grow the vector to a specific length. LEN must be as long or
1764 longer than the current length. The new elements are
1765 uninitialized. Reallocate the internal vector, if needed. */
1767 template<typename T
>
1769 vec
<T
, va_heap
, vl_ptr
>::safe_grow (unsigned len MEM_STAT_DECL
)
1771 unsigned oldlen
= length ();
1772 gcc_checking_assert (oldlen
<= len
);
1773 reserve_exact (len
- oldlen PASS_MEM_STAT
);
1775 m_vec
->quick_grow (len
);
1777 gcc_checking_assert (len
== 0);
1781 /* Grow the embedded vector to a specific length. LEN must be as
1782 long or longer than the current length. The new elements are
1783 initialized to zero. Reallocate the internal vector, if needed. */
1785 template<typename T
>
1787 vec
<T
, va_heap
, vl_ptr
>::safe_grow_cleared (unsigned len MEM_STAT_DECL
)
1789 unsigned oldlen
= length ();
1790 size_t growby
= len
- oldlen
;
1791 safe_grow (len PASS_MEM_STAT
);
1793 vec_default_construct (address () + oldlen
, growby
);
1797 /* Same as vec::safe_grow but without reallocation of the internal vector.
1798 If the vector cannot be extended, a runtime assertion will be triggered. */
1800 template<typename T
>
1802 vec
<T
, va_heap
, vl_ptr
>::quick_grow (unsigned len
)
1804 gcc_checking_assert (m_vec
);
1805 m_vec
->quick_grow (len
);
1809 /* Same as vec::quick_grow_cleared but without reallocation of the
1810 internal vector. If the vector cannot be extended, a runtime
1811 assertion will be triggered. */
1813 template<typename T
>
1815 vec
<T
, va_heap
, vl_ptr
>::quick_grow_cleared (unsigned len
)
1817 gcc_checking_assert (m_vec
);
1818 m_vec
->quick_grow_cleared (len
);
1822 /* Insert an element, OBJ, at the IXth position of this vector. There
1823 must be sufficient space. */
1825 template<typename T
>
1827 vec
<T
, va_heap
, vl_ptr
>::quick_insert (unsigned ix
, const T
&obj
)
1829 m_vec
->quick_insert (ix
, obj
);
1833 /* Insert an element, OBJ, at the IXth position of the vector.
1834 Reallocate the embedded vector, if necessary. */
1836 template<typename T
>
1838 vec
<T
, va_heap
, vl_ptr
>::safe_insert (unsigned ix
, const T
&obj MEM_STAT_DECL
)
1840 reserve (1, false PASS_MEM_STAT
);
1841 quick_insert (ix
, obj
);
1845 /* Remove an element from the IXth position of this vector. Ordering of
1846 remaining elements is preserved. This is an O(N) operation due to
1849 template<typename T
>
1851 vec
<T
, va_heap
, vl_ptr
>::ordered_remove (unsigned ix
)
1853 m_vec
->ordered_remove (ix
);
1857 /* Remove an element from the IXth position of this vector. Ordering
1858 of remaining elements is destroyed. This is an O(1) operation. */
1860 template<typename T
>
1862 vec
<T
, va_heap
, vl_ptr
>::unordered_remove (unsigned ix
)
1864 m_vec
->unordered_remove (ix
);
1868 /* Remove LEN elements starting at the IXth. Ordering is retained.
1869 This is an O(N) operation due to memmove. */
1871 template<typename T
>
1873 vec
<T
, va_heap
, vl_ptr
>::block_remove (unsigned ix
, unsigned len
)
1875 m_vec
->block_remove (ix
, len
);
1879 /* Sort the contents of this vector with qsort. CMP is the comparison
1880 function to pass to qsort. */
1882 template<typename T
>
1884 vec
<T
, va_heap
, vl_ptr
>::qsort (int (*cmp
) (const void *, const void *))
1891 /* Search the contents of the sorted vector with a binary search.
1892 CMP is the comparison function to pass to bsearch. */
1894 template<typename T
>
1896 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
1897 int (*cmp
) (const void *, const void *))
1900 return m_vec
->bsearch (key
, cmp
);
1905 /* Find and return the first position in which OBJ could be inserted
1906 without changing the ordering of this vector. LESSTHAN is a
1907 function that returns true if the first argument is strictly less
1910 template<typename T
>
1912 vec
<T
, va_heap
, vl_ptr
>::lower_bound (T obj
,
1913 bool (*lessthan
)(const T
&, const T
&))
1916 return m_vec
? m_vec
->lower_bound (obj
, lessthan
) : 0;
1919 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1920 size of the vector and so should be used with care. */
1922 template<typename T
>
1924 vec
<T
, va_heap
, vl_ptr
>::contains (const T
&search
) const
1926 return m_vec
? m_vec
->contains (search
) : false;
1929 /* Reverse content of the vector. */
1931 template<typename T
>
1933 vec
<T
, va_heap
, vl_ptr
>::reverse (void)
1935 unsigned l
= length ();
1936 T
*ptr
= address ();
1938 for (unsigned i
= 0; i
< l
/ 2; i
++)
1939 std::swap (ptr
[i
], ptr
[l
- i
- 1]);
1942 template<typename T
>
1944 vec
<T
, va_heap
, vl_ptr
>::using_auto_storage () const
1946 return m_vec
->m_vecpfx
.m_using_auto_storage
;
1949 /* Release VEC and call release of all element vectors. */
1951 template<typename T
>
1953 release_vec_vec (vec
<vec
<T
> > &vec
)
1955 for (unsigned i
= 0; i
< vec
.length (); i
++)
1961 #if (GCC_VERSION >= 3000)
1962 # pragma GCC poison m_vec m_vecpfx m_vecdata