[RFA] Extend hashed symbol dictionaries to work with Ada

[RFA] Extend hashed symbol dictionaries to work with Ada

[Paul Hilfinger]

This patch allows Ada to speed up symbol lookup by using the facilities
in dictionary.[ch] for hashed lookups.  First, we generalize dictionary
search to allow clients to specify any matching function compatible with
the hashing function. Next, we modify the hashing algorithm so that symbols
that wild-match a name hash to the same value.  Finally, we modify Ada
symbol lookup to use these facilities.

Because this patch touches on a hashing algorithm used by other
languages, I took the precaution of doing a speed test on a list of
about 12000 identifiers (repeatedly inserting all of them into a table
and then doing a lookup on a million names at random, thus testing the
speed of the hashing algorithm and how well it distributed names).
There was actually a slight speedup, probably as a result of open-
coding some of the tests in msymbol_hash_iw.  By design, the revised
hashing algorithm produces the same results as the original on most
"normal" C identifiers.

We considered augmenting the dictionary interface still further by allowing
different hashing algorithms for different dictionaries, based on the
(supposed) language of the symbols in that dictionary.  While this produced
better isolation of the changes to Ada programs, the additional flexibility
also complicated the dictionary interface.  I'd prefer to keep things
simple for now.

Tested w/o regressions on Linux i686.

Paul Hilfinger

ChangeLog:

	gdb/
	* ada-lang.c (ada_match_name): Use new API for wild_match.
	(wild_match): Change API to be consistent with that of strcmp_iw;
	return 0 for a match, and switch operand order.
	(full_match): New function.
	(ada_add_block_symbols): Use dict_iter_match_{first,next} for
	matching to allow use of hashing.
	* dictionary.c (struct dict_vector): Generalize iter_name_first,
	iter_name_next ot iter_match_first, iter_match_next.
	(iter_name_first_hashed): Replace with iter_match_first_hashed.
	(iter_name_next_hashed): Replace with iter_match_next_hashed.
	(iter_name_first_linear): Replace with iter_match_first_linear.
	(iter_name_next_linear): Replace with iter_match_next_linear.
	(dict_iter_name_first): Re-implement to use dict_iter_match_first.
	(dict_iter_name_next): Re-implement to use dict_iter_match_next.
	(dict_iter_match_first): New function.
	(dict_iter_match_next): New function.
	(dict_hash): New function.
	* dictionary.h (dict_iter_match_first, dict_iter_match_next): Declare.
	* psymtab.c (ada_lookup_partial_symbol): Use new wild_match API.
---
 gdb/ada-lang.c   |   43 ++++++++-------
 gdb/dictionary.c |  151 ++++++++++++++++++++++++++++++++++++++++--------------
 gdb/dictionary.h |   25 +++++++++
 3 files changed, 160 insertions(+), 59 deletions(-)

diff --git a/gdb/ada-lang.c b/gdb/ada-lang.c
index 09619de..912cc22 100644
--- a/gdb/ada-lang.c
+++ b/gdb/ada-lang.c
@@ -5062,6 +5062,13 @@ wild_match (const char *name, const char *patn)
     }
 }
 
+static int
+full_match (const char* sym_name, const char* search_name)
+{
+  return !ada_match_name (sym_name, search_name, 0);
+}
+
+
 /* Add symbols from BLOCK matching identifier NAME in DOMAIN to
    vector *defn_symbols, updating the list of symbols in OBSTACKP 
    (if necessary).  If WILD, treat as NAME with a wildcard prefix. 
@@ -5086,9 +5093,9 @@ ada_add_block_symbols (struct obstack *obstackp,
   found_sym = 0;
   if (wild)
     {
-      struct symbol *sym;
-
-      ALL_BLOCK_SYMBOLS (block, iter, sym)
+      for (sym = dict_iter_match_first (BLOCK_DICT (block), name,
+					wild_match, &iter);
+	   sym != NULL; sym = dict_iter_match_next (name, wild_match, &iter))
       {
         if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
                                    SYMBOL_DOMAIN (sym), domain)
@@ -5110,29 +5117,25 @@ ada_add_block_symbols (struct obstack *obstackp,
     }
   else
     {
-      ALL_BLOCK_SYMBOLS (block, iter, sym)
+     for (sym = dict_iter_match_first (BLOCK_DICT (block), name,
+					full_match, &iter);
+	   sym != NULL; sym = dict_iter_match_next (name, full_match, &iter))
       {
         if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
                                    SYMBOL_DOMAIN (sym), domain))
           {
-            int cmp = strncmp (name, SYMBOL_LINKAGE_NAME (sym), name_len);
-
-            if (cmp == 0
-                && is_name_suffix (SYMBOL_LINKAGE_NAME (sym) + name_len))
-              {
-		if (SYMBOL_CLASS (sym) != LOC_UNRESOLVED)
+	    if (SYMBOL_CLASS (sym) != LOC_UNRESOLVED)
+	      {
+		if (SYMBOL_IS_ARGUMENT (sym))
+		  arg_sym = sym;
+		else
 		  {
-		    if (SYMBOL_IS_ARGUMENT (sym))
-		      arg_sym = sym;
-		    else
-		      {
-			found_sym = 1;
-			add_defn_to_vec (obstackp,
-					 fixup_symbol_section (sym, objfile),
-					 block);
-		      }
+		    found_sym = 1;
+		    add_defn_to_vec (obstackp,
+				     fixup_symbol_section (sym, objfile),
+				     block);
 		  }
-              }
+	      }
           }
       }
     }
diff --git a/gdb/dictionary.c b/gdb/dictionary.c
index e1c2010..1a2e1e2 100644
--- a/gdb/dictionary.c
+++ b/gdb/dictionary.c
@@ -21,6 +21,7 @@
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include "defs.h"
+#include <ctype.h>
 #include "gdb_obstack.h"
 #include "symtab.h"
 #include "buildsym.h"
@@ -116,11 +117,13 @@ struct dict_vector
 				    struct dict_iterator *iterator);
   struct symbol *(*iterator_next) (struct dict_iterator *iterator);
   /* Functions to iterate over symbols with a given name.  */
-  struct symbol *(*iter_name_first) (const struct dictionary *dict,
+  struct symbol *(*iter_match_first) (const struct dictionary *dict,
 				     const char *name,
+				     int (*equiv) (const char*, const char*),
+				     struct dict_iterator *iterator);
+  struct symbol *(*iter_match_next) (const char *name,
+				     int (*equiv) (const char*, const char*),
 				     struct dict_iterator *iterator);
-  struct symbol *(*iter_name_next) (const char *name,
-				    struct dict_iterator *iterator);
   /* A size function, for maint print symtabs.  */
   int (*size) (const struct dictionary *dict);
 };
@@ -236,12 +239,18 @@ static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 
 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
 
-static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
-					      const char *name,
+static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
+					       const char *name,
+					       int (*compare) (const char*,
+							       const char *),
 					      struct dict_iterator *iterator);
 
-static struct symbol *iter_name_next_hashed (const char *name,
-					     struct dict_iterator *iterator);
+static struct symbol *iter_match_next_hashed (const char *name,
+					      int (*compare) (const char*,
+							      const char *),
+					      struct dict_iterator *iterator);
+
+static unsigned int dict_hash (const char *string);
 
 /* Functions only for DICT_HASHED.  */
 
@@ -264,12 +273,16 @@ static struct symbol *iterator_first_linear (const struct dictionary *dict,
 
 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 
-static struct symbol *iter_name_first_linear (const struct dictionary *dict,
-					      const char *name,
-					      struct dict_iterator *iterator);
+static struct symbol *iter_match_first_linear (const struct dictionary *dict,
+					       const char *name,
+					       int (*compare) (const char*,
+							       const char *),
+					       struct dict_iterator *iterator);
 
-static struct symbol *iter_name_next_linear (const char *name,
-					     struct dict_iterator *iterator);
+static struct symbol *iter_match_next_linear (const char *name,
+					      int (*compare) (const char*,
+							      const char *),
+					      struct dict_iterator *iterator);
 
 static int size_linear (const struct dictionary *dict);
 
@@ -289,8 +302,8 @@ static const struct dict_vector dict_hashed_vector =
     add_symbol_nonexpandable,		/* add_symbol */
     iterator_first_hashed,		/* iterator_first */
     iterator_next_hashed,		/* iterator_next */
-    iter_name_first_hashed,		/* iter_name_first */
-    iter_name_next_hashed,		/* iter_name_next */
+    iter_match_first_hashed,		/* iter_name_first */
+    iter_match_next_hashed,		/* iter_name_next */
     size_hashed,			/* size */
   };
 
@@ -301,8 +314,8 @@ static const struct dict_vector dict_hashed_expandable_vector =
     add_symbol_hashed_expandable,	/* add_symbol */
     iterator_first_hashed,		/* iterator_first */
     iterator_next_hashed,		/* iterator_next */
-    iter_name_first_hashed,		/* iter_name_first */
-    iter_name_next_hashed,		/* iter_name_next */
+    iter_match_first_hashed,		/* iter_name_first */
+    iter_match_next_hashed,		/* iter_name_next */
     size_hashed_expandable,		/* size */
   };
 
@@ -313,8 +326,8 @@ static const struct dict_vector dict_linear_vector =
     add_symbol_nonexpandable,		/* add_symbol */
     iterator_first_linear,		/* iterator_first */
     iterator_next_linear,		/* iterator_next */
-    iter_name_first_linear,		/* iter_name_first */
-    iter_name_next_linear,		/* iter_name_next */
+    iter_match_first_linear,		/* iter_name_first */
+    iter_match_next_linear,		/* iter_name_next */
     size_linear,			/* size */
   };
 
@@ -325,8 +338,8 @@ static const struct dict_vector dict_linear_expandable_vector =
     add_symbol_linear_expandable,	/* add_symbol */
     iterator_first_linear,		/* iterator_first */
     iterator_next_linear,		/* iterator_next */
-    iter_name_first_linear,		/* iter_name_first */
-    iter_name_next_linear,		/* iter_name_next */
+    iter_match_first_linear,		/* iter_name_first */
+    iter_match_next_linear,		/* iter_name_next */
     size_linear,			/* size */
   };
 
@@ -516,14 +529,31 @@ dict_iter_name_first (const struct dictionary *dict,
 		      const char *name,
 		      struct dict_iterator *iterator)
 {
-  return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
+  return dict_iter_match_first (dict, name, strcmp_iw, iterator);
 }
 
 struct symbol *
 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
 {
+  return dict_iter_match_next (name, strcmp_iw, iterator);
+}
+
+struct symbol *
+dict_iter_match_first (const struct dictionary *dict,
+		       const char *name,
+		       int (*compare) (const char*, const char *),
+		       struct dict_iterator *iterator)
+{
+  return (DICT_VECTOR (dict))->iter_match_first (dict, name, compare, iterator);
+}
+
+struct symbol *
+dict_iter_match_next (const char *name,
+		      int (*compare) (const char*, const char *),
+		      struct dict_iterator *iterator)
+{
   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
-    ->iter_name_next (name, iterator);
+    ->iter_match_next (name, compare, iterator);
 }
 
 int
@@ -614,12 +644,12 @@ iterator_hashed_advance (struct dict_iterator *iterator)
 }
 
 static struct symbol *
-iter_name_first_hashed (const struct dictionary *dict,
-			const char *name,
-			struct dict_iterator *iterator)
+iter_match_first_hashed (const struct dictionary *dict,
+			 const char *name,
+			 int (*compare) (const char*, const char *),
+			 struct dict_iterator *iterator)
 {
-  unsigned int hash_index
-    = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
+  unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
   struct symbol *sym;
 
   DICT_ITERATOR_DICT (iterator) = dict;
@@ -632,8 +662,8 @@ iter_name_first_hashed (const struct dictionary *dict,
        sym != NULL;
        sym = sym->hash_next)
     {
-      /* Warning: the order of arguments to strcmp_iw matters!  */
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
+      /* Warning: the order of arguments to compare matters!  */
+      if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 	{
 	  break;
 	}
@@ -645,7 +675,9 @@ iter_name_first_hashed (const struct dictionary *dict,
 }
 
 static struct symbol *
-iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
+iter_match_next_hashed (const char *name,
+			int (*compare) (const char*, const char *),
+			struct dict_iterator *iterator)
 {
   struct symbol *next;
 
@@ -653,7 +685,7 @@ iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
        next != NULL;
        next = next->hash_next)
     {
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
+      if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
 	break;
     }
 
@@ -671,8 +703,8 @@ insert_symbol_hashed (struct dictionary *dict,
   unsigned int hash_index;
   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 
-  hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
-		% DICT_HASHED_NBUCKETS (dict));
+  hash_index = 
+    dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
   sym->hash_next = buckets[hash_index];
   buckets[hash_index] = sym;
 }
@@ -746,6 +778,44 @@ expand_hashtable (struct dictionary *dict)
   xfree (old_buckets);
 }
 
+static unsigned int
+dict_hash (const char *string)
+{
+  unsigned int hash;
+  int c;
+
+  if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
+    string += 5;
+
+  hash = 0;
+  while (*string)
+    {
+      switch (*string)
+	{
+	case '$': case '.': case 'X': case '(':
+	  return hash;
+	case ' ':
+	  string += 1;
+	  break;
+	case '_':
+	  if (string[1] == '_')
+	    {
+	      if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
+		return hash;
+	      hash = 0;
+	      string += 2;
+	      break;
+	    }
+	  /* FALL THROUGH */
+	default:
+	  hash = hash * 67 + *string - 113;
+	  string += 1;
+	  break;
+	}
+    }
+  return hash;
+}
+
 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 
 static struct symbol *
@@ -769,18 +839,21 @@ iterator_next_linear (struct dict_iterator *iterator)
 }
 
 static struct symbol *
-iter_name_first_linear (const struct dictionary *dict,
-			const char *name,
-			struct dict_iterator *iterator)
+iter_match_first_linear (const struct dictionary *dict,
+			 const char *name,
+			 int (*compare) (const char*, const char *),
+			 struct dict_iterator *iterator)
 {
   DICT_ITERATOR_DICT (iterator) = dict;
   DICT_ITERATOR_INDEX (iterator) = -1;
 
-  return iter_name_next_linear (name, iterator);
+  return iter_match_next_linear (name, compare, iterator);
 }
 
 static struct symbol *
-iter_name_next_linear (const char *name, struct dict_iterator *iterator)
+iter_match_next_linear (const char *name,
+			int (*compare) (const char*, const char *),
+			struct dict_iterator *iterator)
 {
   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
   int i, nsyms = DICT_LINEAR_NSYMS (dict);
@@ -789,7 +862,7 @@ iter_name_next_linear (const char *name, struct dict_iterator *iterator)
   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
     {
       sym = DICT_LINEAR_SYM (dict, i);
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
+      if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 	{
 	  retval = sym;
 	  break;
diff --git a/gdb/dictionary.h b/gdb/dictionary.h
index 2242a79..f7d3035 100644
--- a/gdb/dictionary.h
+++ b/gdb/dictionary.h
@@ -134,6 +134,31 @@ extern struct symbol *dict_iter_name_first (const struct dictionary *dict,
 extern struct symbol *dict_iter_name_next (const char *name,
 					   struct dict_iterator *iterator);
 
+/* Initialize ITERATOR to point at the first symbol in DICT whose
+   SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (which must use
+   the same conventions as strcmp_iw and be compatible with any
+   dictionary hashing function), and return that first symbol, or NULL
+   if there are no such symbols.  */
+
+extern struct symbol *dict_iter_match_first (const struct dictionary *dict,
+					     const char *name,
+					     int (*compare) (const char*, 
+							     const char *),
+					     struct dict_iterator *iterator);
+
+/* Advance ITERATOR to point at the next symbol in DICT whose
+   SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (see
+   dict_iter_match_first), or NULL if there are no more such symbols.
+   Don't call this if you've previously received NULL from 
+   dict_iterator_match_first or dict_iterator_match_next on this
+   iteration. And don't call it unless ITERATOR was created by a
+   previous call to dict_iter_match_first with the same NAME and COMPARE.  */
+
+extern struct symbol *dict_iter_match_next (const char *name,
+					    int (*compare) (const char*, 
+							    const char *),
+					    struct dict_iterator *iterator);
+
 /* Return some notion of the size of the dictionary: the number of
    symbols if we have that, the number of hash buckets otherwise.  */
 
-- 
1.7.0.4

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Tom Tromey]

>>>>> "Paul" == Paul Hilfinger <hilfingr@syracuse.mckusick.com> writes:

Paul> This patch allows Ada to speed up symbol lookup by using the facilities
Paul> in dictionary.[ch] for hashed lookups.

Paul> Because this patch touches on a hashing algorithm used by other
Paul> languages, I took the precaution of doing a speed test on a list of
Paul> about 12000 identifiers (repeatedly inserting all of them into a table
Paul> and then doing a lookup on a million names at random, thus testing the
Paul> speed of the hashing algorithm and how well it distributed names).

Thanks for looking at this.

Paul> +full_match (const char* sym_name, const char* search_name)

I noticed a few spots in the patch with "char* something" instead of
"char *something".

Paul> +	case '$': case '.': case 'X': case '(':

I personally think it is clearer to put each case on a separate line,
but I don't insist on it.

This is ok with the "char *" spacing thing fixed.

Tom

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Tom Tromey]

>>>>> "Tom" == Tom Tromey <tromey@redhat.com> writes:

Tom> This is ok with the "char *" spacing thing fixed.

I think I was a little too hasty here.  It would be better if Joel ok'd
any ada-specific changes.  While they seem reasonable to me, I don't
think I know enough to really approve them.  The other bits are fine,
though.

Tom

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Joel Brobecker]

> 	gdb/
> 	* ada-lang.c (ada_match_name): Use new API for wild_match.
> 	(wild_match): Change API to be consistent with that of strcmp_iw;
> 	return 0 for a match, and switch operand order.
> 	(full_match): New function.
> 	(ada_add_block_symbols): Use dict_iter_match_{first,next} for
> 	matching to allow use of hashing.

No further comment on this part (I actually had already looked at
these patches, but did not feel comfortable approving them myself
for the non-Ada parts).

Thanks again, Tom, for looking at the rest.

-- 
Joel

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Doug Evans]

On Tue, Oct 5, 2010 at 1:20 AM, Paul Hilfinger
<hilfingr@syracuse.mckusick.com> wrote:
>
> This patch allows Ada to speed up symbol lookup by using the facilities
> in dictionary.[ch] for hashed lookups.  First, we generalize dictionary
> search to allow clients to specify any matching function compatible with
> the hashing function. Next, we modify the hashing algorithm so that symbols
> that wild-match a name hash to the same value.  Finally, we modify Ada
> symbol lookup to use these facilities.
>
> Because this patch touches on a hashing algorithm used by other
> languages, I took the precaution of doing a speed test on a list of
> about 12000 identifiers (repeatedly inserting all of them into a table
> and then doing a lookup on a million names at random, thus testing the
> speed of the hashing algorithm and how well it distributed names).
> There was actually a slight speedup, probably as a result of open-
> coding some of the tests in msymbol_hash_iw.  By design, the revised
> hashing algorithm produces the same results as the original on most
> "normal" C identifiers.
>
> We considered augmenting the dictionary interface still further by allowing
> different hashing algorithms for different dictionaries, based on the
> (supposed) language of the symbols in that dictionary.  While this produced
> better isolation of the changes to Ada programs, the additional flexibility
> also complicated the dictionary interface.  I'd prefer to keep things
> simple for now.
>
>[...]

Hi.  I wouldn't mind having a couple of comments added to this function:

>
> +static unsigned int
> +dict_hash (const char *string)
> +{
> +  unsigned int hash;
> +  int c;
> +
> +  if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
> +    string += 5;
> +
> +  hash = 0;
> +  while (*string)
> +    {
> +      switch (*string)
> +       {
> +       case '$': case '.': case 'X': case '(':

Why is 'X' special cased?
[Actually, I'd have the comment explain all of these special cases.]

> +         return hash;
> +       case ' ':
> +         string += 1;
> +         break;
> +       case '_':
> +         if (string[1] == '_')
> +           {
> +             if (((c = string[2]) < 'a' || c > 'z') && c != 'O')

Why does this `if' exist?

> +               return hash;
> +             hash = 0;

Why do we restart calculating the hash here?

> +             string += 2;
> +             break;
> +           }
> +         /* FALL THROUGH */
> +       default:
> +         hash = hash * 67 + *string - 113;
> +         string += 1;
> +         break;
> +       }
> +    }
> +  return hash;
> +}
> +

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Paul Hilfinger]

On Wed, 2010-10-06 at 16:43 -0600, Tom Tromey wrote:
> >>>>> "Paul" == Paul Hilfinger <hilfingr@syracuse.mckusick.com> writes:

> Paul> +full_match (const char* sym_name, const char* search_name)
> 
> I noticed a few spots in the patch with "char* something" instead of
> "char *something".
> 

Sorry; that notation is a personal quirk of mine (I consider * to be
part of the type; naturally, this means I have to avoid making the
'char* x, y' mistake).  I sometimes forget to change it to the
wrong ... er ... standard way before submitting.

> Paul> +	case '$': case '.': case 'X': case '(':
> 
> I personally think it is clearer to put each case on a separate line,
> but I don't insist on it.

OK, since it appears that the only other places with more than one
case on a line are in arm-tdep.c and remote.c.

Thanks for looking at this.

Paul

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Paul Hilfinger]

On Wed, 2010-10-06 at 16:52 -0600, Tom Tromey wrote:
> >>>>> "Tom" == Tom Tromey <tromey@redhat.com> writes:
> 
> Tom> This is ok with the "char *" spacing thing fixed.
> 
> I think I was a little too hasty here.  It would be better if Joel ok'd
> any ada-specific changes.  While they seem reasonable to me, I don't
> think I know enough to really approve them.  The other bits are fine,
> though.

Not at all.  I put it out as RFA specifically because I was encroaching
on others' territory.  I'm already an Ada maintainer.

Paul

Re: [RFA] Extend hashed symbol dictionaries to work with Ada

[Paul Hilfinger]

On Wed, 2010-10-06 at 16:59 -0700, Doug Evans wrote:

> Hi.  I wouldn't mind having a couple of comments added to this function:
> 

Arghh.  My mistake.  I added a comment to our local version without
submitting it.  Updating:

+/* Produce an unsigned hash value from STRING0 that is consistent
+   with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
+   That is, two identifiers equivalent according to any of those three
+   comparison operators hash to the same value.  */
+
+static unsigned int
+dict_hash (const char *string)
+{
+  /* The Ada-encoded version of a name P1.P2...Pn has either the form
+     P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
+     are lower-cased identifiers).  The <suffix> (which can be empty)
+     encodes additional information about the denoted entity.  This
+     routine hashes such names to msymbol_hash_iw(Pn).  It actually
+     does this for a superset of both valid Pi and of <suffix>, but 
+     in other cases it simply returns msymbol_hash_iw(STRING0).  */
...

> > +       case '_':
> > +         if (string[1] == '_')
> > +           {
> > +             if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
> 
> Why does this `if' exist?
> 

Follows from the (newly added) comment above.  That condition indicates
a __ followed by something that can't be an encoded Ada identifier.  We
assume it is part of the suffix (as indicated in the comment, we accept
a superset of the valid suffixes).

> > +               return hash;
> > +             hash = 0;
> 
> Why do we restart calculating the hash here?

As the comments indicate, we are ignoring the prefix of a qualified
name to get wild-matching.

Thanks for your comments.

Paul

[commit] Extend hashed symbol dictionaries to work with Ada

[Paul Hilfinger]

Subject: [commit] Extend hashed symbol dictionaries to work with Ada

I've committed the following, with the suggested changes.

Paul Hilfinger



This patch allows Ada to speed up symbol lookup by using the facilities
in dictionary.[ch] for hashed lookups.  First, we generalize dictionary
search to allow clients to specify any matching function compatible with
the hashing function. Next, we modify the hashing algorithm so that symbols
that wild-match a name hash to the same value.  Finally, we modify Ada
symbol lookup to use these facilities.

Because this patch touches on a hashing algorithm used by other
languages, I took the precaution of doing a speed test on a list of
about 12000 identifiers (repeatedly inserting all of them into a table
and then doing a lookup on a million names at random, thus testing the
speed of the hashing algorithm and how well it distributed names).
There was actually a slight speedup, probably as a result of open-
coding some of the tests in msymbol_hash_iw.  By design, the revised
hashing algorithm produces the same results as the original on most
"normal" C identifiers.

We considered augmenting the dictionary interface still further by allowing
different hashing algorithms for different dictionaries, based on the
(supposed) language of the symbols in that dictionary.  While this produced
better isolation of the changes to Ada programs, the additional flexibility
also complicated the dictionary interface.  I'd prefer to keep things
simple for now.

Tested w/o regressions on Linux i686.

ChangeLog:

	gdb/
	* ada-lang.c (ada_match_name): Use new API for wild_match.
	(wild_match): Change API to be consistent with that of strcmp_iw;
	return 0 for a match, and switch operand order.
	(full_match): New function.
	(ada_add_block_symbols): Use dict_iter_match_{first,next} for
	matching to allow use of hashing.
	* dictionary.c (struct dict_vector): Generalize iter_name_first,
	iter_name_next ot iter_match_first, iter_match_next.
	(iter_name_first_hashed): Replace with iter_match_first_hashed.
	(iter_name_next_hashed): Replace with iter_match_next_hashed.
	(iter_name_first_linear): Replace with iter_match_first_linear.
	(iter_name_next_linear): Replace with iter_match_next_linear.
	(dict_iter_name_first): Re-implement to use dict_iter_match_first.
	(dict_iter_name_next): Re-implement to use dict_iter_match_next.
	(dict_iter_match_first): New function.
	(dict_iter_match_next): New function.
	(dict_hash): New function.
	* dictionary.h (dict_iter_match_first, dict_iter_match_next): Declare.
	* psymtab.c (ada_lookup_partial_symbol): Use new wild_match API.
---
 gdb/ChangeLog    |   22 +++++++
 gdb/ada-lang.c   |   43 +++++++------
 gdb/dictionary.c |  169 +++++++++++++++++++++++++++++++++++++++++------------
 gdb/dictionary.h |   25 ++++++++
 4 files changed, 200 insertions(+), 59 deletions(-)

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index a7dad26..9e5a615 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,25 @@
+2010-10-06  Paul Hilfinger  <hilfinger@adacore.com>
+
+	* ada-lang.c (ada_match_name): Use new API for wild_match.
+    	(wild_match): Change API to be consistent with that of strcmp_iw;
+    	return 0 for a match, and switch operand order.
+    	(full_match): New function.
+    	(ada_add_block_symbols): Use dict_iter_match_{first,next} for
+    	matching to allow use of hashing.
+    	* dictionary.c (struct dict_vector): Generalize iter_name_first,
+    	iter_name_next ot iter_match_first, iter_match_next.
+    	(iter_name_first_hashed): Replace with iter_match_first_hashed.
+    	(iter_name_next_hashed): Replace with iter_match_next_hashed.
+    	(iter_name_first_linear): Replace with iter_match_first_linear.
+    	(iter_name_next_linear): Replace with iter_match_next_linear.
+    	(dict_iter_name_first): Re-implement to use dict_iter_match_first.
+    	(dict_iter_name_next): Re-implement to use dict_iter_match_next.
+    	(dict_iter_match_first): New function.
+    	(dict_iter_match_next): New function.
+    	(dict_hash): New function.
+    	* dictionary.h (dict_iter_match_first, dict_iter_match_next): Declare.
+    	* psymtab.c (ada_lookup_partial_symbol): Use new wild_match API.
+
 2010-10-06  Doug Evans  <dje@google.com>
 
 	* data-directory/Makefile.in: Remove @host_makefile_frag@, @frags@.
diff --git a/gdb/ada-lang.c b/gdb/ada-lang.c
index 5fdf851..c111e40 100644
--- a/gdb/ada-lang.c
+++ b/gdb/ada-lang.c
@@ -5062,6 +5062,13 @@ wild_match (const char *name, const char *patn)
     }
 }
 
+static int
+full_match (const char *sym_name, const char *search_name)
+{
+  return !ada_match_name (sym_name, search_name, 0);
+}
+
+
 /* Add symbols from BLOCK matching identifier NAME in DOMAIN to
    vector *defn_symbols, updating the list of symbols in OBSTACKP 
    (if necessary).  If WILD, treat as NAME with a wildcard prefix. 
@@ -5086,9 +5093,9 @@ ada_add_block_symbols (struct obstack *obstackp,
   found_sym = 0;
   if (wild)
     {
-      struct symbol *sym;
-
-      ALL_BLOCK_SYMBOLS (block, iter, sym)
+      for (sym = dict_iter_match_first (BLOCK_DICT (block), name,
+					wild_match, &iter);
+	   sym != NULL; sym = dict_iter_match_next (name, wild_match, &iter))
       {
         if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
                                    SYMBOL_DOMAIN (sym), domain)
@@ -5110,29 +5117,25 @@ ada_add_block_symbols (struct obstack *obstackp,
     }
   else
     {
-      ALL_BLOCK_SYMBOLS (block, iter, sym)
+     for (sym = dict_iter_match_first (BLOCK_DICT (block), name,
+					full_match, &iter);
+	   sym != NULL; sym = dict_iter_match_next (name, full_match, &iter))
       {
         if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
                                    SYMBOL_DOMAIN (sym), domain))
           {
-            int cmp = strncmp (name, SYMBOL_LINKAGE_NAME (sym), name_len);
-
-            if (cmp == 0
-                && is_name_suffix (SYMBOL_LINKAGE_NAME (sym) + name_len))
-              {
-		if (SYMBOL_CLASS (sym) != LOC_UNRESOLVED)
+	    if (SYMBOL_CLASS (sym) != LOC_UNRESOLVED)
+	      {
+		if (SYMBOL_IS_ARGUMENT (sym))
+		  arg_sym = sym;
+		else
 		  {
-		    if (SYMBOL_IS_ARGUMENT (sym))
-		      arg_sym = sym;
-		    else
-		      {
-			found_sym = 1;
-			add_defn_to_vec (obstackp,
-					 fixup_symbol_section (sym, objfile),
-					 block);
-		      }
+		    found_sym = 1;
+		    add_defn_to_vec (obstackp,
+				     fixup_symbol_section (sym, objfile),
+				     block);
 		  }
-              }
+	      }
           }
       }
     }
diff --git a/gdb/dictionary.c b/gdb/dictionary.c
index e1c2010..f3ac306 100644
--- a/gdb/dictionary.c
+++ b/gdb/dictionary.c
@@ -21,6 +21,7 @@
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include "defs.h"
+#include <ctype.h>
 #include "gdb_obstack.h"
 #include "symtab.h"
 #include "buildsym.h"
@@ -116,11 +117,15 @@ struct dict_vector
 				    struct dict_iterator *iterator);
   struct symbol *(*iterator_next) (struct dict_iterator *iterator);
   /* Functions to iterate over symbols with a given name.  */
-  struct symbol *(*iter_name_first) (const struct dictionary *dict,
+  struct symbol *(*iter_match_first) (const struct dictionary *dict,
 				     const char *name,
+				     int (*equiv) (const char *,
+						   const char *),
+				     struct dict_iterator *iterator);
+  struct symbol *(*iter_match_next) (const char *name,
+				     int (*equiv) (const char *,
+						   const char *),
 				     struct dict_iterator *iterator);
-  struct symbol *(*iter_name_next) (const char *name,
-				    struct dict_iterator *iterator);
   /* A size function, for maint print symtabs.  */
   int (*size) (const struct dictionary *dict);
 };
@@ -236,12 +241,18 @@ static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 
 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
 
-static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
-					      const char *name,
+static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
+					       const char *name,
+					       int (*compare) (const char *,
+							       const char *),
 					      struct dict_iterator *iterator);
 
-static struct symbol *iter_name_next_hashed (const char *name,
-					     struct dict_iterator *iterator);
+static struct symbol *iter_match_next_hashed (const char *name,
+					      int (*compare) (const char *,
+							      const char *),
+					      struct dict_iterator *iterator);
+
+static unsigned int dict_hash (const char *string);
 
 /* Functions only for DICT_HASHED.  */
 
@@ -264,12 +275,16 @@ static struct symbol *iterator_first_linear (const struct dictionary *dict,
 
 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 
-static struct symbol *iter_name_first_linear (const struct dictionary *dict,
-					      const char *name,
-					      struct dict_iterator *iterator);
+static struct symbol *iter_match_first_linear (const struct dictionary *dict,
+					       const char *name,
+					       int (*compare) (const char *,
+							       const char *),
+					       struct dict_iterator *iterator);
 
-static struct symbol *iter_name_next_linear (const char *name,
-					     struct dict_iterator *iterator);
+static struct symbol *iter_match_next_linear (const char *name,
+					      int (*compare) (const char *,
+							      const char *),
+					      struct dict_iterator *iterator);
 
 static int size_linear (const struct dictionary *dict);
 
@@ -289,8 +304,8 @@ static const struct dict_vector dict_hashed_vector =
     add_symbol_nonexpandable,		/* add_symbol */
     iterator_first_hashed,		/* iterator_first */
     iterator_next_hashed,		/* iterator_next */
-    iter_name_first_hashed,		/* iter_name_first */
-    iter_name_next_hashed,		/* iter_name_next */
+    iter_match_first_hashed,		/* iter_name_first */
+    iter_match_next_hashed,		/* iter_name_next */
     size_hashed,			/* size */
   };
 
@@ -301,8 +316,8 @@ static const struct dict_vector dict_hashed_expandable_vector =
     add_symbol_hashed_expandable,	/* add_symbol */
     iterator_first_hashed,		/* iterator_first */
     iterator_next_hashed,		/* iterator_next */
-    iter_name_first_hashed,		/* iter_name_first */
-    iter_name_next_hashed,		/* iter_name_next */
+    iter_match_first_hashed,		/* iter_name_first */
+    iter_match_next_hashed,		/* iter_name_next */
     size_hashed_expandable,		/* size */
   };
 
@@ -313,8 +328,8 @@ static const struct dict_vector dict_linear_vector =
     add_symbol_nonexpandable,		/* add_symbol */
     iterator_first_linear,		/* iterator_first */
     iterator_next_linear,		/* iterator_next */
-    iter_name_first_linear,		/* iter_name_first */
-    iter_name_next_linear,		/* iter_name_next */
+    iter_match_first_linear,		/* iter_name_first */
+    iter_match_next_linear,		/* iter_name_next */
     size_linear,			/* size */
   };
 
@@ -325,8 +340,8 @@ static const struct dict_vector dict_linear_expandable_vector =
     add_symbol_linear_expandable,	/* add_symbol */
     iterator_first_linear,		/* iterator_first */
     iterator_next_linear,		/* iterator_next */
-    iter_name_first_linear,		/* iter_name_first */
-    iter_name_next_linear,		/* iter_name_next */
+    iter_match_first_linear,		/* iter_name_first */
+    iter_match_next_linear,		/* iter_name_next */
     size_linear,			/* size */
   };
 
@@ -516,14 +531,31 @@ dict_iter_name_first (const struct dictionary *dict,
 		      const char *name,
 		      struct dict_iterator *iterator)
 {
-  return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
+  return dict_iter_match_first (dict, name, strcmp_iw, iterator);
 }
 
 struct symbol *
 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
 {
+  return dict_iter_match_next (name, strcmp_iw, iterator);
+}
+
+struct symbol *
+dict_iter_match_first (const struct dictionary *dict,
+		       const char *name,
+		       int (*compare) (const char *, const char *),
+		       struct dict_iterator *iterator)
+{
+  return (DICT_VECTOR (dict))->iter_match_first (dict, name, compare, iterator);
+}
+
+struct symbol *
+dict_iter_match_next (const char *name,
+		      int (*compare) (const char *, const char *),
+		      struct dict_iterator *iterator)
+{
   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
-    ->iter_name_next (name, iterator);
+    ->iter_match_next (name, compare, iterator);
 }
 
 int
@@ -614,12 +646,12 @@ iterator_hashed_advance (struct dict_iterator *iterator)
 }
 
 static struct symbol *
-iter_name_first_hashed (const struct dictionary *dict,
-			const char *name,
-			struct dict_iterator *iterator)
+iter_match_first_hashed (const struct dictionary *dict,
+			 const char *name,
+			 int (*compare) (const char *, const char *),
+			 struct dict_iterator *iterator)
 {
-  unsigned int hash_index
-    = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
+  unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
   struct symbol *sym;
 
   DICT_ITERATOR_DICT (iterator) = dict;
@@ -632,8 +664,8 @@ iter_name_first_hashed (const struct dictionary *dict,
        sym != NULL;
        sym = sym->hash_next)
     {
-      /* Warning: the order of arguments to strcmp_iw matters!  */
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
+      /* Warning: the order of arguments to compare matters!  */
+      if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 	{
 	  break;
 	}
@@ -645,7 +677,9 @@ iter_name_first_hashed (const struct dictionary *dict,
 }
 
 static struct symbol *
-iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
+iter_match_next_hashed (const char *name,
+			int (*compare) (const char *, const char *),
+			struct dict_iterator *iterator)
 {
   struct symbol *next;
 
@@ -653,7 +687,7 @@ iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
        next != NULL;
        next = next->hash_next)
     {
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
+      if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
 	break;
     }
 
@@ -671,8 +705,8 @@ insert_symbol_hashed (struct dictionary *dict,
   unsigned int hash_index;
   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 
-  hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
-		% DICT_HASHED_NBUCKETS (dict));
+  hash_index = 
+    dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
   sym->hash_next = buckets[hash_index];
   buckets[hash_index] = sym;
 }
@@ -746,6 +780,60 @@ expand_hashtable (struct dictionary *dict)
   xfree (old_buckets);
 }
 
+/* Produce an unsigned hash value from STRING0 that is consistent
+   with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
+   That is, two identifiers equivalent according to any of those three
+   comparison operators hash to the same value.  */
+
+static unsigned int
+dict_hash (const char *string)
+{
+  /* The Ada-encoded version of a name P1.P2...Pn has either the form
+     P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
+     are lower-cased identifiers).  The <suffix> (which can be empty)
+     encodes additional information about the denoted entity.  This
+     routine hashes such names to msymbol_hash_iw(Pn).  It actually
+     does this for a superset of both valid Pi and of <suffix>, but 
+     in other cases it simply returns msymbol_hash_iw(STRING0).  */
+
+  unsigned int hash;
+  int c;
+
+  if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
+    string += 5;
+
+  hash = 0;
+  while (*string)
+    {
+      switch (*string)
+	{
+	case '$':
+	case '.':
+	case 'X':
+	case '(':
+	  return hash;
+	case ' ':
+	  string += 1;
+	  break;
+	case '_':
+	  if (string[1] == '_')
+	    {
+	      if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
+		return hash;
+	      hash = 0;
+	      string += 2;
+	      break;
+	    }
+	  /* FALL THROUGH */
+	default:
+	  hash = hash * 67 + *string - 113;
+	  string += 1;
+	  break;
+	}
+    }
+  return hash;
+}
+
 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 
 static struct symbol *
@@ -769,18 +857,21 @@ iterator_next_linear (struct dict_iterator *iterator)
 }
 
 static struct symbol *
-iter_name_first_linear (const struct dictionary *dict,
-			const char *name,
-			struct dict_iterator *iterator)
+iter_match_first_linear (const struct dictionary *dict,
+			 const char *name,
+			 int (*compare) (const char *, const char *),
+			 struct dict_iterator *iterator)
 {
   DICT_ITERATOR_DICT (iterator) = dict;
   DICT_ITERATOR_INDEX (iterator) = -1;
 
-  return iter_name_next_linear (name, iterator);
+  return iter_match_next_linear (name, compare, iterator);
 }
 
 static struct symbol *
-iter_name_next_linear (const char *name, struct dict_iterator *iterator)
+iter_match_next_linear (const char *name,
+			int (*compare) (const char *, const char *),
+			struct dict_iterator *iterator)
 {
   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
   int i, nsyms = DICT_LINEAR_NSYMS (dict);
@@ -789,7 +880,7 @@ iter_name_next_linear (const char *name, struct dict_iterator *iterator)
   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
     {
       sym = DICT_LINEAR_SYM (dict, i);
-      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
+      if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 	{
 	  retval = sym;
 	  break;
diff --git a/gdb/dictionary.h b/gdb/dictionary.h
index 2242a79..f7d3035 100644
--- a/gdb/dictionary.h
+++ b/gdb/dictionary.h
@@ -134,6 +134,31 @@ extern struct symbol *dict_iter_name_first (const struct dictionary *dict,
 extern struct symbol *dict_iter_name_next (const char *name,
 					   struct dict_iterator *iterator);
 
+/* Initialize ITERATOR to point at the first symbol in DICT whose
+   SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (which must use
+   the same conventions as strcmp_iw and be compatible with any
+   dictionary hashing function), and return that first symbol, or NULL
+   if there are no such symbols.  */
+
+extern struct symbol *dict_iter_match_first (const struct dictionary *dict,
+					     const char *name,
+					     int (*compare) (const char*, 
+							     const char *),
+					     struct dict_iterator *iterator);
+
+/* Advance ITERATOR to point at the next symbol in DICT whose
+   SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (see
+   dict_iter_match_first), or NULL if there are no more such symbols.
+   Don't call this if you've previously received NULL from 
+   dict_iterator_match_first or dict_iterator_match_next on this
+   iteration. And don't call it unless ITERATOR was created by a
+   previous call to dict_iter_match_first with the same NAME and COMPARE.  */
+
+extern struct symbol *dict_iter_match_next (const char *name,
+					    int (*compare) (const char*, 
+							    const char *),
+					    struct dict_iterator *iterator);
+
 /* Return some notion of the size of the dictionary: the number of
    symbols if we have that, the number of hash buckets otherwise.  */
 
-- 
1.7.0.4



-- 
Paul N. Hilfinger
(Hilfinger@adacore.com)

[commit] Correct dict_hash to our most recent version.

[Paul Hilfinger, :]

Sigh.  I must stop working late at night.  I have corrected my last
checkin of dictionary.c:dict_hash to include the code that the
comments in my commit message was actually discussing (deferring to
msymbol_hash_iw in a few more cases to avoid some nasty hash
collisions).  While I should ask for another round of approval
technically, for expendience I'm going to go out on a limb and check
this in now, since it passes the testsuite, isn't likely to provoke
a violent reaction, given that my first version didn't, and is easily 
undone in any case.

Paul Hilfinger


Changelog:

	gdb/
	* dictionary.c (dict_hash): Revert to msymbol_hash_iw in
	more cases.
---
 gdb/ChangeLog    |    5 +++++
 gdb/dictionary.c |   25 +++++++++++++++++--------
 2 files changed, 22 insertions(+), 8 deletions(-)

diff --git a/gdb/dictionary.c b/gdb/dictionary.c
index f3ac306..4f18e8c 100644
--- a/gdb/dictionary.c
+++ b/gdb/dictionary.c
@@ -786,7 +786,7 @@ expand_hashtable (struct dictionary *dict)
    comparison operators hash to the same value.  */
 
 static unsigned int
-dict_hash (const char *string)
+dict_hash (const char *string0)
 {
   /* The Ada-encoded version of a name P1.P2...Pn has either the form
      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
@@ -796,11 +796,18 @@ dict_hash (const char *string)
      does this for a superset of both valid Pi and of <suffix>, but 
      in other cases it simply returns msymbol_hash_iw(STRING0).  */
 
+  const char *string;
   unsigned int hash;
   int c;
 
-  if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
-    string += 5;
+  string = string0;
+  if (*string == '_')
+    {
+      if (strncmp (string, "_ada_", 5) == 0)
+	string += 5;
+      else
+	return msymbol_hash_iw (string0);
+    }
 
   hash = 0;
   while (*string)
@@ -810,13 +817,15 @@ dict_hash (const char *string)
 	case '$':
 	case '.':
 	case 'X':
-	case '(':
-	  return hash;
+	  if (string0 == string)
+	    return msymbol_hash_iw (string0);
+	  else
+	    return hash;
 	case ' ':
-	  string += 1;
-	  break;
+	case '(':
+	  return msymbol_hash_iw (string0);
 	case '_':
-	  if (string[1] == '_')
+	  if (string[1] == '_' && string != string0)
 	    {
 	      if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
 		return hash;
-- 
1.7.0.4



-- 
Paul N. Hilfinger
(Hilfinger@adacore.com)

Re: [commit] Correct dict_hash to our most recent version.

[Tom Tromey]

>>>>> "Paul" == Paul Hilfinger <<Hilfinger@adacore.com>, ":"@gnat.com> writes:

Paul> Sigh.  I must stop working late at night.  I have corrected my last
Paul> checkin of dictionary.c:dict_hash to include the code that the
Paul> comments in my commit message was actually discussing (deferring to
Paul> msymbol_hash_iw in a few more cases to avoid some nasty hash
Paul> collisions).  While I should ask for another round of approval
Paul> technically, for expendience I'm going to go out on a limb and check
Paul> this in now, since it passes the testsuite, isn't likely to provoke
Paul> a violent reaction, given that my first version didn't, and is easily 
Paul> undone in any case.

My 2 cents.

I think what you did is fine in this situation.
This patch is bordering on the obvious boundary, at least given that you
were just working in this exact area.

It is also ok to just ask for a review.  I personally don't mind the
occasional breakage -- we all make mistakes, and while I sometimes panic
when I check in a bug, I also know there's really no need, so long as
that wasn't the last commit before a release :-)

Tom