#ifndef GCC_VEC_H
#define GCC_VEC_H
#define VEC_length(TDEF,V) (VEC_OP(TDEF,length)(V))
#define VEC_empty(T,V) (VEC_length (T,V) == 0)
#define VEC_last(TDEF,V) (VEC_OP(TDEF,last)(V VEC_CHECK_INFO))
#define VEC_index(TDEF,V,I) (VEC_OP(TDEF,index)(V,I VEC_CHECK_INFO))
#define VEC_iterate(TDEF,V,I,P) (VEC_OP(TDEF,iterate)(V,I,&(P)))
#define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A MEM_STAT_INFO))
#define VEC_free(TDEF,V) (VEC_OP(TDEF,free)(&V))
#define VEC_embedded_size(TDEF,A) (VEC_OP(TDEF,embedded_size)(A))
#define VEC_embedded_init(TDEF,O,A) (VEC_OP(TDEF,embedded_init)(O,A))
#define VEC_space(TDEF,V,R) (VEC_OP(TDEF,space)(V,R))
#define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R MEM_STAT_INFO))
#define VEC_quick_push(TDEF,V,O) \
(VEC_OP(TDEF,quick_push)(V,O VEC_CHECK_INFO))
#define VEC_safe_push(TDEF,V,O) \
(VEC_OP(TDEF,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
#define VEC_pop(TDEF,V) (VEC_OP(TDEF,pop)(V VEC_CHECK_INFO))
#define VEC_truncate(TDEF,V,I) \
(VEC_OP(TDEF,truncate)(V,I VEC_CHECK_INFO))
#define VEC_replace(TDEF,V,I,O) \
(VEC_OP(TDEF,replace)(V,I,O VEC_CHECK_INFO))
#define VEC_quick_insert(TDEF,V,I,O) \
(VEC_OP(TDEF,quick_insert)(V,I,O VEC_CHECK_INFO))
#define VEC_safe_insert(TDEF,V,I,O) \
(VEC_OP(TDEF,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
#define VEC_ordered_remove(TDEF,V,I) \
(VEC_OP(TDEF,ordered_remove)(V,I VEC_CHECK_INFO))
#define VEC_unordered_remove(TDEF,V,I) \
(VEC_OP(TDEF,unordered_remove)(V,I VEC_CHECK_INFO))
#define VEC_address(TDEF,V) (VEC_OP(TDEF,address)(V))
#define VEC_lower_bound(TDEF,V,O,LT) \
(VEC_OP(TDEF,lower_bound)(V,O,LT VEC_CHECK_INFO))
#if !IN_GENGTYPE
extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
extern void vec_gc_free (void *);
extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
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,TDEF) \
(void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(TDEF)), 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,TYPE) (void)(EXPR)
#endif
#define VEC(TDEF) VEC_##TDEF
#define VEC_OP(TDEF,OP) VEC_OP_(VEC(TDEF),OP)
#define VEC_OP_(VEC,OP) VEC_OP__(VEC,OP)
#define VEC_OP__(VEC,OP) VEC ## _ ## OP
#else
#define VEC(TDEF) VEC_ TDEF
#define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
#define VEC_STRINGIFY_(X) #X
#undef GTY
#endif
#define VEC_TDEF(TDEF) \
typedef struct VEC (TDEF) GTY(()) \
{ \
unsigned num; \
unsigned alloc; \
TDEF GTY ((length ("%h.num"))) vec[1]; \
} VEC (TDEF)
#if IN_GENGTYPE
{"DEF_VEC_GC_P", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
{"DEF_VEC_MALLOC_P", "", NULL},
#else
#define DEF_VEC_GC_P(TDEF) DEF_VEC_P(TDEF,gc)
#define DEF_VEC_MALLOC_P(TDEF) DEF_VEC_P(TDEF,heap)
#define DEF_VEC_P(TDEF,a) \
VEC_TDEF (TDEF); \
\
static inline unsigned VEC_OP (TDEF,length) \
(const VEC (TDEF) *vec_) \
{ \
return vec_ ? vec_->num : 0; \
} \
\
static inline TDEF VEC_OP (TDEF,last) \
(const VEC (TDEF) *vec_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ && vec_->num, "last", TDEF); \
\
return vec_->vec[vec_->num - 1]; \
} \
\
static inline TDEF VEC_OP (TDEF,index) \
(const VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
\
return vec_->vec[ix_]; \
} \
\
static inline int VEC_OP (TDEF,iterate) \
(const VEC (TDEF) *vec_, unsigned ix_, TDEF *ptr) \
{ \
if (vec_ && ix_ < vec_->num) \
{ \
*ptr = vec_->vec[ix_]; \
return 1; \
} \
else \
{ \
*ptr = 0; \
return 0; \
} \
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
(int alloc_ MEM_STAT_DECL) \
{ \
return (VEC (TDEF) *) vec_##a##_p_reserve (NULL, alloc_ - !alloc_ PASS_MEM_STAT);\
} \
\
static inline void VEC_OP (TDEF,free) \
(VEC (TDEF) **vec_) \
{ \
vec_##a##_free (*vec_); \
*vec_ = NULL; \
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
(int alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
(VEC (TDEF) *vec_, int alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
static inline int VEC_OP (TDEF,space) \
(VEC (TDEF) *vec_, int alloc_) \
{ \
return vec_ ? ((vec_)->alloc - (vec_)->num \
>= (unsigned)(alloc_ < 0 ? 1 : alloc_)) : !alloc_; \
} \
\
static inline int VEC_OP (TDEF,reserve) \
(VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
{ \
int extend = !VEC_OP (TDEF,space) (*vec_, alloc_); \
\
if (extend) \
*vec_ = (VEC (TDEF) *) vec_##a##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
\
return extend; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
(VEC (TDEF) *vec_, TDEF obj_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (vec_->num < vec_->alloc, "push", TDEF); \
slot_ = &vec_->vec[vec_->num++]; \
*slot_ = obj_; \
\
return slot_; \
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, TDEF obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
{ \
VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_ VEC_CHECK_PASS); \
} \
\
static inline TDEF VEC_OP (TDEF,pop) \
(VEC (TDEF) *vec_ VEC_CHECK_DECL) \
{ \
TDEF obj_; \
\
VEC_ASSERT (vec_->num, "pop", TDEF); \
obj_ = vec_->vec[--vec_->num]; \
\
return obj_; \
} \
\
static inline void VEC_OP (TDEF,truncate) \
(VEC (TDEF) *vec_, unsigned size_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", TDEF); \
if (vec_) \
vec_->num = size_; \
} \
\
static inline TDEF VEC_OP (TDEF,replace) \
(VEC (TDEF) *vec_, unsigned ix_, TDEF obj_ VEC_CHECK_DECL) \
{ \
TDEF old_obj_; \
\
VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
old_obj_ = vec_->vec[ix_]; \
vec_->vec[ix_] = obj_; \
\
return old_obj_; \
} \
\
static inline unsigned VEC_OP (TDEF,lower_bound) \
(VEC (TDEF) *vec_, const TDEF obj_, bool (*lessthan_)(const TDEF, const TDEF) VEC_CHECK_DECL) \
{ \
unsigned int len_ = VEC_OP (TDEF, length) (vec_); \
unsigned int half_, middle_; \
unsigned int first_ = 0; \
while (len_ > 0) \
{ \
TDEF middle_elem_; \
half_ = len_ >> 1; \
middle_ = first_; \
middle_ += half_; \
middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
if (lessthan_ (middle_elem_, obj_)) \
{ \
first_ = middle_; \
++first_; \
len_ = len_ - half_ - 1; \
} \
else \
len_ = half_; \
} \
return first_; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_insert) \
(VEC (TDEF) *vec_, unsigned ix_, TDEF obj_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (vec_->num < vec_->alloc, "insert", TDEF); \
VEC_ASSERT (ix_ <= vec_->num, "insert", TDEF); \
slot_ = &vec_->vec[ix_]; \
memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (TDEF)); \
*slot_ = obj_; \
\
return slot_; \
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, unsigned ix_, TDEF obj_ \
VEC_CHECK_DECL MEM_STAT_DECL) \
{ \
VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS); \
} \
\
static inline TDEF VEC_OP (TDEF,ordered_remove) \
(VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
TDEF obj_; \
\
VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
slot_ = &vec_->vec[ix_]; \
obj_ = *slot_; \
memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF)); \
\
return obj_; \
} \
\
static inline TDEF VEC_OP (TDEF,unordered_remove) \
(VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
TDEF obj_; \
\
VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
slot_ = &vec_->vec[ix_]; \
obj_ = *slot_; \
*slot_ = vec_->vec[--vec_->num]; \
\
return obj_; \
} \
\
static inline TDEF *VEC_OP (TDEF,address) \
(VEC (TDEF) *vec_) \
{ \
return vec_ ? vec_->vec : 0; \
} \
\
struct vec_swallow_trailing_semi
#endif
#if IN_GENGTYPE
{"DEF_VEC_GC_O", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
{"DEF_VEC_MALLOC_O", "", NULL},
#else
#define DEF_VEC_GC_O(TDEF) DEF_VEC_O(TDEF,gc)
#define DEF_VEC_MALLOC_O(TDEF) DEF_VEC_O(TDEF,heap)
#define DEF_VEC_O(TDEF,a) \
VEC_TDEF (TDEF); \
\
static inline unsigned VEC_OP (TDEF,length) \
(const VEC (TDEF) *vec_) \
{ \
return vec_ ? vec_->num : 0; \
} \
\
static inline TDEF *VEC_OP (TDEF,last) \
(VEC (TDEF) *vec_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ && vec_->num, "last", TDEF); \
\
return &vec_->vec[vec_->num - 1]; \
} \
\
static inline TDEF *VEC_OP (TDEF,index) \
(VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
\
return &vec_->vec[ix_]; \
} \
\
static inline int VEC_OP (TDEF,iterate) \
(VEC (TDEF) *vec_, unsigned ix_, TDEF **ptr) \
{ \
if (vec_ && ix_ < vec_->num) \
{ \
*ptr = &vec_->vec[ix_]; \
return 1; \
} \
else \
{ \
*ptr = 0; \
return 0; \
} \
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
(int alloc_ MEM_STAT_DECL) \
{ \
return (VEC (TDEF) *) vec_##a##_o_reserve (NULL, alloc_ - !alloc_, \
offsetof (VEC(TDEF),vec), sizeof (TDEF)\
PASS_MEM_STAT); \
} \
\
static inline void VEC_OP (TDEF,free) \
(VEC (TDEF) **vec_) \
{ \
vec_##a##_free (*vec_); \
*vec_ = NULL; \
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
(int alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
(VEC (TDEF) *vec_, int alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
static inline int VEC_OP (TDEF,space) \
(VEC (TDEF) *vec_, int alloc_) \
{ \
return vec_ ? ((vec_)->alloc - (vec_)->num \
>= (unsigned)(alloc_ < 0 ? 1 : alloc_)) : !alloc_; \
} \
\
static inline int VEC_OP (TDEF,reserve) \
(VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
{ \
int extend = !VEC_OP (TDEF,space) (*vec_, alloc_); \
\
if (extend) \
*vec_ = (VEC (TDEF) *) vec_##a##_o_reserve (*vec_, alloc_, \
offsetof (VEC(TDEF),vec), sizeof (TDEF) \
PASS_MEM_STAT); \
\
return extend; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
(VEC (TDEF) *vec_, const TDEF *obj_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (vec_->num < vec_->alloc, "push", TDEF); \
slot_ = &vec_->vec[vec_->num++]; \
if (obj_) \
*slot_ = *obj_; \
\
return slot_; \
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, const TDEF *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
{ \
VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_ VEC_CHECK_PASS); \
} \
\
static inline void VEC_OP (TDEF,pop) \
(VEC (TDEF) *vec_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_->num, "pop", TDEF); \
--vec_->num; \
} \
\
static inline void VEC_OP (TDEF,truncate) \
(VEC (TDEF) *vec_, unsigned size_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", TDEF); \
if (vec_) \
vec_->num = size_; \
} \
\
static inline TDEF *VEC_OP (TDEF,replace) \
(VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
slot_ = &vec_->vec[ix_]; \
if (obj_) \
*slot_ = *obj_; \
\
return slot_; \
} \
\
static inline unsigned VEC_OP (TDEF,lower_bound) \
(VEC (TDEF) *vec_, const TDEF *obj_, bool (*lessthan_)(const TDEF *, const TDEF *) VEC_CHECK_DECL) \
{ \
unsigned int len_ = VEC_OP (TDEF, length) (vec_); \
unsigned int half_, middle_; \
unsigned int first_ = 0; \
while (len_ > 0) \
{ \
TDEF *middle_elem_; \
half_ = len_ >> 1; \
middle_ = first_; \
middle_ += half_; \
middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
if (lessthan_ (middle_elem_, obj_)) \
{ \
first_ = middle_; \
++first_; \
len_ = len_ - half_ - 1; \
} \
else \
len_ = half_; \
} \
return first_; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_insert) \
(VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (vec_->num < vec_->alloc, "insert", TDEF); \
VEC_ASSERT (ix_ <= vec_->num, "insert", TDEF); \
slot_ = &vec_->vec[ix_]; \
memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (TDEF)); \
if (obj_) \
*slot_ = *obj_; \
\
return slot_; \
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, unsigned ix_, const TDEF *obj_ \
VEC_CHECK_DECL MEM_STAT_DECL) \
{ \
VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_ VEC_CHECK_PASS); \
} \
\
static inline void VEC_OP (TDEF,ordered_remove) \
(VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
TDEF *slot_; \
\
VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
slot_ = &vec_->vec[ix_]; \
memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (TDEF)); \
} \
\
static inline void VEC_OP (TDEF,unordered_remove) \
(VEC (TDEF) *vec_, unsigned ix_ VEC_CHECK_DECL) \
{ \
VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
vec_->vec[ix_] = vec_->vec[--vec_->num]; \
} \
\
static inline TDEF *VEC_OP (TDEF,address) \
(VEC (TDEF) *vec_) \
{ \
return vec_ ? vec_->vec : 0; \
} \
\
struct vec_swallow_trailing_semi
#endif
#endif