Andrew Lunn | 5beef3c | 2009-11-09 21:20:10 +0100 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright (C) 2006-2009 B.A.T.M.A.N. contributors: |
| 3 | * |
| 4 | * Simon Wunderlich, Marek Lindner |
| 5 | * |
| 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. |
| 9 | * |
| 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. |
| 14 | * |
| 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 |
| 18 | * 02110-1301, USA |
| 19 | * |
| 20 | */ |
| 21 | |
| 22 | #include "main.h" |
| 23 | #include "hash.h" |
| 24 | |
| 25 | /* clears the hash */ |
| 26 | void hash_init(struct hashtable_t *hash) |
| 27 | { |
| 28 | int i; |
| 29 | |
| 30 | hash->elements = 0; |
| 31 | |
| 32 | for (i = 0 ; i < hash->size; i++) |
| 33 | hash->table[i] = NULL; |
| 34 | } |
| 35 | |
| 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) |
| 40 | { |
| 41 | struct element_t *bucket, *last_bucket; |
| 42 | int i; |
| 43 | |
| 44 | for (i = 0; i < hash->size; i++) { |
| 45 | bucket = hash->table[i]; |
| 46 | |
| 47 | while (bucket != NULL) { |
| 48 | if (free_cb != NULL) |
| 49 | free_cb(bucket->data); |
| 50 | |
| 51 | last_bucket = bucket; |
| 52 | bucket = bucket->next; |
| 53 | kfree(last_bucket); |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | hash_destroy(hash); |
| 58 | } |
| 59 | |
| 60 | /* free only the hashtable and the hash itself. */ |
| 61 | void hash_destroy(struct hashtable_t *hash) |
| 62 | { |
| 63 | kfree(hash->table); |
| 64 | kfree(hash); |
| 65 | } |
| 66 | |
| 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) |
| 71 | { |
| 72 | struct hash_it_t *iter; |
| 73 | |
| 74 | if (!hash) |
| 75 | return NULL; |
| 76 | |
| 77 | if (iter_in == NULL) { |
| 78 | iter = kmalloc(sizeof(struct hash_it_t), GFP_ATOMIC); |
| 79 | iter->index = -1; |
| 80 | iter->bucket = NULL; |
| 81 | iter->prev_bucket = NULL; |
| 82 | } else { |
| 83 | iter = iter_in; |
| 84 | } |
| 85 | |
| 86 | /* sanity checks first (if our bucket got deleted in the last |
| 87 | * iteration): */ |
| 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); |
| 97 | iter->first_bucket = |
| 98 | &hash->table[iter->index]; |
| 99 | return iter; |
| 100 | } else { |
| 101 | iter->bucket = NULL; |
| 102 | } |
| 103 | } |
| 104 | } else if (iter->prev_bucket != NULL) { |
| 105 | /* |
| 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. |
| 110 | */ |
| 111 | if (iter->prev_bucket->next != iter->bucket) |
| 112 | iter->bucket = iter->prev_bucket; |
| 113 | } |
| 114 | } |
| 115 | |
| 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; |
| 122 | return iter; |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | /* if not returned yet, we've reached the last one on the index and have |
| 127 | * to search forward */ |
| 128 | iter->index++; |
| 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]; |
| 135 | return iter; |
| 136 | } else { |
| 137 | iter->index++; |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | /* nothing to iterate over anymore */ |
| 142 | kfree(iter); |
| 143 | return NULL; |
| 144 | } |
| 145 | |
| 146 | /* allocates and clears the hash */ |
| 147 | struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, |
| 148 | hashdata_choose_cb choose) |
| 149 | { |
| 150 | struct hashtable_t *hash; |
| 151 | |
| 152 | hash = kmalloc(sizeof(struct hashtable_t) , GFP_ATOMIC); |
| 153 | |
| 154 | if (hash == NULL) |
| 155 | return NULL; |
| 156 | |
| 157 | hash->size = size; |
| 158 | hash->table = kmalloc(sizeof(struct element_t *) * size, GFP_ATOMIC); |
| 159 | |
| 160 | if (hash->table == NULL) { |
| 161 | kfree(hash); |
| 162 | return NULL; |
| 163 | } |
| 164 | |
| 165 | hash_init(hash); |
| 166 | |
| 167 | hash->compare = compare; |
| 168 | hash->choose = choose; |
| 169 | |
| 170 | return hash; |
| 171 | } |
| 172 | |
| 173 | /* adds data to the hashtable. returns 0 on success, -1 on error */ |
| 174 | int hash_add(struct hashtable_t *hash, void *data) |
| 175 | { |
| 176 | int index; |
| 177 | struct element_t *bucket, *prev_bucket = NULL; |
| 178 | |
| 179 | if (!hash) |
| 180 | return -1; |
| 181 | |
| 182 | index = hash->choose(data, hash->size); |
| 183 | bucket = hash->table[index]; |
| 184 | |
| 185 | while (bucket != NULL) { |
| 186 | if (hash->compare(bucket->data, data)) |
| 187 | return -1; |
| 188 | |
| 189 | prev_bucket = bucket; |
| 190 | bucket = bucket->next; |
| 191 | } |
| 192 | |
| 193 | /* found the tail of the list, add new element */ |
| 194 | bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); |
| 195 | |
| 196 | if (bucket == NULL) |
| 197 | return -1; |
| 198 | |
| 199 | bucket->data = data; |
| 200 | bucket->next = NULL; |
| 201 | |
| 202 | /* and link it */ |
| 203 | if (prev_bucket == NULL) |
| 204 | hash->table[index] = bucket; |
| 205 | else |
| 206 | prev_bucket->next = bucket; |
| 207 | |
| 208 | hash->elements++; |
| 209 | return 0; |
| 210 | } |
| 211 | |
| 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) |
| 215 | { |
| 216 | int index; |
| 217 | struct element_t *bucket; |
| 218 | |
| 219 | if (!hash) |
| 220 | return NULL; |
| 221 | |
| 222 | index = hash->choose(keydata , hash->size); |
| 223 | bucket = hash->table[index]; |
| 224 | |
| 225 | while (bucket != NULL) { |
| 226 | if (hash->compare(bucket->data, keydata)) |
| 227 | return bucket->data; |
| 228 | |
| 229 | bucket = bucket->next; |
| 230 | } |
| 231 | |
| 232 | return NULL; |
| 233 | } |
| 234 | |
| 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) |
| 240 | { |
| 241 | void *data_save; |
| 242 | |
| 243 | data_save = hash_it_t->bucket->data; |
| 244 | |
| 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; |
| 249 | |
| 250 | kfree(hash_it_t->bucket); |
| 251 | hash->elements--; |
| 252 | |
| 253 | return data_save; |
| 254 | } |
| 255 | |
| 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 |
| 259 | * comparing. */ |
| 260 | void *hash_remove(struct hashtable_t *hash, void *data) |
| 261 | { |
| 262 | struct hash_it_t hash_it_t; |
| 263 | |
| 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; |
| 267 | |
| 268 | while (hash_it_t.bucket != NULL) { |
| 269 | if (hash->compare(hash_it_t.bucket->data, data)) { |
| 270 | hash_it_t.first_bucket = |
| 271 | (hash_it_t.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); |
| 275 | } |
| 276 | |
| 277 | hash_it_t.prev_bucket = hash_it_t.bucket; |
| 278 | hash_it_t.bucket = hash_it_t.bucket->next; |
| 279 | } |
| 280 | |
| 281 | return NULL; |
| 282 | } |
| 283 | |
| 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) |
| 287 | { |
| 288 | struct hashtable_t *new_hash; |
| 289 | struct element_t *bucket; |
| 290 | int i; |
| 291 | |
| 292 | /* initialize a new hash with the new size */ |
| 293 | new_hash = hash_new(size, hash->compare, hash->choose); |
| 294 | |
| 295 | if (new_hash == NULL) |
| 296 | return NULL; |
| 297 | |
| 298 | /* copy the elements */ |
| 299 | for (i = 0; i < hash->size; i++) { |
| 300 | bucket = hash->table[i]; |
| 301 | |
| 302 | while (bucket != NULL) { |
| 303 | hash_add(new_hash, bucket->data); |
| 304 | bucket = bucket->next; |
| 305 | } |
| 306 | } |
| 307 | |
| 308 | /* remove hash and eventual overflow buckets but not the content |
| 309 | * itself. */ |
| 310 | hash_delete(hash, NULL); |
| 311 | |
| 312 | return new_hash; |
| 313 | } |