diff options
author | Ben Cheng <bccheng@google.com> | 2014-03-25 22:37:19 -0700 |
---|---|---|
committer | Ben Cheng <bccheng@google.com> | 2014-03-25 22:37:19 -0700 |
commit | 1bc5aee63eb72b341f506ad058502cd0361f0d10 (patch) | |
tree | c607e8252f3405424ff15bc2d00aa38dadbb2518 /gcc-4.9/gcc/vec.h | |
parent | 283a0bf58fcf333c58a2a92c3ebbc41fb9eb1fdb (diff) | |
download | toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.gz toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.bz2 toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.zip |
Initial checkin of GCC 4.9.0 from trunk (r208799).
Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba
Diffstat (limited to 'gcc-4.9/gcc/vec.h')
-rw-r--r-- | gcc-4.9/gcc/vec.h | 1727 |
1 files changed, 1727 insertions, 0 deletions
diff --git a/gcc-4.9/gcc/vec.h b/gcc-4.9/gcc/vec.h new file mode 100644 index 000000000..587302344 --- /dev/null +++ b/gcc-4.9/gcc/vec.h @@ -0,0 +1,1727 @@ +/* Vector API for GNU compiler. + Copyright (C) 2004-2014 Free Software Foundation, Inc. + Contributed by Nathan Sidwell <nathan@codesourcery.com> + Re-implemented in C++ by Diego Novillo <dnovillo@google.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_VEC_H +#define GCC_VEC_H + +/* FIXME - When compiling some of the gen* binaries, we cannot enable GC + support because the headers generated by gengtype are still not + present. In particular, the header file gtype-desc.h is missing, + so compilation may fail if we try to include ggc.h. + + Since we use some of those declarations, we need to provide them + (even if the GC-based templates are not used). This is not a + problem because the code that runs before gengtype is built will + never need to use GC vectors. But it does force us to declare + these functions more than once. */ +#ifdef GENERATOR_FILE +#define VEC_GC_ENABLED 0 +#else +#define VEC_GC_ENABLED 1 +#endif // GENERATOR_FILE + +#include "statistics.h" // For CXX_MEM_STAT_INFO. + +#if VEC_GC_ENABLED +#include "ggc.h" +#else +# ifndef GCC_GGC_H + /* Even if we think that GC is not enabled, the test that sets it is + weak. There are files compiled with -DGENERATOR_FILE that already + include ggc.h. We only need to provide these definitions if ggc.h + has not been included. Sigh. */ + extern void ggc_free (void *); + extern size_t ggc_round_alloc_size (size_t requested_size); + extern void *ggc_realloc_stat (void *, size_t MEM_STAT_DECL); +# endif // GCC_GGC_H +#endif // VEC_GC_ENABLED + +/* Templated vector type and associated interfaces. + + The interface functions are typesafe and use inline functions, + sometimes backed by out-of-line generic functions. The vectors are + designed to interoperate with the GTY machinery. + + There are both 'index' and 'iterate' accessors. The index accessor + is implemented by operator[]. The iterator returns a boolean + iteration condition and updates the iteration variable passed by + reference. Because the iterator will be inlined, the address-of + can be optimized away. + + Each operation that increases the number of active elements is + available in 'quick' and 'safe' variants. The former presumes that + there is sufficient allocated space for the operation to succeed + (it dies if there is not). The latter will reallocate the + vector, if needed. Reallocation causes an exponential increase in + vector size. If you know you will be adding N elements, it would + be more efficient to use the reserve operation before adding the + elements with the 'quick' operation. This will ensure there are at + least as many elements as you ask for, it will exponentially + increase if there are too few spare slots. If you want reserve a + specific number of slots, but do not want the exponential increase + (for instance, you know this is the last allocation), use the + reserve_exact operation. You can also create a vector of a + specific size from the get go. + + You should prefer the push and pop operations, as they append and + remove from the end of the vector. If you need to remove several + items in one go, use the truncate operation. The insert and remove + operations allow you to change elements in the middle of the + vector. There are two remove operations, one which preserves the + element ordering 'ordered_remove', and one which does not + 'unordered_remove'. The latter function copies the end element + into the removed slot, rather than invoke a memmove operation. The + 'lower_bound' function will determine where to place an item in the + array using insert that will maintain sorted order. + + Vectors are template types with three arguments: the type of the + elements in the vector, the allocation strategy, and the physical + layout to use + + Four allocation strategies are supported: + + - Heap: allocation is done using malloc/free. This is the + default allocation strategy. + + - GC: allocation is done using ggc_alloc/ggc_free. + + - GC atomic: same as GC with the exception that the elements + themselves are assumed to be of an atomic type that does + not need to be garbage collected. This means that marking + routines do not need to traverse the array marking the + individual elements. This increases the performance of + GC activities. + + Two physical layouts are supported: + + - Embedded: The vector is structured using the trailing array + idiom. The last member of the structure is an array of size + 1. When the vector is initially allocated, a single memory + block is created to hold the vector's control data and the + array of elements. These vectors cannot grow without + reallocation (see discussion on embeddable vectors below). + + - Space efficient: The vector is structured as a pointer to an + embedded vector. This is the default layout. It means that + vectors occupy a single word of storage before initial + allocation. Vectors are allowed to grow (the internal + pointer is reallocated but the main vector instance does not + need to relocate). + + The type, allocation and layout are specified when the vector is + declared. + + If you need to directly manipulate a vector, then the 'address' + accessor will return the address of the start of the vector. Also + the 'space' predicate will tell you whether there is spare capacity + in the vector. You will not normally need to use these two functions. + + Notes on the different layout strategies + + * Embeddable vectors (vec<T, A, vl_embed>) + + These vectors are suitable to be embedded in other data + structures so that they can be pre-allocated in a contiguous + memory block. + + Embeddable vectors are implemented using the trailing array + idiom, thus they are not resizeable without changing the address + of the vector object itself. This means you cannot have + variables or fields of embeddable vector type -- always use a + pointer to a vector. The one exception is the final field of a + structure, which could be a vector type. + + You will have to use the embedded_size & embedded_init calls to + create such objects, and they will not be resizeable (so the + 'safe' allocation variants are not available). + + Properties of embeddable vectors: + + - The whole vector and control data are allocated in a single + contiguous block. It uses the trailing-vector idiom, so + allocation must reserve enough space for all the elements + in the vector plus its control data. + - The vector cannot be re-allocated. + - The vector cannot grow nor shrink. + - No indirections needed for access/manipulation. + - It requires 2 words of storage (prior to vector allocation). + + + * Space efficient vector (vec<T, A, vl_ptr>) + + These vectors can grow dynamically and are allocated together + with their control data. They are suited to be included in data + structures. Prior to initial allocation, they only take a single + word of storage. + + These vectors are implemented as a pointer to embeddable vectors. + The semantics allow for this pointer to be NULL to represent + empty vectors. This way, empty vectors occupy minimal space in + the structure containing them. + + Properties: + + - The whole vector and control data are allocated in a single + contiguous block. + - The whole vector may be re-allocated. + - Vector data may grow and shrink. + - Access and manipulation requires a pointer test and + indirection. + - It requires 1 word of storage (prior to vector allocation). + + An example of their use would be, + + struct my_struct { + // A space-efficient vector of tree pointers in GC memory. + vec<tree, va_gc, vl_ptr> v; + }; + + struct my_struct *s; + + if (s->v.length ()) { we have some contents } + s->v.safe_push (decl); // append some decl onto the end + for (ix = 0; s->v.iterate (ix, &elt); ix++) + { do something with elt } +*/ + +/* Support function for statistics. */ +extern void dump_vec_loc_statistics (void); + + +/* Control data for vectors. This contains the number of allocated + and used slots inside a vector. */ + +struct vec_prefix +{ + /* FIXME - These fields should be private, but we need to cater to + compilers that have stricter notions of PODness for types. */ + + /* Memory allocation support routines in vec.c. */ + void register_overhead (size_t, const char *, int, const char *); + void release_overhead (void); + static unsigned calculate_allocation (vec_prefix *, unsigned, bool); + static unsigned calculate_allocation_1 (unsigned, unsigned); + + /* Note that vec_prefix should be a base class for vec, but we use + offsetof() on vector fields of tree structures (e.g., + tree_binfo::base_binfos), and offsetof only supports base types. + + To compensate, we make vec_prefix a field inside vec and make + vec a friend class of vec_prefix so it can access its fields. */ + template <typename, typename, typename> friend struct vec; + + /* The allocator types also need access to our internals. */ + friend struct va_gc; + friend struct va_gc_atomic; + friend struct va_heap; + + unsigned m_alloc : 31; + unsigned m_using_auto_storage : 1; + unsigned m_num; +}; + +/* Calculate the number of slots to reserve a vector, making sure that + RESERVE slots are free. If EXACT grow exactly, otherwise grow + exponentially. PFX is the control data for the vector. */ + +inline unsigned +vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve, + bool exact) +{ + if (exact) + return (pfx ? pfx->m_num : 0) + reserve; + else if (!pfx) + return MAX (4, reserve); + return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve); +} + +template<typename, typename, typename> struct vec; + +/* Valid vector layouts + + vl_embed - Embeddable vector that uses the trailing array idiom. + vl_ptr - Space efficient vector that uses a pointer to an + embeddable vector. */ +struct vl_embed { }; +struct vl_ptr { }; + + +/* Types of supported allocations + + va_heap - Allocation uses malloc/free. + va_gc - Allocation uses ggc_alloc. + va_gc_atomic - Same as GC, but individual elements of the array + do not need to be marked during collection. */ + +/* Allocator type for heap vectors. */ +struct va_heap +{ + /* Heap vectors are frequently regular instances, so use the vl_ptr + layout for them. */ + typedef vl_ptr default_layout; + + template<typename T> + static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool + CXX_MEM_STAT_INFO); + + template<typename T> + static void release (vec<T, va_heap, vl_embed> *&); +}; + + +/* Allocator for heap memory. Ensure there are at least RESERVE free + slots in V. If EXACT is true, grow exactly, else grow + exponentially. As a special case, if the vector had not been + allocated and and RESERVE is 0, no vector will be created. */ + +template<typename T> +inline void +va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact + MEM_STAT_DECL) +{ + unsigned alloc + = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); + gcc_checking_assert (alloc); + + if (GATHER_STATISTICS && v) + v->m_vecpfx.release_overhead (); + + size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc); + unsigned nelem = v ? v->length () : 0; + v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size)); + v->embedded_init (alloc, nelem); + + if (GATHER_STATISTICS) + v->m_vecpfx.register_overhead (size FINAL_PASS_MEM_STAT); +} + + +/* Free the heap space allocated for vector V. */ + +template<typename T> +void +va_heap::release (vec<T, va_heap, vl_embed> *&v) +{ + if (v == NULL) + return; + + if (GATHER_STATISTICS) + v->m_vecpfx.release_overhead (); + ::free (v); + v = NULL; +} + + +/* Allocator type for GC vectors. Notice that we need the structure + declaration even if GC is not enabled. */ + +struct va_gc +{ + /* Use vl_embed as the default layout for GC vectors. Due to GTY + limitations, GC vectors must always be pointers, so it is more + efficient to use a pointer to the vl_embed layout, rather than + using a pointer to a pointer as would be the case with vl_ptr. */ + typedef vl_embed default_layout; + + template<typename T, typename A> + static void reserve (vec<T, A, vl_embed> *&, unsigned, bool + CXX_MEM_STAT_INFO); + + template<typename T, typename A> + static void release (vec<T, A, vl_embed> *&v); +}; + + +/* Free GC memory used by V and reset V to NULL. */ + +template<typename T, typename A> +inline void +va_gc::release (vec<T, A, vl_embed> *&v) +{ + if (v) + ::ggc_free (v); + v = NULL; +} + + +/* Allocator for GC memory. Ensure there are at least RESERVE free + slots in V. If EXACT is true, grow exactly, else grow + exponentially. As a special case, if the vector had not been + allocated and and RESERVE is 0, no vector will be created. */ + +template<typename T, typename A> +void +va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact + MEM_STAT_DECL) +{ + unsigned alloc + = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); + if (!alloc) + { + ::ggc_free (v); + v = NULL; + return; + } + + /* Calculate the amount of space we want. */ + size_t size = vec<T, A, vl_embed>::embedded_size (alloc); + + /* Ask the allocator how much space it will really give us. */ + size = ::ggc_round_alloc_size (size); + + /* Adjust the number of slots accordingly. */ + size_t vec_offset = sizeof (vec_prefix); + size_t elt_size = sizeof (T); + alloc = (size - vec_offset) / elt_size; + + /* And finally, recalculate the amount of space we ask for. */ + size = vec_offset + alloc * elt_size; + + unsigned nelem = v ? v->length () : 0; + v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc_stat (v, size + PASS_MEM_STAT)); + v->embedded_init (alloc, nelem); +} + + +/* Allocator type for GC vectors. This is for vectors of types + atomics w.r.t. collection, so allocation and deallocation is + completely inherited from va_gc. */ +struct va_gc_atomic : va_gc +{ +}; + + +/* Generic vector template. Default values for A and L indicate the + most commonly used strategies. + + FIXME - Ideally, they would all be vl_ptr to encourage using regular + instances for vectors, but the existing GTY machinery is limited + in that it can only deal with GC objects that are pointers + themselves. + + This means that vector operations that need to deal with + potentially NULL pointers, must be provided as free + functions (see the vec_safe_* functions above). */ +template<typename T, + typename A = va_heap, + typename L = typename A::default_layout> +struct GTY((user)) vec +{ +}; + +/* Type to provide NULL values for vec<T, A, L>. This is used to + provide nil initializers for vec instances. Since vec must be + a POD, we cannot have proper ctor/dtor for it. To initialize + a vec instance, you can assign it the value vNULL. */ +struct vnull +{ + template <typename T, typename A, typename L> + operator vec<T, A, L> () { return vec<T, A, L>(); } +}; +extern vnull vNULL; + + +/* Embeddable vector. These vectors are suitable to be embedded + in other data structures so that they can be pre-allocated in a + contiguous memory block. + + Embeddable vectors are implemented using the trailing array idiom, + thus they are not resizeable without changing the address of the + vector object itself. This means you cannot have variables or + fields of embeddable vector type -- always use a pointer to a + vector. The one exception is the final field of a structure, which + could be a vector type. + + You will have to use the embedded_size & embedded_init calls to + create such objects, and they will not be resizeable (so the 'safe' + allocation variants are not available). + + Properties: + + - The whole vector and control data are allocated in a single + contiguous block. It uses the trailing-vector idiom, so + allocation must reserve enough space for all the elements + in the vector plus its control data. + - The vector cannot be re-allocated. + - The vector cannot grow nor shrink. + - No indirections needed for access/manipulation. + - It requires 2 words of storage (prior to vector allocation). */ + +template<typename T, typename A> +struct GTY((user)) vec<T, A, vl_embed> +{ +public: + unsigned allocated (void) const { return m_vecpfx.m_alloc; } + unsigned length (void) const { return m_vecpfx.m_num; } + bool is_empty (void) const { return m_vecpfx.m_num == 0; } + T *address (void) { return m_vecdata; } + const T *address (void) const { return m_vecdata; } + const T &operator[] (unsigned) const; + T &operator[] (unsigned); + T &last (void); + bool space (unsigned) const; + bool iterate (unsigned, T *) const; + bool iterate (unsigned, T **) const; + vec *copy (ALONE_CXX_MEM_STAT_INFO) const; + void splice (vec &); + void splice (vec *src); + T *quick_push (const T &); + T &pop (void); + void truncate (unsigned); + void quick_insert (unsigned, const T &); + void ordered_remove (unsigned); + void unordered_remove (unsigned); + void block_remove (unsigned, unsigned); + void qsort (int (*) (const void *, const void *)); + T *bsearch (const void *key, int (*compar)(const void *, const void *)); + unsigned lower_bound (T, bool (*)(const T &, const T &)) const; + static size_t embedded_size (unsigned); + void embedded_init (unsigned, unsigned = 0, unsigned = 0); + void quick_grow (unsigned len); + void quick_grow_cleared (unsigned len); + + /* vec class can access our internal data and functions. */ + template <typename, typename, typename> friend struct vec; + + /* The allocator types also need access to our internals. */ + friend struct va_gc; + friend struct va_gc_atomic; + friend struct va_heap; + + /* FIXME - These fields should be private, but we need to cater to + compilers that have stricter notions of PODness for types. */ + vec_prefix m_vecpfx; + T m_vecdata[1]; +}; + + +/* Convenience wrapper functions to use when dealing with pointers to + embedded vectors. Some functionality for these vectors must be + provided via free functions for these reasons: + + 1- The pointer may be NULL (e.g., before initial allocation). + + 2- When the vector needs to grow, it must be reallocated, so + the pointer will change its value. + + Because of limitations with the current GC machinery, all vectors + in GC memory *must* be pointers. */ + + +/* If V contains no room for NELEMS elements, return false. Otherwise, + return true. */ +template<typename T, typename A> +inline bool +vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems) +{ + return v ? v->space (nelems) : nelems == 0; +} + + +/* If V is NULL, return 0. Otherwise, return V->length(). */ +template<typename T, typename A> +inline unsigned +vec_safe_length (const vec<T, A, vl_embed> *v) +{ + return v ? v->length () : 0; +} + + +/* If V is NULL, return NULL. Otherwise, return V->address(). */ +template<typename T, typename A> +inline T * +vec_safe_address (vec<T, A, vl_embed> *v) +{ + return v ? v->address () : NULL; +} + + +/* If V is NULL, return true. Otherwise, return V->is_empty(). */ +template<typename T, typename A> +inline bool +vec_safe_is_empty (vec<T, A, vl_embed> *v) +{ + return v ? v->is_empty () : true; +} + + +/* If V does not have space for NELEMS elements, call + V->reserve(NELEMS, EXACT). */ +template<typename T, typename A> +inline bool +vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false + CXX_MEM_STAT_INFO) +{ + bool extend = nelems ? !vec_safe_space (v, nelems) : false; + if (extend) + A::reserve (v, nelems, exact PASS_MEM_STAT); + return extend; +} + +template<typename T, typename A> +inline bool +vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems + CXX_MEM_STAT_INFO) +{ + return vec_safe_reserve (v, nelems, true PASS_MEM_STAT); +} + + +/* Allocate GC memory for V with space for NELEMS slots. If NELEMS + is 0, V is initialized to NULL. */ + +template<typename T, typename A> +inline void +vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO) +{ + v = NULL; + vec_safe_reserve (v, nelems, false PASS_MEM_STAT); +} + + +/* Free the GC memory allocated by vector V and set it to NULL. */ + +template<typename T, typename A> +inline void +vec_free (vec<T, A, vl_embed> *&v) +{ + A::release (v); +} + + +/* Grow V to length LEN. Allocate it, if necessary. */ +template<typename T, typename A> +inline void +vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) +{ + unsigned oldlen = vec_safe_length (v); + gcc_checking_assert (len >= oldlen); + vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT); + v->quick_grow (len); +} + + +/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */ +template<typename T, typename A> +inline void +vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) +{ + unsigned oldlen = vec_safe_length (v); + vec_safe_grow (v, len PASS_MEM_STAT); + memset (&(v->address ()[oldlen]), 0, sizeof (T) * (len - oldlen)); +} + + +/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */ +template<typename T, typename A> +inline bool +vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr) +{ + if (v) + return v->iterate (ix, ptr); + else + { + *ptr = 0; + return false; + } +} + +template<typename T, typename A> +inline bool +vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr) +{ + if (v) + return v->iterate (ix, ptr); + else + { + *ptr = 0; + return false; + } +} + + +/* If V has no room for one more element, reallocate it. Then call + V->quick_push(OBJ). */ +template<typename T, typename A> +inline T * +vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO) +{ + vec_safe_reserve (v, 1, false PASS_MEM_STAT); + return v->quick_push (obj); +} + + +/* if V has no room for one more element, reallocate it. Then call + V->quick_insert(IX, OBJ). */ +template<typename T, typename A> +inline void +vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj + CXX_MEM_STAT_INFO) +{ + vec_safe_reserve (v, 1, false PASS_MEM_STAT); + v->quick_insert (ix, obj); +} + + +/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */ +template<typename T, typename A> +inline void +vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size) +{ + if (v) + v->truncate (size); +} + + +/* If SRC is not NULL, return a pointer to a copy of it. */ +template<typename T, typename A> +inline vec<T, A, vl_embed> * +vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO) +{ + return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL; +} + +/* Copy the elements from SRC to the end of DST as if by memcpy. + Reallocate DST, if necessary. */ +template<typename T, typename A> +inline void +vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src + CXX_MEM_STAT_INFO) +{ + unsigned src_len = vec_safe_length (src); + if (src_len) + { + vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len + PASS_MEM_STAT); + dst->splice (*src); + } +} + + +/* Index into vector. Return the IX'th element. IX must be in the + domain of the vector. */ + +template<typename T, typename A> +inline const T & +vec<T, A, vl_embed>::operator[] (unsigned ix) const +{ + gcc_checking_assert (ix < m_vecpfx.m_num); + return m_vecdata[ix]; +} + +template<typename T, typename A> +inline T & +vec<T, A, vl_embed>::operator[] (unsigned ix) +{ + gcc_checking_assert (ix < m_vecpfx.m_num); + return m_vecdata[ix]; +} + + +/* Get the final element of the vector, which must not be empty. */ + +template<typename T, typename A> +inline T & +vec<T, A, vl_embed>::last (void) +{ + gcc_checking_assert (m_vecpfx.m_num > 0); + return (*this)[m_vecpfx.m_num - 1]; +} + + +/* If this vector has space for NELEMS additional entries, return + true. You usually only need to use this if you are doing your + own vector reallocation, for instance on an embedded vector. This + returns true in exactly the same circumstances that vec::reserve + will. */ + +template<typename T, typename A> +inline bool +vec<T, A, vl_embed>::space (unsigned nelems) const +{ + return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems; +} + + +/* Return iteration condition and update PTR to point to the IX'th + element of this vector. Use this to iterate over the elements of a + vector as follows, + + for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++) + continue; */ + +template<typename T, typename A> +inline bool +vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const +{ + if (ix < m_vecpfx.m_num) + { + *ptr = m_vecdata[ix]; + return true; + } + else + { + *ptr = 0; + return false; + } +} + + +/* Return iteration condition and update *PTR to point to the + IX'th element of this vector. Use this to iterate over the + elements of a vector as follows, + + for (ix = 0; v->iterate (ix, &ptr); ix++) + continue; + + This variant is for vectors of objects. */ + +template<typename T, typename A> +inline bool +vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const +{ + if (ix < m_vecpfx.m_num) + { + *ptr = CONST_CAST (T *, &m_vecdata[ix]); + return true; + } + else + { + *ptr = 0; + return false; + } +} + + +/* Return a pointer to a copy of this vector. */ + +template<typename T, typename A> +inline vec<T, A, vl_embed> * +vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const +{ + vec<T, A, vl_embed> *new_vec = NULL; + unsigned len = length (); + if (len) + { + vec_alloc (new_vec, len PASS_MEM_STAT); + new_vec->embedded_init (len, len); + memcpy (new_vec->address (), m_vecdata, sizeof (T) * len); + } + return new_vec; +} + + +/* Copy the elements from SRC to the end of this vector as if by memcpy. + The vector must have sufficient headroom available. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src) +{ + unsigned len = src.length (); + if (len) + { + gcc_checking_assert (space (len)); + memcpy (address () + length (), src.address (), len * sizeof (T)); + m_vecpfx.m_num += len; + } +} + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src) +{ + if (src) + splice (*src); +} + + +/* Push OBJ (a new element) onto the end of the vector. There must be + sufficient space in the vector. Return a pointer to the slot + where OBJ was inserted. */ + +template<typename T, typename A> +inline T * +vec<T, A, vl_embed>::quick_push (const T &obj) +{ + gcc_checking_assert (space (1)); + T *slot = &m_vecdata[m_vecpfx.m_num++]; + *slot = obj; + return slot; +} + + +/* Pop and return the last element off the end of the vector. */ + +template<typename T, typename A> +inline T & +vec<T, A, vl_embed>::pop (void) +{ + gcc_checking_assert (length () > 0); + return m_vecdata[--m_vecpfx.m_num]; +} + + +/* Set the length of the vector to SIZE. The new length must be less + than or equal to the current length. This is an O(1) operation. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::truncate (unsigned size) +{ + gcc_checking_assert (length () >= size); + m_vecpfx.m_num = size; +} + + +/* Insert an element, OBJ, at the IXth position of this vector. There + must be sufficient space. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj) +{ + gcc_checking_assert (length () < allocated ()); + gcc_checking_assert (ix <= length ()); + T *slot = &m_vecdata[ix]; + memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); + *slot = obj; +} + + +/* Remove an element from the IXth position of this vector. Ordering of + remaining elements is preserved. This is an O(N) operation due to + memmove. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::ordered_remove (unsigned ix) +{ + gcc_checking_assert (ix < length ()); + T *slot = &m_vecdata[ix]; + memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); +} + + +/* Remove an element from the IXth position of this vector. Ordering of + remaining elements is destroyed. This is an O(1) operation. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::unordered_remove (unsigned ix) +{ + gcc_checking_assert (ix < length ()); + m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; +} + + +/* Remove LEN elements starting at the IXth. Ordering is retained. + This is an O(N) operation due to memmove. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) +{ + gcc_checking_assert (ix + len <= length ()); + T *slot = &m_vecdata[ix]; + m_vecpfx.m_num -= len; + memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); +} + + +/* Sort the contents of this vector with qsort. CMP is the comparison + function to pass to qsort. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) +{ + if (length () > 1) + ::qsort (address (), length (), sizeof (T), cmp); +} + + +/* Search the contents of the sorted vector with a binary search. + CMP is the comparison function to pass to bsearch. */ + +template<typename T, typename A> +inline T * +vec<T, A, vl_embed>::bsearch (const void *key, + int (*compar) (const void *, const void *)) +{ + const void *base = this->address (); + size_t nmemb = this->length (); + size_t size = sizeof (T); + /* The following is a copy of glibc stdlib-bsearch.h. */ + size_t l, u, idx; + const void *p; + int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (const void *) (((const char *) base) + (idx * size)); + comparison = (*compar) (key, p); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = idx + 1; + else + return (T *)const_cast<void *>(p); + } + + return NULL; +} + + +/* Find and return the first position in which OBJ could be inserted + without changing the ordering of this vector. LESSTHAN is a + function that returns true if the first argument is strictly less + than the second. */ + +template<typename T, typename A> +unsigned +vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) + const +{ + unsigned int len = length (); + unsigned int half, middle; + unsigned int first = 0; + while (len > 0) + { + half = len / 2; + middle = first; + middle += half; + T middle_elem = (*this)[middle]; + if (lessthan (middle_elem, obj)) + { + first = middle; + ++first; + len = len - half - 1; + } + else + len = half; + } + return first; +} + + +/* Return the number of bytes needed to embed an instance of an + embeddable vec inside another data structure. + + Use these methods to determine the required size and initialization + of a vector V of type T embedded within another structure (as the + final member): + + size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); + void v->embedded_init (unsigned alloc, unsigned num); + + These allow the caller to perform the memory allocation. */ + +template<typename T, typename A> +inline size_t +vec<T, A, vl_embed>::embedded_size (unsigned alloc) +{ + typedef vec<T, A, vl_embed> vec_embedded; + return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); +} + + +/* Initialize the vector to contain room for ALLOC elements and + NUM active elements. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) +{ + m_vecpfx.m_alloc = alloc; + m_vecpfx.m_using_auto_storage = aut; + m_vecpfx.m_num = num; +} + + +/* Grow the vector to a specific length. LEN must be as long or longer than + the current length. The new elements are uninitialized. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::quick_grow (unsigned len) +{ + gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); + m_vecpfx.m_num = len; +} + + +/* Grow the vector to a specific length. LEN must be as long or longer than + the current length. The new elements are initialized to zero. */ + +template<typename T, typename A> +inline void +vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) +{ + unsigned oldlen = length (); + quick_grow (len); + memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen)); +} + + +/* Garbage collection support for vec<T, A, vl_embed>. */ + +template<typename T> +void +gt_ggc_mx (vec<T, va_gc> *v) +{ + extern void gt_ggc_mx (T &); + for (unsigned i = 0; i < v->length (); i++) + gt_ggc_mx ((*v)[i]); +} + +template<typename T> +void +gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) +{ + /* Nothing to do. Vectors of atomic types wrt GC do not need to + be traversed. */ +} + + +/* PCH support for vec<T, A, vl_embed>. */ + +template<typename T, typename A> +void +gt_pch_nx (vec<T, A, vl_embed> *v) +{ + extern void gt_pch_nx (T &); + for (unsigned i = 0; i < v->length (); i++) + gt_pch_nx ((*v)[i]); +} + +template<typename T, typename A> +void +gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) +{ + for (unsigned i = 0; i < v->length (); i++) + op (&((*v)[i]), cookie); +} + +template<typename T, typename A> +void +gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) +{ + extern void gt_pch_nx (T *, gt_pointer_operator, void *); + for (unsigned i = 0; i < v->length (); i++) + gt_pch_nx (&((*v)[i]), op, cookie); +} + + +/* Space efficient vector. These vectors can grow dynamically and are + allocated together with their control data. They are suited to be + included in data structures. Prior to initial allocation, they + only take a single word of storage. + + These vectors are implemented as a pointer to an embeddable vector. + The semantics allow for this pointer to be NULL to represent empty + vectors. This way, empty vectors occupy minimal space in the + structure containing them. + + Properties: + + - The whole vector and control data are allocated in a single + contiguous block. + - The whole vector may be re-allocated. + - Vector data may grow and shrink. + - Access and manipulation requires a pointer test and + indirection. + - It requires 1 word of storage (prior to vector allocation). + + + Limitations: + + These vectors must be PODs because they are stored in unions. + (http://en.wikipedia.org/wiki/Plain_old_data_structures). + As long as we use C++03, we cannot have constructors nor + destructors in classes that are stored in unions. */ + +template<typename T> +struct vec<T, va_heap, vl_ptr> +{ +public: + /* Memory allocation and deallocation for the embedded vector. + Needed because we cannot have proper ctors/dtors defined. */ + void create (unsigned nelems CXX_MEM_STAT_INFO); + void release (void); + + /* Vector operations. */ + bool exists (void) const + { return m_vec != NULL; } + + bool is_empty (void) const + { return m_vec ? m_vec->is_empty () : true; } + + unsigned length (void) const + { return m_vec ? m_vec->length () : 0; } + + T *address (void) + { return m_vec ? m_vec->m_vecdata : NULL; } + + const T *address (void) const + { return m_vec ? m_vec->m_vecdata : NULL; } + + const T &operator[] (unsigned ix) const + { return (*m_vec)[ix]; } + + bool operator!=(const vec &other) const + { return !(*this == other); } + + bool operator==(const vec &other) const + { return address () == other.address (); } + + T &operator[] (unsigned ix) + { return (*m_vec)[ix]; } + + T &last (void) + { return m_vec->last (); } + + bool space (int nelems) const + { return m_vec ? m_vec->space (nelems) : nelems == 0; } + + bool iterate (unsigned ix, T *p) const; + bool iterate (unsigned ix, T **p) const; + vec copy (ALONE_CXX_MEM_STAT_INFO) const; + bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO); + bool reserve_exact (unsigned CXX_MEM_STAT_INFO); + void splice (vec &); + void safe_splice (vec & CXX_MEM_STAT_INFO); + T *quick_push (const T &); + T *safe_push (const T &CXX_MEM_STAT_INFO); + T &pop (void); + void truncate (unsigned); + void safe_grow (unsigned CXX_MEM_STAT_INFO); + void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); + void quick_grow (unsigned); + void quick_grow_cleared (unsigned); + void quick_insert (unsigned, const T &); + void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); + void ordered_remove (unsigned); + void unordered_remove (unsigned); + void block_remove (unsigned, unsigned); + void qsort (int (*) (const void *, const void *)); + T *bsearch (const void *key, int (*compar)(const void *, const void *)); + unsigned lower_bound (T, bool (*)(const T &, const T &)) const; + + bool using_auto_storage () const; + + /* FIXME - This field should be private, but we need to cater to + compilers that have stricter notions of PODness for types. */ + vec<T, va_heap, vl_embed> *m_vec; +}; + + +/* auto_vec is a subclass of vec that automatically manages creating and + releasing the internal vector. If N is non zero then it has N elements of + internal storage. The default is no internal storage, and you probably only + want to ask for internal storage for vectors on the stack because if the + size of the vector is larger than the internal storage that space is wasted. + */ +template<typename T, size_t N = 0> +class auto_vec : public vec<T, va_heap> +{ +public: + auto_vec () + { + m_auto.embedded_init (MAX (N, 2), 0, 1); + this->m_vec = &m_auto; + } + + ~auto_vec () + { + this->release (); + } + +private: + vec<T, va_heap, vl_embed> m_auto; + T m_data[MAX (N - 1, 1)]; +}; + +/* auto_vec is a sub class of vec whose storage is released when it is + destroyed. */ +template<typename T> +class auto_vec<T, 0> : public vec<T, va_heap> +{ +public: + auto_vec () { this->m_vec = NULL; } + auto_vec (size_t n) { this->create (n); } + ~auto_vec () { this->release (); } +}; + + +/* Allocate heap memory for pointer V and create the internal vector + with space for NELEMS elements. If NELEMS is 0, the internal + vector is initialized to empty. */ + +template<typename T> +inline void +vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) +{ + v = new vec<T>; + v->create (nelems PASS_MEM_STAT); +} + + +/* Conditionally allocate heap memory for VEC and its internal vector. */ + +template<typename T> +inline void +vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) +{ + if (!vec) + vec_alloc (vec, nelems PASS_MEM_STAT); +} + + +/* Free the heap memory allocated by vector V and set it to NULL. */ + +template<typename T> +inline void +vec_free (vec<T> *&v) +{ + if (v == NULL) + return; + + v->release (); + delete v; + v = NULL; +} + + +/* Return iteration condition and update PTR to point to the IX'th + element of this vector. Use this to iterate over the elements of a + vector as follows, + + for (ix = 0; v.iterate (ix, &ptr); ix++) + continue; */ + +template<typename T> +inline bool +vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const +{ + if (m_vec) + return m_vec->iterate (ix, ptr); + else + { + *ptr = 0; + return false; + } +} + + +/* Return iteration condition and update *PTR to point to the + IX'th element of this vector. Use this to iterate over the + elements of a vector as follows, + + for (ix = 0; v->iterate (ix, &ptr); ix++) + continue; + + This variant is for vectors of objects. */ + +template<typename T> +inline bool +vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const +{ + if (m_vec) + return m_vec->iterate (ix, ptr); + else + { + *ptr = 0; + return false; + } +} + + +/* Convenience macro for forward iteration. */ +#define FOR_EACH_VEC_ELT(V, I, P) \ + for (I = 0; (V).iterate ((I), &(P)); ++(I)) + +#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ + for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) + +/* Likewise, but start from FROM rather than 0. */ +#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ + for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) + +/* Convenience macro for reverse iteration. */ +#define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ + for (I = (V).length () - 1; \ + (V).iterate ((I), &(P)); \ + (I)--) + +#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ + for (I = vec_safe_length (V) - 1; \ + vec_safe_iterate ((V), (I), &(P)); \ + (I)--) + + +/* Return a copy of this vector. */ + +template<typename T> +inline vec<T, va_heap, vl_ptr> +vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const +{ + vec<T, va_heap, vl_ptr> new_vec = vNULL; + if (length ()) + new_vec.m_vec = m_vec->copy (); + return new_vec; +} + + +/* Ensure that the vector has at least RESERVE slots available (if + EXACT is false), or exactly RESERVE slots available (if EXACT is + true). + + This may create additional headroom if EXACT is false. + + Note that this can cause the embedded vector to be reallocated. + Returns true iff reallocation actually occurred. */ + +template<typename T> +inline bool +vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) +{ + if (space (nelems)) + return false; + + /* For now play a game with va_heap::reserve to hide our auto storage if any, + this is necessary because it doesn't have enough information to know the + embedded vector is in auto storage, and so should not be freed. */ + vec<T, va_heap, vl_embed> *oldvec = m_vec; + unsigned int oldsize = 0; + bool handle_auto_vec = m_vec && using_auto_storage (); + if (handle_auto_vec) + { + m_vec = NULL; + oldsize = oldvec->length (); + nelems += oldsize; + } + + va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); + if (handle_auto_vec) + { + memcpy (m_vec->address (), oldvec->address (), sizeof (T) * oldsize); + m_vec->m_vecpfx.m_num = oldsize; + } + + return true; +} + + +/* Ensure that this vector has exactly NELEMS slots available. This + will not create additional headroom. Note this can cause the + embedded vector to be reallocated. Returns true iff reallocation + actually occurred. */ + +template<typename T> +inline bool +vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) +{ + return reserve (nelems, true PASS_MEM_STAT); +} + + +/* Create the internal vector and reserve NELEMS for it. This is + exactly like vec::reserve, but the internal vector is + unconditionally allocated from scratch. The old one, if it + existed, is lost. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) +{ + m_vec = NULL; + if (nelems > 0) + reserve_exact (nelems PASS_MEM_STAT); +} + + +/* Free the memory occupied by the embedded vector. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::release (void) +{ + if (!m_vec) + return; + + if (using_auto_storage ()) + { + m_vec->m_vecpfx.m_num = 0; + return; + } + + va_heap::release (m_vec); +} + +/* Copy the elements from SRC to the end of this vector as if by memcpy. + SRC and this vector must be allocated with the same memory + allocation mechanism. This vector is assumed to have sufficient + headroom available. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::splice (vec<T, va_heap, vl_ptr> &src) +{ + if (src.m_vec) + m_vec->splice (*(src.m_vec)); +} + + +/* Copy the elements in SRC to the end of this vector as if by memcpy. + SRC and this vector must be allocated with the same mechanism. + If there is not enough headroom in this vector, it will be reallocated + as needed. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::safe_splice (vec<T, va_heap, vl_ptr> &src + MEM_STAT_DECL) +{ + if (src.length ()) + { + reserve_exact (src.length ()); + splice (src); + } +} + + +/* Push OBJ (a new element) onto the end of the vector. There must be + sufficient space in the vector. Return a pointer to the slot + where OBJ was inserted. */ + +template<typename T> +inline T * +vec<T, va_heap, vl_ptr>::quick_push (const T &obj) +{ + return m_vec->quick_push (obj); +} + + +/* Push a new element OBJ onto the end of this vector. Reallocates + the embedded vector, if needed. Return a pointer to the slot where + OBJ was inserted. */ + +template<typename T> +inline T * +vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) +{ + reserve (1, false PASS_MEM_STAT); + return quick_push (obj); +} + + +/* Pop and return the last element off the end of the vector. */ + +template<typename T> +inline T & +vec<T, va_heap, vl_ptr>::pop (void) +{ + return m_vec->pop (); +} + + +/* Set the length of the vector to LEN. The new length must be less + than or equal to the current length. This is an O(1) operation. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::truncate (unsigned size) +{ + if (m_vec) + m_vec->truncate (size); + else + gcc_checking_assert (size == 0); +} + + +/* Grow the vector to a specific length. LEN must be as long or + longer than the current length. The new elements are + uninitialized. Reallocate the internal vector, if needed. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) +{ + unsigned oldlen = length (); + gcc_checking_assert (oldlen <= len); + reserve_exact (len - oldlen PASS_MEM_STAT); + m_vec->quick_grow (len); +} + + +/* Grow the embedded vector to a specific length. LEN must be as + long or longer than the current length. The new elements are + initialized to zero. Reallocate the internal vector, if needed. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) +{ + unsigned oldlen = length (); + safe_grow (len PASS_MEM_STAT); + memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen)); +} + + +/* Same as vec::safe_grow but without reallocation of the internal vector. + If the vector cannot be extended, a runtime assertion will be triggered. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) +{ + gcc_checking_assert (m_vec); + m_vec->quick_grow (len); +} + + +/* Same as vec::quick_grow_cleared but without reallocation of the + internal vector. If the vector cannot be extended, a runtime + assertion will be triggered. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) +{ + gcc_checking_assert (m_vec); + m_vec->quick_grow_cleared (len); +} + + +/* Insert an element, OBJ, at the IXth position of this vector. There + must be sufficient space. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) +{ + m_vec->quick_insert (ix, obj); +} + + +/* Insert an element, OBJ, at the IXth position of the vector. + Reallocate the embedded vector, if necessary. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) +{ + reserve (1, false PASS_MEM_STAT); + quick_insert (ix, obj); +} + + +/* Remove an element from the IXth position of this vector. Ordering of + remaining elements is preserved. This is an O(N) operation due to + a memmove. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) +{ + m_vec->ordered_remove (ix); +} + + +/* Remove an element from the IXth position of this vector. Ordering + of remaining elements is destroyed. This is an O(1) operation. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) +{ + m_vec->unordered_remove (ix); +} + + +/* Remove LEN elements starting at the IXth. Ordering is retained. + This is an O(N) operation due to memmove. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) +{ + m_vec->block_remove (ix, len); +} + + +/* Sort the contents of this vector with qsort. CMP is the comparison + function to pass to qsort. */ + +template<typename T> +inline void +vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) +{ + if (m_vec) + m_vec->qsort (cmp); +} + + +/* Search the contents of the sorted vector with a binary search. + CMP is the comparison function to pass to bsearch. */ + +template<typename T> +inline T * +vec<T, va_heap, vl_ptr>::bsearch (const void *key, + int (*cmp) (const void *, const void *)) +{ + if (m_vec) + return m_vec->bsearch (key, cmp); + return NULL; +} + + +/* Find and return the first position in which OBJ could be inserted + without changing the ordering of this vector. LESSTHAN is a + function that returns true if the first argument is strictly less + than the second. */ + +template<typename T> +inline unsigned +vec<T, va_heap, vl_ptr>::lower_bound (T obj, + bool (*lessthan)(const T &, const T &)) + const +{ + return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; +} + +template<typename T> +inline bool +vec<T, va_heap, vl_ptr>::using_auto_storage () const +{ + return m_vec->m_vecpfx.m_using_auto_storage; +} + +#if (GCC_VERSION >= 3000) +# pragma GCC poison m_vec m_vecpfx m_vecdata +#endif + +#endif // GCC_VEC_H |