Re: [rfa] symbol hashing, part 1/n - updates to hash functions

[Daniel Jacobowitz <drow at mvista dot com>]

On Thu, Oct 11, 2001 at 07:58:20PM -0400, Elena Zannoni wrote:
> Daniel Jacobowitz writes:
>  > This patch still has two logical parts; if you strongly prefer I can break
>  > it up further, but they are somewhat intertwined and I think neither should
>  > be objectionable.  They are:
>  >   - Fix a looping bug in msymbol_hash_iw.  It would not stop on '(' if there
>  > was whitespace before it.
>  >   - Update to use the identifier hash function that libiberty uses, and
>  > more buckets.
>  > 
>  > Is this OK?
> 
> Looks ok to me in theory. Except that, why was the
> 
>  '% MINIMAL_SYMBOL_HASH_SIZE;'
> 
> bit moved outside of the msymbol_hash and msymbol_hash_iw functions?
> You still do the same operation with the results returned by the two
> functions anyway. 
> 
> Also, where are these 2 functions used besides mynsyms.c?  I think we
> should make them static and remove the extern from symtab.h.

Both the moving of modulus and the no-other-uses are addressed by the
hashing patches.  These are the hash functions I will use on the
symtabs; they work for symbols as well as for minsyms.  A symtab has a
dynamic number of buckets.

> Can you give me an example where the '(' error comes up? (Just so I
> understand it better).  How did you come up with the number of
> buckets? Is this also used in libiberty?

The '(' error looks like this:

Hash the string "operator* ()".
At one point, string = " ()".  The initial whitespace loop changes this
to "()".  Then the character is not hashed (because of the if test
already present), but ++string is triggered.  The while loop now
continues, because *string == ')' instead of '('.

The number of blocks I just came up with by experimentation (well, Dan
did, and then I experimented with it and was satisfied).  Libiberty
uses expandable hash tables; I could simply use them instead, but I'd
rather postpone that change until we've got the rest of hashing in
place.

> Can you fix it and resubmit?

After my explanations, does anything else need fixing?

Thanks for looking at these patches!

-- 
Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer