On 11/05/2010 02:16 PM, Mark Martinec wrote:
Jeroen Geilman wrote:for (entry = list; entry; entry = entry->next) { Each map is a linked list of CIDR patterns, so consolidate as much as possible - 100000 single IPs will cause noticable delays when the last entry matches!Funny coincidence: just yesterday I added a Patricia (radix) trie search to SpamAssassin, which also needs to check if an IP address matches a list of included/excluded CIDR ranges of IPv6 or IPv4 addresses. For large lists the speedup can be substantial. Now a lookup takes about 0.2 ms (in Perl), regardless of the size of a table - which is a nice property of a radix trie (commonly used with IP routing tables).Bug 6508: Speeding up lookups on {trusted,internal,msa}_networks https://issues.apache.org/SpamAssassin/show_bug.cgi?id=6508 Patricia trie on Wikipedia: http://en.wikipedia.org/wiki/Patricia_trie
That would revolutionize IP lookups on routers, firewalls etc. Unless they already use this, of course - I know mainly Cisco equipment :) It's a pity I can't code to save my life, this sounds incredibly cool.
Net::Patricia perl module on CPAN: http://search.cpan.org/dist/Net-Patricia/ Mark
-- J.
