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