On Tue, 2 Aug 2016, Mat Martineau wrote:
Decide whether to descend into child nodes based on fnmatch()
rather than performing a depth-first search of all nodes.
Using test-hwdb as an example, it now takes an average of ~50 calls to
trie_fnmatch to perform a lookup instead of ~100000.
Before I forget, the other potential trie_fnmatch optimization I spotted
was to reduce stack usage. alloca isn't expensive in terms of runtime, but
there's no reason to have so many copies of pattern prefixes sitting
around. It would work to allocate a pattern buffer at the beginning. The
matching pattern will not typically be longer than the string being
matched, but '*' may match nothing so reallocs would be a possibility.