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