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