[RFA] convert blocks to dictionaries, phase 1, main part

[David Carlton <carlton at math dot stanford dot edu>]

This is the first of three patches that will begin the process of
converting blocks to do variable lookup via dictionaries.  (Which are
what I'd been calling environments until Andrew noted that that
clashed with the existing 'struct environ'.)

The goal of these three patches it to make sure that all blocks that
are created have a 'dict' member.  Once these patches are applied, it
will be possible to lookup variables either using the old methods
(BLOCK_SYM, etc.) or using the new dictionary methods.  Phase 2 will
then convert all accessors over to using th new dictionary methods;
phase 3 will get rid of the old methods so that the new dictionary
methods get used exclusively.

The patches in this e-mail cover the core code: they introduce the new
dictionary creation stuff necessary to carry out phase 1 (introducing
a new file dictionary.c and adding declarations to symtab.h), and
modify buildsym.c to initialize initialize BLOCK_DICT properly.  In my
next two e-mails, I'll submit patches to jv-lang.c and to mdebugread.c;
those are special cases, so they might as well be forked out
separately.

Note that I'm not including all of the new accessor methods and
dictionary creation functions in this patch: I'm only including enough
to get phase 1 completed.  If you want to see what all that stuff will
look like, it's in
<http://sources.redhat.com/ml/gdb-patches/2002-09/msg00202.html>.
Doing things this way has the advantage that I'm not submitting code
that hasn't been run through the testsuite.

I've run this through the testsuite; no new regressions.

David Carlton
carlton@math.stanford.edu

2002-09-16  David Carlton  <carlton@math.stanford.edu>

	* mdebugread.c: Delete 'maxsyms' member of parse_stack.
	(new_block): Remove argument.
	(new_symtab): Remove 'maxsyms' argument.
	(parse_symbol): Update calls to new_block.
	(parse_procedure): Ditto.
	(fixup_sigtramp): Ditto.
	(psymtab_to_symtab_1): Update calls to new_symtab; don't set
	maxsyms.
	(shrink_block): Comment out entire function.
	(parse_symbol): Remove calls to shrink_block.
	(add_symbol): Add symbol via DICT_TEMP_add_block_symbol.
	(parse_symbol): Initialize BLOCK_DICT (b) after creating new
	blocks.
	(parse_procedure): Ditto.
	(new_symtab): Ditto.
	(fixup_sigtramp): Ditto.
	* jv-lang.c (get_java_class_symtab): Initialize the BLOCK_DICT of
	the static and global blocks.
	(add_class_symtab_symbol): Add symbol via
	DICT_TEMP_add_block_symbol.
	Delete variable class_symtab_space.
	* buildsym.c (finish_block): Initialize BLOCK_DICT (block).
	* Makefile.in: Add source file dictionary.c.
	* dictionary.c: New file.
	* symtab.h: Add 'dict' member to struct block, and add initial
	dictionary-related declarations.

Index: Makefile.in
===================================================================
RCS file: /cvs/src/src/gdb/Makefile.in,v
retrieving revision 1.258
diff -u -p -r1.258 Makefile.in
--- Makefile.in	14 Sep 2002 02:09:39 -0000	1.258
+++ Makefile.in	16 Sep 2002 20:59:22 -0000
@@ -529,7 +529,8 @@ SFILES = ada-exp.y ada-lang.c ada-typepr
 	buildsym.c c-exp.y c-lang.c c-typeprint.c c-valprint.c \
 	coffread.c \
 	complaints.c completer.c corefile.c cp-valprint.c dbxread.c \
-	demangle.c dwarfread.c dwarf2read.c elfread.c environ.c eval.c \
+	demangle.c dictionary.c dwarfread.c \
+	dwarf2read.c elfread.c environ.c eval.c \
 	event-loop.c event-top.c \
 	expprint.c f-exp.y f-lang.c f-typeprint.c f-valprint.c \
 	findvar.c regcache.c gdbarch.c arch-utils.c gdbtypes.c osabi.c \
@@ -820,7 +821,7 @@ TAGFILES_WITH_SRCDIR = $(HFILES_WITH_SRC
 COMMON_OBS = version.o blockframe.o breakpoint.o findvar.o regcache.o \
 	source.o values.o eval.o valops.o valarith.o valprint.o printcmd.o \
 	symtab.o symfile.o symmisc.o linespec.o infcmd.o infrun.o \
-	expprint.o environ.o stack.o thread.o \
+	dictionary.o expprint.o environ.o stack.o thread.o \
 	macrotab.o macrocmd.o macroexp.o macroscope.o \
 	event-loop.o event-top.o inf-loop.o completer.o \
 	gdbarch.o arch-utils.o gdbtypes.o osabi.o copying.o $(DEPFILES) \
@@ -1619,6 +1620,8 @@ dcache.o: dcache.c $(defs_h) $(dcache_h)
 delta68-nat.o: delta68-nat.c $(defs_h)
 demangle.o: demangle.c $(defs_h) $(command_h) $(gdbcmd_h) $(demangle_h) \
 	$(gdb_string_h)
+dictionary.o: $(defs_h) $(gdb_obstack_h) $(symtab_h) $(buildsym_h) \
+	$(gdb_assert_h)
 dink32-rom.o: dink32-rom.c $(defs_h) $(gdbcore_h) $(target_h) $(monitor_h) \
 	$(serial_h) $(symfile_h) $(inferior_h) $(regcache_h)
 doublest.o: doublest.c $(defs_h) $(doublest_h) $(floatformat_h) \

Index: symtab.h
===================================================================
RCS file: /cvs/src/src/gdb/symtab.h,v
retrieving revision 1.39
diff -u -p -r1.39 symtab.h
--- symtab.h	12 Sep 2002 19:19:37 -0000	1.39
+++ symtab.h	16 Sep 2002 20:59:13 -0000
@@ -25,6 +25,7 @@
 
 /* Opaque declarations.  */
 struct obstack;
+struct dictionary;
 
 /* Don't do this; it means that if some .o's are compiled with GNU C
    and some are not (easy to do accidentally the way we configure
@@ -373,6 +374,11 @@ struct block
 
   struct block *superblock;
 
+  /* The dictionary for looking up the symbols associated to names in
+     this block.  */
+
+  struct dictionary *dict;
+
   /* Version of GCC used to compile the function corresponding
      to this block, or 0 if not compiled with GCC.  When possible,
      GCC should be compatible with the native compiler, or if that
@@ -385,6 +391,9 @@ struct block
 
   unsigned char gcc_compile_flag;
 
+  /* FIXME: carlton/2002-09-16: the rest of the members will be
+     deleted once the transition to dictionaries is finished.  */
+
   /* 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
@@ -418,6 +427,7 @@ struct block
 #define BLOCK_END(bl)		(bl)->endaddr
 #define BLOCK_FUNCTION(bl)	(bl)->function
 #define BLOCK_SUPERBLOCK(bl)	(bl)->superblock
+#define BLOCK_DICT(bl)		(bl)->dict
 #define BLOCK_GCC_COMPILED(bl)	(bl)->gcc_compile_flag
 #define BLOCK_HASHTABLE(bl)	(bl)->hashtable
 
@@ -1418,5 +1428,36 @@ extern struct cleanup *make_cleanup_free
    const. */
 extern void set_main_name (const char *name);
 extern /*const */ char *main_name (void);
+
+/* Code for manipulating dictionaries.  These are used to look up the
+   symbols associated to a name.  They are represented by an opaque
+   type 'struct dictionary'.  */
+
+/* FIXME: carlton/2002-09-16: I'm adding in prototypes, etc. only as
+   needed in the patches I'm submitting, so the following list may
+   seem a bit scant.  */
+
+/* FIXME: carlton/2002-09-11: Names that start with DICT_TEMP are
+   intended to be relatively ephemeral; they'll all be deleted once
+   the transition to dictionaries is completed.  */
+
+/* The functions for creating various types of dictionaries.  */
+
+/* Create an dictionary implemented via a struct block.  */
+
+extern struct dictionary *DICT_TEMP_create_block (struct block *block);
+
+/* Create an dictionary implemented via a struct block that can grow
+   if necessary.  The dictionary is initially empty; to add symbols to
+   it, call DICT_TEMP_add_block_symbol().  */
+
+extern struct dictionary *DICT_TEMP_create_block_expandable (struct block
+							     *block);
+/* Add a symbol to an DICT_TEMP_block_expandable.  Returns the
+   associated block (which may get moved during the call in
+   question).  */
+
+extern struct block *DICT_TEMP_add_block_symbol (struct dictionary *dict,
+						 struct symbol *sym);
 
 #endif /* !defined(SYMTAB_H) */

--- /dev/null	Thu Apr 11 07:25:15 2002
+++ dictionary.c	Mon Sep 16 10:44:58 2002
@@ -0,0 +1,200 @@
+/* Routines for name->symbol translation in GDB.
+   
+   Copyright 2002 Free Software Foundation, Inc.
+
+   Contributed by David Carlton <carlton@bactrian.org>.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or (at
+   your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#include "defs.h"
+#include "gdb_obstack.h"
+#include "symtab.h"
+#include "buildsym.h"
+#include "gdb_assert.h"
+
+/* FIXME: carlton/2002-09-11: Names that start with DICT_TEMP are
+   intended to be relatively ephemeral; they'll all be deleted once
+   the transition to dictionaries is completed.  */
+
+/* There are various different implementations of dictionaries, all
+   accessible to the outside world via an opaque 'struct dictionary'.
+   Given that goal, and the (admittedly less important) goal not to
+   have unnecessary pointers within the data structure, the simplest
+   way to handle this seems to be to have struct dictionary have a
+   single member, which is a union of structs giving all of the
+   different implementations; each of those structs starts off with an
+   'dict_type' member which tells you what member of the union to
+   actually look at.  */
+
+/* These are the different types of implementations.  */
+
+/* FIXME: carlton/2002-09-16: I'll include the code for the various
+   implementations once they become necessary, but this enum gives you
+   a preview as to what there will be.  */
+
+enum dict_type
+  {
+    /* Symbols are stored in a (fixed-size) hash table.  */
+    DICT_HASHED,
+    /* Symbols are stored in a (fixed-size) array.  */
+    DICT_LINEAR,
+    /* Symbols are stored in an expandable array.  */
+    DICT_LINEAR_EXPANDABLE,
+    /* Symbols are stored in a struct block.  */
+    DICT_TEMP_BLOCK,
+    /* Symbols are stored in a struct block that can expand.  */
+    DICT_TEMP_BLOCK_EXPANDABLE,
+  };
+
+/* These are the data structures holding the implementations
+   themselves.  */
+
+/* In this implementation, symbols are stored in a struct block.  */
+
+struct DICT_TEMP_dictionary_block
+{
+  struct block *block;
+};
+
+/* In this implementation, symbols are stored in a struct block that
+   can expand.  */
+
+struct DICT_TEMP_dictionary_block_expandable
+{
+  struct block *block;
+  int capacity;
+};
+
+/* See comments before the definition of enum dict_type for a
+   discussion on the multiplicity of implementations.  */
+
+/* NOTE: carlton/2002-09-12: At some point, I considered having struct
+   dictionary be a struct containing one data member that was a union
+   of implementation structs, each of which started with the data
+   that's common to all implementations (currently just
+   implementation_type).  The advantage to that is that then the
+   dictionary creation functions could allocate just enough space to
+   store the current implementation, rather than enough space to store
+   the largest possible implementation.  The disavantage is that it's
+   theoretically slightly nonportable and makes it a bit more
+   tedious/error-prone to add new common data in the future.  Given
+   the small amount of wasted space, the disadvantages of that method
+   seemed to outweigh the benefits.  */
+
+struct dictionary
+{
+  enum dict_type implementation_type;
+  union
+  {
+    struct DICT_TEMP_dictionary_block DICT_TEMP_block;
+    struct DICT_TEMP_dictionary_block_expandable DICT_TEMP_block_expandable;
+  }
+  data;
+};
+
+/* Accessor macros.  */
+
+#define DICT_TYPE(d)		(d)->implementation_type
+
+/* This can be used on block_expandable dictionaries, too.  */
+
+#define DICT_TEMP_BLOCK_BLOCK(d)		(d)->data.DICT_TEMP_block.block
+
+#define DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY(d)	\
+	(d)->data.DICT_TEMP_block_expandable.capacity
+
+/* This is the initial capacity for linear_expandable dictionaries.
+   (And it's also the capacity for block_expandable dictiroments once
+   a single symbol has been added to them.)  */
+
+#define DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY	10
+
+/* Create an dictionary implemented via a struct block.
+   
+   This has a memory leak: the memory allocated via it never gets
+   freed.  (Unless the calling code calls dict_free(), which is
+   unlikely.)  But given that this implementation of dictionaries will
+   go away once the transition to dictionaries is finished and given
+   that, in practice, the amount of memory leaked will be very small,
+   I'm not inclined to fix that (e.g. by allocating on the same
+   obstack used for the argument).  */
+
+struct dictionary *
+DICT_TEMP_create_block (struct block *block)
+{
+  struct dictionary *retval;
+
+  retval = xmalloc (sizeof (struct dictionary));
+  DICT_TYPE (retval) = DICT_TEMP_BLOCK;
+  DICT_TEMP_BLOCK_BLOCK (retval) = block;
+
+  return retval;
+}
+
+/* Create an dictionary implemented via a struct block that can grow
+   if necessary.  The dictionary is initially empty; to add symbols to
+   it, call DICT_TEMP_add_block_symbol().
+
+   As with DICT_TEMP_create_block(), this has an unimportant memory
+   leak.  */
+
+struct dictionary *
+DICT_TEMP_create_block_expandable (struct block *block)
+{
+  struct dictionary *retval;
+
+  retval = xmalloc (sizeof (struct dictionary));
+  DICT_TYPE (retval) = DICT_TEMP_BLOCK_EXPANDABLE;
+  DICT_TEMP_BLOCK_BLOCK (retval) = block;
+
+  /* Set capacity to 0; the first call to DICT_TEMP_add_block_symbol()
+     will resize the block.  */
+  DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (retval) = 0;
+
+  return retval;
+}
+
+/* Add a symbol to an DICT_TEMP_block_expandable.  Returns the
+   associated block (which may get moved during the call in
+   question).  */
+
+struct block *
+DICT_TEMP_add_block_symbol (struct dictionary *dict,
+			    struct symbol *sym)
+{
+  gdb_assert (DICT_TYPE (dict) == DICT_TEMP_BLOCK_EXPANDABLE);
+
+  int nsyms = ++BLOCK_NSYMS (DICT_TEMP_BLOCK_BLOCK (dict));
+
+  /* Do we have enough room?  If not, grow it.  */
+  if (nsyms > DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (dict)) {
+    DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (dict)
+      = (DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (dict)
+	 ? 2 * DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (dict)
+	 : DICT_LINEAR_EXPANDABLE_INITIAL_CAPACITY);
+    DICT_TEMP_BLOCK_BLOCK (dict)
+      = xrealloc (DICT_TEMP_BLOCK_BLOCK (dict),
+		  sizeof (struct block)
+		  + ((DICT_TEMP_BLOCK_EXPANDABLE_CAPACITY (dict) - 1)
+		     * sizeof (struct symbol *)));
+  }
+
+  BLOCK_SYM (DICT_TEMP_BLOCK_BLOCK (dict), nsyms - 1) = sym;
+
+  return DICT_TEMP_BLOCK_BLOCK (dict);
+}

Index: buildsym.c
===================================================================
RCS file: /cvs/src/src/gdb/buildsym.c,v
retrieving revision 1.20
diff -u -p -r1.20 buildsym.c
--- buildsym.c	10 Sep 2002 23:45:26 -0000	1.20
+++ buildsym.c	16 Sep 2002 20:59:34 -0000
@@ -294,6 +294,7 @@ finish_block (struct symbol *symbol, str
   BLOCK_END (block) = end;
   /* Superblock filled in when containing block is made */
   BLOCK_SUPERBLOCK (block) = NULL;
+  BLOCK_DICT (block) = DICT_TEMP_create_block (block);
 
   BLOCK_GCC_COMPILED (block) = processing_gcc_compilation;