1/* 2 * Copyright (C) 2006-2010 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 */ 26static 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. */ 39void 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. */ 61void 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 if an iterator 68 * initialized with HASHIT() is supplied as iter. Use the returned 69 * (or supplied) iterator to access the elements until hash_iterate returns 70 * NULL. */ 71 72struct hash_it_t *hash_iterate(struct hashtable_t *hash, 73 struct hash_it_t *iter) 74{ 75 if (!hash) 76 return NULL; 77 if (!iter) 78 return NULL; 79 80 /* sanity checks first (if our bucket got deleted in the last 81 * iteration): */ 82 if (iter->bucket != NULL) { 83 if (iter->first_bucket != NULL) { 84 /* we're on the first element and it got removed after 85 * the last iteration. */ 86 if ((*iter->first_bucket) != iter->bucket) { 87 /* there are still other elements in the list */ 88 if ((*iter->first_bucket) != NULL) { 89 iter->prev_bucket = NULL; 90 iter->bucket = (*iter->first_bucket); 91 iter->first_bucket = 92 &hash->table[iter->index]; 93 return iter; 94 } else { 95 iter->bucket = NULL; 96 } 97 } 98 } else if (iter->prev_bucket != NULL) { 99 /* 100 * we're not on the first element, and the bucket got 101 * removed after the last iteration. the last bucket's 102 * next pointer is not pointing to our actual bucket 103 * anymore. select the next. 104 */ 105 if (iter->prev_bucket->next != iter->bucket) 106 iter->bucket = iter->prev_bucket; 107 } 108 } 109 110 /* now as we are sane, select the next one if there is some */ 111 if (iter->bucket != NULL) { 112 if (iter->bucket->next != NULL) { 113 iter->prev_bucket = iter->bucket; 114 iter->bucket = iter->bucket->next; 115 iter->first_bucket = NULL; 116 return iter; 117 } 118 } 119 120 /* if not returned yet, we've reached the last one on the index and have 121 * to search forward */ 122 iter->index++; 123 /* go through the entries of the hash table */ 124 while (iter->index < hash->size) { 125 if ((hash->table[iter->index]) != NULL) { 126 iter->prev_bucket = NULL; 127 iter->bucket = hash->table[iter->index]; 128 iter->first_bucket = &hash->table[iter->index]; 129 return iter; 130 } else { 131 iter->index++; 132 } 133 } 134 135 /* nothing to iterate over anymore */ 136 return NULL; 137} 138 139/* allocates and clears the hash */ 140struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, 141 hashdata_choose_cb choose) 142{ 143 struct hashtable_t *hash; 144 145 hash = kmalloc(sizeof(struct hashtable_t) , GFP_ATOMIC); 146 147 if (hash == NULL) 148 return NULL; 149 150 hash->size = size; 151 hash->table = kmalloc(sizeof(struct element_t *) * size, GFP_ATOMIC); 152 153 if (hash->table == NULL) { 154 kfree(hash); 155 return NULL; 156 } 157 158 hash_init(hash); 159 160 hash->compare = compare; 161 hash->choose = choose; 162 163 return hash; 164} 165 166/* adds data to the hashtable. returns 0 on success, -1 on error */ 167int hash_add(struct hashtable_t *hash, void *data) 168{ 169 int index; 170 struct element_t *bucket, *prev_bucket = NULL; 171 172 if (!hash) 173 return -1; 174 175 index = hash->choose(data, hash->size); 176 bucket = hash->table[index]; 177 178 while (bucket != NULL) { 179 if (hash->compare(bucket->data, data)) 180 return -1; 181 182 prev_bucket = bucket; 183 bucket = bucket->next; 184 } 185 186 /* found the tail of the list, add new element */ 187 bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC); 188 189 if (bucket == NULL) 190 return -1; 191 192 bucket->data = data; 193 bucket->next = NULL; 194 195 /* and link it */ 196 if (prev_bucket == NULL) 197 hash->table[index] = bucket; 198 else 199 prev_bucket->next = bucket; 200 201 hash->elements++; 202 return 0; 203} 204 205/* finds data, based on the key in keydata. returns the found data on success, 206 * or NULL on error */ 207void *hash_find(struct hashtable_t *hash, void *keydata) 208{ 209 int index; 210 struct element_t *bucket; 211 212 if (!hash) 213 return NULL; 214 215 index = hash->choose(keydata , hash->size); 216 bucket = hash->table[index]; 217 218 while (bucket != NULL) { 219 if (hash->compare(bucket->data, keydata)) 220 return bucket->data; 221 222 bucket = bucket->next; 223 } 224 225 return NULL; 226} 227 228/* remove bucket (this might be used in hash_iterate() if you already found the 229 * bucket you want to delete and don't need the overhead to find it again with 230 * hash_remove(). But usually, you don't want to use this function, as it 231 * fiddles with hash-internals. */ 232void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) 233{ 234 void *data_save; 235 236 data_save = hash_it_t->bucket->data; 237 238 if (hash_it_t->prev_bucket != NULL) 239 hash_it_t->prev_bucket->next = hash_it_t->bucket->next; 240 else if (hash_it_t->first_bucket != NULL) 241 (*hash_it_t->first_bucket) = hash_it_t->bucket->next; 242 243 kfree(hash_it_t->bucket); 244 hash->elements--; 245 246 return data_save; 247} 248 249/* removes data from hash, if found. returns pointer do data on success, so you 250 * can remove the used structure yourself, or NULL on error . data could be the 251 * structure you use with just the key filled, we just need the key for 252 * comparing. */ 253void *hash_remove(struct hashtable_t *hash, void *data) 254{ 255 struct hash_it_t hash_it_t; 256 257 hash_it_t.index = hash->choose(data, hash->size); 258 hash_it_t.bucket = hash->table[hash_it_t.index]; 259 hash_it_t.prev_bucket = NULL; 260 261 while (hash_it_t.bucket != NULL) { 262 if (hash->compare(hash_it_t.bucket->data, data)) { 263 hash_it_t.first_bucket = 264 (hash_it_t.bucket == 265 hash->table[hash_it_t.index] ? 266 &hash->table[hash_it_t.index] : NULL); 267 return hash_remove_bucket(hash, &hash_it_t); 268 } 269 270 hash_it_t.prev_bucket = hash_it_t.bucket; 271 hash_it_t.bucket = hash_it_t.bucket->next; 272 } 273 274 return NULL; 275} 276 277/* resize the hash, returns the pointer to the new hash or NULL on 278 * error. removes the old hash on success. */ 279struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) 280{ 281 struct hashtable_t *new_hash; 282 struct element_t *bucket; 283 int i; 284 285 /* initialize a new hash with the new size */ 286 new_hash = hash_new(size, hash->compare, hash->choose); 287 288 if (new_hash == NULL) 289 return NULL; 290 291 /* copy the elements */ 292 for (i = 0; i < hash->size; i++) { 293 bucket = hash->table[i]; 294 295 while (bucket != NULL) { 296 hash_add(new_hash, bucket->data); 297 bucket = bucket->next; 298 } 299 } 300 301 /* remove hash and eventual overflow buckets but not the content 302 * itself. */ 303 hash_delete(hash, NULL); 304 305 return new_hash; 306} 307