• Jiří Techet's avatar
    Store "equal" tags into binary trees instead of lists in Symbol tree · 3cf01615
    Jiří Techet yazdı
    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.
    3cf01615
symbols.c 71.7 KB