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)