[Geany-devel] linear time tag manager - Re: [ANNOUNCE] gproject - yet another geany project plugin

[Jiří Techet]

On Wed, Jun 9, 2010 at 14:58, Nick Treleaven
<nick.treleaven at btinternet.com> wrote:
> On Mon, 7 Jun 2010 23:38:19 +0200
> Jiří Techet <techet at gmail.com> wrote:
>
>> * for big projects I'd like to create some basic ctags support. The
>> tag manager used by geany is totally unusable for big projects because
>> building the object hierarchy has quadratic to exponential complexity.
>> I need a simple tag support that works in linear time.
>
> Wouldn't it be better to fix tagmanager (if possible) to work faster -
> what is the cause of the non-linear behaviour - is it resorting?
>

Well, I had a very brief look at the tag manager so the following may
be wrong. From what I have seen the tag manager maintains a hierarchy
of say N objects. If you e.g. remove a file with M objects, for each
of the M objects you have to scan the N objects and remove the
reference to it. This makes N*M loop iterations (OK, I was wrong about
the exponential time if it really works this way, but again, I would
have to study the sources more carefully).

API-wise, the slow functions are

tm_workspace_add_object()
tm_workspace_remove_object()

I'm not sure if this is fixable - tag manager is definitely more
powerful than ctags that just scans the files sequentially without
creating any hierarchy. I'm not sure what's all the functionality you
use and if ctags' flat structure is enough for you.

Regards,

Jiri