Hi,

I have to write a really really fast algorithm to match an IP address to a list of groups, where each group is defined using a notation like 192.168.0.0/252.255.0.255. As you can see, the bitmask can contain zeros even in the middle, so the traditional "longest prefix match" algorithms won't work. If an IP matches two groups, it will be assigned to the group containing most 1's in the netmask.

I'm not working with many entries (let's say < 1000) and I don't want to use a data structure requiring a large memory footprint (let's say > 1-2 MB), but it really has to be fast (of course I can't afford a linear search).

Do you have any suggestion? Thanks guys.

UPDATE: I found something quite interesting at http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf, but it's still too memory-hungry for my utopic use case