/cp
[official-gcc.git] / gcc / vec.h
blob61a6189407699b4f4baca983d4b06eedbd60f38b
1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
6 This file is part of GCC.
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.
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.
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/>. */
22 #ifndef GCC_VEC_H
23 #define GCC_VEC_H
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.*/
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);
34 /* Templated vector type and associated interfaces.
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.
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.
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.
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.
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
76 Four allocation strategies are supported:
78 - Heap: allocation is done using malloc/free. This is the
79 default allocation strategy.
81 - GC: allocation is done using ggc_alloc/ggc_free.
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.
90 Two physical layouts are supported:
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).
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).
106 The type, allocation and layout are specified when the vector is
107 declared.
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.
114 Notes on the different layout strategies
116 * Embeddable vectors (vec<T, A, vl_embed>)
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.
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.
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).
133 Properties of embeddable vectors:
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).
145 * Space efficient vector (vec<T, A, vl_ptr>)
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.
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.
157 Properties:
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).
167 An example of their use would be,
169 struct my_struct {
170 // A space-efficient vector of tree pointers in GC memory.
171 vec<tree, va_gc, vl_ptr> v;
174 struct my_struct *s;
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 }
182 /* Support function for statistics. */
183 extern void dump_vec_loc_statistics (void);
185 /* Hashtable mapping vec addresses to descriptors. */
186 extern htab_t vec_mem_usage_hash;
188 /* Control data for vectors. This contains the number of allocated
189 and used slots inside a vector. */
191 struct vec_prefix
193 /* FIXME - These fields should be private, but we need to cater to
194 compilers that have stricter notions of PODness for types. */
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);
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.
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;
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;
215 unsigned m_alloc : 31;
216 unsigned m_using_auto_storage : 1;
217 unsigned m_num;
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. */
224 inline unsigned
225 vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
226 bool exact)
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);
235 template<typename, typename, typename> struct vec;
237 /* Valid vector layouts
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 { };
246 /* Types of supported allocations
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. */
253 /* Allocator type for heap vectors. */
254 struct va_heap
256 /* Heap vectors are frequently regular instances, so use the vl_ptr
257 layout for them. */
258 typedef vl_ptr default_layout;
260 template<typename T>
261 static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
262 CXX_MEM_STAT_INFO);
264 template<typename T>
265 static void release (vec<T, va_heap, vl_embed> *&);
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 and RESERVE is 0, no vector will be created. */
274 template<typename T>
275 inline void
276 va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
277 MEM_STAT_DECL)
279 unsigned alloc
280 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
281 gcc_checking_assert (alloc);
283 if (GATHER_STATISTICS && v)
284 v->m_vecpfx.release_overhead (v, v->allocated (), false);
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);
291 if (GATHER_STATISTICS)
292 v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT);
296 /* Free the heap space allocated for vector V. */
298 template<typename T>
299 void
300 va_heap::release (vec<T, va_heap, vl_embed> *&v)
302 if (v == NULL)
303 return;
305 if (GATHER_STATISTICS)
306 v->m_vecpfx.release_overhead (v, v->allocated (), true);
307 ::free (v);
308 v = NULL;
312 /* Allocator type for GC vectors. Notice that we need the structure
313 declaration even if GC is not enabled. */
315 struct va_gc
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;
323 template<typename T, typename A>
324 static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
325 CXX_MEM_STAT_INFO);
327 template<typename T, typename A>
328 static void release (vec<T, A, vl_embed> *&v);
332 /* Free GC memory used by V and reset V to NULL. */
334 template<typename T, typename A>
335 inline void
336 va_gc::release (vec<T, A, vl_embed> *&v)
338 if (v)
339 ::ggc_free (v);
340 v = NULL;
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 and RESERVE is 0, no vector will be created. */
349 template<typename T, typename A>
350 void
351 va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
352 MEM_STAT_DECL)
354 unsigned alloc
355 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
356 if (!alloc)
358 ::ggc_free (v);
359 v = NULL;
360 return;
363 /* Calculate the amount of space we want. */
364 size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
366 /* Ask the allocator how much space it will really give us. */
367 size = ::ggc_round_alloc_size (size);
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;
374 /* And finally, recalculate the amount of space we ask for. */
375 size = vec_offset + alloc * elt_size;
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);
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. */
387 struct va_gc_atomic : va_gc
392 /* Generic vector template. Default values for A and L indicate the
393 most commonly used strategies.
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.
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). */
403 template<typename T,
404 typename A = va_heap,
405 typename L = typename A::default_layout>
406 struct GTY((user)) vec
410 /* Type to provide NULL values for vec<T, A, L>. This is used to
411 provide nil initializers for vec instances. Since vec must be
412 a POD, we cannot have proper ctor/dtor for it. To initialize
413 a vec instance, you can assign it the value vNULL. */
414 struct vnull
416 template <typename T, typename A, typename L>
417 operator vec<T, A, L> () { return vec<T, A, L>(); }
419 extern vnull vNULL;
422 /* Embeddable vector. These vectors are suitable to be embedded
423 in other data structures so that they can be pre-allocated in a
424 contiguous memory block.
426 Embeddable vectors are implemented using the trailing array idiom,
427 thus they are not resizeable without changing the address of the
428 vector object itself. This means you cannot have variables or
429 fields of embeddable vector type -- always use a pointer to a
430 vector. The one exception is the final field of a structure, which
431 could be a vector type.
433 You will have to use the embedded_size & embedded_init calls to
434 create such objects, and they will not be resizeable (so the 'safe'
435 allocation variants are not available).
437 Properties:
439 - The whole vector and control data are allocated in a single
440 contiguous block. It uses the trailing-vector idiom, so
441 allocation must reserve enough space for all the elements
442 in the vector plus its control data.
443 - The vector cannot be re-allocated.
444 - The vector cannot grow nor shrink.
445 - No indirections needed for access/manipulation.
446 - It requires 2 words of storage (prior to vector allocation). */
448 template<typename T, typename A>
449 struct GTY((user)) vec<T, A, vl_embed>
451 public:
452 unsigned allocated (void) const { return m_vecpfx.m_alloc; }
453 unsigned length (void) const { return m_vecpfx.m_num; }
454 bool is_empty (void) const { return m_vecpfx.m_num == 0; }
455 T *address (void) { return m_vecdata; }
456 const T *address (void) const { return m_vecdata; }
457 const T &operator[] (unsigned) const;
458 T &operator[] (unsigned);
459 T &last (void);
460 bool space (unsigned) const;
461 bool iterate (unsigned, T *) const;
462 bool iterate (unsigned, T **) const;
463 vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
464 void splice (const vec &);
465 void splice (const vec *src);
466 T *quick_push (const T &);
467 T &pop (void);
468 void truncate (unsigned);
469 void quick_insert (unsigned, const T &);
470 void ordered_remove (unsigned);
471 void unordered_remove (unsigned);
472 void block_remove (unsigned, unsigned);
473 void qsort (int (*) (const void *, const void *));
474 T *bsearch (const void *key, int (*compar)(const void *, const void *));
475 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
476 static size_t embedded_size (unsigned);
477 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
478 void quick_grow (unsigned len);
479 void quick_grow_cleared (unsigned len);
481 /* vec class can access our internal data and functions. */
482 template <typename, typename, typename> friend struct vec;
484 /* The allocator types also need access to our internals. */
485 friend struct va_gc;
486 friend struct va_gc_atomic;
487 friend struct va_heap;
489 /* FIXME - These fields should be private, but we need to cater to
490 compilers that have stricter notions of PODness for types. */
491 vec_prefix m_vecpfx;
492 T m_vecdata[1];
496 /* Convenience wrapper functions to use when dealing with pointers to
497 embedded vectors. Some functionality for these vectors must be
498 provided via free functions for these reasons:
500 1- The pointer may be NULL (e.g., before initial allocation).
502 2- When the vector needs to grow, it must be reallocated, so
503 the pointer will change its value.
505 Because of limitations with the current GC machinery, all vectors
506 in GC memory *must* be pointers. */
509 /* If V contains no room for NELEMS elements, return false. Otherwise,
510 return true. */
511 template<typename T, typename A>
512 inline bool
513 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
515 return v ? v->space (nelems) : nelems == 0;
519 /* If V is NULL, return 0. Otherwise, return V->length(). */
520 template<typename T, typename A>
521 inline unsigned
522 vec_safe_length (const vec<T, A, vl_embed> *v)
524 return v ? v->length () : 0;
528 /* If V is NULL, return NULL. Otherwise, return V->address(). */
529 template<typename T, typename A>
530 inline T *
531 vec_safe_address (vec<T, A, vl_embed> *v)
533 return v ? v->address () : NULL;
537 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
538 template<typename T, typename A>
539 inline bool
540 vec_safe_is_empty (vec<T, A, vl_embed> *v)
542 return v ? v->is_empty () : true;
546 /* If V does not have space for NELEMS elements, call
547 V->reserve(NELEMS, EXACT). */
548 template<typename T, typename A>
549 inline bool
550 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
551 CXX_MEM_STAT_INFO)
553 bool extend = nelems ? !vec_safe_space (v, nelems) : false;
554 if (extend)
555 A::reserve (v, nelems, exact PASS_MEM_STAT);
556 return extend;
559 template<typename T, typename A>
560 inline bool
561 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
562 CXX_MEM_STAT_INFO)
564 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
568 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
569 is 0, V is initialized to NULL. */
571 template<typename T, typename A>
572 inline void
573 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
575 v = NULL;
576 vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
580 /* Free the GC memory allocated by vector V and set it to NULL. */
582 template<typename T, typename A>
583 inline void
584 vec_free (vec<T, A, vl_embed> *&v)
586 A::release (v);
590 /* Grow V to length LEN. Allocate it, if necessary. */
591 template<typename T, typename A>
592 inline void
593 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
595 unsigned oldlen = vec_safe_length (v);
596 gcc_checking_assert (len >= oldlen);
597 vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
598 v->quick_grow (len);
602 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
603 template<typename T, typename A>
604 inline void
605 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
607 unsigned oldlen = vec_safe_length (v);
608 vec_safe_grow (v, len PASS_MEM_STAT);
609 memset (&(v->address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
613 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
614 template<typename T, typename A>
615 inline bool
616 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
618 if (v)
619 return v->iterate (ix, ptr);
620 else
622 *ptr = 0;
623 return false;
627 template<typename T, typename A>
628 inline bool
629 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
631 if (v)
632 return v->iterate (ix, ptr);
633 else
635 *ptr = 0;
636 return false;
641 /* If V has no room for one more element, reallocate it. Then call
642 V->quick_push(OBJ). */
643 template<typename T, typename A>
644 inline T *
645 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
647 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
648 return v->quick_push (obj);
652 /* if V has no room for one more element, reallocate it. Then call
653 V->quick_insert(IX, OBJ). */
654 template<typename T, typename A>
655 inline void
656 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
657 CXX_MEM_STAT_INFO)
659 vec_safe_reserve (v, 1, false PASS_MEM_STAT);
660 v->quick_insert (ix, obj);
664 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
665 template<typename T, typename A>
666 inline void
667 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
669 if (v)
670 v->truncate (size);
674 /* If SRC is not NULL, return a pointer to a copy of it. */
675 template<typename T, typename A>
676 inline vec<T, A, vl_embed> *
677 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
679 return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
682 /* Copy the elements from SRC to the end of DST as if by memcpy.
683 Reallocate DST, if necessary. */
684 template<typename T, typename A>
685 inline void
686 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
687 CXX_MEM_STAT_INFO)
689 unsigned src_len = vec_safe_length (src);
690 if (src_len)
692 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
693 PASS_MEM_STAT);
694 dst->splice (*src);
699 /* Index into vector. Return the IX'th element. IX must be in the
700 domain of the vector. */
702 template<typename T, typename A>
703 inline const T &
704 vec<T, A, vl_embed>::operator[] (unsigned ix) const
706 gcc_checking_assert (ix < m_vecpfx.m_num);
707 return m_vecdata[ix];
710 template<typename T, typename A>
711 inline T &
712 vec<T, A, vl_embed>::operator[] (unsigned ix)
714 gcc_checking_assert (ix < m_vecpfx.m_num);
715 return m_vecdata[ix];
719 /* Get the final element of the vector, which must not be empty. */
721 template<typename T, typename A>
722 inline T &
723 vec<T, A, vl_embed>::last (void)
725 gcc_checking_assert (m_vecpfx.m_num > 0);
726 return (*this)[m_vecpfx.m_num - 1];
730 /* If this vector has space for NELEMS additional entries, return
731 true. You usually only need to use this if you are doing your
732 own vector reallocation, for instance on an embedded vector. This
733 returns true in exactly the same circumstances that vec::reserve
734 will. */
736 template<typename T, typename A>
737 inline bool
738 vec<T, A, vl_embed>::space (unsigned nelems) const
740 return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
744 /* Return iteration condition and update PTR to point to the IX'th
745 element of this vector. Use this to iterate over the elements of a
746 vector as follows,
748 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
749 continue; */
751 template<typename T, typename A>
752 inline bool
753 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
755 if (ix < m_vecpfx.m_num)
757 *ptr = m_vecdata[ix];
758 return true;
760 else
762 *ptr = 0;
763 return false;
768 /* Return iteration condition and update *PTR to point to the
769 IX'th element of this vector. Use this to iterate over the
770 elements of a vector as follows,
772 for (ix = 0; v->iterate (ix, &ptr); ix++)
773 continue;
775 This variant is for vectors of objects. */
777 template<typename T, typename A>
778 inline bool
779 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
781 if (ix < m_vecpfx.m_num)
783 *ptr = CONST_CAST (T *, &m_vecdata[ix]);
784 return true;
786 else
788 *ptr = 0;
789 return false;
794 /* Return a pointer to a copy of this vector. */
796 template<typename T, typename A>
797 inline vec<T, A, vl_embed> *
798 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
800 vec<T, A, vl_embed> *new_vec = NULL;
801 unsigned len = length ();
802 if (len)
804 vec_alloc (new_vec, len PASS_MEM_STAT);
805 new_vec->embedded_init (len, len);
806 memcpy (new_vec->address (), m_vecdata, sizeof (T) * len);
808 return new_vec;
812 /* Copy the elements from SRC to the end of this vector as if by memcpy.
813 The vector must have sufficient headroom available. */
815 template<typename T, typename A>
816 inline void
817 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
819 unsigned len = src.length ();
820 if (len)
822 gcc_checking_assert (space (len));
823 memcpy (address () + length (), src.address (), len * sizeof (T));
824 m_vecpfx.m_num += len;
828 template<typename T, typename A>
829 inline void
830 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
832 if (src)
833 splice (*src);
837 /* Push OBJ (a new element) onto the end of the vector. There must be
838 sufficient space in the vector. Return a pointer to the slot
839 where OBJ was inserted. */
841 template<typename T, typename A>
842 inline T *
843 vec<T, A, vl_embed>::quick_push (const T &obj)
845 gcc_checking_assert (space (1));
846 T *slot = &m_vecdata[m_vecpfx.m_num++];
847 *slot = obj;
848 return slot;
852 /* Pop and return the last element off the end of the vector. */
854 template<typename T, typename A>
855 inline T &
856 vec<T, A, vl_embed>::pop (void)
858 gcc_checking_assert (length () > 0);
859 return m_vecdata[--m_vecpfx.m_num];
863 /* Set the length of the vector to SIZE. The new length must be less
864 than or equal to the current length. This is an O(1) operation. */
866 template<typename T, typename A>
867 inline void
868 vec<T, A, vl_embed>::truncate (unsigned size)
870 gcc_checking_assert (length () >= size);
871 m_vecpfx.m_num = size;
875 /* Insert an element, OBJ, at the IXth position of this vector. There
876 must be sufficient space. */
878 template<typename T, typename A>
879 inline void
880 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
882 gcc_checking_assert (length () < allocated ());
883 gcc_checking_assert (ix <= length ());
884 T *slot = &m_vecdata[ix];
885 memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
886 *slot = obj;
890 /* Remove an element from the IXth position of this vector. Ordering of
891 remaining elements is preserved. This is an O(N) operation due to
892 memmove. */
894 template<typename T, typename A>
895 inline void
896 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
898 gcc_checking_assert (ix < length ());
899 T *slot = &m_vecdata[ix];
900 memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
904 /* Remove an element from the IXth position of this vector. Ordering of
905 remaining elements is destroyed. This is an O(1) operation. */
907 template<typename T, typename A>
908 inline void
909 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
911 gcc_checking_assert (ix < length ());
912 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
916 /* Remove LEN elements starting at the IXth. Ordering is retained.
917 This is an O(N) operation due to memmove. */
919 template<typename T, typename A>
920 inline void
921 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
923 gcc_checking_assert (ix + len <= length ());
924 T *slot = &m_vecdata[ix];
925 m_vecpfx.m_num -= len;
926 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
930 /* Sort the contents of this vector with qsort. CMP is the comparison
931 function to pass to qsort. */
933 template<typename T, typename A>
934 inline void
935 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
937 if (length () > 1)
938 ::qsort (address (), length (), sizeof (T), cmp);
942 /* Search the contents of the sorted vector with a binary search.
943 CMP is the comparison function to pass to bsearch. */
945 template<typename T, typename A>
946 inline T *
947 vec<T, A, vl_embed>::bsearch (const void *key,
948 int (*compar) (const void *, const void *))
950 const void *base = this->address ();
951 size_t nmemb = this->length ();
952 size_t size = sizeof (T);
953 /* The following is a copy of glibc stdlib-bsearch.h. */
954 size_t l, u, idx;
955 const void *p;
956 int comparison;
958 l = 0;
959 u = nmemb;
960 while (l < u)
962 idx = (l + u) / 2;
963 p = (const void *) (((const char *) base) + (idx * size));
964 comparison = (*compar) (key, p);
965 if (comparison < 0)
966 u = idx;
967 else if (comparison > 0)
968 l = idx + 1;
969 else
970 return (T *)const_cast<void *>(p);
973 return NULL;
977 /* Find and return the first position in which OBJ could be inserted
978 without changing the ordering of this vector. LESSTHAN is a
979 function that returns true if the first argument is strictly less
980 than the second. */
982 template<typename T, typename A>
983 unsigned
984 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
985 const
987 unsigned int len = length ();
988 unsigned int half, middle;
989 unsigned int first = 0;
990 while (len > 0)
992 half = len / 2;
993 middle = first;
994 middle += half;
995 T middle_elem = (*this)[middle];
996 if (lessthan (middle_elem, obj))
998 first = middle;
999 ++first;
1000 len = len - half - 1;
1002 else
1003 len = half;
1005 return first;
1009 /* Return the number of bytes needed to embed an instance of an
1010 embeddable vec inside another data structure.
1012 Use these methods to determine the required size and initialization
1013 of a vector V of type T embedded within another structure (as the
1014 final member):
1016 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1017 void v->embedded_init (unsigned alloc, unsigned num);
1019 These allow the caller to perform the memory allocation. */
1021 template<typename T, typename A>
1022 inline size_t
1023 vec<T, A, vl_embed>::embedded_size (unsigned alloc)
1025 typedef vec<T, A, vl_embed> vec_embedded;
1026 return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
1030 /* Initialize the vector to contain room for ALLOC elements and
1031 NUM active elements. */
1033 template<typename T, typename A>
1034 inline void
1035 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
1037 m_vecpfx.m_alloc = alloc;
1038 m_vecpfx.m_using_auto_storage = aut;
1039 m_vecpfx.m_num = num;
1043 /* Grow the vector to a specific length. LEN must be as long or longer than
1044 the current length. The new elements are uninitialized. */
1046 template<typename T, typename A>
1047 inline void
1048 vec<T, A, vl_embed>::quick_grow (unsigned len)
1050 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
1051 m_vecpfx.m_num = len;
1055 /* Grow the vector to a specific length. LEN must be as long or longer than
1056 the current length. The new elements are initialized to zero. */
1058 template<typename T, typename A>
1059 inline void
1060 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
1062 unsigned oldlen = length ();
1063 quick_grow (len);
1064 memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
1068 /* Garbage collection support for vec<T, A, vl_embed>. */
1070 template<typename T>
1071 void
1072 gt_ggc_mx (vec<T, va_gc> *v)
1074 extern void gt_ggc_mx (T &);
1075 for (unsigned i = 0; i < v->length (); i++)
1076 gt_ggc_mx ((*v)[i]);
1079 template<typename T>
1080 void
1081 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
1083 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1084 be traversed. */
1088 /* PCH support for vec<T, A, vl_embed>. */
1090 template<typename T, typename A>
1091 void
1092 gt_pch_nx (vec<T, A, vl_embed> *v)
1094 extern void gt_pch_nx (T &);
1095 for (unsigned i = 0; i < v->length (); i++)
1096 gt_pch_nx ((*v)[i]);
1099 template<typename T, typename A>
1100 void
1101 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1103 for (unsigned i = 0; i < v->length (); i++)
1104 op (&((*v)[i]), cookie);
1107 template<typename T, typename A>
1108 void
1109 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
1111 extern void gt_pch_nx (T *, gt_pointer_operator, void *);
1112 for (unsigned i = 0; i < v->length (); i++)
1113 gt_pch_nx (&((*v)[i]), op, cookie);
1117 /* Space efficient vector. These vectors can grow dynamically and are
1118 allocated together with their control data. They are suited to be
1119 included in data structures. Prior to initial allocation, they
1120 only take a single word of storage.
1122 These vectors are implemented as a pointer to an embeddable vector.
1123 The semantics allow for this pointer to be NULL to represent empty
1124 vectors. This way, empty vectors occupy minimal space in the
1125 structure containing them.
1127 Properties:
1129 - The whole vector and control data are allocated in a single
1130 contiguous block.
1131 - The whole vector may be re-allocated.
1132 - Vector data may grow and shrink.
1133 - Access and manipulation requires a pointer test and
1134 indirection.
1135 - It requires 1 word of storage (prior to vector allocation).
1138 Limitations:
1140 These vectors must be PODs because they are stored in unions.
1141 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1142 As long as we use C++03, we cannot have constructors nor
1143 destructors in classes that are stored in unions. */
1145 template<typename T>
1146 struct vec<T, va_heap, vl_ptr>
1148 public:
1149 /* Memory allocation and deallocation for the embedded vector.
1150 Needed because we cannot have proper ctors/dtors defined. */
1151 void create (unsigned nelems CXX_MEM_STAT_INFO);
1152 void release (void);
1154 /* Vector operations. */
1155 bool exists (void) const
1156 { return m_vec != NULL; }
1158 bool is_empty (void) const
1159 { return m_vec ? m_vec->is_empty () : true; }
1161 unsigned length (void) const
1162 { return m_vec ? m_vec->length () : 0; }
1164 T *address (void)
1165 { return m_vec ? m_vec->m_vecdata : NULL; }
1167 const T *address (void) const
1168 { return m_vec ? m_vec->m_vecdata : NULL; }
1170 const T &operator[] (unsigned ix) const
1171 { return (*m_vec)[ix]; }
1173 bool operator!=(const vec &other) const
1174 { return !(*this == other); }
1176 bool operator==(const vec &other) const
1177 { return address () == other.address (); }
1179 T &operator[] (unsigned ix)
1180 { return (*m_vec)[ix]; }
1182 T &last (void)
1183 { return m_vec->last (); }
1185 bool space (int nelems) const
1186 { return m_vec ? m_vec->space (nelems) : nelems == 0; }
1188 bool iterate (unsigned ix, T *p) const;
1189 bool iterate (unsigned ix, T **p) const;
1190 vec copy (ALONE_CXX_MEM_STAT_INFO) const;
1191 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
1192 bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
1193 void splice (const vec &);
1194 void safe_splice (const vec & CXX_MEM_STAT_INFO);
1195 T *quick_push (const T &);
1196 T *safe_push (const T &CXX_MEM_STAT_INFO);
1197 T &pop (void);
1198 void truncate (unsigned);
1199 void safe_grow (unsigned CXX_MEM_STAT_INFO);
1200 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
1201 void quick_grow (unsigned);
1202 void quick_grow_cleared (unsigned);
1203 void quick_insert (unsigned, const T &);
1204 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
1205 void ordered_remove (unsigned);
1206 void unordered_remove (unsigned);
1207 void block_remove (unsigned, unsigned);
1208 void qsort (int (*) (const void *, const void *));
1209 T *bsearch (const void *key, int (*compar)(const void *, const void *));
1210 unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
1212 bool using_auto_storage () const;
1214 /* FIXME - This field should be private, but we need to cater to
1215 compilers that have stricter notions of PODness for types. */
1216 vec<T, va_heap, vl_embed> *m_vec;
1220 /* auto_vec is a subclass of vec that automatically manages creating and
1221 releasing the internal vector. If N is non zero then it has N elements of
1222 internal storage. The default is no internal storage, and you probably only
1223 want to ask for internal storage for vectors on the stack because if the
1224 size of the vector is larger than the internal storage that space is wasted.
1226 template<typename T, size_t N = 0>
1227 class auto_vec : public vec<T, va_heap>
1229 public:
1230 auto_vec ()
1232 m_auto.embedded_init (MAX (N, 2), 0, 1);
1233 this->m_vec = &m_auto;
1236 ~auto_vec ()
1238 this->release ();
1241 private:
1242 vec<T, va_heap, vl_embed> m_auto;
1243 T m_data[MAX (N - 1, 1)];
1246 /* auto_vec is a sub class of vec whose storage is released when it is
1247 destroyed. */
1248 template<typename T>
1249 class auto_vec<T, 0> : public vec<T, va_heap>
1251 public:
1252 auto_vec () { this->m_vec = NULL; }
1253 auto_vec (size_t n) { this->create (n); }
1254 ~auto_vec () { this->release (); }
1258 /* Allocate heap memory for pointer V and create the internal vector
1259 with space for NELEMS elements. If NELEMS is 0, the internal
1260 vector is initialized to empty. */
1262 template<typename T>
1263 inline void
1264 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
1266 v = new vec<T>;
1267 v->create (nelems PASS_MEM_STAT);
1271 /* Conditionally allocate heap memory for VEC and its internal vector. */
1273 template<typename T>
1274 inline void
1275 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
1277 if (!vec)
1278 vec_alloc (vec, nelems PASS_MEM_STAT);
1282 /* Free the heap memory allocated by vector V and set it to NULL. */
1284 template<typename T>
1285 inline void
1286 vec_free (vec<T> *&v)
1288 if (v == NULL)
1289 return;
1291 v->release ();
1292 delete v;
1293 v = NULL;
1297 /* Return iteration condition and update PTR to point to the IX'th
1298 element of this vector. Use this to iterate over the elements of a
1299 vector as follows,
1301 for (ix = 0; v.iterate (ix, &ptr); ix++)
1302 continue; */
1304 template<typename T>
1305 inline bool
1306 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
1308 if (m_vec)
1309 return m_vec->iterate (ix, ptr);
1310 else
1312 *ptr = 0;
1313 return false;
1318 /* Return iteration condition and update *PTR to point to the
1319 IX'th element of this vector. Use this to iterate over the
1320 elements of a vector as follows,
1322 for (ix = 0; v->iterate (ix, &ptr); ix++)
1323 continue;
1325 This variant is for vectors of objects. */
1327 template<typename T>
1328 inline bool
1329 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
1331 if (m_vec)
1332 return m_vec->iterate (ix, ptr);
1333 else
1335 *ptr = 0;
1336 return false;
1341 /* Convenience macro for forward iteration. */
1342 #define FOR_EACH_VEC_ELT(V, I, P) \
1343 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1345 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1346 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1348 /* Likewise, but start from FROM rather than 0. */
1349 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1350 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1352 /* Convenience macro for reverse iteration. */
1353 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1354 for (I = (V).length () - 1; \
1355 (V).iterate ((I), &(P)); \
1356 (I)--)
1358 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1359 for (I = vec_safe_length (V) - 1; \
1360 vec_safe_iterate ((V), (I), &(P)); \
1361 (I)--)
1364 /* Return a copy of this vector. */
1366 template<typename T>
1367 inline vec<T, va_heap, vl_ptr>
1368 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
1370 vec<T, va_heap, vl_ptr> new_vec = vNULL;
1371 if (length ())
1372 new_vec.m_vec = m_vec->copy ();
1373 return new_vec;
1377 /* Ensure that the vector has at least RESERVE slots available (if
1378 EXACT is false), or exactly RESERVE slots available (if EXACT is
1379 true).
1381 This may create additional headroom if EXACT is false.
1383 Note that this can cause the embedded vector to be reallocated.
1384 Returns true iff reallocation actually occurred. */
1386 template<typename T>
1387 inline bool
1388 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
1390 if (space (nelems))
1391 return false;
1393 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1394 this is necessary because it doesn't have enough information to know the
1395 embedded vector is in auto storage, and so should not be freed. */
1396 vec<T, va_heap, vl_embed> *oldvec = m_vec;
1397 unsigned int oldsize = 0;
1398 bool handle_auto_vec = m_vec && using_auto_storage ();
1399 if (handle_auto_vec)
1401 m_vec = NULL;
1402 oldsize = oldvec->length ();
1403 nelems += oldsize;
1406 va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
1407 if (handle_auto_vec)
1409 memcpy (m_vec->address (), oldvec->address (), sizeof (T) * oldsize);
1410 m_vec->m_vecpfx.m_num = oldsize;
1413 return true;
1417 /* Ensure that this vector has exactly NELEMS slots available. This
1418 will not create additional headroom. Note this can cause the
1419 embedded vector to be reallocated. Returns true iff reallocation
1420 actually occurred. */
1422 template<typename T>
1423 inline bool
1424 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
1426 return reserve (nelems, true PASS_MEM_STAT);
1430 /* Create the internal vector and reserve NELEMS for it. This is
1431 exactly like vec::reserve, but the internal vector is
1432 unconditionally allocated from scratch. The old one, if it
1433 existed, is lost. */
1435 template<typename T>
1436 inline void
1437 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
1439 m_vec = NULL;
1440 if (nelems > 0)
1441 reserve_exact (nelems PASS_MEM_STAT);
1445 /* Free the memory occupied by the embedded vector. */
1447 template<typename T>
1448 inline void
1449 vec<T, va_heap, vl_ptr>::release (void)
1451 if (!m_vec)
1452 return;
1454 if (using_auto_storage ())
1456 m_vec->m_vecpfx.m_num = 0;
1457 return;
1460 va_heap::release (m_vec);
1463 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1464 SRC and this vector must be allocated with the same memory
1465 allocation mechanism. This vector is assumed to have sufficient
1466 headroom available. */
1468 template<typename T>
1469 inline void
1470 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
1472 if (src.m_vec)
1473 m_vec->splice (*(src.m_vec));
1477 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1478 SRC and this vector must be allocated with the same mechanism.
1479 If there is not enough headroom in this vector, it will be reallocated
1480 as needed. */
1482 template<typename T>
1483 inline void
1484 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
1485 MEM_STAT_DECL)
1487 if (src.length ())
1489 reserve_exact (src.length ());
1490 splice (src);
1495 /* Push OBJ (a new element) onto the end of the vector. There must be
1496 sufficient space in the vector. Return a pointer to the slot
1497 where OBJ was inserted. */
1499 template<typename T>
1500 inline T *
1501 vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
1503 return m_vec->quick_push (obj);
1507 /* Push a new element OBJ onto the end of this vector. Reallocates
1508 the embedded vector, if needed. Return a pointer to the slot where
1509 OBJ was inserted. */
1511 template<typename T>
1512 inline T *
1513 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
1515 reserve (1, false PASS_MEM_STAT);
1516 return quick_push (obj);
1520 /* Pop and return the last element off the end of the vector. */
1522 template<typename T>
1523 inline T &
1524 vec<T, va_heap, vl_ptr>::pop (void)
1526 return m_vec->pop ();
1530 /* Set the length of the vector to LEN. The new length must be less
1531 than or equal to the current length. This is an O(1) operation. */
1533 template<typename T>
1534 inline void
1535 vec<T, va_heap, vl_ptr>::truncate (unsigned size)
1537 if (m_vec)
1538 m_vec->truncate (size);
1539 else
1540 gcc_checking_assert (size == 0);
1544 /* Grow the vector to a specific length. LEN must be as long or
1545 longer than the current length. The new elements are
1546 uninitialized. Reallocate the internal vector, if needed. */
1548 template<typename T>
1549 inline void
1550 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
1552 unsigned oldlen = length ();
1553 gcc_checking_assert (oldlen <= len);
1554 reserve_exact (len - oldlen PASS_MEM_STAT);
1555 if (m_vec)
1556 m_vec->quick_grow (len);
1557 else
1558 gcc_checking_assert (len == 0);
1562 /* Grow the embedded vector to a specific length. LEN must be as
1563 long or longer than the current length. The new elements are
1564 initialized to zero. Reallocate the internal vector, if needed. */
1566 template<typename T>
1567 inline void
1568 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
1570 unsigned oldlen = length ();
1571 safe_grow (len PASS_MEM_STAT);
1572 memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
1576 /* Same as vec::safe_grow but without reallocation of the internal vector.
1577 If the vector cannot be extended, a runtime assertion will be triggered. */
1579 template<typename T>
1580 inline void
1581 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
1583 gcc_checking_assert (m_vec);
1584 m_vec->quick_grow (len);
1588 /* Same as vec::quick_grow_cleared but without reallocation of the
1589 internal vector. If the vector cannot be extended, a runtime
1590 assertion will be triggered. */
1592 template<typename T>
1593 inline void
1594 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
1596 gcc_checking_assert (m_vec);
1597 m_vec->quick_grow_cleared (len);
1601 /* Insert an element, OBJ, at the IXth position of this vector. There
1602 must be sufficient space. */
1604 template<typename T>
1605 inline void
1606 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
1608 m_vec->quick_insert (ix, obj);
1612 /* Insert an element, OBJ, at the IXth position of the vector.
1613 Reallocate the embedded vector, if necessary. */
1615 template<typename T>
1616 inline void
1617 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
1619 reserve (1, false PASS_MEM_STAT);
1620 quick_insert (ix, obj);
1624 /* Remove an element from the IXth position of this vector. Ordering of
1625 remaining elements is preserved. This is an O(N) operation due to
1626 a memmove. */
1628 template<typename T>
1629 inline void
1630 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
1632 m_vec->ordered_remove (ix);
1636 /* Remove an element from the IXth position of this vector. Ordering
1637 of remaining elements is destroyed. This is an O(1) operation. */
1639 template<typename T>
1640 inline void
1641 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
1643 m_vec->unordered_remove (ix);
1647 /* Remove LEN elements starting at the IXth. Ordering is retained.
1648 This is an O(N) operation due to memmove. */
1650 template<typename T>
1651 inline void
1652 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
1654 m_vec->block_remove (ix, len);
1658 /* Sort the contents of this vector with qsort. CMP is the comparison
1659 function to pass to qsort. */
1661 template<typename T>
1662 inline void
1663 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
1665 if (m_vec)
1666 m_vec->qsort (cmp);
1670 /* Search the contents of the sorted vector with a binary search.
1671 CMP is the comparison function to pass to bsearch. */
1673 template<typename T>
1674 inline T *
1675 vec<T, va_heap, vl_ptr>::bsearch (const void *key,
1676 int (*cmp) (const void *, const void *))
1678 if (m_vec)
1679 return m_vec->bsearch (key, cmp);
1680 return NULL;
1684 /* Find and return the first position in which OBJ could be inserted
1685 without changing the ordering of this vector. LESSTHAN is a
1686 function that returns true if the first argument is strictly less
1687 than the second. */
1689 template<typename T>
1690 inline unsigned
1691 vec<T, va_heap, vl_ptr>::lower_bound (T obj,
1692 bool (*lessthan)(const T &, const T &))
1693 const
1695 return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
1698 template<typename T>
1699 inline bool
1700 vec<T, va_heap, vl_ptr>::using_auto_storage () const
1702 return m_vec->m_vecpfx.m_using_auto_storage;
1705 #if (GCC_VERSION >= 3000)
1706 # pragma GCC poison m_vec m_vecpfx m_vecdata
1707 #endif
1709 #endif // GCC_VEC_H