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