Parser code like ``` vString *str = vStringNew(); while (someCondition) { int c = getcFromInputFile(); vStringPut(str, c); if (lookupCaseKeyword (vStringValue(str), some_lang)) { do_stuff(); vStringClear(str); } } ``` is prone to quadratic complexity because when someCondition isn't satisfied in the parsed file, the string str grows by one in each iteration and in each iteration `lookupCaseKeyword()` has to go through `strlen(str)` characters to compute the hash.
Since we know the maximum length of the strings inside the keyword hash table, we can store this value and if the queried string is longer than this value, we can be sure it isn't present in the hash table and return quickly without having to compute the full hash of the string.
This code has already been merged into ctags master so we can cherry-pick it safely. I'll merge it in about a week if there are no objections.
Fixes the hang of SQL parser reported in https://github.com/geany/geany-osx/issues/42. You can view, comment on, or merge this pull request online at:
https://github.com/geany/geany/pull/3433
-- Commit Summary --
* ctags: Add quick path for looking up too long strings in the keyword table
-- File Changes --
M ctags/main/keyword.c (29)
-- Patch Links --
https://github.com/geany/geany/pull/3433.patch https://github.com/geany/geany/pull/3433.diff