• Geoff Simmons's avatar
    Implement QP prefix searching without recursion. · 83364942
    Geoff Simmons authored
    The new algorithm improves efficiency with iteration in place of
    recursion, and in a number of other ways:
    
    - Avoid searches into dead-end branches. The traversal of all branches
    was done because of the overlapping prefix case -- "foo" and "foobar"
    both in the set. Now we just search the tree for a match, but before
    descending into the next branch, check if there are other branches at
    which the current prefix matches a terminating node.
    
    - Only do string comparisons when we hit a terminating node.
    
    - Mark terminating nodes with a flag in the tree, so that we don't go
    looking for the null byte in the strings table during the search.
    
    While we're here, rename the flag for the nibble search as hinib --
    non-zero if and only if we inspect the most significant nibble at that
    node. Also remove some dead code from QP_Insert().
    83364942
Name
Last commit
Last update
m4 Loading commit data...
pkg/rpm Loading commit data...
src Loading commit data...
.dir-locals.el Loading commit data...
.gitignore Loading commit data...
CONTRIBUTING.rst Loading commit data...
COPYING Loading commit data...
INSTALL.rst Loading commit data...
LICENSE Loading commit data...
Makefile.am Loading commit data...
README.rst Loading commit data...
TODO Loading commit data...
autogen.sh Loading commit data...
configure.ac Loading commit data...