This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Vector API tweaks
- From: Nathan Sidwell <nathan at codesourcery dot com>
- To: Mark Mitchell <mark at codesourcery dot com>
- Cc: gcc-patches at gcc dot gnu dot org, Ben Elliston <bje at au1 dot ibm dot com>
- Date: Tue, 06 Jul 2004 17:36:52 +0100
- Subject: Vector API tweaks
- Organization: Codesourcery LLC
This patch makes a few changes to the vector API
1) Added a VEC_truncate call for O(1) deletion. Requested by Ben.
2) Added MEM_STAT_DECL and MEM_STAT_INFO stuff
3) Replaced the VEC_embedded_alloc with VEC_embedded_size & VEC_embedded_init,
which are more flexible.
built & tested on i686-pc-linux gnu, ok?
nathan
--
Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC
nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk
2004-07-06 Nathan Sidwell <nathan@codesourcery.com>
* vec.h (VEC_embedded_alloc): Remove.
(VEC_embedded_size, VEC_embedded_init): New.
(VEC_alloc, VEC_reserve, VEC_safe_push, VEC_safe_insert): Add
MEM_STAT_INFO.
(VEC_truncate): New.
(vec_p_reserve, vec_o_reserve): Add MEM_STAT_DECL.
(vec_embedded_alloc): Remove.
* vec.c (vec_p_reserve, vec_o_reserve): Add MEM_STAT_DECL, adjust.
(vec_embedded_alloc): Remove.
Index: vec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/vec.h,v
retrieving revision 2.3
diff -c -3 -p -r2.3 vec.h
*** vec.h 29 Jun 2004 15:56:17 -0000 2.3
--- vec.h 6 Jul 2004 13:41:20 -0000
*************** Software Foundation, 59 Temple Place - S
*** 44,55 ****
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_alloc call 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.
Each operation that increases the number of active elements is
available in 'quick' and 'safe' variants. The former presumes that
--- 44,55 ----
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.
Each operation that increases the number of active elements is
available in 'quick' and 'safe' variants. The former presumes that
*************** Software Foundation, 59 Temple Place - S
*** 61,67 ****
elements with the 'quick' operation.
You should prefer the push and pop operations, as they append and
! remove from the end of the vector. The insert and remove
operations allow you to change elements in the middle of the
vector. There are two remove operations, one which preserves the
element ordering 'ordered_remove', and one which does not
--- 61,68 ----
elements with the 'quick' operation.
You should prefer the push and pop operations, as they append and
! remove from the end of the vector. If you need to remove several
! items in one go, use the truncate operation. The insert and remove
operations allow you to change elements in the middle of the
vector. There are two remove operations, one which preserves the
element ordering 'ordered_remove', and one which does not
*************** Software Foundation, 59 Temple Place - S
*** 134,156 ****
VEC(T) *VEC_T_alloc(size_t reserve);
Allocate a new vector with space for RESERVE objects. */
! #define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A))
! /* Allocate new vector offset within a structure
! void *VEC_T_embedded_alloc(size_t offset, size_t reserve);
!
! Allocate a new vector which is at offset OFFSET within a structure,
! and with space for RESERVE objects. Return a pointer to the start
! of the structure containing the vector. Naturally, the vector must
! be the last member of the structure. */
! #define VEC_embedded_alloc(TDEF,O,A) (VEC_OP(TDEF,embedded_alloc)(O,A))
/* Reserve space.
void VEC_T_reserve(VEC(T) *&v, size_t reserve);
Ensure that V has at least RESERVE slots available. Note this can
cause V to be reallocated. */
! #define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R))
/* Push object with no reallocation
T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
--- 135,158 ----
VEC(T) *VEC_T_alloc(size_t reserve);
Allocate a new vector with space for RESERVE objects. */
! #define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A MEM_STAT_INFO))
! /* 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(size_t reserve);
! void VEC_T_embedded_init(VEC(T) *v, size_t reserve);
!
! These allow the caller to perform the memory allocation. */
! #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))
/* Reserve space.
void VEC_T_reserve(VEC(T) *&v, size_t reserve);
Ensure that V has at least RESERVE slots available. Note this can
cause V to be reallocated. */
! #define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R MEM_STAT_INFO))
/* Push object with no reallocation
T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
*************** Software Foundation, 59 Temple Place - S
*** 169,175 ****
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. */
! #define VEC_safe_push(TDEF,V,O) (VEC_OP(TDEF,safe_push)(&(V),O))
/* Pop element off end
T VEC_T_pop (VEC(T) *v); // Pointer
--- 171,177 ----
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. */
! #define VEC_safe_push(TDEF,V,O) (VEC_OP(TDEF,safe_push)(&(V),O MEM_STAT_INFO))
/* Pop element off end
T VEC_T_pop (VEC(T) *v); // Pointer
*************** Software Foundation, 59 Temple Place - S
*** 179,184 ****
--- 181,192 ----
pointer vectors. */
#define VEC_pop(TDEF,V) (VEC_OP(TDEF,pop)(V))
+ /* Truncate to specific length
+ void VEC_T_truncate (VEC(T) *v, size_t len);
+
+ Set the length as specified. This is an O(1) operation. */
+ #define VEC_truncate(TDEF,V,I) (VEC_OP(TDEF,truncate)(V,I))
+
/* Replace element
T VEC_T_replace (VEC(T) *v, size_t ix, T val); // Pointer
T *VEC_T_replace (VEC(T) *v, size_t ix, T *val); // Object
*************** Software Foundation, 59 Temple Place - S
*** 208,214 ****
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(TDEF,V,I,O) (VEC_OP(TDEF,safe_insert)(&(V),I,O))
/* Remove element retaining order
T VEC_T_ordered_remove (VEC(T) *v, size_t ix); // Pointer
--- 216,222 ----
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(TDEF,V,I,O) (VEC_OP(TDEF,safe_insert)(&(V),I,O MEM_STAT_INFO))
/* Remove element retaining order
T VEC_T_ordered_remove (VEC(T) *v, size_t ix); // Pointer
*************** Software Foundation, 59 Temple Place - S
*** 229,240 ****
#define VEC_unordered_remove(TDEF,V,I) (VEC_OP(TDEF,unordered_remove)(V,I))
#if !IN_GENGTYPE
- #include "auto-host.h"
-
/* Reallocate an array of elements with prefix. */
! extern void *vec_p_reserve (void *, size_t);
! extern void *vec_o_reserve (void *, size_t, size_t, size_t);
! extern void *vec_embedded_alloc (size_t, size_t, size_t, size_t);
#if ENABLE_CHECKING
extern void vec_assert_fail (const char *, const char *,
--- 237,245 ----
#define VEC_unordered_remove(TDEF,V,I) (VEC_OP(TDEF,unordered_remove)(V,I))
#if !IN_GENGTYPE
/* Reallocate an array of elements with prefix. */
! extern void *vec_p_reserve (void *, size_t MEM_STAT_DECL);
! extern void *vec_o_reserve (void *, size_t, size_t, size_t MEM_STAT_DECL);
#if ENABLE_CHECKING
extern void vec_assert_fail (const char *, const char *,
*************** static inline TDEF VEC_OP (TDEF,iterate)
*** 304,326 ****
return vec_ && ix_ < vec_->num ? vec_->vec[ix_] : NULL; \
} \
\
! static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
(size_t alloc_) \
{ \
! return vec_p_reserve (NULL, alloc_ - !alloc_); \
} \
\
! static inline void *VEC_OP (TDEF,embedded_alloc) \
! (size_t offset_, size_t alloc_) \
{ \
! return vec_embedded_alloc (offset_, offsetof (VEC(TDEF),vec), \
! sizeof (TDEF), alloc_); \
} \
\
static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_) \
{ \
! *vec_ = vec_p_reserve (*vec_, alloc_); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
--- 309,337 ----
return vec_ && ix_ < vec_->num ? vec_->vec[ix_] : NULL; \
} \
\
! static inline VEC (TDEF) *VEC_OP (TDEF,alloc MEM_STAT_DECL) \
(size_t alloc_) \
{ \
! return vec_p_reserve (NULL, alloc_ - !alloc_ PASS_MEM_STAT); \
} \
\
! static inline size_t VEC_OP (TDEF,embedded_size) \
! (size_t alloc_) \
{ \
! return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
! } \
! \
! static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, size_t alloc_) \
! { \
! vec_->num = 0; \
! vec_->alloc = alloc_; \
} \
\
static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_ MEM_STAT_DECL) \
{ \
! *vec_ = vec_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
*************** static inline TDEF *VEC_OP (TDEF,quick_p
*** 336,345 ****
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
! (VEC (TDEF) **vec_, TDEF obj_) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
--- 347,356 ----
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
! (VEC (TDEF) **vec_, TDEF obj_ MEM_STAT_DECL) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
*************** static inline TDEF VEC_OP (TDEF,pop)
*** 355,360 ****
--- 366,378 ----
return obj_; \
} \
\
+ static inline void VEC_OP (TDEF,truncate) \
+ (VEC (TDEF) *vec_, size_t size_) \
+ { \
+ VEC_ASSERT (vec_->num >= size_, "truncate", TDEF); \
+ vec_->num = size_; \
+ } \
+ \
static inline TDEF VEC_OP (TDEF,replace) \
(VEC (TDEF) *vec_, size_t ix_, TDEF obj_) \
{ \
*************** static inline TDEF *VEC_OP (TDEF,quick_i
*** 382,391 ****
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
! (VEC (TDEF) **vec_, size_t ix_, TDEF obj_) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
--- 400,409 ----
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
! (VEC (TDEF) **vec_, size_t ix_, TDEF obj_ MEM_STAT_DECL) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
*************** static inline TDEF *VEC_OP (TDEF,iterate
*** 458,481 ****
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
! (size_t alloc_) \
{ \
return vec_o_reserve (NULL, alloc_ - !alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF)); \
} \
\
! static inline void *VEC_OP (TDEF,embedded_alloc) \
! (size_t offset_, size_t alloc_) \
{ \
! return vec_embedded_alloc (offset_, offsetof (VEC(TDEF),vec), \
! sizeof (TDEF), alloc_); \
} \
\
static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_) \
{ \
*vec_ = vec_o_reserve (*vec_, alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF)); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
--- 476,507 ----
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
! (size_t alloc_ MEM_STAT_DECL) \
{ \
return vec_o_reserve (NULL, alloc_ - !alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF) \
! PASS_MEM_STAT); \
! } \
! \
! static inline size_t VEC_OP (TDEF,embedded_size) \
! (size_t alloc_) \
! { \
! return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
! static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, size_t alloc_) \
{ \
! vec_->num = 0; \
! vec_->alloc = alloc_; \
} \
\
static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_ MEM_STAT_DECL) \
{ \
*vec_ = vec_o_reserve (*vec_, alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF) \
! PASS_MEM_STAT); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
*************** static inline TDEF *VEC_OP (TDEF,quick_p
*** 492,501 ****
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
! (VEC (TDEF) **vec_, const TDEF *obj_) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
--- 518,527 ----
} \
\
static inline TDEF *VEC_OP (TDEF,safe_push) \
! (VEC (TDEF) **vec_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
*************** static inline void VEC_OP (TDEF,pop)
*** 504,510 ****
(VEC (TDEF) *vec_) \
{ \
VEC_ASSERT (vec_->num, "pop", TDEF); \
! vec_->vec[--vec_->num]; \
} \
\
static inline TDEF *VEC_OP (TDEF,replace) \
--- 530,543 ----
(VEC (TDEF) *vec_) \
{ \
VEC_ASSERT (vec_->num, "pop", TDEF); \
! --vec_->num; \
! } \
! \
! static inline void VEC_OP (TDEF,truncate) \
! (VEC (TDEF) *vec_, size_t size_) \
! { \
! VEC_ASSERT (vec_->num >= size_, "truncate", TDEF); \
! vec_->num = size_; \
} \
\
static inline TDEF *VEC_OP (TDEF,replace) \
*************** static inline TDEF *VEC_OP (TDEF,quick_i
*** 536,545 ****
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
! (VEC (TDEF) **vec_, size_t ix_, const TDEF *obj_) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
--- 569,578 ----
} \
\
static inline TDEF *VEC_OP (TDEF,safe_insert) \
! (VEC (TDEF) **vec_, size_t ix_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
Index: vec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/vec.c,v
retrieving revision 2.1
diff -c -3 -p -r2.1 vec.c
*** vec.c 28 Jun 2004 10:30:21 -0000 2.1
--- vec.c 6 Jul 2004 13:41:20 -0000
*************** struct vec_prefix
*** 39,48 ****
exponentially. VEC can be NULL, to create a new vector. */
void *
! vec_p_reserve (void *vec, size_t reserve)
{
return vec_o_reserve (vec, reserve,
! offsetof (struct vec_prefix, vec), sizeof (void *));
}
/* Ensure there are at least RESERVE free slots in VEC, if RESERVE !=
--- 39,49 ----
exponentially. VEC can be NULL, to create a new vector. */
void *
! vec_p_reserve (void *vec, size_t reserve MEM_STAT_DECL)
{
return vec_o_reserve (vec, reserve,
! offsetof (struct vec_prefix, vec), sizeof (void *)
! PASS_MEM_STAT);
}
/* Ensure there are at least RESERVE free slots in VEC, if RESERVE !=
*************** vec_p_reserve (void *vec, size_t reserve
*** 52,58 ****
consistes of ELT_SIZE sized elements. */
void *
! vec_o_reserve (void *vec, size_t reserve, size_t vec_offset, size_t elt_size)
{
struct vec_prefix *pfx = vec;
size_t alloc;
--- 53,60 ----
consistes of ELT_SIZE sized elements. */
void *
! vec_o_reserve (void *vec, size_t reserve, size_t vec_offset, size_t elt_size
! MEM_STAT_DECL)
{
struct vec_prefix *pfx = vec;
size_t alloc;
*************** vec_o_reserve (void *vec, size_t reserve
*** 64,70 ****
if (!pfx || pfx->alloc < alloc)
{
! vec = ggc_realloc (vec, vec_offset + alloc * elt_size);
((struct vec_prefix *)vec)->alloc = alloc;
if (!pfx)
((struct vec_prefix *)vec)->num = 0;
--- 66,73 ----
if (!pfx || pfx->alloc < alloc)
{
! vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size
! PASS_MEM_STAT);
((struct vec_prefix *)vec)->alloc = alloc;
if (!pfx)
((struct vec_prefix *)vec)->num = 0;
*************** vec_o_reserve (void *vec, size_t reserve
*** 73,95 ****
return vec;
}
- /* Allocate a structure which contains a vector as a trailing element.
- The vector is at STRUCT_OFFSET offset within the struct and the
- vector's array is at VEC_OFFSET offset within the vector. */
-
- void *
- vec_embedded_alloc (size_t struct_offset, size_t vec_offset,
- size_t elt_size, size_t reserve)
- {
- void *ptr = ggc_alloc (struct_offset + vec_offset + elt_size * reserve);
- struct vec_prefix *pfx = (struct vec_prefix *)((char *)ptr + struct_offset);
-
- pfx->num = 0;
- pfx->alloc = reserve;
-
- return ptr;
- }
-
#if ENABLE_CHECKING
/* Issue a vector domain error, and then fall over. */
--- 76,81 ----