// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
// Copyright (c) 2001-2007 International Computer Science Institute
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software")
// to deal in the Software without restriction, subject to the conditions
// listed in the XORP LICENSE file. These conditions include: you must
// preserve this copyright notice, and you cannot mention the copyright
// holders in advertising related to the Software without their permission.
// The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
// notice is a summary of the XORP LICENSE file; the license in that file is
// legally binding.
#ident "$XORP: xorp/libxorp/test_ref_trie.cc,v 1.15 2007/02/16 22:46:25 pavlin Exp $"
#include "libxorp_module.h"
#include "xorp.h"
#include "ipv4net.hh"
#include "ipv6net.hh"
#include "ref_trie.hh"
class IPv4RouteEntry {};
class IPv6RouteEntry {};
RefTrie<IPv4, IPv4RouteEntry*> trie;
RefTrie<IPv6, IPv6RouteEntry*> trie6;
void test(IPv4Net test_net, IPv4RouteEntry *test_route) {
printf("-----------------------------------------------\n");
printf("looking up net: %s\n", test_net.str().c_str());
RefTrie<IPv4, IPv4RouteEntry*>::iterator ti = trie.lookup_node(test_net);
if (ti == trie.end()) {
printf("Fail: no result\n");
trie.print();
abort();
}
const IPv4RouteEntry *r = ti.payload();
if (r==test_route) {
printf("PASS\n");
} else {
printf("Fail: route=%p\n", r);
trie.print();
abort();
}
printf("-----------\n");
}
void test_find(IPv4 test_addr, IPv4RouteEntry *test_route) {
printf("-----------------------------------------------\n");
printf("looking up net: %s\n", test_addr.str().c_str());
RefTrie<IPv4, IPv4RouteEntry*>::iterator ti = trie.find(test_addr);
if (ti == trie.end()) {
printf("Fail: no result\n");
trie.print();
abort();
}
const IPv4RouteEntry *r = ti.payload();
if (r==test_route) {
printf("PASS\n");
} else {
printf("Fail: route=%p\n", r);
trie.print();
abort();
}
printf("-----------\n");
}
void test_less_specific(IPv4Net test_net, IPv4RouteEntry *test_route) {
printf("-----------------------------------------------\n");
printf("looking up less specific for net: %s\n", test_net.str().c_str());
RefTrie<IPv4, IPv4RouteEntry*>::iterator ti = trie.find_less_specific(test_net);
if (ti == trie.end()) {
if (test_route == NULL) {
printf("PASS\n");
printf("-----------\n");
return;
}
printf("Fail: no result\n");
trie.print();
abort();
}
const IPv4RouteEntry *r = ti.payload();
if (r==test_route) {
printf("PASS\n");
} else {
printf("Fail: route=%p\n", r);
trie.print();
abort();
}
printf("-----------\n");
}
void test_upper_bound(IPv4 test_addr, IPv4 test_answer) {
printf("-----------------------------------------------\n");
printf("looking up upper bound: %s\n", test_addr.str().c_str());
IPv4 lo, hi;
trie.find_bounds(test_addr, lo, hi);
IPv4 result= hi;
if (test_answer == result) {
printf("Pass: result = %s\n", result.str().c_str());
} else {
printf("Fail: answer should be %s, result was %s\n",
test_answer.str().c_str(), result.str().c_str());
trie.print();
abort();
}
printf("-----------\n");
}
void test_lower_bound(IPv4 test_addr, IPv4 test_answer) {
printf("-----------------------------------------------\n");
printf("looking up lower bound: %s\n", test_addr.str().c_str());
IPv4 lo, hi;
trie.find_bounds(test_addr, lo, hi);
IPv4 result= lo;
if (test_answer == result) {
printf("Pass: result = %s\n", result.str().c_str());
} else {
printf("Fail: answer should be %s, result was %s\n",
test_answer.str().c_str(), result.str().c_str());
trie.print();
abort();
}
printf("-----------\n");
}
void test6(IPv6Net test_net, IPv6RouteEntry *test_route) {
printf("-----------------------------------------------\n");
printf("looking up net: %s\n", test_net.str().c_str());
RefTrie<IPv6, IPv6RouteEntry*>::iterator ti = trie6.lookup_node(test_net);
if (ti == trie6.end()) {
printf("Fail: no result\n");
trie.print();
abort();
}
const IPv6RouteEntry *r = ti.payload();
if (r==test_route) {
printf("PASS\n");
} else {
printf("Fail: route=%p\n", r);
trie.print();
abort();
}
printf("-----------\n");
}
void test_find6(IPv6 test_addr, IPv6RouteEntry *test_route) {
printf("-----------------------------------------------\n");
printf("looking up net: %s\n", test_addr.str().c_str());
RefTrie<IPv6, IPv6RouteEntry*>::iterator ti = trie6.find(test_addr);
const IPv6RouteEntry *r = ti.payload();
if (ti == trie6.end()) {
printf("Fail: no result\n");
trie.print();
abort();
}
if (r==test_route) {
printf("PASS\n");
} else {
printf("Fail: route=%p\n", r);
trie.print();
abort();
}
printf("-----------\n");
}
void test_upper_bound6(IPv6 test_addr, IPv6 test_answer) {
printf("-----------------------------------------------\n");
printf("looking up upper bound: %s\n", test_addr.str().c_str());
IPv6 lo, hi;
trie6.find_bounds(test_addr, lo, hi);
IPv6 result= hi;
if (test_answer == result) {
printf("Pass: result = %s\n", result.str().c_str());
} else {
printf("Fail: answer should be %s, result was %s\n",
test_answer.str().c_str(), result.str().c_str());
trie.print();
abort();
}
printf("-----------\n");
}
void test_equals_preorder()
{
printf("Remove entry that is being pointed at by an iterator\n");
// Create an trie and install a single entry
RefTrie<IPv4, IPv4RouteEntry*> test_trie;
IPv4RouteEntry d1;
IPv4Net n1("1.2.1.0/24");
printf("adding n1: %s route: %p\n", n1.str().c_str(), &d1);
test_trie.insert(n1, &d1);
// Create an iterator pointing at this entry
RefTrie<IPv4, IPv4RouteEntry*>::PreOrderIterator iter;
iter = test_trie.begin();
// Erase the entry
test_trie.erase(iter);
// The iterator is now the only thing pointing at the entry.
// Zap the iterator to allow the entry that is being pointed at to
// be removed. Used to triger a bug in the iterator code.
RefTrie<IPv4, IPv4RouteEntry*>::PreOrderIterator empty;
iter = empty;
printf("PASS\n");
}
void test_equals_postorder()
{
printf("Remove entry that is being pointed at by an iterator\n");
// Create an trie and install a single entry
RefTrie<IPv4, IPv4RouteEntry*> test_trie;
IPv4RouteEntry d1;
IPv4Net n1("1.2.1.0/24");
printf("adding n1: %s route: %p\n", n1.str().c_str(), &d1);
test_trie.insert(n1, &d1);
// Create an iterator pointing at this entry
RefTrie<IPv4, IPv4RouteEntry*>::PostOrderIterator iter;
iter = test_trie.begin();
// Erase the entry
test_trie.erase(iter);
// The iterator is now the only thing pointing at the entry.
// Zap the iterator to allow the entry that is being pointed at to
// be removed. Used to triger a bug in the iterator code.
RefTrie<IPv4, IPv4RouteEntry*>::PostOrderIterator empty;
iter = empty;
printf("PASS\n");
}
int main() {
IPv4RouteEntry d1;
IPv4Net n1(IPv4("1.2.1.0"), 24);
printf("adding n1: %s route: %p\n", n1.str().c_str(), &d1);
trie.insert(n1, &d1);
test(n1, &d1);
IPv4RouteEntry d2;
IPv4Net n2(IPv4("1.2.0.0"), 16);
printf("\n\nadding n2: %s route: %p\n", n2.str().c_str(), &d2);
trie.insert(n2, &d2);
test(n1, &d1);
test(n2, &d2);
IPv4RouteEntry d3;
IPv4Net n3(IPv4("1.2.3.0"), 24);
printf("\n\nadding n3: %s route: %p\n", n3.str().c_str(), &d3);
trie.insert(n3, &d3);
test(n1, &d1);
test(n2, &d2);
test(n3, &d3);
IPv4RouteEntry d4;
IPv4Net n4(IPv4("1.2.128.0"), 24);
printf("\n\nadding n4: %s route: %p\n", n4.str().c_str(), &d4);
trie.insert(n4, &d4);
test(n1, &d1);
test(n2, &d2);
test(n3, &d3);
test(n4, &d4);
IPv4RouteEntry d5;
IPv4Net n5(IPv4("1.2.0.0"), 20);
printf("\n\nadding n5: %s route: %p\n", n5.str().c_str(), &d5);
trie.insert(n5, &d5);
test(n1, &d1);
test(n2, &d2);
test(n3, &d3);
test(n4, &d4);
test(n5, &d5);
trie.print();
trie.erase(n5);
test(n1, &d1);
test(n2, &d2);
test(n3, &d3);
test(n4, &d4);
trie.print();
trie.erase(n1);
test(n2, &d2);
test(n3, &d3);
test(n4, &d4);
trie.print();
trie.erase(n2);
test(n3, &d3);
test(n4, &d4);
trie.print();
trie.insert(n2, &d2);
trie.erase(n3);
test(n2, &d2);
test(n4, &d4);
trie.print();
IPv4RouteEntry d6;
IPv4Net n6(IPv4("1.2.192.0"), 24);
printf("\n\nadding n6: %s route: %p\n", n6.str().c_str(), &d6);
trie.insert(n6, &d6);
test(n2, &d2);
test(n4, &d4);
test(n6, &d6);
test_find(IPv4("1.2.192.1"), &d6);
test_find(IPv4("1.2.191.1"), &d2);
trie.print();
test_upper_bound(IPv4("1.2.190.1"), IPv4("1.2.191.255"));
test_lower_bound(IPv4("1.2.190.1"), IPv4("1.2.129.0"));
test_upper_bound(IPv4("1.2.120.1"), IPv4("1.2.127.255"));
test_lower_bound(IPv4("1.2.120.1"), IPv4("1.2.0.0"));
test_upper_bound(IPv4("1.2.192.1"), IPv4("1.2.192.255"));
test_lower_bound(IPv4("1.2.192.1"), IPv4("1.2.192.0"));
test_upper_bound(IPv4("1.2.128.1"), IPv4("1.2.128.255"));
test_lower_bound(IPv4("1.2.128.1"), IPv4("1.2.128.0"));
test_upper_bound(IPv4("1.2.193.1"), IPv4("1.2.255.255"));
test_lower_bound(IPv4("1.2.193.1"), IPv4("1.2.193.0"));
trie.erase(n4);
test_upper_bound(IPv4("1.2.128.1"), IPv4("1.2.191.255"));
test_lower_bound(IPv4("1.2.128.1"), IPv4("1.2.0.0"));
test_lower_bound(IPv4("1.2.190.1"), IPv4("1.2.0.0"));
trie.erase(n6);
test_upper_bound(IPv4("1.2.128.1"), IPv4("1.2.255.255"));
test_lower_bound(IPv4("1.2.128.1"), IPv4("1.2.0.0"));
trie.erase(n2);
test_upper_bound(IPv4("1.2.128.1"), IPv4("255.255.255.255"));
test_lower_bound(IPv4("1.2.128.1"), IPv4("0.0.0.0"));
IPv6RouteEntry d7;
IPv6 ip6a("fe80::2c0:4fff:fe68:8c58");
IPv6Net ip6net(ip6a, 96);
trie6.insert(ip6net, &d7);
test6(ip6net, &d7);
test_find6(ip6a, &d7);
test_upper_bound6(ip6a, IPv6("fe80::2c0:4fff:ffff:ffff"));
//attempts to test remaining code paths
trie.print();
trie.insert(n2, &d2);
trie.insert(n3, &d3);
trie.insert(n1, &d1);
IPv4RouteEntry d8;
IPv4Net n8(IPv4("1.2.3.0"), 23);
trie.insert(n8, &d8);
trie.print();
trie.erase(n8);
IPv4RouteEntry d9;
IPv4Net n9(IPv4("1.2.2.0"), 24);
trie.insert(n9, &d9);
trie.print();
trie.erase(n9);
trie.erase(n2);
IPv4RouteEntry d10;
IPv4Net n10(IPv4("1.2.0.0"), 15);
trie.insert(n10, &d10); /* 1.2.0.0/15 */
trie.print();
trie.erase(n10);
trie.insert(n2, &d2); /* 1.2.0.0/16 */
trie.print();
IPv4RouteEntry d11;
IPv4Net n11(IPv4("1.0.0.0"), 14);
trie.insert(n11, &d11);
trie.print();
trie.insert(n10, &d10); /* 1.2.0.0/15 */
trie.print();
trie.erase(n11);
IPv4RouteEntry d12;
IPv4Net n12(IPv4("1.3.0.0"), 17);
trie.insert(n12, &d12);
trie.print();
trie.erase(n2);
test_find(IPv4("1.2.2.1"), &d10);
test_less_specific(n1, &d10); /* 1.2.1.0/24 */
test_less_specific(n3, &d10); /* 1.2.3.0/24 */
test_less_specific(n12, &d10); /* 1.3.0.0/17 */
test_less_specific(n10, NULL); /* 1.2.0.0/15 */
test_less_specific(n4, &d10); /* 1.2.128.0/24 */
trie.print();
test_lower_bound(IPv4("1.2.128.1"), IPv4("1.2.4.0"));
test_upper_bound(IPv4("1.2.0.1"), IPv4("1.2.0.255"));
trie.print();
trie.erase(n10); /* 1.0.0.0/14 */
trie.insert(n11, &d11); /* 1.0.0.0/14 */
trie.print();
test_upper_bound(IPv4("1.0.0.1"), IPv4("1.2.0.255"));
trie.erase(n11);
test_lower_bound(IPv4("1.0.0.1"), IPv4("0.0.0.0"));
test_upper_bound(IPv4("1.3.128.1"), IPv4("255.255.255.255"));
test_upper_bound(IPv4("1.2.2.1"), IPv4("1.2.2.255"));
trie.print();
RefTrie<IPv4, IPv4RouteEntry*>::iterator iter;
IPv4Net subroot(IPv4("1.2.0.0"), 21);
iter = trie.search_subtree(subroot);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
trie.erase(n3);
trie.erase(n1);
trie.insert(n11, &d11);
trie.print();
iter = trie.search_subtree(subroot);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
trie.insert(n1, &d1);
trie.erase(n1);
iter = trie.search_subtree(subroot);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
trie.erase(n12);
trie.insert(n1, &d1);
trie.insert(n3, &d3);
trie.erase(n1);
iter = trie.search_subtree(subroot);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
trie.insert(n10, &d10);
trie.insert(n1, &d1);
trie.insert(n9, &d9);
trie.print();
iter = trie.search_subtree(n10);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
trie.print();
iter = trie.search_subtree(n3);
while (iter!=trie.end()) {
printf("------\n");
iter++;
}
//-------------------------------------------------------
printf("Test replacement of interior node\n");
IPv4Net n13(IPv4("1.2.2.0"), 23);
IPv4RouteEntry d13;
trie.insert(n13, &d13);
trie.print();
//-------------------------------------------------------
printf("==================\nTest of begin()\n");
trie.erase(n11);
trie.erase(n10);
trie.print();
//-------------------------------------------------------
printf("==================\nTest of lower_bound()\n");
trie.print();
iter = trie.lower_bound(n1); /*1.2.1.0/24*/
assert(iter.key() == n1);
iter = trie.lower_bound(n9); /*1.2.2.0/24*/
assert(iter.key() == n9);
iter = trie.lower_bound(n3); /*1.2.3.0/24*/
assert(iter.key() == n3);
iter = trie.lower_bound(n13); /*1.2.2.0/23*/
assert(iter.key() == n13);
iter = trie.lower_bound(IPNet<IPv4>("1.2.1.128/25"));
assert(iter.key() == n1); /*1.2.1.0/24*/
iter = trie.lower_bound(IPNet<IPv4>("1.2.4.128/25"));
assert(iter == trie.end());
iter = trie.lower_bound(IPNet<IPv4>("1.2.1.0/23"));
assert(iter.key() == n9); /*1.2.2.0/24*/
iter = trie.lower_bound(IPNet<IPv4>("1.0.0.0/24"));
if (iter != trie.end())
printf("iter.key = %s\n", iter.key().str().c_str());
else
printf("iter = end\n");
assert(iter.key() == n1); /*1.2.1.0/24*/
//-------------------------------------------------------
printf("Test /32 prefix works\n");
IPv4Net n14(IPv4("9.9.9.9"), 32);
IPv4RouteEntry d14;
IPv4Net n15(IPv4("9.9.9.9"), 24);
IPv4RouteEntry d15;
trie.insert(n14, &d14);
trie.insert(n15, &d15);
test_find(IPv4("9.9.9.9"), &d14);
test_find(IPv4("9.9.9.8"), &d15);
trie.erase(n14);
trie.erase(n15);
trie.erase(n1);
trie.erase(n3);
trie.erase(n9);
trie.erase(n13);
printf("==================\nTest of preorder iterator\n");
// this is the list of subnets in prefix order. The test consists in
// inserting a list of unsorted subnets and check that the preorder
// iterator retrieves them in the proper order.
const char * subnets[] = { "1.2.0.0/16",
"1.2.0.0/20",
"1.2.1.0/24",
"1.2.3.0/24",
"1.2.128.0/24" };
IPv4RouteEntry d16;
IPv4Net n16(subnets[3]);
printf("adding n16: %s route: %p\n", n16.str().c_str(), &d16);
trie.insert(n16, &d16);
IPv4RouteEntry d17;
IPv4Net n17(subnets[2]);
printf("adding n17: %s route: %p\n", n17.str().c_str(), &d17);
trie.insert(n17, &d17);
IPv4RouteEntry d18;
IPv4Net n18(subnets[0]);
printf("adding n18: %s route: %p\n", n18.str().c_str(), &d18);
trie.insert(n18, &d18);
IPv4RouteEntry d19;
IPv4Net n19(subnets[4]);
printf("adding n19: %s route: %p\n", n19.str().c_str(), &d19);
trie.insert(n19, &d19);
IPv4RouteEntry d20;
IPv4Net n20(subnets[1]);
printf("adding n20: %s route: %p\n", n20.str().c_str(), &d20);
trie.insert(n20, &d20);
//-------------------------------------------------------
printf("-----------\n");
printf("Test of prefix increment (++ti)\n");
printf("-----------\n");
RefTrie<IPv4, IPv4RouteEntry*>::PreOrderIterator ti;
int subnetidx = 0;
for (ti = trie.begin() ; ti != trie.end() ; ++ti) {
printf("*** node: %-26s %s\n",
ti.cur()->k().str().c_str(),
ti.cur()->has_payload() ? "PL" : "[]");
if (strcmp(subnets[subnetidx++],ti.cur()->k().str().c_str())) {
fprintf(stderr, "invalid traversal order detected!\n");
exit(1);
}
if (!ti.cur()->has_payload()) {
fprintf(stderr, "iterator should not return empty nodes!\n");
exit(1);
}
}
if (subnetidx != 5) {
fprintf(stderr, "iterator missing nodes!\n");
exit(1);
}
printf("PASS\n");
//-------------------------------------------------------
printf("-----------\n");
printf("Test of postfix increment (ti++)\n");
printf("-----------\n");
subnetidx = 0;
for (ti = trie.begin() ; ti != trie.end() ; ti++) {
printf("*** node: %-26s %s\n",
ti.cur()->k().str().c_str(),
ti.cur()->has_payload() ? "PL" : "[]");
if (strcmp(subnets[subnetidx++],ti.cur()->k().str().c_str())) {
fprintf(stderr, "invalid traversal order detected!\n");
exit(1);
}
if (!ti.cur()->has_payload()) {
fprintf(stderr, "iterator should not return empty nodes!\n");
exit(1);
}
}
if (subnetidx != 5) {
fprintf(stderr, "iterator missing nodes!\n");
exit(1);
}
printf("PASS\n");
test_equals_postorder();
test_equals_preorder();
#if 0
//-------------------------------------------------------
printf("-----------\n");
printf("Test of iterator, with insertion\n");
printf("-----------\n");
IPv4RouteEntry d21;
IPv4Net n21("1.2.2.0", 24);
int cnt;
int insert_pos = 0;
int entries = trie.route_count();
RefTrie<IPv4, IPv4RouteEntry*>::iterator iteri;
for(cnt = 0, iteri = trie.begin(); iteri != trie.end(); iteri++, cnt++) {
if (n21 > iteri.cur()->k()) {
printf("*** node: %-26s %s\n", iteri.cur()->k().str().c_str(),
iteri.cur()->has_payload() ? "PL" : "[]");
insert_pos = cnt;
break;
}
}
for(cnt = 0, iteri = trie.begin(); iteri != trie.end(); iteri++, cnt++) {
if (cnt == insert_pos) {
printf("adding n21: %s route: %p\n", n21.str().c_str(), &d21);
trie.insert(n21, &d21);
}
printf("*** node: %-26s %s\n", iteri.cur()->k().str().c_str(),
iteri.cur()->has_payload() ? "PL" : "[]");
}
if(entries != cnt) {
fprintf(stderr,
"Failed to print correct number of nodes inserted\n");
exit(1);
}
printf("PASS\n");
IPv4Net prev = trie.begin().cur()->k();
for(iteri = trie.begin(); iteri != trie.end(); iteri++, cnt++) {
printf("*** node: %-26s %s\n", iteri.cur()->k().str().c_str(),
iteri.cur()->has_payload() ? "PL" : "[]");
if (iteri.cur()->k() < prev) {
fprintf(stderr,
"Ordering problem\n");
exit(1);
}
prev = iteri.cur()->k();
}
printf("PASS\n");
#endif
}
syntax highlighted by Code2HTML, v. 0.9.1