2 * Routing Table functions.
3 * Copyright (C) 1998 Kunihiro Ishiguro
5 * This file is part of GNU Zebra.
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
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.
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Zebra; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
28 #include "sockunion.h"
30 void route_node_delete (struct route_node *);
31 void route_table_free (struct route_table *);
34 route_table_init (void)
36 struct route_table *rt;
38 rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
43 route_table_finish (struct route_table *rt)
45 route_table_free (rt);
48 /* Allocate new route node. */
52 struct route_node *node;
53 node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
57 /* Allocate new route node with prefix set. */
59 route_node_set (struct route_table *table, struct prefix *prefix)
61 struct route_node *node;
63 node = route_node_new ();
65 prefix_copy (&node->p, prefix);
71 /* Free route node. */
73 route_node_free (struct route_node *node)
75 XFREE (MTYPE_ROUTE_NODE, node);
78 /* Free route table. */
80 route_table_free (struct route_table *rt)
82 struct route_node *tmp_node;
83 struct route_node *node;
100 node = node->l_right;
109 if (node->l_left == tmp_node)
112 node->l_right = NULL;
114 route_node_free (tmp_node);
118 route_node_free (tmp_node);
123 XFREE (MTYPE_ROUTE_TABLE, rt);
127 /* Utility mask array. */
128 static u_char maskbit[] =
130 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
133 /* Common prefix route genaration. */
135 route_common (struct prefix *n, struct prefix *p, struct prefix *new)
141 u_char *np = (u_char *)&n->u.prefix;
142 u_char *pp = (u_char *)&p->u.prefix;
143 u_char *newp = (u_char *)&new->u.prefix;
145 for (i = 0; i < p->prefixlen / 8; i++)
153 new->prefixlen = i * 8;
155 if (new->prefixlen != p->prefixlen)
157 diff = np[i] ^ pp[i];
159 while (new->prefixlen < p->prefixlen && !(mask & diff))
164 newp[i] = np[i] & maskbit[new->prefixlen % 8];
168 /* Macro version of check_bit (). */
169 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
171 /* Check bit of the prefix. */
173 check_bit (u_char *prefix, u_char prefixlen)
177 u_char *p = (u_char *)prefix;
179 assert (prefixlen <= 128);
181 offset = prefixlen / 8;
182 shift = 7 - (prefixlen % 8);
184 return (p[offset] >> shift & 1);
187 /* Macro version of set_link (). */
188 #define SET_LINK(X,Y) (X)->link[CHECK_BIT(&(Y)->prefix,(X)->prefixlen)] = (Y);\
192 set_link (struct route_node *node, struct route_node *new)
196 bit = check_bit (&new->p.u.prefix, node->p.prefixlen);
198 assert (bit == 0 || bit == 1);
200 node->link[bit] = new;
206 route_lock_node (struct route_node *node)
214 route_unlock_node (struct route_node *node)
219 route_node_delete (node);
222 /* Dump routing table. */
224 route_dump_node (struct route_table *t)
226 struct route_node *node;
229 for (node = route_top (t); node != NULL; node = route_next (node))
231 printf ("[%d] %p %s/%d\n",
234 inet_ntop (node->p.family, &node->p.u.prefix, buf, 46),
239 /* Find matched prefix. */
241 route_node_match (struct route_table *table, struct prefix *p)
243 struct route_node *node;
244 struct route_node *matched;
249 /* Walk down tree. If there is matched route then store it to
251 while (node && node->p.prefixlen <= p->prefixlen &&
252 prefix_match (&node->p, p))
256 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
259 /* If matched route found, return it. */
261 return route_lock_node (matched);
267 route_node_match_ipv4 (struct route_table *table, struct in_addr *addr)
269 struct prefix_ipv4 p;
271 memset (&p, 0, sizeof (struct prefix_ipv4));
273 p.prefixlen = IPV4_MAX_PREFIXLEN;
276 return route_node_match (table, (struct prefix *) &p);
281 route_node_match_ipv6 (struct route_table *table, struct in6_addr *addr)
283 struct prefix_ipv6 p;
285 memset (&p, 0, sizeof (struct prefix_ipv6));
287 p.prefixlen = IPV6_MAX_PREFIXLEN;
290 return route_node_match (table, (struct prefix *) &p);
292 #endif /* HAVE_IPV6 */
294 /* Lookup same prefix node. Return NULL when we can't find route. */
296 route_node_lookup (struct route_table *table, struct prefix *p)
298 struct route_node *node;
302 while (node && node->p.prefixlen <= p->prefixlen &&
303 prefix_match (&node->p, p))
305 if (node->p.prefixlen == p->prefixlen && node->info)
306 return route_lock_node (node);
308 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
314 /* Add node to routing table. */
316 route_node_get (struct route_table *table, struct prefix *p)
318 struct route_node *new;
319 struct route_node *node;
320 struct route_node *match;
324 while (node && node->p.prefixlen <= p->prefixlen &&
325 prefix_match (&node->p, p))
327 if (node->p.prefixlen == p->prefixlen)
329 route_lock_node (node);
333 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)];
338 new = route_node_set (table, p);
340 set_link (match, new);
346 new = route_node_new ();
347 route_common (&node->p, p, &new->p);
348 new->p.family = p->family;
350 set_link (new, node);
353 set_link (match, new);
357 if (new->p.prefixlen != p->prefixlen)
360 new = route_node_set (table, p);
361 set_link (match, new);
364 route_lock_node (new);
369 /* Delete node from the routing table. */
371 route_node_delete (struct route_node *node)
373 struct route_node *child;
374 struct route_node *parent;
376 assert (node->lock == 0);
377 assert (node->info == NULL);
379 if (node->l_left && node->l_right)
383 child = node->l_left;
385 child = node->l_right;
387 parent = node->parent;
390 child->parent = parent;
394 if (parent->l_left == node)
395 parent->l_left = child;
397 parent->l_right = child;
400 node->table->top = child;
402 route_node_free (node);
404 /* If parent node is stub then delete it also. */
405 if (parent && parent->lock == 0)
406 route_node_delete (parent);
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. */
412 route_top (struct route_table *table)
414 /* If there is no node in the routing table return NULL. */
415 if (table->top == NULL)
418 /* Lock the top node and return it. */
419 route_lock_node (table->top);
423 /* Unlock current node and lock next node then return it. */
425 route_next (struct route_node *node)
427 struct route_node *next;
428 struct route_node *start;
430 /* Node may be deleted from route_unlock_node so we have to preserve
431 next node's pointer. */
436 route_lock_node (next);
437 route_unlock_node (node);
442 next = node->l_right;
443 route_lock_node (next);
444 route_unlock_node (node);
451 if (node->parent->l_left == node && node->parent->l_right)
453 next = node->parent->l_right;
454 route_lock_node (next);
455 route_unlock_node (start);
460 route_unlock_node (start);
464 /* Unlock current node and lock next node until limit. */
466 route_next_until (struct route_node *node, struct route_node *limit)
468 struct route_node *next;
469 struct route_node *start;
471 /* Node may be deleted from route_unlock_node so we have to preserve
472 next node's pointer. */
477 route_lock_node (next);
478 route_unlock_node (node);
483 next = node->l_right;
484 route_lock_node (next);
485 route_unlock_node (node);
490 while (node->parent && node != limit)
492 if (node->parent->l_left == node && node->parent->l_right)
494 next = node->parent->l_right;
495 route_lock_node (next);
496 route_unlock_node (start);
501 route_unlock_node (start);