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