From Tom Tromey <tromey@cygnus.com> and Keith Seitz <?>:

* minsyms.c: #include <ctype.h>, for msymbol_hash_iw.
(compact_minimal_symbols): Added `objfile' argument.
Put symbols in the objfile's hash table.
(install_minimal_symbols): Put symbols in the objfile's demangled
hash table.
(lookup_minimal_symbol): Use hash table to find symbol in
objfile.
(msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): New
functions.
(prim_record_minimal_symbol_and_info): Initialize the
hash link fields of the new minimal symbol.
* symtab.h (struct minimal_symbol): New fields `hash_next',
`demangled_hash_next'.
(msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): Declare.
* objfiles.h (MINIMAL_SYMBOL_HASH_SIZE): New define.
(struct objfile): New fields `msymbol_hash',
`msymbol_demangled_hash'.

4 files changed, 137 insertions, 8 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 8c6f5fdad6f..75e29b18351 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,5 +1,27 @@
 2000-03-06  Jim Blandy  <jimb@redhat.com>
 
+	From Tom Tromey <tromey@cygnus.com> and Keith Seitz <?>:
+
+	* minsyms.c: #include <ctype.h>, for msymbol_hash_iw.
+	(compact_minimal_symbols): Added `objfile' argument.
+	Put symbols in the objfile's hash table.
+	(install_minimal_symbols): Put symbols in the objfile's demangled
+	hash table.
+	(lookup_minimal_symbol): Use hash table to find symbol in
+	objfile.
+	(msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): New
+	functions.
+	(prim_record_minimal_symbol_and_info): Initialize the
+	hash link fields of the new minimal symbol.
+	* symtab.h (struct minimal_symbol): New fields `hash_next',
+	`demangled_hash_next'.
+	(msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): Declare.
+	* objfiles.h (MINIMAL_SYMBOL_HASH_SIZE): New define.
+	(struct objfile): New fields `msymbol_hash',
+	`msymbol_demangled_hash'.
+
+2000-03-06  Jim Blandy  <jimb@redhat.com>
+
 	* solib.c (first_link_map_member): Doc fix.
 
 2000-03-06  Elena Zannoni  <ezannoni@kwikemart.cygnus.com>
diff --git a/gdb/minsyms.c b/gdb/minsyms.c
index 30e0e77185c..9a083c0b522 100644
--- a/gdb/minsyms.c
+++ b/gdb/minsyms.c
@@ -39,6 +39,7 @@
 
 
 #include "defs.h"
+#include <ctype.h>
 #include "gdb_string.h"
 #include "symtab.h"
 #include "bfd.h"
@@ -78,7 +79,50 @@ static int
 compare_minimal_symbols PARAMS ((const void *, const void *));
 
 static int
-compact_minimal_symbols PARAMS ((struct minimal_symbol *, int));
+compact_minimal_symbols PARAMS ((struct minimal_symbol *, int,
+				 struct objfile *));
+
+/* Compute a hash code based using the same criteria as `strcmp_iw'.  */
+
+unsigned int
+msymbol_hash_iw (const char *string)
+{
+  unsigned int hash = 0;
+  while (*string && *string != '(')
+    {
+      while (isspace (*string))
+	++string;
+      if (*string && *string != '(')
+	hash = (31 * hash) + *string;
+      ++string;
+    }
+  return hash % MINIMAL_SYMBOL_HASH_SIZE;
+}
+
+/* Compute a hash code for a string.  */
+
+unsigned int
+msymbol_hash (const char *string)
+{
+  unsigned int hash = 0;
+  for (; *string; ++string)
+    hash = (31 * hash) + *string;
+  return hash % MINIMAL_SYMBOL_HASH_SIZE;
+}
+
+/* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE.  */
+void
+add_minsym_to_hash_table (struct minimal_symbol *sym,
+			  struct minimal_symbol **table)
+{
+  if (sym->hash_next == NULL)
+    {
+      unsigned int hash = msymbol_hash (SYMBOL_NAME (sym));
+      sym->hash_next = table[hash];
+      table[hash] = sym;
+    }
+}
+
 
 /* Look through all the current minimal symbol tables and find the
    first minimal symbol that matches NAME.  If OBJF is non-NULL, limit
@@ -103,6 +147,9 @@ lookup_minimal_symbol (name, sfile, objf)
   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);
+
 #ifdef SOFUN_ADDRESS_MAYBE_MISSING
   if (sfile != NULL)
     {
@@ -118,10 +165,13 @@ lookup_minimal_symbol (name, sfile, objf)
     {
       if (objf == NULL || objf == objfile)
 	{
-	  for (msymbol = objfile->msymbols;
-	       msymbol != NULL && SYMBOL_NAME (msymbol) != NULL &&
-	       found_symbol == NULL;
-	       msymbol++)
+	  /* Do two passes: the first over the ordinary hash table,
+	     and the second over the demangled hash table.  */
+	  int pass = 1;
+
+	  msymbol = objfile->msymbol_hash[hash];
+	  
+	  while (msymbol != NULL && found_symbol == NULL)
 	    {
 	      if (SYMBOL_MATCHES_NAME (msymbol, name))
 		{
@@ -159,6 +209,19 @@ lookup_minimal_symbol (name, sfile, objf)
 		      break;
 		    }
 		}
+
+	      /* Find the next symbol on the hash chain.  At the end
+		 of the first pass, try the demangled hash list.  */
+	      if (pass == 1)
+		msymbol = msymbol->hash_next;
+	      else
+		msymbol = msymbol->demangled_hash_next;
+	      if (msymbol == NULL)
+		{
+		  ++pass;
+		  if (pass == 2)
+		    msymbol = objfile->msymbol_demangled_hash[dem_hash];
+		}
 	    }
 	}
     }
@@ -603,6 +666,10 @@ prim_record_minimal_symbol_and_info (name, address, ms_type, info, section,
   MSYMBOL_TYPE (msymbol) = ms_type;
   /* FIXME:  This info, if it remains, needs its own field.  */
   MSYMBOL_INFO (msymbol) = info;	/* FIXME! */
+
+  msymbol->hash_next = NULL;
+  msymbol->demangled_hash_next = NULL;
+
   msym_bunch_index++;
   msym_count++;
   OBJSTAT (objfile, n_minsyms++);
@@ -672,6 +739,7 @@ discard_minimal_symbols (foo)
     }
 }
 
+
 /* Compact duplicate entries out of a minimal symbol table by walking
    through the table and compacting out entries with duplicate addresses
    and matching names.  Return the number of entries remaining.
@@ -709,9 +777,10 @@ discard_minimal_symbols (foo)
    overwrite its type with the type from the one we are compacting out.  */
 
 static int
-compact_minimal_symbols (msymbol, mcount)
+compact_minimal_symbols (msymbol, mcount, objfile)
      struct minimal_symbol *msymbol;
      int mcount;
+     struct objfile *objfile;
 {
   struct minimal_symbol *copyfrom;
   struct minimal_symbol *copyto;
@@ -734,6 +803,8 @@ compact_minimal_symbols (msymbol, mcount)
 	  else
 	    {
 	      *copyto++ = *copyfrom++;
+
+	      add_minsym_to_hash_table (copyto - 1, objfile->msymbol_hash);
 	    }
 	}
       *copyto++ = *copyfrom++;
@@ -826,7 +897,7 @@ install_minimal_symbols (objfile)
       /* Compact out any duplicates, and free up whatever space we are
          no longer using.  */
 
-      mcount = compact_minimal_symbols (msymbols, mcount);
+      mcount = compact_minimal_symbols (msymbols, mcount, objfile);
 
       obstack_blank (&objfile->symbol_obstack,
 	       (mcount + 1 - alloc_count) * sizeof (struct minimal_symbol));
@@ -860,6 +931,9 @@ install_minimal_symbols (objfile)
       for (; mcount-- > 0; msymbols++)
 	{
 	  SYMBOL_INIT_DEMANGLED_NAME (msymbols, &objfile->symbol_obstack);
+	  if (SYMBOL_DEMANGLED_NAME (msymbols) != NULL)
+	    add_minsym_to_hash_table (msymbols,
+				      objfile->msymbol_demangled_hash);
 	}
     }
 }
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index 98d45751e78..d1bd4dad2a8 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -1,5 +1,5 @@
 /* Definitions for symbol file management in GDB.
-   Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
+   Copyright (C) 1992, 1993, 1994, 1995, 1999 Free Software Foundation, Inc.
 
    This file is part of GDB.
 
@@ -200,6 +200,9 @@ struct objstats
 extern void print_objfile_statistics PARAMS ((void));
 extern void print_symbol_bcache_statistics PARAMS ((void));
 
+/* Number of entries in the minimal symbol hash table.  */
+#define MINIMAL_SYMBOL_HASH_SIZE 349
+
 /* Master structure for keeping track of each file from which
    gdb reads symbols.  There are several ways these get allocated: 1.
    The main symbol file, symfile_objfile, set by the symbol-file command,
@@ -292,6 +295,15 @@ struct objfile
     struct minimal_symbol *msymbols;
     int minimal_symbol_count;
 
+    /* This is a hash table used to index the minimal symbols by name.  */
+
+    struct minimal_symbol *msymbol_hash[MINIMAL_SYMBOL_HASH_SIZE];
+
+    /* This hash table is used to index the minimal symbols by their
+       demangled names.  */
+
+    struct minimal_symbol *msymbol_demangled_hash[MINIMAL_SYMBOL_HASH_SIZE];
+
     /* For object file formats which don't specify fundamental types, gdb
        can create such types.  For now, it maintains a vector of pointers
        to these internally created fundamental types on a per objfile basis,
diff --git a/gdb/symtab.h b/gdb/symtab.h
index 28d6e8ed5ff..efa18383912 100644
--- a/gdb/symtab.h
+++ b/gdb/symtab.h
@@ -357,10 +357,21 @@ struct minimal_symbol
 	mst_file_bss		/* Static version of mst_bss */
       }
     type BYTE_BITFIELD;
+
+    /* Minimal symbols with the same hash key are kept on a linked
+       list.  This is the link.  */
+
+    struct minimal_symbol *hash_next;
+
+    /* Minimal symbols are stored in two different hash tables.  This is
+       the `next' pointer for the demangled hash table.  */
+
+    struct minimal_symbol *demangled_hash_next;
   };
 
 #define MSYMBOL_INFO(msymbol)		(msymbol)->info
 #define MSYMBOL_TYPE(msymbol)		(msymbol)->type
+
 
 
 /* All of the name-scope contours of the program
@@ -1243,6 +1254,16 @@ extern CORE_ADDR find_stab_function_addr PARAMS ((char *,
 						  struct objfile *));
 #endif
 
+extern unsigned int
+msymbol_hash_iw PARAMS ((const char *));
+
+extern unsigned int
+msymbol_hash PARAMS ((const char *));
+
+extern void
+add_minsym_to_hash_table (struct minimal_symbol *sym,
+			  struct minimal_symbol **table);
+
 extern struct minimal_symbol *
   lookup_minimal_symbol PARAMS ((const char *, const char *, struct objfile *));