1 /* Vector API for GNU compiler.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Nathan Sidwell <nathan@codesourcery.com>
5 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
26 /* FIXME - When compiling some of the gen* binaries, we cannot enable GC
27 support because the headers generated by gengtype are still not
28 present. In particular, the header file gtype-desc.h is missing,
29 so compilation may fail if we try to include ggc.h.
31 Since we use some of those declarations, we need to provide them
32 (even if the GC-based templates are not used). This is not a
33 problem because the code that runs before gengtype is built will
34 never need to use GC vectors. But it does force us to declare
35 these functions more than once. */
37 #define VEC_GC_ENABLED 0
39 #define VEC_GC_ENABLED 1
40 #endif // GENERATOR_FILE
42 #include "statistics.h" // For CXX_MEM_STAT_INFO.
48 /* Even if we think that GC is not enabled, the test that sets it is
49 weak. There are files compiled with -DGENERATOR_FILE that already
50 include ggc.h. We only need to provide these definitions if ggc.h
51 has not been included. Sigh. */
52 extern void ggc_free (void *);
53 extern size_t ggc_round_alloc_size (size_t requested_size
);
54 extern void *ggc_internal_cleared_alloc_stat (size_t MEM_STAT_DECL
)
56 extern void *ggc_realloc_stat (void *, size_t MEM_STAT_DECL
);
58 #endif // VEC_GC_ENABLED
60 /* Templated vector type and associated interfaces.
62 The interface functions are typesafe and use inline functions,
63 sometimes backed by out-of-line generic functions. The vectors are
64 designed to interoperate with the GTY machinery.
66 There are both 'index' and 'iterate' accessors. The index accessor
67 is implemented by operator[]. The iterator returns a boolean
68 iteration condition and updates the iteration variable passed by
69 reference. Because the iterator will be inlined, the address-of
70 can be optimized away.
72 Each operation that increases the number of active elements is
73 available in 'quick' and 'safe' variants. The former presumes that
74 there is sufficient allocated space for the operation to succeed
75 (it dies if there is not). The latter will reallocate the
76 vector, if needed. Reallocation causes an exponential increase in
77 vector size. If you know you will be adding N elements, it would
78 be more efficient to use the reserve operation before adding the
79 elements with the 'quick' operation. This will ensure there are at
80 least as many elements as you ask for, it will exponentially
81 increase if there are too few spare slots. If you want reserve a
82 specific number of slots, but do not want the exponential increase
83 (for instance, you know this is the last allocation), use the
84 reserve_exact operation. You can also create a vector of a
85 specific size from the get go.
87 You should prefer the push and pop operations, as they append and
88 remove from the end of the vector. If you need to remove several
89 items in one go, use the truncate operation. The insert and remove
90 operations allow you to change elements in the middle of the
91 vector. There are two remove operations, one which preserves the
92 element ordering 'ordered_remove', and one which does not
93 'unordered_remove'. The latter function copies the end element
94 into the removed slot, rather than invoke a memmove operation. The
95 'lower_bound' function will determine where to place an item in the
96 array using insert that will maintain sorted order.
98 Vectors are template types with three arguments: the type of the
99 elements in the vector, the allocation strategy, and the physical
102 Four allocation strategies are supported:
104 - Heap: allocation is done using malloc/free. This is the
105 default allocation strategy.
107 - Stack: allocation is done using alloca.
109 - GC: allocation is done using ggc_alloc/ggc_free.
111 - GC atomic: same as GC with the exception that the elements
112 themselves are assumed to be of an atomic type that does
113 not need to be garbage collected. This means that marking
114 routines do not need to traverse the array marking the
115 individual elements. This increases the performance of
118 Two physical layouts are supported:
120 - Embedded: The vector is structured using the trailing array
121 idiom. The last member of the structure is an array of size
122 1. When the vector is initially allocated, a single memory
123 block is created to hold the vector's control data and the
124 array of elements. These vectors cannot grow without
125 reallocation (see discussion on embeddable vectors below).
127 - Space efficient: The vector is structured as a pointer to an
128 embedded vector. This is the default layout. It means that
129 vectors occupy a single word of storage before initial
130 allocation. Vectors are allowed to grow (the internal
131 pointer is reallocated but the main vector instance does not
134 The type, allocation and layout are specified when the vector is
137 If you need to directly manipulate a vector, then the 'address'
138 accessor will return the address of the start of the vector. Also
139 the 'space' predicate will tell you whether there is spare capacity
140 in the vector. You will not normally need to use these two functions.
142 Notes on the different layout strategies
144 * Embeddable vectors (vec<T, A, vl_embed>)
146 These vectors are suitable to be embedded in other data
147 structures so that they can be pre-allocated in a contiguous
150 Embeddable vectors are implemented using the trailing array
151 idiom, thus they are not resizeable without changing the address
152 of the vector object itself. This means you cannot have
153 variables or fields of embeddable vector type -- always use a
154 pointer to a vector. The one exception is the final field of a
155 structure, which could be a vector type.
157 You will have to use the embedded_size & embedded_init calls to
158 create such objects, and they will not be resizeable (so the
159 'safe' allocation variants are not available).
161 Properties of embeddable vectors:
163 - The whole vector and control data are allocated in a single
164 contiguous block. It uses the trailing-vector idiom, so
165 allocation must reserve enough space for all the elements
166 in the vector plus its control data.
167 - The vector cannot be re-allocated.
168 - The vector cannot grow nor shrink.
169 - No indirections needed for access/manipulation.
170 - It requires 2 words of storage (prior to vector allocation).
173 * Space efficient vector (vec<T, A, vl_ptr>)
175 These vectors can grow dynamically and are allocated together
176 with their control data. They are suited to be included in data
177 structures. Prior to initial allocation, they only take a single
180 These vectors are implemented as a pointer to embeddable vectors.
181 The semantics allow for this pointer to be NULL to represent
182 empty vectors. This way, empty vectors occupy minimal space in
183 the structure containing them.
187 - The whole vector and control data are allocated in a single
189 - The whole vector may be re-allocated.
190 - Vector data may grow and shrink.
191 - Access and manipulation requires a pointer test and
193 - It requires 1 word of storage (prior to vector allocation).
195 An example of their use would be,
198 // A space-efficient vector of tree pointers in GC memory.
199 vec<tree, va_gc, vl_ptr> v;
204 if (s->v.length ()) { we have some contents }
205 s->v.safe_push (decl); // append some decl onto the end
206 for (ix = 0; s->v.iterate (ix, &elt); ix++)
207 { do something with elt }
210 /* Support function for statistics. */
211 extern void dump_vec_loc_statistics (void);
214 /* Control data for vectors. This contains the number of allocated
215 and used slots inside a vector. */
220 /* Memory allocation support routines in vec.c. */
221 void register_overhead (size_t, const char *, int, const char *);
222 void release_overhead (void);
223 static unsigned calculate_allocation (vec_prefix
*, unsigned, bool);
225 /* Note that vec_prefix should be a base class for vec, but we use
226 offsetof() on vector fields of tree structures (e.g.,
227 tree_binfo::base_binfos), and offsetof only supports base types.
229 To compensate, we make vec_prefix a field inside vec and make
230 vec a friend class of vec_prefix so it can access its fields. */
231 template <typename
, typename
, typename
> friend class vec
;
233 /* The allocator types also need access to our internals. */
235 friend struct va_gc_atomic
;
236 friend struct va_heap
;
237 friend struct va_stack
;
243 template<typename
, typename
, typename
> class vec
;
245 /* Valid vector layouts
247 vl_embed - Embeddable vector that uses the trailing array idiom.
248 vl_ptr - Space efficient vector that uses a pointer to an
249 embeddable vector. */
254 /* Types of supported allocations
256 va_heap - Allocation uses malloc/free.
257 va_gc - Allocation uses ggc_alloc.
258 va_gc_atomic - Same as GC, but individual elements of the array
259 do not need to be marked during collection.
260 va_stack - Allocation uses alloca. */
262 /* Allocator type for heap vectors. */
265 /* Heap vectors are frequently regular instances, so use the vl_ptr
267 typedef vl_ptr default_layout
;
270 static void reserve (vec
<T
, va_heap
, vl_embed
> *&, unsigned, bool
274 static void release (vec
<T
, va_heap
, vl_embed
> *&);
278 /* Allocator for heap memory. Ensure there are at least RESERVE free
279 slots in V. If EXACT is true, grow exactly, else grow
280 exponentially. As a special case, if the vector had not been
281 allocated and and RESERVE is 0, no vector will be created. */
285 va_heap::reserve (vec
<T
, va_heap
, vl_embed
> *&v
, unsigned reserve
, bool exact
288 unsigned alloc
= vec_prefix::calculate_allocation (v
? &v
->pfx_
: 0, reserve
,
296 if (GATHER_STATISTICS
&& v
)
297 v
->pfx_
.release_overhead ();
299 size_t size
= vec
<T
, va_heap
, vl_embed
>::embedded_size (alloc
);
300 unsigned nelem
= v
? v
->length () : 0;
301 v
= static_cast <vec
<T
, va_heap
, vl_embed
> *> (xrealloc (v
, size
));
302 v
->embedded_init (alloc
, nelem
);
304 if (GATHER_STATISTICS
)
305 v
->pfx_
.register_overhead (size FINAL_PASS_MEM_STAT
);
309 /* Free the heap space allocated for vector V. */
313 va_heap::release (vec
<T
, va_heap
, vl_embed
> *&v
)
315 if (GATHER_STATISTICS
)
316 v
->pfx_
.release_overhead ();
322 /* Allocator type for GC vectors. Notice that we need the structure
323 declaration even if GC is not enabled. */
327 /* Use vl_embed as the default layout for GC vectors. Due to GTY
328 limitations, GC vectors must always be pointers, so it is more
329 efficient to use a pointer to the vl_embed layout, rather than
330 using a pointer to a pointer as would be the case with vl_ptr. */
331 typedef vl_embed default_layout
;
333 template<typename T
, typename A
>
334 static void reserve (vec
<T
, A
, vl_embed
> *&, unsigned, bool
337 template<typename T
, typename A
>
338 static void release (vec
<T
, A
, vl_embed
> *&v
) { v
= NULL
; }
342 /* Allocator for GC memory. Ensure there are at least RESERVE free
343 slots in V. If EXACT is true, grow exactly, else grow
344 exponentially. As a special case, if the vector had not been
345 allocated and and RESERVE is 0, no vector will be created. */
347 template<typename T
, typename A
>
349 va_gc::reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned reserve
, bool exact
352 unsigned alloc
= vec_prefix::calculate_allocation (v
? &v
->pfx_
: 0, reserve
,
361 /* Calculate the amount of space we want. */
362 size_t size
= vec
<T
, A
, vl_embed
>::embedded_size (alloc
);
364 /* Ask the allocator how much space it will really give us. */
365 size
= ggc_round_alloc_size (size
);
367 /* Adjust the number of slots accordingly. */
368 size_t vec_offset
= sizeof (vec_prefix
);
369 size_t elt_size
= sizeof (T
);
370 alloc
= (size
- vec_offset
) / elt_size
;
372 /* And finally, recalculate the amount of space we ask for. */
373 size
= vec_offset
+ alloc
* elt_size
;
375 unsigned nelem
= v
? v
->length () : 0;
376 v
= static_cast <vec
<T
, A
, vl_embed
> *> (ggc_realloc_stat (v
, size
));
377 v
->embedded_init (alloc
, nelem
);
381 /* Allocator type for GC vectors. This is for vectors of types
382 atomics w.r.t. collection, so allocation and deallocation is
383 completely inherited from va_gc. */
384 struct va_gc_atomic
: va_gc
389 /* Allocator type for stack vectors. */
392 /* Use vl_ptr as the default layout for stack vectors. */
393 typedef vl_ptr default_layout
;
396 static void alloc (vec
<T
, va_stack
, vl_ptr
>&, unsigned,
397 vec
<T
, va_stack
, vl_embed
> *);
399 template <typename T
>
400 static void reserve (vec
<T
, va_stack
, vl_embed
> *&, unsigned, bool
403 template <typename T
>
404 static void release (vec
<T
, va_stack
, vl_embed
> *&);
407 /* Helper functions to keep track of vectors allocated on the stack. */
408 void register_stack_vec (void *);
409 int stack_vec_register_index (void *);
410 void unregister_stack_vec (unsigned);
412 /* Allocate a vector V which uses alloca for the initial allocation.
413 SPACE is space allocated using alloca. NELEMS is the number of
414 entries allocated. */
418 va_stack::alloc (vec
<T
, va_stack
, vl_ptr
> &v
, unsigned nelems
,
419 vec
<T
, va_stack
, vl_embed
> *space
)
422 register_stack_vec (static_cast<void *> (v
.vec_
));
423 v
.vec_
->embedded_init (nelems
, 0);
427 /* Reserve NELEMS slots for a vector initially allocated on the stack.
428 When this happens, we switch back to heap allocation. We remove
429 the vector from stack_vecs, if it is there, since we no longer need
430 to avoid freeing it. If EXACT is true, grow exactly, otherwise
431 grow exponentially. */
435 va_stack::reserve (vec
<T
, va_stack
, vl_embed
> *&v
, unsigned nelems
, bool exact
438 int ix
= stack_vec_register_index (static_cast<void *> (v
));
440 unregister_stack_vec (ix
);
443 /* V is already on the heap. */
444 va_heap::reserve (reinterpret_cast<vec
<T
, va_heap
, vl_embed
> *&> (v
),
449 /* Move VEC_ to the heap. */
450 nelems
+= v
->pfx_
.num_
;
451 vec
<T
, va_stack
, vl_embed
> *oldvec
= v
;
453 va_heap::reserve (reinterpret_cast<vec
<T
, va_heap
, vl_embed
> *&>(v
), nelems
,
457 v
->pfx_
.num_
= oldvec
->length ();
458 memcpy (v
->data_
, oldvec
->data_
, oldvec
->length () * sizeof (T
));
463 /* Free a vector allocated on the stack. Don't actually free it if we
464 find it in the hash table. */
468 va_stack::release (vec
<T
, va_stack
, vl_embed
> *&v
)
470 int ix
= stack_vec_register_index (static_cast<void *> (v
));
473 unregister_stack_vec (ix
);
478 /* The vector was not on the list of vectors allocated on the stack, so it
479 must be allocated on the heap. */
480 va_heap::release (reinterpret_cast<vec
<T
, va_heap
, vl_embed
> *&> (v
));
485 /* Generic vector template. Default values for A and L indicate the
486 most commonly used strategies.
488 FIXME - Ideally, they would all be vl_ptr to encourage using regular
489 instances for vectors, but the existing GTY machinery is limited
490 in that it can only deal with GC objects that are pointers
493 This means that vector operations that need to deal with
494 potentially NULL pointers, must be provided as free
495 functions (see the vec_safe_* functions above). */
497 typename A
= va_heap
,
498 typename L
= typename
A::default_layout
>
499 class GTY((user
)) vec
504 /* Embeddable vector. These vectors are suitable to be embedded
505 in other data structures so that they can be pre-allocated in a
506 contiguous memory block.
508 Embeddable vectors are implemented using the trailing array idiom,
509 thus they are not resizeable without changing the address of the
510 vector object itself. This means you cannot have variables or
511 fields of embeddable vector type -- always use a pointer to a
512 vector. The one exception is the final field of a structure, which
513 could be a vector type.
515 You will have to use the embedded_size & embedded_init calls to
516 create such objects, and they will not be resizeable (so the 'safe'
517 allocation variants are not available).
521 - The whole vector and control data are allocated in a single
522 contiguous block. It uses the trailing-vector idiom, so
523 allocation must reserve enough space for all the elements
524 in the vector plus its control data.
525 - The vector cannot be re-allocated.
526 - The vector cannot grow nor shrink.
527 - No indirections needed for access/manipulation.
528 - It requires 2 words of storage (prior to vector allocation). */
530 template<typename T
, typename A
>
531 class GTY((user
)) vec
<T
, A
, vl_embed
>
534 unsigned allocated (void) const { return pfx_
.alloc_
; }
535 unsigned length (void) const { return pfx_
.num_
; }
536 bool is_empty (void) const { return pfx_
.num_
== 0; }
537 T
*address (void) { return data_
; }
538 const T
*address (void) const { return data_
; }
539 const T
&operator[] (unsigned) const;
540 T
&operator[] (unsigned);
542 bool space (unsigned) const;
543 bool iterate (unsigned, T
*) const;
544 bool iterate (unsigned, T
**) const;
545 vec
*copy (ALONE_MEM_STAT_DECL
) const;
547 void splice (vec
*src
);
548 T
*quick_push (const T
&);
550 void truncate (unsigned);
551 void quick_insert (unsigned, const T
&);
552 void ordered_remove (unsigned);
553 void unordered_remove (unsigned);
554 void block_remove (unsigned, unsigned);
555 void qsort (int (*) (const void *, const void *));
556 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
557 static size_t embedded_size (unsigned);
558 void embedded_init (unsigned, unsigned = 0);
559 void quick_grow (unsigned len
);
560 void quick_grow_cleared (unsigned len
);
562 /* vec class can access our internal data and functions. */
563 template <typename
, typename
, typename
> friend class vec
;
565 /* The allocator types also need access to our internals. */
567 friend struct va_gc_atomic
;
568 friend struct va_heap
;
569 friend struct va_stack
;
577 /* Convenience wrapper functions to use when dealing with pointers to
578 embedded vectors. Some functionality for these vectors must be
579 provided via free functions for these reasons:
581 1- The pointer may be NULL (e.g., before initial allocation).
583 2- When the vector needs to grow, it must be reallocated, so
584 the pointer will change its value.
586 Because of limitations with the current GC machinery, all vectors
587 in GC memory *must* be pointers. */
590 /* If V contains no room for NELEMS elements, return false. Otherwise,
592 template<typename T
, typename A
>
594 vec_safe_space (const vec
<T
, A
, vl_embed
> *v
, unsigned nelems
)
596 return v
? v
->space (nelems
) : nelems
== 0;
600 /* If V is NULL, return 0. Otherwise, return V->length(). */
601 template<typename T
, typename A
>
603 vec_safe_length (const vec
<T
, A
, vl_embed
> *v
)
605 return v
? v
->length () : 0;
609 /* If V is NULL, return NULL. Otherwise, return V->address(). */
610 template<typename T
, typename A
>
612 vec_safe_address (vec
<T
, A
, vl_embed
> *v
)
614 return v
? v
->address () : NULL
;
618 /* If V is NULL, return true. Otherwise, return V->is_empty(). */
619 template<typename T
, typename A
>
621 vec_safe_is_empty (vec
<T
, A
, vl_embed
> *v
)
623 return v
? v
->is_empty () : true;
627 /* If V does not have space for NELEMS elements, call
628 V->reserve(NELEMS, EXACT). */
629 template<typename T
, typename A
>
631 vec_safe_reserve (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems
, bool exact
= false
634 bool extend
= nelems
? !vec_safe_space (v
, nelems
) : false;
636 A::reserve (v
, nelems
, exact PASS_MEM_STAT
);
640 template<typename T
, typename A
>
642 vec_safe_reserve_exact (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems MEM_STAT_DECL
)
644 return vec_safe_reserve (v
, nelems
, true PASS_MEM_STAT
);
648 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS
649 is 0, V is initialized to NULL. */
651 template<typename T
, typename A
>
653 vec_alloc (vec
<T
, A
, vl_embed
> *&v
, unsigned nelems MEM_STAT_DECL
)
656 vec_safe_reserve (v
, nelems
);
660 /* Free the GC memory allocated by vector V and set it to NULL. */
662 template<typename T
, typename A
>
664 vec_free (vec
<T
, A
, vl_embed
> *&v
)
670 /* Grow V to length LEN. Allocate it, if necessary. */
671 template<typename T
, typename A
>
673 vec_safe_grow (vec
<T
, A
, vl_embed
> *&v
, unsigned len MEM_STAT_DECL
)
675 unsigned oldlen
= vec_safe_length (v
);
676 gcc_checking_assert (len
>= oldlen
);
677 vec_safe_reserve_exact (v
, len
- oldlen PASS_MEM_STAT
);
678 v
->quick_grow (len PASS_MEM_STAT
);
682 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */
683 template<typename T
, typename A
>
685 vec_safe_grow_cleared (vec
<T
, A
, vl_embed
> *&v
, unsigned len MEM_STAT_DECL
)
687 unsigned oldlen
= vec_safe_length (v
);
688 vec_safe_grow (v
, len PASS_MEM_STAT
);
689 memset (&(v
->address()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
693 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */
694 template<typename T
, typename A
>
696 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
**ptr
)
699 return v
->iterate (ix
, ptr
);
707 template<typename T
, typename A
>
709 vec_safe_iterate (const vec
<T
, A
, vl_embed
> *v
, unsigned ix
, T
*ptr
)
712 return v
->iterate (ix
, ptr
);
721 /* If V has no room for one more element, reallocate it. Then call
722 V->quick_push(OBJ). */
723 template<typename T
, typename A
>
725 vec_safe_push (vec
<T
, A
, vl_embed
> *&v
, const T
&obj MEM_STAT_DECL
)
727 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
728 return v
->quick_push (obj PASS_MEM_STAT
);
732 /* if V has no room for one more element, reallocate it. Then call
733 V->quick_insert(IX, OBJ). */
734 template<typename T
, typename A
>
736 vec_safe_insert (vec
<T
, A
, vl_embed
> *&v
, unsigned ix
, const T
&obj
739 vec_safe_reserve (v
, 1, false PASS_MEM_STAT
);
740 v
->quick_insert (ix
, obj
);
744 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */
745 template<typename T
, typename A
>
747 vec_safe_truncate (vec
<T
, A
, vl_embed
> *v
, unsigned size
)
754 /* If SRC is not NULL, return a pointer to a copy of it. */
755 template<typename T
, typename A
>
756 inline vec
<T
, A
, vl_embed
> *
757 vec_safe_copy (vec
<T
, A
, vl_embed
> *src
)
759 return src
? src
->copy () : NULL
;
762 /* Copy the elements from SRC to the end of DST as if by memcpy.
763 Reallocate DST, if necessary. */
764 template<typename T
, typename A
>
766 vec_safe_splice (vec
<T
, A
, vl_embed
> *&dst
, vec
<T
, A
, vl_embed
> *src
769 unsigned src_len
= vec_safe_length (src
);
772 vec_safe_reserve_exact (dst
, vec_safe_length (dst
) + src_len
);
778 /* Index into vector. Return the IX'th element. IX must be in the
779 domain of the vector. */
781 template<typename T
, typename A
>
783 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
) const
785 gcc_checking_assert (ix
< pfx_
.num_
);
789 template<typename T
, typename A
>
791 vec
<T
, A
, vl_embed
>::operator[] (unsigned ix
)
793 gcc_checking_assert (ix
< pfx_
.num_
);
798 /* Get the final element of the vector, which must not be empty. */
800 template<typename T
, typename A
>
802 vec
<T
, A
, vl_embed
>::last (void)
804 gcc_checking_assert (pfx_
.num_
> 0);
805 return (*this)[pfx_
.num_
- 1];
809 /* If this vector has space for NELEMS additional entries, return
810 true. You usually only need to use this if you are doing your
811 own vector reallocation, for instance on an embedded vector. This
812 returns true in exactly the same circumstances that vec::reserve
815 template<typename T
, typename A
>
817 vec
<T
, A
, vl_embed
>::space (unsigned nelems
) const
819 return pfx_
.alloc_
- pfx_
.num_
>= nelems
;
823 /* Return iteration condition and update PTR to point to the IX'th
824 element of this vector. Use this to iterate over the elements of a
827 for (ix = 0; vec<T, A>::iterate(v, ix, &ptr); ix++)
830 template<typename T
, typename A
>
832 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
*ptr
) const
847 /* Return iteration condition and update *PTR to point to the
848 IX'th element of this vector. Use this to iterate over the
849 elements of a vector as follows,
851 for (ix = 0; v->iterate(ix, &ptr); ix++)
854 This variant is for vectors of objects. */
856 template<typename T
, typename A
>
858 vec
<T
, A
, vl_embed
>::iterate (unsigned ix
, T
**ptr
) const
862 *ptr
= CONST_CAST (T
*, &data_
[ix
]);
873 /* Return a pointer to a copy of this vector. */
875 template<typename T
, typename A
>
876 inline vec
<T
, A
, vl_embed
> *
877 vec
<T
, A
, vl_embed
>::copy (ALONE_MEM_STAT_DECL
) const
879 vec
<T
, A
, vl_embed
> *new_vec
= NULL
;
880 unsigned len
= length ();
883 vec_alloc (new_vec
, len PASS_MEM_STAT
);
884 new_vec
->embedded_init (len
, len
);
885 memcpy (new_vec
->address(), data_
, sizeof (T
) * len
);
891 /* Copy the elements from SRC to the end of this vector as if by memcpy.
892 The vector must have sufficient headroom available. */
894 template<typename T
, typename A
>
896 vec
<T
, A
, vl_embed
>::splice (vec
<T
, A
, vl_embed
> &src
)
898 unsigned len
= src
.length();
901 gcc_checking_assert (space (len
));
902 memcpy (address() + length(), src
.address(), len
* sizeof (T
));
907 template<typename T
, typename A
>
909 vec
<T
, A
, vl_embed
>::splice (vec
<T
, A
, vl_embed
> *src
)
916 /* Push OBJ (a new element) onto the end of the vector. There must be
917 sufficient space in the vector. Return a pointer to the slot
918 where OBJ was inserted. */
920 template<typename T
, typename A
>
922 vec
<T
, A
, vl_embed
>::quick_push (const T
&obj
)
924 gcc_checking_assert (space (1));
925 T
*slot
= &data_
[pfx_
.num_
++];
931 /* Pop and return the last element off the end of the vector. */
933 template<typename T
, typename A
>
935 vec
<T
, A
, vl_embed
>::pop (void)
937 gcc_checking_assert (length () > 0);
938 return data_
[--pfx_
.num_
];
942 /* Set the length of the vector to SIZE. The new length must be less
943 than or equal to the current length. This is an O(1) operation. */
945 template<typename T
, typename A
>
947 vec
<T
, A
, vl_embed
>::truncate (unsigned size
)
949 gcc_checking_assert (length () >= size
);
954 /* Insert an element, OBJ, at the IXth position of this vector. There
955 must be sufficient space. */
957 template<typename T
, typename A
>
959 vec
<T
, A
, vl_embed
>::quick_insert (unsigned ix
, const T
&obj
)
961 gcc_checking_assert (length () < allocated ());
962 gcc_checking_assert (ix
<= length ());
963 T
*slot
= &data_
[ix
];
964 memmove (slot
+ 1, slot
, (pfx_
.num_
++ - ix
) * sizeof (T
));
969 /* Remove an element from the IXth position of this vector. Ordering of
970 remaining elements is preserved. This is an O(N) operation due to
973 template<typename T
, typename A
>
975 vec
<T
, A
, vl_embed
>::ordered_remove (unsigned ix
)
977 gcc_checking_assert (ix
< length());
978 T
*slot
= &data_
[ix
];
979 memmove (slot
, slot
+ 1, (--pfx_
.num_
- ix
) * sizeof (T
));
983 /* Remove an element from the IXth position of this vector. Ordering of
984 remaining elements is destroyed. This is an O(1) operation. */
986 template<typename T
, typename A
>
988 vec
<T
, A
, vl_embed
>::unordered_remove (unsigned ix
)
990 gcc_checking_assert (ix
< length());
991 data_
[ix
] = data_
[--pfx_
.num_
];
995 /* Remove LEN elements starting at the IXth. Ordering is retained.
996 This is an O(N) operation due to memmove. */
998 template<typename T
, typename A
>
1000 vec
<T
, A
, vl_embed
>::block_remove (unsigned ix
, unsigned len
)
1002 gcc_checking_assert (ix
+ len
<= length());
1003 T
*slot
= &data_
[ix
];
1005 memmove (slot
, slot
+ len
, (pfx_
.num_
- ix
) * sizeof (T
));
1009 /* Sort the contents of this vector with qsort. CMP is the comparison
1010 function to pass to qsort. */
1012 template<typename T
, typename A
>
1014 vec
<T
, A
, vl_embed
>::qsort (int (*cmp
) (const void *, const void *))
1016 ::qsort (address(), length(), sizeof (T
), cmp
);
1020 /* Find and return the first position in which OBJ could be inserted
1021 without changing the ordering of this vector. LESSTHAN is a
1022 function that returns true if the first argument is strictly less
1025 template<typename T
, typename A
>
1027 vec
<T
, A
, vl_embed
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&))
1030 unsigned int len
= length ();
1031 unsigned int half
, middle
;
1032 unsigned int first
= 0;
1038 T middle_elem
= (*this)[middle
];
1039 if (lessthan (middle_elem
, obj
))
1043 len
= len
- half
- 1;
1052 /* Return the number of bytes needed to embed an instance of an
1053 embeddable vec inside another data structure.
1055 Use these methods to determine the required size and initialization
1056 of a vector V of type T embedded within another structure (as the
1059 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
1060 void v->embedded_init(unsigned alloc, unsigned num);
1062 These allow the caller to perform the memory allocation. */
1064 template<typename T
, typename A
>
1066 vec
<T
, A
, vl_embed
>::embedded_size (unsigned alloc
)
1068 typedef vec
<T
, A
, vl_embed
> vec_embedded
;
1069 return offsetof (vec_embedded
, data_
) + alloc
* sizeof (T
);
1073 /* Initialize the vector to contain room for ALLOC elements and
1074 NUM active elements. */
1076 template<typename T
, typename A
>
1078 vec
<T
, A
, vl_embed
>::embedded_init (unsigned alloc
, unsigned num
)
1080 pfx_
.alloc_
= alloc
;
1085 /* Grow the vector to a specific length. LEN must be as long or longer than
1086 the current length. The new elements are uninitialized. */
1088 template<typename T
, typename A
>
1090 vec
<T
, A
, vl_embed
>::quick_grow (unsigned len
)
1092 gcc_checking_assert (length () <= len
&& len
<= pfx_
.alloc_
);
1097 /* Grow the vector to a specific length. LEN must be as long or longer than
1098 the current length. The new elements are initialized to zero. */
1100 template<typename T
, typename A
>
1102 vec
<T
, A
, vl_embed
>::quick_grow_cleared (unsigned len
)
1104 unsigned oldlen
= length ();
1106 memset (&(address()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
1110 /* Garbage collection support for vec<T, A, vl_embed>. */
1112 template<typename T
>
1114 gt_ggc_mx (vec
<T
, va_gc
> *v
)
1116 extern void gt_ggc_mx (T
&);
1117 for (unsigned i
= 0; i
< v
->length (); i
++)
1118 gt_ggc_mx ((*v
)[i
]);
1121 template<typename T
>
1123 gt_ggc_mx (vec
<T
, va_gc_atomic
, vl_embed
> *v ATTRIBUTE_UNUSED
)
1125 /* Nothing to do. Vectors of atomic types wrt GC do not need to
1130 /* PCH support for vec<T, A, vl_embed>. */
1132 template<typename T
, typename A
>
1134 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
)
1136 extern void gt_pch_nx (T
&);
1137 for (unsigned i
= 0; i
< v
->length (); i
++)
1138 gt_pch_nx ((*v
)[i
]);
1141 template<typename T
, typename A
>
1143 gt_pch_nx (vec
<T
*, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1145 for (unsigned i
= 0; i
< v
->length (); i
++)
1146 op (&((*v
)[i
]), cookie
);
1149 template<typename T
, typename A
>
1151 gt_pch_nx (vec
<T
, A
, vl_embed
> *v
, gt_pointer_operator op
, void *cookie
)
1153 extern void gt_pch_nx (T
*, gt_pointer_operator
, void *);
1154 for (unsigned i
= 0; i
< v
->length (); i
++)
1155 gt_pch_nx (&((*v
)[i
]), op
, cookie
);
1159 /* Space efficient vector. These vectors can grow dynamically and are
1160 allocated together with their control data. They are suited to be
1161 included in data structures. Prior to initial allocation, they
1162 only take a single word of storage.
1164 These vectors are implemented as a pointer to an embeddable vector.
1165 The semantics allow for this pointer to be NULL to represent empty
1166 vectors. This way, empty vectors occupy minimal space in the
1167 structure containing them.
1171 - The whole vector and control data are allocated in a single
1173 - The whole vector may be re-allocated.
1174 - Vector data may grow and shrink.
1175 - Access and manipulation requires a pointer test and
1177 - It requires 1 word of storage (prior to vector allocation).
1182 These vectors must be PODs because they are stored in unions.
1183 (http://en.wikipedia.org/wiki/Plain_old_data_structures).
1184 As long as we use C++03, we cannot have constructors nor
1185 destructors in classes that are stored in unions. */
1187 template<typename T
, typename A
>
1188 class vec
<T
, A
, vl_ptr
>
1191 /* Memory allocation and deallocation for the embedded vector.
1192 Needed because we cannot have proper ctors/dtors defined. */
1193 void create (unsigned nelems CXX_MEM_STAT_INFO
);
1194 void release (void);
1196 /* Vector operations. */
1197 bool exists (void) const
1198 { return vec_
!= NULL
; }
1200 bool is_empty (void) const
1201 { return vec_
? vec_
->is_empty() : true; }
1203 unsigned length (void) const
1204 { return vec_
? vec_
->length() : 0; }
1207 { return vec_
? vec_
->data_
: NULL
; }
1209 const T
*address (void) const
1210 { return vec_
? vec_
->data_
: NULL
; }
1212 const T
&operator[] (unsigned ix
) const
1213 { return (*vec_
)[ix
]; }
1215 bool operator!=(const vec
&other
) const
1216 { return !(*this == other
); }
1218 bool operator==(const vec
&other
) const
1219 { return address() == other
.address(); }
1221 T
&operator[] (unsigned ix
)
1222 { return (*vec_
)[ix
]; }
1225 { return vec_
->last(); }
1227 bool space (int nelems
) const
1228 { return vec_
? vec_
->space (nelems
) : nelems
== 0; }
1230 bool iterate (unsigned ix
, T
*p
) const;
1231 bool iterate (unsigned ix
, T
**p
) const;
1232 vec
copy (ALONE_CXX_MEM_STAT_INFO
) const;
1233 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO
);
1234 bool reserve_exact (unsigned CXX_MEM_STAT_INFO
);
1235 void splice (vec
&);
1236 void safe_splice (vec
& CXX_MEM_STAT_INFO
);
1237 T
*quick_push (const T
&);
1238 T
*safe_push (const T
&CXX_MEM_STAT_INFO
);
1240 void truncate (unsigned);
1241 void safe_grow (unsigned CXX_MEM_STAT_INFO
);
1242 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO
);
1243 void quick_grow (unsigned);
1244 void quick_grow_cleared (unsigned);
1245 void quick_insert (unsigned, const T
&);
1246 void safe_insert (unsigned, const T
& CXX_MEM_STAT_INFO
);
1247 void ordered_remove (unsigned);
1248 void unordered_remove (unsigned);
1249 void block_remove (unsigned, unsigned);
1250 void qsort (int (*) (const void *, const void *));
1251 unsigned lower_bound (T
, bool (*)(const T
&, const T
&)) const;
1253 template<typename T1
>
1254 friend void va_stack::alloc(vec
<T1
, va_stack
, vl_ptr
>&, unsigned,
1255 vec
<T1
, va_stack
, vl_embed
> *);
1258 vec
<T
, A
, vl_embed
> *vec_
;
1262 /* Empty specialization for GC allocation. This will prevent GC
1263 vectors from using the vl_ptr layout. FIXME: This is needed to
1264 circumvent limitations in the GTY machinery. */
1266 template<typename T
>
1267 class vec
<T
, va_gc
, vl_ptr
>
1272 /* Allocate heap memory for pointer V and create the internal vector
1273 with space for NELEMS elements. If NELEMS is 0, the internal
1274 vector is initialized to empty. */
1276 template<typename T
>
1278 vec_alloc (vec
<T
> *&v
, unsigned nelems MEM_STAT_DECL
)
1281 v
->create (nelems PASS_MEM_STAT
);
1285 /* Conditionally allocate heap memory for VEC and its internal vector. */
1287 template<typename T
>
1289 vec_check_alloc (vec
<T
, va_heap
> *&vec
, unsigned nelems MEM_STAT_DECL
)
1292 vec_alloc (vec
, nelems PASS_MEM_STAT
);
1296 /* Free the heap memory allocated by vector V and set it to NULL. */
1298 template<typename T
>
1300 vec_free (vec
<T
> *&v
)
1311 /* Allocate a new stack vector with space for exactly NELEMS objects.
1312 If NELEMS is zero, NO vector is created.
1314 For the stack allocator, no memory is really allocated. The vector
1315 is initialized to be at address SPACE and contain NELEMS slots.
1316 Memory allocation actually occurs in the expansion of VEC_alloc.
1320 * This does not allocate an instance of vec<T, A>. It allocates the
1321 actual vector of elements (i.e., vec<T, A, vl_embed>) inside a
1324 * This allocator must always be a macro:
1326 We support a vector which starts out with space on the stack and
1327 switches to heap space when forced to reallocate. This works a
1328 little differently. In the case of stack vectors, vec_alloc will
1329 expand to a call to vec_alloc_1 that calls XALLOCAVAR to request
1330 the initial allocation. This uses alloca to get the initial
1331 space. Since alloca can not be usefully called in an inline
1332 function, vec_alloc must always be a macro.
1334 Important limitations of stack vectors:
1336 - Only the initial allocation will be made using alloca, so pass
1337 a reasonable estimate that doesn't use too much stack space;
1340 - Don't return a stack-allocated vector from the function which
1343 #define vec_stack_alloc(T,V,N) \
1345 typedef vec<T, va_stack, vl_embed> stackv; \
1346 va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\
1350 /* Return iteration condition and update PTR to point to the IX'th
1351 element of this vector. Use this to iterate over the elements of a
1354 for (ix = 0; v.iterate(ix, &ptr); ix++)
1357 template<typename T
, typename A
>
1359 vec
<T
, A
, vl_ptr
>::iterate (unsigned ix
, T
*ptr
) const
1362 return vec_
->iterate (ix
, ptr
);
1371 /* Return iteration condition and update *PTR to point to the
1372 IX'th element of this vector. Use this to iterate over the
1373 elements of a vector as follows,
1375 for (ix = 0; v->iterate(ix, &ptr); ix++)
1378 This variant is for vectors of objects. */
1380 template<typename T
, typename A
>
1382 vec
<T
, A
, vl_ptr
>::iterate (unsigned ix
, T
**ptr
) const
1385 return vec_
->iterate (ix
, ptr
);
1394 /* Convenience macro for forward iteration. */
1395 #define FOR_EACH_VEC_ELT(V, I, P) \
1396 for (I = 0; (V).iterate ((I), &(P)); ++(I))
1398 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
1399 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
1401 /* Likewise, but start from FROM rather than 0. */
1402 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \
1403 for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
1405 /* Convenience macro for reverse iteration. */
1406 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \
1407 for (I = (V).length () - 1; \
1408 (V).iterate ((I), &(P)); \
1411 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \
1412 for (I = vec_safe_length (V) - 1; \
1413 vec_safe_iterate ((V), (I), &(P)); \
1417 /* Return a copy of this vector. */
1419 template<typename T
, typename A
>
1420 inline vec
<T
, A
, vl_ptr
>
1421 vec
<T
, A
, vl_ptr
>::copy (ALONE_MEM_STAT_DECL
) const
1423 vec
<T
, A
, vl_ptr
> new_vec
= vec
<T
, A
, vl_ptr
>();
1425 new_vec
.vec_
= vec_
->copy ();
1430 /* Ensure that the vector has at least RESERVE slots available (if
1431 EXACT is false), or exactly RESERVE slots available (if EXACT is
1434 This may create additional headroom if EXACT is false.
1436 Note that this can cause the embedded vector to be reallocated.
1437 Returns true iff reallocation actually occurred. */
1439 template<typename T
, typename A
>
1441 vec
<T
, A
, vl_ptr
>::reserve (unsigned nelems
, bool exact MEM_STAT_DECL
)
1443 bool extend
= nelems
? !space (nelems
) : false;
1445 A::reserve (vec_
, nelems
, exact PASS_MEM_STAT
);
1450 /* Ensure that this vector has exactly NELEMS slots available. This
1451 will not create additional headroom. Note this can cause the
1452 embedded vector to be reallocated. Returns true iff reallocation
1453 actually occurred. */
1455 template<typename T
, typename A
>
1457 vec
<T
, A
, vl_ptr
>::reserve_exact (unsigned nelems MEM_STAT_DECL
)
1459 return reserve (nelems
, true PASS_MEM_STAT
);
1463 /* Create the internal vector and reserve NELEMS for it. This is
1464 exactly like vec::reserve, but the internal vector is
1465 unconditionally allocated from scratch. The old one, if it
1466 existed, is lost. */
1468 template<typename T
, typename A
>
1470 vec
<T
, A
, vl_ptr
>::create (unsigned nelems MEM_STAT_DECL
)
1474 reserve_exact (nelems PASS_MEM_STAT
);
1478 /* Free the memory occupied by the embedded vector. */
1480 template<typename T
, typename A
>
1482 vec
<T
, A
, vl_ptr
>::release (void)
1489 /* Copy the elements from SRC to the end of this vector as if by memcpy.
1490 SRC and this vector must be allocated with the same memory
1491 allocation mechanism. This vector is assumed to have sufficient
1492 headroom available. */
1494 template<typename T
, typename A
>
1496 vec
<T
, A
, vl_ptr
>::splice (vec
<T
, A
, vl_ptr
> &src
)
1499 vec_
->splice (*(src
.vec_
));
1503 /* Copy the elements in SRC to the end of this vector as if by memcpy.
1504 SRC and this vector must be allocated with the same mechanism.
1505 If there is not enough headroom in this vector, it will be reallocated
1508 template<typename T
, typename A
>
1510 vec
<T
, A
, vl_ptr
>::safe_splice (vec
<T
, A
, vl_ptr
> &src MEM_STAT_DECL
)
1514 reserve_exact (src
.length());
1520 /* Push OBJ (a new element) onto the end of the vector. There must be
1521 sufficient space in the vector. Return a pointer to the slot
1522 where OBJ was inserted. */
1524 template<typename T
, typename A
>
1526 vec
<T
, A
, vl_ptr
>::quick_push (const T
&obj
)
1528 return vec_
->quick_push (obj
);
1532 /* Push a new element OBJ onto the end of this vector. Reallocates
1533 the embedded vector, if needed. Return a pointer to the slot where
1534 OBJ was inserted. */
1536 template<typename T
, typename A
>
1538 vec
<T
, A
, vl_ptr
>::safe_push (const T
&obj MEM_STAT_DECL
)
1540 reserve (1, false PASS_MEM_STAT
);
1541 return quick_push (obj
);
1545 /* Pop and return the last element off the end of the vector. */
1547 template<typename T
, typename A
>
1549 vec
<T
, A
, vl_ptr
>::pop (void)
1551 return vec_
->pop ();
1555 /* Set the length of the vector to LEN. The new length must be less
1556 than or equal to the current length. This is an O(1) operation. */
1558 template<typename T
, typename A
>
1560 vec
<T
, A
, vl_ptr
>::truncate (unsigned size
)
1563 vec_
->truncate (size
);
1565 gcc_checking_assert (size
== 0);
1569 /* Grow the vector to a specific length. LEN must be as long or
1570 longer than the current length. The new elements are
1571 uninitialized. Reallocate the internal vector, if needed. */
1573 template<typename T
, typename A
>
1575 vec
<T
, A
, vl_ptr
>::safe_grow (unsigned len MEM_STAT_DECL
)
1577 unsigned oldlen
= length ();
1578 gcc_checking_assert (oldlen
<= len
);
1579 reserve_exact (len
- oldlen PASS_MEM_STAT
);
1580 vec_
->quick_grow (len
);
1584 /* Grow the embedded vector to a specific length. LEN must be as
1585 long or longer than the current length. The new elements are
1586 initialized to zero. Reallocate the internal vector, if needed. */
1588 template<typename T
, typename A
>
1590 vec
<T
, A
, vl_ptr
>::safe_grow_cleared (unsigned len MEM_STAT_DECL
)
1592 unsigned oldlen
= length ();
1593 safe_grow (len PASS_MEM_STAT
);
1594 memset (&(address()[oldlen
]), 0, sizeof (T
) * (len
- oldlen
));
1598 /* Same as vec::safe_grow but without reallocation of the internal vector.
1599 If the vector cannot be extended, a runtime assertion will be triggered. */
1601 template<typename T
, typename A
>
1603 vec
<T
, A
, vl_ptr
>::quick_grow (unsigned len
)
1605 gcc_checking_assert (vec_
);
1606 vec_
->quick_grow (len
);
1610 /* Same as vec::quick_grow_cleared but without reallocation of the
1611 internal vector. If the vector cannot be extended, a runtime
1612 assertion will be triggered. */
1614 template<typename T
, typename A
>
1616 vec
<T
, A
, vl_ptr
>::quick_grow_cleared (unsigned len
)
1618 gcc_checking_assert (vec_
);
1619 vec_
->quick_grow_cleared (len
);
1623 /* Insert an element, OBJ, at the IXth position of this vector. There
1624 must be sufficient space. */
1626 template<typename T
, typename A
>
1628 vec
<T
, A
, vl_ptr
>::quick_insert (unsigned ix
, const T
&obj
)
1630 vec_
->quick_insert (ix
, obj
);
1634 /* Insert an element, OBJ, at the IXth position of the vector.
1635 Reallocate the embedded vector, if necessary. */
1637 template<typename T
, typename A
>
1639 vec
<T
, A
, vl_ptr
>::safe_insert (unsigned ix
, const T
&obj MEM_STAT_DECL
)
1641 reserve (1, false PASS_MEM_STAT
);
1642 quick_insert (ix
, obj
);
1646 /* Remove an element from the IXth position of this vector. Ordering of
1647 remaining elements is preserved. This is an O(N) operation due to
1650 template<typename T
, typename A
>
1652 vec
<T
, A
, vl_ptr
>::ordered_remove (unsigned ix
)
1654 vec_
->ordered_remove (ix
);
1658 /* Remove an element from the IXth position of this vector. Ordering
1659 of remaining elements is destroyed. This is an O(1) operation. */
1661 template<typename T
, typename A
>
1663 vec
<T
, A
, vl_ptr
>::unordered_remove (unsigned ix
)
1665 vec_
->unordered_remove (ix
);
1669 /* Remove LEN elements starting at the IXth. Ordering is retained.
1670 This is an O(N) operation due to memmove. */
1672 template<typename T
, typename A
>
1674 vec
<T
, A
, vl_ptr
>::block_remove (unsigned ix
, unsigned len
)
1676 vec_
->block_remove (ix
, len
);
1680 /* Sort the contents of this vector with qsort. CMP is the comparison
1681 function to pass to qsort. */
1683 template<typename T
, typename A
>
1685 vec
<T
, A
, vl_ptr
>::qsort (int (*cmp
) (const void *, const void *))
1692 /* Find and return the first position in which OBJ could be inserted
1693 without changing the ordering of this vector. LESSTHAN is a
1694 function that returns true if the first argument is strictly less
1697 template<typename T
, typename A
>
1699 vec
<T
, A
, vl_ptr
>::lower_bound (T obj
, bool (*lessthan
)(const T
&, const T
&)) const
1701 return vec_
? vec_
->lower_bound (obj
, lessthan
) : 0;