What is the most suitable data structure for IPv4 addresses with intersecting ranges?

Question

Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses.
Packet filters like Iptables don't need some special data structure for finding IPv4 addresses.

I need to implement some data structure, where I could efficiently (log(N)) find IPv4 addresses, which are specified in firewall rules. But there could also be IPv4 address prefixes and ranges. These ranges could be intersected and have exclusions (exclude one range or IP from another one). But I think exclusions could be resolved in time of constructing (deploying) data structure.
For each entry (IP-address or range or subnet prefix) I need to store a pointer to bit-vector which represents firewall rule-set. So the first set bit in this vector is the first rule that matches this source IP (e.g.).
Thus the Longest Prefix Match doesn't fit.
I was considering the Interval Tree or Red-Black tree but I'm not sure that these are the most efficient ways.

P.S. inserting and deleting is not a big problem but it would be good to be also log(N)

Answer 1

Your problem is somewhat underspecified as you don't clearly describe what you want to associate with a CIDR range. Do you just care for presence/absence of an entry for some IP address or range, or do you need to store more info, like a router?

If you only store one bit of information, you may without loss of generality use non-overlapping CIDR ranges which can be stored in a suitable sorted data structure (tree, sorted array, whatever) yielding log(N) lookup times. Inserting ranges can make use of the fact that CIDR ranges can be merged when they have the same prefix length and their prefixes only differ in the last bit. When deleting ranges, you would find overlapping ranges which are either smaller or equal to the range being deleted, otherwise you get a larger range that needs to be split into halves and then work on the half overlapping the range to be deleted. It is very likely that a tree structure has both log(N) lookup times as well as better than O(N) insert and delete times, but I've not looked at it rigorously.