vec.h source code [gcc/vec.h]

1	/ Vector API for GNU compiler.*
2	Copyright (C) 2004-2024 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	T &last (void);
615	bool space (unsigned) const;
616	bool iterate (unsigned, T ) const*;
617	bool iterate (unsigned, T *) const*;
618	vec copy (ALONE_CXX_MEM_STAT_INFO) const*;
619	void splice (const vec &);
620	void splice (const vec *src);
621	T quick_push (const* T &);
622	using pop_ret_type
623	= typename std::conditional <std::is_trivially_destructible <T>::value,
624	T &, void>::type;
625	pop_ret_type pop (void);
626	void truncate (unsigned);
627	void quick_insert (unsigned, const T &);
628	void ordered_remove (unsigned);
629	void unordered_remove (unsigned);
630	void block_remove (unsigned, unsigned);
631	void qsort (int () (const* void , const* void *));
632	void sort (int () (const* void , const* void , void* ), void* *);
633	void stablesort (int () (const* void , const* void , void* ), void* *);
634	T bsearch (const* void key, int* (compar) (const* void , const* void *));
635	T bsearch (const* void *key,
636	int (compar)(const* void , const* void , void* ), void* *);
637	unsigned lower_bound (const T &, bool () (const* T &, const T &)) const;
638	bool contains (const T &search) const;
639	static size_t embedded_size (unsigned);
640	void embedded_init (unsigned, unsigned = `0`, unsigned = `0`);
641	void quick_grow (unsigned len);
642	void quick_grow_cleared (unsigned len);
643
644	/ vec class can access our internal data and functions. /
645	template <typename, typename, typename> friend struct vec;
646
647	/ The allocator types also need access to our internals. /
648	friend struct va_gc;
649	friend struct va_gc_atomic;
650	friend struct va_heap;
651
652	/ FIXME - This field should be private, but we need to cater to*
653	compilers that have stricter notions of PODness for types. /*
654	/ Align m_vecpfx to simplify address (). /
655	alignas (T) alignas (vec_prefix) vec_prefix m_vecpfx;
656	};
657
658
659	/ Convenience wrapper functions to use when dealing with pointers to*
660	embedded vectors. Some functionality for these vectors must be
661	provided via free functions for these reasons:
662
663	1- The pointer may be NULL (e.g., before initial allocation).
664
665	2- When the vector needs to grow, it must be reallocated, so
666	the pointer will change its value.
667
668	Because of limitations with the current GC machinery, all vectors
669	in GC memory must* be pointers. /
670
671
672	/ If V contains no room for NELEMS elements, return false. Otherwise,*
673	return true. /*
674	template<typename T, typename A>
675	inline bool
676	vec_safe_space (const vec<T, A, vl_embed> v, unsigned* nelems)
677	{
678	return v ? v->space (nelems) : nelems == `0`;
679	}
680
681
682	/ If V is NULL, return 0. Otherwise, return V->length(). /
683	template<typename T, typename A>
684	inline unsigned
685	vec_safe_length (const vec<T, A, vl_embed> *v)
686	{
687	return v ? v->length () : `0`;
688	}
689
690
691	/ If V is NULL, return NULL. Otherwise, return V->address(). /
692	template<typename T, typename A>
693	inline T *
694	vec_safe_address (vec<T, A, vl_embed> *v)
695	{
696	return v ? v->address () : NULL;
697	}
698
699
700	/ If V is NULL, return true. Otherwise, return V->is_empty(). /
701	template<typename T, typename A>
702	inline bool
703	vec_safe_is_empty (vec<T, A, vl_embed> *v)
704	{
705	return v ? v->is_empty () : true;
706	}
707
708	/ If V does not have space for NELEMS elements, call*
709	V->reserve(NELEMS, EXACT). /*
710	template<typename T, typename A>
711	inline bool
712	vec_safe_reserve (vec<T, A, vl_embed> &v, unsigned* nelems, bool exact = false
713	CXX_MEM_STAT_INFO)
714	{
715	bool extend = nelems ? !vec_safe_space (v, nelems) : false;
716	if (extend)
717	A::reserve (v, nelems, exact PASS_MEM_STAT);
718	return extend;
719	}
720
721	template<typename T, typename A>
722	inline bool
723	vec_safe_reserve_exact (vec<T, A, vl_embed> &v, unsigned* nelems
724	CXX_MEM_STAT_INFO)
725	{
726	return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
727	}
728
729
730	/ Allocate GC memory for V with space for NELEMS slots. If NELEMS*
731	is 0, V is initialized to NULL. /*
732
733	template<typename T, typename A>
734	inline void
735	vec_alloc (vec<T, A, vl_embed> &v, unsigned* nelems CXX_MEM_STAT_INFO)
736	{
737	v = NULL;
738	vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
739	}
740
741
742	/ Free the GC memory allocated by vector V and set it to NULL. /
743
744	template<typename T, typename A>
745	inline void
746	vec_free (vec<T, A, vl_embed> *&v)
747	{
748	A::release (v);
749	}
750
751
752	/ Grow V to length LEN. Allocate it, if necessary. /
753	template<typename T, typename A>
754	inline void
755	vec_safe_grow (vec<T, A, vl_embed> &v, unsigned* len,
756	bool exact = false CXX_MEM_STAT_INFO)
757	{
758	unsigned oldlen = vec_safe_length (v);
759	gcc_checking_assert (len >= oldlen);
760	vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
761	v->quick_grow (len);
762	}
763
764
765	/ If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). /
766	template<typename T, typename A>
767	inline void
768	vec_safe_grow_cleared (vec<T, A, vl_embed> &v, unsigned* len,
769	bool exact = false CXX_MEM_STAT_INFO)
770	{
771	unsigned oldlen = vec_safe_length (v);
772	gcc_checking_assert (len >= oldlen);
773	vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
774	v->quick_grow_cleared (len);
775	}
776
777
778	/ Assume V is not NULL. /
779
780	template<typename T>
781	inline void
782	vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
783	unsigned len, bool exact = false CXX_MEM_STAT_INFO)
784	{
785	v->safe_grow_cleared (len, exact PASS_MEM_STAT);
786	}
787
788	/ If V does not have space for NELEMS elements, call*
789	V->reserve(NELEMS, EXACT). /*
790
791	template<typename T>
792	inline bool
793	vec_safe_reserve (vec<T, va_heap, vl_ptr> &v, unsigned* nelems, bool exact = false
794	CXX_MEM_STAT_INFO)
795	{
796	return v->reserve (nelems, exact);
797	}
798
799
800	/ If V is NULL return false, otherwise return V->iterate(IX, PTR). /
801	template<typename T, typename A>
802	inline bool
803	vec_safe_iterate (const vec<T, A, vl_embed> v, unsigned* ix, T **ptr)
804	{
805	if (v)
806	return v->iterate (ix, ptr);
807	else
808	{
809	*ptr = `0`;
810	return false;
811	}
812	}
813
814	template<typename T, typename A>
815	inline bool
816	vec_safe_iterate (const vec<T, A, vl_embed> v, unsigned* ix, T *ptr)
817	{
818	if (v)
819	return v->iterate (ix, ptr);
820	else
821	{
822	*ptr = `0`;
823	return false;
824	}
825	}
826
827
828	/ If V has no room for one more element, reallocate it. Then call*
829	V->quick_push(OBJ). /*
830	template<typename T, typename A>
831	inline T *
832	vec_safe_push (vec<T, A, vl_embed> &v, const* T &obj CXX_MEM_STAT_INFO)
833	{
834	vec_safe_reserve (v, `1`, false PASS_MEM_STAT);
835	return v->quick_push (obj);
836	}
837
838
839	/ if V has no room for one more element, reallocate it. Then call*
840	V->quick_insert(IX, OBJ). /*
841	template<typename T, typename A>
842	inline void
843	vec_safe_insert (vec<T, A, vl_embed> &v, unsigned* ix, const T &obj
844	CXX_MEM_STAT_INFO)
845	{
846	vec_safe_reserve (v, `1`, false PASS_MEM_STAT);
847	v->quick_insert (ix, obj);
848	}
849
850
851	/ If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). /
852	template<typename T, typename A>
853	inline void
854	vec_safe_truncate (vec<T, A, vl_embed> v, unsigned* size)
855	{
856	if (v)
857	v->truncate (size);
858	}
859
860
861	/ If SRC is not NULL, return a pointer to a copy of it. /
862	template<typename T, typename A>
863	inline vec<T, A, vl_embed> *
864	vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
865	{
866	return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
867	}
868
869	/ Copy the elements from SRC to the end of DST as if by memcpy.*
870	Reallocate DST, if necessary. /*
871	template<typename T, typename A>
872	inline void
873	vec_safe_splice (vec<T, A, vl_embed> &dst, const* vec<T, A, vl_embed> *src
874	CXX_MEM_STAT_INFO)
875	{
876	unsigned src_len = vec_safe_length (src);
877	if (src_len)
878	{
879	vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
880	PASS_MEM_STAT);
881	dst->splice (*src);
882	}
883	}
884
885	/ Return true if SEARCH is an element of V. Note that this is O(N) in the*
886	size of the vector and so should be used with care. /*
887
888	template<typename T, typename A>
889	inline bool
890	vec_safe_contains (vec<T, A, vl_embed> v, const* T &search)
891	{
892	return v ? v->contains (search) : false;
893	}
894
895	/ Index into vector. Return the IX'th element. IX must be in the*
896	domain of the vector. /*
897
898	template<typename T, typename A>
899	inline const T &
900	vec<T, A, vl_embed>::operator[] (unsigned ix) const
901	{
902	gcc_checking_assert (ix < m_vecpfx.m_num);
903	return address ()[ix];
904	}
905
906	template<typename T, typename A>
907	inline T &
908	vec<T, A, vl_embed>::operator[] (unsigned ix)
909	{
910	gcc_checking_assert (ix < m_vecpfx.m_num);
911	return address ()[ix];
912	}
913
914
915	/ Get the final element of the vector, which must not be empty. /
916
917	template<typename T, typename A>
918	inline T &
919	vec<T, A, vl_embed>::last (void)
920	{
921	gcc_checking_assert (m_vecpfx.m_num > `0`);
922	return (*this)[m_vecpfx.m_num - `1`];
923	}
924
925
926	/ If this vector has space for NELEMS additional entries, return*
927	true. You usually only need to use this if you are doing your
928	own vector reallocation, for instance on an embedded vector. This
929	returns true in exactly the same circumstances that vec::reserve
930	will. /*
931
932	template<typename T, typename A>
933	inline bool
934	vec<T, A, vl_embed>::space (unsigned nelems) const
935	{
936	return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
937	}
938
939
940	/ Return iteration condition and update PTR to (a copy of) the IX'th
941	element of this vector. Use this to iterate over the elements of a
942	vector as follows,
943
944	for (ix = 0; v->iterate (ix, &val); ix++)
945	continue; /*
946
947	template<typename T, typename A>
948	inline bool
949	vec<T, A, vl_embed>::iterate (unsigned ix, T ptr) const*
950	{
951	if (ix < m_vecpfx.m_num)
952	{
953	*ptr = address ()[ix];
954	return true;
955	}
956	else
957	{
958	*ptr = `0`;
959	return false;
960	}
961	}
962
963
964	/ Return iteration condition and update PTR to point to the
965	IX'th element of this vector. Use this to iterate over the
966	elements of a vector as follows,
967
968	for (ix = 0; v->iterate (ix, &ptr); ix++)
969	continue;
970
971	This variant is for vectors of objects. /*
972
973	template<typename T, typename A>
974	inline bool
975	vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const*
976	{
977	if (ix < m_vecpfx.m_num)
978	{
979	ptr = CONST_CAST (T , &address ()[ix]);
980	return true;
981	}
982	else
983	{
984	*ptr = `0`;
985	return false;
986	}
987	}
988
989
990	/ Return a pointer to a copy of this vector. /
991
992	template<typename T, typename A>
993	inline vec<T, A, vl_embed> *
994	vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
995	{
996	vec<T, A, vl_embed> *new_vec = NULL;
997	unsigned len = length ();
998	if (len)
999	{
1000	vec_alloc (new_vec, len PASS_MEM_STAT);
1001	new_vec->embedded_init (len, len);
1002	vec_copy_construct (new_vec->address (), address (), len);
1003	}
1004	return new_vec;
1005	}
1006
1007
1008	/ Copy the elements from SRC to the end of this vector as if by memcpy.*
1009	The vector must have sufficient headroom available. /*
1010
1011	template<typename T, typename A>
1012	inline void
1013	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
1014	{
1015	unsigned len = src.length ();
1016	if (len)
1017	{
1018	gcc_checking_assert (space (len));
1019	vec_copy_construct (end (), src.address (), len);
1020	m_vecpfx.m_num += len;
1021	}
1022	}
1023
1024	template<typename T, typename A>
1025	inline void
1026	vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1027	{
1028	if (src)
1029	splice (*src);
1030	}
1031
1032
1033	/ Push OBJ (a new element) onto the end of the vector. There must be*
1034	sufficient space in the vector. Return a pointer to the slot
1035	where OBJ was inserted. /*
1036
1037	template<typename T, typename A>
1038	inline T *
1039	vec<T, A, vl_embed>::quick_push (const T &obj)
1040	{
1041	gcc_checking_assert (space (`1`));
1042	T *slot = &address ()[m_vecpfx.m_num++];
1043	::new (static_cast<void*>(slot)) T (obj);
1044	return slot;
1045	}
1046
1047
1048	/ Pop and return a reference to the last element off the end of the*
1049	vector. If T has non-trivial destructor, this method just pops
1050	the element and returns void type. /*
1051
1052	template<typename T, typename A>
1053	inline typename vec<T, A, vl_embed>::pop_ret_type
1054	vec<T, A, vl_embed>::pop (void)
1055	{
1056	gcc_checking_assert (length () > `0`);
1057	T &last = address ()[--m_vecpfx.m_num];
1058	if (!std::is_trivially_destructible <T>::value)
1059	last.~T ();
1060	return static_cast <pop_ret_type> (last);
1061	}
1062
1063
1064	/ Set the length of the vector to SIZE. The new length must be less*
1065	than or equal to the current length. This is an O(1) operation. /*
1066
1067	template<typename T, typename A>
1068	inline void
1069	vec<T, A, vl_embed>::truncate (unsigned size)
1070	{
1071	unsigned l = length ();
1072	gcc_checking_assert (l >= size);
1073	if (!std::is_trivially_destructible <T>::value)
1074	vec_destruct (address () + size, l - size);
1075	m_vecpfx.m_num = size;
1076	}
1077
1078
1079	/ Insert an element, OBJ, at the IXth position of this vector. There*
1080	must be sufficient space. This operation is not suitable for non-trivially
1081	copyable types. /*
1082
1083	template<typename T, typename A>
1084	inline void
1085	vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1086	{
1087	gcc_checking_assert (length () < allocated ());
1088	gcc_checking_assert (ix <= length ());
1089	#if GCC_VERSION >= 5000
1090	/ GCC 4.8 and 4.9 only implement std::is_trivially_destructible,*
1091	but not std::is_trivially_copyable nor
1092	std::is_trivially_default_constructible. /*
1093	static_assert (std::is_trivially_copyable <T>::value, "");
1094	#endif
1095	T *slot = &address ()[ix];
1096	memmove (slot + `1`, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1097	*slot = obj;
1098	}
1099
1100
1101	/ Remove an element from the IXth position of this vector. Ordering of*
1102	remaining elements is preserved. This is an O(N) operation due to
1103	memmove. Not suitable for non-trivially copyable types. /*
1104
1105	template<typename T, typename A>
1106	inline void
1107	vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1108	{
1109	gcc_checking_assert (ix < length ());
1110	#if GCC_VERSION >= 5000
1111	static_assert (std::is_trivially_copyable <T>::value, "");
1112	#endif
1113	T *slot = &address ()[ix];
1114	memmove (slot, slot + `1`, (--m_vecpfx.m_num - ix) * sizeof (T));
1115	}
1116
1117
1118	/ Remove elements in [START, END) from VEC for which COND holds. Ordering of*
1119	remaining elements is preserved. This is an O(N) operation. /*
1120
1121	#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1122	elem_ptr, start, end, cond) \
1123	{ \
1124	gcc_assert ((end) <= (vec).length ()); \
1125	for (read_index = write_index = (start); read_index < (end); \
1126	++read_index) \
1127	{ \
1128	elem_ptr = &(vec)[read_index]; \
1129	bool remove_p = (cond); \
1130	if (remove_p) \
1131	continue; \
1132	\
1133	if (read_index != write_index) \
1134	(vec)[write_index] = (vec)[read_index]; \
1135	\
1136	write_index++; \
1137	} \
1138	\
1139	if (read_index - write_index > 0) \
1140	(vec).block_remove (write_index, read_index - write_index); \
1141	}
1142
1143
1144	/ Remove elements from VEC for which COND holds. Ordering of remaining*
1145	elements is preserved. This is an O(N) operation. /*
1146
1147	#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1148	cond) \
1149	VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1150	elem_ptr, 0, (vec).length (), (cond))
1151
1152	/ Remove an element from the IXth position of this vector. Ordering of*
1153	remaining elements is destroyed. This is an O(1) operation. /*
1154
1155	template<typename T, typename A>
1156	inline void
1157	vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1158	{
1159	gcc_checking_assert (ix < length ());
1160	#if GCC_VERSION >= 5000
1161	static_assert (std::is_trivially_copyable <T>::value, "");
1162	#endif
1163	T *p = address ();
1164	p[ix] = p[--m_vecpfx.m_num];
1165	}
1166
1167
1168	/ Remove LEN elements starting at the IXth. Ordering is retained.*
1169	This is an O(N) operation due to memmove. /*
1170
1171	template<typename T, typename A>
1172	inline void
1173	vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1174	{
1175	gcc_checking_assert (ix + len <= length ());
1176	#if GCC_VERSION >= 5000
1177	static_assert (std::is_trivially_copyable <T>::value, "");
1178	#endif
1179	T *slot = &address ()[ix];
1180	m_vecpfx.m_num -= len;
1181	memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1182	}
1183
1184
1185	#if GCC_VERSION >= 5000
1186	namespace vec_detail
1187	{
1188	/ gcc_{qsort,qsort_r,stablesort_r} implementation under the hood*
1189	uses memcpy/memmove to reorder the array elements.
1190	We want to assert these methods aren't used on types for which
1191	that isn't appropriate, but unfortunately std::pair of 2 trivially
1192	copyable types isn't trivially copyable and we use qsort on many
1193	such std::pair instantiations. Let's allow both trivially
1194	copyable types and std::pair of 2 trivially copyable types as
1195	exception for qsort/sort/stablesort. /*
1196	template<typename T>
1197	struct is_trivially_copyable_or_pair : std::is_trivially_copyable<T> { };
1198
1199	template<typename T, typename U>
1200	struct is_trivially_copyable_or_pair<std::pair<T, U> >
1201	: std::integral_constant<bool, std::is_trivially_copyable<T>::value
1202	&& std::is_trivially_copyable<U>::value> { };
1203	}
1204	#endif
1205
1206	/ Sort the contents of this vector with qsort. CMP is the comparison*
1207	function to pass to qsort. /*
1208
1209	template<typename T, typename A>
1210	inline void
1211	vec<T, A, vl_embed>::qsort (int (cmp) (const* void , const* void *))
1212	{
1213	#if GCC_VERSION >= 5000
1214	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1215	#endif
1216	if (length () > `1`)
1217	gcc_qsort (address (), length (), sizeof (T), cmp);
1218	}
1219
1220	/ Sort the contents of this vector with qsort. CMP is the comparison*
1221	function to pass to qsort. /*
1222
1223	template<typename T, typename A>
1224	inline void
1225	vec<T, A, vl_embed>::sort (int (cmp) (const* void , const* void , void* *),
1226	void *data)
1227	{
1228	#if GCC_VERSION >= 5000
1229	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1230	#endif
1231	if (length () > `1`)
1232	gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1233	}
1234
1235	/ Sort the contents of this vector with gcc_stablesort_r. CMP is the*
1236	comparison function to pass to qsort. /*
1237
1238	template<typename T, typename A>
1239	inline void
1240	vec<T, A, vl_embed>::stablesort (int (cmp) (const* void , const* void *,
1241	void ), void* *data)
1242	{
1243	#if GCC_VERSION >= 5000
1244	static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1245	#endif
1246	if (length () > `1`)
1247	gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1248	}
1249
1250	/ Search the contents of the sorted vector with a binary search.*
1251	CMP is the comparison function to pass to bsearch. /*
1252
1253	template<typename T, typename A>
1254	inline T *
1255	vec<T, A, vl_embed>::bsearch (const void *key,
1256	int (compar) (const* void , const* void *))
1257	{
1258	const void base = this*->address ();
1259	size_t nmemb = this->length ();
1260	size_t size = sizeof (T);
1261	/ The following is a copy of glibc stdlib-bsearch.h. /
1262	size_t l, u, idx;
1263	const void *p;
1264	int comparison;
1265
1266	l = `0`;
1267	u = nmemb;
1268	while (l < u)
1269	{
1270	idx = (l + u) / `2`;
1271	p = (const void ) (((const* char ) base) + (idx size));
1272	comparison = (*compar) (key, p);
1273	if (comparison < `0`)
1274	u = idx;
1275	else if (comparison > `0`)
1276	l = idx + `1`;
1277	else
1278	return (T )const_cast<void* *>(p);
1279	}
1280
1281	return NULL;
1282	}
1283
1284	/ Search the contents of the sorted vector with a binary search.*
1285	CMP is the comparison function to pass to bsearch. /*
1286
1287	template<typename T, typename A>
1288	inline T *
1289	vec<T, A, vl_embed>::bsearch (const void *key,
1290	int (compar) (const* void , const* void *,
1291	void ), void* *data)
1292	{
1293	const void base = this*->address ();
1294	size_t nmemb = this->length ();
1295	size_t size = sizeof (T);
1296	/ The following is a copy of glibc stdlib-bsearch.h. /
1297	size_t l, u, idx;
1298	const void *p;
1299	int comparison;
1300
1301	l = `0`;
1302	u = nmemb;
1303	while (l < u)
1304	{
1305	idx = (l + u) / `2`;
1306	p = (const void ) (((const* char ) base) + (idx size));
1307	comparison = (*compar) (key, p, data);
1308	if (comparison < `0`)
1309	u = idx;
1310	else if (comparison > `0`)
1311	l = idx + `1`;
1312	else
1313	return (T )const_cast<void* *>(p);
1314	}
1315
1316	return NULL;
1317	}
1318
1319	/ Return true if SEARCH is an element of V. Note that this is O(N) in the*
1320	size of the vector and so should be used with care. /*
1321
1322	template<typename T, typename A>
1323	inline bool
1324	vec<T, A, vl_embed>::contains (const T &search) const
1325	{
1326	unsigned int len = length ();
1327	const T *p = address ();
1328	for (unsigned int i = `0`; i < len; i++)
1329	{
1330	const T *slot = &p[i];
1331	if (*slot == search)
1332	return true;
1333	}
1334
1335	return false;
1336	}
1337
1338	/ Find and return the first position in which OBJ could be inserted*
1339	without changing the ordering of this vector. LESSTHAN is a
1340	function that returns true if the first argument is strictly less
1341	than the second. /*
1342
1343	template<typename T, typename A>
1344	unsigned
1345	vec<T, A, vl_embed>::lower_bound (const T &obj,
1346	bool (lessthan)(const* T &, const T &))
1347	const
1348	{
1349	unsigned int len = length ();
1350	unsigned int half, middle;
1351	unsigned int first = `0`;
1352	while (len > `0`)
1353	{
1354	half = len / `2`;
1355	middle = first;
1356	middle += half;
1357	const T &middle_elem = address ()[middle];
1358	if (lessthan (middle_elem, obj))
1359	{
1360	first = middle;
1361	++first;
1362	len = len - half - `1`;
1363	}
1364	else
1365	len = half;
1366	}
1367	return first;
1368	}
1369
1370
1371	/ Return the number of bytes needed to embed an instance of an*
1372	embeddable vec inside another data structure.
1373
1374	Use these methods to determine the required size and initialization
1375	of a vector V of type T embedded within another structure (as the
1376	final member):
1377
1378	size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1379	void v->embedded_init (unsigned alloc, unsigned num);
1380
1381	These allow the caller to perform the memory allocation. /*
1382
1383	template<typename T, typename A>
1384	inline size_t
1385	vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1386	{
1387	struct alignas (T) U { char data[sizeof (T)]; };
1388	typedef vec<U, A, vl_embed> vec_embedded;
1389	typedef typename std::conditional<std::is_standard_layout<T>::value,
1390	vec, vec_embedded>::type vec_stdlayout;
1391	static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1392	static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1393	return sizeof (vec_stdlayout) + alloc * sizeof (T);
1394	}
1395
1396
1397	/ Initialize the vector to contain room for ALLOC elements and*
1398	NUM active elements. /*
1399
1400	template<typename T, typename A>
1401	inline void
1402	vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1403	{
1404	m_vecpfx.m_alloc = alloc;
1405	m_vecpfx.m_using_auto_storage = aut;
1406	m_vecpfx.m_num = num;
1407	}
1408
1409
1410	/ Grow the vector to a specific length. LEN must be as long or longer than*
1411	the current length. The new elements are uninitialized. /*
1412
1413	template<typename T, typename A>
1414	inline void
1415	vec<T, A, vl_embed>::quick_grow (unsigned len)
1416	{
1417	gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1418	#if GCC_VERSION >= 5000
1419	static_assert (std::is_trivially_default_constructible <T>::value, "");
1420	#endif
1421	m_vecpfx.m_num = len;
1422	}
1423
1424
1425	/ Grow the vector to a specific length. LEN must be as long or longer than*
1426	the current length. The new elements are initialized to zero. /*
1427
1428	template<typename T, typename A>
1429	inline void
1430	vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1431	{
1432	unsigned oldlen = length ();
1433	size_t growby = len - oldlen;
1434	gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1435	m_vecpfx.m_num = len;
1436	if (growby != `0`)
1437	vec_default_construct (address () + oldlen, growby);
1438	}
1439
1440	/ Garbage collection support for vec<T, A, vl_embed>. /
1441
1442	template<typename T>
1443	void
1444	gt_ggc_mx (vec<T, va_gc> *v)
1445	{
1446	static_assert (std::is_trivially_destructible <T>::value, "");
1447	extern void gt_ggc_mx (T &);
1448	for (unsigned i = `0`; i < v->length (); i++)
1449	gt_ggc_mx ((*v)[i]);
1450	}
1451
1452	template<typename T>
1453	void
1454	gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1455	{
1456	static_assert (std::is_trivially_destructible <T>::value, "");
1457	/ Nothing to do. Vectors of atomic types wrt GC do not need to*
1458	be traversed. /*
1459	}
1460
1461
1462	/ PCH support for vec<T, A, vl_embed>. /
1463
1464	template<typename T, typename A>
1465	void
1466	gt_pch_nx (vec<T, A, vl_embed> *v)
1467	{
1468	extern void gt_pch_nx (T &);
1469	for (unsigned i = `0`; i < v->length (); i++)
1470	gt_pch_nx ((*v)[i]);
1471	}
1472
1473	template<typename T>
1474	void
1475	gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *)
1476	{
1477	/ No pointers to note. /
1478	}
1479
1480	template<typename T, typename A>
1481	void
1482	gt_pch_nx (vec<T , A, vl_embed> v, gt_pointer_operator op, void *cookie)
1483	{
1484	for (unsigned i = `0`; i < v->length (); i++)
1485	op (&((*v)[i]), NULL, cookie);
1486	}
1487
1488	template<typename T, typename A>
1489	void
1490	gt_pch_nx (vec<T, A, vl_embed> v, gt_pointer_operator op, void* *cookie)
1491	{
1492	extern void gt_pch_nx (T , gt_pointer_operator, void* *);
1493	for (unsigned i = `0`; i < v->length (); i++)
1494	gt_pch_nx (&((*v)[i]), op, cookie);
1495	}
1496
1497	template<typename T>
1498	void
1499	gt_pch_nx (vec<T, va_gc_atomic, vl_embed> , gt_pointer_operator, void* *)
1500	{
1501	/ No pointers to note. /
1502	}
1503
1504
1505	/ Space efficient vector. These vectors can grow dynamically and are*
1506	allocated together with their control data. They are suited to be
1507	included in data structures. Prior to initial allocation, they
1508	only take a single word of storage.
1509
1510	These vectors are implemented as a pointer to an embeddable vector.
1511	The semantics allow for this pointer to be NULL to represent empty
1512	vectors. This way, empty vectors occupy minimal space in the
1513	structure containing them.
1514
1515	Properties:
1516
1517	- The whole vector and control data are allocated in a single
1518	contiguous block.
1519	- The whole vector may be re-allocated.
1520	- Vector data may grow and shrink.
1521	- Access and manipulation requires a pointer test and
1522	indirection.
1523	- It requires 1 word of storage (prior to vector allocation).
1524
1525
1526	Limitations:
1527
1528	These vectors must be PODs because they are stored in unions.
1529	(http://en.wikipedia.org/wiki/Plain_old_data_structures).
1530	As long as we use C++03, we cannot have constructors nor
1531	destructors in classes that are stored in unions. /*
1532
1533	template<typename T, size_t N = `0`>
1534	class auto_vec;
1535
1536	template<typename T>
1537	struct vec<T, va_heap, vl_ptr>
1538	{
1539	public:
1540	/ Default ctors to ensure triviality. Use value-initialization*
1541	(e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1542	instance. /*
1543	vec () = default;
1544	vec (const vec &) = default;
1545	/ Initialization from the generic vNULL. /
1546	vec (vnull): m_vec () { }
1547	/ Same as default ctor: vec storage must be released manually. /
1548	~vec () = default;
1549
1550	/ Defaulted same as copy ctor. /
1551	vec& operator= (const vec &) = default;
1552
1553	/ Prevent implicit conversion from auto_vec. Use auto_vec::to_vec()*
1554	instead. /*
1555	template <size_t N>
1556	vec (auto_vec<T, N> &) = delete;
1557
1558	template <size_t N>
1559	void operator= (auto_vec<T, N> &) = delete;
1560
1561	/ Memory allocation and deallocation for the embedded vector.*
1562	Needed because we cannot have proper ctors/dtors defined. /*
1563	void create (unsigned nelems CXX_MEM_STAT_INFO);
1564	void release (void);
1565
1566	/ Vector operations. /
1567	bool exists (void) const
1568	{ return m_vec != NULL; }
1569
1570	bool is_empty (void) const
1571	{ return m_vec ? m_vec->is_empty () : true; }
1572
1573	unsigned allocated (void) const
1574	{ return m_vec ? m_vec->allocated () : `0`; }
1575
1576	unsigned length (void) const
1577	{ return m_vec ? m_vec->length () : `0`; }
1578
1579	T address (void*)
1580	{ return m_vec ? m_vec->address () : NULL; }
1581
1582	const T address (void) const*
1583	{ return m_vec ? m_vec->address () : NULL; }
1584
1585	T begin () { return* address (); }
1586	const T begin () const* { return address (); }
1587	T end () { return* begin () + length (); }
1588	const T end () const* { return begin () + length (); }
1589	const T &operator[] (unsigned ix) const
1590	{ return (*m_vec)[ix]; }
1591
1592	bool operator!=(const vec &other) const
1593	{ return !(*this == other); }
1594
1595	bool operator==(const vec &other) const
1596	{ return address () == other.address (); }
1597
1598	T &operator[] (unsigned ix)
1599	{ return (*m_vec)[ix]; }
1600
1601	T &last (void)
1602	{ return m_vec->last (); }
1603
1604	bool space (int nelems) const
1605	{ return m_vec ? m_vec->space (nelems) : nelems == `0`; }
1606
1607	bool iterate (unsigned ix, T p) const*;
1608	bool iterate (unsigned ix, T *p) const*;
1609	vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1610	bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1611	bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1612	void splice (const vec &);
1613	void safe_splice (const vec & CXX_MEM_STAT_INFO);
1614	T quick_push (const* T &);
1615	T safe_push (const* T &CXX_MEM_STAT_INFO);
1616	using pop_ret_type
1617	= typename std::conditional <std::is_trivially_destructible <T>::value,
1618	T &, void>::type;
1619	pop_ret_type pop (void);
1620	void truncate (unsigned);
1621	void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
1622	void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
1623	void quick_grow (unsigned);
1624	void quick_grow_cleared (unsigned);
1625	void quick_insert (unsigned, const T &);
1626	void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1627	void ordered_remove (unsigned);
1628	void unordered_remove (unsigned);
1629	void block_remove (unsigned, unsigned);
1630	void qsort (int () (const* void , const* void *));
1631	void sort (int () (const* void , const* void , void* ), void* *);
1632	void stablesort (int () (const* void , const* void , void* ), void* *);
1633	T bsearch (const* void key, int* (compar)(const* void , const* void *));
1634	T bsearch (const* void *key,
1635	int (compar)(const* void , const* void , void* ), void* *);
1636	unsigned lower_bound (T, bool ()(const* T &, const T &)) const;
1637	bool contains (const T &search) const;
1638	void reverse (void);
1639
1640	bool using_auto_storage () const;
1641
1642	/ FIXME - This field should be private, but we need to cater to*
1643	compilers that have stricter notions of PODness for types. /*
1644	vec<T, va_heap, vl_embed> *m_vec;
1645	};
1646
1647
1648	/ auto_vec is a subclass of vec that automatically manages creating and*
1649	releasing the internal vector. If N is non zero then it has N elements of
1650	internal storage. The default is no internal storage, and you probably only
1651	want to ask for internal storage for vectors on the stack because if the
1652	size of the vector is larger than the internal storage that space is wasted.
1653	*/
1654	template<typename T, size_t N / = 0 />
1655	class auto_vec : public vec<T, va_heap>
1656	{
1657	public:
1658	auto_vec ()
1659	{
1660	m_auto.embedded_init (N, `0`, `1`);
1661	/ ??? Instead of initializing m_vec from &m_auto directly use an*
1662	expression that avoids refering to a specific member of 'this'
1663	to derail the -Wstringop-overflow diagnostic code, avoiding
1664	the impression that data accesses are supposed to be to the
1665	m_auto member storage. /*
1666	size_t off = (char ) &m_auto - (char* ) this*;
1667	this->m_vec = (vec<T, va_heap, vl_embed> ) ((char* ) this* + off);
1668	}
1669
1670	auto_vec (size_t s CXX_MEM_STAT_INFO)
1671	{
1672	if (s > N)
1673	{
1674	this->create (s PASS_MEM_STAT);
1675	return;
1676	}
1677
1678	m_auto.embedded_init (N, `0`, `1`);
1679	/ ??? See above. /
1680	size_t off = (char ) &m_auto - (char* ) this*;
1681	this->m_vec = (vec<T, va_heap, vl_embed> ) ((char* ) this* + off);
1682	}
1683
1684	~auto_vec ()
1685	{
1686	this->release ();
1687	}
1688
1689	/ Explicitly convert to the base class. There is no conversion*
1690	from a const auto_vec because a copy of the returned vec can
1691	be used to modify THIS.*
1692	This is a legacy function not to be used in new code. /*
1693	vec<T, va_heap> to_vec_legacy () {
1694	return *static_cast<vec<T, va_heap> >(this*);
1695	}
1696
1697	private:
1698	vec<T, va_heap, vl_embed> m_auto;
1699	unsigned char m_data[sizeof (T) * N];
1700	};
1701
1702	/ auto_vec is a sub class of vec whose storage is released when it is*
1703	destroyed. /*
1704	template<typename T>
1705	class auto_vec<T, `0`> : public vec<T, va_heap>
1706	{
1707	public:
1708	auto_vec () { this->m_vec = NULL; }
1709	auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); }
1710	~auto_vec () { this->release (); }
1711
1712	auto_vec (vec<T, va_heap>&& r)
1713	{
1714	gcc_assert (!r.using_auto_storage ());
1715	this->m_vec = r.m_vec;
1716	r.m_vec = NULL;
1717	}
1718
1719	auto_vec (auto_vec<T> &&r)
1720	{
1721	gcc_assert (!r.using_auto_storage ());
1722	this->m_vec = r.m_vec;
1723	r.m_vec = NULL;
1724	}
1725
1726	auto_vec& operator= (vec<T, va_heap>&& r)
1727	{
1728	if (this == &r)
1729	return *this;
1730
1731	gcc_assert (!r.using_auto_storage ());
1732	this->release ();
1733	this->m_vec = r.m_vec;
1734	r.m_vec = NULL;
1735	return *this;
1736	}
1737
1738	auto_vec& operator= (auto_vec<T> &&r)
1739	{
1740	if (this == &r)
1741	return *this;
1742
1743	gcc_assert (!r.using_auto_storage ());
1744	this->release ();
1745	this->m_vec = r.m_vec;
1746	r.m_vec = NULL;
1747	return *this;
1748	}
1749
1750	/ Explicitly convert to the base class. There is no conversion*
1751	from a const auto_vec because a copy of the returned vec can
1752	be used to modify THIS.*
1753	This is a legacy function not to be used in new code. /*
1754	vec<T, va_heap> to_vec_legacy () {
1755	return *static_cast<vec<T, va_heap> >(this*);
1756	}
1757
1758	// You probably don't want to copy a vector, so these are deleted to prevent
1759	// unintentional use. If you really need a copy of the vectors contents you
1760	// can use copy ().
1761	auto_vec (const auto_vec &) = delete;
1762	auto_vec &operator= (const auto_vec &) = delete;
1763	};
1764
1765
1766	/ Allocate heap memory for pointer V and create the internal vector*
1767	with space for NELEMS elements. If NELEMS is 0, the internal
1768	vector is initialized to empty. /*
1769
1770	template<typename T>
1771	inline void
1772	vec_alloc (vec<T> &v, unsigned* nelems CXX_MEM_STAT_INFO)
1773	{
1774	v = new vec<T>;
1775	v->create (nelems PASS_MEM_STAT);
1776	}
1777
1778
1779	/ A subclass of auto_vec <char > that frees all of its elements on
1780	deletion. /*
1781
1782	class auto_string_vec : public auto_vec <char *>
1783	{
1784	public:
1785	~auto_string_vec ();
1786	};
1787
1788	/ A subclass of auto_vec <T > that deletes all of its elements on
1789	destruction.
1790
1791	This is a crude way for a vec to "own" the objects it points to
1792	and clean up automatically.
1793
1794	For example, no attempt is made to delete elements when an item
1795	within the vec is overwritten.
1796
1797	We can't rely on gnu::unique_ptr within a container,
1798	since we can't rely on move semantics in C++98. /*
1799
1800	template <typename T>
1801	class auto_delete_vec : public auto_vec <T *>
1802	{
1803	public:
1804	auto_delete_vec () {}
1805	auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1806
1807	~auto_delete_vec ();
1808
1809	private:
1810	DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1811	};
1812
1813	/ Conditionally allocate heap memory for VEC and its internal vector. /
1814
1815	template<typename T>
1816	inline void
1817	vec_check_alloc (vec<T, va_heap> &vec, unsigned* nelems CXX_MEM_STAT_INFO)
1818	{
1819	if (!vec)
1820	vec_alloc (vec, nelems PASS_MEM_STAT);
1821	}
1822
1823
1824	/ Free the heap memory allocated by vector V and set it to NULL. /
1825
1826	template<typename T>
1827	inline void
1828	vec_free (vec<T> *&v)
1829	{
1830	if (v == NULL)
1831	return;
1832
1833	v->release ();
1834	delete v;
1835	v = NULL;
1836	}
1837
1838
1839	/ Return iteration condition and update PTR to point to the IX'th*
1840	element of this vector. Use this to iterate over the elements of a
1841	vector as follows,
1842
1843	for (ix = 0; v.iterate (ix, &ptr); ix++)
1844	continue; /*
1845
1846	template<typename T>
1847	inline bool
1848	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T ptr) const*
1849	{
1850	if (m_vec)
1851	return m_vec->iterate (ix, ptr);
1852	else
1853	{
1854	*ptr = `0`;
1855	return false;
1856	}
1857	}
1858
1859
1860	/ Return iteration condition and update PTR to point to the
1861	IX'th element of this vector. Use this to iterate over the
1862	elements of a vector as follows,
1863
1864	for (ix = 0; v->iterate (ix, &ptr); ix++)
1865	continue;
1866
1867	This variant is for vectors of objects. /*
1868
1869	template<typename T>
1870	inline bool
1871	vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const*
1872	{
1873	if (m_vec)
1874	return m_vec->iterate (ix, ptr);
1875	else
1876	{
1877	*ptr = `0`;
1878	return false;
1879	}
1880	}
1881
1882
1883	/ Convenience macro for forward iteration. /
1884	#define FOR_EACH_VEC_ELT(V, I, P) \
1885	for (I = 0; (V).iterate ((I), &(P)); ++(I))
1886
1887	#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1888	for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1889
1890	/ Likewise, but start from FROM rather than 0. /
1891	#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1892	for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1893
1894	/ Convenience macro for reverse iteration. /
1895	#define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1896	for (I = (V).length () - 1; \
1897	(V).iterate ((I), &(P)); \
1898	(I)--)
1899
1900	#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1901	for (I = vec_safe_length (V) - 1; \
1902	vec_safe_iterate ((V), (I), &(P)); \
1903	(I)--)
1904
1905	/ auto_string_vec's dtor, freeing all contained strings, automatically*
1906	chaining up to ~auto_vec <char >, which frees the internal buffer. /
1907
1908	inline
1909	auto_string_vec::~auto_string_vec ()
1910	{
1911	int i;
1912	char *str;
1913	FOR_EACH_VEC_ELT (*this, i, str)
1914	free (ptr: str);
1915	}
1916
1917	/ auto_delete_vec's dtor, deleting all contained items, automatically*
1918	chaining up to ~auto_vec <T>, which frees the internal buffer. /
1919
1920	template <typename T>
1921	inline
1922	auto_delete_vec<T>::~auto_delete_vec ()
1923	{
1924	int i;
1925	T *item;
1926	FOR_EACH_VEC_ELT (*this, i, item)
1927	delete item;
1928	}
1929
1930
1931	/ Return a copy of this vector. /
1932
1933	template<typename T>
1934	inline vec<T, va_heap, vl_ptr>
1935	vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1936	{
1937	vec<T, va_heap, vl_ptr> new_vec{ };
1938	if (length ())
1939	new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1940	return new_vec;
1941	}
1942
1943
1944	/ Ensure that the vector has at least RESERVE slots available (if*
1945	EXACT is false), or exactly RESERVE slots available (if EXACT is
1946	true).
1947
1948	This may create additional headroom if EXACT is false.
1949
1950	Note that this can cause the embedded vector to be reallocated.
1951	Returns true iff reallocation actually occurred. /*
1952
1953	template<typename T>
1954	inline bool
1955	vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1956	{
1957	if (space (nelems))
1958	return false;
1959
1960	/ For now play a game with va_heap::reserve to hide our auto storage if any,*
1961	this is necessary because it doesn't have enough information to know the
1962	embedded vector is in auto storage, and so should not be freed. /*
1963	vec<T, va_heap, vl_embed> *oldvec = m_vec;
1964	unsigned int oldsize = `0`;
1965	bool handle_auto_vec = m_vec && using_auto_storage ();
1966	if (handle_auto_vec)
1967	{
1968	m_vec = NULL;
1969	oldsize = oldvec->length ();
1970	nelems += oldsize;
1971	}
1972
1973	va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1974	if (handle_auto_vec)
1975	{
1976	vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1977	m_vec->m_vecpfx.m_num = oldsize;
1978	}
1979
1980	return true;
1981	}
1982
1983
1984	/ Ensure that this vector has exactly NELEMS slots available. This*
1985	will not create additional headroom. Note this can cause the
1986	embedded vector to be reallocated. Returns true iff reallocation
1987	actually occurred. /*
1988
1989	template<typename T>
1990	inline bool
1991	vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1992	{
1993	return reserve (nelems, exact: true PASS_MEM_STAT);
1994	}
1995
1996
1997	/ Create the internal vector and reserve NELEMS for it. This is*
1998	exactly like vec::reserve, but the internal vector is
1999	unconditionally allocated from scratch. The old one, if it
2000	existed, is lost. /*
2001
2002	template<typename T>
2003	inline void
2004	vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
2005	{
2006	m_vec = NULL;
2007	if (nelems > `0`)
2008	reserve_exact (nelems PASS_MEM_STAT);
2009	}
2010
2011
2012	/ Free the memory occupied by the embedded vector. /
2013
2014	template<typename T>
2015	inline void
2016	vec<T, va_heap, vl_ptr>::release (void)
2017	{
2018	if (!m_vec)
2019	return;
2020
2021	if (using_auto_storage ())
2022	{
2023	m_vec->m_vecpfx.m_num = `0`;
2024	return;
2025	}
2026
2027	va_heap::release (m_vec);
2028	}
2029
2030	/ Copy the elements from SRC to the end of this vector as if by memcpy.*
2031	SRC and this vector must be allocated with the same memory
2032	allocation mechanism. This vector is assumed to have sufficient
2033	headroom available. /*
2034
2035	template<typename T>
2036	inline void
2037	vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
2038	{
2039	if (src.length ())
2040	m_vec->splice (*(src.m_vec));
2041	}
2042
2043
2044	/ Copy the elements in SRC to the end of this vector as if by memcpy.*
2045	SRC and this vector must be allocated with the same mechanism.
2046	If there is not enough headroom in this vector, it will be reallocated
2047	as needed. /*
2048
2049	template<typename T>
2050	inline void
2051	vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
2052	MEM_STAT_DECL)
2053	{
2054	if (src.length ())
2055	{
2056	reserve_exact (nelems: src.length ());
2057	splice (src);
2058	}
2059	}
2060
2061
2062	/ Push OBJ (a new element) onto the end of the vector. There must be*
2063	sufficient space in the vector. Return a pointer to the slot
2064	where OBJ was inserted. /*
2065
2066	template<typename T>
2067	inline T *
2068	vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
2069	{
2070	return m_vec->quick_push (obj);
2071	}
2072
2073
2074	/ Push a new element OBJ onto the end of this vector. Reallocates*
2075	the embedded vector, if needed. Return a pointer to the slot where
2076	OBJ was inserted. /*
2077
2078	template<typename T>
2079	inline T *
2080	vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
2081	{
2082	reserve (nelems: `1`, exact: false PASS_MEM_STAT);
2083	return quick_push (obj);
2084	}
2085
2086
2087	/ Pop and return a reference to the last element off the end of the*
2088	vector. If T has non-trivial destructor, this method just pops
2089	last element and returns void. /*
2090
2091	template<typename T>
2092	inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
2093	vec<T, va_heap, vl_ptr>::pop (void)
2094	{
2095	return m_vec->pop ();
2096	}
2097
2098
2099	/ Set the length of the vector to LEN. The new length must be less*
2100	than or equal to the current length. This is an O(1) operation. /*
2101
2102	template<typename T>
2103	inline void
2104	vec<T, va_heap, vl_ptr>::truncate (unsigned size)
2105	{
2106	if (m_vec)
2107	m_vec->truncate (size);
2108	else
2109	gcc_checking_assert (size == `0`);
2110	}
2111
2112
2113	/ Grow the vector to a specific length. LEN must be as long or*
2114	longer than the current length. The new elements are
2115	uninitialized. Reallocate the internal vector, if needed. /*
2116
2117	template<typename T>
2118	inline void
2119	vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2120	{
2121	unsigned oldlen = length ();
2122	gcc_checking_assert (oldlen <= len);
2123	reserve (nelems: len - oldlen, exact PASS_MEM_STAT);
2124	if (m_vec)
2125	m_vec->quick_grow (len);
2126	else
2127	gcc_checking_assert (len == `0`);
2128	}
2129
2130
2131	/ Grow the embedded vector to a specific length. LEN must be as*
2132	long or longer than the current length. The new elements are
2133	initialized to zero. Reallocate the internal vector, if needed. /*
2134
2135	template<typename T>
2136	inline void
2137	vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2138	MEM_STAT_DECL)
2139	{
2140	unsigned oldlen = length ();
2141	gcc_checking_assert (oldlen <= len);
2142	reserve (nelems: len - oldlen, exact PASS_MEM_STAT);
2143	if (m_vec)
2144	m_vec->quick_grow_cleared (len);
2145	else
2146	gcc_checking_assert (len == `0`);
2147	}
2148
2149
2150	/ Same as vec::safe_grow but without reallocation of the internal vector.*
2151	If the vector cannot be extended, a runtime assertion will be triggered. /*
2152
2153	template<typename T>
2154	inline void
2155	vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2156	{
2157	gcc_checking_assert (m_vec);
2158	m_vec->quick_grow (len);
2159	}
2160
2161
2162	/ Same as vec::quick_grow_cleared but without reallocation of the*
2163	internal vector. If the vector cannot be extended, a runtime
2164	assertion will be triggered. /*
2165
2166	template<typename T>
2167	inline void
2168	vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2169	{
2170	gcc_checking_assert (m_vec);
2171	m_vec->quick_grow_cleared (len);
2172	}
2173
2174
2175	/ Insert an element, OBJ, at the IXth position of this vector. There*
2176	must be sufficient space. /*
2177
2178	template<typename T>
2179	inline void
2180	vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2181	{
2182	m_vec->quick_insert (ix, obj);
2183	}
2184
2185
2186	/ Insert an element, OBJ, at the IXth position of the vector.*
2187	Reallocate the embedded vector, if necessary. /*
2188
2189	template<typename T>
2190	inline void
2191	vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2192	{
2193	reserve (nelems: `1`, exact: false PASS_MEM_STAT);
2194	quick_insert (ix, obj);
2195	}
2196
2197
2198	/ Remove an element from the IXth position of this vector. Ordering of*
2199	remaining elements is preserved. This is an O(N) operation due to
2200	a memmove. /*
2201
2202	template<typename T>
2203	inline void
2204	vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2205	{
2206	m_vec->ordered_remove (ix);
2207	}
2208
2209
2210	/ Remove an element from the IXth position of this vector. Ordering*
2211	of remaining elements is destroyed. This is an O(1) operation. /*
2212
2213	template<typename T>
2214	inline void
2215	vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2216	{
2217	m_vec->unordered_remove (ix);
2218	}
2219
2220
2221	/ Remove LEN elements starting at the IXth. Ordering is retained.*
2222	This is an O(N) operation due to memmove. /*
2223
2224	template<typename T>
2225	inline void
2226	vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2227	{
2228	m_vec->block_remove (ix, len);
2229	}
2230
2231
2232	/ Sort the contents of this vector with qsort. CMP is the comparison*
2233	function to pass to qsort. /*
2234
2235	template<typename T>
2236	inline void
2237	vec<T, va_heap, vl_ptr>::qsort (int (cmp) (const* void , const* void *))
2238	{
2239	if (m_vec)
2240	m_vec->qsort (cmp);
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>::sort (int (cmp) (const* void , const* void *,
2249	void ), void* *data)
2250	{
2251	if (m_vec)
2252	m_vec->sort (cmp, data);
2253	}
2254
2255	/ Sort the contents of this vector with gcc_stablesort_r. CMP is the*
2256	comparison function to pass to qsort. /*
2257
2258	template<typename T>
2259	inline void
2260	vec<T, va_heap, vl_ptr>::stablesort (int (cmp) (const* void , const* void *,
2261	void ), void* *data)
2262	{
2263	if (m_vec)
2264	m_vec->stablesort (cmp, data);
2265	}
2266
2267	/ Search the contents of the sorted vector with a binary search.*
2268	CMP is the comparison function to pass to bsearch. /*
2269
2270	template<typename T>
2271	inline T *
2272	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2273	int (cmp) (const* void , const* void *))
2274	{
2275	if (m_vec)
2276	return m_vec->bsearch (key, cmp);
2277	return NULL;
2278	}
2279
2280	/ Search the contents of the sorted vector with a binary search.*
2281	CMP is the comparison function to pass to bsearch. /*
2282
2283	template<typename T>
2284	inline T *
2285	vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2286	int (cmp) (const* void , const* void *,
2287	void ), void* *data)
2288	{
2289	if (m_vec)
2290	return m_vec->bsearch (key, cmp, data);
2291	return NULL;
2292	}
2293
2294
2295	/ Find and return the first position in which OBJ could be inserted*
2296	without changing the ordering of this vector. LESSTHAN is a
2297	function that returns true if the first argument is strictly less
2298	than the second. /*
2299
2300	template<typename T>
2301	inline unsigned
2302	vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2303	bool (lessthan)(const* T &, const T &))
2304	const
2305	{
2306	return m_vec ? m_vec->lower_bound (obj, lessthan) : `0`;
2307	}
2308
2309	/ Return true if SEARCH is an element of V. Note that this is O(N) in the*
2310	size of the vector and so should be used with care. /*
2311
2312	template<typename T>
2313	inline bool
2314	vec<T, va_heap, vl_ptr>::contains (const T &search) const
2315	{
2316	return m_vec ? m_vec->contains (search) : false;
2317	}
2318
2319	/ Reverse content of the vector. /
2320
2321	template<typename T>
2322	inline void
2323	vec<T, va_heap, vl_ptr>::reverse (void)
2324	{
2325	unsigned l = length ();
2326	T *ptr = address ();
2327
2328	for (unsigned i = `0`; i < l / `2`; i++)
2329	std::swap (ptr[i], ptr[l - i - `1`]);
2330	}
2331
2332	template<typename T>
2333	inline bool
2334	vec<T, va_heap, vl_ptr>::using_auto_storage () const
2335	{
2336	return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2337	}
2338
2339	/ Release VEC and call release of all element vectors. /
2340
2341	template<typename T>
2342	inline void
2343	release_vec_vec (vec<vec<T> > &vec)
2344	{
2345	for (unsigned i = `0`; i < vec.length (); i++)
2346	vec[i].release ();
2347
2348	vec.release ();
2349	}
2350
2351	// Provide a subset of the std::span functionality. (We can't use std::span
2352	// itself because it's a C++20 feature.)
2353	//
2354	// In addition, provide an invalid value that is distinct from all valid
2355	// sequences (including the empty sequence). This can be used to return
2356	// failure without having to use std::optional.
2357	//
2358	// There is no operator bool because it would be ambiguous whether it is
2359	// testing for a valid value or an empty sequence.
2360	template<typename T>
2361	class array_slice
2362	{
2363	template<typename OtherT> friend class array_slice;
2364
2365	public:
2366	using value_type = T;
2367	using iterator = T *;
2368	using const_iterator = const T *;
2369
2370	array_slice () : m_base (nullptr), m_size (`0`) {}
2371
2372	template<typename OtherT>
2373	array_slice (array_slice<OtherT> other)
2374	: m_base (other.m_base), m_size (other.m_size) {}
2375
2376	array_slice (iterator base, unsigned int size)
2377	: m_base (base), m_size (size) {}
2378
2379	template<size_t N>
2380	array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2381
2382	template<typename OtherT>
2383	array_slice (const vec<OtherT> &v)
2384	: m_base (v.address ()), m_size (v.length ()) {}
2385
2386	template<typename OtherT>
2387	array_slice (vec<OtherT> &v)
2388	: m_base (v.address ()), m_size (v.length ()) {}
2389
2390	template<typename OtherT, typename A>
2391	array_slice (const vec<OtherT, A, vl_embed> *v)
2392	: m_base (v ? v->address () : nullptr), m_size (v ? v->length () : `0`) {}
2393
2394	template<typename OtherT, typename A>
2395	array_slice (vec<OtherT, A, vl_embed> *v)
2396	: m_base (v ? v->address () : nullptr), m_size (v ? v->length () : `0`) {}
2397
2398	iterator begin () { return m_base; }
2399	iterator end () { return m_base + m_size; }
2400
2401	const_iterator begin () const { return m_base; }
2402	const_iterator end () const { return m_base + m_size; }
2403
2404	value_type &front ();
2405	value_type &back ();
2406	value_type &operator[] (unsigned int i);
2407
2408	const value_type &front () const;
2409	const value_type &back () const;
2410	const value_type &operator[] (unsigned int i) const;
2411
2412	size_t size () const { return m_size; }
2413	size_t size_bytes () const { return m_size * sizeof (T); }
2414	bool empty () const { return m_size == `0`; }
2415
2416	// An invalid array_slice that represents a failed operation. This is
2417	// distinct from an empty slice, which is a valid result in some contexts.
2418	static array_slice invalid () { return { nullptr, ~`0U` }; }
2419
2420	// True if the array is valid, false if it is an array like INVALID.
2421	bool is_valid () const { return m_base \|\| m_size == `0`; }
2422
2423	private:
2424	iterator m_base;
2425	unsigned int m_size;
2426	};
2427
2428	template<typename T>
2429	inline typename array_slice<T>::value_type &
2430	array_slice<T>::front ()
2431	{
2432	gcc_checking_assert (m_size);
2433	return m_base[`0`];
2434	}
2435
2436	template<typename T>
2437	inline const typename array_slice<T>::value_type &
2438	array_slice<T>::front () const
2439	{
2440	gcc_checking_assert (m_size);
2441	return m_base[`0`];
2442	}
2443
2444	template<typename T>
2445	inline typename array_slice<T>::value_type &
2446	array_slice<T>::back ()
2447	{
2448	gcc_checking_assert (m_size);
2449	return m_base[m_size - `1`];
2450	}
2451
2452	template<typename T>
2453	inline const typename array_slice<T>::value_type &
2454	array_slice<T>::back () const
2455	{
2456	gcc_checking_assert (m_size);
2457	return m_base[m_size - `1`];
2458	}
2459
2460	template<typename T>
2461	inline typename array_slice<T>::value_type &
2462	array_slice<T>::operator[] (unsigned int i)
2463	{
2464	gcc_checking_assert (i < m_size);
2465	return m_base[i];
2466	}
2467
2468	template<typename T>
2469	inline const typename array_slice<T>::value_type &
2470	array_slice<T>::operator[] (unsigned int i) const
2471	{
2472	gcc_checking_assert (i < m_size);
2473	return m_base[i];
2474	}
2475
2476	template<typename T>
2477	array_slice<T>
2478	make_array_slice (T base, unsigned* int size)
2479	{
2480	return array_slice<T> (base, size);
2481	}
2482
2483	#if (GCC_VERSION >= 3000)
2484	# pragma GCC poison m_vec m_vecpfx m_vecdata
2485	#endif
2486
2487	#endif // GCC_VEC_H
2488

source code of gcc/vec.h