1	/* Vector API for GNU compiler.
2	Copyright (C) 2004-2025 Free Software Foundation, Inc.
3	Contributed by Nathan Sidwell <nathan@codesourcery.com>
4	Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5
6	This file is part of GCC.
7
8	GCC is free software; you can redistribute it and/or modify it under
9	the terms of the GNU General Public License as published by the Free
10	Software Foundation; either version 3, or (at your option) any later
11	version.
12
13	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14	WARRANTY; without even the implied warranty of MERCHANTABILITY or
15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16	for more details.
17
18	You should have received a copy of the GNU General Public License
19	along with GCC; see the file COPYING3. If not see
20	<http://www.gnu.org/licenses/>. */
21
22	#ifndef GCC_VEC_H
23	#define GCC_VEC_H
24
25	/* 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.*/
29
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);
33
34	/* Templated vector type and associated interfaces.
35
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.
39
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.
45
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.
60
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.
71
72	Vectors are template types with three arguments: the type of the
73	elements in the vector, the allocation strategy, and the physical
74	layout to use
75
76	Four allocation strategies are supported:
77
78	- Heap: allocation is done using malloc/free. This is the
79	default allocation strategy.
80
81	- GC: allocation is done using ggc_alloc/ggc_free.
82
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
88	GC activities.
89
90	Two physical layouts are supported:
91
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).
98
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
104	need to relocate).
105
106	The type, allocation and layout are specified when the vector is
107	declared.
108
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.
113
114	Not all vector operations support non-POD types and such restrictions
115	are enforced through static assertions. Some operations which often use
116	memmove to move elements around like quick_insert, safe_insert,
117	ordered_remove, unordered_remove, block_remove etc. require trivially
118	copyable types. Sorting operations, qsort, sort and stablesort, require
119	those too but as an extension allow also std::pair of 2 trivially copyable
120	types which happens to work even when std::pair itself isn't trivially
121	copyable. The quick_grow and safe_grow operations require trivially
122	default constructible types. One can use quick_grow_cleared or
123	safe_grow_cleared for non-trivially default constructible types if needed
124	(but of course such operation is more expensive then). The pop operation
125	returns reference to the last element only for trivially destructible
126	types, for non-trivially destructible types one should use last operation
127	followed by pop which in that case returns void.
128	And finally, the GC and GC atomic vectors should always be used with
129	trivially destructible types, as nothing will invoke destructors when they
130	are freed during GC.
131
132	Notes on the different layout strategies
133
134	* Embeddable vectors (vec<T, A, vl_embed>)
135
136	These vectors are suitable to be embedded in other data
137	structures so that they can be pre-allocated in a contiguous
138	memory block.
139
140	Embeddable vectors are implemented using the trailing array
141	idiom, thus they are not resizeable without changing the address
142	of the vector object itself. This means you cannot have
143	variables or fields of embeddable vector type -- always use a
144	pointer to a vector. The one exception is the final field of a
145	structure, which could be a vector type.
146
147	You will have to use the embedded_size & embedded_init calls to
148	create such objects, and they will not be resizeable (so the
149	'safe' allocation variants are not available).
150
151	Properties of embeddable vectors:
152
153	- The whole vector and control data are allocated in a single
154	contiguous block. It uses the trailing-vector idiom, so
155	allocation must reserve enough space for all the elements
156	in the vector plus its control data.
157	- The vector cannot be re-allocated.
158	- The vector cannot grow nor shrink.
159	- No indirections needed for access/manipulation.
160	- It requires 2 words of storage (prior to vector allocation).
161
162
163	* Space efficient vector (vec<T, A, vl_ptr>)
164
165	These vectors can grow dynamically and are allocated together
166	with their control data. They are suited to be included in data
167	structures. Prior to initial allocation, they only take a single
168	word of storage.
169
170	These vectors are implemented as a pointer to embeddable vectors.
171	The semantics allow for this pointer to be NULL to represent
172	empty vectors. This way, empty vectors occupy minimal space in
173	the structure containing them.
174
175	Properties:
176
177	- The whole vector and control data are allocated in a single
178	contiguous block.
179	- The whole vector may be re-allocated.
180	- Vector data may grow and shrink.
181	- Access and manipulation requires a pointer test and
182	indirection.
183	- It requires 1 word of storage (prior to vector allocation).
184
185	An example of their use would be,
186
187	struct my_struct {
188	// A space-efficient vector of tree pointers in GC memory.
189	vec<tree, va_gc, vl_ptr> v;
190	};
191
192	struct my_struct *s;
193
194	if (s->v.length ()) { we have some contents }
195	s->v.safe_push (decl); // append some decl onto the end
196	for (ix = 0; s->v.iterate (ix, &elt); ix++)
197	{ do something with elt }
198	*/
199
200	/* Support function for statistics. */
201	extern void dump_vec_loc_statistics (void);
202
203	/* Hashtable mapping vec addresses to descriptors. */
204	extern htab_t vec_mem_usage_hash;
205
206	/* Destruct N elements in DST. */
207
208	template <typename T>
209	inline void
210	vec_destruct (T *dst, unsigned n)
211	{
212	for ( ; n; ++dst, --n)
213	dst->~T ();
214	}
215
216	/* Control data for vectors. This contains the number of allocated
217	and used slots inside a vector. */
218
219	struct vec_prefix
220	{
221	/* FIXME - These fields should be private, but we need to cater to
222	compilers that have stricter notions of PODness for types. */
223
224	/* Memory allocation support routines in vec.cc. */
225	void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
226	void release_overhead (void *, size_t, size_t, bool CXX_MEM_STAT_INFO);
227	static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
228	static unsigned calculate_allocation_1 (unsigned, unsigned);
229
230	/* Note that vec_prefix should be a base class for vec, but we use
231	offsetof() on vector fields of tree structures (e.g.,
232	tree_binfo::base_binfos), and offsetof only supports base types.
233
234	To compensate, we make vec_prefix a field inside vec and make
235	vec a friend class of vec_prefix so it can access its fields. */
236	template <typename, typename, typename> friend struct vec;
237
238	/* The allocator types also need access to our internals. */
239	friend struct va_gc;
240	friend struct va_gc_atomic;
241	friend struct va_heap;
242
243	unsigned m_alloc : 31;
244	unsigned m_using_auto_storage : 1;
245	unsigned m_num;
246	};
247
248	/* Calculate the number of slots to reserve a vector, making sure that
249	RESERVE slots are free. If EXACT grow exactly, otherwise grow
250	exponentially. PFX is the control data for the vector. */
251
252	inline unsigned
253	vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
254	bool exact)
255	{
256	if (exact)
257	return (pfx ? pfx->m_num : 0) + reserve;
258	else if (!pfx)
259	return MAX (4, reserve);
260	return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
261	}
262
263	template<typename, typename, typename> struct vec;
264
265	/* Valid vector layouts
266
267	vl_embed - Embeddable vector that uses the trailing array idiom.
268	vl_ptr - Space efficient vector that uses a pointer to an
269	embeddable vector. */
270	struct vl_embed { };
271	struct vl_ptr { };
272
273
274	/* Types of supported allocations
275
276	va_heap - Allocation uses malloc/free.
277	va_gc - Allocation uses ggc_alloc.
278	va_gc_atomic - Same as GC, but individual elements of the array
279	do not need to be marked during collection. */
280
281	/* Allocator type for heap vectors. */
282	struct va_heap
283	{
284	/* Heap vectors are frequently regular instances, so use the vl_ptr
285	layout for them. */
286	typedef vl_ptr default_layout;
287
288	template<typename T>
289	static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
290	CXX_MEM_STAT_INFO);
291
292	template<typename T>
293	static void release (vec<T, va_heap, vl_embed> *&);
294	};
295
296
297	/* Allocator for heap memory. Ensure there are at least RESERVE free
298	slots in V. If EXACT is true, grow exactly, else grow
299	exponentially. As a special case, if the vector had not been
300	allocated and RESERVE is 0, no vector will be created. */
301
302	template<typename T>
303	inline void
304	va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
305	MEM_STAT_DECL)
306	{
307	size_t elt_size = sizeof (T);
308	unsigned alloc
309	= vec_prefix::calculate_allocation (pfx: v ? &v->m_vecpfx : 0, reserve, exact);
310	gcc_checking_assert (alloc);
311
312	if (GATHER_STATISTICS && v)
313	v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
314	v->allocated (), false);
315
316	size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
317	unsigned nelem = v ? v->length () : 0;
318	v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
319	v->embedded_init (alloc, nelem);
320
321	if (GATHER_STATISTICS)
322	v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
323	}
324
325
326	#if GCC_VERSION >= 4007
327	#pragma GCC diagnostic push
328	#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
329	#endif
330
331	/* Free the heap space allocated for vector V. */
332
333	template<typename T>
334	void
335	va_heap::release (vec<T, va_heap, vl_embed> *&v)
336	{
337	size_t elt_size = sizeof (T);
338	if (v == NULL)
339	return;
340
341	if (!std::is_trivially_destructible <T>::value)
342	vec_destruct (v->address (), v->length ());
343
344	if (GATHER_STATISTICS)
345	v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
346	v->allocated (), true);
347	::free (ptr: v);
348	v = NULL;
349	}
350
351	#if GCC_VERSION >= 4007
352	#pragma GCC diagnostic pop
353	#endif
354
355	/* Allocator type for GC vectors. Notice that we need the structure
356	declaration even if GC is not enabled. */
357
358	struct va_gc
359	{
360	/* Use vl_embed as the default layout for GC vectors. Due to GTY
361	limitations, GC vectors must always be pointers, so it is more
362	efficient to use a pointer to the vl_embed layout, rather than
363	using a pointer to a pointer as would be the case with vl_ptr. */
364	typedef vl_embed default_layout;
365
366	template<typename T, typename A>
367	static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
368	CXX_MEM_STAT_INFO);
369
370	template<typename T, typename A>
371	static void release (vec<T, A, vl_embed> *&v);
372	};
373
374
375	/* Free GC memory used by V and reset V to NULL. */
376
377	template<typename T, typename A>
378	inline void
379	va_gc::release (vec<T, A, vl_embed> *&v)
380	{
381	if (v)
382	::ggc_free (v);
383	v = NULL;
384	}
385
386
387	/* Allocator for GC memory. Ensure there are at least RESERVE free
388	slots in V. If EXACT is true, grow exactly, else grow
389	exponentially. As a special case, if the vector had not been
390	allocated and RESERVE is 0, no vector will be created. */
391
392	template<typename T, typename A>
393	void
394	va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
395	MEM_STAT_DECL)
396	{
397	unsigned alloc
398	= vec_prefix::calculate_allocation (pfx: v ? &v->m_vecpfx : 0, reserve, exact);
399	if (!alloc)
400	{
401	::ggc_free (v);
402	v = NULL;
403	return;
404	}
405
406	/* Calculate the amount of space we want. */
407	size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
408
409	/* Ask the allocator how much space it will really give us. */
410	size = ::ggc_round_alloc_size (requested_size: size);
411
412	/* Adjust the number of slots accordingly. */
413	size_t vec_offset = sizeof (vec_prefix);
414	size_t elt_size = sizeof (T);
415	alloc = (size - vec_offset) / elt_size;
416
417	/* And finally, recalculate the amount of space we ask for. */
418	size = vec_offset + alloc * elt_size;
419
420	unsigned nelem = v ? v->length () : 0;
421	v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
422	PASS_MEM_STAT));
423	v->embedded_init (alloc, nelem);
424	}
425
426
427	/* Allocator type for GC vectors. This is for vectors of types
428	atomics w.r.t. collection, so allocation and deallocation is
429	completely inherited from va_gc. */
430	struct va_gc_atomic : va_gc
431	{
432	};
433
434
435	/* Generic vector template. Default values for A and L indicate the
436	most commonly used strategies.
437
438	FIXME - Ideally, they would all be vl_ptr to encourage using regular
439	instances for vectors, but the existing GTY machinery is limited
440	in that it can only deal with GC objects that are pointers
441	themselves.
442
443	This means that vector operations that need to deal with
444	potentially NULL pointers, must be provided as free
445	functions (see the vec_safe_* functions above). */
446	template<typename T,
447	typename A = va_heap,
448	typename L = typename A::default_layout>
449	struct GTY((user)) vec
450	{
451	};
452
453	/* Allow C++11 range-based 'for' to work directly on vec<T>*. */
454	template<typename T, typename A, typename L>
455	T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
456	template<typename T, typename A, typename L>
457	T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
458	template<typename T, typename A, typename L>
459	const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
460	template<typename T, typename A, typename L>
461	const T* end (const vec<T,A,L> *v) { return v ? v->end () : nullptr; }
462
463	/* Generic vec<> debug helpers.
464
465	These need to be instantiated for each vec<TYPE> used throughout
466	the compiler like this:
467
468	DEFINE_DEBUG_VEC (TYPE)
469
470	The reason we have a debug_helper() is because GDB can't
471	disambiguate a plain call to debug(some_vec), and it must be called
472	like debug<TYPE>(some_vec). */
473
474	template<typename T>
475	void
476	debug_helper (vec<T> &ref)
477	{
478	unsigned i;
479	for (i = 0; i < ref.length (); ++i)
480	{
481	fprintf (stderr, format: "[%d] = ", i);
482	debug_slim (ref[i]);
483	fputc (c: '\n', stderr);
484	}
485	}
486
487	/* We need a separate va_gc variant here because default template
488	argument for functions cannot be used in c++-98. Once this
489	restriction is removed, those variant should be folded with the
490	above debug_helper. */
491
492	template<typename T>
493	void
494	debug_helper (vec<T, va_gc> &ref)
495	{
496	unsigned i;
497	for (i = 0; i < ref.length (); ++i)
498	{
499	fprintf (stderr, format: "[%d] = ", i);
500	debug_slim (ref[i]);
501	fputc (c: '\n', stderr);
502	}
503	}
504
505	/* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
506	functions for a type T. */
507
508	#define DEFINE_DEBUG_VEC(T) \
509	template void debug_helper (vec<T> &); \
510	template void debug_helper (vec<T, va_gc> &); \
511	/* Define the vec<T> debug functions. */ \
512	DEBUG_FUNCTION void \
513	debug (vec<T> &ref) \
514	{ \
515	debug_helper <T> (ref); \
516	} \
517	DEBUG_FUNCTION void \
518	debug (vec<T> *ptr) \
519	{ \
520	if (ptr) \
521	debug (*ptr); \
522	else \
523	fprintf (stderr, "<nil>\n"); \
524	} \
525	/* Define the vec<T, va_gc> debug functions. */ \
526	DEBUG_FUNCTION void \
527	debug (vec<T, va_gc> &ref) \
528	{ \
529	debug_helper <T> (ref); \
530	} \
531	DEBUG_FUNCTION void \
532	debug (vec<T, va_gc> *ptr) \
533	{ \
534	if (ptr) \
535	debug (*ptr); \
536	else \
537	fprintf (stderr, "<nil>\n"); \
538	}
539
540	/* Default-construct N elements in DST. */
541
542	template <typename T>
543	inline void
544	vec_default_construct (T *dst, unsigned n)
545	{
546	for ( ; n; ++dst, --n)
547	::new (static_cast<void*>(dst)) T ();
548	}
549
550	/* Copy-construct N elements in DST from *SRC. */
551
552	template <typename T>
553	inline void
554	vec_copy_construct (T *dst, const T *src, unsigned n)
555	{
556	for ( ; n; ++dst, ++src, --n)
557	::new (static_cast<void*>(dst)) T (*src);
558	}
559
560	/* Type to provide zero-initialized values for vec<T, A, L>. This is
561	used to provide nil initializers for vec instances. Since vec must
562	be a trivially copyable type that can be copied by memcpy and zeroed
563	out by memset, it must have defaulted default and copy ctor and copy
564	assignment. To initialize a vec either use value initialization
565	(e.g., vec() or vec v{ };) or assign it the value vNULL. This isn't
566	needed for file-scope and function-local static vectors, which are
567	zero-initialized by default. */
568	struct vnull { };
569	constexpr vnull vNULL{ };
570
571
572	/* Embeddable vector. These vectors are suitable to be embedded
573	in other data structures so that they can be pre-allocated in a
574	contiguous memory block.
575
576	Embeddable vectors are implemented using the trailing array idiom,
577	thus they are not resizeable without changing the address of the
578	vector object itself. This means you cannot have variables or
579	fields of embeddable vector type -- always use a pointer to a
580	vector. The one exception is the final field of a structure, which
581	could be a vector type.
582
583	You will have to use the embedded_size & embedded_init calls to
584	create such objects, and they will not be resizeable (so the 'safe'
585	allocation variants are not available).
586
587	Properties:
588
589	- The whole vector and control data are allocated in a single
590	contiguous block. It uses the trailing-vector idiom, so
591	allocation must reserve enough space for all the elements
592	in the vector plus its control data.
593	- The vector cannot be re-allocated.
594	- The vector cannot grow nor shrink.
595	- No indirections needed for access/manipulation.
596	- It requires 2 words of storage (prior to vector allocation). */
597
598	template<typename T, typename A>
599	struct GTY((user)) vec<T, A, vl_embed>
600	{
601	public:
602	unsigned allocated (void) const { return m_vecpfx.m_alloc; }
603	unsigned length (void) const { return m_vecpfx.m_num; }
604	bool is_empty (void) const { return m_vecpfx.m_num == 0; }
605	T *address (void) { return reinterpret_cast <T *> (this + 1); }
606	const T *address (void) const
607	{ return reinterpret_cast <const T *> (this + 1); }
608	T *begin () { return address (); }
609	const T *begin () const { return address (); }
610	T *end () { return address () + length (); }
611	const T *end () const { return address () + length (); }
612	const T &operator[] (unsigned) const;
613	T &operator[] (unsigned);
614	const T &last (void) const;
615	T &last (void);
616	bool space (unsigned) const;
617	bool iterate (unsigned, T *) const;
618	bool iterate (unsigned, T **) const;
619	vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
620	void splice (const vec &);
621	void splice (const vec *src);
622	T *quick_push (const T &);
623	using pop_ret_type
624	= typename std::conditional <std::is_trivially_destructible <T>::value,
625	T &, void>::type;
626	pop_ret_type pop (void);
627	void truncate (unsigned);
628	void quick_insert (unsigned, const T &);
629	void ordered_remove (unsigned);
630	void unordered_remove (unsigned);
631	void block_remove (unsigned, unsigned);
632	void qsort (int (*) (const void *, const void *));
633	void sort (int (*) (const void *, const void *, void *), void *);
634	void stablesort (int (*) (const void *, const void *, void *), void *);
635	T *bsearch (const void *key, int (*compar) (const void *, const void *));
636	T *bsearch (const void *key,
637	int (*compar)(const void *, const void *, void *), void *);
638	unsigned lower_bound (const T &, bool (*) (const T &, const T &)) const;
639	bool contains (const T &search) const;
640	static size_t embedded_size (unsigned);
641	void embedded_init (unsigned, unsigned = 0, unsigned = 0);
642	void quick_grow (unsigned len);
643	void quick_grow_cleared (unsigned len);
644
645	/* vec class can access our internal data and functions. */
646	template <typename, typename, typename> friend struct vec;
647
648	/* The allocator types also need access to our internals. */
649	friend struct va_gc;
650	friend struct va_gc_atomic;
651	friend struct va_heap;
652
653	/* FIXME - This field should be private, but we need to cater to
654	compilers that have stricter notions of PODness for types. */
655	/* Align m_vecpfx to simplify address (). */
656	alignas (T) alignas (vec_prefix) vec_prefix m_vecpfx;
657	};
658
659
660	/* Convenience wrapper functions to use when dealing with pointers to
661	embedded vectors. Some functionality for these vectors must be
662	provided via free functions for these reasons:
663
664	1- The pointer may be NULL (e.g., before initial allocation).
665
666	2- When the vector needs to grow, it must be reallocated, so
667	the pointer will change its value.
668
669	Because of limitations with the current GC machinery, all vectors
670	in GC memory *must* be pointers. */
671
672
673	/* If V contains no room for NELEMS elements, return false. Otherwise,
674	return true. */
675	template<typename T, typename A>
676	inline bool
677	vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
678	{
679	return v ? v->space (nelems) : nelems == 0;
680	}
681
682
683	/* If V is NULL, return 0. Otherwise, return V->length(). */
684	template<typename T, typename A>
685	inline unsigned
686	vec_safe_length (const vec<T, A, vl_embed> *v)
687	{
688	return v ? v->length () : 0;
689	}
690
691
692	/* If V is NULL, return NULL. Otherwise, return V->address(). */
693	template<typename T, typename A>
694	inline T *
695	vec_safe_address (vec<T, A, vl_embed> *v)
696	{
697	return v ? v->address () : NULL;
698	}
699
700
701	/* If V is NULL, return true. Otherwise, return V->is_empty(). */
702	template<typename T, typename A>
703	inline bool
704	vec_safe_is_empty (vec<T, A, vl_embed> *v)
705	{
706	return v ? v->is_empty () : true;
707	}
708
709	/* If V does not have space for NELEMS elements, call
710	V->reserve(NELEMS, EXACT). */
711	template<typename T, typename A>
712	inline bool
713	vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
714	CXX_MEM_STAT_INFO)
715	{
716	bool extend = nelems ? !vec_safe_space (v, nelems) : false;
717	if (extend)
718	A::reserve (v, nelems, exact PASS_MEM_STAT);
719	return extend;
720	}
721
722	template<typename T, typename A>
723	inline bool
724	vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
725	CXX_MEM_STAT_INFO)
726	{
727	return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
728	}
729
730
731	/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
732	is 0, V is initialized to NULL. */
733
734	template<typename T, typename A>
735	inline void
736	vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
737	{
738	v = NULL;
739	vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
740	}
741
742
743	/* Free the GC memory allocated by vector V and set it to NULL. */
744
745	template<typename T, typename A>
746	inline void
747	vec_free (vec<T, A, vl_embed> *&v)
748	{
749	A::release (v);
750	}
751
752
753	/* Grow V to length LEN. Allocate it, if necessary. */
754	template<typename T, typename A>
755	inline void
756	vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
757	bool exact = false CXX_MEM_STAT_INFO)
758	{
759	unsigned oldlen = vec_safe_length (v);
760	gcc_checking_assert (len >= oldlen);
761	vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
762	v->quick_grow (len);
763	}
764
765
766	/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
767	template<typename T, typename A>
768	inline void
769	vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
770	bool exact = false CXX_MEM_STAT_INFO)
771	{
772	unsigned oldlen = vec_safe_length (v);
773	gcc_checking_assert (len >= oldlen);
774	vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
775	v->quick_grow_cleared (len);
776	}
777
778
779	/* Assume V is not NULL. */
780
781	template<typename T>
782	inline void
783	vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
784	unsigned len, bool exact = false CXX_MEM_STAT_INFO)
785	{
786	v->safe_grow_cleared (len, exact PASS_MEM_STAT);
787	}
788
789	/* If V does not have space for NELEMS elements, call
790	V->reserve(NELEMS, EXACT). */
791
792	template<typename T>
793	inline bool
794	vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
795	CXX_MEM_STAT_INFO)
796	{
797	return v->reserve (nelems, exact);
798	}
799
800
801	/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
802	template<typename T, typename A>
803	inline bool
804	vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
805	{
806	if (v)
807	return v->iterate (ix, ptr);
808	else
809	{
810	*ptr = 0;
811	return false;
812	}
813	}
814
815	template<typename T, typename A>
816	inline bool
817	vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
818	{
819	if (v)
820	return v->iterate (ix, ptr);
821	else
822	{
823	*ptr = 0;
824	return false;
825	}
826	}
827
828
829	/* If V has no room for one more element, reallocate it. Then call
830	V->quick_push(OBJ). */
831	template<typename T, typename A>
832	inline T *
833	vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
834	{
835	vec_safe_reserve (v, 1, false PASS_MEM_STAT);
836	return v->quick_push (obj);
837	}
838
839
840	/* if V has no room for one more element, reallocate it. Then call
841	V->quick_insert(IX, OBJ). */
842	template<typename T, typename A>
843	inline void
844	vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
845	CXX_MEM_STAT_INFO)
846	{
847	vec_safe_reserve (v, 1, false PASS_MEM_STAT);
848	v->quick_insert (ix, obj);
849	}
850
851
852	/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
853	template<typename T, typename A>
854	inline void
855	vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
856	{
857	if (v)
858	v->truncate (size);
859	}
860
861
862	/* If SRC is not NULL, return a pointer to a copy of it. */
863	template<typename T, typename A>
864	inline vec<T, A, vl_embed> *
865	vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
866	{
867	return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
868	}
869
870	/* Copy the elements from SRC to the end of DST as if by memcpy.
871	Reallocate DST, if necessary. */
872	template<typename T, typename A>
873	inline void
874	vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
875	CXX_MEM_STAT_INFO)
876	{
877	unsigned src_len = vec_safe_length (src);
878	if (src_len)
879	{
880	vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
881	PASS_MEM_STAT);
882	dst->splice (*src);
883	}
884	}
885
886	/* Return true if SEARCH is an element of V. Note that this is O(N) in the
887	size of the vector and so should be used with care. */
888
889	template<typename T, typename A>
890	inline bool
891	vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
892	{
893	return v ? v->contains (search) : false;
894	}
895
896	/* Index into vector. Return the IX'th element. IX must be in the
897	domain of the vector. */
898
899	template<typename T, typename A>
900	inline const T &
901	vec<T, A, vl_embed>::operator[] (unsigned ix) const
902	{
903	gcc_checking_assert (ix < m_vecpfx.m_num);
904	return address ()[ix];
905	}
906
907	template<typename T, typename A>
908	inline T &
909	vec<T, A, vl_embed>::operator[] (unsigned ix)
910	{
911	gcc_checking_assert (ix < m_vecpfx.m_num);
912	return address ()[ix];
913	}
914
915
916	/* Get the final element of the vector, which must not be empty. */
917
918	template<typename T, typename A>
919	inline const T &
920	vec<T, A, vl_embed>::last (void) const
921	{
922	gcc_checking_assert (m_vecpfx.m_num > 0);
923	return (*this)[m_vecpfx.m_num - 1];
924	}
925
926	template<typename T, typename A>
927	inline T &
928	vec<T, A, vl_embed>::last (void)
929	{
930	gcc_checking_assert (m_vecpfx.m_num > 0);
931	return (*this)[m_vecpfx.m_num - 1];
932	}
933
934
935	/* If this vector has space for NELEMS additional entries, return
936	true. You usually only need to use this if you are doing your
937	own vector reallocation, for instance on an embedded vector. This
938	returns true in exactly the same circumstances that vec::reserve
939	will. */
940
941	template<typename T, typename A>
942	inline bool
943	vec<T, A, vl_embed>::space (unsigned nelems) const
944	{
945	return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
946	}
947
948
949	/* Return iteration condition and update *PTR to (a copy of) the IX'th
950	element of this vector. Use this to iterate over the elements of a
951	vector as follows,
952
953	for (ix = 0; v->iterate (ix, &val); ix++)
954	continue; */
955
956	template<typename T, typename A>
957	inline bool
958	vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
959	{
960	if (ix < m_vecpfx.m_num)
961	{
962	*ptr = address ()[ix];
963	return true;
964	}
965	else
966	{
967	*ptr = 0;
968	return false;
969	}
970	}
971
972
973	/* Return iteration condition and update *PTR to point to the
974	IX'th element of this vector. Use this to iterate over the
975	elements of a vector as follows,
976
977	for (ix = 0; v->iterate (ix, &ptr); ix++)
978	continue;
979
980	This variant is for vectors of objects. */
981
982	template<typename T, typename A>
983	inline bool
984	vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
985	{
986	if (ix < m_vecpfx.m_num)
987	{
988	*ptr = CONST_CAST (T *, &address ()[ix]);
989	return true;
990	}
991	else
992	{
993	*ptr = 0;
994	return false;
995	}
996	}
997
998
999	/* Return a pointer to a copy of this vector. */
1000
1001	template<typename T, typename A>
1002	inline vec<T, A, vl_embed> *
1003	vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
1004	{
1005	vec<T, A, vl_embed> *new_vec = NULL;
1006	unsigned len = length ();
1007	if (len)
1008	{
1009	vec_alloc (new_vec, len PASS_MEM_STAT);
1010	new_vec->embedded_init (len, len);
1011	vec_copy_construct (new_vec->address (), address (), len);
1012	}
1013	return new_vec;
1014	}
1015
1016
1017	/* Copy the elements from SRC to the end of this vector as if by memcpy.
1018	The vector must have sufficient headroom available. */
1019
1020	template<typename T, typename A>
1021	inline void
1022	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
1023	{
1024	unsigned len = src.length ();
1025	if (len)
1026	{
1027	gcc_checking_assert (space (len));
1028	vec_copy_construct (end (), src.address (), len);
1029	m_vecpfx.m_num += len;
1030	}
1031	}
1032
1033	template<typename T, typename A>
1034	inline void
1035	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1036	{
1037	if (src)
1038	splice (*src);
1039	}
1040
1041
1042	/* Push OBJ (a new element) onto the end of the vector. There must be
1043	sufficient space in the vector. Return a pointer to the slot
1044	where OBJ was inserted. */
1045
1046	template<typename T, typename A>
1047	inline T *
1048	vec<T, A, vl_embed>::quick_push (const T &obj)
1049	{
1050	gcc_checking_assert (space (1));
1051	T *slot = &address ()[m_vecpfx.m_num++];
1052	::new (static_cast<void*>(slot)) T (obj);
1053	return slot;
1054	}
1055
1056
1057	/* Pop and return a reference to the last element off the end of the
1058	vector. If T has non-trivial destructor, this method just pops
1059	the element and returns void type. */
1060
1061	template<typename T, typename A>
1062	inline typename vec<T, A, vl_embed>::pop_ret_type
1063	vec<T, A, vl_embed>::pop (void)
1064	{
1065	gcc_checking_assert (length () > 0);
1066	T &last = address ()[--m_vecpfx.m_num];
1067	if (!std::is_trivially_destructible <T>::value)
1068	last.~T ();
1069	return static_cast <pop_ret_type> (last);
1070	}
1071
1072
1073	/* Set the length of the vector to SIZE. The new length must be less
1074	than or equal to the current length. This is an O(1) operation. */
1075
1076	template<typename T, typename A>
1077	inline void
1078	vec<T, A, vl_embed>::truncate (unsigned size)
1079	{
1080	unsigned l = length ();
1081	gcc_checking_assert (l >= size);
1082	if (!std::is_trivially_destructible <T>::value)
1083	vec_destruct (address () + size, l - size);
1084	m_vecpfx.m_num = size;
1085	}
1086
1087
1088	/* Insert an element, OBJ, at the IXth position of this vector. There
1089	must be sufficient space. This operation is not suitable for non-trivially
1090	copyable types. */
1091
1092	template<typename T, typename A>
1093	inline void
1094	vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1095	{
1096	gcc_checking_assert (length () < allocated ());
1097	gcc_checking_assert (ix <= length ());
1098	#if GCC_VERSION >= 5000
1099	/* GCC 4.8 and 4.9 only implement std::is_trivially_destructible,
1100	but not std::is_trivially_copyable nor
1101	std::is_trivially_default_constructible. */
1102	static_assert (std::is_trivially_copyable <T>::value, "");
1103	#endif
1104	T *slot = &address ()[ix];
1105	memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1106	*slot = obj;
1107	}
1108
1109
1110	/* Remove an element from the IXth position of this vector. Ordering of
1111	remaining elements is preserved. This is an O(N) operation due to
1112	memmove. Not suitable for non-trivially copyable types. */
1113
1114	template<typename T, typename A>
1115	inline void
1116	vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1117	{
1118	gcc_checking_assert (ix < length ());
1119	#if GCC_VERSION >= 5000
1120	static_assert (std::is_trivially_copyable <T>::value, "");
1121	#endif
1122	T *slot = &address ()[ix];
1123	memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1124	}
1125
1126
1127	/* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1128	remaining elements is preserved. This is an O(N) operation. */
1129
1130	#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1131	elem_ptr, start, end, cond) \
1132	{ \
1133	gcc_assert ((end) <= (vec).length ()); \
1134	for (read_index = write_index = (start); read_index < (end); \
1135	++read_index) \
1136	{ \
1137	elem_ptr = &(vec)[read_index]; \
1138	bool remove_p = (cond); \
1139	if (remove_p) \
1140	continue; \
1141	\
1142	if (read_index != write_index) \
1143	(vec)[write_index] = (vec)[read_index]; \
1144	\
1145	write_index++; \
1146	} \
1147	\
1148	if (read_index - write_index > 0) \
1149	(vec).block_remove (write_index, read_index - write_index); \
1150	}
1151
1152
1153	/* Remove elements from VEC for which COND holds. Ordering of remaining
1154	elements is preserved. This is an O(N) operation. */
1155
1156	#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1157	cond) \
1158	VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1159	elem_ptr, 0, (vec).length (), (cond))
1160
1161	/* Remove an element from the IXth position of this vector. Ordering of
1162	remaining elements is destroyed. This is an O(1) operation. */
1163
1164	template<typename T, typename A>
1165	inline void
1166	vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1167	{
1168	gcc_checking_assert (ix < length ());
1169	#if GCC_VERSION >= 5000
1170	static_assert (std::is_trivially_copyable <T>::value, "");
1171	#endif
1172	T *p = address ();
1173	p[ix] = p[--m_vecpfx.m_num];
1174	}
1175
1176
1177	/* Remove LEN elements starting at the IXth. Ordering is retained.
1178	This is an O(N) operation due to memmove. */
1179
1180	template<typename T, typename A>
1181	inline void
1182	vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1183	{
1184	gcc_checking_assert (ix + len <= length ());
1185	#if GCC_VERSION >= 5000
1186	static_assert (std::is_trivially_copyable <T>::value, "");
1187	#endif
1188	T *slot = &address ()[ix];
1189	m_vecpfx.m_num -= len;
1190	memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1191	}
1192
1193
1194	#if GCC_VERSION >= 5000
1195	namespace vec_detail
1196	{
1197	/* gcc_{qsort,qsort_r,stablesort_r} implementation under the hood
1198	uses memcpy/memmove to reorder the array elements.
1199	We want to assert these methods aren't used on types for which
1200	that isn't appropriate, but unfortunately std::pair of 2 trivially
1201	copyable types isn't trivially copyable and we use qsort on many
1202	such std::pair instantiations. Let's allow both trivially
1203	copyable types and std::pair of 2 trivially copyable types as
1204	exception for qsort/sort/stablesort. */
1205	template<typename T>
1206	struct is_trivially_copyable_or_pair : std::is_trivially_copyable<T> { };
1207
1208	template<typename T, typename U>
1209	struct is_trivially_copyable_or_pair<std::pair<T, U> >
1210	: std::integral_constant<bool, std::is_trivially_copyable<T>::value
1211	&& std::is_trivially_copyable<U>::value> { };
1212	}
1213	#endif
1214
1215	/* Sort the contents of this vector with qsort. CMP is the comparison
1216	function to pass to qsort. */
1217
1218	template<typename T, typename A>
1219	inline void
1220	vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1221	{
1222	#if GCC_VERSION >= 5000
1223	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1224	#endif
1225	if (length () > 1)
1226	gcc_qsort (address (), length (), sizeof (T), cmp);
1227	}
1228
1229	/* Sort the contents of this vector with qsort. CMP is the comparison
1230	function to pass to qsort. */
1231
1232	template<typename T, typename A>
1233	inline void
1234	vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1235	void *data)
1236	{
1237	#if GCC_VERSION >= 5000
1238	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1239	#endif
1240	if (length () > 1)
1241	gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1242	}
1243
1244	/* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1245	comparison function to pass to qsort. */
1246
1247	template<typename T, typename A>
1248	inline void
1249	vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1250	void *), void *data)
1251	{
1252	#if GCC_VERSION >= 5000
1253	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1254	#endif
1255	if (length () > 1)
1256	gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1257	}
1258
1259	/* Search the contents of the sorted vector with a binary search.
1260	CMP is the comparison function to pass to bsearch. */
1261
1262	template<typename T, typename A>
1263	inline T *
1264	vec<T, A, vl_embed>::bsearch (const void *key,
1265	int (*compar) (const void *, const void *))
1266	{
1267	const void *base = this->address ();
1268	size_t nmemb = this->length ();
1269	size_t size = sizeof (T);
1270	/* The following is a copy of glibc stdlib-bsearch.h. */
1271	size_t l, u, idx;
1272	const void *p;
1273	int comparison;
1274
1275	l = 0;
1276	u = nmemb;
1277	while (l < u)
1278	{
1279	idx = (l + u) / 2;
1280	p = (const void *) (((const char *) base) + (idx * size));
1281	comparison = (*compar) (key, p);
1282	if (comparison < 0)
1283	u = idx;
1284	else if (comparison > 0)
1285	l = idx + 1;
1286	else
1287	return (T *)const_cast<void *>(p);
1288	}
1289
1290	return NULL;
1291	}
1292
1293	/* Search the contents of the sorted vector with a binary search.
1294	CMP is the comparison function to pass to bsearch. */
1295
1296	template<typename T, typename A>
1297	inline T *
1298	vec<T, A, vl_embed>::bsearch (const void *key,
1299	int (*compar) (const void *, const void *,
1300	void *), void *data)
1301	{
1302	const void *base = this->address ();
1303	size_t nmemb = this->length ();
1304	size_t size = sizeof (T);
1305	/* The following is a copy of glibc stdlib-bsearch.h. */
1306	size_t l, u, idx;
1307	const void *p;
1308	int comparison;
1309
1310	l = 0;
1311	u = nmemb;
1312	while (l < u)
1313	{
1314	idx = (l + u) / 2;
1315	p = (const void *) (((const char *) base) + (idx * size));
1316	comparison = (*compar) (key, p, data);
1317	if (comparison < 0)
1318	u = idx;
1319	else if (comparison > 0)
1320	l = idx + 1;
1321	else
1322	return (T *)const_cast<void *>(p);
1323	}
1324
1325	return NULL;
1326	}
1327
1328	/* Return true if SEARCH is an element of V. Note that this is O(N) in the
1329	size of the vector and so should be used with care. */
1330
1331	template<typename T, typename A>
1332	inline bool
1333	vec<T, A, vl_embed>::contains (const T &search) const
1334	{
1335	unsigned int len = length ();
1336	const T *p = address ();
1337	for (unsigned int i = 0; i < len; i++)
1338	{
1339	const T *slot = &p[i];
1340	if (*slot == search)
1341	return true;
1342	}
1343
1344	return false;
1345	}
1346
1347	/* Find and return the first position in which OBJ could be inserted
1348	without changing the ordering of this vector. LESSTHAN is a
1349	function that returns true if the first argument is strictly less
1350	than the second. */
1351
1352	template<typename T, typename A>
1353	unsigned
1354	vec<T, A, vl_embed>::lower_bound (const T &obj,
1355	bool (*lessthan)(const T &, const T &))
1356	const
1357	{
1358	unsigned int len = length ();
1359	unsigned int half, middle;
1360	unsigned int first = 0;
1361	while (len > 0)
1362	{
1363	half = len / 2;
1364	middle = first;
1365	middle += half;
1366	const T &middle_elem = address ()[middle];
1367	if (lessthan (middle_elem, obj))
1368	{
1369	first = middle;
1370	++first;
1371	len = len - half - 1;
1372	}
1373	else
1374	len = half;
1375	}
1376	return first;
1377	}
1378
1379
1380	/* Return the number of bytes needed to embed an instance of an
1381	embeddable vec inside another data structure.
1382
1383	Use these methods to determine the required size and initialization
1384	of a vector V of type T embedded within another structure (as the
1385	final member):
1386
1387	size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1388	void v->embedded_init (unsigned alloc, unsigned num);
1389
1390	These allow the caller to perform the memory allocation. */
1391
1392	template<typename T, typename A>
1393	inline size_t
1394	vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1395	{
1396	struct alignas (T) U { char data[sizeof (T)]; };
1397	typedef vec<U, A, vl_embed> vec_embedded;
1398	typedef typename std::conditional<std::is_standard_layout<T>::value,
1399	vec, vec_embedded>::type vec_stdlayout;
1400	static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1401	static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1402	return sizeof (vec_stdlayout) + alloc * sizeof (T);
1403	}
1404
1405
1406	/* Initialize the vector to contain room for ALLOC elements and
1407	NUM active elements. */
1408
1409	template<typename T, typename A>
1410	inline void
1411	vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1412	{
1413	m_vecpfx.m_alloc = alloc;
1414	m_vecpfx.m_using_auto_storage = aut;
1415	m_vecpfx.m_num = num;
1416	}
1417
1418
1419	/* Grow the vector to a specific length. LEN must be as long or longer than
1420	the current length. The new elements are uninitialized. */
1421
1422	template<typename T, typename A>
1423	inline void
1424	vec<T, A, vl_embed>::quick_grow (unsigned len)
1425	{
1426	gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1427	#if GCC_VERSION >= 5000
1428	static_assert (std::is_trivially_default_constructible <T>::value, "");
1429	#endif
1430	m_vecpfx.m_num = len;
1431	}
1432
1433
1434	/* Grow the vector to a specific length. LEN must be as long or longer than
1435	the current length. The new elements are initialized to zero. */
1436
1437	template<typename T, typename A>
1438	inline void
1439	vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1440	{
1441	unsigned oldlen = length ();
1442	size_t growby = len - oldlen;
1443	gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1444	m_vecpfx.m_num = len;
1445	if (growby != 0)
1446	vec_default_construct (address () + oldlen, growby);
1447	}
1448
1449	/* Garbage collection support for vec<T, A, vl_embed>. */
1450
1451	template<typename T>
1452	void
1453	gt_ggc_mx (vec<T, va_gc> *v)
1454	{
1455	static_assert (std::is_trivially_destructible <T>::value, "");
1456	extern void gt_ggc_mx (T &);
1457	for (unsigned i = 0; i < v->length (); i++)
1458	gt_ggc_mx ((*v)[i]);
1459	}
1460
1461	template<typename T>
1462	void
1463	gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1464	{
1465	static_assert (std::is_trivially_destructible <T>::value, "");
1466	/* Nothing to do. Vectors of atomic types wrt GC do not need to
1467	be traversed. */
1468	}
1469
1470
1471	/* PCH support for vec<T, A, vl_embed>. */
1472
1473	template<typename T, typename A>
1474	void
1475	gt_pch_nx (vec<T, A, vl_embed> *v)
1476	{
1477	extern void gt_pch_nx (T &);
1478	for (unsigned i = 0; i < v->length (); i++)
1479	gt_pch_nx ((*v)[i]);
1480	}
1481
1482	template<typename T>
1483	void
1484	gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *)
1485	{
1486	/* No pointers to note. */
1487	}
1488
1489	template<typename T, typename A>
1490	void
1491	gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1492	{
1493	for (unsigned i = 0; i < v->length (); i++)
1494	op (&((*v)[i]), NULL, cookie);
1495	}
1496
1497	template<typename T, typename A>
1498	void
1499	gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1500	{
1501	extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1502	for (unsigned i = 0; i < v->length (); i++)
1503	gt_pch_nx (&((*v)[i]), op, cookie);
1504	}
1505
1506	template<typename T>
1507	void
1508	gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *, gt_pointer_operator, void *)
1509	{
1510	/* No pointers to note. */
1511	}
1512
1513
1514	/* Space efficient vector. These vectors can grow dynamically and are
1515	allocated together with their control data. They are suited to be
1516	included in data structures. Prior to initial allocation, they
1517	only take a single word of storage.
1518
1519	These vectors are implemented as a pointer to an embeddable vector.
1520	The semantics allow for this pointer to be NULL to represent empty
1521	vectors. This way, empty vectors occupy minimal space in the
1522	structure containing them.
1523
1524	Properties:
1525
1526	- The whole vector and control data are allocated in a single
1527	contiguous block.
1528	- The whole vector may be re-allocated.
1529	- Vector data may grow and shrink.
1530	- Access and manipulation requires a pointer test and
1531	indirection.
1532	- It requires 1 word of storage (prior to vector allocation).
1533
1534
1535	Limitations:
1536
1537	These vectors must be PODs because they are stored in unions.
1538	(http://en.wikipedia.org/wiki/Plain_old_data_structures).
1539	As long as we use C++03, we cannot have constructors nor
1540	destructors in classes that are stored in unions. */
1541
1542	template<typename T, size_t N = 0>
1543	class auto_vec;
1544
1545	template<typename T>
1546	struct vec<T, va_heap, vl_ptr>
1547	{
1548	public:
1549	/* Default ctors to ensure triviality. Use value-initialization
1550	(e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1551	instance. */
1552	vec () = default;
1553	vec (const vec &) = default;
1554	/* Initialization from the generic vNULL. */
1555	vec (vnull): m_vec () { }
1556	/* Same as default ctor: vec storage must be released manually. */
1557	~vec () = default;
1558
1559	/* Defaulted same as copy ctor. */
1560	vec& operator= (const vec &) = default;
1561
1562	/* Prevent implicit conversion from auto_vec. Use auto_vec::to_vec()
1563	instead. */
1564	template <size_t N>
1565	vec (auto_vec<T, N> &) = delete;
1566
1567	template <size_t N>
1568	void operator= (auto_vec<T, N> &) = delete;
1569
1570	/* Memory allocation and deallocation for the embedded vector.
1571	Needed because we cannot have proper ctors/dtors defined. */
1572	void create (unsigned nelems CXX_MEM_STAT_INFO);
1573	void release (void);
1574
1575	/* Vector operations. */
1576	bool exists (void) const
1577	{ return m_vec != NULL; }
1578
1579	bool is_empty (void) const
1580	{ return m_vec ? m_vec->is_empty () : true; }
1581
1582	unsigned allocated (void) const
1583	{ return m_vec ? m_vec->allocated () : 0; }
1584
1585	unsigned length (void) const
1586	{ return m_vec ? m_vec->length () : 0; }
1587
1588	T *address (void)
1589	{ return m_vec ? m_vec->address () : NULL; }
1590
1591	const T *address (void) const
1592	{ return m_vec ? m_vec->address () : NULL; }
1593
1594	T *begin () { return address (); }
1595	const T *begin () const { return address (); }
1596	T *end () { return begin () + length (); }
1597	const T *end () const { return begin () + length (); }
1598	const T &operator[] (unsigned ix) const
1599	{ return (*m_vec)[ix]; }
1600	const T &last (void) const
1601	{ return m_vec->last (); }
1602
1603	bool operator!=(const vec &other) const
1604	{ return !(*this == other); }
1605
1606	bool operator==(const vec &other) const
1607	{ return address () == other.address (); }
1608
1609	T &operator[] (unsigned ix)
1610	{ return (*m_vec)[ix]; }
1611
1612	T &last (void)
1613	{ return m_vec->last (); }
1614
1615	bool space (int nelems) const
1616	{ return m_vec ? m_vec->space (nelems) : nelems == 0; }
1617
1618	bool iterate (unsigned ix, T *p) const;
1619	bool iterate (unsigned ix, T **p) const;
1620	vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1621	bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1622	bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1623	void splice (const vec &);
1624	void safe_splice (const vec & CXX_MEM_STAT_INFO);
1625	T *quick_push (const T &);
1626	T *safe_push (const T &CXX_MEM_STAT_INFO);
1627	using pop_ret_type
1628	= typename std::conditional <std::is_trivially_destructible <T>::value,
1629	T &, void>::type;
1630	pop_ret_type pop (void);
1631	void truncate (unsigned);
1632	void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
1633	void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
1634	void quick_grow (unsigned);
1635	void quick_grow_cleared (unsigned);
1636	void quick_insert (unsigned, const T &);
1637	void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1638	void ordered_remove (unsigned);
1639	void unordered_remove (unsigned);
1640	void block_remove (unsigned, unsigned);
1641	void qsort (int (*) (const void *, const void *));
1642	void sort (int (*) (const void *, const void *, void *), void *);
1643	void stablesort (int (*) (const void *, const void *, void *), void *);
1644	T *bsearch (const void *key, int (*compar)(const void *, const void *));
1645	T *bsearch (const void *key,
1646	int (*compar)(const void *, const void *, void *), void *);
1647	unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1648	bool contains (const T &search) const;
1649	void reverse (void);
1650
1651	bool using_auto_storage () const;
1652
1653	/* FIXME - This field should be private, but we need to cater to
1654	compilers that have stricter notions of PODness for types. */
1655	vec<T, va_heap, vl_embed> *m_vec;
1656	};
1657
1658
1659	/* auto_vec is a subclass of vec that automatically manages creating and
1660	releasing the internal vector. If N is non zero then it has N elements of
1661	internal storage. The default is no internal storage, and you probably only
1662	want to ask for internal storage for vectors on the stack because if the
1663	size of the vector is larger than the internal storage that space is wasted.
1664	*/
1665	template<typename T, size_t N /* = 0 */>
1666	class auto_vec : public vec<T, va_heap>
1667	{
1668	public:
1669	auto_vec ()
1670	{
1671	m_auto.embedded_init (N, 0, 1);
1672	/* ??? Instead of initializing m_vec from &m_auto directly use an
1673	expression that avoids refering to a specific member of 'this'
1674	to derail the -Wstringop-overflow diagnostic code, avoiding
1675	the impression that data accesses are supposed to be to the
1676	m_auto member storage. */
1677	size_t off = (char *) &m_auto - (char *) this;
1678	this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1679	}
1680
1681	auto_vec (size_t s CXX_MEM_STAT_INFO)
1682	{
1683	if (s > N)
1684	{
1685	this->create (s PASS_MEM_STAT);
1686	return;
1687	}
1688
1689	m_auto.embedded_init (N, 0, 1);
1690	/* ??? See above. */
1691	size_t off = (char *) &m_auto - (char *) this;
1692	this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1693	}
1694
1695	~auto_vec ()
1696	{
1697	this->release ();
1698	}
1699
1700	/* Explicitly convert to the base class. There is no conversion
1701	from a const auto_vec because a copy of the returned vec can
1702	be used to modify *THIS.
1703	This is a legacy function not to be used in new code. */
1704	vec<T, va_heap> to_vec_legacy () {
1705	return *static_cast<vec<T, va_heap> *>(this);
1706	}
1707
1708	private:
1709	vec<T, va_heap, vl_embed> m_auto;
1710	unsigned char m_data[sizeof (T) * N];
1711	};
1712
1713	/* auto_vec is a sub class of vec whose storage is released when it is
1714	destroyed. */
1715	template<typename T>
1716	class auto_vec<T, 0> : public vec<T, va_heap>
1717	{
1718	public:
1719	auto_vec () { this->m_vec = NULL; }
1720	auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); }
1721	~auto_vec () { this->release (); }
1722
1723	auto_vec (vec<T, va_heap>&& r)
1724	{
1725	gcc_assert (!r.using_auto_storage ());
1726	this->m_vec = r.m_vec;
1727	r.m_vec = NULL;
1728	}
1729
1730	auto_vec (auto_vec<T> &&r)
1731	{
1732	gcc_assert (!r.using_auto_storage ());
1733	this->m_vec = r.m_vec;
1734	r.m_vec = NULL;
1735	}
1736
1737	auto_vec& operator= (vec<T, va_heap>&& r)
1738	{
1739	if (this == &r)
1740	return *this;
1741
1742	gcc_assert (!r.using_auto_storage ());
1743	this->release ();
1744	this->m_vec = r.m_vec;
1745	r.m_vec = NULL;
1746	return *this;
1747	}
1748
1749	auto_vec& operator= (auto_vec<T> &&r)
1750	{
1751	if (this == &r)
1752	return *this;
1753
1754	gcc_assert (!r.using_auto_storage ());
1755	this->release ();
1756	this->m_vec = r.m_vec;
1757	r.m_vec = NULL;
1758	return *this;
1759	}
1760
1761	/* Explicitly convert to the base class. There is no conversion
1762	from a const auto_vec because a copy of the returned vec can
1763	be used to modify *THIS.
1764	This is a legacy function not to be used in new code. */
1765	vec<T, va_heap> to_vec_legacy () {
1766	return *static_cast<vec<T, va_heap> *>(this);
1767	}
1768
1769	// You probably don't want to copy a vector, so these are deleted to prevent
1770	// unintentional use. If you really need a copy of the vectors contents you
1771	// can use copy ().
1772	auto_vec (const auto_vec &) = delete;
1773	auto_vec &operator= (const auto_vec &) = delete;
1774	};
1775
1776
1777	/* Allocate heap memory for pointer V and create the internal vector
1778	with space for NELEMS elements. If NELEMS is 0, the internal
1779	vector is initialized to empty. */
1780
1781	template<typename T>
1782	inline void
1783	vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1784	{
1785	v = new vec<T>;
1786	v->create (nelems PASS_MEM_STAT);
1787	}
1788
1789
1790	/* A subclass of auto_vec <char *> that frees all of its elements on
1791	deletion. */
1792
1793	class auto_string_vec : public auto_vec <char *>
1794	{
1795	public:
1796	~auto_string_vec ();
1797	};
1798
1799	/* A subclass of auto_vec <T *> that deletes all of its elements on
1800	destruction.
1801
1802	This is a crude way for a vec to "own" the objects it points to
1803	and clean up automatically.
1804
1805	For example, no attempt is made to delete elements when an item
1806	within the vec is overwritten.
1807
1808	We can't rely on gnu::unique_ptr within a container,
1809	since we can't rely on move semantics in C++98. */
1810
1811	template <typename T>
1812	class auto_delete_vec : public auto_vec <T *>
1813	{
1814	public:
1815	auto_delete_vec () {}
1816	auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1817
1818	~auto_delete_vec ();
1819
1820	private:
1821	DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1822	};
1823
1824	/* Conditionally allocate heap memory for VEC and its internal vector. */
1825
1826	template<typename T>
1827	inline void
1828	vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1829	{
1830	if (!vec)
1831	vec_alloc (vec, nelems PASS_MEM_STAT);
1832	}
1833
1834
1835	/* Free the heap memory allocated by vector V and set it to NULL. */
1836
1837	template<typename T>
1838	inline void
1839	vec_free (vec<T> *&v)
1840	{
1841	if (v == NULL)
1842	return;
1843
1844	v->release ();
1845	delete v;
1846	v = NULL;
1847	}
1848
1849
1850	/* Return iteration condition and update PTR to point to the IX'th
1851	element of this vector. Use this to iterate over the elements of a
1852	vector as follows,
1853
1854	for (ix = 0; v.iterate (ix, &ptr); ix++)
1855	continue; */
1856
1857	template<typename T>
1858	inline bool
1859	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1860	{
1861	if (m_vec)
1862	return m_vec->iterate (ix, ptr);
1863	else
1864	{
1865	*ptr = 0;
1866	return false;
1867	}
1868	}
1869
1870
1871	/* Return iteration condition and update *PTR to point to the
1872	IX'th element of this vector. Use this to iterate over the
1873	elements of a vector as follows,
1874
1875	for (ix = 0; v->iterate (ix, &ptr); ix++)
1876	continue;
1877
1878	This variant is for vectors of objects. */
1879
1880	template<typename T>
1881	inline bool
1882	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1883	{
1884	if (m_vec)
1885	return m_vec->iterate (ix, ptr);
1886	else
1887	{
1888	*ptr = 0;
1889	return false;
1890	}
1891	}
1892
1893
1894	/* Convenience macro for forward iteration. */
1895	#define FOR_EACH_VEC_ELT(V, I, P) \
1896	for (I = 0; (V).iterate ((I), &(P)); ++(I))
1897
1898	#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1899	for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1900
1901	/* Likewise, but start from FROM rather than 0. */
1902	#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1903	for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1904
1905	/* Convenience macro for reverse iteration. */
1906	#define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1907	for (I = (V).length () - 1; \
1908	(V).iterate ((I), &(P)); \
1909	(I)--)
1910
1911	#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1912	for (I = vec_safe_length (V) - 1; \
1913	vec_safe_iterate ((V), (I), &(P)); \
1914	(I)--)
1915
1916	/* auto_string_vec's dtor, freeing all contained strings, automatically
1917	chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1918
1919	inline
1920	auto_string_vec::~auto_string_vec ()
1921	{
1922	int i;
1923	char *str;
1924	FOR_EACH_VEC_ELT (*this, i, str)
1925	free (ptr: str);
1926	}
1927
1928	/* auto_delete_vec's dtor, deleting all contained items, automatically
1929	chaining up to ~auto_vec <T*>, which frees the internal buffer. */
1930
1931	template <typename T>
1932	inline
1933	auto_delete_vec<T>::~auto_delete_vec ()
1934	{
1935	int i;
1936	T *item;
1937	FOR_EACH_VEC_ELT (*this, i, item)
1938	delete item;
1939	}
1940
1941
1942	/* Return a copy of this vector. */
1943
1944	template<typename T>
1945	inline vec<T, va_heap, vl_ptr>
1946	vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1947	{
1948	vec<T, va_heap, vl_ptr> new_vec{ };
1949	if (length ())
1950	new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1951	return new_vec;
1952	}
1953
1954
1955	/* Ensure that the vector has at least RESERVE slots available (if
1956	EXACT is false), or exactly RESERVE slots available (if EXACT is
1957	true).
1958
1959	This may create additional headroom if EXACT is false.
1960
1961	Note that this can cause the embedded vector to be reallocated.
1962	Returns true iff reallocation actually occurred. */
1963
1964	template<typename T>
1965	inline bool
1966	vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1967	{
1968	if (space (nelems))
1969	return false;
1970
1971	/* For now play a game with va_heap::reserve to hide our auto storage if any,
1972	this is necessary because it doesn't have enough information to know the
1973	embedded vector is in auto storage, and so should not be freed. */
1974	vec<T, va_heap, vl_embed> *oldvec = m_vec;
1975	unsigned int oldsize = 0;
1976	bool handle_auto_vec = m_vec && using_auto_storage ();
1977	if (handle_auto_vec)
1978	{
1979	m_vec = NULL;
1980	oldsize = oldvec->length ();
1981	nelems += oldsize;
1982	}
1983
1984	va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1985	if (handle_auto_vec)
1986	{
1987	vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1988	m_vec->m_vecpfx.m_num = oldsize;
1989	}
1990
1991	return true;
1992	}
1993
1994
1995	/* Ensure that this vector has exactly NELEMS slots available. This
1996	will not create additional headroom. Note this can cause the
1997	embedded vector to be reallocated. Returns true iff reallocation
1998	actually occurred. */
1999
2000	template<typename T>
2001	inline bool
2002	vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
2003	{
2004	return reserve (nelems, exact: true PASS_MEM_STAT);
2005	}
2006
2007
2008	/* Create the internal vector and reserve NELEMS for it. This is
2009	exactly like vec::reserve, but the internal vector is
2010	unconditionally allocated from scratch. The old one, if it
2011	existed, is lost. */
2012
2013	template<typename T>
2014	inline void
2015	vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
2016	{
2017	m_vec = NULL;
2018	if (nelems > 0)
2019	reserve_exact (nelems PASS_MEM_STAT);
2020	}
2021
2022
2023	/* Free the memory occupied by the embedded vector. */
2024
2025	template<typename T>
2026	inline void
2027	vec<T, va_heap, vl_ptr>::release (void)
2028	{
2029	if (!m_vec)
2030	return;
2031
2032	if (using_auto_storage ())
2033	{
2034	m_vec->truncate (0);
2035	return;
2036	}
2037
2038	va_heap::release (m_vec);
2039	}
2040
2041	/* Copy the elements from SRC to the end of this vector as if by memcpy.
2042	SRC and this vector must be allocated with the same memory
2043	allocation mechanism. This vector is assumed to have sufficient
2044	headroom available. */
2045
2046	template<typename T>
2047	inline void
2048	vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
2049	{
2050	if (src.length ())
2051	m_vec->splice (*(src.m_vec));
2052	}
2053
2054
2055	/* Copy the elements in SRC to the end of this vector as if by memcpy.
2056	SRC and this vector must be allocated with the same mechanism.
2057	If there is not enough headroom in this vector, it will be reallocated
2058	as needed. */
2059
2060	template<typename T>
2061	inline void
2062	vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
2063	MEM_STAT_DECL)
2064	{
2065	if (src.length ())
2066	{
2067	reserve_exact (nelems: src.length ());
2068	splice (src);
2069	}
2070	}
2071
2072
2073	/* Push OBJ (a new element) onto the end of the vector. There must be
2074	sufficient space in the vector. Return a pointer to the slot
2075	where OBJ was inserted. */
2076
2077	template<typename T>
2078	inline T *
2079	vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
2080	{
2081	return m_vec->quick_push (obj);
2082	}
2083
2084
2085	/* Push a new element OBJ onto the end of this vector. Reallocates
2086	the embedded vector, if needed. Return a pointer to the slot where
2087	OBJ was inserted. */
2088
2089	template<typename T>
2090	inline T *
2091	vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
2092	{
2093	reserve (nelems: 1, exact: false PASS_MEM_STAT);
2094	return quick_push (obj);
2095	}
2096
2097
2098	/* Pop and return a reference to the last element off the end of the
2099	vector. If T has non-trivial destructor, this method just pops
2100	last element and returns void. */
2101
2102	template<typename T>
2103	inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
2104	vec<T, va_heap, vl_ptr>::pop (void)
2105	{
2106	return m_vec->pop ();
2107	}
2108
2109
2110	/* Set the length of the vector to LEN. The new length must be less
2111	than or equal to the current length. This is an O(1) operation. */
2112
2113	template<typename T>
2114	inline void
2115	vec<T, va_heap, vl_ptr>::truncate (unsigned size)
2116	{
2117	if (m_vec)
2118	m_vec->truncate (size);
2119	else
2120	gcc_checking_assert (size == 0);
2121	}
2122
2123
2124	/* Grow the vector to a specific length. LEN must be as long or
2125	longer than the current length. The new elements are
2126	uninitialized. Reallocate the internal vector, if needed. */
2127
2128	template<typename T>
2129	inline void
2130	vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2131	{
2132	unsigned oldlen = length ();
2133	gcc_checking_assert (oldlen <= len);
2134	reserve (nelems: len - oldlen, exact PASS_MEM_STAT);
2135	if (m_vec)
2136	m_vec->quick_grow (len);
2137	else
2138	gcc_checking_assert (len == 0);
2139	}
2140
2141
2142	/* Grow the embedded vector to a specific length. LEN must be as
2143	long or longer than the current length. The new elements are
2144	initialized to zero. Reallocate the internal vector, if needed. */
2145
2146	template<typename T>
2147	inline void
2148	vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2149	MEM_STAT_DECL)
2150	{
2151	unsigned oldlen = length ();
2152	gcc_checking_assert (oldlen <= len);
2153	reserve (nelems: len - oldlen, exact PASS_MEM_STAT);
2154	if (m_vec)
2155	m_vec->quick_grow_cleared (len);
2156	else
2157	gcc_checking_assert (len == 0);
2158	}
2159
2160
2161	/* Same as vec::safe_grow but without reallocation of the internal vector.
2162	If the vector cannot be extended, a runtime assertion will be triggered. */
2163
2164	template<typename T>
2165	inline void
2166	vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2167	{
2168	gcc_checking_assert (m_vec);
2169	m_vec->quick_grow (len);
2170	}
2171
2172
2173	/* Same as vec::quick_grow_cleared but without reallocation of the
2174	internal vector. If the vector cannot be extended, a runtime
2175	assertion will be triggered. */
2176
2177	template<typename T>
2178	inline void
2179	vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2180	{
2181	gcc_checking_assert (m_vec);
2182	m_vec->quick_grow_cleared (len);
2183	}
2184
2185
2186	/* Insert an element, OBJ, at the IXth position of this vector. There
2187	must be sufficient space. */
2188
2189	template<typename T>
2190	inline void
2191	vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2192	{
2193	m_vec->quick_insert (ix, obj);
2194	}
2195
2196
2197	/* Insert an element, OBJ, at the IXth position of the vector.
2198	Reallocate the embedded vector, if necessary. */
2199
2200	template<typename T>
2201	inline void
2202	vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2203	{
2204	reserve (nelems: 1, exact: false PASS_MEM_STAT);
2205	quick_insert (ix, obj);
2206	}
2207
2208
2209	/* Remove an element from the IXth position of this vector. Ordering of
2210	remaining elements is preserved. This is an O(N) operation due to
2211	a memmove. */
2212
2213	template<typename T>
2214	inline void
2215	vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2216	{
2217	m_vec->ordered_remove (ix);
2218	}
2219
2220
2221	/* Remove an element from the IXth position of this vector. Ordering
2222	of remaining elements is destroyed. This is an O(1) operation. */
2223
2224	template<typename T>
2225	inline void
2226	vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2227	{
2228	m_vec->unordered_remove (ix);
2229	}
2230
2231
2232	/* Remove LEN elements starting at the IXth. Ordering is retained.
2233	This is an O(N) operation due to memmove. */
2234
2235	template<typename T>
2236	inline void
2237	vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2238	{
2239	m_vec->block_remove (ix, len);
2240	}
2241
2242
2243	/* Sort the contents of this vector with qsort. CMP is the comparison
2244	function to pass to qsort. */
2245
2246	template<typename T>
2247	inline void
2248	vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
2249	{
2250	if (m_vec)
2251	m_vec->qsort (cmp);
2252	}
2253
2254	/* Sort the contents of this vector with qsort. CMP is the comparison
2255	function to pass to qsort. */
2256
2257	template<typename T>
2258	inline void
2259	vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
2260	void *), void *data)
2261	{
2262	if (m_vec)
2263	m_vec->sort (cmp, data);
2264	}
2265
2266	/* Sort the contents of this vector with gcc_stablesort_r. CMP is the
2267	comparison function to pass to qsort. */
2268
2269	template<typename T>
2270	inline void
2271	vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *,
2272	void *), void *data)
2273	{
2274	if (m_vec)
2275	m_vec->stablesort (cmp, data);
2276	}
2277
2278	/* Search the contents of the sorted vector with a binary search.
2279	CMP is the comparison function to pass to bsearch. */
2280
2281	template<typename T>
2282	inline T *
2283	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2284	int (*cmp) (const void *, const void *))
2285	{
2286	if (m_vec)
2287	return m_vec->bsearch (key, cmp);
2288	return NULL;
2289	}
2290
2291	/* Search the contents of the sorted vector with a binary search.
2292	CMP is the comparison function to pass to bsearch. */
2293
2294	template<typename T>
2295	inline T *
2296	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2297	int (*cmp) (const void *, const void *,
2298	void *), void *data)
2299	{
2300	if (m_vec)
2301	return m_vec->bsearch (key, cmp, data);
2302	return NULL;
2303	}
2304
2305
2306	/* Find and return the first position in which OBJ could be inserted
2307	without changing the ordering of this vector. LESSTHAN is a
2308	function that returns true if the first argument is strictly less
2309	than the second. */
2310
2311	template<typename T>
2312	inline unsigned
2313	vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2314	bool (*lessthan)(const T &, const T &))
2315	const
2316	{
2317	return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
2318	}
2319
2320	/* Return true if SEARCH is an element of V. Note that this is O(N) in the
2321	size of the vector and so should be used with care. */
2322
2323	template<typename T>
2324	inline bool
2325	vec<T, va_heap, vl_ptr>::contains (const T &search) const
2326	{
2327	return m_vec ? m_vec->contains (search) : false;
2328	}
2329
2330	/* Reverse content of the vector. */
2331
2332	template<typename T>
2333	inline void
2334	vec<T, va_heap, vl_ptr>::reverse (void)
2335	{
2336	unsigned l = length ();
2337	T *ptr = address ();
2338
2339	for (unsigned i = 0; i < l / 2; i++)
2340	std::swap (ptr[i], ptr[l - i - 1]);
2341	}
2342
2343	template<typename T>
2344	inline bool
2345	vec<T, va_heap, vl_ptr>::using_auto_storage () const
2346	{
2347	return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2348	}
2349
2350	/* Release VEC and call release of all element vectors. */
2351
2352	template<typename T>
2353	inline void
2354	release_vec_vec (vec<vec<T> > &vec)
2355	{
2356	for (unsigned i = 0; i < vec.length (); i++)
2357	vec[i].release ();
2358
2359	vec.release ();
2360	}
2361
2362	// Provide a subset of the std::span functionality. (We can't use std::span
2363	// itself because it's a C++20 feature.)
2364	//
2365	// In addition, provide an invalid value that is distinct from all valid
2366	// sequences (including the empty sequence). This can be used to return
2367	// failure without having to use std::optional.
2368	//
2369	// There is no operator bool because it would be ambiguous whether it is
2370	// testing for a valid value or an empty sequence.
2371	template<typename T>
2372	class array_slice
2373	{
2374	template<typename OtherT> friend class array_slice;
2375
2376	public:
2377	using value_type = T;
2378	using iterator = T *;
2379	using const_iterator = const T *;
2380
2381	array_slice () : m_base (nullptr), m_size (0) {}
2382
2383	template<typename OtherT>
2384	array_slice (array_slice<OtherT> other)
2385	: m_base (other.m_base), m_size (other.m_size) {}
2386
2387	array_slice (iterator base, unsigned int size)
2388	: m_base (base), m_size (size) {}
2389
2390	template<size_t N>
2391	array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2392
2393	template<typename OtherT>
2394	array_slice (const vec<OtherT> &v)
2395	: m_base (v.address ()), m_size (v.length ()) {}
2396
2397	template<typename OtherT>
2398	array_slice (vec<OtherT> &v)
2399	: m_base (v.address ()), m_size (v.length ()) {}
2400
2401	template<typename OtherT, typename A>
2402	array_slice (const vec<OtherT, A, vl_embed> *v)
2403	: m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2404
2405	template<typename OtherT, typename A>
2406	array_slice (vec<OtherT, A, vl_embed> *v)
2407	: m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2408
2409	iterator begin () { gcc_checking_assert (is_valid ()); return m_base; }
2410	iterator end () { gcc_checking_assert (is_valid ()); return m_base + m_size; }
2411
2412	const_iterator begin () const { gcc_checking_assert (is_valid ()); return m_base; }
2413	const_iterator end () const { gcc_checking_assert (is_valid ()); return m_base + m_size; }
2414
2415	value_type &front ();
2416	value_type &back ();
2417	value_type &operator[] (unsigned int i);
2418
2419	const value_type &front () const;
2420	const value_type &back () const;
2421	const value_type &operator[] (unsigned int i) const;
2422
2423	unsigned size () const { return m_size; }
2424	size_t size_bytes () const { return m_size * sizeof (T); }
2425	bool empty () const { return m_size == 0; }
2426
2427	// An invalid array_slice that represents a failed operation. This is
2428	// distinct from an empty slice, which is a valid result in some contexts.
2429	static array_slice invalid () { return { nullptr, ~0U }; }
2430
2431	// True if the array is valid, false if it is an array like INVALID.
2432	bool is_valid () const { return m_base || m_size == 0; }
2433
2434	private:
2435	iterator m_base;
2436	unsigned int m_size;
2437	};
2438
2439	template<typename T>
2440	inline typename array_slice<T>::value_type &
2441	array_slice<T>::front ()
2442	{
2443	gcc_checking_assert (m_size);
2444	return m_base[0];
2445	}
2446
2447	template<typename T>
2448	inline const typename array_slice<T>::value_type &
2449	array_slice<T>::front () const
2450	{
2451	gcc_checking_assert (m_size);
2452	return m_base[0];
2453	}
2454
2455	template<typename T>
2456	inline typename array_slice<T>::value_type &
2457	array_slice<T>::back ()
2458	{
2459	gcc_checking_assert (m_size);
2460	return m_base[m_size - 1];
2461	}
2462
2463	template<typename T>
2464	inline const typename array_slice<T>::value_type &
2465	array_slice<T>::back () const
2466	{
2467	gcc_checking_assert (m_size);
2468	return m_base[m_size - 1];
2469	}
2470
2471	template<typename T>
2472	inline typename array_slice<T>::value_type &
2473	array_slice<T>::operator[] (unsigned int i)
2474	{
2475	gcc_checking_assert (i < m_size);
2476	return m_base[i];
2477	}
2478
2479	template<typename T>
2480	inline const typename array_slice<T>::value_type &
2481	array_slice<T>::operator[] (unsigned int i) const
2482	{
2483	gcc_checking_assert (i < m_size);
2484	return m_base[i];
2485	}
2486
2487	template<typename T>
2488	array_slice<T>
2489	make_array_slice (T *base, unsigned int size)
2490	{
2491	return array_slice<T> (base, size);
2492	}
2493
2494	#if (GCC_VERSION >= 3000)
2495	# pragma GCC poison m_vec m_vecpfx m_vecdata
2496	#endif
2497
2498	#endif // GCC_VEC_H
2499