KFind patch for incremental searching

David Faure faure at kde.org
Mon Jun 7 21:05:01 BST 2004

On Monday 07 June 2004 14:14, Arend van Beelen jr. wrote:
> On Monday 07 June 2004 11:18, David Faure wrote:
> [...]
> > I see.
> > I hope the applications will free the KFind object (or at least clear its
> > cache) when stopping the incr. search though; it sounds quite expensive to
> > have a full copy of the document's text in memory (think of a 150-pages
> > kword document).
> Well, freeing is kind of troublesome as you never know when the search 
> finished because the user can always issue a Find Next. KHTML will delete and 
> reallocate the entire KFind object when a new search starts though.

> But I don't know how KOffice stores its documents in memory, but given the 
> fact QString uses shallow copies, the memory consumption should stay at a 
> minimum and the cache will only have real copies of the data blocks if the 
> set data blocks are destroyed in the calling application (like KHTML does).
Unfortunately this doesn't apply to KOffice, due to character formatting being
a pointer stored with every QChar. To get a plain-QString we need to build it
from that formatted data, so it's not shared (and it's a bit slow to build it...).

> The only thing I'm a bit worried about is how to handle insertion of data 
> blocks (paragraphs) at random points in the cache. Does KOffice increment all 
> following paragraph ID's if one paragraph is inserted or are paragraph ID's 
> non-lineair? 
They are kept consecutive, so everything is renumbered indeed. But IMHO it's
OK to just clear the KFind data cache when this happens, and to simply look 
through the text again when resuming the search. Apparently one can do lots
of document operations before resuming the search, so maintaining an alternate
document model sounds like a LOT of hassle! A little performance penalty
when resuming a search after modifying the document sounds acceptable
compared to that.

I think the memory usage problem is mostly dependent on how the incr. search
gets activated. E.g. in [X]Emacs or vim, one enters incr. search mode (Ctrl-S or '/'),
then types the string (and while doing it the highlight updates), then exits the
search mode (arrow key or enter). If we do something similar, then at that point 
we can delete the whole KFind cache. You say one can 'find next', but can
one also add or remove letters from the incr. search at that point?

Obviously if it's done more like kmail's search bar, where the gui for the incr. search
is always visible, then things are different, and we need the cache to be always 
present since one can edit the search string at any moment.

> In the former case insertion could become a rather expensive  
> operation, in the latter case it would probably require both a QValueVector 
> and a QPtrList to keep track of both the ID's and the order in which they are 
> in the document. The latter case would also require a more complex insertion 
> function in which you can specify at which position you want to insert the 
> block with the new ID. Personally I would prefer the first option (lineair 
> ID's). A single insertion could then result in a number of setData's and the 
> burden to keep track of those is placed on the calling application, but the 
> KFind class itself is saved from a lot of extra complexity.
Yes - let's just let the app throw away the cache.

> > So does the new option have to be in setOptions()? Why not a separate
> > bool setting in KFind? After all the KFindDialog options are those coming
> > from the dialog :) 
> No, KFindDialog options can come from the dialog, but don't have to.
I guess you meant "KFind options" here, but I see your point.
Ah well, it bothers everyone as it is (even I), so let's move them
for KDE 4 indeed.

David Faure, faure at kde.org, sponsored by Trolltech to work on KDE,
Konqueror (http://www.konqueror.org), and KOffice (http://www.koffice.org).

More information about the kde-core-devel mailing list