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> --- ldpd/l2vpn.c | 4 ++-- ldpd/lde.c | 17 ++++++++++++++--- ldpd/lde.h | 9 ++++++--- ldpd/lde_lib.c | 18 +++++++++--------- 4 files changed, 31 insertions(+), 17 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index 851ff77..c0f6586 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -459,7 +459,7 @@ l2vpn_binding_ctl(pid_t pid) fn = (struct fec_node *)f; if (fn->local_label == NO_LABEL && - LIST_EMPTY(&fn->downstream)) + RB_EMPTY(&fn->downstream)) continue; memset(&pwctl, 0, sizeof(pwctl)); @@ -477,7 +477,7 @@ l2vpn_binding_ctl(pid_t pid) } else pwctl.local_label = NO_LABEL; - LIST_FOREACH(me, &fn->downstream, entry) + RB_FOREACH(me, lde_map_head, &fn->downstream) if (f->u.pwid.lsr_id.s_addr == me->nexthop->id.s_addr) break; diff --git a/ldpd/lde.c b/ldpd/lde.c index 67ed982..a1309c6 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -45,12 +45,14 @@ static struct lde_nbr *lde_nbr_find(uint32_t); static void lde_nbr_clear(void); static void lde_nbr_addr_update(struct lde_nbr *, struct lde_addr *, int); +static __inline int lde_map_compare(struct lde_map *, struct lde_map *); static void lde_map_free(void *); static int lde_address_add(struct lde_nbr *, struct lde_addr *); static int lde_address_del(struct lde_nbr *, struct lde_addr *); static void lde_address_list_free(struct lde_nbr *); RB_GENERATE(nbr_tree, lde_nbr, entry, lde_nbr_compare) +RB_GENERATE(lde_map_head, lde_map, entry, lde_map_compare) struct ldpd_conf *ldeconf; struct nbr_tree lde_nbrs = RB_INITIALIZER(&lde_nbrs); @@ -1141,6 +1143,13 @@ lde_nbr_addr_update(struct lde_nbr *ln, struct lde_addr *lde_addr, int removed) } } +static __inline int +lde_map_compare(struct lde_map *a, struct lde_map *b) +{ + return (ldp_addrcmp(AF_INET, (union ldpd_addr *)&a->nexthop->id, + (union ldpd_addr *)&b->nexthop->id)); +} + struct lde_map * lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent) { @@ -1154,13 +1163,15 @@ lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent) me->nexthop = ln; if (sent) { - LIST_INSERT_HEAD(&fn->upstream, me, entry); + RB_INSERT(lde_map_head, &fn->upstream, me); + me->head = &fn->upstream; if (fec_insert(&ln->sent_map, &me->fec)) log_warnx("failed to add %s to sent map", log_fec(&me->fec)); /* XXX on failure more cleanup is needed */ } else { - LIST_INSERT_HEAD(&fn->downstream, me, entry); + RB_INSERT(lde_map_head, &fn->downstream, me); + me->head = &fn->downstream; if (fec_insert(&ln->recv_map, &me->fec)) log_warnx("failed to add %s to recv map", log_fec(&me->fec)); @@ -1185,7 +1196,7 @@ lde_map_free(void *ptr) { struct lde_map *map = ptr; - LIST_REMOVE(map, entry); + RB_REMOVE(lde_map_head, map->head, map); free(map); } diff --git a/ldpd/lde.h b/ldpd/lde.h index 5f5d37d..fe90b2c 100644 --- a/ldpd/lde.h +++ b/ldpd/lde.h @@ -62,10 +62,13 @@ struct lde_req { /* mapping entries */ struct lde_map { struct fec fec; - LIST_ENTRY(lde_map) entry; + struct lde_map_head *head; /* fec_node's upstream/downstream */ + RB_ENTRY(lde_map) entry; struct lde_nbr *nexthop; struct map map; }; +RB_HEAD(lde_map_head, lde_map); +RB_PROTOTYPE(lde_map_head, lde_map, entry, lde_map_cmp); /* withdraw entries */ struct lde_wdraw { @@ -112,8 +115,8 @@ struct fec_node { struct fec fec; LIST_HEAD(, fec_nh) nexthops; /* fib nexthops */ - LIST_HEAD(, lde_map) downstream; /* recv mappings */ - LIST_HEAD(, lde_map) upstream; /* sent mappings */ + struct lde_map_head downstream; /* recv mappings */ + struct lde_map_head upstream; /* sent mappings */ uint32_t local_label; void *data; /* fec specific data */ diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c index 14ac592..df65eda 100644 --- a/ldpd/lde_lib.c +++ b/ldpd/lde_lib.c @@ -159,7 +159,7 @@ rt_dump(pid_t pid) RB_FOREACH(f, fec_tree, &ft) { fn = (struct fec_node *)f; if (fn->local_label == NO_LABEL && - LIST_EMPTY(&fn->downstream)) + RB_EMPTY(&fn->downstream)) continue; rtctl.first = 1; @@ -179,7 +179,7 @@ rt_dump(pid_t pid) } rtctl.local_label = fn->local_label; - LIST_FOREACH(me, &fn->downstream, entry) { + RB_FOREACH(me, lde_map_head, &fn->downstream) { rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop); rtctl.nexthop = me->nexthop->id; rtctl.remote_label = me->map.label; @@ -188,7 +188,7 @@ rt_dump(pid_t pid) &rtctl, sizeof(rtctl)); rtctl.first = 0; } - if (LIST_EMPTY(&fn->downstream)) { + if (RB_EMPTY(&fn->downstream)) { rtctl.in_use = 0; rtctl.nexthop.s_addr = INADDR_ANY; rtctl.remote_label = NO_LABEL; @@ -224,10 +224,10 @@ fec_free(void *arg) while ((fnh = LIST_FIRST(&fn->nexthops))) fec_nh_del(fnh); - if (!LIST_EMPTY(&fn->downstream)) + if (!RB_EMPTY(&fn->downstream)) log_warnx("%s: fec %s downstream list not empty", __func__, log_fec(&fn->fec)); - if (!LIST_EMPTY(&fn->upstream)) + if (!RB_EMPTY(&fn->upstream)) log_warnx("%s: fec %s upstream list not empty", __func__, log_fec(&fn->fec)); @@ -251,8 +251,8 @@ fec_add(struct fec *fec) fn->fec = *fec; fn->local_label = NO_LABEL; - LIST_INIT(&fn->upstream); - LIST_INIT(&fn->downstream); + RB_INIT(&fn->upstream); + RB_INIT(&fn->downstream); LIST_INIT(&fn->nexthops); if (fec_insert(&ft, &fn->fec)) @@ -774,8 +774,8 @@ lde_gc_timer(struct thread *thread) fn = (struct fec_node *) fec; if (!LIST_EMPTY(&fn->nexthops) || - !LIST_EMPTY(&fn->downstream) || - !LIST_EMPTY(&fn->upstream)) + !RB_EMPTY(&fn->downstream) || + !RB_EMPTY(&fn->upstream)) continue; fec_remove(&ft, &fn->fec); -- 1.9.1