src/libstrongswan/utils/hashtable.c

   1 /*
   2  * Copyright (C) 2008 Tobias Brunner
   3  * Hochschule fuer Technik Rapperswil
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   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 MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  *
  15  * $Id$
  16  */
  17
  18 #include <utils/linked_list.h>
  19
  20 #include "hashtable.h"
  21
  22 /** The maximum capacity of the hash table (MUST be a power of 2) */
  23 #define MAX_CAPACITY (1 << 30)
  24
  25 typedef struct pair_t pair_t;
  26
  27 /**
  28  * This pair holds a pointer to the key and value it represents.
  29  */
  30 struct pair_t {
  31         /**
  32          * Key of a hash table item.
  33          */
  34         void *key;
  35
  36         /**
  37          * Value of a hash table item.
  38          */
  39         void *value;
  40
  41         /**
  42          * Cached hash (used in case of a resize).
  43          */
  44         u_int hash;
  45 };
  46
  47 /**
  48  * Creates an empty pair object.
  49  */
  50 pair_t *pair_create(void *key, void *value, u_int hash)
  51 {
  52         pair_t *this = malloc_thing(pair_t);
  53
  54         this->key = key;
  55         this->value = value;
  56         this->hash = hash;
  57
  58         return this;
  59 }
  60
  61 typedef struct private_hashtable_t private_hashtable_t;
  62
  63 /**
  64  * Private data of a hashtable_t object.
  65  *
  66  */
  67 struct private_hashtable_t {
  68         /**
  69          * Public part of hash table.
  70          */
  71         hashtable_t public;
  72
  73         /**
  74          * The number of items in the hash table.
  75          */
  76         u_int count;
  77
  78         /**
  79          * The current capacity of the hash table (always a power of 2).
  80          */
  81         u_int capacity;
  82
  83         /**
  84          * The current mask to calculate the row index (capacity - 1).
  85          */
  86         u_int mask;
  87
  88         /**
  89          * The load factor.
  90          */
  91         float load_factor;
  92
  93         /**
  94          * The actual table.
  95          */
  96         linked_list_t **table;
  97
  98         /**
  99          * The hashing function.
 100          */
 101         hashtable_hash_t hash;
 102
 103         /**
 104          * The equality function.
 105          */
 106         hashtable_equals_t equals;
 107 };
 108
 109 typedef struct private_enumerator_t private_enumerator_t;
 110
 111 /**
 112  * hash table enumerator implementation
 113  */
 114 struct private_enumerator_t {
 115
 116         /**
 117          * implements enumerator interface
 118          */
 119         enumerator_t enumerator;
 120
 121         /**
 122          * associated hash table
 123          */
 124         private_hashtable_t *table;
 125
 126         /**
 127          * current row index
 128          */
 129         u_int row;
 130
 131         /**
 132          * enumerator for the current row
 133          */
 134         enumerator_t *current;
 135 };
 136
 137 /**
 138  * Compare a pair in a list with the given key.
 139  */
 140 static inline bool pair_equals(pair_t *pair, private_hashtable_t *this, void *key)
 141 {
 142         return this->equals(key, pair->key);
 143 }
 144
 145 /**
 146  * This function returns the next-highest power of two for the given number.
 147  * The algorithm works by setting all bits on the right-hand side of the most
 148  * significant 1 to 1 and then increments the whole number so it rolls over
 149  * to the nearest power of two. Note: returns 0 for n == 0
 150  */
 151 static u_int get_nearest_powerof2(u_int n)
 152 {
 153         u_int i;
 154         --n;
 155         for (i = 1; i < sizeof(u_int) * 8; i <<= 1)
 156         {
 157                 n |= n >> i;
 158         }
 159         return ++n;
 160 }
 161
 162 /**
 163  * Init hash table parameters
 164  */
 165 static void init_hashtable(private_hashtable_t *this, u_int capacity)
 166 {
 167         capacity = max(1, min(capacity, MAX_CAPACITY));
 168         this->count = 0;
 169         this->capacity = get_nearest_powerof2(capacity);
 170         this->mask = this->capacity - 1;
 171         this->load_factor = 0.75;
 172
 173         this->table = (linked_list_t**)calloc(this->capacity, sizeof(linked_list_t*));
 174         memset(this->table, 0, this->capacity * sizeof(linked_list_t*));
 175 }
 176
 177 /**
 178  * Double the size of the hash table and rehash all the elements.
 179  */
 180 static void rehash(private_hashtable_t *this)
 181 {
 182         u_int row;
 183         u_int old_capacity = this->capacity;
 184         linked_list_t **old_table = this->table;
 185
 186         if (old_capacity >= MAX_CAPACITY)
 187         {
 188                 return;
 189         }
 190
 191         init_hashtable(this, old_capacity << 1);
 192
 193         for (row = 0; row < old_capacity; ++row)
 194         {
 195                 linked_list_t *list;
 196                 if ((list = old_table[row]) != NULL)
 197                 {
 198                         pair_t *pair;
 199                         enumerator_t *enumerator = list->create_enumerator(list);
 200                         while (enumerator->enumerate(enumerator, &pair))
 201                         {
 202                                 linked_list_t *new_list;
 203                                 u_int new_row = pair->hash & this->mask;
 204                                 list->remove_at(list, enumerator);
 205                                 if ((new_list = this->table[new_row]) == NULL)
 206                                 {
 207                                         new_list = this->table[new_row] = linked_list_create();
 208                                 }
 209                                 new_list->insert_last(new_list, pair);
 210                         }
 211                         enumerator->destroy(enumerator);
 212                         list->destroy(list);
 213                 }
 214         }
 215         free(old_table);
 216 }
 217
 218 /**
 219  * Implementation of hashtable_t.put
 220  */
 221 static void *put(private_hashtable_t *this, void *key, void *value)
 222 {
 223         linked_list_t *list;
 224         void *old_value = NULL;
 225         u_int hash = this->hash(key);
 226         u_int row = hash & this->mask;
 227
 228         if ((list = this->table[row]) != NULL)
 229         {
 230                 pair_t *pair;
 231                 enumerator_t *enumerator = list->create_enumerator(list);
 232                 while (enumerator->enumerate(enumerator, &pair))
 233                 {
 234                         if (pair_equals(pair, this, key))
 235                         {
 236                                 old_value = pair->value;
 237                                 pair->value = value;
 238                                 break;
 239                         }
 240                 }
 241                 enumerator->destroy(enumerator);
 242         }
 243         else
 244         {
 245                 list = this->table[row] = linked_list_create();
 246         }
 247
 248         if (!old_value)
 249         {
 250                 list->insert_last(list, pair_create(key, value, hash));
 251                 this->count++;
 252         }
 253
 254         if (this->count >= this->capacity * this->load_factor)
 255         {
 256                 rehash(this);
 257         }
 258
 259         return old_value;
 260 }
 261
 262 /**
 263  * Implementation of hashtable_t.get
 264  */
 265 static void *get(private_hashtable_t *this, void *key)
 266 {
 267         void *value = NULL;
 268         linked_list_t *list;
 269         u_int row = this->hash(key) & this->mask;
 270
 271         if ((list = this->table[row]) != NULL)
 272         {
 273                 pair_t *pair;
 274                 if (list->find_first(list, (linked_list_match_t)pair_equals,
 275                                 (void**)&pair, this, key) == SUCCESS)
 276                 {
 277                         value = pair->value;
 278                 }
 279         }
 280
 281         return value;
 282 }
 283
 284 /**
 285  * Implementation of hashtable_t.remove
 286  */
 287 static void *remove(private_hashtable_t *this, void *key)
 288 {
 289         void *value = NULL;
 290         linked_list_t *list;
 291         u_int row = this->hash(key) & this->mask;
 292
 293         if ((list = this->table[row]) != NULL)
 294         {
 295                 pair_t *pair;
 296                 enumerator_t *enumerator = list->create_enumerator(list);
 297                 while (enumerator->enumerate(enumerator, &pair))
 298                 {
 299                         if (pair_equals(pair, this, key))
 300                         {
 301                                 list->remove_at(list, enumerator);
 302                                 value = pair->value;
 303                                 this->count--;
 304                                 free(pair);
 305                                 break;
 306                         }
 307                 }
 308                 enumerator->destroy(enumerator);
 309         }
 310
 311         return value;
 312 }
 313
 314 /**
 315  * Implementation of hashtable_t.get_count
 316  */
 317 static u_int get_count(private_hashtable_t *this)
 318 {
 319         return this->count;
 320 }
 321
 322 /**
 323  * Implementation of private_enumerator_t.enumerator.enumerate.
 324  */
 325 static bool enumerate(private_enumerator_t *this, void **item)
 326 {
 327         while (this->row < this->table->capacity)
 328         {
 329                 if (this->current)
 330                 {
 331                         pair_t *pair;
 332                         if (this->current->enumerate(this->current, (void**)&pair))
 333                         {
 334                                 *item = pair->value;
 335                                 return TRUE;
 336                         }
 337                         this->current->destroy(this->current);
 338                         this->current = NULL;
 339                 }
 340                 else
 341                 {
 342                         linked_list_t *list;
 343                         if ((list = this->table->table[this->row]) != NULL)
 344                         {
 345                                 this->current = list->create_enumerator(list);
 346                                 continue;
 347                         }
 348                 }
 349                 this->row++;
 350         }
 351         return FALSE;
 352 }
 353
 354 /**
 355  * Implementation of private_enumerator_t.enumerator.destroy.
 356  */
 357 static void enumerator_destroy(private_enumerator_t *this)
 358 {
 359         if (this->current)
 360         {
 361                 this->current->destroy(this->current);
 362         }
 363         free(this);
 364 }
 365
 366 /**
 367  * Implementation of hashtable_t.create_enumerator.
 368  */
 369 static enumerator_t* create_enumerator(private_hashtable_t *this)
 370 {
 371         private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
 372
 373         enumerator->enumerator.enumerate = (void*)enumerate;
 374         enumerator->enumerator.destroy = (void*)enumerator_destroy;
 375         enumerator->table = this;
 376         enumerator->row = 0;
 377         enumerator->current = NULL;
 378
 379         return &enumerator->enumerator;
 380 }
 381
 382 /**
 383  * Implementation of hashtable_t.destroy
 384  */
 385 static void destroy(private_hashtable_t *this)
 386 {
 387         u_int row;
 388         for (row = 0; row < this->capacity; ++row)
 389         {
 390                 linked_list_t *list;
 391                 if ((list = this->table[row]) != NULL)
 392                 {
 393                         list->destroy_function(list, free);
 394                 }
 395         }
 396         free(this->table);
 397         free(this);
 398 }
 399
 400 /*
 401  * Described in header.
 402  */
 403 hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
 404                                                           u_int capacity)
 405 {
 406         private_hashtable_t *this = malloc_thing(private_hashtable_t);
 407
 408         this->public.put = (void*(*)(hashtable_t*,void*,void*))put;
 409         this->public.get = (void*(*)(hashtable_t*,void*))get;
 410         this->public.remove = (void*(*)(hashtable_t*,void*))remove;
 411         this->public.get_count = (u_int(*)(hashtable_t*))get_count;
 412         this->public.create_enumerator = (enumerator_t*(*)(hashtable_t*))create_enumerator;
 413         this->public.destroy = (void(*)(hashtable_t*))destroy;
 414
 415         this->count = 0;
 416         this->capacity = 0;
 417         this->mask = 0;
 418         this->load_factor = 0;
 419         this->table = NULL;
 420         this->hash = hash;
 421         this->equals = equals;
 422
 423         init_hashtable(this, capacity);
 424
 425         return &this->public;
 426 }