Hi. "ping" [for the libiberty part]
[The gdb part needs to be updated due to recent changes there, but I'm
going to wait until the libiberty part is approved.]
On Mon, Jul 9, 2012 at 11:10 AM, Doug Evans <d...@google.com> wrote:
> 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;
> }
