{"action":"created","issue":{"url":"https://api.github.com/repos/geany/geany/issues/797","labels_url":"https://api.github.com/repos/geany/geany/issues/797/labels{/name}","comments_url":"https://api.github.com/repos/geany/geany/issues/797/comments","events_url":"https://api.github.com/repos/geany/geany/issues/797/events","html_url":"https://github.com/geany/geany/pull/797","id":121867877,"number":797,"title":"Store \"equal\" tags into binary trees instead of lists in Symbol tree","user":{"login":"techee","id":713965,"avatar_url":"https://avatars.githubusercontent.com/u/713965?v=3","gravatar_id":"","url":"https://api.github.com/users/techee","html_url":"https://github.com/techee","followers_url":"https://api.github.com/users/techee/followers","following_url":"https://api.github.com/users/techee/following{/other_user}","gists_url":"https://api.github.com/users/techee/gists{/gist_id}","starred_url":"https://api.github.com/users/techee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/techee/subscriptions","organizations_url":"https://api.github.com/users/techee/orgs","repos_url":"https://api.github.com/users/techee/repos","events_url":"https://api.github.com/users/techee/events{/privacy}","received_events_url":"https://api.github.com/users/techee/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2015-12-12T17:32:35Z","updated_at":"2016-01-05T15:25:52Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/geany/geany/pulls/797","html_url":"https://github.com/geany/geany/pull/797","diff_url":"https://github.com/geany/geany/pull/797.diff","patch_url":"https://github.com/geany/geany/pull/797.patch"},"body":"At the moment tags with identical names are stored into a linked list in\r\ntags_table and parents_table. This however leads to quadratic complexity\r\nwhen looking up the nearest parent or tag in tree because the whole list\r\nhas to be traversed.\r\n\r\nUse binary trees indexed by line number instead of lists so the lookup can\r\nbe performed in log(N) time and the overall complexity is N*log(N) instead\r\nof N^2.\r\n\r\nThe GTree API is a little stupid because during the search it doesn't give\r\naccess to the value and it doesn't tell when a leaf node was reached. For\r\nthis reason the lookup has to be made in two steps - first, the best line\r\nnumber is found (returned in user_data) and then a normal search for the\r\nfound line number is made to get the value stored in the tree.\r\n\r\nThis patch fixes the problem described in #577 when e.g. a big json export\r\nfile contains many identically named tags."},"comment":{"url":"https://api.github.com/repos/geany/geany/issues/comments/169034160","html_url":"https://github.com/geany/geany/pull/797#issuecomment-169034160","issue_url":"https://api.github.com/repos/geany/geany/issues/797","id":169034160,"user":{"login":"techee","id":713965,"avatar_url":"https://avatars.githubusercontent.com/u/713965?v=3","gravatar_id":"","url":"https://api.github.com/users/techee","html_url":"https://github.com/techee","followers_url":"https://api.github.com/users/techee/followers","following_url":"https://api.github.com/users/techee/following{/other_user}","gists_url":"https://api.github.com/users/techee/gists{/gist_id}","starred_url":"https://api.github.com/users/techee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/techee/subscriptions","organizations_url":"https://api.github.com/users/techee/orgs","repos_url":"https://api.github.com/users/techee/repos","events_url":"https://api.github.com/users/techee/events{/privacy}","received_events_url":"https://api.github.com/users/techee/received_events","type":"User","site_admin":false},"created_at":"2016-01-05T15:25:52Z","updated_at":"2016-01-05T15:25:52Z","body":"@b4n Thanks for reviewing and for the patch - yes, the tree lookup was unnecessary (I was first simplifying the existing code to understand it better and with the original code the TMTag parameter was unnecessary so I replaced it just with gchar *name, then changed the code to use the tree but forgot we can actually use the original tag).\r\n\r\nAbout the g_tree_search() and g_tree_lookup() pairs - yes, if there's at least a single element in the tree, it will be returned by g_tree_search()'s user_data. The only \"danger\" is when the tree is empty (can happen because of tags_table_remove()) but there's no real problem here either as looking for whatever line number always returns NULL in g_tree_lookup().\r\n\r\nYes, the patch won't do any miracles - a big enough file will make the editor unusable but at least the slow-downs will be kind of \"normal\" - N*log(N) is \"almost\" like N, for big enough N the log(N) part gets smaller and smaller. Anything quadratic is fine until some number but then becomes crazy within a very short interval.\r\n\r\nBy the way, is there a way to apply patches using spaces instead of tabs? Github seems to replace tabs with spaces and I had to apply your changes manually because of that."}}