KDevelop-PG-Location-Table::positionAt updated with new combined relative/binary algorithm

[Andreas Pakulat]

On 26.10.09 17:37:31, Milian Wolff wrote:
> On Monday, 26. October 2009 17:07:29 Andreas Pakulat wrote:
> > On 26.10.09 17:13:09, Milian Wolff wrote:
> > > Hey guys,
> > >
> > > just wanted to notify you that I updated the algorithm that is used in
> > > the KDevelop-PG-Qt LocationTable::positionAt method. The old linear
> > > algorithm was of course pretty bad for huge files (i.e. our
> > > phpfunctions.php with its 80k lines).
> > 
> > Nice and btw, of course the linear search algorithm was simply implemented
> > because it was easiest and "fast enough" for the few dummy-usecases we(I)
> > had back then :)
> 
> True, but why did you not use an existing container class?

Ssooooo, I've just checked the original code in kdev-pg and where it
"came from". Apparently Jakob "copied" it from the location table of C++
support. 

If I understand that code correctly it works similar to what you've
implemented now. It first tries the 5 "closest" lines to the last offset
to check wether they contain the searched-for offset. If that fails it
uses QMap::lowerBound which is apparently fast enough. So maybe we
should re-use that idea and convert to a real map (unless you did so
already) to allow re-using the lowerBount(). I think the "close to
last-used offset" check is still worth it, as it vastly increases linear
access, which usually happens a lot during initial parsing (IIRC)...

Andreas

-- 
Are you sure the back door is locked?