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]

fix c/10675


Two quadratic operations when processing fields of a structure:

  (1) Use of chainon.  Fixed by building the list in reverse in
      the parser and then using nreverse.

  (2) Detection of duplicate field names is just nested for loops.
      Fixed by building a hash table of field names and looking 
      for collisions.

Testing still in progress, but it's pretty trivial...


r~


	* c-decl.c: Include hashtab.h.
	(detect_field_duplicates): New.
	(finish_struct): Use it.
	* c-parse.in (structsp_attr): Reverse component_decl_list.
	(component_decl_list, component_decl_list2): Don't use chainon.
	* Makefile.in (c-decl.o): Update.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1049
diff -c -p -d -u -r1.1049 Makefile.in
--- Makefile.in	5 May 2003 21:59:32 -0000	1.1049
+++ Makefile.in	9 May 2003 01:26:20 -0000
@@ -1258,10 +1258,10 @@ $(parsedir)/c-parse.y: c-parse.in
 c-incpath.o: c-incpath.c c-incpath.h $(CONFIG_H) $(SYSTEM_H) $(CPPLIB_H) \
 		intl.h prefix.h coretypes.h $(TM_H) cppdefault.h
 
-c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(RTL_H) \
-    $(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h $(EXPR_H) \
-    debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) c-pragma.h \
-    gt-c-decl.h cgraph.h
+c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
+    $(RTL_H) $(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h \
+    $(EXPR_H) debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) \
+    c-pragma.h gt-c-decl.h cgraph.h $(HASHTAB_H)
 c-typeck.o : c-typeck.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
     $(TARGET_H) flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h $(TM_P_H)
 c-lang.o : c-lang.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
Index: c-decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-decl.c,v
retrieving revision 1.386
diff -c -p -d -u -r1.386 c-decl.c
--- c-decl.c	8 May 2003 15:04:44 -0000	1.386
+++ c-decl.c	9 May 2003 01:26:20 -0000
@@ -49,6 +49,7 @@ Software Foundation, 59 Temple Place - S
 #include "c-common.h"
 #include "c-pragma.h"
 #include "cgraph.h"
+#include "hashtab.h"
 
 /* In grokdeclarator, distinguish syntactic contexts of declarators.  */
 enum decl_context
@@ -4883,6 +4884,63 @@ grokfield (filename, line, declarator, d
   return value;
 }
 
+/* Generate an error for any duplicate field names in FIELDLIST.  Munge
+   the list such that this does not present a problem later.  */
+
+static void
+detect_field_duplicates (tree fieldlist)
+{
+  tree x, y;
+  int timeout = 10;
+
+  /* First, see if there are more than "a few" fields.
+     This is trivially true if there are zero or one fields.  */
+  if (!fieldlist)
+    return;
+  x = TREE_CHAIN (fieldlist);
+  if (!x)
+    return;
+  do {
+    timeout--;
+    x = TREE_CHAIN (x);
+  } while (timeout > 0 && x);
+
+  /* If there were "few" fields, avoid the overhead of allocating
+     a hash table.  Instead just do the nested traversal thing.  */
+  if (timeout > 0)
+    {
+      for (x = TREE_CHAIN (fieldlist); x ; x = TREE_CHAIN (x))
+	if (DECL_NAME (x))
+	  {
+	    for (y = fieldlist; y != x; y = TREE_CHAIN (y))
+	      if (DECL_NAME (y) == DECL_NAME (x))
+		{
+		  error_with_decl (x, "duplicate member `%s'");
+		  DECL_NAME (x) = NULL_TREE;
+		}
+	  }
+    }
+  else
+    {
+      htab_t htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+      void **slot;
+
+      for (x = fieldlist; x ; x = TREE_CHAIN (x))
+	if ((y = DECL_NAME (x)) != 0)
+	  {
+	    slot = htab_find_slot (htab, y, INSERT);
+	    if (*slot)
+	      {
+		error_with_decl (x, "duplicate member `%s'");
+		DECL_NAME (x) = NULL_TREE;
+	      }
+	    *slot = y;
+	  }
+
+      htab_delete (htab);
+    }
+}
+
 /* Fill in the fields of a RECORD_TYPE or UNION_TYPE node, T.
    FIELDLIST is a chain of FIELD_DECL nodes for the fields.
    ATTRIBUTES are attributes to be applied to the structure.  */
@@ -5062,31 +5120,7 @@ finish_struct (t, fieldlist, attributes)
 	saw_named_field = 1;
     }
 
-  /* Delete all duplicate fields from the fieldlist */
-  for (x = fieldlist; x && TREE_CHAIN (x);)
-    /* Anonymous fields aren't duplicates.  */
-    if (DECL_NAME (TREE_CHAIN (x)) == 0)
-      x = TREE_CHAIN (x);
-    else
-      {
-	tree y = fieldlist;
-
-	while (1)
-	  {
-	    if (DECL_NAME (y) == DECL_NAME (TREE_CHAIN (x)))
-	      break;
-	    if (y == x)
-	      break;
-	    y = TREE_CHAIN (y);
-	  }
-	if (DECL_NAME (y) == DECL_NAME (TREE_CHAIN (x)))
-	  {
-	    error_with_decl (TREE_CHAIN (x), "duplicate member `%s'");
-	    TREE_CHAIN (x) = TREE_CHAIN (TREE_CHAIN (x));
-	  }
-	else
-	  x = TREE_CHAIN (x);
-      }
+  detect_field_duplicates (fieldlist);
 
   /* Now we have the nearly final fieldlist.  Record it,
      then lay out the structure or union (including the fields).  */
Index: c-parse.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-parse.in,v
retrieving revision 1.157
diff -c -p -d -u -r1.157 c-parse.in
--- c-parse.in	1 May 2003 16:13:27 -0000	1.157
+++ c-parse.in	9 May 2003 01:26:21 -0000
@@ -1759,18 +1759,20 @@ structsp_attr:
 		  /* Start scope of tag before parsing components.  */
 		}
 	  component_decl_list '}' maybe_attribute
-		{ $$ = finish_struct ($<ttype>4, $5, chainon ($1, $7)); }
+		{ $$ = finish_struct ($<ttype>4, nreverse ($5),
+				      chainon ($1, $7)); }
 	| struct_head '{' component_decl_list '}' maybe_attribute
 		{ $$ = finish_struct (start_struct (RECORD_TYPE, NULL_TREE),
-				      $3, chainon ($1, $5));
+				      nreverse ($3), chainon ($1, $5));
 		}
 	| union_head identifier '{'
 		{ $$ = start_struct (UNION_TYPE, $2); }
 	  component_decl_list '}' maybe_attribute
-		{ $$ = finish_struct ($<ttype>4, $5, chainon ($1, $7)); }
+		{ $$ = finish_struct ($<ttype>4, nreverse ($5),
+				      chainon ($1, $7)); }
 	| union_head '{' component_decl_list '}' maybe_attribute
 		{ $$ = finish_struct (start_struct (UNION_TYPE, NULL_TREE),
-				      $3, chainon ($1, $5));
+				      nreverse ($3), chainon ($1, $5));
 		}
 	| enum_head identifier '{'
 		{ $$ = start_enum ($2); }
@@ -1813,14 +1815,14 @@ component_decl_list:
 	  component_decl_list2
 		{ $$ = $1; }
 	| component_decl_list2 component_decl
-		{ $$ = chainon ($1, $2);
+		{ TREE_CHAIN ($2) = $1; $$ = $2;
 		  pedwarn ("no semicolon at end of struct or union"); }
 	;
 
 component_decl_list2:	/* empty */
 		{ $$ = NULL_TREE; }
 	| component_decl_list2 component_decl ';'
-		{ $$ = chainon ($1, $2); }
+		{ TREE_CHAIN ($2) = $1; $$ = $2; }
 	| component_decl_list2 ';'
 		{ if (pedantic)
 		    pedwarn ("extra semicolon in struct or union specified"); }
@@ -1831,7 +1833,7 @@ ifobjc
 		  tree interface = lookup_interface ($3);
 
 		  if (interface)
-		    $$ = get_class_ivars (interface);
+		    $$ = nreverse (get_class_ivars (interface));
 		  else
 		    {
 		      error ("cannot find interface declaration for `%s'",


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