[Github-comments] [geany] Store "equal" tags into binary trees instead of lists in Symbol tree (#797)

Jiří Techet notifications at xxxxx
Sat Dec 12 17:32:36 UTC 2015


At the moment tags with identical names are stored into a linked list in
tags_table and parents_table. This however leads to quadratic complexity
when looking up the nearest parent or tag in tree because the whole list
has to be traversed.

Use binary trees indexed by line number instead of lists so the lookup can
be performed in log(N) time and the overall complexity is N*log(N) instead
of N^2.

The GTree API is a little stupid because during the search it doesn't give
access to the value and it doesn't tell when a leaf node was reached. For
this reason the lookup has to be made in two steps - first, the best line
number is found (returned in user_data) and then a normal search for the
found line number is made to get the value stored in the tree.

This patch fixes the problem described in #577 when e.g. a big json export
file contains many identically named tags.
You can view, comment on, or merge this pull request online at:

  https://github.com/geany/geany/pull/797

-- Commit Summary --

  * Store "equal" tags into binary trees instead of lists in Symbol tree

-- File Changes --

    M src/symbols.c (249)

-- Patch Links --

https://github.com/geany/geany/pull/797.patch
https://github.com/geany/geany/pull/797.diff

---
Reply to this email directly or view it on GitHub:
https://github.com/geany/geany/pull/797
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.geany.org/pipermail/github-comments/attachments/20151212/f2247cf6/attachment.html>


More information about the Github-comments mailing list