1/* Vector API for GNU compiler.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#ifndef GCC_VEC_H
23#define GCC_VEC_H
24
25/* Some gen* file have no ggc support as the header file gtype-desc.h is
26 missing. Provide these definitions in case ggc.h has not been included.
27 This is not a problem because any code that runs before gengtype is built
28 will never need to use GC vectors.*/
29
30extern void ggc_free (void *);
31extern size_t ggc_round_alloc_size (size_t requested_size);
32extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
33
34/* Templated vector type and associated interfaces.
35
36 The interface functions are typesafe and use inline functions,
37 sometimes backed by out-of-line generic functions. The vectors are
38 designed to interoperate with the GTY machinery.
39
40 There are both 'index' and 'iterate' accessors. The index accessor
41 is implemented by operator[]. The iterator returns a boolean
42 iteration condition and updates the iteration variable passed by
43 reference. Because the iterator will be inlined, the address-of
44 can be optimized away.
45
46 Each operation that increases the number of active elements is
47 available in 'quick' and 'safe' variants. The former presumes that
48 there is sufficient allocated space for the operation to succeed
49 (it dies if there is not). The latter will reallocate the
50 vector, if needed. Reallocation causes an exponential increase in
51 vector size. If you know you will be adding N elements, it would
52 be more efficient to use the reserve operation before adding the
53 elements with the 'quick' operation. This will ensure there are at
54 least as many elements as you ask for, it will exponentially
55 increase if there are too few spare slots. If you want reserve a
56 specific number of slots, but do not want the exponential increase
57 (for instance, you know this is the last allocation), use the
58 reserve_exact operation. You can also create a vector of a
59 specific size from the get go.
60
61 You should prefer the push and pop operations, as they append and
62 remove from the end of the vector. If you need to remove several
63 items in one go, use the truncate operation. The insert and remove
64 operations allow you to change elements in the middle of the
65 vector. There are two remove operations, one which preserves the
66 element ordering 'ordered_remove', and one which does not
67 'unordered_remove'. The latter function copies the end element
68 into the removed slot, rather than invoke a memmove operation. The
69 'lower_bound' function will determine where to place an item in the
70 array using insert that will maintain sorted order.
71
72 Vectors are template types with three arguments: the type of the
73 elements in the vector, the allocation strategy, and the physical
74 layout to use
75
76 Four allocation strategies are supported:
77
78 - Heap: allocation is done using malloc/free. This is the
79 default allocation strategy.
80
81 - GC: allocation is done using ggc_alloc/ggc_free.
82
83 - GC atomic: same as GC with the exception that the elements
84 themselves are assumed to be of an atomic type that does
85 not need to be garbage collected. This means that marking
86 routines do not need to traverse the array marking the
87 individual elements. This increases the performance of
88 GC activities.
89
90 Two physical layouts are supported:
91
92 - Embedded: The vector is structured using the trailing array
93 idiom. The last member of the structure is an array of size
94 1. When the vector is initially allocated, a single memory
95 block is created to hold the vector's control data and the
96 array of elements. These vectors cannot grow without
97 reallocation (see discussion on embeddable vectors below).
98
99 - Space efficient: The vector is structured as a pointer to an
100 embedded vector. This is the default layout. It means that
101 vectors occupy a single word of storage before initial
102 allocation. Vectors are allowed to grow (the internal
103 pointer is reallocated but the main vector instance does not
104 need to relocate).
105
106 The type, allocation and layout are specified when the vector is
107 declared.
108
109 If you need to directly manipulate a vector, then the 'address'
110 accessor will return the address of the start of the vector. Also
111 the 'space' predicate will tell you whether there is spare capacity
112 in the vector. You will not normally need to use these two functions.
113
114 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. */
183extern void dump_vec_loc_statistics (void);
184
185/* Hashtable mapping vec addresses to descriptors. */
186extern 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
191struct 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.c. */
197 void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
198 void release_overhead (void *, 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
224inline unsigned
225vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
226 bool exact)
227{
228 if (exact)
229 return (pfx ? pfx->m_num : 0) + reserve;
230 else if (!pfx)
231 return MAX (4, reserve);
232 return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
233}
234
235template<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. */
242struct vl_embed { };
243struct 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. */
254struct 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
274template<typename T>
275inline void
276va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
277 MEM_STAT_DECL)
278{
279 unsigned alloc
280 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
281 gcc_checking_assert (alloc);
282
283 if (GATHER_STATISTICS && v)
284 v->m_vecpfx.release_overhead (v, v->allocated (), false);
285
286 size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
287 unsigned nelem = v ? v->length () : 0;
288 v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
289 v->embedded_init (alloc, nelem);
290
291 if (GATHER_STATISTICS)
292 v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT);
293}
294
295
296/* Free the heap space allocated for vector V. */
297
298template<typename T>
299void
300va_heap::release (vec<T, va_heap, vl_embed> *&v)
301{
302 if (v == NULL)
303 return;
304
305 if (GATHER_STATISTICS)
306 v->m_vecpfx.release_overhead (v, v->allocated (), true);
307 ::free (v);
308 v = NULL;
309}
310
311
312/* Allocator type for GC vectors. Notice that we need the structure
313 declaration even if GC is not enabled. */
314
315struct va_gc
316{
317 /* Use vl_embed as the default layout for GC vectors. Due to GTY
318 limitations, GC vectors must always be pointers, so it is more
319 efficient to use a pointer to the vl_embed layout, rather than
320 using a pointer to a pointer as would be the case with vl_ptr. */
321 typedef vl_embed default_layout;
322
323 template<typename T, typename A>
324 static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
325 CXX_MEM_STAT_INFO);
326
327 template<typename T, typename A>
328 static void release (vec<T, A, vl_embed> *&v);
329};
330
331
332/* Free GC memory used by V and reset V to NULL. */
333
334template<typename T, typename A>
335inline void
336va_gc::release (vec<T, A, vl_embed> *&v)
337{
338 if (v)
339 ::ggc_free (v);
340 v = NULL;
341}
342
343
344/* Allocator for GC memory. Ensure there are at least RESERVE free
345 slots in V. If EXACT is true, grow exactly, else grow
346 exponentially. As a special case, if the vector had not been
347 allocated and RESERVE is 0, no vector will be created. */
348
349template<typename T, typename A>
350void
351va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
352 MEM_STAT_DECL)
353{
354 unsigned alloc
355 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
356 if (!alloc)
357 {
358 ::ggc_free (v);
359 v = NULL;
360 return;
361 }
362
363 /* Calculate the amount of space we want. */
364 size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
365
366 /* Ask the allocator how much space it will really give us. */
367 size = ::ggc_round_alloc_size (size);
368
369 /* Adjust the number of slots accordingly. */
370 size_t vec_offset = sizeof (vec_prefix);
371 size_t elt_size = sizeof (T);
372 alloc = (size - vec_offset) / elt_size;
373
374 /* And finally, recalculate the amount of space we ask for. */
375 size = vec_offset + alloc * elt_size;
376
377 unsigned nelem = v ? v->length () : 0;
378 v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
379 PASS_MEM_STAT));
380 v->embedded_init (alloc, nelem);
381}
382
383
384/* Allocator type for GC vectors. This is for vectors of types
385 atomics w.r.t. collection, so allocation and deallocation is
386 completely inherited from va_gc. */
387struct va_gc_atomic : va_gc
388{
389};
390
391
392/* Generic vector template. Default values for A and L indicate the
393 most commonly used strategies.
394
395 FIXME - Ideally, they would all be vl_ptr to encourage using regular
396 instances for vectors, but the existing GTY machinery is limited
397 in that it can only deal with GC objects that are pointers
398 themselves.
399
400 This means that vector operations that need to deal with
401 potentially NULL pointers, must be provided as free
402 functions (see the vec_safe_* functions above). */
403template<typename T,
404 typename A = va_heap,
405 typename L = typename A::default_layout>
406struct GTY((user)) vec
407{
408};
409
410/* Generic vec<> debug helpers.
411
412 These need to be instantiated for each vec<TYPE> used throughout
413 the compiler like this:
414
415 DEFINE_DEBUG_VEC (TYPE)
416
417 The reason we have a debug_helper() is because GDB can't
418 disambiguate a plain call to debug(some_vec), and it must be called
419 like debug<TYPE>(some_vec). */
420
421template<typename T>
422void
423debug_helper (vec<T> &ref)
424{
425 unsigned i;
426 for (i = 0; i < ref.length (); ++i)
427 {
428 fprintf (stderr, "[%d] = ", i);
429 debug_slim (ref[i]);
430 fputc ('\n', stderr);
431 }
432}
433
434/* We need a separate va_gc variant here because default template
435 argument for functions cannot be used in c++-98. Once this
436 restriction is removed, those variant should be folded with the
437 above debug_helper. */
438
439template<typename T>
440void
441debug_helper (vec<T, va_gc> &ref)
442{
443 unsigned i;
444 for (i = 0; i < ref.length (); ++i)
445 {
446 fprintf (stderr, "[%d] = ", i);
447 debug_slim (ref[i]);
448 fputc ('\n', stderr);
449 }
450}
451
452/* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper
453 functions for a type T. */
454
455#define DEFINE_DEBUG_VEC(T) \
456 template void debug_helper (vec<T> &); \
457 template void debug_helper (vec<T, va_gc> &); \
458 /* Define the vec<T> debug functions. */ \
459 DEBUG_FUNCTION void \
460 debug (vec<T> &ref) \
461 { \
462 debug_helper <T> (ref); \
463 } \
464 DEBUG_FUNCTION void \
465 debug (vec<T> *ptr) \
466 { \
467 if (ptr) \
468 debug (*ptr); \
469 else \
470 fprintf (stderr, "<nil>\n"); \
471 } \
472 /* Define the vec<T, va_gc> debug functions. */ \
473 DEBUG_FUNCTION void \
474 debug (vec<T, va_gc> &ref) \
475 { \
476 debug_helper <T> (ref); \
477 } \
478 DEBUG_FUNCTION void \
479 debug (vec<T, va_gc> *ptr) \
480 { \
481 if (ptr) \
482 debug (*ptr); \
483 else \
484 fprintf (stderr, "<nil>\n"); \
485 }
486
487/* Default-construct N elements in DST. */
488
489template <typename T>
490inline void
491vec_default_construct (T *dst, unsigned n)
492{
493 for ( ; n; ++dst, --n)
494 ::new (static_cast<void*>(dst)) T ();
495}
496
497/* Copy-construct N elements in DST from *SRC. */
498
499template <typename T>
500inline void
501vec_copy_construct (T *dst, const T *src, unsigned n)
502{
503 for ( ; n; ++dst, ++src, --n)
504 ::new (static_cast<void*>(dst)) T (*src);
505}
506
507/* Type to provide NULL values for vec<T, A, L>. This is used to
508 provide nil initializers for vec instances. Since vec must be
509 a POD, we cannot have proper ctor/dtor for it. To initialize
510 a vec instance, you can assign it the value vNULL. This isn't
511 needed for file-scope and function-local static vectors, which
512 are zero-initialized by default. */
513struct vnull
514{
515 template <typename T, typename A, typename L>
516 CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); }
517};
518extern vnull vNULL;
519
520
521/* Embeddable vector. These vectors are suitable to be embedded
522 in other data structures so that they can be pre-allocated in a
523 contiguous memory block.
524
525 Embeddable vectors are implemented using the trailing array idiom,
526 thus they are not resizeable without changing the address of the
527 vector object itself. This means you cannot have variables or
528 fields of embeddable vector type -- always use a pointer to a
529 vector. The one exception is the final field of a structure, which
530 could be a vector type.
531
532 You will have to use the embedded_size & embedded_init calls to
533 create such objects, and they will not be resizeable (so the 'safe'
534 allocation variants are not available).
535
536 Properties:
537
538 - The whole vector and control data are allocated in a single
539 contiguous block. It uses the trailing-vector idiom, so
540 allocation must reserve enough space for all the elements
541 in the vector plus its control data.
542 - The vector cannot be re-allocated.
543 - The vector cannot grow nor shrink.
544 - No indirections needed for access/manipulation.
545 - It requires 2 words of storage (prior to vector allocation). */
546
547template<typename T, typename A>
548struct GTY((user)) vec<T, A, vl_embed>
549{
550public:
551 unsigned allocated (void) const { return m_vecpfx.m_alloc; }
552 unsigned length (void) const { return m_vecpfx.m_num; }
553 bool is_empty (void) const { return m_vecpfx.m_num == 0; }
554 T *address (void) { return m_vecdata; }
555 const T *address (void) const { return m_vecdata; }
556 T *begin () { return address (); }
557 const T *begin () const { return address (); }
558 T *end () { return address () + length (); }
559 const T *end () const { return address () + length (); }
560 const T &operator[] (unsigned) const;
561 T &operator[] (unsigned);
562 T &last (void);
563 bool space (unsigned) const;
564 bool iterate (unsigned, T *) const;
565 bool iterate (unsigned, T **) const;
566 vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
567 void splice (const vec &);
568 void splice (const vec *src);
569 T *quick_push (const T &);
570 T &pop (void);
571 void truncate (unsigned);
572 void quick_insert (unsigned, const T &);
573 void ordered_remove (unsigned);
574 void unordered_remove (unsigned);
575 void block_remove (unsigned, unsigned);
576 void qsort (int (*) (const void *, const void *));
577 T *bsearch (const void *key, int (*compar)(const void *, const void *));
578 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
579 bool contains (const T &search) const;
580 static size_t embedded_size (unsigned);
581 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
582 void quick_grow (unsigned len);
583 void quick_grow_cleared (unsigned len);
584
585 /* vec class can access our internal data and functions. */
586 template <typename, typename, typename> friend struct vec;
587
588 /* The allocator types also need access to our internals. */
589 friend struct va_gc;
590 friend struct va_gc_atomic;
591 friend struct va_heap;
592
593 /* FIXME - These fields should be private, but we need to cater to
594 compilers that have stricter notions of PODness for types. */
595 vec_prefix m_vecpfx;
596 T m_vecdata[1];
597};
598
599
600/* Convenience wrapper functions to use when dealing with pointers to
601 embedded vectors. Some functionality for these vectors must be
602 provided via free functions for these reasons:
603
604 1- The pointer may be NULL (e.g., before initial allocation).
605
606 2- When the vector needs to grow, it must be reallocated, so
607 the pointer will change its value.
608
609 Because of limitations with the current GC machinery, all vectors
610 in GC memory *must* be pointers. */
611
612
613/* If V contains no room for NELEMS elements, return false. Otherwise,
614 return true. */
615template<typename T, typename A>
616inline bool
617vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
618{
619 return v ? v->space (nelems) : nelems == 0;
620}
621
622
623/* If V is NULL, return 0. Otherwise, return V->length(). */
624template<typename T, typename A>
625inline unsigned
626vec_safe_length (const vec<T, A, vl_embed> *v)
627{
628 return v ? v->length () : 0;
629}
630
631
632/* If V is NULL, return NULL. Otherwise, return V->address(). */
633template<typename T, typename A>
634inline T *
635vec_safe_address (vec<T, A, vl_embed> *v)
636{
637 return v ? v->address () : NULL;
638}
639
640
641/* If V is NULL, return true. Otherwise, return V->is_empty(). */
642template<typename T, typename A>
643inline bool
644vec_safe_is_empty (vec<T, A, vl_embed> *v)
645{
646 return v ? v->is_empty () : true;
647}
648
649/* If V does not have space for NELEMS elements, call
650 V->reserve(NELEMS, EXACT). */
651template<typename T, typename A>
652inline bool
653vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
654 CXX_MEM_STAT_INFO)
655{
656 bool extend = nelems ? !vec_safe_space (v, nelems) : false;
657 if (extend)
658 A::reserve (v, nelems, exact PASS_MEM_STAT);
659 return extend;
660}
661
662template<typename T, typename A>
663inline bool
664vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
665 CXX_MEM_STAT_INFO)
666{
667 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
668}
669
670
671/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
672 is 0, V is initialized to NULL. */
673
674template<typename T, typename A>
675inline void
676vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
677{
678 v = NULL;
679 vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
680}
681
682
683/* Free the GC memory allocated by vector V and set it to NULL. */
684
685template<typename T, typename A>
686inline void
687vec_free (vec<T, A, vl_embed> *&v)
688{
689 A::release (v);
690}
691
692
693/* Grow V to length LEN. Allocate it, if necessary. */
694template<typename T, typename A>
695inline void
696vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
697{
698 unsigned oldlen = vec_safe_length (v);
699 gcc_checking_assert (len >= oldlen);
700 vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
701 v->quick_grow (len);
702}
703
704
705/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
706template<typename T, typename A>
707inline void
708vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
709{
710 unsigned oldlen = vec_safe_length (v);
711 vec_safe_grow (v, len PASS_MEM_STAT);
712 vec_default_construct (v->address () + oldlen, len - oldlen);
713}
714
715
716/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
717template<typename T, typename A>
718inline bool
719vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
720{
721 if (v)
722 return v->iterate (ix, ptr);
723 else
724 {
725 *ptr = 0;
726 return false;
727 }
728}
729
730template<typename T, typename A>
731inline bool
732vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
733{
734 if (v)
735 return v->iterate (ix, ptr);
736 else
737 {
738 *ptr = 0;
739 return false;
740 }
741}
742
743
744/* If V has no room for one more element, reallocate it. Then call
745 V->quick_push(OBJ). */
746template<typename T, typename A>
747inline T *
748vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
749{
750 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
751 return v->quick_push (obj);
752}
753
754
755/* if V has no room for one more element, reallocate it. Then call
756 V->quick_insert(IX, OBJ). */
757template<typename T, typename A>
758inline void
759vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
760 CXX_MEM_STAT_INFO)
761{
762 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
763 v->quick_insert (ix, obj);
764}
765
766
767/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
768template<typename T, typename A>
769inline void
770vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
771{
772 if (v)
773 v->truncate (size);
774}
775
776
777/* If SRC is not NULL, return a pointer to a copy of it. */
778template<typename T, typename A>
779inline vec<T, A, vl_embed> *
780vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
781{
782 return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
783}
784
785/* Copy the elements from SRC to the end of DST as if by memcpy.
786 Reallocate DST, if necessary. */
787template<typename T, typename A>
788inline void
789vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
790 CXX_MEM_STAT_INFO)
791{
792 unsigned src_len = vec_safe_length (src);
793 if (src_len)
794 {
795 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
796 PASS_MEM_STAT);
797 dst->splice (*src);
798 }
799}
800
801/* Return true if SEARCH is an element of V. Note that this is O(N) in the
802 size of the vector and so should be used with care. */
803
804template<typename T, typename A>
805inline bool
806vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
807{
808 return v ? v->contains (search) : false;
809}
810
811/* Index into vector. Return the IX'th element. IX must be in the
812 domain of the vector. */
813
814template<typename T, typename A>
815inline const T &
816vec<T, A, vl_embed>::operator[] (unsigned ix) const
817{
818 gcc_checking_assert (ix < m_vecpfx.m_num);
819 return m_vecdata[ix];
820}
821
822template<typename T, typename A>
823inline T &
824vec<T, A, vl_embed>::operator[] (unsigned ix)
825{
826 gcc_checking_assert (ix < m_vecpfx.m_num);
827 return m_vecdata[ix];
828}
829
830
831/* Get the final element of the vector, which must not be empty. */
832
833template<typename T, typename A>
834inline T &
835vec<T, A, vl_embed>::last (void)
836{
837 gcc_checking_assert (m_vecpfx.m_num > 0);
838 return (*this)[m_vecpfx.m_num - 1];
839}
840
841
842/* If this vector has space for NELEMS additional entries, return
843 true. You usually only need to use this if you are doing your
844 own vector reallocation, for instance on an embedded vector. This
845 returns true in exactly the same circumstances that vec::reserve
846 will. */
847
848template<typename T, typename A>
849inline bool
850vec<T, A, vl_embed>::space (unsigned nelems) const
851{
852 return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
853}
854
855
856/* Return iteration condition and update PTR to point to the IX'th
857 element of this vector. Use this to iterate over the elements of a
858 vector as follows,
859
860 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
861 continue; */
862
863template<typename T, typename A>
864inline bool
865vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
866{
867 if (ix < m_vecpfx.m_num)
868 {
869 *ptr = m_vecdata[ix];
870 return true;
871 }
872 else
873 {
874 *ptr = 0;
875 return false;
876 }
877}
878
879
880/* Return iteration condition and update *PTR to point to the
881 IX'th element of this vector. Use this to iterate over the
882 elements of a vector as follows,
883
884 for (ix = 0; v->iterate (ix, &ptr); ix++)
885 continue;
886
887 This variant is for vectors of objects. */
888
889template<typename T, typename A>
890inline bool
891vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
892{
893 if (ix < m_vecpfx.m_num)
894 {
895 *ptr = CONST_CAST (T *, &m_vecdata[ix]);
896 return true;
897 }
898 else
899 {
900 *ptr = 0;
901 return false;
902 }
903}
904
905
906/* Return a pointer to a copy of this vector. */
907
908template<typename T, typename A>
909inline vec<T, A, vl_embed> *
910vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
911{
912 vec<T, A, vl_embed> *new_vec = NULL;
913 unsigned len = length ();
914 if (len)
915 {
916 vec_alloc (new_vec, len PASS_MEM_STAT);
917 new_vec->embedded_init (len, len);
918 vec_copy_construct (new_vec->address (), m_vecdata, len);
919 }
920 return new_vec;
921}
922
923
924/* Copy the elements from SRC to the end of this vector as if by memcpy.
925 The vector must have sufficient headroom available. */
926
927template<typename T, typename A>
928inline void
929vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
930{
931 unsigned len = src.length ();
932 if (len)
933 {
934 gcc_checking_assert (space (len));
935 vec_copy_construct (end (), src.address (), len);
936 m_vecpfx.m_num += len;
937 }
938}
939
940template<typename T, typename A>
941inline void
942vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
943{
944 if (src)
945 splice (*src);
946}
947
948
949/* Push OBJ (a new element) onto the end of the vector. There must be
950 sufficient space in the vector. Return a pointer to the slot
951 where OBJ was inserted. */
952
953template<typename T, typename A>
954inline T *
955vec<T, A, vl_embed>::quick_push (const T &obj)
956{
957 gcc_checking_assert (space (1));
958 T *slot = &m_vecdata[m_vecpfx.m_num++];
959 *slot = obj;
960 return slot;
961}
962
963
964/* Pop and return the last element off the end of the vector. */
965
966template<typename T, typename A>
967inline T &
968vec<T, A, vl_embed>::pop (void)
969{
970 gcc_checking_assert (length () > 0);
971 return m_vecdata[--m_vecpfx.m_num];
972}
973
974
975/* Set the length of the vector to SIZE. The new length must be less
976 than or equal to the current length. This is an O(1) operation. */
977
978template<typename T, typename A>
979inline void
980vec<T, A, vl_embed>::truncate (unsigned size)
981{
982 gcc_checking_assert (length () >= size);
983 m_vecpfx.m_num = size;
984}
985
986
987/* Insert an element, OBJ, at the IXth position of this vector. There
988 must be sufficient space. */
989
990template<typename T, typename A>
991inline void
992vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
993{
994 gcc_checking_assert (length () < allocated ());
995 gcc_checking_assert (ix <= length ());
996 T *slot = &m_vecdata[ix];
997 memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
998 *slot = obj;
999}
1000
1001
1002/* Remove an element from the IXth position of this vector. Ordering of
1003 remaining elements is preserved. This is an O(N) operation due to
1004 memmove. */
1005
1006template<typename T, typename A>
1007inline void
1008vec<T, A, vl_embed>::ordered_remove (unsigned ix)
1009{
1010 gcc_checking_assert (ix < length ());
1011 T *slot = &m_vecdata[ix];
1012 memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
1013}
1014
1015
1016/* Remove an element from the IXth position of this vector. Ordering of
1017 remaining elements is destroyed. This is an O(1) operation. */
1018
1019template<typename T, typename A>
1020inline void
1021vec<T, A, vl_embed>::unordered_remove (unsigned ix)
1022{
1023 gcc_checking_assert (ix < length ());
1024 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
1025}
1026
1027
1028/* Remove LEN elements starting at the IXth. Ordering is retained.
1029 This is an O(N) operation due to memmove. */
1030
1031template<typename T, typename A>
1032inline void
1033vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
1034{
1035 gcc_checking_assert (ix + len <= length ());
1036 T *slot = &m_vecdata[ix];
1037 m_vecpfx.m_num -= len;
1038 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
1039}
1040
1041
1042/* Sort the contents of this vector with qsort. CMP is the comparison
1043 function to pass to qsort. */
1044
1045template<typename T, typename A>
1046inline void
1047vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
1048{
1049 if (length () > 1)
1050 ::qsort (address (), length (), sizeof (T), cmp);
1051}
1052
1053
1054/* Search the contents of the sorted vector with a binary search.
1055 CMP is the comparison function to pass to bsearch. */
1056
1057template<typename T, typename A>
1058inline T *
1059vec<T, A, vl_embed>::bsearch (const void *key,
1060 int (*compar) (const void *, const void *))
1061{
1062 const void *base = this->address ();
1063 size_t nmemb = this->length ();
1064 size_t size = sizeof (T);
1065 /* The following is a copy of glibc stdlib-bsearch.h. */
1066 size_t l, u, idx;
1067 const void *p;
1068 int comparison;
1069
1070 l = 0;
1071 u = nmemb;
1072 while (l < u)
1073 {
1074 idx = (l + u) / 2;
1075 p = (const void *) (((const char *) base) + (idx * size));
1076 comparison = (*compar) (key, p);
1077 if (comparison < 0)
1078 u = idx;
1079 else if (comparison > 0)
1080 l = idx + 1;
1081 else
1082 return (T *)const_cast<void *>(p);
1083 }
1084
1085 return NULL;
1086}
1087
1088/* Return true if SEARCH is an element of V. Note that this is O(N) in the
1089 size of the vector and so should be used with care. */
1090
1091template<typename T, typename A>
1092inline bool
1093vec<T, A, vl_embed>::contains (const T &search) const
1094{
1095 unsigned int len = length ();
1096 for (unsigned int i = 0; i < len; i++)
1097 if ((*this)[i] == search)
1098 return true;
1099
1100 return false;
1101}
1102
1103/* Find and return the first position in which OBJ could be inserted
1104 without changing the ordering of this vector. LESSTHAN is a
1105 function that returns true if the first argument is strictly less
1106 than the second. */
1107
1108template<typename T, typename A>
1109unsigned
1110vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
1111 const
1112{
1113 unsigned int len = length ();
1114 unsigned int half, middle;
1115 unsigned int first = 0;
1116 while (len > 0)
1117 {
1118 half = len / 2;
1119 middle = first;
1120 middle += half;
1121 T middle_elem = (*this)[middle];
1122 if (lessthan (middle_elem, obj))
1123 {
1124 first = middle;
1125 ++first;
1126 len = len - half - 1;
1127 }
1128 else
1129 len = half;
1130 }
1131 return first;
1132}
1133
1134
1135/* Return the number of bytes needed to embed an instance of an
1136 embeddable vec inside another data structure.
1137
1138 Use these methods to determine the required size and initialization
1139 of a vector V of type T embedded within another structure (as the
1140 final member):
1141
1142 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1143 void v->embedded_init (unsigned alloc, unsigned num);
1144
1145 These allow the caller to perform the memory allocation. */
1146
1147template<typename T, typename A>
1148inline size_t
1149vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1150{
1151 typedef vec<T, A, vl_embed> vec_embedded;
1152 return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
1153}
1154
1155
1156/* Initialize the vector to contain room for ALLOC elements and
1157 NUM active elements. */
1158
1159template<typename T, typename A>
1160inline void
1161vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1162{
1163 m_vecpfx.m_alloc = alloc;
1164 m_vecpfx.m_using_auto_storage = aut;
1165 m_vecpfx.m_num = num;
1166}
1167
1168
1169/* Grow the vector to a specific length. LEN must be as long or longer than
1170 the current length. The new elements are uninitialized. */
1171
1172template<typename T, typename A>
1173inline void
1174vec<T, A, vl_embed>::quick_grow (unsigned len)
1175{
1176 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1177 m_vecpfx.m_num = len;
1178}
1179
1180
1181/* Grow the vector to a specific length. LEN must be as long or longer than
1182 the current length. The new elements are initialized to zero. */
1183
1184template<typename T, typename A>
1185inline void
1186vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1187{
1188 unsigned oldlen = length ();
1189 size_t growby = len - oldlen;
1190 quick_grow (len);
1191 if (growby != 0)
1192 vec_default_construct (address () + oldlen, growby);
1193}
1194
1195/* Garbage collection support for vec<T, A, vl_embed>. */
1196
1197template<typename T>
1198void
1199gt_ggc_mx (vec<T, va_gc> *v)
1200{
1201 extern void gt_ggc_mx (T &);
1202 for (unsigned i = 0; i < v->length (); i++)
1203 gt_ggc_mx ((*v)[i]);
1204}
1205
1206template<typename T>
1207void
1208gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1209{
1210 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1211 be traversed. */
1212}
1213
1214
1215/* PCH support for vec<T, A, vl_embed>. */
1216
1217template<typename T, typename A>
1218void
1219gt_pch_nx (vec<T, A, vl_embed> *v)
1220{
1221 extern void gt_pch_nx (T &);
1222 for (unsigned i = 0; i < v->length (); i++)
1223 gt_pch_nx ((*v)[i]);
1224}
1225
1226template<typename T, typename A>
1227void
1228gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1229{
1230 for (unsigned i = 0; i < v->length (); i++)
1231 op (&((*v)[i]), cookie);
1232}
1233
1234template<typename T, typename A>
1235void
1236gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1237{
1238 extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1239 for (unsigned i = 0; i < v->length (); i++)
1240 gt_pch_nx (&((*v)[i]), op, cookie);
1241}
1242
1243
1244/* Space efficient vector. These vectors can grow dynamically and are
1245 allocated together with their control data. They are suited to be
1246 included in data structures. Prior to initial allocation, they
1247 only take a single word of storage.
1248
1249 These vectors are implemented as a pointer to an embeddable vector.
1250 The semantics allow for this pointer to be NULL to represent empty
1251 vectors. This way, empty vectors occupy minimal space in the
1252 structure containing them.
1253
1254 Properties:
1255
1256 - The whole vector and control data are allocated in a single
1257 contiguous block.
1258 - The whole vector may be re-allocated.
1259 - Vector data may grow and shrink.
1260 - Access and manipulation requires a pointer test and
1261 indirection.
1262 - It requires 1 word of storage (prior to vector allocation).
1263
1264
1265 Limitations:
1266
1267 These vectors must be PODs because they are stored in unions.
1268 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1269 As long as we use C++03, we cannot have constructors nor
1270 destructors in classes that are stored in unions. */
1271
1272template<typename T>
1273struct vec<T, va_heap, vl_ptr>
1274{
1275public:
1276 /* Memory allocation and deallocation for the embedded vector.
1277 Needed because we cannot have proper ctors/dtors defined. */
1278 void create (unsigned nelems CXX_MEM_STAT_INFO);
1279 void release (void);
1280
1281 /* Vector operations. */
1282 bool exists (void) const
1283 { return m_vec != NULL; }
1284
1285 bool is_empty (void) const
1286 { return m_vec ? m_vec->is_empty () : true; }
1287
1288 unsigned length (void) const
1289 { return m_vec ? m_vec->length () : 0; }
1290
1291 T *address (void)
1292 { return m_vec ? m_vec->m_vecdata : NULL; }
1293
1294 const T *address (void) const
1295 { return m_vec ? m_vec->m_vecdata : NULL; }
1296
1297 T *begin () { return address (); }
1298 const T *begin () const { return address (); }
1299 T *end () { return begin () + length (); }
1300 const T *end () const { return begin () + length (); }
1301 const T &operator[] (unsigned ix) const
1302 { return (*m_vec)[ix]; }
1303
1304 bool operator!=(const vec &other) const
1305 { return !(*this == other); }
1306
1307 bool operator==(const vec &other) const
1308 { return address () == other.address (); }
1309
1310 T &operator[] (unsigned ix)
1311 { return (*m_vec)[ix]; }
1312
1313 T &last (void)
1314 { return m_vec->last (); }
1315
1316 bool space (int nelems) const
1317 { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1318
1319 bool iterate (unsigned ix, T *p) const;
1320 bool iterate (unsigned ix, T **p) const;
1321 vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1322 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1323 bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1324 void splice (const vec &);
1325 void safe_splice (const vec & CXX_MEM_STAT_INFO);
1326 T *quick_push (const T &);
1327 T *safe_push (const T &CXX_MEM_STAT_INFO);
1328 T &pop (void);
1329 void truncate (unsigned);
1330 void safe_grow (unsigned CXX_MEM_STAT_INFO);
1331 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
1332 void quick_grow (unsigned);
1333 void quick_grow_cleared (unsigned);
1334 void quick_insert (unsigned, const T &);
1335 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1336 void ordered_remove (unsigned);
1337 void unordered_remove (unsigned);
1338 void block_remove (unsigned, unsigned);
1339 void qsort (int (*) (const void *, const void *));
1340 T *bsearch (const void *key, int (*compar)(const void *, const void *));
1341 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1342 bool contains (const T &search) const;
1343
1344 bool using_auto_storage () const;
1345
1346 /* FIXME - This field should be private, but we need to cater to
1347 compilers that have stricter notions of PODness for types. */
1348 vec<T, va_heap, vl_embed> *m_vec;
1349};
1350
1351
1352/* auto_vec is a subclass of vec that automatically manages creating and
1353 releasing the internal vector. If N is non zero then it has N elements of
1354 internal storage. The default is no internal storage, and you probably only
1355 want to ask for internal storage for vectors on the stack because if the
1356 size of the vector is larger than the internal storage that space is wasted.
1357 */
1358template<typename T, size_t N = 0>
1359class auto_vec : public vec<T, va_heap>
1360{
1361public:
1362 auto_vec ()
1363 {
1364 m_auto.embedded_init (MAX (N, 2), 0, 1);
1365 this->m_vec = &m_auto;
1366 }
1367
1368 auto_vec (size_t s)
1369 {
1370 if (s > N)
1371 {
1372 this->create (s);
1373 return;
1374 }
1375
1376 m_auto.embedded_init (MAX (N, 2), 0, 1);
1377 this->m_vec = &m_auto;
1378 }
1379
1380 ~auto_vec ()
1381 {
1382 this->release ();
1383 }
1384
1385private:
1386 vec<T, va_heap, vl_embed> m_auto;
1387 T m_data[MAX (N - 1, 1)];
1388};
1389
1390/* auto_vec is a sub class of vec whose storage is released when it is
1391 destroyed. */
1392template<typename T>
1393class auto_vec<T, 0> : public vec<T, va_heap>
1394{
1395public:
1396 auto_vec () { this->m_vec = NULL; }
1397 auto_vec (size_t n) { this->create (n); }
1398 ~auto_vec () { this->release (); }
1399};
1400
1401
1402/* Allocate heap memory for pointer V and create the internal vector
1403 with space for NELEMS elements. If NELEMS is 0, the internal
1404 vector is initialized to empty. */
1405
1406template<typename T>
1407inline void
1408vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1409{
1410 v = new vec<T>;
1411 v->create (nelems PASS_MEM_STAT);
1412}
1413
1414
1415/* Conditionally allocate heap memory for VEC and its internal vector. */
1416
1417template<typename T>
1418inline void
1419vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1420{
1421 if (!vec)
1422 vec_alloc (vec, nelems PASS_MEM_STAT);
1423}
1424
1425
1426/* Free the heap memory allocated by vector V and set it to NULL. */
1427
1428template<typename T>
1429inline void
1430vec_free (vec<T> *&v)
1431{
1432 if (v == NULL)
1433 return;
1434
1435 v->release ();
1436 delete v;
1437 v = NULL;
1438}
1439
1440
1441/* Return iteration condition and update PTR to point to the IX'th
1442 element of this vector. Use this to iterate over the elements of a
1443 vector as follows,
1444
1445 for (ix = 0; v.iterate (ix, &ptr); ix++)
1446 continue; */
1447
1448template<typename T>
1449inline bool
1450vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1451{
1452 if (m_vec)
1453 return m_vec->iterate (ix, ptr);
1454 else
1455 {
1456 *ptr = 0;
1457 return false;
1458 }
1459}
1460
1461
1462/* Return iteration condition and update *PTR to point to the
1463 IX'th element of this vector. Use this to iterate over the
1464 elements of a vector as follows,
1465
1466 for (ix = 0; v->iterate (ix, &ptr); ix++)
1467 continue;
1468
1469 This variant is for vectors of objects. */
1470
1471template<typename T>
1472inline bool
1473vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1474{
1475 if (m_vec)
1476 return m_vec->iterate (ix, ptr);
1477 else
1478 {
1479 *ptr = 0;
1480 return false;
1481 }
1482}
1483
1484
1485/* Convenience macro for forward iteration. */
1486#define FOR_EACH_VEC_ELT(V, I, P) \
1487 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1488
1489#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1490 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1491
1492/* Likewise, but start from FROM rather than 0. */
1493#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1494 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1495
1496/* Convenience macro for reverse iteration. */
1497#define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1498 for (I = (V).length () - 1; \
1499 (V).iterate ((I), &(P)); \
1500 (I)--)
1501
1502#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1503 for (I = vec_safe_length (V) - 1; \
1504 vec_safe_iterate ((V), (I), &(P)); \
1505 (I)--)
1506
1507
1508/* Return a copy of this vector. */
1509
1510template<typename T>
1511inline vec<T, va_heap, vl_ptr>
1512vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1513{
1514 vec<T, va_heap, vl_ptr> new_vec = vNULL;
1515 if (length ())
1516 new_vec.m_vec = m_vec->copy ();
1517 return new_vec;
1518}
1519
1520
1521/* Ensure that the vector has at least RESERVE slots available (if
1522 EXACT is false), or exactly RESERVE slots available (if EXACT is
1523 true).
1524
1525 This may create additional headroom if EXACT is false.
1526
1527 Note that this can cause the embedded vector to be reallocated.
1528 Returns true iff reallocation actually occurred. */
1529
1530template<typename T>
1531inline bool
1532vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1533{
1534 if (space (nelems))
1535 return false;
1536
1537 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1538 this is necessary because it doesn't have enough information to know the
1539 embedded vector is in auto storage, and so should not be freed. */
1540 vec<T, va_heap, vl_embed> *oldvec = m_vec;
1541 unsigned int oldsize = 0;
1542 bool handle_auto_vec = m_vec && using_auto_storage ();
1543 if (handle_auto_vec)
1544 {
1545 m_vec = NULL;
1546 oldsize = oldvec->length ();
1547 nelems += oldsize;
1548 }
1549
1550 va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1551 if (handle_auto_vec)
1552 {
1553 vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
1554 m_vec->m_vecpfx.m_num = oldsize;
1555 }
1556
1557 return true;
1558}
1559
1560
1561/* Ensure that this vector has exactly NELEMS slots available. This
1562 will not create additional headroom. Note this can cause the
1563 embedded vector to be reallocated. Returns true iff reallocation
1564 actually occurred. */
1565
1566template<typename T>
1567inline bool
1568vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1569{
1570 return reserve (nelems, true PASS_MEM_STAT);
1571}
1572
1573
1574/* Create the internal vector and reserve NELEMS for it. This is
1575 exactly like vec::reserve, but the internal vector is
1576 unconditionally allocated from scratch. The old one, if it
1577 existed, is lost. */
1578
1579template<typename T>
1580inline void
1581vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1582{
1583 m_vec = NULL;
1584 if (nelems > 0)
1585 reserve_exact (nelems PASS_MEM_STAT);
1586}
1587
1588
1589/* Free the memory occupied by the embedded vector. */
1590
1591template<typename T>
1592inline void
1593vec<T, va_heap, vl_ptr>::release (void)
1594{
1595 if (!m_vec)
1596 return;
1597
1598 if (using_auto_storage ())
1599 {
1600 m_vec->m_vecpfx.m_num = 0;
1601 return;
1602 }
1603
1604 va_heap::release (m_vec);
1605}
1606
1607/* Copy the elements from SRC to the end of this vector as if by memcpy.
1608 SRC and this vector must be allocated with the same memory
1609 allocation mechanism. This vector is assumed to have sufficient
1610 headroom available. */
1611
1612template<typename T>
1613inline void
1614vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1615{
1616 if (src.m_vec)
1617 m_vec->splice (*(src.m_vec));
1618}
1619
1620
1621/* Copy the elements in SRC to the end of this vector as if by memcpy.
1622 SRC and this vector must be allocated with the same mechanism.
1623 If there is not enough headroom in this vector, it will be reallocated
1624 as needed. */
1625
1626template<typename T>
1627inline void
1628vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1629 MEM_STAT_DECL)
1630{
1631 if (src.length ())
1632 {
1633 reserve_exact (src.length ());
1634 splice (src);
1635 }
1636}
1637
1638
1639/* Push OBJ (a new element) onto the end of the vector. There must be
1640 sufficient space in the vector. Return a pointer to the slot
1641 where OBJ was inserted. */
1642
1643template<typename T>
1644inline T *
1645vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1646{
1647 return m_vec->quick_push (obj);
1648}
1649
1650
1651/* Push a new element OBJ onto the end of this vector. Reallocates
1652 the embedded vector, if needed. Return a pointer to the slot where
1653 OBJ was inserted. */
1654
1655template<typename T>
1656inline T *
1657vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1658{
1659 reserve (1, false PASS_MEM_STAT);
1660 return quick_push (obj);
1661}
1662
1663
1664/* Pop and return the last element off the end of the vector. */
1665
1666template<typename T>
1667inline T &
1668vec<T, va_heap, vl_ptr>::pop (void)
1669{
1670 return m_vec->pop ();
1671}
1672
1673
1674/* Set the length of the vector to LEN. The new length must be less
1675 than or equal to the current length. This is an O(1) operation. */
1676
1677template<typename T>
1678inline void
1679vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1680{
1681 if (m_vec)
1682 m_vec->truncate (size);
1683 else
1684 gcc_checking_assert (size == 0);
1685}
1686
1687
1688/* Grow the vector to a specific length. LEN must be as long or
1689 longer than the current length. The new elements are
1690 uninitialized. Reallocate the internal vector, if needed. */
1691
1692template<typename T>
1693inline void
1694vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
1695{
1696 unsigned oldlen = length ();
1697 gcc_checking_assert (oldlen <= len);
1698 reserve_exact (len - oldlen PASS_MEM_STAT);
1699 if (m_vec)
1700 m_vec->quick_grow (len);
1701 else
1702 gcc_checking_assert (len == 0);
1703}
1704
1705
1706/* Grow the embedded vector to a specific length. LEN must be as
1707 long or longer than the current length. The new elements are
1708 initialized to zero. Reallocate the internal vector, if needed. */
1709
1710template<typename T>
1711inline void
1712vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
1713{
1714 unsigned oldlen = length ();
1715 size_t growby = len - oldlen;
1716 safe_grow (len PASS_MEM_STAT);
1717 if (growby != 0)
1718 vec_default_construct (address () + oldlen, growby);
1719}
1720
1721
1722/* Same as vec::safe_grow but without reallocation of the internal vector.
1723 If the vector cannot be extended, a runtime assertion will be triggered. */
1724
1725template<typename T>
1726inline void
1727vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
1728{
1729 gcc_checking_assert (m_vec);
1730 m_vec->quick_grow (len);
1731}
1732
1733
1734/* Same as vec::quick_grow_cleared but without reallocation of the
1735 internal vector. If the vector cannot be extended, a runtime
1736 assertion will be triggered. */
1737
1738template<typename T>
1739inline void
1740vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
1741{
1742 gcc_checking_assert (m_vec);
1743 m_vec->quick_grow_cleared (len);
1744}
1745
1746
1747/* Insert an element, OBJ, at the IXth position of this vector. There
1748 must be sufficient space. */
1749
1750template<typename T>
1751inline void
1752vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
1753{
1754 m_vec->quick_insert (ix, obj);
1755}
1756
1757
1758/* Insert an element, OBJ, at the IXth position of the vector.
1759 Reallocate the embedded vector, if necessary. */
1760
1761template<typename T>
1762inline void
1763vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
1764{
1765 reserve (1, false PASS_MEM_STAT);
1766 quick_insert (ix, obj);
1767}
1768
1769
1770/* Remove an element from the IXth position of this vector. Ordering of
1771 remaining elements is preserved. This is an O(N) operation due to
1772 a memmove. */
1773
1774template<typename T>
1775inline void
1776vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
1777{
1778 m_vec->ordered_remove (ix);
1779}
1780
1781
1782/* Remove an element from the IXth position of this vector. Ordering
1783 of remaining elements is destroyed. This is an O(1) operation. */
1784
1785template<typename T>
1786inline void
1787vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
1788{
1789 m_vec->unordered_remove (ix);
1790}
1791
1792
1793/* Remove LEN elements starting at the IXth. Ordering is retained.
1794 This is an O(N) operation due to memmove. */
1795
1796template<typename T>
1797inline void
1798vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
1799{
1800 m_vec->block_remove (ix, len);
1801}
1802
1803
1804/* Sort the contents of this vector with qsort. CMP is the comparison
1805 function to pass to qsort. */
1806
1807template<typename T>
1808inline void
1809vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
1810{
1811 if (m_vec)
1812 m_vec->qsort (cmp);
1813}
1814
1815
1816/* Search the contents of the sorted vector with a binary search.
1817 CMP is the comparison function to pass to bsearch. */
1818
1819template<typename T>
1820inline T *
1821vec<T, va_heap, vl_ptr>::bsearch (const void *key,
1822 int (*cmp) (const void *, const void *))
1823{
1824 if (m_vec)
1825 return m_vec->bsearch (key, cmp);
1826 return NULL;
1827}
1828
1829
1830/* Find and return the first position in which OBJ could be inserted
1831 without changing the ordering of this vector. LESSTHAN is a
1832 function that returns true if the first argument is strictly less
1833 than the second. */
1834
1835template<typename T>
1836inline unsigned
1837vec<T, va_heap, vl_ptr>::lower_bound (T obj,
1838 bool (*lessthan)(const T &, const T &))
1839 const
1840{
1841 return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
1842}
1843
1844/* Return true if SEARCH is an element of V. Note that this is O(N) in the
1845 size of the vector and so should be used with care. */
1846
1847template<typename T>
1848inline bool
1849vec<T, va_heap, vl_ptr>::contains (const T &search) const
1850{
1851 return m_vec ? m_vec->contains (search) : false;
1852}
1853
1854template<typename T>
1855inline bool
1856vec<T, va_heap, vl_ptr>::using_auto_storage () const
1857{
1858 return m_vec->m_vecpfx.m_using_auto_storage;
1859}
1860
1861/* Release VEC and call release of all element vectors. */
1862
1863template<typename T>
1864inline void
1865release_vec_vec (vec<vec<T> > &vec)
1866{
1867 for (unsigned i = 0; i < vec.length (); i++)
1868 vec[i].release ();
1869
1870 vec.release ();
1871}
1872
1873#if (GCC_VERSION >= 3000)
1874# pragma GCC poison m_vec m_vecpfx m_vecdata
1875#endif
1876
1877#endif // GCC_VEC_H
1878