##Update - example lookup
Note, I hacked together this tree for supporting faster lookups of IPs in a number of CIDR ranges. Python is not my primary language, so inspect it carefully, and adjust as needed. Specifically, I have used some naive mecheanisms for parsing IP addresses in to integers. Use dedicated libraries to do that instead.
You can see it running on ideone: https://ideone.com/cd0O2I
def parseIPPart(ipx, shift):
if ipx is None:
return 0
return int(ipx) << shift
def parseIP(ipString):
(ip0, ip1, ip2, ip3) = ipString.split(".")
addr = parseIPPart(ip0, 24) + parseIPPart(ip1, 16) + parseIPPart(ip2, 8) + parseIPPart(ip3, 0)
return addr
def parseCIDR(cidr):
(addrString, bitsString) = cidr.split('/')
bits = 32
if bitsString is not None:
bits = int(bitsString)
addr = parseIP(addrString)
return [addr, bits]
class CIDRTree:
class CIDRNode:
def __init__(self, depth):
self.depth = depth
self.isset = None
self.unset = None
self.leaf = False
def __init__(self):
self.root = CIDRTree.CIDRNode(-1)
def addCIDR(self, cidr):
(ip, bits) = parseCIDR(cidr)
node = self.root
for b in range(bits):
if node.leaf:
# Previous bigger CIDR Covers this subnet
return
mask = 1 << (31 - b)
val = (ip & mask) != 0
kid = None
if val:
if node.isset is None:
node.isset = CIDRTree.CIDRNode(b)
kid = node.isset
else:
if node.unset is None:
node.unset = CIDRTree.CIDRNode(b)
kid = node.unset
node = kid
# node is now a representation of the leaf that comes from this CIDR.
# Clear out any more specific CIDRs that are no longer relevant (this CIDR includes a previous CIDR)
node.isset = None
node.unset = None
node.leaf = True
#print("Added CIDR ", ip, " and bits ", bits)
def matches(self, ipString):
ip = parseIP(ipString)
node = self.root
shift = 0
while node is not None and not node.leaf:
shift+=1
mask = 1 << (32 - shift)
val = (ip & mask) != 0
node = node.isset if val else node.unset
return node is not None and node.leaf
if __name__ == "__main__":
cidrTree = CIDRTree()
cidrTree.addCIDR("8.0.0.0/8")
cidrTree.addCIDR("9.8.7.0/24")
print ("Tree matches 8.8.8.8:", cidrTree.matches("8.8.8.8"))
print ("Tree matches 9.9.9.9:", cidrTree.matches("9.9.9.9"))
print ("Tree matches 9.8.7.6:", cidrTree.matches("9.8.7.6"))
