diff options
Diffstat (limited to 'lib/table.c')
| -rw-r--r-- | lib/table.c | 1162 |
1 files changed, 553 insertions, 609 deletions
diff --git a/lib/table.c b/lib/table.c index 1095b03b76..8e84d803ea 100644 --- a/lib/table.c +++ b/lib/table.c @@ -29,510 +29,472 @@ #include "sockunion.h" #include "jhash.h" -DEFINE_MTYPE( LIB, ROUTE_TABLE, "Route table") -DEFINE_MTYPE( LIB, ROUTE_NODE, "Route node") +DEFINE_MTYPE(LIB, ROUTE_TABLE, "Route table") +DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node") -static void route_node_delete (struct route_node *); -static void route_table_free (struct route_table *); +static void route_node_delete(struct route_node *); +static void route_table_free(struct route_table *); static unsigned route_table_hash_key(void *pp) { - struct prefix copy; + struct prefix copy; - /* make sure *all* unused bits are zero, particularly including alignment / - * padding and unused prefix bytes. */ - memset (©, 0, sizeof(copy)); - prefix_copy (©, (struct prefix *)pp); - return jhash (©, sizeof(copy), 0x55aa5a5a); + /* make sure *all* unused bits are zero, particularly including + * alignment / + * padding and unused prefix bytes. */ + memset(©, 0, sizeof(copy)); + prefix_copy(©, (struct prefix *)pp); + return jhash(©, sizeof(copy), 0x55aa5a5a); } static int route_table_hash_cmp(const void *a, const void *b) { - const struct prefix *pa = a, *pb = b; - return prefix_cmp(pa, pb) == 0; + const struct prefix *pa = a, *pb = b; + return prefix_cmp(pa, pb) == 0; } /* * route_table_init_with_delegate */ struct route_table * -route_table_init_with_delegate (route_table_delegate_t *delegate) +route_table_init_with_delegate(route_table_delegate_t *delegate) { - struct route_table *rt; + struct route_table *rt; - rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table)); - rt->delegate = delegate; - rt->hash = hash_create(route_table_hash_key, - route_table_hash_cmp, - "route table hash"); - return rt; + rt = XCALLOC(MTYPE_ROUTE_TABLE, sizeof(struct route_table)); + rt->delegate = delegate; + rt->hash = hash_create(route_table_hash_key, route_table_hash_cmp, + "route table hash"); + return rt; } -void -route_table_finish (struct route_table *rt) +void route_table_finish(struct route_table *rt) { - route_table_free (rt); + route_table_free(rt); } /* Allocate new route node. */ -static struct route_node * -route_node_new (struct route_table *table) +static struct route_node *route_node_new(struct route_table *table) { - return table->delegate->create_node (table->delegate, table); + return table->delegate->create_node(table->delegate, table); } /* Allocate new route node with prefix set. */ -static struct route_node * -route_node_set (struct route_table *table, const struct prefix *prefix) +static struct route_node *route_node_set(struct route_table *table, + const struct prefix *prefix) { - struct route_node *node, *inserted; - - node = route_node_new (table); + struct route_node *node, *inserted; - prefix_copy (&node->p, prefix); - node->table = table; + node = route_node_new(table); - inserted = hash_get (node->table->hash, node, hash_alloc_intern); - assert (inserted == node); + prefix_copy(&node->p, prefix); + node->table = table; - return node; + inserted = hash_get(node->table->hash, node, hash_alloc_intern); + assert(inserted == node); + + return node; } /* Free route node. */ -static void -route_node_free (struct route_table *table, struct route_node *node) +static void route_node_free(struct route_table *table, struct route_node *node) { - if (table->cleanup) - table->cleanup(table, node); - table->delegate->destroy_node (table->delegate, table, node); + if (table->cleanup) + table->cleanup(table, node); + table->delegate->destroy_node(table->delegate, table, node); } /* Free route table. */ -static void -route_table_free (struct route_table *rt) -{ - struct route_node *tmp_node; - struct route_node *node; - - if (rt == NULL) - return; - - hash_clean (rt->hash, NULL); - hash_free (rt->hash); - - node = rt->top; - - /* Bulk deletion of nodes remaining in this table. This function is not - called until workers have completed their dependency on this table. - A final route_unlock_node() will not be called for these nodes. */ - while (node) - { - if (node->l_left) - { - node = node->l_left; - continue; +static void route_table_free(struct route_table *rt) +{ + struct route_node *tmp_node; + struct route_node *node; + + if (rt == NULL) + return; + + hash_clean(rt->hash, NULL); + hash_free(rt->hash); + + node = rt->top; + + /* Bulk deletion of nodes remaining in this table. This function is not + called until workers have completed their dependency on this table. + A final route_unlock_node() will not be called for these nodes. */ + 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; + + tmp_node->table->count--; + tmp_node->lock = 0; /* to cause assert if unlocked after this */ + route_node_free(rt, tmp_node); + + if (node != NULL) { + if (node->l_left == tmp_node) + node->l_left = NULL; + else + node->l_right = NULL; + } else { + break; + } } - if (node->l_right) - { - node = node->l_right; - continue; - } - - tmp_node = node; - node = node->parent; - - tmp_node->table->count--; - tmp_node->lock = 0; /* to cause assert if unlocked after this */ - route_node_free (rt, tmp_node); - - if (node != NULL) - { - if (node->l_left == tmp_node) - node->l_left = NULL; - else - node->l_right = NULL; - } - else - { - break; - } - } - - assert (rt->count == 0); + assert(rt->count == 0); - XFREE (MTYPE_ROUTE_TABLE, rt); - return; + XFREE(MTYPE_ROUTE_TABLE, rt); + return; } /* Utility mask array. */ -static const u_char maskbit[] = -{ - 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff -}; +static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0, + 0xf8, 0xfc, 0xfe, 0xff}; /* Common prefix route genaration. */ -static void -route_common (const struct prefix *n, const struct prefix *p, struct prefix *new) -{ - int i; - u_char diff; - u_char mask; - - const u_char *np = (const u_char *)&n->u.prefix; - const u_char *pp = (const 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++; +static void route_common(const struct prefix *n, const struct prefix *p, + struct prefix *new) +{ + int i; + u_char diff; + u_char mask; + + const u_char *np = (const u_char *)&n->u.prefix; + const u_char *pp = (const 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]; } - newp[i] = np[i] & maskbit[new->prefixlen % 8]; - } } -static void -set_link (struct route_node *node, struct route_node *new) +static void set_link(struct route_node *node, struct route_node *new) { - unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen); + unsigned int bit = prefix_bit(&new->p.u.prefix, node->p.prefixlen); - node->link[bit] = new; - new->parent = node; + node->link[bit] = new; + new->parent = node; } /* Lock node. */ -struct route_node * -route_lock_node (struct route_node *node) +struct route_node *route_lock_node(struct route_node *node) { - node->lock++; - return node; + node->lock++; + return node; } /* Unlock node. */ -void -route_unlock_node (struct route_node *node) +void route_unlock_node(struct route_node *node) { - assert (node->lock > 0); - node->lock--; + assert(node->lock > 0); + node->lock--; - if (node->lock == 0) - route_node_delete (node); + if (node->lock == 0) + route_node_delete(node); } /* Find matched prefix. */ -struct route_node * -route_node_match (const struct route_table *table, union prefixconstptr pu) +struct route_node *route_node_match(const struct route_table *table, + union prefixconstptr pu) { - const struct prefix *p = pu.p; - struct route_node *node; - struct route_node *matched; + const struct prefix *p = pu.p; + struct route_node *node; + struct route_node *matched; - matched = NULL; - node = table->top; + 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; - - if (node->p.prefixlen == p->prefixlen) - break; - - node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)]; - } + /* 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; - /* If matched route found, return it. */ - if (matched) - return route_lock_node (matched); + if (node->p.prefixlen == p->prefixlen) + break; - return NULL; + node = node->link[prefix_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 (const struct route_table *table, - const struct in_addr *addr) +struct route_node *route_node_match_ipv4(const struct route_table *table, + const struct in_addr *addr) { - struct prefix_ipv4 p; + struct prefix_ipv4 p; - memset (&p, 0, sizeof (struct prefix_ipv4)); - p.family = AF_INET; - p.prefixlen = IPV4_MAX_PREFIXLEN; - p.prefix = *addr; + 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); + return route_node_match(table, (struct prefix *)&p); } -struct route_node * -route_node_match_ipv6 (const struct route_table *table, - const struct in6_addr *addr) +struct route_node *route_node_match_ipv6(const struct route_table *table, + const struct in6_addr *addr) { - struct prefix_ipv6 p; + struct prefix_ipv6 p; - memset (&p, 0, sizeof (struct prefix_ipv6)); - p.family = AF_INET6; - p.prefixlen = IPV6_MAX_PREFIXLEN; - p.prefix = *addr; + 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); + return route_node_match(table, (struct prefix *)&p); } /* Lookup same prefix node. Return NULL when we can't find route. */ -struct route_node * -route_node_lookup (const struct route_table *table, union prefixconstptr pu) +struct route_node *route_node_lookup(const struct route_table *table, + union prefixconstptr pu) { - const struct prefix *p = pu.p; - struct route_node *node; + const struct prefix *p = pu.p; + struct route_node *node; - node = hash_get (table->hash, (void *)p, NULL); - return (node && node->info) ? route_lock_node (node) : NULL; + node = hash_get(table->hash, (void *)p, NULL); + return (node && node->info) ? route_lock_node(node) : NULL; } /* Lookup same prefix node. Return NULL when we can't find route. */ -struct route_node * -route_node_lookup_maynull (const struct route_table *table, union prefixconstptr pu) +struct route_node *route_node_lookup_maynull(const struct route_table *table, + union prefixconstptr pu) { - const struct prefix *p = pu.p; - struct route_node *node; + const struct prefix *p = pu.p; + struct route_node *node; - node = hash_get (table->hash, (void *)p, NULL); - return node ? route_lock_node (node) : NULL; + node = hash_get(table->hash, (void *)p, NULL); + return node ? route_lock_node(node) : NULL; } /* Add node to routing table. */ -struct route_node * -route_node_get (struct route_table *const table, union prefixconstptr pu) -{ - const struct prefix *p = pu.p; - struct route_node *new; - struct route_node *node; - struct route_node *match; - struct route_node *inserted; - u_char prefixlen = p->prefixlen; - const u_char *prefix = &p->u.prefix; - - node = hash_get (table->hash, (void *)p, NULL); - if (node && node->info) - return route_lock_node (node); - - match = NULL; - node = table->top; - while (node && node->p.prefixlen <= prefixlen && - prefix_match (&node->p, p)) - { - if (node->p.prefixlen == prefixlen) - return route_lock_node (node); - - match = node; - node = node->link[prefix_bit(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 (table); - route_common (&node->p, p, &new->p); - new->p.family = p->family; - new->table = table; - set_link (new, node); - inserted = hash_get (node->table->hash, new, hash_alloc_intern); - assert (inserted == new); - - 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); - table->count++; +struct route_node *route_node_get(struct route_table *const table, + union prefixconstptr pu) +{ + const struct prefix *p = pu.p; + struct route_node *new; + struct route_node *node; + struct route_node *match; + struct route_node *inserted; + u_char prefixlen = p->prefixlen; + const u_char *prefix = &p->u.prefix; + + node = hash_get(table->hash, (void *)p, NULL); + if (node && node->info) + return route_lock_node(node); + + match = NULL; + node = table->top; + while (node && node->p.prefixlen <= prefixlen + && prefix_match(&node->p, p)) { + if (node->p.prefixlen == prefixlen) + return route_lock_node(node); + + match = node; + node = node->link[prefix_bit(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(table); + route_common(&node->p, p, &new->p); + new->p.family = p->family; + new->table = table; + set_link(new, node); + inserted = hash_get(node->table->hash, new, hash_alloc_intern); + assert(inserted == new); + + 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); + table->count++; + } } - } - table->count++; - route_lock_node (new); - - return new; + table->count++; + route_lock_node(new); + + return new; } /* Delete node from the routing table. */ -static void -route_node_delete (struct route_node *node) +static void route_node_delete(struct route_node *node) { - struct route_node *child; - struct route_node *parent; + struct route_node *child; + struct route_node *parent; - assert (node->lock == 0); - assert (node->info == NULL); + assert(node->lock == 0); + assert(node->info == NULL); - if (node->l_left && node->l_right) - return; + if (node->l_left && node->l_right) + return; - if (node->l_left) - child = node->l_left; - else - child = node->l_right; + if (node->l_left) + child = node->l_left; + else + child = node->l_right; - parent = node->parent; + parent = node->parent; - if (child) - child->parent = 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; + if (parent) { + if (parent->l_left == node) + parent->l_left = child; + else + parent->l_right = child; + } else + node->table->top = child; - node->table->count--; + node->table->count--; - hash_release (node->table->hash, node); + hash_release(node->table->hash, node); - /* WARNING: FRAGILE CODE! - * route_node_free may have the side effect of free'ing the entire table. - * this is permitted only if table->count got decremented to zero above, - * because in that case parent will also be NULL, so that we won't try to - * delete a now-stale parent below. - * - * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */ + /* WARNING: FRAGILE CODE! + * route_node_free may have the side effect of free'ing the entire + * table. + * this is permitted only if table->count got decremented to zero above, + * because in that case parent will also be NULL, so that we won't try + * to + * delete a now-stale parent below. + * + * cf. srcdest_srcnode_destroy() in zebra/zebra_rib.c */ - route_node_free (node->table, node); + route_node_free(node->table, node); - /* If parent node is stub then delete it also. */ - if (parent && parent->lock == 0) - route_node_delete (parent); + /* 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) +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; + /* 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; + /* 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; +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; } - node = node->parent; - } - route_unlock_node (start); - return NULL; + 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, const 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; +struct route_node *route_next_until(struct route_node *node, + const 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; } - node = node->parent; - } - route_unlock_node (start); - return NULL; + route_unlock_node(start); + return NULL; } -unsigned long -route_table_count (const struct route_table *table) +unsigned long route_table_count(const struct route_table *table) { - return table->count; + return table->count; } /** @@ -540,13 +502,12 @@ route_table_count (const struct route_table *table) * * Default function for creating a route node. */ -struct route_node * -route_node_create (route_table_delegate_t *delegate, - struct route_table *table) +struct route_node *route_node_create(route_table_delegate_t *delegate, + struct route_table *table) { - struct route_node *node; - node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node)); - return node; + struct route_node *node; + node = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct route_node)); + return node; } /** @@ -554,34 +515,30 @@ route_node_create (route_table_delegate_t *delegate, * * Default function for destroying a route node. */ -void -route_node_destroy (route_table_delegate_t *delegate, - struct route_table *table, struct route_node *node) +void route_node_destroy(route_table_delegate_t *delegate, + struct route_table *table, struct route_node *node) { - XFREE (MTYPE_ROUTE_NODE, node); + XFREE(MTYPE_ROUTE_NODE, node); } /* * Default delegate. */ static route_table_delegate_t default_delegate = { - .create_node = route_node_create, - .destroy_node = route_node_destroy -}; + .create_node = route_node_create, + .destroy_node = route_node_destroy}; -route_table_delegate_t * -route_table_get_default_delegate(void) +route_table_delegate_t *route_table_get_default_delegate(void) { - return &default_delegate; + return &default_delegate; } /* * route_table_init */ -struct route_table * -route_table_init (void) +struct route_table *route_table_init(void) { - return route_table_init_with_delegate (&default_delegate); + return route_table_init_with_delegate(&default_delegate); } /** @@ -589,63 +546,58 @@ route_table_init (void) * * Compare two prefixes according to the order in which they appear in * an iteration over a tree. - * + * * @return -1 if p1 occurs before p2 (p1 < p2) * 0 if the prefixes are identical (p1 == p2) * +1 if p1 occurs after p2 (p1 > p2) */ -int -route_table_prefix_iter_cmp (const struct prefix *p1, const struct prefix *p2) -{ - struct prefix common_space; - struct prefix *common = &common_space; - - if (p1->prefixlen <= p2->prefixlen) - { - if (prefix_match (p1, p2)) - { +int route_table_prefix_iter_cmp(const struct prefix *p1, + const struct prefix *p2) +{ + struct prefix common_space; + struct prefix *common = &common_space; + + if (p1->prefixlen <= p2->prefixlen) { + if (prefix_match(p1, p2)) { + + /* + * p1 contains p2, or is equal to it. + */ + return (p1->prefixlen == p2->prefixlen) ? 0 : -1; + } + } else { + + /* + * Check if p2 contains p1. + */ + if (prefix_match(p2, p1)) + return 1; + } - /* - * p1 contains p2, or is equal to it. - */ - return (p1->prefixlen == p2->prefixlen) ? 0 : -1; + route_common(p1, p2, common); + assert(common->prefixlen < p1->prefixlen); + assert(common->prefixlen < p2->prefixlen); + + /* + * Both prefixes are longer than the common prefix. + * + * We need to check the bit after the common prefixlen to determine + * which one comes later. + */ + if (prefix_bit(&p1->u.prefix, common->prefixlen)) { + + /* + * We branch to the right to get to p1 from the common prefix. + */ + assert(!prefix_bit(&p2->u.prefix, common->prefixlen)); + return 1; } - } - else - { - - /* - * Check if p2 contains p1. - */ - if (prefix_match (p2, p1)) - return 1; - } - - route_common (p1, p2, common); - assert (common->prefixlen < p1->prefixlen); - assert (common->prefixlen < p2->prefixlen); - - /* - * Both prefixes are longer than the common prefix. - * - * We need to check the bit after the common prefixlen to determine - * which one comes later. - */ - if (prefix_bit (&p1->u.prefix, common->prefixlen)) - { - - /* - * We branch to the right to get to p1 from the common prefix. - */ - assert (!prefix_bit (&p2->u.prefix, common->prefixlen)); - return 1; - } - - /* - * We branch to the right to get to p2 from the common prefix. - */ - assert (prefix_bit (&p2->u.prefix, common->prefixlen)); - return -1; + + /* + * We branch to the right to get to p2 from the common prefix. + */ + assert(prefix_bit(&p2->u.prefix, common->prefixlen)); + return -1; } /* @@ -654,18 +606,16 @@ route_table_prefix_iter_cmp (const struct prefix *p1, const struct prefix *p2) * Helper function that returns the first node that follows the nodes * in the sub-tree under 'node' in iteration order. */ -static struct route_node * -route_get_subtree_next (struct route_node *node) +static struct route_node *route_get_subtree_next(struct route_node *node) { - while (node->parent) - { - if (node->parent->l_left == node && node->parent->l_right) - return node->parent->l_right; + while (node->parent) { + if (node->parent->l_left == node && node->parent->l_right) + return node->parent->l_right; - node = node->parent; - } + node = node->parent; + } - return NULL; + return NULL; } /** @@ -677,99 +627,99 @@ route_get_subtree_next (struct route_node *node) * @see route_table_get_next */ static struct route_node * -route_table_get_next_internal (const struct route_table *table, - const struct prefix *p) -{ - struct route_node *node, *tmp_node; - int cmp; - - node = table->top; - - while (node) - { - int match; - - if (node->p.prefixlen < p->prefixlen) - match = prefix_match (&node->p, p); - else - match = prefix_match (p, &node->p); - - if (match) - { - if (node->p.prefixlen == p->prefixlen) - { - - /* - * The prefix p exists in the tree, just return the next - * node. - */ - route_lock_node (node); - node = route_next (node); - if (node) - route_unlock_node (node); - - return (node); - } - - if (node->p.prefixlen > p->prefixlen) - { - - /* - * Node is in the subtree of p, and hence greater than p. - */ - return node; - } - - /* - * p is in the sub-tree under node. - */ - tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)]; - - if (tmp_node) - { - node = tmp_node; - continue; - } - - /* - * There are no nodes in the direction where p should be. If - * node has a right child, then it must be greater than p. - */ - if (node->l_right) - return node->l_right; - - /* - * No more children to follow, go upwards looking for the next - * node. - */ - return route_get_subtree_next (node); - } - - /* - * Neither node prefix nor 'p' contains the other. - */ - cmp = route_table_prefix_iter_cmp (&node->p, p); - if (cmp > 0) - { - - /* - * Node follows p in iteration order. Return it. - */ - return node; +route_table_get_next_internal(const struct route_table *table, + const struct prefix *p) +{ + struct route_node *node, *tmp_node; + int cmp; + + node = table->top; + + while (node) { + int match; + + if (node->p.prefixlen < p->prefixlen) + match = prefix_match(&node->p, p); + else + match = prefix_match(p, &node->p); + + if (match) { + if (node->p.prefixlen == p->prefixlen) { + + /* + * The prefix p exists in the tree, just return + * the next + * node. + */ + route_lock_node(node); + node = route_next(node); + if (node) + route_unlock_node(node); + + return (node); + } + + if (node->p.prefixlen > p->prefixlen) { + + /* + * Node is in the subtree of p, and hence + * greater than p. + */ + return node; + } + + /* + * p is in the sub-tree under node. + */ + tmp_node = node->link[prefix_bit(&p->u.prefix, + node->p.prefixlen)]; + + if (tmp_node) { + node = tmp_node; + continue; + } + + /* + * There are no nodes in the direction where p should + * be. If + * node has a right child, then it must be greater than + * p. + */ + if (node->l_right) + return node->l_right; + + /* + * No more children to follow, go upwards looking for + * the next + * node. + */ + return route_get_subtree_next(node); + } + + /* + * Neither node prefix nor 'p' contains the other. + */ + cmp = route_table_prefix_iter_cmp(&node->p, p); + if (cmp > 0) { + + /* + * Node follows p in iteration order. Return it. + */ + return node; + } + + assert(cmp < 0); + + /* + * Node and the subtree under it come before prefix p in + * iteration order. Prefix p and its sub-tree are not present in + * the tree. Go upwards and find the first node that follows the + * subtree. That node will also succeed p. + */ + return route_get_subtree_next(node); } - assert (cmp < 0); - - /* - * Node and the subtree under it come before prefix p in - * iteration order. Prefix p and its sub-tree are not present in - * the tree. Go upwards and find the first node that follows the - * subtree. That node will also succeed p. - */ - return route_get_subtree_next (node); - } - - return NULL; + return NULL; } /** @@ -778,30 +728,28 @@ route_table_get_next_internal (const struct route_table *table, * Find the node that occurs after the given prefix in order of * iteration. */ -struct route_node * -route_table_get_next (const struct route_table *table, union prefixconstptr pu) +struct route_node *route_table_get_next(const struct route_table *table, + union prefixconstptr pu) { - const struct prefix *p = pu.p; - struct route_node *node; + const struct prefix *p = pu.p; + struct route_node *node; - node = route_table_get_next_internal (table, p); - if (node) - { - assert (route_table_prefix_iter_cmp (&node->p, p) > 0); - route_lock_node (node); - } - return node; + node = route_table_get_next_internal(table, p); + if (node) { + assert(route_table_prefix_iter_cmp(&node->p, p) > 0); + route_lock_node(node); + } + return node; } /* * route_table_iter_init */ -void -route_table_iter_init (route_table_iter_t * iter, struct route_table *table) +void route_table_iter_init(route_table_iter_t *iter, struct route_table *table) { - memset (iter, 0, sizeof (*iter)); - iter->state = RT_ITER_STATE_INIT; - iter->table = table; + memset(iter, 0, sizeof(*iter)); + iter->state = RT_ITER_STATE_INIT; + iter->table = table; } /* @@ -812,34 +760,32 @@ route_table_iter_init (route_table_iter_t * iter, struct route_table *table) * An iteration can be resumed by just calling route_table_iter_next() * on the iterator. */ -void -route_table_iter_pause (route_table_iter_t * iter) -{ - switch (iter->state) - { - - case RT_ITER_STATE_INIT: - case RT_ITER_STATE_PAUSED: - case RT_ITER_STATE_DONE: - return; - - case RT_ITER_STATE_ITERATING: - - /* - * Save the prefix that we are currently at. The next call to - * route_table_iter_next() will return the node after this prefix - * in the tree. - */ - prefix_copy (&iter->pause_prefix, &iter->current->p); - route_unlock_node (iter->current); - iter->current = NULL; - iter->state = RT_ITER_STATE_PAUSED; - return; - - default: - assert (0); - } - +void route_table_iter_pause(route_table_iter_t *iter) +{ + switch (iter->state) { + + case RT_ITER_STATE_INIT: + case RT_ITER_STATE_PAUSED: + case RT_ITER_STATE_DONE: + return; + + case RT_ITER_STATE_ITERATING: + + /* + * Save the prefix that we are currently at. The next call to + * route_table_iter_next() will return the node after this + * prefix + * in the tree. + */ + prefix_copy(&iter->pause_prefix, &iter->current->p); + route_unlock_node(iter->current); + iter->current = NULL; + iter->state = RT_ITER_STATE_PAUSED; + return; + + default: + assert(0); + } } /* @@ -847,19 +793,17 @@ route_table_iter_pause (route_table_iter_t * iter) * * Release any resources held by the iterator. */ -void -route_table_iter_cleanup (route_table_iter_t * iter) -{ - if (iter->state == RT_ITER_STATE_ITERATING) - { - route_unlock_node (iter->current); - iter->current = NULL; - } - assert (!iter->current); - - /* - * Set the state to RT_ITER_STATE_DONE to make any - * route_table_iter_next() calls on this iterator return NULL. - */ - iter->state = RT_ITER_STATE_DONE; +void route_table_iter_cleanup(route_table_iter_t *iter) +{ + if (iter->state == RT_ITER_STATE_ITERATING) { + route_unlock_node(iter->current); + iter->current = NULL; + } + assert(!iter->current); + + /* + * Set the state to RT_ITER_STATE_DONE to make any + * route_table_iter_next() calls on this iterator return NULL. + */ + iter->state = RT_ITER_STATE_DONE; } |