]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* |
2 | * Routing Table functions. | |
3 | * Copyright (C) 1998 Kunihiro Ishiguro | |
4 | * | |
5 | * This file is part of GNU Zebra. | |
6 | * | |
7 | * GNU Zebra 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 | |
10 | * later version. | |
11 | * | |
12 | * GNU Zebra 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. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public License | |
18 | * along with GNU Zebra; see the file COPYING. If not, write to the Free | |
19 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
20 | * 02111-1307, USA. | |
21 | */ | |
22 | ||
23 | #include <zebra.h> | |
24 | ||
25 | #include "prefix.h" | |
26 | #include "table.h" | |
27 | #include "memory.h" | |
28 | #include "sockunion.h" | |
29 | ||
3eb8ef37 AS |
30 | static void route_node_delete (struct route_node *); |
31 | static void route_table_free (struct route_table *); | |
6b0655a2 | 32 | |
f9c1b7bb AS |
33 | |
34 | /* | |
35 | * route_table_init_with_delegate | |
36 | */ | |
718e3744 | 37 | struct route_table * |
f9c1b7bb | 38 | route_table_init_with_delegate (route_table_delegate_t *delegate) |
718e3744 | 39 | { |
40 | struct route_table *rt; | |
41 | ||
42 | rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table)); | |
f9c1b7bb | 43 | rt->delegate = delegate; |
718e3744 | 44 | return rt; |
45 | } | |
46 | ||
47 | void | |
48 | route_table_finish (struct route_table *rt) | |
49 | { | |
50 | route_table_free (rt); | |
51 | } | |
52 | ||
53 | /* Allocate new route node. */ | |
8cc4198f | 54 | static struct route_node * |
f9c1b7bb | 55 | route_node_new (struct route_table *table) |
718e3744 | 56 | { |
f9c1b7bb | 57 | return table->delegate->create_node (table->delegate, table); |
718e3744 | 58 | } |
59 | ||
60 | /* Allocate new route node with prefix set. */ | |
8cc4198f | 61 | static struct route_node * |
718e3744 | 62 | route_node_set (struct route_table *table, struct prefix *prefix) |
63 | { | |
64 | struct route_node *node; | |
65 | ||
f9c1b7bb | 66 | node = route_node_new (table); |
718e3744 | 67 | |
68 | prefix_copy (&node->p, prefix); | |
69 | node->table = table; | |
70 | ||
71 | return node; | |
72 | } | |
73 | ||
74 | /* Free route node. */ | |
8cc4198f | 75 | static void |
f9c1b7bb | 76 | route_node_free (struct route_table *table, struct route_node *node) |
718e3744 | 77 | { |
f9c1b7bb | 78 | table->delegate->destroy_node (table->delegate, table, node); |
718e3744 | 79 | } |
80 | ||
81 | /* Free route table. */ | |
3eb8ef37 | 82 | static void |
718e3744 | 83 | route_table_free (struct route_table *rt) |
84 | { | |
85 | struct route_node *tmp_node; | |
86 | struct route_node *node; | |
87 | ||
88 | if (rt == NULL) | |
89 | return; | |
90 | ||
91 | node = rt->top; | |
92 | ||
3eb8ef37 AS |
93 | /* Bulk deletion of nodes remaining in this table. This function is not |
94 | called until workers have completed their dependency on this table. | |
95 | A final route_unlock_node() will not be called for these nodes. */ | |
718e3744 | 96 | while (node) |
97 | { | |
98 | if (node->l_left) | |
99 | { | |
100 | node = node->l_left; | |
101 | continue; | |
102 | } | |
103 | ||
104 | if (node->l_right) | |
105 | { | |
106 | node = node->l_right; | |
107 | continue; | |
108 | } | |
109 | ||
110 | tmp_node = node; | |
111 | node = node->parent; | |
112 | ||
3eb8ef37 AS |
113 | tmp_node->table->count--; |
114 | tmp_node->lock = 0; /* to cause assert if unlocked after this */ | |
f9c1b7bb | 115 | route_node_free (rt, tmp_node); |
3eb8ef37 | 116 | |
718e3744 | 117 | if (node != NULL) |
118 | { | |
119 | if (node->l_left == tmp_node) | |
120 | node->l_left = NULL; | |
121 | else | |
122 | node->l_right = NULL; | |
718e3744 | 123 | } |
124 | else | |
125 | { | |
718e3744 | 126 | break; |
127 | } | |
128 | } | |
129 | ||
3eb8ef37 AS |
130 | assert (rt->count == 0); |
131 | ||
718e3744 | 132 | XFREE (MTYPE_ROUTE_TABLE, rt); |
133 | return; | |
134 | } | |
135 | ||
136 | /* Utility mask array. */ | |
38cc00cd | 137 | static const u_char maskbit[] = |
718e3744 | 138 | { |
139 | 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff | |
140 | }; | |
141 | ||
142 | /* Common prefix route genaration. */ | |
143 | static void | |
144 | route_common (struct prefix *n, struct prefix *p, struct prefix *new) | |
145 | { | |
146 | int i; | |
147 | u_char diff; | |
148 | u_char mask; | |
149 | ||
150 | u_char *np = (u_char *)&n->u.prefix; | |
151 | u_char *pp = (u_char *)&p->u.prefix; | |
152 | u_char *newp = (u_char *)&new->u.prefix; | |
153 | ||
154 | for (i = 0; i < p->prefixlen / 8; i++) | |
155 | { | |
156 | if (np[i] == pp[i]) | |
157 | newp[i] = np[i]; | |
158 | else | |
159 | break; | |
160 | } | |
161 | ||
162 | new->prefixlen = i * 8; | |
163 | ||
164 | if (new->prefixlen != p->prefixlen) | |
165 | { | |
166 | diff = np[i] ^ pp[i]; | |
167 | mask = 0x80; | |
168 | while (new->prefixlen < p->prefixlen && !(mask & diff)) | |
169 | { | |
170 | mask >>= 1; | |
171 | new->prefixlen++; | |
172 | } | |
173 | newp[i] = np[i] & maskbit[new->prefixlen % 8]; | |
174 | } | |
175 | } | |
176 | ||
718e3744 | 177 | static void |
178 | set_link (struct route_node *node, struct route_node *new) | |
179 | { | |
1352ef32 | 180 | unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen); |
718e3744 | 181 | |
182 | node->link[bit] = new; | |
183 | new->parent = node; | |
184 | } | |
185 | ||
186 | /* Lock node. */ | |
187 | struct route_node * | |
188 | route_lock_node (struct route_node *node) | |
189 | { | |
190 | node->lock++; | |
191 | return node; | |
192 | } | |
193 | ||
194 | /* Unlock node. */ | |
195 | void | |
196 | route_unlock_node (struct route_node *node) | |
197 | { | |
3eb8ef37 | 198 | assert (node->lock > 0); |
718e3744 | 199 | node->lock--; |
200 | ||
201 | if (node->lock == 0) | |
202 | route_node_delete (node); | |
203 | } | |
204 | ||
718e3744 | 205 | /* Find matched prefix. */ |
206 | struct route_node * | |
38cc00cd | 207 | route_node_match (const struct route_table *table, const struct prefix *p) |
718e3744 | 208 | { |
209 | struct route_node *node; | |
210 | struct route_node *matched; | |
211 | ||
212 | matched = NULL; | |
213 | node = table->top; | |
214 | ||
215 | /* Walk down tree. If there is matched route then store it to | |
216 | matched. */ | |
217 | while (node && node->p.prefixlen <= p->prefixlen && | |
218 | prefix_match (&node->p, p)) | |
219 | { | |
220 | if (node->info) | |
221 | matched = node; | |
f8416810 PJ |
222 | |
223 | if (node->p.prefixlen == p->prefixlen) | |
224 | break; | |
225 | ||
1352ef32 | 226 | node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)]; |
718e3744 | 227 | } |
228 | ||
229 | /* If matched route found, return it. */ | |
230 | if (matched) | |
231 | return route_lock_node (matched); | |
232 | ||
233 | return NULL; | |
234 | } | |
235 | ||
236 | struct route_node * | |
38cc00cd SH |
237 | route_node_match_ipv4 (const struct route_table *table, |
238 | const struct in_addr *addr) | |
718e3744 | 239 | { |
240 | struct prefix_ipv4 p; | |
241 | ||
242 | memset (&p, 0, sizeof (struct prefix_ipv4)); | |
243 | p.family = AF_INET; | |
244 | p.prefixlen = IPV4_MAX_PREFIXLEN; | |
245 | p.prefix = *addr; | |
246 | ||
247 | return route_node_match (table, (struct prefix *) &p); | |
248 | } | |
249 | ||
250 | #ifdef HAVE_IPV6 | |
251 | struct route_node * | |
38cc00cd SH |
252 | route_node_match_ipv6 (const struct route_table *table, |
253 | const struct in6_addr *addr) | |
718e3744 | 254 | { |
255 | struct prefix_ipv6 p; | |
256 | ||
257 | memset (&p, 0, sizeof (struct prefix_ipv6)); | |
258 | p.family = AF_INET6; | |
259 | p.prefixlen = IPV6_MAX_PREFIXLEN; | |
260 | p.prefix = *addr; | |
261 | ||
262 | return route_node_match (table, (struct prefix *) &p); | |
263 | } | |
264 | #endif /* HAVE_IPV6 */ | |
265 | ||
266 | /* Lookup same prefix node. Return NULL when we can't find route. */ | |
267 | struct route_node * | |
3eb8ef37 | 268 | route_node_lookup (const struct route_table *table, struct prefix *p) |
718e3744 | 269 | { |
270 | struct route_node *node; | |
47d3b607 JBD |
271 | u_char prefixlen = p->prefixlen; |
272 | const u_char *prefix = &p->u.prefix; | |
718e3744 | 273 | |
274 | node = table->top; | |
275 | ||
47d3b607 | 276 | while (node && node->p.prefixlen <= prefixlen && |
718e3744 | 277 | prefix_match (&node->p, p)) |
278 | { | |
47d3b607 | 279 | if (node->p.prefixlen == prefixlen) |
f8416810 | 280 | return node->info ? route_lock_node (node) : NULL; |
718e3744 | 281 | |
47d3b607 | 282 | node = node->link[prefix_bit(prefix, node->p.prefixlen)]; |
718e3744 | 283 | } |
284 | ||
285 | return NULL; | |
286 | } | |
287 | ||
288 | /* Add node to routing table. */ | |
289 | struct route_node * | |
3eb8ef37 | 290 | route_node_get (struct route_table *const table, struct prefix *p) |
718e3744 | 291 | { |
292 | struct route_node *new; | |
293 | struct route_node *node; | |
294 | struct route_node *match; | |
47d3b607 JBD |
295 | u_char prefixlen = p->prefixlen; |
296 | const u_char *prefix = &p->u.prefix; | |
718e3744 | 297 | |
298 | match = NULL; | |
299 | node = table->top; | |
47d3b607 | 300 | while (node && node->p.prefixlen <= prefixlen && |
718e3744 | 301 | prefix_match (&node->p, p)) |
302 | { | |
47d3b607 | 303 | if (node->p.prefixlen == prefixlen) |
f8416810 | 304 | return route_lock_node (node); |
47d3b607 | 305 | |
718e3744 | 306 | match = node; |
47d3b607 | 307 | node = node->link[prefix_bit(prefix, node->p.prefixlen)]; |
718e3744 | 308 | } |
309 | ||
310 | if (node == NULL) | |
311 | { | |
312 | new = route_node_set (table, p); | |
313 | if (match) | |
314 | set_link (match, new); | |
315 | else | |
316 | table->top = new; | |
317 | } | |
318 | else | |
319 | { | |
f9c1b7bb | 320 | new = route_node_new (table); |
718e3744 | 321 | route_common (&node->p, p, &new->p); |
322 | new->p.family = p->family; | |
323 | new->table = table; | |
324 | set_link (new, node); | |
325 | ||
326 | if (match) | |
327 | set_link (match, new); | |
328 | else | |
329 | table->top = new; | |
330 | ||
331 | if (new->p.prefixlen != p->prefixlen) | |
332 | { | |
333 | match = new; | |
334 | new = route_node_set (table, p); | |
335 | set_link (match, new); | |
3eb8ef37 | 336 | table->count++; |
718e3744 | 337 | } |
338 | } | |
3eb8ef37 | 339 | table->count++; |
718e3744 | 340 | route_lock_node (new); |
341 | ||
342 | return new; | |
343 | } | |
344 | ||
345 | /* Delete node from the routing table. */ | |
3eb8ef37 | 346 | static void |
718e3744 | 347 | route_node_delete (struct route_node *node) |
348 | { | |
349 | struct route_node *child; | |
350 | struct route_node *parent; | |
351 | ||
352 | assert (node->lock == 0); | |
353 | assert (node->info == NULL); | |
354 | ||
355 | if (node->l_left && node->l_right) | |
356 | return; | |
357 | ||
358 | if (node->l_left) | |
359 | child = node->l_left; | |
360 | else | |
361 | child = node->l_right; | |
362 | ||
363 | parent = node->parent; | |
364 | ||
365 | if (child) | |
366 | child->parent = parent; | |
367 | ||
368 | if (parent) | |
369 | { | |
370 | if (parent->l_left == node) | |
371 | parent->l_left = child; | |
372 | else | |
373 | parent->l_right = child; | |
374 | } | |
375 | else | |
376 | node->table->top = child; | |
377 | ||
3eb8ef37 AS |
378 | node->table->count--; |
379 | ||
f9c1b7bb | 380 | route_node_free (node->table, node); |
718e3744 | 381 | |
382 | /* If parent node is stub then delete it also. */ | |
383 | if (parent && parent->lock == 0) | |
384 | route_node_delete (parent); | |
385 | } | |
386 | ||
387 | /* Get fist node and lock it. This function is useful when one want | |
388 | to lookup all the node exist in the routing table. */ | |
389 | struct route_node * | |
390 | route_top (struct route_table *table) | |
391 | { | |
392 | /* If there is no node in the routing table return NULL. */ | |
393 | if (table->top == NULL) | |
394 | return NULL; | |
395 | ||
396 | /* Lock the top node and return it. */ | |
397 | route_lock_node (table->top); | |
398 | return table->top; | |
399 | } | |
400 | ||
401 | /* Unlock current node and lock next node then return it. */ | |
402 | struct route_node * | |
403 | route_next (struct route_node *node) | |
404 | { | |
405 | struct route_node *next; | |
406 | struct route_node *start; | |
407 | ||
408 | /* Node may be deleted from route_unlock_node so we have to preserve | |
409 | next node's pointer. */ | |
410 | ||
411 | if (node->l_left) | |
412 | { | |
413 | next = node->l_left; | |
414 | route_lock_node (next); | |
415 | route_unlock_node (node); | |
416 | return next; | |
417 | } | |
418 | if (node->l_right) | |
419 | { | |
420 | next = node->l_right; | |
421 | route_lock_node (next); | |
422 | route_unlock_node (node); | |
423 | return next; | |
424 | } | |
425 | ||
426 | start = node; | |
427 | while (node->parent) | |
428 | { | |
429 | if (node->parent->l_left == node && node->parent->l_right) | |
430 | { | |
431 | next = node->parent->l_right; | |
432 | route_lock_node (next); | |
433 | route_unlock_node (start); | |
434 | return next; | |
435 | } | |
436 | node = node->parent; | |
437 | } | |
438 | route_unlock_node (start); | |
439 | return NULL; | |
440 | } | |
441 | ||
442 | /* Unlock current node and lock next node until limit. */ | |
443 | struct route_node * | |
444 | route_next_until (struct route_node *node, struct route_node *limit) | |
445 | { | |
446 | struct route_node *next; | |
447 | struct route_node *start; | |
448 | ||
449 | /* Node may be deleted from route_unlock_node so we have to preserve | |
450 | next node's pointer. */ | |
451 | ||
452 | if (node->l_left) | |
453 | { | |
454 | next = node->l_left; | |
455 | route_lock_node (next); | |
456 | route_unlock_node (node); | |
457 | return next; | |
458 | } | |
459 | if (node->l_right) | |
460 | { | |
461 | next = node->l_right; | |
462 | route_lock_node (next); | |
463 | route_unlock_node (node); | |
464 | return next; | |
465 | } | |
466 | ||
467 | start = node; | |
468 | while (node->parent && node != limit) | |
469 | { | |
470 | if (node->parent->l_left == node && node->parent->l_right) | |
471 | { | |
472 | next = node->parent->l_right; | |
473 | route_lock_node (next); | |
474 | route_unlock_node (start); | |
475 | return next; | |
476 | } | |
477 | node = node->parent; | |
478 | } | |
479 | route_unlock_node (start); | |
480 | return NULL; | |
481 | } | |
3eb8ef37 AS |
482 | |
483 | unsigned long | |
484 | route_table_count (const struct route_table *table) | |
485 | { | |
486 | return table->count; | |
487 | } | |
f9c1b7bb AS |
488 | |
489 | /** | |
490 | * route_node_create | |
491 | * | |
492 | * Default function for creating a route node. | |
493 | */ | |
494 | static struct route_node * | |
495 | route_node_create (route_table_delegate_t *delegate, | |
496 | struct route_table *table) | |
497 | { | |
498 | struct route_node *node; | |
499 | node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node)); | |
500 | return node; | |
501 | } | |
502 | ||
503 | /** | |
504 | * route_node_destroy | |
505 | * | |
506 | * Default function for destroying a route node. | |
507 | */ | |
508 | static void | |
509 | route_node_destroy (route_table_delegate_t *delegate, | |
510 | struct route_table *table, struct route_node *node) | |
511 | { | |
512 | XFREE (MTYPE_ROUTE_NODE, node); | |
513 | } | |
514 | ||
515 | /* | |
516 | * Default delegate. | |
517 | */ | |
518 | static route_table_delegate_t default_delegate = { | |
519 | .create_node = route_node_create, | |
520 | .destroy_node = route_node_destroy | |
521 | }; | |
522 | ||
523 | /* | |
524 | * route_table_init | |
525 | */ | |
526 | struct route_table * | |
527 | route_table_init (void) | |
528 | { | |
529 | return route_table_init_with_delegate (&default_delegate); | |
530 | } | |
28971c8c AS |
531 | |
532 | /** | |
533 | * route_table_prefix_iter_cmp | |
534 | * | |
535 | * Compare two prefixes according to the order in which they appear in | |
536 | * an iteration over a tree. | |
537 | * | |
538 | * @return -1 if p1 occurs before p2 (p1 < p2) | |
539 | * 0 if the prefixes are identical (p1 == p2) | |
540 | * +1 if p1 occurs after p2 (p1 > p2) | |
541 | */ | |
542 | int | |
543 | route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2) | |
544 | { | |
545 | struct prefix common_space; | |
546 | struct prefix *common = &common_space; | |
547 | ||
548 | if (p1->prefixlen <= p2->prefixlen) | |
549 | { | |
550 | if (prefix_match (p1, p2)) | |
551 | { | |
552 | ||
553 | /* | |
554 | * p1 contains p2, or is equal to it. | |
555 | */ | |
556 | return (p1->prefixlen == p2->prefixlen) ? 0 : -1; | |
557 | } | |
558 | } | |
559 | else | |
560 | { | |
561 | ||
562 | /* | |
563 | * Check if p2 contains p1. | |
564 | */ | |
565 | if (prefix_match (p2, p1)) | |
566 | return 1; | |
567 | } | |
568 | ||
569 | route_common (p1, p2, common); | |
570 | assert (common->prefixlen < p1->prefixlen); | |
571 | assert (common->prefixlen < p2->prefixlen); | |
572 | ||
573 | /* | |
574 | * Both prefixes are longer than the common prefix. | |
575 | * | |
576 | * We need to check the bit after the common prefixlen to determine | |
577 | * which one comes later. | |
578 | */ | |
579 | if (prefix_bit (&p1->u.prefix, common->prefixlen)) | |
580 | { | |
581 | ||
582 | /* | |
583 | * We branch to the right to get to p1 from the common prefix. | |
584 | */ | |
585 | assert (!prefix_bit (&p2->u.prefix, common->prefixlen)); | |
586 | return 1; | |
587 | } | |
588 | ||
589 | /* | |
590 | * We branch to the right to get to p2 from the common prefix. | |
591 | */ | |
592 | assert (prefix_bit (&p2->u.prefix, common->prefixlen)); | |
593 | return -1; | |
594 | } | |
595 | ||
596 | /* | |
597 | * route_get_subtree_next | |
598 | * | |
599 | * Helper function that returns the first node that follows the nodes | |
600 | * in the sub-tree under 'node' in iteration order. | |
601 | */ | |
602 | static struct route_node * | |
603 | route_get_subtree_next (struct route_node *node) | |
604 | { | |
605 | while (node->parent) | |
606 | { | |
607 | if (node->parent->l_left == node && node->parent->l_right) | |
608 | return node->parent->l_right; | |
609 | ||
610 | node = node->parent; | |
611 | } | |
612 | ||
613 | return NULL; | |
614 | } | |
615 | ||
616 | /** | |
617 | * route_table_get_next_internal | |
618 | * | |
619 | * Helper function to find the node that occurs after the given prefix in | |
620 | * order of iteration. | |
621 | * | |
622 | * @see route_table_get_next | |
623 | */ | |
624 | static struct route_node * | |
625 | route_table_get_next_internal (const struct route_table *table, | |
626 | struct prefix *p) | |
627 | { | |
628 | struct route_node *node, *tmp_node; | |
28971c8c AS |
629 | int cmp; |
630 | ||
28971c8c AS |
631 | node = table->top; |
632 | ||
633 | while (node) | |
634 | { | |
635 | int match; | |
636 | ||
637 | if (node->p.prefixlen < p->prefixlen) | |
638 | match = prefix_match (&node->p, p); | |
639 | else | |
640 | match = prefix_match (p, &node->p); | |
641 | ||
642 | if (match) | |
643 | { | |
644 | if (node->p.prefixlen == p->prefixlen) | |
645 | { | |
646 | ||
647 | /* | |
648 | * The prefix p exists in the tree, just return the next | |
649 | * node. | |
650 | */ | |
651 | route_lock_node (node); | |
652 | node = route_next (node); | |
653 | if (node) | |
654 | route_unlock_node (node); | |
655 | ||
656 | return (node); | |
657 | } | |
658 | ||
659 | if (node->p.prefixlen > p->prefixlen) | |
660 | { | |
661 | ||
662 | /* | |
663 | * Node is in the subtree of p, and hence greater than p. | |
664 | */ | |
665 | return node; | |
666 | } | |
667 | ||
668 | /* | |
669 | * p is in the sub-tree under node. | |
670 | */ | |
671 | tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)]; | |
672 | ||
673 | if (tmp_node) | |
674 | { | |
675 | node = tmp_node; | |
676 | continue; | |
677 | } | |
678 | ||
679 | /* | |
680 | * There are no nodes in the direction where p should be. If | |
681 | * node has a right child, then it must be greater than p. | |
682 | */ | |
683 | if (node->l_right) | |
684 | return node->l_right; | |
685 | ||
686 | /* | |
687 | * No more children to follow, go upwards looking for the next | |
688 | * node. | |
689 | */ | |
690 | return route_get_subtree_next (node); | |
691 | } | |
692 | ||
693 | /* | |
694 | * Neither node prefix nor 'p' contains the other. | |
695 | */ | |
696 | cmp = route_table_prefix_iter_cmp (&node->p, p); | |
697 | if (cmp > 0) | |
698 | { | |
699 | ||
700 | /* | |
701 | * Node follows p in iteration order. Return it. | |
702 | */ | |
703 | return node; | |
704 | } | |
705 | ||
706 | assert (cmp < 0); | |
707 | ||
708 | /* | |
709 | * Node and the subtree under it come before prefix p in | |
710 | * iteration order. Prefix p and its sub-tree are not present in | |
711 | * the tree. Go upwards and find the first node that follows the | |
712 | * subtree. That node will also succeed p. | |
713 | */ | |
714 | return route_get_subtree_next (node); | |
715 | } | |
716 | ||
717 | return NULL; | |
718 | } | |
719 | ||
720 | /** | |
721 | * route_table_get_next | |
722 | * | |
723 | * Find the node that occurs after the given prefix in order of | |
724 | * iteration. | |
725 | */ | |
726 | struct route_node * | |
727 | route_table_get_next (const struct route_table *table, struct prefix *p) | |
728 | { | |
729 | struct route_node *node; | |
730 | ||
731 | node = route_table_get_next_internal (table, p); | |
732 | if (node) | |
733 | { | |
734 | assert (route_table_prefix_iter_cmp (&node->p, p) > 0); | |
735 | route_lock_node (node); | |
736 | } | |
737 | return node; | |
738 | } | |
739 | ||
740 | /* | |
741 | * route_table_iter_init | |
742 | */ | |
743 | void | |
744 | route_table_iter_init (route_table_iter_t * iter, struct route_table *table) | |
745 | { | |
746 | memset (iter, 0, sizeof (*iter)); | |
747 | iter->state = RT_ITER_STATE_INIT; | |
748 | iter->table = table; | |
749 | } | |
750 | ||
751 | /* | |
752 | * route_table_iter_pause | |
753 | * | |
754 | * Pause an iteration over the table. This allows the iteration to be | |
755 | * resumed point after arbitrary additions/deletions from the table. | |
756 | * An iteration can be resumed by just calling route_table_iter_next() | |
757 | * on the iterator. | |
758 | */ | |
759 | void | |
760 | route_table_iter_pause (route_table_iter_t * iter) | |
761 | { | |
762 | switch (iter->state) | |
763 | { | |
764 | ||
765 | case RT_ITER_STATE_INIT: | |
766 | case RT_ITER_STATE_PAUSED: | |
767 | case RT_ITER_STATE_DONE: | |
768 | return; | |
769 | ||
770 | case RT_ITER_STATE_ITERATING: | |
771 | ||
772 | /* | |
773 | * Save the prefix that we are currently at. The next call to | |
774 | * route_table_iter_next() will return the node after this prefix | |
775 | * in the tree. | |
776 | */ | |
777 | prefix_copy (&iter->pause_prefix, &iter->current->p); | |
778 | route_unlock_node (iter->current); | |
779 | iter->current = NULL; | |
780 | iter->state = RT_ITER_STATE_PAUSED; | |
781 | return; | |
782 | ||
783 | default: | |
784 | assert (0); | |
785 | } | |
786 | ||
787 | } | |
788 | ||
789 | /* | |
790 | * route_table_iter_cleanup | |
791 | * | |
792 | * Release any resources held by the iterator. | |
793 | */ | |
794 | void | |
795 | route_table_iter_cleanup (route_table_iter_t * iter) | |
796 | { | |
797 | if (iter->state == RT_ITER_STATE_ITERATING) | |
798 | { | |
799 | route_unlock_node (iter->current); | |
800 | iter->current = NULL; | |
801 | } | |
802 | assert (!iter->current); | |
803 | ||
804 | /* | |
805 | * Set the state to RT_ITER_STATE_DONE to make any | |
806 | * route_table_iter_next() calls on this iterator return NULL. | |
807 | */ | |
808 | iter->state = RT_ITER_STATE_DONE; | |
809 | } |