Blame view
net/batman-adv/hash.h
4.97 KB
e19f9759e
|
1 |
/* Copyright (C) 2006-2014 B.A.T.M.A.N. contributors: |
c6c8fea29
|
2 3 4 5 6 7 8 9 10 11 12 13 14 |
* * Simon Wunderlich, Marek Lindner * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License |
ebf38fb7a
|
15 |
* along with this program; if not, see <http://www.gnu.org/licenses/>. |
c6c8fea29
|
16 17 18 19 20 21 |
*/ #ifndef _NET_BATMAN_ADV_HASH_H_ #define _NET_BATMAN_ADV_HASH_H_ #include <linux/list.h> |
9cfc7bd60
|
22 23 24 |
/* callback to a compare function. should compare 2 element datas for their * keys, return 0 if same and not 0 if not same */ |
5bf74e9ca
|
25 26 |
typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *, const void *); |
c6c8fea29
|
27 28 29 |
/* the hashfunction, should return an index * based on the key in the data of the first |
9cfc7bd60
|
30 31 |
* argument and the size the second */ |
5bf74e9ca
|
32 33 |
typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t); typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *); |
c6c8fea29
|
34 |
|
5bf74e9ca
|
35 |
struct batadv_hashtable { |
fb778ea17
|
36 37 |
struct hlist_head *table; /* the hashtable itself with the buckets */ spinlock_t *list_locks; /* spinlock for each hash list entry */ |
c90681b85
|
38 |
uint32_t size; /* size of hashtable */ |
c6c8fea29
|
39 40 41 |
}; /* allocates and clears the hash */ |
5bf74e9ca
|
42 |
struct batadv_hashtable *batadv_hash_new(uint32_t size); |
c6c8fea29
|
43 |
|
5d52dad27
|
44 |
/* set class key for all locks */ |
5bf74e9ca
|
45 |
void batadv_hash_set_lock_class(struct batadv_hashtable *hash, |
5d52dad27
|
46 |
struct lock_class_key *key); |
c6c8fea29
|
47 |
/* free only the hashtable and the hash itself. */ |
5bf74e9ca
|
48 |
void batadv_hash_destroy(struct batadv_hashtable *hash); |
c6c8fea29
|
49 50 51 |
/* 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 |
9cfc7bd60
|
52 53 |
* elements, memory might be leaked. */ |
5bf74e9ca
|
54 55 56 |
static inline void batadv_hash_delete(struct batadv_hashtable *hash, batadv_hashdata_free_cb free_cb, void *arg) |
c6c8fea29
|
57 58 |
{ struct hlist_head *head; |
7aadf889e
|
59 |
struct hlist_node *node, *node_tmp; |
fb778ea17
|
60 |
spinlock_t *list_lock; /* spinlock to protect write access */ |
c90681b85
|
61 |
uint32_t i; |
c6c8fea29
|
62 63 64 |
for (i = 0; i < hash->size; i++) { head = &hash->table[i]; |
fb778ea17
|
65 |
list_lock = &hash->list_locks[i]; |
c6c8fea29
|
66 |
|
fb778ea17
|
67 |
spin_lock_bh(list_lock); |
7aadf889e
|
68 69 |
hlist_for_each_safe(node, node_tmp, head) { hlist_del_rcu(node); |
c6c8fea29
|
70 |
|
7aadf889e
|
71 72 |
if (free_cb) free_cb(node, arg); |
c6c8fea29
|
73 |
} |
fb778ea17
|
74 |
spin_unlock_bh(list_lock); |
c6c8fea29
|
75 |
} |
1a8eaf073
|
76 |
batadv_hash_destroy(hash); |
c6c8fea29
|
77 |
} |
2c53040f0
|
78 |
/** |
07568d036
|
79 80 81 82 83 84 85 |
* 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. */ |
467b5fe69
|
86 |
static inline uint32_t batadv_hash_bytes(uint32_t hash, const void *data, |
07568d036
|
87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
uint32_t size) { const unsigned char *key = data; int i; for (i = 0; i < size; i++) { hash += key[i]; hash += (hash << 10); hash ^= (hash >> 6); } return hash; } /** |
2c53040f0
|
101 |
* batadv_hash_add - adds data to the hashtable |
1a1f37d92
|
102 103 104 105 106 107 108 109 110 |
* @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. */ |
5bf74e9ca
|
111 112 113 |
static inline int batadv_hash_add(struct batadv_hashtable *hash, batadv_hashdata_compare_cb compare, batadv_hashdata_choose_cb choose, |
c0a559295
|
114 115 |
const void *data, struct hlist_node *data_node) |
c6c8fea29
|
116 |
{ |
c90681b85
|
117 118 |
uint32_t index; int ret = -1; |
c6c8fea29
|
119 |
struct hlist_head *head; |
7aadf889e
|
120 |
struct hlist_node *node; |
fb778ea17
|
121 |
spinlock_t *list_lock; /* spinlock to protect write access */ |
c6c8fea29
|
122 123 |
if (!hash) |
1a1f37d92
|
124 |
goto out; |
c6c8fea29
|
125 126 127 |
index = choose(data, hash->size); head = &hash->table[index]; |
fb778ea17
|
128 |
list_lock = &hash->list_locks[index]; |
c6c8fea29
|
129 |
|
75c5a2e78
|
130 131 132 |
spin_lock_bh(list_lock); hlist_for_each(node, head) { |
7aadf889e
|
133 134 |
if (!compare(node, data)) continue; |
1a1f37d92
|
135 |
ret = 1; |
75c5a2e78
|
136 |
goto unlock; |
c6c8fea29
|
137 138 139 |
} /* no duplicate found in list, add new element */ |
7aadf889e
|
140 |
hlist_add_head_rcu(data_node, head); |
c6c8fea29
|
141 |
|
1a1f37d92
|
142 |
ret = 0; |
fb778ea17
|
143 |
|
75c5a2e78
|
144 145 |
unlock: spin_unlock_bh(list_lock); |
1a1f37d92
|
146 147 |
out: return ret; |
c6c8fea29
|
148 149 150 151 152 |
} /* 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 |
9cfc7bd60
|
153 154 |
* comparing. */ |
5bf74e9ca
|
155 156 157 158 |
static inline void *batadv_hash_remove(struct batadv_hashtable *hash, batadv_hashdata_compare_cb compare, batadv_hashdata_choose_cb choose, void *data) |
c6c8fea29
|
159 |
{ |
c90681b85
|
160 |
uint32_t index; |
7aadf889e
|
161 |
struct hlist_node *node; |
c6c8fea29
|
162 |
struct hlist_head *head; |
fb778ea17
|
163 |
void *data_save = NULL; |
c6c8fea29
|
164 165 166 |
index = choose(data, hash->size); head = &hash->table[index]; |
fb778ea17
|
167 |
spin_lock_bh(&hash->list_locks[index]); |
7aadf889e
|
168 169 170 171 172 173 174 |
hlist_for_each(node, head) { if (!compare(node, data)) continue; data_save = node; hlist_del_rcu(node); break; |
c6c8fea29
|
175 |
} |
fb778ea17
|
176 |
spin_unlock_bh(&hash->list_locks[index]); |
c6c8fea29
|
177 |
|
fb778ea17
|
178 |
return data_save; |
c6c8fea29
|
179 |
} |
c6c8fea29
|
180 |
#endif /* _NET_BATMAN_ADV_HASH_H_ */ |