Branch data Line data Source code
1 : : /* Vector API for GNU compiler.
2 : : Copyright (C) 2004-2025 Free Software Foundation, Inc.
3 : : Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 : : Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5 : :
6 : : This file is part of GCC.
7 : :
8 : : GCC is free software; you can redistribute it and/or modify it under
9 : : the terms of the GNU General Public License as published by the Free
10 : : Software Foundation; either version 3, or (at your option) any later
11 : : version.
12 : :
13 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 : : for more details.
17 : :
18 : : You should have received a copy of the GNU General Public License
19 : : along with GCC; see the file COPYING3. If not see
20 : : <http://www.gnu.org/licenses/>. */
21 : :
22 : : #ifndef GCC_VEC_H
23 : : #define GCC_VEC_H
24 : :
25 : : /* Some gen* file have no ggc support as the header file gtype-desc.h is
26 : : missing. Provide these definitions in case ggc.h has not been included.
27 : : This is not a problem because any code that runs before gengtype is built
28 : : will never need to use GC vectors.*/
29 : :
30 : : extern void ggc_free (void *);
31 : : extern size_t ggc_round_alloc_size (size_t requested_size);
32 : : extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
33 : :
34 : : /* Templated vector type and associated interfaces.
35 : :
36 : : The interface functions are typesafe and use inline functions,
37 : : sometimes backed by out-of-line generic functions. The vectors are
38 : : designed to interoperate with the GTY machinery.
39 : :
40 : : There are both 'index' and 'iterate' accessors. The index accessor
41 : : is implemented by operator[]. The iterator returns a boolean
42 : : iteration condition and updates the iteration variable passed by
43 : : reference. Because the iterator will be inlined, the address-of
44 : : can be optimized away.
45 : :
46 : : Each operation that increases the number of active elements is
47 : : available in 'quick' and 'safe' variants. The former presumes that
48 : : there is sufficient allocated space for the operation to succeed
49 : : (it dies if there is not). The latter will reallocate the
50 : : vector, if needed. Reallocation causes an exponential increase in
51 : : vector size. If you know you will be adding N elements, it would
52 : : be more efficient to use the reserve operation before adding the
53 : : elements with the 'quick' operation. This will ensure there are at
54 : : least as many elements as you ask for, it will exponentially
55 : : increase if there are too few spare slots. If you want reserve a
56 : : specific number of slots, but do not want the exponential increase
57 : : (for instance, you know this is the last allocation), use the
58 : : reserve_exact operation. You can also create a vector of a
59 : : specific size from the get go.
60 : :
61 : : You should prefer the push and pop operations, as they append and
62 : : remove from the end of the vector. If you need to remove several
63 : : items in one go, use the truncate operation. The insert and remove
64 : : operations allow you to change elements in the middle of the
65 : : vector. There are two remove operations, one which preserves the
66 : : element ordering 'ordered_remove', and one which does not
67 : : 'unordered_remove'. The latter function copies the end element
68 : : into the removed slot, rather than invoke a memmove operation. The
69 : : 'lower_bound' function will determine where to place an item in the
70 : : array using insert that will maintain sorted order.
71 : :
72 : : Vectors are template types with three arguments: the type of the
73 : : elements in the vector, the allocation strategy, and the physical
74 : : layout to use
75 : :
76 : : Four allocation strategies are supported:
77 : :
78 : : - Heap: allocation is done using malloc/free. This is the
79 : : default allocation strategy.
80 : :
81 : : - GC: allocation is done using ggc_alloc/ggc_free.
82 : :
83 : : - GC atomic: same as GC with the exception that the elements
84 : : themselves are assumed to be of an atomic type that does
85 : : not need to be garbage collected. This means that marking
86 : : routines do not need to traverse the array marking the
87 : : individual elements. This increases the performance of
88 : : GC activities.
89 : :
90 : : Two physical layouts are supported:
91 : :
92 : : - Embedded: The vector is structured using the trailing array
93 : : idiom. The last member of the structure is an array of size
94 : : 1. When the vector is initially allocated, a single memory
95 : : block is created to hold the vector's control data and the
96 : : array of elements. These vectors cannot grow without
97 : : reallocation (see discussion on embeddable vectors below).
98 : :
99 : : - Space efficient: The vector is structured as a pointer to an
100 : : embedded vector. This is the default layout. It means that
101 : : vectors occupy a single word of storage before initial
102 : : allocation. Vectors are allowed to grow (the internal
103 : : pointer is reallocated but the main vector instance does not
104 : : need to relocate).
105 : :
106 : : The type, allocation and layout are specified when the vector is
107 : : declared.
108 : :
109 : : If you need to directly manipulate a vector, then the 'address'
110 : : accessor will return the address of the start of the vector. Also
111 : : the 'space' predicate will tell you whether there is spare capacity
112 : : in the vector. You will not normally need to use these two functions.
113 : :
114 : : Not all vector operations support non-POD types and such restrictions
115 : : are enforced through static assertions. Some operations which often use
116 : : memmove to move elements around like quick_insert, safe_insert,
117 : : ordered_remove, unordered_remove, block_remove etc. require trivially
118 : : copyable types. Sorting operations, qsort, sort and stablesort, require
119 : : those too but as an extension allow also std::pair of 2 trivially copyable
120 : : types which happens to work even when std::pair itself isn't trivially
121 : : copyable. The quick_grow and safe_grow operations require trivially
122 : : default constructible types. One can use quick_grow_cleared or
123 : : safe_grow_cleared for non-trivially default constructible types if needed
124 : : (but of course such operation is more expensive then). The pop operation
125 : : returns reference to the last element only for trivially destructible
126 : : types, for non-trivially destructible types one should use last operation
127 : : followed by pop which in that case returns void.
128 : : And finally, the GC and GC atomic vectors should always be used with
129 : : trivially destructible types, as nothing will invoke destructors when they
130 : : are freed during GC.
131 : :
132 : : Notes on the different layout strategies
133 : :
134 : : * Embeddable vectors (vec<T, A, vl_embed>)
135 : :
136 : : These vectors are suitable to be embedded in other data
137 : : structures so that they can be pre-allocated in a contiguous
138 : : memory block.
139 : :
140 : : Embeddable vectors are implemented using the trailing array
141 : : idiom, thus they are not resizeable without changing the address
142 : : of the vector object itself. This means you cannot have
143 : : variables or fields of embeddable vector type -- always use a
144 : : pointer to a vector. The one exception is the final field of a
145 : : structure, which could be a vector type.
146 : :
147 : : You will have to use the embedded_size & embedded_init calls to
148 : : create such objects, and they will not be resizeable (so the
149 : : 'safe' allocation variants are not available).
150 : :
151 : : Properties of embeddable vectors:
152 : :
153 : : - The whole vector and control data are allocated in a single
154 : : contiguous block. It uses the trailing-vector idiom, so
155 : : allocation must reserve enough space for all the elements
156 : : in the vector plus its control data.
157 : : - The vector cannot be re-allocated.
158 : : - The vector cannot grow nor shrink.
159 : : - No indirections needed for access/manipulation.
160 : : - It requires 2 words of storage (prior to vector allocation).
161 : :
162 : :
163 : : * Space efficient vector (vec<T, A, vl_ptr>)
164 : :
165 : : These vectors can grow dynamically and are allocated together
166 : : with their control data. They are suited to be included in data
167 : : structures. Prior to initial allocation, they only take a single
168 : : word of storage.
169 : :
170 : : These vectors are implemented as a pointer to embeddable vectors.
171 : : The semantics allow for this pointer to be NULL to represent
172 : : empty vectors. This way, empty vectors occupy minimal space in
173 : : the structure containing them.
174 : :
175 : : Properties:
176 : :
177 : : - The whole vector and control data are allocated in a single
178 : : contiguous block.
179 : : - The whole vector may be re-allocated.
180 : : - Vector data may grow and shrink.
181 : : - Access and manipulation requires a pointer test and
182 : : indirection.
183 : : - It requires 1 word of storage (prior to vector allocation).
184 : :
185 : : An example of their use would be,
186 : :
187 : : struct my_struct {
188 : : // A space-efficient vector of tree pointers in GC memory.
189 : : vec<tree, va_gc, vl_ptr> v;
190 : : };
191 : :
192 : : struct my_struct *s;
193 : :
194 : : if (s->v.length ()) { we have some contents }
195 : : s->v.safe_push (decl); // append some decl onto the end
196 : : for (ix = 0; s->v.iterate (ix, &elt); ix++)
197 : : { do something with elt }
198 : : */
199 : :
200 : : /* Support function for statistics. */
201 : : extern void dump_vec_loc_statistics (void);
202 : :
203 : : /* Hashtable mapping vec addresses to descriptors. */
204 : : extern htab_t vec_mem_usage_hash;
205 : :
206 : : /* Destruct N elements in DST. */
207 : :
208 : : template <typename T>
209 : : inline void
210 : 28318097 : vec_destruct (T *dst, unsigned n)
211 : : {
212 : 91783535 : for ( ; n; ++dst, --n)
213 : 63465438 : dst->~T ();
214 : 7855059 : }
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 : 4379130773 : vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
254 : : bool exact)
255 : : {
256 : 4379130773 : if (exact)
257 : 730951891 : return (pfx ? pfx->m_num : 0) + reserve;
258 : 3648178882 : else if (!pfx)
259 : 2948583227 : return MAX (4, reserve);
260 : 699595655 : 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 : 2101055306 : va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
305 : : MEM_STAT_DECL)
306 : : {
307 : 2101055306 : size_t elt_size = sizeof (T);
308 : : unsigned alloc
309 : 2101055306 : = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
310 : 2101055306 : 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 : 2101055306 : size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
317 : 4503670377 : unsigned nelem = v ? v->length () : 0;
318 : 2101055306 : v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
319 : 2101055305 : v->embedded_init (alloc, nelem);
320 : :
321 : : if (GATHER_STATISTICS)
322 : : v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
323 : 2101055305 : }
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 : 1781434314 : va_heap::release (vec<T, va_heap, vl_embed> *&v)
336 : : {
337 : 1781434314 : size_t elt_size = sizeof (T);
338 : 2241765 : if (v == NULL)
339 : : return;
340 : :
341 : : if (!std::is_trivially_destructible <T>::value)
342 : 1076141 : 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 : 1778028650 : ::free (v);
348 : 1751551672 : 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 : 372929337 : va_gc::release (vec<T, A, vl_embed> *&v)
380 : : {
381 : 370904849 : if (v)
382 : 91949356 : ::ggc_free (v);
383 : 281981015 : 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 : 2278075468 : va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
395 : : MEM_STAT_DECL)
396 : : {
397 : : unsigned alloc
398 : 2278075468 : = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
399 : 2278075468 : 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 : 2278075468 : 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 : 4556150936 : size = ::ggc_round_alloc_size (size);
411 : :
412 : : /* Adjust the number of slots accordingly. */
413 : 2278075468 : size_t vec_offset = sizeof (vec_prefix);
414 : 2278075468 : size_t elt_size = sizeof (T);
415 : 2278075468 : alloc = (size - vec_offset) / elt_size;
416 : :
417 : : /* And finally, recalculate the amount of space we ask for. */
418 : 2278075468 : size = vec_offset + alloc * elt_size;
419 : :
420 : 2278075468 : unsigned nelem = v ? v->length () : 0;
421 : 2278075468 : v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
422 : : PASS_MEM_STAT));
423 : 2278075468 : 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 : 126629362 : T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
456 : : template<typename T, typename A, typename L>
457 : 126522257 : T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
458 : : template<typename T, typename A, typename L>
459 : 6069 : const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
460 : : template<typename T, typename A, typename L>
461 : 6390189 : 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 : 585316702 : vec_default_construct (T *dst, unsigned n)
545 : : {
546 : 16654878440 : for ( ; n; ++dst, --n)
547 : 16069561738 : ::new (static_cast<void*>(dst)) T ();
548 : 24696782 : }
549 : :
550 : : /* Copy-construct N elements in DST from *SRC. */
551 : :
552 : : template <typename T>
553 : : inline void
554 : 209761903 : vec_copy_construct (T *dst, const T *src, unsigned n)
555 : : {
556 : 1187691283 : for ( ; n; ++dst, ++src, --n)
557 : 977929380 : ::new (static_cast<void*>(dst)) T (*src);
558 : 91017239 : }
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 : 1476339851 : unsigned allocated (void) const { return m_vecpfx.m_alloc; }
603 : 25442815131 : unsigned length (void) const { return m_vecpfx.m_num; }
604 : 16041969720 : bool is_empty (void) const { return m_vecpfx.m_num == 0; }
605 : 5108273125 : T *address (void) { return reinterpret_cast <T *> (this + 1); }
606 : 270899455 : const T *address (void) const
607 : 270899455 : { return reinterpret_cast <const T *> (this + 1); }
608 : 112148359 : T *begin () { return address (); }
609 : 76387141 : const T *begin () const { return address (); }
610 : 174788879 : T *end () { return address () + length (); }
611 : 82771261 : const T *end () const { return address () + length (); }
612 : : const T &operator[] (unsigned) const;
613 : : T &operator[] (unsigned);
614 : : T &last (void);
615 : : bool space (unsigned) const;
616 : : bool iterate (unsigned, T *) const;
617 : : bool iterate (unsigned, T **) const;
618 : : vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
619 : : void splice (const vec &);
620 : : void splice (const vec *src);
621 : : T *quick_push (const T &);
622 : : using pop_ret_type
623 : : = typename std::conditional <std::is_trivially_destructible <T>::value,
624 : : T &, void>::type;
625 : : pop_ret_type pop (void);
626 : : void truncate (unsigned);
627 : : void quick_insert (unsigned, const T &);
628 : : void ordered_remove (unsigned);
629 : : void unordered_remove (unsigned);
630 : : void block_remove (unsigned, unsigned);
631 : : void qsort (int (*) (const void *, const void *));
632 : : void sort (int (*) (const void *, const void *, void *), void *);
633 : : void stablesort (int (*) (const void *, const void *, void *), void *);
634 : : T *bsearch (const void *key, int (*compar) (const void *, const void *));
635 : : T *bsearch (const void *key,
636 : : int (*compar)(const void *, const void *, void *), void *);
637 : : unsigned lower_bound (const T &, bool (*) (const T &, const T &)) const;
638 : : bool contains (const T &search) const;
639 : : static size_t embedded_size (unsigned);
640 : : void embedded_init (unsigned, unsigned = 0, unsigned = 0);
641 : : void quick_grow (unsigned len);
642 : : void quick_grow_cleared (unsigned len);
643 : :
644 : : /* vec class can access our internal data and functions. */
645 : : template <typename, typename, typename> friend struct vec;
646 : :
647 : : /* The allocator types also need access to our internals. */
648 : : friend struct va_gc;
649 : : friend struct va_gc_atomic;
650 : : friend struct va_heap;
651 : :
652 : : /* FIXME - This field should be private, but we need to cater to
653 : : compilers that have stricter notions of PODness for types. */
654 : : /* Align m_vecpfx to simplify address (). */
655 : : alignas (T) alignas (vec_prefix) vec_prefix m_vecpfx;
656 : : };
657 : :
658 : :
659 : : /* Convenience wrapper functions to use when dealing with pointers to
660 : : embedded vectors. Some functionality for these vectors must be
661 : : provided via free functions for these reasons:
662 : :
663 : : 1- The pointer may be NULL (e.g., before initial allocation).
664 : :
665 : : 2- When the vector needs to grow, it must be reallocated, so
666 : : the pointer will change its value.
667 : :
668 : : Because of limitations with the current GC machinery, all vectors
669 : : in GC memory *must* be pointers. */
670 : :
671 : :
672 : : /* If V contains no room for NELEMS elements, return false. Otherwise,
673 : : return true. */
674 : : template<typename T, typename A>
675 : : inline bool
676 : 43738203743 : vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
677 : : {
678 : 85496515419 : return v ? v->space (nelems) : nelems == 0;
679 : : }
680 : :
681 : :
682 : : /* If V is NULL, return 0. Otherwise, return V->length(). */
683 : : template<typename T, typename A>
684 : : inline unsigned
685 : >27949*10^7 : vec_safe_length (const vec<T, A, vl_embed> *v)
686 : : {
687 : >27522*10^7 : return v ? v->length () : 0;
688 : : }
689 : :
690 : :
691 : : /* If V is NULL, return NULL. Otherwise, return V->address(). */
692 : : template<typename T, typename A>
693 : : inline T *
694 : 63914900 : vec_safe_address (vec<T, A, vl_embed> *v)
695 : : {
696 : 63914900 : return v ? v->address () : NULL;
697 : : }
698 : :
699 : :
700 : : /* If V is NULL, return true. Otherwise, return V->is_empty(). */
701 : : template<typename T, typename A>
702 : : inline bool
703 : 2995355655 : vec_safe_is_empty (vec<T, A, vl_embed> *v)
704 : : {
705 : 2995305862 : return v ? v->is_empty () : true;
706 : : }
707 : :
708 : : /* If V does not have space for NELEMS elements, call
709 : : V->reserve(NELEMS, EXACT). */
710 : : template<typename T, typename A>
711 : : inline bool
712 : 43763439742 : vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
713 : : CXX_MEM_STAT_INFO)
714 : : {
715 : 85521751418 : bool extend = nelems ? !vec_safe_space (v, nelems) : false;
716 : : if (extend)
717 : 2411952493 : A::reserve (v, nelems, exact PASS_MEM_STAT);
718 : 43763439742 : return extend;
719 : : }
720 : :
721 : : template<typename T, typename A>
722 : : inline bool
723 : 237423846 : vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
724 : : CXX_MEM_STAT_INFO)
725 : : {
726 : 51948688 : return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
727 : : }
728 : :
729 : :
730 : : /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
731 : : is 0, V is initialized to NULL. */
732 : :
733 : : template<typename T, typename A>
734 : : inline void
735 : 295502494 : vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
736 : : {
737 : 96722537 : v = NULL;
738 : 295211659 : vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
739 : 3379748 : }
740 : :
741 : :
742 : : /* Free the GC memory allocated by vector V and set it to NULL. */
743 : :
744 : : template<typename T, typename A>
745 : : inline void
746 : 358537158 : vec_free (vec<T, A, vl_embed> *&v)
747 : : {
748 : 363268358 : A::release (v);
749 : 21863483 : }
750 : :
751 : :
752 : : /* Grow V to length LEN. Allocate it, if necessary. */
753 : : template<typename T, typename A>
754 : : inline void
755 : 2787271 : vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
756 : : bool exact = false CXX_MEM_STAT_INFO)
757 : : {
758 : 2787271 : unsigned oldlen = vec_safe_length (v);
759 : 603885 : gcc_checking_assert (len >= oldlen);
760 : 2787271 : vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
761 : 2787271 : v->quick_grow (len);
762 : 2787271 : }
763 : :
764 : :
765 : : /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
766 : : template<typename T, typename A>
767 : : inline void
768 : 73217146 : vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
769 : : bool exact = false CXX_MEM_STAT_INFO)
770 : : {
771 : 73217146 : unsigned oldlen = vec_safe_length (v);
772 : 44136642 : gcc_checking_assert (len >= oldlen);
773 : 73217146 : vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
774 : 73217146 : v->quick_grow_cleared (len);
775 : 73217146 : }
776 : :
777 : :
778 : : /* Assume V is not NULL. */
779 : :
780 : : template<typename T>
781 : : inline void
782 : 13044135 : vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
783 : : unsigned len, bool exact = false CXX_MEM_STAT_INFO)
784 : : {
785 : 13044135 : v->safe_grow_cleared (len, exact PASS_MEM_STAT);
786 : 13044135 : }
787 : :
788 : : /* If V does not have space for NELEMS elements, call
789 : : V->reserve(NELEMS, EXACT). */
790 : :
791 : : template<typename T>
792 : : inline bool
793 : : vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
794 : : CXX_MEM_STAT_INFO)
795 : : {
796 : : return v->reserve (nelems, exact);
797 : : }
798 : :
799 : :
800 : : /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
801 : : template<typename T, typename A>
802 : : inline bool
803 : 28494670720 : vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
804 : : {
805 : 28376056095 : if (v)
806 : >12132*10^7 : return v->iterate (ix, ptr);
807 : : else
808 : : {
809 : : *ptr = 0;
810 : : return false;
811 : : }
812 : : }
813 : :
814 : : template<typename T, typename A>
815 : : inline bool
816 : 14826959962 : vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
817 : : {
818 : 14782604597 : if (v)
819 : 2465297706 : return v->iterate (ix, ptr);
820 : : else
821 : : {
822 : 510111 : *ptr = 0;
823 : 510111 : return false;
824 : : }
825 : : }
826 : :
827 : :
828 : : /* If V has no room for one more element, reallocate it. Then call
829 : : V->quick_push(OBJ). */
830 : : template<typename T, typename A>
831 : : inline T *
832 : 41209070924 : vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
833 : : {
834 : 41209070924 : vec_safe_reserve (v, 1, false PASS_MEM_STAT);
835 : 41209070924 : return v->quick_push (obj);
836 : : }
837 : :
838 : :
839 : : /* if V has no room for one more element, reallocate it. Then call
840 : : V->quick_insert(IX, OBJ). */
841 : : template<typename T, typename A>
842 : : inline void
843 : 7588849 : vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
844 : : CXX_MEM_STAT_INFO)
845 : : {
846 : 7588849 : vec_safe_reserve (v, 1, false PASS_MEM_STAT);
847 : 7588849 : v->quick_insert (ix, obj);
848 : 7588849 : }
849 : :
850 : :
851 : : /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
852 : : template<typename T, typename A>
853 : : inline void
854 : 1137579832 : vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
855 : : {
856 : 1137576096 : if (v)
857 : 821910931 : v->truncate (size);
858 : 3736 : }
859 : :
860 : :
861 : : /* If SRC is not NULL, return a pointer to a copy of it. */
862 : : template<typename T, typename A>
863 : : inline vec<T, A, vl_embed> *
864 : 103539215 : vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
865 : : {
866 : 101266235 : return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
867 : : }
868 : :
869 : : /* Copy the elements from SRC to the end of DST as if by memcpy.
870 : : Reallocate DST, if necessary. */
871 : : template<typename T, typename A>
872 : : inline void
873 : 595737126 : vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
874 : : CXX_MEM_STAT_INFO)
875 : : {
876 : 973807924 : unsigned src_len = vec_safe_length (src);
877 : 378070798 : if (src_len)
878 : : {
879 : 17436400 : vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
880 : : PASS_MEM_STAT);
881 : 9957068 : dst->splice (*src);
882 : : }
883 : 595737126 : }
884 : :
885 : : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
886 : : size of the vector and so should be used with care. */
887 : :
888 : : template<typename T, typename A>
889 : : inline bool
890 : 7241028 : vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
891 : : {
892 : 7268164 : return v ? v->contains (search) : false;
893 : : }
894 : :
895 : : /* Index into vector. Return the IX'th element. IX must be in the
896 : : domain of the vector. */
897 : :
898 : : template<typename T, typename A>
899 : : inline const T &
900 : 429078921 : vec<T, A, vl_embed>::operator[] (unsigned ix) const
901 : : {
902 : 429078921 : gcc_checking_assert (ix < m_vecpfx.m_num);
903 : 429078921 : return address ()[ix];
904 : : }
905 : :
906 : : template<typename T, typename A>
907 : : inline T &
908 : >36173*10^7 : vec<T, A, vl_embed>::operator[] (unsigned ix)
909 : : {
910 : >36173*10^7 : gcc_checking_assert (ix < m_vecpfx.m_num);
911 : >36173*10^7 : return address ()[ix];
912 : : }
913 : :
914 : :
915 : : /* Get the final element of the vector, which must not be empty. */
916 : :
917 : : template<typename T, typename A>
918 : : inline T &
919 : 28141893712 : vec<T, A, vl_embed>::last (void)
920 : : {
921 : 28141893712 : gcc_checking_assert (m_vecpfx.m_num > 0);
922 : 28141893712 : return (*this)[m_vecpfx.m_num - 1];
923 : : }
924 : :
925 : :
926 : : /* If this vector has space for NELEMS additional entries, return
927 : : true. You usually only need to use this if you are doing your
928 : : own vector reallocation, for instance on an embedded vector. This
929 : : returns true in exactly the same circumstances that vec::reserve
930 : : will. */
931 : :
932 : : template<typename T, typename A>
933 : : inline bool
934 : >18642*10^7 : vec<T, A, vl_embed>::space (unsigned nelems) const
935 : : {
936 : 90899159181 : return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
937 : : }
938 : :
939 : :
940 : : /* Return iteration condition and update *PTR to (a copy of) the IX'th
941 : : element of this vector. Use this to iterate over the elements of a
942 : : vector as follows,
943 : :
944 : : for (ix = 0; v->iterate (ix, &val); ix++)
945 : : continue; */
946 : :
947 : : template<typename T, typename A>
948 : : inline bool
949 : 87168643353 : vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
950 : : {
951 : 59088382849 : if (ix < m_vecpfx.m_num)
952 : : {
953 : 42098271579 : *ptr = address ()[ix];
954 : 53519126 : return true;
955 : : }
956 : : else
957 : : {
958 : 74979769 : *ptr = 0;
959 : 59154239 : return false;
960 : : }
961 : : }
962 : :
963 : :
964 : : /* Return iteration condition and update *PTR to point to the
965 : : IX'th element of this vector. Use this to iterate over the
966 : : elements of a vector as follows,
967 : :
968 : : for (ix = 0; v->iterate (ix, &ptr); ix++)
969 : : continue;
970 : :
971 : : This variant is for vectors of objects. */
972 : :
973 : : template<typename T, typename A>
974 : : inline bool
975 : 24945563675 : vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
976 : : {
977 : 24215053508 : if (ix < m_vecpfx.m_num)
978 : : {
979 : 19394507694 : *ptr = CONST_CAST (T *, &address ()[ix]);
980 : 50629704 : return true;
981 : : }
982 : : else
983 : : {
984 : 357105 : *ptr = 0;
985 : 357105 : return false;
986 : : }
987 : : }
988 : :
989 : :
990 : : /* Return a pointer to a copy of this vector. */
991 : :
992 : : template<typename T, typename A>
993 : : inline vec<T, A, vl_embed> *
994 : 165874389 : vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
995 : : {
996 : 165874389 : vec<T, A, vl_embed> *new_vec = NULL;
997 : 165874389 : unsigned len = length ();
998 : 165874389 : if (len)
999 : : {
1000 : 165165827 : vec_alloc (new_vec, len PASS_MEM_STAT);
1001 : 165165827 : new_vec->embedded_init (len, len);
1002 : 241037587 : vec_copy_construct (new_vec->address (), address (), len);
1003 : : }
1004 : 165874389 : return new_vec;
1005 : : }
1006 : :
1007 : :
1008 : : /* Copy the elements from SRC to the end of this vector as if by memcpy.
1009 : : The vector must have sufficient headroom available. */
1010 : :
1011 : : template<typename T, typename A>
1012 : : inline void
1013 : 22961108 : vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
1014 : : {
1015 : 22961108 : unsigned len = src.length ();
1016 : 22961108 : if (len)
1017 : : {
1018 : 22961108 : gcc_checking_assert (space (len));
1019 : 22961108 : vec_copy_construct (end (), src.address (), len);
1020 : 22961108 : m_vecpfx.m_num += len;
1021 : : }
1022 : 22961108 : }
1023 : :
1024 : : template<typename T, typename A>
1025 : : inline void
1026 : : vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1027 : : {
1028 : : if (src)
1029 : : splice (*src);
1030 : : }
1031 : :
1032 : :
1033 : : /* Push OBJ (a new element) onto the end of the vector. There must be
1034 : : sufficient space in the vector. Return a pointer to the slot
1035 : : where OBJ was inserted. */
1036 : :
1037 : : template<typename T, typename A>
1038 : : inline T *
1039 : 97181092354 : vec<T, A, vl_embed>::quick_push (const T &obj)
1040 : : {
1041 : 97181092354 : gcc_checking_assert (space (1));
1042 : 97181092354 : T *slot = &address ()[m_vecpfx.m_num++];
1043 : 97181092354 : ::new (static_cast<void*>(slot)) T (obj);
1044 : 97181092354 : return slot;
1045 : : }
1046 : :
1047 : :
1048 : : /* Pop and return a reference to the last element off the end of the
1049 : : vector. If T has non-trivial destructor, this method just pops
1050 : : the element and returns void type. */
1051 : :
1052 : : template<typename T, typename A>
1053 : : inline typename vec<T, A, vl_embed>::pop_ret_type
1054 : 56349677290 : vec<T, A, vl_embed>::pop (void)
1055 : : {
1056 : 56349677290 : gcc_checking_assert (length () > 0);
1057 : 56349677290 : T &last = address ()[--m_vecpfx.m_num];
1058 : : if (!std::is_trivially_destructible <T>::value)
1059 : : last.~T ();
1060 : 56349677290 : return static_cast <pop_ret_type> (last);
1061 : : }
1062 : :
1063 : :
1064 : : /* Set the length of the vector to SIZE. The new length must be less
1065 : : than or equal to the current length. This is an O(1) operation. */
1066 : :
1067 : : template<typename T, typename A>
1068 : : inline void
1069 : 46575259653 : vec<T, A, vl_embed>::truncate (unsigned size)
1070 : : {
1071 : 46575259653 : unsigned l = length ();
1072 : 46575259653 : gcc_checking_assert (l >= size);
1073 : : if (!std::is_trivially_destructible <T>::value)
1074 : 27241989 : vec_destruct (address () + size, l - size);
1075 : 46575259653 : m_vecpfx.m_num = size;
1076 : 46575259653 : }
1077 : :
1078 : :
1079 : : /* Insert an element, OBJ, at the IXth position of this vector. There
1080 : : must be sufficient space. This operation is not suitable for non-trivially
1081 : : copyable types. */
1082 : :
1083 : : template<typename T, typename A>
1084 : : inline void
1085 : 533063451 : vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1086 : : {
1087 : 533063451 : gcc_checking_assert (length () < allocated ());
1088 : 533063451 : 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 : 533063451 : T *slot = &address ()[ix];
1096 : 533063451 : memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1097 : 533063451 : *slot = obj;
1098 : 533063451 : }
1099 : :
1100 : :
1101 : : /* Remove an element from the IXth position of this vector. Ordering of
1102 : : remaining elements is preserved. This is an O(N) operation due to
1103 : : memmove. Not suitable for non-trivially copyable types. */
1104 : :
1105 : : template<typename T, typename A>
1106 : : inline void
1107 : 34661570 : vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1108 : : {
1109 : 34661570 : gcc_checking_assert (ix < length ());
1110 : : #if GCC_VERSION >= 5000
1111 : : static_assert (std::is_trivially_copyable <T>::value, "");
1112 : : #endif
1113 : 34661570 : T *slot = &address ()[ix];
1114 : 34661570 : memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1115 : 34661570 : }
1116 : :
1117 : :
1118 : : /* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1119 : : remaining elements is preserved. This is an O(N) operation. */
1120 : :
1121 : : #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1122 : : elem_ptr, start, end, cond) \
1123 : : { \
1124 : : gcc_assert ((end) <= (vec).length ()); \
1125 : : for (read_index = write_index = (start); read_index < (end); \
1126 : : ++read_index) \
1127 : : { \
1128 : : elem_ptr = &(vec)[read_index]; \
1129 : : bool remove_p = (cond); \
1130 : : if (remove_p) \
1131 : : continue; \
1132 : : \
1133 : : if (read_index != write_index) \
1134 : : (vec)[write_index] = (vec)[read_index]; \
1135 : : \
1136 : : write_index++; \
1137 : : } \
1138 : : \
1139 : : if (read_index - write_index > 0) \
1140 : : (vec).block_remove (write_index, read_index - write_index); \
1141 : : }
1142 : :
1143 : :
1144 : : /* Remove elements from VEC for which COND holds. Ordering of remaining
1145 : : elements is preserved. This is an O(N) operation. */
1146 : :
1147 : : #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1148 : : cond) \
1149 : : VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1150 : : elem_ptr, 0, (vec).length (), (cond))
1151 : :
1152 : : /* Remove an element from the IXth position of this vector. Ordering of
1153 : : remaining elements is destroyed. This is an O(1) operation. */
1154 : :
1155 : : template<typename T, typename A>
1156 : : inline void
1157 : 270080344 : vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1158 : : {
1159 : 270080344 : gcc_checking_assert (ix < length ());
1160 : : #if GCC_VERSION >= 5000
1161 : : static_assert (std::is_trivially_copyable <T>::value, "");
1162 : : #endif
1163 : 270080344 : T *p = address ();
1164 : 270080344 : p[ix] = p[--m_vecpfx.m_num];
1165 : 270080344 : }
1166 : :
1167 : :
1168 : : /* Remove LEN elements starting at the IXth. Ordering is retained.
1169 : : This is an O(N) operation due to memmove. */
1170 : :
1171 : : template<typename T, typename A>
1172 : : inline void
1173 : 878276 : vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1174 : : {
1175 : 878276 : gcc_checking_assert (ix + len <= length ());
1176 : : #if GCC_VERSION >= 5000
1177 : : static_assert (std::is_trivially_copyable <T>::value, "");
1178 : : #endif
1179 : 878276 : T *slot = &address ()[ix];
1180 : 878276 : m_vecpfx.m_num -= len;
1181 : 878276 : memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1182 : 878276 : }
1183 : :
1184 : :
1185 : : #if GCC_VERSION >= 5000
1186 : : namespace vec_detail
1187 : : {
1188 : : /* gcc_{qsort,qsort_r,stablesort_r} implementation under the hood
1189 : : uses memcpy/memmove to reorder the array elements.
1190 : : We want to assert these methods aren't used on types for which
1191 : : that isn't appropriate, but unfortunately std::pair of 2 trivially
1192 : : copyable types isn't trivially copyable and we use qsort on many
1193 : : such std::pair instantiations. Let's allow both trivially
1194 : : copyable types and std::pair of 2 trivially copyable types as
1195 : : exception for qsort/sort/stablesort. */
1196 : : template<typename T>
1197 : : struct is_trivially_copyable_or_pair : std::is_trivially_copyable<T> { };
1198 : :
1199 : : template<typename T, typename U>
1200 : : struct is_trivially_copyable_or_pair<std::pair<T, U> >
1201 : : : std::integral_constant<bool, std::is_trivially_copyable<T>::value
1202 : : && std::is_trivially_copyable<U>::value> { };
1203 : : }
1204 : : #endif
1205 : :
1206 : : /* Sort the contents of this vector with qsort. CMP is the comparison
1207 : : function to pass to qsort. */
1208 : :
1209 : : template<typename T, typename A>
1210 : : inline void
1211 : 108042674 : vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1212 : : {
1213 : : #if GCC_VERSION >= 5000
1214 : : static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1215 : : #endif
1216 : 108042674 : if (length () > 1)
1217 : 92570976 : gcc_qsort (address (), length (), sizeof (T), cmp);
1218 : 108042674 : }
1219 : :
1220 : : /* Sort the contents of this vector with qsort. CMP is the comparison
1221 : : function to pass to qsort. */
1222 : :
1223 : : template<typename T, typename A>
1224 : : inline void
1225 : 1510813 : vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1226 : : void *data)
1227 : : {
1228 : : #if GCC_VERSION >= 5000
1229 : : static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1230 : : #endif
1231 : 1510813 : if (length () > 1)
1232 : 1492956 : gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1233 : 1510813 : }
1234 : :
1235 : : /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1236 : : comparison function to pass to qsort. */
1237 : :
1238 : : template<typename T, typename A>
1239 : : inline void
1240 : 6889 : vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1241 : : void *), void *data)
1242 : : {
1243 : : #if GCC_VERSION >= 5000
1244 : : static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
1245 : : #endif
1246 : 6889 : if (length () > 1)
1247 : 6552 : gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1248 : 6889 : }
1249 : :
1250 : : /* Search the contents of the sorted vector with a binary search.
1251 : : CMP is the comparison function to pass to bsearch. */
1252 : :
1253 : : template<typename T, typename A>
1254 : : inline T *
1255 : : vec<T, A, vl_embed>::bsearch (const void *key,
1256 : : int (*compar) (const void *, const void *))
1257 : : {
1258 : : const void *base = this->address ();
1259 : : size_t nmemb = this->length ();
1260 : : size_t size = sizeof (T);
1261 : : /* The following is a copy of glibc stdlib-bsearch.h. */
1262 : : size_t l, u, idx;
1263 : : const void *p;
1264 : : int comparison;
1265 : :
1266 : : l = 0;
1267 : : u = nmemb;
1268 : : while (l < u)
1269 : : {
1270 : : idx = (l + u) / 2;
1271 : : p = (const void *) (((const char *) base) + (idx * size));
1272 : : comparison = (*compar) (key, p);
1273 : : if (comparison < 0)
1274 : : u = idx;
1275 : : else if (comparison > 0)
1276 : : l = idx + 1;
1277 : : else
1278 : : return (T *)const_cast<void *>(p);
1279 : : }
1280 : :
1281 : : return NULL;
1282 : : }
1283 : :
1284 : : /* Search the contents of the sorted vector with a binary search.
1285 : : CMP is the comparison function to pass to bsearch. */
1286 : :
1287 : : template<typename T, typename A>
1288 : : inline T *
1289 : 197145 : vec<T, A, vl_embed>::bsearch (const void *key,
1290 : : int (*compar) (const void *, const void *,
1291 : : void *), void *data)
1292 : : {
1293 : 197145 : const void *base = this->address ();
1294 : 197145 : size_t nmemb = this->length ();
1295 : 197145 : 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 : 197145 : l = 0;
1302 : 197145 : u = nmemb;
1303 : 255055 : while (l < u)
1304 : : {
1305 : 255055 : idx = (l + u) / 2;
1306 : 255055 : p = (const void *) (((const char *) base) + (idx * size));
1307 : 255055 : comparison = (*compar) (key, p, data);
1308 : 255055 : if (comparison < 0)
1309 : : u = idx;
1310 : 218547 : else if (comparison > 0)
1311 : 21402 : l = idx + 1;
1312 : : else
1313 : : return (T *)const_cast<void *>(p);
1314 : : }
1315 : :
1316 : : return NULL;
1317 : : }
1318 : :
1319 : : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1320 : : size of the vector and so should be used with care. */
1321 : :
1322 : : template<typename T, typename A>
1323 : : inline bool
1324 : 45990174 : vec<T, A, vl_embed>::contains (const T &search) const
1325 : : {
1326 : 45990174 : unsigned int len = length ();
1327 : 45990174 : const T *p = address ();
1328 : 148793413 : for (unsigned int i = 0; i < len; i++)
1329 : : {
1330 : 116020424 : const T *slot = &p[i];
1331 : 116020424 : if (*slot == search)
1332 : : return true;
1333 : : }
1334 : :
1335 : : return false;
1336 : : }
1337 : :
1338 : : /* Find and return the first position in which OBJ could be inserted
1339 : : without changing the ordering of this vector. LESSTHAN is a
1340 : : function that returns true if the first argument is strictly less
1341 : : than the second. */
1342 : :
1343 : : template<typename T, typename A>
1344 : : unsigned
1345 : 83720376 : vec<T, A, vl_embed>::lower_bound (const T &obj,
1346 : : bool (*lessthan)(const T &, const T &))
1347 : : const
1348 : : {
1349 : 83720376 : unsigned int len = length ();
1350 : : unsigned int half, middle;
1351 : 83720376 : unsigned int first = 0;
1352 : 196136532 : while (len > 0)
1353 : : {
1354 : 112416156 : half = len / 2;
1355 : 112416156 : middle = first;
1356 : 112416156 : middle += half;
1357 : 112416156 : const T &middle_elem = address ()[middle];
1358 : 112416156 : if (lessthan (middle_elem, obj))
1359 : : {
1360 : 95583777 : first = middle;
1361 : 95583777 : ++first;
1362 : 95583777 : len = len - half - 1;
1363 : : }
1364 : : else
1365 : : len = half;
1366 : : }
1367 : 83720376 : return first;
1368 : : }
1369 : :
1370 : :
1371 : : /* Return the number of bytes needed to embed an instance of an
1372 : : embeddable vec inside another data structure.
1373 : :
1374 : : Use these methods to determine the required size and initialization
1375 : : of a vector V of type T embedded within another structure (as the
1376 : : final member):
1377 : :
1378 : : size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1379 : : void v->embedded_init (unsigned alloc, unsigned num);
1380 : :
1381 : : These allow the caller to perform the memory allocation. */
1382 : :
1383 : : template<typename T, typename A>
1384 : : inline size_t
1385 : 4499380451 : vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1386 : : {
1387 : : struct alignas (T) U { char data[sizeof (T)]; };
1388 : : typedef vec<U, A, vl_embed> vec_embedded;
1389 : : typedef typename std::conditional<std::is_standard_layout<T>::value,
1390 : : vec, vec_embedded>::type vec_stdlayout;
1391 : : static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1392 : : static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1393 : 4499380451 : return sizeof (vec_stdlayout) + alloc * sizeof (T);
1394 : : }
1395 : :
1396 : :
1397 : : /* Initialize the vector to contain room for ALLOC elements and
1398 : : NUM active elements. */
1399 : :
1400 : : template<typename T, typename A>
1401 : : inline void
1402 : 23727328200 : vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1403 : : {
1404 : 23727328200 : m_vecpfx.m_alloc = alloc;
1405 : 23727328200 : m_vecpfx.m_using_auto_storage = aut;
1406 : 21393231948 : m_vecpfx.m_num = num;
1407 : 2316398655 : }
1408 : :
1409 : :
1410 : : /* Grow the vector to a specific length. LEN must be as long or longer than
1411 : : the current length. The new elements are uninitialized. */
1412 : :
1413 : : template<typename T, typename A>
1414 : : inline void
1415 : 201717375 : vec<T, A, vl_embed>::quick_grow (unsigned len)
1416 : : {
1417 : 201717375 : 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 : 201717375 : m_vecpfx.m_num = len;
1422 : 201717375 : }
1423 : :
1424 : :
1425 : : /* Grow the vector to a specific length. LEN must be as long or longer than
1426 : : the current length. The new elements are initialized to zero. */
1427 : :
1428 : : template<typename T, typename A>
1429 : : inline void
1430 : 605107757 : vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1431 : : {
1432 : 605107757 : unsigned oldlen = length ();
1433 : 605107757 : size_t growby = len - oldlen;
1434 : 605107757 : gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1435 : 605107757 : m_vecpfx.m_num = len;
1436 : 605107757 : if (growby != 0)
1437 : 585316702 : vec_default_construct (address () + oldlen, growby);
1438 : 605107757 : }
1439 : :
1440 : : /* Garbage collection support for vec<T, A, vl_embed>. */
1441 : :
1442 : : template<typename T>
1443 : : void
1444 : 3168093608 : gt_ggc_mx (vec<T, va_gc> *v)
1445 : : {
1446 : : static_assert (std::is_trivially_destructible <T>::value, "");
1447 : : extern void gt_ggc_mx (T &);
1448 : 64166342176 : for (unsigned i = 0; i < v->length (); i++)
1449 : 60998248568 : gt_ggc_mx ((*v)[i]);
1450 : 3168093608 : }
1451 : :
1452 : : template<typename T>
1453 : : void
1454 : : gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1455 : : {
1456 : : static_assert (std::is_trivially_destructible <T>::value, "");
1457 : : /* Nothing to do. Vectors of atomic types wrt GC do not need to
1458 : : be traversed. */
1459 : : }
1460 : :
1461 : :
1462 : : /* PCH support for vec<T, A, vl_embed>. */
1463 : :
1464 : : template<typename T, typename A>
1465 : : void
1466 : 694004 : gt_pch_nx (vec<T, A, vl_embed> *v)
1467 : : {
1468 : : extern void gt_pch_nx (T &);
1469 : 2326415 : for (unsigned i = 0; i < v->length (); i++)
1470 : 1632411 : gt_pch_nx ((*v)[i]);
1471 : 694004 : }
1472 : :
1473 : : template<typename T>
1474 : : void
1475 : : gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *)
1476 : : {
1477 : : /* No pointers to note. */
1478 : : }
1479 : :
1480 : : template<typename T, typename A>
1481 : : void
1482 : 406778 : gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1483 : : {
1484 : 933179 : for (unsigned i = 0; i < v->length (); i++)
1485 : 526401 : op (&((*v)[i]), NULL, cookie);
1486 : 406778 : }
1487 : :
1488 : : template<typename T, typename A>
1489 : : void
1490 : 287226 : gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1491 : : {
1492 : : extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1493 : 1393236 : for (unsigned i = 0; i < v->length (); i++)
1494 : 1106010 : gt_pch_nx (&((*v)[i]), op, cookie);
1495 : 287226 : }
1496 : :
1497 : : template<typename T>
1498 : : void
1499 : : gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *, gt_pointer_operator, void *)
1500 : : {
1501 : : /* No pointers to note. */
1502 : : }
1503 : :
1504 : :
1505 : : /* Space efficient vector. These vectors can grow dynamically and are
1506 : : allocated together with their control data. They are suited to be
1507 : : included in data structures. Prior to initial allocation, they
1508 : : only take a single word of storage.
1509 : :
1510 : : These vectors are implemented as a pointer to an embeddable vector.
1511 : : The semantics allow for this pointer to be NULL to represent empty
1512 : : vectors. This way, empty vectors occupy minimal space in the
1513 : : structure containing them.
1514 : :
1515 : : Properties:
1516 : :
1517 : : - The whole vector and control data are allocated in a single
1518 : : contiguous block.
1519 : : - The whole vector may be re-allocated.
1520 : : - Vector data may grow and shrink.
1521 : : - Access and manipulation requires a pointer test and
1522 : : indirection.
1523 : : - It requires 1 word of storage (prior to vector allocation).
1524 : :
1525 : :
1526 : : Limitations:
1527 : :
1528 : : These vectors must be PODs because they are stored in unions.
1529 : : (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1530 : : As long as we use C++03, we cannot have constructors nor
1531 : : destructors in classes that are stored in unions. */
1532 : :
1533 : : template<typename T, size_t N = 0>
1534 : : class auto_vec;
1535 : :
1536 : : template<typename T>
1537 : : struct vec<T, va_heap, vl_ptr>
1538 : : {
1539 : : public:
1540 : : /* Default ctors to ensure triviality. Use value-initialization
1541 : : (e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1542 : : instance. */
1543 : : vec () = default;
1544 : : vec (const vec &) = default;
1545 : : /* Initialization from the generic vNULL. */
1546 : 907142211 : 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 : 1885456662 : bool exists (void) const
1568 : 1338256772 : { return m_vec != NULL; }
1569 : :
1570 : 13617844554 : bool is_empty (void) const
1571 : 13109604251 : { return m_vec ? m_vec->is_empty () : true; }
1572 : :
1573 : 813038 : unsigned allocated (void) const
1574 : 813038 : { return m_vec ? m_vec->allocated () : 0; }
1575 : :
1576 : 75589421221 : unsigned length (void) const
1577 : 73532635567 : { return m_vec ? m_vec->length () : 0; }
1578 : :
1579 : 9185139203 : T *address (void)
1580 : 4338917334 : { return m_vec ? m_vec->address () : NULL; }
1581 : :
1582 : 226675357 : const T *address (void) const
1583 : 218614664 : { return m_vec ? m_vec->address () : NULL; }
1584 : :
1585 : 6972388986 : T *begin () { return address (); }
1586 : 41063315 : const T *begin () const { return address (); }
1587 : 4264773849 : T *end () { return begin () + length (); }
1588 : 23437692 : const T *end () const { return begin () + length (); }
1589 : 9377126717 : const T &operator[] (unsigned ix) const
1590 : 9276710872 : { return (*m_vec)[ix]; }
1591 : :
1592 : 2850066 : bool operator!=(const vec &other) const
1593 : 2850066 : { return !(*this == other); }
1594 : :
1595 : 76785907 : bool operator==(const vec &other) const
1596 : 153570123 : { return address () == other.address (); }
1597 : :
1598 : >10139*10^7 : T &operator[] (unsigned ix)
1599 : 80134164223 : { return (*m_vec)[ix]; }
1600 : :
1601 : 8965355375 : T &last (void)
1602 : 8965354763 : { return m_vec->last (); }
1603 : :
1604 : 49034897109 : bool space (int nelems) const
1605 : 49034897109 : { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1606 : :
1607 : : bool iterate (unsigned ix, T *p) const;
1608 : : bool iterate (unsigned ix, T **p) const;
1609 : : vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1610 : : bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1611 : : bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1612 : : void splice (const vec &);
1613 : : void safe_splice (const vec & CXX_MEM_STAT_INFO);
1614 : : T *quick_push (const T &);
1615 : : T *safe_push (const T &CXX_MEM_STAT_INFO);
1616 : : using pop_ret_type
1617 : : = typename std::conditional <std::is_trivially_destructible <T>::value,
1618 : : T &, void>::type;
1619 : : pop_ret_type pop (void);
1620 : : void truncate (unsigned);
1621 : : void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
1622 : : void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
1623 : : void quick_grow (unsigned);
1624 : : void quick_grow_cleared (unsigned);
1625 : : void quick_insert (unsigned, const T &);
1626 : : void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1627 : : void ordered_remove (unsigned);
1628 : : void unordered_remove (unsigned);
1629 : : void block_remove (unsigned, unsigned);
1630 : : void qsort (int (*) (const void *, const void *));
1631 : : void sort (int (*) (const void *, const void *, void *), void *);
1632 : : void stablesort (int (*) (const void *, const void *, void *), void *);
1633 : : T *bsearch (const void *key, int (*compar)(const void *, const void *));
1634 : : T *bsearch (const void *key,
1635 : : int (*compar)(const void *, const void *, void *), void *);
1636 : : unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1637 : : bool contains (const T &search) const;
1638 : : void reverse (void);
1639 : :
1640 : : bool using_auto_storage () const;
1641 : :
1642 : : /* FIXME - This field should be private, but we need to cater to
1643 : : compilers that have stricter notions of PODness for types. */
1644 : : vec<T, va_heap, vl_embed> *m_vec;
1645 : : };
1646 : :
1647 : :
1648 : : /* auto_vec is a subclass of vec that automatically manages creating and
1649 : : releasing the internal vector. If N is non zero then it has N elements of
1650 : : internal storage. The default is no internal storage, and you probably only
1651 : : want to ask for internal storage for vectors on the stack because if the
1652 : : size of the vector is larger than the internal storage that space is wasted.
1653 : : */
1654 : : template<typename T, size_t N /* = 0 */>
1655 : : class auto_vec : public vec<T, va_heap>
1656 : : {
1657 : : public:
1658 : 18764376387 : auto_vec ()
1659 : : {
1660 : 18764376387 : 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 : 18764376387 : size_t off = (char *) &m_auto - (char *) this;
1667 : 18231458301 : this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1668 : 196691902 : }
1669 : :
1670 : 332781380 : auto_vec (size_t s CXX_MEM_STAT_INFO)
1671 : : {
1672 : 332576169 : if (s > N)
1673 : : {
1674 : 34375844 : this->create (s PASS_MEM_STAT);
1675 : 34375844 : return;
1676 : : }
1677 : :
1678 : 298405536 : m_auto.embedded_init (N, 0, 1);
1679 : : /* ??? See above. */
1680 : 298405536 : size_t off = (char *) &m_auto - (char *) this;
1681 : 298405536 : this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1682 : : }
1683 : :
1684 : 18715705982 : ~auto_vec ()
1685 : : {
1686 : 17929485377 : this->release ();
1687 : 3413564947 : }
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 : 16490898 : vec<T, va_heap> to_vec_legacy () {
1694 : 16490898 : return *static_cast<vec<T, va_heap> *>(this);
1695 : : }
1696 : :
1697 : : private:
1698 : : vec<T, va_heap, vl_embed> m_auto;
1699 : : unsigned char m_data[sizeof (T) * N];
1700 : : };
1701 : :
1702 : : /* auto_vec is a sub class of vec whose storage is released when it is
1703 : : destroyed. */
1704 : : template<typename T>
1705 : : class auto_vec<T, 0> : public vec<T, va_heap>
1706 : : {
1707 : : public:
1708 : 1720447283 : auto_vec () { this->m_vec = NULL; }
1709 : 165461629 : auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); }
1710 : 1834124304 : ~auto_vec () { this->release (); }
1711 : :
1712 : 632754 : auto_vec (vec<T, va_heap>&& r)
1713 : : {
1714 : 0 : gcc_assert (!r.using_auto_storage ());
1715 : 632754 : this->m_vec = r.m_vec;
1716 : 632754 : r.m_vec = NULL;
1717 : 632754 : }
1718 : :
1719 : 7095340 : auto_vec (auto_vec<T> &&r)
1720 : : {
1721 : 0 : gcc_assert (!r.using_auto_storage ());
1722 : 7095340 : this->m_vec = r.m_vec;
1723 : 7095340 : r.m_vec = NULL;
1724 : 7095340 : }
1725 : :
1726 : 33368237 : auto_vec& operator= (vec<T, va_heap>&& r)
1727 : : {
1728 : 33368237 : if (this == &r)
1729 : : return *this;
1730 : :
1731 : 0 : gcc_assert (!r.using_auto_storage ());
1732 : 33368237 : this->release ();
1733 : 33368237 : this->m_vec = r.m_vec;
1734 : 33368237 : r.m_vec = NULL;
1735 : 33368237 : return *this;
1736 : : }
1737 : :
1738 : 8201921 : auto_vec& operator= (auto_vec<T> &&r)
1739 : : {
1740 : 8201921 : if (this == &r)
1741 : : return *this;
1742 : :
1743 : 0 : gcc_assert (!r.using_auto_storage ());
1744 : 8201921 : this->release ();
1745 : 8201921 : this->m_vec = r.m_vec;
1746 : 8201921 : r.m_vec = NULL;
1747 : 8201921 : 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 : 618 : vec<T, va_heap> to_vec_legacy () {
1755 : 618 : return *static_cast<vec<T, va_heap> *>(this);
1756 : : }
1757 : :
1758 : : // You probably don't want to copy a vector, so these are deleted to prevent
1759 : : // unintentional use. If you really need a copy of the vectors contents you
1760 : : // can use copy ().
1761 : : auto_vec (const auto_vec &) = delete;
1762 : : auto_vec &operator= (const auto_vec &) = delete;
1763 : : };
1764 : :
1765 : :
1766 : : /* Allocate heap memory for pointer V and create the internal vector
1767 : : with space for NELEMS elements. If NELEMS is 0, the internal
1768 : : vector is initialized to empty. */
1769 : :
1770 : : template<typename T>
1771 : : inline void
1772 : 1886367 : vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1773 : : {
1774 : 1886367 : v = new vec<T>;
1775 : 1886367 : v->create (nelems PASS_MEM_STAT);
1776 : 1886367 : }
1777 : :
1778 : :
1779 : : /* A subclass of auto_vec <char *> that frees all of its elements on
1780 : : deletion. */
1781 : :
1782 : 3289 : class auto_string_vec : public auto_vec <char *>
1783 : : {
1784 : : public:
1785 : : ~auto_string_vec ();
1786 : : };
1787 : :
1788 : : /* A subclass of auto_vec <T *> that deletes all of its elements on
1789 : : destruction.
1790 : :
1791 : : This is a crude way for a vec to "own" the objects it points to
1792 : : and clean up automatically.
1793 : :
1794 : : For example, no attempt is made to delete elements when an item
1795 : : within the vec is overwritten.
1796 : :
1797 : : We can't rely on gnu::unique_ptr within a container,
1798 : : since we can't rely on move semantics in C++98. */
1799 : :
1800 : : template <typename T>
1801 : : class auto_delete_vec : public auto_vec <T *>
1802 : : {
1803 : : public:
1804 : 115404 : auto_delete_vec () {}
1805 : 8066575 : auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1806 : :
1807 : : ~auto_delete_vec ();
1808 : :
1809 : : private:
1810 : : DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1811 : : };
1812 : :
1813 : : /* Conditionally allocate heap memory for VEC and its internal vector. */
1814 : :
1815 : : template<typename T>
1816 : : inline void
1817 : 157 : vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1818 : : {
1819 : 157 : if (!vec)
1820 : 85 : vec_alloc (vec, nelems PASS_MEM_STAT);
1821 : : }
1822 : :
1823 : :
1824 : : /* Free the heap memory allocated by vector V and set it to NULL. */
1825 : :
1826 : : template<typename T>
1827 : : inline void
1828 : 5771625 : vec_free (vec<T> *&v)
1829 : : {
1830 : 5771625 : if (v == NULL)
1831 : : return;
1832 : :
1833 : 1877347 : v->release ();
1834 : 1877347 : delete v;
1835 : 1877347 : v = NULL;
1836 : : }
1837 : :
1838 : :
1839 : : /* Return iteration condition and update PTR to point to the IX'th
1840 : : element of this vector. Use this to iterate over the elements of a
1841 : : vector as follows,
1842 : :
1843 : : for (ix = 0; v.iterate (ix, &ptr); ix++)
1844 : : continue; */
1845 : :
1846 : : template<typename T>
1847 : : inline bool
1848 : 51585809528 : vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1849 : : {
1850 : 54138035367 : if (m_vec)
1851 : 59630243648 : return m_vec->iterate (ix, ptr);
1852 : : else
1853 : : {
1854 : 328376883 : *ptr = 0;
1855 : 328376883 : return false;
1856 : : }
1857 : : }
1858 : :
1859 : :
1860 : : /* Return iteration condition and update *PTR to point to the
1861 : : IX'th element of this vector. Use this to iterate over the
1862 : : elements of a vector as follows,
1863 : :
1864 : : for (ix = 0; v->iterate (ix, &ptr); ix++)
1865 : : continue;
1866 : :
1867 : : This variant is for vectors of objects. */
1868 : :
1869 : : template<typename T>
1870 : : inline bool
1871 : 4576254426 : vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1872 : : {
1873 : 4570108159 : if (m_vec)
1874 : 4950097883 : return m_vec->iterate (ix, ptr);
1875 : : else
1876 : : {
1877 : 1018231 : *ptr = 0;
1878 : 1018231 : return false;
1879 : : }
1880 : : }
1881 : :
1882 : :
1883 : : /* Convenience macro for forward iteration. */
1884 : : #define FOR_EACH_VEC_ELT(V, I, P) \
1885 : : for (I = 0; (V).iterate ((I), &(P)); ++(I))
1886 : :
1887 : : #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1888 : : for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1889 : :
1890 : : /* Likewise, but start from FROM rather than 0. */
1891 : : #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1892 : : for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1893 : :
1894 : : /* Convenience macro for reverse iteration. */
1895 : : #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1896 : : for (I = (V).length () - 1; \
1897 : : (V).iterate ((I), &(P)); \
1898 : : (I)--)
1899 : :
1900 : : #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1901 : : for (I = vec_safe_length (V) - 1; \
1902 : : vec_safe_iterate ((V), (I), &(P)); \
1903 : : (I)--)
1904 : :
1905 : : /* auto_string_vec's dtor, freeing all contained strings, automatically
1906 : : chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1907 : :
1908 : : inline
1909 : 3095 : auto_string_vec::~auto_string_vec ()
1910 : : {
1911 : 3095 : int i;
1912 : 3095 : char *str;
1913 : 3558087 : FOR_EACH_VEC_ELT (*this, i, str)
1914 : 3554992 : free (str);
1915 : 3095 : }
1916 : :
1917 : : /* auto_delete_vec's dtor, deleting all contained items, automatically
1918 : : chaining up to ~auto_vec <T*>, which frees the internal buffer. */
1919 : :
1920 : : template <typename T>
1921 : : inline
1922 : 8555773 : auto_delete_vec<T>::~auto_delete_vec ()
1923 : : {
1924 : : int i;
1925 : : T *item;
1926 : 43790374 : FOR_EACH_VEC_ELT (*this, i, item)
1927 : 68657884 : delete item;
1928 : 8555773 : }
1929 : :
1930 : :
1931 : : /* Return a copy of this vector. */
1932 : :
1933 : : template<typename T>
1934 : : inline vec<T, va_heap, vl_ptr>
1935 : 145508450 : vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1936 : : {
1937 : 145508450 : vec<T, va_heap, vl_ptr> new_vec{ };
1938 : 131977874 : if (length ())
1939 : 131962230 : new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1940 : 145508450 : return new_vec;
1941 : : }
1942 : :
1943 : :
1944 : : /* Ensure that the vector has at least RESERVE slots available (if
1945 : : EXACT is false), or exactly RESERVE slots available (if EXACT is
1946 : : true).
1947 : :
1948 : : This may create additional headroom if EXACT is false.
1949 : :
1950 : : Note that this can cause the embedded vector to be reallocated.
1951 : : Returns true iff reallocation actually occurred. */
1952 : :
1953 : : template<typename T>
1954 : : inline bool
1955 : 48884242644 : vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1956 : : {
1957 : 97768485288 : 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 : 1967178281 : vec<T, va_heap, vl_embed> *oldvec = m_vec;
1964 : 1967178281 : unsigned int oldsize = 0;
1965 : 1967178281 : bool handle_auto_vec = m_vec && using_auto_storage ();
1966 : : if (handle_auto_vec)
1967 : : {
1968 : 21634968 : m_vec = NULL;
1969 : 21634968 : oldsize = oldvec->length ();
1970 : 21634968 : nelems += oldsize;
1971 : : }
1972 : :
1973 : 1967178281 : va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1974 : 1967178281 : if (handle_auto_vec)
1975 : : {
1976 : 21634968 : vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1977 : 21634968 : m_vec->m_vecpfx.m_num = oldsize;
1978 : : }
1979 : :
1980 : : return true;
1981 : : }
1982 : :
1983 : :
1984 : : /* Ensure that this vector has exactly NELEMS slots available. This
1985 : : will not create additional headroom. Note this can cause the
1986 : : embedded vector to be reallocated. Returns true iff reallocation
1987 : : actually occurred. */
1988 : :
1989 : : template<typename T>
1990 : : inline bool
1991 : 1852693128 : vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1992 : : {
1993 : 1734093577 : return reserve (nelems, true PASS_MEM_STAT);
1994 : : }
1995 : :
1996 : :
1997 : : /* Create the internal vector and reserve NELEMS for it. This is
1998 : : exactly like vec::reserve, but the internal vector is
1999 : : unconditionally allocated from scratch. The old one, if it
2000 : : existed, is lost. */
2001 : :
2002 : : template<typename T>
2003 : : inline void
2004 : 1065607070 : vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
2005 : : {
2006 : 1060780257 : m_vec = NULL;
2007 : 328492117 : if (nelems > 0)
2008 : 486490229 : reserve_exact (nelems PASS_MEM_STAT);
2009 : 328492117 : }
2010 : :
2011 : :
2012 : : /* Free the memory occupied by the embedded vector. */
2013 : :
2014 : : template<typename T>
2015 : : inline void
2016 : 32285823018 : vec<T, va_heap, vl_ptr>::release (void)
2017 : : {
2018 : 32285823018 : if (!m_vec)
2019 : : return;
2020 : :
2021 : 28858620639 : if (using_auto_storage ())
2022 : : {
2023 : 27078407881 : m_vec->truncate (0);
2024 : 27078407881 : return;
2025 : : }
2026 : :
2027 : 1780212758 : va_heap::release (m_vec);
2028 : : }
2029 : :
2030 : : /* Copy the elements from SRC to the end of this vector as if by memcpy.
2031 : : SRC and this vector must be allocated with the same memory
2032 : : allocation mechanism. This vector is assumed to have sufficient
2033 : : headroom available. */
2034 : :
2035 : : template<typename T>
2036 : : inline void
2037 : 14637195 : vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
2038 : : {
2039 : 13818033 : if (src.length ())
2040 : 13002844 : m_vec->splice (*(src.m_vec));
2041 : 14637195 : }
2042 : :
2043 : :
2044 : : /* Copy the elements in SRC to the end of this vector as if by memcpy.
2045 : : SRC and this vector must be allocated with the same mechanism.
2046 : : If there is not enough headroom in this vector, it will be reallocated
2047 : : as needed. */
2048 : :
2049 : : template<typename T>
2050 : : inline void
2051 : 1495880 : vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
2052 : : MEM_STAT_DECL)
2053 : : {
2054 : 1411507 : if (src.length ())
2055 : : {
2056 : 1405323 : reserve_exact (src.length ());
2057 : 1405323 : splice (src);
2058 : : }
2059 : 1495880 : }
2060 : :
2061 : :
2062 : : /* Push OBJ (a new element) onto the end of the vector. There must be
2063 : : sufficient space in the vector. Return a pointer to the slot
2064 : : where OBJ was inserted. */
2065 : :
2066 : : template<typename T>
2067 : : inline T *
2068 : 54641402376 : vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
2069 : : {
2070 : 35620518892 : return m_vec->quick_push (obj);
2071 : : }
2072 : :
2073 : :
2074 : : /* Push a new element OBJ onto the end of this vector. Reallocates
2075 : : the embedded vector, if needed. Return a pointer to the slot where
2076 : : OBJ was inserted. */
2077 : :
2078 : : template<typename T>
2079 : : inline T *
2080 : 45888382698 : vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
2081 : : {
2082 : 45888382698 : reserve (1, false PASS_MEM_STAT);
2083 : 45888382692 : return quick_push (obj);
2084 : : }
2085 : :
2086 : :
2087 : : /* Pop and return a reference to the last element off the end of the
2088 : : vector. If T has non-trivial destructor, this method just pops
2089 : : last element and returns void. */
2090 : :
2091 : : template<typename T>
2092 : : inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
2093 : 27816043297 : vec<T, va_heap, vl_ptr>::pop (void)
2094 : : {
2095 : 27740877362 : return m_vec->pop ();
2096 : : }
2097 : :
2098 : :
2099 : : /* Set the length of the vector to LEN. The new length must be less
2100 : : than or equal to the current length. This is an O(1) operation. */
2101 : :
2102 : : template<typename T>
2103 : : inline void
2104 : 17844235085 : vec<T, va_heap, vl_ptr>::truncate (unsigned size)
2105 : : {
2106 : 17844235085 : if (m_vec)
2107 : 17716252324 : m_vec->truncate (size);
2108 : : else
2109 : 127982761 : gcc_checking_assert (size == 0);
2110 : 17844235085 : }
2111 : :
2112 : :
2113 : : /* Grow the vector to a specific length. LEN must be as long or
2114 : : longer than the current length. The new elements are
2115 : : uninitialized. Reallocate the internal vector, if needed. */
2116 : :
2117 : : template<typename T>
2118 : : inline void
2119 : 187440346 : vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2120 : : {
2121 : 228348179 : unsigned oldlen = length ();
2122 : 40907833 : gcc_checking_assert (oldlen <= len);
2123 : 187440346 : reserve (len - oldlen, exact PASS_MEM_STAT);
2124 : 187440346 : if (m_vec)
2125 : 187430299 : m_vec->quick_grow (len);
2126 : : else
2127 : 10047 : gcc_checking_assert (len == 0);
2128 : 187440346 : }
2129 : :
2130 : :
2131 : : /* Grow the embedded vector to a specific length. LEN must be as
2132 : : long or longer than the current length. The new elements are
2133 : : initialized to zero. Reallocate the internal vector, if needed. */
2134 : :
2135 : : template<typename T>
2136 : : inline void
2137 : 480311720 : vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2138 : : MEM_STAT_DECL)
2139 : : {
2140 : 573092297 : unsigned oldlen = length ();
2141 : 92780577 : gcc_checking_assert (oldlen <= len);
2142 : 480311720 : reserve (len - oldlen, exact PASS_MEM_STAT);
2143 : 480311720 : if (m_vec)
2144 : 480073247 : m_vec->quick_grow_cleared (len);
2145 : : else
2146 : 238473 : gcc_checking_assert (len == 0);
2147 : 480311720 : }
2148 : :
2149 : :
2150 : : /* Same as vec::safe_grow but without reallocation of the internal vector.
2151 : : If the vector cannot be extended, a runtime assertion will be triggered. */
2152 : :
2153 : : template<typename T>
2154 : : inline void
2155 : 11445492 : vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2156 : : {
2157 : 11445492 : gcc_checking_assert (m_vec);
2158 : 11445492 : m_vec->quick_grow (len);
2159 : 11445492 : }
2160 : :
2161 : :
2162 : : /* Same as vec::quick_grow_cleared but without reallocation of the
2163 : : internal vector. If the vector cannot be extended, a runtime
2164 : : assertion will be triggered. */
2165 : :
2166 : : template<typename T>
2167 : : inline void
2168 : 50906372 : vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2169 : : {
2170 : 50906372 : gcc_checking_assert (m_vec);
2171 : 50906372 : m_vec->quick_grow_cleared (len);
2172 : 50906372 : }
2173 : :
2174 : :
2175 : : /* Insert an element, OBJ, at the IXth position of this vector. There
2176 : : must be sufficient space. */
2177 : :
2178 : : template<typename T>
2179 : : inline void
2180 : 226719224 : vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2181 : : {
2182 : 226719224 : m_vec->quick_insert (ix, obj);
2183 : 495 : }
2184 : :
2185 : :
2186 : : /* Insert an element, OBJ, at the IXth position of the vector.
2187 : : Reallocate the embedded vector, if necessary. */
2188 : :
2189 : : template<typename T>
2190 : : inline void
2191 : 226711724 : vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2192 : : {
2193 : 226711724 : reserve (1, false PASS_MEM_STAT);
2194 : 226711724 : quick_insert (ix, obj);
2195 : 226711724 : }
2196 : :
2197 : :
2198 : : /* Remove an element from the IXth position of this vector. Ordering of
2199 : : remaining elements is preserved. This is an O(N) operation due to
2200 : : a memmove. */
2201 : :
2202 : : template<typename T>
2203 : : inline void
2204 : 1836376 : vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2205 : : {
2206 : 1836346 : m_vec->ordered_remove (ix);
2207 : 152871 : }
2208 : :
2209 : :
2210 : : /* Remove an element from the IXth position of this vector. Ordering
2211 : : of remaining elements is destroyed. This is an O(1) operation. */
2212 : :
2213 : : template<typename T>
2214 : : inline void
2215 : 34508766 : vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2216 : : {
2217 : 34508766 : m_vec->unordered_remove (ix);
2218 : 6756076 : }
2219 : :
2220 : :
2221 : : /* Remove LEN elements starting at the IXth. Ordering is retained.
2222 : : This is an O(N) operation due to memmove. */
2223 : :
2224 : : template<typename T>
2225 : : inline void
2226 : 70521 : vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2227 : : {
2228 : 70521 : m_vec->block_remove (ix, len);
2229 : 46566 : }
2230 : :
2231 : :
2232 : : /* Sort the contents of this vector with qsort. CMP is the comparison
2233 : : function to pass to qsort. */
2234 : :
2235 : : template<typename T>
2236 : : inline void
2237 : 544884996 : vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
2238 : : {
2239 : 494586902 : if (m_vec)
2240 : 87891295 : m_vec->qsort (cmp);
2241 : 48834173 : }
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 : 1511297 : vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
2249 : : void *), void *data)
2250 : : {
2251 : 33933 : if (m_vec)
2252 : 1510813 : m_vec->sort (cmp, data);
2253 : : }
2254 : :
2255 : : /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
2256 : : comparison function to pass to qsort. */
2257 : :
2258 : : template<typename T>
2259 : : inline void
2260 : 6889 : vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *,
2261 : : void *), void *data)
2262 : : {
2263 : 6299 : if (m_vec)
2264 : 6889 : m_vec->stablesort (cmp, data);
2265 : : }
2266 : :
2267 : : /* Search the contents of the sorted vector with a binary search.
2268 : : CMP is the comparison function to pass to bsearch. */
2269 : :
2270 : : template<typename T>
2271 : : inline T *
2272 : : vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2273 : : int (*cmp) (const void *, const void *))
2274 : : {
2275 : : if (m_vec)
2276 : : return m_vec->bsearch (key, cmp);
2277 : : return NULL;
2278 : : }
2279 : :
2280 : : /* Search the contents of the sorted vector with a binary search.
2281 : : CMP is the comparison function to pass to bsearch. */
2282 : :
2283 : : template<typename T>
2284 : : inline T *
2285 : 197145 : vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2286 : : int (*cmp) (const void *, const void *,
2287 : : void *), void *data)
2288 : : {
2289 : 197145 : if (m_vec)
2290 : 197145 : return m_vec->bsearch (key, cmp, data);
2291 : : return NULL;
2292 : : }
2293 : :
2294 : :
2295 : : /* Find and return the first position in which OBJ could be inserted
2296 : : without changing the ordering of this vector. LESSTHAN is a
2297 : : function that returns true if the first argument is strictly less
2298 : : than the second. */
2299 : :
2300 : : template<typename T>
2301 : : inline unsigned
2302 : 137988925 : vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2303 : : bool (*lessthan)(const T &, const T &))
2304 : : const
2305 : : {
2306 : 137988925 : return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
2307 : : }
2308 : :
2309 : : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
2310 : : size of the vector and so should be used with care. */
2311 : :
2312 : : template<typename T>
2313 : : inline bool
2314 : 45963692 : vec<T, va_heap, vl_ptr>::contains (const T &search) const
2315 : : {
2316 : 91926730 : return m_vec ? m_vec->contains (search) : false;
2317 : : }
2318 : :
2319 : : /* Reverse content of the vector. */
2320 : :
2321 : : template<typename T>
2322 : : inline void
2323 : 2115223 : vec<T, va_heap, vl_ptr>::reverse (void)
2324 : : {
2325 : 2115223 : unsigned l = length ();
2326 : 2115223 : T *ptr = address ();
2327 : :
2328 : 2509888 : for (unsigned i = 0; i < l / 2; i++)
2329 : 394665 : std::swap (ptr[i], ptr[l - i - 1]);
2330 : 2115223 : }
2331 : :
2332 : : template<typename T>
2333 : : inline bool
2334 : 29230371015 : vec<T, va_heap, vl_ptr>::using_auto_storage () const
2335 : : {
2336 : 29230371015 : return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2337 : : }
2338 : :
2339 : : /* Release VEC and call release of all element vectors. */
2340 : :
2341 : : template<typename T>
2342 : : inline void
2343 : : release_vec_vec (vec<vec<T> > &vec)
2344 : : {
2345 : : for (unsigned i = 0; i < vec.length (); i++)
2346 : : vec[i].release ();
2347 : :
2348 : : vec.release ();
2349 : : }
2350 : :
2351 : : // Provide a subset of the std::span functionality. (We can't use std::span
2352 : : // itself because it's a C++20 feature.)
2353 : : //
2354 : : // In addition, provide an invalid value that is distinct from all valid
2355 : : // sequences (including the empty sequence). This can be used to return
2356 : : // failure without having to use std::optional.
2357 : : //
2358 : : // There is no operator bool because it would be ambiguous whether it is
2359 : : // testing for a valid value or an empty sequence.
2360 : : template<typename T>
2361 : : class array_slice
2362 : : {
2363 : : template<typename OtherT> friend class array_slice;
2364 : :
2365 : : public:
2366 : : using value_type = T;
2367 : : using iterator = T *;
2368 : : using const_iterator = const T *;
2369 : :
2370 : 31019074 : array_slice () : m_base (nullptr), m_size (0) {}
2371 : :
2372 : : template<typename OtherT>
2373 : 65971568 : array_slice (array_slice<OtherT> other)
2374 : : : m_base (other.m_base), m_size (other.m_size) {}
2375 : :
2376 : 715180384 : array_slice (iterator base, unsigned int size)
2377 : 67251778 : : m_base (base), m_size (size) {}
2378 : :
2379 : : template<size_t N>
2380 : 10045103 : array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2381 : :
2382 : : template<typename OtherT>
2383 : 22411336 : array_slice (const vec<OtherT> &v)
2384 : 24074382 : : m_base (v.address ()), m_size (v.length ()) {}
2385 : :
2386 : : template<typename OtherT>
2387 : 29425518 : array_slice (vec<OtherT> &v)
2388 : 29425518 : : m_base (v.address ()), m_size (v.length ()) {}
2389 : :
2390 : : template<typename OtherT, typename A>
2391 : 2001 : array_slice (const vec<OtherT, A, vl_embed> *v)
2392 : 2001 : : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2393 : :
2394 : : template<typename OtherT, typename A>
2395 : 49204 : array_slice (vec<OtherT, A, vl_embed> *v)
2396 : 49204 : : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2397 : :
2398 : 147637897 : iterator begin () { return m_base; }
2399 : 174132541 : iterator end () { return m_base + m_size; }
2400 : :
2401 : 55900766 : const_iterator begin () const { return m_base; }
2402 : 656206272 : 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 : 298902057 : unsigned size () const { return m_size; }
2413 : 17936555 : size_t size_bytes () const { return m_size * sizeof (T); }
2414 : 19799934 : 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 : 5494396 : static array_slice invalid () { return { nullptr, ~0U }; }
2419 : :
2420 : : // True if the array is valid, false if it is an array like INVALID.
2421 : 91308748 : bool is_valid () const { return m_base || m_size == 0; }
2422 : :
2423 : : private:
2424 : : iterator m_base;
2425 : : unsigned int m_size;
2426 : : };
2427 : :
2428 : : template<typename T>
2429 : : inline typename array_slice<T>::value_type &
2430 : 285 : array_slice<T>::front ()
2431 : : {
2432 : 285 : gcc_checking_assert (m_size);
2433 : 285 : return m_base[0];
2434 : : }
2435 : :
2436 : : template<typename T>
2437 : : inline const typename array_slice<T>::value_type &
2438 : 4904 : array_slice<T>::front () const
2439 : : {
2440 : 4904 : gcc_checking_assert (m_size);
2441 : 4904 : return m_base[0];
2442 : : }
2443 : :
2444 : : template<typename T>
2445 : : inline typename array_slice<T>::value_type &
2446 : 0 : array_slice<T>::back ()
2447 : : {
2448 : 0 : gcc_checking_assert (m_size);
2449 : 0 : return m_base[m_size - 1];
2450 : : }
2451 : :
2452 : : template<typename T>
2453 : : inline const typename array_slice<T>::value_type &
2454 : 97793432 : array_slice<T>::back () const
2455 : : {
2456 : 97793432 : gcc_checking_assert (m_size);
2457 : 97793432 : return m_base[m_size - 1];
2458 : : }
2459 : :
2460 : : template<typename T>
2461 : : inline typename array_slice<T>::value_type &
2462 : 97032247 : array_slice<T>::operator[] (unsigned int i)
2463 : : {
2464 : 97032247 : gcc_checking_assert (i < m_size);
2465 : 97032247 : return m_base[i];
2466 : : }
2467 : :
2468 : : template<typename T>
2469 : : inline const typename array_slice<T>::value_type &
2470 : 97846036 : array_slice<T>::operator[] (unsigned int i) const
2471 : : {
2472 : 97846036 : gcc_checking_assert (i < m_size);
2473 : 97846036 : return m_base[i];
2474 : : }
2475 : :
2476 : : template<typename T>
2477 : : array_slice<T>
2478 : 121122 : make_array_slice (T *base, unsigned int size)
2479 : : {
2480 : 121122 : 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
|
