Re: [RFA] bug in symtab.c:lookup_block_symbol()'s search method

[Jason Molenda <jason-swarelist@molenda.com>]

On Sat, Sep 15, 2001 at 01:38:18PM +0300, Eli Zaretskii wrote:

> > Dan's patch dropped the "exits out of linear search" -- now it
> > binary searches to the beginning of plausible ranges, and steps
> > through to the end of the block.  It's now an O(1/2*N) algorithm
> > for worst-case, i.e. non-matches.
> 
> Are you saying that Dan's change was a gratuitous one, i.e. there was
> no reason whatsoever to make that change?

Yes.  The lookup_block_symbol() function already depends on the
first character being a meaningful, comparable character (the binary
search is based on this, and on strcmp() of all things), so ending
the search based on this criteria will not further weaken this
algorithm.

If there is real concern that this method of comparison is invalid
for some languages, then the entire patch Dan submitted needs to
be reworked or we need to stick with comparing only mangled/native
names.

It can't be had both ways -- either the whole conversion to umangled
comparisons, as it is currently written, is invalid, or my correction
of the linear search is correct.  The current lookup_block_symbol
search code is as incorrect as my patch.  The only benefits of the
current lookup_block_symbol code is that it linear searches over half
of the symbols in the block, so it stands a 50% chance of hitting one
of these names that we're talking about.  I'd not characterize that
as 'correct'.

Jason