1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#ifndef _NET_BATMAN_ADV_HASH_H_
21#define _NET_BATMAN_ADV_HASH_H_
22
23#include <linux/list.h>
24
25
26
27
28typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *,
29 const void *);
30
31
32
33
34
35typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t);
36typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
37
38struct batadv_hashtable {
39 struct hlist_head *table;
40 spinlock_t *list_locks;
41 uint32_t size;
42};
43
44
45struct batadv_hashtable *batadv_hash_new(uint32_t size);
46
47
48void batadv_hash_set_lock_class(struct batadv_hashtable *hash,
49 struct lock_class_key *key);
50
51
52void batadv_hash_destroy(struct batadv_hashtable *hash);
53
54
55
56
57
58static 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;
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
86
87
88
89
90
91
92static inline uint32_t batadv_hash_bytes(uint32_t hash, const 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
108
109
110
111
112
113
114
115
116
117static 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;
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
147 hlist_add_head_rcu(data_node, head);
148
149 ret = 0;
150
151unlock:
152 spin_unlock_bh(list_lock);
153out:
154 return ret;
155}
156
157
158
159
160
161
162static 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
190