• Geoff Simmons's avatar
    Implement QP prefix searching without recursion. · 1ec2deee
    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().
    1ec2deee
Name
Last commit
Last update
..
tests Loading commit data...
Makefile.am Loading commit data...
patricia.c Loading commit data...
patricia.h Loading commit data...
ph.c Loading commit data...
ph.h Loading commit data...
popcnt_compat.h Loading commit data...
qp.c Loading commit data...
qp.h Loading commit data...
selector.vsc Loading commit data...
vmod_selector.c Loading commit data...
vmod_selector.vcc Loading commit data...