1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2021 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 /* Allow C++11 range-based 'for' to work directly on vec<T>*. */
423 template<typename T
, typename A
, typename L
>
424 T
* begin (vec
<T
,A
,L
> *v
) { return v
? v
->begin () : nullptr; }
425 template<typename T
, typename A
, typename L
>
426 T
* end (vec
<T
,A
,L
> *v
) { return v
? v
->end () : nullptr; }
427 template<typename T
, typename A
, typename L
>
428 const T
* begin (const vec
<T
,A
,L
> *v
) { return v
? v
->begin () : nullptr; }
429 template<typename T
, typename A
, typename L
>
430 const T
* end (const vec
<T
,A
,L
> *v
) { return v
? v
->end () : nullptr; }
432 /* Generic vec<> debug helpers.
434 These need to be instantiated for each vec<TYPE> used throughout
435 the compiler like this:
437 DEFINE_DEBUG_VEC (TYPE)
439 The reason we have a debug_helper() is because GDB can't
440 disambiguate a plain call to debug(some_vec), and it must be called
441 like debug<TYPE>(some_vec). */
445 debug_helper (vec
<T
> &ref
)
448 for (i
= 0; i
< ref
.length (); ++i
)
450 fprintf (stderr
, "[%d] = ", i
);
452 fputc ('\n', stderr
);
456 /* We need a separate va_gc variant here because default template
457 argument for functions cannot be used in c++-98. Once this
458 restriction is removed, those variant should be folded with the
459 above debug_helper. */
463 debug_helper (vec
<T
, va_gc
> &ref
)
466 for (i
= 0; i
< ref
.length (); ++i
)
468 fprintf (stderr
, "[%d] = ", i
);
470 fputc ('\n', stderr
);
474 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
475 functions for a type T. */
477 #define DEFINE_DEBUG_VEC(T) \
478 template void debug_helper (vec<T> &); \
479 template void debug_helper (vec<T, va_gc> &); \
480 /* Define the vec<T> debug functions. */ \
481 DEBUG_FUNCTION void \
482 debug (vec<T> &ref) \
484 debug_helper <T> (ref); \
486 DEBUG_FUNCTION void \
487 debug (vec<T> *ptr) \
492 fprintf (stderr, "<nil>\n"); \
494 /* Define the vec<T, va_gc> debug functions. */ \
495 DEBUG_FUNCTION void \
496 debug (vec<T, va_gc> &ref) \
498 debug_helper <T> (ref); \
500 DEBUG_FUNCTION void \
501 debug (vec<T, va_gc> *ptr) \
506 fprintf (stderr, "<nil>\n"); \
509 /* Default-construct N elements in DST. */
511 template <typename T
>
513 vec_default_construct (T
*dst
, unsigned n
)
515 #ifdef BROKEN_VALUE_INITIALIZATION
516 /* Versions of GCC before 4.4 sometimes leave certain objects
517 uninitialized when value initialized, though if the type has
518 user defined default ctor, that ctor is invoked. As a workaround
519 perform clearing first and then the value initialization, which
520 fixes the case when value initialization doesn't initialize due to
521 the bugs and should initialize to all zeros, but still allows
522 vectors for types with user defined default ctor that initializes
523 some or all elements to non-zero. If T has no user defined
524 default ctor and some non-static data members have user defined
525 default ctors that initialize to non-zero the workaround will
526 still not work properly; in that case we just need to provide
527 user defined default ctor. */
528 memset (dst
, '\0', sizeof (T
) * n
);
530 for ( ; n
; ++dst
, --n
)
531 ::new (static_cast<void*>(dst
)) T ();
534 /* Copy-construct N elements in DST from *SRC. */
536 template <typename T
>
538 vec_copy_construct (T
*dst
, const T
*src
, unsigned n
)
540 for ( ; n
; ++dst
, ++src
, --n
)
541 ::new (static_cast<void*>(dst
)) T (*src
);
544 /* Type to provide zero-initialized values for vec<T, A, L>. This is
545 used to provide nil initializers for vec instances. Since vec must
546 be a trivially copyable type that can be copied by memcpy and zeroed
547 out by memset, it must have defaulted default and copy ctor and copy
548 assignment. To initialize a vec either use value initialization
549 (e.g., vec() or vec v{ };) or assign it the value vNULL. This isn't
550 needed for file-scope and function-local static vectors, which are
551 zero-initialized by default. */
553 constexpr vnull vNULL
{ };
556 /* Embeddable vector. These vectors are suitable to be embedded
557 in other data structures so that they can be pre-allocated in a
558 contiguous memory block.
560 Embeddable vectors are implemented using the trailing array idiom,
561 thus they are not resizeable without changing the address of the
562 vector object itself. This means you cannot have variables or
563 fields of embeddable vector type -- always use a pointer to a
564 vector. The one exception is the final field of a structure, which
565 could be a vector type.
567 You will have to use the embedded_size & embedded_init calls to
568 create such objects, and they will not be resizeable (so the 'safe'
569 allocation variants are not available).
573 - The whole vector and control data are allocated in a single
574 contiguous block. It uses the trailing-vector idiom, so
575 allocation must reserve enough space for all the elements
576 in the vector plus its control data.
577 - The vector cannot be re-allocated.
578 - The vector cannot grow nor shrink.
579 - No indirections needed for access/manipulation.
580 - It requires 2 words of storage (prior to vector allocation). */
582 template<typename T
, typename A
>
583 struct GTY((user
)) vec
<T
, A
, vl_embed
>
586 unsigned allocated (void) const { return m_vecpfx
.m_alloc
; }
587 unsigned length (void) const { return m_vecpfx
.m_num
; }
588 bool is_empty (void) const { return m_vecpfx
.m_num
== 0; }
589 T
*address (void) { return m_vecdata
; }
590 const T
*address (void) const { return m_vecdata
; }
591 T
*begin () { return address (); }
592 const T
*begin () const { return address (); }
593 T
*end () { return address () + length (); }
594 const T
*end () const { return address () + length (); }
595 const T
&operator[] (unsigned) const;
596 T
&operator[] (unsigned);
598 bool space (unsigned) const;
599 bool iterate (unsigned, T
*) const;
600 bool iterate (unsigned, T
**) const;
601 vec
*copy (ALONE_CXX_MEM_STAT_INFO
) const;
602 void splice (const vec
&);
603 void splice (const vec
*src
);
604 T
*quick_push (const T
&);
606 void truncate (unsigned);
607 void quick_insert (unsigned, const T
&);
608 void ordered_remove (unsigned);
609 void unordered_remove (unsigned);
610 void block_remove (unsigned, unsigned);
611 void qsort (int (*) (const void *, const void *));
612 void sort (int (*) (const void *, const void *, void *), void *);
613 void stablesort (int (*) (const void *, const void *, void *), void *);
614 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
615 T
*bsearch (const void *key
,
616 int (*compar
)(const void *, const void *, void *), void *);
617 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
618 bool contains (const T
&search
) const;
619 static size_t embedded_size (unsigned);
620 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
621 void quick_grow (unsigned len
);
622 void quick_grow_cleared (unsigned len
);
624 /* vec class can access our internal data and functions. */
625 template <typename
, typename
, typename
> friend struct vec
;
627 /* The allocator types also need access to our internals. */
629 friend struct va_gc_atomic
;
630 friend struct va_heap
;
632 /* FIXME - These fields should be private, but we need to cater to
633 compilers that have stricter notions of PODness for types. */
639 /* Convenience wrapper functions to use when dealing with pointers to
640 embedded vectors. Some functionality for these vectors must be
641 provided via free functions for these reasons:
643 1- The pointer may be NULL (e.g., before initial allocation).
645 2- When the vector needs to grow, it must be reallocated, so
646 the pointer will change its value.
648 Because of limitations with the current GC machinery, all vectors
649 in GC memory *must* be pointers. */
652 /* If V contains no room for NELEMS elements, return false. Otherwise,
654 template<typename T
, typename A
>
656 vec_safe_space (const vec
<T
, A
, vl_embed
> *v
, unsigned nelems
)
658 return v
? v
->space (nelems
) : nelems
== 0;
662 /* If V is NULL, return 0. Otherwise, return V->length(). */
663 template<typename T
, typename A
>
665 vec_safe_length (const vec
<T
, A
, vl_embed
> *v
)
667 return v
? v
->length () : 0;
671 /* If V is NULL, return NULL. Otherwise, return V->address(). */
672 template<typename T
, typename A
>
674 vec_safe_address (vec
<T
, A
, vl_embed
> *v
)
676 return v
? v
->address () : NULL
;
680 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
681 template<typename T
, typename A
>
683 vec_safe_is_empty (vec
<T
, A
, vl_embed
> *v
)
685 return v
? v
->is_empty () : true;
688 /* If V does not have space for NELEMS elements, call
689 V->reserve(NELEMS, EXACT). */
690 template<typename T
, typename A
>
692 vec_safe_reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
, bool exact
= false
695 bool extend
= nelems
? !vec_safe_space (v
, nelems
) : false;
697 A::reserve (v
, nelems
, exact PASS_MEM_STAT
);
701 template<typename T
, typename A
>
703 vec_safe_reserve_exact (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
706 return vec_safe_reserve (v
, nelems
, true PASS_MEM_STAT
);
710 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
711 is 0, V is initialized to NULL. */
713 template<typename T
, typename A
>
715 vec_alloc (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
718 vec_safe_reserve (v
, nelems
, false PASS_MEM_STAT
);
722 /* Free the GC memory allocated by vector V and set it to NULL. */
724 template<typename T
, typename A
>
726 vec_free (vec
<T
, A
, vl_embed
> *&v
)
732 /* Grow V to length LEN. Allocate it, if necessary. */
733 template<typename T
, typename A
>
735 vec_safe_grow (vec
<T
, A
, vl_embed
> *&v
, unsigned len
,
736 bool exact
= false CXX_MEM_STAT_INFO
)
738 unsigned oldlen
= vec_safe_length (v
);
739 gcc_checking_assert (len
>= oldlen
);
740 vec_safe_reserve (v
, len
- oldlen
, exact PASS_MEM_STAT
);
745 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
746 template<typename T
, typename A
>
748 vec_safe_grow_cleared (vec
<T
, A
, vl_embed
> *&v
, unsigned len
,
749 bool exact
= false CXX_MEM_STAT_INFO
)
751 unsigned oldlen
= vec_safe_length (v
);
752 vec_safe_grow (v
, len
, exact PASS_MEM_STAT
);
753 vec_default_construct (v
->address () + oldlen
, len
- oldlen
);
757 /* Assume V is not NULL. */
761 vec_safe_grow_cleared (vec
<T
, va_heap
, vl_ptr
> *&v
,
762 unsigned len
, bool exact
= false CXX_MEM_STAT_INFO
)
764 v
->safe_grow_cleared (len
, exact PASS_MEM_STAT
);
767 /* If V does not have space for NELEMS elements, call
768 V->reserve(NELEMS, EXACT). */
772 vec_safe_reserve (vec
<T
, va_heap
, vl_ptr
> *&v
, unsigned nelems
, bool exact
= false
775 return v
->reserve (nelems
, exact
);
779 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
780 template<typename T
, typename A
>
782 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
**ptr
)
785 return v
->iterate (ix
, ptr
);
793 template<typename T
, typename A
>
795 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
*ptr
)
798 return v
->iterate (ix
, ptr
);
807 /* If V has no room for one more element, reallocate it. Then call
808 V->quick_push(OBJ). */
809 template<typename T
, typename A
>
811 vec_safe_push (vec
<T
, A
, vl_embed
> *&v
, const T
&obj CXX_MEM_STAT_INFO
)
813 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
814 return v
->quick_push (obj
);
818 /* if V has no room for one more element, reallocate it. Then call
819 V->quick_insert(IX, OBJ). */
820 template<typename T
, typename A
>
822 vec_safe_insert (vec
<T
, A
, vl_embed
> *&v
, unsigned ix
, const T
&obj
825 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
826 v
->quick_insert (ix
, obj
);
830 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
831 template<typename T
, typename A
>
833 vec_safe_truncate (vec
<T
, A
, vl_embed
> *v
, unsigned size
)
840 /* If SRC is not NULL, return a pointer to a copy of it. */
841 template<typename T
, typename A
>
842 inline vec
<T
, A
, vl_embed
> *
843 vec_safe_copy (vec
<T
, A
, vl_embed
> *src CXX_MEM_STAT_INFO
)
845 return src
? src
->copy (ALONE_PASS_MEM_STAT
) : NULL
;
848 /* Copy the elements from SRC to the end of DST as if by memcpy.
849 Reallocate DST, if necessary. */
850 template<typename T
, typename A
>
852 vec_safe_splice (vec
<T
, A
, vl_embed
> *&dst
, const vec
<T
, A
, vl_embed
> *src
855 unsigned src_len
= vec_safe_length (src
);
858 vec_safe_reserve_exact (dst
, vec_safe_length (dst
) + src_len
864 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
865 size of the vector and so should be used with care. */
867 template<typename T
, typename A
>
869 vec_safe_contains (vec
<T
, A
, vl_embed
> *v
, const T
&search
)
871 return v
? v
->contains (search
) : false;
874 /* Index into vector. Return the IX'th element. IX must be in the
875 domain of the vector. */
877 template<typename T
, typename A
>
879 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
) const
881 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
882 return m_vecdata
[ix
];
885 template<typename T
, typename A
>
887 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
)
889 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
890 return m_vecdata
[ix
];
894 /* Get the final element of the vector, which must not be empty. */
896 template<typename T
, typename A
>
898 vec
<T
, A
, vl_embed
>::last (void)
900 gcc_checking_assert (m_vecpfx
.m_num
> 0);
901 return (*this)[m_vecpfx
.m_num
- 1];
905 /* If this vector has space for NELEMS additional entries, return
906 true. You usually only need to use this if you are doing your
907 own vector reallocation, for instance on an embedded vector. This
908 returns true in exactly the same circumstances that vec::reserve
911 template<typename T
, typename A
>
913 vec
<T
, A
, vl_embed
>::space (unsigned nelems
) const
915 return m_vecpfx
.m_alloc
- m_vecpfx
.m_num
>= nelems
;
919 /* Return iteration condition and update PTR to point to the IX'th
920 element of this vector. Use this to iterate over the elements of a
923 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
926 template<typename T
, typename A
>
928 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
*ptr
) const
930 if (ix
< m_vecpfx
.m_num
)
932 *ptr
= m_vecdata
[ix
];
943 /* Return iteration condition and update *PTR to point to the
944 IX'th element of this vector. Use this to iterate over the
945 elements of a vector as follows,
947 for (ix = 0; v->iterate (ix, &ptr); ix++)
950 This variant is for vectors of objects. */
952 template<typename T
, typename A
>
954 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
**ptr
) const
956 if (ix
< m_vecpfx
.m_num
)
958 *ptr
= CONST_CAST (T
*, &m_vecdata
[ix
]);
969 /* Return a pointer to a copy of this vector. */
971 template<typename T
, typename A
>
972 inline vec
<T
, A
, vl_embed
> *
973 vec
<T
, A
, vl_embed
>::copy (ALONE_MEM_STAT_DECL
) const
975 vec
<T
, A
, vl_embed
> *new_vec
= NULL
;
976 unsigned len
= length ();
979 vec_alloc (new_vec
, len PASS_MEM_STAT
);
980 new_vec
->embedded_init (len
, len
);
981 vec_copy_construct (new_vec
->address (), m_vecdata
, len
);
987 /* Copy the elements from SRC to the end of this vector as if by memcpy.
988 The vector must have sufficient headroom available. */
990 template<typename T
, typename A
>
992 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> &src
)
994 unsigned len
= src
.length ();
997 gcc_checking_assert (space (len
));
998 vec_copy_construct (end (), src
.address (), len
);
999 m_vecpfx
.m_num
+= len
;
1003 template<typename T
, typename A
>
1005 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> *src
)
1012 /* Push OBJ (a new element) onto the end of the vector. There must be
1013 sufficient space in the vector. Return a pointer to the slot
1014 where OBJ was inserted. */
1016 template<typename T
, typename A
>
1018 vec
<T
, A
, vl_embed
>::quick_push (const T
&obj
)
1020 gcc_checking_assert (space (1));
1021 T
*slot
= &m_vecdata
[m_vecpfx
.m_num
++];
1027 /* Pop and return the last element off the end of the vector. */
1029 template<typename T
, typename A
>
1031 vec
<T
, A
, vl_embed
>::pop (void)
1033 gcc_checking_assert (length () > 0);
1034 return m_vecdata
[--m_vecpfx
.m_num
];
1038 /* Set the length of the vector to SIZE. The new length must be less
1039 than or equal to the current length. This is an O(1) operation. */
1041 template<typename T
, typename A
>
1043 vec
<T
, A
, vl_embed
>::truncate (unsigned size
)
1045 gcc_checking_assert (length () >= size
);
1046 m_vecpfx
.m_num
= size
;
1050 /* Insert an element, OBJ, at the IXth position of this vector. There
1051 must be sufficient space. */
1053 template<typename T
, typename A
>
1055 vec
<T
, A
, vl_embed
>::quick_insert (unsigned ix
, const T
&obj
)
1057 gcc_checking_assert (length () < allocated ());
1058 gcc_checking_assert (ix
<= length ());
1059 T
*slot
= &m_vecdata
[ix
];
1060 memmove (slot
+ 1, slot
, (m_vecpfx
.m_num
++ - ix
) * sizeof (T
));
1065 /* Remove an element from the IXth position of this vector. Ordering of
1066 remaining elements is preserved. This is an O(N) operation due to
1069 template<typename T
, typename A
>
1071 vec
<T
, A
, vl_embed
>::ordered_remove (unsigned ix
)
1073 gcc_checking_assert (ix
< length ());
1074 T
*slot
= &m_vecdata
[ix
];
1075 memmove (slot
, slot
+ 1, (--m_vecpfx
.m_num
- ix
) * sizeof (T
));
1079 /* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1080 remaining elements is preserved. This is an O(N) operation. */
1082 #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1083 elem_ptr, start, end, cond) \
1085 gcc_assert ((end) <= (vec).length ()); \
1086 for (read_index = write_index = (start); read_index < (end); \
1089 elem_ptr = &(vec)[read_index]; \
1090 bool remove_p = (cond); \
1094 if (read_index != write_index) \
1095 (vec)[write_index] = (vec)[read_index]; \
1100 if (read_index - write_index > 0) \
1101 (vec).block_remove (write_index, read_index - write_index); \
1105 /* Remove elements from VEC for which COND holds. Ordering of remaining
1106 elements is preserved. This is an O(N) operation. */
1108 #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1110 VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1111 elem_ptr, 0, (vec).length (), (cond))
1113 /* Remove an element from the IXth position of this vector. Ordering of
1114 remaining elements is destroyed. This is an O(1) operation. */
1116 template<typename T
, typename A
>
1118 vec
<T
, A
, vl_embed
>::unordered_remove (unsigned ix
)
1120 gcc_checking_assert (ix
< length ());
1121 m_vecdata
[ix
] = m_vecdata
[--m_vecpfx
.m_num
];
1125 /* Remove LEN elements starting at the IXth. Ordering is retained.
1126 This is an O(N) operation due to memmove. */
1128 template<typename T
, typename A
>
1130 vec
<T
, A
, vl_embed
>::block_remove (unsigned ix
, unsigned len
)
1132 gcc_checking_assert (ix
+ len
<= length ());
1133 T
*slot
= &m_vecdata
[ix
];
1134 m_vecpfx
.m_num
-= len
;
1135 memmove (slot
, slot
+ len
, (m_vecpfx
.m_num
- ix
) * sizeof (T
));
1139 /* Sort the contents of this vector with qsort. CMP is the comparison
1140 function to pass to qsort. */
1142 template<typename T
, typename A
>
1144 vec
<T
, A
, vl_embed
>::qsort (int (*cmp
) (const void *, const void *))
1147 gcc_qsort (address (), length (), sizeof (T
), cmp
);
1150 /* Sort the contents of this vector with qsort. CMP is the comparison
1151 function to pass to qsort. */
1153 template<typename T
, typename A
>
1155 vec
<T
, A
, vl_embed
>::sort (int (*cmp
) (const void *, const void *, void *),
1159 gcc_sort_r (address (), length (), sizeof (T
), cmp
, data
);
1162 /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1163 comparison function to pass to qsort. */
1165 template<typename T
, typename A
>
1167 vec
<T
, A
, vl_embed
>::stablesort (int (*cmp
) (const void *, const void *,
1168 void *), void *data
)
1171 gcc_stablesort_r (address (), length (), sizeof (T
), cmp
, data
);
1174 /* Search the contents of the sorted vector with a binary search.
1175 CMP is the comparison function to pass to bsearch. */
1177 template<typename T
, typename A
>
1179 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
1180 int (*compar
) (const void *, const void *))
1182 const void *base
= this->address ();
1183 size_t nmemb
= this->length ();
1184 size_t size
= sizeof (T
);
1185 /* The following is a copy of glibc stdlib-bsearch.h. */
1195 p
= (const void *) (((const char *) base
) + (idx
* size
));
1196 comparison
= (*compar
) (key
, p
);
1199 else if (comparison
> 0)
1202 return (T
*)const_cast<void *>(p
);
1208 /* Search the contents of the sorted vector with a binary search.
1209 CMP is the comparison function to pass to bsearch. */
1211 template<typename T
, typename A
>
1213 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
1214 int (*compar
) (const void *, const void *,
1215 void *), void *data
)
1217 const void *base
= this->address ();
1218 size_t nmemb
= this->length ();
1219 size_t size
= sizeof (T
);
1220 /* The following is a copy of glibc stdlib-bsearch.h. */
1230 p
= (const void *) (((const char *) base
) + (idx
* size
));
1231 comparison
= (*compar
) (key
, p
, data
);
1234 else if (comparison
> 0)
1237 return (T
*)const_cast<void *>(p
);
1243 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1244 size of the vector and so should be used with care. */
1246 template<typename T
, typename A
>
1248 vec
<T
, A
, vl_embed
>::contains (const T
&search
) const
1250 unsigned int len
= length ();
1251 for (unsigned int i
= 0; i
< len
; i
++)
1252 if ((*this)[i
] == search
)
1258 /* Find and return the first position in which OBJ could be inserted
1259 without changing the ordering of this vector. LESSTHAN is a
1260 function that returns true if the first argument is strictly less
1263 template<typename T
, typename A
>
1265 vec
<T
, A
, vl_embed
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&))
1268 unsigned int len
= length ();
1269 unsigned int half
, middle
;
1270 unsigned int first
= 0;
1276 T middle_elem
= (*this)[middle
];
1277 if (lessthan (middle_elem
, obj
))
1281 len
= len
- half
- 1;
1290 /* Return the number of bytes needed to embed an instance of an
1291 embeddable vec inside another data structure.
1293 Use these methods to determine the required size and initialization
1294 of a vector V of type T embedded within another structure (as the
1297 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1298 void v->embedded_init (unsigned alloc, unsigned num);
1300 These allow the caller to perform the memory allocation. */
1302 template<typename T
, typename A
>
1304 vec
<T
, A
, vl_embed
>::embedded_size (unsigned alloc
)
1306 struct alignas (T
) U
{ char data
[sizeof (T
)]; };
1307 typedef vec
<U
, A
, vl_embed
> vec_embedded
;
1308 typedef typename
std::conditional
<std::is_standard_layout
<T
>::value
,
1309 vec
, vec_embedded
>::type vec_stdlayout
;
1310 static_assert (sizeof (vec_stdlayout
) == sizeof (vec
), "");
1311 static_assert (alignof (vec_stdlayout
) == alignof (vec
), "");
1312 return offsetof (vec_stdlayout
, m_vecdata
) + alloc
* sizeof (T
);
1316 /* Initialize the vector to contain room for ALLOC elements and
1317 NUM active elements. */
1319 template<typename T
, typename A
>
1321 vec
<T
, A
, vl_embed
>::embedded_init (unsigned alloc
, unsigned num
, unsigned aut
)
1323 m_vecpfx
.m_alloc
= alloc
;
1324 m_vecpfx
.m_using_auto_storage
= aut
;
1325 m_vecpfx
.m_num
= num
;
1329 /* Grow the vector to a specific length. LEN must be as long or longer than
1330 the current length. The new elements are uninitialized. */
1332 template<typename T
, typename A
>
1334 vec
<T
, A
, vl_embed
>::quick_grow (unsigned len
)
1336 gcc_checking_assert (length () <= len
&& len
<= m_vecpfx
.m_alloc
);
1337 m_vecpfx
.m_num
= len
;
1341 /* Grow the vector to a specific length. LEN must be as long or longer than
1342 the current length. The new elements are initialized to zero. */
1344 template<typename T
, typename A
>
1346 vec
<T
, A
, vl_embed
>::quick_grow_cleared (unsigned len
)
1348 unsigned oldlen
= length ();
1349 size_t growby
= len
- oldlen
;
1352 vec_default_construct (address () + oldlen
, growby
);
1355 /* Garbage collection support for vec<T, A, vl_embed>. */
1357 template<typename T
>
1359 gt_ggc_mx (vec
<T
, va_gc
> *v
)
1361 extern void gt_ggc_mx (T
&);
1362 for (unsigned i
= 0; i
< v
->length (); i
++)
1363 gt_ggc_mx ((*v
)[i
]);
1366 template<typename T
>
1368 gt_ggc_mx (vec
<T
, va_gc_atomic
, vl_embed
> *v ATTRIBUTE_UNUSED
)
1370 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1375 /* PCH support for vec<T, A, vl_embed>. */
1377 template<typename T
, typename A
>
1379 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
)
1381 extern void gt_pch_nx (T
&);
1382 for (unsigned i
= 0; i
< v
->length (); i
++)
1383 gt_pch_nx ((*v
)[i
]);
1386 template<typename T
, typename A
>
1388 gt_pch_nx (vec
<T
*, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1390 for (unsigned i
= 0; i
< v
->length (); i
++)
1391 op (&((*v
)[i
]), NULL
, cookie
);
1394 template<typename T
, typename A
>
1396 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1398 extern void gt_pch_nx (T
*, gt_pointer_operator
, void *);
1399 for (unsigned i
= 0; i
< v
->length (); i
++)
1400 gt_pch_nx (&((*v
)[i
]), op
, cookie
);
1404 /* Space efficient vector. These vectors can grow dynamically and are
1405 allocated together with their control data. They are suited to be
1406 included in data structures. Prior to initial allocation, they
1407 only take a single word of storage.
1409 These vectors are implemented as a pointer to an embeddable vector.
1410 The semantics allow for this pointer to be NULL to represent empty
1411 vectors. This way, empty vectors occupy minimal space in the
1412 structure containing them.
1416 - The whole vector and control data are allocated in a single
1418 - The whole vector may be re-allocated.
1419 - Vector data may grow and shrink.
1420 - Access and manipulation requires a pointer test and
1422 - It requires 1 word of storage (prior to vector allocation).
1427 These vectors must be PODs because they are stored in unions.
1428 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1429 As long as we use C++03, we cannot have constructors nor
1430 destructors in classes that are stored in unions. */
1432 template<typename T
, size_t N
= 0>
1435 template<typename T
>
1436 struct vec
<T
, va_heap
, vl_ptr
>
1439 /* Default ctors to ensure triviality. Use value-initialization
1440 (e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1443 vec (const vec
&) = default;
1444 /* Initialization from the generic vNULL. */
1445 vec (vnull
): m_vec () { }
1446 /* Same as default ctor: vec storage must be released manually. */
1449 /* Defaulted same as copy ctor. */
1450 vec
& operator= (const vec
&) = default;
1452 /* Prevent implicit conversion from auto_vec. Use auto_vec::to_vec()
1455 vec (auto_vec
<T
, N
> &) = delete;
1458 void operator= (auto_vec
<T
, N
> &) = delete;
1460 /* Memory allocation and deallocation for the embedded vector.
1461 Needed because we cannot have proper ctors/dtors defined. */
1462 void create (unsigned nelems CXX_MEM_STAT_INFO
);
1463 void release (void);
1465 /* Vector operations. */
1466 bool exists (void) const
1467 { return m_vec
!= NULL
; }
1469 bool is_empty (void) const
1470 { return m_vec
? m_vec
->is_empty () : true; }
1472 unsigned length (void) const
1473 { return m_vec
? m_vec
->length () : 0; }
1476 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1478 const T
*address (void) const
1479 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1481 T
*begin () { return address (); }
1482 const T
*begin () const { return address (); }
1483 T
*end () { return begin () + length (); }
1484 const T
*end () const { return begin () + length (); }
1485 const T
&operator[] (unsigned ix
) const
1486 { return (*m_vec
)[ix
]; }
1488 bool operator!=(const vec
&other
) const
1489 { return !(*this == other
); }
1491 bool operator==(const vec
&other
) const
1492 { return address () == other
.address (); }
1494 T
&operator[] (unsigned ix
)
1495 { return (*m_vec
)[ix
]; }
1498 { return m_vec
->last (); }
1500 bool space (int nelems
) const
1501 { return m_vec
? m_vec
->space (nelems
) : nelems
== 0; }
1503 bool iterate (unsigned ix
, T
*p
) const;
1504 bool iterate (unsigned ix
, T
**p
) const;
1505 vec
copy (ALONE_CXX_MEM_STAT_INFO
) const;
1506 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO
);
1507 bool reserve_exact (unsigned CXX_MEM_STAT_INFO
);
1508 void splice (const vec
&);
1509 void safe_splice (const vec
& CXX_MEM_STAT_INFO
);
1510 T
*quick_push (const T
&);
1511 T
*safe_push (const T
&CXX_MEM_STAT_INFO
);
1513 void truncate (unsigned);
1514 void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO
);
1515 void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO
);
1516 void quick_grow (unsigned);
1517 void quick_grow_cleared (unsigned);
1518 void quick_insert (unsigned, const T
&);
1519 void safe_insert (unsigned, const T
& CXX_MEM_STAT_INFO
);
1520 void ordered_remove (unsigned);
1521 void unordered_remove (unsigned);
1522 void block_remove (unsigned, unsigned);
1523 void qsort (int (*) (const void *, const void *));
1524 void sort (int (*) (const void *, const void *, void *), void *);
1525 void stablesort (int (*) (const void *, const void *, void *), void *);
1526 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
1527 T
*bsearch (const void *key
,
1528 int (*compar
)(const void *, const void *, void *), void *);
1529 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
1530 bool contains (const T
&search
) const;
1531 void reverse (void);
1533 bool using_auto_storage () const;
1535 /* FIXME - This field should be private, but we need to cater to
1536 compilers that have stricter notions of PODness for types. */
1537 vec
<T
, va_heap
, vl_embed
> *m_vec
;
1541 /* auto_vec is a subclass of vec that automatically manages creating and
1542 releasing the internal vector. If N is non zero then it has N elements of
1543 internal storage. The default is no internal storage, and you probably only
1544 want to ask for internal storage for vectors on the stack because if the
1545 size of the vector is larger than the internal storage that space is wasted.
1547 template<typename T
, size_t N
/* = 0 */>
1548 class auto_vec
: public vec
<T
, va_heap
>
1553 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1554 this->m_vec
= &m_auto
;
1557 auto_vec (size_t s CXX_MEM_STAT_INFO
)
1561 this->create (s PASS_MEM_STAT
);
1565 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1566 this->m_vec
= &m_auto
;
1574 /* Explicitly convert to the base class. There is no conversion
1575 from a const auto_vec because a copy of the returned vec can
1576 be used to modify *THIS.
1577 This is a legacy function not to be used in new code. */
1578 vec
<T
, va_heap
> to_vec_legacy () {
1579 return *static_cast<vec
<T
, va_heap
> *>(this);
1583 vec
<T
, va_heap
, vl_embed
> m_auto
;
1584 T m_data
[MAX (N
- 1, 1)];
1587 /* auto_vec is a sub class of vec whose storage is released when it is
1589 template<typename T
>
1590 class auto_vec
<T
, 0> : public vec
<T
, va_heap
>
1593 auto_vec () { this->m_vec
= NULL
; }
1594 auto_vec (size_t n CXX_MEM_STAT_INFO
) { this->create (n PASS_MEM_STAT
); }
1595 ~auto_vec () { this->release (); }
1597 auto_vec (vec
<T
, va_heap
>&& r
)
1599 gcc_assert (!r
.using_auto_storage ());
1600 this->m_vec
= r
.m_vec
;
1604 auto_vec (auto_vec
<T
> &&r
)
1606 gcc_assert (!r
.using_auto_storage ());
1607 this->m_vec
= r
.m_vec
;
1611 auto_vec
& operator= (vec
<T
, va_heap
>&& r
)
1616 gcc_assert (!r
.using_auto_storage ());
1618 this->m_vec
= r
.m_vec
;
1623 auto_vec
& operator= (auto_vec
<T
> &&r
)
1628 gcc_assert (!r
.using_auto_storage ());
1630 this->m_vec
= r
.m_vec
;
1635 /* Explicitly convert to the base class. There is no conversion
1636 from a const auto_vec because a copy of the returned vec can
1637 be used to modify *THIS.
1638 This is a legacy function not to be used in new code. */
1639 vec
<T
, va_heap
> to_vec_legacy () {
1640 return *static_cast<vec
<T
, va_heap
> *>(this);
1643 // You probably don't want to copy a vector, so these are deleted to prevent
1644 // unintentional use. If you really need a copy of the vectors contents you
1646 auto_vec(const auto_vec
&) = delete;
1647 auto_vec
&operator= (const auto_vec
&) = delete;
1651 /* Allocate heap memory for pointer V and create the internal vector
1652 with space for NELEMS elements. If NELEMS is 0, the internal
1653 vector is initialized to empty. */
1655 template<typename T
>
1657 vec_alloc (vec
<T
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
1660 v
->create (nelems PASS_MEM_STAT
);
1664 /* A subclass of auto_vec <char *> that frees all of its elements on
1667 class auto_string_vec
: public auto_vec
<char *>
1670 ~auto_string_vec ();
1673 /* A subclass of auto_vec <T *> that deletes all of its elements on
1676 This is a crude way for a vec to "own" the objects it points to
1677 and clean up automatically.
1679 For example, no attempt is made to delete elements when an item
1680 within the vec is overwritten.
1682 We can't rely on gnu::unique_ptr within a container,
1683 since we can't rely on move semantics in C++98. */
1685 template <typename T
>
1686 class auto_delete_vec
: public auto_vec
<T
*>
1689 auto_delete_vec () {}
1690 auto_delete_vec (size_t s
) : auto_vec
<T
*> (s
) {}
1692 ~auto_delete_vec ();
1695 DISABLE_COPY_AND_ASSIGN(auto_delete_vec
);
1698 /* Conditionally allocate heap memory for VEC and its internal vector. */
1700 template<typename T
>
1702 vec_check_alloc (vec
<T
, va_heap
> *&vec
, unsigned nelems CXX_MEM_STAT_INFO
)
1705 vec_alloc (vec
, nelems PASS_MEM_STAT
);
1709 /* Free the heap memory allocated by vector V and set it to NULL. */
1711 template<typename T
>
1713 vec_free (vec
<T
> *&v
)
1724 /* Return iteration condition and update PTR to point to the IX'th
1725 element of this vector. Use this to iterate over the elements of a
1728 for (ix = 0; v.iterate (ix, &ptr); ix++)
1731 template<typename T
>
1733 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
*ptr
) const
1736 return m_vec
->iterate (ix
, ptr
);
1745 /* Return iteration condition and update *PTR to point to the
1746 IX'th element of this vector. Use this to iterate over the
1747 elements of a vector as follows,
1749 for (ix = 0; v->iterate (ix, &ptr); ix++)
1752 This variant is for vectors of objects. */
1754 template<typename T
>
1756 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
**ptr
) const
1759 return m_vec
->iterate (ix
, ptr
);
1768 /* Convenience macro for forward iteration. */
1769 #define FOR_EACH_VEC_ELT(V, I, P) \
1770 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1772 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1773 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1775 /* Likewise, but start from FROM rather than 0. */
1776 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1777 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1779 /* Convenience macro for reverse iteration. */
1780 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1781 for (I = (V).length () - 1; \
1782 (V).iterate ((I), &(P)); \
1785 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1786 for (I = vec_safe_length (V) - 1; \
1787 vec_safe_iterate ((V), (I), &(P)); \
1790 /* auto_string_vec's dtor, freeing all contained strings, automatically
1791 chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1794 auto_string_vec::~auto_string_vec ()
1798 FOR_EACH_VEC_ELT (*this, i
, str
)
1802 /* auto_delete_vec's dtor, deleting all contained items, automatically
1803 chaining up to ~auto_vec <T*>, which frees the internal buffer. */
1805 template <typename T
>
1807 auto_delete_vec
<T
>::~auto_delete_vec ()
1811 FOR_EACH_VEC_ELT (*this, i
, item
)
1816 /* Return a copy of this vector. */
1818 template<typename T
>
1819 inline vec
<T
, va_heap
, vl_ptr
>
1820 vec
<T
, va_heap
, vl_ptr
>::copy (ALONE_MEM_STAT_DECL
) const
1822 vec
<T
, va_heap
, vl_ptr
> new_vec
{ };
1824 new_vec
.m_vec
= m_vec
->copy (ALONE_PASS_MEM_STAT
);
1829 /* Ensure that the vector has at least RESERVE slots available (if
1830 EXACT is false), or exactly RESERVE slots available (if EXACT is
1833 This may create additional headroom if EXACT is false.
1835 Note that this can cause the embedded vector to be reallocated.
1836 Returns true iff reallocation actually occurred. */
1838 template<typename T
>
1840 vec
<T
, va_heap
, vl_ptr
>::reserve (unsigned nelems
, bool exact MEM_STAT_DECL
)
1845 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1846 this is necessary because it doesn't have enough information to know the
1847 embedded vector is in auto storage, and so should not be freed. */
1848 vec
<T
, va_heap
, vl_embed
> *oldvec
= m_vec
;
1849 unsigned int oldsize
= 0;
1850 bool handle_auto_vec
= m_vec
&& using_auto_storage ();
1851 if (handle_auto_vec
)
1854 oldsize
= oldvec
->length ();
1858 va_heap::reserve (m_vec
, nelems
, exact PASS_MEM_STAT
);
1859 if (handle_auto_vec
)
1861 vec_copy_construct (m_vec
->address (), oldvec
->address (), oldsize
);
1862 m_vec
->m_vecpfx
.m_num
= oldsize
;
1869 /* Ensure that this vector has exactly NELEMS slots available. This
1870 will not create additional headroom. Note this can cause the
1871 embedded vector to be reallocated. Returns true iff reallocation
1872 actually occurred. */
1874 template<typename T
>
1876 vec
<T
, va_heap
, vl_ptr
>::reserve_exact (unsigned nelems MEM_STAT_DECL
)
1878 return reserve (nelems
, true PASS_MEM_STAT
);
1882 /* Create the internal vector and reserve NELEMS for it. This is
1883 exactly like vec::reserve, but the internal vector is
1884 unconditionally allocated from scratch. The old one, if it
1885 existed, is lost. */
1887 template<typename T
>
1889 vec
<T
, va_heap
, vl_ptr
>::create (unsigned nelems MEM_STAT_DECL
)
1893 reserve_exact (nelems PASS_MEM_STAT
);
1897 /* Free the memory occupied by the embedded vector. */
1899 template<typename T
>
1901 vec
<T
, va_heap
, vl_ptr
>::release (void)
1906 if (using_auto_storage ())
1908 m_vec
->m_vecpfx
.m_num
= 0;
1912 va_heap::release (m_vec
);
1915 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1916 SRC and this vector must be allocated with the same memory
1917 allocation mechanism. This vector is assumed to have sufficient
1918 headroom available. */
1920 template<typename T
>
1922 vec
<T
, va_heap
, vl_ptr
>::splice (const vec
<T
, va_heap
, vl_ptr
> &src
)
1925 m_vec
->splice (*(src
.m_vec
));
1929 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1930 SRC and this vector must be allocated with the same mechanism.
1931 If there is not enough headroom in this vector, it will be reallocated
1934 template<typename T
>
1936 vec
<T
, va_heap
, vl_ptr
>::safe_splice (const vec
<T
, va_heap
, vl_ptr
> &src
1941 reserve_exact (src
.length ());
1947 /* Push OBJ (a new element) onto the end of the vector. There must be
1948 sufficient space in the vector. Return a pointer to the slot
1949 where OBJ was inserted. */
1951 template<typename T
>
1953 vec
<T
, va_heap
, vl_ptr
>::quick_push (const T
&obj
)
1955 return m_vec
->quick_push (obj
);
1959 /* Push a new element OBJ onto the end of this vector. Reallocates
1960 the embedded vector, if needed. Return a pointer to the slot where
1961 OBJ was inserted. */
1963 template<typename T
>
1965 vec
<T
, va_heap
, vl_ptr
>::safe_push (const T
&obj MEM_STAT_DECL
)
1967 reserve (1, false PASS_MEM_STAT
);
1968 return quick_push (obj
);
1972 /* Pop and return the last element off the end of the vector. */
1974 template<typename T
>
1976 vec
<T
, va_heap
, vl_ptr
>::pop (void)
1978 return m_vec
->pop ();
1982 /* Set the length of the vector to LEN. The new length must be less
1983 than or equal to the current length. This is an O(1) operation. */
1985 template<typename T
>
1987 vec
<T
, va_heap
, vl_ptr
>::truncate (unsigned size
)
1990 m_vec
->truncate (size
);
1992 gcc_checking_assert (size
== 0);
1996 /* Grow the vector to a specific length. LEN must be as long or
1997 longer than the current length. The new elements are
1998 uninitialized. Reallocate the internal vector, if needed. */
2000 template<typename T
>
2002 vec
<T
, va_heap
, vl_ptr
>::safe_grow (unsigned len
, bool exact MEM_STAT_DECL
)
2004 unsigned oldlen
= length ();
2005 gcc_checking_assert (oldlen
<= len
);
2006 reserve (len
- oldlen
, exact PASS_MEM_STAT
);
2008 m_vec
->quick_grow (len
);
2010 gcc_checking_assert (len
== 0);
2014 /* Grow the embedded vector to a specific length. LEN must be as
2015 long or longer than the current length. The new elements are
2016 initialized to zero. Reallocate the internal vector, if needed. */
2018 template<typename T
>
2020 vec
<T
, va_heap
, vl_ptr
>::safe_grow_cleared (unsigned len
, bool exact
2023 unsigned oldlen
= length ();
2024 size_t growby
= len
- oldlen
;
2025 safe_grow (len
, exact PASS_MEM_STAT
);
2027 vec_default_construct (address () + oldlen
, growby
);
2031 /* Same as vec::safe_grow but without reallocation of the internal vector.
2032 If the vector cannot be extended, a runtime assertion will be triggered. */
2034 template<typename T
>
2036 vec
<T
, va_heap
, vl_ptr
>::quick_grow (unsigned len
)
2038 gcc_checking_assert (m_vec
);
2039 m_vec
->quick_grow (len
);
2043 /* Same as vec::quick_grow_cleared but without reallocation of the
2044 internal vector. If the vector cannot be extended, a runtime
2045 assertion will be triggered. */
2047 template<typename T
>
2049 vec
<T
, va_heap
, vl_ptr
>::quick_grow_cleared (unsigned len
)
2051 gcc_checking_assert (m_vec
);
2052 m_vec
->quick_grow_cleared (len
);
2056 /* Insert an element, OBJ, at the IXth position of this vector. There
2057 must be sufficient space. */
2059 template<typename T
>
2061 vec
<T
, va_heap
, vl_ptr
>::quick_insert (unsigned ix
, const T
&obj
)
2063 m_vec
->quick_insert (ix
, obj
);
2067 /* Insert an element, OBJ, at the IXth position of the vector.
2068 Reallocate the embedded vector, if necessary. */
2070 template<typename T
>
2072 vec
<T
, va_heap
, vl_ptr
>::safe_insert (unsigned ix
, const T
&obj MEM_STAT_DECL
)
2074 reserve (1, false PASS_MEM_STAT
);
2075 quick_insert (ix
, obj
);
2079 /* Remove an element from the IXth position of this vector. Ordering of
2080 remaining elements is preserved. This is an O(N) operation due to
2083 template<typename T
>
2085 vec
<T
, va_heap
, vl_ptr
>::ordered_remove (unsigned ix
)
2087 m_vec
->ordered_remove (ix
);
2091 /* Remove an element from the IXth position of this vector. Ordering
2092 of remaining elements is destroyed. This is an O(1) operation. */
2094 template<typename T
>
2096 vec
<T
, va_heap
, vl_ptr
>::unordered_remove (unsigned ix
)
2098 m_vec
->unordered_remove (ix
);
2102 /* Remove LEN elements starting at the IXth. Ordering is retained.
2103 This is an O(N) operation due to memmove. */
2105 template<typename T
>
2107 vec
<T
, va_heap
, vl_ptr
>::block_remove (unsigned ix
, unsigned len
)
2109 m_vec
->block_remove (ix
, len
);
2113 /* Sort the contents of this vector with qsort. CMP is the comparison
2114 function to pass to qsort. */
2116 template<typename T
>
2118 vec
<T
, va_heap
, vl_ptr
>::qsort (int (*cmp
) (const void *, const void *))
2124 /* Sort the contents of this vector with qsort. CMP is the comparison
2125 function to pass to qsort. */
2127 template<typename T
>
2129 vec
<T
, va_heap
, vl_ptr
>::sort (int (*cmp
) (const void *, const void *,
2130 void *), void *data
)
2133 m_vec
->sort (cmp
, data
);
2136 /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
2137 comparison function to pass to qsort. */
2139 template<typename T
>
2141 vec
<T
, va_heap
, vl_ptr
>::stablesort (int (*cmp
) (const void *, const void *,
2142 void *), void *data
)
2145 m_vec
->stablesort (cmp
, data
);
2148 /* Search the contents of the sorted vector with a binary search.
2149 CMP is the comparison function to pass to bsearch. */
2151 template<typename T
>
2153 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
2154 int (*cmp
) (const void *, const void *))
2157 return m_vec
->bsearch (key
, cmp
);
2161 /* Search the contents of the sorted vector with a binary search.
2162 CMP is the comparison function to pass to bsearch. */
2164 template<typename T
>
2166 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
2167 int (*cmp
) (const void *, const void *,
2168 void *), void *data
)
2171 return m_vec
->bsearch (key
, cmp
, data
);
2176 /* Find and return the first position in which OBJ could be inserted
2177 without changing the ordering of this vector. LESSTHAN is a
2178 function that returns true if the first argument is strictly less
2181 template<typename T
>
2183 vec
<T
, va_heap
, vl_ptr
>::lower_bound (T obj
,
2184 bool (*lessthan
)(const T
&, const T
&))
2187 return m_vec
? m_vec
->lower_bound (obj
, lessthan
) : 0;
2190 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
2191 size of the vector and so should be used with care. */
2193 template<typename T
>
2195 vec
<T
, va_heap
, vl_ptr
>::contains (const T
&search
) const
2197 return m_vec
? m_vec
->contains (search
) : false;
2200 /* Reverse content of the vector. */
2202 template<typename T
>
2204 vec
<T
, va_heap
, vl_ptr
>::reverse (void)
2206 unsigned l
= length ();
2207 T
*ptr
= address ();
2209 for (unsigned i
= 0; i
< l
/ 2; i
++)
2210 std::swap (ptr
[i
], ptr
[l
- i
- 1]);
2213 template<typename T
>
2215 vec
<T
, va_heap
, vl_ptr
>::using_auto_storage () const
2217 return m_vec
? m_vec
->m_vecpfx
.m_using_auto_storage
: false;
2220 /* Release VEC and call release of all element vectors. */
2222 template<typename T
>
2224 release_vec_vec (vec
<vec
<T
> > &vec
)
2226 for (unsigned i
= 0; i
< vec
.length (); i
++)
2232 // Provide a subset of the std::span functionality. (We can't use std::span
2233 // itself because it's a C++20 feature.)
2235 // In addition, provide an invalid value that is distinct from all valid
2236 // sequences (including the empty sequence). This can be used to return
2237 // failure without having to use std::optional.
2239 // There is no operator bool because it would be ambiguous whether it is
2240 // testing for a valid value or an empty sequence.
2241 template<typename T
>
2244 template<typename OtherT
> friend class array_slice
;
2247 using value_type
= T
;
2248 using iterator
= T
*;
2249 using const_iterator
= const T
*;
2251 array_slice () : m_base (nullptr), m_size (0) {}
2253 template<typename OtherT
>
2254 array_slice (array_slice
<OtherT
> other
)
2255 : m_base (other
.m_base
), m_size (other
.m_size
) {}
2257 array_slice (iterator base
, unsigned int size
)
2258 : m_base (base
), m_size (size
) {}
2261 array_slice (T (&array
)[N
]) : m_base (array
), m_size (N
) {}
2263 template<typename OtherT
>
2264 array_slice (const vec
<OtherT
> &v
)
2265 : m_base (v
.address ()), m_size (v
.length ()) {}
2267 iterator
begin () { return m_base
; }
2268 iterator
end () { return m_base
+ m_size
; }
2270 const_iterator
begin () const { return m_base
; }
2271 const_iterator
end () const { return m_base
+ m_size
; }
2273 value_type
&front ();
2274 value_type
&back ();
2275 value_type
&operator[] (unsigned int i
);
2277 const value_type
&front () const;
2278 const value_type
&back () const;
2279 const value_type
&operator[] (unsigned int i
) const;
2281 size_t size () const { return m_size
; }
2282 size_t size_bytes () const { return m_size
* sizeof (T
); }
2283 bool empty () const { return m_size
== 0; }
2285 // An invalid array_slice that represents a failed operation. This is
2286 // distinct from an empty slice, which is a valid result in some contexts.
2287 static array_slice
invalid () { return { nullptr, ~0U }; }
2289 // True if the array is valid, false if it is an array like INVALID.
2290 bool is_valid () const { return m_base
|| m_size
== 0; }
2294 unsigned int m_size
;
2297 template<typename T
>
2298 inline typename array_slice
<T
>::value_type
&
2299 array_slice
<T
>::front ()
2301 gcc_checking_assert (m_size
);
2305 template<typename T
>
2306 inline const typename array_slice
<T
>::value_type
&
2307 array_slice
<T
>::front () const
2309 gcc_checking_assert (m_size
);
2313 template<typename T
>
2314 inline typename array_slice
<T
>::value_type
&
2315 array_slice
<T
>::back ()
2317 gcc_checking_assert (m_size
);
2318 return m_base
[m_size
- 1];
2321 template<typename T
>
2322 inline const typename array_slice
<T
>::value_type
&
2323 array_slice
<T
>::back () const
2325 gcc_checking_assert (m_size
);
2326 return m_base
[m_size
- 1];
2329 template<typename T
>
2330 inline typename array_slice
<T
>::value_type
&
2331 array_slice
<T
>::operator[] (unsigned int i
)
2333 gcc_checking_assert (i
< m_size
);
2337 template<typename T
>
2338 inline const typename array_slice
<T
>::value_type
&
2339 array_slice
<T
>::operator[] (unsigned int i
) const
2341 gcc_checking_assert (i
< m_size
);
2345 template<typename T
>
2347 make_array_slice (T
*base
, unsigned int size
)
2349 return array_slice
<T
> (base
, size
);
2352 #if (GCC_VERSION >= 3000)
2353 # pragma GCC poison m_vec m_vecpfx m_vecdata