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/ldp_vty_conf.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/ldp_vty_conf.c')
| -rw-r--r-- | ldpd/ldp_vty_conf.c | 22 |
1 files changed, 11 insertions, 11 deletions
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index b97964228..e408abb09 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -358,9 +358,9 @@ ldp_l2vpn_config_write(struct vty *vty) vty_out(vty, " member interface %s%s", lif->ifname, VTY_NEWLINE); - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) ldp_l2vpn_pw_config_write(vty, pw); - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) ldp_l2vpn_pw_config_write(vty, pw); vty_out(vty, " !%s", VTY_NEWLINE); @@ -1425,7 +1425,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) if (pw == NULL) goto cancel; - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1451,7 +1451,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) pw = l2vpn_pw_new(l2vpn, &kif); pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF; - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); ldp_reload_ref(vty_conf, (void **)&pw); VTY_PUSH_CONTEXT_SUB(LDP_PSEUDOWIRE_NODE, pw); @@ -1720,12 +1720,12 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = LIST_FIRST(&l2vpn->pw_inactive_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); @@ -1784,13 +1784,13 @@ l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, pw = l2vpn_pw_new(l2vpn, &kif); pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF; - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); return (pw); } void -l2vpn_pw_del_api(struct l2vpn_pw *pw) +l2vpn_pw_del_api(struct l2vpn *l2vpn, struct l2vpn_pw *pw) { - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } |