2 * Copyright (C) 2006-2009 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
26 void hash_init(struct hashtable_t
*hash
)
32 for (i
= 0 ; i
< hash
->size
; i
++)
33 hash
->table
[i
] = NULL
;
36 /* remove the hash structure. if hashdata_free_cb != NULL, this function will be
37 * called to remove the elements inside of the hash. if you don't remove the
38 * elements, memory might be leaked. */
39 void hash_delete(struct hashtable_t
*hash
, hashdata_free_cb free_cb
)
41 struct element_t
*bucket
, *last_bucket
;
44 for (i
= 0; i
< hash
->size
; i
++) {
45 bucket
= hash
->table
[i
];
47 while (bucket
!= NULL
) {
49 free_cb(bucket
->data
);
52 bucket
= bucket
->next
;
60 /* free only the hashtable and the hash itself. */
61 void hash_destroy(struct hashtable_t
*hash
)
67 /* iterate though the hash. first element is selected with iter_in NULL. use
68 * the returned iterator to access the elements until hash_it_t returns NULL. */
69 struct hash_it_t
*hash_iterate(struct hashtable_t
*hash
,
70 struct hash_it_t
*iter_in
)
72 struct hash_it_t
*iter
;
77 if (iter_in
== NULL
) {
78 iter
= kmalloc(sizeof(struct hash_it_t
), GFP_ATOMIC
);
81 iter
->prev_bucket
= NULL
;
86 /* sanity checks first (if our bucket got deleted in the last
88 if (iter
->bucket
!= NULL
) {
89 if (iter
->first_bucket
!= NULL
) {
90 /* we're on the first element and it got removed after
91 * the last iteration. */
92 if ((*iter
->first_bucket
) != iter
->bucket
) {
93 /* there are still other elements in the list */
94 if ((*iter
->first_bucket
) != NULL
) {
95 iter
->prev_bucket
= NULL
;
96 iter
->bucket
= (*iter
->first_bucket
);
98 &hash
->table
[iter
->index
];
104 } else if (iter
->prev_bucket
!= NULL
) {
106 * we're not on the first element, and the bucket got
107 * removed after the last iteration. the last bucket's
108 * next pointer is not pointing to our actual bucket
109 * anymore. select the next.
111 if (iter
->prev_bucket
->next
!= iter
->bucket
)
112 iter
->bucket
= iter
->prev_bucket
;
116 /* now as we are sane, select the next one if there is some */
117 if (iter
->bucket
!= NULL
) {
118 if (iter
->bucket
->next
!= NULL
) {
119 iter
->prev_bucket
= iter
->bucket
;
120 iter
->bucket
= iter
->bucket
->next
;
121 iter
->first_bucket
= NULL
;
126 /* if not returned yet, we've reached the last one on the index and have
127 * to search forward */
129 /* go through the entries of the hash table */
130 while (iter
->index
< hash
->size
) {
131 if ((hash
->table
[iter
->index
]) != NULL
) {
132 iter
->prev_bucket
= NULL
;
133 iter
->bucket
= hash
->table
[iter
->index
];
134 iter
->first_bucket
= &hash
->table
[iter
->index
];
141 /* nothing to iterate over anymore */
146 /* allocates and clears the hash */
147 struct hashtable_t
*hash_new(int size
, hashdata_compare_cb compare
,
148 hashdata_choose_cb choose
)
150 struct hashtable_t
*hash
;
152 hash
= kmalloc(sizeof(struct hashtable_t
) , GFP_ATOMIC
);
158 hash
->table
= kmalloc(sizeof(struct element_t
*) * size
, GFP_ATOMIC
);
160 if (hash
->table
== NULL
) {
167 hash
->compare
= compare
;
168 hash
->choose
= choose
;
173 /* adds data to the hashtable. returns 0 on success, -1 on error */
174 int hash_add(struct hashtable_t
*hash
, void *data
)
177 struct element_t
*bucket
, *prev_bucket
= NULL
;
182 index
= hash
->choose(data
, hash
->size
);
183 bucket
= hash
->table
[index
];
185 while (bucket
!= NULL
) {
186 if (hash
->compare(bucket
->data
, data
))
189 prev_bucket
= bucket
;
190 bucket
= bucket
->next
;
193 /* found the tail of the list, add new element */
194 bucket
= kmalloc(sizeof(struct element_t
), GFP_ATOMIC
);
203 if (prev_bucket
== NULL
)
204 hash
->table
[index
] = bucket
;
206 prev_bucket
->next
= bucket
;
212 /* finds data, based on the key in keydata. returns the found data on success,
213 * or NULL on error */
214 void *hash_find(struct hashtable_t
*hash
, void *keydata
)
217 struct element_t
*bucket
;
222 index
= hash
->choose(keydata
, hash
->size
);
223 bucket
= hash
->table
[index
];
225 while (bucket
!= NULL
) {
226 if (hash
->compare(bucket
->data
, keydata
))
229 bucket
= bucket
->next
;
235 /* remove bucket (this might be used in hash_iterate() if you already found the
236 * bucket you want to delete and don't need the overhead to find it again with
237 * hash_remove(). But usually, you don't want to use this function, as it
238 * fiddles with hash-internals. */
239 void *hash_remove_bucket(struct hashtable_t
*hash
, struct hash_it_t
*hash_it_t
)
243 data_save
= hash_it_t
->bucket
->data
;
245 if (hash_it_t
->prev_bucket
!= NULL
)
246 hash_it_t
->prev_bucket
->next
= hash_it_t
->bucket
->next
;
247 else if (hash_it_t
->first_bucket
!= NULL
)
248 (*hash_it_t
->first_bucket
) = hash_it_t
->bucket
->next
;
250 kfree(hash_it_t
->bucket
);
256 /* removes data from hash, if found. returns pointer do data on success, so you
257 * can remove the used structure yourself, or NULL on error . data could be the
258 * structure you use with just the key filled, we just need the key for
260 void *hash_remove(struct hashtable_t
*hash
, void *data
)
262 struct hash_it_t hash_it_t
;
264 hash_it_t
.index
= hash
->choose(data
, hash
->size
);
265 hash_it_t
.bucket
= hash
->table
[hash_it_t
.index
];
266 hash_it_t
.prev_bucket
= NULL
;
268 while (hash_it_t
.bucket
!= NULL
) {
269 if (hash
->compare(hash_it_t
.bucket
->data
, data
)) {
270 hash_it_t
.first_bucket
=
272 hash
->table
[hash_it_t
.index
] ?
273 &hash
->table
[hash_it_t
.index
] : NULL
);
274 return hash_remove_bucket(hash
, &hash_it_t
);
277 hash_it_t
.prev_bucket
= hash_it_t
.bucket
;
278 hash_it_t
.bucket
= hash_it_t
.bucket
->next
;
284 /* resize the hash, returns the pointer to the new hash or NULL on
285 * error. removes the old hash on success. */
286 struct hashtable_t
*hash_resize(struct hashtable_t
*hash
, int size
)
288 struct hashtable_t
*new_hash
;
289 struct element_t
*bucket
;
292 /* initialize a new hash with the new size */
293 new_hash
= hash_new(size
, hash
->compare
, hash
->choose
);
295 if (new_hash
== NULL
)
298 /* copy the elements */
299 for (i
= 0; i
< hash
->size
; i
++) {
300 bucket
= hash
->table
[i
];
302 while (bucket
!= NULL
) {
303 hash_add(new_hash
, bucket
->data
);
304 bucket
= bucket
->next
;
308 /* remove hash and eventual overflow buckets but not the content
310 hash_delete(hash
, NULL
);