drivers/staging/batman-adv/hash.h

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