summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--ldpd/adjacency.c8
-rw-r--r--ldpd/interface.c10
-rw-r--r--ldpd/l2vpn.c27
-rw-r--r--ldpd/lde.c27
-rw-r--r--ldpd/lde_lib.c27
-rw-r--r--ldpd/ldp_vty_conf.c7
-rw-r--r--ldpd/ldpd.c36
-rw-r--r--ldpd/ldpe.c22
-rw-r--r--ldpd/neighbor.c22
-rw-r--r--lib/Makefile.am2
-rw-r--r--lib/ns.c6
-rw-r--r--lib/openbsd-tree.c640
-rw-r--r--lib/openbsd-tree.h646
-rw-r--r--lib/vrf.c16
-rw-r--r--zebra/zebra_rib.c2
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 \
diff --git a/lib/ns.c b/lib/ns.c
index 8c489d68f..68dc3fa34 100644
--- a/lib/ns.c
+++ b/lib/ns.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_ */
diff --git a/lib/vrf.c b/lib/vrf.c
index c4e527db5..42debe5f1 100644
--- a/lib/vrf.c
+++ b/lib/vrf.c
@@ -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;