3 * Copyright (C) 2012 OSR.
5 * This file is part of Quagga
7 * Quagga is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2, or (at your option) any
12 * Quagga is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Quagga; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
31 * Information that is kept for each node in the radix tree.
33 typedef struct test_node_t_
37 * Human readable representation of the string. Allocated using
43 struct thread_master
*master
;
48 * Add the given prefix (passed in as a string) to the given table.
51 add_node (struct route_table
*table
, const char *prefix_str
)
55 struct route_node
*rn
;
59 if (str2prefix_ipv4 (prefix_str
, &p
) <= 0)
64 rn
= route_node_get (table
, (struct prefix
*) &p
);
71 node
= malloc (sizeof (test_node_t
));
73 node
->prefix_str
= strdup (prefix_str
);
74 assert (node
->prefix_str
);
81 * Convenience function to add a bunch of nodes together.
83 * The arguments must be prefixes in string format, with a NULL as the
87 add_nodes (struct route_table
*table
, ...)
92 va_start (arglist
, table
);
94 prefix
= va_arg (arglist
, char *);
97 add_node (table
, prefix
);
98 prefix
= va_arg (arglist
, char *);
107 * Recursive function to print a route node and its children.
112 print_subtree (struct route_node
*rn
, const char *legend
, int indent_level
)
114 char buf
[PREFIX2STR_BUFFER
];
118 * Print this node first.
120 for (i
= 0; i
< indent_level
; i
++)
125 prefix2str (&rn
->p
, buf
, sizeof (buf
));
126 printf ("%s: %s", legend
, buf
);
129 printf (" (internal)");
134 print_subtree (rn
->l_left
, "Left", indent_level
+ 1);
138 print_subtree (rn
->l_right
, "Right", indent_level
+ 1);
145 * Function that prints out the internal structure of a route table.
148 print_table (struct route_table
*table
)
150 struct route_node
*rn
;
156 printf ("<Empty Table>\n");
160 print_subtree (rn
, "Top", 0);
166 * Remove all nodes from the given table.
169 clear_table (struct route_table
*table
)
171 route_table_iter_t iter
;
172 struct route_node
*rn
;
175 route_table_iter_init (&iter
, table
);
177 while ((rn
= route_table_iter_next (&iter
)))
185 route_unlock_node (rn
);
186 free (node
->prefix_str
);
190 route_table_iter_cleanup (&iter
);
192 assert (table
->top
== NULL
);
196 * verify_next_by_iterating
198 * Iterate over the tree to make sure that the first prefix after
199 * target_pfx is the expected one. Note that target_pfx may not be
200 * present in the tree.
203 verify_next_by_iterating (struct route_table
*table
,
204 struct prefix
*target_pfx
, struct prefix
*next_pfx
)
206 route_table_iter_t iter
;
207 struct route_node
*rn
;
209 route_table_iter_init (&iter
, table
);
210 while ((rn
= route_table_iter_next (&iter
)))
212 if (route_table_prefix_iter_cmp (&rn
->p
, target_pfx
) > 0)
214 assert (!prefix_cmp (&rn
->p
, next_pfx
));
224 route_table_iter_cleanup (&iter
);
230 * Verifies that route_table_get_next() returns the expected result
231 * (result) for the prefix string 'target'.
234 verify_next (struct route_table
*table
, const char *target
, const char *next
)
236 struct prefix_ipv4 target_pfx
, next_pfx
;
237 struct route_node
*rn
;
238 char result_buf
[PREFIX2STR_BUFFER
];
240 if (str2prefix_ipv4 (target
, &target_pfx
) <= 0)
245 rn
= route_table_get_next (table
, (struct prefix
*) &target_pfx
);
248 prefix2str (&rn
->p
, result_buf
, sizeof (result_buf
));
252 snprintf (result_buf
, sizeof (result_buf
), "(Null)");
257 printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target
,
258 next
? next
: "(Null)", result_buf
);
263 verify_next_by_iterating (table
, (struct prefix
*) &target_pfx
, NULL
);
269 if (str2prefix_ipv4 (next
, &next_pfx
) <= 0)
274 if (prefix_cmp (&rn
->p
, (struct prefix
*) &next_pfx
))
278 route_unlock_node (rn
);
280 verify_next_by_iterating (table
, (struct prefix
*) &target_pfx
,
281 (struct prefix
*) &next_pfx
);
290 struct route_table
*table
;
292 printf ("\n\nTesting route_table_get_next()\n");
293 table
= route_table_init ();
296 * Target exists in tree, but has no successor.
298 add_nodes (table
, "1.0.1.0/24", NULL
);
299 verify_next (table
, "1.0.1.0/24", NULL
);
303 * Target exists in tree, and there is a node in its left subtree.
305 add_nodes (table
, "1.0.1.0/24", "1.0.1.0/25", NULL
);
306 verify_next (table
, "1.0.1.0/24", "1.0.1.0/25");
310 * Target exists in tree, and there is a node in its right subtree.
312 add_nodes (table
, "1.0.1.0/24", "1.0.1.128/25", NULL
);
313 verify_next (table
, "1.0.1.0/24", "1.0.1.128/25");
317 * Target exists in the tree, next node is outside subtree.
319 add_nodes (table
, "1.0.1.0/24", "1.1.0.0/16", NULL
);
320 verify_next (table
, "1.0.1.0/24", "1.1.0.0/16");
324 * The target node does not exist in the tree for all the test cases
329 * There is no successor in the tree.
331 add_nodes (table
, "1.0.0.0/16", NULL
);
332 verify_next (table
, "1.0.1.0/24", NULL
);
336 * There exists a node that would be in the target's left subtree.
338 add_nodes (table
, "1.0.0.0/16", "1.0.1.0/25", NULL
);
339 verify_next (table
, "1.0.1.0/24", "1.0.1.0/25");
343 * There exists a node would be in the target's right subtree.
345 add_nodes (table
, "1.0.0.0/16", "1.0.1.128/25", NULL
);
346 verify_next (table
, "1.0.1.0/24", "1.0.1.128/25");
350 * A search for the target reaches a node where there are no child
351 * nodes in the direction of the target (left), but the node has a
354 add_nodes (table
, "1.0.0.0/16", "1.0.128.0/17", NULL
);
355 verify_next (table
, "1.0.0.0/17", "1.0.128.0/17");
359 * A search for the target reaches a node with no children. We have
360 * to go upwards in the tree to find a successor.
362 add_nodes (table
, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
363 "1.0.128.0/17", NULL
);
364 verify_next (table
, "1.0.1.0/25", "1.0.128.0/17");
368 * A search for the target reaches a node where neither the node nor
369 * the target prefix contain each other.
371 * In first case below the node succeeds the target.
373 * In the second case, the node comes before the target, so we have
374 * to go up the tree looking for a successor.
376 add_nodes (table
, "1.0.0.0/16", "1.0.1.0/24", NULL
);
377 verify_next (table
, "1.0.0.0/24", "1.0.1.0/24");
380 add_nodes (table
, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
381 "1.0.128.0/17", NULL
);
382 verify_next (table
, "1.0.1.128/25", "1.0.128.0/17");
385 route_table_finish (table
);
389 * verify_prefix_iter_cmp
392 verify_prefix_iter_cmp (const char *p1
, const char *p2
, int exp_result
)
394 struct prefix_ipv4 p1_pfx
, p2_pfx
;
397 if (str2prefix_ipv4 (p1
, &p1_pfx
) <= 0)
402 if (str2prefix_ipv4 (p2
, &p2_pfx
) <= 0)
407 result
= route_table_prefix_iter_cmp ((struct prefix
*) &p1_pfx
,
408 (struct prefix
*) &p2_pfx
);
410 printf ("Verifying cmp(%s, %s) returns %d\n", p1
, p2
, exp_result
);
412 assert (exp_result
== result
);
415 * Also check the reverse comparision.
417 result
= route_table_prefix_iter_cmp ((struct prefix
*) &p2_pfx
,
418 (struct prefix
*) &p1_pfx
);
422 exp_result
= -exp_result
;
425 printf ("Verifying cmp(%s, %s) returns %d\n", p1
, p2
, exp_result
);
426 assert (result
== exp_result
);
430 * test_prefix_iter_cmp
432 * Tests comparision of prefixes according to order of iteration.
435 test_prefix_iter_cmp ()
437 printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
439 verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
441 verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
443 verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
447 * verify_iter_with_pause
449 * Iterates over a tree using two methods: 'normal' iteration, and an
450 * iterator that pauses at each node. Verifies that the two methods
451 * yield the same results.
454 verify_iter_with_pause (struct route_table
*table
)
456 unsigned long num_nodes
;
457 struct route_node
*rn
, *iter_rn
;
458 route_table_iter_t iter_space
;
459 route_table_iter_t
*iter
= &iter_space
;
461 route_table_iter_init (iter
, table
);
464 for (rn
= route_top (table
); rn
; rn
= route_next (rn
))
467 route_table_iter_pause (iter
);
469 assert (iter
->current
== NULL
);
470 if (route_table_iter_started (iter
))
472 assert (iter
->state
== RT_ITER_STATE_PAUSED
);
476 assert (rn
== table
->top
);
477 assert (iter
->state
== RT_ITER_STATE_INIT
);
480 iter_rn
= route_table_iter_next (iter
);
483 * Make sure both iterations return the same node.
485 assert (rn
== iter_rn
);
488 assert (num_nodes
== route_table_count (table
));
490 route_table_iter_pause (iter
);
491 iter_rn
= route_table_iter_next (iter
);
493 assert (iter_rn
== NULL
);
494 assert (iter
->state
== RT_ITER_STATE_DONE
);
496 assert (route_table_iter_next (iter
) == NULL
);
497 assert (iter
->state
== RT_ITER_STATE_DONE
);
499 route_table_iter_cleanup (iter
);
502 printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes
);
509 test_iter_pause (void)
511 struct route_table
*table
;
513 const char *prefixes
[] = {
521 num_prefixes
= sizeof (prefixes
) / sizeof (prefixes
[0]);
523 printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
524 table
= route_table_init ();
525 for (i
= 0; i
< num_prefixes
; i
++)
527 add_nodes (table
, prefixes
[i
], NULL
);
530 verify_iter_with_pause (table
);
533 route_table_finish (table
);
542 test_prefix_iter_cmp ();