/* Vector API for GNU compiler.
- Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2013 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.
#ifndef GCC_VEC_H
#define GCC_VEC_H
-#include "statistics.h" /* For MEM_STAT_DECL. */
-
-/* The macros here implement a set of templated vector types and
- associated interfaces. These templates are implemented with
- macros, as we're not in C++ land. The interface functions are
- typesafe and use static inline functions, sometimes backed by
- out-of-line generic functions. The vectors are designed to
- interoperate with the GTY machinery.
-
- Because of the different behavior of structure objects, scalar
- objects and of pointers, there are three flavors, one for each of
- these variants. Both the structure object and pointer variants
- pass pointers to objects around -- in the former case the pointers
- are stored into the vector and in the latter case the pointers are
- dereferenced and the objects copied into the vector. The scalar
- object variant is suitable for int-like objects, and the vector
- elements are returned by value.
-
- There are both 'index' and 'iterate' accessors. 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.
-
- The 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
- 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 probably not be resizeable (so
- don't use the 'safe' allocation variants). The trailing array
- idiom is used (rather than a pointer to an array of data), because,
- if we allow NULL to also represent an empty vector, empty vectors
- occupy minimal space in the structure containing them.
+/* 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
'lower_bound' function will determine where to place an item in the
array using insert that will maintain sorted order.
- When a vector type is defined, first a non-memory managed version
- is created. You can then define either or both garbage collected
- and heap allocated versions. The allocation mechanism is specified
- when the type is defined, and is therefore part of the type. If
- you need both gc'd and heap allocated versions, you still must have
- *exactly* one definition of the common non-memory managed base vector.
+ 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.
+
+ - Stack: allocation is done using alloca.
+
+ - 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.
- Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to
- get the non-memory allocation version, and then a
- DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed
- vectors. Variables of vector type are declared using a
- VEC(TYPEDEF,ALLOC) macro. The ALLOC argument specifies the
- allocation strategy, and can be either 'gc' or 'heap' for garbage
- collected and heap allocated respectively. It can be 'none' to get
- a vector that must be explicitly allocated (for instance as a
- trailing array of another structure). The characters O, P and I
- indicate whether TYPEDEF is a pointer (P), object (O) or integral
- (I) type. Be careful to pick the correct one, as you'll get an
- awkward and inefficient API if you use the wrong one. There is a
- check, which results in a compile-time warning, for the P and I
- versions, but there is no check for the O versions, as that is not
- possible in plain C. Due to the way GTY works, you must annotate
- any structures you wish to insert or reference from a vector with a
- GTY(()) tag. You need to do this even if you never declare the GC
- allocated variants.
+ Notes on the different layout strategies
- An example of their use would be,
+ * 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).
- DEF_VEC_P(tree); // non-managed tree vector.
- DEF_VEC_ALLOC_P(tree,gc); // gc'd vector of tree pointers. This must
- // appear at file scope.
+
+ * 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 {
- VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers.
+ // A space-efficient vector of tree pointers in GC memory.
+ vec<tree, va_gc, vl_ptr> v;
};
struct my_struct *s;
- if (VEC_length(tree,s->v)) { we have some contents }
- VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
- for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
+ 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 }
-
*/
-/* Macros to invoke API calls. A single macro works for both pointer
- and object vectors, but the argument and return types might well be
- different. In each macro, T is the typedef of the vector elements,
- and A is the allocation strategy. The allocation strategy is only
- present when it is required. Some of these macros pass the vector,
- V, by reference (by taking its address), this is noted in the
- descriptions. */
+/* 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);
+
+ /* 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;
+ friend struct va_stack;
+
+ unsigned alloc_;
+ unsigned num_;
+};
+
+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.
+ va_stack - Allocation uses alloca. */
+
+/* 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->vecpfx_ : 0, reserve, exact);
+ if (!alloc)
+ {
+ release (v);
+ return;
+ }
+
+ if (GATHER_STATISTICS && v)
+ v->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->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->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) { 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->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
+{
+};
+
+
+/* Allocator type for stack vectors. */
+struct va_stack
+{
+ /* Use vl_ptr as the default layout for stack vectors. */
+ typedef vl_ptr default_layout;
+
+ template<typename T>
+ static void alloc (vec<T, va_stack, vl_ptr>&, unsigned,
+ vec<T, va_stack, vl_embed> *);
+
+ template <typename T>
+ static void reserve (vec<T, va_stack, vl_embed> *&, unsigned, bool
+ CXX_MEM_STAT_INFO);
+
+ template <typename T>
+ static void release (vec<T, va_stack, vl_embed> *&);
+};
+
+/* Helper functions to keep track of vectors allocated on the stack. */
+void register_stack_vec (void *);
+int stack_vec_register_index (void *);
+void unregister_stack_vec (unsigned);
+
+/* Allocate a vector V which uses alloca for the initial allocation.
+ SPACE is space allocated using alloca. NELEMS is the number of
+ entries allocated. */
+
+template<typename T>
+void
+va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems,
+ vec<T, va_stack, vl_embed> *space)
+{
+ v.vec_ = space;
+ register_stack_vec (static_cast<void *> (v.vec_));
+ v.vec_->embedded_init (nelems, 0);
+}
+
+
+/* Reserve NELEMS slots for a vector initially allocated on the stack.
+ When this happens, we switch back to heap allocation. We remove
+ the vector from stack_vecs, if it is there, since we no longer need
+ to avoid freeing it. If EXACT is true, grow exactly, otherwise
+ grow exponentially. */
+
+template<typename T>
+void
+va_stack::reserve (vec<T, va_stack, vl_embed> *&v, unsigned nelems, bool exact
+ MEM_STAT_DECL)
+{
+ int ix = stack_vec_register_index (static_cast<void *> (v));
+ if (ix >= 0)
+ unregister_stack_vec (ix);
+ else
+ {
+ /* V is already on the heap. */
+ va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v),
+ nelems, exact PASS_MEM_STAT);
+ return;
+ }
+
+ /* Move VEC_ to the heap. */
+ nelems += v->vecpfx_.num_;
+ vec<T, va_stack, vl_embed> *oldvec = v;
+ v = NULL;
+ va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&>(v), nelems,
+ exact PASS_MEM_STAT);
+ if (v && oldvec)
+ {
+ v->vecpfx_.num_ = oldvec->length ();
+ memcpy (v->vecdata_,
+ oldvec->vecdata_,
+ oldvec->length () * sizeof (T));
+ }
+}
+
+
+/* Free a vector allocated on the stack. Don't actually free it if we
+ find it in the hash table. */
+
+template<typename T>
+void
+va_stack::release (vec<T, va_stack, vl_embed> *&v)
+{
+ if (v == NULL)
+ return;
+
+ int ix = stack_vec_register_index (static_cast<void *> (v));
+ if (ix >= 0)
+ {
+ unregister_stack_vec (ix);
+ v = NULL;
+ }
+ else
+ {
+ /* The vector was not on the list of vectors allocated on the stack, so it
+ must be allocated on the heap. */
+ va_heap::release (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v));
+ }
+}
+
+
+/* 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 vecpfx_.alloc_; }
+ unsigned length (void) const { return vecpfx_.num_; }
+ bool is_empty (void) const { return vecpfx_.num_ == 0; }
+ T *address (void) { return vecdata_; }
+ const T *address (void) const { return 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 *));
+ unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+ static size_t embedded_size (unsigned);
+ void embedded_init (unsigned, 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;
+ friend struct va_stack;
+
+ /* FIXME - These fields should be private, but we need to cater to
+ compilers that have stricter notions of PODness for types. */
+ vec_prefix vecpfx_;
+ T 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;
+}
+
-/* Length of vector
- unsigned VEC_T_length(const VEC(T) *v);
+/* 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;
+}
- Return the number of active elements in V. V can be NULL, in which
- case zero is returned. */
-#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
+/* 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;
+}
-/* Check if vector is empty
- int VEC_T_empty(const VEC(T) *v);
+/* 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;
+}
- Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
-#define VEC_empty(T,V) (VEC_length (T,V) == 0)
+/* 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);
+}
-/* Get the final element of the vector.
- T VEC_T_last(VEC(T) *v); // Integer
- T VEC_T_last(VEC(T) *v); // Pointer
- T *VEC_T_last(VEC(T) *v); // Object
- Return the final element. V must not be empty. */
+/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
+ is 0, V is initialized to NULL. */
-#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
+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);
+}
-/* Index into vector
- T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
- T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
- T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
- Return the IX'th element. If IX must be in the domain of V. */
+/* 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));
+}
+
-#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
+/* 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)
+{
+ return src ? src->copy () : 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);
+ }
+}
-/* Iterate over vector
- int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
- int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
- int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
- Return iteration condition and update PTR to point to the IX'th
- element. At the end of iteration, sets PTR to NULL. Use this to
- iterate over the elements of a vector as follows,
+/* Index into vector. Return the IX'th element. IX must be in the
+ domain of the vector. */
- for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
+template<typename T, typename A>
+inline const T &
+vec<T, A, vl_embed>::operator[] (unsigned ix) const
+{
+ gcc_checking_assert (ix < vecpfx_.num_);
+ return vecdata_[ix];
+}
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::operator[] (unsigned ix)
+{
+ gcc_checking_assert (ix < vecpfx_.num_);
+ return 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 (vecpfx_.num_ > 0);
+ return (*this)[vecpfx_.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 vecpfx_.alloc_ - vecpfx_.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; */
-#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
+{
+ if (ix < vecpfx_.num_)
+ {
+ *ptr = vecdata_[ix];
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
-/* Convenience macro for forward iteration. */
-#define FOR_EACH_VEC_ELT(T, V, I, P) \
- for (I = 0; VEC_iterate (T, (V), (I), (P)); ++(I))
+/* 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,
-/* Likewise, but start from FROM rather than 0. */
+ for (ix = 0; v->iterate(ix, &ptr); ix++)
+ continue;
-#define FOR_EACH_VEC_ELT_FROM(T, V, I, P, FROM) \
- for (I = (FROM); VEC_iterate (T, (V), (I), (P)); ++(I))
+ This variant is for vectors of objects. */
-/* Convenience macro for reverse iteration. */
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
+{
+ if (ix < vecpfx_.num_)
+ {
+ *ptr = CONST_CAST (T *, &vecdata_[ix]);
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
-#define FOR_EACH_VEC_ELT_REVERSE(T,V,I,P) \
- for (I = VEC_length (T, (V)) - 1; \
- VEC_iterate (T, (V), (I), (P)); \
- (I)--)
-/* Allocate new vector.
- VEC(T,A) *VEC_T_A_alloc(int reserve);
+/* 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(), 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));
+ vecpfx_.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 = &vecdata_[vecpfx_.num_++];
+ *slot = obj;
+ return slot;
+}
+
- Allocate a new vector with space for RESERVE objects. If RESERVE
- is zero, NO vector is created. */
+/* Pop and return the last element off the end of the vector. */
-#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::pop (void)
+{
+ gcc_checking_assert (length () > 0);
+ return vecdata_[--vecpfx_.num_];
+}
-/* Free a vector.
- void VEC_T_A_free(VEC(T,A) *&);
- Free a vector and set it to NULL. */
+/* 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. */
-#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::truncate (unsigned size)
+{
+ gcc_checking_assert (length () >= size);
+ vecpfx_.num_ = size;
+}
-/* Use these to determine the required size and initialization of a
- vector embedded within another structure (as the final member).
- size_t VEC_T_embedded_size(int reserve);
- void VEC_T_embedded_init(VEC(T) *v, int reserve);
+/* 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 = &vecdata_[ix];
+ memmove (slot + 1, slot, (vecpfx_.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 = &vecdata_[ix];
+ memmove (slot, slot + 1, (--vecpfx_.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());
+ vecdata_[ix] = vecdata_[--vecpfx_.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 = &vecdata_[ix];
+ vecpfx_.num_ -= len;
+ memmove (slot, slot + len, (vecpfx_.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 *))
+{
+ ::qsort (address(), length(), sizeof (T), cmp);
+}
+
+
+/* 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. */
-#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N))
-#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
+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, vecdata_) + alloc * sizeof (T);
+}
-/* Copy a vector.
- VEC(T,A) *VEC_T_A_copy(VEC(T) *);
- Copy the live elements of a vector into a new vector. The new and
- old vectors need not be allocated by the same mechanism. */
+/* Initialize the vector to contain room for ALLOC elements and
+ NUM active elements. */
-#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num)
+{
+ vecpfx_.alloc_ = alloc;
+ vecpfx_.num_ = num;
+}
-/* Determine if a vector has additional capacity.
- int VEC_T_space (VEC(T) *v,int reserve)
+/* Grow the vector to a specific length. LEN must be as long or longer than
+ the current length. The new elements are uninitialized. */
- If V has space for RESERVE additional entries, return nonzero. You
- usually only need to use this if you are doing your own vector
- reallocation, for instance on an embedded vector. This returns
- nonzero in exactly the same circumstances that VEC_T_reserve
- will. */
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow (unsigned len)
+{
+ gcc_checking_assert (length () <= len && len <= vecpfx_.alloc_);
+ vecpfx_.num_ = len;
+}
-#define VEC_space(T,V,R) \
- (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
-/* Reserve space.
- int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
+/* 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. */
- Ensure that V has at least RESERVE slots available. This will
- create additional headroom. Note this can cause V to be
- reallocated. Returns nonzero iff reallocation actually
- occurred. */
+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));
+}
-#define VEC_reserve(T,A,V,R) \
- (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
-/* Reserve space exactly.
- int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
+/* Garbage collection support for vec<T, A, vl_embed>. */
- Ensure that V has at least RESERVE slots available. This will not
- create additional headroom. Note this can cause V to be
- reallocated. Returns nonzero iff reallocation actually
- occurred. */
+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]);
+}
-#define VEC_reserve_exact(T,A,V,R) \
- (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
+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. */
+}
-/* Copy elements with no reallocation
- void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
- void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Pointer
- void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Object
- Copy the elements in SRC to the end of DST as if by memcpy. DST and
- SRC need not be allocated with the same mechanism, although they most
- often will be. DST is assumed to have sufficient headroom
- available. */
+/* PCH support for vec<T, A, vl_embed>. */
-#define VEC_splice(T,DST,SRC) \
- (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
+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]);
+}
-/* Copy elements with reallocation
- void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
- void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Pointer
- void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Object
+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);
+}
- Copy the elements in SRC to the end of DST as if by memcpy. DST and
- SRC need not be allocated with the same mechanism, although they most
- often will be. DST need not have sufficient headroom and will be
- reallocated if needed. */
+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);
+}
-#define VEC_safe_splice(T,A,DST,SRC) \
- (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO))
-
-/* Push object with no reallocation
- T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
- T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
- T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
- Push a new element onto the end, returns a pointer to the slot
- filled in. For object vectors, the new value can be NULL, in which
- case NO initialization is performed. There must
- be sufficient space in the vector. */
+/* 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.
-#define VEC_quick_push(T,V,O) \
- (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
+ 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.
-/* Push object with reallocation
- T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
- T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
- T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
+ Properties:
- Push a new element onto the end, returns a pointer to the slot
- filled in. For object vectors, the new value can be NULL, in which
- case NO initialization is performed. Reallocates V, if needed. */
+ - 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).
-#define VEC_safe_push(T,A,V,O) \
- (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
-/* Pop element off end
- T VEC_T_pop (VEC(T) *v); // Integer
- T VEC_T_pop (VEC(T) *v); // Pointer
- void VEC_T_pop (VEC(T) *v); // Object
+ Limitations:
- Pop the last element off the end. Returns the element popped, for
- pointer vectors. */
+ 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. */
-#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
+template<typename T, typename A>
+struct vec<T, A, 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 vec_ != NULL; }
+
+ bool is_empty (void) const
+ { return vec_ ? vec_->is_empty() : true; }
+
+ unsigned length (void) const
+ { return vec_ ? vec_->length() : 0; }
+
+ T *address (void)
+ { return vec_ ? vec_->vecdata_ : NULL; }
+
+ const T *address (void) const
+ { return vec_ ? vec_->vecdata_ : NULL; }
+
+ const T &operator[] (unsigned ix) const
+ { return (*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 (*vec_)[ix]; }
+
+ T &last (void)
+ { return vec_->last(); }
+
+ bool space (int nelems) const
+ { return vec_ ? 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 *));
+ unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+
+ template<typename T1>
+ friend void va_stack::alloc(vec<T1, va_stack, vl_ptr>&, unsigned,
+ vec<T1, va_stack, vl_embed> *);
+
+ /* FIXME - This field should be private, but we need to cater to
+ compilers that have stricter notions of PODness for types. */
+ vec<T, A, vl_embed> *vec_;
+};
+
+
+/* Empty specialization for GC allocation. This will prevent GC
+ vectors from using the vl_ptr layout. FIXME: This is needed to
+ circumvent limitations in the GTY machinery. */
+
+template<typename T>
+struct vec<T, va_gc, vl_ptr>
+{
+};
-/* Truncate to specific length
- void VEC_T_truncate (VEC(T) *v, unsigned len);
- Set the length as specified. The new length must be less than or
- equal to the current length. This is an O(1) operation. */
+/* 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. */
-#define VEC_truncate(T,V,I) \
- (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
+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);
+}
-/* Grow to a specific length.
- void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
- Grow the vector to a specific length. The LEN must be as
- long or longer than the current length. The new elements are
- uninitialized. */
+/* Conditionally allocate heap memory for VEC and its internal vector. */
-#define VEC_safe_grow(T,A,V,I) \
- (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+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);
+}
-/* Grow to a specific length.
- void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
- Grow the vector to a specific length. The LEN must be as
- long or longer than the current length. The new elements are
- initialized to zero. */
+/* Free the heap memory allocated by vector V and set it to NULL. */
-#define VEC_safe_grow_cleared(T,A,V,I) \
- (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+template<typename T>
+inline void
+vec_free (vec<T> *&v)
+{
+ if (v == NULL)
+ return;
-/* Replace element
- T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
- T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
- T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object
+ v->release ();
+ delete v;
+ v = NULL;
+}
- Replace the IXth element of V with a new value, VAL. For pointer
- vectors returns the original value. For object vectors returns a
- pointer to the new value. For object vectors the new value can be
- NULL, in which case no overwriting of the slot is actually
- performed. */
-#define VEC_replace(T,V,I,O) \
- (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+/* Allocate a new stack vector with space for exactly NELEMS objects.
+ If NELEMS is zero, NO vector is created.
-/* Insert object with no reallocation
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
+ For the stack allocator, no memory is really allocated. The vector
+ is initialized to be at address SPACE and contain NELEMS slots.
+ Memory allocation actually occurs in the expansion of VEC_alloc.
- Insert an element, VAL, at the IXth position of V. Return a pointer
- to the slot created. For vectors of object, the new value can be
- NULL, in which case no initialization of the inserted slot takes
- place. There must be sufficient space. */
+ Usage notes:
-#define VEC_quick_insert(T,V,I,O) \
- (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+ * This does not allocate an instance of vec<T, A>. It allocates the
+ actual vector of elements (i.e., vec<T, A, vl_embed>) inside a
+ vec<T, A> instance.
-/* Insert object with reallocation
- T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
- T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
- T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
+ * This allocator must always be a macro:
- Insert an element, VAL, at the IXth position of V. Return a pointer
- to the slot created. For vectors of object, the new value can be
- NULL, in which case no initialization of the inserted slot takes
- place. Reallocate V, if necessary. */
+ We support a vector which starts out with space on the stack and
+ switches to heap space when forced to reallocate. This works a
+ little differently. In the case of stack vectors, vec_alloc will
+ expand to a call to vec_alloc_1 that calls XALLOCAVAR to request
+ the initial allocation. This uses alloca to get the initial
+ space. Since alloca can not be usefully called in an inline
+ function, vec_alloc must always be a macro.
-#define VEC_safe_insert(T,A,V,I,O) \
- (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+ Important limitations of stack vectors:
-/* Remove element retaining order
- T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
- T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
- void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
+ - Only the initial allocation will be made using alloca, so pass
+ a reasonable estimate that doesn't use too much stack space;
+ don't pass zero.
- Remove an element from the IXth position of V. Ordering of
- remaining elements is preserved. For pointer vectors returns the
- removed object. This is an O(N) operation due to a memmove. */
+ - Don't return a stack-allocated vector from the function which
+ allocated it. */
-#define VEC_ordered_remove(T,V,I) \
- (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+#define vec_stack_alloc(T,V,N) \
+ do { \
+ typedef vec<T, va_stack, vl_embed> stackv; \
+ va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\
+ } while (0)
-/* Remove element destroying order
- T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
- T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
- void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
- Remove an element from the IXth position of V. Ordering of
- remaining elements is destroyed. For pointer vectors returns the
- removed object. This is an O(1) operation. */
+/* 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,
-#define VEC_unordered_remove(T,V,I) \
- (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+ for (ix = 0; v.iterate(ix, &ptr); ix++)
+ continue; */
-/* Remove a block of elements
- void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_ptr>::iterate (unsigned ix, T *ptr) const
+{
+ if (vec_)
+ return vec_->iterate (ix, ptr);
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
- Remove LEN elements starting at the IXth. Ordering is retained.
- This is an O(N) operation due to memmove. */
-#define VEC_block_remove(T,V,I,L) \
- (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
-
-/* Get the address of the array of elements
- T *VEC_T_address (VEC(T) v)
-
- If you need to directly manipulate the array (for instance, you
- want to feed it to qsort), use this accessor. */
-
-#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
-
-/* Conveniently sort the contents of the vector with qsort.
- void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */
-
-#define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V), \
- sizeof (T), CMP)
-
-/* Find the first index in the vector not less than the object.
- unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
- bool (*lessthan) (const T, const T)); // Integer
- unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
- bool (*lessthan) (const T, const T)); // Pointer
- unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
- bool (*lessthan) (const T*, const T*)); // Object
-
- Find the first position in which VAL could be inserted without
- changing the ordering of V. LESSTHAN is a function that returns
- true if the first argument is strictly less than the second. */
-
-#define VEC_lower_bound(T,V,O,LT) \
- (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
-
-/* Reallocate an array of elements with prefix. */
-extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void ggc_free (void *);
-#define vec_gc_free(V) ggc_free (V)
-extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void dump_vec_loc_statistics (void);
-#ifdef GATHER_STATISTICS
-void vec_heap_free (void *);
-#else
-/* Avoid problems with frontends that #define free(x). */
-#define vec_heap_free(V) (free) (V)
-#endif
+/* 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,
-#if ENABLE_CHECKING
-#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
-#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
-#define VEC_CHECK_PASS ,file_,line_,function_
+ for (ix = 0; v->iterate(ix, &ptr); ix++)
+ continue;
-#define VEC_ASSERT(EXPR,OP,T,A) \
- (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
+ This variant is for vectors of objects. */
-extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
- ATTRIBUTE_NORETURN;
-#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
-#else
-#define VEC_CHECK_INFO
-#define VEC_CHECK_DECL
-#define VEC_CHECK_PASS
-#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
-#endif
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_ptr>::iterate (unsigned ix, T **ptr) const
+{
+ if (vec_)
+ return vec_->iterate (ix, ptr);
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
-/* Note: gengtype has hardwired knowledge of the expansions of the
- VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the
- expansions of these macros you may need to change gengtype too. */
-
-typedef struct GTY(()) vec_prefix
-{
- unsigned num;
- unsigned alloc;
-} vec_prefix;
-
-#define VEC(T,A) VEC_##T##_##A
-#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
-
-/* Base of vector type, not user visible. */
-#define VEC_T(T,B) \
-typedef struct VEC(T,B) \
-{ \
- struct vec_prefix prefix; \
- T vec[1]; \
-} VEC(T,B)
-
-#define VEC_T_GTY(T,B) \
-typedef struct GTY(()) VEC(T,B) \
-{ \
- struct vec_prefix prefix; \
- T GTY ((length ("%h.prefix.num"))) vec[1]; \
-} VEC(T,B)
-
-/* Derived vector type, user visible. */
-#define VEC_TA_GTY(T,B,A,GTY) \
-typedef struct GTY VEC(T,A) \
-{ \
- VEC(T,B) base; \
-} VEC(T,A)
-
-#define VEC_TA(T,B,A) \
-typedef struct VEC(T,A) \
-{ \
- VEC(T,B) base; \
-} VEC(T,A)
-
-/* Convert to base type. */
-#if GCC_VERSION >= 4000
-#define VEC_BASE(P) \
- ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0)
-#else
-#define VEC_BASE(P) ((P) ? &(P)->base : 0)
-#endif
-/* Vector of integer-like object. */
-#define DEF_VEC_I(T) \
-static inline void VEC_OP (T,must_be,integral_type) (void) \
-{ \
- (void)~(T)0; \
-} \
- \
-VEC_T(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_P(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_I(T,A) \
-DEF_VEC_NONALLOC_FUNCS_I(T,A) \
-struct vec_swallow_trailing_semi
-
-/* Vector of pointer to object. */
-#define DEF_VEC_P(T) \
-static inline void VEC_OP (T,must_be,pointer_type) (void) \
-{ \
- (void)((T)1 == (void *)1); \
-} \
- \
-VEC_T_GTY(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_P(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_P(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_P(T,A) \
-DEF_VEC_NONALLOC_FUNCS_P(T,A) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_P(T) \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->prefix.num : 0; \
-} \
- \
-static inline T VEC_OP (T,base,last) \
- (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
- \
- return vec_->vec[vec_->prefix.num - 1]; \
-} \
- \
-static inline T VEC_OP (T,base,index) \
- (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
- \
- return vec_->vec[ix_]; \
-} \
- \
-static inline int VEC_OP (T,base,iterate) \
- (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
-{ \
- if (vec_ && ix_ < vec_->prefix.num) \
- { \
- *ptr = vec_->vec[ix_]; \
- return 1; \
- } \
- else \
- { \
- *ptr = (T) 0; \
- return 0; \
- } \
-} \
- \
-static inline size_t VEC_OP (T,base,embedded_size) \
- (int alloc_) \
-{ \
- return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
-} \
- \
-static inline void VEC_OP (T,base,embedded_init) \
- (VEC(T,base) *vec_, int alloc_) \
-{ \
- vec_->prefix.num = 0; \
- vec_->prefix.alloc = alloc_; \
-} \
- \
-static inline int VEC_OP (T,base,space) \
- (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (alloc_ >= 0, "space", T, base); \
- return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
-} \
- \
-static inline void VEC_OP(T,base,splice) \
- (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
-{ \
- if (src_) \
- { \
- unsigned len_ = src_->prefix.num; \
- VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
- \
- memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
- dst_->prefix.num += len_; \
- } \
-} \
- \
-static inline T *VEC_OP (T,base,quick_push) \
- (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
- slot_ = &vec_->vec[vec_->prefix.num++]; \
- *slot_ = obj_; \
- \
- return slot_; \
-} \
- \
-static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- T obj_; \
- \
- VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
- obj_ = vec_->vec[--vec_->prefix.num]; \
- \
- return obj_; \
-} \
- \
-static inline void VEC_OP (T,base,truncate) \
- (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
- if (vec_) \
- vec_->prefix.num = size_; \
-} \
- \
-static inline T VEC_OP (T,base,replace) \
- (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
-{ \
- T old_obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
- old_obj_ = vec_->vec[ix_]; \
- vec_->vec[ix_] = obj_; \
- \
- return old_obj_; \
-} \
- \
-static inline T *VEC_OP (T,base,quick_insert) \
- (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
- VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
- *slot_ = obj_; \
- \
- return slot_; \
-} \
- \
-static inline T VEC_OP (T,base,ordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- T obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- obj_ = *slot_; \
- memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
- \
- return obj_; \
-} \
- \
-static inline T VEC_OP (T,base,unordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- T obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- obj_ = *slot_; \
- *slot_ = vec_->vec[--vec_->prefix.num]; \
- \
- return obj_; \
-} \
- \
-static inline void VEC_OP (T,base,block_remove) \
- (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- vec_->prefix.num -= len_; \
- memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline T *VEC_OP (T,base,address) \
- (VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->vec : 0; \
-} \
- \
-static inline unsigned VEC_OP (T,base,lower_bound) \
- (VEC(T,base) *vec_, const T obj_, \
- bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
-{ \
- unsigned int len_ = VEC_OP (T,base, length) (vec_); \
- unsigned int half_, middle_; \
- unsigned int first_ = 0; \
- while (len_ > 0) \
- { \
- T middle_elem_; \
- half_ = len_ >> 1; \
- middle_ = first_; \
- middle_ += half_; \
- middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
- if (lessthan_ (middle_elem_, obj_)) \
- { \
- first_ = middle_; \
- ++first_; \
- len_ = len_ - half_ - 1; \
- } \
- else \
- len_ = half_; \
- } \
- return first_; \
-}
-
-#define DEF_VEC_ALLOC_FUNC_P(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
- PASS_MEM_STAT); \
-}
-
-
-#define DEF_VEC_NONALLOC_FUNCS_P(T,A) \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
- (NULL, len_ PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
-}
-
-/* Vector of object. */
-#define DEF_VEC_O(T) \
-VEC_T_GTY(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_O(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_O(T,A) \
-DEF_VEC_NONALLOC_FUNCS_O(T,A) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_O(T) \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->prefix.num : 0; \
-} \
- \
-static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
- \
- return &vec_->vec[vec_->prefix.num - 1]; \
-} \
- \
-static inline T *VEC_OP (T,base,index) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
- \
- return &vec_->vec[ix_]; \
-} \
- \
-static inline int VEC_OP (T,base,iterate) \
- (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
-{ \
- if (vec_ && ix_ < vec_->prefix.num) \
- { \
- *ptr = &vec_->vec[ix_]; \
- return 1; \
- } \
- else \
- { \
- *ptr = 0; \
- return 0; \
- } \
-} \
- \
-static inline size_t VEC_OP (T,base,embedded_size) \
- (int alloc_) \
-{ \
- return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
-} \
- \
-static inline void VEC_OP (T,base,embedded_init) \
- (VEC(T,base) *vec_, int alloc_) \
-{ \
- vec_->prefix.num = 0; \
- vec_->prefix.alloc = alloc_; \
-} \
- \
-static inline int VEC_OP (T,base,space) \
- (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (alloc_ >= 0, "space", T, base); \
- return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \
-} \
- \
-static inline void VEC_OP(T,base,splice) \
- (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
-{ \
- if (src_) \
- { \
- unsigned len_ = src_->prefix.num; \
- VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \
- \
- memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \
- dst_->prefix.num += len_; \
- } \
-} \
- \
-static inline T *VEC_OP (T,base,quick_push) \
- (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
- slot_ = &vec_->vec[vec_->prefix.num++]; \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
- --vec_->prefix.num; \
-} \
- \
-static inline void VEC_OP (T,base,truncate) \
- (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \
- if (vec_) \
- vec_->prefix.num = size_; \
-} \
- \
-static inline T *VEC_OP (T,base,replace) \
- (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
- slot_ = &vec_->vec[ix_]; \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline T *VEC_OP (T,base,quick_insert) \
- (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
- VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline void VEC_OP (T,base,ordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline void VEC_OP (T,base,unordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \
-} \
- \
-static inline void VEC_OP (T,base,block_remove) \
- (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- vec_->prefix.num -= len_; \
- memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline T *VEC_OP (T,base,address) \
- (VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->vec : 0; \
-} \
- \
-static inline unsigned VEC_OP (T,base,lower_bound) \
- (VEC(T,base) *vec_, const T *obj_, \
- bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
-{ \
- unsigned int len_ = VEC_OP (T, base, length) (vec_); \
- unsigned int half_, middle_; \
- unsigned int first_ = 0; \
- while (len_ > 0) \
- { \
- T *middle_elem_; \
- half_ = len_ >> 1; \
- middle_ = first_; \
- middle_ += half_; \
- middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
- if (lessthan_ (middle_elem_, obj_)) \
- { \
- first_ = middle_; \
- ++first_; \
- len_ = len_ - half_ - 1; \
- } \
- else \
- len_ = half_; \
- } \
- return first_; \
-}
-
-#define DEF_VEC_ALLOC_FUNC_O(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
- offsetof (VEC(T,A),base.vec), \
- sizeof (T) \
- PASS_MEM_STAT); \
-}
-
-#define DEF_VEC_NONALLOC_FUNCS_O(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
- (NULL, len_, \
- offsetof (VEC(T,A),base.vec), sizeof (T) \
- PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec),\
- sizeof (T) \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
- VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
-}
-
-#define DEF_VEC_ALLOC_FUNC_I(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
-}
-
-#define DEF_VEC_NONALLOC_FUNCS_I(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
- (NULL, len_, \
- offsetof (VEC(T,A),base.vec), sizeof (T) \
- PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec),\
- sizeof (T) \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
- VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
-}
-
-/* We support a vector which starts out with space on the stack and
- switches to heap space when forced to reallocate. This works a
- little differently. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
- DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial
- space; because alloca can not be usefully called in an inline
- function, and because a macro can not define a macro, you must then
- write a #define for each type:
-
- #define VEC_{TYPE}_stack_alloc(alloc) \
- VEC_stack_alloc({TYPE}, alloc)
-
- This is really a hack and perhaps can be made better. Note that
- this macro will wind up evaluating the ALLOC parameter twice.
-
- Only the initial allocation will be made using alloca, so pass a
- reasonable estimate that doesn't use too much stack space; don't
- pass zero. Don't return a VEC(TYPE,stack) vector from the function
- which allocated it. */
-
-extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact_1 (int, void *);
-extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void vec_stack_free (void *);
-
-#ifdef GATHER_STATISTICS
-#define VEC_stack_alloc(T,alloc,name,line,function) \
- (VEC_OP (T,stack,alloc1) \
- (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#else
-#define VEC_stack_alloc(T,alloc) \
- (VEC_OP (T,stack,alloc1) \
- (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#endif
+/* 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)--)
+
-#define DEF_VEC_ALLOC_P_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_P_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_P(T,stack) \
-struct vec_swallow_trailing_semi
+/* Return a copy of this vector. */
-#define DEF_VEC_ALLOC_FUNC_P_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
+template<typename T, typename A>
+inline vec<T, A, vl_ptr>
+vec<T, A, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
+{
+ vec<T, A, vl_ptr> new_vec = vNULL;
+ if (length ())
+ new_vec.vec_ = vec_->copy ();
+ return new_vec;
}
-#define DEF_VEC_ALLOC_O_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_O_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_O(T,stack) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_FUNC_O_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
+/* 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, typename A>
+inline bool
+vec<T, A, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
+{
+ bool extend = nelems ? !space (nelems) : false;
+ if (extend)
+ A::reserve (vec_, nelems, exact PASS_MEM_STAT);
+ return extend;
}
-#define DEF_VEC_ALLOC_I_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_I_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_I(T,stack) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_FUNC_I_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
+/* 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, typename A>
+inline bool
+vec<T, A, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
+{
+ return reserve (nelems, true PASS_MEM_STAT);
}
-#endif /* GCC_VEC_H */
+
+/* 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, typename A>
+inline void
+vec<T, A, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
+{
+ vec_ = NULL;
+ if (nelems > 0)
+ reserve_exact (nelems PASS_MEM_STAT);
+}
+
+
+/* Free the memory occupied by the embedded vector. */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::release (void)
+{
+ if (vec_)
+ A::release (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, typename A>
+inline void
+vec<T, A, vl_ptr>::splice (vec<T, A, vl_ptr> &src)
+{
+ if (src.vec_)
+ vec_->splice (*(src.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, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_splice (vec<T, A, 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, typename A>
+inline T *
+vec<T, A, vl_ptr>::quick_push (const T &obj)
+{
+ return 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, typename A>
+inline T *
+vec<T, A, 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, typename A>
+inline T &
+vec<T, A, vl_ptr>::pop (void)
+{
+ return 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, typename A>
+inline void
+vec<T, A, vl_ptr>::truncate (unsigned size)
+{
+ if (vec_)
+ 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, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
+{
+ unsigned oldlen = length ();
+ gcc_checking_assert (oldlen <= len);
+ reserve_exact (len - oldlen PASS_MEM_STAT);
+ 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, typename A>
+inline void
+vec<T, A, 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, typename A>
+inline void
+vec<T, A, vl_ptr>::quick_grow (unsigned len)
+{
+ gcc_checking_assert (vec_);
+ 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, typename A>
+inline void
+vec<T, A, vl_ptr>::quick_grow_cleared (unsigned len)
+{
+ gcc_checking_assert (vec_);
+ vec_->quick_grow_cleared (len);
+}
+
+
+/* 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_ptr>::quick_insert (unsigned ix, const T &obj)
+{
+ 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, typename A>
+inline void
+vec<T, A, 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, typename A>
+inline void
+vec<T, A, vl_ptr>::ordered_remove (unsigned ix)
+{
+ 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, typename A>
+inline void
+vec<T, A, vl_ptr>::unordered_remove (unsigned ix)
+{
+ 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, typename A>
+inline void
+vec<T, A, vl_ptr>::block_remove (unsigned ix, unsigned len)
+{
+ 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, typename A>
+inline void
+vec<T, A, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
+{
+ if (vec_)
+ vec_->qsort (cmp);
+}
+
+
+/* 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>
+inline unsigned
+vec<T, A, vl_ptr>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
+ const
+{
+ return vec_ ? vec_->lower_bound (obj, lessthan) : 0;
+}
+
+#if (GCC_VERSION >= 3000)
+# pragma GCC poison vec_ vecpfx_ vecdata_
+#endif
+
+#endif // GCC_VEC_H
projects / platform / upstream / gcc48.git / blobdiff