1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* Copyright (C) 2006-2019 B.A.T.M.A.N. contributors: 3 * 4 * Simon Wunderlich, Marek Lindner 5 */ 6 7 #ifndef _NET_BATMAN_ADV_HASH_H_ 8 #define _NET_BATMAN_ADV_HASH_H_ 9 10 #include "main.h" 11 12 #include <linux/atomic.h> 13 #include <linux/compiler.h> 14 #include <linux/list.h> 15 #include <linux/rculist.h> 16 #include <linux/spinlock.h> 17 #include <linux/stddef.h> 18 #include <linux/types.h> 19 20 struct lock_class_key; 21 22 /* callback to a compare function. should compare 2 element datas for their 23 * keys 24 * 25 * Return: true if same and false if not same 26 */ 27 typedef bool (*batadv_hashdata_compare_cb)(const struct hlist_node *, 28 const void *); 29 30 /* the hashfunction 31 * 32 * Return: an index based on the key in the data of the first argument and the 33 * size the second 34 */ 35 typedef u32 (*batadv_hashdata_choose_cb)(const void *, u32); 36 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *); 37 38 /** 39 * struct batadv_hashtable - Wrapper of simple hlist based hashtable 40 */ 41 struct batadv_hashtable { 42 /** @table: the hashtable itself with the buckets */ 43 struct hlist_head *table; 44 45 /** @list_locks: spinlock for each hash list entry */ 46 spinlock_t *list_locks; 47 48 /** @size: size of hashtable */ 49 u32 size; 50 51 /** @generation: current (generation) sequence number */ 52 atomic_t generation; 53 }; 54 55 /* allocates and clears the hash */ 56 struct batadv_hashtable *batadv_hash_new(u32 size); 57 58 /* set class key for all locks */ 59 void batadv_hash_set_lock_class(struct batadv_hashtable *hash, 60 struct lock_class_key *key); 61 62 /* free only the hashtable and the hash itself. */ 63 void batadv_hash_destroy(struct batadv_hashtable *hash); 64 65 /** 66 * batadv_hash_add() - adds data to the hashtable 67 * @hash: storage hash table 68 * @compare: callback to determine if 2 hash elements are identical 69 * @choose: callback calculating the hash index 70 * @data: data passed to the aforementioned callbacks as argument 71 * @data_node: to be added element 72 * 73 * Return: 0 on success, 1 if the element already is in the hash 74 * and -1 on error. 75 */ 76 static inline int batadv_hash_add(struct batadv_hashtable *hash, 77 batadv_hashdata_compare_cb compare, 78 batadv_hashdata_choose_cb choose, 79 const void *data, 80 struct hlist_node *data_node) 81 { 82 u32 index; 83 int ret = -1; 84 struct hlist_head *head; 85 struct hlist_node *node; 86 spinlock_t *list_lock; /* spinlock to protect write access */ 87 88 if (!hash) 89 goto out; 90 91 index = choose(data, hash->size); 92 head = &hash->table[index]; 93 list_lock = &hash->list_locks[index]; 94 95 spin_lock_bh(list_lock); 96 97 hlist_for_each(node, head) { 98 if (!compare(node, data)) 99 continue; 100 101 ret = 1; 102 goto unlock; 103 } 104 105 /* no duplicate found in list, add new element */ 106 hlist_add_head_rcu(data_node, head); 107 atomic_inc(&hash->generation); 108 109 ret = 0; 110 111 unlock: 112 spin_unlock_bh(list_lock); 113 out: 114 return ret; 115 } 116 117 /** 118 * batadv_hash_remove() - Removes data from hash, if found 119 * @hash: hash table 120 * @compare: callback to determine if 2 hash elements are identical 121 * @choose: callback calculating the hash index 122 * @data: data passed to the aforementioned callbacks as argument 123 * 124 * ata could be the structure you use with just the key filled, we just need 125 * the key for comparing. 126 * 127 * Return: returns pointer do data on success, so you can remove the used 128 * structure yourself, or NULL on error 129 */ 130 static inline void *batadv_hash_remove(struct batadv_hashtable *hash, 131 batadv_hashdata_compare_cb compare, 132 batadv_hashdata_choose_cb choose, 133 void *data) 134 { 135 u32 index; 136 struct hlist_node *node; 137 struct hlist_head *head; 138 void *data_save = NULL; 139 140 index = choose(data, hash->size); 141 head = &hash->table[index]; 142 143 spin_lock_bh(&hash->list_locks[index]); 144 hlist_for_each(node, head) { 145 if (!compare(node, data)) 146 continue; 147 148 data_save = node; 149 hlist_del_rcu(node); 150 atomic_inc(&hash->generation); 151 break; 152 } 153 spin_unlock_bh(&hash->list_locks[index]); 154 155 return data_save; 156 } 157 158 #endif /* _NET_BATMAN_ADV_HASH_H_ */ 159