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