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