Annotation of embedaddon/quagga/tests/table_test.c, revision 1.1
1.1 ! misho 1: /* $QuaggaId: Format:%an, %ai, %h$ $
! 2: *
! 3: * Routing table test
! 4: * Copyright (C) 2012 OSR.
! 5: *
! 6: * This file is part of Quagga
! 7: *
! 8: * Quagga is free software; you can redistribute it and/or modify it
! 9: * under the terms of the GNU General Public License as published by the
! 10: * Free Software Foundation; either version 2, or (at your option) any
! 11: * later version.
! 12: *
! 13: * Quagga is distributed in the hope that it will be useful, but
! 14: * WITHOUT ANY WARRANTY; without even the implied warranty of
! 15: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
! 16: * General Public License for more details.
! 17: *
! 18: * You should have received a copy of the GNU General Public License
! 19: * along with Quagga; see the file COPYING. If not, write to the Free
! 20: * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
! 21: * 02111-1307, USA.
! 22: */
! 23:
! 24: #include <zebra.h>
! 25:
! 26: #include "prefix.h"
! 27: #include "table.h"
! 28:
! 29: /*
! 30: * test_node_t
! 31: *
! 32: * Information that is kept for each node in the radix tree.
! 33: */
! 34: typedef struct test_node_t_
! 35: {
! 36:
! 37: /*
! 38: * Human readable representation of the string. Allocated using
! 39: * malloc()/dup().
! 40: */
! 41: char *prefix_str;
! 42: } test_node_t;
! 43:
! 44: struct thread_master *master;
! 45:
! 46: /*
! 47: * add_node
! 48: *
! 49: * Add the given prefix (passed in as a string) to the given table.
! 50: */
! 51: static void
! 52: add_node (struct route_table *table, const char *prefix_str)
! 53: {
! 54: struct prefix_ipv4 p;
! 55: test_node_t *node;
! 56: struct route_node *rn;
! 57:
! 58: assert (prefix_str);
! 59:
! 60: if (str2prefix_ipv4 (prefix_str, &p) <= 0)
! 61: {
! 62: assert (0);
! 63: }
! 64:
! 65: rn = route_node_get (table, (struct prefix *) &p);
! 66: if (rn->info)
! 67: {
! 68: assert (0);
! 69: return;
! 70: }
! 71:
! 72: node = malloc (sizeof (test_node_t));
! 73: assert (node);
! 74: node->prefix_str = strdup (prefix_str);
! 75: assert (node->prefix_str);
! 76: rn->info = node;
! 77: }
! 78:
! 79: /*
! 80: * add_nodes
! 81: *
! 82: * Convenience function to add a bunch of nodes together.
! 83: *
! 84: * The arguments must be prefixes in string format, with a NULL as the
! 85: * last argument.
! 86: */
! 87: static void
! 88: add_nodes (struct route_table *table, ...)
! 89: {
! 90: va_list arglist;
! 91: char *prefix;
! 92:
! 93: va_start (arglist, table);
! 94:
! 95: prefix = va_arg (arglist, char *);
! 96: while (prefix)
! 97: {
! 98: add_node (table, prefix);
! 99: prefix = va_arg (arglist, char *);
! 100: }
! 101:
! 102: va_end (arglist);
! 103: }
! 104:
! 105: /*
! 106: * print_subtree
! 107: *
! 108: * Recursive function to print a route node and its children.
! 109: *
! 110: * @see print_table
! 111: */
! 112: static void
! 113: print_subtree (struct route_node *rn, const char *legend, int indent_level)
! 114: {
! 115: char buf[INET_ADDRSTRLEN + 4];
! 116: int i;
! 117:
! 118: /*
! 119: * Print this node first.
! 120: */
! 121: for (i = 0; i < indent_level; i++)
! 122: {
! 123: printf (" ");
! 124: }
! 125:
! 126: prefix2str (&rn->p, buf, sizeof (buf));
! 127: printf ("%s: %s", legend, buf);
! 128: if (!rn->info)
! 129: {
! 130: printf (" (internal)");
! 131: }
! 132: printf ("\n");
! 133: if (rn->l_left)
! 134: {
! 135: print_subtree (rn->l_left, "Left", indent_level + 1);
! 136: }
! 137: if (rn->l_right)
! 138: {
! 139: print_subtree (rn->l_right, "Right", indent_level + 1);
! 140: }
! 141: }
! 142:
! 143: /*
! 144: * print_table
! 145: *
! 146: * Function that prints out the internal structure of a route table.
! 147: */
! 148: static void
! 149: print_table (struct route_table *table)
! 150: {
! 151: struct route_node *rn;
! 152:
! 153: rn = table->top;
! 154:
! 155: if (!rn)
! 156: {
! 157: printf ("<Empty Table>\n");
! 158: return;
! 159: }
! 160:
! 161: print_subtree (rn, "Top", 0);
! 162: }
! 163:
! 164: /*
! 165: * clear_table
! 166: *
! 167: * Remove all nodes from the given table.
! 168: */
! 169: static void
! 170: clear_table (struct route_table *table)
! 171: {
! 172: route_table_iter_t iter;
! 173: struct route_node *rn;
! 174: test_node_t *node;
! 175:
! 176: route_table_iter_init (&iter, table);
! 177:
! 178: while ((rn = route_table_iter_next (&iter)))
! 179: {
! 180: node = rn->info;
! 181: if (!node)
! 182: {
! 183: continue;
! 184: }
! 185: rn->info = NULL;
! 186: route_unlock_node (rn);
! 187: free (node->prefix_str);
! 188: free (node);
! 189: }
! 190:
! 191: route_table_iter_cleanup (&iter);
! 192:
! 193: assert (table->top == NULL);
! 194: }
! 195:
! 196: /*
! 197: * verify_next_by_iterating
! 198: *
! 199: * Iterate over the tree to make sure that the first prefix after
! 200: * target_pfx is the expected one. Note that target_pfx may not be
! 201: * present in the tree.
! 202: */
! 203: static void
! 204: verify_next_by_iterating (struct route_table *table,
! 205: struct prefix *target_pfx, struct prefix *next_pfx)
! 206: {
! 207: route_table_iter_t iter;
! 208: struct route_node *rn;
! 209:
! 210: route_table_iter_init (&iter, table);
! 211: while ((rn = route_table_iter_next (&iter)))
! 212: {
! 213: if (route_table_prefix_iter_cmp (&rn->p, target_pfx) > 0)
! 214: {
! 215: assert (!prefix_cmp (&rn->p, next_pfx));
! 216: break;
! 217: }
! 218: }
! 219:
! 220: if (!rn)
! 221: {
! 222: assert (!next_pfx);
! 223: }
! 224:
! 225: route_table_iter_cleanup (&iter);
! 226: }
! 227:
! 228: /*
! 229: * verify_next
! 230: *
! 231: * Verifies that route_table_get_next() returns the expected result
! 232: * (result) for the prefix string 'target'.
! 233: */
! 234: static void
! 235: verify_next (struct route_table *table, const char *target, const char *next)
! 236: {
! 237: struct prefix_ipv4 target_pfx, next_pfx;
! 238: struct route_node *rn;
! 239: char result_buf[INET_ADDRSTRLEN + 4];
! 240:
! 241: if (str2prefix_ipv4 (target, &target_pfx) <= 0)
! 242: {
! 243: assert (0);
! 244: }
! 245:
! 246: rn = route_table_get_next (table, (struct prefix *) &target_pfx);
! 247: if (rn)
! 248: {
! 249: prefix2str (&rn->p, result_buf, sizeof (result_buf));
! 250: }
! 251: else
! 252: {
! 253: snprintf (result_buf, sizeof (result_buf), "(Null)");
! 254: }
! 255:
! 256: printf ("\n");
! 257: print_table (table);
! 258: printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target,
! 259: next ? next : "(Null)", result_buf);
! 260:
! 261: if (!rn)
! 262: {
! 263: assert (!next);
! 264: verify_next_by_iterating (table, (struct prefix *) &target_pfx, NULL);
! 265: return;
! 266: }
! 267:
! 268: assert (next);
! 269:
! 270: if (str2prefix_ipv4 (next, &next_pfx) <= 0)
! 271: {
! 272: assert (0);
! 273: }
! 274:
! 275: if (prefix_cmp (&rn->p, (struct prefix *) &next_pfx))
! 276: {
! 277: assert (0);
! 278: }
! 279: route_unlock_node (rn);
! 280:
! 281: verify_next_by_iterating (table, (struct prefix *) &target_pfx,
! 282: (struct prefix *) &next_pfx);
! 283: }
! 284:
! 285: /*
! 286: * test_get_next
! 287: */
! 288: static void
! 289: test_get_next (void)
! 290: {
! 291: struct route_table *table;
! 292:
! 293: printf ("\n\nTesting route_table_get_next()\n");
! 294: table = route_table_init ();
! 295:
! 296: /*
! 297: * Target exists in tree, but has no successor.
! 298: */
! 299: add_nodes (table, "1.0.1.0/24", NULL);
! 300: verify_next (table, "1.0.1.0/24", NULL);
! 301: clear_table (table);
! 302:
! 303: /*
! 304: * Target exists in tree, and there is a node in its left subtree.
! 305: */
! 306: add_nodes (table, "1.0.1.0/24", "1.0.1.0/25", NULL);
! 307: verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
! 308: clear_table (table);
! 309:
! 310: /*
! 311: * Target exists in tree, and there is a node in its right subtree.
! 312: */
! 313: add_nodes (table, "1.0.1.0/24", "1.0.1.128/25", NULL);
! 314: verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
! 315: clear_table (table);
! 316:
! 317: /*
! 318: * Target exists in the tree, next node is outside subtree.
! 319: */
! 320: add_nodes (table, "1.0.1.0/24", "1.1.0.0/16", NULL);
! 321: verify_next (table, "1.0.1.0/24", "1.1.0.0/16");
! 322: clear_table (table);
! 323:
! 324: /*
! 325: * The target node does not exist in the tree for all the test cases
! 326: * below this point.
! 327: */
! 328:
! 329: /*
! 330: * There is no successor in the tree.
! 331: */
! 332: add_nodes (table, "1.0.0.0/16", NULL);
! 333: verify_next (table, "1.0.1.0/24", NULL);
! 334: clear_table (table);
! 335:
! 336: /*
! 337: * There exists a node that would be in the target's left subtree.
! 338: */
! 339: add_nodes (table, "1.0.0.0/16", "1.0.1.0/25", NULL);
! 340: verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
! 341: clear_table (table);
! 342:
! 343: /*
! 344: * There exists a node would be in the target's right subtree.
! 345: */
! 346: add_nodes (table, "1.0.0.0/16", "1.0.1.128/25", NULL);
! 347: verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
! 348: clear_table (table);
! 349:
! 350: /*
! 351: * A search for the target reaches a node where there are no child
! 352: * nodes in the direction of the target (left), but the node has a
! 353: * right child.
! 354: */
! 355: add_nodes (table, "1.0.0.0/16", "1.0.128.0/17", NULL);
! 356: verify_next (table, "1.0.0.0/17", "1.0.128.0/17");
! 357: clear_table (table);
! 358:
! 359: /*
! 360: * A search for the target reaches a node with no children. We have
! 361: * to go upwards in the tree to find a successor.
! 362: */
! 363: add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
! 364: "1.0.128.0/17", NULL);
! 365: verify_next (table, "1.0.1.0/25", "1.0.128.0/17");
! 366: clear_table (table);
! 367:
! 368: /*
! 369: * A search for the target reaches a node where neither the node nor
! 370: * the target prefix contain each other.
! 371: *
! 372: * In first case below the node succeeds the target.
! 373: *
! 374: * In the second case, the node comes before the target, so we have
! 375: * to go up the tree looking for a successor.
! 376: */
! 377: add_nodes (table, "1.0.0.0/16", "1.0.1.0/24", NULL);
! 378: verify_next (table, "1.0.0.0/24", "1.0.1.0/24");
! 379: clear_table (table);
! 380:
! 381: add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
! 382: "1.0.128.0/17", NULL);
! 383: verify_next (table, "1.0.1.128/25", "1.0.128.0/17");
! 384: clear_table (table);
! 385:
! 386: route_table_finish (table);
! 387: }
! 388:
! 389: /*
! 390: * verify_prefix_iter_cmp
! 391: */
! 392: static void
! 393: verify_prefix_iter_cmp (const char *p1, const char *p2, int exp_result)
! 394: {
! 395: struct prefix_ipv4 p1_pfx, p2_pfx;
! 396: int result;
! 397:
! 398: if (str2prefix_ipv4 (p1, &p1_pfx) <= 0)
! 399: {
! 400: assert (0);
! 401: }
! 402:
! 403: if (str2prefix_ipv4 (p2, &p2_pfx) <= 0)
! 404: {
! 405: assert (0);
! 406: }
! 407:
! 408: result = route_table_prefix_iter_cmp ((struct prefix *) &p1_pfx,
! 409: (struct prefix *) &p2_pfx);
! 410:
! 411: printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
! 412:
! 413: assert (exp_result == result);
! 414:
! 415: /*
! 416: * Also check the reverse comparision.
! 417: */
! 418: result = route_table_prefix_iter_cmp ((struct prefix *) &p2_pfx,
! 419: (struct prefix *) &p1_pfx);
! 420:
! 421: if (exp_result)
! 422: {
! 423: exp_result = -exp_result;
! 424: }
! 425:
! 426: printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
! 427: assert (result == exp_result);
! 428: }
! 429:
! 430: /*
! 431: * test_prefix_iter_cmp
! 432: *
! 433: * Tests comparision of prefixes according to order of iteration.
! 434: */
! 435: static void
! 436: test_prefix_iter_cmp ()
! 437: {
! 438: printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
! 439:
! 440: verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
! 441:
! 442: verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
! 443:
! 444: verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
! 445: }
! 446:
! 447: /*
! 448: * verify_iter_with_pause
! 449: *
! 450: * Iterates over a tree using two methods: 'normal' iteration, and an
! 451: * iterator that pauses at each node. Verifies that the two methods
! 452: * yield the same results.
! 453: */
! 454: static void
! 455: verify_iter_with_pause (struct route_table *table)
! 456: {
! 457: unsigned long num_nodes;
! 458: struct route_node *rn, *iter_rn;
! 459: route_table_iter_t iter_space;
! 460: route_table_iter_t *iter = &iter_space;
! 461:
! 462: route_table_iter_init (iter, table);
! 463: num_nodes = 0;
! 464:
! 465: for (rn = route_top (table); rn; rn = route_next (rn))
! 466: {
! 467: num_nodes++;
! 468: route_table_iter_pause (iter);
! 469:
! 470: assert (iter->current == NULL);
! 471: if (route_table_iter_started (iter))
! 472: {
! 473: assert (iter->state == RT_ITER_STATE_PAUSED);
! 474: }
! 475: else
! 476: {
! 477: assert (rn == table->top);
! 478: assert (iter->state == RT_ITER_STATE_INIT);
! 479: }
! 480:
! 481: iter_rn = route_table_iter_next (iter);
! 482:
! 483: /*
! 484: * Make sure both iterations return the same node.
! 485: */
! 486: assert (rn == iter_rn);
! 487: }
! 488:
! 489: assert (num_nodes == route_table_count (table));
! 490:
! 491: route_table_iter_pause (iter);
! 492: iter_rn = route_table_iter_next (iter);
! 493:
! 494: assert (iter_rn == NULL);
! 495: assert (iter->state == RT_ITER_STATE_DONE);
! 496:
! 497: assert (route_table_iter_next (iter) == NULL);
! 498: assert (iter->state == RT_ITER_STATE_DONE);
! 499:
! 500: route_table_iter_cleanup (iter);
! 501:
! 502: print_table (table);
! 503: printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes);
! 504: }
! 505:
! 506: /*
! 507: * test_iter_pause
! 508: */
! 509: static void
! 510: test_iter_pause (void)
! 511: {
! 512: struct route_table *table;
! 513: int i, num_prefixes;
! 514: const char *prefixes[] = {
! 515: "1.0.1.0/24",
! 516: "1.0.1.0/25",
! 517: "1.0.1.128/25",
! 518: "1.0.2.0/24",
! 519: "2.0.0.0/8"
! 520: };
! 521:
! 522: num_prefixes = sizeof (prefixes) / sizeof (prefixes[0]);
! 523:
! 524: printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
! 525: table = route_table_init ();
! 526: for (i = 0; i < num_prefixes; i++)
! 527: {
! 528: add_nodes (table, prefixes[i], NULL);
! 529: }
! 530:
! 531: verify_iter_with_pause (table);
! 532:
! 533: clear_table (table);
! 534: route_table_finish (table);
! 535: }
! 536:
! 537: /*
! 538: * run_tests
! 539: */
! 540: static void
! 541: run_tests (void)
! 542: {
! 543: test_prefix_iter_cmp ();
! 544: test_get_next ();
! 545: test_iter_pause ();
! 546: }
! 547:
! 548: /*
! 549: * main
! 550: */
! 551: int
! 552: main (void)
! 553: {
! 554: run_tests ();
! 555: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to table_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / tests