[RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

[Blech, sent to right list this time.  Already sent to gcc-patches@.]

Hi.

filename_seen in gdb does a linear search, this patch changes it
to use a hash table.

Ok to check in?

I couldn't think of a good reason to put filename_hash,filename_eq in gdb,
and I like placing them close to where hashtab.c and filename_cmp are defined.
I also couldn't think of a sufficient reason to put them in a file by
themselves.  Ergo adding them to filename_cmp.c, filenames.h.
[It's possible there's a program that uses filename_cmp and already
defines functions with the same names (thus this will introduce a build
failure), but that's always a risk.  I couldn't find any in gdb,binutils,gcc.
Technically speaking, it's also possible that adding the #include "hashtab.h"
to filenames.h could introduce a build failure (e.g., some file has a static
symbol that collides with one used in hashtab.h).  I'm hoping that's more of
a theoretical concern.]

2012-07-09  Doug Evans  <dje@google.com>

	include/
	* filenames.h: #include "hashtab.h".
	(filename_hash, filename_eq): Declare.

	libiberty/
	* filename_cmp.c (filename_hash, filename_eq): New functions.

	gdb/
	* symtab.c (filename_seen): Rewrite to use a hash table.

Index: include/filenames.h
===================================================================
RCS file: /cvs/src/src/include/filenames.h,v
retrieving revision 1.10
diff -u -p -r1.10 filenames.h
--- include/filenames.h	1 Jul 2011 18:24:38 -0000	1.10
+++ include/filenames.h	9 Jul 2012 17:24:53 -0000
@@ -26,6 +26,8 @@ Foundation, Inc., 51 Franklin Street - F
 #ifndef FILENAMES_H
 #define FILENAMES_H
 
+#include "hashtab.h" /* for hashval_t */
+
 #ifdef __cplusplus
 extern "C" {
 #endif
@@ -84,6 +86,10 @@ extern int filename_cmp (const char *s1,
 extern int filename_ncmp (const char *s1, const char *s2,
 			  size_t n);
 
+extern hashval_t filename_hash (const void *s);
+
+extern int filename_eq (const void *s1, const void *s2);
+
 #ifdef __cplusplus
 }
 #endif
Index: libiberty/filename_cmp.c
===================================================================
RCS file: /cvs/src/src/libiberty/filename_cmp.c,v
retrieving revision 1.6
diff -u -p -r1.6 filename_cmp.c
--- libiberty/filename_cmp.c	1 Jul 2011 18:24:39 -0000	1.6
+++ libiberty/filename_cmp.c	9 Jul 2012 17:24:53 -0000
@@ -141,3 +141,52 @@ filename_ncmp (const char *s1, const cha
   return 0;
 #endif
 }
+
+/*
+
+@deftypefn Extension hashval_t filename_hash (const void *@var{s})
+
+Return the hash value for file name @var{s} that will be compared
+using filename_cmp.
+This function is for use with hashtab.c hash tables.
+
+@end deftypefn
+
+*/
+
+hashval_t
+filename_hash (const void *s)
+{
+  /* The cast is for -Wc++-compat.  */
+  const unsigned char *str = (const unsigned char *) s;
+  hashval_t r = 0;
+  unsigned char c;
+
+  while ((c = *str++) != 0)
+    {
+      if (c == '\\')
+	c = '/';
+      c = TOLOWER (c);
+      r = r * 67 + c - 113;
+    }
+
+  return r;
+}
+
+/*
+
+@deftypefn Extension int filename_eq (const void *@var{s1}, const void *@var{s2})
+
+Return non-zero if file names @var{s1} and @var{s2} are equivalent.
+This function is for use with hashtab.c hash tables.
+
+@end deftypefn
+
+*/
+
+int
+filename_eq (const void *s1, const void *s2)
+{
+  /* The casts are for -Wc++-compat.  */
+  return filename_cmp ((const char *) s1, (const char *) s2) == 0;
+}
Index: gdb/symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.316
diff -u -p -r1.316 symtab.c
--- gdb/symtab.c	29 Jun 2012 22:46:45 -0000	1.316
+++ gdb/symtab.c	9 Jul 2012 17:24:54 -0000
@@ -3108,44 +3108,34 @@ operator_chars (char *p, char **end)
 /* If FILE is not already in the table of files, return zero;
    otherwise return non-zero.  Optionally add FILE to the table if ADD
    is non-zero.  If *FIRST is non-zero, forget the old table
-   contents.  */
+   contents.
+
+   NOTE: We don't manage space for FILE, we assume FILE lives as long
+   as the caller needs.  */
 
 static int
 filename_seen (const char *file, int add, int *first)
 {
   /* Table of files seen so far.  */
-  static const char **tab = NULL;
-  /* Allocated size of tab in elements.
-     Start with one 256-byte block (when using GNU malloc.c).
-     24 is the malloc overhead when range checking is in effect.  */
-  static int tab_alloc_size = (256 - 24) / sizeof (char *);
-  /* Current size of tab in elements.  */
-  static int tab_cur_size;
-  const char **p;
+  static htab_t files_seen;
+  void **slot;
 
   if (*first)
     {
-      if (tab == NULL)
-	tab = (const char **) xmalloc (tab_alloc_size * sizeof (*tab));
-      tab_cur_size = 0;
+      if (files_seen != NULL)
+	htab_delete (files_seen);
+      files_seen = htab_create_alloc (10, filename_hash, filename_eq,
+				      NULL, xcalloc, xfree);
     }
 
   /* Is FILE in tab?  */
-  for (p = tab; p < tab + tab_cur_size; p++)
-    if (filename_cmp (*p, file) == 0)
-      return 1;
+  slot = htab_find_slot (files_seen, file, add ? INSERT : NO_INSERT);
+  if (*slot != NULL)
+    return 1;
 
   /* No; maybe add it to tab.  */
   if (add)
-    {
-      if (tab_cur_size == tab_alloc_size)
-	{
-	  tab_alloc_size *= 2;
-	  tab = (const char **) xrealloc ((char *) tab,
-					  tab_alloc_size * sizeof (*tab));
-	}
-      tab[tab_cur_size++] = file;
-    }
+    *slot = (char *) file;
 
   return 0;
 }