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