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