1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2016 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
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
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/>. */
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
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
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
106 The type, allocation and layout are specified when the vector is
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
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
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.
159 - The whole vector and control data are allocated in a single
161 - The whole vector may be re-allocated.
162 - Vector data may grow and shrink.
163 - Access and manipulation requires a pointer test and
165 - It requires 1 word of storage (prior to vector allocation).
167 An example of their use would be,
170 // A space-efficient vector of tree pointers in GC memory.
171 vec<tree, va_gc, vl_ptr> v;
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. */
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. */
212 friend struct va_gc_atomic
;
213 friend struct va_heap
;
215 unsigned m_alloc
: 31;
216 unsigned m_using_auto_storage
: 1;
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. */
225 vec_prefix::calculate_allocation (vec_prefix
*pfx
, unsigned reserve
,
229 return (pfx
? pfx
->m_num
: 0) + reserve
;
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. */
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. */
256 /* Heap vectors are frequently regular instances, so use the vl_ptr
258 typedef vl_ptr default_layout
;
261 static void reserve (vec
<T
, va_heap
, vl_embed
> *&, unsigned, bool
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 RESERVE is 0, no vector will be created. */
276 va_heap::reserve (vec
<T
, va_heap
, vl_embed
> *&v
, unsigned reserve
, bool exact
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. */
300 va_heap::release (vec
<T
, va_heap
, vl_embed
> *&v
)
305 if (GATHER_STATISTICS
)
306 v
->m_vecpfx
.release_overhead (v
, v
->allocated (), true);
312 /* Allocator type for GC vectors. Notice that we need the structure
313 declaration even if GC is not enabled. */
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
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
>
336 va_gc::release (vec
<T
, A
, vl_embed
> *&v
)
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. */
349 template<typename T
, typename A
>
351 va_gc::reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned reserve
, bool exact
355 = vec_prefix::calculate_allocation (v
? &v
->m_vecpfx
: 0, reserve
, exact
);
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
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
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). */
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. */
416 template <typename T
, typename A
, typename L
>
417 #if __cpp_constexpr >= 200704
420 operator vec
<T
, A
, L
> () { return vec
<T
, A
, L
>(); }
425 /* Embeddable vector. These vectors are suitable to be embedded
426 in other data structures so that they can be pre-allocated in a
427 contiguous memory block.
429 Embeddable vectors are implemented using the trailing array idiom,
430 thus they are not resizeable without changing the address of the
431 vector object itself. This means you cannot have variables or
432 fields of embeddable vector type -- always use a pointer to a
433 vector. The one exception is the final field of a structure, which
434 could be a vector type.
436 You will have to use the embedded_size & embedded_init calls to
437 create such objects, and they will not be resizeable (so the 'safe'
438 allocation variants are not available).
442 - The whole vector and control data are allocated in a single
443 contiguous block. It uses the trailing-vector idiom, so
444 allocation must reserve enough space for all the elements
445 in the vector plus its control data.
446 - The vector cannot be re-allocated.
447 - The vector cannot grow nor shrink.
448 - No indirections needed for access/manipulation.
449 - It requires 2 words of storage (prior to vector allocation). */
451 template<typename T
, typename A
>
452 struct GTY((user
)) vec
<T
, A
, vl_embed
>
455 unsigned allocated (void) const { return m_vecpfx
.m_alloc
; }
456 unsigned length (void) const { return m_vecpfx
.m_num
; }
457 bool is_empty (void) const { return m_vecpfx
.m_num
== 0; }
458 T
*address (void) { return m_vecdata
; }
459 const T
*address (void) const { return m_vecdata
; }
460 T
*begin () { return address (); }
461 const T
*begin () const { return address (); }
462 T
*end () { return address () + length (); }
463 const T
*end () const { return address () + length (); }
464 const T
&operator[] (unsigned) const;
465 T
&operator[] (unsigned);
467 bool space (unsigned) const;
468 bool iterate (unsigned, T
*) const;
469 bool iterate (unsigned, T
**) const;
470 vec
*copy (ALONE_CXX_MEM_STAT_INFO
) const;
471 void splice (const vec
&);
472 void splice (const vec
*src
);
473 T
*quick_push (const T
&);
475 void truncate (unsigned);
476 void quick_insert (unsigned, const T
&);
477 void ordered_remove (unsigned);
478 void unordered_remove (unsigned);
479 void block_remove (unsigned, unsigned);
480 void qsort (int (*) (const void *, const void *));
481 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
482 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
483 bool contains (const T
&search
) const;
484 static size_t embedded_size (unsigned);
485 void embedded_init (unsigned, unsigned = 0, unsigned = 0);
486 void quick_grow (unsigned len
);
487 void quick_grow_cleared (unsigned len
);
489 /* vec class can access our internal data and functions. */
490 template <typename
, typename
, typename
> friend struct vec
;
492 /* The allocator types also need access to our internals. */
494 friend struct va_gc_atomic
;
495 friend struct va_heap
;
497 /* FIXME - These fields should be private, but we need to cater to
498 compilers that have stricter notions of PODness for types. */
504 /* Convenience wrapper functions to use when dealing with pointers to
505 embedded vectors. Some functionality for these vectors must be
506 provided via free functions for these reasons:
508 1- The pointer may be NULL (e.g., before initial allocation).
510 2- When the vector needs to grow, it must be reallocated, so
511 the pointer will change its value.
513 Because of limitations with the current GC machinery, all vectors
514 in GC memory *must* be pointers. */
517 /* If V contains no room for NELEMS elements, return false. Otherwise,
519 template<typename T
, typename A
>
521 vec_safe_space (const vec
<T
, A
, vl_embed
> *v
, unsigned nelems
)
523 return v
? v
->space (nelems
) : nelems
== 0;
527 /* If V is NULL, return 0. Otherwise, return V->length(). */
528 template<typename T
, typename A
>
530 vec_safe_length (const vec
<T
, A
, vl_embed
> *v
)
532 return v
? v
->length () : 0;
536 /* If V is NULL, return NULL. Otherwise, return V->address(). */
537 template<typename T
, typename A
>
539 vec_safe_address (vec
<T
, A
, vl_embed
> *v
)
541 return v
? v
->address () : NULL
;
545 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
546 template<typename T
, typename A
>
548 vec_safe_is_empty (vec
<T
, A
, vl_embed
> *v
)
550 return v
? v
->is_empty () : true;
553 /* If V does not have space for NELEMS elements, call
554 V->reserve(NELEMS, EXACT). */
555 template<typename T
, typename A
>
557 vec_safe_reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
, bool exact
= false
560 bool extend
= nelems
? !vec_safe_space (v
, nelems
) : false;
562 A::reserve (v
, nelems
, exact PASS_MEM_STAT
);
566 template<typename T
, typename A
>
568 vec_safe_reserve_exact (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
571 return vec_safe_reserve (v
, nelems
, true PASS_MEM_STAT
);
575 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
576 is 0, V is initialized to NULL. */
578 template<typename T
, typename A
>
580 vec_alloc (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
583 vec_safe_reserve (v
, nelems
, false PASS_MEM_STAT
);
587 /* Free the GC memory allocated by vector V and set it to NULL. */
589 template<typename T
, typename A
>
591 vec_free (vec
<T
, A
, vl_embed
> *&v
)
597 /* Grow V to length LEN. Allocate it, if necessary. */
598 template<typename T
, typename A
>
600 vec_safe_grow (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
602 unsigned oldlen
= vec_safe_length (v
);
603 gcc_checking_assert (len
>= oldlen
);
604 vec_safe_reserve_exact (v
, len
- oldlen PASS_MEM_STAT
);
609 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
610 template<typename T
, typename A
>
612 vec_safe_grow_cleared (vec
<T
, A
, vl_embed
> *&v
, unsigned len CXX_MEM_STAT_INFO
)
614 unsigned oldlen
= vec_safe_length (v
);
615 vec_safe_grow (v
, len PASS_MEM_STAT
);
616 memset (&(v
->address ()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
620 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
621 template<typename T
, typename A
>
623 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
**ptr
)
626 return v
->iterate (ix
, ptr
);
634 template<typename T
, typename A
>
636 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
*ptr
)
639 return v
->iterate (ix
, ptr
);
648 /* If V has no room for one more element, reallocate it. Then call
649 V->quick_push(OBJ). */
650 template<typename T
, typename A
>
652 vec_safe_push (vec
<T
, A
, vl_embed
> *&v
, const T
&obj CXX_MEM_STAT_INFO
)
654 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
655 return v
->quick_push (obj
);
659 /* if V has no room for one more element, reallocate it. Then call
660 V->quick_insert(IX, OBJ). */
661 template<typename T
, typename A
>
663 vec_safe_insert (vec
<T
, A
, vl_embed
> *&v
, unsigned ix
, const T
&obj
666 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
667 v
->quick_insert (ix
, obj
);
671 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
672 template<typename T
, typename A
>
674 vec_safe_truncate (vec
<T
, A
, vl_embed
> *v
, unsigned size
)
681 /* If SRC is not NULL, return a pointer to a copy of it. */
682 template<typename T
, typename A
>
683 inline vec
<T
, A
, vl_embed
> *
684 vec_safe_copy (vec
<T
, A
, vl_embed
> *src CXX_MEM_STAT_INFO
)
686 return src
? src
->copy (ALONE_PASS_MEM_STAT
) : NULL
;
689 /* Copy the elements from SRC to the end of DST as if by memcpy.
690 Reallocate DST, if necessary. */
691 template<typename T
, typename A
>
693 vec_safe_splice (vec
<T
, A
, vl_embed
> *&dst
, const vec
<T
, A
, vl_embed
> *src
696 unsigned src_len
= vec_safe_length (src
);
699 vec_safe_reserve_exact (dst
, vec_safe_length (dst
) + src_len
705 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
706 size of the vector and so should be used with care. */
708 template<typename T
, typename A
>
710 vec_safe_contains (vec
<T
, A
, vl_embed
> *v
, const T
&search
)
712 return v
? v
->contains (search
) : false;
715 /* Index into vector. Return the IX'th element. IX must be in the
716 domain of the vector. */
718 template<typename T
, typename A
>
720 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
) const
722 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
723 return m_vecdata
[ix
];
726 template<typename T
, typename A
>
728 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
)
730 gcc_checking_assert (ix
< m_vecpfx
.m_num
);
731 return m_vecdata
[ix
];
735 /* Get the final element of the vector, which must not be empty. */
737 template<typename T
, typename A
>
739 vec
<T
, A
, vl_embed
>::last (void)
741 gcc_checking_assert (m_vecpfx
.m_num
> 0);
742 return (*this)[m_vecpfx
.m_num
- 1];
746 /* If this vector has space for NELEMS additional entries, return
747 true. You usually only need to use this if you are doing your
748 own vector reallocation, for instance on an embedded vector. This
749 returns true in exactly the same circumstances that vec::reserve
752 template<typename T
, typename A
>
754 vec
<T
, A
, vl_embed
>::space (unsigned nelems
) const
756 return m_vecpfx
.m_alloc
- m_vecpfx
.m_num
>= nelems
;
760 /* Return iteration condition and update PTR to point to the IX'th
761 element of this vector. Use this to iterate over the elements of a
764 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
767 template<typename T
, typename A
>
769 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
*ptr
) const
771 if (ix
< m_vecpfx
.m_num
)
773 *ptr
= m_vecdata
[ix
];
784 /* Return iteration condition and update *PTR to point to the
785 IX'th element of this vector. Use this to iterate over the
786 elements of a vector as follows,
788 for (ix = 0; v->iterate (ix, &ptr); ix++)
791 This variant is for vectors of objects. */
793 template<typename T
, typename A
>
795 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
**ptr
) const
797 if (ix
< m_vecpfx
.m_num
)
799 *ptr
= CONST_CAST (T
*, &m_vecdata
[ix
]);
810 /* Return a pointer to a copy of this vector. */
812 template<typename T
, typename A
>
813 inline vec
<T
, A
, vl_embed
> *
814 vec
<T
, A
, vl_embed
>::copy (ALONE_MEM_STAT_DECL
) const
816 vec
<T
, A
, vl_embed
> *new_vec
= NULL
;
817 unsigned len
= length ();
820 vec_alloc (new_vec
, len PASS_MEM_STAT
);
821 new_vec
->embedded_init (len
, len
);
822 memcpy (new_vec
->address (), m_vecdata
, sizeof (T
) * len
);
828 /* Copy the elements from SRC to the end of this vector as if by memcpy.
829 The vector must have sufficient headroom available. */
831 template<typename T
, typename A
>
833 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> &src
)
835 unsigned len
= src
.length ();
838 gcc_checking_assert (space (len
));
839 memcpy (address () + length (), src
.address (), len
* sizeof (T
));
840 m_vecpfx
.m_num
+= len
;
844 template<typename T
, typename A
>
846 vec
<T
, A
, vl_embed
>::splice (const vec
<T
, A
, vl_embed
> *src
)
853 /* Push OBJ (a new element) onto the end of the vector. There must be
854 sufficient space in the vector. Return a pointer to the slot
855 where OBJ was inserted. */
857 template<typename T
, typename A
>
859 vec
<T
, A
, vl_embed
>::quick_push (const T
&obj
)
861 gcc_checking_assert (space (1));
862 T
*slot
= &m_vecdata
[m_vecpfx
.m_num
++];
868 /* Pop and return the last element off the end of the vector. */
870 template<typename T
, typename A
>
872 vec
<T
, A
, vl_embed
>::pop (void)
874 gcc_checking_assert (length () > 0);
875 return m_vecdata
[--m_vecpfx
.m_num
];
879 /* Set the length of the vector to SIZE. The new length must be less
880 than or equal to the current length. This is an O(1) operation. */
882 template<typename T
, typename A
>
884 vec
<T
, A
, vl_embed
>::truncate (unsigned size
)
886 gcc_checking_assert (length () >= size
);
887 m_vecpfx
.m_num
= size
;
891 /* Insert an element, OBJ, at the IXth position of this vector. There
892 must be sufficient space. */
894 template<typename T
, typename A
>
896 vec
<T
, A
, vl_embed
>::quick_insert (unsigned ix
, const T
&obj
)
898 gcc_checking_assert (length () < allocated ());
899 gcc_checking_assert (ix
<= length ());
900 T
*slot
= &m_vecdata
[ix
];
901 memmove (slot
+ 1, slot
, (m_vecpfx
.m_num
++ - ix
) * sizeof (T
));
906 /* Remove an element from the IXth position of this vector. Ordering of
907 remaining elements is preserved. This is an O(N) operation due to
910 template<typename T
, typename A
>
912 vec
<T
, A
, vl_embed
>::ordered_remove (unsigned ix
)
914 gcc_checking_assert (ix
< length ());
915 T
*slot
= &m_vecdata
[ix
];
916 memmove (slot
, slot
+ 1, (--m_vecpfx
.m_num
- ix
) * sizeof (T
));
920 /* Remove an element from the IXth position of this vector. Ordering of
921 remaining elements is destroyed. This is an O(1) operation. */
923 template<typename T
, typename A
>
925 vec
<T
, A
, vl_embed
>::unordered_remove (unsigned ix
)
927 gcc_checking_assert (ix
< length ());
928 m_vecdata
[ix
] = m_vecdata
[--m_vecpfx
.m_num
];
932 /* Remove LEN elements starting at the IXth. Ordering is retained.
933 This is an O(N) operation due to memmove. */
935 template<typename T
, typename A
>
937 vec
<T
, A
, vl_embed
>::block_remove (unsigned ix
, unsigned len
)
939 gcc_checking_assert (ix
+ len
<= length ());
940 T
*slot
= &m_vecdata
[ix
];
941 m_vecpfx
.m_num
-= len
;
942 memmove (slot
, slot
+ len
, (m_vecpfx
.m_num
- ix
) * sizeof (T
));
946 /* Sort the contents of this vector with qsort. CMP is the comparison
947 function to pass to qsort. */
949 template<typename T
, typename A
>
951 vec
<T
, A
, vl_embed
>::qsort (int (*cmp
) (const void *, const void *))
954 ::qsort (address (), length (), sizeof (T
), cmp
);
958 /* Search the contents of the sorted vector with a binary search.
959 CMP is the comparison function to pass to bsearch. */
961 template<typename T
, typename A
>
963 vec
<T
, A
, vl_embed
>::bsearch (const void *key
,
964 int (*compar
) (const void *, const void *))
966 const void *base
= this->address ();
967 size_t nmemb
= this->length ();
968 size_t size
= sizeof (T
);
969 /* The following is a copy of glibc stdlib-bsearch.h. */
979 p
= (const void *) (((const char *) base
) + (idx
* size
));
980 comparison
= (*compar
) (key
, p
);
983 else if (comparison
> 0)
986 return (T
*)const_cast<void *>(p
);
992 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
993 size of the vector and so should be used with care. */
995 template<typename T
, typename A
>
997 vec
<T
, A
, vl_embed
>::contains (const T
&search
) const
999 unsigned int len
= length ();
1000 for (unsigned int i
= 0; i
< len
; i
++)
1001 if ((*this)[i
] == search
)
1007 /* Find and return the first position in which OBJ could be inserted
1008 without changing the ordering of this vector. LESSTHAN is a
1009 function that returns true if the first argument is strictly less
1012 template<typename T
, typename A
>
1014 vec
<T
, A
, vl_embed
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&))
1017 unsigned int len
= length ();
1018 unsigned int half
, middle
;
1019 unsigned int first
= 0;
1025 T middle_elem
= (*this)[middle
];
1026 if (lessthan (middle_elem
, obj
))
1030 len
= len
- half
- 1;
1039 /* Return the number of bytes needed to embed an instance of an
1040 embeddable vec inside another data structure.
1042 Use these methods to determine the required size and initialization
1043 of a vector V of type T embedded within another structure (as the
1046 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1047 void v->embedded_init (unsigned alloc, unsigned num);
1049 These allow the caller to perform the memory allocation. */
1051 template<typename T
, typename A
>
1053 vec
<T
, A
, vl_embed
>::embedded_size (unsigned alloc
)
1055 typedef vec
<T
, A
, vl_embed
> vec_embedded
;
1056 return offsetof (vec_embedded
, m_vecdata
) + alloc
* sizeof (T
);
1060 /* Initialize the vector to contain room for ALLOC elements and
1061 NUM active elements. */
1063 template<typename T
, typename A
>
1065 vec
<T
, A
, vl_embed
>::embedded_init (unsigned alloc
, unsigned num
, unsigned aut
)
1067 m_vecpfx
.m_alloc
= alloc
;
1068 m_vecpfx
.m_using_auto_storage
= aut
;
1069 m_vecpfx
.m_num
= num
;
1073 /* Grow the vector to a specific length. LEN must be as long or longer than
1074 the current length. The new elements are uninitialized. */
1076 template<typename T
, typename A
>
1078 vec
<T
, A
, vl_embed
>::quick_grow (unsigned len
)
1080 gcc_checking_assert (length () <= len
&& len
<= m_vecpfx
.m_alloc
);
1081 m_vecpfx
.m_num
= len
;
1085 /* Grow the vector to a specific length. LEN must be as long or longer than
1086 the current length. The new elements are initialized to zero. */
1088 template<typename T
, typename A
>
1090 vec
<T
, A
, vl_embed
>::quick_grow_cleared (unsigned len
)
1092 unsigned oldlen
= length ();
1094 memset (&(address ()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
1098 /* Garbage collection support for vec<T, A, vl_embed>. */
1100 template<typename T
>
1102 gt_ggc_mx (vec
<T
, va_gc
> *v
)
1104 extern void gt_ggc_mx (T
&);
1105 for (unsigned i
= 0; i
< v
->length (); i
++)
1106 gt_ggc_mx ((*v
)[i
]);
1109 template<typename T
>
1111 gt_ggc_mx (vec
<T
, va_gc_atomic
, vl_embed
> *v ATTRIBUTE_UNUSED
)
1113 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1118 /* PCH support for vec<T, A, vl_embed>. */
1120 template<typename T
, typename A
>
1122 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
)
1124 extern void gt_pch_nx (T
&);
1125 for (unsigned i
= 0; i
< v
->length (); i
++)
1126 gt_pch_nx ((*v
)[i
]);
1129 template<typename T
, typename A
>
1131 gt_pch_nx (vec
<T
*, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1133 for (unsigned i
= 0; i
< v
->length (); i
++)
1134 op (&((*v
)[i
]), cookie
);
1137 template<typename T
, typename A
>
1139 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1141 extern void gt_pch_nx (T
*, gt_pointer_operator
, void *);
1142 for (unsigned i
= 0; i
< v
->length (); i
++)
1143 gt_pch_nx (&((*v
)[i
]), op
, cookie
);
1147 /* Space efficient vector. These vectors can grow dynamically and are
1148 allocated together with their control data. They are suited to be
1149 included in data structures. Prior to initial allocation, they
1150 only take a single word of storage.
1152 These vectors are implemented as a pointer to an embeddable vector.
1153 The semantics allow for this pointer to be NULL to represent empty
1154 vectors. This way, empty vectors occupy minimal space in the
1155 structure containing them.
1159 - The whole vector and control data are allocated in a single
1161 - The whole vector may be re-allocated.
1162 - Vector data may grow and shrink.
1163 - Access and manipulation requires a pointer test and
1165 - It requires 1 word of storage (prior to vector allocation).
1170 These vectors must be PODs because they are stored in unions.
1171 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1172 As long as we use C++03, we cannot have constructors nor
1173 destructors in classes that are stored in unions. */
1175 template<typename T
>
1176 struct vec
<T
, va_heap
, vl_ptr
>
1179 /* Memory allocation and deallocation for the embedded vector.
1180 Needed because we cannot have proper ctors/dtors defined. */
1181 void create (unsigned nelems CXX_MEM_STAT_INFO
);
1182 void release (void);
1184 /* Vector operations. */
1185 bool exists (void) const
1186 { return m_vec
!= NULL
; }
1188 bool is_empty (void) const
1189 { return m_vec
? m_vec
->is_empty () : true; }
1191 unsigned length (void) const
1192 { return m_vec
? m_vec
->length () : 0; }
1195 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1197 const T
*address (void) const
1198 { return m_vec
? m_vec
->m_vecdata
: NULL
; }
1200 T
*begin () { return address (); }
1201 const T
*begin () const { return address (); }
1202 T
*end () { return begin () + length (); }
1203 const T
*end () const { return begin () + length (); }
1204 const T
&operator[] (unsigned ix
) const
1205 { return (*m_vec
)[ix
]; }
1207 bool operator!=(const vec
&other
) const
1208 { return !(*this == other
); }
1210 bool operator==(const vec
&other
) const
1211 { return address () == other
.address (); }
1213 T
&operator[] (unsigned ix
)
1214 { return (*m_vec
)[ix
]; }
1217 { return m_vec
->last (); }
1219 bool space (int nelems
) const
1220 { return m_vec
? m_vec
->space (nelems
) : nelems
== 0; }
1222 bool iterate (unsigned ix
, T
*p
) const;
1223 bool iterate (unsigned ix
, T
**p
) const;
1224 vec
copy (ALONE_CXX_MEM_STAT_INFO
) const;
1225 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO
);
1226 bool reserve_exact (unsigned CXX_MEM_STAT_INFO
);
1227 void splice (const vec
&);
1228 void safe_splice (const vec
& CXX_MEM_STAT_INFO
);
1229 T
*quick_push (const T
&);
1230 T
*safe_push (const T
&CXX_MEM_STAT_INFO
);
1232 void truncate (unsigned);
1233 void safe_grow (unsigned CXX_MEM_STAT_INFO
);
1234 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO
);
1235 void quick_grow (unsigned);
1236 void quick_grow_cleared (unsigned);
1237 void quick_insert (unsigned, const T
&);
1238 void safe_insert (unsigned, const T
& CXX_MEM_STAT_INFO
);
1239 void ordered_remove (unsigned);
1240 void unordered_remove (unsigned);
1241 void block_remove (unsigned, unsigned);
1242 void qsort (int (*) (const void *, const void *));
1243 T
*bsearch (const void *key
, int (*compar
)(const void *, const void *));
1244 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
1245 bool contains (const T
&search
) const;
1247 bool using_auto_storage () const;
1249 /* FIXME - This field should be private, but we need to cater to
1250 compilers that have stricter notions of PODness for types. */
1251 vec
<T
, va_heap
, vl_embed
> *m_vec
;
1255 /* auto_vec is a subclass of vec that automatically manages creating and
1256 releasing the internal vector. If N is non zero then it has N elements of
1257 internal storage. The default is no internal storage, and you probably only
1258 want to ask for internal storage for vectors on the stack because if the
1259 size of the vector is larger than the internal storage that space is wasted.
1261 template<typename T
, size_t N
= 0>
1262 class auto_vec
: public vec
<T
, va_heap
>
1267 m_auto
.embedded_init (MAX (N
, 2), 0, 1);
1268 this->m_vec
= &m_auto
;
1277 vec
<T
, va_heap
, vl_embed
> m_auto
;
1278 T m_data
[MAX (N
- 1, 1)];
1281 /* auto_vec is a sub class of vec whose storage is released when it is
1283 template<typename T
>
1284 class auto_vec
<T
, 0> : public vec
<T
, va_heap
>
1287 auto_vec () { this->m_vec
= NULL
; }
1288 auto_vec (size_t n
) { this->create (n
); }
1289 ~auto_vec () { this->release (); }
1293 /* Allocate heap memory for pointer V and create the internal vector
1294 with space for NELEMS elements. If NELEMS is 0, the internal
1295 vector is initialized to empty. */
1297 template<typename T
>
1299 vec_alloc (vec
<T
> *&v
, unsigned nelems CXX_MEM_STAT_INFO
)
1302 v
->create (nelems PASS_MEM_STAT
);
1306 /* Conditionally allocate heap memory for VEC and its internal vector. */
1308 template<typename T
>
1310 vec_check_alloc (vec
<T
, va_heap
> *&vec
, unsigned nelems CXX_MEM_STAT_INFO
)
1313 vec_alloc (vec
, nelems PASS_MEM_STAT
);
1317 /* Free the heap memory allocated by vector V and set it to NULL. */
1319 template<typename T
>
1321 vec_free (vec
<T
> *&v
)
1332 /* Return iteration condition and update PTR to point to the IX'th
1333 element of this vector. Use this to iterate over the elements of a
1336 for (ix = 0; v.iterate (ix, &ptr); ix++)
1339 template<typename T
>
1341 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
*ptr
) const
1344 return m_vec
->iterate (ix
, ptr
);
1353 /* Return iteration condition and update *PTR to point to the
1354 IX'th element of this vector. Use this to iterate over the
1355 elements of a vector as follows,
1357 for (ix = 0; v->iterate (ix, &ptr); ix++)
1360 This variant is for vectors of objects. */
1362 template<typename T
>
1364 vec
<T
, va_heap
, vl_ptr
>::iterate (unsigned ix
, T
**ptr
) const
1367 return m_vec
->iterate (ix
, ptr
);
1376 /* Convenience macro for forward iteration. */
1377 #define FOR_EACH_VEC_ELT(V, I, P) \
1378 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1380 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1381 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1383 /* Likewise, but start from FROM rather than 0. */
1384 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1385 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1387 /* Convenience macro for reverse iteration. */
1388 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1389 for (I = (V).length () - 1; \
1390 (V).iterate ((I), &(P)); \
1393 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1394 for (I = vec_safe_length (V) - 1; \
1395 vec_safe_iterate ((V), (I), &(P)); \
1399 /* Return a copy of this vector. */
1401 template<typename T
>
1402 inline vec
<T
, va_heap
, vl_ptr
>
1403 vec
<T
, va_heap
, vl_ptr
>::copy (ALONE_MEM_STAT_DECL
) const
1405 vec
<T
, va_heap
, vl_ptr
> new_vec
= vNULL
;
1407 new_vec
.m_vec
= m_vec
->copy ();
1412 /* Ensure that the vector has at least RESERVE slots available (if
1413 EXACT is false), or exactly RESERVE slots available (if EXACT is
1416 This may create additional headroom if EXACT is false.
1418 Note that this can cause the embedded vector to be reallocated.
1419 Returns true iff reallocation actually occurred. */
1421 template<typename T
>
1423 vec
<T
, va_heap
, vl_ptr
>::reserve (unsigned nelems
, bool exact MEM_STAT_DECL
)
1428 /* For now play a game with va_heap::reserve to hide our auto storage if any,
1429 this is necessary because it doesn't have enough information to know the
1430 embedded vector is in auto storage, and so should not be freed. */
1431 vec
<T
, va_heap
, vl_embed
> *oldvec
= m_vec
;
1432 unsigned int oldsize
= 0;
1433 bool handle_auto_vec
= m_vec
&& using_auto_storage ();
1434 if (handle_auto_vec
)
1437 oldsize
= oldvec
->length ();
1441 va_heap::reserve (m_vec
, nelems
, exact PASS_MEM_STAT
);
1442 if (handle_auto_vec
)
1444 memcpy (m_vec
->address (), oldvec
->address (), sizeof (T
) * oldsize
);
1445 m_vec
->m_vecpfx
.m_num
= oldsize
;
1452 /* Ensure that this vector has exactly NELEMS slots available. This
1453 will not create additional headroom. Note this can cause the
1454 embedded vector to be reallocated. Returns true iff reallocation
1455 actually occurred. */
1457 template<typename T
>
1459 vec
<T
, va_heap
, vl_ptr
>::reserve_exact (unsigned nelems MEM_STAT_DECL
)
1461 return reserve (nelems
, true PASS_MEM_STAT
);
1465 /* Create the internal vector and reserve NELEMS for it. This is
1466 exactly like vec::reserve, but the internal vector is
1467 unconditionally allocated from scratch. The old one, if it
1468 existed, is lost. */
1470 template<typename T
>
1472 vec
<T
, va_heap
, vl_ptr
>::create (unsigned nelems MEM_STAT_DECL
)
1476 reserve_exact (nelems PASS_MEM_STAT
);
1480 /* Free the memory occupied by the embedded vector. */
1482 template<typename T
>
1484 vec
<T
, va_heap
, vl_ptr
>::release (void)
1489 if (using_auto_storage ())
1491 m_vec
->m_vecpfx
.m_num
= 0;
1495 va_heap::release (m_vec
);
1498 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1499 SRC and this vector must be allocated with the same memory
1500 allocation mechanism. This vector is assumed to have sufficient
1501 headroom available. */
1503 template<typename T
>
1505 vec
<T
, va_heap
, vl_ptr
>::splice (const vec
<T
, va_heap
, vl_ptr
> &src
)
1508 m_vec
->splice (*(src
.m_vec
));
1512 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1513 SRC and this vector must be allocated with the same mechanism.
1514 If there is not enough headroom in this vector, it will be reallocated
1517 template<typename T
>
1519 vec
<T
, va_heap
, vl_ptr
>::safe_splice (const vec
<T
, va_heap
, vl_ptr
> &src
1524 reserve_exact (src
.length ());
1530 /* Push OBJ (a new element) onto the end of the vector. There must be
1531 sufficient space in the vector. Return a pointer to the slot
1532 where OBJ was inserted. */
1534 template<typename T
>
1536 vec
<T
, va_heap
, vl_ptr
>::quick_push (const T
&obj
)
1538 return m_vec
->quick_push (obj
);
1542 /* Push a new element OBJ onto the end of this vector. Reallocates
1543 the embedded vector, if needed. Return a pointer to the slot where
1544 OBJ was inserted. */
1546 template<typename T
>
1548 vec
<T
, va_heap
, vl_ptr
>::safe_push (const T
&obj MEM_STAT_DECL
)
1550 reserve (1, false PASS_MEM_STAT
);
1551 return quick_push (obj
);
1555 /* Pop and return the last element off the end of the vector. */
1557 template<typename T
>
1559 vec
<T
, va_heap
, vl_ptr
>::pop (void)
1561 return m_vec
->pop ();
1565 /* Set the length of the vector to LEN. The new length must be less
1566 than or equal to the current length. This is an O(1) operation. */
1568 template<typename T
>
1570 vec
<T
, va_heap
, vl_ptr
>::truncate (unsigned size
)
1573 m_vec
->truncate (size
);
1575 gcc_checking_assert (size
== 0);
1579 /* Grow the vector to a specific length. LEN must be as long or
1580 longer than the current length. The new elements are
1581 uninitialized. Reallocate the internal vector, if needed. */
1583 template<typename T
>
1585 vec
<T
, va_heap
, vl_ptr
>::safe_grow (unsigned len MEM_STAT_DECL
)
1587 unsigned oldlen
= length ();
1588 gcc_checking_assert (oldlen
<= len
);
1589 reserve_exact (len
- oldlen PASS_MEM_STAT
);
1591 m_vec
->quick_grow (len
);
1593 gcc_checking_assert (len
== 0);
1597 /* Grow the embedded vector to a specific length. LEN must be as
1598 long or longer than the current length. The new elements are
1599 initialized to zero. Reallocate the internal vector, if needed. */
1601 template<typename T
>
1603 vec
<T
, va_heap
, vl_ptr
>::safe_grow_cleared (unsigned len MEM_STAT_DECL
)
1605 unsigned oldlen
= length ();
1606 safe_grow (len PASS_MEM_STAT
);
1607 memset (&(address ()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
1611 /* Same as vec::safe_grow but without reallocation of the internal vector.
1612 If the vector cannot be extended, a runtime assertion will be triggered. */
1614 template<typename T
>
1616 vec
<T
, va_heap
, vl_ptr
>::quick_grow (unsigned len
)
1618 gcc_checking_assert (m_vec
);
1619 m_vec
->quick_grow (len
);
1623 /* Same as vec::quick_grow_cleared but without reallocation of the
1624 internal vector. If the vector cannot be extended, a runtime
1625 assertion will be triggered. */
1627 template<typename T
>
1629 vec
<T
, va_heap
, vl_ptr
>::quick_grow_cleared (unsigned len
)
1631 gcc_checking_assert (m_vec
);
1632 m_vec
->quick_grow_cleared (len
);
1636 /* Insert an element, OBJ, at the IXth position of this vector. There
1637 must be sufficient space. */
1639 template<typename T
>
1641 vec
<T
, va_heap
, vl_ptr
>::quick_insert (unsigned ix
, const T
&obj
)
1643 m_vec
->quick_insert (ix
, obj
);
1647 /* Insert an element, OBJ, at the IXth position of the vector.
1648 Reallocate the embedded vector, if necessary. */
1650 template<typename T
>
1652 vec
<T
, va_heap
, vl_ptr
>::safe_insert (unsigned ix
, const T
&obj MEM_STAT_DECL
)
1654 reserve (1, false PASS_MEM_STAT
);
1655 quick_insert (ix
, obj
);
1659 /* Remove an element from the IXth position of this vector. Ordering of
1660 remaining elements is preserved. This is an O(N) operation due to
1663 template<typename T
>
1665 vec
<T
, va_heap
, vl_ptr
>::ordered_remove (unsigned ix
)
1667 m_vec
->ordered_remove (ix
);
1671 /* Remove an element from the IXth position of this vector. Ordering
1672 of remaining elements is destroyed. This is an O(1) operation. */
1674 template<typename T
>
1676 vec
<T
, va_heap
, vl_ptr
>::unordered_remove (unsigned ix
)
1678 m_vec
->unordered_remove (ix
);
1682 /* Remove LEN elements starting at the IXth. Ordering is retained.
1683 This is an O(N) operation due to memmove. */
1685 template<typename T
>
1687 vec
<T
, va_heap
, vl_ptr
>::block_remove (unsigned ix
, unsigned len
)
1689 m_vec
->block_remove (ix
, len
);
1693 /* Sort the contents of this vector with qsort. CMP is the comparison
1694 function to pass to qsort. */
1696 template<typename T
>
1698 vec
<T
, va_heap
, vl_ptr
>::qsort (int (*cmp
) (const void *, const void *))
1705 /* Search the contents of the sorted vector with a binary search.
1706 CMP is the comparison function to pass to bsearch. */
1708 template<typename T
>
1710 vec
<T
, va_heap
, vl_ptr
>::bsearch (const void *key
,
1711 int (*cmp
) (const void *, const void *))
1714 return m_vec
->bsearch (key
, cmp
);
1719 /* Find and return the first position in which OBJ could be inserted
1720 without changing the ordering of this vector. LESSTHAN is a
1721 function that returns true if the first argument is strictly less
1724 template<typename T
>
1726 vec
<T
, va_heap
, vl_ptr
>::lower_bound (T obj
,
1727 bool (*lessthan
)(const T
&, const T
&))
1730 return m_vec
? m_vec
->lower_bound (obj
, lessthan
) : 0;
1733 /* Return true if SEARCH is an element of V. Note that this is O(N) in the
1734 size of the vector and so should be used with care. */
1736 template<typename T
>
1738 vec
<T
, va_heap
, vl_ptr
>::contains (const T
&search
) const
1740 return m_vec
? m_vec
->contains (search
) : false;
1743 template<typename T
>
1745 vec
<T
, va_heap
, vl_ptr
>::using_auto_storage () const
1747 return m_vec
->m_vecpfx
.m_using_auto_storage
;
1750 /* Release VEC and call release of all element vectors. */
1752 template<typename T
>
1754 release_vec_vec (vec
<vec
<T
> > &vec
)
1756 for (unsigned i
= 0; i
< vec
.length (); i
++)
1762 #if (GCC_VERSION >= 3000)
1763 # pragma GCC poison m_vec m_vecpfx m_vecdata