From e3f2075749379ea50fffb8a4590e38627fa43f9e Mon Sep 17 00:00:00 2001 From: Reyk Floeter Date: Tue, 13 Sep 2005 12:11:05 +0000 Subject: replace the node hash table with a red-black tree. this fixes some bugs in the node table (like duplicate nodes in hostap mode), we get rid of possible hash collisions, and it simplifies the code. tested by many, ok damien@, jsg@ --- sys/net80211/ieee80211_node.h | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'sys/net80211/ieee80211_node.h') diff --git a/sys/net80211/ieee80211_node.h b/sys/net80211/ieee80211_node.h index 577ddf102ca..2a4828cefb2 100644 --- a/sys/net80211/ieee80211_node.h +++ b/sys/net80211/ieee80211_node.h @@ -1,4 +1,4 @@ -/* $OpenBSD: ieee80211_node.h,v 1.7 2005/09/08 13:24:53 reyk Exp $ */ +/* $OpenBSD: ieee80211_node.h,v 1.8 2005/09/13 12:11:03 reyk Exp $ */ /* $NetBSD: ieee80211_node.h,v 1.9 2004/04/30 22:57:32 dyoung Exp $ */ /*- @@ -43,11 +43,6 @@ #define IEEE80211_INACT_MAX (300/IEEE80211_INACT_WAIT) #define IEEE80211_CACHE_SIZE 100 -#define IEEE80211_NODE_HASHSIZE 32 -/* simple hash is enough for variation of macaddr */ -#define IEEE80211_NODE_HASH(addr) \ - (((u_int8_t *)(addr))[IEEE80211_ADDR_LEN - 1] % IEEE80211_NODE_HASHSIZE) - struct ieee80211_rateset { u_int8_t rs_nrates; u_int8_t rs_rates[IEEE80211_RATE_MAXSIZE]; @@ -77,8 +72,8 @@ enum ieee80211_node_state { * the ieee80211com structure. */ struct ieee80211_node { - TAILQ_ENTRY(ieee80211_node) ni_list; - LIST_ENTRY(ieee80211_node) ni_hash; + RB_ENTRY(ieee80211_node) ni_node; + u_int ni_refcnt; u_int ni_scangen; /* gen# for timeout scan */ @@ -129,6 +124,8 @@ struct ieee80211_node { u_int32_t *ni_challenge; /* shared-key challenge */ }; +RB_HEAD(ieee80211_tree, ieee80211_node); + #define ieee80211_node_incref(ni) \ do { \ int _s = splnet(); \ @@ -195,7 +192,7 @@ extern struct ieee80211_node *ieee80211_find_txnode(struct ieee80211com *, u_int8_t *); extern struct ieee80211_node * ieee80211_find_node_for_beacon(struct ieee80211com *, - u_int8_t *, struct ieee80211_channel *, char *); + u_int8_t *, struct ieee80211_channel *, char *, u_int8_t); extern struct ieee80211_node * ieee80211_lookup_node(struct ieee80211com *, u_int8_t *, struct ieee80211_channel *); extern void ieee80211_release_node(struct ieee80211com *, @@ -210,9 +207,12 @@ extern void ieee80211_node_join(struct ieee80211com *, struct ieee80211_node *, int); extern void ieee80211_node_leave(struct ieee80211com *, struct ieee80211_node *); - extern int ieee80211_match_bss(struct ieee80211com *, struct ieee80211_node *); extern void ieee80211_create_ibss(struct ieee80211com* , struct ieee80211_channel *); + +extern int ieee80211_node_cmp(struct ieee80211_node *, struct ieee80211_node *); +RB_PROTOTYPE(ieee80211_tree, ieee80211_node, ni_node, ieee80211_node_cmp); + #endif /* _NET80211_IEEE80211_NODE_H_ */ -- cgit v1.2.3