From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15946 invoked by alias); 9 Jul 2012 18:14:23 -0000 Received: (qmail 15937 invoked by uid 22791); 9 Jul 2012 18:14:22 -0000 X-SWARE-Spam-Status: No, hits=-4.1 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-qc0-f201.google.com (HELO mail-qc0-f201.google.com) (209.85.216.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 09 Jul 2012 18:14:08 +0000 Received: by qcha6 with SMTP id a6so1232463qch.0 for ; Mon, 09 Jul 2012 11:14:07 -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=YyCOrN8ReWyHzTruFNHvJNiH10yEt8MeqpglWWl8htg=; b=ko3jYApDOlAgdilEHsjbrtIAWZzuTbFzLxsNaDB4FJRdsebswVN+Muo0OS/ShTiRxK 0cXspldDpaN3B724o1m53typM8xOjBd5G8fu4qybEfKnBdoiVefPSy1FxPA2f/hFTNoO 4IV4uFwuhlaMBpeeOoqzV2PHcFKRI3XkHHmaL/KStv4Gdl9uDLWMjNY+yLGTqRSrxSw5 C1LkDAcCISleA+KGlGBLpNw0HTIUFmvRYkEFXBaV8LZEyiBKc88dXoaky7UoCasX+hIu cpNJV81vZiCw/+Eeq8aSBVTApLej4nzQcjgJu+XwdcAIIdNmrX36L5TanxolvKJpmwrm STDg== Received: by 10.236.155.166 with SMTP id j26mr21133010yhk.0.1341857647666; Mon, 09 Jul 2012 11:14:07 -0700 (PDT) Received: by 10.236.155.166 with SMTP id j26mr21132996yhk.0.1341857647604; Mon, 09 Jul 2012 11:14:07 -0700 (PDT) Received: from wpzn4.hot.corp.google.com (216-239-44-65.google.com [216.239.44.65]) by gmr-mx.google.com with ESMTPS id n15si3558920anq.2.2012.07.09.11.14.07 (version=TLSv1/SSLv3 cipher=AES128-SHA); Mon, 09 Jul 2012 11:14:07 -0700 (PDT) Received: from ruffy2.mtv.corp.google.com (ruffy2.mtv.corp.google.com [172.18.110.129]) by wpzn4.hot.corp.google.com (Postfix) with ESMTP id 6F69A1E0043 for ; Mon, 9 Jul 2012 11:14:07 -0700 (PDT) Received: by ruffy2.mtv.corp.google.com (Postfix, from userid 67641) id 213E81E13A1; Mon, 9 Jul 2012 11:14:07 -0700 (PDT) To: gdb-patches@sourceware.org Subject: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb. Message-Id: <20120709181407.213E81E13A1@ruffy2.mtv.corp.google.com> Date: Mon, 09 Jul 2012 18:14:00 -0000 From: dje@google.com (Doug Evans) X-Gm-Message-State: ALoCoQmtE2gpMQDPjvtFo+fLxyUkbuvd1qRY99gOVMBhufoNUD+QgbezgAlTSoP2HDNILR8ZDWZvtM5JAW8KMs5E8bsltnvj9ymT7m/TcHKSlZ9VmRzyrMeWADTiQdPfqfyIRFS6GX/R+A09ROkI+wZGbF+DOitu7m1/GOW7ZYs6JrFOh4ml2yv/glGkgLWYl0eQuvpEtAN88DgihOycdcOjM+1rUY+IDg== 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/msg00112.txt.bz2 [Blech, sent to right list this time. Already sent to gcc-patches@.] 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; }