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