this moves 80211 over to using the function version of red-black
trees. it gives us back the 2.5k of code that RB_GENERATE adds.
ok?
Index: ieee80211_ioctl.c
===================================================================
RCS file: /cvs/src/sys/net80211/ieee80211_ioctl.c,v
retrieving revision 1.43
diff -u -p -r1.43 ieee80211_ioctl.c
--- ieee80211_ioctl.c 31 Aug 2016 13:33:52 -0000 1.43
+++ ieee80211_ioctl.c 6 Sep 2016 03:46:37 -0000
@@ -754,7 +754,7 @@ ieee80211_ioctl(struct ifnet *ifp, u_lon
case SIOCG80211ALLNODES:
na = (struct ieee80211_nodereq_all *)data;
na->na_nodes = i = 0;
- ni = RB_MIN(ieee80211_tree, &ic->ic_tree);
+ ni = RBT_MIN(ieee80211_tree, &ic->ic_tree);
while (ni && na->na_size >=
i + sizeof(struct ieee80211_nodereq)) {
ieee80211_node2req(ic, ni, &nrbuf);
@@ -764,7 +764,7 @@ ieee80211_ioctl(struct ifnet *ifp, u_lon
break;
i += sizeof(struct ieee80211_nodereq);
na->na_nodes++;
- ni = RB_NEXT(ieee80211_tree, &ic->ic_tree, ni);
+ ni = RBT_NEXT(ieee80211_tree, ni);
}
break;
case SIOCG80211FLAGS:
Index: ieee80211_node.c
===================================================================
RCS file: /cvs/src/sys/net80211/ieee80211_node.c,v
retrieving revision 1.104
diff -u -p -r1.104 ieee80211_node.c
--- ieee80211_node.c 17 Aug 2016 09:42:03 -0000 1.104
+++ ieee80211_node.c 6 Sep 2016 03:46:37 -0000
@@ -92,9 +92,9 @@ ieee80211_inact_timeout(void *arg)
int s;
s = splnet();
- for (ni = RB_MIN(ieee80211_tree, &ic->ic_tree);
+ for (ni = RBT_MIN(ieee80211_tree, &ic->ic_tree);
ni != NULL; ni = next_ni) {
- next_ni = RB_NEXT(ieee80211_tree, &ic->ic_tree, ni);
+ next_ni = RBT_NEXT(ieee80211_tree, ni);
if (ni->ni_refcnt > 0)
continue;
if (ni->ni_inact < IEEE80211_INACT_MAX)
@@ -123,7 +123,7 @@ ieee80211_node_attach(struct ifnet *ifp)
int size;
#endif
- RB_INIT(&ic->ic_tree);
+ RBT_INIT(ieee80211_tree, &ic->ic_tree);
ic->ic_node_alloc = ieee80211_node_alloc;
ic->ic_node_free = ieee80211_node_free;
ic->ic_node_copy = ieee80211_node_copy;
@@ -538,7 +538,7 @@ ieee80211_end_scan(struct ifnet *ifp)
if (ic->ic_scan_count)
ic->ic_flags &= ~IEEE80211_F_ASCAN;
- ni = RB_MIN(ieee80211_tree, &ic->ic_tree);
+ ni = RBT_MIN(ieee80211_tree, &ic->ic_tree);
#ifndef IEEE80211_STA_ONLY
if (ic->ic_opmode == IEEE80211_M_HOSTAP) {
@@ -554,7 +554,7 @@ ieee80211_end_scan(struct ifnet *ifp)
* channel from the active set.
*/
memset(occupied, 0, sizeof(occupied));
- RB_FOREACH(ni, ieee80211_tree, &ic->ic_tree)
+ RBT_FOREACH(ni, ieee80211_tree, &ic->ic_tree)
setbit(occupied, ieee80211_chan2ieee(ic, ni->ni_chan));
for (i = 0; i < IEEE80211_CHAN_MAX; i++)
if (isset(ic->ic_chan_active, i) && isclr(occupied, i))
@@ -611,7 +611,7 @@ ieee80211_end_scan(struct ifnet *ifp)
selbs = NULL;
for (; ni != NULL; ni = nextbs) {
- nextbs = RB_NEXT(ieee80211_tree, &ic->ic_tree, ni);
+ nextbs = RBT_NEXT(ieee80211_tree, ni);
if (ni->ni_fails) {
/*
* The configuration of the access points may change
@@ -807,7 +807,7 @@ ieee80211_setup_node(struct ieee80211com
timeout_set(&ni->ni_sa_query_to, ieee80211_sa_query_timeout, ni);
#endif
s = splnet();
- RB_INSERT(ieee80211_tree, &ic->ic_tree, ni);
+ RBT_INSERT(ieee80211_tree, &ic->ic_tree, ni);
ic->ic_nnodes++;
splx(s);
}
@@ -845,14 +845,14 @@ ieee80211_find_node(struct ieee80211com
struct ieee80211_node *ni;
int cmp;
- /* similar to RB_FIND except we compare keys, not nodes */
- ni = RB_ROOT(&ic->ic_tree);
+ /* similar to RBT_FIND except we compare keys, not nodes */
+ ni = RBT_ROOT(ieee80211_tree, &ic->ic_tree);
while (ni != NULL) {
cmp = memcmp(macaddr, ni->ni_macaddr, IEEE80211_ADDR_LEN);
if (cmp < 0)
- ni = RB_LEFT(ni, ni_node);
+ ni = RBT_LEFT(ieee80211_tree, ni);
else if (cmp > 0)
- ni = RB_RIGHT(ni, ni_node);
+ ni = RBT_RIGHT(ieee80211_tree, ni);
else
break;
}
@@ -1112,7 +1112,7 @@ ieee80211_free_node(struct ieee80211com
IEEE80211_AID_CLR(ni->ni_associd, ic->ic_aid_bitmap);
#endif
ieee80211_ba_del(ni);
- RB_REMOVE(ieee80211_tree, &ic->ic_tree, ni);
+ RBT_REMOVE(ieee80211_tree, &ic->ic_tree, ni);
ic->ic_nnodes--;
#ifndef IEEE80211_STA_ONLY
if (mq_purge(&ni->ni_savedq) > 0) {
@@ -1147,7 +1147,7 @@ ieee80211_free_allnodes(struct ieee80211
DPRINTF(("freeing all nodes\n"));
s = splnet();
- while ((ni = RB_MIN(ieee80211_tree, &ic->ic_tree)) != NULL)
+ while ((ni = RBT_MIN(ieee80211_tree, &ic->ic_tree)) != NULL)
ieee80211_free_node(ic, ni);
splx(s);
@@ -1162,9 +1162,9 @@ ieee80211_clean_cached(struct ieee80211c
int s;
s = splnet();
- for (ni = RB_MIN(ieee80211_tree, &ic->ic_tree);
+ for (ni = RBT_MIN(ieee80211_tree, &ic->ic_tree);
ni != NULL; ni = next_ni) {
- next_ni = RB_NEXT(ieee80211_tree, &ic->ic_tree, ni);
+ next_ni = RBT_NEXT(ieee80211_tree, ni);
if (ni->ni_state == IEEE80211_STA_CACHE)
ieee80211_free_node(ic, ni);
}
@@ -1195,9 +1195,9 @@ ieee80211_clean_nodes(struct ieee80211co
#endif
s = splnet();
- for (ni = RB_MIN(ieee80211_tree, &ic->ic_tree);
+ for (ni = RBT_MIN(ieee80211_tree, &ic->ic_tree);
ni != NULL; ni = next_ni) {
- next_ni = RB_NEXT(ieee80211_tree, &ic->ic_tree, ni);
+ next_ni = RBT_NEXT(ieee80211_tree, ni);
if (!cache_timeout && ic->ic_nnodes < ic->ic_max_nnodes)
break;
if (ni->ni_scangen == gen) /* previously handled */
@@ -1282,7 +1282,7 @@ ieee80211_iterate_nodes(struct ieee80211
int s;
s = splnet();
- RB_FOREACH(ni, ieee80211_tree, &ic->ic_tree)
+ RBT_FOREACH(ni, ieee80211_tree, &ic->ic_tree)
(*f)(arg, ni);
splx(s);
}
@@ -1877,4 +1877,4 @@ ieee80211_node_cmp(const struct ieee8021
/*
* Generate red-black tree function logic
*/
-RB_GENERATE(ieee80211_tree, ieee80211_node, ni_node, ieee80211_node_cmp);
+RBT_GENERATE(ieee80211_tree, ieee80211_node, ni_node, ieee80211_node_cmp);
Index: ieee80211_node.h
===================================================================
RCS file: /cvs/src/sys/net80211/ieee80211_node.h,v
retrieving revision 1.60
diff -u -p -r1.60 ieee80211_node.h
--- ieee80211_node.h 28 Apr 2016 08:18:10 -0000 1.60
+++ ieee80211_node.h 6 Sep 2016 03:46:37 -0000
@@ -162,7 +162,7 @@ struct ieee80211_rx_ba {
* the ieee80211com structure.
*/
struct ieee80211_node {
- RB_ENTRY(ieee80211_node) ni_node;
+ RBT_ENTRY(ieee80211_node) ni_node;
struct ieee80211com *ni_ic; /* back-pointer */
@@ -284,7 +284,7 @@ struct ieee80211_node {
#define IEEE80211_NODE_SA_QUERY_FAILED 0x1000 /* last SA Query failed */
};
-RB_HEAD(ieee80211_tree, ieee80211_node);
+RBT_HEAD(ieee80211_tree, ieee80211_node);
static __inline void
ieee80211_node_incref(struct ieee80211_node *ni)
@@ -379,6 +379,6 @@ extern void ieee80211_set_tim(struct iee
extern int ieee80211_node_cmp(const struct ieee80211_node *,
const struct ieee80211_node *);
-RB_PROTOTYPE(ieee80211_tree, ieee80211_node, ni_node, ieee80211_node_cmp);
+RBT_PROTOTYPE(ieee80211_tree, ieee80211_node, ni_node, ieee80211_node_cmp);
#endif /* _NET80211_IEEE80211_NODE_H_ */
Index: ieee80211_proto.c
===================================================================
RCS file: /cvs/src/sys/net80211/ieee80211_proto.c,v
retrieving revision 1.68
diff -u -p -r1.68 ieee80211_proto.c
--- ieee80211_proto.c 20 Jul 2016 15:40:27 -0000 1.68
+++ ieee80211_proto.c 6 Sep 2016 03:46:37 -0000
@@ -847,7 +847,7 @@ ieee80211_newstate(struct ieee80211com *
#ifndef IEEE80211_STA_ONLY
case IEEE80211_M_HOSTAP:
s = splnet();
- RB_FOREACH(ni, ieee80211_tree, &ic->ic_tree) {
+ RBT_FOREACH(ni, ieee80211_tree, &ic->ic_tree) {
if (ni->ni_state != IEEE80211_STA_ASSOC)
continue;
IEEE80211_SEND_MGMT(ic, ni,
@@ -873,7 +873,7 @@ ieee80211_newstate(struct ieee80211com *
#ifndef IEEE80211_STA_ONLY
case IEEE80211_M_HOSTAP:
s = splnet();
- RB_FOREACH(ni, ieee80211_tree, &ic->ic_tree) {
+ RBT_FOREACH(ni, ieee80211_tree, &ic->ic_tree) {
IEEE80211_SEND_MGMT(ic, ni,
IEEE80211_FC0_SUBTYPE_DEAUTH,
IEEE80211_REASON_AUTH_LEAVE);
