drivers/staging/batman-adv/hash.c

   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 */
  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 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
  72 struct 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 */
 140 struct 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 */
 167 int 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 */
 207 void *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. */
 232 void *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. */
 253 void *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. */
 279 struct 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 }