fork(243) download
copy 
  1. def parseIPPart(ipx, shift):
  2.     if ipx is None:
  3.         return 0
  4.     return int(ipx) << shift
  5.  
  6. def parseIP(ipString):
  7.     (ip0, ip1, ip2, ip3) = ipString.split(".")
  8.     addr = parseIPPart(ip0, 24) + parseIPPart(ip1, 16) + parseIPPart(ip2, 8) + parseIPPart(ip3, 0)
  9.     return addr
  10.  
  11.  
  12. def parseCIDR(cidr):
  13.     (addrString, bitsString) = cidr.split('/')
  14.     bits = 32
  15.     if bitsString is not None:
  16.         bits = int(bitsString)
  17.     addr = parseIP(addrString)
  18.     return [addr, bits]
  19.  
  20.  
  21. class CIDRTree:
  22.     class CIDRNode:
  23.         def __init__(self, depth):
  24.             self.depth = depth
  25.             self.isset = None
  26.             self.unset = None
  27.             self.leaf = False
  28.  
  29.     def __init__(self):
  30.         self.root = CIDRTree.CIDRNode(-1)
  31.  
  32.     def addCIDR(self, cidr):
  33.         (ip, bits) = parseCIDR(cidr)
  34.         node = self.root
  35.         for b in range(bits):
  36.             if node.leaf:
  37.                 # Previous bigger CIDR Covers this subnet
  38.                 return
  39.             mask = 1 << (31 - b)
  40.             val = (ip & mask) != 0
  41.             kid = None
  42.             if val:
  43.                 if node.isset is None:
  44.                     node.isset = CIDRTree.CIDRNode(b)
  45.                 kid = node.isset
  46.             else:
  47.                 if node.unset is None:
  48.                     node.unset = CIDRTree.CIDRNode(b)
  49.                 kid = node.unset
  50.             node = kid
  51.         # node is now a representation of the leaf that comes from this CIDR.
  52.         # Clear out any more specific CIDRs that are no longer relevant (this CIDR includes a previous CIDR)
  53.         node.isset = None
  54.         node.unset = None
  55.         node.leaf = True
  56.         #print("Added CIDR ", ip, " and bits ", bits)
  57.  
  58.     def matches(self, ipString):
  59.  
  60.         ip = parseIP(ipString)
  61.         node = self.root
  62.         shift = 0
  63.         while node is not None and not node.leaf:
  64.             shift+=1
  65.             mask = 1 << (32 - shift)
  66.             val = (ip & mask) != 0
  67.             node = node.isset if val else node.unset
  68.  
  69.         return node is not None and node.leaf
  70.  
  71. if __name__ == "__main__":
  72.     cidrTree = CIDRTree()
  73.     cidrTree.addCIDR("8.0.0.0/8")
  74.     cidrTree.addCIDR("9.8.7.0/24")
  75.  
  76.     print ("Tree matches 8.8.8.8:", cidrTree.matches("8.8.8.8"))
  77.     print ("Tree matches 9.9.9.9:", cidrTree.matches("9.9.9.9"))
  78.     print ("Tree matches 9.8.7.6:", cidrTree.matches("9.8.7.6"))
  79.  
  80.  
  81.  
Success #stdin #stdout 0.01s 28384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree matches 8.8.8.8: True
Tree matches 9.9.9.9: False
Tree matches 9.8.7.6: True
https://ideone.com/cd0O2I
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!