From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21173 invoked by alias); 13 Jul 2012 18:52:21 -0000 Received: (qmail 21155 invoked by uid 22791); 13 Jul 2012 18:52:20 -0000 X-SWARE-Spam-Status: No, hits=-5.5 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-vb0-f41.google.com (HELO mail-vb0-f41.google.com) (209.85.212.41) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 13 Jul 2012 18:52:07 +0000 Received: by vbkv13 with SMTP id v13so3052794vbk.0 for ; Fri, 13 Jul 2012 11:52:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:x-system-of-record:x-gm-message-state; bh=34zSyFaAalvwbZKwZrlKh2OYyfz6eBJhFPwlk9pUTQU=; b=W/2rG/5myDdQg+RUH0LI1CMoyeh0PTU0Vi3LEqxBBgZCCqeExluDicKqeK/XbXONUE weaHTQ4qeP6GC4ht48VyS0nKtHjtzPdbpzWqDm0MDO4Ni2fhxXtHOe/7+iCc4QLCSUuN OtzPkn3V2gdW+sCS6AGxP5auaBr6+l03Dtn77pnC/huFciTKGIvjRxkUEu8M8FpOjYmQ eahdyMTuWOtCLLG/vHkoMtNEtWMQMDra7lzRqRtsBuPIB1vqDVE/lzaqH23L3O0nPshW SqjyYXHQgrIC4twAbwAw8dnE+3aJB4KhJadS75bl43qCLqHf2DjwvGEbKDzE3HATiyMq iERw== Received: by 10.220.225.194 with SMTP id it2mr1111896vcb.32.1342205526690; Fri, 13 Jul 2012 11:52:06 -0700 (PDT) MIME-Version: 1.0 Received: by 10.220.225.194 with SMTP id it2mr1111880vcb.32.1342205526220; Fri, 13 Jul 2012 11:52:06 -0700 (PDT) Received: by 10.52.157.4 with HTTP; Fri, 13 Jul 2012 11:52:06 -0700 (PDT) In-Reply-To: <20120709181015.2FCA41E13A1@ruffy2.mtv.corp.google.com> References: <20120709181015.2FCA41E13A1@ruffy2.mtv.corp.google.com> Date: Fri, 13 Jul 2012 18:52:00 -0000 Message-ID: Subject: Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb. From: Doug Evans To: gcc-patches@gcc.gnu.org Cc: gdb-patches Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true X-Gm-Message-State: ALoCoQldPnKKburagw4+0Wyo4X50jYt1V/sIE9AIbjDe4XqctITj1b10AvWRQG/GBzpCDSA3ia+5Zkisv9L9w3K+0YuaUJ5FBNzCVa3ABOtywJ6eWzxTwFz5NES/QGRs1175r4U5dcxcFikYHJLVWJ4z3Z2PjNO7kM2clZ21o5U1dKUGyotZ7Qivvm/i78ndLJzjX9g1A84e X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2012-07/txt/msg00182.txt.bz2 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 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 > > 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; > }