move pf from the RB macros to the RBT functions.

9 files changed, 147 insertions, 146 deletions

diff --git a/sys/net/if_pfsync.c b/sys/net/if_pfsync.c
index f07cd352755..8fb027d4e79 100644
--- a/sys/net/if_pfsync.c
+++ b/sys/net/if_pfsync.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_pfsync.c,v 1.232 2016/09/21 07:41:49 mpi Exp $	*/
+/*	$OpenBSD: if_pfsync.c,v 1.233 2016/09/27 02:51:12 dlg Exp $	*/
 
 /*
  * Copyright (c) 2002 Michael Shalayeff
@@ -747,8 +747,8 @@ pfsync_in_clr(caddr_t buf, int len, int count, int flags)
 		    (kif = pfi_kif_find(clr->ifname)) == NULL)
 			continue;
 
-		for (st = RB_MIN(pf_state_tree_id, &tree_id); st; st = nexts) {
-			nexts = RB_NEXT(pf_state_tree_id, &tree_id, st);
+		for (st = RBT_MIN(pf_state_tree_id, &tree_id); st; st = nexts) {
+			nexts = RBT_NEXT(pf_state_tree_id, st);
 			if (st->creatorid == creatorid &&
 			    ((kif && st->kif == kif) || !kif)) {
 				SET(st->state_flags, PFSTATE_NOSYNC);
diff --git a/sys/net/pf.c b/sys/net/pf.c
index 4a661daa0b4..415f0de75eb 100644
--- a/sys/net/pf.c
+++ b/sys/net/pf.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf.c,v 1.985 2016/09/22 10:50:19 jsg Exp $ */
+/*	$OpenBSD: pf.c,v 1.986 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -293,11 +293,12 @@ struct pf_pool_limit pf_pool_limits[PF_LIMIT_MAX] = {
 			mrm->r->states_cur++;			\
 	} while (0)
 
-static __inline int pf_src_compare(struct pf_src_node *, struct pf_src_node *);
-static __inline int pf_state_compare_key(struct pf_state_key *,
-	struct pf_state_key *);
-static __inline int pf_state_compare_id(struct pf_state *,
-	struct pf_state *);
+static __inline int pf_src_compare(const struct pf_src_node *,
+	const struct pf_src_node *);
+static __inline int pf_state_compare_key(const struct pf_state_key *,
+	const struct pf_state_key *);
+static __inline int pf_state_compare_id(const struct pf_state *,
+	const struct pf_state *);
 static __inline void pf_cksum_uncover(u_int16_t *, u_int16_t, u_int8_t);
 static __inline void pf_cksum_cover(u_int16_t *, u_int16_t, u_int8_t);
 
@@ -306,16 +307,17 @@ struct pf_src_tree tree_src_tracking;
 struct pf_state_tree_id tree_id;
 struct pf_state_queue state_list;
 
-RB_GENERATE(pf_src_tree, pf_src_node, entry, pf_src_compare);
-RB_GENERATE(pf_state_tree, pf_state_key, entry, pf_state_compare_key);
-RB_GENERATE(pf_state_tree_id, pf_state,
+RBT_GENERATE(pf_src_tree, pf_src_node, entry, pf_src_compare);
+RBT_GENERATE(pf_state_tree, pf_state_key, entry, pf_state_compare_key);
+RBT_GENERATE(pf_state_tree_id, pf_state,
     entry_id, pf_state_compare_id);
 
 SLIST_HEAD(pf_rule_gcl, pf_rule)	pf_rule_gcl =
 	SLIST_HEAD_INITIALIZER(pf_rule_gcl);
 
 __inline int
-pf_addr_compare(struct pf_addr *a, struct pf_addr *b, sa_family_t af)
+pf_addr_compare(const struct pf_addr *a, const struct pf_addr *b,
+    sa_family_t af)
 {
 	switch (af) {
 	case AF_INET:
@@ -349,7 +351,7 @@ pf_addr_compare(struct pf_addr *a, struct pf_addr *b, sa_family_t af)
 }
 
 static __inline int
-pf_src_compare(struct pf_src_node *a, struct pf_src_node *b)
+pf_src_compare(const struct pf_src_node *a, const struct pf_src_node *b)
 {
 	int	diff;
 
@@ -480,7 +482,7 @@ pf_src_connlimit(struct pf_state **state)
 			struct pf_state *st;
 
 			pf_status.lcounters[LCNT_OVERLOAD_FLUSH]++;
-			RB_FOREACH(st, pf_state_tree_id, &tree_id) {
+			RBT_FOREACH(st, pf_state_tree_id, &tree_id) {
 				sk = st->key[PF_SK_WIRE];
 				/*
 				 * Kill states from this source.  (Only those
@@ -528,7 +530,7 @@ pf_insert_src_node(struct pf_src_node **sn, struct pf_rule *rule,
 		PF_ACPY(&k.addr, src, af);
 		k.rule.ptr = rule;
 		pf_status.scounters[SCNT_SRC_NODE_SEARCH]++;
-		*sn = RB_FIND(pf_src_tree, &tree_src_tracking, &k);
+		*sn = RBT_FIND(pf_src_tree, &tree_src_tracking, &k);
 	}
 	if (*sn == NULL) {
 		if (!rule->max_src_nodes ||
@@ -549,7 +551,7 @@ pf_insert_src_node(struct pf_src_node **sn, struct pf_rule *rule,
 		PF_ACPY(&(*sn)->addr, src, af);
 		if (raddr)
 			PF_ACPY(&(*sn)->raddr, raddr, af);
-		if (RB_INSERT(pf_src_tree,
+		if (RBT_INSERT(pf_src_tree,
 		    &tree_src_tracking, *sn) != NULL) {
 			if (pf_status.debug >= LOG_NOTICE) {
 				log(LOG_NOTICE,
@@ -584,7 +586,7 @@ pf_remove_src_node(struct pf_src_node *sn)
 	if (sn->rule.ptr->states_cur == 0 &&
 	    sn->rule.ptr->src_nodes == 0)
 		pf_rm_rule(NULL, sn->rule.ptr);
-	RB_REMOVE(pf_src_tree, &tree_src_tracking, sn);
+	RBT_REMOVE(pf_src_tree, &tree_src_tracking, sn);
 	pf_status.scounters[SCNT_SRC_NODE_REMOVALS]++;
 	pf_status.src_nodes--;
 	pool_put(&pf_src_tree_pl, sn);
@@ -625,7 +627,7 @@ pf_state_rm_src_node(struct pf_state *s, struct pf_src_node *sn)
 /* state table stuff */
 
 static __inline int
-pf_state_compare_key(struct pf_state_key *a, struct pf_state_key *b)
+pf_state_compare_key(const struct pf_state_key *a, const struct pf_state_key *b)
 {
 	int	diff;
 
@@ -647,7 +649,7 @@ pf_state_compare_key(struct pf_state_key *a, struct pf_state_key *b)
 }
 
 static __inline int
-pf_state_compare_id(struct pf_state *a, struct pf_state *b)
+pf_state_compare_id(const struct pf_state *a, const struct pf_state *b)
 {
 	if (a->id > b->id)
 		return (1);
@@ -669,7 +671,7 @@ pf_state_key_attach(struct pf_state_key *sk, struct pf_state *s, int idx)
 	struct pf_state		*olds = NULL;
 
 	KASSERT(s->key[idx] == NULL);
-	if ((cur = RB_INSERT(pf_state_tree, &pf_statetbl, sk)) != NULL) {
+	if ((cur = RBT_INSERT(pf_state_tree, &pf_statetbl, sk)) != NULL) {
 		/* key exists. check for same kif, if none, add to key */
 		TAILQ_FOREACH(si, &cur->states, entry)
 			if (si->s->kif == s->kif &&
@@ -768,7 +770,7 @@ pf_state_key_detach(struct pf_state *s, int idx)
 	sk = s->key[idx];
 	s->key[idx] = NULL;
 	if (TAILQ_EMPTY(&sk->states)) {
-		RB_REMOVE(pf_state_tree, &pf_statetbl, sk);
+		RBT_REMOVE(pf_state_tree, &pf_statetbl, sk);
 		sk->removed = 1;
 		pf_state_key_unlink_reverse(sk);
 		pf_inpcb_unlink_state_key(sk->inp);
@@ -944,7 +946,7 @@ pf_state_insert(struct pfi_kif *kif, struct pf_state_key **skw,
 		s->id = htobe64(pf_status.stateid++);
 		s->creatorid = pf_status.hostid;
 	}
-	if (RB_INSERT(pf_state_tree_id, &tree_id, s) != NULL) {
+	if (RBT_INSERT(pf_state_tree_id, &tree_id, s) != NULL) {
 		if (pf_status.debug >= LOG_NOTICE) {
 			log(LOG_NOTICE, "pf: state insert failed: "
 			    "id: %016llx creatorid: %08x",
@@ -969,7 +971,7 @@ pf_find_state_byid(struct pf_state_cmp *key)
 {
 	pf_status.fcounters[FCNT_STATE_SEARCH]++;
 
-	return (RB_FIND(pf_state_tree_id, &tree_id, (struct pf_state *)key));
+	return (RBT_FIND(pf_state_tree_id, &tree_id, (struct pf_state *)key));
 }
 
 int
@@ -1048,7 +1050,7 @@ pf_find_state(struct pfi_kif *kif, struct pf_state_key_cmp *key, u_int dir,
 	}
 
 	if (sk == NULL) {
-		if ((sk = RB_FIND(pf_state_tree, &pf_statetbl,
+		if ((sk = RBT_FIND(pf_state_tree, &pf_statetbl,
 		    (struct pf_state_key *)key)) == NULL)
 			return (NULL);
 		if (dir == PF_OUT && pkt_sk &&
@@ -1084,7 +1086,7 @@ pf_find_state_all(struct pf_state_key_cmp *key, u_int dir, int *more)
 
 	pf_status.fcounters[FCNT_STATE_SEARCH]++;
 
-	sk = RB_FIND(pf_state_tree, &pf_statetbl, (struct pf_state_key *)key);
+	sk = RBT_FIND(pf_state_tree, &pf_statetbl, (struct pf_state_key *)key);
 
 	if (sk != NULL) {
 		TAILQ_FOREACH(si, &sk->states, entry)
@@ -1269,14 +1271,13 @@ pf_purge_expired_src_nodes(int waslocked)
 	struct pf_src_node		*cur, *next;
 	int				 locked = waslocked;
 
-	for (cur = RB_MIN(pf_src_tree, &tree_src_tracking); cur; cur = next) {
-	next = RB_NEXT(pf_src_tree, &tree_src_tracking, cur);
+	for (cur = RBT_MIN(pf_src_tree, &tree_src_tracking); cur; cur = next) {
+		next = RBT_NEXT(pf_src_tree, cur);
 
 		if (cur->states == 0 && cur->expire <= time_uptime) {
 			if (! locked) {
 				rw_enter_write(&pf_consistency_lock);
-				next = RB_NEXT(pf_src_tree,
-				    &tree_src_tracking, cur);
+				next = RBT_NEXT(pf_src_tree, cur);
 				locked = 1;
 			}
 			pf_remove_src_node(cur);
@@ -1327,7 +1328,7 @@ pf_remove_state(struct pf_state *cur)
 		    TH_RST|TH_ACK, 0, 0, 0, 1, cur->tag,
 		    cur->key[PF_SK_WIRE]->rdomain);
 	}
-	RB_REMOVE(pf_state_tree_id, &tree_id, cur);
+	RBT_REMOVE(pf_state_tree_id, &tree_id, cur);
 #if NPFLOW > 0
 	if (cur->state_flags & PFSTATE_PFLOW)
 		export_pflow(cur);
@@ -3025,7 +3026,7 @@ pf_step_into_anchor(int *depth, struct pf_ruleset **rs,
 	f->r = *r;
 	if ((*r)->anchor_wildcard) {
 		f->parent = &(*r)->anchor->children;
-		if ((f->child = RB_MIN(pf_anchor_node, f->parent)) == NULL) {
+		if ((f->child = RBT_MIN(pf_anchor_node, f->parent)) == NULL) {
 			*r = NULL;
 			return;
 		}
@@ -3050,7 +3051,7 @@ pf_step_out_of_anchor(int *depth, struct pf_ruleset **rs,
 			break;
 		f = pf_anchor_stack + *depth - 1;
 		if (f->parent != NULL && f->child != NULL) {
-			f->child = RB_NEXT(pf_anchor_node, f->parent, f->child);
+			f->child = RBT_NEXT(pf_anchor_node, f->child);
 			if (f->child != NULL) {
 				*rs = &f->child->ruleset;
 				*r = TAILQ_FIRST((*rs)->rules.active.ptr);
diff --git a/sys/net/pf_if.c b/sys/net/pf_if.c
index 75c73bc3843..88593d41119 100644
--- a/sys/net/pf_if.c
+++ b/sys/net/pf_if.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_if.c,v 1.84 2016/09/15 02:00:18 dlg Exp $ */
+/*	$OpenBSD: pf_if.c,v 1.85 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright 2005 Henning Brauer <henning@openbsd.org>
@@ -72,12 +72,12 @@ void		 pfi_table_update(struct pfr_ktable *, struct pfi_kif *,
 void		 pfi_kifaddr_update(void *);
 void		 pfi_instance_add(struct ifnet *, u_int8_t, int);
 void		 pfi_address_add(struct sockaddr *, sa_family_t, u_int8_t);
-int		 pfi_if_compare(struct pfi_kif *, struct pfi_kif *);
+int		 pfi_if_compare(const struct pfi_kif *, const struct pfi_kif *);
 int		 pfi_skip_if(const char *, struct pfi_kif *);
 int		 pfi_unmask(void *);
 
-RB_PROTOTYPE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
-RB_GENERATE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
+RBT_PROTOTYPE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
+RBT_GENERATE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
 
 #define PFI_BUFFER_MAX		0x10000
 #define PFI_MTYPE		M_IFADDR
@@ -105,7 +105,7 @@ pfi_kif_find(const char *kif_name)
 
 	bzero(&s, sizeof(s));
 	strlcpy(s.pfik_name, kif_name, sizeof(s.pfik_name));
-	return (RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&s));
+	return (RBT_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&s));
 }
 
 struct pfi_kif *
@@ -130,7 +130,7 @@ pfi_kif_get(const char *kif_name)
 		kif->pfik_flags_new |= PFI_IFLAG_ANY;
 	}
 
-	RB_INSERT(pfi_ifhead, &pfi_ifs, kif);
+	RBT_INSERT(pfi_ifhead, &pfi_ifs, kif);
 	return (kif);
 }
 
@@ -195,7 +195,7 @@ pfi_kif_unref(struct pfi_kif *kif, enum pfi_kif_refs what)
 	if (kif->pfik_rules || kif->pfik_states || kif->pfik_routes)
 		return;
 
-	RB_REMOVE(pfi_ifhead, &pfi_ifs, kif);
+	RBT_REMOVE(pfi_ifhead, &pfi_ifs, kif);
 	free(kif, PFI_MTYPE, 0);
 }
 
@@ -628,7 +628,7 @@ pfi_kifaddr_update(void *v)
 }
 
 int
-pfi_if_compare(struct pfi_kif *p, struct pfi_kif *q)
+pfi_if_compare(const struct pfi_kif *p, const struct pfi_kif *q)
 {
 	return (strncmp(p->pfik_name, q->pfik_name, IFNAMSIZ));
 }
@@ -644,7 +644,7 @@ pfi_update_status(const char *name, struct pf_status *pfs)
 
 	s = splsoftnet();
 	if (*name == '\0' && pfs == NULL) {
-		RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+		RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
 			bzero(p->pfik_packets, sizeof(p->pfik_packets));
 			bzero(p->pfik_bytes, sizeof(p->pfik_bytes));
 			p->pfik_tzero = time_second;
@@ -654,7 +654,7 @@ pfi_update_status(const char *name, struct pf_status *pfs)
 	}
 
 	strlcpy(key.pfik_name, name, sizeof(key.pfik_name));
-	p = RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&key);
+	p = RBT_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&key);
 	if (p == NULL) {
 		splx(s);
 		return;
@@ -704,8 +704,8 @@ pfi_get_ifaces(const char *name, struct pfi_kif *buf, int *size)
 	int		 s, n = 0;
 
 	s = splsoftnet();
-	for (p = RB_MIN(pfi_ifhead, &pfi_ifs); p; p = nextp) {
-		nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p);
+	for (p = RBT_MIN(pfi_ifhead, &pfi_ifs); p; p = nextp) {
+		nextp = RBT_NEXT(pfi_ifhead, p);
 		if (pfi_skip_if(name, p))
 			continue;
 		if (*size > n++) {
@@ -717,7 +717,7 @@ pfi_get_ifaces(const char *name, struct pfi_kif *buf, int *size)
 				splx(s);
 				return (EFAULT);
 			}
-			nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p);
+			nextp = RBT_NEXT(pfi_ifhead, p);
 			pfi_kif_unref(p, PFI_KIF_REF_RULE);
 		}
 	}
@@ -755,7 +755,7 @@ pfi_set_flags(const char *name, int flags)
 	int		 s;
 
 	s = splsoftnet();
-	RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+	RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
 		if (pfi_skip_if(name, p))
 			continue;
 		p->pfik_flags_new = p->pfik_flags | flags;
@@ -771,7 +771,7 @@ pfi_clear_flags(const char *name, int flags)
 	int		 s;
 
 	s = splsoftnet();
-	RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+	RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
 		if (pfi_skip_if(name, p))
 			continue;
 		p->pfik_flags_new = p->pfik_flags & ~flags;
@@ -787,7 +787,7 @@ pfi_xcommit(void)
 	int		 s;
 
 	s = splsoftnet();
-	RB_FOREACH(p, pfi_ifhead, &pfi_ifs)
+	RBT_FOREACH(p, pfi_ifhead, &pfi_ifs)
 		p->pfik_flags = p->pfik_flags_new;
 	splx(s);
 }
diff --git a/sys/net/pf_ioctl.c b/sys/net/pf_ioctl.c
index e8b364e7283..e105e21a82a 100644
--- a/sys/net/pf_ioctl.c
+++ b/sys/net/pf_ioctl.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_ioctl.c,v 1.300 2016/09/15 02:00:18 dlg Exp $ */
+/*	$OpenBSD: pf_ioctl.c,v 1.301 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -169,8 +169,8 @@ pfattach(int num)
 		pf_pool_limits[PF_LIMIT_TABLE_ENTRIES].limit =
 		    PFR_KENTRY_HIWAT_SMALL;
 
-	RB_INIT(&tree_src_tracking);
-	RB_INIT(&pf_anchors);
+	RBT_INIT(pf_src_tree, &tree_src_tracking);
+	RBT_INIT(pf_anchor_global, &pf_anchors);
 	pf_init_ruleset(&pf_main_ruleset);
 	TAILQ_INIT(&pf_queues[0]);
 	TAILQ_INIT(&pf_queues[1]);
@@ -1418,8 +1418,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		struct pfioc_state_kill *psk = (struct pfioc_state_kill *)addr;
 		u_int			 killed = 0;
 
-		for (s = RB_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
-			nexts = RB_NEXT(pf_state_tree_id, &tree_id, s);
+		for (s = RBT_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
+			nexts = RBT_NEXT(pf_state_tree_id, s);
 
 			if (!psk->psk_ifname[0] || !strcmp(psk->psk_ifname,
 			    s->kif->pfik_name)) {
@@ -1456,9 +1456,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 			break;
 		}
 
-		for (s = RB_MIN(pf_state_tree_id, &tree_id); s;
-		    s = nexts) {
-			nexts = RB_NEXT(pf_state_tree_id, &tree_id, s);
+		for (s = RBT_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
+			nexts = RBT_NEXT(pf_state_tree_id, s);
 
 			if (s->direction == PF_OUT) {
 				sk = s->key[PF_SK_STACK];
@@ -1754,11 +1753,11 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		pr->nr = 0;
 		if (ruleset->anchor == NULL) {
 			/* XXX kludge for pf_main_ruleset */
-			RB_FOREACH(anchor, pf_anchor_global, &pf_anchors)
+			RBT_FOREACH(anchor, pf_anchor_global, &pf_anchors)
 				if (anchor->parent == NULL)
 					pr->nr++;
 		} else {
-			RB_FOREACH(anchor, pf_anchor_node,
+			RBT_FOREACH(anchor, pf_anchor_node,
 			    &ruleset->anchor->children)
 				pr->nr++;
 		}
@@ -1779,14 +1778,14 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		pr->name[0] = 0;
 		if (ruleset->anchor == NULL) {
 			/* XXX kludge for pf_main_ruleset */
-			RB_FOREACH(anchor, pf_anchor_global, &pf_anchors)
+			RBT_FOREACH(anchor, pf_anchor_global, &pf_anchors)
 				if (anchor->parent == NULL && nr++ == pr->nr) {
 					strlcpy(pr->name, anchor->name,
 					    sizeof(pr->name));
 					break;
 				}
 		} else {
-			RB_FOREACH(anchor, pf_anchor_node,
+			RBT_FOREACH(anchor, pf_anchor_node,
 			    &ruleset->anchor->children)
 				if (nr++ == pr->nr) {
 					strlcpy(pr->name, anchor->name,
@@ -2236,7 +2235,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		int			 space = psn->psn_len;
 
 		if (space == 0) {
-			RB_FOREACH(n, pf_src_tree, &tree_src_tracking)
+			RBT_FOREACH(n, pf_src_tree, &tree_src_tracking)
 				nr++;
 			psn->psn_len = sizeof(struct pf_src_node) * nr;
 			break;
@@ -2245,7 +2244,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		pstore = malloc(sizeof(*pstore), M_TEMP, M_WAITOK);
 
 		p = psn->psn_src_nodes;
-		RB_FOREACH(n, pf_src_tree, &tree_src_tracking) {
+		RBT_FOREACH(n, pf_src_tree, &tree_src_tracking) {
 			int	secs = time_uptime, diff;
 
 			if ((nr + 1) * sizeof(*p) > (unsigned)psn->psn_len)
@@ -2289,9 +2288,9 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		struct pf_src_node	*n;
 		struct pf_state		*state;
 
-		RB_FOREACH(state, pf_state_tree_id, &tree_id)
+		RBT_FOREACH(state, pf_state_tree_id, &tree_id)
 			pf_src_tree_remove_state(state);
-		RB_FOREACH(n, pf_src_tree, &tree_src_tracking)
+		RBT_FOREACH(n, pf_src_tree, &tree_src_tracking)
 			n->expire = 1;
 		pf_purge_expired_src_nodes(1);
 		break;
@@ -2304,7 +2303,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 		    (struct pfioc_src_node_kill *)addr;
 		u_int			killed = 0;
 
-		RB_FOREACH(sn, pf_src_tree, &tree_src_tracking) {
+		RBT_FOREACH(sn, pf_src_tree, &tree_src_tracking) {
 			if (PF_MATCHA(psnk->psnk_src.neg,
 				&psnk->psnk_src.addr.v.a.addr,
 				&psnk->psnk_src.addr.v.a.mask,
@@ -2315,7 +2314,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 				&sn->raddr, sn->af)) {
 				/* Handle state to src_node linkage */
 				if (sn->states != 0)
-					RB_FOREACH(s, pf_state_tree_id,
+					RBT_FOREACH(s, pf_state_tree_id,
 					   &tree_id)
 						pf_state_rm_src_node(s, sn);
 				sn->expire = 1;
diff --git a/sys/net/pf_lb.c b/sys/net/pf_lb.c
index e42bdfae84f..959716c2b76 100644
--- a/sys/net/pf_lb.c
+++ b/sys/net/pf_lb.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_lb.c,v 1.55 2016/07/19 12:51:19 henning Exp $ */
+/*	$OpenBSD: pf_lb.c,v 1.56 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -275,7 +275,7 @@ pf_map_addr_sticky(sa_family_t af, struct pf_rule *r, struct pf_addr *saddr,
 	PF_ACPY(&k.addr, saddr, af);
 	k.rule.ptr = r;
 	pf_status.scounters[SCNT_SRC_NODE_SEARCH]++;
-	sns[type] = RB_FIND(pf_src_tree, &tree_src_tracking, &k);
+	sns[type] = RBT_FIND(pf_src_tree, &tree_src_tracking, &k);
 	if (sns[type] == NULL)
 		return (-1);
 
@@ -307,7 +307,7 @@ pf_map_addr_sticky(sa_family_t af, struct pf_rule *r, struct pf_addr *saddr,
 		}
 		if (sns[type]->states != 0) {
 			/* XXX expensive */
-			RB_FOREACH(s, pf_state_tree_id,
+			RBT_FOREACH(s, pf_state_tree_id,
 			   &tree_id)
 				pf_state_rm_src_node(s,
 				    sns[type]);
diff --git a/sys/net/pf_norm.c b/sys/net/pf_norm.c
index 5c5d6ff0e9a..15b395fc36d 100644
--- a/sys/net/pf_norm.c
+++ b/sys/net/pf_norm.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_norm.c,v 1.192 2016/09/15 02:00:18 dlg Exp $ */
+/*	$OpenBSD: pf_norm.c,v 1.193 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright 2001 Niels Provos <provos@citi.umich.edu>
@@ -74,7 +74,7 @@ struct pf_frent {
 	u_int16_t	 fe_mff;	/* more fragment flag */
 };
 
-/* keep synced with struct pf_fragment, used in RB_FIND */
+/* keep synced with struct pf_fragment, used in RBT_FIND */
 struct pf_fragment_cmp {
 	struct pf_addr	fr_src;
 	struct pf_addr	fr_dst;
@@ -92,7 +92,7 @@ struct pf_fragment {
 	u_int8_t	fr_proto;	/* protocol of this fragment */
 	u_int8_t	fr_direction;	/* pf packet direction */
 
-	RB_ENTRY(pf_fragment) fr_entry;
+	RBT_ENTRY(pf_fragment) fr_entry;
 	TAILQ_ENTRY(pf_fragment) frag_next;
 	TAILQ_HEAD(pf_fragq, pf_frent) fr_queue;
 	int32_t		fr_timeout;
@@ -107,11 +107,11 @@ struct pf_fragment_tag {
 
 TAILQ_HEAD(pf_fragqueue, pf_fragment)	pf_fragqueue;
 
-static __inline int	 pf_frag_compare(struct pf_fragment *,
-			    struct pf_fragment *);
-RB_HEAD(pf_frag_tree, pf_fragment)	pf_frag_tree, pf_cache_tree;
-RB_PROTOTYPE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
-RB_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
+static __inline int	 pf_frag_compare(const struct pf_fragment *,
+			    const struct pf_fragment *);
+RBT_HEAD(pf_frag_tree, pf_fragment)	pf_frag_tree, pf_cache_tree;
+RBT_PROTOTYPE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
+RBT_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
 
 /* Private prototypes */
 void			 pf_flush_fragments(void);
@@ -151,7 +151,7 @@ pf_normalize_init(void)
 }
 
 static __inline int
-pf_frag_compare(struct pf_fragment *a, struct pf_fragment *b)
+pf_frag_compare(const struct pf_fragment *a, const struct pf_fragment *b)
 {
 	int	diff;
 
@@ -211,7 +211,7 @@ pf_free_fragment(struct pf_fragment *frag)
 {
 	struct pf_frent		*frent;
 
-	RB_REMOVE(pf_frag_tree, &pf_frag_tree, frag);
+	RBT_REMOVE(pf_frag_tree, &pf_frag_tree, frag);
 	TAILQ_REMOVE(&pf_fragqueue, frag, frag_next);
 
 	/* Free all fragment entries */
@@ -229,7 +229,7 @@ pf_find_fragment(struct pf_fragment_cmp *key, struct pf_frag_tree *tree)
 {
 	struct pf_fragment	*frag;
 
-	frag = RB_FIND(pf_frag_tree, tree, (struct pf_fragment *)key);
+	frag = RBT_FIND(pf_frag_tree, tree, (struct pf_fragment *)key);
 	if (frag != NULL) {
 		TAILQ_REMOVE(&pf_fragqueue, frag, frag_next);
 		TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next);
@@ -309,7 +309,7 @@ pf_fillup_fragment(struct pf_fragment_cmp *key, struct pf_frent *frent,
 		frag->fr_timeout = time_uptime;
 		frag->fr_maxlen = frent->fe_len;
 
-		RB_INSERT(pf_frag_tree, &pf_frag_tree, frag);
+		RBT_INSERT(pf_frag_tree, &pf_frag_tree, frag);
 		TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next);
 
 		/* We do not have a previous fragment */
diff --git a/sys/net/pf_ruleset.c b/sys/net/pf_ruleset.c
index 31c2c89fb2c..8fbd73d1d66 100644
--- a/sys/net/pf_ruleset.c
+++ b/sys/net/pf_ruleset.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_ruleset.c,v 1.12 2016/07/19 13:34:12 henning Exp $ */
+/*	$OpenBSD: pf_ruleset.c,v 1.13 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -79,13 +79,14 @@
 struct pf_anchor_global	 pf_anchors;
 struct pf_anchor	 pf_main_anchor;
 
-static __inline int pf_anchor_compare(struct pf_anchor *, struct pf_anchor *);
+static __inline int pf_anchor_compare(const struct pf_anchor *,
+    const struct pf_anchor *);
 
-RB_GENERATE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare);
-RB_GENERATE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare);
+RBT_GENERATE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare);
+RBT_GENERATE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare);
 
 static __inline int
-pf_anchor_compare(struct pf_anchor *a, struct pf_anchor *b)
+pf_anchor_compare(const struct pf_anchor *a, const struct pf_anchor *b)
 {
 	int c = strcmp(a->path, b->path);
 
@@ -111,7 +112,7 @@ pf_find_anchor(const char *path)
 	if (key == NULL)
 		return (NULL);
 	strlcpy(key->path, path, sizeof(key->path));
-	found = RB_FIND(pf_anchor_global, &pf_anchors, key);
+	found = RBT_FIND(pf_anchor_global, &pf_anchors, key);
 	rs_free(key);
 	return (found);
 }
@@ -180,7 +181,7 @@ pf_find_or_create_ruleset(const char *path)
 			rs_free(p);
 			return (NULL);
 		}
-		RB_INIT(&anchor->children);
+		RBT_INIT(pf_anchor_node, &anchor->children);
 		strlcpy(anchor->name, q, sizeof(anchor->name));
 		if (parent != NULL) {
 			strlcpy(anchor->path, parent->path,
@@ -188,10 +189,10 @@ pf_find_or_create_ruleset(const char *path)
 			strlcat(anchor->path, "/", sizeof(anchor->path));
 		}
 		strlcat(anchor->path, anchor->name, sizeof(anchor->path));
-		if ((dup = RB_INSERT(pf_anchor_global, &pf_anchors, anchor)) !=
+		if ((dup = RBT_INSERT(pf_anchor_global, &pf_anchors, anchor)) !=
 		    NULL) {
 			DPFPRINTF(LOG_NOTICE,
-			    "pf_find_or_create_ruleset: RB_INSERT1 "
+			    "pf_find_or_create_ruleset: RBT_INSERT1 "
 			    "'%s' '%s' collides with '%s' '%s'",
 			    anchor->path, anchor->name, dup->path, dup->name);
 			rs_free(anchor);
@@ -200,14 +201,14 @@ pf_find_or_create_ruleset(const char *path)
 		}
 		if (parent != NULL) {
 			anchor->parent = parent;
-			if ((dup = RB_INSERT(pf_anchor_node, &parent->children,
+			if ((dup = RBT_INSERT(pf_anchor_node, &parent->children,
 			    anchor)) != NULL) {
 				DPFPRINTF(LOG_NOTICE,
 				    "pf_find_or_create_ruleset: "
-				    "RB_INSERT2 '%s' '%s' collides with "
+				    "RBT_INSERT2 '%s' '%s' collides with "
 				    "'%s' '%s'", anchor->path, anchor->name,
 				    dup->path, dup->name);
-				RB_REMOVE(pf_anchor_global, &pf_anchors,
+				RBT_REMOVE(pf_anchor_global, &pf_anchors,
 				    anchor);
 				rs_free(anchor);
 				rs_free(p);
@@ -233,7 +234,7 @@ pf_remove_if_empty_ruleset(struct pf_ruleset *ruleset)
 
 	while (ruleset != NULL) {
 		if (ruleset == &pf_main_ruleset || ruleset->anchor == NULL ||
-		    !RB_EMPTY(&ruleset->anchor->children) ||
+		    !RBT_EMPTY(pf_anchor_node, &ruleset->anchor->children) ||
 		    ruleset->anchor->refcnt > 0 || ruleset->tables > 0 ||
 		    ruleset->topen)
 			return;
@@ -241,9 +242,9 @@ pf_remove_if_empty_ruleset(struct pf_ruleset *ruleset)
 		    !TAILQ_EMPTY(ruleset->rules.inactive.ptr) ||
 		    ruleset->rules.inactive.open)
 			return;
-		RB_REMOVE(pf_anchor_global, &pf_anchors, ruleset->anchor);
+		RBT_REMOVE(pf_anchor_global, &pf_anchors, ruleset->anchor);
 		if ((parent = ruleset->anchor->parent) != NULL)
-			RB_REMOVE(pf_anchor_node, &parent->children,
+			RBT_REMOVE(pf_anchor_node, &parent->children,
 			    ruleset->anchor);
 		rs_free(ruleset->anchor);
 		if (parent == NULL)
diff --git a/sys/net/pf_table.c b/sys/net/pf_table.c
index 5aa261c42cd..83834c5105f 100644
--- a/sys/net/pf_table.c
+++ b/sys/net/pf_table.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_table.c,v 1.118 2016/09/15 02:00:18 dlg Exp $	*/
+/*	$OpenBSD: pf_table.c,v 1.119 2016/09/27 02:51:12 dlg Exp $	*/
 
 /*
  * Copyright (c) 2002 Cedric Berger
@@ -177,8 +177,8 @@ struct pfr_ktable	*pfr_create_ktable(struct pfr_table *, time_t, int,
 			    int);
 void			 pfr_destroy_ktables(struct pfr_ktableworkq *, int);
 void			 pfr_destroy_ktable(struct pfr_ktable *, int);
-int			 pfr_ktable_compare(struct pfr_ktable *,
-			    struct pfr_ktable *);
+int			 pfr_ktable_compare(const struct pfr_ktable *,
+			    const struct pfr_ktable *);
 void			 pfr_ktable_winfo_update(struct pfr_ktable *,
 			    struct pfr_kentry *);
 struct pfr_ktable	*pfr_lookup_table(struct pfr_table *);
@@ -190,8 +190,8 @@ int			 pfr_skip_table(struct pfr_table *,
 struct pfr_kentry	*pfr_kentry_byidx(struct pfr_ktable *, int, int);
 int			 pfr_islinklocal(sa_family_t, struct pf_addr *);
 
-RB_PROTOTYPE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
-RB_GENERATE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
+RBT_PROTOTYPE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
+RBT_GENERATE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
 
 struct pfr_ktablehead	 pfr_ktables;
 struct pfr_table	 pfr_nulltable;
@@ -1273,7 +1273,7 @@ pfr_clr_tables(struct pfr_table *filter, int *ndel, int flags)
 		return (ENOENT);
 
 	SLIST_INIT(&workq);
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (pfr_skip_table(filter, p, flags))
 			continue;
 		if (!strcmp(p->pfrkt_anchor, PF_RESERVED_ANCHOR))
@@ -1311,7 +1311,7 @@ pfr_add_tables(struct pfr_table *tbl, int size, int *nadd, int flags)
 		    flags & PFR_FLAG_USERIOCTL))
 			senderr(EINVAL);
 		key.pfrkt_flags |= PFR_TFLAG_ACTIVE;
-		p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+		p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 		if (p == NULL) {
 			p = pfr_create_ktable(&key.pfrkt_t, tzero, 1,
 			    !(flags & PFR_FLAG_USERIOCTL));
@@ -1328,7 +1328,7 @@ pfr_add_tables(struct pfr_table *tbl, int size, int *nadd, int flags)
 
 			/* find or create root table */
 			bzero(key.pfrkt_anchor, sizeof(key.pfrkt_anchor));
-			r = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+			r = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 			if (r != NULL) {
 				p->pfrkt_root = r;
 				goto _skip;
@@ -1387,7 +1387,7 @@ pfr_del_tables(struct pfr_table *tbl, int size, int *ndel, int flags)
 		if (pfr_validate_table(&key.pfrkt_t, 0,
 		    flags & PFR_FLAG_USERIOCTL))
 			return (EINVAL);
-		p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+		p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 		if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) {
 			SLIST_FOREACH(q, &workq, pfrkt_workq)
 				if (!pfr_ktable_compare(p, q))
@@ -1425,7 +1425,7 @@ pfr_get_tables(struct pfr_table *filter, struct pfr_table *tbl, int *size,
 		*size = n;
 		return (0);
 	}
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (pfr_skip_table(filter, p, flags))
 			continue;
 		if (n-- <= 0)
@@ -1463,7 +1463,7 @@ pfr_get_tstats(struct pfr_table *filter, struct pfr_tstats *tbl, int *size,
 		return (0);
 	}
 	SLIST_INIT(&workq);
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (pfr_skip_table(filter, p, flags))
 			continue;
 		if (n-- <= 0)
@@ -1504,7 +1504,7 @@ pfr_clr_tstats(struct pfr_table *tbl, int size, int *nzero, int flags)
 			return (EFAULT);
 		if (pfr_validate_table(&key.pfrkt_t, 0, 0))
 			return (EINVAL);
-		p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+		p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 		if (p != NULL) {
 			SLIST_INSERT_HEAD(&workq, p, pfrkt_workq);
 			xzero++;
@@ -1539,7 +1539,7 @@ pfr_set_tflags(struct pfr_table *tbl, int size, int setflag, int clrflag,
 		if (pfr_validate_table(&key.pfrkt_t, 0,
 		    flags & PFR_FLAG_USERIOCTL))
 			return (EINVAL);
-		p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+		p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 		if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) {
 			p->pfrkt_nflags = (p->pfrkt_flags | setflag) &
 			    ~clrflag;
@@ -1582,7 +1582,7 @@ pfr_ina_begin(struct pfr_table *trs, u_int32_t *ticket, int *ndel, int flags)
 	if (rs == NULL)
 		return (ENOMEM);
 	SLIST_INIT(&workq);
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
 		    pfr_skip_table(trs, p, 0))
 			continue;
@@ -1625,7 +1625,7 @@ pfr_ina_define(struct pfr_table *tbl, struct pfr_addr *addr, int size,
 		return (EBUSY);
 	tbl->pfrt_flags |= PFR_TFLAG_INACTIVE;
 	SLIST_INIT(&tableq);
-	kt = RB_FIND(pfr_ktablehead, &pfr_ktables, (struct pfr_ktable *)tbl);
+	kt = RBT_FIND(pfr_ktablehead, &pfr_ktables, (struct pfr_ktable *)tbl);
 	if (kt == NULL) {
 		kt = pfr_create_ktable(tbl, 0, 1,
 		    !(flags & PFR_FLAG_USERIOCTL));
@@ -1639,7 +1639,7 @@ pfr_ina_define(struct pfr_table *tbl, struct pfr_addr *addr, int size,
 		/* find or create root table */
 		bzero(&key, sizeof(key));
 		strlcpy(key.pfrkt_name, tbl->pfrt_name, sizeof(key.pfrkt_name));
-		rt = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+		rt = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
 		if (rt != NULL) {
 			kt->pfrkt_root = rt;
 			goto _skip;
@@ -1721,7 +1721,7 @@ pfr_ina_rollback(struct pfr_table *trs, u_int32_t ticket, int *ndel, int flags)
 	if (rs == NULL || !rs->topen || ticket != rs->tticket)
 		return (0);
 	SLIST_INIT(&workq);
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
 		    pfr_skip_table(trs, p, 0))
 			continue;
@@ -1755,7 +1755,7 @@ pfr_ina_commit(struct pfr_table *trs, u_int32_t ticket, int *nadd,
 		return (EBUSY);
 
 	SLIST_INIT(&workq);
-	RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+	RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
 		if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
 		    pfr_skip_table(trs, p, 0))
 			continue;
@@ -1928,7 +1928,7 @@ pfr_insert_ktables(struct pfr_ktableworkq *workq)
 void
 pfr_insert_ktable(struct pfr_ktable *kt)
 {
-	RB_INSERT(pfr_ktablehead, &pfr_ktables, kt);
+	RBT_INSERT(pfr_ktablehead, &pfr_ktables, kt);
 	pfr_ktable_cnt++;
 	if (kt->pfrkt_root != NULL)
 		if (!kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR]++)
@@ -1959,7 +1959,7 @@ pfr_setflags_ktable(struct pfr_ktable *kt, int newf)
 	if (!(newf & PFR_TFLAG_ACTIVE))
 		newf &= ~PFR_TFLAG_USRMASK;
 	if (!(newf & PFR_TFLAG_SETMASK)) {
-		RB_REMOVE(pfr_ktablehead, &pfr_ktables, kt);
+		RBT_REMOVE(pfr_ktablehead, &pfr_ktables, kt);
 		if (kt->pfrkt_root != NULL)
 			if (!--kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR])
 				pfr_setflags_ktable(kt->pfrkt_root,
@@ -2082,7 +2082,7 @@ pfr_destroy_ktable(struct pfr_ktable *kt, int flushaddr)
 }
 
 int
-pfr_ktable_compare(struct pfr_ktable *p, struct pfr_ktable *q)
+pfr_ktable_compare(const struct pfr_ktable *p, const struct pfr_ktable *q)
 {
 	int d;
 
@@ -2095,7 +2095,7 @@ struct pfr_ktable *
 pfr_lookup_table(struct pfr_table *tbl)
 {
 	/* struct pfr_ktable start like a struct pfr_table */
-	return (RB_FIND(pfr_ktablehead, &pfr_ktables,
+	return (RBT_FIND(pfr_ktablehead, &pfr_ktables,
 	    (struct pfr_ktable *)tbl));
 }
 
diff --git a/sys/net/pfvar.h b/sys/net/pfvar.h
index 855d39228bc..7efc398aa60 100644
--- a/sys/net/pfvar.h
+++ b/sys/net/pfvar.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pfvar.h,v 1.438 2016/09/03 17:11:40 sashan Exp $ */
+/*	$OpenBSD: pfvar.h,v 1.439 2016/09/27 02:51:12 dlg Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -619,7 +619,7 @@ SLIST_HEAD(pf_rule_slist, pf_rule_item);
 enum pf_sn_types { PF_SN_NONE, PF_SN_NAT, PF_SN_RDR, PF_SN_ROUTE, PF_SN_MAX };
 
 struct pf_src_node {
-	RB_ENTRY(pf_src_node)	 entry;
+	RBT_ENTRY(pf_src_node)	 entry;
 	struct pf_addr		 addr;
 	struct pf_addr		 raddr;
 	union pf_rule_ptr	 rule;
@@ -682,7 +682,7 @@ struct pf_state_peer {
 
 TAILQ_HEAD(pf_state_queue, pf_state);
 
-/* keep synced with struct pf_state_key, used in RB_FIND */
+/* keep synced with struct pf_state_key, used in RBT_FIND */
 struct pf_state_key_cmp {
 	struct pf_addr	 addr[2];
 	u_int16_t	 port[2];
@@ -705,7 +705,7 @@ struct pf_state_key {
 	sa_family_t	 af;
 	u_int8_t	 proto;
 
-	RB_ENTRY(pf_state_key)	 entry;
+	RBT_ENTRY(pf_state_key)	 entry;
 	struct pf_statelisthead	 states;
 	struct pf_state_key	*reverse;
 	struct inpcb		*inp;
@@ -716,7 +716,7 @@ struct pf_state_key {
 	((key[PF_SK_WIRE]->af != key[PF_SK_STACK]->af) &&	\
 	 (key[PF_SK_WIRE]->af != (family)))
 
-/* keep synced with struct pf_state, used in RB_FIND */
+/* keep synced with struct pf_state, used in RBT_FIND */
 struct pf_state_cmp {
 	u_int64_t		 id;
 	u_int32_t		 creatorid;
@@ -732,7 +732,7 @@ struct pf_state {
 
 	TAILQ_ENTRY(pf_state)	 sync_list;
 	TAILQ_ENTRY(pf_state)	 entry_list;
-	RB_ENTRY(pf_state)	 entry_id;
+	RBT_ENTRY(pf_state)	 entry_id;
 	struct pf_state_peer	 src;
 	struct pf_state_peer	 dst;
 	struct pf_rule_slist	 match_rules;
@@ -916,11 +916,11 @@ struct pf_ruleset {
 	int			 topen;
 };
 
-RB_HEAD(pf_anchor_global, pf_anchor);
-RB_HEAD(pf_anchor_node, pf_anchor);
+RBT_HEAD(pf_anchor_global, pf_anchor);
+RBT_HEAD(pf_anchor_node, pf_anchor);
 struct pf_anchor {
-	RB_ENTRY(pf_anchor)	 entry_global;
-	RB_ENTRY(pf_anchor)	 entry_node;
+	RBT_ENTRY(pf_anchor)	 entry_global;
+	RBT_ENTRY(pf_anchor)	 entry_node;
 	struct pf_anchor	*parent;
 	struct pf_anchor_node	 children;
 	char			 name[PF_ANCHOR_NAME_SIZE];
@@ -929,8 +929,8 @@ struct pf_anchor {
 	int			 refcnt;	/* anchor rules */
 	int			 match;
 };
-RB_PROTOTYPE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare)
-RB_PROTOTYPE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare)
+RBT_PROTOTYPE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare)
+RBT_PROTOTYPE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare)
 
 #define PF_RESERVED_ANCHOR	"_pf"
 
@@ -1080,10 +1080,10 @@ struct pfr_kentry_all {
 #define pfrke_rkif	u.kr.kif
 
 SLIST_HEAD(pfr_ktableworkq, pfr_ktable);
-RB_HEAD(pfr_ktablehead, pfr_ktable);
+RBT_HEAD(pfr_ktablehead, pfr_ktable);
 struct pfr_ktable {
 	struct pfr_tstats	 pfrkt_ts;
-	RB_ENTRY(pfr_ktable)	 pfrkt_tree;
+	RBT_ENTRY(pfr_ktable)	 pfrkt_tree;
 	SLIST_ENTRY(pfr_ktable)	 pfrkt_workq;
 	struct radix_node_head	*pfrkt_ip4;
 	struct radix_node_head	*pfrkt_ip6;
@@ -1109,19 +1109,19 @@ struct pfr_ktable {
 #define pfrkt_nomatch	pfrkt_ts.pfrts_nomatch
 #define pfrkt_tzero	pfrkt_ts.pfrts_tzero
 
-RB_HEAD(pf_state_tree, pf_state_key);
-RB_PROTOTYPE(pf_state_tree, pf_state_key, entry, pf_state_compare_key)
+RBT_HEAD(pf_state_tree, pf_state_key);
+RBT_PROTOTYPE(pf_state_tree, pf_state_key, entry, pf_state_compare_key)
 
-RB_HEAD(pf_state_tree_ext_gwy, pf_state_key);
-RB_PROTOTYPE(pf_state_tree_ext_gwy, pf_state_key,
+RBT_HEAD(pf_state_tree_ext_gwy, pf_state_key);
+RBT_PROTOTYPE(pf_state_tree_ext_gwy, pf_state_key,
     entry_ext_gwy, pf_state_compare_ext_gwy)
 
-RB_HEAD(pfi_ifhead, pfi_kif);
+RBT_HEAD(pfi_ifhead, pfi_kif);
 
 /* state tables */
 extern struct pf_state_tree	 pf_statetbl;
 
-/* keep synced with pfi_kif, used in RB_FIND */
+/* keep synced with pfi_kif, used in RBT_FIND */
 struct pfi_kif_cmp {
 	char				 pfik_name[IFNAMSIZ];
 };
@@ -1131,7 +1131,7 @@ struct ifg_group;
 
 struct pfi_kif {
 	char				 pfik_name[IFNAMSIZ];
-	RB_ENTRY(pfi_kif)		 pfik_tree;
+	RBT_ENTRY(pfi_kif)		 pfik_tree;
 	u_int64_t			 pfik_packets[2][2][2];
 	u_int64_t			 pfik_bytes[2][2][2];
 	time_t				 pfik_tzero;
@@ -1641,12 +1641,12 @@ struct pfioc_iface {
 #define DIOCGETQSTATS	_IOWR('D', 96, struct pfioc_qstats)
 
 #ifdef _KERNEL
-RB_HEAD(pf_src_tree, pf_src_node);
-RB_PROTOTYPE(pf_src_tree, pf_src_node, entry, pf_src_compare);
+RBT_HEAD(pf_src_tree, pf_src_node);
+RBT_PROTOTYPE(pf_src_tree, pf_src_node, entry, pf_src_compare);
 extern struct pf_src_tree tree_src_tracking;
 
-RB_HEAD(pf_state_tree_id, pf_state);
-RB_PROTOTYPE(pf_state_tree_id, pf_state,
+RBT_HEAD(pf_state_tree_id, pf_state);
+RBT_PROTOTYPE(pf_state_tree_id, pf_state,
     entry_id, pf_state_compare_id);
 extern struct pf_state_tree_id tree_id;
 extern struct pf_state_queue state_list;
@@ -1842,8 +1842,8 @@ void		 pf_tag2tagname(u_int16_t, char *);
 void		 pf_tag_ref(u_int16_t);
 void		 pf_tag_unref(u_int16_t);
 void		 pf_tag_packet(struct mbuf *, int, int);
-int		 pf_addr_compare(struct pf_addr *, struct pf_addr *,
-		    sa_family_t);
+int		 pf_addr_compare(const struct pf_addr *,
+		    const struct pf_addr *, sa_family_t);
 
 extern struct pf_status	pf_status;
 extern struct pool	pf_frent_pl, pf_frag_pl;