#include "bgpd/bgpd.h"
#include "bgpd/bgp_table.h"
+#include "bgp_addpath.h"
void bgp_table_lock(struct bgp_table *rt)
{
{
struct bgp_node *node;
node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node));
+
+ RB_INIT(bgp_adj_out_rb, &node->adj_out);
return bgp_node_to_rnode(node);
}
struct route_table *table, struct route_node *node)
{
struct bgp_node *bgp_node;
+ struct bgp_table *rt;
bgp_node = bgp_node_from_rnode(node);
+ rt = table->info;
+
+ if (rt->bgp) {
+ bgp_addpath_free_node_data(&rt->bgp->tx_addpath,
+ &bgp_node->tx_addpath,
+ rt->afi, rt->safi);
+ }
+
XFREE(MTYPE_BGP_NODE, bgp_node);
}
/*
* Set up back pointer to bgp_table.
*/
- rt->route_table->info = rt;
+ route_table_set_info(rt->route_table, rt);
/*
- * pointer to bgp instance allows working back from bgp_info to bgp
+ * pointer to bgp instance allows working back from bgp_path_info to bgp
*/
rt->bgp = bgp;
return rt;
}
+
+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;
+}
+
+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 (bgp_node_has_bgp_path_info_data(node)
+ && 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 (bgp_node_has_bgp_path_info_data(matched)) {
+ 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 (bgp_node_has_bgp_path_info_data(node)) {
+ bgp_lock_node(node);
+ listnode_add(matches, node);
+ }
+ }
+ }
+}