From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8712 invoked by alias); 11 Jul 2002 17:37:16 -0000 Mailing-List: contact gdb-patches-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sources.redhat.com Received: (qmail 8691 invoked from network); 11 Jul 2002 17:37:05 -0000 Received: from unknown (HELO zwingli.cygnus.com) (208.245.165.35) by sources.redhat.com with SMTP; 11 Jul 2002 17:37:05 -0000 Received: by zwingli.cygnus.com (Postfix, from userid 442) id 830C15EA11; Thu, 11 Jul 2002 12:37:03 -0500 (EST) To: Daniel Jacobowitz Cc: gdb-patches@sources.redhat.com Subject: Re: [rfa] Symbol hashing (for the last time?) References: <20011030112756.A1546@nevyn.them.org> <20020711005652.GA17895@nevyn.them.org> From: Jim Blandy Date: Thu, 11 Jul 2002 10:43:00 -0000 In-Reply-To: <20020711005652.GA17895@nevyn.them.org> Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-SW-Source: 2002-07/txt/msg00230.txt.bz2 The definition of `struct block' in symtab.h needs a nice, detailed comment explaining exactly how the hash table works --- which hash function is used, chaining, allocation invariants, mangled vs. unmangled names, etc. Daniel Jacobowitz writes: > Here's a patch from last October, dusted off and merged to the current > sources. The only substantial changes were some fixes for ada-lang.c, > merged after I wrote the original patch. I've verified no regressions > on i386-linux for GCC (2.95,3.0.4,3.1)/(stabs,dwarf2). > > This converts the normal symbol table lookups into hash tables. A few > sorts of symbol tables aren't hashed: those produced by mdebugread.c > and dstread.c, because they build symbol tables in lots of ad-hoc code, > and symbol tables which are actually the arguments to a function > (because order matters, or at least comments suggest so). A next step > will be to convert mdebugread.c, delete dstread.c (it's marked for an > upcoming obsoletion, isn't it?), and then delete all the complicated > binary search code since the only remaining unhashed symtabs will be > argument lists, which are small. > > This should help performance a bit on large programs. Ok to commit? > Anyone see any problems with it? > > -- > Daniel Jacobowitz Carnegie Mellon University > MontaVista Software Debian GNU/Linux Developer > > 2002-07-10 Daniel Jacobowitz > > Based on patch from Daniel Berlin . > * buildsym.c: Include "demangle.h" for SYMBOL_INIT_DEMANGLED_NAME. > (finish_block) For non-function blocks, hash the symbol table. For > function blocks, mark the symbol table as unhashed. > * minsyms.c (msymbol_hash): Return hash value without taking modulus. > (msymbol_hash_iw): Likewise. > (add_minsym_to_hash_table): Take modulus of msymbol_hash's return > value. > (add_minsym_to_demangled_hash_table): Likewise for msymbol_hash_iw. > (lookup_minimal_symbol): Likewise for both. > * symtab.h (struct block): Add `hashtable' flag. > (BLOCK_HASHTABLE): New macro. > (BLOCK_BUCKETS): New macro. > (BLOCK_BUCKET): New macro. > (ALL_BLOCK_SYMBOLS): New macro. > (BLOCK_SHOULD_SORT): Do not sort hashed blocks. > (struct symbol): Add `hash_next' pointer. > * symtab.c (lookup_block_symbol): Search using the hash table when > possible. > (find_pc_sect_symtab): Use ALL_BLOCK_SYMBOLS. > (search_symbols, find_addr_symbol): Likewise. > > * dstread.c (process_dst_block): Clear hashtable bit for new block. > (read_dst_symtab): Likewise. > * jv-lang.c (get_java_class_symtab): Likewise. > * mdebugread.c: Include "gdb_assert.h". > (shrink_block): Assert that the block being modified is not hashed. > * coffread.c (patch_opaque_types): Use ALL_BLOCK_SYMBOLS. > * symmisc.c (free_symtab_block): Walk the hash table when freeing > symbols. > (dump_symtab): Recognize hashed blocks. > * printcmd.c (print_frame_args): Assert that function blocks do not > have hashed symbol tables. > * ada-lang.c (symtab_for_sym): Use ALL_BLOCK_SYMBOLS. > (fill_in_ada_prototype, debug_print_block): Likewise. > (ada_add_block_symbols): Use ALL_BLOCK_SYMBOLS. Handle hash tables. > > Index: gdb/ada-lang.c > =================================================================== > RCS file: /cvs/src/src/gdb/ada-lang.c,v > retrieving revision 1.2 > diff -u -p -r1.2 ada-lang.c > --- gdb/ada-lang.c 19 Jun 2002 16:55:28 -0000 1.2 > +++ gdb/ada-lang.c 11 Jul 2002 00:14:23 -0000 > @@ -3560,6 +3560,7 @@ symtab_for_sym (sym) > struct symtab* s; > struct objfile *objfile; > struct block *b; > + struct symbol *tmp_sym; > int i, j; > > ALL_SYMTABS (objfile, s) > @@ -3574,12 +3575,12 @@ symtab_for_sym (sym) > case LOC_BLOCK: > case LOC_CONST_BYTES: > b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK); > - for (i = 0; i < BLOCK_NSYMS (b); i += 1) > - if (sym == BLOCK_SYM (b, i)) > + ALL_BLOCK_SYMBOLS (b, i, tmp_sym) > + if (sym == tmp_sym) > return s; > b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK); > - for (i = 0; i < BLOCK_NSYMS (b); i += 1) > - if (sym == BLOCK_SYM (b, i)) > + ALL_BLOCK_SYMBOLS (b, i, tmp_sym) > + if (sym == tmp_sym) > return s; > break; > default: > @@ -3601,8 +3602,8 @@ symtab_for_sym (sym) > j < BLOCKVECTOR_NBLOCKS (BLOCKVECTOR (s)); j += 1) > { > b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), j); > - for (i = 0; i < BLOCK_NSYMS (b); i += 1) > - if (sym == BLOCK_SYM (b, i)) > + ALL_BLOCK_SYMBOLS (b, i, tmp_sym) > + if (sym == tmp_sym) > return s; > } > break; > @@ -4094,14 +4095,14 @@ ada_add_block_symbols (block, name, name > /* Set true when we find a matching non-argument symbol */ > int found_sym; > int is_sorted = BLOCK_SHOULD_SORT (block); > + struct symbol *sym; > > arg_sym = NULL; found_sym = 0; > if (wild) > { > - for (i = 0; i < BLOCK_NSYMS (block); i += 1) > + struct symbol *sym; > + ALL_BLOCK_SYMBOLS (block, i, sym) > { > - struct symbol *sym = BLOCK_SYM (block, i); > - > if (SYMBOL_NAMESPACE (sym) == namespace && > wild_match (name, name_len, SYMBOL_NAME (sym))) > { > @@ -4149,44 +4150,46 @@ ada_add_block_symbols (block, name, name > else > i = 0; > > - for (; i < BLOCK_NSYMS (block); i += 1) > - { > - struct symbol *sym = BLOCK_SYM (block, i); > - > - if (SYMBOL_NAMESPACE (sym) == namespace) > - { > - int cmp = strncmp (name, SYMBOL_NAME (sym), name_len); > - > - if (cmp < 0) > - { > - if (is_sorted) > - break; > - } > - else if (cmp == 0 > - && is_name_suffix (SYMBOL_NAME (sym) + name_len)) > - { > - switch (SYMBOL_CLASS (sym)) > - { > - case LOC_ARG: > - case LOC_LOCAL_ARG: > - case LOC_REF_ARG: > - case LOC_REGPARM: > - case LOC_REGPARM_ADDR: > - case LOC_BASEREG_ARG: > - arg_sym = sym; > - break; > - case LOC_UNRESOLVED: > - break; > - default: > - found_sym = 1; > - fill_in_ada_prototype (sym); > - add_defn_to_vec (fixup_symbol_section (sym, objfile), > - block); > - break; > - } > - } > - } > - } > + for (; i < BLOCK_BUCKETS (block); i += 1) > + for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next) > + { > + if (SYMBOL_NAMESPACE (sym) == namespace) > + { > + int cmp = strncmp (name, SYMBOL_NAME (sym), name_len); > + > + if (cmp < 0) > + { > + if (is_sorted) > + { > + i = BLOCK_BUCKETS (block); > + break; > + } > + } > + else if (cmp == 0 > + && is_name_suffix (SYMBOL_NAME (sym) + name_len)) > + { > + switch (SYMBOL_CLASS (sym)) > + { > + case LOC_ARG: > + case LOC_LOCAL_ARG: > + case LOC_REF_ARG: > + case LOC_REGPARM: > + case LOC_REGPARM_ADDR: > + case LOC_BASEREG_ARG: > + arg_sym = sym; > + break; > + case LOC_UNRESOLVED: > + break; > + default: > + found_sym = 1; > + fill_in_ada_prototype (sym); > + add_defn_to_vec (fixup_symbol_section (sym, objfile), > + block); > + break; > + } > + } > + } > + } > } > > if (! found_sym && arg_sym != NULL) > @@ -4219,53 +4222,57 @@ ada_add_block_symbols (block, name, name > else > i = 0; > > - for (; i < BLOCK_NSYMS (block); i += 1) > - { > - struct symbol *sym = BLOCK_SYM (block, i); > - > - if (SYMBOL_NAMESPACE (sym) == namespace) > - { > - int cmp; > - > - cmp = (int) '_' - (int) SYMBOL_NAME (sym)[0]; > - if (cmp == 0) > - { > - cmp = strncmp ("_ada_", SYMBOL_NAME (sym), 5); > - if (cmp == 0) > - cmp = strncmp (name, SYMBOL_NAME (sym) + 5, name_len); > - } > - > - if (cmp < 0) > - { > - if (is_sorted) > - break; > - } > - else if (cmp == 0 > - && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5)) > - { > - switch (SYMBOL_CLASS (sym)) > - { > - case LOC_ARG: > - case LOC_LOCAL_ARG: > - case LOC_REF_ARG: > - case LOC_REGPARM: > - case LOC_REGPARM_ADDR: > - case LOC_BASEREG_ARG: > - arg_sym = sym; > - break; > - case LOC_UNRESOLVED: > - break; > - default: > - found_sym = 1; > - fill_in_ada_prototype (sym); > - add_defn_to_vec (fixup_symbol_section (sym, objfile), > - block); > - break; > - } > - } > - } > - } > - > + for (; i < BLOCK_BUCKETS (block); i += 1) > + for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next) > + { > + struct symbol *sym = BLOCK_SYM (block, i); > + > + if (SYMBOL_NAMESPACE (sym) == namespace) > + { > + int cmp; > + > + cmp = (int) '_' - (int) SYMBOL_NAME (sym)[0]; > + if (cmp == 0) > + { > + cmp = strncmp ("_ada_", SYMBOL_NAME (sym), 5); > + if (cmp == 0) > + cmp = strncmp (name, SYMBOL_NAME (sym) + 5, name_len); > + } > + > + if (cmp < 0) > + { > + if (is_sorted) > + { > + i = BLOCK_BUCKETS (block); > + break; > + } > + } > + else if (cmp == 0 > + && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5)) > + { > + switch (SYMBOL_CLASS (sym)) > + { > + case LOC_ARG: > + case LOC_LOCAL_ARG: > + case LOC_REF_ARG: > + case LOC_REGPARM: > + case LOC_REGPARM_ADDR: > + case LOC_BASEREG_ARG: > + arg_sym = sym; > + break; > + case LOC_UNRESOLVED: > + break; > + default: > + found_sym = 1; > + fill_in_ada_prototype (sym); > + add_defn_to_vec (fixup_symbol_section (sym, objfile), > + block); > + break; > + } > + } > + } > + } > + > /* NOTE: This really shouldn't be needed for _ada_ symbols. > They aren't parameters, right? */ > if (! found_sym && arg_sym != NULL) > @@ -4292,6 +4299,7 @@ fill_in_ada_prototype (func) > struct type* ftype; > struct type* rtype; > size_t max_fields; > + struct symbol *sym; > > if (func == NULL > || TYPE_CODE (SYMBOL_TYPE (func)) != TYPE_CODE_FUNC > @@ -4308,16 +4316,13 @@ fill_in_ada_prototype (func) > SYMBOL_TYPE (func) = ftype; > > b = SYMBOL_BLOCK_VALUE (func); > - nsyms = BLOCK_NSYMS (b); > > nargs = 0; > max_fields = 8; > TYPE_FIELDS (ftype) = > (struct field*) xmalloc (sizeof (struct field) * max_fields); > - for (i = 0; i < nsyms; i += 1) > + ALL_BLOCK_SYMBOLS (b, i, sym) > { > - struct symbol *sym = BLOCK_SYM (b, i); > - > GROW_VECT (TYPE_FIELDS (ftype), max_fields, nargs+1); > > switch (SYMBOL_CLASS (sym)) > @@ -4903,6 +4908,8 @@ debug_print_block (b) > struct block* b; > { > int i; > + struct symbol *i; > + > fprintf (stderr, "Block: %p; [0x%lx, 0x%lx]", > b, BLOCK_START(b), BLOCK_END(b)); > if (BLOCK_FUNCTION(b) != NULL) > @@ -4910,11 +4917,11 @@ debug_print_block (b) > fprintf (stderr, "\n"); > fprintf (stderr, "\t Superblock: %p\n", BLOCK_SUPERBLOCK(b)); > fprintf (stderr, "\t Symbols:"); > - for (i = 0; i < BLOCK_NSYMS (b); i += 1) > + ALL_BLOCK_SYMBOLS (b, i, sym) > { > if (i > 0 && i % 4 == 0) > fprintf (stderr, "\n\t\t "); > - fprintf (stderr, " %s", SYMBOL_NAME (BLOCK_SYM (b, i))); > + fprintf (stderr, " %s", SYMBOL_NAME (sym)); > } > fprintf (stderr, "\n"); > } > Index: gdb/buildsym.c > =================================================================== > RCS file: /cvs/src/src/gdb/buildsym.c,v > retrieving revision 1.16 > diff -u -p -r1.16 buildsym.c > --- gdb/buildsym.c 15 May 2002 21:19:18 -0000 1.16 > +++ gdb/buildsym.c 11 Jul 2002 00:14:23 -0000 > @@ -40,6 +40,7 @@ > #include "bcache.h" > #include "filenames.h" /* For DOSish file names */ > #include "macrotab.h" > +#include "demangle.h" /* Needed by SYMBOL_INIT_DEMANGLED_NAME. */ > /* Ask buildsym.h to define the vars it normally declares `extern'. */ > #define EXTERN > /**/ > @@ -243,17 +244,45 @@ finish_block (struct symbol *symbol, str > /* EMPTY */ ; > } > > - block = (struct block *) obstack_alloc (&objfile->symbol_obstack, > - (sizeof (struct block) + ((i - 1) * sizeof (struct symbol *)))); > - > /* Copy the symbols into the block. */ > > - BLOCK_NSYMS (block) = i; > - for (next = *listhead; next; next = next->next) > + if (symbol) > + { > + block = (struct block *) > + obstack_alloc (&objfile->symbol_obstack, > + (sizeof (struct block) + > + ((i - 1) * sizeof (struct symbol *)))); > + BLOCK_NSYMS (block) = i; > + for (next = *listhead; next; next = next->next) > + for (j = next->nsyms - 1; j >= 0; j--) > + { > + BLOCK_SYM (block, --i) = next->symbol[j]; > + } > + } > + else > { > - for (j = next->nsyms - 1; j >= 0; j--) > + block = (struct block *) > + obstack_alloc (&objfile->symbol_obstack, > + (sizeof (struct block) + > + ((i / 5) * sizeof (struct symbol *)))); > + for (j = 0; j < ((i / 5) + 1); j++) > { > - BLOCK_SYM (block, --i) = next->symbol[j]; > + BLOCK_BUCKET (block, j) = 0; > + } > + BLOCK_BUCKETS (block) = (i / 5) + 1; > + for (next = *listhead; next; next = next->next) > + { > + for (j = next->nsyms - 1; j >= 0; j--) > + { > + struct symbol *sym; > + unsigned int hash_index; > + SYMBOL_INIT_DEMANGLED_NAME (next->symbol[j], &objfile->symbol_obstack); > + hash_index = msymbol_hash_iw (SYMBOL_SOURCE_NAME (next->symbol[j])); > + hash_index = hash_index % BLOCK_BUCKETS (block); > + sym = BLOCK_BUCKET (block, hash_index); > + BLOCK_BUCKET (block, hash_index) = next->symbol[j]; > + next->symbol[j]->hash_next = sym; > + } > } > } > > @@ -271,6 +300,7 @@ finish_block (struct symbol *symbol, str > struct type *ftype = SYMBOL_TYPE (symbol); > SYMBOL_BLOCK_VALUE (symbol) = block; > BLOCK_FUNCTION (block) = symbol; > + BLOCK_HASHTABLE (block) = 0; > > if (TYPE_NFIELDS (ftype) <= 0) > { > @@ -352,6 +382,7 @@ finish_block (struct symbol *symbol, str > else > { > BLOCK_FUNCTION (block) = NULL; > + BLOCK_HASHTABLE (block) = 1; > } > > /* Now "free" the links of the list, and empty the list. */ > Index: gdb/coffread.c > =================================================================== > RCS file: /cvs/src/src/gdb/coffread.c,v > retrieving revision 1.26 > diff -u -p -r1.26 coffread.c > --- gdb/coffread.c 19 Mar 2002 19:00:03 -0000 1.26 > +++ gdb/coffread.c 11 Jul 2002 00:14:23 -0000 > @@ -1409,13 +1409,12 @@ patch_opaque_types (struct symtab *s) > > /* Go through the per-file symbols only */ > b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK); > - for (i = BLOCK_NSYMS (b) - 1; i >= 0; i--) > + ALL_BLOCK_SYMBOLS (b, i, real_sym) > { > /* Find completed typedefs to use to fix opaque ones. > Remove syms from the chain when their types are stored, > but search the whole chain, as there may be several syms > from different files with the same name. */ > - real_sym = BLOCK_SYM (b, i); > if (SYMBOL_CLASS (real_sym) == LOC_TYPEDEF && > SYMBOL_NAMESPACE (real_sym) == VAR_NAMESPACE && > TYPE_CODE (SYMBOL_TYPE (real_sym)) == TYPE_CODE_PTR && > Index: gdb/dstread.c > =================================================================== > RCS file: /cvs/src/src/gdb/dstread.c,v > retrieving revision 1.8 > diff -u -p -r1.8 dstread.c > --- gdb/dstread.c 13 May 2002 14:00:35 -0000 1.8 > +++ gdb/dstread.c 11 Jul 2002 00:14:24 -0000 > @@ -1396,6 +1396,7 @@ process_dst_block (struct objfile *objfi > symnum++; > } > BLOCK_NSYMS (block) = total_symbols; > + BLOCK_HASHTABLE (block) = 0; > BLOCK_START (block) = address; > BLOCK_END (block) = address + size; > BLOCK_SUPERBLOCK (block) = 0; > @@ -1480,6 +1481,7 @@ read_dst_symtab (struct objfile *objfile > (total_globals - 1) * > sizeof (struct symbol *)); > BLOCK_NSYMS (global_block) = total_globals; > + BLOCK_HASHTABLE (global_block) = 0; > for (symnum = 0; symnum < total_globals; symnum++) > { > nextsym = dst_global_symbols->next; > Index: gdb/jv-lang.c > =================================================================== > RCS file: /cvs/src/src/gdb/jv-lang.c,v > retrieving revision 1.11 > diff -u -p -r1.11 jv-lang.c > --- gdb/jv-lang.c 2 Dec 2001 22:43:59 -0000 1.11 > +++ gdb/jv-lang.c 11 Jul 2002 00:14:24 -0000 > @@ -106,6 +106,7 @@ get_java_class_symtab (void) > bl = (struct block *) > obstack_alloc (&objfile->symbol_obstack, sizeof (struct block)); > BLOCK_NSYMS (bl) = 0; > + BLOCK_HASHTABLE (bl) = 0; > BLOCK_START (bl) = 0; > BLOCK_END (bl) = 0; > BLOCK_FUNCTION (bl) = NULL; > Index: gdb/mdebugread.c > =================================================================== > RCS file: /cvs/src/src/gdb/mdebugread.c,v > retrieving revision 1.26 > diff -u -p -r1.26 mdebugread.c > --- gdb/mdebugread.c 13 May 2002 14:00:36 -0000 1.26 > +++ gdb/mdebugread.c 11 Jul 2002 00:14:25 -0000 > @@ -52,6 +52,7 @@ > #include "stabsread.h" > #include "complaints.h" > #include "demangle.h" > +#include "gdb_assert.h" > > /* These are needed if the tm.h file does not contain the necessary > mips specific definitions. */ > @@ -4726,6 +4727,11 @@ shrink_block (struct block *b, struct sy > (sizeof (struct block) > + ((BLOCK_NSYMS (b) - 1) > * sizeof (struct symbol *)))); > + > + /* FIXME: Not worth hashing this block as it's built. */ > + /* All callers should have created the block with new_block (), which > + would mean it was not previously hashed. Make sure. */ > + gdb_assert (BLOCK_HASHTABLE (new) == 0); > > /* Should chase pointers to old one. Fortunately, that`s just > the block`s function and inferior blocks */ > Index: gdb/minsyms.c > =================================================================== > RCS file: /cvs/src/src/gdb/minsyms.c,v > retrieving revision 1.21 > diff -u -p -r1.21 minsyms.c > --- gdb/minsyms.c 24 Apr 2002 08:00:54 -0000 1.21 > +++ gdb/minsyms.c 11 Jul 2002 00:14:25 -0000 > @@ -91,7 +91,7 @@ msymbol_hash_iw (const char *string) > ++string; > } > } > - return hash % MINIMAL_SYMBOL_HASH_SIZE; > + return hash; > } > > /* Compute a hash code for a string. */ > @@ -102,7 +102,7 @@ msymbol_hash (const char *string) > unsigned int hash = 0; > for (; *string; ++string) > hash = hash * 67 + *string - 113; > - return hash % MINIMAL_SYMBOL_HASH_SIZE; > + return hash; > } > > /* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE. */ > @@ -112,7 +112,7 @@ add_minsym_to_hash_table (struct minimal > { > if (sym->hash_next == NULL) > { > - unsigned int hash = msymbol_hash (SYMBOL_NAME (sym)); > + unsigned int hash = msymbol_hash (SYMBOL_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE; > sym->hash_next = table[hash]; > table[hash] = sym; > } > @@ -126,7 +126,7 @@ add_minsym_to_demangled_hash_table (stru > { > if (sym->demangled_hash_next == NULL) > { > - unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym)); > + unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE; > sym->demangled_hash_next = table[hash]; > table[hash] = sym; > } > @@ -154,8 +154,8 @@ lookup_minimal_symbol (register const ch > struct minimal_symbol *found_file_symbol = NULL; > struct minimal_symbol *trampoline_symbol = NULL; > > - unsigned int hash = msymbol_hash (name); > - unsigned int dem_hash = msymbol_hash_iw (name); > + unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE; > + unsigned int dem_hash = msymbol_hash_iw (name) % MINIMAL_SYMBOL_HASH_SIZE; > > #ifdef SOFUN_ADDRESS_MAYBE_MISSING > if (sfile != NULL) > Index: gdb/printcmd.c > =================================================================== > RCS file: /cvs/src/src/gdb/printcmd.c,v > retrieving revision 1.39 > diff -u -p -r1.39 printcmd.c > --- gdb/printcmd.c 11 May 2002 23:48:23 -0000 1.39 > +++ gdb/printcmd.c 11 Jul 2002 00:14:26 -0000 > @@ -40,6 +40,7 @@ > #include "objfiles.h" /* ditto */ > #include "completer.h" /* for completion functions */ > #include "ui-out.h" > +#include "gdb_assert.h" > > extern int asm_demangle; /* Whether to demangle syms in asm printouts */ > extern int addressprint; /* Whether to print hex addresses in HLL " */ > @@ -1785,6 +1786,10 @@ print_frame_args (struct symbol *func, s > if (func) > { > b = SYMBOL_BLOCK_VALUE (func); > + /* Function blocks are order sensitive, and thus should not be > + hashed. */ > + gdb_assert (BLOCK_HASHTABLE (b) == 0); > + > ALL_BLOCK_SYMBOLS (b, i, sym) > { > QUIT; > Index: gdb/symmisc.c > =================================================================== > RCS file: /cvs/src/src/gdb/symmisc.c,v > retrieving revision 1.9 > diff -u -p -r1.9 symmisc.c > --- gdb/symmisc.c 15 May 2002 21:19:21 -0000 1.9 > +++ gdb/symmisc.c 11 Jul 2002 00:14:26 -0000 > @@ -86,11 +86,17 @@ static void > free_symtab_block (struct objfile *objfile, struct block *b) > { > register int i, n; > - n = BLOCK_NSYMS (b); > + struct symbol *sym, *next_sym; > + > + n = BLOCK_BUCKETS (b); > for (i = 0; i < n; i++) > { > - xmfree (objfile->md, SYMBOL_NAME (BLOCK_SYM (b, i))); > - xmfree (objfile->md, (PTR) BLOCK_SYM (b, i)); > + for (sym = BLOCK_BUCKET (b, i); sym; sym = next_sym) > + { > + next_sym = sym->hash_next; > + xmfree (objfile->md, SYMBOL_NAME (sym)); > + xmfree (objfile->md, (PTR) sym); > + } > } > xmfree (objfile->md, (PTR) b); > } > @@ -457,8 +463,14 @@ dump_symtab (struct objfile *objfile, st > fprintf_filtered (outfile, " under "); > gdb_print_host_address (BLOCK_SUPERBLOCK (b), outfile); > } > - blen = BLOCK_NSYMS (b); > - fprintf_filtered (outfile, ", %d syms in ", blen); > + /* drow/2002-07-10: We could save the total symbols count > + even if we're using a hashtable, but nothing else but this message > + wants it. */ > + blen = BLOCK_BUCKETS (b); > + if (BLOCK_HASHTABLE (b)) > + fprintf_filtered (outfile, ", %d buckets in ", blen); > + else > + fprintf_filtered (outfile, ", %d syms in ", blen); > print_address_numeric (BLOCK_START (b), 1, outfile); > fprintf_filtered (outfile, ".."); > print_address_numeric (BLOCK_END (b), 1, outfile); > @@ -474,8 +486,8 @@ dump_symtab (struct objfile *objfile, st > if (BLOCK_GCC_COMPILED (b)) > fprintf_filtered (outfile, ", compiled with gcc%d", BLOCK_GCC_COMPILED (b)); > fprintf_filtered (outfile, "\n"); > - /* Now print each symbol in this block. */ > - /* FIXMED: Sort? */ > + /* Now print each symbol in this block (in no particular order, if > + we're using a hashtable). */ > ALL_BLOCK_SYMBOLS (b, j, sym) > { > struct print_symbol_args s; > Index: gdb/symtab.c > =================================================================== > RCS file: /cvs/src/src/gdb/symtab.c,v > retrieving revision 1.64 > diff -u -p -r1.64 symtab.c > --- gdb/symtab.c 4 Jul 2002 15:22:42 -0000 1.64 > +++ gdb/symtab.c 11 Jul 2002 00:14:27 -0000 > @@ -1328,6 +1328,22 @@ lookup_block_symbol (register const stru > register struct symbol *sym_found = NULL; > register int do_linear_search = 1; > > + if (BLOCK_HASHTABLE (block)) > + { > + unsigned int hash_index; > + hash_index = msymbol_hash_iw (name); > + hash_index = hash_index % BLOCK_BUCKETS (block); > + for (sym = BLOCK_BUCKET (block, hash_index); sym; sym = sym->hash_next) > + { > + if (SYMBOL_NAMESPACE (sym) == namespace > + && (mangled_name > + ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0 > + : SYMBOL_MATCHES_NAME (sym, name))) > + return sym; > + } > + return NULL; > + } > + > /* If the blocks's symbols were sorted, start with a binary search. */ > > if (BLOCK_SHOULD_SORT (block)) > @@ -1582,14 +1598,15 @@ find_pc_sect_symtab (CORE_ADDR pc, asect > if (section != 0) > { > int i; > + struct symbol *sym = NULL; > > - for (i = 0; i < b->nsyms; i++) > + ALL_BLOCK_SYMBOLS (b, i, sym) > { > - fixup_symbol_section (b->sym[i], objfile); > - if (section == SYMBOL_BFD_SECTION (b->sym[i])) > + fixup_symbol_section (sym, objfile); > + if (section == SYMBOL_BFD_SECTION (sym)) > break; > } > - if (i >= b->nsyms) > + if ((i >= BLOCK_BUCKETS (b)) && (sym == NULL)) > continue; /* no symbol in this symtab matches section */ > } > distance = BLOCK_END (b) - BLOCK_START (b); > @@ -1661,10 +1678,8 @@ find_addr_symbol (CORE_ADDR addr, struct > { > QUIT; > block = BLOCKVECTOR_BLOCK (BLOCKVECTOR (symtab), blocknum); > - top = BLOCK_NSYMS (block); > - for (bot = 0; bot < top; bot++) > + ALL_BLOCK_SYMBOLS (block, bot, sym) > { > - sym = BLOCK_SYM (block, bot); > switch (SYMBOL_CLASS (sym)) > { > case LOC_STATIC: > @@ -2795,10 +2810,9 @@ search_symbols (char *regexp, namespace_ > struct symbol_search *prevtail = tail; > int nfound = 0; > b = BLOCKVECTOR_BLOCK (bv, i); > - for (j = 0; j < BLOCK_NSYMS (b); j++) > + ALL_BLOCK_SYMBOLS (b, j, sym) > { > QUIT; > - sym = BLOCK_SYM (b, j); > if (file_matches (s->filename, files, nfiles) > && ((regexp == NULL || SYMBOL_MATCHES_REGEXP (sym)) > && ((kind == VARIABLES_NAMESPACE && SYMBOL_CLASS (sym) != LOC_TYPEDEF > Index: gdb/symtab.h > =================================================================== > RCS file: /cvs/src/src/gdb/symtab.h,v > retrieving revision 1.33 > diff -u -p -r1.33 symtab.h > --- gdb/symtab.h 28 Jun 2002 22:09:11 -0000 1.33 > +++ gdb/symtab.h 11 Jul 2002 00:14:27 -0000 > @@ -386,6 +386,10 @@ struct block > > unsigned char gcc_compile_flag; > > + /* If this is really a hashtable of the symbols, this flag is 1. */ > + > + unsigned char hashtable; > + > /* Number of local symbols. */ > > int nsyms; > @@ -398,30 +402,35 @@ struct block > > #define BLOCK_START(bl) (bl)->startaddr > #define BLOCK_END(bl) (bl)->endaddr > -#define BLOCK_NSYMS(bl) (bl)->nsyms > -#define BLOCK_SYM(bl, n) (bl)->sym[n] > #define BLOCK_FUNCTION(bl) (bl)->function > #define BLOCK_SUPERBLOCK(bl) (bl)->superblock > #define BLOCK_GCC_COMPILED(bl) (bl)->gcc_compile_flag > +#define BLOCK_HASHTABLE(bl) (bl)->hashtable > > -/* Macro to loop through all symbols in a block BL. > - i counts which symbol we are looking at, and sym points to the current > - symbol. > - The contortion at the end is to avoid reading past the last valid > - BLOCK_SYM. */ > -#define ALL_BLOCK_SYMBOLS(bl, i, sym) \ > - for ((i) = 0, (sym) = BLOCK_SYM ((bl), (i)); \ > - (i) < BLOCK_NSYMS ((bl)); \ > - ++(i), (sym) = ((i) < BLOCK_NSYMS ((bl))) \ > - ? BLOCK_SYM ((bl), (i)) \ > - : NULL) > +/* For blocks without a hashtable (BLOCK_HASHTABLE (bl) == 0) only. */ > +#define BLOCK_NSYMS(bl) (bl)->nsyms > +#define BLOCK_SYM(bl, n) (bl)->sym[n] > + > +/* For blocks with a hashtable, but these are valid for non-hashed blocks as > + well - each symbol will appear to be one bucket by itself. */ > +#define BLOCK_BUCKETS(bl) (bl)->nsyms > +#define BLOCK_BUCKET(bl, n) (bl)->sym[n] > + > +/* Macro to loop through all symbols in a block BL, in no particular order. > + i counts which bucket we are in, and sym points to the current symbol. */ > + > +#define ALL_BLOCK_SYMBOLS(bl, i, sym) \ > + for ((i) = 0; (i) < BLOCK_BUCKETS ((bl)); (i)++) \ > + for ((sym) = BLOCK_BUCKET ((bl), (i)); (sym); \ > + (sym) = (sym)->hash_next) > > /* Nonzero if symbols of block BL should be sorted alphabetically. > Don't sort a block which corresponds to a function. If we did the > sorting would have to preserve the order of the symbols for the > - arguments. */ > + arguments. Also don't sort any block that we chose to hash. */ > > -#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl) == NULL) > +#define BLOCK_SHOULD_SORT(bl) (! BLOCK_HASHTABLE (bl) \ > + && BLOCK_FUNCTION (bl) == NULL) > > > /* Represent one symbol name; a variable, constant, function or typedef. */ > @@ -671,6 +680,8 @@ struct symbol > /* List of ranges where this symbol is active. This is only > used by alias symbols at the current time. */ > struct range_list *ranges; > + > + struct symbol *hash_next; > }; > >