--- /dev/null Sun Oct 2 19:30:21 2016 +++ lib/libadt/Makefile Sat Oct 1 23:01:52 2016 @@ -0,0 +1,20 @@ +# $OpenBSD: Makefile,v 1.43 2016/03/30 06:38:42 jmc Exp $ + +.include + +LIB= adt +MAN= + +# use more warnings than defined in bsd.own.mk +CDIAGFLAGS+= -Wbad-function-cast +CDIAGFLAGS+= -Wcast-align +CDIAGFLAGS+= -Wcast-qual +CDIAGFLAGS+= -Wextra +CDIAGFLAGS+= -Wmissing-declarations +CDIAGFLAGS+= -Wuninitialized +CDIAGFLAGS+= -Wno-unused-parameter + +.PATH: ${.CURDIR}/../../sys/kern +SRCS= subr_tree.c + +.include Index: sbin/pfctl/Makefile =================================================================== RCS file: /cvs/src/sbin/pfctl/Makefile,v retrieving revision 1.21 diff -u -p -r1.21 Makefile --- sbin/pfctl/Makefile 19 Apr 2014 14:22:32 -0000 1.21 +++ sbin/pfctl/Makefile 2 Oct 2016 09:45:47 -0000 @@ -12,7 +12,7 @@ MAN= pfctl.8 # Ruleset and Anchor handling .PATH: ${.CURDIR}/../../sys/net -LDADD+= -lm -DPADD+= ${LIBM} +LDADD+= -lm -ladt +DPADD+= ${LIBM} ${LIBADT} .include Index: sbin/pfctl/pfctl.c =================================================================== RCS file: /cvs/src/sbin/pfctl/pfctl.c,v retrieving revision 1.337 diff -u -p -r1.337 pfctl.c --- sbin/pfctl/pfctl.c 3 Sep 2016 21:30:49 -0000 1.337 +++ sbin/pfctl/pfctl.c 2 Oct 2016 09:45:47 -0000 @@ -1450,7 +1450,7 @@ pfctl_rules(int dev, char *filename, int char *p; bzero(&pf, sizeof(pf)); - RB_INIT(&pf_anchors); + RBT_INIT(pf_anchor_global, &pf_anchors); memset(&pf_main_anchor, 0, sizeof(pf_main_anchor)); pf_init_ruleset(&pf_main_anchor.ruleset); pf_main_anchor.ruleset.anchor = &pf_main_anchor; Index: sys/kern/subr_tree.c =================================================================== RCS file: /cvs/src/sys/kern/subr_tree.c,v retrieving revision 1.6 diff -u -p -r1.6 subr_tree.c --- sys/kern/subr_tree.c 20 Sep 2016 01:11:27 -0000 1.6 +++ sys/kern/subr_tree.c 2 Oct 2016 09:45:47 -0000 @@ -41,13 +41,13 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ -#include -#include +#include +//#include static inline void * rb_n2e(const struct rb_type *t, void *node) { - caddr_t addr = (caddr_t)node; + unsigned long addr = (unsigned long)node; return ((void *)(addr + t->t_offset)); } @@ -55,11 +55,14 @@ rb_n2e(const struct rb_type *t, void *no static inline void * rb_e2n(const struct rb_type *t, struct rb_entry *rbe) { - caddr_t addr = (caddr_t)rbe; + unsigned long addr = (unsigned long)rbe; return ((void *)(addr - t->t_offset)); } +#define RBE_BLACK 0 +#define RBE_RED 1 + #define RBE_LEFT(_rbe) (_rbe)->rbt_left #define RBE_RIGHT(_rbe) (_rbe)->rbt_right #define RBE_PARENT(_rbe) (_rbe)->rbt_parent @@ -72,14 +75,14 @@ rbe_set(struct rb_entry *rbe, struct rb_ { RBE_PARENT(rbe) = parent; RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; - RBE_COLOR(rbe) = RB_RED; + RBE_COLOR(rbe) = RBE_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; + RBE_COLOR(black) = RBE_BLACK; + RBE_COLOR(red) = RBE_RED; } static inline void @@ -170,13 +173,13 @@ rbe_insert_color(const struct rb_type *t struct rb_entry *parent, *gparent, *tmp; while ((parent = RBE_PARENT(rbe)) != NULL && - RBE_COLOR(parent) == RB_RED) { + RBE_COLOR(parent) == RBE_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; + if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) { + RBE_COLOR(tmp) = RBE_BLACK; rbe_set_blackred(parent, gparent); rbe = gparent; continue; @@ -193,8 +196,8 @@ rbe_insert_color(const struct rb_type *t rbe_rotate_right(t, rbt, gparent); } else { tmp = RBE_LEFT(gparent); - if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { - RBE_COLOR(tmp) = RB_BLACK; + if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) { + RBE_COLOR(tmp) = RBE_BLACK; rbe_set_blackred(parent, gparent); rbe = gparent; continue; @@ -212,7 +215,7 @@ rbe_insert_color(const struct rb_type *t } } - RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK; + RBE_COLOR(RBH_ROOT(rbt)) = RBE_BLACK; } static inline void @@ -221,40 +224,40 @@ rbe_remove_color(const struct rb_type *t { struct rb_entry *tmp; - while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + while ((rbe == NULL || RBE_COLOR(rbe) == RBE_BLACK) && rbe != RBH_ROOT(rbt)) { if (RBE_LEFT(parent) == rbe) { tmp = RBE_RIGHT(parent); - if (RBE_COLOR(tmp) == RB_RED) { + if (RBE_COLOR(tmp) == RBE_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_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) && (RBE_RIGHT(tmp) == NULL || - RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { - RBE_COLOR(tmp) = RB_RED; + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) { + RBE_COLOR(tmp) = RBE_RED; rbe = parent; parent = RBE_PARENT(rbe); } else { if (RBE_RIGHT(tmp) == NULL || - RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK) { struct rb_entry *oleft; oleft = RBE_LEFT(tmp); if (oleft != NULL) - RBE_COLOR(oleft) = RB_BLACK; + RBE_COLOR(oleft) = RBE_BLACK; - RBE_COLOR(tmp) = RB_RED; + RBE_COLOR(tmp) = RBE_RED; rbe_rotate_right(t, rbt, tmp); tmp = RBE_RIGHT(parent); } RBE_COLOR(tmp) = RBE_COLOR(parent); - RBE_COLOR(parent) = RB_BLACK; + RBE_COLOR(parent) = RBE_BLACK; if (RBE_RIGHT(tmp)) - RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK; + RBE_COLOR(RBE_RIGHT(tmp)) = RBE_BLACK; rbe_rotate_left(t, rbt, parent); rbe = RBH_ROOT(rbt); @@ -262,37 +265,37 @@ rbe_remove_color(const struct rb_type *t } } else { tmp = RBE_LEFT(parent); - if (RBE_COLOR(tmp) == RB_RED) { + if (RBE_COLOR(tmp) == RBE_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_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) && (RBE_RIGHT(tmp) == NULL || - RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { - RBE_COLOR(tmp) = RB_RED; + RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) { + RBE_COLOR(tmp) = RBE_RED; rbe = parent; parent = RBE_PARENT(rbe); } else { if (RBE_LEFT(tmp) == NULL || - RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) { struct rb_entry *oright; oright = RBE_RIGHT(tmp); if (oright != NULL) - RBE_COLOR(oright) = RB_BLACK; + RBE_COLOR(oright) = RBE_BLACK; - RBE_COLOR(tmp) = RB_RED; + RBE_COLOR(tmp) = RBE_RED; rbe_rotate_left(t, rbt, tmp); tmp = RBE_LEFT(parent); } RBE_COLOR(tmp) = RBE_COLOR(parent); - RBE_COLOR(parent) = RB_BLACK; + RBE_COLOR(parent) = RBE_BLACK; if (RBE_LEFT(tmp) != NULL) - RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK; + RBE_COLOR(RBE_LEFT(tmp)) = RBE_BLACK; rbe_rotate_right(t, rbt, parent); rbe = RBH_ROOT(rbt); @@ -302,7 +305,7 @@ rbe_remove_color(const struct rb_type *t } if (rbe != NULL) - RBE_COLOR(rbe) = RB_BLACK; + RBE_COLOR(rbe) = RBE_BLACK; } static inline struct rb_entry * @@ -381,7 +384,7 @@ rbe_remove(const struct rb_type *t, stru } else RBH_ROOT(rbt) = child; color: - if (color == RB_BLACK) + if (color == RBE_BLACK) rbe_remove_color(t, rbt, parent, child); return (old); Index: sys/net/if_pfsync.c =================================================================== RCS file: /cvs/src/sys/net/if_pfsync.c,v retrieving revision 1.234 diff -u -p -r1.234 if_pfsync.c --- sys/net/if_pfsync.c 27 Sep 2016 04:57:17 -0000 1.234 +++ sys/net/if_pfsync.c 2 Oct 2016 09:45:47 -0000 @@ -747,8 +749,8 @@ pfsync_in_clr(caddr_t buf, int len, int (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); Index: sys/net/pf.c =================================================================== RCS file: /cvs/src/sys/net/pf.c,v retrieving revision 1.987 diff -u -p -r1.987 pf.c --- sys/net/pf.c 27 Sep 2016 04:57:17 -0000 1.987 +++ sys/net/pf.c 2 Oct 2016 09:45:47 -0000 @@ -293,11 +293,12 @@ struct pf_pool_limit pf_pool_limits[PF_L 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, struc } 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 ** 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 ** 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 *s 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, /* 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 } 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 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, 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, str 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 * { 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, struc } 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_cm 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 p 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 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); Index: sys/net/pf_if.c =================================================================== RCS file: /cvs/src/sys/net/pf_if.c,v retrieving revision 1.86 diff -u -p -r1.86 pf_if.c --- sys/net/pf_if.c 27 Sep 2016 04:57:17 -0000 1.86 +++ sys/net/pf_if.c 2 Oct 2016 09:45:47 -0000 @@ -72,12 +72,12 @@ void pfi_table_update(struct pfr_ktabl 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 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, stru 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, stru } 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 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 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 flag 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 fl 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); } Index: sys/net/pf_ioctl.c =================================================================== RCS file: /cvs/src/sys/net/pf_ioctl.c,v retrieving revision 1.302 diff -u -p -r1.302 pf_ioctl.c --- sys/net/pf_ioctl.c 27 Sep 2016 04:57:17 -0000 1.302 +++ sys/net/pf_ioctl.c 2 Oct 2016 09:45:47 -0000 @@ -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 a 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 a 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 a 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 a 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 a 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 a 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 a 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 a (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 a &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; Index: sys/net/pf_lb.c =================================================================== RCS file: /cvs/src/sys/net/pf_lb.c,v retrieving revision 1.57 diff -u -p -r1.57 pf_lb.c --- sys/net/pf_lb.c 27 Sep 2016 04:57:17 -0000 1.57 +++ sys/net/pf_lb.c 2 Oct 2016 09:45:47 -0000 @@ -275,7 +275,7 @@ pf_map_addr_sticky(sa_family_t af, struc 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, struc } 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]); Index: sys/net/pf_norm.c =================================================================== RCS file: /cvs/src/sys/net/pf_norm.c,v retrieving revision 1.194 diff -u -p -r1.194 pf_norm.c --- sys/net/pf_norm.c 27 Sep 2016 04:57:17 -0000 1.194 +++ sys/net/pf_norm.c 2 Oct 2016 09:45:47 -0000 @@ -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 *fra { 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 { 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_cm 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 */ Index: sys/net/pf_ruleset.c =================================================================== RCS file: /cvs/src/sys/net/pf_ruleset.c,v retrieving revision 1.14 diff -u -p -r1.14 pf_ruleset.c --- sys/net/pf_ruleset.c 27 Sep 2016 04:57:17 -0000 1.14 +++ sys/net/pf_ruleset.c 2 Oct 2016 09:45:47 -0000 @@ -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 *pa 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 *pa 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 *pa } 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_rul 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_rul !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) Index: sys/net/pf_table.c =================================================================== RCS file: /cvs/src/sys/net/pf_table.c,v retrieving revision 1.120 diff -u -p -r1.120 pf_table.c --- sys/net/pf_table.c 27 Sep 2016 04:57:17 -0000 1.120 +++ sys/net/pf_table.c 2 Oct 2016 09:45:47 -0000 @@ -177,8 +177,8 @@ struct pfr_ktable *pfr_create_ktable(str 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, 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, in 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, in /* 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, in 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, *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, 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, in 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, in 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_i 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, st 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, st /* 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, 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_ 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_ktablework 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 *k 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 -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)); } Index: sys/net/pfvar.h =================================================================== RCS file: /cvs/src/sys/net/pfvar.h,v retrieving revision 1.440 diff -u -p -r1.440 pfvar.h --- sys/net/pfvar.h 27 Sep 2016 04:57:17 -0000 1.440 +++ sys/net/pfvar.h 2 Oct 2016 09:45:47 -0000 @@ -35,7 +35,7 @@ #define _NET_PFVAR_H_ #include -#include +#include #include #include #include @@ -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,9 @@ 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 +1081,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 +1110,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 +1132,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 +1642,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 +1843,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; Index: sys/sys/cdefs.h =================================================================== RCS file: /cvs/src/sys/sys/cdefs.h,v retrieving revision 1.39 diff -u -p -r1.39 cdefs.h --- sys/sys/cdefs.h 18 Apr 2014 11:51:17 -0000 1.39 +++ sys/sys/cdefs.h 2 Oct 2016 09:45:47 -0000 @@ -87,6 +87,15 @@ #endif /* !__GNUC__ */ #endif /* !(__STDC__ || __cplusplus) */ +/* Macros for calculating the offset of a field */ +#ifndef __offsetof +#if __GNUC_PREREQ__(4, 0) +#define __offsetof(s, e) __builtin_offsetof(s, e) +#else +#define __offsetof(s, e) ((size_t)&((s *)0)->e) +#endif +#endif + /* * GCC1 and some versions of GCC2 declare dead (non-returning) and * pure (no side effects) functions using "volatile" and "const"; Index: sys/sys/rbt.h =================================================================== RCS file: sys/sys/rbt.h diff -N sys/sys/rbt.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ sys/sys/rbt.h 2 Oct 2016 09:45:47 -0000 @@ -0,0 +1,219 @@ +/* $OpenBSD: tree.h,v 1.24 2016/09/15 06:07:22 dlg Exp $ */ + +/* + * Copyright (c) 2016 David Gwynne + * + * 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. + */ + +#ifndef _SYS_RBT_H_ +#define _SYS_RBT_H_ + +#include +#include + +#include + +static inline void +_rb_init(struct rb_tree *rbt) +{ + rbt->rbt_root = NULL; +} + +static inline int +_rb_empty(struct rb_tree *rbt) +{ + return (rbt->rbt_root == NULL); +} + +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_color(const struct rb_type *, void *); +void _rb_poison(const struct rb_type *, void *, unsigned long); +int _rb_check(const struct rb_type *, void *, unsigned long); + +#define RBT_INITIALIZER(_head) { { NULL } } + +#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RBT_TYPE; \ + \ +static inline void \ +_name##_RBT_INIT(struct _name *head) \ +{ \ + _rb_init(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ +{ \ + return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_FIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ +{ \ + return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_ROOT(struct _name *head) \ +{ \ + return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline int \ +_name##_RBT_EMPTY(struct _name *head) \ +{ \ + return _rb_empty(&head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MIN(struct _name *head) \ +{ \ + return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_MAX(struct _name *head) \ +{ \ + return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline struct _type * \ +_name##_RBT_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RBT_TYPE, elm); \ +} \ + \ +static inline void \ +_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RBT_TYPE, elm, poison); \ +} \ + \ +static inline int \ +_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RBT_TYPE, elm, poison); \ +} + +#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RBT_INFO = { \ + _name##_RBT_COMPARE, \ + _aug, \ + __offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO + +#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RBT_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) + +#define RBT_GENERATE(_name, _type, _field, _cmp) \ + RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) + +#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) +#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) +#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) +#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) +#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) +#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) +#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) +#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) +#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) +#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) +#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) +#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) +#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) +#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) +#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) +#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) + +#define RBT_FOREACH(_e, _name, _head) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_NEXT(_name, (_e))) + +#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) + +#define RBT_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RBT_PREV(_name, (_e))) + +#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RBT_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ + (_e) = (_n)) + +#endif /* _SYS_RBT_H_ */ Index: sys/sys/rbt_t.h =================================================================== RCS file: sys/sys/rbt_t.h diff -N sys/sys/rbt_t.h --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ sys/sys/rbt_t.h 2 Oct 2016 09:45:47 -0000 @@ -0,0 +1,46 @@ +/* $OpenBSD: tree.h,v 1.24 2016/09/15 06:07:22 dlg Exp $ */ + +/* + * Copyright (c) 2016 David Gwynne + * + * 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. + */ + +#ifndef _SYS_RBT_T_H_ +#define _SYS_RBT_T_H_ + +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 RBT_HEAD(_name, _type) \ +struct _name { \ + struct rb_tree rbh_root; \ +} + +#define RBT_ENTRY(_type) struct rb_entry + +#endif /* _SYS_RBT_T_H_ */ Index: sys/sys/tree.h =================================================================== RCS file: /cvs/src/sys/sys/tree.h,v retrieving revision 1.25 diff -u -p -r1.25 tree.h --- sys/sys/tree.h 26 Sep 2016 08:08:51 -0000 1.25 +++ sys/sys/tree.h 2 Oct 2016 09:45:47 -0000 @@ -748,239 +748,13 @@ name##_RB_MINMAX(struct name *head, int (x) = (y)) -/* - * Copyright (c) 2016 David Gwynne - * - * 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. - */ - -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 RBT_HEAD(_name, _type) \ -struct _name { \ - struct rb_tree rbh_root; \ -} - -#define RBT_ENTRY(_type) struct rb_entry +#include +//#include #ifdef _KERNEL -static inline void -_rb_init(struct rb_tree *rbt) -{ - rbt->rbt_root = NULL; -} - -static inline int -_rb_empty(struct rb_tree *rbt) -{ - return (rbt->rbt_root == NULL); -} - -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_color(const struct rb_type *, void *); -void _rb_poison(const struct rb_type *, void *, unsigned long); -int _rb_check(const struct rb_type *, void *, unsigned long); - -#define RBT_INITIALIZER(_head) { { NULL } } - -#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ -extern const struct rb_type *const _name##_RBT_TYPE; \ - \ -__unused static inline void \ -_name##_RBT_INIT(struct _name *head) \ -{ \ - _rb_init(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ -{ \ - return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ -{ \ - return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_FIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ -{ \ - return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_ROOT(struct _name *head) \ -{ \ - return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline int \ -_name##_RBT_EMPTY(struct _name *head) \ -{ \ - return _rb_empty(&head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MIN(struct _name *head) \ -{ \ - return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_MAX(struct _name *head) \ -{ \ - return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_NEXT(struct _type *elm) \ -{ \ - return _rb_next(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PREV(struct _type *elm) \ -{ \ - return _rb_prev(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_LEFT(struct _type *elm) \ -{ \ - return _rb_left(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_RIGHT(struct _type *elm) \ -{ \ - return _rb_right(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline struct _type * \ -_name##_RBT_PARENT(struct _type *elm) \ -{ \ - return _rb_parent(_name##_RBT_TYPE, elm); \ -} \ - \ -__unused static inline void \ -_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_poison(_name##_RBT_TYPE, elm, poison); \ -} \ - \ -__unused static inline int \ -_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ -{ \ - return _rb_check(_name##_RBT_TYPE, elm, poison); \ -} - -#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ -static int \ -_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ -{ \ - const struct _type *l = lptr, *r = rptr; \ - return _cmp(l, r); \ -} \ -static const struct rb_type _name##_RBT_INFO = { \ - _name##_RBT_COMPARE, \ - _aug, \ - offsetof(struct _type, _field), \ -}; \ -const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO - -#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ -static void \ -_name##_RBT_AUGMENT(void *ptr) \ -{ \ - struct _type *p = ptr; \ - return _aug(p); \ -} \ -RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) - -#define RBT_GENERATE(_name, _type, _field, _cmp) \ - RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) - -#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) -#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) -#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) -#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) -#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) -#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) -#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) -#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) -#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) -#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) -#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) -#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) -#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) -#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) -#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) -#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) - -#define RBT_FOREACH(_e, _name, _head) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_NEXT(_name, (_e))) - -#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MIN(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ - (_e) = (_n)) - -#define RBT_FOREACH_REVERSE(_e, _name, _head) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL; \ - (_e) = RBT_PREV(_name, (_e))) - -#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ - for ((_e) = RBT_MAX(_name, (_head)); \ - (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ - (_e) = (_n)) +#include +//#include #endif /* _KERNEL */ Index: usr.sbin/snmpd/snmpd.h =================================================================== RCS file: /cvs/src/usr.sbin/snmpd/snmpd.h,v retrieving revision 1.68 diff -u -p -r1.68 snmpd.h --- usr.sbin/snmpd/snmpd.h 25 Sep 2016 14:58:00 -0000 1.68 +++ usr.sbin/snmpd/snmpd.h 2 Oct 2016 09:45:48 -0000 @@ -20,6 +20,8 @@ #ifndef SNMPD_H #define SNMPD_H +#include + #include #include #include