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 static 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, void *arg)
  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, arg);
  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)
 141 {
 142         struct hashtable_t *hash;
 143
 144         hash = kmalloc(sizeof(struct hashtable_t) , GFP_ATOMIC);
 145
 146         if (hash == NULL)
 147                 return NULL;
 148
 149         hash->size = size;
 150         hash->table = kmalloc(sizeof(struct element_t *) * size, GFP_ATOMIC);
 151
 152         if (hash->table == NULL) {
 153                 kfree(hash);
 154                 return NULL;
 155         }
 156
 157         hash_init(hash);
 158
 159         return hash;
 160 }
 161
 162 /* adds data to the hashtable. returns 0 on success, -1 on error */
 163 int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare,
 164              hashdata_choose_cb choose, void *data)
 165 {
 166         int index;
 167         struct element_t *bucket, *prev_bucket = NULL;
 168
 169         if (!hash)
 170                 return -1;
 171
 172         index = choose(data, hash->size);
 173         bucket = hash->table[index];
 174
 175         while (bucket != NULL) {
 176                 if (compare(bucket->data, data))
 177                         return -1;
 178
 179                 prev_bucket = bucket;
 180                 bucket = bucket->next;
 181         }
 182
 183         /* found the tail of the list, add new element */
 184         bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC);
 185
 186         if (bucket == NULL)
 187                 return -1;
 188
 189         bucket->data = data;
 190         bucket->next = NULL;
 191
 192         /* and link it */
 193         if (prev_bucket == NULL)
 194                 hash->table[index] = bucket;
 195         else
 196                 prev_bucket->next = bucket;
 197
 198         hash->elements++;
 199         return 0;
 200 }
 201
 202 /* finds data, based on the key in keydata. returns the found data on success,
 203  * or NULL on error */
 204 void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare,
 205                 hashdata_choose_cb choose, void *keydata)
 206 {
 207         int index;
 208         struct element_t *bucket;
 209
 210         if (!hash)
 211                 return NULL;
 212
 213         index = choose(keydata , hash->size);
 214         bucket = hash->table[index];
 215
 216         while (bucket != NULL) {
 217                 if (compare(bucket->data, keydata))
 218                         return bucket->data;
 219
 220                 bucket = bucket->next;
 221         }
 222
 223         return NULL;
 224 }
 225
 226 /* remove bucket (this might be used in hash_iterate() if you already found the
 227  * bucket you want to delete and don't need the overhead to find it again with
 228  * hash_remove(). But usually, you don't want to use this function, as it
 229  * fiddles with hash-internals. */
 230 void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t)
 231 {
 232         void *data_save;
 233
 234         data_save = hash_it_t->bucket->data;
 235
 236         if (hash_it_t->prev_bucket != NULL)
 237                 hash_it_t->prev_bucket->next = hash_it_t->bucket->next;
 238         else if (hash_it_t->first_bucket != NULL)
 239                 (*hash_it_t->first_bucket) = hash_it_t->bucket->next;
 240
 241         kfree(hash_it_t->bucket);
 242         hash->elements--;
 243
 244         return data_save;
 245 }
 246
 247 /* removes data from hash, if found. returns pointer do data on success, so you
 248  * can remove the used structure yourself, or NULL on error .  data could be the
 249  * structure you use with just the key filled, we just need the key for
 250  * comparing. */
 251 void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare,
 252                   hashdata_choose_cb choose, void *data)
 253 {
 254         struct hash_it_t hash_it_t;
 255
 256         hash_it_t.index = choose(data, hash->size);
 257         hash_it_t.bucket = hash->table[hash_it_t.index];
 258         hash_it_t.prev_bucket = NULL;
 259
 260         while (hash_it_t.bucket != NULL) {
 261                 if (compare(hash_it_t.bucket->data, data)) {
 262                         hash_it_t.first_bucket =
 263                                 (hash_it_t.bucket ==
 264                                  hash->table[hash_it_t.index] ?
 265                                  &hash->table[hash_it_t.index] : NULL);
 266                         return hash_remove_bucket(hash, &hash_it_t);
 267                 }
 268
 269                 hash_it_t.prev_bucket = hash_it_t.bucket;
 270                 hash_it_t.bucket = hash_it_t.bucket->next;
 271         }
 272
 273         return NULL;
 274 }
 275
 276 /* resize the hash, returns the pointer to the new hash or NULL on
 277  * error. removes the old hash on success. */
 278 struct hashtable_t *hash_resize(struct hashtable_t *hash,
 279                                 hashdata_compare_cb compare,
 280                                 hashdata_choose_cb choose, int size)
 281 {
 282         struct hashtable_t *new_hash;
 283         struct element_t *bucket;
 284         int i;
 285
 286         /* initialize a new hash with the new size */
 287         new_hash = hash_new(size);
 288
 289         if (new_hash == NULL)
 290                 return NULL;
 291
 292         /* copy the elements */
 293         for (i = 0; i < hash->size; i++) {
 294                 bucket = hash->table[i];
 295
 296                 while (bucket != NULL) {
 297                         hash_add(new_hash, compare, choose, bucket->data);
 298                         bucket = bucket->next;
 299                 }
 300         }
 301
 302         /* remove hash and eventual overflow buckets but not the content
 303          * itself. */
 304         hash_delete(hash, NULL, NULL);
 305
 306         return new_hash;
 307 }