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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
30extern void ggc_free (void *);
31extern size_t ggc_round_alloc_size (size_t requested_size);
32extern 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. */
201extern void dump_vec_loc_statistics (void);
202
203/* Hashtable mapping vec addresses to descriptors. */
204extern htab_t vec_mem_usage_hash;
205
206/* Destruct N elements in DST. */
207
208template <typename T>
209inline void
210vec_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
219struct 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
252inline unsigned
253vec_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
263template<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. */
270struct vl_embed { };
271struct 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. */
282struct 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
302template<typename T>
303inline void
304va_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
333template<typename T>
334void
335va_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
358struct 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
377template<typename T, typename A>
378inline void
379va_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
392template<typename T, typename A>
393void
394va_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. */
430struct 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). */
446template<typename T,
447 typename A = va_heap,
448 typename L = typename A::default_layout>
449struct GTY((user)) vec
450{
451};
452
453/* Allow C++11 range-based 'for' to work directly on vec<T>*. */
454template<typename T, typename A, typename L>
455T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
456template<typename T, typename A, typename L>
457T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
458template<typename T, typename A, typename L>
459const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
460template<typename T, typename A, typename L>
461const 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
474template<typename T>
475void
476debug_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
492template<typename T>
493void
494debug_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
542template <typename T>
543inline void
544vec_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
552template <typename T>
553inline void
554vec_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. */
568struct vnull { };
569constexpr 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
598template<typename T, typename A>
599struct GTY((user)) vec<T, A, vl_embed>
600{
601public:
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. */
674template<typename T, typename A>
675inline bool
676vec_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(). */
683template<typename T, typename A>
684inline unsigned
685vec_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(). */
692template<typename T, typename A>
693inline T *
694vec_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(). */
701template<typename T, typename A>
702inline bool
703vec_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). */
710template<typename T, typename A>
711inline bool
712vec_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
721template<typename T, typename A>
722inline bool
723vec_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
733template<typename T, typename A>
734inline void
735vec_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
744template<typename T, typename A>
745inline void
746vec_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. */
753template<typename T, typename A>
754inline void
755vec_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). */
766template<typename T, typename A>
767inline void
768vec_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
780template<typename T>
781inline void
782vec_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
791template<typename T>
792inline bool
793vec_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). */
801template<typename T, typename A>
802inline bool
803vec_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
814template<typename T, typename A>
815inline bool
816vec_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). */
830template<typename T, typename A>
831inline T *
832vec_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). */
841template<typename T, typename A>
842inline void
843vec_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). */
852template<typename T, typename A>
853inline void
854vec_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. */
862template<typename T, typename A>
863inline vec<T, A, vl_embed> *
864vec_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. */
871template<typename T, typename A>
872inline void
873vec_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
888template<typename T, typename A>
889inline bool
890vec_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
898template<typename T, typename A>
899inline const T &
900vec<T, A, vl_embed>::operator[] (unsigned ix) const
901{
902 gcc_checking_assert (ix < m_vecpfx.m_num);
903 return address ()[ix];
904}
905
906template<typename T, typename A>
907inline T &
908vec<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
917template<typename T, typename A>
918inline T &
919vec<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
932template<typename T, typename A>
933inline bool
934vec<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
947template<typename T, typename A>
948inline bool
949vec<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
973template<typename T, typename A>
974inline bool
975vec<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
992template<typename T, typename A>
993inline vec<T, A, vl_embed> *
994vec<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
1011template<typename T, typename A>
1012inline void
1013vec<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
1024template<typename T, typename A>
1025inline void
1026vec<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
1037template<typename T, typename A>
1038inline T *
1039vec<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
1052template<typename T, typename A>
1053inline typename vec<T, A, vl_embed>::pop_ret_type
1054vec<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
1067template<typename T, typename A>
1068inline void
1069vec<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
1083template<typename T, typename A>
1084inline void
1085vec<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
1105template<typename T, typename A>
1106inline void
1107vec<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
1155template<typename T, typename A>
1156inline void
1157vec<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
1171template<typename T, typename A>
1172inline void
1173vec<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
1186namespace 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
1209template<typename T, typename A>
1210inline void
1211vec<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
1223template<typename T, typename A>
1224inline void
1225vec<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
1238template<typename T, typename A>
1239inline void
1240vec<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
1253template<typename T, typename A>
1254inline T *
1255vec<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
1287template<typename T, typename A>
1288inline T *
1289vec<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
1322template<typename T, typename A>
1323inline bool
1324vec<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
1343template<typename T, typename A>
1344unsigned
1345vec<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
1383template<typename T, typename A>
1384inline size_t
1385vec<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
1400template<typename T, typename A>
1401inline void
1402vec<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
1413template<typename T, typename A>
1414inline void
1415vec<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
1428template<typename T, typename A>
1429inline void
1430vec<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
1442template<typename T>
1443void
1444gt_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
1452template<typename T>
1453void
1454gt_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
1464template<typename T, typename A>
1465void
1466gt_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
1473template<typename T>
1474void
1475gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *)
1476{
1477 /* No pointers to note. */
1478}
1479
1480template<typename T, typename A>
1481void
1482gt_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
1488template<typename T, typename A>
1489void
1490gt_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
1497template<typename T>
1498void
1499gt_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
1533template<typename T, size_t N = 0>
1534class auto_vec;
1535
1536template<typename T>
1537struct vec<T, va_heap, vl_ptr>
1538{
1539public:
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 */
1654template<typename T, size_t N /* = 0 */>
1655class auto_vec : public vec<T, va_heap>
1656{
1657public:
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
1697private:
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. */
1704template<typename T>
1705class auto_vec<T, 0> : public vec<T, va_heap>
1706{
1707public:
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
1770template<typename T>
1771inline void
1772vec_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
1782class 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
1800template <typename T>
1801class 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
1809private:
1810 DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1811};
1812
1813/* Conditionally allocate heap memory for VEC and its internal vector. */
1814
1815template<typename T>
1816inline void
1817vec_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
1826template<typename T>
1827inline void
1828vec_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
1846template<typename T>
1847inline bool
1848vec<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
1869template<typename T>
1870inline bool
1871vec<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
1908inline
1909auto_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
1920template <typename T>
1921inline
1922auto_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
1933template<typename T>
1934inline vec<T, va_heap, vl_ptr>
1935vec<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
1953template<typename T>
1954inline bool
1955vec<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
1989template<typename T>
1990inline bool
1991vec<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
2002template<typename T>
2003inline void
2004vec<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
2014template<typename T>
2015inline void
2016vec<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
2035template<typename T>
2036inline void
2037vec<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
2049template<typename T>
2050inline void
2051vec<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
2066template<typename T>
2067inline T *
2068vec<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
2078template<typename T>
2079inline T *
2080vec<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
2091template<typename T>
2092inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
2093vec<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
2102template<typename T>
2103inline void
2104vec<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
2117template<typename T>
2118inline void
2119vec<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
2135template<typename T>
2136inline void
2137vec<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
2153template<typename T>
2154inline void
2155vec<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
2166template<typename T>
2167inline void
2168vec<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
2178template<typename T>
2179inline void
2180vec<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
2189template<typename T>
2190inline void
2191vec<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
2202template<typename T>
2203inline void
2204vec<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
2213template<typename T>
2214inline void
2215vec<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
2224template<typename T>
2225inline void
2226vec<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
2235template<typename T>
2236inline void
2237vec<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
2246template<typename T>
2247inline void
2248vec<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
2258template<typename T>
2259inline void
2260vec<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
2270template<typename T>
2271inline T *
2272vec<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
2283template<typename T>
2284inline T *
2285vec<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
2300template<typename T>
2301inline unsigned
2302vec<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
2312template<typename T>
2313inline bool
2314vec<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
2321template<typename T>
2322inline void
2323vec<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
2332template<typename T>
2333inline bool
2334vec<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
2341template<typename T>
2342inline void
2343release_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.
2360template<typename T>
2361class array_slice
2362{
2363 template<typename OtherT> friend class array_slice;
2364
2365public:
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
2423private:
2424 iterator m_base;
2425 unsigned int m_size;
2426};
2427
2428template<typename T>
2429inline typename array_slice<T>::value_type &
2430array_slice<T>::front ()
2431{
2432 gcc_checking_assert (m_size);
2433 return m_base[0];
2434}
2435
2436template<typename T>
2437inline const typename array_slice<T>::value_type &
2438array_slice<T>::front () const
2439{
2440 gcc_checking_assert (m_size);
2441 return m_base[0];
2442}
2443
2444template<typename T>
2445inline typename array_slice<T>::value_type &
2446array_slice<T>::back ()
2447{
2448 gcc_checking_assert (m_size);
2449 return m_base[m_size - 1];
2450}
2451
2452template<typename T>
2453inline const typename array_slice<T>::value_type &
2454array_slice<T>::back () const
2455{
2456 gcc_checking_assert (m_size);
2457 return m_base[m_size - 1];
2458}
2459
2460template<typename T>
2461inline typename array_slice<T>::value_type &
2462array_slice<T>::operator[] (unsigned int i)
2463{
2464 gcc_checking_assert (i < m_size);
2465 return m_base[i];
2466}
2467
2468template<typename T>
2469inline const typename array_slice<T>::value_type &
2470array_slice<T>::operator[] (unsigned int i) const
2471{
2472 gcc_checking_assert (i < m_size);
2473 return m_base[i];
2474}
2475
2476template<typename T>
2477array_slice<T>
2478make_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