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

[Doug Evans <dje at google dot 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;
> +}
> +