[intercu] Use a hash table for DIEs after all

[Daniel Jacobowitz <drow at false dot org>]

It turns out the splay tree was really not being efficient.  For a mostly
sorted access pattern, and strictly sorted addition, trees are about your
worst-case data structure.  The hash table seems to do much better.

Committed to the intercu branch.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

2004-02-21  Daniel Jacobowitz  <drow@mvista.com>

	* Makefile.in (hashtab_h): Add.
	(dwarf2read.o): Update dependencies.
	* dwarf2read.c: Include "hashtab.h".
	(struct dwarf2_cu): Change partial_dies to an htab_t.
	(hash_obstack_allocate, partial_die_hash, partial_die_eq): New
	functions.
	(dwarf2_build_psymtabs_hard): Call htab_create_alloc_ex.
	(load_partial_dies): Call htab_find_slot_with_hash.
	(find_partial_die): Call htab_find_with_hash.

Index: Makefile.in
===================================================================
RCS file: /cvs/src/src/gdb/Makefile.in,v
retrieving revision 1.512.2.1
diff -u -p -r1.512.2.1 Makefile.in
--- Makefile.in	21 Feb 2004 20:17:22 -0000	1.512.2.1
+++ Makefile.in	21 Feb 2004 20:47:59 -0000
@@ -583,6 +583,7 @@ gdb_sim_d10v_h = $(INCLUDE_DIR)/gdb/sim-
 gdb_sim_frv_h = $(INCLUDE_DIR)/gdb/sim-frv.h
 gdb_sim_sh_h =	$(INCLUDE_DIR)/gdb/sim-sh.h
 splay_tree_h =  $(INCLUDE_DIR)/splay-tree.h
+hashtab_h =    $(INCLUDE_DIR)/hashtab.h
 
 readline_headers = \
 	$(READLINE_SRC)/chardefs.h \
@@ -1707,7 +1708,7 @@ dwarf2read.o: dwarf2read.c $(defs_h) $(b
 	$(expression_h) $(filenames_h) $(macrotab_h) $(language_h) \
 	$(complaints_h) $(bcache_h) $(dwarf2expr_h) $(dwarf2loc_h) \
 	$(cp_support_h) $(gdb_string_h) $(gdb_assert_h) \
-	$(splay_tree_h)
+	$(splay_tree_h) $(hashtab_h)
 dwarfread.o: dwarfread.c $(defs_h) $(symtab_h) $(gdbtypes_h) $(objfiles_h) \
 	$(elf_dwarf_h) $(buildsym_h) $(demangle_h) $(expression_h) \
 	$(language_h) $(complaints_h) $(gdb_string_h)
Index: dwarf2read.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarf2read.c,v
retrieving revision 1.135.2.5
diff -u -p -r1.135.2.5 dwarf2read.c
--- dwarf2read.c	21 Feb 2004 20:46:11 -0000	1.135.2.5
+++ dwarf2read.c	21 Feb 2004 20:48:00 -0000
@@ -45,6 +45,7 @@
 #include "dwarf2loc.h"
 #include "cp-support.h"
 #include "splay-tree.h"
+#include "hashtab.h"
 
 #include <fcntl.h>
 #include "gdb_string.h"
@@ -260,7 +261,7 @@ struct dwarf2_cu
      fundamental types gdb knows how to construct.  */
   struct type *ftypes[FT_NUM_MEMBERS];	/* Fundamental types */
 
-  splay_tree partial_dies;
+  htab_t partial_dies;
   struct obstack partial_die_obstack;
 };
 
@@ -954,6 +955,30 @@ splay_tree_obstack_deallocate (void *obj
   return;
 }
 
+static void *
+hash_obstack_allocate (void *data, size_t size, size_t count)
+{
+  unsigned int total = size * count;
+  void *ptr = obstack_alloc ((struct obstack *) data, total);
+  memset (ptr, 0, total);
+  return ptr;
+}
+
+static hashval_t
+partial_die_hash (const void *item)
+{
+  const struct partial_die_info *part_die = item;
+  return part_die->offset;
+}
+
+static int
+partial_die_eq (const void *item_lhs, const void *item_rhs)
+{
+  const struct partial_die_info *part_die_lhs = item_lhs;
+  const struct partial_die_info *part_die_rhs = item_rhs;
+  return part_die_lhs->offset == part_die_rhs->offset;
+}
+
 /* Try to locate the sections we need for DWARF 2 debugging
    information and return true if we have enough to do something.  */
 
@@ -1318,10 +1343,12 @@ dwarf2_build_psymtabs_hard (struct objfi
 
 	  obstack_init (&cu.partial_die_obstack);
 	  cu.partial_dies
-	    = splay_tree_new_with_allocator (splay_tree_compare_ints, NULL,
-					     NULL, splay_tree_obstack_allocate,
-					     splay_tree_obstack_deallocate,
-					     &cu.partial_die_obstack);
+	    = htab_create_alloc_ex (29, partial_die_hash,
+				    partial_die_eq,
+				    NULL,
+				    &cu.partial_die_obstack,
+				    hash_obstack_allocate,
+				    splay_tree_obstack_deallocate);
 
 	  load_partial_dies (abfd, info_ptr, &cu);
 
@@ -4501,6 +4528,7 @@ load_partial_dies (bfd *abfd, char *info
   struct partial_die_info *parent_die, *last_die;
   struct abbrev_info *abbrev;
   unsigned int bytes_read;
+  void **slot;
 
   /* FIXME: Obviously we need a nesting level passed in for incremental use.  */
   int nesting_level = 1;
@@ -4559,8 +4587,10 @@ load_partial_dies (bfd *abfd, char *info
       last_die = part_die;
 
       //      fprintf_unfiltered (gdb_stderr, "Inserting DIE %x\n", part_die->offset);
-      splay_tree_insert (cu->partial_dies, part_die->offset,
-			 (splay_tree_value) part_die);
+      slot = htab_find_slot_with_hash (cu->partial_dies, part_die,
+				       part_die->offset, INSERT);
+      // gdb_assert (*slot == NULL);
+      *slot = part_die;
 
       part_die = obstack_alloc (&cu->partial_die_obstack,
 				sizeof (struct partial_die_info));
@@ -4714,14 +4744,16 @@ static struct partial_die_info *
 find_partial_die (unsigned long offset, struct dwarf2_cu *cu)
 {
   struct partial_die_info *lookup_die = NULL;
-  splay_tree_node node;
+  struct partial_die_info part_die;
 
-  node = splay_tree_lookup (cu->partial_dies, offset);
-  if (node == NULL)
+  part_die.offset = offset;
+  lookup_die = htab_find_with_hash (cu->partial_dies, &part_die, offset);
+  
+  if (lookup_die == NULL)
     internal_error (__FILE__, __LINE__,
 		    "could not find partial DIE in cache\n");
 
-  return (struct partial_die_info *) node->value;
+  return lookup_die;
 }
 
 static void