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_ */