1 /* Copyright (C) 2006-2012 B.A.T.M.A.N. contributors: 2 * 3 * Simon Wunderlich, Marek Lindner 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of version 2 of the GNU General Public 7 * License as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it will be useful, but 10 * WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 17 * 02110-1301, USA 18 */ 19 20 #ifndef _NET_BATMAN_ADV_HASH_H_ 21 #define _NET_BATMAN_ADV_HASH_H_ 22 23 #include <linux/list.h> 24 25 /* callback to a compare function. should compare 2 element datas for their 26 * keys, return 0 if same and not 0 if not same 27 */ 28 typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *, 29 const void *); 30 31 /* the hashfunction, should return an index 32 * based on the key in the data of the first 33 * argument and the size the second 34 */ 35 typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t); 36 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *); 37 38 struct batadv_hashtable { 39 struct hlist_head *table; /* the hashtable itself with the buckets */ 40 spinlock_t *list_locks; /* spinlock for each hash list entry */ 41 uint32_t size; /* size of hashtable */ 42 }; 43 44 /* allocates and clears the hash */ 45 struct batadv_hashtable *batadv_hash_new(uint32_t size); 46 47 /* set class key for all locks */ 48 void batadv_hash_set_lock_class(struct batadv_hashtable *hash, 49 struct lock_class_key *key); 50 51 /* free only the hashtable and the hash itself. */ 52 void batadv_hash_destroy(struct batadv_hashtable *hash); 53 54 /* remove the hash structure. if hashdata_free_cb != NULL, this function will be 55 * called to remove the elements inside of the hash. if you don't remove the 56 * elements, memory might be leaked. 57 */ 58 static inline void batadv_hash_delete(struct batadv_hashtable *hash, 59 batadv_hashdata_free_cb free_cb, 60 void *arg) 61 { 62 struct hlist_head *head; 63 struct hlist_node *node, *node_tmp; 64 spinlock_t *list_lock; /* spinlock to protect write access */ 65 uint32_t i; 66 67 for (i = 0; i < hash->size; i++) { 68 head = &hash->table[i]; 69 list_lock = &hash->list_locks[i]; 70 71 spin_lock_bh(list_lock); 72 hlist_for_each_safe(node, node_tmp, head) { 73 hlist_del_rcu(node); 74 75 if (free_cb) 76 free_cb(node, arg); 77 } 78 spin_unlock_bh(list_lock); 79 } 80 81 batadv_hash_destroy(hash); 82 } 83 84 /** 85 * batadv_hash_bytes - hash some bytes and add them to the previous hash 86 * @hash: previous hash value 87 * @data: data to be hashed 88 * @size: number of bytes to be hashed 89 * 90 * Returns the new hash value. 91 */ 92 static inline uint32_t batadv_hash_bytes(uint32_t hash, void *data, 93 uint32_t size) 94 { 95 const unsigned char *key = data; 96 int i; 97 98 for (i = 0; i < size; i++) { 99 hash += key[i]; 100 hash += (hash << 10); 101 hash ^= (hash >> 6); 102 } 103 return hash; 104 } 105 106 /** 107 * batadv_hash_add - adds data to the hashtable 108 * @hash: storage hash table 109 * @compare: callback to determine if 2 hash elements are identical 110 * @choose: callback calculating the hash index 111 * @data: data passed to the aforementioned callbacks as argument 112 * @data_node: to be added element 113 * 114 * Returns 0 on success, 1 if the element already is in the hash 115 * and -1 on error. 116 */ 117 static inline int batadv_hash_add(struct batadv_hashtable *hash, 118 batadv_hashdata_compare_cb compare, 119 batadv_hashdata_choose_cb choose, 120 const void *data, 121 struct hlist_node *data_node) 122 { 123 uint32_t index; 124 int ret = -1; 125 struct hlist_head *head; 126 struct hlist_node *node; 127 spinlock_t *list_lock; /* spinlock to protect write access */ 128 129 if (!hash) 130 goto out; 131 132 index = choose(data, hash->size); 133 head = &hash->table[index]; 134 list_lock = &hash->list_locks[index]; 135 136 spin_lock_bh(list_lock); 137 138 hlist_for_each(node, head) { 139 if (!compare(node, data)) 140 continue; 141 142 ret = 1; 143 goto unlock; 144 } 145 146 /* no duplicate found in list, add new element */ 147 hlist_add_head_rcu(data_node, head); 148 149 ret = 0; 150 151 unlock: 152 spin_unlock_bh(list_lock); 153 out: 154 return ret; 155 } 156 157 /* removes data from hash, if found. returns pointer do data on success, so you 158 * can remove the used structure yourself, or NULL on error . data could be the 159 * structure you use with just the key filled, we just need the key for 160 * comparing. 161 */ 162 static inline void *batadv_hash_remove(struct batadv_hashtable *hash, 163 batadv_hashdata_compare_cb compare, 164 batadv_hashdata_choose_cb choose, 165 void *data) 166 { 167 uint32_t index; 168 struct hlist_node *node; 169 struct hlist_head *head; 170 void *data_save = NULL; 171 172 index = choose(data, hash->size); 173 head = &hash->table[index]; 174 175 spin_lock_bh(&hash->list_locks[index]); 176 hlist_for_each(node, head) { 177 if (!compare(node, data)) 178 continue; 179 180 data_save = node; 181 hlist_del_rcu(node); 182 break; 183 } 184 spin_unlock_bh(&hash->list_locks[index]); 185 186 return data_save; 187 } 188 189 #endif /* _NET_BATMAN_ADV_HASH_H_ */ 190