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
Net::Patricia perl module on CPAN:
http://search.cpan.org/dist/Net-Patricia/
Mark
