2003-02-19 David Carlton <carlton@math.stanford.edu>

	* mdebugread.c (new_block): Add 'function' arg.
	(parse_symbol): New arg to new_block.
	(new_symtab): Ditto.
	(fixup_sigtramp): Ditto.
	* cp-support.c (initialize_namespace_blocks): Use
	dict_hashed_expandable instead of dict_linear_expandable.
	* jv-lang.c (get_java_class_symtab): Ditto.
	* dictionary.c (enum dict_type): Add DICT_HASHED_EXPANDABLE.
	(struct dictionary_hashed_expandable): New.
	(struct dictionary): Add hashed_expandable member.
	(DICT_EXPANDABLE_INITIAL_CAPACITY): Rename from
	DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY.
	(dict_create_linear_expandable): Use
	DICT_EXPANDABLE_INITIAL_CAPACITY.
	(dict_linear_vtbl): New.
	(dict_create_hashed_expandable): New.
	(add_symbol_hashed_expandable): New.
	(dict_create_hashed): Move code into insert_symbol_hashed.
	(insert_symbol_hashed): New.
	(expand_hashtable): New.
	* dictionary.h: Declare dict_create_hashed_expandable.

6 files changed, 190 insertions, 41 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 817f79e5170..fb4a3560c20 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,27 @@
+2003-02-19  David Carlton  <carlton@math.stanford.edu>
+
+	* mdebugread.c (new_block): Add 'function' arg.
+	(parse_symbol): New arg to new_block.
+	(new_symtab): Ditto.
+	(fixup_sigtramp): Ditto.
+	* cp-support.c (initialize_namespace_blocks): Use
+	dict_hashed_expandable instead of dict_linear_expandable.
+	* jv-lang.c (get_java_class_symtab): Ditto.
+	* dictionary.c (enum dict_type): Add DICT_HASHED_EXPANDABLE.
+	(struct dictionary_hashed_expandable): New.
+	(struct dictionary): Add hashed_expandable member.
+	(DICT_EXPANDABLE_INITIAL_CAPACITY): Rename from
+	DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY.
+	(dict_create_linear_expandable): Use
+	DICT_EXPANDABLE_INITIAL_CAPACITY.
+	(dict_linear_vtbl): New.
+	(dict_create_hashed_expandable): New.
+	(add_symbol_hashed_expandable): New.
+	(dict_create_hashed): Move code into insert_symbol_hashed.
+	(insert_symbol_hashed): New.
+	(expand_hashtable): New.
+	* dictionary.h: Declare dict_create_hashed_expandable.
+
 2003-02-12  David Carlton  <carlton@math.stanford.edu>
 
 	* linespec.c (examine_compound_token): Call decode_namespace.
diff --git a/gdb/cp-support.c b/gdb/cp-support.c
index a32b1832a70..7858eb7533c 100644
--- a/gdb/cp-support.c
+++ b/gdb/cp-support.c
@@ -429,7 +429,7 @@ initialize_namespace_blocks (void)
 
   /* Allocate GLOBAL_BLOCK, which is namespace_block.  */
   bl = allocate_block (&objfile->symbol_obstack);
-  BLOCK_DICT (bl) = dict_create_linear_expandable ();
+  BLOCK_DICT (bl) = dict_create_hashed_expandable ();
   BLOCKVECTOR_BLOCK (bv, GLOBAL_BLOCK) = bl;
   namespace_block = bl;
 
@@ -438,7 +438,7 @@ initialize_namespace_blocks (void)
      pretend that it's actually a local block (e.g. by setting
      BLOCK_SUPERBLOCK appropriately).  */
   bl = allocate_block (&objfile->symbol_obstack);
-  BLOCK_DICT (bl) = dict_create_linear_expandable ();
+  BLOCK_DICT (bl) = dict_create_hashed_expandable ();
   BLOCKVECTOR_BLOCK (bv, 2) = bl;
   possible_namespace_block = bl;
 
diff --git a/gdb/dictionary.c b/gdb/dictionary.c
index be8bb578310..15b8ac02c3e 100644
--- a/gdb/dictionary.c
+++ b/gdb/dictionary.c
@@ -102,9 +102,11 @@
 
 enum dict_type
   {
-    /* Symbols are stored in a (fixed-size) hash table.  */
+    /* Symbols are stored in a fixed-size hash table.  */
     DICT_HASHED,
-    /* Symbols are stored in a (fixed-size) array.  */
+    /* Symbols are stored in an expandable hash table.  */
+    DICT_HASHED_EXPANDABLE,
+    /* Symbols are stored in a fixed-size array.  */
     DICT_LINEAR,
     /* Symbols are stored in an expandable array.  */
     DICT_LINEAR_EXPANDABLE,
@@ -144,6 +146,16 @@ struct dictionary_hashed
   struct symbol **buckets;
 };
 
+struct dictionary_hashed_expandable
+{
+  /* How many buckets we currently have.  */
+  int nbuckets;
+  struct symbol **buckets;
+  /* How many syms we currently have; we need this so we will know
+     when to add more buckets.  */
+  int nsyms;
+};
+
 struct dictionary_linear
 {
   int nsyms;
@@ -171,6 +183,7 @@ struct dictionary
   union
   {
     struct dictionary_hashed hashed;
+    struct dictionary_hashed_expandable hashed_expandable;
     struct dictionary_linear linear;
     struct dictionary_linear_expandable linear_expandable;
   }
@@ -181,10 +194,14 @@ struct dictionary
 
 #define DICT_VTBL(d)			(d)->vtbl
 
+/* These can be used for DICT_HASHED_EXPANDABLE, too.  */
+
 #define DICT_HASHED_NBUCKETS(d)		(d)->data.hashed.nbuckets
 #define DICT_HASHED_BUCKETS(d)		(d)->data.hashed.buckets
 #define DICT_HASHED_BUCKET(d,i)		DICT_HASHED_BUCKETS (d) [i]
 
+#define DICT_HASHED_EXPANDABLE_NSYMS(d)	(d)->data.hashed_expandable.nsyms
+
 /* These can be used for DICT_LINEAR_EXPANDABLEs, too.  */
 
 #define DICT_LINEAR_NSYMS(d)		(d)->data.linear.nsyms
@@ -194,9 +211,9 @@ struct dictionary
 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
 		(d)->data.linear_expandable.capacity
 
-/* The initial size of a DICT_LINEAR_EXPANDABLE dictionary.  */
+/* The initial size of a DICT_*_EXPANDABLE dictionary.  */
 
-#define DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY 10
+#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
 
 /* This calculates the number of buckets we'll use in a hashtable,
    given the number of symbols that it will contain.  */
@@ -216,11 +233,6 @@ struct dictionary
    otherwise, this is unused.  */
 #define DICT_ITERATOR_CURRENT(iter)		(iter)->current
 
-/* Functions to handle some of the common code in dict_iterator_first and
-   dict_iterator_next.  */
-
-static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
-
 /* Declarations of functions for vtbls.  */
 
 /* Functions that might work across a range of dictionary types.  */
@@ -230,7 +242,8 @@ static void add_symbol_nonexpandable (struct dictionary *dict,
 
 static void free_obstack (struct dictionary *dict);
 
-/* Functions for DICT_HASHED dictionaries.  */
+/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
+   dictionaries.  */
 
 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 					     struct dict_iterator *iterator);
@@ -244,6 +257,13 @@ static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
 static struct symbol *iter_name_next_hashed (const char *name,
 					     struct dict_iterator *iterator);
 
+/* Functions only for DICT_HASHED_EXPANDABLE.  */
+
+static void free_hashed_expandable (struct dictionary *dict);
+
+static void add_symbol_hashed_expandable (struct dictionary *dict,
+					  struct symbol *sym);
+
 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
    dictionaries.  */
 
@@ -276,6 +296,14 @@ static const struct dict_vtbl dict_hashed_vtbl =
     iter_name_first_hashed, iter_name_next_hashed,
   };
 
+static const struct dict_vtbl dict_hashed_expandable_vtbl =
+  {
+    DICT_HASHED_EXPANDABLE, free_hashed_expandable,
+    add_symbol_hashed_expandable,
+    iterator_first_hashed, iterator_next_hashed,
+    iter_name_first_hashed, iter_name_next_hashed,
+  };
+
 static const struct dict_vtbl dict_linear_vtbl =
   {
     DICT_LINEAR, free_obstack,  add_symbol_nonexpandable,
@@ -291,6 +319,16 @@ static const struct dict_vtbl dict_linear_expandable_vtbl =
     iter_name_first_linear, iter_name_next_linear,
   };
 
+/* Declarations of helper functions (i.e. ones that don't go into
+   vtbls).  */
+
+static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
+
+static void insert_symbol_hashed (struct dictionary *dict,
+				  struct symbol *sym);
+
+static void expand_hashtable (struct dictionary *dict);
+
 /* The creation functions.  */
 
 /* Create a dictionary implemented via a fixed-size hashtable.  All
@@ -329,17 +367,33 @@ dict_create_hashed (struct obstack *obstack,
     {
       for (i = list_counter->nsyms - 1; i >= 0; --i)
 	{
-	  struct symbol *sym = list_counter->symbol[i];
-	  unsigned int hash_index;
-	  hash_index = msymbol_hash_iw (SYMBOL_BEST_NAME (sym)) % nbuckets;
-	  sym->hash_next = buckets[hash_index];
-	  buckets[hash_index] = sym;
+	  insert_symbol_hashed (retval, list_counter->symbol[i]);
 	}
     }
 
   return retval;
 }
 
+/* Create a dictionary implemented via a hashtable that grows as
+   necessary.  The dictionary is initially empty; to add symbols to
+   it, call dict_add_symbol().  Call dict_free() when you're done with
+   it.  */
+
+extern struct dictionary *
+dict_create_hashed_expandable (void)
+{
+  struct dictionary *retval;
+
+  retval = xmalloc (sizeof (struct dictionary));
+  DICT_VTBL (retval) = &dict_hashed_expandable_vtbl;
+  DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
+  DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
+					  sizeof (struct symbol *));
+  DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
+
+  return retval;
+}
+
 /* Create a dictionary implemented via a fixed-size array.  All memory
    it uses is allocated on OBSTACK; the environment is initialized
    from the SYMBOL_LIST.  The symbols are ordered in the same order
@@ -390,12 +444,6 @@ dict_create_linear (struct obstack *obstack,
    it, call dict_add_symbol().  Call dict_free() when you're done with
    it.  */
 
-/* FIXME: carlton/2002-09-11: This environment type exists only to
-   make mdebugread.c and jv-lang.c happy.  The former should be
-   converted over to the buildsym.c mechanisms (or made obsolete, I
-   suggest in an excess of optimism); the latter should perhaps be
-   rethought.  */
-
 struct dictionary *
 dict_create_linear_expandable (void)
 {
@@ -405,7 +453,7 @@ dict_create_linear_expandable (void)
   DICT_VTBL (retval) = &dict_linear_expandable_vtbl;
   DICT_LINEAR_NSYMS (retval) = 0;
   DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
-    = DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY;
+    = DICT_EXPANDABLE_INITIAL_CAPACITY;
   DICT_LINEAR_SYMS (retval)
     = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
 	       * sizeof (struct symbol *));
@@ -509,7 +557,7 @@ add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 		  "dict_add_symbol: non-expandable dictionary");
 }
 
-/* Functions for DICT_HASHED.  */
+/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 
 static struct symbol *
 iterator_first_hashed (const struct dictionary *dict,
@@ -610,6 +658,75 @@ iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
   return next;
 }
 
+/* Insert SYM into DICT.  */
+
+static void
+insert_symbol_hashed (struct dictionary *dict,
+		      struct symbol *sym)
+{
+  unsigned int hash_index;
+  struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
+
+  hash_index = (msymbol_hash_iw (SYMBOL_BEST_NAME (sym))
+		% DICT_HASHED_NBUCKETS (dict));
+  sym->hash_next = buckets[hash_index];
+  buckets[hash_index] = sym;
+}
+
+/* Functions only for DICT_HASHED_EXPANDABLE.  */
+
+static void
+free_hashed_expandable (struct dictionary *dict)
+{
+  xfree (DICT_HASHED_BUCKETS (dict));
+  xfree (dict);
+}
+
+static void
+add_symbol_hashed_expandable (struct dictionary *dict,
+			      struct symbol *sym)
+{
+  int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
+
+  if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
+    expand_hashtable (dict);
+
+  insert_symbol_hashed (dict, sym);
+  DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
+}
+
+static void
+expand_hashtable (struct dictionary *dict)
+{
+  int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
+  struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
+  int new_nbuckets = 2*old_nbuckets + 1;
+  struct symbol **new_buckets = xcalloc (new_nbuckets,
+					 sizeof (struct symbol *));
+  int i;
+
+  DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
+  DICT_HASHED_BUCKETS (dict) = new_buckets;
+
+  for (i = 0; i < old_nbuckets; ++i) {
+    struct symbol *sym, *next_sym;
+
+    sym = old_buckets[i];
+    if (sym != NULL) {
+      for (next_sym = sym->hash_next;
+	   next_sym != NULL;
+	   next_sym = sym->hash_next) {
+	insert_symbol_hashed (dict, sym);
+	sym = next_sym;
+      }
+
+      insert_symbol_hashed (dict, sym);
+    }
+  }
+
+  xfree (old_buckets);
+}
+
 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 
 static struct symbol *
diff --git a/gdb/dictionary.h b/gdb/dictionary.h
index 87b61afd0a7..65e69cf5057 100644
--- a/gdb/dictionary.h
+++ b/gdb/dictionary.h
@@ -44,6 +44,13 @@ extern struct dictionary *dict_create_hashed (struct obstack *obstack,
 					      const struct pending
 					      *symbol_list);
 
+/* Create a dictionary implemented via a hashtable that grows as
+   necessary.  The dictionary is initially empty; to add symbols to
+   it, call dict_add_symbol().  Call dict_free() when you're done with
+   it.  */
+
+extern struct dictionary *dict_create_hashed_expandable (void);
+
 /* Create a dictionary implemented via a fixed-size array.  All memory
    it uses is allocated on OBSTACK; the environment is initialized
    from the SYMBOL_LIST.  The symbols are ordered in the same order
@@ -58,12 +65,6 @@ extern struct dictionary *dict_create_linear (struct obstack *obstack,
    it, call dict_add_symbol().  Call dict_free() when you're done with
    it.  */
 
-/* FIXME: carlton/2002-09-11: This environment type exists only to
-   make mdebugread.c and jv-lang.c happy.  The former should be
-   converted over to the buildsym.c mechanisms (or made obsolete, I
-   suggest in an excess of optimism); the latter should probably be
-   rethought.  */
-
 extern struct dictionary *dict_create_linear_expandable (void);
 
 
diff --git a/gdb/jv-lang.c b/gdb/jv-lang.c
index fd74ced401f..ffd61081366 100644
--- a/gdb/jv-lang.c
+++ b/gdb/jv-lang.c
@@ -122,7 +122,7 @@ get_java_class_symtab (void)
 
       /* Allocate GLOBAL_BLOCK.  */
       bl = allocate_block (&objfile->symbol_obstack);
-      BLOCK_DICT (bl) = dict_create_linear_expandable ();
+      BLOCK_DICT (bl) = dict_create_hashed_expandable ();
       BLOCKVECTOR_BLOCK (bv, GLOBAL_BLOCK) = bl;
       class_symtab->free_func = free_class_block;
     }
diff --git a/gdb/mdebugread.c b/gdb/mdebugread.c
index a6b6fd17599..f1bc7fe0066 100644
--- a/gdb/mdebugread.c
+++ b/gdb/mdebugread.c
@@ -285,7 +285,7 @@ static struct symbol *new_symbol (char *);
 
 static struct type *new_type (char *);
 
-static struct block *new_block (void);
+static struct block *new_block (int function);
 
 static struct symtab *new_symtab (char *, int, struct objfile *);
 
@@ -832,7 +832,7 @@ parse_symbol (SYMR *sh, union aux_ext *ax, char *ext_sh, int bigend,
 	TYPE_FLAGS (SYMBOL_TYPE (s)) |= TYPE_FLAG_PROTOTYPED;
 
       /* Create and enter a new lexical context */
-      b = new_block ();
+      b = new_block (1);
       SYMBOL_BLOCK_VALUE (s) = b;
       BLOCK_FUNCTION (b) = s;
       BLOCK_START (b) = BLOCK_END (b) = sh->value;
@@ -1163,7 +1163,7 @@ parse_symbol (SYMR *sh, union aux_ext *ax, char *ext_sh, int bigend,
 	}
 
       top_stack->blocktype = stBlock;
-      b = new_block ();
+      b = new_block (0);
       BLOCK_START (b) = sh->value + top_stack->procadr;
       BLOCK_SUPERBLOCK (b) = top_stack->cur_block;
       top_stack->cur_block = b;
@@ -4602,8 +4602,8 @@ new_symtab (char *name, int maxlines, struct objfile *objfile)
 
   /* All symtabs must have at least two blocks */
   BLOCKVECTOR (s) = new_bvect (2);
-  global_block = new_block ();
-  static_block = new_block ();
+  global_block = new_block (0);
+  static_block = new_block (0);
   BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK) = global_block;
   BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK) = static_block;
   BLOCK_SUPERBLOCK (static_block) = global_block;
@@ -4690,13 +4690,20 @@ new_bvect (int nblocks)
   return bv;
 }
 
-/* Allocate and zero a new block.  Set its BLOCK_DICT.  */
+/* Allocate and zero a new block, and set its BLOCK_DICT.  If function
+   is non-zero, assume the block is associated to a function, and make
+   sure that the symbols are stored linearly; otherwise, store them
+   hashed.  */
 
 static struct block *
-new_block (void)
+new_block (int function)
 {
   struct block *retval = xzalloc (sizeof (struct block));
-  BLOCK_DICT (retval) = dict_create_linear_expandable ();
+
+  if (function)
+    BLOCK_DICT (retval) = dict_create_linear_expandable ();
+  else
+    BLOCK_DICT (retval) = dict_create_hashed_expandable ();
 
   return retval;
 }
@@ -4824,7 +4831,7 @@ fixup_sigtramp (void)
   TYPE_TARGET_TYPE (SYMBOL_TYPE (s)) = mdebug_type_void;
 
   /* Need a block to allocate MIPS_EFI_SYMBOL_NAME in */
-  b = new_block ();
+  b = new_block (0);
   SYMBOL_BLOCK_VALUE (s) = b;
   BLOCK_START (b) = sigtramp_address;
   BLOCK_END (b) = sigtramp_end;