diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-14 20:39:28 +0100 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-01-04 01:07:13 +0100 |
| commit | 057d48bd58776c31db20ec8cf3044cb1d20140d5 (patch) | |
| tree | fff0a4472f2e1b59b52408f43dc0e97e57897976 /ldpd/ldpd.h | |
| parent | ldpd: use red-black trees to store 'l2vpn_pw' elements (diff) | |
| download | frr-057d48bd58776c31db20ec8cf3044cb1d20140d5.tar.xz frr-057d48bd58776c31db20ec8cf3044cb1d20140d5.zip | |
ldpd: use red-black trees to store 'adj' elements
Using red-black trees instead of linked lists brings the following
benefits:
1 - Elements are naturally ordered (no need to reorder anything before
outputting data to the user);
2 - Faster lookups/deletes: O(log n) time complexity against O(n).
The insert operation with red-black trees is more expensive though,
but that's not a big issue since lookups are much more frequent.
Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
Diffstat (limited to 'ldpd/ldpd.h')
| -rw-r--r-- | ldpd/ldpd.h | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 6836920bc..4d575597a 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -196,7 +196,10 @@ enum nbr_action { NBR_ACT_CLOSE_SESSION }; -TAILQ_HEAD(mapping_head, mapping_entry); +/* forward declarations */ +RB_HEAD(global_adj_head, adj); +RB_HEAD(nbr_adj_head, adj); +RB_HEAD(ia_adj_head, adj); struct map { uint8_t type; @@ -256,7 +259,7 @@ struct iface_af { int af; int enabled; int state; - LIST_HEAD(, adj) adj_list; + struct ia_adj_head adj_tree; time_t uptime; struct thread *hello_timer; uint16_t hello_holdtime; @@ -450,7 +453,7 @@ struct ldpd_global { uint32_t conf_seqnum; int pfkeysock; struct if_addr_head addr_list; - LIST_HEAD(, adj) adj_list; + struct global_adj_head adj_tree; struct in_addr mcast_addr_v4; struct in6_addr mcast_addr_v6; TAILQ_HEAD(, pending_conn) pending_conns; |