diff options
Diffstat (limited to 'gcc/vec.h')
| -rw-r--r-- | gcc/vec.h | 1739 |
1 files changed, 738 insertions, 1001 deletions
@@ -1,7 +1,8 @@ /* Vector API for GNU compiler. - Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010 + Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012 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. @@ -134,6 +135,153 @@ along with GCC; see the file COPYING3. If not see */ +#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 + +#define VEC(T,A) vec_t<T> + +enum vec_allocation_t { heap, gc, stack }; + +struct vec_prefix +{ + unsigned num; + unsigned alloc; +}; + +/* Vector type, user visible. */ +template<typename T> +struct GTY(()) vec_t +{ + vec_prefix prefix; + T vec[1]; +}; + +/* Garbage collection support for vec_t. */ + +template<typename T> +void +gt_ggc_mx (vec_t<T> *v) +{ + extern void gt_ggc_mx (T&); + for (unsigned i = 0; i < v->prefix.num; i++) + gt_ggc_mx (v->vec[i]); +} + + +/* PCH support for vec_t. */ + +template<typename T> +void +gt_pch_nx (vec_t<T> *v) +{ + extern void gt_pch_nx (T&); + for (unsigned i = 0; i < v->prefix.num; i++) + gt_pch_nx (v->vec[i]); +} + +template<typename T> +void +gt_pch_nx (vec_t<T *> *v, gt_pointer_operator op, void *cookie) +{ + for (unsigned i = 0; i < v->prefix.num; i++) + op (&(v->vec[i]), cookie); +} + +template<typename T> +void +gt_pch_nx (vec_t<T> *v, gt_pointer_operator op, void *cookie) +{ + 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); + +extern void dump_vec_loc_statistics (void); +extern void ggc_free (void *); +extern void vec_heap_free (void *); + + /* 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, @@ -148,7 +296,14 @@ along with GCC; see the file COPYING3. If not see 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))) +#define VEC_length(T,V) (VEC_length_1<T> (V)) + +template<typename T> +static inline unsigned +VEC_length_1 (const vec_t<T> *vec_) +{ + return vec_ ? vec_->prefix.num : 0; +} /* Check if vector is empty @@ -156,7 +311,30 @@ along with GCC; see the file COPYING3. If not see Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ -#define VEC_empty(T,V) (VEC_length (T,V) == 0) +#define VEC_empty(T,V) (VEC_empty_1<T> (V)) + +template<typename T> +static inline bool +VEC_empty_1 (const vec_t<T> *vec_) +{ + return VEC_length (T, vec_) == 0; +} + + +/* 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_address_1<T> (V)) + +template<typename T> +static inline T * +VEC_address_1 (vec_t<T> *vec_) +{ + return vec_ ? vec_->vec : 0; +} /* Get the final element of the vector. @@ -166,16 +344,42 @@ along with GCC; see the file COPYING3. If not see Return the final element. V must not be empty. */ -#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) +#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) +{ + VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); + return vec_->vec[vec_->prefix.num - 1]; +} + /* 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. */ + 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)) + +template<typename T> +static inline T& +VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) +{ + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); + return vec_->vec[ix_]; +} + +template<typename T> +static inline const T& +VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) +{ + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); + return vec_->vec[ix_]; +} -#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) /* Iterate over vector int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer @@ -189,7 +393,39 @@ along with GCC; see the file COPYING3. If not see for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) continue; */ -#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) +#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 (vec_ && ix_ < vec_->prefix.num) + { + *ptr = vec_->vec[ix_]; + return true; + } + else + { + *ptr = 0; + return false; + } +} + +template<typename T> +static inline bool +VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr) +{ + if (vec_ && ix_ < vec_->prefix.num) + { + *ptr = &vec_->vec[ix_]; + return true; + } + else + { + *ptr = 0; + return false; + } +} /* Convenience macro for forward iteration. */ @@ -208,31 +444,99 @@ along with GCC; see the file COPYING3. If not see VEC_iterate (T, (V), (I), (P)); \ (I)--) + +/* 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); + + These allow the caller to perform the memory allocation. */ + +#define VEC_embedded_size(T,N) (VEC_embedded_size_1<T> (N)) + +template<typename T> +static inline size_t +VEC_embedded_size_1 (int alloc_) +{ + return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T); +} + +#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N)) + +template<typename T> +static inline void +VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_) +{ + vec_->prefix.num = 0; + vec_->prefix.alloc = alloc_; +} + + /* 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. */ + is zero, NO vector is created. + + 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. + + 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)) + +template<typename T, enum vec_allocation_t A> +static inline vec_t<T> * +VEC_alloc_1 (int alloc_ MEM_STAT_DECL) +{ + return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT); +} + +template<typename T> +static inline vec_t<T> * +VEC_alloc_1 (int alloc_, vec_t<T> *space) +{ + return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space); +} -#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) /* Free a vector. void VEC_T_A_free(VEC(T,A) *&); Free a vector and set it to NULL. */ -#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) +#define VEC_free(T,A,V) (VEC_free_1<T, A> (&V)) -/* 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); - - These allow the caller to perform the memory allocation. */ +template<typename T, enum vec_allocation_t A> +static inline void +VEC_free_1 (vec_t<T> **vec_) +{ + if (*vec_) + { + if (A == heap) + vec_heap_free (*vec_); + else if (A == gc) + ggc_free (*vec_); + else if (A == stack) + vec_stack_free (*vec_); + } + *vec_ = NULL; +} -#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)) /* Copy a vector. VEC(T,A) *VEC_T_A_copy(VEC(T) *); @@ -240,7 +544,24 @@ along with GCC; see the file COPYING3. If not see Copy the live elements of a vector into a new vector. The new and old vectors need not be allocated by the same mechanism. */ -#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) +#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; + + 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_); + } + return new_vec_; +} + /* Determine if a vector has additional capacity. @@ -252,8 +573,18 @@ along with GCC; see the file COPYING3. If not see nonzero in exactly the same circumstances that VEC_T_reserve will. */ -#define VEC_space(T,V,R) \ - (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) +#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) +{ + VEC_ASSERT (alloc_ >= 0, "space", T, base); + return vec_ + ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ + : !alloc_; +} + /* Reserve space. int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); @@ -264,7 +595,20 @@ along with GCC; see the file COPYING3. If not see occurred. */ #define VEC_reserve(T,A,V,R) \ - (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) + (VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO)) + +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) +{ + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); + + if (extend) + *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT); + + return extend; +} + /* Reserve space exactly. int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve); @@ -275,7 +619,20 @@ along with GCC; see the file COPYING3. If not see occurred. */ #define VEC_reserve_exact(T,A,V,R) \ - (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) + (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) +{ + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); + + if (extend) + *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT); + + return extend; +} + /* Copy elements with no reallocation void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer @@ -287,8 +644,23 @@ along with GCC; see the file COPYING3. If not see often will be. DST is assumed to have sufficient headroom available. */ -#define VEC_splice(T,DST,SRC) \ - (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO)) +#define VEC_splice(T,DST,SRC) (VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO)) + +template<typename T> +static inline void +VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *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_; + } +} + /* Copy elements with reallocation void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer @@ -301,7 +673,21 @@ along with GCC; see the file COPYING3. If not see reallocated if needed. */ #define VEC_safe_splice(T,A,DST,SRC) \ - (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO)) + (VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO)) + +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) +{ + if (src_) + { + VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num + VEC_CHECK_PASS MEM_STAT_INFO); + + VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS); + } +} + /* Push object with no reallocation T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer @@ -313,8 +699,31 @@ along with GCC; see the file COPYING3. If not see case NO initialization is performed. There must be sufficient space in the vector. */ -#define VEC_quick_push(T,V,O) \ - (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) +#define VEC_quick_push(T,V,O) (VEC_quick_push_1<T> (V, O VEC_CHECK_INFO)) + +template<typename T> +static inline T & +VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL) +{ + 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_; +} + +template<typename T> +static inline T * +VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL) +{ + 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_; +} + /* Push object with reallocation T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer @@ -326,7 +735,24 @@ along with GCC; see the file COPYING3. If not see case NO initialization is performed. Reallocates V, if needed. */ #define VEC_safe_push(T,A,V,O) \ - (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) + (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) +{ + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS); +} + +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) +{ + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS); +} + /* Pop element off end T VEC_T_pop (VEC(T) *v); // Integer @@ -336,7 +762,16 @@ along with GCC; see the file COPYING3. If not see Pop the last element off the end. Returns the element popped, for pointer vectors. */ -#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) +#define VEC_pop(T,V) (VEC_pop_1<T> (V VEC_CHECK_INFO)) + +template<typename T> +static inline T& +VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL) +{ + VEC_ASSERT (vec_->prefix.num, "pop", T, base); + return vec_->vec[--vec_->prefix.num]; +} + /* Truncate to specific length void VEC_T_truncate (VEC(T) *v, unsigned len); @@ -344,8 +779,18 @@ along with GCC; see the file COPYING3. If not see Set the length as specified. The new length must be less than or equal to the current length. This is an O(1) operation. */ -#define VEC_truncate(T,V,I) \ - (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) +#define VEC_truncate(T,V,I) \ + (VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO)) + +template<typename T> +static inline void +VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL) +{ + VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); + if (vec_) + vec_->prefix.num = size_; +} + /* Grow to a specific length. void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); @@ -355,7 +800,20 @@ along with GCC; see the file COPYING3. If not see uninitialized. */ #define VEC_safe_grow(T,A,V,I) \ - (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) + (VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO)) + +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) +{ + 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_; +} + /* Grow to a specific length. void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len); @@ -364,8 +822,21 @@ along with GCC; see the file COPYING3. If not see long or longer than the current length. The new elements are initialized to zero. */ -#define VEC_safe_grow_cleared(T,A,V,I) \ - (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) +#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)) + +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) +{ + 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)); +} + /* Replace element T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer @@ -379,20 +850,57 @@ along with GCC; see the file COPYING3. If not see performed. */ #define VEC_replace(T,V,I,O) \ - (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) + (VEC_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO)) + +template<typename T> +static inline T& +VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) +{ + VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); + vec_->vec[ix_] = obj_; + return vec_->vec[ix_]; +} + /* 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 + 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 - 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. */ + 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. */ #define VEC_quick_insert(T,V,I,O) \ - (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) + (VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO)) + +template<typename T> +static inline void +VEC_quick_insert_1 (vec_t<T> *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_; +} + +template<typename T> +static inline void +VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_ 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 (ptr_) + *slot_ = *ptr_; +} + /* Insert object with reallocation T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer @@ -405,31 +913,70 @@ along with GCC; see the file COPYING3. If not see place. Reallocate V, if necessary. */ #define VEC_safe_insert(T,A,V,I,O) \ - (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) + (VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) + +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) +{ + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS); +} + +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) +{ + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS); +} + + /* 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); // Integer + void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object 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. */ + remaining elements is preserved. This is an O(N) operation due to + a memmove. */ #define VEC_ordered_remove(T,V,I) \ - (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) + (VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO)) + +template<typename T> +static inline void +VEC_ordered_remove_1 (vec_t<T> *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)); +} + /* 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); // Integer + void 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. */ + 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_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) + (VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO)) + +template<typename T> +static inline void +VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) +{ + VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); + vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; +} + /* Remove a block of elements void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); @@ -438,22 +985,27 @@ along with GCC; see the file COPYING3. If not see 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)) + (VEC_block_remove_1<T> (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. */ +template<typename T> +static inline void +VEC_block_remove_1 (vec_t<T> *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)); +} -#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), \ +#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 @@ -466,955 +1018,140 @@ along with GCC; see the file COPYING3. If not see 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)) +#define VEC_lower_bound(T,V,O,LT) \ + (VEC_lower_bound_1<T> (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); -extern void vec_heap_free (void *); - -#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 - -/* 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 +template<typename T> +static inline unsigned +VEC_lower_bound_1 (vec_t<T> *vec_, T obj_, + bool (*lessthan_)(T, T) VEC_CHECK_DECL) { - 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) - -#define VEC_T_GTY_ATOMIC(T,B) \ -typedef struct GTY(()) VEC(T,B) \ -{ \ - struct vec_prefix prefix; \ - T GTY ((atomic)) 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_; \ + 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_; } -#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 - -/* Vector of atomic object. */ -#define DEF_VEC_A(T) \ -VEC_T_GTY_ATOMIC(T,base); \ -VEC_TA(T,base,none); \ -DEF_VEC_FUNC_O(T) \ -struct vec_swallow_trailing_semi -#define DEF_VEC_ALLOC_A(T,A) DEF_VEC_ALLOC_O(T,A) - -#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); \ +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_; } -/* 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) +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); - This is really a hack and perhaps can be made better. Note that - this macro will wind up evaluating the ALLOC parameter twice. +/* 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. */ - 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 *); - -/* Unfortunately, we cannot use MEM_STAT_DECL here. */ -#if 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 - -#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 - -#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, enum vec_allocation_t A> +vec_t<T> * +vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL) +{ + 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); + } } -#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); \ -} - -#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 +/* 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. */ -#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); \ +template<typename T, enum vec_allocation_t A> +vec_t<T> * +vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL) +{ + 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); + } } #endif /* GCC_VEC_H */ |