/* Vector API for GNU compiler.
- Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2017 Free Software Foundation, Inc.
Contributed by Nathan Sidwell <nathan@codesourcery.com>
Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
#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.
+/* Some gen* file have no ggc support as the header file gtype-desc.h is
+ missing. Provide these definitions in case ggc.h has not been included.
+ This is not a problem because any code that runs before gengtype is built
+ will never need to use GC vectors.*/
+
+extern void ggc_free (void *);
+extern size_t ggc_round_alloc_size (size_t requested_size);
+extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
+
+/* 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.
+
+ - 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,A,P,I}(TYPEDEF) macro, to
- get the non-memory allocation version, and then a
- DEF_VEC_ALLOC_{O,A,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, A, P and I
- indicate whether TYPEDEF is a pointer (P), object (O), atomic object
- (A) 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 or
- a even a crash if you pick the atomic object version when the object
- version should have been chosen instead. 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).
+
+
+ * 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).
- 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.
+ 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 }
-
*/
-#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_
-
-#define VEC_ASSERT(EXPR,OP,T,A) \
- (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
-
-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
+/* Support function for statistics. */
+extern void dump_vec_loc_statistics (void);
-#define VEC(T,A) vec_t<T>
+/* Hashtable mapping vec addresses to descriptors. */
+extern htab_t vec_mem_usage_hash;
-enum vec_allocation_t { heap, gc, stack };
+/* Control data for vectors. This contains the number of allocated
+ and used slots inside a vector. */
struct vec_prefix
{
- unsigned num;
- unsigned alloc;
+ /* 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 (void *, size_t, size_t CXX_MEM_STAT_INFO);
+ void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO);
+ 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;
};
-/* Vector type, user visible. */
-template<typename T>
-struct GTY(()) vec_t
+/* 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)
{
- vec_prefix prefix;
- T vec[1];
+ 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> *&);
};
-/* Garbage collection support for vec_t. */
+
+/* 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 RESERVE is 0, no vector will be created. */
template<typename T>
-void
-gt_ggc_mx (vec_t<T> *v)
+inline void
+va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
+ MEM_STAT_DECL)
{
- extern void gt_ggc_mx (T&);
- for (unsigned i = 0; i < v->prefix.num; i++)
- gt_ggc_mx (v->vec[i]);
+ 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 (v, v->allocated (), false);
+
+ 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 (v, alloc, nelem PASS_MEM_STAT);
}
-/* PCH support for vec_t. */
+/* Free the heap space allocated for vector V. */
template<typename T>
void
-gt_pch_nx (vec_t<T> *v)
+va_heap::release (vec<T, va_heap, vl_embed> *&v)
{
- extern void gt_pch_nx (T&);
- for (unsigned i = 0; i < v->prefix.num; i++)
- gt_pch_nx (v->vec[i]);
+ if (v == NULL)
+ return;
+
+ if (GATHER_STATISTICS)
+ v->m_vecpfx.release_overhead (v, v->allocated (), true);
+ ::free (v);
+ v = NULL;
}
-template<typename T>
-void
-gt_pch_nx (vec_t<T *> *v, gt_pointer_operator op, void *cookie)
+
+/* 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)
{
- for (unsigned i = 0; i < v->prefix.num; i++)
- op (&(v->vec[i]), cookie);
+ if (v)
+ ::ggc_free (v);
+ v = NULL;
}
-template<typename T>
+
+/* 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 RESERVE is 0, no vector will be created. */
+
+template<typename T, typename A>
void
-gt_pch_nx (vec_t<T> *v, gt_pointer_operator op, void *cookie)
+va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
+ MEM_STAT_DECL)
{
- extern void gt_pch_nx (T *, gt_pointer_operator, void *);
- for (unsigned i = 0; i < v->prefix.num; i++)
- gt_pch_nx (&(v->vec[i]), op, cookie);
-}
-
-
-/* FIXME cxx-conversion. Remove these definitions and update all
- calling sites. */
-/* Vector of integer-like object. */
-#define DEF_VEC_I(T) struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I(T,A) struct vec_swallow_trailing_semi
-
-/* Vector of pointer to object. */
-#define DEF_VEC_P(T) struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_P(T,A) struct vec_swallow_trailing_semi
-
-/* Vector of object. */
-#define DEF_VEC_O(T) struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O(T,A) struct vec_swallow_trailing_semi
-
-/* Vectors on the stack. */
-#define DEF_VEC_ALLOC_P_STACK(T) struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O_STACK(T) struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I_STACK(T) struct vec_swallow_trailing_semi
-
-/* Vectors of atomic types. Atomic types do not need to have its
- elements marked for GC and PCH. To avoid unnecessary traversals,
- we provide template instantiations for the GC/PCH functions that
- do not traverse the vector.
-
- FIXME cxx-conversion - Once vec_t users are converted this can
- be provided in some other way (e.g., adding an additional template
- parameter to the vec_t class). */
-#define DEF_VEC_A(TYPE) \
-template<typename T> \
-void \
-gt_ggc_mx (vec_t<TYPE> *v ATTRIBUTE_UNUSED) \
-{ \
-} \
- \
-template<typename T> \
-void \
-gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED) \
-{ \
-} \
- \
-template<typename T> \
-void \
-gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED, \
- gt_pointer_operator op ATTRIBUTE_UNUSED, \
- void *cookie ATTRIBUTE_UNUSED) \
-{ \
-} \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_A(T,A) struct vec_swallow_trailing_semi
-
-/* Support functions for stack vectors. */
-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 *);
-
-/* Reallocate an array of elements with prefix. */
-template<typename T, enum vec_allocation_t A>
-extern vec_t<T> *vec_reserve (vec_t<T> *, int MEM_STAT_DECL);
-
-template<typename T, enum vec_allocation_t A>
-extern vec_t<T> *vec_reserve_exact (vec_t<T> *, int MEM_STAT_DECL);
+ unsigned alloc
+ = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
+ if (!alloc)
+ {
+ ::ggc_free (v);
+ v = NULL;
+ return;
+ }
-extern void dump_vec_loc_statistics (void);
-extern void ggc_free (void *);
-extern void vec_heap_free (void *);
+ /* 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);
-/* 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. */
+ /* 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;
-/* Length of vector
- unsigned VEC_T_length(const VEC(T) *v);
+ /* And finally, recalculate the amount of space we ask for. */
+ size = vec_offset + alloc * elt_size;
- Return the number of active elements in V. V can be NULL, in which
- case zero is returned. */
+ unsigned nelem = v ? v->length () : 0;
+ v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
+ PASS_MEM_STAT));
+ v->embedded_init (alloc, nelem);
+}
-#define VEC_length(T,V) (VEC_length_1<T> (V))
-template<typename T>
-static inline unsigned
-VEC_length_1 (const vec_t<T> *vec_)
+/* 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
{
- return vec_ ? vec_->prefix.num : 0;
-}
+};
-/* Check if vector is empty
- int VEC_T_empty(const VEC(T) *v);
+/* Generic vector template. Default values for A and L indicate the
+ most commonly used strategies.
- Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
+ 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.
-#define VEC_empty(T,V) (VEC_empty_1<T> (V))
+ 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
+{
+};
-template<typename T>
-static inline bool
-VEC_empty_1 (const vec_t<T> *vec_)
+/* Default-construct N elements in DST. */
+
+template <typename T>
+inline void
+vec_default_construct (T *dst, unsigned n)
+{
+ for ( ; n; ++dst, --n)
+ ::new (static_cast<void*>(dst)) T ();
+}
+
+/* Copy-construct N elements in DST from *SRC. */
+
+template <typename T>
+inline void
+vec_copy_construct (T *dst, const T *src, unsigned n)
{
- return VEC_length (T, vec_) == 0;
+ for ( ; n; ++dst, ++src, --n)
+ ::new (static_cast<void*>(dst)) T (*src);
}
+/* 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. This isn't
+ needed for file-scope and function-local static vectors, which
+ are zero-initialized by default. */
+struct vnull
+{
+ template <typename T, typename A, typename L>
+ CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); }
+};
+extern vnull vNULL;
-/* 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. */
+/* 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.
-#define VEC_address(T,V) (VEC_address_1<T> (V))
+ 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.
-template<typename T>
-static inline T *
-VEC_address_1 (vec_t<T> *vec_)
+ 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>
{
- return vec_ ? vec_->vec : 0;
+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; }
+ T *begin () { return address (); }
+ const T *begin () const { return address (); }
+ T *end () { return address () + length (); }
+ const T *end () const { return address () + length (); }
+ 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 (const vec &);
+ void splice (const 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;
+ bool contains (const T &search) 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;
}
-/* 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
+/* 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 final element. V must not be empty. */
+/* 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;
+}
-#define VEC_last(T,V) (VEC_last_1<T> (V VEC_CHECK_INFO))
-template<typename T>
-static inline T&
-VEC_last_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+/* 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)
{
- VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base);
- return vec_->vec[vec_->prefix.num - 1];
+ 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;
+}
-/* 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
+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);
+}
- Return the IX'th element. IX must be in the domain of V. */
-#define VEC_index(T,V,I) (VEC_index_1<T> (V, I VEC_CHECK_INFO))
+/* Allocate GC memory for V with space for NELEMS slots. If NELEMS
+ is 0, V is initialized to NULL. */
-template<typename T>
-static inline T&
-VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
{
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
- return vec_->vec[ix_];
+ v = NULL;
+ vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
}
-template<typename T>
-static inline const T&
-VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+
+/* 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)
{
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
- return vec_->vec[ix_];
+ A::release (v);
}
-/* 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
+/* 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);
+}
- 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,
- for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
- continue; */
+/* 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);
+ vec_default_construct (v->address () + oldlen, len - oldlen);
+}
-#define VEC_iterate(T,V,I,P) (VEC_iterate_1<T> (V, I, &(P)))
-template<typename T>
-static inline bool
-VEC_iterate_1 (const vec_t<T> *vec_, unsigned ix_, T *ptr)
+/* 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 (vec_ && ix_ < vec_->prefix.num)
- {
- *ptr = vec_->vec[ix_];
- return true;
- }
+ if (v)
+ return v->iterate (ix, ptr);
else
{
*ptr = 0;
}
}
-template<typename T>
-static inline bool
-VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr)
+template<typename T, typename A>
+inline bool
+vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
{
- if (vec_ && ix_ < vec_->prefix.num)
- {
- *ptr = &vec_->vec[ix_];
- return true;
- }
+ if (v)
+ return v->iterate (ix, ptr);
else
{
*ptr = 0;
}
}
-/* Convenience macro for forward iteration. */
-
-#define FOR_EACH_VEC_ELT(T, V, I, P) \
- for (I = 0; VEC_iterate (T, (V), (I), (P)); ++(I))
-/* Likewise, but start from FROM rather than 0. */
+/* 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);
+}
-#define FOR_EACH_VEC_ELT_FROM(T, V, I, P, FROM) \
- for (I = (FROM); VEC_iterate (T, (V), (I), (P)); ++(I))
-/* Convenience macro for reverse iteration. */
+/* 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);
+}
-#define FOR_EACH_VEC_ELT_REVERSE(T,V,I,P) \
- for (I = VEC_length (T, (V)) - 1; \
- VEC_iterate (T, (V), (I), (P)); \
- (I)--)
+/* 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);
+}
-/* 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);
+/* 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;
+}
- These allow the caller to perform the memory allocation. */
+/* 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, const 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);
+ }
+}
-#define VEC_embedded_size(T,N) (VEC_embedded_size_1<T> (N))
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
-template<typename T>
-static inline size_t
-VEC_embedded_size_1 (int alloc_)
+template<typename T, typename A>
+inline bool
+vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
{
- return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T);
+ return v ? v->contains (search) : false;
}
-#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N))
+/* Index into vector. Return the IX'th element. IX must be in the
+ domain of the vector. */
-template<typename T>
-static inline void
-VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_)
+template<typename T, typename A>
+inline const T &
+vec<T, A, vl_embed>::operator[] (unsigned ix) const
{
- vec_->prefix.num = 0;
- vec_->prefix.alloc = alloc_;
+ 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];
+}
-/* Allocate new vector.
- VEC(T,A) *VEC_T_A_alloc(int reserve);
- Allocate a new vector with space for RESERVE objects. If RESERVE
- is zero, NO vector is created.
+/* Get the final element of the vector, which must not be empty. */
- 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.
+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];
+}
- 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. */
-#define VEC_alloc(T,A,N) \
- ((A == stack) \
- ? VEC_alloc_1 (N, \
- XALLOCAVAR (vec_t<T>, \
- VEC_embedded_size_1<T> (N))) \
- : VEC_alloc_1<T, A> (N MEM_STAT_INFO))
+/* 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, enum vec_allocation_t A>
-static inline vec_t<T> *
-VEC_alloc_1 (int alloc_ MEM_STAT_DECL)
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::space (unsigned nelems) const
{
- return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT);
+ return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
}
-template<typename T>
-static inline vec_t<T> *
-VEC_alloc_1 (int alloc_, vec_t<T> *space)
+
+/* 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
{
- return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space);
+ if (ix < m_vecpfx.m_num)
+ {
+ *ptr = m_vecdata[ix];
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
}
-/* Free a vector.
- void VEC_T_A_free(VEC(T,A) *&);
+/* 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,
- Free a vector and set it to NULL. */
+ for (ix = 0; v->iterate (ix, &ptr); ix++)
+ continue;
-#define VEC_free(T,A,V) (VEC_free_1<T, A> (&V))
+ This variant is for vectors of objects. */
-template<typename T, enum vec_allocation_t A>
-static inline void
-VEC_free_1 (vec_t<T> **vec_)
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
{
- if (*vec_)
+ if (ix < m_vecpfx.m_num)
{
- if (A == heap)
- vec_heap_free (*vec_);
- else if (A == gc)
- ggc_free (*vec_);
- else if (A == stack)
- vec_stack_free (*vec_);
+ *ptr = CONST_CAST (T *, &m_vecdata[ix]);
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
}
- *vec_ = NULL;
}
-/* Copy a vector.
- VEC(T,A) *VEC_T_A_copy(VEC(T) *);
+/* Return a pointer to a copy of this vector. */
- Copy the live elements of a vector into a new vector. The new and
- old vectors need not be allocated by the same mechanism. */
+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);
+ vec_copy_construct (new_vec->address (), m_vecdata, len);
+ }
+ return new_vec;
+}
-#define VEC_copy(T,A,V) (VEC_copy_1<T, A> (V MEM_STAT_INFO))
-template<typename T, enum vec_allocation_t A>
-static inline vec_t<T> *
-VEC_copy_1 (vec_t<T> *vec_ MEM_STAT_DECL)
-{
- size_t len_ = vec_ ? vec_->prefix.num : 0;
- vec_t<T> *new_vec_ = NULL;
+/* Copy the elements from SRC to the end of this vector as if by memcpy.
+ The vector must have sufficient headroom available. */
- if (len_)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
+{
+ unsigned len = src.length ();
+ if (len)
{
- new_vec_ = vec_reserve_exact<T, A> (NULL, len_ PASS_MEM_STAT);
- new_vec_->prefix.num = len_;
- memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_);
+ gcc_checking_assert (space (len));
+ vec_copy_construct (end (), src.address (), len);
+ m_vecpfx.m_num += len;
}
- return new_vec_;
}
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
+{
+ if (src)
+ splice (*src);
+}
-/* Determine if a vector has additional capacity.
- int VEC_T_space (VEC(T) *v,int reserve)
+/* 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. */
- 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 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;
+}
-#define VEC_space(T,V,R) (VEC_space_1<T> (V, R VEC_CHECK_INFO))
-template<typename T>
-static inline int
-VEC_space_1 (vec_t<T> *vec_, int alloc_ VEC_CHECK_DECL)
+/* 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)
{
- VEC_ASSERT (alloc_ >= 0, "space", T, base);
- return vec_
- ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_
- : !alloc_;
+ gcc_checking_assert (length () > 0);
+ return m_vecdata[--m_vecpfx.m_num];
}
-/* Reserve space.
- int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
+/* 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;
+}
- 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. */
-#define VEC_reserve(T,A,V,R) \
- (VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO))
+/* Insert an element, OBJ, at the IXth position of this vector. There
+ must be sufficient space. */
-template<typename T, enum vec_allocation_t A>
-static inline int
-VEC_reserve_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
{
- int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+ 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;
+}
- if (extend)
- *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT);
- return extend;
+/* 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));
}
-/* Reserve space exactly.
- int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
+/* Remove an element from the IXth position of this vector. Ordering of
+ remaining elements is destroyed. This is an O(1) operation. */
- 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, 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];
+}
-#define VEC_reserve_exact(T,A,V,R) \
- (VEC_reserve_exact_1<T, A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO))
-template<typename T, enum vec_allocation_t A>
-static inline int
-VEC_reserve_exact_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)
+/* 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)
{
- int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+ 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));
+}
- if (extend)
- *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT);
- return extend;
+/* 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);
}
-/* 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
+/* Search the contents of the sorted vector with a binary search.
+ CMP is the comparison function to pass to bsearch. */
- 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. */
+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);
+ }
-#define VEC_splice(T,DST,SRC) (VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO))
+ return NULL;
+}
-template<typename T>
-static inline void
-VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *src_ VEC_CHECK_DECL)
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::contains (const T &search) const
{
- if (src_)
- {
- unsigned len_ = src_->prefix.num;
- VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice",
- T, base);
+ unsigned int len = length ();
+ for (unsigned int i = 0; i < len; i++)
+ if ((*this)[i] == search)
+ return true;
+
+ return false;
+}
+
+/* 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. */
- memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));
- dst_->prefix.num += len_;
+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;
}
-/* 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
+/* Return the number of bytes needed to embed an instance of an
+ embeddable vec inside another data structure.
- 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. */
+ 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):
-#define VEC_safe_splice(T,A,DST,SRC) \
- (VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO))
+ size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
+ void v->embedded_init (unsigned alloc, unsigned num);
-template<typename T, enum vec_allocation_t A>
-static inline void
-VEC_safe_splice_1 (vec_t<T> **dst_, vec_t<T> *src_ VEC_CHECK_DECL MEM_STAT_DECL)
+ 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)
{
- if (src_)
- {
- VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num
- VEC_CHECK_PASS MEM_STAT_INFO);
+ typedef vec<T, A, vl_embed> vec_embedded;
+ return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
+}
- VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS);
- }
+
+/* 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;
}
-
-/* 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. */
+/* 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. */
-#define VEC_quick_push(T,V,O) (VEC_quick_push_1<T> (V, O VEC_CHECK_INFO))
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
+{
+ unsigned oldlen = length ();
+ size_t growby = len - oldlen;
+ quick_grow (len);
+ if (growby != 0)
+ vec_default_construct (address () + oldlen, growby);
+}
+
+/* Garbage collection support for vec<T, A, vl_embed>. */
template<typename T>
-static inline T &
-VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL)
+void
+gt_ggc_mx (vec<T, va_gc> *v)
{
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
- vec_->vec[vec_->prefix.num] = obj_;
- T &val_ = vec_->vec[vec_->prefix.num];
- vec_->prefix.num++;
- return val_;
+ extern void gt_ggc_mx (T &);
+ for (unsigned i = 0; i < v->length (); i++)
+ gt_ggc_mx ((*v)[i]);
}
template<typename T>
-static inline T *
-VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL)
+void
+gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
{
- T *slot_;
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
- slot_ = &vec_->vec[vec_->prefix.num++];
- if (ptr_)
- *slot_ = *ptr_;
- return slot_;
+ /* Nothing to do. Vectors of atomic types wrt GC do not need to
+ be traversed. */
}
-/* 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
+/* 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:
- 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. */
+ 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; }
+
+ T *begin () { return address (); }
+ const T *begin () const { return address (); }
+ T *end () { return begin () + length (); }
+ const T *end () const { return begin () + length (); }
+ 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 (const vec &);
+ void safe_splice (const 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 contains (const T &search) 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;
+};
-#define VEC_safe_push(T,A,V,O) \
- (VEC_safe_push_1<T, A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO))
-template<typename T, enum vec_allocation_t A>
-static inline T &
-VEC_safe_push_1 (vec_t<T> **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)
+/* 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>
{
- VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
- return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS);
+public:
+ auto_vec ()
+ {
+ m_auto.embedded_init (MAX (N, 2), 0, 1);
+ this->m_vec = &m_auto;
+ }
+
+ auto_vec (size_t s)
+ {
+ if (s > N)
+ {
+ this->create (s);
+ return;
+ }
+
+ 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);
}
-template<typename T, enum vec_allocation_t A>
-static inline T *
-VEC_safe_push_1 (vec_t<T> **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL)
+
+/* 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)
{
- VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
- return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS);
+ if (!vec)
+ vec_alloc (vec, nelems PASS_MEM_STAT);
}
-/* 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
+/* 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;
+}
+
- Pop the last element off the end. Returns the element popped, for
- pointer vectors. */
+/* 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_pop(T,V) (VEC_pop_1<T> (V VEC_CHECK_INFO))
+ for (ix = 0; v.iterate (ix, &ptr); ix++)
+ continue; */
template<typename T>
-static inline T&
-VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+inline bool
+vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
{
- VEC_ASSERT (vec_->prefix.num, "pop", T, base);
- return vec_->vec[--vec_->prefix.num];
+ if (m_vec)
+ return m_vec->iterate (ix, ptr);
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
}
-/* Truncate to specific length
- void VEC_T_truncate (VEC(T) *v, unsigned len);
+/* 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,
- Set the length as specified. The new length must be less than or
- equal to the current length. This is an O(1) operation. */
+ for (ix = 0; v->iterate (ix, &ptr); ix++)
+ continue;
-#define VEC_truncate(T,V,I) \
- (VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO))
+ This variant is for vectors of objects. */
template<typename T>
-static inline void
-VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL)
+inline bool
+vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
{
- VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);
- if (vec_)
- vec_->prefix.num = size_;
+ if (m_vec)
+ return m_vec->iterate (ix, ptr);
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
}
-/* Grow to a specific length.
- void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
+/* Convenience macro for forward iteration. */
+#define FOR_EACH_VEC_ELT(V, I, P) \
+ for (I = 0; (V).iterate ((I), &(P)); ++(I))
- Grow the vector to a specific length. The LEN must be as
- long or longer than the current length. The new elements are
- uninitialized. */
+#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \
+ for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
-#define VEC_safe_grow(T,A,V,I) \
- (VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO))
+/* 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))
-template<typename T, enum vec_allocation_t A>
-static inline void
-VEC_safe_grow_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)
+/* 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_ASSERT (size_ >= 0 && VEC_length (T, *vec_) <= (unsigned)size_,
- "grow", T, A);
- VEC_reserve_exact_1<T, A> (vec_,
- size_ - (int)(*vec_ ? (*vec_)->prefix.num : 0)
- VEC_CHECK_PASS PASS_MEM_STAT);
- (*vec_)->prefix.num = size_;
+ vec<T, va_heap, vl_ptr> new_vec = vNULL;
+ if (length ())
+ new_vec.m_vec = m_vec->copy ();
+ return new_vec;
}
-/* Grow to a specific length.
- void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
+/* Ensure that the vector has at least RESERVE slots available (if
+ EXACT is false), or exactly RESERVE slots available (if EXACT is
+ true).
- 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. */
+ This may create additional headroom if EXACT is false.
-#define VEC_safe_grow_cleared(T,A,V,I) \
- (VEC_safe_grow_cleared_1<T,A> (&(V), (int)(I) \
- VEC_CHECK_INFO MEM_STAT_INFO))
+ Note that this can cause the embedded vector to be reallocated.
+ Returns true iff reallocation actually occurred. */
-template<typename T, enum vec_allocation_t A>
-static inline void
-VEC_safe_grow_cleared_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL
- MEM_STAT_DECL)
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
{
- int oldsize = VEC_length (T, *vec_);
- VEC_safe_grow_1<T, A> (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);
- memset (&(VEC_address (T, *vec_)[oldsize]), 0,
- sizeof (T) * (size_ - oldsize));
+ 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)
+ {
+ vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
+ m_vec->m_vecpfx.m_num = oldsize;
+ }
+
+ return true;
}
-/* 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
+/* 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);
+}
- 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_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO))
+/* 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>
-static inline T&
-VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+inline void
+vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
{
- VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base);
- vec_->vec[ix_] = obj_;
- return vec_->vec[ix_];
+ m_vec = NULL;
+ if (nelems > 0)
+ reserve_exact (nelems PASS_MEM_STAT);
}
-/* Insert object with no reallocation
- void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
- void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
- void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
+/* Free the memory occupied by the embedded vector. */
- Insert an element, VAL, at the IXth position of V. 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. */
+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;
+ }
-#define VEC_quick_insert(T,V,I,O) \
- (VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO))
+ 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>
-static inline void
-VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+inline void
+vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
{
- T *slot_;
+ if (src.m_vec)
+ m_vec->splice (*(src.m_vec));
+}
+
- 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_;
+/* 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 (const 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>
-static inline void
-VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_ VEC_CHECK_DECL)
+inline T *
+vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
{
- T *slot_;
+ return m_vec->quick_push (obj);
+}
+
- 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 (ptr_)
- *slot_ = *ptr_;
+/* 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);
}
-/* 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
+/* 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 ();
+}
- 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. */
-#define VEC_safe_insert(T,A,V,I,O) \
- (VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+/* 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, enum vec_allocation_t A>
-static inline void
-VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T obj_
- VEC_CHECK_DECL MEM_STAT_DECL)
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::truncate (unsigned size)
{
- VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
- VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS);
+ if (m_vec)
+ m_vec->truncate (size);
+ else
+ gcc_checking_assert (size == 0);
}
-template<typename T, enum vec_allocation_t A>
-static inline void
-VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T *ptr_
- VEC_CHECK_DECL MEM_STAT_DECL)
+
+/* 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)
{
- VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
- VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS);
+ unsigned oldlen = length ();
+ gcc_checking_assert (oldlen <= len);
+ reserve_exact (len - oldlen PASS_MEM_STAT);
+ if (m_vec)
+ m_vec->quick_grow (len);
+ else
+ gcc_checking_assert (len == 0);
}
+/* 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. */
-/* Remove element retaining order
- void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
- void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
- void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
+{
+ unsigned oldlen = length ();
+ size_t growby = len - oldlen;
+ safe_grow (len PASS_MEM_STAT);
+ if (growby != 0)
+ vec_default_construct (address () + oldlen, growby);
+}
- Remove an element from the IXth position of V. Ordering of
- remaining elements is preserved. This is an O(N) operation due to
- a memmove. */
-#define VEC_ordered_remove(T,V,I) \
- (VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO))
+/* 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>
-static inline void
-VEC_ordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+inline void
+vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
{
- 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));
+ gcc_checking_assert (m_vec);
+ m_vec->quick_grow (len);
}
-/* Remove element destroying order
- void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
- void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
- void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
+/* 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);
+}
- Remove an element from the IXth position of V. Ordering of
- remaining elements is destroyed. This is an O(1) operation. */
-#define VEC_unordered_remove(T,V,I) \
- (VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO))
+/* Insert an element, OBJ, at the IXth position of this vector. There
+ must be sufficient space. */
template<typename T>
-static inline void
-VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+inline void
+vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
{
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);
- vec_->vec[ix_] = vec_->vec[--vec_->prefix.num];
+ m_vec->quick_insert (ix, obj);
}
-/* Remove a block of elements
- void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
+/* Insert an element, OBJ, at the IXth position of the vector.
+ Reallocate the embedded vector, if necessary. */
- 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>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
+{
+ reserve (1, false PASS_MEM_STAT);
+ quick_insert (ix, obj);
+}
-#define VEC_block_remove(T,V,I,L) \
- (VEC_block_remove_1<T> (V, I, L VEC_CHECK_INFO))
+
+/* 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>
-static inline void
-VEC_block_remove_1 (vec_t<T> *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)
+inline void
+vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
{
- 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));
+ m_vec->ordered_remove (ix);
}
-/* Conveniently sort the contents of the vector with qsort.
- void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */
+/* Remove an element from the IXth position of this vector. Ordering
+ of remaining elements is destroyed. This is an O(1) operation. */
-#define VEC_qsort(T,V,CMP) qsort(VEC_address (T, V), VEC_length (T, V), \
- sizeof (T), CMP)
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
+{
+ m_vec->unordered_remove (ix);
+}
-/* 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
+/* Remove LEN elements starting at the IXth. Ordering is retained.
+ This is an O(N) operation due to memmove. */
- 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. */
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
+{
+ m_vec->block_remove (ix, len);
+}
-#define VEC_lower_bound(T,V,O,LT) \
- (VEC_lower_bound_1<T> (V, O, LT VEC_CHECK_INFO))
+
+/* Sort the contents of this vector with qsort. CMP is the comparison
+ function to pass to qsort. */
template<typename T>
-static inline unsigned
-VEC_lower_bound_1 (vec_t<T> *vec_, T obj_,
- bool (*lessthan_)(T, T) VEC_CHECK_DECL)
-{
- unsigned int len_ = VEC_length (T, 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_index_1 (vec_, middle_ VEC_CHECK_PASS);
- if (lessthan_ (middle_elem_, obj_))
- {
- first_ = middle_;
- ++first_;
- len_ = len_ - half_ - 1;
- }
- else
- len_ = half_;
- }
- return first_;
+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>
-static inline unsigned
-VEC_lower_bound_1 (vec_t<T> *vec_, const T *ptr_,
- bool (*lessthan_)(const T*, const T*) VEC_CHECK_DECL)
-{
- unsigned int len_ = VEC_length (T, 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_index_1 (vec_, middle_ VEC_CHECK_PASS);
- if (lessthan_ (middle_elem_, ptr_))
- {
- first_ = middle_;
- ++first_;
- len_ = len_ - half_ - 1;
- }
- else
- len_ = half_;
- }
- return first_;
+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;
}
-void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
-void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
+/* 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;
+}
-/* Ensure there are at least RESERVE free slots in VEC_, growing
- exponentially. If RESERVE < 0 grow exactly, else grow
- exponentially. As a special case, if VEC_ is NULL, and RESERVE is
- 0, no vector will be created. */
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
-template<typename T, enum vec_allocation_t A>
-vec_t<T> *
-vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::contains (const T &search) const
{
- if (A == gc)
- return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
- offsetof (vec_t<T>, vec),
- sizeof (T), false
- PASS_MEM_STAT);
- else if (A == heap)
- return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
- offsetof (vec_t<T>, vec),
- sizeof (T), false
- PASS_MEM_STAT);
- else
- {
- /* Only allow stack vectors when re-growing them. The initial
- allocation of stack vectors must be done with the
- VEC_stack_alloc macro, because it uses alloca() for the
- allocation. */
- if (vec_ == NULL)
- {
- fprintf (stderr, "Stack vectors must be initially allocated "
- "with VEC_stack_alloc.\n");
- gcc_unreachable ();
- }
- return (vec_t<T> *) vec_stack_o_reserve (vec_, reserve,
- offsetof (vec_t<T>, vec),
- sizeof (T) PASS_MEM_STAT);
- }
+ return m_vec ? m_vec->contains (search) : false;
}
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::using_auto_storage () const
+{
+ return m_vec->m_vecpfx.m_using_auto_storage;
+}
-/* Ensure there are at least RESERVE free slots in VEC_, growing
- exactly. If RESERVE < 0 grow exactly, else grow exponentially. As
- a special case, if VEC_ is NULL, and RESERVE is 0, no vector will be
- created. */
+/* Release VEC and call release of all element vectors. */
-template<typename T, enum vec_allocation_t A>
-vec_t<T> *
-vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+template<typename T>
+inline void
+release_vec_vec (vec<vec<T> > &vec)
{
- if (A == gc)
- return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
- sizeof (struct vec_prefix),
- sizeof (T), true
- PASS_MEM_STAT);
- else if (A == heap)
- return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
- sizeof (struct vec_prefix),
- sizeof (T), true
- PASS_MEM_STAT);
- else if (A == stack)
- {
- /* Only allow stack vectors when re-growing them. The initial
- allocation of stack vectors must be done with VEC_alloc,
- because it uses alloca() for the allocation. */
- if (vec_ == NULL)
- {
- fprintf (stderr, "Stack vectors must be initially allocated "
- "with VEC_stack_alloc.\n");
- gcc_unreachable ();
- }
- return (vec_t<T> *) vec_stack_o_reserve_exact (vec_, reserve,
- sizeof (struct vec_prefix),
- sizeof (T)
- PASS_MEM_STAT);
- }
+ for (unsigned i = 0; i < vec.length (); i++)
+ vec[i].release ();
+
+ vec.release ();
}
-#endif /* GCC_VEC_H */
+#if (GCC_VERSION >= 3000)
+# pragma GCC poison m_vec m_vecpfx m_vecdata
+#endif
+
+#endif // GCC_VEC_H
projects / gcc.git / blobdiff