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