2 * Copyright (C) 2006-2011 B.A.T.M.A.N. contributors:
4 * Simon Wunderlich, Marek Lindner
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of version 2 of the GNU General Public
8 * License as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 #ifndef _NET_BATMAN_ADV_HASH_H_
23 #define _NET_BATMAN_ADV_HASH_H_
25 #include <linux/list.h>
27 /* callback to a compare function. should
28 * compare 2 element datas for their keys,
29 * return 0 if same and not 0 if not
31 typedef int (*hashdata_compare_cb
)(void *, void *);
33 /* the hashfunction, should return an index
34 * based on the key in the data of the first
35 * argument and the size the second */
36 typedef int (*hashdata_choose_cb
)(void *, int);
37 typedef void (*hashdata_free_cb
)(void *, void *);
40 void *data
; /* pointer to the data */
41 struct hlist_node hlist
; /* bucket list pointer */
46 struct hlist_head
*table
; /* the hashtable itself with the buckets */
47 spinlock_t
*list_locks
; /* spinlock for each hash list entry */
48 int size
; /* size of hashtable */
51 /* allocates and clears the hash */
52 struct hashtable_t
*hash_new(int size
);
54 /* free only the hashtable and the hash itself. */
55 void hash_destroy(struct hashtable_t
*hash
);
57 void bucket_free_rcu(struct rcu_head
*rcu
);
59 /* remove the hash structure. if hashdata_free_cb != NULL, this function will be
60 * called to remove the elements inside of the hash. if you don't remove the
61 * elements, memory might be leaked. */
62 static inline void hash_delete(struct hashtable_t
*hash
,
63 hashdata_free_cb free_cb
, void *arg
)
65 struct hlist_head
*head
;
66 struct hlist_node
*walk
, *safe
;
67 struct element_t
*bucket
;
68 spinlock_t
*list_lock
; /* spinlock to protect write access */
71 for (i
= 0; i
< hash
->size
; i
++) {
72 head
= &hash
->table
[i
];
73 list_lock
= &hash
->list_locks
[i
];
75 spin_lock_bh(list_lock
);
76 hlist_for_each_entry_safe(bucket
, walk
, safe
, head
, hlist
) {
78 free_cb(bucket
->data
, arg
);
81 call_rcu(&bucket
->rcu
, bucket_free_rcu
);
83 spin_unlock_bh(list_lock
);
89 /* adds data to the hashtable. returns 0 on success, -1 on error */
90 static inline int hash_add(struct hashtable_t
*hash
,
91 hashdata_compare_cb compare
,
92 hashdata_choose_cb choose
, void *data
)
95 struct hlist_head
*head
;
96 struct hlist_node
*walk
, *safe
;
97 struct element_t
*bucket
;
98 spinlock_t
*list_lock
; /* spinlock to protect write access */
103 index
= choose(data
, hash
->size
);
104 head
= &hash
->table
[index
];
105 list_lock
= &hash
->list_locks
[index
];
108 hlist_for_each_entry_safe(bucket
, walk
, safe
, head
, hlist
) {
109 if (compare(bucket
->data
, data
))
114 /* no duplicate found in list, add new element */
115 bucket
= kmalloc(sizeof(struct element_t
), GFP_ATOMIC
);
121 spin_lock_bh(list_lock
);
122 hlist_add_head_rcu(&bucket
->hlist
, head
);
123 spin_unlock_bh(list_lock
);
133 /* removes data from hash, if found. returns pointer do data on success, so you
134 * can remove the used structure yourself, or NULL on error . data could be the
135 * structure you use with just the key filled, we just need the key for
137 static inline void *hash_remove(struct hashtable_t
*hash
,
138 hashdata_compare_cb compare
,
139 hashdata_choose_cb choose
, void *data
)
142 struct hlist_node
*walk
;
143 struct element_t
*bucket
;
144 struct hlist_head
*head
;
145 void *data_save
= NULL
;
147 index
= choose(data
, hash
->size
);
148 head
= &hash
->table
[index
];
150 spin_lock_bh(&hash
->list_locks
[index
]);
151 hlist_for_each_entry(bucket
, walk
, head
, hlist
) {
152 if (compare(bucket
->data
, data
)) {
153 data_save
= bucket
->data
;
155 call_rcu(&bucket
->rcu
, bucket_free_rcu
);
159 spin_unlock_bh(&hash
->list_locks
[index
]);
165 * finds data, based on the key in keydata. returns the found data on success,
168 * caller must lock with rcu_read_lock() / rcu_read_unlock()
170 static inline void *hash_find(struct hashtable_t
*hash
,
171 hashdata_compare_cb compare
,
172 hashdata_choose_cb choose
, void *keydata
)
175 struct hlist_head
*head
;
176 struct hlist_node
*walk
;
177 struct element_t
*bucket
;
178 void *bucket_data
= NULL
;
183 index
= choose(keydata
, hash
->size
);
184 head
= &hash
->table
[index
];
186 hlist_for_each_entry(bucket
, walk
, head
, hlist
) {
187 if (compare(bucket
->data
, keydata
)) {
188 bucket_data
= bucket
->data
;
196 #endif /* _NET_BATMAN_ADV_HASH_H_ */