Line data Source code
1 : /* Vector API for GNU compiler.
2 : Copyright (C) 2004-2023 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 : Notes on the different layout strategies
115 :
116 : * Embeddable vectors (vec<T, A, vl_embed>)
117 :
118 : These vectors are suitable to be embedded in other data
119 : structures so that they can be pre-allocated in a contiguous
120 : memory block.
121 :
122 : Embeddable vectors are implemented using the trailing array
123 : idiom, thus they are not resizeable without changing the address
124 : of the vector object itself. This means you cannot have
125 : variables or fields of embeddable vector type -- always use a
126 : pointer to a vector. The one exception is the final field of a
127 : structure, which could be a vector type.
128 :
129 : You will have to use the embedded_size & embedded_init calls to
130 : create such objects, and they will not be resizeable (so the
131 : 'safe' allocation variants are not available).
132 :
133 : Properties of embeddable vectors:
134 :
135 : - The whole vector and control data are allocated in a single
136 : contiguous block. It uses the trailing-vector idiom, so
137 : allocation must reserve enough space for all the elements
138 : in the vector plus its control data.
139 : - The vector cannot be re-allocated.
140 : - The vector cannot grow nor shrink.
141 : - No indirections needed for access/manipulation.
142 : - It requires 2 words of storage (prior to vector allocation).
143 :
144 :
145 : * Space efficient vector (vec<T, A, vl_ptr>)
146 :
147 : These vectors can grow dynamically and are allocated together
148 : with their control data. They are suited to be included in data
149 : structures. Prior to initial allocation, they only take a single
150 : word of storage.
151 :
152 : These vectors are implemented as a pointer to embeddable vectors.
153 : The semantics allow for this pointer to be NULL to represent
154 : empty vectors. This way, empty vectors occupy minimal space in
155 : the structure containing them.
156 :
157 : Properties:
158 :
159 : - The whole vector and control data are allocated in a single
160 : contiguous block.
161 : - The whole vector may be re-allocated.
162 : - Vector data may grow and shrink.
163 : - Access and manipulation requires a pointer test and
164 : indirection.
165 : - It requires 1 word of storage (prior to vector allocation).
166 :
167 : An example of their use would be,
168 :
169 : struct my_struct {
170 : // A space-efficient vector of tree pointers in GC memory.
171 : vec<tree, va_gc, vl_ptr> v;
172 : };
173 :
174 : struct my_struct *s;
175 :
176 : if (s->v.length ()) { we have some contents }
177 : s->v.safe_push (decl); // append some decl onto the end
178 : for (ix = 0; s->v.iterate (ix, &elt); ix++)
179 : { do something with elt }
180 : */
181 :
182 : /* Support function for statistics. */
183 : extern void dump_vec_loc_statistics (void);
184 :
185 : /* Hashtable mapping vec addresses to descriptors. */
186 : extern htab_t vec_mem_usage_hash;
187 :
188 : /* Control data for vectors. This contains the number of allocated
189 : and used slots inside a vector. */
190 :
191 : struct vec_prefix
192 : {
193 : /* FIXME - These fields should be private, but we need to cater to
194 : compilers that have stricter notions of PODness for types. */
195 :
196 : /* Memory allocation support routines in vec.cc. */
197 : void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
198 : void release_overhead (void *, size_t, size_t, bool CXX_MEM_STAT_INFO);
199 : static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
200 : static unsigned calculate_allocation_1 (unsigned, unsigned);
201 :
202 : /* Note that vec_prefix should be a base class for vec, but we use
203 : offsetof() on vector fields of tree structures (e.g.,
204 : tree_binfo::base_binfos), and offsetof only supports base types.
205 :
206 : To compensate, we make vec_prefix a field inside vec and make
207 : vec a friend class of vec_prefix so it can access its fields. */
208 : template <typename, typename, typename> friend struct vec;
209 :
210 : /* The allocator types also need access to our internals. */
211 : friend struct va_gc;
212 : friend struct va_gc_atomic;
213 : friend struct va_heap;
214 :
215 : unsigned m_alloc : 31;
216 : unsigned m_using_auto_storage : 1;
217 : unsigned m_num;
218 : };
219 :
220 : /* Calculate the number of slots to reserve a vector, making sure that
221 : RESERVE slots are free. If EXACT grow exactly, otherwise grow
222 : exponentially. PFX is the control data for the vector. */
223 :
224 : inline unsigned
225 564531828 : vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
226 : bool exact)
227 : {
228 564531828 : if (exact)
229 74447034 : return (pfx ? pfx->m_num : 0) + reserve;
230 490084794 : else if (!pfx)
231 421742962 : return MAX (4, reserve);
232 68341832 : return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
233 : }
234 :
235 : template<typename, typename, typename> struct vec;
236 :
237 : /* Valid vector layouts
238 :
239 : vl_embed - Embeddable vector that uses the trailing array idiom.
240 : vl_ptr - Space efficient vector that uses a pointer to an
241 : embeddable vector. */
242 : struct vl_embed { };
243 : struct vl_ptr { };
244 :
245 :
246 : /* Types of supported allocations
247 :
248 : va_heap - Allocation uses malloc/free.
249 : va_gc - Allocation uses ggc_alloc.
250 : va_gc_atomic - Same as GC, but individual elements of the array
251 : do not need to be marked during collection. */
252 :
253 : /* Allocator type for heap vectors. */
254 : struct va_heap
255 : {
256 : /* Heap vectors are frequently regular instances, so use the vl_ptr
257 : layout for them. */
258 : typedef vl_ptr default_layout;
259 :
260 : template<typename T>
261 : static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
262 : CXX_MEM_STAT_INFO);
263 :
264 : template<typename T>
265 : static void release (vec<T, va_heap, vl_embed> *&);
266 : };
267 :
268 :
269 : /* Allocator for heap memory. Ensure there are at least RESERVE free
270 : slots in V. If EXACT is true, grow exactly, else grow
271 : exponentially. As a special case, if the vector had not been
272 : allocated and RESERVE is 0, no vector will be created. */
273 :
274 : template<typename T>
275 : inline void
276 91197161 : va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
277 : MEM_STAT_DECL)
278 : {
279 91197161 : size_t elt_size = sizeof (T);
280 : unsigned alloc
281 91197161 : = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
282 91197161 : gcc_checking_assert (alloc);
283 :
284 : if (GATHER_STATISTICS && v)
285 : v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
286 : v->allocated (), false);
287 :
288 91197161 : size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
289 199756324 : unsigned nelem = v ? v->length () : 0;
290 91197161 : v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
291 91197161 : v->embedded_init (alloc, nelem);
292 :
293 : if (GATHER_STATISTICS)
294 : v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT);
295 91197161 : }
296 :
297 :
298 : #if GCC_VERSION >= 4007
299 : #pragma GCC diagnostic push
300 : #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
301 : #endif
302 :
303 : /* Free the heap space allocated for vector V. */
304 :
305 : template<typename T>
306 : void
307 69805239 : va_heap::release (vec<T, va_heap, vl_embed> *&v)
308 : {
309 69805239 : size_t elt_size = sizeof (T);
310 181327 : if (v == NULL)
311 : return;
312 :
313 : if (GATHER_STATISTICS)
314 : v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
315 : v->allocated (), true);
316 65202661 : ::free (v);
317 65200592 : v = NULL;
318 : }
319 :
320 : #if GCC_VERSION >= 4007
321 : #pragma GCC diagnostic pop
322 : #endif
323 :
324 : /* Allocator type for GC vectors. Notice that we need the structure
325 : declaration even if GC is not enabled. */
326 :
327 : struct va_gc
328 : {
329 : /* Use vl_embed as the default layout for GC vectors. Due to GTY
330 : limitations, GC vectors must always be pointers, so it is more
331 : efficient to use a pointer to the vl_embed layout, rather than
332 : using a pointer to a pointer as would be the case with vl_ptr. */
333 : typedef vl_embed default_layout;
334 :
335 : template<typename T, typename A>
336 : static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
337 : CXX_MEM_STAT_INFO);
338 :
339 : template<typename T, typename A>
340 : static void release (vec<T, A, vl_embed> *&v);
341 : };
342 :
343 :
344 : /* Free GC memory used by V and reset V to NULL. */
345 :
346 : template<typename T, typename A>
347 : inline void
348 353360 : va_gc::release (vec<T, A, vl_embed> *&v)
349 : {
350 261359 : if (v)
351 134279 : ::ggc_free (v);
352 350931 : v = NULL;
353 : }
354 :
355 :
356 : /* Allocator for GC memory. Ensure there are at least RESERVE free
357 : slots in V. If EXACT is true, grow exactly, else grow
358 : exponentially. As a special case, if the vector had not been
359 : allocated and RESERVE is 0, no vector will be created. */
360 :
361 : template<typename T, typename A>
362 : void
363 473334667 : va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
364 : MEM_STAT_DECL)
365 : {
366 : unsigned alloc
367 473334667 : = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
368 473334667 : if (!alloc)
369 : {
370 0 : ::ggc_free (v);
371 0 : v = NULL;
372 0 : return;
373 : }
374 :
375 : /* Calculate the amount of space we want. */
376 473334667 : size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
377 :
378 : /* Ask the allocator how much space it will really give us. */
379 946669334 : size = ::ggc_round_alloc_size (size);
380 :
381 : /* Adjust the number of slots accordingly. */
382 473334667 : size_t vec_offset = sizeof (vec_prefix);
383 473334667 : size_t elt_size = sizeof (T);
384 473334667 : alloc = (size - vec_offset) / elt_size;
385 :
386 : /* And finally, recalculate the amount of space we ask for. */
387 473334667 : size = vec_offset + alloc * elt_size;
388 :
389 473334667 : unsigned nelem = v ? v->length () : 0;
390 473334667 : v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
391 : PASS_MEM_STAT));
392 946669334 : v->embedded_init (alloc, nelem);
393 : }
394 :
395 :
396 : /* Allocator type for GC vectors. This is for vectors of types
397 : atomics w.r.t. collection, so allocation and deallocation is
398 : completely inherited from va_gc. */
399 : struct va_gc_atomic : va_gc
400 : {
401 : };
402 :
403 :
404 : /* Generic vector template. Default values for A and L indicate the
405 : most commonly used strategies.
406 :
407 : FIXME - Ideally, they would all be vl_ptr to encourage using regular
408 : instances for vectors, but the existing GTY machinery is limited
409 : in that it can only deal with GC objects that are pointers
410 : themselves.
411 :
412 : This means that vector operations that need to deal with
413 : potentially NULL pointers, must be provided as free
414 : functions (see the vec_safe_* functions above). */
415 : template<typename T,
416 : typename A = va_heap,
417 : typename L = typename A::default_layout>
418 : struct GTY((user)) vec
419 : {
420 : };
421 :
422 : /* Allow C++11 range-based 'for' to work directly on vec<T>*. */
423 : template<typename T, typename A, typename L>
424 24797963 : T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
425 : template<typename T, typename A, typename L>
426 24741039 : T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; }
427 : template<typename T, typename A, typename L>
428 : const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; }
429 : template<typename T, typename A, typename L>
430 : const T* end (const vec<T,A,L> *v) { return v ? v->end () : nullptr; }
431 :
432 : /* Generic vec<> debug helpers.
433 :
434 : These need to be instantiated for each vec<TYPE> used throughout
435 : the compiler like this:
436 :
437 : DEFINE_DEBUG_VEC (TYPE)
438 :
439 : The reason we have a debug_helper() is because GDB can't
440 : disambiguate a plain call to debug(some_vec), and it must be called
441 : like debug<TYPE>(some_vec). */
442 :
443 : template<typename T>
444 : void
445 : debug_helper (vec<T> &ref)
446 : {
447 : unsigned i;
448 : for (i = 0; i < ref.length (); ++i)
449 : {
450 : fprintf (stderr, "[%d] = ", i);
451 : debug_slim (ref[i]);
452 : fputc ('\n', stderr);
453 : }
454 : }
455 :
456 : /* We need a separate va_gc variant here because default template
457 : argument for functions cannot be used in c++-98. Once this
458 : restriction is removed, those variant should be folded with the
459 : above debug_helper. */
460 :
461 : template<typename T>
462 : void
463 : debug_helper (vec<T, va_gc> &ref)
464 : {
465 : unsigned i;
466 : for (i = 0; i < ref.length (); ++i)
467 : {
468 : fprintf (stderr, "[%d] = ", i);
469 : debug_slim (ref[i]);
470 : fputc ('\n', stderr);
471 : }
472 : }
473 :
474 : /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
475 : functions for a type T. */
476 :
477 : #define DEFINE_DEBUG_VEC(T) \
478 : template void debug_helper (vec<T> &); \
479 : template void debug_helper (vec<T, va_gc> &); \
480 : /* Define the vec<T> debug functions. */ \
481 : DEBUG_FUNCTION void \
482 : debug (vec<T> &ref) \
483 : { \
484 : debug_helper <T> (ref); \
485 : } \
486 : DEBUG_FUNCTION void \
487 : debug (vec<T> *ptr) \
488 : { \
489 : if (ptr) \
490 : debug (*ptr); \
491 : else \
492 : fprintf (stderr, "<nil>\n"); \
493 : } \
494 : /* Define the vec<T, va_gc> debug functions. */ \
495 : DEBUG_FUNCTION void \
496 : debug (vec<T, va_gc> &ref) \
497 : { \
498 : debug_helper <T> (ref); \
499 : } \
500 : DEBUG_FUNCTION void \
501 : debug (vec<T, va_gc> *ptr) \
502 : { \
503 : if (ptr) \
504 : debug (*ptr); \
505 : else \
506 : fprintf (stderr, "<nil>\n"); \
507 : }
508 :
509 : /* Default-construct N elements in DST. */
510 :
511 : template <typename T>
512 : inline void
513 7810173 : vec_default_construct (T *dst, unsigned n)
514 : {
515 : #ifdef BROKEN_VALUE_INITIALIZATION
516 : /* Versions of GCC before 4.4 sometimes leave certain objects
517 : uninitialized when value initialized, though if the type has
518 : user defined default ctor, that ctor is invoked. As a workaround
519 : perform clearing first and then the value initialization, which
520 : fixes the case when value initialization doesn't initialize due to
521 : the bugs and should initialize to all zeros, but still allows
522 : vectors for types with user defined default ctor that initializes
523 : some or all elements to non-zero. If T has no user defined
524 : default ctor and some non-static data members have user defined
525 : default ctors that initialize to non-zero the workaround will
526 : still not work properly; in that case we just need to provide
527 : user defined default ctor. */
528 : memset (dst, '\0', sizeof (T) * n);
529 : #endif
530 40994396 : for ( ; n; ++dst, --n)
531 33184223 : ::new (static_cast<void*>(dst)) T ();
532 : }
533 :
534 : /* Copy-construct N elements in DST from *SRC. */
535 :
536 : template <typename T>
537 : inline void
538 1883513 : vec_copy_construct (T *dst, const T *src, unsigned n)
539 : {
540 7651322 : for ( ; n; ++dst, ++src, --n)
541 5767809 : ::new (static_cast<void*>(dst)) T (*src);
542 : }
543 :
544 : /* Type to provide zero-initialized values for vec<T, A, L>. This is
545 : used to provide nil initializers for vec instances. Since vec must
546 : be a trivially copyable type that can be copied by memcpy and zeroed
547 : out by memset, it must have defaulted default and copy ctor and copy
548 : assignment. To initialize a vec either use value initialization
549 : (e.g., vec() or vec v{ };) or assign it the value vNULL. This isn't
550 : needed for file-scope and function-local static vectors, which are
551 : zero-initialized by default. */
552 : struct vnull { };
553 : constexpr vnull vNULL{ };
554 :
555 :
556 : /* Embeddable vector. These vectors are suitable to be embedded
557 : in other data structures so that they can be pre-allocated in a
558 : contiguous memory block.
559 :
560 : Embeddable vectors are implemented using the trailing array idiom,
561 : thus they are not resizeable without changing the address of the
562 : vector object itself. This means you cannot have variables or
563 : fields of embeddable vector type -- always use a pointer to a
564 : vector. The one exception is the final field of a structure, which
565 : could be a vector type.
566 :
567 : You will have to use the embedded_size & embedded_init calls to
568 : create such objects, and they will not be resizeable (so the 'safe'
569 : allocation variants are not available).
570 :
571 : Properties:
572 :
573 : - The whole vector and control data are allocated in a single
574 : contiguous block. It uses the trailing-vector idiom, so
575 : allocation must reserve enough space for all the elements
576 : in the vector plus its control data.
577 : - The vector cannot be re-allocated.
578 : - The vector cannot grow nor shrink.
579 : - No indirections needed for access/manipulation.
580 : - It requires 2 words of storage (prior to vector allocation). */
581 :
582 : template<typename T, typename A>
583 : struct GTY((user)) vec<T, A, vl_embed>
584 : {
585 : public:
586 14317178 : unsigned allocated (void) const { return m_vecpfx.m_alloc; }
587 4119427636 : unsigned length (void) const { return m_vecpfx.m_num; }
588 801983692 : bool is_empty (void) const { return m_vecpfx.m_num == 0; }
589 92603648 : T *address (void) { return reinterpret_cast <T *> (this + 1); }
590 51283837 : const T *address (void) const
591 51283837 : { return reinterpret_cast <const T *> (this + 1); }
592 9597516 : T *begin () { return address (); }
593 49611073 : const T *begin () const { return address (); }
594 29773321 : T *end () { return address () + length (); }
595 49611073 : const T *end () const { return address () + length (); }
596 : const T &operator[] (unsigned) const;
597 : T &operator[] (unsigned);
598 : T &last (void);
599 : bool space (unsigned) const;
600 : bool iterate (unsigned, T *) const;
601 : bool iterate (unsigned, T **) const;
602 : vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
603 : void splice (const vec &);
604 : void splice (const vec *src);
605 : T *quick_push (const T &);
606 : T &pop (void);
607 : void truncate (unsigned);
608 : void quick_insert (unsigned, const T &);
609 : void ordered_remove (unsigned);
610 : void unordered_remove (unsigned);
611 : void block_remove (unsigned, unsigned);
612 : void qsort (int (*) (const void *, const void *));
613 : void sort (int (*) (const void *, const void *, void *), void *);
614 : void stablesort (int (*) (const void *, const void *, void *), void *);
615 : T *bsearch (const void *key, int (*compar) (const void *, const void *));
616 : T *bsearch (const void *key,
617 : int (*compar)(const void *, const void *, void *), void *);
618 : unsigned lower_bound (const T &, bool (*) (const T &, const T &)) const;
619 : bool contains (const T &search) const;
620 : static size_t embedded_size (unsigned);
621 : void embedded_init (unsigned, unsigned = 0, unsigned = 0);
622 : void quick_grow (unsigned len);
623 : void quick_grow_cleared (unsigned len);
624 :
625 : /* vec class can access our internal data and functions. */
626 : template <typename, typename, typename> friend struct vec;
627 :
628 : /* The allocator types also need access to our internals. */
629 : friend struct va_gc;
630 : friend struct va_gc_atomic;
631 : friend struct va_heap;
632 :
633 : /* FIXME - This field should be private, but we need to cater to
634 : compilers that have stricter notions of PODness for types. */
635 : /* Align m_vecpfx to simplify address (). */
636 : alignas (T) alignas (vec_prefix) vec_prefix m_vecpfx;
637 : };
638 :
639 :
640 : /* Convenience wrapper functions to use when dealing with pointers to
641 : embedded vectors. Some functionality for these vectors must be
642 : provided via free functions for these reasons:
643 :
644 : 1- The pointer may be NULL (e.g., before initial allocation).
645 :
646 : 2- When the vector needs to grow, it must be reallocated, so
647 : the pointer will change its value.
648 :
649 : Because of limitations with the current GC machinery, all vectors
650 : in GC memory *must* be pointers. */
651 :
652 :
653 : /* If V contains no room for NELEMS elements, return false. Otherwise,
654 : return true. */
655 : template<typename T, typename A>
656 : inline bool
657 24121728307 : vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
658 : {
659 47940527181 : return v ? v->space (nelems) : nelems == 0;
660 : }
661 :
662 :
663 : /* If V is NULL, return 0. Otherwise, return V->length(). */
664 : template<typename T, typename A>
665 : inline unsigned
666 3499722743 : vec_safe_length (const vec<T, A, vl_embed> *v)
667 : {
668 3497166754 : return v ? v->length () : 0;
669 : }
670 :
671 :
672 : /* If V is NULL, return NULL. Otherwise, return V->address(). */
673 : template<typename T, typename A>
674 : inline T *
675 5463538 : vec_safe_address (vec<T, A, vl_embed> *v)
676 : {
677 5463538 : return v ? v->address () : NULL;
678 : }
679 :
680 :
681 : /* If V is NULL, return true. Otherwise, return V->is_empty(). */
682 : template<typename T, typename A>
683 : inline bool
684 859455713 : vec_safe_is_empty (vec<T, A, vl_embed> *v)
685 : {
686 859455713 : return v ? v->is_empty () : true;
687 : }
688 :
689 : /* If V does not have space for NELEMS elements, call
690 : V->reserve(NELEMS, EXACT). */
691 : template<typename T, typename A>
692 : inline bool
693 24122711682 : vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
694 : CXX_MEM_STAT_INFO)
695 : {
696 47941510556 : bool extend = nelems ? !vec_safe_space (v, nelems) : false;
697 : if (extend)
698 343347778 : A::reserve (v, nelems, exact PASS_MEM_STAT);
699 24122711682 : return extend;
700 : }
701 :
702 : template<typename T, typename A>
703 : inline bool
704 128019061 : vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
705 : CXX_MEM_STAT_INFO)
706 : {
707 26181993 : return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
708 : }
709 :
710 :
711 : /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
712 : is 0, V is initialized to NULL. */
713 :
714 : template<typename T, typename A>
715 : inline void
716 40945825 : vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
717 : {
718 39127920 : v = NULL;
719 40856565 : vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
720 569 : }
721 :
722 :
723 : /* Free the GC memory allocated by vector V and set it to NULL. */
724 :
725 : template<typename T, typename A>
726 : inline void
727 446549 : vec_free (vec<T, A, vl_embed> *&v)
728 : {
729 11268517 : A::release (v);
730 89898 : }
731 :
732 :
733 : /* Grow V to length LEN. Allocate it, if necessary. */
734 : template<typename T, typename A>
735 : inline void
736 2165569 : vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len,
737 : bool exact = false CXX_MEM_STAT_INFO)
738 : {
739 2165569 : unsigned oldlen = vec_safe_length (v);
740 470895 : gcc_checking_assert (len >= oldlen);
741 2165569 : vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
742 2165569 : v->quick_grow (len);
743 2165569 : }
744 :
745 :
746 : /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
747 : template<typename T, typename A>
748 : inline void
749 330394 : vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
750 : bool exact = false CXX_MEM_STAT_INFO)
751 : {
752 330394 : unsigned oldlen = vec_safe_length (v);
753 330394 : vec_safe_grow (v, len, exact PASS_MEM_STAT);
754 330394 : vec_default_construct (v->address () + oldlen, len - oldlen);
755 330394 : }
756 :
757 :
758 : /* Assume V is not NULL. */
759 :
760 : template<typename T>
761 : inline void
762 : vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v,
763 : unsigned len, bool exact = false CXX_MEM_STAT_INFO)
764 : {
765 : v->safe_grow_cleared (len, exact PASS_MEM_STAT);
766 : }
767 :
768 : /* If V does not have space for NELEMS elements, call
769 : V->reserve(NELEMS, EXACT). */
770 :
771 : template<typename T>
772 : inline bool
773 : vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false
774 : CXX_MEM_STAT_INFO)
775 : {
776 : return v->reserve (nelems, exact);
777 : }
778 :
779 :
780 : /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
781 : template<typename T, typename A>
782 : inline bool
783 6768134205 : vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
784 : {
785 6678152349 : if (v)
786 751339026 : return v->iterate (ix, ptr);
787 : else
788 : {
789 : *ptr = 0;
790 : return false;
791 : }
792 : }
793 :
794 : template<typename T, typename A>
795 : inline bool
796 3944677874 : vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
797 : {
798 3920162565 : if (v)
799 1175327612 : return v->iterate (ix, ptr);
800 : else
801 : {
802 10 : *ptr = 0;
803 10 : return false;
804 : }
805 : }
806 :
807 :
808 : /* If V has no room for one more element, reallocate it. Then call
809 : V->quick_push(OBJ). */
810 : template<typename T, typename A>
811 : inline T *
812 23937842424 : vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
813 : {
814 23937842424 : vec_safe_reserve (v, 1, false PASS_MEM_STAT);
815 23937842424 : return v->quick_push (obj);
816 : }
817 :
818 :
819 : /* if V has no room for one more element, reallocate it. Then call
820 : V->quick_insert(IX, OBJ). */
821 : template<typename T, typename A>
822 : inline void
823 1477059 : vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
824 : CXX_MEM_STAT_INFO)
825 : {
826 1477059 : vec_safe_reserve (v, 1, false PASS_MEM_STAT);
827 1477059 : v->quick_insert (ix, obj);
828 1477059 : }
829 :
830 :
831 : /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
832 : template<typename T, typename A>
833 : inline void
834 337484842 : vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
835 : {
836 337484316 : if (v)
837 261124499 : v->truncate (size);
838 526 : }
839 :
840 :
841 : /* If SRC is not NULL, return a pointer to a copy of it. */
842 : template<typename T, typename A>
843 : inline vec<T, A, vl_embed> *
844 6578431 : vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
845 : {
846 6578431 : return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
847 : }
848 :
849 : /* Copy the elements from SRC to the end of DST as if by memcpy.
850 : Reallocate DST, if necessary. */
851 : template<typename T, typename A>
852 : inline void
853 16 : vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
854 : CXX_MEM_STAT_INFO)
855 : {
856 32 : unsigned src_len = vec_safe_length (src);
857 16 : if (src_len)
858 : {
859 32 : vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
860 : PASS_MEM_STAT);
861 16 : dst->splice (*src);
862 : }
863 16 : }
864 :
865 : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
866 : size of the vector and so should be used with care. */
867 :
868 : template<typename T, typename A>
869 : inline bool
870 : vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
871 : {
872 : return v ? v->contains (search) : false;
873 : }
874 :
875 : /* Index into vector. Return the IX'th element. IX must be in the
876 : domain of the vector. */
877 :
878 : template<typename T, typename A>
879 : inline const T &
880 235130857 : vec<T, A, vl_embed>::operator[] (unsigned ix) const
881 : {
882 235130857 : gcc_checking_assert (ix < m_vecpfx.m_num);
883 235130857 : return address ()[ix];
884 : }
885 :
886 : template<typename T, typename A>
887 : inline T &
888 78738896509 : vec<T, A, vl_embed>::operator[] (unsigned ix)
889 : {
890 78738896509 : gcc_checking_assert (ix < m_vecpfx.m_num);
891 78738896509 : return address ()[ix];
892 : }
893 :
894 :
895 : /* Get the final element of the vector, which must not be empty. */
896 :
897 : template<typename T, typename A>
898 : inline T &
899 12567057124 : vec<T, A, vl_embed>::last (void)
900 : {
901 12567057124 : gcc_checking_assert (m_vecpfx.m_num > 0);
902 12567057124 : return (*this)[m_vecpfx.m_num - 1];
903 : }
904 :
905 :
906 : /* If this vector has space for NELEMS additional entries, return
907 : true. You usually only need to use this if you are doing your
908 : own vector reallocation, for instance on an embedded vector. This
909 : returns true in exactly the same circumstances that vec::reserve
910 : will. */
911 :
912 : template<typename T, typename A>
913 : inline bool
914 76768113782 : vec<T, A, vl_embed>::space (unsigned nelems) const
915 : {
916 23818803589 : return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
917 : }
918 :
919 :
920 : /* Return iteration condition and update *PTR to (a copy of) the IX'th
921 : element of this vector. Use this to iterate over the elements of a
922 : vector as follows,
923 :
924 : for (ix = 0; v->iterate (ix, &val); ix++)
925 : continue; */
926 :
927 : template<typename T, typename A>
928 : inline bool
929 10882519848 : vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
930 : {
931 10367634751 : if (ix < m_vecpfx.m_num)
932 : {
933 4852887493 : *ptr = address ()[ix];
934 26424 : return true;
935 : }
936 : else
937 : {
938 1753515 : *ptr = 0;
939 13124 : return false;
940 : }
941 : }
942 :
943 :
944 : /* Return iteration condition and update *PTR to point to the
945 : IX'th element of this vector. Use this to iterate over the
946 : elements of a vector as follows,
947 :
948 : for (ix = 0; v->iterate (ix, &ptr); ix++)
949 : continue;
950 :
951 : This variant is for vectors of objects. */
952 :
953 : template<typename T, typename A>
954 : inline bool
955 2144969075 : vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
956 : {
957 2144962054 : if (ix < m_vecpfx.m_num)
958 : {
959 1623204124 : *ptr = CONST_CAST (T *, &address ()[ix]);
960 0 : return true;
961 : }
962 : else
963 : {
964 : *ptr = 0;
965 : return false;
966 : }
967 : }
968 :
969 :
970 : /* Return a pointer to a copy of this vector. */
971 :
972 : template<typename T, typename A>
973 : inline vec<T, A, vl_embed> *
974 1818837 : vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
975 : {
976 1818837 : vec<T, A, vl_embed> *new_vec = NULL;
977 1818837 : unsigned len = length ();
978 1818837 : if (len)
979 : {
980 1672748 : vec_alloc (new_vec, len PASS_MEM_STAT);
981 1672748 : new_vec->embedded_init (len, len);
982 3491585 : vec_copy_construct (new_vec->address (), address (), len);
983 : }
984 1818837 : return new_vec;
985 : }
986 :
987 :
988 : /* Copy the elements from SRC to the end of this vector as if by memcpy.
989 : The vector must have sufficient headroom available. */
990 :
991 : template<typename T, typename A>
992 : inline void
993 16 : vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
994 : {
995 16 : unsigned len = src.length ();
996 16 : if (len)
997 : {
998 16 : gcc_checking_assert (space (len));
999 16 : vec_copy_construct (end (), src.address (), len);
1000 16 : m_vecpfx.m_num += len;
1001 : }
1002 16 : }
1003 :
1004 : template<typename T, typename A>
1005 : inline void
1006 : vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
1007 : {
1008 : if (src)
1009 : splice (*src);
1010 : }
1011 :
1012 :
1013 : /* Push OBJ (a new element) onto the end of the vector. There must be
1014 : sufficient space in the vector. Return a pointer to the slot
1015 : where OBJ was inserted. */
1016 :
1017 : template<typename T, typename A>
1018 : inline T *
1019 38737198702 : vec<T, A, vl_embed>::quick_push (const T &obj)
1020 : {
1021 38737198702 : gcc_checking_assert (space (1));
1022 38737198702 : T *slot = &address ()[m_vecpfx.m_num++];
1023 38737198702 : *slot = obj;
1024 38737198702 : return slot;
1025 : }
1026 :
1027 :
1028 : /* Pop and return the last element off the end of the vector. */
1029 :
1030 : template<typename T, typename A>
1031 : inline T &
1032 30881568656 : vec<T, A, vl_embed>::pop (void)
1033 : {
1034 30881568656 : gcc_checking_assert (length () > 0);
1035 30881568656 : return address ()[--m_vecpfx.m_num];
1036 : }
1037 :
1038 :
1039 : /* Set the length of the vector to SIZE. The new length must be less
1040 : than or equal to the current length. This is an O(1) operation. */
1041 :
1042 : template<typename T, typename A>
1043 : inline void
1044 368273097 : vec<T, A, vl_embed>::truncate (unsigned size)
1045 : {
1046 368273097 : gcc_checking_assert (length () >= size);
1047 368273097 : m_vecpfx.m_num = size;
1048 368273097 : }
1049 :
1050 :
1051 : /* Insert an element, OBJ, at the IXth position of this vector. There
1052 : must be sufficient space. */
1053 :
1054 : template<typename T, typename A>
1055 : inline void
1056 14317178 : vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
1057 : {
1058 14317178 : gcc_checking_assert (length () < allocated ());
1059 14317178 : gcc_checking_assert (ix <= length ());
1060 14317178 : T *slot = &address ()[ix];
1061 14317178 : memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
1062 14317178 : *slot = obj;
1063 14317178 : }
1064 :
1065 :
1066 : /* Remove an element from the IXth position of this vector. Ordering of
1067 : remaining elements is preserved. This is an O(N) operation due to
1068 : memmove. */
1069 :
1070 : template<typename T, typename A>
1071 : inline void
1072 3751 : vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1073 : {
1074 3751 : gcc_checking_assert (ix < length ());
1075 3751 : T *slot = &address ()[ix];
1076 3751 : memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1077 3751 : }
1078 :
1079 :
1080 : /* Remove elements in [START, END) from VEC for which COND holds. Ordering of
1081 : remaining elements is preserved. This is an O(N) operation. */
1082 :
1083 : #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
1084 : elem_ptr, start, end, cond) \
1085 : { \
1086 : gcc_assert ((end) <= (vec).length ()); \
1087 : for (read_index = write_index = (start); read_index < (end); \
1088 : ++read_index) \
1089 : { \
1090 : elem_ptr = &(vec)[read_index]; \
1091 : bool remove_p = (cond); \
1092 : if (remove_p) \
1093 : continue; \
1094 : \
1095 : if (read_index != write_index) \
1096 : (vec)[write_index] = (vec)[read_index]; \
1097 : \
1098 : write_index++; \
1099 : } \
1100 : \
1101 : if (read_index - write_index > 0) \
1102 : (vec).block_remove (write_index, read_index - write_index); \
1103 : }
1104 :
1105 :
1106 : /* Remove elements from VEC for which COND holds. Ordering of remaining
1107 : elements is preserved. This is an O(N) operation. */
1108 :
1109 : #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
1110 : cond) \
1111 : VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \
1112 : elem_ptr, 0, (vec).length (), (cond))
1113 :
1114 : /* Remove an element from the IXth position of this vector. Ordering of
1115 : remaining elements is destroyed. This is an O(1) operation. */
1116 :
1117 : template<typename T, typename A>
1118 : inline void
1119 434313 : vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1120 : {
1121 434313 : gcc_checking_assert (ix < length ());
1122 434313 : T *p = address ();
1123 434313 : p[ix] = p[--m_vecpfx.m_num];
1124 434313 : }
1125 :
1126 :
1127 : /* Remove LEN elements starting at the IXth. Ordering is retained.
1128 : This is an O(N) operation due to memmove. */
1129 :
1130 : template<typename T, typename A>
1131 : inline void
1132 1 : vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1133 : {
1134 1 : gcc_checking_assert (ix + len <= length ());
1135 1 : T *slot = &address ()[ix];
1136 1 : m_vecpfx.m_num -= len;
1137 1 : memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1138 1 : }
1139 :
1140 :
1141 : /* Sort the contents of this vector with qsort. CMP is the comparison
1142 : function to pass to qsort. */
1143 :
1144 : template<typename T, typename A>
1145 : inline void
1146 14564625 : vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1147 : {
1148 14564625 : if (length () > 1)
1149 12945239 : gcc_qsort (address (), length (), sizeof (T), cmp);
1150 14564625 : }
1151 :
1152 : /* Sort the contents of this vector with qsort. CMP is the comparison
1153 : function to pass to qsort. */
1154 :
1155 : template<typename T, typename A>
1156 : inline void
1157 : vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
1158 : void *data)
1159 : {
1160 : if (length () > 1)
1161 : gcc_sort_r (address (), length (), sizeof (T), cmp, data);
1162 : }
1163 :
1164 : /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
1165 : comparison function to pass to qsort. */
1166 :
1167 : template<typename T, typename A>
1168 : inline void
1169 : vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
1170 : void *), void *data)
1171 : {
1172 : if (length () > 1)
1173 : gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
1174 : }
1175 :
1176 : /* Search the contents of the sorted vector with a binary search.
1177 : CMP is the comparison function to pass to bsearch. */
1178 :
1179 : template<typename T, typename A>
1180 : inline T *
1181 : vec<T, A, vl_embed>::bsearch (const void *key,
1182 : int (*compar) (const void *, const void *))
1183 : {
1184 : const void *base = this->address ();
1185 : size_t nmemb = this->length ();
1186 : size_t size = sizeof (T);
1187 : /* The following is a copy of glibc stdlib-bsearch.h. */
1188 : size_t l, u, idx;
1189 : const void *p;
1190 : int comparison;
1191 :
1192 : l = 0;
1193 : u = nmemb;
1194 : while (l < u)
1195 : {
1196 : idx = (l + u) / 2;
1197 : p = (const void *) (((const char *) base) + (idx * size));
1198 : comparison = (*compar) (key, p);
1199 : if (comparison < 0)
1200 : u = idx;
1201 : else if (comparison > 0)
1202 : l = idx + 1;
1203 : else
1204 : return (T *)const_cast<void *>(p);
1205 : }
1206 :
1207 : return NULL;
1208 : }
1209 :
1210 : /* Search the contents of the sorted vector with a binary search.
1211 : CMP is the comparison function to pass to bsearch. */
1212 :
1213 : template<typename T, typename A>
1214 : inline T *
1215 : vec<T, A, vl_embed>::bsearch (const void *key,
1216 : int (*compar) (const void *, const void *,
1217 : void *), void *data)
1218 : {
1219 : const void *base = this->address ();
1220 : size_t nmemb = this->length ();
1221 : size_t size = sizeof (T);
1222 : /* The following is a copy of glibc stdlib-bsearch.h. */
1223 : size_t l, u, idx;
1224 : const void *p;
1225 : int comparison;
1226 :
1227 : l = 0;
1228 : u = nmemb;
1229 : while (l < u)
1230 : {
1231 : idx = (l + u) / 2;
1232 : p = (const void *) (((const char *) base) + (idx * size));
1233 : comparison = (*compar) (key, p, data);
1234 : if (comparison < 0)
1235 : u = idx;
1236 : else if (comparison > 0)
1237 : l = idx + 1;
1238 : else
1239 : return (T *)const_cast<void *>(p);
1240 : }
1241 :
1242 : return NULL;
1243 : }
1244 :
1245 : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1246 : size of the vector and so should be used with care. */
1247 :
1248 : template<typename T, typename A>
1249 : inline bool
1250 : vec<T, A, vl_embed>::contains (const T &search) const
1251 : {
1252 : unsigned int len = length ();
1253 : const T *p = address ();
1254 : for (unsigned int i = 0; i < len; i++)
1255 : {
1256 : const T *slot = &p[i];
1257 : if (*slot == search)
1258 : return true;
1259 : }
1260 :
1261 : return false;
1262 : }
1263 :
1264 : /* Find and return the first position in which OBJ could be inserted
1265 : without changing the ordering of this vector. LESSTHAN is a
1266 : function that returns true if the first argument is strictly less
1267 : than the second. */
1268 :
1269 : template<typename T, typename A>
1270 : unsigned
1271 : vec<T, A, vl_embed>::lower_bound (const T &obj,
1272 : bool (*lessthan)(const T &, const T &))
1273 : const
1274 : {
1275 : unsigned int len = length ();
1276 : unsigned int half, middle;
1277 : unsigned int first = 0;
1278 : while (len > 0)
1279 : {
1280 : half = len / 2;
1281 : middle = first;
1282 : middle += half;
1283 : const T &middle_elem = address ()[middle];
1284 : if (lessthan (middle_elem, obj))
1285 : {
1286 : first = middle;
1287 : ++first;
1288 : len = len - half - 1;
1289 : }
1290 : else
1291 : len = half;
1292 : }
1293 : return first;
1294 : }
1295 :
1296 :
1297 : /* Return the number of bytes needed to embed an instance of an
1298 : embeddable vec inside another data structure.
1299 :
1300 : Use these methods to determine the required size and initialization
1301 : of a vector V of type T embedded within another structure (as the
1302 : final member):
1303 :
1304 : size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1305 : void v->embedded_init (unsigned alloc, unsigned num);
1306 :
1307 : These allow the caller to perform the memory allocation. */
1308 :
1309 : template<typename T, typename A>
1310 : inline size_t
1311 564532833 : vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1312 : {
1313 : struct alignas (T) U { char data[sizeof (T)]; };
1314 : typedef vec<U, A, vl_embed> vec_embedded;
1315 : typedef typename std::conditional<std::is_standard_layout<T>::value,
1316 : vec, vec_embedded>::type vec_stdlayout;
1317 : static_assert (sizeof (vec_stdlayout) == sizeof (vec), "");
1318 : static_assert (alignof (vec_stdlayout) == alignof (vec), "");
1319 564532833 : return sizeof (vec_stdlayout) + alloc * sizeof (T);
1320 : }
1321 :
1322 :
1323 : /* Initialize the vector to contain room for ALLOC elements and
1324 : NUM active elements. */
1325 :
1326 : template<typename T, typename A>
1327 : inline void
1328 1948403651 : vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1329 : {
1330 1948403651 : m_vecpfx.m_alloc = alloc;
1331 1948403651 : m_vecpfx.m_using_auto_storage = aut;
1332 1225921088 : m_vecpfx.m_num = num;
1333 473335672 : }
1334 :
1335 :
1336 : /* Grow the vector to a specific length. LEN must be as long or longer than
1337 : the current length. The new elements are uninitialized. */
1338 :
1339 : template<typename T, typename A>
1340 : inline void
1341 15365057 : vec<T, A, vl_embed>::quick_grow (unsigned len)
1342 : {
1343 15365057 : gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1344 15365057 : m_vecpfx.m_num = len;
1345 15365057 : }
1346 :
1347 :
1348 : /* Grow the vector to a specific length. LEN must be as long or longer than
1349 : the current length. The new elements are initialized to zero. */
1350 :
1351 : template<typename T, typename A>
1352 : inline void
1353 585679 : vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1354 : {
1355 585679 : unsigned oldlen = length ();
1356 585679 : size_t growby = len - oldlen;
1357 585679 : quick_grow (len);
1358 585679 : if (growby != 0)
1359 585679 : vec_default_construct (address () + oldlen, growby);
1360 585679 : }
1361 :
1362 : /* Garbage collection support for vec<T, A, vl_embed>. */
1363 :
1364 : template<typename T>
1365 : void
1366 537930235 : gt_ggc_mx (vec<T, va_gc> *v)
1367 : {
1368 : extern void gt_ggc_mx (T &);
1369 43246333882 : for (unsigned i = 0; i < v->length (); i++)
1370 42712369788 : gt_ggc_mx ((*v)[i]);
1371 537930235 : }
1372 :
1373 : template<typename T>
1374 : void
1375 : gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1376 : {
1377 : /* Nothing to do. Vectors of atomic types wrt GC do not need to
1378 : be traversed. */
1379 : }
1380 :
1381 :
1382 : /* PCH support for vec<T, A, vl_embed>. */
1383 :
1384 : template<typename T, typename A>
1385 : void
1386 213524 : gt_pch_nx (vec<T, A, vl_embed> *v)
1387 : {
1388 : extern void gt_pch_nx (T &);
1389 552022 : for (unsigned i = 0; i < v->length (); i++)
1390 338498 : gt_pch_nx ((*v)[i]);
1391 213524 : }
1392 :
1393 : template<typename T>
1394 : void
1395 : gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *)
1396 : {
1397 : /* No pointers to note. */
1398 : }
1399 :
1400 : template<typename T, typename A>
1401 : void
1402 66967 : gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1403 : {
1404 92547 : for (unsigned i = 0; i < v->length (); i++)
1405 25580 : op (&((*v)[i]), NULL, cookie);
1406 66967 : }
1407 :
1408 : template<typename T, typename A>
1409 : void
1410 1655 : gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1411 : {
1412 : extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1413 8947 : for (unsigned i = 0; i < v->length (); i++)
1414 7292 : gt_pch_nx (&((*v)[i]), op, cookie);
1415 1655 : }
1416 :
1417 : template<typename T>
1418 : void
1419 : gt_pch_nx (vec<T, va_gc_atomic, vl_embed> *, gt_pointer_operator, void *)
1420 : {
1421 : /* No pointers to note. */
1422 : }
1423 :
1424 :
1425 : /* Space efficient vector. These vectors can grow dynamically and are
1426 : allocated together with their control data. They are suited to be
1427 : included in data structures. Prior to initial allocation, they
1428 : only take a single word of storage.
1429 :
1430 : These vectors are implemented as a pointer to an embeddable vector.
1431 : The semantics allow for this pointer to be NULL to represent empty
1432 : vectors. This way, empty vectors occupy minimal space in the
1433 : structure containing them.
1434 :
1435 : Properties:
1436 :
1437 : - The whole vector and control data are allocated in a single
1438 : contiguous block.
1439 : - The whole vector may be re-allocated.
1440 : - Vector data may grow and shrink.
1441 : - Access and manipulation requires a pointer test and
1442 : indirection.
1443 : - It requires 1 word of storage (prior to vector allocation).
1444 :
1445 :
1446 : Limitations:
1447 :
1448 : These vectors must be PODs because they are stored in unions.
1449 : (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1450 : As long as we use C++03, we cannot have constructors nor
1451 : destructors in classes that are stored in unions. */
1452 :
1453 : template<typename T, size_t N = 0>
1454 : class auto_vec;
1455 :
1456 : template<typename T>
1457 : struct vec<T, va_heap, vl_ptr>
1458 : {
1459 : public:
1460 : /* Default ctors to ensure triviality. Use value-initialization
1461 : (e.g., vec() or vec v{ };) or vNULL to create a zero-initialized
1462 : instance. */
1463 : vec () = default;
1464 : vec (const vec &) = default;
1465 : /* Initialization from the generic vNULL. */
1466 7060290 : vec (vnull): m_vec () { }
1467 : /* Same as default ctor: vec storage must be released manually. */
1468 : ~vec () = default;
1469 :
1470 : /* Defaulted same as copy ctor. */
1471 : vec& operator= (const vec &) = default;
1472 :
1473 : /* Prevent implicit conversion from auto_vec. Use auto_vec::to_vec()
1474 : instead. */
1475 : template <size_t N>
1476 : vec (auto_vec<T, N> &) = delete;
1477 :
1478 : template <size_t N>
1479 : void operator= (auto_vec<T, N> &) = delete;
1480 :
1481 : /* Memory allocation and deallocation for the embedded vector.
1482 : Needed because we cannot have proper ctors/dtors defined. */
1483 : void create (unsigned nelems CXX_MEM_STAT_INFO);
1484 : void release (void);
1485 :
1486 : /* Vector operations. */
1487 3938 : bool exists (void) const
1488 3938 : { return m_vec != NULL; }
1489 :
1490 896418760 : bool is_empty (void) const
1491 894635748 : { return m_vec ? m_vec->is_empty () : true; }
1492 :
1493 : unsigned allocated (void) const
1494 : { return m_vec ? m_vec->allocated () : 0; }
1495 :
1496 5265664786 : unsigned length (void) const
1497 5340572612 : { return m_vec ? m_vec->length () : 0; }
1498 :
1499 281026934 : T *address (void)
1500 20915055 : { return m_vec ? m_vec->address () : NULL; }
1501 :
1502 1880 : const T *address (void) const
1503 0 : { return m_vec ? m_vec->address () : NULL; }
1504 :
1505 159133896 : T *begin () { return address (); }
1506 : const T *begin () const { return address (); }
1507 129019780 : T *end () { return begin () + length (); }
1508 : const T *end () const { return begin () + length (); }
1509 2018 : const T &operator[] (unsigned ix) const
1510 2018 : { return (*m_vec)[ix]; }
1511 :
1512 : bool operator!=(const vec &other) const
1513 : { return !(*this == other); }
1514 :
1515 1880 : bool operator==(const vec &other) const
1516 1880 : { return address () == other.address (); }
1517 :
1518 1477370485 : T &operator[] (unsigned ix)
1519 1477056721 : { return (*m_vec)[ix]; }
1520 :
1521 4362 : T &last (void)
1522 4362 : { return m_vec->last (); }
1523 :
1524 14285562065 : bool space (int nelems) const
1525 14285562065 : { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1526 :
1527 : bool iterate (unsigned ix, T *p) const;
1528 : bool iterate (unsigned ix, T **p) const;
1529 : vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1530 : bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1531 : bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1532 : void splice (const vec &);
1533 : void safe_splice (const vec & CXX_MEM_STAT_INFO);
1534 : T *quick_push (const T &);
1535 : T *safe_push (const T &CXX_MEM_STAT_INFO);
1536 : T &pop (void);
1537 : void truncate (unsigned);
1538 : void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
1539 : void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
1540 : void quick_grow (unsigned);
1541 : void quick_grow_cleared (unsigned);
1542 : void quick_insert (unsigned, const T &);
1543 : void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1544 : void ordered_remove (unsigned);
1545 : void unordered_remove (unsigned);
1546 : void block_remove (unsigned, unsigned);
1547 : void qsort (int (*) (const void *, const void *));
1548 : void sort (int (*) (const void *, const void *, void *), void *);
1549 : void stablesort (int (*) (const void *, const void *, void *), void *);
1550 : T *bsearch (const void *key, int (*compar)(const void *, const void *));
1551 : T *bsearch (const void *key,
1552 : int (*compar)(const void *, const void *, void *), void *);
1553 : unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1554 : bool contains (const T &search) const;
1555 : void reverse (void);
1556 :
1557 : bool using_auto_storage () const;
1558 :
1559 : /* FIXME - This field should be private, but we need to cater to
1560 : compilers that have stricter notions of PODness for types. */
1561 : vec<T, va_heap, vl_embed> *m_vec;
1562 : };
1563 :
1564 :
1565 : /* auto_vec is a subclass of vec that automatically manages creating and
1566 : releasing the internal vector. If N is non zero then it has N elements of
1567 : internal storage. The default is no internal storage, and you probably only
1568 : want to ask for internal storage for vectors on the stack because if the
1569 : size of the vector is larger than the internal storage that space is wasted.
1570 : */
1571 : template<typename T, size_t N /* = 0 */>
1572 : class auto_vec : public vec<T, va_heap>
1573 : {
1574 : public:
1575 1382195712 : auto_vec ()
1576 : {
1577 1382195712 : m_auto.embedded_init (N, 0, 1);
1578 : /* ??? Instead of initializing m_vec from &m_auto directly use an
1579 : expression that avoids refering to a specific member of 'this'
1580 : to derail the -Wstringop-overflow diagnostic code, avoiding
1581 : the impression that data accesses are supposed to be to the
1582 : m_auto member storage. */
1583 1382195712 : size_t off = (char *) &m_auto - (char *) this;
1584 1005327869 : this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1585 127040404 : }
1586 :
1587 2358 : auto_vec (size_t s CXX_MEM_STAT_INFO)
1588 : {
1589 2358 : if (s > N)
1590 : {
1591 0 : this->create (s PASS_MEM_STAT);
1592 0 : return;
1593 : }
1594 :
1595 2358 : m_auto.embedded_init (N, 0, 1);
1596 : /* ??? See above. */
1597 2358 : size_t off = (char *) &m_auto - (char *) this;
1598 2358 : this->m_vec = (vec<T, va_heap, vl_embed> *) ((char *) this + off);
1599 : }
1600 :
1601 1382304975 : ~auto_vec ()
1602 : {
1603 1382176502 : this->release ();
1604 1253080517 : }
1605 :
1606 : /* Explicitly convert to the base class. There is no conversion
1607 : from a const auto_vec because a copy of the returned vec can
1608 : be used to modify *THIS.
1609 : This is a legacy function not to be used in new code. */
1610 : vec<T, va_heap> to_vec_legacy () {
1611 : return *static_cast<vec<T, va_heap> *>(this);
1612 : }
1613 :
1614 : private:
1615 : vec<T, va_heap, vl_embed> m_auto;
1616 : unsigned char m_data[sizeof (T) * N];
1617 : };
1618 :
1619 : /* auto_vec is a sub class of vec whose storage is released when it is
1620 : destroyed. */
1621 : template<typename T>
1622 : class auto_vec<T, 0> : public vec<T, va_heap>
1623 : {
1624 : public:
1625 452572260 : auto_vec () { this->m_vec = NULL; }
1626 585679 : auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); }
1627 453213394 : ~auto_vec () { this->release (); }
1628 :
1629 : auto_vec (vec<T, va_heap>&& r)
1630 : {
1631 : gcc_assert (!r.using_auto_storage ());
1632 : this->m_vec = r.m_vec;
1633 : r.m_vec = NULL;
1634 : }
1635 :
1636 59138 : auto_vec (auto_vec<T> &&r)
1637 : {
1638 0 : gcc_assert (!r.using_auto_storage ());
1639 59138 : this->m_vec = r.m_vec;
1640 59138 : r.m_vec = NULL;
1641 59138 : }
1642 :
1643 : auto_vec& operator= (vec<T, va_heap>&& r)
1644 : {
1645 : if (this == &r)
1646 : return *this;
1647 :
1648 : gcc_assert (!r.using_auto_storage ());
1649 : this->release ();
1650 : this->m_vec = r.m_vec;
1651 : r.m_vec = NULL;
1652 : return *this;
1653 : }
1654 :
1655 : auto_vec& operator= (auto_vec<T> &&r)
1656 : {
1657 : if (this == &r)
1658 : return *this;
1659 :
1660 : gcc_assert (!r.using_auto_storage ());
1661 : this->release ();
1662 : this->m_vec = r.m_vec;
1663 : r.m_vec = NULL;
1664 : return *this;
1665 : }
1666 :
1667 : /* Explicitly convert to the base class. There is no conversion
1668 : from a const auto_vec because a copy of the returned vec can
1669 : be used to modify *THIS.
1670 : This is a legacy function not to be used in new code. */
1671 : vec<T, va_heap> to_vec_legacy () {
1672 : return *static_cast<vec<T, va_heap> *>(this);
1673 : }
1674 :
1675 : // You probably don't want to copy a vector, so these are deleted to prevent
1676 : // unintentional use. If you really need a copy of the vectors contents you
1677 : // can use copy ().
1678 : auto_vec(const auto_vec &) = delete;
1679 : auto_vec &operator= (const auto_vec &) = delete;
1680 : };
1681 :
1682 :
1683 : /* Allocate heap memory for pointer V and create the internal vector
1684 : with space for NELEMS elements. If NELEMS is 0, the internal
1685 : vector is initialized to empty. */
1686 :
1687 : template<typename T>
1688 : inline void
1689 107621 : vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1690 : {
1691 107621 : v = new vec<T>;
1692 107621 : v->create (nelems PASS_MEM_STAT);
1693 107621 : }
1694 :
1695 :
1696 : /* A subclass of auto_vec <char *> that frees all of its elements on
1697 : deletion. */
1698 :
1699 : class auto_string_vec : public auto_vec <char *>
1700 : {
1701 : public:
1702 : ~auto_string_vec ();
1703 : };
1704 :
1705 : /* A subclass of auto_vec <T *> that deletes all of its elements on
1706 : destruction.
1707 :
1708 : This is a crude way for a vec to "own" the objects it points to
1709 : and clean up automatically.
1710 :
1711 : For example, no attempt is made to delete elements when an item
1712 : within the vec is overwritten.
1713 :
1714 : We can't rely on gnu::unique_ptr within a container,
1715 : since we can't rely on move semantics in C++98. */
1716 :
1717 : template <typename T>
1718 : class auto_delete_vec : public auto_vec <T *>
1719 : {
1720 : public:
1721 0 : auto_delete_vec () {}
1722 : auto_delete_vec (size_t s) : auto_vec <T *> (s) {}
1723 :
1724 : ~auto_delete_vec ();
1725 :
1726 : private:
1727 : DISABLE_COPY_AND_ASSIGN(auto_delete_vec);
1728 : };
1729 :
1730 : /* Conditionally allocate heap memory for VEC and its internal vector. */
1731 :
1732 : template<typename T>
1733 : inline void
1734 : vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1735 : {
1736 : if (!vec)
1737 : vec_alloc (vec, nelems PASS_MEM_STAT);
1738 : }
1739 :
1740 :
1741 : /* Free the heap memory allocated by vector V and set it to NULL. */
1742 :
1743 : template<typename T>
1744 : inline void
1745 204166 : vec_free (vec<T> *&v)
1746 : {
1747 204166 : if (v == NULL)
1748 : return;
1749 :
1750 107689 : v->release ();
1751 107689 : delete v;
1752 107689 : v = NULL;
1753 : }
1754 :
1755 :
1756 : /* Return iteration condition and update PTR to point to the IX'th
1757 : element of this vector. Use this to iterate over the elements of a
1758 : vector as follows,
1759 :
1760 : for (ix = 0; v.iterate (ix, &ptr); ix++)
1761 : continue; */
1762 :
1763 : template<typename T>
1764 : inline bool
1765 772135388 : vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1766 : {
1767 772133738 : if (m_vec)
1768 1030035023 : return m_vec->iterate (ix, ptr);
1769 : else
1770 : {
1771 0 : *ptr = 0;
1772 0 : return false;
1773 : }
1774 : }
1775 :
1776 :
1777 : /* Return iteration condition and update *PTR to point to the
1778 : IX'th element of this vector. Use this to iterate over the
1779 : elements of a vector as follows,
1780 :
1781 : for (ix = 0; v->iterate (ix, &ptr); ix++)
1782 : continue;
1783 :
1784 : This variant is for vectors of objects. */
1785 :
1786 : template<typename T>
1787 : inline bool
1788 7021 : vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1789 : {
1790 7021 : if (m_vec)
1791 7021 : return m_vec->iterate (ix, ptr);
1792 : else
1793 : {
1794 : *ptr = 0;
1795 : return false;
1796 : }
1797 : }
1798 :
1799 :
1800 : /* Convenience macro for forward iteration. */
1801 : #define FOR_EACH_VEC_ELT(V, I, P) \
1802 : for (I = 0; (V).iterate ((I), &(P)); ++(I))
1803 :
1804 : #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1805 : for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1806 :
1807 : /* Likewise, but start from FROM rather than 0. */
1808 : #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1809 : for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1810 :
1811 : /* Convenience macro for reverse iteration. */
1812 : #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1813 : for (I = (V).length () - 1; \
1814 : (V).iterate ((I), &(P)); \
1815 : (I)--)
1816 :
1817 : #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1818 : for (I = vec_safe_length (V) - 1; \
1819 : vec_safe_iterate ((V), (I), &(P)); \
1820 : (I)--)
1821 :
1822 : /* auto_string_vec's dtor, freeing all contained strings, automatically
1823 : chaining up to ~auto_vec <char *>, which frees the internal buffer. */
1824 :
1825 : inline
1826 : auto_string_vec::~auto_string_vec ()
1827 : {
1828 : int i;
1829 : char *str;
1830 : FOR_EACH_VEC_ELT (*this, i, str)
1831 : free (str);
1832 : }
1833 :
1834 : /* auto_delete_vec's dtor, deleting all contained items, automatically
1835 : chaining up to ~auto_vec <T*>, which frees the internal buffer. */
1836 :
1837 : template <typename T>
1838 : inline
1839 0 : auto_delete_vec<T>::~auto_delete_vec ()
1840 : {
1841 : int i;
1842 : T *item;
1843 0 : FOR_EACH_VEC_ELT (*this, i, item)
1844 0 : delete item;
1845 0 : }
1846 :
1847 :
1848 : /* Return a copy of this vector. */
1849 :
1850 : template<typename T>
1851 : inline vec<T, va_heap, vl_ptr>
1852 1410 : vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1853 : {
1854 1410 : vec<T, va_heap, vl_ptr> new_vec{ };
1855 1410 : if (length ())
1856 1410 : new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT);
1857 1410 : return new_vec;
1858 : }
1859 :
1860 :
1861 : /* Ensure that the vector has at least RESERVE slots available (if
1862 : EXACT is false), or exactly RESERVE slots available (if EXACT is
1863 : true).
1864 :
1865 : This may create additional headroom if EXACT is false.
1866 :
1867 : Note that this can cause the embedded vector to be reallocated.
1868 : Returns true iff reallocation actually occurred. */
1869 :
1870 : template<typename T>
1871 : inline bool
1872 14285562065 : vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1873 : {
1874 28571124130 : if (space (nelems))
1875 : return false;
1876 :
1877 : /* For now play a game with va_heap::reserve to hide our auto storage if any,
1878 : this is necessary because it doesn't have enough information to know the
1879 : embedded vector is in auto storage, and so should not be freed. */
1880 90978545 : vec<T, va_heap, vl_embed> *oldvec = m_vec;
1881 90978545 : unsigned int oldsize = 0;
1882 90978545 : bool handle_auto_vec = m_vec && using_auto_storage ();
1883 : if (handle_auto_vec)
1884 : {
1885 210749 : m_vec = NULL;
1886 210749 : oldsize = oldvec->length ();
1887 210749 : nelems += oldsize;
1888 : }
1889 :
1890 90978545 : va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1891 90978545 : if (handle_auto_vec)
1892 : {
1893 210749 : vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1894 210749 : m_vec->m_vecpfx.m_num = oldsize;
1895 : }
1896 :
1897 : return true;
1898 : }
1899 :
1900 :
1901 : /* Ensure that this vector has exactly NELEMS slots available. This
1902 : will not create additional headroom. Note this can cause the
1903 : embedded vector to be reallocated. Returns true iff reallocation
1904 : actually occurred. */
1905 :
1906 : template<typename T>
1907 : inline bool
1908 56713586 : vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1909 : {
1910 56073198 : return reserve (nelems, true PASS_MEM_STAT);
1911 : }
1912 :
1913 :
1914 : /* Create the internal vector and reserve NELEMS for it. This is
1915 : exactly like vec::reserve, but the internal vector is
1916 : unconditionally allocated from scratch. The old one, if it
1917 : existed, is lost. */
1918 :
1919 : template<typename T>
1920 : inline void
1921 36179629 : vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1922 : {
1923 77152119 : m_vec = NULL;
1924 1912150 : if (nelems > 0)
1925 56088857 : reserve_exact (nelems PASS_MEM_STAT);
1926 1912150 : }
1927 :
1928 :
1929 : /* Free the memory occupied by the embedded vector. */
1930 :
1931 : template<typename T>
1932 : inline void
1933 1898922986 : vec<T, va_heap, vl_ptr>::release (void)
1934 : {
1935 1898922986 : if (!m_vec)
1936 : return;
1937 :
1938 1451717484 : if (using_auto_storage ())
1939 : {
1940 1382094226 : m_vec->m_vecpfx.m_num = 0;
1941 1382094226 : return;
1942 : }
1943 :
1944 69623258 : va_heap::release (m_vec);
1945 : }
1946 :
1947 : /* Copy the elements from SRC to the end of this vector as if by memcpy.
1948 : SRC and this vector must be allocated with the same memory
1949 : allocation mechanism. This vector is assumed to have sufficient
1950 : headroom available. */
1951 :
1952 : template<typename T>
1953 : inline void
1954 : vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1955 : {
1956 : if (src.length ())
1957 : m_vec->splice (*(src.m_vec));
1958 : }
1959 :
1960 :
1961 : /* Copy the elements in SRC to the end of this vector as if by memcpy.
1962 : SRC and this vector must be allocated with the same mechanism.
1963 : If there is not enough headroom in this vector, it will be reallocated
1964 : as needed. */
1965 :
1966 : template<typename T>
1967 : inline void
1968 : vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1969 : MEM_STAT_DECL)
1970 : {
1971 : if (src.length ())
1972 : {
1973 : reserve_exact (src.length ());
1974 : splice (src);
1975 : }
1976 : }
1977 :
1978 :
1979 : /* Push OBJ (a new element) onto the end of the vector. There must be
1980 : sufficient space in the vector. Return a pointer to the slot
1981 : where OBJ was inserted. */
1982 :
1983 : template<typename T>
1984 : inline T *
1985 14226808876 : vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1986 : {
1987 4499379334 : return m_vec->quick_push (obj);
1988 : }
1989 :
1990 :
1991 : /* Push a new element OBJ onto the end of this vector. Reallocates
1992 : the embedded vector, if needed. Return a pointer to the slot where
1993 : OBJ was inserted. */
1994 :
1995 : template<typename T>
1996 : inline T *
1997 14216231724 : vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1998 : {
1999 14216231724 : reserve (1, false PASS_MEM_STAT);
2000 14216231724 : return quick_push (obj);
2001 : }
2002 :
2003 :
2004 : /* Pop and return the last element off the end of the vector. */
2005 :
2006 : template<typename T>
2007 : inline T &
2008 13552731626 : vec<T, va_heap, vl_ptr>::pop (void)
2009 : {
2010 13552731626 : return m_vec->pop ();
2011 : }
2012 :
2013 :
2014 : /* Set the length of the vector to LEN. The new length must be less
2015 : than or equal to the current length. This is an O(1) operation. */
2016 :
2017 : template<typename T>
2018 : inline void
2019 107092558 : vec<T, va_heap, vl_ptr>::truncate (unsigned size)
2020 : {
2021 107092558 : if (m_vec)
2022 107070698 : m_vec->truncate (size);
2023 : else
2024 21860 : gcc_checking_assert (size == 0);
2025 107092558 : }
2026 :
2027 :
2028 : /* Grow the vector to a specific length. LEN must be as long or
2029 : longer than the current length. The new elements are
2030 : uninitialized. Reallocate the internal vector, if needed. */
2031 :
2032 : template<typename T>
2033 : inline void
2034 12613809 : vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL)
2035 : {
2036 20700668 : unsigned oldlen = length ();
2037 8086859 : gcc_checking_assert (oldlen <= len);
2038 12613809 : reserve (len - oldlen, exact PASS_MEM_STAT);
2039 12613809 : if (m_vec)
2040 12613809 : m_vec->quick_grow (len);
2041 : else
2042 0 : gcc_checking_assert (len == 0);
2043 12613809 : }
2044 :
2045 :
2046 : /* Grow the embedded vector to a specific length. LEN must be as
2047 : long or longer than the current length. The new elements are
2048 : initialized to zero. Reallocate the internal vector, if needed. */
2049 :
2050 : template<typename T>
2051 : inline void
2052 6894120 : vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
2053 : MEM_STAT_DECL)
2054 : {
2055 6894120 : unsigned oldlen = length ();
2056 6894120 : size_t growby = len - oldlen;
2057 6894120 : safe_grow (len, exact PASS_MEM_STAT);
2058 6894120 : if (growby != 0)
2059 13788200 : vec_default_construct (address () + oldlen, growby);
2060 6894120 : }
2061 :
2062 :
2063 : /* Same as vec::safe_grow but without reallocation of the internal vector.
2064 : If the vector cannot be extended, a runtime assertion will be triggered. */
2065 :
2066 : template<typename T>
2067 : inline void
2068 : vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
2069 : {
2070 : gcc_checking_assert (m_vec);
2071 : m_vec->quick_grow (len);
2072 : }
2073 :
2074 :
2075 : /* Same as vec::quick_grow_cleared but without reallocation of the
2076 : internal vector. If the vector cannot be extended, a runtime
2077 : assertion will be triggered. */
2078 :
2079 : template<typename T>
2080 : inline void
2081 585679 : vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
2082 : {
2083 585679 : gcc_checking_assert (m_vec);
2084 585679 : m_vec->quick_grow_cleared (len);
2085 585679 : }
2086 :
2087 :
2088 : /* Insert an element, OBJ, at the IXth position of this vector. There
2089 : must be sufficient space. */
2090 :
2091 : template<typename T>
2092 : inline void
2093 : vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
2094 : {
2095 : m_vec->quick_insert (ix, obj);
2096 : }
2097 :
2098 :
2099 : /* Insert an element, OBJ, at the IXth position of the vector.
2100 : Reallocate the embedded vector, if necessary. */
2101 :
2102 : template<typename T>
2103 : inline void
2104 : vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
2105 : {
2106 : reserve (1, false PASS_MEM_STAT);
2107 : quick_insert (ix, obj);
2108 : }
2109 :
2110 :
2111 : /* Remove an element from the IXth position of this vector. Ordering of
2112 : remaining elements is preserved. This is an O(N) operation due to
2113 : a memmove. */
2114 :
2115 : template<typename T>
2116 : inline void
2117 : vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
2118 : {
2119 : m_vec->ordered_remove (ix);
2120 : }
2121 :
2122 :
2123 : /* Remove an element from the IXth position of this vector. Ordering
2124 : of remaining elements is destroyed. This is an O(1) operation. */
2125 :
2126 : template<typename T>
2127 : inline void
2128 54 : vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
2129 : {
2130 54 : m_vec->unordered_remove (ix);
2131 54 : }
2132 :
2133 :
2134 : /* Remove LEN elements starting at the IXth. Ordering is retained.
2135 : This is an O(N) operation due to memmove. */
2136 :
2137 : template<typename T>
2138 : inline void
2139 : vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
2140 : {
2141 : m_vec->block_remove (ix, len);
2142 : }
2143 :
2144 :
2145 : /* Sort the contents of this vector with qsort. CMP is the comparison
2146 : function to pass to qsort. */
2147 :
2148 : template<typename T>
2149 : inline void
2150 292791194 : vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
2151 : {
2152 292791194 : if (m_vec)
2153 318002 : m_vec->qsort (cmp);
2154 : }
2155 :
2156 : /* Sort the contents of this vector with qsort. CMP is the comparison
2157 : function to pass to qsort. */
2158 :
2159 : template<typename T>
2160 : inline void
2161 : vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
2162 : void *), void *data)
2163 : {
2164 : if (m_vec)
2165 : m_vec->sort (cmp, data);
2166 : }
2167 :
2168 : /* Sort the contents of this vector with gcc_stablesort_r. CMP is the
2169 : comparison function to pass to qsort. */
2170 :
2171 : template<typename T>
2172 : inline void
2173 : vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *,
2174 : void *), void *data)
2175 : {
2176 : if (m_vec)
2177 : m_vec->stablesort (cmp, data);
2178 : }
2179 :
2180 : /* Search the contents of the sorted vector with a binary search.
2181 : CMP is the comparison function to pass to bsearch. */
2182 :
2183 : template<typename T>
2184 : inline T *
2185 : vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2186 : int (*cmp) (const void *, const void *))
2187 : {
2188 : if (m_vec)
2189 : return m_vec->bsearch (key, cmp);
2190 : return NULL;
2191 : }
2192 :
2193 : /* Search the contents of the sorted vector with a binary search.
2194 : CMP is the comparison function to pass to bsearch. */
2195 :
2196 : template<typename T>
2197 : inline T *
2198 : vec<T, va_heap, vl_ptr>::bsearch (const void *key,
2199 : int (*cmp) (const void *, const void *,
2200 : void *), void *data)
2201 : {
2202 : if (m_vec)
2203 : return m_vec->bsearch (key, cmp, data);
2204 : return NULL;
2205 : }
2206 :
2207 :
2208 : /* Find and return the first position in which OBJ could be inserted
2209 : without changing the ordering of this vector. LESSTHAN is a
2210 : function that returns true if the first argument is strictly less
2211 : than the second. */
2212 :
2213 : template<typename T>
2214 : inline unsigned
2215 : vec<T, va_heap, vl_ptr>::lower_bound (T obj,
2216 : bool (*lessthan)(const T &, const T &))
2217 : const
2218 : {
2219 : return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
2220 : }
2221 :
2222 : /* Return true if SEARCH is an element of V. Note that this is O(N) in the
2223 : size of the vector and so should be used with care. */
2224 :
2225 : template<typename T>
2226 : inline bool
2227 : vec<T, va_heap, vl_ptr>::contains (const T &search) const
2228 : {
2229 : return m_vec ? m_vec->contains (search) : false;
2230 : }
2231 :
2232 : /* Reverse content of the vector. */
2233 :
2234 : template<typename T>
2235 : inline void
2236 : vec<T, va_heap, vl_ptr>::reverse (void)
2237 : {
2238 : unsigned l = length ();
2239 : T *ptr = address ();
2240 :
2241 : for (unsigned i = 0; i < l / 2; i++)
2242 : std::swap (ptr[i], ptr[l - i - 1]);
2243 : }
2244 :
2245 : template<typename T>
2246 : inline bool
2247 1469304577 : vec<T, va_heap, vl_ptr>::using_auto_storage () const
2248 : {
2249 1469304577 : return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false;
2250 : }
2251 :
2252 : /* Release VEC and call release of all element vectors. */
2253 :
2254 : template<typename T>
2255 : inline void
2256 : release_vec_vec (vec<vec<T> > &vec)
2257 : {
2258 : for (unsigned i = 0; i < vec.length (); i++)
2259 : vec[i].release ();
2260 :
2261 : vec.release ();
2262 : }
2263 :
2264 : // Provide a subset of the std::span functionality. (We can't use std::span
2265 : // itself because it's a C++20 feature.)
2266 : //
2267 : // In addition, provide an invalid value that is distinct from all valid
2268 : // sequences (including the empty sequence). This can be used to return
2269 : // failure without having to use std::optional.
2270 : //
2271 : // There is no operator bool because it would be ambiguous whether it is
2272 : // testing for a valid value or an empty sequence.
2273 : template<typename T>
2274 : class array_slice
2275 : {
2276 : template<typename OtherT> friend class array_slice;
2277 :
2278 : public:
2279 : using value_type = T;
2280 : using iterator = T *;
2281 : using const_iterator = const T *;
2282 :
2283 : array_slice () : m_base (nullptr), m_size (0) {}
2284 :
2285 : template<typename OtherT>
2286 : array_slice (array_slice<OtherT> other)
2287 : : m_base (other.m_base), m_size (other.m_size) {}
2288 :
2289 : array_slice (iterator base, unsigned int size)
2290 : : m_base (base), m_size (size) {}
2291 :
2292 : template<size_t N>
2293 : array_slice (T (&array)[N]) : m_base (array), m_size (N) {}
2294 :
2295 : template<typename OtherT>
2296 : array_slice (const vec<OtherT> &v)
2297 : : m_base (v.address ()), m_size (v.length ()) {}
2298 :
2299 : template<typename OtherT>
2300 : array_slice (vec<OtherT> &v)
2301 : : m_base (v.address ()), m_size (v.length ()) {}
2302 :
2303 : template<typename OtherT, typename A>
2304 : array_slice (const vec<OtherT, A, vl_embed> *v)
2305 : : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2306 :
2307 : template<typename OtherT, typename A>
2308 : array_slice (vec<OtherT, A, vl_embed> *v)
2309 : : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {}
2310 :
2311 0 : iterator begin () { return m_base; }
2312 0 : iterator end () { return m_base + m_size; }
2313 :
2314 : const_iterator begin () const { return m_base; }
2315 : const_iterator end () const { return m_base + m_size; }
2316 :
2317 : value_type &front ();
2318 : value_type &back ();
2319 : value_type &operator[] (unsigned int i);
2320 :
2321 : const value_type &front () const;
2322 : const value_type &back () const;
2323 : const value_type &operator[] (unsigned int i) const;
2324 :
2325 : size_t size () const { return m_size; }
2326 : size_t size_bytes () const { return m_size * sizeof (T); }
2327 : bool empty () const { return m_size == 0; }
2328 :
2329 : // An invalid array_slice that represents a failed operation. This is
2330 : // distinct from an empty slice, which is a valid result in some contexts.
2331 : static array_slice invalid () { return { nullptr, ~0U }; }
2332 :
2333 : // True if the array is valid, false if it is an array like INVALID.
2334 : bool is_valid () const { return m_base || m_size == 0; }
2335 :
2336 : private:
2337 : iterator m_base;
2338 : unsigned int m_size;
2339 : };
2340 :
2341 : template<typename T>
2342 : inline typename array_slice<T>::value_type &
2343 : array_slice<T>::front ()
2344 : {
2345 : gcc_checking_assert (m_size);
2346 : return m_base[0];
2347 : }
2348 :
2349 : template<typename T>
2350 : inline const typename array_slice<T>::value_type &
2351 : array_slice<T>::front () const
2352 : {
2353 : gcc_checking_assert (m_size);
2354 : return m_base[0];
2355 : }
2356 :
2357 : template<typename T>
2358 : inline typename array_slice<T>::value_type &
2359 : array_slice<T>::back ()
2360 : {
2361 : gcc_checking_assert (m_size);
2362 : return m_base[m_size - 1];
2363 : }
2364 :
2365 : template<typename T>
2366 : inline const typename array_slice<T>::value_type &
2367 : array_slice<T>::back () const
2368 : {
2369 : gcc_checking_assert (m_size);
2370 : return m_base[m_size - 1];
2371 : }
2372 :
2373 : template<typename T>
2374 : inline typename array_slice<T>::value_type &
2375 : array_slice<T>::operator[] (unsigned int i)
2376 : {
2377 : gcc_checking_assert (i < m_size);
2378 : return m_base[i];
2379 : }
2380 :
2381 : template<typename T>
2382 : inline const typename array_slice<T>::value_type &
2383 : array_slice<T>::operator[] (unsigned int i) const
2384 : {
2385 : gcc_checking_assert (i < m_size);
2386 : return m_base[i];
2387 : }
2388 :
2389 : template<typename T>
2390 : array_slice<T>
2391 : make_array_slice (T *base, unsigned int size)
2392 : {
2393 : return array_slice<T> (base, size);
2394 : }
2395 :
2396 : #if (GCC_VERSION >= 3000)
2397 : # pragma GCC poison m_vec m_vecpfx m_vecdata
2398 : #endif
2399 :
2400 : #endif // GCC_VEC_H
|
