path: root/include
diff options
authorJesper Dangaard Brouer <>2008-07-03 20:31:42 +0200
committerPatrick McHardy <>2008-07-03 20:31:42 +0200
commit4bae3f1001028ee283a5e1fcea4a561b0068f95d (patch)
tree6a6c125a7a36c72cf8105825b5c6d177e60998ee /include
parent526d3e138635e33773d1ca16477052a04f53f5bd (diff)
libiptc: fix scalability performance issue during initial ruleset parsing
Finding jump chains is slow O(Chain*Rules). The problem: is that the chain list is searched lineary for each rule with a jump target. The problem lies in the "second pass" (of function parse_table) where the userchain jump targets are found. For each rule "R" with a IPTCC_R_JUMP target, function iptcc_find_chain_by_offset() searches through the chains "C" in the chain list (worst-case hitting the last one). The solution: in this patch is to speed up iptcc_find_chain_by_offset() by using binary search. Reducing complexity from O(C) to O(log C). Implementation: Its possible to use the same bsearch algorithm and data structure (chain_index), as used for chain name searching. How is that possible: One has to realize that the chains are both sorted by name and offsets, this is because the chains are already sorted in the ruleset from the kernel. Signed-off-by: Jesper Dangaard Brouer <> Signed-off-by: Patrick McHardy <>
Diffstat (limited to 'include')
0 files changed, 0 insertions, 0 deletions