/
BinaryNode.py
133 lines (102 loc) · 3.94 KB
/
BinaryNode.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# date March 2020
import timeit
class BinaryNode(object):
def __init__(self, NextHop=""):
self.NextHop = NextHop # here we save the value of the leaf node
self.Left = None # 0's branch
self.Right = None # 1's branch
def AddChild(self, prefix, path):
if len(path) == 0:
return
if len(path) == 1:
if path == "0":
self.Left = BinaryNode(NextHop=prefix)
else:
self.Right = BinaryNode(NextHop=prefix)
elif len(path) > 1:
if path.startswith("0"):
if self.Left is None:
self.Left = BinaryNode()
self.Left.AddChild(prefix, path[1:])
else:
if self.Right is None:
self.Right = BinaryNode()
self.Right.AddChild(prefix, path[1:])
def Lookup(self, address, backtrack=""):
if self.NextHop != "": # saving the last hop visited
backtrack = self.NextHop
if address == "" or (self.Left is None and self.Right is None): # if we are on a leaf node return the last prefix
return backtrack
if address.startswith("0"): # for each hop we check whether go to the left or right branch
if self.Left is not None: # if there's still a child, look deeper in the trie
return self.Left.Lookup(address[1:], backtrack)
else: # otherwise return the last valid prefix
return backtrack
else:
if self.Right is not None:
return self.Right.Lookup(address[1:], backtrack)
else:
return backtrack
def LookupNonRecursive(self, address, rootPrefix = "0"):
backtrack = ""
partialAddress =address
node = self
while (node is not None):
if node.NextHop != "":
backtrack = node.NextHop
if partialAddress == "" or (node.Left is None and node.Right is None):
return backtrack
if partialAddress.startswith("0"):
if node.Left is not None:
partialAddress = partialAddress[1:]
node = node.Left
else:
return backtrack
else:
if node.Right is not None:
partialAddress = partialAddress[1:]
node = node.Right
else:
return backtrack
return backtrack
def Create(default_value='0'):
# helper method to rapidly create the trie reading the db.txt
_root = BinaryNode(default_value)
with open("db.txt", 'r') as f:
my_list = [line.rstrip('\n') for line in f]
for address in my_list:
addr, binary_address = address.split(',')
ip, mask = addr.split("\\")
_root.AddChild(ip, binary_address)
return _root
def convert_in_bin(address):
# simple method to convert an IP address in its binary representation
if address.find('\\') != -1:
ip = address.split("\\")[0]
mask = int(address.split("\\")[1])
return ''.join([bin(int(x) + 256)[3:] for x in ip.split('.')])[:mask]
else:
return ''.join([bin(int(x) + 256)[3:] for x in address.split('.')])
def _is_binary(string):
is_binary = True
try:
int(string, 2)
except ValueError:
is_binary = False
return is_binary
# DEBUG
if __name__ == "__main__":
root = Create("0")
with open('tosearch.txt', 'r') as t:
my_list = [line.rstrip('\n') for line in t]
times = []
for entry in my_list:
addr = entry.split(",")[0]
ip = addr.split("\\")[0]
mask = int(addr.split("\\")[1])
binary_address = convert_in_bin(ip)[:mask]
start = timeit.default_timer()
root.Lookup(binary_address)
end = timeit.default_timer() - start
times.append(end * 1000)
print ("binary trie: " + str(sum(times)) + "ms")