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 geany/geany-osx#42.

You can view, comment on, or merge this pull request online at:

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

Commit Summary

dea43ba ctags: Add quick path for looking up too long strings in the keyword table

File Changes

M ctags/main/keyword.c (29)

Patch Links:

—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you are subscribed to this thread.