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, hashdata_choose_cb choose)
 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         hash->choose = choose;
 160
 161         return hash;
 162 }
 163
 164 /* adds data to the hashtable. returns 0 on success, -1 on error */
 165 int hash_add(struct hashtable_t *hash, hashdata_compare_cb compare, void *data)
 166 {
 167         int index;
 168         struct element_t *bucket, *prev_bucket = NULL;
 169
 170         if (!hash)
 171                 return -1;
 172
 173         index = hash->choose(data, hash->size);
 174         bucket = hash->table[index];
 175
 176         while (bucket != NULL) {
 177                 if (compare(bucket->data, data))
 178                         return -1;
 179
 180                 prev_bucket = bucket;
 181                 bucket = bucket->next;
 182         }
 183
 184         /* found the tail of the list, add new element */
 185         bucket = kmalloc(sizeof(struct element_t), GFP_ATOMIC);
 186
 187         if (bucket == NULL)
 188                 return -1;
 189
 190         bucket->data = data;
 191         bucket->next = NULL;
 192
 193         /* and link it */
 194         if (prev_bucket == NULL)
 195                 hash->table[index] = bucket;
 196         else
 197                 prev_bucket->next = bucket;
 198
 199         hash->elements++;
 200         return 0;
 201 }
 202
 203 /* finds data, based on the key in keydata. returns the found data on success,
 204  * or NULL on error */
 205 void *hash_find(struct hashtable_t *hash, hashdata_compare_cb compare,
 206                 void *keydata)
 207 {
 208         int index;
 209         struct element_t *bucket;
 210
 211         if (!hash)
 212                 return NULL;
 213
 214         index = hash->choose(keydata , hash->size);
 215         bucket = hash->table[index];
 216
 217         while (bucket != NULL) {
 218                 if (compare(bucket->data, keydata))
 219                         return bucket->data;
 220
 221                 bucket = bucket->next;
 222         }
 223
 224         return NULL;
 225 }
 226
 227 /* remove bucket (this might be used in hash_iterate() if you already found the
 228  * bucket you want to delete and don't need the overhead to find it again with
 229  * hash_remove(). But usually, you don't want to use this function, as it
 230  * fiddles with hash-internals. */
 231 void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t)
 232 {
 233         void *data_save;
 234
 235         data_save = hash_it_t->bucket->data;
 236
 237         if (hash_it_t->prev_bucket != NULL)
 238                 hash_it_t->prev_bucket->next = hash_it_t->bucket->next;
 239         else if (hash_it_t->first_bucket != NULL)
 240                 (*hash_it_t->first_bucket) = hash_it_t->bucket->next;
 241
 242         kfree(hash_it_t->bucket);
 243         hash->elements--;
 244
 245         return data_save;
 246 }
 247
 248 /* removes data from hash, if found. returns pointer do data on success, so you
 249  * can remove the used structure yourself, or NULL on error .  data could be the
 250  * structure you use with just the key filled, we just need the key for
 251  * comparing. */
 252 void *hash_remove(struct hashtable_t *hash, hashdata_compare_cb compare,
 253                   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 (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,
 280                                 hashdata_compare_cb compare, 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, hash->choose);
 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, 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 }