#include "bgpd/bgpd.h"
#include "bgpd/bgp_table.h"
-void
-bgp_table_lock (struct bgp_table *rt)
+void bgp_table_lock(struct bgp_table *rt)
{
- rt->lock++;
+ rt->lock++;
}
-void
-bgp_table_unlock (struct bgp_table *rt)
+void bgp_table_unlock(struct bgp_table *rt)
{
- assert (rt->lock > 0);
- rt->lock--;
+ assert(rt->lock > 0);
+ rt->lock--;
- if (rt->lock != 0)
- {
- return;
- }
+ if (rt->lock != 0) {
+ return;
+ }
- route_table_finish (rt->route_table);
- rt->route_table = NULL;
+ route_table_finish(rt->route_table);
+ rt->route_table = NULL;
- if (rt->owner)
- {
- peer_unlock (rt->owner);
- rt->owner = NULL;
- }
-
- XFREE (MTYPE_BGP_TABLE, rt);
+ XFREE(MTYPE_BGP_TABLE, rt);
}
-void
-bgp_table_finish (struct bgp_table **rt)
+void bgp_table_finish(struct bgp_table **rt)
{
- if (*rt != NULL)
- {
- bgp_table_unlock(*rt);
- *rt = NULL;
- }
+ if (*rt != NULL) {
+ bgp_table_unlock(*rt);
+ *rt = NULL;
+ }
}
/*
* bgp_node_create
*/
-static struct route_node *
-bgp_node_create (route_table_delegate_t *delegate, struct route_table *table)
+static struct route_node *bgp_node_create(route_table_delegate_t *delegate,
+ struct route_table *table)
{
- struct bgp_node *node;
- node = XCALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node));
- return bgp_node_to_rnode (node);
+ struct bgp_node *node;
+ node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node));
+ return bgp_node_to_rnode(node);
}
/*
* bgp_node_destroy
*/
-static void
-bgp_node_destroy (route_table_delegate_t *delegate,
- struct route_table *table, struct route_node *node)
+static void bgp_node_destroy(route_table_delegate_t *delegate,
+ struct route_table *table, struct route_node *node)
{
- struct bgp_node *bgp_node;
- bgp_node = bgp_node_from_rnode (node);
- XFREE (MTYPE_BGP_NODE, bgp_node);
+ struct bgp_node *bgp_node;
+ bgp_node = bgp_node_from_rnode(node);
+ XFREE(MTYPE_BGP_NODE, bgp_node);
}
/*
* Function vector to customize the behavior of the route table
* library for BGP route tables.
*/
-route_table_delegate_t bgp_table_delegate = {
- .create_node = bgp_node_create,
- .destroy_node = bgp_node_destroy
-};
+route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create,
+ .destroy_node = bgp_node_destroy};
/*
* bgp_table_init
*/
-struct bgp_table *
-bgp_table_init (afi_t afi, safi_t safi)
+struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi)
{
- struct bgp_table *rt;
+ struct bgp_table *rt;
+
+ rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table));
+
+ rt->route_table = route_table_init_with_delegate(&bgp_table_delegate);
+
+ /*
+ * Set up back pointer to bgp_table.
+ */
+ rt->route_table->info = rt;
- rt = XCALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table));
+ /*
+ * pointer to bgp instance allows working back from bgp_info to bgp
+ */
+ rt->bgp = bgp;
- rt->route_table = route_table_init_with_delegate (&bgp_table_delegate);
+ bgp_table_lock(rt);
+ rt->afi = afi;
+ rt->safi = safi;
- /*
- * Set up back pointer to bgp_table.
- */
- rt->route_table->info = rt;
+ return rt;
+}
- bgp_table_lock (rt);
- rt->afi = afi;
- rt->safi = safi;
+static struct bgp_node *
+bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit,
+ const uint8_t maxlen)
+{
+ if (node->l_left && node->p.prefixlen < maxlen
+ && node->l_left->p.prefixlen <= maxlen) {
+ return bgp_node_from_rnode(node->l_left);
+ }
+ if (node->l_right && node->p.prefixlen < maxlen
+ && node->l_right->p.prefixlen <= maxlen) {
+ return bgp_node_from_rnode(node->l_right);
+ }
+
+ while (node->parent && node != limit) {
+ if (bgp_node_from_rnode(node->parent->l_left) == node
+ && node->parent->l_right) {
+ return bgp_node_from_rnode(node->parent->l_right);
+ }
+ node = bgp_node_from_rnode(node->parent);
+ }
+ return NULL;
+}
- return rt;
+void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p,
+ uint8_t maxlen, struct list *matches)
+{
+ struct bgp_node *node = bgp_node_from_rnode(table->route_table->top);
+ struct bgp_node *matched = NULL;
+
+ while (node && node->p.prefixlen <= p->prefixlen
+ && prefix_match(&node->p, p)) {
+ if (node->info && node->p.prefixlen == p->prefixlen) {
+ matched = node;
+ break;
+ }
+ node = bgp_node_from_rnode(node->link[prefix_bit(
+ &p->u.prefix, node->p.prefixlen)]);
+ }
+
+ if (node == NULL)
+ return;
+
+ if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent)
+ return;
+ else if (matched == NULL)
+ matched = node = bgp_node_from_rnode(node->parent);
+
+ if (matched->info) {
+ bgp_lock_node(matched);
+ listnode_add(matches, matched);
+ }
+
+ while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) {
+ if (prefix_match(p, &node->p)) {
+ if (node->info) {
+ bgp_lock_node(node);
+ listnode_add(matches, node);
+ }
+ }
+ }
}