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 <d...@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;
}
