diff options
Diffstat (limited to 'net/batman-adv/hash.h')
| -rw-r--r-- | net/batman-adv/hash.h | 130 |
1 files changed, 84 insertions, 46 deletions
diff --git a/net/batman-adv/hash.h b/net/batman-adv/hash.h index 434822b2747..539fc126679 100644 --- a/net/batman-adv/hash.h +++ b/net/batman-adv/hash.h @@ -1,5 +1,4 @@ -/* - * Copyright (C) 2006-2011 B.A.T.M.A.N. contributors: +/* Copyright (C) 2006-2014 B.A.T.M.A.N. contributors: * * Simon Wunderlich, Marek Lindner * @@ -13,10 +12,7 @@ * General Public License for more details. * * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - * 02110-1301, USA - * + * along with this program; if not, see <http://www.gnu.org/licenses/>. */ #ifndef _NET_BATMAN_ADV_HASH_H_ @@ -24,40 +20,47 @@ #include <linux/list.h> -/* callback to a compare function. should - * compare 2 element datas for their keys, - * return 0 if same and not 0 if not - * same */ -typedef int (*hashdata_compare_cb)(struct hlist_node *, void *); +/* callback to a compare function. should compare 2 element datas for their + * keys, return 0 if same and not 0 if not same + */ +typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *, + const void *); /* the hashfunction, should return an index * based on the key in the data of the first - * argument and the size the second */ -typedef int (*hashdata_choose_cb)(void *, int); -typedef void (*hashdata_free_cb)(struct hlist_node *, void *); + * argument and the size the second + */ +typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t); +typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *); -struct hashtable_t { +struct batadv_hashtable { struct hlist_head *table; /* the hashtable itself with the buckets */ spinlock_t *list_locks; /* spinlock for each hash list entry */ - int size; /* size of hashtable */ + uint32_t size; /* size of hashtable */ }; /* allocates and clears the hash */ -struct hashtable_t *hash_new(int size); +struct batadv_hashtable *batadv_hash_new(uint32_t size); + +/* set class key for all locks */ +void batadv_hash_set_lock_class(struct batadv_hashtable *hash, + struct lock_class_key *key); /* free only the hashtable and the hash itself. */ -void hash_destroy(struct hashtable_t *hash); +void batadv_hash_destroy(struct batadv_hashtable *hash); /* remove the hash structure. if hashdata_free_cb != NULL, this function will be * called to remove the elements inside of the hash. if you don't remove the - * elements, memory might be leaked. */ -static inline void hash_delete(struct hashtable_t *hash, - hashdata_free_cb free_cb, void *arg) + * elements, memory might be leaked. + */ +static inline void batadv_hash_delete(struct batadv_hashtable *hash, + batadv_hashdata_free_cb free_cb, + void *arg) { struct hlist_head *head; struct hlist_node *node, *node_tmp; spinlock_t *list_lock; /* spinlock to protect write access */ - int i; + uint32_t i; for (i = 0; i < hash->size; i++) { head = &hash->table[i]; @@ -73,58 +76,93 @@ static inline void hash_delete(struct hashtable_t *hash, spin_unlock_bh(list_lock); } - hash_destroy(hash); + batadv_hash_destroy(hash); } -/* adds data to the hashtable. returns 0 on success, -1 on error */ -static inline int hash_add(struct hashtable_t *hash, - hashdata_compare_cb compare, - hashdata_choose_cb choose, - void *data, struct hlist_node *data_node) +/** + * batadv_hash_bytes - hash some bytes and add them to the previous hash + * @hash: previous hash value + * @data: data to be hashed + * @size: number of bytes to be hashed + * + * Returns the new hash value. + */ +static inline uint32_t batadv_hash_bytes(uint32_t hash, const void *data, + uint32_t size) { - int index; + const unsigned char *key = data; + int i; + + for (i = 0; i < size; i++) { + hash += key[i]; + hash += (hash << 10); + hash ^= (hash >> 6); + } + return hash; +} + +/** + * batadv_hash_add - adds data to the hashtable + * @hash: storage hash table + * @compare: callback to determine if 2 hash elements are identical + * @choose: callback calculating the hash index + * @data: data passed to the aforementioned callbacks as argument + * @data_node: to be added element + * + * Returns 0 on success, 1 if the element already is in the hash + * and -1 on error. + */ +static inline int batadv_hash_add(struct batadv_hashtable *hash, + batadv_hashdata_compare_cb compare, + batadv_hashdata_choose_cb choose, + const void *data, + struct hlist_node *data_node) +{ + uint32_t index; + int ret = -1; struct hlist_head *head; struct hlist_node *node; spinlock_t *list_lock; /* spinlock to protect write access */ if (!hash) - goto err; + goto out; index = choose(data, hash->size); head = &hash->table[index]; list_lock = &hash->list_locks[index]; - rcu_read_lock(); - __hlist_for_each_rcu(node, head) { + spin_lock_bh(list_lock); + + hlist_for_each(node, head) { if (!compare(node, data)) continue; - goto err_unlock; + ret = 1; + goto unlock; } - rcu_read_unlock(); /* no duplicate found in list, add new element */ - spin_lock_bh(list_lock); hlist_add_head_rcu(data_node, head); - spin_unlock_bh(list_lock); - return 0; + ret = 0; -err_unlock: - rcu_read_unlock(); -err: - return -1; +unlock: + spin_unlock_bh(list_lock); +out: + return ret; } /* removes data from hash, if found. returns pointer do data on success, so you * can remove the used structure yourself, or NULL on error . data could be the * structure you use with just the key filled, we just need the key for - * comparing. */ -static inline void *hash_remove(struct hashtable_t *hash, - hashdata_compare_cb compare, - hashdata_choose_cb choose, void *data) + * comparing. + */ +static inline void *batadv_hash_remove(struct batadv_hashtable *hash, + batadv_hashdata_compare_cb compare, + batadv_hashdata_choose_cb choose, + void *data) { - size_t index; + uint32_t index; struct hlist_node *node; struct hlist_head *head; void *data_save = NULL; |