1	/* Vector API for GNU compiler.
2	Copyright (C) 2004-2022 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	Notes on the different layout strategies
115
116	* Embeddable vectors (vec<T, A, vl_embed>)
117
118	These vectors are suitable to be embedded in other data
119	structures so that they can be pre-allocated in a contiguous
120	memory block.
121
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.
128
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).
132
133	Properties of embeddable vectors:
134
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).
143
144
145	* Space efficient vector (vec<T, A, vl_ptr>)
146
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
150	word of storage.
151
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.
156
157	Properties:
158
159	- The whole vector and control data are allocated in a single
160	contiguous block.
161	- The whole vector may be re-allocated.
162	- Vector data may grow and shrink.
163	- Access and manipulation requires a pointer test and
164	indirection.
165	- It requires 1 word of storage (prior to vector allocation).
166
167	An example of their use would be,
168
169	struct my_struct {
170	// A space-efficient vector of tree pointers in GC memory.
171	vec<tree, va_gc, vl_ptr> v;
172	};
173
174	struct my_struct *s;
175
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 }
180	*/
181
182	/* Support function for statistics. */
183	extern void dump_vec_loc_statistics (void);
184
185	/* Hashtable mapping vec addresses to descriptors. */
186	extern htab_t vec_mem_usage_hash;
187
188	/* Control data for vectors. This contains the number of allocated
189	and used slots inside a vector. */
190
191	struct vec_prefix
192	{
193	/* FIXME - These fields should be private, but we need to cater to
194	compilers that have stricter notions of PODness for types. */
195
196	/* Memory allocation support routines in vec.cc. */
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);
201
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.
205
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;
209
210	/* The allocator types also need access to our internals. */
211	friend struct va_gc;
212	friend struct va_gc_atomic;
213	friend struct va_heap;
214
215	unsigned m_alloc : 31;
216	unsigned m_using_auto_storage : 1;
217	unsigned m_num;
218	};
219
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. */
223
224	inline unsigned
225	vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
226	bool exact)
227	{
228	if (exact)
229	return (pfx ? pfx->m_num : 0) + reserve;
230	else if (!pfx)
231	return MAX (4, reserve);
232	return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
233	}
234
235	template<typename, typename, typename> struct vec;
236
237	/* Valid vector layouts
238
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. */
242	struct vl_embed { };
243	struct vl_ptr { };
244
245
246	/* Types of supported allocations
247
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. */
252
253	/* Allocator type for heap vectors. */
254	struct va_heap
255	{
256	/* Heap vectors are frequently regular instances, so use the vl_ptr
257	layout for them. */
258	typedef vl_ptr default_layout;
259
260	template<typename T>
261	static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
262	CXX_MEM_STAT_INFO);
263
264	template<typename T>
265	static void release (vec<T, va_heap, vl_embed> *&);
266	};
267
268
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. */
273
274	template<typename T>
275	inline void
276	va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
277	MEM_STAT_DECL)
278	{
279	size_t elt_size = sizeof (T);
280	unsigned alloc
281	= vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
282	gcc_checking_assert (alloc);
283
284	if (GATHER_STATISTICS && v)
285	v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
286	v->allocated (), false);
287
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);
292
293	if (GATHER_STATISTICS)
294	v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
295	}
296
297
298	#if GCC_VERSION >= 4007
299	#pragma GCC diagnostic push
300	#pragma GCC diagnostic ignored "-Wfree-nonheap-object"
301	#endif
302
303	/* Free the heap space allocated for vector V. */
304
305	template<typename T>
306	void
307	va_heap::release (vec<T, va_heap, vl_embed> *&v)
308	{
309	size_t elt_size = sizeof (T);
310	if (v == NULL)
311	return;
312
313	if (GATHER_STATISTICS)
314	v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
315	v->allocated (), true);
316	::free (v);
317	v = NULL;
318	}
319
320	#if GCC_VERSION >= 4007
321	#pragma GCC diagnostic pop
322	#endif
323
324	/* Allocator type for GC vectors. Notice that we need the structure
325	declaration even if GC is not enabled. */
326
327	struct va_gc
328	{
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;
334
335	template<typename T, typename A>
336	static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
337	CXX_MEM_STAT_INFO);
338
339	template<typename T, typename A>
340	static void release (vec<T, A, vl_embed> *&v);
341	};
342
343
344	/* Free GC memory used by V and reset V to NULL. */
345
346	template<typename T, typename A>
347	inline void
348	va_gc::release (vec<T, A, vl_embed> *&v)
349	{
350	if (v)
351	::ggc_free (v);
352	v = NULL;
353	}
354
355
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. */
360
361	template<typename T, typename A>
362	void
363	va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
364	MEM_STAT_DECL)
365	{
366	unsigned alloc
367	= vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
368	if (!alloc)
369	{
370	::ggc_free (v);
371	v = NULL;
372	return;
373	}
374
375	/* Calculate the amount of space we want. */
376	size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
377
378	/* Ask the allocator how much space it will really give us. */
379	size = ::ggc_round_alloc_size (size);
380
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;
385
386	/* And finally, recalculate the amount of space we ask for. */
387	size = vec_offset + alloc * elt_size;
388
389	unsigned nelem = v ? v->length () : 0;
390	v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
391	PASS_MEM_STAT));
392	v->embedded_init (alloc, nelem);
393	}
394
395
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
400	{
401	};
402
403
404	/* Generic vector template. Default values for A and L indicate the
405	most commonly used strategies.
406
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
410	themselves.
411
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). */
415	template<typename T,
416	typename A = va_heap,
417	typename L = typename A::default_layout>
418	struct GTY((user)) vec
419	{
420	};
421
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; }
431
432	/* Generic vec<> debug helpers.
433
434	These need to be instantiated for each vec<TYPE> used throughout
435	the compiler like this:
436
437	DEFINE_DEBUG_VEC (TYPE)
438
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). */
442
443	template<typename T>
444	void
445	debug_helper (vec<T> &ref)
446	{
447	unsigned i;
448	for (i = 0; i < ref.length (); ++i)
449	{
450	fprintf (stderr, "[%d] = ", i);
451	debug_slim (ref[i]);
452	fputc ('\n', stderr);
453	}
454	}
455
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. */
460
461	template<typename T>
462	void
463	debug_helper (vec<T, va_gc> &ref)
464	{
465	unsigned i;
466	for (i = 0; i < ref.length (); ++i)
467	{
468	fprintf (stderr, "[%d] = ", i);
469	debug_slim (ref[i]);
470	fputc ('\n', stderr);
471	}
472	}
473
474	/* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
475	functions for a type T. */
476
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) \
483	{ \
484	debug_helper <T> (ref); \
485	} \
486	DEBUG_FUNCTION void \
487	debug (vec<T> *ptr) \
488	{ \
489	if (ptr) \
490	debug (*ptr); \
491	else \
492	fprintf (stderr, "<nil>\n"); \
493	} \
494	/* Define the vec<T, va_gc> debug functions. */ \
495	DEBUG_FUNCTION void \
496	debug (vec<T, va_gc> &ref) \
497	{ \
498	debug_helper <T> (ref); \
499	} \
500	DEBUG_FUNCTION void \
501	debug (vec<T, va_gc> *ptr) \
502	{ \
503	if (ptr) \
504	debug (*ptr); \
505	else \
506	fprintf (stderr, "<nil>\n"); \
507	}
508
509	/* Default-construct N elements in DST. */
510
511	template <typename T>
512	inline void
513	vec_default_construct (T *dst, unsigned n)
514	{
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);
529	#endif
530	for ( ; n; ++dst, --n)
531	::new (static_cast<void*>(dst)) T ();
532	}
533
534	/* Copy-construct N elements in DST from *SRC. */
535
536	template <typename T>
537	inline void
538	vec_copy_construct (T *dst, const T *src, unsigned n)
539	{
540	for ( ; n; ++dst, ++src, --n)
541	::new (static_cast<void*>(dst)) T (*src);
542	}
543
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. */
552	struct vnull { };
553	constexpr vnull vNULL{ };
554
555
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.
559
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.
566
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).
570
571	Properties:
572
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). */
581
582	template<typename T, typename A>
583	struct GTY((user)) vec<T, A, vl_embed>
584	{
585	public:
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);
597	T &last (void);
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 &);
605	T &pop (void);
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);
623
624	/* vec class can access our internal data and functions. */
625	template <typename, typename, typename> friend struct vec;
626
627	/* The allocator types also need access to our internals. */
628	friend struct va_gc;
629	friend struct va_gc_atomic;
630	friend struct va_heap;
631
632	/* FIXME - These fields should be private, but we need to cater to
633	compilers that have stricter notions of PODness for types. */
634	vec_prefix m_vecpfx;
635	T m_vecdata[1];
636	};
637
638
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:
642
643	1- The pointer may be NULL (e.g., before initial allocation).
644
645	2- When the vector needs to grow, it must be reallocated, so
646	the pointer will change its value.
647
648	Because of limitations with the current GC machinery, all vectors
649	in GC memory *must* be pointers. */
650
651
652	/* If V contains no room for NELEMS elements, return false. Otherwise,
653	return true. */
654	template<typename T, typename A>
655	inline bool
656	vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
657	{
658	return v ? v->space (nelems) : nelems == 0;
659	}
660
661
662	/* If V is NULL, return 0. Otherwise, return V->length(). */
663	template<typename T, typename A>
664	inline unsigned
665	vec_safe_length (const vec<T, A, vl_embed> *v)
666	{
667	return v ? v->length () : 0;
668	}
669
670
671	/* If V is NULL, return NULL. Otherwise, return V->address(). */
672	template<typename T, typename A>
673	inline T *
674	vec_safe_address (vec<T, A, vl_embed> *v)
675	{
676	return v ? v->address () : NULL;
677	}
678
679
680	/* If V is NULL, return true. Otherwise, return V->is_empty(). */
681	template<typename T, typename A>
682	inline bool
683	vec_safe_is_empty (vec<T, A, vl_embed> *v)
684	{
685	return v ? v->is_empty () : true;
686	}
687
688	/* If V does not have space for NELEMS elements, call
689	V->reserve(NELEMS, EXACT). */
690	template<typename T, typename A>
691	inline bool
692	vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
693	CXX_MEM_STAT_INFO)
694	{
695	bool extend = nelems ? !vec_safe_space (v, nelems) : false;
696	if (extend)
697	A::reserve (v, nelems, exact PASS_MEM_STAT);
698	return extend;
699	}
700
701	template<typename T, typename A>
702	inline bool
703	vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
704	CXX_MEM_STAT_INFO)
705	{
706	return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
707	}
708
709
710	/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
711	is 0, V is initialized to NULL. */
712
713	template<typename T, typename A>
714	inline void
715	vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
716	{
717	v = NULL;
718	vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
719	}
720
721
722	/* Free the GC memory allocated by vector V and set it to NULL. */
723
724	template<typename T, typename A>
725	inline void
726	vec_free (vec<T, A, vl_embed> *&v)
727	{
728	A::release (v);
729	}
730
731
732	/* Grow V to length LEN. Allocate it, if necessary. */
733	template<typename T, typename A>
734	inline void
735	vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
736	bool exact = false CXX_MEM_STAT_INFO)
737	{
738	unsigned oldlen = vec_safe_length (v);
739	gcc_checking_assert (len >= oldlen);
740	vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
741	v->quick_grow (len);
742	}
743
744
745	/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
746	template<typename T, typename A>
747	inline void
748	vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
749	bool exact = false CXX_MEM_STAT_INFO)
750	{
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);
754	}
755
756
757	/* Assume V is not NULL. */
758
759	template<typename T>
760	inline void
761	vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
762	unsigned len, bool exact = false CXX_MEM_STAT_INFO)
763	{
764	v->safe_grow_cleared (len, exact PASS_MEM_STAT);
765	}
766
767	/* If V does not have space for NELEMS elements, call
768	V->reserve(NELEMS, EXACT). */
769
770	template<typename T>
771	inline bool
772	vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
773	CXX_MEM_STAT_INFO)
774	{
775	return v->reserve (nelems, exact);
776	}
777
778
779	/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
780	template<typename T, typename A>
781	inline bool
782	vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
783	{
784	if (v)
785	return v->iterate (ix, ptr);
786	else
787	{
788	*ptr = 0;
789	return false;
790	}
791	}
792
793	template<typename T, typename A>
794	inline bool
795	vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
796	{
797	if (v)
798	return v->iterate (ix, ptr);
799	else
800	{
801	*ptr = 0;
802	return false;
803	}
804	}
805
806
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>
810	inline T *
811	vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
812	{
813	vec_safe_reserve (v, 1, false PASS_MEM_STAT);
814	return v->quick_push (obj);
815	}
816
817
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>
821	inline void
822	vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
823	CXX_MEM_STAT_INFO)
824	{
825	vec_safe_reserve (v, 1, false PASS_MEM_STAT);
826	v->quick_insert (ix, obj);
827	}
828
829
830	/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
831	template<typename T, typename A>
832	inline void
833	vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
834	{
835	if (v)
836	v->truncate (size);
837	}
838
839
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)
844	{
845	return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
846	}
847
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>
851	inline void
852	vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
853	CXX_MEM_STAT_INFO)
854	{
855	unsigned src_len = vec_safe_length (src);
856	if (src_len)
857	{
858	vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
859	PASS_MEM_STAT);
860	dst->splice (*src);
861	}
862	}
863
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. */
866
867	template<typename T, typename A>
868	inline bool
869	vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
870	{
871	return v ? v->contains (search) : false;
872	}
873
874	/* Index into vector. Return the IX'th element. IX must be in the
875	domain of the vector. */
876
877	template<typename T, typename A>
878	inline const T &
879	vec<T, A, vl_embed>::operator[] (unsigned ix) const
880	{
881	gcc_checking_assert (ix < m_vecpfx.m_num);
882	return m_vecdata[ix];
883	}
884
885	template<typename T, typename A>
886	inline T &
887	vec<T, A, vl_embed>::operator[] (unsigned ix)
888	{
889	gcc_checking_assert (ix < m_vecpfx.m_num);
890	return m_vecdata[ix];
891	}
892
893
894	/* Get the final element of the vector, which must not be empty. */
895
896	template<typename T, typename A>
897	inline T &
898	vec<T, A, vl_embed>::last (void)
899	{
900	gcc_checking_assert (m_vecpfx.m_num > 0);
901	return (*this)[m_vecpfx.m_num - 1];
902	}
903
904
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
909	will. */
910
911	template<typename T, typename A>
912	inline bool
913	vec<T, A, vl_embed>::space (unsigned nelems) const
914	{
915	return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
916	}
917
918
919	/* Return iteration condition and update *PTR to (a copy of) the IX'th
920	element of this vector. Use this to iterate over the elements of a
921	vector as follows,
922
923	for (ix = 0; v->iterate (ix, &val); ix++)
924	continue; */
925
926	template<typename T, typename A>
927	inline bool
928	vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
929	{
930	if (ix < m_vecpfx.m_num)
931	{
932	*ptr = m_vecdata[ix];
933	return true;
934	}
935	else
936	{
937	*ptr = 0;
938	return false;
939	}
940	}
941
942
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,
946
947	for (ix = 0; v->iterate (ix, &ptr); ix++)
948	continue;
949
950	This variant is for vectors of objects. */
951
952	template<typename T, typename A>
953	inline bool
954	vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
955	{
956	if (ix < m_vecpfx.m_num)
957	{
958	*ptr = CONST_CAST (T *, &m_vecdata[ix]);
959	return true;
960	}
961	else
962	{
963	*ptr = 0;
964	return false;
965	}
966	}
967
968
969	/* Return a pointer to a copy of this vector. */
970
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
974	{
975	vec<T, A, vl_embed> *new_vec = NULL;
976	unsigned len = length ();
977	if (len)
978	{
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);
982	}
983	return new_vec;
984	}
985
986
987	/* Copy the elements from SRC to the end of this vector as if by memcpy.
988	The vector must have sufficient headroom available. */
989
990	template<typename T, typename A>
991	inline void
992	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
993	{
994	unsigned len = src.length ();
995	if (len)
996	{
997	gcc_checking_assert (space (len));
998	vec_copy_construct (end (), src.address (), len);
999	m_vecpfx.m_num += len;
1000	}
1001	}
1002
1003	template<typename T, typename A>
1004	inline void
1005	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1006	{
1007	if (src)
1008	splice (*src);
1009	}
1010
1011
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. */
1015
1016	template<typename T, typename A>
1017	inline T *
1018	vec<T, A, vl_embed>::quick_push (const T &obj)
1019	{
1020	gcc_checking_assert (space (1));
1021	T *slot = &m_vecdata[m_vecpfx.m_num++];
1022	*slot = obj;
1023	return slot;
1024	}
1025
1026
1027	/* Pop and return the last element off the end of the vector. */
1028
1029	template<typename T, typename A>
1030	inline T &
1031	vec<T, A, vl_embed>::pop (void)
1032	{
1033	gcc_checking_assert (length () > 0);
1034	return m_vecdata[--m_vecpfx.m_num];
1035	}
1036
1037
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. */
1040
1041	template<typename T, typename A>
1042	inline void
1043	vec<T, A, vl_embed>::truncate (unsigned size)
1044	{
1045	gcc_checking_assert (length () >= size);
1046	m_vecpfx.m_num = size;
1047	}
1048
1049
1050	/* Insert an element, OBJ, at the IXth position of this vector. There
1051	must be sufficient space. */
1052
1053	template<typename T, typename A>
1054	inline void
1055	vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1056	{
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));
1061	*slot = obj;
1062	}
1063
1064
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
1067	memmove. */
1068
1069	template<typename T, typename A>
1070	inline void
1071	vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1072	{
1073	gcc_checking_assert (ix < length ());
1074	T *slot = &m_vecdata[ix];
1075	memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1076	}
1077
1078
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. */
1081
1082	#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1083	elem_ptr, start, end, cond) \
1084	{ \
1085	gcc_assert ((end) <= (vec).length ()); \
1086	for (read_index = write_index = (start); read_index < (end); \
1087	++read_index) \
1088	{ \
1089	elem_ptr = &(vec)[read_index]; \
1090	bool remove_p = (cond); \
1091	if (remove_p) \
1092	continue; \
1093	\
1094	if (read_index != write_index) \
1095	(vec)[write_index] = (vec)[read_index]; \
1096	\
1097	write_index++; \
1098	} \
1099	\
1100	if (read_index - write_index > 0) \
1101	(vec).block_remove (write_index, read_index - write_index); \
1102	}
1103
1104
1105	/* Remove elements from VEC for which COND holds. Ordering of remaining
1106	elements is preserved. This is an O(N) operation. */
1107
1108	#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1109	cond) \
1110	VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1111	elem_ptr, 0, (vec).length (), (cond))
1112
1113	/* Remove an element from the IXth position of this vector. Ordering of
1114	remaining elements is destroyed. This is an O(1) operation. */
1115
1116	template<typename T, typename A>
1117	inline void
1118	vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1119	{
1120	gcc_checking_assert (ix < length ());
1121	m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1122	}
1123
1124
1125	/* Remove LEN elements starting at the IXth. Ordering is retained.
1126	This is an O(N) operation due to memmove. */
1127
1128	template<typename T, typename A>
1129	inline void
1130	vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1131	{
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));
1136	}
1137
1138
1139	/* Sort the contents of this vector with qsort. CMP is the comparison
1140	function to pass to qsort. */
1141
1142	template<typename T, typename A>
1143	inline void
1144	vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1145	{
1146	if (length () > 1)
1147	gcc_qsort (address (), length (), sizeof (T), cmp);
1148	}
1149
1150	/* Sort the contents of this vector with qsort. CMP is the comparison
1151	function to pass to qsort. */
1152
1153	template<typename T, typename A>
1154	inline void
1155	vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1156	void *data)
1157	{
1158	if (length () > 1)
1159	gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1160	}
1161
1162	/* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1163	comparison function to pass to qsort. */
1164
1165	template<typename T, typename A>
1166	inline void
1167	vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1168	void *), void *data)
1169	{
1170	if (length () > 1)
1171	gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1172	}
1173
1174	/* Search the contents of the sorted vector with a binary search.
1175	CMP is the comparison function to pass to bsearch. */
1176
1177	template<typename T, typename A>
1178	inline T *
1179	vec<T, A, vl_embed>::bsearch (const void *key,
1180	int (*compar) (const void *, const void *))
1181	{
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. */
1186	size_t l, u, idx;
1187	const void *p;
1188	int comparison;
1189
1190	l = 0;
1191	u = nmemb;
1192	while (l < u)
1193	{
1194	idx = (l + u) / 2;
1195	p = (const void *) (((const char *) base) + (idx * size));
1196	comparison = (*compar) (key, p);
1197	if (comparison < 0)
1198	u = idx;
1199	else if (comparison > 0)
1200	l = idx + 1;
1201	else
1202	return (T *)const_cast<void *>(p);
1203	}
1204
1205	return NULL;
1206	}
1207
1208	/* Search the contents of the sorted vector with a binary search.
1209	CMP is the comparison function to pass to bsearch. */
1210
1211	template<typename T, typename A>
1212	inline T *
1213	vec<T, A, vl_embed>::bsearch (const void *key,
1214	int (*compar) (const void *, const void *,
1215	void *), void *data)
1216	{
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. */
1221	size_t l, u, idx;
1222	const void *p;
1223	int comparison;
1224
1225	l = 0;
1226	u = nmemb;
1227	while (l < u)
1228	{
1229	idx = (l + u) / 2;
1230	p = (const void *) (((const char *) base) + (idx * size));
1231	comparison = (*compar) (key, p, data);
1232	if (comparison < 0)
1233	u = idx;
1234	else if (comparison > 0)
1235	l = idx + 1;
1236	else
1237	return (T *)const_cast<void *>(p);
1238	}
1239
1240	return NULL;
1241	}
1242
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. */
1245
1246	template<typename T, typename A>
1247	inline bool
1248	vec<T, A, vl_embed>::contains (const T &search) const
1249	{
1250	unsigned int len = length ();
1251	for (unsigned int i = 0; i < len; i++)
1252	if ((*this)[i] == search)
1253	return true;
1254
1255	return false;
1256	}
1257
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
1261	than the second. */
1262
1263	template<typename T, typename A>
1264	unsigned
1265	vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1266	const
1267	{
1268	unsigned int len = length ();
1269	unsigned int half, middle;
1270	unsigned int first = 0;
1271	while (len > 0)
1272	{
1273	half = len / 2;
1274	middle = first;
1275	middle += half;
1276	T middle_elem = (*this)[middle];
1277	if (lessthan (middle_elem, obj))
1278	{
1279	first = middle;
1280	++first;
1281	len = len - half - 1;
1282	}
1283	else
1284	len = half;
1285	}
1286	return first;
1287	}
1288
1289
1290	/* Return the number of bytes needed to embed an instance of an
1291	embeddable vec inside another data structure.
1292
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
1295	final member):
1296
1297	size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1298	void v->embedded_init (unsigned alloc, unsigned num);
1299
1300	These allow the caller to perform the memory allocation. */
1301
1302	template<typename T, typename A>
1303	inline size_t
1304	vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1305	{
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);
1313	}
1314
1315
1316	/* Initialize the vector to contain room for ALLOC elements and
1317	NUM active elements. */
1318
1319	template<typename T, typename A>
1320	inline void
1321	vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1322	{
1323	m_vecpfx.m_alloc = alloc;
1324	m_vecpfx.m_using_auto_storage = aut;
1325	m_vecpfx.m_num = num;
1326	}
1327
1328
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. */
1331
1332	template<typename T, typename A>
1333	inline void
1334	vec<T, A, vl_embed>::quick_grow (unsigned len)
1335	{
1336	gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1337	m_vecpfx.m_num = len;
1338	}
1339
1340
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. */
1343
1344	template<typename T, typename A>
1345	inline void
1346	vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1347	{
1348	unsigned oldlen = length ();
1349	size_t growby = len - oldlen;
1350	quick_grow (len);
1351	if (growby != 0)
1352	vec_default_construct (address () + oldlen, growby);
1353	}
1354
1355	/* Garbage collection support for vec<T, A, vl_embed>. */
1356
1357	template<typename T>
1358	void
1359	gt_ggc_mx (vec<T, va_gc> *v)
1360	{
1361	extern void gt_ggc_mx (T &);
1362	for (unsigned i = 0; i < v->length (); i++)
1363	gt_ggc_mx ((*v)[i]);
1364	}
1365
1366	template<typename T>
1367	void
1368	gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1369	{
1370	/* Nothing to do. Vectors of atomic types wrt GC do not need to
1371	be traversed. */
1372	}
1373
1374
1375	/* PCH support for vec<T, A, vl_embed>. */
1376
1377	template<typename T, typename A>
1378	void
1379	gt_pch_nx (vec<T, A, vl_embed> *v)
1380	{
1381	extern void gt_pch_nx (T &);
1382	for (unsigned i = 0; i < v->length (); i++)
1383	gt_pch_nx ((*v)[i]);
1384	}
1385
1386	template<typename T, typename A>
1387	void
1388	gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1389	{
1390	for (unsigned i = 0; i < v->length (); i++)
1391	op (&((*v)[i]), NULL, cookie);
1392	}
1393
1394	template<typename T, typename A>
1395	void
1396	gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1397	{
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);
1401	}
1402
1403
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.
1408
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.
1413
1414	Properties:
1415
1416	- The whole vector and control data are allocated in a single
1417	contiguous block.
1418	- The whole vector may be re-allocated.
1419	- Vector data may grow and shrink.
1420	- Access and manipulation requires a pointer test and
1421	indirection.
1422	- It requires 1 word of storage (prior to vector allocation).
1423
1424
1425	Limitations:
1426
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. */
1431
1432	template<typename T, size_t N = 0>
1433	class auto_vec;
1434
1435	template<typename T>
1436	struct vec<T, va_heap, vl_ptr>
1437	{
1438	public:
1439	/* Default ctors to ensure triviality. Use value-initialization
1440	(e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1441	instance. */
1442	vec () = default;
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. */
1447	~vec () = default;
1448
1449	/* Defaulted same as copy ctor. */
1450	vec& operator= (const vec &) = default;
1451
1452	/* Prevent implicit conversion from auto_vec. Use auto_vec::to_vec()
1453	instead. */
1454	template <size_t N>
1455	vec (auto_vec<T, N> &) = delete;
1456
1457	template <size_t N>
1458	void operator= (auto_vec<T, N> &) = delete;
1459
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);
1464
1465	/* Vector operations. */
1466	bool exists (void) const
1467	{ return m_vec != NULL; }
1468
1469	bool is_empty (void) const
1470	{ return m_vec ? m_vec->is_empty () : true; }
1471
1472	unsigned length (void) const
1473	{ return m_vec ? m_vec->length () : 0; }
1474
1475	T *address (void)
1476	{ return m_vec ? m_vec->m_vecdata : NULL; }
1477
1478	const T *address (void) const
1479	{ return m_vec ? m_vec->m_vecdata : NULL; }
1480
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]; }
1487
1488	bool operator!=(const vec &other) const
1489	{ return !(*this == other); }
1490
1491	bool operator==(const vec &other) const
1492	{ return address () == other.address (); }
1493
1494	T &operator[] (unsigned ix)
1495	{ return (*m_vec)[ix]; }
1496
1497	T &last (void)
1498	{ return m_vec->last (); }
1499
1500	bool space (int nelems) const
1501	{ return m_vec ? m_vec->space (nelems) : nelems == 0; }
1502
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);
1512	T &pop (void);
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);
1532
1533	bool using_auto_storage () const;
1534
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;
1538	};
1539
1540
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.
1546	*/
1547	template<typename T, size_t N /* = 0 */>
1548	class auto_vec : public vec<T, va_heap>
1549	{
1550	public:
1551	auto_vec ()
1552	{
1553	m_auto.embedded_init (MAX (N, 2), 0, 1);
1554	this->m_vec = &m_auto;
1555	}
1556
1557	auto_vec (size_t s CXX_MEM_STAT_INFO)
1558	{
1559	if (s > N)
1560	{
1561	this->create (s PASS_MEM_STAT);
1562	return;
1563	}
1564
1565	m_auto.embedded_init (MAX (N, 2), 0, 1);
1566	this->m_vec = &m_auto;
1567	}
1568
1569	~auto_vec ()
1570	{
1571	this->release ();
1572	}
1573
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);
1580	}
1581
1582	private:
1583	vec<T, va_heap, vl_embed> m_auto;
1584	T m_data[MAX (N - 1, 1)];
1585	};
1586
1587	/* auto_vec is a sub class of vec whose storage is released when it is
1588	destroyed. */
1589	template<typename T>
1590	class auto_vec<T, 0> : public vec<T, va_heap>
1591	{
1592	public:
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 (); }
1596
1597	auto_vec (vec<T, va_heap>&& r)
1598	{
1599	gcc_assert (!r.using_auto_storage ());
1600	this->m_vec = r.m_vec;
1601	r.m_vec = NULL;
1602	}
1603
1604	auto_vec (auto_vec<T> &&r)
1605	{
1606	gcc_assert (!r.using_auto_storage ());
1607	this->m_vec = r.m_vec;
1608	r.m_vec = NULL;
1609	}
1610
1611	auto_vec& operator= (vec<T, va_heap>&& r)
1612	{
1613	if (this == &r)
1614	return *this;
1615
1616	gcc_assert (!r.using_auto_storage ());
1617	this->release ();
1618	this->m_vec = r.m_vec;
1619	r.m_vec = NULL;
1620	return *this;
1621	}
1622
1623	auto_vec& operator= (auto_vec<T> &&r)
1624	{
1625	if (this == &r)
1626	return *this;
1627
1628	gcc_assert (!r.using_auto_storage ());
1629	this->release ();
1630	this->m_vec = r.m_vec;
1631	r.m_vec = NULL;
1632	return *this;
1633	}
1634
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);
1641	}
1642
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
1645	// can use copy ().
1646	auto_vec(const auto_vec &) = delete;
1647	auto_vec &operator= (const auto_vec &) = delete;
1648	};
1649
1650
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. */
1654
1655	template<typename T>
1656	inline void
1657	vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1658	{
1659	v = new vec<T>;
1660	v->create (nelems PASS_MEM_STAT);
1661	}
1662
1663
1664	/* A subclass of auto_vec <char *> that frees all of its elements on
1665	deletion. */
1666
1667	class auto_string_vec : public auto_vec <char *>
1668	{
1669	public:
1670	~auto_string_vec ();
1671	};
1672
1673	/* A subclass of auto_vec <T *> that deletes all of its elements on
1674	destruction.
1675
1676	This is a crude way for a vec to "own" the objects it points to
1677	and clean up automatically.
1678
1679	For example, no attempt is made to delete elements when an item
1680	within the vec is overwritten.
1681
1682	We can't rely on gnu::unique_ptr within a container,
1683	since we can't rely on move semantics in C++98. */
1684
1685	template <typename T>
1686	class auto_delete_vec : public auto_vec <T *>
1687	{
1688	public:
1689	auto_delete_vec () {}
1690	auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1691
1692	~auto_delete_vec ();
1693
1694	private:
1695	DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1696	};
1697
1698	/* Conditionally allocate heap memory for VEC and its internal vector. */
1699
1700	template<typename T>
1701	inline void
1702	vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1703	{
1704	if (!vec)
1705	vec_alloc (vec, nelems PASS_MEM_STAT);
1706	}
1707
1708
1709	/* Free the heap memory allocated by vector V and set it to NULL. */
1710
1711	template<typename T>
1712	inline void
1713	vec_free (vec<T> *&v)
1714	{
1715	if (v == NULL)
1716	return;
1717
1718	v->release ();
1719	delete v;
1720	v = NULL;
1721	}
1722
1723
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
1726	vector as follows,
1727
1728	for (ix = 0; v.iterate (ix, &ptr); ix++)
1729	continue; */
1730
1731	template<typename T>
1732	inline bool
1733	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1734	{
1735	if (m_vec)
1736	return m_vec->iterate (ix, ptr);
1737	else
1738	{
1739	*ptr = 0;
1740	return false;
1741	}
1742	}
1743
1744
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,
1748
1749	for (ix = 0; v->iterate (ix, &ptr); ix++)
1750	continue;
1751
1752	This variant is for vectors of objects. */
1753
1754	template<typename T>
1755	inline bool
1756	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1757	{
1758	if (m_vec)
1759	return m_vec->iterate (ix, ptr);
1760	else
1761	{
1762	*ptr = 0;
1763	return false;
1764	}
1765	}
1766
1767
1768	/* Convenience macro for forward iteration. */
1769	#define FOR_EACH_VEC_ELT(V, I, P) \
1770	for (I = 0; (V).iterate ((I), &(P)); ++(I))
1771
1772	#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1773	for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1774
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))
1778
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)); \
1783	(I)--)
1784
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)); \
1788	(I)--)
1789
1790	/* auto_string_vec's dtor, freeing all contained strings, automatically
1791	chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1792
1793	inline
1794	auto_string_vec::~auto_string_vec ()
1795	{
1796	int i;
1797	char *str;
1798	FOR_EACH_VEC_ELT (*this, i, str)
1799	free (str);
1800	}
1801
1802	/* auto_delete_vec's dtor, deleting all contained items, automatically
1803	chaining up to ~auto_vec <T*>, which frees the internal buffer. */
1804
1805	template <typename T>
1806	inline
1807	auto_delete_vec<T>::~auto_delete_vec ()
1808	{
1809	int i;
1810	T *item;
1811	FOR_EACH_VEC_ELT (*this, i, item)
1812	delete item;
1813	}
1814
1815
1816	/* Return a copy of this vector. */
1817
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
1821	{
1822	vec<T, va_heap, vl_ptr> new_vec{ };
1823	if (length ())
1824	new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1825	return new_vec;
1826	}
1827
1828
1829	/* Ensure that the vector has at least RESERVE slots available (if
1830	EXACT is false), or exactly RESERVE slots available (if EXACT is
1831	true).
1832
1833	This may create additional headroom if EXACT is false.
1834
1835	Note that this can cause the embedded vector to be reallocated.
1836	Returns true iff reallocation actually occurred. */
1837
1838	template<typename T>
1839	inline bool
1840	vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1841	{
1842	if (space (nelems))
1843	return false;
1844
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)
1852	{
1853	m_vec = NULL;
1854	oldsize = oldvec->length ();
1855	nelems += oldsize;
1856	}
1857
1858	va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1859	if (handle_auto_vec)
1860	{
1861	vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1862	m_vec->m_vecpfx.m_num = oldsize;
1863	}
1864
1865	return true;
1866	}
1867
1868
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. */
1873
1874	template<typename T>
1875	inline bool
1876	vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1877	{
1878	return reserve (nelems, true PASS_MEM_STAT);
1879	}
1880
1881
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. */
1886
1887	template<typename T>
1888	inline void
1889	vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1890	{
1891	m_vec = NULL;
1892	if (nelems > 0)
1893	reserve_exact (nelems PASS_MEM_STAT);
1894	}
1895
1896
1897	/* Free the memory occupied by the embedded vector. */
1898
1899	template<typename T>
1900	inline void
1901	vec<T, va_heap, vl_ptr>::release (void)
1902	{
1903	if (!m_vec)
1904	return;
1905
1906	if (using_auto_storage ())
1907	{
1908	m_vec->m_vecpfx.m_num = 0;
1909	return;
1910	}
1911
1912	va_heap::release (m_vec);
1913	}
1914
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. */
1919
1920	template<typename T>
1921	inline void
1922	vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1923	{
1924	if (src.length ())
1925	m_vec->splice (*(src.m_vec));
1926	}
1927
1928
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
1932	as needed. */
1933
1934	template<typename T>
1935	inline void
1936	vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1937	MEM_STAT_DECL)
1938	{
1939	if (src.length ())
1940	{
1941	reserve_exact (src.length ());
1942	splice (src);
1943	}
1944	}
1945
1946
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. */
1950
1951	template<typename T>
1952	inline T *
1953	vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1954	{
1955	return m_vec->quick_push (obj);
1956	}
1957
1958
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. */
1962
1963	template<typename T>
1964	inline T *
1965	vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1966	{
1967	reserve (1, false PASS_MEM_STAT);
1968	return quick_push (obj);
1969	}
1970
1971
1972	/* Pop and return the last element off the end of the vector. */
1973
1974	template<typename T>
1975	inline T &
1976	vec<T, va_heap, vl_ptr>::pop (void)
1977	{
1978	return m_vec->pop ();
1979	}
1980
1981
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. */
1984
1985	template<typename T>
1986	inline void
1987	vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1988	{
1989	if (m_vec)
1990	m_vec->truncate (size);
1991	else
1992	gcc_checking_assert (size == 0);
1993	}
1994
1995
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. */
1999
2000	template<typename T>
2001	inline void
2002	vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2003	{
2004	unsigned oldlen = length ();
2005	gcc_checking_assert (oldlen <= len);
2006	reserve (len - oldlen, exact PASS_MEM_STAT);
2007	if (m_vec)
2008	m_vec->quick_grow (len);
2009	else
2010	gcc_checking_assert (len == 0);
2011	}
2012
2013
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. */
2017
2018	template<typename T>
2019	inline void
2020	vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2021	MEM_STAT_DECL)
2022	{
2023	unsigned oldlen = length ();
2024	size_t growby = len - oldlen;
2025	safe_grow (len, exact PASS_MEM_STAT);
2026	if (growby != 0)
2027	vec_default_construct (address () + oldlen, growby);
2028	}
2029
2030
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. */
2033
2034	template<typename T>
2035	inline void
2036	vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2037	{
2038	gcc_checking_assert (m_vec);
2039	m_vec->quick_grow (len);
2040	}
2041
2042
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. */
2046
2047	template<typename T>
2048	inline void
2049	vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2050	{
2051	gcc_checking_assert (m_vec);
2052	m_vec->quick_grow_cleared (len);
2053	}
2054
2055
2056	/* Insert an element, OBJ, at the IXth position of this vector. There
2057	must be sufficient space. */
2058
2059	template<typename T>
2060	inline void
2061	vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2062	{
2063	m_vec->quick_insert (ix, obj);
2064	}
2065
2066
2067	/* Insert an element, OBJ, at the IXth position of the vector.
2068	Reallocate the embedded vector, if necessary. */
2069
2070	template<typename T>
2071	inline void
2072	vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2073	{
2074	reserve (1, false PASS_MEM_STAT);
2075	quick_insert (ix, obj);
2076	}
2077
2078
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
2081	a memmove. */
2082
2083	template<typename T>
2084	inline void
2085	vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2086	{
2087	m_vec->ordered_remove (ix);
2088	}
2089
2090
2091	/* Remove an element from the IXth position of this vector. Ordering
2092	of remaining elements is destroyed. This is an O(1) operation. */
2093
2094	template<typename T>
2095	inline void
2096	vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2097	{
2098	m_vec->unordered_remove (ix);
2099	}
2100
2101
2102	/* Remove LEN elements starting at the IXth. Ordering is retained.
2103	This is an O(N) operation due to memmove. */
2104
2105	template<typename T>
2106	inline void
2107	vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2108	{
2109	m_vec->block_remove (ix, len);
2110	}
2111
2112
2113	/* Sort the contents of this vector with qsort. CMP is the comparison
2114	function to pass to qsort. */
2115
2116	template<typename T>
2117	inline void
2118	vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
2119	{
2120	if (m_vec)
2121	m_vec->qsort (cmp);
2122	}
2123
2124	/* Sort the contents of this vector with qsort. CMP is the comparison
2125	function to pass to qsort. */
2126
2127	template<typename T>
2128	inline void
2129	vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
2130	void *), void *data)
2131	{
2132	if (m_vec)
2133	m_vec->sort (cmp, data);
2134	}
2135
2136	/* Sort the contents of this vector with gcc_stablesort_r. CMP is the
2137	comparison function to pass to qsort. */
2138
2139	template<typename T>
2140	inline void
2141	vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *,
2142	void *), void *data)
2143	{
2144	if (m_vec)
2145	m_vec->stablesort (cmp, data);
2146	}
2147
2148	/* Search the contents of the sorted vector with a binary search.
2149	CMP is the comparison function to pass to bsearch. */
2150
2151	template<typename T>
2152	inline T *
2153	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2154	int (*cmp) (const void *, const void *))
2155	{
2156	if (m_vec)
2157	return m_vec->bsearch (key, cmp);
2158	return NULL;
2159	}
2160
2161	/* Search the contents of the sorted vector with a binary search.
2162	CMP is the comparison function to pass to bsearch. */
2163
2164	template<typename T>
2165	inline T *
2166	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2167	int (*cmp) (const void *, const void *,
2168	void *), void *data)
2169	{
2170	if (m_vec)
2171	return m_vec->bsearch (key, cmp, data);
2172	return NULL;
2173	}
2174
2175
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
2179	than the second. */
2180
2181	template<typename T>
2182	inline unsigned
2183	vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2184	bool (*lessthan)(const T &, const T &))
2185	const
2186	{
2187	return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
2188	}
2189
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. */
2192
2193	template<typename T>
2194	inline bool
2195	vec<T, va_heap, vl_ptr>::contains (const T &search) const
2196	{
2197	return m_vec ? m_vec->contains (search) : false;
2198	}
2199
2200	/* Reverse content of the vector. */
2201
2202	template<typename T>
2203	inline void
2204	vec<T, va_heap, vl_ptr>::reverse (void)
2205	{
2206	unsigned l = length ();
2207	T *ptr = address ();
2208
2209	for (unsigned i = 0; i < l / 2; i++)
2210	std::swap (ptr[i], ptr[l - i - 1]);
2211	}
2212
2213	template<typename T>
2214	inline bool
2215	vec<T, va_heap, vl_ptr>::using_auto_storage () const
2216	{
2217	return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2218	}
2219
2220	/* Release VEC and call release of all element vectors. */
2221
2222	template<typename T>
2223	inline void
2224	release_vec_vec (vec<vec<T> > &vec)
2225	{
2226	for (unsigned i = 0; i < vec.length (); i++)
2227	vec[i].release ();
2228
2229	vec.release ();
2230	}
2231
2232	// Provide a subset of the std::span functionality. (We can't use std::span
2233	// itself because it's a C++20 feature.)
2234	//
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.
2238	//
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>
2242	class array_slice
2243	{
2244	template<typename OtherT> friend class array_slice;
2245
2246	public:
2247	using value_type = T;
2248	using iterator = T *;
2249	using const_iterator = const T *;
2250
2251	array_slice () : m_base (nullptr), m_size (0) {}
2252
2253	template<typename OtherT>
2254	array_slice (array_slice<OtherT> other)
2255	: m_base (other.m_base), m_size (other.m_size) {}
2256
2257	array_slice (iterator base, unsigned int size)
2258	: m_base (base), m_size (size) {}
2259
2260	template<size_t N>
2261	array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2262
2263	template<typename OtherT>
2264	array_slice (const vec<OtherT> &v)
2265	: m_base (v.address ()), m_size (v.length ()) {}
2266
2267	iterator begin () { return m_base; }
2268	iterator end () { return m_base + m_size; }
2269
2270	const_iterator begin () const { return m_base; }
2271	const_iterator end () const { return m_base + m_size; }
2272
2273	value_type &front ();
2274	value_type &back ();
2275	value_type &operator[] (unsigned int i);
2276
2277	const value_type &front () const;
2278	const value_type &back () const;
2279	const value_type &operator[] (unsigned int i) const;
2280
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; }
2284
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 }; }
2288
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; }
2291
2292	private:
2293	iterator m_base;
2294	unsigned int m_size;
2295	};
2296
2297	template<typename T>
2298	inline typename array_slice<T>::value_type &
2299	array_slice<T>::front ()
2300	{
2301	gcc_checking_assert (m_size);
2302	return m_base[0];
2303	}
2304
2305	template<typename T>
2306	inline const typename array_slice<T>::value_type &
2307	array_slice<T>::front () const
2308	{
2309	gcc_checking_assert (m_size);
2310	return m_base[0];
2311	}
2312
2313	template<typename T>
2314	inline typename array_slice<T>::value_type &
2315	array_slice<T>::back ()
2316	{
2317	gcc_checking_assert (m_size);
2318	return m_base[m_size - 1];
2319	}
2320
2321	template<typename T>
2322	inline const typename array_slice<T>::value_type &
2323	array_slice<T>::back () const
2324	{
2325	gcc_checking_assert (m_size);
2326	return m_base[m_size - 1];
2327	}
2328
2329	template<typename T>
2330	inline typename array_slice<T>::value_type &
2331	array_slice<T>::operator[] (unsigned int i)
2332	{
2333	gcc_checking_assert (i < m_size);
2334	return m_base[i];
2335	}
2336
2337	template<typename T>
2338	inline const typename array_slice<T>::value_type &
2339	array_slice<T>::operator[] (unsigned int i) const
2340	{
2341	gcc_checking_assert (i < m_size);
2342	return m_base[i];
2343	}
2344
2345	template<typename T>
2346	array_slice<T>
2347	make_array_slice (T *base, unsigned int size)
2348	{
2349	return array_slice<T> (base, size);
2350	}
2351
2352	#if (GCC_VERSION >= 3000)
2353	# pragma GCC poison m_vec m_vecpfx m_vecdata
2354	#endif
2355
2356	#endif // GCC_VEC_H
2357