#!/usr/bin/env python
# Copyright (c) 2004 Damien Miller <djm@mindrot.org>
#
# Permission to use, copy, modify, and distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
# $Id: test.py,v 1.14 2005/04/25 07:32:36 djm Exp $
import radix
import unittest
import socket
class TestRadix(unittest.TestCase):
def test_00__create_destroy(self):
tree = radix.Radix()
self.assertEqual(str(type(tree)), "<type 'radix.Radix'>")
del tree
def test_01__create_node(self):
tree = radix.Radix()
node = tree.add("10.0.0.0/8")
self.assertEqual(str(type(node)), "<type 'radix.RadixNode'>")
self.assertEqual(node.prefix, "10.0.0.0/8")
self.assertEqual(node.network, "10.0.0.0")
self.assertEqual(node.prefixlen, 8)
self.assertEqual(node.family, socket.AF_INET)
node = tree.add("10.0.0.0", 16)
self.assertEqual(node.network, "10.0.0.0")
self.assertEqual(node.prefixlen, 16)
node = tree.add(network = "10.0.0.0", masklen = 24)
self.assertEqual(node.network, "10.0.0.0")
self.assertEqual(node.prefixlen, 24)
node2 = tree.add(network = "ff00::", masklen = 24)
self.assertEqual(node2.network, "ff00::")
self.assertEqual(node2.prefixlen, 24)
self.assert_(node is not node2)
def test_02__node_userdata(self):
tree = radix.Radix()
node = tree.add(network = "10.0.0.0", masklen=28)
node.data["blah"] = "abc123"
node.data["foo"] = 12345
self.assertEqual(node.data["blah"], "abc123")
self.assertEqual(node.data["foo"], 12345)
self.assertRaises(AttributeError, lambda x: x.nonexist, node)
del node.data["blah"]
self.assertRaises(KeyError, lambda x: x.data["blah"], node)
def test_03__search_exact(self):
tree = radix.Radix()
node1 = tree.add("10.0.0.0/8")
node2 = tree.add("10.0.0.0/16")
node3 = tree.add("10.0.0.0/24")
node2.data["foo"] = 12345
node = tree.search_exact("127.0.0.1")
self.assertEqual(node, None)
node = tree.search_exact("10.0.0.0")
self.assertEqual(node, None)
node = tree.search_exact("10.0.0.0/24")
self.assertEqual(node, node3)
node = tree.search_exact("10.0.0.0/8")
self.assertEqual(node, node1)
node = tree.search_exact("10.0.0.0/16")
self.assertEqual(node.data["foo"], 12345)
def test_04__search_best(self):
tree = radix.Radix()
node1 = tree.add("10.0.0.0/8")
node2 = tree.add("10.0.0.0/16")
node3 = tree.add("10.0.0.0/24")
node = tree.search_best("127.0.0.1")
self.assertEqual(node, None)
node = tree.search_best("10.0.0.0")
self.assertEqual(node, node3)
node = tree.search_best("10.0.0.0/24")
self.assertEqual(node, node3)
node = tree.search_best("10.0.1.0/24")
self.assertEqual(node, node2)
def test_05__concurrent_trees(self):
tree1 = radix.Radix()
node1_1 = tree1.add("20.0.0.0/8")
node1_1 = tree1.add("10.0.0.0/8")
node1_2 = tree1.add("10.0.0.0/16")
node1_3 = tree1.add("10.0.0.0/24")
node1_3.data["blah"] = 12345
tree2 = radix.Radix()
node2_1 = tree2.add("30.0.0.0/8")
node2_1 = tree2.add("10.0.0.0/8")
node2_2 = tree2.add("10.0.0.0/16")
node2_3 = tree2.add("10.0.0.0/24")
node2_3.data["blah"] = 45678
self.assertNotEqual(tree1, tree2)
self.assertNotEqual(node1_2, node2_2)
node = tree1.search_best("10.0.1.0/24")
self.assertEqual(node, node1_2)
self.assertNotEqual(node, node2_2)
node = tree2.search_best("20.0.0.0/24")
self.assertEqual(node, None)
node = tree2.search_best("10.0.0.10")
self.assertEqual(node.data["blah"], 45678)
def test_06__deletes(self):
tree = radix.Radix()
node1 = tree.add("10.0.0.0/8")
node3 = tree.add("10.0.0.0/24")
tree.delete("10.0.0.0/24")
self.assertRaises(KeyError, tree.delete, "127.0.0.1")
self.assertRaises(KeyError, tree.delete, "10.0.0.0/24")
node = tree.search_best("10.0.0.10")
self.assertEqual(node, node1)
def test_07__nodes(self):
tree = radix.Radix()
prefixes = [
"10.0.0.0/8", "127.0.0.1/32",
"10.1.0.0/16", "10.100.100.100/32",
"abcd:ef12::/32", "abcd:ef01:2345:6789::/64", "::1/128"
]
prefixes.sort()
for prefix in prefixes:
tree.add(prefix)
nodes = tree.nodes()
addrs = map(lambda x: x.prefix, nodes)
addrs.sort()
self.assertEqual(addrs, prefixes)
def test_08__nodes_empty_tree(self):
tree = radix.Radix()
nodes = tree.nodes()
self.assertEqual(nodes, [])
def test_09__prefixes(self):
tree = radix.Radix()
prefixes = [
"10.0.0.0/8", "127.0.0.1/32",
"10.1.0.0/16", "10.100.100.100/32",
"abcd:ef12::/32", "abcd:ef01:2345:6789::/64", "::1/128"
]
prefixes.sort()
for prefix in prefixes:
tree.add(prefix)
addrs = tree.prefixes()
addrs.sort()
self.assertEqual(addrs, prefixes)
def test_10__use_after_free(self):
tree = radix.Radix()
node1 = tree.add("10.0.0.0/8")
del tree
self.assertEquals(node1.prefix, "10.0.0.0/8")
def test_11__unique_instance(self):
tree = radix.Radix()
node1 = tree.add("10.0.0.0/8")
node2 = tree.add("10.0.0.0/8")
self.assert_(node1 is node2)
self.assert_(node1.prefix is node2.prefix)
def test_12__inconsistent_masks4(self):
tree = radix.Radix()
node1 = tree.add("10.255.255.255", 28)
node2 = tree.add(network = "10.255.255.240/28")
node3 = tree.add(network = "10.255.255.252", masklen = 28)
self.assert_(node1 is node2)
self.assert_(node1 is node3)
self.assertEquals(node1.prefix, "10.255.255.240/28")
def test_13__inconsistent_masks6(self):
tree = radix.Radix()
node1 = tree.add("dead:beef:1234:5678::", 32)
node2 = tree.add(network = "dead:beef:8888:9999::/32")
node3 = tree.add(network = "dead:beef::", masklen = 32)
self.assert_(node1 is node2)
self.assert_(node1 is node3)
self.assertEquals(node1.prefix, "dead:beef::/32")
def test_14__packed_addresses4(self):
tree = radix.Radix()
p = '\xe0\x14\x0b@'
node = tree.add(packed = p, masklen = 26)
self.assertEquals(node.family, socket.AF_INET)
self.assertEquals(node.prefix, "224.20.11.64/26")
self.assertEquals(node.packed, p)
def test_15__packed_addresses6(self):
tree = radix.Radix()
p = '\xde\xad\xbe\xef\x124Vx\x9a\xbc\xde\xf0\x00\x00\x00\x00'
node = tree.add(packed = p, masklen = 108)
self.assertEquals(node.family, socket.AF_INET6)
self.assertEquals(node.prefix, "dead:beef:1234:5678:9abc:def0::/108")
self.assertEquals(node.packed, p)
def test_16__bad_addresses(self):
tree = radix.Radix()
self.assertRaises(TypeError, tree.add)
self.assertRaises(ValueError, tree.add, "blah/32")
self.assertRaises(ValueError, tree.add, "blah", 32)
self.assertRaises(ValueError, tree.add, "127.0.0.1", -2)
self.assertRaises(ValueError, tree.add, "127.0.0.1", 64)
self.assertRaises(ValueError, tree.add, "::", -2)
self.assertRaises(ValueError, tree.add, "::", 256)
self.assertEquals(len(tree.nodes()), 0)
def test_17__mixed_address_family(self):
tree = radix.Radix()
node1 = tree.add("255.255.255.255", 32)
node2 = tree.add("ffff::/32")
node1_o = tree.search_best("255.255.255.255")
node2_o = tree.search_best("ffff::")
self.assert_(node1 is node1_o)
self.assert_(node2 is node2_o)
self.assertNotEquals(node1.prefix, node2.prefix)
self.assertNotEquals(node1.network, node2.network)
self.assertNotEquals(node1.family, node2.family)
def test_18__iterator(self):
tree = radix.Radix()
prefixes = [
"::1/128", "2000::/16", "2000::/8", "dead:beef::/64",
"ffff::/16", "10.0.0.0/8", "a00::/8", "255.255.0.0/16",
"::/0", "0.0.0.0/0"
]
prefixes.sort()
for prefix in prefixes:
tree.add(prefix)
iterprefixes = []
for node in tree:
iterprefixes.append(node.prefix)
iterprefixes.sort()
self.assertEqual(iterprefixes, prefixes)
def test_19__iterate_on_empty(self):
tree = radix.Radix()
prefixes = []
for node in tree:
prefixes.append(node.prefix)
self.assertEqual(prefixes, [])
def test_20__iterate_and_modify_tree(self):
tree = radix.Radix()
prefixes = [
"::1/128", "2000::/16", "2000::/8", "dead:beef::/64",
"0.0.0.0/8", "127.0.0.1/32"
]
prefixes.sort()
for prefix in prefixes:
tree.add(prefix)
self.assertRaises(RuntimeWarning, map, lambda x: tree.delete(x.prefix), tree)
def test_21__lots_of_prefixes(self):
tree = radix.Radix()
num_nodes_in = 0
for i in range(0,128):
for j in range(0,128):
k = ((i + j) % 8) + 24
node = tree.add("1.%d.%d.0" % (i, j), k)
node.data["i"] = i
node.data["j"] = j
num_nodes_in += 1
num_nodes_del = 0
for i in range(0,128,5):
for j in range(0,128,3):
k = ((i + j) % 8) + 24
tree.delete("1.%d.%d.0" % (i, j), k)
num_nodes_del += 1
num_nodes_out = 0
for node in tree:
i = node.data["i"]
j = node.data["j"]
k = ((i + j) % 8) + 24
prefix = "1.%d.%d.0/%d" % (i, j, k)
self.assertEquals(node.prefix, prefix)
num_nodes_out += 1
self.assertEquals(num_nodes_in - num_nodes_del, num_nodes_out)
self.assertEquals(num_nodes_in - num_nodes_del,
len(tree.nodes()))
def test_22__broken_sanitise(self):
tree = radix.Radix()
node = tree.add("255.255.255.255/15")
self.assertEquals(node.prefix, "255.254.0.0/15")
def main():
unittest.main()
if __name__ == '__main__':
main()
syntax highlighted by Code2HTML, v. 0.9.1