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