diff options
-rw-r--r-- | ldpd/adjacency.c | 8 | ||||
-rw-r--r-- | ldpd/interface.c | 10 | ||||
-rw-r--r-- | ldpd/l2vpn.c | 27 | ||||
-rw-r--r-- | ldpd/lde.c | 27 | ||||
-rw-r--r-- | ldpd/lde_lib.c | 27 | ||||
-rw-r--r-- | ldpd/ldp_vty_conf.c | 7 | ||||
-rw-r--r-- | ldpd/ldpd.c | 36 | ||||
-rw-r--r-- | ldpd/ldpe.c | 22 | ||||
-rw-r--r-- | ldpd/neighbor.c | 22 | ||||
-rw-r--r-- | lib/Makefile.am | 2 | ||||
-rw-r--r-- | lib/ns.c | 6 | ||||
-rw-r--r-- | lib/openbsd-tree.c | 640 | ||||
-rw-r--r-- | lib/openbsd-tree.h | 646 | ||||
-rw-r--r-- | lib/vrf.c | 16 | ||||
-rw-r--r-- | zebra/zebra_rib.c | 2 |
15 files changed, 975 insertions, 523 deletions
diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c index 52e277665..8a2252e72 100644 --- a/ldpd/adjacency.c +++ b/ldpd/adjacency.c @@ -25,9 +25,9 @@ #include "ldpe.h" #include "log.h" -static __inline int adj_compare(struct adj *, struct adj *); +static __inline int adj_compare(const struct adj *, const struct adj *); static int adj_itimer(struct thread *); -static __inline int tnbr_compare(struct tnbr *, struct tnbr *); +static __inline int tnbr_compare(const struct tnbr *, const struct tnbr *); static void tnbr_del(struct ldpd_conf *, struct tnbr *); static void tnbr_start(struct tnbr *); static void tnbr_stop(struct tnbr *); @@ -41,7 +41,7 @@ RB_GENERATE(ia_adj_head, adj, ia_entry, adj_compare) RB_GENERATE(tnbr_head, tnbr, entry, tnbr_compare) static __inline int -adj_compare(struct adj *a, struct adj *b) +adj_compare(const struct adj *a, const struct adj *b) { if (adj_get_af(a) < adj_get_af(b)) return (-1); @@ -220,7 +220,7 @@ adj_stop_itimer(struct adj *adj) /* targeted neighbors */ static __inline int -tnbr_compare(struct tnbr *a, struct tnbr *b) +tnbr_compare(const struct tnbr *a, const struct tnbr *b) { if (a->af < b->af) return (-1); diff --git a/ldpd/interface.c b/ldpd/interface.c index a064a58b2..527a6bc96 100644 --- a/ldpd/interface.c +++ b/ldpd/interface.c @@ -26,7 +26,7 @@ #include "sockopt.h" -static __inline int iface_compare(struct iface *, struct iface *); +static __inline int iface_compare(const struct iface *, const struct iface *); static struct if_addr *if_addr_new(struct kaddr *); static struct if_addr *if_addr_lookup(struct if_addr_head *, struct kaddr *); static int if_start(struct iface *, int); @@ -43,7 +43,7 @@ static int if_leave_ipv6_group(struct iface *, struct in6_addr *); RB_GENERATE(iface_head, iface, entry, iface_compare) static __inline int -iface_compare(struct iface *a, struct iface *b) +iface_compare(const struct iface *a, const struct iface *b) { return (strcmp(a->name, b->name)); } @@ -81,12 +81,12 @@ ldpe_if_init(struct iface *iface) /* ipv4 */ iface->ipv4.iface = iface; iface->ipv4.state = IF_STA_DOWN; - RB_INIT(&iface->ipv4.adj_tree); + RB_INIT(iface_head, &iface->ipv4.adj_tree); /* ipv6 */ iface->ipv6.iface = iface; iface->ipv6.state = IF_STA_DOWN; - RB_INIT(&iface->ipv6.adj_tree); + RB_INIT(iface_head, &iface->ipv6.adj_tree); } void @@ -305,7 +305,7 @@ if_reset(struct iface *iface, int af) ia = iface_af_get(iface, af); if_stop_hello_timer(ia); - while ((adj = RB_ROOT(&ia->adj_tree)) != NULL) + while ((adj = RB_ROOT(iface_head, &ia->adj_tree)) != NULL) adj_del(adj, S_SHUTDOWN); /* try to cleanup */ diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index 27948f5a1..f15461d3d 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -27,16 +27,16 @@ #include "log.h" static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); -static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); -static __inline int l2vpn_if_compare(struct l2vpn_if *, struct l2vpn_if *); -static __inline int l2vpn_pw_compare(struct l2vpn_pw *, struct l2vpn_pw *); +static __inline int l2vpn_compare(const struct l2vpn *, const struct l2vpn *); +static __inline int l2vpn_if_compare(const struct l2vpn_if *, const struct l2vpn_if *); +static __inline int l2vpn_pw_compare(const struct l2vpn_pw *, const struct l2vpn_pw *); RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) RB_GENERATE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare) RB_GENERATE(l2vpn_pw_head, l2vpn_pw, entry, l2vpn_pw_compare) static __inline int -l2vpn_compare(struct l2vpn *a, struct l2vpn *b) +l2vpn_compare(const struct l2vpn *a, const struct l2vpn *b) { return (strcmp(a->name, b->name)); } @@ -55,9 +55,9 @@ l2vpn_new(const char *name) l2vpn->mtu = DEFAULT_L2VPN_MTU; l2vpn->pw_type = DEFAULT_PW_TYPE; - RB_INIT(&l2vpn->if_tree); - RB_INIT(&l2vpn->pw_tree); - RB_INIT(&l2vpn->pw_inactive_tree); + RB_INIT(l2vpn_if_head, &l2vpn->if_tree); + RB_INIT(l2vpn_pw_head, &l2vpn->pw_tree); + RB_INIT(l2vpn_pw_head, &l2vpn->pw_inactive_tree); return (l2vpn); } @@ -76,15 +76,16 @@ l2vpn_del(struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + while ((lif = RB_ROOT(l2vpn_if_head, &l2vpn->if_tree)) != NULL) { RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) { RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, + &l2vpn->pw_inactive_tree)) != NULL) { RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } @@ -111,7 +112,7 @@ l2vpn_exit(struct l2vpn *l2vpn) } static __inline int -l2vpn_if_compare(struct l2vpn_if *a, struct l2vpn_if *b) +l2vpn_if_compare(const struct l2vpn_if *a, const struct l2vpn_if *b) { return (strcmp(a->ifname, b->ifname)); } @@ -174,7 +175,7 @@ l2vpn_if_update(struct l2vpn_if *lif) } static __inline int -l2vpn_pw_compare(struct l2vpn_pw *a, struct l2vpn_pw *b) +l2vpn_pw_compare(const struct l2vpn_pw *a, const struct l2vpn_pw *b) { return (strcmp(a->ifname, b->ifname)); } @@ -512,7 +513,7 @@ l2vpn_binding_ctl(pid_t pid) fn = (struct fec_node *)f; if (fn->local_label == NO_LABEL && - RB_EMPTY(&fn->downstream)) + RB_EMPTY(lde_map_head, &fn->downstream)) continue; memset(&pwctl, 0, sizeof(pwctl)); diff --git a/ldpd/lde.c b/ldpd/lde.c index 4b1ad63d6..0ef46dab3 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -41,15 +41,16 @@ static void lde_shutdown(void); static int lde_dispatch_imsg(struct thread *); static int lde_dispatch_parent(struct thread *); -static __inline int lde_nbr_compare(struct lde_nbr *, - struct lde_nbr *); +static __inline int lde_nbr_compare(const struct lde_nbr *, + const struct lde_nbr *); static struct lde_nbr *lde_nbr_new(uint32_t, struct lde_nbr *); static void lde_nbr_del(struct lde_nbr *); 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 __inline int lde_map_compare(const struct lde_map *, + const 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 *); @@ -542,10 +543,10 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); - RB_INIT(&nconf->iface_tree); - RB_INIT(&nconf->tnbr_tree); - RB_INIT(&nconf->nbrp_tree); - RB_INIT(&nconf->l2vpn_tree); + RB_INIT(iface_head, &nconf->iface_tree); + RB_INIT(tnbr_head, &nconf->tnbr_tree); + RB_INIT(nbrp_head, &nconf->nbrp_tree); + RB_INIT(l2vpn_head, &nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -573,9 +574,9 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - RB_INIT(&nl2vpn->if_tree); - RB_INIT(&nl2vpn->pw_tree); - RB_INIT(&nl2vpn->pw_inactive_tree); + RB_INIT(l2vpn_if_head, &nl2vpn->if_tree); + RB_INIT(l2vpn_pw_head, &nl2vpn->pw_tree); + RB_INIT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree); RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; @@ -1189,7 +1190,7 @@ lde_send_notification_eol_pwid(struct lde_nbr *ln, uint16_t pw_type) } static __inline int -lde_nbr_compare(struct lde_nbr *a, struct lde_nbr *b) +lde_nbr_compare(const struct lde_nbr *a, const struct lde_nbr *b) { return (a->peerid - b->peerid); } @@ -1314,7 +1315,7 @@ lde_nbr_clear(void) { struct lde_nbr *ln; - while ((ln = RB_ROOT(&lde_nbrs)) != NULL) + while ((ln = RB_ROOT(nbr_tree, &lde_nbrs)) != NULL) lde_nbr_del(ln); } @@ -1360,7 +1361,7 @@ 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) +lde_map_compare(const struct lde_map *a, const struct lde_map *b) { return (ldp_addrcmp(AF_INET, (union ldpd_addr *)&a->nexthop->id, (union ldpd_addr *)&b->nexthop->id)); diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c index 8dc305cac..edf686537 100644 --- a/ldpd/lde_lib.c +++ b/ldpd/lde_lib.c @@ -25,7 +25,7 @@ #include "mpls.h" -static __inline int fec_compare(struct fec *, struct fec *); +static __inline int fec_compare(const struct fec *, const struct fec *); static int lde_nbr_is_nexthop(struct fec_node *, struct lde_nbr *); static void fec_free(void *); @@ -43,11 +43,11 @@ struct thread *gc_timer; void fec_init(struct fec_tree *fh) { - RB_INIT(fh); + RB_INIT(fec_tree, fh); } static __inline int -fec_compare(struct fec *a, struct fec *b) +fec_compare(const struct fec *a, const struct fec *b) { if (a->type < b->type) return (-1); @@ -129,7 +129,7 @@ fec_clear(struct fec_tree *fh, void (*free_cb)(void *)) { struct fec *f; - while ((f = RB_ROOT(fh)) != NULL) { + while ((f = RB_ROOT(fec_tree, fh)) != NULL) { fec_remove(fh, f); free_cb(f); } @@ -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 && - RB_EMPTY(&fn->downstream)) + RB_EMPTY(lde_map_head, &fn->downstream)) continue; memset(&rtctl, 0, sizeof(rtctl)); @@ -179,7 +179,7 @@ rt_dump(pid_t pid) } rtctl.local_label = fn->local_label; - if (RB_EMPTY(&fn->downstream)) { + if (RB_EMPTY(lde_map_head, &fn->downstream)) { rtctl.in_use = 0; rtctl.nexthop.s_addr = INADDR_ANY; rtctl.remote_label = NO_LABEL; @@ -231,10 +231,10 @@ fec_free(void *arg) while ((fnh = LIST_FIRST(&fn->nexthops))) fec_nh_del(fnh); - if (!RB_EMPTY(&fn->downstream)) + if (!RB_EMPTY(lde_map_head, &fn->downstream)) log_warnx("%s: fec %s downstream list not empty", __func__, log_fec(&fn->fec)); - if (!RB_EMPTY(&fn->upstream)) + if (!RB_EMPTY(lde_map_head, &fn->upstream)) log_warnx("%s: fec %s upstream list not empty", __func__, log_fec(&fn->fec)); @@ -258,8 +258,8 @@ fec_add(struct fec *fec) fn->fec = *fec; fn->local_label = NO_LABEL; - RB_INIT(&fn->upstream); - RB_INIT(&fn->downstream); + RB_INIT(lde_map_head, &fn->upstream); + RB_INIT(lde_map_head, &fn->downstream); LIST_INIT(&fn->nexthops); if (fec_insert(&ft, &fn->fec)) @@ -396,7 +396,8 @@ lde_kernel_update(struct fec *fec) lde_gc_start_timer(); } else { fn->local_label = lde_update_label(fn); - if (fn->local_label != NO_LABEL && RB_EMPTY(&fn->upstream)) + if (fn->local_label != NO_LABEL && + RB_EMPTY(lde_map_head, &fn->upstream)) /* FEC.1: perform lsr label distribution procedure */ RB_FOREACH(ln, nbr_tree, &lde_nbrs) lde_send_labelmapping(ln, fn, 1); @@ -904,8 +905,8 @@ lde_gc_timer(struct thread *thread) fn = (struct fec_node *) fec; if (!LIST_EMPTY(&fn->nexthops) || - !RB_EMPTY(&fn->downstream) || - !RB_EMPTY(&fn->upstream)) + !RB_EMPTY(lde_map_head, &fn->downstream) || + !RB_EMPTY(lde_map_head, &fn->upstream)) continue; fec_remove(&ft, &fn->fec); diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index 839490714..87f76d3d0 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -1725,17 +1725,18 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + while ((lif = RB_ROOT(l2vpn_if_head, &l2vpn->if_tree)) != NULL) { QOBJ_UNREG(lif); RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) { QOBJ_UNREG(pw); RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, + &l2vpn->pw_inactive_tree)) != NULL) { QOBJ_UNREG(pw); RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index 6993ad15c..abcad79d6 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -1043,13 +1043,13 @@ ldp_config_reset_main(struct ldpd_conf *conf) struct iface *iface; struct nbr_params *nbrp; - while ((iface = RB_ROOT(&conf->iface_tree)) != NULL) { + while ((iface = RB_ROOT(iface_head, &conf->iface_tree)) != NULL) { QOBJ_UNREG(iface); RB_REMOVE(iface_head, &conf->iface_tree, iface); free(iface); } - while ((nbrp = RB_ROOT(&conf->nbrp_tree)) != NULL) { + while ((nbrp = RB_ROOT(nbrp_head, &conf->nbrp_tree)) != NULL) { QOBJ_UNREG(nbrp); RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp); free(nbrp); @@ -1105,18 +1105,20 @@ ldp_config_reset_l2vpns(struct ldpd_conf *conf) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((l2vpn = RB_ROOT(&conf->l2vpn_tree)) != NULL) { - while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + while ((l2vpn = RB_ROOT(l2vpn_head, &conf->l2vpn_tree)) != NULL) { + while ((lif = RB_ROOT(l2vpn_if_head, + &l2vpn->if_tree)) != NULL) { QOBJ_UNREG(lif); RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) { QOBJ_UNREG(pw); RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + while ((pw = RB_ROOT(l2vpn_pw_head, + &l2vpn->pw_inactive_tree)) != NULL) { QOBJ_UNREG(pw); RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); @@ -1135,19 +1137,19 @@ ldp_clear_config(struct ldpd_conf *xconf) struct nbr_params *nbrp; struct l2vpn *l2vpn; - while ((iface = RB_ROOT(&xconf->iface_tree)) != NULL) { + while ((iface = RB_ROOT(iface_head, &xconf->iface_tree)) != NULL) { RB_REMOVE(iface_head, &xconf->iface_tree, iface); free(iface); } - while ((tnbr = RB_ROOT(&xconf->tnbr_tree)) != NULL) { + while ((tnbr = RB_ROOT(tnbr_head, &xconf->tnbr_tree)) != NULL) { RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr); free(tnbr); } - while ((nbrp = RB_ROOT(&xconf->nbrp_tree)) != NULL) { + while ((nbrp = RB_ROOT(nbrp_head, &xconf->nbrp_tree)) != NULL) { RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp); free(nbrp); } - while ((l2vpn = RB_ROOT(&xconf->l2vpn_tree)) != NULL) { + while ((l2vpn = RB_ROOT(l2vpn_head, &xconf->l2vpn_tree)) != NULL) { RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, l2vpn); l2vpn_del(l2vpn); } @@ -1550,9 +1552,9 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf) if ((l2vpn = l2vpn_find(conf, xl->name)) == NULL) { COPY(l2vpn, xl); RB_INSERT(l2vpn_head, &conf->l2vpn_tree, l2vpn); - RB_INIT(&l2vpn->if_tree); - RB_INIT(&l2vpn->pw_tree); - RB_INIT(&l2vpn->pw_inactive_tree); + RB_INIT(l2vpn_if_head, &l2vpn->if_tree); + RB_INIT(l2vpn_pw_head, &l2vpn->pw_tree); + RB_INIT(l2vpn_pw_head, &l2vpn->pw_inactive_tree); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1761,10 +1763,10 @@ config_new_empty(void) if (xconf == NULL) fatal(NULL); - RB_INIT(&xconf->iface_tree); - RB_INIT(&xconf->tnbr_tree); - RB_INIT(&xconf->nbrp_tree); - RB_INIT(&xconf->l2vpn_tree); + RB_INIT(iface_head, &xconf->iface_tree); + RB_INIT(tnbr_head, &xconf->tnbr_tree); + RB_INIT(nbrp_head, &xconf->nbrp_tree); + RB_INIT(l2vpn_head, &xconf->l2vpn_tree); /* set default values */ ldp_config_reset(xconf); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 451d637bc..ba153dfde 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -152,7 +152,7 @@ ldpe_init(struct ldpd_init *init) control_listen(); LIST_INIT(&global.addr_list); - RB_INIT(&global.adj_tree); + RB_INIT(global_adj_head, &global.adj_tree); TAILQ_INIT(&global.pending_conns); if (inet_pton(AF_INET, AllRouters_v4, &global.mcast_addr_v4) != 1) fatal("inet_pton"); @@ -216,7 +216,7 @@ ldpe_shutdown(void) LIST_REMOVE(if_addr, entry); free(if_addr); } - while ((adj = RB_ROOT(&global.adj_tree)) != NULL) + while ((adj = RB_ROOT(global_adj_head, &global.adj_tree)) != NULL) adj_del(adj, S_SHUTDOWN); /* clean up */ @@ -456,10 +456,10 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); - RB_INIT(&nconf->iface_tree); - RB_INIT(&nconf->tnbr_tree); - RB_INIT(&nconf->nbrp_tree); - RB_INIT(&nconf->l2vpn_tree); + RB_INIT(iface_head, &nconf->iface_tree); + RB_INIT(tnbr_head, &nconf->tnbr_tree); + RB_INIT(nbrp_head, &nconf->nbrp_tree); + RB_INIT(l2vpn_head, &nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -487,9 +487,9 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - RB_INIT(&nl2vpn->if_tree); - RB_INIT(&nl2vpn->pw_tree); - RB_INIT(&nl2vpn->pw_inactive_tree); + RB_INIT(l2vpn_if_head, &nl2vpn->if_tree); + RB_INIT(l2vpn_pw_head, &nl2vpn->pw_tree); + RB_INIT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree); RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; @@ -876,8 +876,8 @@ ldpe_adj_detail_ctl(struct ctl_conn *c) continue; strlcpy(ictl.name, iface->name, sizeof(ictl.name)); - if (RB_EMPTY(&iface->ipv4.adj_tree) && - RB_EMPTY(&iface->ipv6.adj_tree)) + if (RB_EMPTY(ia_adj_head, &iface->ipv4.adj_tree) && + RB_EMPTY(ia_adj_head, &iface->ipv6.adj_tree)) ictl.no_adj = 1; imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_IFACE, 0, 0, -1, &ictl, sizeof(ictl)); diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c index f867db228..f8d4b5f5f 100644 --- a/ldpd/neighbor.c +++ b/ldpd/neighbor.c @@ -26,9 +26,11 @@ #include "lde.h" #include "log.h" -static __inline int nbr_id_compare(struct nbr *, struct nbr *); -static __inline int nbr_addr_compare(struct nbr *, struct nbr *); -static __inline int nbr_pid_compare(struct nbr *, struct nbr *); +static __inline int nbr_id_compare(const struct nbr *, const struct nbr *); +static __inline int nbr_addr_compare(const struct nbr *, + const struct nbr *); +static __inline int nbr_pid_compare(const struct nbr *, + const struct nbr *); static void nbr_update_peerid(struct nbr *); static int nbr_ktimer(struct thread *); static void nbr_start_ktimer(struct nbr *); @@ -39,8 +41,8 @@ static void nbr_start_itimeout(struct nbr *); static int nbr_idtimer(struct thread *); static int nbr_act_session_operational(struct nbr *); static void nbr_send_labelmappings(struct nbr *); -static __inline int nbr_params_compare(struct nbr_params *, - struct nbr_params *); +static __inline int nbr_params_compare(const struct nbr_params *, + const struct nbr_params *); RB_GENERATE(nbr_id_head, nbr, id_tree, nbr_id_compare) RB_GENERATE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare) @@ -101,13 +103,13 @@ struct nbr_addr_head nbrs_by_addr = RB_INITIALIZER(&nbrs_by_addr); struct nbr_pid_head nbrs_by_pid = RB_INITIALIZER(&nbrs_by_pid); static __inline int -nbr_id_compare(struct nbr *a, struct nbr *b) +nbr_id_compare(const struct nbr *a, const struct nbr *b) { return (ntohl(a->id.s_addr) - ntohl(b->id.s_addr)); } static __inline int -nbr_addr_compare(struct nbr *a, struct nbr *b) +nbr_addr_compare(const struct nbr *a, const struct nbr *b) { if (a->af < b->af) return (-1); @@ -118,7 +120,7 @@ nbr_addr_compare(struct nbr *a, struct nbr *b) } static __inline int -nbr_pid_compare(struct nbr *a, struct nbr *b) +nbr_pid_compare(const struct nbr *a, const struct nbr *b) { return (a->peerid - b->peerid); } @@ -229,7 +231,7 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr, if ((nbr = calloc(1, sizeof(*nbr))) == NULL) fatal(__func__); - RB_INIT(&nbr->adj_tree); + RB_INIT(nbr_adj_head, &nbr->adj_tree); nbr->state = NBR_STA_PRESENT; nbr->peerid = 0; nbr->af = af; @@ -764,7 +766,7 @@ nbr_send_labelmappings(struct nbr *nbr) } static __inline int -nbr_params_compare(struct nbr_params *a, struct nbr_params *b) +nbr_params_compare(const struct nbr_params *a, const struct nbr_params *b) { return (ntohl(a->lsr_id.s_addr) - ntohl(b->lsr_id.s_addr)); } diff --git a/lib/Makefile.am b/lib/Makefile.am index a1b78d3c4..4a8b4290a 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -15,7 +15,7 @@ libfrr_la_LDFLAGS = -version-info 0:0:0 libfrr_la_SOURCES = \ network.c pid_output.c getopt.c getopt1.c \ - checksum.c vector.c linklist.c vty.c \ + checksum.c vector.c linklist.c vty.c openbsd-tree.c \ graph.c command_parse.y command_lex.l command_match.c \ command_graph.c \ command.c \ @@ -39,7 +39,7 @@ DEFINE_MTYPE_STATIC(LIB, NS, "Logical-Router") DEFINE_MTYPE_STATIC(LIB, NS_NAME, "Logical-Router Name") -static __inline int ns_compare (struct ns *, struct ns *); +static __inline int ns_compare (const struct ns *, const struct ns *); static struct ns *ns_lookup (ns_id_t); RB_GENERATE (ns_head, ns, entry, ns_compare) @@ -108,7 +108,7 @@ static int ns_enable (struct ns *ns); static void ns_disable (struct ns *ns); static __inline int -ns_compare(struct ns *a, struct ns *b) +ns_compare(const struct ns *a, const struct ns *b) { return (a->ns_id - b->ns_id); } @@ -453,7 +453,7 @@ ns_terminate (void) { struct ns *ns; - while ((ns = RB_ROOT (&ns_tree)) != NULL) + while ((ns = RB_ROOT (ns_head, &ns_tree)) != NULL) ns_delete (ns); } diff --git a/lib/openbsd-tree.c b/lib/openbsd-tree.c new file mode 100644 index 000000000..37762abc1 --- /dev/null +++ b/lib/openbsd-tree.c @@ -0,0 +1,640 @@ +/* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */ + +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdlib.h> + +#include <lib/openbsd-tree.h> + +static inline struct rb_entry * +rb_n2e(const struct rb_type *t, void *node) +{ + unsigned long addr = (unsigned long)node; + + return ((struct rb_entry *)(addr + t->t_offset)); +} + +static inline void * +rb_e2n(const struct rb_type *t, struct rb_entry *rbe) +{ + unsigned long addr = (unsigned long)rbe; + + return ((void *)(addr - t->t_offset)); +} + +#define RBE_LEFT(_rbe) (_rbe)->rbt_left +#define RBE_RIGHT(_rbe) (_rbe)->rbt_right +#define RBE_PARENT(_rbe) (_rbe)->rbt_parent +#define RBE_COLOR(_rbe) (_rbe)->rbt_color + +#define RBH_ROOT(_rbt) (_rbt)->rbt_root + +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +{ + RBE_PARENT(rbe) = parent; + RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; + RBE_COLOR(rbe) = RB_RED; +} + +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) +{ + RBE_COLOR(black) = RB_BLACK; + RBE_COLOR(red) = RB_RED; +} + +static inline void +rbe_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + (*t->t_augment)(rb_e2n(t, rbe)); +} + +static inline void +rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + if (t->t_augment != NULL) + rbe_augment(t, rbe); +} + +static inline void +rbe_rotate_left(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_RIGHT(rbe); + RBE_RIGHT(rbe) = RBE_LEFT(tmp); + if (RBE_RIGHT(rbe) != NULL) + RBE_PARENT(RBE_LEFT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_LEFT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_LEFT(rbe); + RBE_LEFT(rbe) = RBE_RIGHT(tmp); + if (RBE_LEFT(rbe) != NULL) + RBE_PARENT(RBE_RIGHT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_RIGHT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent, *gparent, *tmp; + + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RB_RED) { + gparent = RBE_PARENT(parent); + + if (parent == RBE_LEFT(gparent)) { + tmp = RBE_RIGHT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_RIGHT(parent) == rbe) { + rbe_rotate_left(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_right(t, rbt, gparent); + } else { + tmp = RBE_LEFT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_LEFT(parent) == rbe) { + rbe_rotate_right(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_left(t, rbt, gparent); + } + } + + RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK; +} + +static inline void +rbe_remove_color(const struct rb_type *t, struct rb_tree *rbt, + struct rb_entry *parent, struct rb_entry *rbe) +{ + struct rb_entry *tmp; + + while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + rbe != RBH_ROOT(rbt)) { + if (RBE_LEFT(parent) == rbe) { + tmp = RBE_RIGHT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_left(t, rbt, parent); + tmp = RBE_RIGHT(parent); + } + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + struct rb_entry *oleft; + + oleft = RBE_LEFT(tmp); + if (oleft != NULL) + RBE_COLOR(oleft) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_right(t, rbt, tmp); + tmp = RBE_RIGHT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_RIGHT(tmp)) + RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK; + + rbe_rotate_left(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } else { + tmp = RBE_LEFT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_right(t, rbt, parent); + tmp = RBE_LEFT(parent); + } + + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + struct rb_entry *oright; + + oright = RBE_RIGHT(tmp); + if (oright != NULL) + RBE_COLOR(oright) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_left(t, rbt, tmp); + tmp = RBE_LEFT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_LEFT(tmp) != NULL) + RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK; + + rbe_rotate_right(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } + } + + if (rbe != NULL) + RBE_COLOR(rbe) = RB_BLACK; +} + +static inline struct rb_entry * +rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *child, *parent, *old = rbe; + unsigned int color; + + if (RBE_LEFT(rbe) == NULL) + child = RBE_RIGHT(rbe); + else if (RBE_RIGHT(rbe) == NULL) + child = RBE_LEFT(rbe); + else { + struct rb_entry *tmp; + + rbe = RBE_RIGHT(rbe); + while ((tmp = RBE_LEFT(rbe)) != NULL) + rbe = tmp; + + child = RBE_RIGHT(rbe); + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; + if (RBE_PARENT(rbe) == old) + parent = rbe; + *rbe = *old; + + tmp = RBE_PARENT(old); + if (tmp != NULL) { + if (RBE_LEFT(tmp) == old) + RBE_LEFT(tmp) = rbe; + else + RBE_RIGHT(tmp) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + RBE_PARENT(RBE_LEFT(old)) = rbe; + if (RBE_RIGHT(old)) + RBE_PARENT(RBE_RIGHT(old)) = rbe; + + if (t->t_augment != NULL && parent != NULL) { + tmp = parent; + do { + rbe_augment(t, tmp); + tmp = RBE_PARENT(tmp); + } while (tmp != NULL); + } + + goto color; + } + + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; +color: + if (color == RB_BLACK) + rbe_remove_color(t, rbt, parent, child); + + return (old); +} + +void * +_rb_remove(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *old; + + old = rbe_remove(t, rbt, rbe); + + return (old == NULL ? NULL : rb_e2n(t, old)); +} + +void * +_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *tmp; + struct rb_entry *parent = NULL; + void *node; + int comp = 0; + + tmp = RBH_ROOT(rbt); + while (tmp != NULL) { + parent = tmp; + + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + rbe_set(rbe, parent); + + if (parent != NULL) { + if (comp < 0) + RBE_LEFT(parent) = rbe; + else + RBE_RIGHT(parent) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + rbe_insert_color(t, rbt, rbe); + + return (NULL); +} + +/* Finds the node with the same key as elm */ +void * +_rb_find(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (NULL); +} + +/* Finds the first node greater than or equal to the search key */ +void * +_rb_nfind(const struct rb_type *t, struct rb_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + void *res = NULL; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) { + res = node; + tmp = RBE_LEFT(tmp); + } else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (res); +} + +void * +_rb_next(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_RIGHT(rbe) != NULL) { + rbe = RBE_RIGHT(rbe); + while (RBE_LEFT(rbe) != NULL) + rbe = RBE_LEFT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_prev(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_root(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + + return (rbe == NULL ? rbe : rb_e2n(t, rbe)); +} + +void * +_rb_min(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_LEFT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_max(const struct rb_type *t, struct rb_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_left(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_LEFT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_right(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_RIGHT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_parent(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_PARENT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void +_rb_set_left(const struct rb_type *t, void *node, void *left) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left); + + RBE_LEFT(rbe) = rbl; +} + +void +_rb_set_right(const struct rb_type *t, void *node, void *right) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right); + + RBE_RIGHT(rbe) = rbr; +} + +void +_rb_set_parent(const struct rb_type *t, void *node, void *parent) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent); + + RBE_PARENT(rbe) = rbp; +} + +void +_rb_poison(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) = + (struct rb_entry *)poison; +} + +int +_rb_check(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + return ((unsigned long)RBE_PARENT(rbe) == poison && + (unsigned long)RBE_LEFT(rbe) == poison && + (unsigned long)RBE_RIGHT(rbe) == poison); +} diff --git a/lib/openbsd-tree.h b/lib/openbsd-tree.h index e6502b1e7..8cf1a3df7 100644 --- a/lib/openbsd-tree.h +++ b/lib/openbsd-tree.h @@ -287,462 +287,266 @@ void name##_SPLAY_MINMAX(struct name *head, int __comp) \ (x) != NULL; \ (x) = SPLAY_NEXT(name, head, x)) -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (0) +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ #define RB_BLACK 0 #define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ -} while (0) -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (0) +struct rb_type { + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + unsigned int t_offset; /* offset of rb_entry in type */ +}; + +struct rb_tree { + struct rb_entry *rbt_root; +}; + +struct rb_entry { + struct rb_entry *rbt_parent; + struct rb_entry *rbt_left; + struct rb_entry *rbt_right; + unsigned int rbt_color; +}; + +#define RB_HEAD(_name, _type) \ +struct _name { \ + struct rb_tree rbh_root; \ +} -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif +#define RB_ENTRY(_type) struct rb_entry -#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) +static inline void +_rb_init(struct rb_tree *rbt) +{ + rbt->rbt_root = NULL; +} -#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) +static inline int +_rb_empty(struct rb_tree *rbt) +{ + return (rbt->rbt_root == NULL); +} -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RB_INSERT(struct name *, struct type *); \ -attr struct type *name##_RB_FIND(struct name *, struct type *); \ -attr struct type *name##_RB_NFIND(struct name *, struct type *); \ -attr struct type *name##_RB_NEXT(struct type *); \ -attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ +void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); +void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rb_tree *); +void *_rb_min(const struct rb_type *, struct rb_tree *); +void *_rb_max(const struct rb_type *, struct rb_tree *); +void *_rb_next(const struct rb_type *, void *); +void *_rb_prev(const struct rb_type *, void *); +void *_rb_left(const struct rb_type *, void *); +void *_rb_right(const struct rb_type *, void *); +void *_rb_parent(const struct rb_type *, void *); +void _rb_set_left(const struct rb_type *, void *, void *); +void _rb_set_right(const struct rb_type *, void *, void *); +void _rb_set_parent(const struct rb_type *, void *, void *); +void _rb_poison(const struct rb_type *, void *, unsigned long); +int _rb_check(const struct rb_type *, void *, unsigned long); + +#define RB_INITIALIZER(_head) { { NULL } } + +#ifndef __unused +#define __unused __attribute__((__unused__)) +#endif /* __unused */ + +#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RB_TYPE; \ \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +__unused static inline void \ +_name##_RB_INIT(struct _name *head) \ { \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) && \ - RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ + _rb_init(&head->rbh_root); \ } \ \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_INSERT(struct _name *head, struct _type *elm) \ { \ - struct type *tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RB_LEFT(tmp, field)))\ - RB_COLOR(oleft, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RB_RIGHT(tmp, field)))\ - RB_COLOR(oright, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ + return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ } \ \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ { \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field))) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field))); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ + return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ } \ \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RB_INSERT(struct name *head, struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_FIND(struct _name *head, const struct _type *key) \ { \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ + return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ } \ \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RB_FIND(struct name *head, struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_NFIND(struct _name *head, const struct _type *key) \ { \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ + return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ } \ \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_ROOT(struct _name *head) \ { \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ + return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ } \ \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_NEXT(struct type *elm) \ +__unused static inline int \ +_name##_RB_EMPTY(struct _name *head) \ { \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ + return _rb_empty(&head->rbh_root); \ } \ \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ +__unused static inline struct _type * \ +_name##_RB_MIN(struct _name *head) \ { \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ + return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ } \ \ -attr struct type * \ -name##_RB_MINMAX(struct name *head, int val) \ +__unused static inline struct _type * \ +_name##_RB_MAX(struct _name *head) \ { \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ + return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__unused static inline struct _type * \ +_name##_RB_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RB_TYPE, elm); \ +} \ + \ +__unused static inline struct _type * \ +_name##_RB_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RB_TYPE, elm); \ +} \ + \ +__unused static inline struct _type * \ +_name##_RB_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RB_TYPE, elm); \ +} \ + \ +__unused static inline struct _type * \ +_name##_RB_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RB_TYPE, elm); \ +} \ + \ +__unused static inline struct _type * \ +_name##_RB_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RB_TYPE, elm); \ +} \ + \ +__unused static inline void \ +_name##_RB_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + return _rb_set_left(_name##_RB_TYPE, elm, left); \ +} \ + \ +__unused static inline void \ +_name##_RB_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + return _rb_set_right(_name##_RB_TYPE, elm, right); \ +} \ + \ +__unused static inline void \ +_name##_RB_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ +} \ + \ +__unused static inline void \ +_name##_RB_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RB_TYPE, elm, poison); \ +} \ + \ +__unused static inline int \ +_name##_RB_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RB_TYPE, elm, poison); \ } -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ - (x) = (y)) +#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RB_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RB_INFO = { \ + _name##_RB_COMPARE, \ + _aug, \ + offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; + +#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RB_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) + +#define RB_GENERATE(_name, _type, _field, _cmp) \ + RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) + +#define RB_INIT(_name, _head) _name##_RB_INIT(_head) +#define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm) +#define RB_REMOVE(_name, _head, _elm) _name##_RB_REMOVE(_head, _elm) +#define RB_FIND(_name, _head, _key) _name##_RB_FIND(_head, _key) +#define RB_NFIND(_name, _head, _key) _name##_RB_NFIND(_head, _key) +#define RB_ROOT(_name, _head) _name##_RB_ROOT(_head) +#define RB_EMPTY(_name, _head) _name##_RB_EMPTY(_head) +#define RB_MIN(_name, _head) _name##_RB_MIN(_head) +#define RB_MAX(_name, _head) _name##_RB_MAX(_head) +#define RB_NEXT(_name, _elm) _name##_RB_NEXT(_elm) +#define RB_PREV(_name, _elm) _name##_RB_PREV(_elm) +#define RB_LEFT(_name, _elm) _name##_RB_LEFT(_elm) +#define RB_RIGHT(_name, _elm) _name##_RB_RIGHT(_elm) +#define RB_PARENT(_name, _elm) _name##_RB_PARENT(_elm) +#define RB_SET_LEFT(_name, _elm, _l) _name##_RB_SET_LEFT(_elm, _l) +#define RB_SET_RIGHT(_name, _elm, _r) _name##_RB_SET_RIGHT(_elm, _r) +#define RB_SET_PARENT(_name, _elm, _p) _name##_RB_SET_PARENT(_elm, _p) +#define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p) +#define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p) + +#define RB_FOREACH(_e, _name, _head) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RB_NEXT(_name, (_e))) + +#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) + +#define RB_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RB_PREV(_name, (_e))) + +#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); \ + (_e) = (_n)) #endif /* _SYS_TREE_H_ */ @@ -35,11 +35,11 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map") DEFINE_QOBJ_TYPE(vrf) -static __inline int vrf_id_compare (struct vrf *, struct vrf *); -static __inline int vrf_name_compare (struct vrf *, struct vrf *); +static __inline int vrf_id_compare (const struct vrf *, const struct vrf *); +static __inline int vrf_name_compare (const struct vrf *, const struct vrf *); -RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare) -RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare) +RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare); +RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare); struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id); struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name); @@ -72,13 +72,13 @@ vrf_lookup_by_name (const char *name) } static __inline int -vrf_id_compare (struct vrf *a, struct vrf *b) +vrf_id_compare (const struct vrf *a, const struct vrf *b) { return (a->vrf_id - b->vrf_id); } static int -vrf_name_compare (struct vrf *a, struct vrf *b) +vrf_name_compare (const struct vrf *a, const struct vrf *b) { return strcmp (a->name, b->name); } @@ -419,9 +419,9 @@ vrf_terminate (void) if (debug_vrf) zlog_debug ("%s: Shutting down vrf subsystem", __PRETTY_FUNCTION__); - while ((vrf = RB_ROOT (&vrfs_by_id)) != NULL) + while ((vrf = RB_ROOT (vrf_id_head, &vrfs_by_id)) != NULL) vrf_delete (vrf); - while ((vrf = RB_ROOT (&vrfs_by_name)) != NULL) + while ((vrf = RB_ROOT (vrf_name_head, &vrfs_by_name)) != NULL) vrf_delete (vrf); } diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c index e9ccac1c9..c2af0a0d2 100644 --- a/zebra/zebra_rib.c +++ b/zebra/zebra_rib.c @@ -2897,7 +2897,7 @@ vrf_id_get_next (vrf_id_t vrf_id, vrf_id_t *next_id_p) vrf = vrf_lookup_by_id (vrf_id); if (vrf) { - vrf = RB_NEXT (vrf_id_head, &vrfs_by_id, vrf); + vrf = RB_NEXT (vrf_id_head, vrf); if (vrf) { *next_id_p = vrf->vrf_id; return 1; |