2002-07-11 Daniel Jacobowitz <drow@mvista.com>

	Based on patch from Daniel Berlin <dberlin@dberlin.org>.
	* 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.  Comment the
	hashtable.
	(BLOCK_HASHTABLE, BLOCK_BUCKETS, BLOCK_BUCKET): New macro.
	(ALL_BLOCK_SYMBOLS): Update.
	(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.

1 files changed, 44 insertions, 15 deletions

diff --git a/gdb/symtab.h b/gdb/symtab.h
index 713dd0d..6ea5538 100644
--- a/gdb/symtab.h
+++ b/gdb/symtab.h
@@ -386,6 +386,25 @@ struct block
 
     unsigned char gcc_compile_flag;
 
+    /* The symbols for this block are either in a simple linear list or
+       in a simple hashtable.  Blocks which correspond to a function
+       (which have a list of symbols corresponding to arguments) use
+       a linear list, as do some older symbol readers (currently only
+       mdebugread and dstread).  Other blocks are hashed.
+
+       The hashtable uses the same hash function as the minsym hashtables,
+       found in minsyms.c:minsym_hash_iw.  Symbols are hashed based on
+       their demangled name if appropriate, and on their name otherwise.
+       The hash function ignores space, and stops at the beginning of the
+       argument list if any.
+
+       The table is laid out in NSYMS/5 buckets and symbols are chained via
+       their hash_next field.  */
+
+    /* If this is really a hashtable of the symbols, this flag is 1.  */
+
+    unsigned char hashtable;
+
     /* Number of local symbols.  */
 
     int nsyms;
@@ -398,30 +417,38 @@ 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 used to set the size of a hashtable for N symbols.  */
+#define BLOCK_HASHTABLE_SIZE(n)	((n)/5 + 1)
+
+/* 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 +698,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;
   };