diff options
| author | Donald Sharp <sharpd@cumulusnetworks.com> | 2018-12-07 09:01:59 -0500 |
|---|---|---|
| committer | Donald Sharp <sharpd@cumulusnetworks.com> | 2018-12-07 10:26:00 -0500 |
| commit | a79c04e7fe6f1d0f0d6b1ad0534a47dc8fb83943 (patch) | |
| tree | 60281d0b3ea6d833f480fc6006917d0405cf6944 /bgpd/bgp_advertise.h | |
| parent | 60e2b4f56695fba680493cfbb61fd8d4d5b6fdf7 (diff) | |
bgpd: Convert adj_out to a RB tree
The adj_out data structure is a linked list of adjacencies
1 per update group. In a large scale env where we are
not using peer groups, this list lookup starts to become
rather costly. Convert to a better data structure for this.
Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
Diffstat (limited to 'bgpd/bgp_advertise.h')
| -rw-r--r-- | bgpd/bgp_advertise.h | 11 |
1 files changed, 6 insertions, 5 deletions
diff --git a/bgpd/bgp_advertise.h b/bgpd/bgp_advertise.h index 1912aec1bf..9aa5a0eaff 100644 --- a/bgpd/bgp_advertise.h +++ b/bgpd/bgp_advertise.h @@ -67,9 +67,8 @@ struct bgp_advertise { /* BGP adjacency out. */ struct bgp_adj_out { - /* Lined list pointer. */ - struct bgp_adj_out *next; - struct bgp_adj_out *prev; + /* RB Tree of adjacency entries */ + RB_ENTRY(bgp_adj_out) adj_entry; /* Advertised subgroup. */ struct update_subgroup *subgroup; @@ -89,6 +88,10 @@ struct bgp_adj_out { struct bgp_advertise *adv; }; +RB_HEAD(bgp_adj_out_rb, bgp_adj_out); +RB_PROTOTYPE(bgp_adj_out_rb, bgp_adj_out, adj_entry, + bgp_adj_out_compare); + /* BGP adjacency in. */ struct bgp_adj_in { /* Linked list pointer. */ @@ -134,8 +137,6 @@ struct bgp_synchronize { #define BGP_ADJ_IN_ADD(N, A) BGP_PATH_INFO_ADD(N, A, adj_in) #define BGP_ADJ_IN_DEL(N, A) BGP_PATH_INFO_DEL(N, A, adj_in) -#define BGP_ADJ_OUT_ADD(N, A) BGP_PATH_INFO_ADD(N, A, adj_out) -#define BGP_ADJ_OUT_DEL(N, A) BGP_PATH_INFO_DEL(N, A, adj_out) #define BGP_ADV_FIFO_ADD(F, N) \ do { \ |