From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 13618 invoked by alias); 9 Jul 2012 18:10:33 -0000 Received: (qmail 13605 invoked by uid 22791); 9 Jul 2012 18:10:31 -0000 X-SWARE-Spam-Status: No, hits=-4.4 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,KHOP_RCVD_TRUST,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-wi0-f201.google.com (HELO mail-wi0-f201.google.com) (209.85.212.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 09 Jul 2012 18:10:17 +0000 Received: by wibhm2 with SMTP id hm2so170734wib.0 for ; Mon, 09 Jul 2012 11:10:16 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=to:subject:message-id:date:from:x-gm-message-state; bh=poSgleitjJFmZTPWphP9piRXqjf+hzeNfvaEox7eihk=; b=K6Kbr7fNFu40uKB4LKF/2a+qDH7vt4hCI0ZFd12lnMJGTZduk5VNjwIYj18PmPZKa1 lcEppfZaSfQgwHTvAGkdcnMcYAT4ajsN5BzwEAWXpNmplwJGktfozNcSsbtxs8j75cJb ZsjVSKbYS5TvMB9kbQ883Z3Bnkzflkp7QVvQ6elL4EbD3Gl6tI3svLA84oC7fmKw2Nau SQsE4WodF0uEIQHaa5YqZ6BC0Ka/T2vL4i5/3jpY6+L9Xj/1dWnNvIK+oTEq2DLpn+8E lAGfx9rt6xZ8LWvCVGlzrZcNFvswwKkuK9Y9tX+dD1vqb3sC+fWpncEZTwuLeIViPlvr A3tA== Received: by 10.14.185.140 with SMTP id u12mr13095273eem.0.1341857416467; Mon, 09 Jul 2012 11:10:16 -0700 (PDT) Received: by 10.14.185.140 with SMTP id u12mr13095261eem.0.1341857416290; Mon, 09 Jul 2012 11:10:16 -0700 (PDT) Received: from hpza9.eem.corp.google.com ([74.125.121.33]) by gmr-mx.google.com with ESMTPS id d52si22976690eei.1.2012.07.09.11.10.16 (version=TLSv1/SSLv3 cipher=AES128-SHA); Mon, 09 Jul 2012 11:10:16 -0700 (PDT) Received: from ruffy2.mtv.corp.google.com (ruffy2.mtv.corp.google.com [172.18.110.129]) by hpza9.eem.corp.google.com (Postfix) with ESMTP id EA38D5C0060; Mon, 9 Jul 2012 11:10:15 -0700 (PDT) Received: by ruffy2.mtv.corp.google.com (Postfix, from userid 67641) id 2FCA41E13A1; Mon, 9 Jul 2012 11:10:15 -0700 (PDT) To: gcc-patches@gcc.gnu.org, gdb@sourceware.org Subject: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb. Message-Id: <20120709181015.2FCA41E13A1@ruffy2.mtv.corp.google.com> Date: Mon, 09 Jul 2012 18:10:00 -0000 From: dje@google.com (Doug Evans) X-Gm-Message-State: ALoCoQl0AqHv2ieoIVI+bI5xvHJIwOxQ+JEdwmVftXTyJl0Eq/HGsTyFWPgmcS7+ZgFKZ5aB2/7Mr+vdP+aJcwV3Vtnki1toSEfbbtz+oNDlIxlk1Cvw3esHl6RADr/v50Xz8o9W2AntlgU5dfOR9iyTy1ow2pttBEAZ0OGVxnO27pvyM0u6HTBewY/N+Q+FN9M5nmaW8Cm4 X-IsSubscribed: yes Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org X-SW-Source: 2012-07/txt/msg00005.txt.bz2 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; }