[Patch] - remove duplicated hash function (beginner project)

["Christophe Jaillet" <christophe dot jaillet at wanadoo dot fr>]

Hi,

in the beginner project of the gcc web site, one is about removing
duplicated algorithms. This post is a try to remove one about hash function.

In file gcc/scan.c, there is a function called 'hashstr()' that hashes a
string in the same way as 'htab_hash_string()' from libiberty.

The only differences are that 'hashstr()' :
    - can be passed a length if the hash is not concerning the whole string
    - add the string length in the computation of the hash value.

Looking a bit deeper, we can see that :
    1) 'hashstr()' is only used in gen-protos.c and fix-header.c. In nearly
all cases, then length passed to the function is the exact length of the
string, so the whole string is hashed. The only execption is
'inrecognized_function()' where the length is given by the NODE_LEN macro
but as far as I have investigated libcpp token, I think that it also retrun
the length of the string.
        --> so using 'htab_hash_string' should give the same result

    2) adding the length of the string to the computation should also not be
an issue.

So, I thing that it is safe to remove this redundant hash function from
scan.c and use the on from libierty instead.

I tried to bootstrapped the compiler with the following patch but as no
occurence of neither gen-protos.c nor fix-header.c where in the output, I
consider that the proposed patch is *UNTESTED*.

Hoping someone can confirm this and test it as I'm not sure how to do it the
right way.


CJ

----------------------------------------------

2006-01-28  Christophe Jaillet  <christophe.jaillet@wanadoo.fr>

* gen-protos.c: include "hashtab.h".
(add_hash): use htab_hash_string instead of hashstr and reorder code.
* scan.c (hashstr): remove function ...
* scan.h (hashstr): ... and definition.
* fix-header.c: include "hashtab.h".
(lookup_std_proto): use htab_hash_string instead of hashstr
* Makefile.in: gen-protos.c and fix-header.c depends on hashtab.h now

Index: gcc/gen-protos.c
===================================================================
--- gcc/gen-protos.c (révision 110273)
+++ gcc/gen-protos.c (copie de travail)
@@ -22,6 +22,7 @@
 #include "tm.h"
 #include "scan.h"
 #include "errors.h"
+#include "hashtab.h"

 int verbose = 0;

@@ -36,13 +37,13 @@
 static void
 add_hash (const char *fname)
 {
-  int i, i0;
+  hashval_t i, i0;

   /* NOTE:  If you edit this, also edit lookup_std_proto in fix-header.c !!
*/
-  i = hashstr (fname, strlen (fname)) % HASH_SIZE;
-  i0 = i;
+  i = htab_hash_string (fname) % HASH_SIZE;
   if (hash_tab[i] != 0)
     {
+      i0 = i;
       collisions++;
       for (;;)
  {
Index: gcc/scan.c
===================================================================
--- gcc/scan.c (révision 110273)
+++ gcc/scan.c (copie de travail)
@@ -225,16 +225,3 @@
   *s->ptr = 0;
   return c;
 }
-
-unsigned int
-hashstr (const char *str, unsigned int len)
-{
-  unsigned int n = len;
-  unsigned int r = 0;
-  const unsigned char *s = (const unsigned char *) str;
-
-  do
-    r = r * 67 + (*s++ - 113);
-  while (--n);
-  return r + len;
-}
Index: gcc/scan.h
===================================================================
--- gcc/scan.h (révision 110273)
+++ gcc/scan.h (copie de travail)
@@ -54,7 +54,6 @@
 extern void recognized_function (const struct cpp_token *,
      unsigned int, int, int);
 extern void recognized_extern (const struct cpp_token *);
-extern unsigned int hashstr (const char *, unsigned int);

 extern int scan_decls (struct cpp_reader *, int, char **);

Index: gcc/fix-header.c
===================================================================
--- gcc/fix-header.c (révision 110273)
+++ gcc/fix-header.c (copie de travail)
@@ -80,6 +80,7 @@
 #include "cpplib.h"
 #include "c-incpath.h"
 #include "errors.h"
+#include "hashtab.h"

 #ifdef TARGET_EXTRA_INCLUDES
 void TARGET_EXTRA_INCLUDES (const char *sysroot ATTRIBUTE_UNUSED,
@@ -395,8 +396,8 @@
 static struct fn_decl *
 lookup_std_proto (const char *name, int name_length)
 {
-  int i = hashstr (name, name_length) % HASH_SIZE;
-  int i0 = i;
+  hashval_t i = htab_hash_string (name) % HASH_SIZE;
+  hashval_t i0 = i;
   for (;;)
     {
       struct fn_decl *fn;
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (révision 110273)
+++ gcc/Makefile.in (copie de travail)
@@ -3217,7 +3217,7 @@
    $(GEN_PROTOS_OBJS) $(BUILD_LIBS)

 build/gen-protos.o: gen-protos.c scan.h $(BCONFIG_H) $(SYSTEM_H)
coretypes.h \
-  $(GTM_H) errors.h
+  $(GTM_H) $(HASHTAB_H) errors.h

 build/scan.o: scan.c scan.h $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(GTM_H)

@@ -3242,7 +3242,8 @@
   build/scan.o $(BUILD_ERRORS) $(LIBS)

 build/fix-header.o: fix-header.c $(OBSTACK_H) scan.h errors.h \
- xsys-protos.h $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(GTM_H) $(CPPLIB_H)
+ xsys-protos.h $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(GTM_H) $(CPPLIB_H) \
+ $(HASHTAB_H)

 build/scan-decls.o: scan-decls.c scan.h $(CPPLIB_H) $(BCONFIG_H)
$(SYSTEM_H) coretypes.h $(GTM_H)