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

[Doug Evans <dje@google.com>]

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;
> +}
> +