2 * Copyright (C) 1998, 2001 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 #include "sockunion.h"
30 #include "bgpd/bgpd.h"
31 #include "bgpd/bgp_table.h"
32 #include "bgp_addpath.h"
34 void bgp_table_lock(struct bgp_table
*rt
)
39 void bgp_table_unlock(struct bgp_table
*rt
)
48 route_table_finish(rt
->route_table
);
49 rt
->route_table
= NULL
;
51 XFREE(MTYPE_BGP_TABLE
, rt
);
54 void bgp_table_finish(struct bgp_table
**rt
)
57 bgp_table_unlock(*rt
);
65 static struct route_node
*bgp_node_create(route_table_delegate_t
*delegate
,
66 struct route_table
*table
)
68 struct bgp_node
*node
;
69 node
= XCALLOC(MTYPE_BGP_NODE
, sizeof(struct bgp_node
));
70 return bgp_node_to_rnode(node
);
76 static void bgp_node_destroy(route_table_delegate_t
*delegate
,
77 struct route_table
*table
, struct route_node
*node
)
79 struct bgp_node
*bgp_node
;
81 bgp_node
= bgp_node_from_rnode(node
);
85 bgp_addpath_free_node_data(&rt
->bgp
->tx_addpath
,
86 &bgp_node
->tx_addpath
,
90 XFREE(MTYPE_BGP_NODE
, bgp_node
);
94 * Function vector to customize the behavior of the route table
95 * library for BGP route tables.
97 route_table_delegate_t bgp_table_delegate
= {.create_node
= bgp_node_create
,
98 .destroy_node
= bgp_node_destroy
};
103 struct bgp_table
*bgp_table_init(struct bgp
*bgp
, afi_t afi
, safi_t safi
)
105 struct bgp_table
*rt
;
107 rt
= XCALLOC(MTYPE_BGP_TABLE
, sizeof(struct bgp_table
));
109 rt
->route_table
= route_table_init_with_delegate(&bgp_table_delegate
);
112 * Set up back pointer to bgp_table.
114 route_table_set_info(rt
->route_table
, rt
);
117 * pointer to bgp instance allows working back from bgp_path_info to bgp
128 static struct bgp_node
*
129 bgp_route_next_until_maxlen(struct bgp_node
*node
, const struct bgp_node
*limit
,
130 const uint8_t maxlen
)
132 if (node
->l_left
&& node
->p
.prefixlen
< maxlen
133 && node
->l_left
->p
.prefixlen
<= maxlen
) {
134 return bgp_node_from_rnode(node
->l_left
);
136 if (node
->l_right
&& node
->p
.prefixlen
< maxlen
137 && node
->l_right
->p
.prefixlen
<= maxlen
) {
138 return bgp_node_from_rnode(node
->l_right
);
141 while (node
->parent
&& node
!= limit
) {
142 if (bgp_node_from_rnode(node
->parent
->l_left
) == node
143 && node
->parent
->l_right
) {
144 return bgp_node_from_rnode(node
->parent
->l_right
);
146 node
= bgp_node_from_rnode(node
->parent
);
151 void bgp_table_range_lookup(const struct bgp_table
*table
, struct prefix
*p
,
152 uint8_t maxlen
, struct list
*matches
)
154 struct bgp_node
*node
= bgp_node_from_rnode(table
->route_table
->top
);
155 struct bgp_node
*matched
= NULL
;
157 while (node
&& node
->p
.prefixlen
<= p
->prefixlen
158 && prefix_match(&node
->p
, p
)) {
159 if (node
->info
&& node
->p
.prefixlen
== p
->prefixlen
) {
163 node
= bgp_node_from_rnode(node
->link
[prefix_bit(
164 &p
->u
.prefix
, node
->p
.prefixlen
)]);
170 if ((matched
== NULL
&& node
->p
.prefixlen
> maxlen
) || !node
->parent
)
172 else if (matched
== NULL
)
173 matched
= node
= bgp_node_from_rnode(node
->parent
);
176 bgp_lock_node(matched
);
177 listnode_add(matches
, matched
);
180 while ((node
= bgp_route_next_until_maxlen(node
, matched
, maxlen
))) {
181 if (prefix_match(p
, &node
->p
)) {
184 listnode_add(matches
, node
);