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