diff options
| -rw-r--r-- | usr.sbin/hostapd/hostapd.c | 51 | ||||
| -rw-r--r-- | usr.sbin/hostapd/hostapd.h | 15 |
2 files changed, 31 insertions, 35 deletions
diff --git a/usr.sbin/hostapd/hostapd.c b/usr.sbin/hostapd/hostapd.c index f79d47d78ce..37563509430 100644 --- a/usr.sbin/hostapd/hostapd.c +++ b/usr.sbin/hostapd/hostapd.c @@ -1,4 +1,4 @@ -/* $OpenBSD: hostapd.c,v 1.17 2005/08/17 13:18:33 reyk Exp $ */ +/* $OpenBSD: hostapd.c,v 1.18 2005/09/09 13:21:13 reyk Exp $ */ /* * Copyright (c) 2004, 2005 Reyk Floeter <reyk@vantronix.net> @@ -304,7 +304,6 @@ hostapd_sig_handler(int sig) void hostapd_cleanup(struct hostapd_config *cfg) { - int i; struct ip_mreq mreq; struct hostapd_table *table; struct hostapd_entry *entry; @@ -339,13 +338,9 @@ hostapd_cleanup(struct hostapd_config *cfg) /* Cleanup tables */ while ((table = TAILQ_FIRST(&cfg->c_tables)) != NULL) { - for (i = 0; i < HOSTAPD_TABLE_HASHSIZE; i++) { - while ((entry = - TAILQ_FIRST(&table->t_head[i])) != NULL) { - TAILQ_REMOVE(&table->t_head[i], entry, - e_entries); - free(entry); - } + while((entry = RB_MIN(hostapd_tree, &table->t_tree)) != NULL) { + RB_REMOVE(hostapd_tree, &table->t_tree, entry); + free(entry); } while ((entry = TAILQ_FIRST(&table->t_mask_head)) != NULL) { TAILQ_REMOVE(&table->t_mask_head, entry, e_entries); @@ -511,7 +506,6 @@ hostapd_randval(u_int8_t *buf, const u_int len) struct hostapd_table * hostapd_table_add(struct hostapd_config *cfg, const char *name) { - int i; struct hostapd_table *table; if (hostapd_table_lookup(cfg, name) != NULL) @@ -521,8 +515,7 @@ hostapd_table_add(struct hostapd_config *cfg, const char *name) return (NULL); strlcpy(table->t_name, name, sizeof(table->t_name)); - for (i = 0; i < HOSTAPD_TABLE_HASHSIZE; i++) - TAILQ_INIT(&table->t_head[i]); + RB_INIT(&table->t_tree); TAILQ_INIT(&table->t_mask_head); TAILQ_INSERT_TAIL(&cfg->c_tables, table, t_entries); @@ -545,7 +538,6 @@ hostapd_table_lookup(struct hostapd_config *cfg, const char *name) struct hostapd_entry * hostapd_entry_add(struct hostapd_table *table, u_int8_t *lladdr) { - u_int hash; struct hostapd_entry *entry; if (hostapd_entry_lookup(table, lladdr) != NULL) @@ -556,8 +548,7 @@ hostapd_entry_add(struct hostapd_table *table, u_int8_t *lladdr) return (NULL); bcopy(lladdr, entry->e_lladdr, IEEE80211_ADDR_LEN); - hash = HOSTAPD_TABLE_HASH(lladdr); - TAILQ_INSERT_TAIL(&table->t_head[hash], entry, e_entries); + RB_INSERT(hostapd_tree, &table->t_tree, entry); return (entry); } @@ -565,16 +556,13 @@ hostapd_entry_add(struct hostapd_table *table, u_int8_t *lladdr) struct hostapd_entry * hostapd_entry_lookup(struct hostapd_table *table, u_int8_t *lladdr) { - u_int hash; - struct hostapd_entry *entry; + struct hostapd_entry *entry, key; - hash = HOSTAPD_TABLE_HASH(lladdr); - TAILQ_FOREACH(entry, &table->t_head[hash], e_entries) { - if (bcmp(lladdr, entry->e_lladdr, IEEE80211_ADDR_LEN) == 0) - return (entry); - } + bcopy(lladdr, key.e_lladdr, IEEE80211_ADDR_LEN); + if ((entry = RB_FIND(hostapd_tree, &table->t_tree, &key)) != NULL) + return (entry); - /* Masked entries can't be handled by the hash table */ + /* Masked entries can't be handled by the red-black tree */ TAILQ_FOREACH(entry, &table->t_mask_head, e_entries) { if (HOSTAPD_ENTRY_MASK_MATCH(entry, lladdr)) return (entry); @@ -586,17 +574,22 @@ hostapd_entry_lookup(struct hostapd_table *table, u_int8_t *lladdr) void hostapd_entry_update(struct hostapd_table *table, struct hostapd_entry *entry) { - u_int hash; - - hash = HOSTAPD_TABLE_HASH(entry->e_lladdr); - TAILQ_REMOVE(&table->t_head[hash], entry, e_entries); + RB_REMOVE(hostapd_tree, &table->t_tree, entry); /* Apply mask to entry */ if (entry->e_flags & HOSTAPD_ENTRY_F_MASK) { HOSTAPD_ENTRY_MASK_ADD(entry->e_lladdr, entry->e_mask); TAILQ_INSERT_TAIL(&table->t_mask_head, entry, e_entries); } else { - hash = HOSTAPD_TABLE_HASH(entry->e_lladdr); - TAILQ_INSERT_TAIL(&table->t_head[hash], entry, e_entries); + RB_INSERT(hostapd_tree, &table->t_tree, entry); } } + +int +hostapd_entry_cmp(struct hostapd_entry *a, struct hostapd_entry *b) +{ + return (bcmp(a->e_lladdr, b->e_lladdr, IEEE80211_ADDR_LEN)); +} + +RB_GENERATE(hostapd_tree, hostapd_entry, e_nodes, hostapd_entry_cmp); + diff --git a/usr.sbin/hostapd/hostapd.h b/usr.sbin/hostapd/hostapd.h index a5ff7fdf8cc..95b88d9c4ae 100644 --- a/usr.sbin/hostapd/hostapd.h +++ b/usr.sbin/hostapd/hostapd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: hostapd.h,v 1.5 2005/07/30 17:18:24 reyk Exp $ */ +/* $OpenBSD: hostapd.h,v 1.6 2005/09/09 13:21:13 reyk Exp $ */ /* * Copyright (c) 2004, 2005 Reyk Floeter <reyk@vantronix.net> @@ -22,6 +22,7 @@ #include <sys/param.h> #include <sys/types.h> #include <sys/socket.h> +#include <sys/tree.h> #include <net/if.h> #include <netinet/in.h> @@ -136,6 +137,7 @@ struct hostapd_entry { struct in_addr a_ipv4; } e_addr; + RB_ENTRY(hostapd_entry) e_nodes; TAILQ_ENTRY(hostapd_entry) e_entries; }; @@ -143,10 +145,8 @@ struct hostapd_entry { #define e_ipv4 e_addr.a_ipv4 #define HOSTAPD_TABLE_NAMELEN 32 -#define HOSTAPD_TABLE_HASHSIZE 256 -#define HOSTAPD_TABLE_HASH(_a) ((((( \ - (0 ^ (_a)[0]) ^ (_a)[1]) ^ (_a)[2]) ^ (_a)[3]) ^ (_a)[4]) ^ (_a)[5] \ -) + +RB_HEAD(hostapd_tree, hostapd_entry); struct hostapd_table { char t_name[HOSTAPD_TABLE_NAMELEN]; @@ -154,7 +154,7 @@ struct hostapd_table { #define HOSTAPD_TABLE_F_CONST 0x01 - TAILQ_HEAD(, hostapd_entry) t_head[HOSTAPD_TABLE_HASHSIZE]; + struct hostapd_tree t_tree; TAILQ_HEAD(, hostapd_entry) t_mask_head; TAILQ_ENTRY(hostapd_table) t_entries; }; @@ -341,6 +341,9 @@ struct hostapd_entry *hostapd_entry_lookup(struct hostapd_table *, u_int8_t *); void hostapd_entry_update(struct hostapd_table *, struct hostapd_entry *); +int hostapd_entry_cmp(struct hostapd_entry *, struct hostapd_entry *); + +RB_PROTOTYPE(hostapd_tree, hostapd_entry, e_nodes, hostapd_entry_cmp); int hostapd_parse_file(struct hostapd_config *); int hostapd_parse_symset(char *); |