This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Type safe vector API
- 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 au dot ibm dot com>
- Date: Mon, 28 Jun 2004 11:37:32 +0100
- Subject: Re: Type safe vector API
- Organization: CodeSourcery LLC
- References: <40D980E9.1050801@codesourcery.com> <40DBD1FC.1040503@codesourcery.com>
Mark Mitchell wrote:
If nobody objects in another 24 hours, please go ahead and check this
in. Hopefully the tree-ssa folks can make use of this for their
purposes as well.
This is the patch I've installed. It adds an example use and a new
VEC_last (T,V) accessor to get the final element.
nathan
--
Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC
nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk
2004-06-28 Nathan Sidwell <nathan@codesourcery.com>
* vec.h, vec.c: New, type safe vector API.
* Makefile.in (OBJS-common): Add vec.o.
(vec.o): New target.
(gengtype-lex.o): Depend on vec.h.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1306
diff -c -3 -p -r1.1306 Makefile.in
*** Makefile.in 23 Jun 2004 20:12:41 -0000 1.1306
--- Makefile.in 25 Jun 2004 10:44:52 -0000
*************** OBJS-common = \
*** 914,920 ****
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o \
targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o \
! varasm.o varray.o version.o vmsdbgout.o xcoffout.o alloc-pool.o \
et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o \
rtl-profile.o tree-profile.o rtlhooks.o cfgexpand.o
--- 914,920 ----
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
simplify-rtx.o sreal.o stmt.o stor-layout.o stringpool.o \
targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o unroll.o \
! varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o \
et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o \
rtl-profile.o tree-profile.o rtlhooks.o cfgexpand.o
*************** global.o : global.c $(CONFIG_H) $(SYSTEM
*** 1990,1995 ****
--- 1990,1996 ----
toplev.h $(TM_P_H)
varray.o : varray.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) varray.h $(GGC_H) errors.h \
$(HASHTAB_H)
+ vec.o : vec.c $(CONFIG_H) coretypes.h vec.h ggc.h errors.h
ra.o : ra.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TM_P_H) insn-config.h \
$(RECOG_H) $(INTEGRATE_H) function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h \
$(BASIC_BLOCK_H) $(DF_H) $(EXPR_H) output.h toplev.h $(FLAGS_H) reload.h $(RA_H)
*************** gengtype.o : gengtype.c gengtype.h $(BCO
*** 2515,2521 ****
real.h $(RTL_BASE_H) gtyp-gen.h
gengtype-lex.o : gengtype-lex.c gengtype.h gengtype-yacc.h \
! $(BCONFIG_H) coretypes.h $(GTM_H) $(SYSTEM_H)
$(CC_FOR_BUILD) -c $(BUILD_CFLAGS) $(BUILD_CPPFLAGS) $(INCLUDES) \
$< $(OUTPUT_OPTION)
--- 2516,2522 ----
real.h $(RTL_BASE_H) gtyp-gen.h
gengtype-lex.o : gengtype-lex.c gengtype.h gengtype-yacc.h \
! $(BCONFIG_H) coretypes.h $(GTM_H) $(SYSTEM_H) vec.h
$(CC_FOR_BUILD) -c $(BUILD_CFLAGS) $(BUILD_CPPFLAGS) $(INCLUDES) \
$< $(OUTPUT_OPTION)
Index: gengtype-lex.l
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gengtype-lex.l,v
retrieving revision 1.21
diff -c -3 -p -r1.21 gengtype-lex.l
*** gengtype-lex.l 31 May 2004 19:49:50 -0000 1.21
--- gengtype-lex.l 25 Jun 2004 10:44:53 -0000
*************** Software Foundation, 59 Temple Place - S
*** 30,35 ****
--- 30,40 ----
#include "gengtype.h"
#include "gengtype-yacc.h"
+ #define YY_INPUT(BUF,RESULT,SIZE) ((RESULT) = macro_input (BUF,SIZE))
+
+ static unsigned macro_input (char *buffer, unsigned);
+ static void push_macro_expansion (const char *, unsigned,
+ const char *, unsigned);
static void update_lineno (const char *l, size_t len);
struct fileloc lexer_line;
*************** ITYPE {IWORD}({WS}{IWORD})*
*** 218,223 ****
--- 223,257 ----
return ENT_YACCUNION;
}
+ ^"DEF_VEC_"[[:alnum:]_]*{WS}?"("{WS}?{ID}{WS}?")" {
+ char *macro, *arg;
+ unsigned macro_len, arg_len;
+ char *ptr = yytext;
+ type_p t;
+
+ /* Locate the macro and argument strings. */
+ macro = ptr;
+ while (*ptr != '(' && !ISSPACE (*ptr))
+ ptr++;
+ macro_len = ptr - macro;
+ while (*ptr == '(' || ISSPACE (*ptr))
+ ptr++;
+ arg = ptr;
+ while (*ptr != ')' && !ISSPACE (*ptr))
+ ptr++;
+ arg_len = ptr - arg;
+
+ /* Push the macro for later expansion. */
+ push_macro_expansion (macro, macro_len, arg, arg_len);
+
+ /* Create the struct and typedef. */
+ ptr = xmemdup ("VEC_", 4, 4 + arg_len + 1);
+ memcpy (&ptr[4], arg, arg_len);
+ ptr[4 + arg_len] = 0;
+ t = find_structure (ptr, 0);
+ do_typedef (ptr, t, &lexer_line);
+ }
+
<in_struct>{
"/*" { BEGIN(in_struct_comment); }
*************** ITYPE {IWORD}({WS}{IWORD})*
*** 229,235 ****
{WS} { update_lineno (yytext, yyleng); }
"const"/[^[:alnum:]_] /* don't care */
-
"GTY"/[^[:alnum:]_] { return GTY_TOKEN; }
"union"/[^[:alnum:]_] { return UNION; }
"struct"/[^[:alnum:]_] { return STRUCT; }
--- 263,268 ----
*************** ITYPE {IWORD}({WS}{IWORD})*
*** 254,259 ****
--- 287,314 ----
return SCALAR;
}
+ "VEC"{WS}?"("{WS}?{ID}{WS}?")" {
+ char *macro, *arg;
+ unsigned macro_len, arg_len;
+ char *ptr = yytext;
+
+ macro = ptr;
+ while (*ptr != '(' && !ISSPACE (*ptr))
+ ptr++;
+ macro_len = ptr - macro;
+ while (*ptr == '(' || ISSPACE (*ptr))
+ ptr++;
+ arg = ptr;
+ while (*ptr != ')' && !ISSPACE (*ptr))
+ ptr++;
+ arg_len = ptr - arg;
+ ptr = xmemdup (macro, macro_len, macro_len + arg_len + 2);
+ ptr[macro_len] = '_';
+ memcpy (&ptr[macro_len+1], arg, arg_len);
+ yylval.s = ptr;
+ return ID;
+ }
+
{ID}/[^[:alnum:]_] {
yylval.s = xmemdup (yytext, yyleng, yyleng+1);
return ID;
*************** ITYPE {IWORD}({WS}{IWORD})*
*** 340,345 ****
--- 395,487 ----
%%
+ /* Deal with the expansion caused by the DEF_VEC_x macros. */
+
+ typedef struct macro
+ {
+ const char *name;
+ const char *expansion;
+ struct macro *next;
+ } macro_t;
+
+ static const macro_t macro_defs[] =
+ {
+ #define IN_GENGTYPE 1
+ #include "vec.h"
+ {NULL, NULL, NULL}
+ };
+
+ /* Chain of macro expansions to do at end of scanning. */
+ static macro_t *macro_expns;
+
+ /* Push macro NAME (NAME_LEN) with argument ARG (ARG_LEN) onto the
+ expansion queue. We ensure NAME is known at this point. */
+
+ static void
+ push_macro_expansion (const char *name, unsigned name_len,
+ const char *arg, unsigned arg_len)
+ {
+ unsigned ix;
+
+ for (ix = 0; macro_defs[ix].name; ix++)
+ if (strlen (macro_defs[ix].name) == name_len
+ && !memcmp (name, macro_defs[ix].name, name_len))
+ {
+ macro_t *expansion = xmalloc (sizeof (*expansion));
+
+ expansion->next = macro_expns;
+ expansion->name = xmemdup (arg, arg_len, arg_len+1);
+ expansion->expansion = macro_defs[ix].expansion;
+ macro_expns = expansion;
+ return;
+ }
+ error_at_line (&lexer_line, "unrecognized macro `%.*s(%.*s)'",
+ name_len, name, arg_len, arg);
+ }
+
+ /* Attempt to read some input. Use fread until we're at the end of
+ file. At end of file expand the next queued macro. We presume the
+ buffer is large enough for the entire expansion. */
+
+ static unsigned
+ macro_input (char *buffer, unsigned size)
+ {
+ unsigned result;
+
+ result = fread (buffer, 1, size, yyin);
+ if (result)
+ /*NOP*/;
+ else if (ferror (yyin))
+ YY_FATAL_ERROR ("read of source file failed");
+ else if (macro_expns)
+ {
+ const char *expn;
+ unsigned len;
+
+ for (expn = macro_expns->expansion; *expn; expn++)
+ {
+ if (*expn == '#')
+ {
+ if (buffer[result-1] == ' ' && buffer[result-2] == '_')
+ result--;
+ len = strlen (macro_expns->name);
+ memcpy (&buffer[result], macro_expns->name, len);
+ result += len;
+ }
+ else
+ {
+ buffer[result++] = *expn;
+ if (*expn == ';' || *expn == '{')
+ buffer[result++] = '\n';
+ }
+ }
+ if (result > size)
+ YY_FATAL_ERROR ("buffer too small to expand macro");
+ macro_expns = macro_expns->next;
+ }
+ return result;
+ }
+
void
yyerror (const char *s)
{
Index: vec.c
===================================================================
RCS file: vec.c
diff -N vec.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- vec.c 25 Jun 2004 10:44:53 -0000
***************
*** 0 ****
--- 1,104 ----
+ /* Vector API for GNU compiler.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+ Contributed by Nathan Sidwell <nathan@codesourcery.com>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "ggc.h"
+ #include "vec.h"
+ #include "errors.h"
+ #include "coretypes.h"
+ #include "tree.h"
+
+ struct vec_prefix
+ {
+ size_t num;
+ size_t alloc;
+ void *vec[1];
+ };
+
+ /* Ensure there are at least RESERVE free slots in VEC, if RESERVE !=
+ ~0u. If RESERVE == ~0u increase the current allocation
+ 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 !=
+ ~0u. If RESERVE == ~0u, increase the current allocation
+ exponentially. VEC can be NULL, in which case a new vector is
+ created. The vector's trailing array is at VEC_OFFSET offset and
+ 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;
+
+ if (reserve + 1)
+ alloc = (pfx ? pfx->num : 0) + reserve;
+ else
+ alloc = pfx ? pfx->alloc * 2 : 4;
+
+ 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;
+ }
+
+ 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. */
+
+ void
+ vec_assert_fail (const char *op, const char *struct_name,
+ const char *file, size_t line, const char *function)
+ {
+ internal_error ("vector %s %s domain error, in %s at %s:%u",
+ struct_name, op, function, function,
+ trim_filename (file), line);
+ }
+ #endif
Index: vec.h
===================================================================
RCS file: vec.h
diff -N vec.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- vec.h 25 Jun 2004 17:26:59 -0000
***************
*** 0 ****
--- 1,567 ----
+ /* Vector API for GNU compiler.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+ Contributed by Nathan Sidwell <nathan@codesourcery.com>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #ifndef GCC_VEC_H
+ #define GCC_VEC_H
+
+ /* 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 behaviour of objects and of pointers to
+ objects, there are two flavours. One to deal with a vector of
+ pointers to objects, and one to deal with a vector of objects
+ themselves. Both of these 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. Therefore, when using a vector of pointers, the
+ objects pointed to must be long lived, but when dealing with a
+ vector of objects, the source objects need not be.
+
+ 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_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
+ there is sufficient allocated space for the operation to succeed
+ (it aborts if there is not). The latter will reallocate the
+ vector, if needed. Reallocation causes an exponential increase in
+ vector size. If you know you will be adding N elements, it would
+ be more efficient to use the reserve operation before adding the
+ 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
+ 'unordered_remove'. The latter function copies the end element
+ into the removed slot, rather than invoke a memmove operation.
+
+ Vector types are defined using a DEF_VEC_x(TYPEDEF) macro, and
+ variables of vector type are declared using a VEC(TYPEDEF)
+ macro. The 'x' letter indicates whether TYPEDEF is a pointer (P) or
+ object (O) type.
+
+ An example of their use would be,
+
+ DEF_VEC_P(tree); // define a vector of tree pointers. This must
+ // appear at file scope.
+
+ struct my_struct {
+ VEC(tree) *v; // A (pointer to) a vector of tree pointers.
+ };
+
+ struct my_struct *s;
+
+ if (VEC_length(tree,s)) { we have some contents }
+ VEC_safe_push(tree,s,decl); // append some decl onto the end
+ for (ix = 0; (t = VEC_iterate(tree,s,ix)); ix++)
+ { do something with t }
+
+ */
+
+ /* 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, TDEF is the typedef of the vector
+ elements. Some of these macros pass the vector, V, by reference
+ (by taking its address), this is noted in the descriptions. */
+
+ /* Length of vector
+ size_t VEC_T_length(const VEC(T) *v);
+
+ Return the number of active elements in V. V can be NULL, in which
+ case zero is returned. */
+ #define VEC_length(TDEF,V) (VEC_OP(TDEF,length)(V))
+
+ /* Get the final element of the vector.
+ T VEC_T_last(VEC(T) *v); // Pointer
+ T *VEC_T_last(VEC(T) *v); // Object
+
+ Return the final element. If V is empty, abort. */
+ #define VEC_last(TDEF,V) (VEC_OP(TDEF,last)(V))
+
+ /* Index into vector
+ T VEC_T_index(VEC(T) *v, size_t ix); // Pointer
+ T *VEC_T_index(VEC(T) *v, size_t ix); // Object
+
+ Return the IX'th element. If IX is outside the domain of V,
+ abort. */
+ #define VEC_index(TDEF,V,I) (VEC_OP(TDEF,index)(V,I))
+
+ /* Iterate over vector
+ T VEC_T_index(VEC(T) *v, size_t ix); // Pointer
+ T *VEC_T_index(VEC(T) *v, size_t ix); // Object
+
+ Return the IX'th element or NULL. Use this to iterate over the
+ elements of a vector as follows,
+
+ for (ix = 0; (ptr = VEC_iterate(T,v,ix)); ix++)
+ continue; */
+ #define VEC_iterate(TDEF,V,I) (VEC_OP(TDEF,iterate)(V,I))
+
+ /* Allocate new vector.
+ 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
+ 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. Aborts if there is
+ insufficient space in the vector. */
+ #define VEC_quick_push(TDEF,V,O) (VEC_OP(TDEF,quick_push)(V,O))
+
+ /* Push object with reallocation
+ T *VEC_T_safe_push (VEC(T) *&v, T obj); // Pointer
+ T *VEC_T_safe_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. 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
+ void VEC_T_pop (VEC(T) *v); // Object
+
+ Pop the last element off the end. Returns the element popped, for
+ pointer vectors. */
+ #define VEC_pop(TDEF,V) (VEC_OP(TDEF,pop)(V))
+
+ /* 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
+
+ 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(TDEF,V,I,O) (VEC_OP(TDEF,replace)(V,I,O))
+
+ /* Insert object with no reallocation
+ T *VEC_T_quick_insert (VEC(T) *v, size_t ix, T val); // Pointer
+ T *VEC_T_quick_insert (VEC(T) *v, size_t 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. Aborts if there is insufficient space. */
+ #define VEC_quick_insert(TDEF,V,I,O) (VEC_OP(TDEF,quick_insert)(V,I,O))
+
+ /* Insert object with reallocation
+ T *VEC_T_safe_insert (VEC(T) *&v, size_t ix, T val); // Pointer
+ T *VEC_T_safe_insert (VEC(T) *&v, size_t 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. 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
+ void VEC_T_ordered_remove (VEC(T) *v, size_t ix); // Object
+
+ Remove an element from the IXth position of V. Ordering of
+ remaining elements is preserverd. For pointer vectors returns the
+ removed object. This is an O(N) operation due to a memmove. */
+ #define VEC_ordered_remove(TDEF,V,I) (VEC_OP(TDEF,ordered_remove)(V,I))
+
+ /* Remove element destroying order
+ T VEC_T_unordered_remove (VEC(T) *v, size_t ix); // Pointer
+ void VEC_T_unordered_remove (VEC(T) *v, size_t 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. */
+ #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 *,
+ const char *, size_t, const char *)
+ ATTRIBUTE_NORETURN;
+ #define VEC_ASSERT_FAIL(OP,VEC) \
+ vec_assert_fail (OP,#VEC,__FILE__,__LINE__,__FUNCTION__)
+
+ #define VEC_ASSERT(EXPR,OP,TDEF) \
+ (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(TDEF)), 0))
+ #else
+ #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 /* IN_GENGTYPE */
+ #define VEC(TDEF) VEC_ TDEF
+ #define VEC_STRINGIFY(X) VEC_STRINGIFY_(X)
+ #define VEC_STRINGIFY_(X) #X
+ #undef GTY
+ #endif /* IN_GENGTYPE */
+
+ #define VEC_TDEF(TDEF) \
+ typedef struct VEC (TDEF) GTY(()) \
+ { \
+ size_t num; \
+ size_t alloc; \
+ TDEF GTY ((length ("%h.num"))) vec[1]; \
+ } VEC (TDEF)
+
+ /* Vector of pointer to object. */
+ #if IN_GENGTYPE
+ {"DEF_VEC_P", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
+ #else
+
+ #define DEF_VEC_P(TDEF) \
+ VEC_TDEF (TDEF); \
+ \
+ static inline size_t 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_ASSERT (vec_ && vec_->num, "last", TDEF); \
+ \
+ return vec_->vec[vec->num - 1]; \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,index) \
+ (const VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
+ \
+ return vec_->vec[ix_]; \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,iterate) \
+ (const VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ 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) \
+ (VEC (TDEF) *vec_, TDEF obj_) \
+ { \
+ 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_) \
+ { \
+ if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
+ VEC_OP (TDEF,reserve) (vec_, ~0u); \
+ \
+ return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,pop) \
+ (VEC (TDEF) *vec_) \
+ { \
+ TDEF obj_; \
+ \
+ VEC_ASSERT (vec_->num, "pop", TDEF); \
+ obj_ = vec_->vec[--vec_->num]; \
+ \
+ return obj_; \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,replace) \
+ (VEC (TDEF) *vec_, size_t ix_, TDEF obj_) \
+ { \
+ TDEF old_obj_; \
+ \
+ VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
+ old_obj_ = vec_->vec[ix_]; \
+ vec_->vec[ix_] = obj_; \
+ \
+ return old_obj_; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,quick_insert) \
+ (VEC (TDEF) *vec_, size_t ix_, TDEF obj_) \
+ { \
+ 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_); \
+ *slot_ = obj_; \
+ \
+ return slot_; \
+ } \
+ \
+ 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_, ~0u); \
+ \
+ return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,ordered_remove) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ TDEF *slot_; \
+ TDEF obj_; \
+ \
+ VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
+ slot_ = &vec_->vec[ix_]; \
+ obj_ = *slot_; \
+ memmove (slot_, slot_ + 1, --vec_->num - ix_); \
+ \
+ return obj_; \
+ } \
+ \
+ static inline TDEF VEC_OP (TDEF,unordered_remove) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ TDEF *slot_; \
+ TDEF obj_; \
+ \
+ VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
+ slot_ = &vec_->vec[ix_]; \
+ obj_ = *slot_; \
+ *slot_ = vec_->vec[--vec_->num]; \
+ \
+ return obj_; \
+ } \
+ \
+ struct vec_swallow_trailing_semi
+ #endif
+
+ /* Vector of object. */
+ #if IN_GENGTYPE
+ {"DEF_VEC_O", VEC_STRINGIFY (VEC_TDEF (#)) ";", NULL},
+ #else
+
+ #define DEF_VEC_O(TDEF) \
+ VEC_TDEF (TDEF); \
+ \
+ static inline size_t VEC_OP (TDEF,length) \
+ (const VEC (TDEF) *vec_) \
+ { \
+ return vec_ ? vec_->num : 0; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,last) \
+ (VEC (TDEF) *vec_) \
+ { \
+ VEC_ASSERT (vec_ && vec_->num, "last", TDEF); \
+ \
+ return &vec_->vec[vec_->num - 1]; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,index) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ VEC_ASSERT (vec_ && ix_ < vec_->num, "index", TDEF); \
+ \
+ return &vec_->vec[ix_]; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,iterate) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ return vec_ && ix_ < vec_->num ? &vec_->vec[ix_] : NULL; \
+ } \
+ \
+ 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) \
+ (VEC (TDEF) *vec_, const TDEF *obj_) \
+ { \
+ 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_) \
+ { \
+ if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
+ VEC_OP (TDEF,reserve) (vec_, ~0u); \
+ \
+ return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
+ } \
+ \
+ static inline void VEC_OP (TDEF,pop) \
+ (VEC (TDEF) *vec_) \
+ { \
+ VEC_ASSERT (vec_->num, "pop", TDEF); \
+ vec_->vec[--vec_->num]; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,replace) \
+ (VEC (TDEF) *vec_, size_t ix_, const TDEF *obj_) \
+ { \
+ TDEF *slot_; \
+ \
+ VEC_ASSERT (ix_ < vec_->num, "replace", TDEF); \
+ slot_ = &vec_->vec[ix_]; \
+ if (obj_) \
+ *slot_ = *obj_; \
+ \
+ return slot_; \
+ } \
+ \
+ static inline TDEF *VEC_OP (TDEF,quick_insert) \
+ (VEC (TDEF) *vec_, size_t ix_, const TDEF *obj_) \
+ { \
+ 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_); \
+ if (obj_) \
+ *slot_ = *obj_; \
+ \
+ return slot_; \
+ } \
+ \
+ 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_, ~0u); \
+ \
+ return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
+ } \
+ \
+ static inline void VEC_OP (TDEF,ordered_remove) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ TDEF *slot_; \
+ \
+ VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
+ slot_ = &vec_->vec[ix_]; \
+ memmove (slot_, slot_ + 1, --vec_->num - ix_); \
+ } \
+ \
+ static inline void VEC_OP (TDEF,unordered_remove) \
+ (VEC (TDEF) *vec_, size_t ix_) \
+ { \
+ VEC_ASSERT (ix_ < vec_->num, "remove", TDEF); \
+ vec_->vec[ix_] = vec_->vec[--vec_->num]; \
+ } \
+ \
+ struct vec_swallow_trailing_semi
+ #endif
+
+ #endif /* GCC_VEC_H */