Annotation of embedaddon/quagga/lib/table.c, revision 1.1
1.1 ! misho 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: *
! 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
! 20: * 02111-1307, USA.
! 21: */
! 22:
! 23: #include <zebra.h>
! 24:
! 25: #include "prefix.h"
! 26: #include "table.h"
! 27: #include "memory.h"
! 28: #include "sockunion.h"
! 29:
! 30: void route_node_delete (struct route_node *);
! 31: void route_table_free (struct route_table *);
! 32:
! 33: struct route_table *
! 34: route_table_init (void)
! 35: {
! 36: struct route_table *rt;
! 37:
! 38: rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table));
! 39: return rt;
! 40: }
! 41:
! 42: void
! 43: route_table_finish (struct route_table *rt)
! 44: {
! 45: route_table_free (rt);
! 46: }
! 47:
! 48: /* Allocate new route node. */
! 49: static struct route_node *
! 50: route_node_new (void)
! 51: {
! 52: struct route_node *node;
! 53: node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node));
! 54: return node;
! 55: }
! 56:
! 57: /* Allocate new route node with prefix set. */
! 58: static struct route_node *
! 59: route_node_set (struct route_table *table, struct prefix *prefix)
! 60: {
! 61: struct route_node *node;
! 62:
! 63: node = route_node_new ();
! 64:
! 65: prefix_copy (&node->p, prefix);
! 66: node->table = table;
! 67:
! 68: return node;
! 69: }
! 70:
! 71: /* Free route node. */
! 72: static void
! 73: route_node_free (struct route_node *node)
! 74: {
! 75: XFREE (MTYPE_ROUTE_NODE, node);
! 76: }
! 77:
! 78: /* Free route table. */
! 79: void
! 80: 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:
! 88: node = rt->top;
! 89:
! 90: while (node)
! 91: {
! 92: if (node->l_left)
! 93: {
! 94: node = node->l_left;
! 95: continue;
! 96: }
! 97:
! 98: if (node->l_right)
! 99: {
! 100: node = node->l_right;
! 101: continue;
! 102: }
! 103:
! 104: tmp_node = node;
! 105: node = node->parent;
! 106:
! 107: if (node != NULL)
! 108: {
! 109: if (node->l_left == tmp_node)
! 110: node->l_left = NULL;
! 111: else
! 112: node->l_right = NULL;
! 113:
! 114: route_node_free (tmp_node);
! 115: }
! 116: else
! 117: {
! 118: route_node_free (tmp_node);
! 119: break;
! 120: }
! 121: }
! 122:
! 123: XFREE (MTYPE_ROUTE_TABLE, rt);
! 124: return;
! 125: }
! 126:
! 127: /* Utility mask array. */
! 128: static const u_char maskbit[] =
! 129: {
! 130: 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff
! 131: };
! 132:
! 133: /* Common prefix route genaration. */
! 134: static void
! 135: route_common (struct prefix *n, struct prefix *p, struct prefix *new)
! 136: {
! 137: int i;
! 138: u_char diff;
! 139: u_char mask;
! 140:
! 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;
! 144:
! 145: for (i = 0; i < p->prefixlen / 8; i++)
! 146: {
! 147: if (np[i] == pp[i])
! 148: newp[i] = np[i];
! 149: else
! 150: break;
! 151: }
! 152:
! 153: new->prefixlen = i * 8;
! 154:
! 155: if (new->prefixlen != p->prefixlen)
! 156: {
! 157: diff = np[i] ^ pp[i];
! 158: mask = 0x80;
! 159: while (new->prefixlen < p->prefixlen && !(mask & diff))
! 160: {
! 161: mask >>= 1;
! 162: new->prefixlen++;
! 163: }
! 164: newp[i] = np[i] & maskbit[new->prefixlen % 8];
! 165: }
! 166: }
! 167:
! 168: static void
! 169: set_link (struct route_node *node, struct route_node *new)
! 170: {
! 171: unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen);
! 172:
! 173: node->link[bit] = new;
! 174: new->parent = node;
! 175: }
! 176:
! 177: /* Lock node. */
! 178: struct route_node *
! 179: route_lock_node (struct route_node *node)
! 180: {
! 181: node->lock++;
! 182: return node;
! 183: }
! 184:
! 185: /* Unlock node. */
! 186: void
! 187: route_unlock_node (struct route_node *node)
! 188: {
! 189: node->lock--;
! 190:
! 191: if (node->lock == 0)
! 192: route_node_delete (node);
! 193: }
! 194:
! 195: /* Find matched prefix. */
! 196: struct route_node *
! 197: route_node_match (const struct route_table *table, const struct prefix *p)
! 198: {
! 199: struct route_node *node;
! 200: struct route_node *matched;
! 201:
! 202: matched = NULL;
! 203: node = table->top;
! 204:
! 205: /* Walk down tree. If there is matched route then store it to
! 206: matched. */
! 207: while (node && node->p.prefixlen <= p->prefixlen &&
! 208: prefix_match (&node->p, p))
! 209: {
! 210: if (node->info)
! 211: matched = node;
! 212:
! 213: if (node->p.prefixlen == p->prefixlen)
! 214: break;
! 215:
! 216: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
! 217: }
! 218:
! 219: /* If matched route found, return it. */
! 220: if (matched)
! 221: return route_lock_node (matched);
! 222:
! 223: return NULL;
! 224: }
! 225:
! 226: struct route_node *
! 227: route_node_match_ipv4 (const struct route_table *table,
! 228: const struct in_addr *addr)
! 229: {
! 230: struct prefix_ipv4 p;
! 231:
! 232: memset (&p, 0, sizeof (struct prefix_ipv4));
! 233: p.family = AF_INET;
! 234: p.prefixlen = IPV4_MAX_PREFIXLEN;
! 235: p.prefix = *addr;
! 236:
! 237: return route_node_match (table, (struct prefix *) &p);
! 238: }
! 239:
! 240: #ifdef HAVE_IPV6
! 241: struct route_node *
! 242: route_node_match_ipv6 (const struct route_table *table,
! 243: const struct in6_addr *addr)
! 244: {
! 245: struct prefix_ipv6 p;
! 246:
! 247: memset (&p, 0, sizeof (struct prefix_ipv6));
! 248: p.family = AF_INET6;
! 249: p.prefixlen = IPV6_MAX_PREFIXLEN;
! 250: p.prefix = *addr;
! 251:
! 252: return route_node_match (table, (struct prefix *) &p);
! 253: }
! 254: #endif /* HAVE_IPV6 */
! 255:
! 256: /* Lookup same prefix node. Return NULL when we can't find route. */
! 257: struct route_node *
! 258: route_node_lookup (struct route_table *table, struct prefix *p)
! 259: {
! 260: struct route_node *node;
! 261:
! 262: node = table->top;
! 263:
! 264: while (node && node->p.prefixlen <= p->prefixlen &&
! 265: prefix_match (&node->p, p))
! 266: {
! 267: if (node->p.prefixlen == p->prefixlen)
! 268: return node->info ? route_lock_node (node) : NULL;
! 269:
! 270: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
! 271: }
! 272:
! 273: return NULL;
! 274: }
! 275:
! 276: /* Add node to routing table. */
! 277: struct route_node *
! 278: route_node_get (struct route_table *table, struct prefix *p)
! 279: {
! 280: struct route_node *new;
! 281: struct route_node *node;
! 282: struct route_node *match;
! 283:
! 284: match = NULL;
! 285: node = table->top;
! 286: while (node && node->p.prefixlen <= p->prefixlen &&
! 287: prefix_match (&node->p, p))
! 288: {
! 289: if (node->p.prefixlen == p->prefixlen)
! 290: return route_lock_node (node);
! 291:
! 292: match = node;
! 293: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
! 294: }
! 295:
! 296: if (node == NULL)
! 297: {
! 298: new = route_node_set (table, p);
! 299: if (match)
! 300: set_link (match, new);
! 301: else
! 302: table->top = new;
! 303: }
! 304: else
! 305: {
! 306: new = route_node_new ();
! 307: route_common (&node->p, p, &new->p);
! 308: new->p.family = p->family;
! 309: new->table = table;
! 310: set_link (new, node);
! 311:
! 312: if (match)
! 313: set_link (match, new);
! 314: else
! 315: table->top = new;
! 316:
! 317: if (new->p.prefixlen != p->prefixlen)
! 318: {
! 319: match = new;
! 320: new = route_node_set (table, p);
! 321: set_link (match, new);
! 322: }
! 323: }
! 324: route_lock_node (new);
! 325:
! 326: return new;
! 327: }
! 328:
! 329: /* Delete node from the routing table. */
! 330: void
! 331: route_node_delete (struct route_node *node)
! 332: {
! 333: struct route_node *child;
! 334: struct route_node *parent;
! 335:
! 336: assert (node->lock == 0);
! 337: assert (node->info == NULL);
! 338:
! 339: if (node->l_left && node->l_right)
! 340: return;
! 341:
! 342: if (node->l_left)
! 343: child = node->l_left;
! 344: else
! 345: child = node->l_right;
! 346:
! 347: parent = node->parent;
! 348:
! 349: if (child)
! 350: child->parent = parent;
! 351:
! 352: if (parent)
! 353: {
! 354: if (parent->l_left == node)
! 355: parent->l_left = child;
! 356: else
! 357: parent->l_right = child;
! 358: }
! 359: else
! 360: node->table->top = child;
! 361:
! 362: route_node_free (node);
! 363:
! 364: /* If parent node is stub then delete it also. */
! 365: if (parent && parent->lock == 0)
! 366: route_node_delete (parent);
! 367: }
! 368:
! 369: /* Get fist node and lock it. This function is useful when one want
! 370: to lookup all the node exist in the routing table. */
! 371: struct route_node *
! 372: route_top (struct route_table *table)
! 373: {
! 374: /* If there is no node in the routing table return NULL. */
! 375: if (table->top == NULL)
! 376: return NULL;
! 377:
! 378: /* Lock the top node and return it. */
! 379: route_lock_node (table->top);
! 380: return table->top;
! 381: }
! 382:
! 383: /* Unlock current node and lock next node then return it. */
! 384: struct route_node *
! 385: route_next (struct route_node *node)
! 386: {
! 387: struct route_node *next;
! 388: struct route_node *start;
! 389:
! 390: /* Node may be deleted from route_unlock_node so we have to preserve
! 391: next node's pointer. */
! 392:
! 393: if (node->l_left)
! 394: {
! 395: next = node->l_left;
! 396: route_lock_node (next);
! 397: route_unlock_node (node);
! 398: return next;
! 399: }
! 400: if (node->l_right)
! 401: {
! 402: next = node->l_right;
! 403: route_lock_node (next);
! 404: route_unlock_node (node);
! 405: return next;
! 406: }
! 407:
! 408: start = node;
! 409: while (node->parent)
! 410: {
! 411: if (node->parent->l_left == node && node->parent->l_right)
! 412: {
! 413: next = node->parent->l_right;
! 414: route_lock_node (next);
! 415: route_unlock_node (start);
! 416: return next;
! 417: }
! 418: node = node->parent;
! 419: }
! 420: route_unlock_node (start);
! 421: return NULL;
! 422: }
! 423:
! 424: /* Unlock current node and lock next node until limit. */
! 425: struct route_node *
! 426: route_next_until (struct route_node *node, struct route_node *limit)
! 427: {
! 428: struct route_node *next;
! 429: struct route_node *start;
! 430:
! 431: /* Node may be deleted from route_unlock_node so we have to preserve
! 432: next node's pointer. */
! 433:
! 434: if (node->l_left)
! 435: {
! 436: next = node->l_left;
! 437: route_lock_node (next);
! 438: route_unlock_node (node);
! 439: return next;
! 440: }
! 441: if (node->l_right)
! 442: {
! 443: next = node->l_right;
! 444: route_lock_node (next);
! 445: route_unlock_node (node);
! 446: return next;
! 447: }
! 448:
! 449: start = node;
! 450: while (node->parent && node != limit)
! 451: {
! 452: if (node->parent->l_left == node && node->parent->l_right)
! 453: {
! 454: next = node->parent->l_right;
! 455: route_lock_node (next);
! 456: route_unlock_node (start);
! 457: return next;
! 458: }
! 459: node = node->parent;
! 460: }
! 461: route_unlock_node (start);
! 462: return NULL;
! 463: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to table.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib