2 * Copyright (C) 2006-2010 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 */
45 struct hlist_head
*table
; /* the hashtable itself, with the buckets */
46 int size
; /* size of hashtable */
49 /* allocates and clears the hash */
50 struct hashtable_t
*hash_new(int size
);
52 /* free only the hashtable and the hash itself. */
53 void hash_destroy(struct hashtable_t
*hash
);
55 /* remove the hash structure. if hashdata_free_cb != NULL, this function will be
56 * called to remove the elements inside of the hash. if you don't remove the
57 * elements, memory might be leaked. */
58 static inline void hash_delete(struct hashtable_t
*hash
,
59 hashdata_free_cb free_cb
, void *arg
)
61 struct hlist_head
*head
;
62 struct hlist_node
*walk
, *safe
;
63 struct element_t
*bucket
;
66 for (i
= 0; i
< hash
->size
; i
++) {
67 head
= &hash
->table
[i
];
69 hlist_for_each_safe(walk
, safe
, head
) {
70 bucket
= hlist_entry(walk
, struct element_t
, hlist
);
72 free_cb(bucket
->data
, arg
);
82 /* adds data to the hashtable. returns 0 on success, -1 on error */
83 static inline int hash_add(struct hashtable_t
*hash
,
84 hashdata_compare_cb compare
,
85 hashdata_choose_cb choose
, void *data
)
88 struct hlist_head
*head
;
89 struct hlist_node
*walk
, *safe
;
90 struct element_t
*bucket
;
95 index
= choose(data
, hash
->size
);
96 head
= &hash
->table
[index
];
98 hlist_for_each_safe(walk
, safe
, head
) {
99 bucket
= hlist_entry(walk
, struct element_t
, hlist
);
100 if (compare(bucket
->data
, data
))
104 /* no duplicate found in list, add new element */
105 bucket
= kmalloc(sizeof(struct element_t
), GFP_ATOMIC
);
111 hlist_add_head(&bucket
->hlist
, head
);
116 /* removes data from hash, if found. returns pointer do data on success, so you
117 * can remove the used structure yourself, or NULL on error . data could be the
118 * structure you use with just the key filled, we just need the key for
120 static inline void *hash_remove(struct hashtable_t
*hash
,
121 hashdata_compare_cb compare
,
122 hashdata_choose_cb choose
, void *data
)
125 struct hlist_node
*walk
;
126 struct element_t
*bucket
;
127 struct hlist_head
*head
;
130 index
= choose(data
, hash
->size
);
131 head
= &hash
->table
[index
];
133 hlist_for_each_entry(bucket
, walk
, head
, hlist
) {
134 if (compare(bucket
->data
, data
)) {
135 data_save
= bucket
->data
;
145 /* finds data, based on the key in keydata. returns the found data on success,
146 * or NULL on error */
147 static inline void *hash_find(struct hashtable_t
*hash
,
148 hashdata_compare_cb compare
,
149 hashdata_choose_cb choose
, void *keydata
)
152 struct hlist_head
*head
;
153 struct hlist_node
*walk
;
154 struct element_t
*bucket
;
159 index
= choose(keydata
, hash
->size
);
160 head
= &hash
->table
[index
];
162 hlist_for_each(walk
, head
) {
163 bucket
= hlist_entry(walk
, struct element_t
, hlist
);
164 if (compare(bucket
->data
, keydata
))
171 #endif /* _NET_BATMAN_ADV_HASH_H_ */