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 along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 * Information that is kept for each node in the radix tree.
32 typedef struct test_node_t_
{
35 * Human readable representation of the string. Allocated using
41 struct thread_master
*master
;
46 * Add the given prefix (passed in as a string) to the given table.
48 static void add_node(struct route_table
*table
, const char *prefix_str
)
52 struct route_node
*rn
;
56 if (str2prefix_ipv4(prefix_str
, &p
) <= 0) {
60 rn
= route_node_get(table
, (struct prefix
*)&p
);
66 node
= malloc(sizeof(test_node_t
));
68 node
->prefix_str
= strdup(prefix_str
);
69 assert(node
->prefix_str
);
76 * Convenience function to add a bunch of nodes together.
78 * The arguments must be prefixes in string format, with a NULL as the
81 static void add_nodes(struct route_table
*table
, ...)
86 va_start(arglist
, table
);
88 prefix
= va_arg(arglist
, char *);
90 add_node(table
, prefix
);
91 prefix
= va_arg(arglist
, char *);
100 * Recursive function to print a route node and its children.
104 static void print_subtree(struct route_node
*rn
, const char *legend
,
110 * Print this node first.
112 for (i
= 0; i
< indent_level
; i
++) {
116 printfrr("%s: %pFX", legend
, &rn
->p
);
118 printf(" (internal)");
122 print_subtree(rn
->l_left
, "Left", indent_level
+ 1);
125 print_subtree(rn
->l_right
, "Right", indent_level
+ 1);
132 * Function that prints out the internal structure of a route table.
134 static void print_table(struct route_table
*table
)
136 struct route_node
*rn
;
141 printf("<Empty Table>\n");
145 print_subtree(rn
, "Top", 0);
151 * Remove all nodes from the given table.
153 static void clear_table(struct route_table
*table
)
155 route_table_iter_t iter
;
156 struct route_node
*rn
;
159 route_table_iter_init(&iter
, table
);
161 while ((rn
= route_table_iter_next(&iter
))) {
167 route_unlock_node(rn
);
168 free(node
->prefix_str
);
172 route_table_iter_cleanup(&iter
);
174 assert(table
->top
== NULL
);
178 * verify_next_by_iterating
180 * Iterate over the tree to make sure that the first prefix after
181 * target_pfx is the expected one. Note that target_pfx may not be
182 * present in the tree.
184 static void verify_next_by_iterating(struct route_table
*table
,
185 struct prefix
*target_pfx
,
186 struct prefix
*next_pfx
)
188 route_table_iter_t iter
;
189 struct route_node
*rn
;
191 route_table_iter_init(&iter
, table
);
192 while ((rn
= route_table_iter_next(&iter
))) {
193 if (route_table_prefix_iter_cmp(&rn
->p
, target_pfx
) > 0) {
194 assert(!prefix_cmp(&rn
->p
, next_pfx
));
203 route_table_iter_cleanup(&iter
);
209 * Verifies that route_table_get_next() returns the expected result
210 * (result) for the prefix string 'target'.
212 static void verify_next(struct route_table
*table
, const char *target
,
215 struct prefix_ipv4 target_pfx
, next_pfx
;
216 struct route_node
*rn
;
217 char result_buf
[PREFIX2STR_BUFFER
];
219 if (str2prefix_ipv4(target
, &target_pfx
) <= 0) {
223 rn
= route_table_get_next(table
, (struct prefix
*)&target_pfx
);
225 prefix2str(&rn
->p
, result_buf
, sizeof(result_buf
));
227 snprintf(result_buf
, sizeof(result_buf
), "(Null)");
232 printf("Verifying successor of %s. Expected: %s, Result: %s\n", target
,
233 next
? next
: "(Null)", result_buf
);
237 verify_next_by_iterating(table
, (struct prefix
*)&target_pfx
,
244 if (str2prefix_ipv4(next
, &next_pfx
) <= 0) {
248 if (prefix_cmp(&rn
->p
, (struct prefix
*)&next_pfx
)) {
251 route_unlock_node(rn
);
253 verify_next_by_iterating(table
, (struct prefix
*)&target_pfx
,
254 (struct prefix
*)&next_pfx
);
260 static void test_get_next(void)
262 struct route_table
*table
;
264 printf("\n\nTesting route_table_get_next()\n");
265 table
= route_table_init();
268 * Target exists in tree, but has no successor.
270 add_nodes(table
, "1.0.1.0/24", NULL
);
271 verify_next(table
, "1.0.1.0/24", NULL
);
275 * Target exists in tree, and there is a node in its left subtree.
277 add_nodes(table
, "1.0.1.0/24", "1.0.1.0/25", NULL
);
278 verify_next(table
, "1.0.1.0/24", "1.0.1.0/25");
282 * Target exists in tree, and there is a node in its right subtree.
284 add_nodes(table
, "1.0.1.0/24", "1.0.1.128/25", NULL
);
285 verify_next(table
, "1.0.1.0/24", "1.0.1.128/25");
289 * Target exists in the tree, next node is outside subtree.
291 add_nodes(table
, "1.0.1.0/24", "1.1.0.0/16", NULL
);
292 verify_next(table
, "1.0.1.0/24", "1.1.0.0/16");
296 * The target node does not exist in the tree for all the test cases
301 * There is no successor in the tree.
303 add_nodes(table
, "1.0.0.0/16", NULL
);
304 verify_next(table
, "1.0.1.0/24", NULL
);
308 * There exists a node that would be in the target's left subtree.
310 add_nodes(table
, "1.0.0.0/16", "1.0.1.0/25", NULL
);
311 verify_next(table
, "1.0.1.0/24", "1.0.1.0/25");
315 * There exists a node would be in the target's right subtree.
317 add_nodes(table
, "1.0.0.0/16", "1.0.1.128/25", NULL
);
318 verify_next(table
, "1.0.1.0/24", "1.0.1.128/25");
322 * A search for the target reaches a node where there are no child
323 * nodes in the direction of the target (left), but the node has a
326 add_nodes(table
, "1.0.0.0/16", "1.0.128.0/17", NULL
);
327 verify_next(table
, "1.0.0.0/17", "1.0.128.0/17");
331 * A search for the target reaches a node with no children. We have
332 * to go upwards in the tree to find a successor.
334 add_nodes(table
, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
335 "1.0.128.0/17", NULL
);
336 verify_next(table
, "1.0.1.0/25", "1.0.128.0/17");
340 * A search for the target reaches a node where neither the node nor
341 * the target prefix contain each other.
343 * In first case below the node succeeds the target.
345 * In the second case, the node comes before the target, so we have
346 * to go up the tree looking for a successor.
348 add_nodes(table
, "1.0.0.0/16", "1.0.1.0/24", NULL
);
349 verify_next(table
, "1.0.0.0/24", "1.0.1.0/24");
352 add_nodes(table
, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
353 "1.0.128.0/17", NULL
);
354 verify_next(table
, "1.0.1.128/25", "1.0.128.0/17");
357 route_table_finish(table
);
361 * verify_prefix_iter_cmp
363 static void verify_prefix_iter_cmp(const char *p1
, const char *p2
,
366 struct prefix_ipv4 p1_pfx
, p2_pfx
;
369 if (str2prefix_ipv4(p1
, &p1_pfx
) <= 0) {
373 if (str2prefix_ipv4(p2
, &p2_pfx
) <= 0) {
377 result
= route_table_prefix_iter_cmp((struct prefix
*)&p1_pfx
,
378 (struct prefix
*)&p2_pfx
);
380 printf("Verifying cmp(%s, %s) returns %d\n", p1
, p2
, exp_result
);
382 assert(exp_result
== result
);
385 * Also check the reverse comparision.
387 result
= route_table_prefix_iter_cmp((struct prefix
*)&p2_pfx
,
388 (struct prefix
*)&p1_pfx
);
391 exp_result
= -exp_result
;
394 printf("Verifying cmp(%s, %s) returns %d\n", p1
, p2
, exp_result
);
395 assert(result
== exp_result
);
399 * test_prefix_iter_cmp
401 * Tests comparision of prefixes according to order of iteration.
403 static void test_prefix_iter_cmp(void)
405 printf("\n\nTesting route_table_prefix_iter_cmp()\n");
407 verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/8", 0);
409 verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/16", -1);
411 verify_prefix_iter_cmp("1.0.0.0/16", "1.128.0.0/16", -1);
415 * verify_iter_with_pause
417 * Iterates over a tree using two methods: 'normal' iteration, and an
418 * iterator that pauses at each node. Verifies that the two methods
419 * yield the same results.
421 static void verify_iter_with_pause(struct route_table
*table
)
423 unsigned long num_nodes
;
424 struct route_node
*rn
, *iter_rn
;
425 route_table_iter_t iter_space
;
426 route_table_iter_t
*iter
= &iter_space
;
428 route_table_iter_init(iter
, table
);
431 for (rn
= route_top(table
); rn
; rn
= route_next(rn
)) {
433 route_table_iter_pause(iter
);
435 assert(iter
->current
== NULL
);
436 if (route_table_iter_started(iter
)) {
437 assert(iter
->state
== RT_ITER_STATE_PAUSED
);
439 assert(rn
== table
->top
);
440 assert(iter
->state
== RT_ITER_STATE_INIT
);
443 iter_rn
= route_table_iter_next(iter
);
446 * Make sure both iterations return the same node.
448 assert(rn
== iter_rn
);
451 assert(num_nodes
== route_table_count(table
));
453 route_table_iter_pause(iter
);
454 iter_rn
= route_table_iter_next(iter
);
456 assert(iter_rn
== NULL
);
457 assert(iter
->state
== RT_ITER_STATE_DONE
);
459 assert(route_table_iter_next(iter
) == NULL
);
460 assert(iter
->state
== RT_ITER_STATE_DONE
);
462 route_table_iter_cleanup(iter
);
465 printf("Verified pausing iteration on tree with %lu nodes\n",
472 static void test_iter_pause(void)
474 struct route_table
*table
;
476 const char *prefixes
[] = {"1.0.1.0/24", "1.0.1.0/25", "1.0.1.128/25",
477 "1.0.2.0/24", "2.0.0.0/8"};
479 num_prefixes
= array_size(prefixes
);
481 printf("\n\nTesting that route_table_iter_pause() works as expected\n");
482 table
= route_table_init();
483 for (i
= 0; i
< num_prefixes
; i
++) {
484 add_nodes(table
, prefixes
[i
], NULL
);
487 verify_iter_with_pause(table
);
490 route_table_finish(table
);
496 static void run_tests(void)
498 test_prefix_iter_cmp();