This is the mail archive of the gdb-patches@sources.redhat.com mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[RFA] delete BLOCK_SHOULD_SORT


I'd like to delete all occurences of BLOCK_SHOULD_SORT from GDB; it's
really no longer necessary, and will get in the way of my dictionary
work.

The history, as I understand it, is that formerly symbols in blocks
were always stored linearly; but, for blocks where the order didn't
matter, the symbols were sorted to improve search time.  Then blocks
using hashtables were introduced; these are now used almost everywhere
that sorted linear blocks had been previously used.  In particular,
blocks produced by buildsym.c, which is the vast majority of blocks,
will never satisfy BLOCK_SHOULD_SORT.

Right now, I believe that there are only two situations where blocks
satisfying BLOCK_SHOULD_SORT can be produced:

* jv-lang.c builds one such block.  However, despite its satisfying
  the BLOCK_SHOULD_SORT predicate, the block in question _isn't_
  sorted, leading to a special case in lookup_block_symbol().

* mdebugread.c hasn't been converted over to use the buildsym.c
  mechanisms, so it's still producing sorted blocks in some
  situations.

So, basically, making this change will get rid of some cruft, make an
unnoticeable speed improvement to symbol manipulation stuff for normal
usage, and when debugging ECOFF files, symbol table lookup will be a
bit slower.  (But it will still be correct: this is removing an
optimization, but the unoptimized behavior will still work.)  If
anybody out there actually uses ECOFF and is bothered by this, clearly
the best thing would be for that person to convert mdebugread.c to use
the mechanisms in buildsym.c just like every other debugging format
reader.

I think the changes are pretty straightforward, though I'd appreciate
it if somebody more conversant with ada-lang.c than I am could make
sure I'm not missing anything with my change there.

David Carlton
carlton@math.stanford.edu

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

	* symtab.h: Delete BLOCK_SHOULD_SORT.
	* symtab.c (lookup_block_symbol): Assume non-hashed blocks aren't
	sorted.
	* ada-lang.c (ada_add_block_symbols): Ditto.
	* symfile.h: Delete prototypes for sort_block_syms and
	sort_symtab_syms.
	* symfile.c: Delete functions sort_block_syms and
	sort_symtab_syms.
	* coffread.c (coff_symfile_read): Remove call to
	sort_symtab_syms.
	* xcoffread.c (xcoff_psymtab_to_symtab_1): Ditto.
	* mdebugread.c (psymtab_to_symtab_1): Ditto.
	* hpread.c (hpread_psymtab_to_symtab_1): Ditto.
	* dwarfread.c (psymtab_to_symtab_1): Ditto.
	* dwarf2read.c (psymtab_to_symtab_1): Ditto.
	* dbxread.c (dbx_psymtab_to_symtab_1): Ditto.

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	18 Sep 2002 20:56:48 -0000
@@ -441,13 +441,6 @@ struct block
 	  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.  Also don't sort any block that we chose to hash.  */
-
-#define BLOCK_SHOULD_SORT(bl) (! BLOCK_HASHTABLE (bl) \
-			       && BLOCK_FUNCTION (bl) == NULL)
 
 
 /* Represent one symbol name; a variable, constant, function or typedef.  */

Index: symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.69
diff -u -p -r1.69 symtab.c
--- symtab.c	30 Aug 2002 03:24:00 -0000	1.69
+++ symtab.c	18 Sep 2002 20:56:53 -0000
@@ -1334,10 +1334,9 @@ lookup_block_symbol (register const stru
 		     const char *mangled_name,
 		     const namespace_enum namespace)
 {
-  register int bot, top, inc;
+  register int bot, top;
   register struct symbol *sym;
   register struct symbol *sym_found = NULL;
-  register int do_linear_search = 1;
 
   if (BLOCK_HASHTABLE (block))
     {
@@ -1354,103 +1353,27 @@ lookup_block_symbol (register const stru
 	}
       return NULL;
     }
-
-  /* If the blocks's symbols were sorted, start with a binary search.  */
-
-  if (BLOCK_SHOULD_SORT (block))
-    {
-      /* Reset the linear search flag so if the binary search fails, we
-         won't do the linear search once unless we find some reason to
-         do so */
-
-      do_linear_search = 0;
-      top = BLOCK_NSYMS (block);
-      bot = 0;
-
-      /* Advance BOT to not far before the first symbol whose name is NAME. */
-
-      while (1)
-	{
-	  inc = (top - bot + 1);
-	  /* No need to keep binary searching for the last few bits worth.  */
-	  if (inc < 4)
-	    {
-	      break;
-	    }
-	  inc = (inc >> 1) + bot;
-	  sym = BLOCK_SYM (block, inc);
-	  if (!do_linear_search && (SYMBOL_LANGUAGE (sym) == language_java))
-	    {
-	      do_linear_search = 1;
-	    }
-	  if (SYMBOL_SOURCE_NAME (sym)[0] < name[0])
-	    {
-	      bot = inc;
-	    }
-	  else if (SYMBOL_SOURCE_NAME (sym)[0] > name[0])
-	    {
-	      top = inc;
-	    }
-	  else if (strcmp (SYMBOL_SOURCE_NAME (sym), name) < 0)
-	    {
-	      bot = inc;
-	    }
-	  else
-	    {
-	      top = inc;
-	    }
-	}
-
-      /* Now scan forward until we run out of symbols, find one whose
-         name is greater than NAME, or find one we want.  If there is
-         more than one symbol with the right name and namespace, we
-         return the first one; I believe it is now impossible for us
-         to encounter two symbols with the same name and namespace
-         here, because blocks containing argument symbols are no
-         longer sorted.  The exception is for C++, where multiple functions
-	 (cloned constructors / destructors, in particular) can have
-	 the same demangled name.  So if we have a particular
-	 mangled name to match, try to do so.  */
-
-      top = BLOCK_NSYMS (block);
-      while (bot < top)
-	{
-	  sym = BLOCK_SYM (block, bot);
-	  if (SYMBOL_NAMESPACE (sym) == namespace
-	      && (mangled_name
-		  ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0
-		  : SYMBOL_MATCHES_NAME (sym, name)))
-	    {
-	      return sym;
-	    }
-          if (SYMBOL_SOURCE_NAME (sym)[0] > name[0])
-            {
-              break;
-            }
-	  bot++;
-	}
-    }
-
-  /* Here if block isn't sorted, or we fail to find a match during the
-     binary search above.  If during the binary search above, we find a
-     symbol which is a Java symbol, then we have re-enabled the linear
-     search flag which was reset when starting the binary search.
-
-     This loop is equivalent to the loop above, but hacked greatly for speed.
-
-     Note that parameter symbols do not always show up last in the
-     list; this loop makes sure to take anything else other than
-     parameter symbols first; it only uses parameter symbols as a
-     last resort.  Note that this only takes up extra computation
-     time on a match.  */
-
-  if (do_linear_search)
+  else
     {
+      /* Note that parameter symbols do not always show up last in the
+	 list.  This loop makes sure to take anything else other than
+	 parameter symbols first; it only uses parameter symbols as a
+	 last resort.  Note that this only takes up extra computation
+	 time on a match.  */
       top = BLOCK_NSYMS (block);
       bot = 0;
       while (bot < top)
 	{
 	  sym = BLOCK_SYM (block, bot);
+	  /* If there is more than one symbol with the right name and
+	     namespace, we return the first one; I believe it is now
+	     impossible for us to encounter two symbols with the same
+	     name and namespace here, because blocks containing
+	     argument symbols are no longer sorted.  The exception is
+	     for C++, where multiple functions (cloned constructors /
+	     destructors, in particular) can have the same demangled
+	     name.  So if we have a particular mangled name to match,
+	     try to do so.  */
 	  if (SYMBOL_NAMESPACE (sym) == namespace
 	      && (mangled_name
 		  ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0
@@ -1492,8 +1415,8 @@ lookup_block_symbol (register const stru
 	    }
 	  bot++;
 	}
+      return (sym_found);		/* Will be NULL if not found. */
     }
-  return (sym_found);		/* Will be NULL if not found. */
 }
 
 /* Given a main symbol SYM and ADDR, search through the alias

Index: ada-lang.c
===================================================================
RCS file: /cvs/src/src/gdb/ada-lang.c,v
retrieving revision 1.9
diff -u -p -r1.9 ada-lang.c
--- ada-lang.c	8 Sep 2002 17:43:26 -0000	1.9
+++ ada-lang.c	18 Sep 2002 20:53:52 -0000
@@ -3949,7 +3949,6 @@ ada_add_block_symbols (struct block *blo
   struct symbol *arg_sym;
   /* Set true when we find a matching non-argument symbol */
   int found_sym;
-  int is_sorted = BLOCK_SHOULD_SORT (block);
   struct symbol *sym;
 
   arg_sym = NULL;
@@ -3985,45 +3984,14 @@ ada_add_block_symbols (struct block *blo
     }
   else
     {
-      if (is_sorted)
-	{
-	  int U;
-	  i = 0;
-	  U = BLOCK_NSYMS (block) - 1;
-	  while (U - i > 4)
-	    {
-	      int M = (U + i) >> 1;
-	      struct symbol *sym = BLOCK_SYM (block, M);
-	      if (SYMBOL_NAME (sym)[0] < name[0])
-		i = M + 1;
-	      else if (SYMBOL_NAME (sym)[0] > name[0])
-		U = M - 1;
-	      else if (strcmp (SYMBOL_NAME (sym), name) < 0)
-		i = M + 1;
-	      else
-		U = M;
-	    }
-	}
-      else
-	i = 0;
-
-      for (; i < BLOCK_BUCKETS (block); i += 1)
-	for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next)
+      ALL_BLOCK_SYMBOLS (block, i, sym)
 	  {
 	    if (SYMBOL_NAMESPACE (sym) == namespace)
 	      {
 		int cmp = strncmp (name, SYMBOL_NAME (sym), name_len);
 
-		if (cmp < 0)
-		  {
-		    if (is_sorted)
-		      {
-			i = BLOCK_BUCKETS (block);
-			break;
-		      }
-		  }
-		else if (cmp == 0
-			 && is_name_suffix (SYMBOL_NAME (sym) + name_len))
+		if (cmp == 0
+		    && is_name_suffix (SYMBOL_NAME (sym) + name_len))
 		  {
 		    switch (SYMBOL_CLASS (sym))
 		      {
@@ -4059,30 +4027,8 @@ ada_add_block_symbols (struct block *blo
     {
       arg_sym = NULL;
       found_sym = 0;
-      if (is_sorted)
-	{
-	  int U;
-	  i = 0;
-	  U = BLOCK_NSYMS (block) - 1;
-	  while (U - i > 4)
-	    {
-	      int M = (U + i) >> 1;
-	      struct symbol *sym = BLOCK_SYM (block, M);
-	      if (SYMBOL_NAME (sym)[0] < '_')
-		i = M + 1;
-	      else if (SYMBOL_NAME (sym)[0] > '_')
-		U = M - 1;
-	      else if (strcmp (SYMBOL_NAME (sym), "_ada_") < 0)
-		i = M + 1;
-	      else
-		U = M;
-	    }
-	}
-      else
-	i = 0;
 
-      for (; i < BLOCK_BUCKETS (block); i += 1)
-	for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next)
+      ALL_BLOCK_SYMBOLS (block, i, sym)
 	  {
 	    struct symbol *sym = BLOCK_SYM (block, i);
 
@@ -4098,16 +4044,8 @@ ada_add_block_symbols (struct block *blo
 		      cmp = strncmp (name, SYMBOL_NAME (sym) + 5, name_len);
 		  }
 
-		if (cmp < 0)
-		  {
-		    if (is_sorted)
-		      {
-			i = BLOCK_BUCKETS (block);
-			break;
-		      }
-		  }
-		else if (cmp == 0
-			 && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5))
+		if (cmp == 0
+		    && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5))
 		  {
 		    switch (SYMBOL_CLASS (sym))
 		      {

Index: symfile.h
===================================================================
RCS file: /cvs/src/src/gdb/symfile.h,v
retrieving revision 1.13
diff -u -p -r1.13 symfile.h
--- symfile.h	22 Apr 2002 10:19:04 -0000	1.13
+++ symfile.h	18 Sep 2002 20:56:41 -0000
@@ -198,12 +198,6 @@ extern struct partial_symtab *start_psym
 						    struct partial_symbol **,
 						    struct partial_symbol **);
 
-/* Sorting your symbols for fast lookup or alphabetical printing.  */
-
-extern void sort_block_syms (struct block *);
-
-extern void sort_symtab_syms (struct symtab *);
-
 /* Make a copy of the string at PTR with SIZE characters in the symbol obstack
    (and add a null character at the end in the copy).
    Returns the address of the copy.  */

Index: symfile.c
===================================================================
RCS file: /cvs/src/src/gdb/symfile.c,v
retrieving revision 1.65
diff -u -p -r1.65 symfile.c
--- symfile.c	1 Aug 2002 17:18:32 -0000	1.65
+++ symfile.c	18 Sep 2002 20:56:34 -0000
@@ -275,38 +275,6 @@ sort_pst_symbols (struct partial_symtab 
 	 compare_psymbols);
 }
 
-/* Call sort_block_syms to sort alphabetically the symbols of one block.  */
-
-void
-sort_block_syms (register struct block *b)
-{
-  qsort (&BLOCK_SYM (b, 0), BLOCK_NSYMS (b),
-	 sizeof (struct symbol *), compare_symbols);
-}
-
-/* Call sort_symtab_syms to sort alphabetically
-   the symbols of each block of one symtab.  */
-
-void
-sort_symtab_syms (register struct symtab *s)
-{
-  register struct blockvector *bv;
-  int nbl;
-  int i;
-  register struct block *b;
-
-  if (s == 0)
-    return;
-  bv = BLOCKVECTOR (s);
-  nbl = BLOCKVECTOR_NBLOCKS (bv);
-  for (i = 0; i < nbl; i++)
-    {
-      b = BLOCKVECTOR_BLOCK (bv, i);
-      if (BLOCK_SHOULD_SORT (b))
-	sort_block_syms (b);
-    }
-}
-
 /* Make a null terminated copy of the string at PTR with SIZE characters in
    the obstack pointed to by OBSTACKP .  Returns the address of the copy.
    Note that the string at PTR does not have to be null terminated, I.E. it

Index: coffread.c
===================================================================
RCS file: /cvs/src/src/gdb/coffread.c,v
retrieving revision 1.29
diff -u -p -r1.29 coffread.c
--- coffread.c	22 Aug 2002 05:50:11 -0000	1.29
+++ coffread.c	18 Sep 2002 20:55:11 -0000
@@ -637,15 +637,6 @@ coff_symfile_read (struct objfile *objfi
 
   coff_symtab_read ((long) symtab_offset, num_symbols, objfile);
 
-  /* Sort symbols alphabetically within each block.  */
-
-  {
-    struct symtab *s;
-
-    for (s = objfile->symtabs; s != NULL; s = s->next)
-      sort_symtab_syms (s);
-  }
-
   /* Install any minimal symbols that have been collected as the current
      minimal symbols for this objfile.  */
 

Index: xcoffread.c
===================================================================
RCS file: /cvs/src/src/gdb/xcoffread.c,v
retrieving revision 1.20
diff -u -p -r1.20 xcoffread.c
--- xcoffread.c	12 Jul 2002 18:30:15 -0000	1.20
+++ xcoffread.c	18 Sep 2002 20:56:59 -0000
@@ -1768,7 +1768,6 @@ xcoff_psymtab_to_symtab_1 (struct partia
       old_chain = make_cleanup (really_free_pendings, 0);
 
       read_xcoff_symtab (pst);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }

Index: mdebugread.c
===================================================================
RCS file: /cvs/src/src/gdb/mdebugread.c,v
retrieving revision 1.28
diff -u -p -r1.28 mdebugread.c
--- mdebugread.c	29 Jul 2002 22:55:26 -0000	1.28
+++ mdebugread.c	18 Sep 2002 20:56:25 -0000
@@ -3981,10 +3981,6 @@ psymtab_to_symtab_1 (struct partial_symt
 	  end_stabs ();
 	}
 
-      /* Sort the symbol table now, we are done adding symbols to it.
-         We must do this before parse_procedure calls lookup_symbol.  */
-      sort_symtab_syms (st);
-
       /* There used to be a call to sort_blocks here, but this should not
          be necessary for stabs symtabs.  And as sort_blocks modifies the
          start address of the GLOBAL_BLOCK to the FIRST_LOCAL_BLOCK,
@@ -4178,9 +4174,6 @@ psymtab_to_symtab_1 (struct partial_symt
       pop_parse_stack ();
 
       st->primary = 1;
-
-      /* Sort the symbol table now, we are done adding symbols to it. */
-      sort_symtab_syms (st);
 
       sort_blocks (st);
     }

Index: hpread.c
===================================================================
RCS file: /cvs/src/src/gdb/hpread.c,v
retrieving revision 1.22
diff -u -p -r1.22 hpread.c
--- hpread.c	4 Aug 2002 19:11:12 -0000	1.22
+++ hpread.c	18 Sep 2002 20:56:18 -0000
@@ -2729,7 +2729,6 @@ hpread_psymtab_to_symtab_1 (struct parti
 	hpread_expand_symtab (pst->objfile, LDSYMOFF (pst), LDSYMLEN (pst),
 			      pst->textlow, pst->texthigh - pst->textlow,
 			      pst->section_offsets, pst->filename);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }

Index: dwarfread.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarfread.c,v
retrieving revision 1.14
diff -u -p -r1.14 dwarfread.c
--- dwarfread.c	1 Aug 2002 17:18:32 -0000	1.14
+++ dwarfread.c	18 Sep 2002 20:58:30 -0000
@@ -2364,7 +2364,6 @@ psymtab_to_symtab_1 (struct partial_symt
 		  wrap_here ("");
 		  gdb_flush (gdb_stdout);
 		}
-	      sort_symtab_syms (pst->symtab);
 	      do_cleanups (old_chain);
 	    }
 	  pst->readin = 1;

Index: dwarf2read.c
===================================================================
RCS file: /cvs/src/src/gdb/dwarf2read.c,v
retrieving revision 1.66
diff -u -p -r1.66 dwarf2read.c
--- dwarf2read.c	3 Sep 2002 17:32:11 -0000	1.66
+++ dwarf2read.c	18 Sep 2002 20:56:12 -0000
@@ -1606,7 +1606,6 @@ psymtab_to_symtab_1 (struct partial_symt
     }
   pst->symtab = symtab;
   pst->readin = 1;
-  sort_symtab_syms (pst->symtab);
 
   do_cleanups (back_to);
 }

Index: dbxread.c
===================================================================
RCS file: /cvs/src/src/gdb/dbxread.c,v
retrieving revision 1.34
diff -u -p -r1.34 dbxread.c
--- dbxread.c	29 Jul 2002 22:55:26 -0000	1.34
+++ dbxread.c	18 Sep 2002 20:55:59 -0000
@@ -2477,7 +2477,6 @@ dbx_psymtab_to_symtab_1 (struct partial_
       /* Read in this file's symbols */
       bfd_seek (pst->objfile->obfd, SYMBOL_OFFSET (pst), SEEK_SET);
       read_ofile_symtab (pst);
-      sort_symtab_syms (pst->symtab);
 
       do_cleanups (old_chain);
     }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]