This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Type safe vector API


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 */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]