-
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