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