drivers/staging/batman-adv/hash.c

   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 }