From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jason Molenda To: Eli Zaretskii Cc: gdb-patches@sources.redhat.com Subject: Re: [RFA] bug in symtab.c:lookup_block_symbol()'s search method Date: Sat, 15 Sep 2001 12:52:00 -0000 Message-id: <20010915125120.A11429@shell17.ba.best.com> References: <20010910113226.A23487@shell17.ba.best.com> <87zo82swwa.fsf@cgsoftware.com> <20010910130347.A5628@shell17.ba.best.com> <8766aq7nki.fsf@cgsoftware.com> <3BA219EF.3000300@cygnus.com> <9003-Fri14Sep2001190223+0300-eliz@is.elta.co.il> <20010914091241.A28921@shell17.ba.best.com> <1659-Fri14Sep2001204927+0300-eliz@is.elta.co.il> <20010915005255.A2369@shell17.ba.best.com> <2110-Sat15Sep2001133818+0300-eliz@is.elta.co.il> X-SW-Source: 2001-09/msg00195.html 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