From patchwork Mon Jul 9 18:10:15 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Doug Evans X-Patchwork-Id: 169910 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 59C222C0201 for ; Tue, 10 Jul 2012 04:10:49 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1342462250; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Received:To:Subject:Message-Id:Date: From:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=BtULm6s TToNkKn4160Lv4JJg2l4=; b=yQNjp13atqwLnochSpF7MyGIcYxIOz07+2QNpno 0CoXzncg29u4W+j605eXg3YNYVyru/355d8W36EeBk8WqXHSZMvbS4pPG1kzgVu8 fpUPNoYlIt+yzUqA0S11WxTSkDkep5Dnk9HqH7vGcppTykbReJspZq2Ld81Wfrhh QwIY= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:Received:Received:Received:Received:To:Subject:Message-Id:Date:From:X-Gm-Message-State:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=GqiUP63rvVTiROHU9HtMDcnAcOrHqoUAlykB+QwACbZJP6DmlbON5UQombOwdO CyYzvwbvXeDUmnabzLZdLeQG936x0p6ZdS7waz16+JKaFqofTgrtcTpQdEurj84G IuJefwpsP0Dnn17cpS6P0cL4slLB0CaWGHO2xYt2d7FKU=; Received: (qmail 13841 invoked by alias); 9 Jul 2012 18:10:36 -0000 Received: (qmail 13636 invoked by uid 22791); 9 Jul 2012 18:10:34 -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-we0-f201.google.com (HELO mail-we0-f201.google.com) (74.125.82.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 09 Jul 2012 18:10:18 +0000 Received: by weyx56 with SMTP id x56so25179wey.2 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=LBuP7I08pho+8qA57N34/2wMTvhzpMPkedlQYaXkzZz2kJrhBO1Ww6A+VwCQ/+RTYA hT7Rc4xgAVQLV2oINg46c8P8z8+BTAKr4xrJD/8qPifCMcmk4tp9DsLqF0+fdlvBHhNK pUGXoPrgG71U95rGDQ+CJDW3DCzQYFSdDPmYIRfmtz8Ad4Th8ETq7xPkrRkUYrvjq3VT V0A3wIllT4p4R017pgXxJiLHiPRjhDM9C/FZ8T+euGsmXVnW32bya8MYneKq+RJKaKgT tq5JjLA8WJIm+AMZtSqk9RaYbCnkpFVmu5MG6D9HZhTMhvBEB2hzFn6SK3j9qnmvgJdW JIlw== Received: by 10.14.185.140 with SMTP id u12mr13095274eem.0.1341857416514; 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, 9 Jul 2012 11:10:15 -0700 (PDT) From: dje@google.com (Doug Evans) X-Gm-Message-State: ALoCoQlYdL2IBOErB6frjgZD1uwh3VC/NENQ+i5UCC4kORucp/Dd6fUZD5X58xbMdg7J5tJ0Est1VihWQfvSLSwWlnMiwsv0dzjNVymFNBuXbzjgL1Wx9H7R3kfGvAqDPmOkzt9fWDxalnu93FhTKoJQTa5S5iWi4jZI1xdkC5eW+HLQauNAtpmZNny21TzO1qmIosBK2GRE0d30ZstsuFTo77VnVWL/YQ== Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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; }