diff options
Diffstat (limited to 'lib/table.c')
-rw-r--r-- | lib/table.c | 503 |
1 files changed, 503 insertions, 0 deletions
diff --git a/lib/table.c b/lib/table.c new file mode 100644 index 00000000..00ba58d9 --- /dev/null +++ b/lib/table.c @@ -0,0 +1,503 @@ +/* + * Routing Table functions. + * Copyright (C) 1998 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Zebra; see the file COPYING. If not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include <zebra.h> + +#include "prefix.h" +#include "table.h" +#include "memory.h" +#include "sockunion.h" + +void route_node_delete (struct route_node *); +void route_table_free (struct route_table *); + +struct route_table * +route_table_init (void) +{ + struct route_table *rt; + + rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table)); + return rt; +} + +void +route_table_finish (struct route_table *rt) +{ + route_table_free (rt); +} + +/* Allocate new route node. */ +struct route_node * +route_node_new () +{ + struct route_node *node; + node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node)); + return node; +} + +/* Allocate new route node with prefix set. */ +struct route_node * +route_node_set (struct route_table *table, struct prefix *prefix) +{ + struct route_node *node; + + node = route_node_new (); + + prefix_copy (&node->p, prefix); + node->table = table; + + return node; +} + +/* Free route node. */ +void +route_node_free (struct route_node *node) +{ + XFREE (MTYPE_ROUTE_NODE, node); +} + +/* Free route table. */ +void +route_table_free (struct route_table *rt) +{ + struct route_node *tmp_node; + struct route_node *node; + + if (rt == NULL) + return; + + node = rt->top; + + while (node) + { + if (node->l_left) + { + node = node->l_left; + continue; + } + + if (node->l_right) + { + node = node->l_right; + continue; + } + + tmp_node = node; + node = node->parent; + + if (node != NULL) + { + if (node->l_left == tmp_node) + node->l_left = NULL; + else + node->l_right = NULL; + + route_node_free (tmp_node); + } + else + { + route_node_free (tmp_node); + break; + } + } + + XFREE (MTYPE_ROUTE_TABLE, rt); + return; +} + +/* Utility mask array. */ +static u_char maskbit[] = +{ + 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff +}; + +/* Common prefix route genaration. */ +static void +route_common (struct prefix *n, struct prefix *p, struct prefix *new) +{ + int i; + u_char diff; + u_char mask; + + u_char *np = (u_char *)&n->u.prefix; + u_char *pp = (u_char *)&p->u.prefix; + u_char *newp = (u_char *)&new->u.prefix; + + for (i = 0; i < p->prefixlen / 8; i++) + { + if (np[i] == pp[i]) + newp[i] = np[i]; + else + break; + } + + new->prefixlen = i * 8; + + if (new->prefixlen != p->prefixlen) + { + diff = np[i] ^ pp[i]; + mask = 0x80; + while (new->prefixlen < p->prefixlen && !(mask & diff)) + { + mask >>= 1; + new->prefixlen++; + } + newp[i] = np[i] & maskbit[new->prefixlen % 8]; + } +} + +/* Macro version of check_bit (). */ +#define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1) + +/* Check bit of the prefix. */ +static int +check_bit (u_char *prefix, u_char prefixlen) +{ + int offset; + int shift; + u_char *p = (u_char *)prefix; + + assert (prefixlen <= 128); + + offset = prefixlen / 8; + shift = 7 - (prefixlen % 8); + + return (p[offset] >> shift & 1); +} + +/* Macro version of set_link (). */ +#define SET_LINK(X,Y) (X)->link[CHECK_BIT(&(Y)->prefix,(X)->prefixlen)] = (Y);\ + (Y)->parent = (X) + +static void +set_link (struct route_node *node, struct route_node *new) +{ + int bit; + + bit = check_bit (&new->p.u.prefix, node->p.prefixlen); + + assert (bit == 0 || bit == 1); + + node->link[bit] = new; + new->parent = node; +} + +/* Lock node. */ +struct route_node * +route_lock_node (struct route_node *node) +{ + node->lock++; + return node; +} + +/* Unlock node. */ +void +route_unlock_node (struct route_node *node) +{ + node->lock--; + + if (node->lock == 0) + route_node_delete (node); +} + +/* Dump routing table. */ +void +route_dump_node (struct route_table *t) +{ + struct route_node *node; + char buf[46]; + + for (node = route_top (t); node != NULL; node = route_next (node)) + { + printf ("[%d] %p %s/%d\n", + node->lock, + node->info, + inet_ntop (node->p.family, &node->p.u.prefix, buf, 46), + node->p.prefixlen); + } +} + +/* Find matched prefix. */ +struct route_node * +route_node_match (struct route_table *table, struct prefix *p) +{ + struct route_node *node; + struct route_node *matched; + + matched = NULL; + node = table->top; + + /* Walk down tree. If there is matched route then store it to + matched. */ + while (node && node->p.prefixlen <= p->prefixlen && + prefix_match (&node->p, p)) + { + if (node->info) + matched = node; + node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; + } + + /* If matched route found, return it. */ + if (matched) + return route_lock_node (matched); + + return NULL; +} + +struct route_node * +route_node_match_ipv4 (struct route_table *table, struct in_addr *addr) +{ + struct prefix_ipv4 p; + + memset (&p, 0, sizeof (struct prefix_ipv4)); + p.family = AF_INET; + p.prefixlen = IPV4_MAX_PREFIXLEN; + p.prefix = *addr; + + return route_node_match (table, (struct prefix *) &p); +} + +#ifdef HAVE_IPV6 +struct route_node * +route_node_match_ipv6 (struct route_table *table, struct in6_addr *addr) +{ + struct prefix_ipv6 p; + + memset (&p, 0, sizeof (struct prefix_ipv6)); + p.family = AF_INET6; + p.prefixlen = IPV6_MAX_PREFIXLEN; + p.prefix = *addr; + + return route_node_match (table, (struct prefix *) &p); +} +#endif /* HAVE_IPV6 */ + +/* Lookup same prefix node. Return NULL when we can't find route. */ +struct route_node * +route_node_lookup (struct route_table *table, struct prefix *p) +{ + struct route_node *node; + + node = table->top; + + while (node && node->p.prefixlen <= p->prefixlen && + prefix_match (&node->p, p)) + { + if (node->p.prefixlen == p->prefixlen && node->info) + return route_lock_node (node); + + node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; + } + + return NULL; +} + +/* Add node to routing table. */ +struct route_node * +route_node_get (struct route_table *table, struct prefix *p) +{ + struct route_node *new; + struct route_node *node; + struct route_node *match; + + match = NULL; + node = table->top; + while (node && node->p.prefixlen <= p->prefixlen && + prefix_match (&node->p, p)) + { + if (node->p.prefixlen == p->prefixlen) + { + route_lock_node (node); + return node; + } + match = node; + node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; + } + + if (node == NULL) + { + new = route_node_set (table, p); + if (match) + set_link (match, new); + else + table->top = new; + } + else + { + new = route_node_new (); + route_common (&node->p, p, &new->p); + new->p.family = p->family; + new->table = table; + set_link (new, node); + + if (match) + set_link (match, new); + else + table->top = new; + + if (new->p.prefixlen != p->prefixlen) + { + match = new; + new = route_node_set (table, p); + set_link (match, new); + } + } + route_lock_node (new); + + return new; +} + +/* Delete node from the routing table. */ +void +route_node_delete (struct route_node *node) +{ + struct route_node *child; + struct route_node *parent; + + assert (node->lock == 0); + assert (node->info == NULL); + + if (node->l_left && node->l_right) + return; + + if (node->l_left) + child = node->l_left; + else + child = node->l_right; + + parent = node->parent; + + if (child) + child->parent = parent; + + if (parent) + { + if (parent->l_left == node) + parent->l_left = child; + else + parent->l_right = child; + } + else + node->table->top = child; + + route_node_free (node); + + /* If parent node is stub then delete it also. */ + if (parent && parent->lock == 0) + route_node_delete (parent); +} + +/* Get fist node and lock it. This function is useful when one want + to lookup all the node exist in the routing table. */ +struct route_node * +route_top (struct route_table *table) +{ + /* If there is no node in the routing table return NULL. */ + if (table->top == NULL) + return NULL; + + /* Lock the top node and return it. */ + route_lock_node (table->top); + return table->top; +} + +/* Unlock current node and lock next node then return it. */ +struct route_node * +route_next (struct route_node *node) +{ + struct route_node *next; + struct route_node *start; + + /* Node may be deleted from route_unlock_node so we have to preserve + next node's pointer. */ + + if (node->l_left) + { + next = node->l_left; + route_lock_node (next); + route_unlock_node (node); + return next; + } + if (node->l_right) + { + next = node->l_right; + route_lock_node (next); + route_unlock_node (node); + return next; + } + + start = node; + while (node->parent) + { + if (node->parent->l_left == node && node->parent->l_right) + { + next = node->parent->l_right; + route_lock_node (next); + route_unlock_node (start); + return next; + } + node = node->parent; + } + route_unlock_node (start); + return NULL; +} + +/* Unlock current node and lock next node until limit. */ +struct route_node * +route_next_until (struct route_node *node, struct route_node *limit) +{ + struct route_node *next; + struct route_node *start; + + /* Node may be deleted from route_unlock_node so we have to preserve + next node's pointer. */ + + if (node->l_left) + { + next = node->l_left; + route_lock_node (next); + route_unlock_node (node); + return next; + } + if (node->l_right) + { + next = node->l_right; + route_lock_node (next); + route_unlock_node (node); + return next; + } + + start = node; + while (node->parent && node != limit) + { + if (node->parent->l_left == node && node->parent->l_right) + { + next = node->parent->l_right; + route_lock_node (next); + route_unlock_node (start); + return next; + } + node = node->parent; + } + route_unlock_node (start); + return NULL; +} |