diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-14 16:53:07 +0100 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-01-04 01:07:13 +0100 |
| commit | 20bacaeba2381b7b199166e006576606defbaf0f (patch) | |
| tree | 4d7750899bae7956d4283078420b4133a61a41be /ldpd/lde.c | |
| parent | ldpd: use red-black trees to store 'l2vpn_if' elements (diff) | |
| download | frr-20bacaeba2381b7b199166e006576606defbaf0f.tar.xz frr-20bacaeba2381b7b199166e006576606defbaf0f.zip | |
ldpd: use red-black trees to store 'l2vpn_pw' 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/lde.c')
| -rw-r--r-- | ldpd/lde.c | 8 |
1 files changed, 4 insertions, 4 deletions
diff --git a/ldpd/lde.c b/ldpd/lde.c index 522650cdc..aa83ef0ab 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -511,8 +511,8 @@ lde_dispatch_parent(struct thread *thread) memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); RB_INIT(&nl2vpn->if_tree); - LIST_INIT(&nl2vpn->pw_list); - LIST_INIT(&nl2vpn->pw_inactive_list); + RB_INIT(&nl2vpn->pw_tree); + RB_INIT(&nl2vpn->pw_inactive_tree); RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; @@ -530,7 +530,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_tree, npw); break; case IMSG_RECONF_L2VPN_IPW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) @@ -538,7 +538,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_inactive_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree, npw); break; case IMSG_RECONF_END: merge_config(ldeconf, nconf); |