#!/usr/bin/env python # Copyright (c) 2004 Damien Miller # # 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.15 2007/12/18 00:53:53 djm Exp $ import radix import unittest import socket import pickle import cPickle class TestRadix(unittest.TestCase): def test_00__create_destroy(self): tree = radix.Radix() self.assertEqual(str(type(tree)), "") del tree def test_01__create_node(self): tree = radix.Radix() node = tree.add("10.0.0.0/8") self.assertEqual(str(type(node)), "") 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 test_21__pickle(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 addr = "1.%d.%d.0" % (i, j) node = tree.add(addr, k) node.data["i"] = i node.data["j"] = j num_nodes_in += 1 tree_pickled = pickle.dumps(tree) del tree tree2 = pickle.loads(tree_pickled) for i in range(0,128): for j in range(0,128): k = ((i + j) % 8) + 24 addr = "1.%d.%d.0" % (i, j) node = tree2.search_exact(addr, k) self.assertNotEquals(node, None) self.assertEquals(node.data["i"], i) self.assertEquals(node.data["j"], j) node.data["j"] = j self.assertEquals(len(tree2.nodes()), num_nodes_in) def test_21__cpickle(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 addr = "1.%d.%d.0" % (i, j) node = tree.add(addr, k) node.data["i"] = i node.data["j"] = j num_nodes_in += 1 tree_pickled = cPickle.dumps(tree) del tree tree2 = cPickle.loads(tree_pickled) for i in range(0,128): for j in range(0,128): k = ((i + j) % 8) + 24 addr = "1.%d.%d.0" % (i, j) node = tree2.search_exact(addr, k) self.assertNotEquals(node, None) self.assertEquals(node.data["i"], i) self.assertEquals(node.data["j"], j) node.data["j"] = j self.assertEquals(len(tree2.nodes()), num_nodes_in) def main(): unittest.main() if __name__ == '__main__': main()