albert-magyar/paraglob — pull request #1 by albert-magyar (2013-11-05 22:19:36+00:00)
Title: Trie

After a few weeks of being too busy with my work and graduate applications, I put together something using tries for prefix and suffix matching. The choice to add a key into the prefix or suffix trie is handled by the relative lengths of the wildcard-free prefix and suffix of a given pattern.

Final matching is handled by the regex features in the GNU C library, so this branch will only build with gcc for now. This also raises a couple of issues:

1. POSIX BRE-compliant patterns are used internally, while arguments to `paraglob_insert` and to the callback follow the `fnmatch` style, necessitating conversion. **The implemented conversion and prefix/suffix extraction functions for patterns are not nearly done, but work for the driver's inputs.**

2. Compiled DFAs are stored for every pattern key, which increases the memory footprint to levels that might be unacceptable with many inserted patterns.

3. The compiled DFA uses the complete pattern. It would be possible to strip the already-matched prefix or suffix from the pattern and query as an optimization.

Right now, the implementation is very much just a quick test, but the performance seems to be quite a bit better than the `fnmatch` approach, at least an order of magnitude in many cases. I need to add proper deletion, correct the prefix/suffix extraction for all cases, and clean it up somewhat, but one change to the interface that I will likely make in this branch is changing the patterns to POSIX BRE style throughout. This will simplify managing stored copies of patterns, since it won't be necessary to keep around the `fnmatch`-style pattern to feed to the callback.

To address the second problem, I am working on implementing a structure reminiscent of a fully-associative cache, where the N (supplied at instantiation) most recently matched patterns are stored with compiled DFAs, while the rest have only the pattern stored. This will be aided by converging on a single pattern style, since the BRE-style pattern would otherwise need to be stored alongside the original pattern.