lib/silcutil/silchashtable.c

   1 /*
   2
   3   silchashtable.c
   4
   5   Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6
   7   Copyright (C) 2001 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; either version 2 of the License, or
  12   (at your option) any later version.
  13
  14   This program is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19 */
  20 /* Implementation of collision resistant hash table. */
  21 /* $Id$ */
  22
  23 #include "silcincludes.h"
  24 #include "silchashtable.h"
  25
  26 /* Default size of the hash table (index to prime table) */
  27 #define SILC_HASH_TABLE_SIZE 3
  28
  29 /* Produce the index by hashing the key */
  30 #define SILC_HASH_TABLE_HASH (ht->hash(key) % primesize[ht->table_size])
  31
  32 /* One entry in the hash table. Includes the key and the associated
  33    context. The `next' pointer is non-NULL if two (or more) different
  34    keys hashed to same value.  The pointer is the pointer to the next
  35    entry. */
  36 typedef struct SilcHashTableEntryStruct {
  37   void *key;
  38   void *context;
  39   struct SilcHashTableEntryStruct *next;
  40 } *SilcHashTableEntry;
  41
  42 /* Hash table. */
  43 struct SilcHashTableStruct {
  44   SilcHashTableEntry *table;
  45   uint32 table_size;
  46   uint32 entry_count;
  47   SilcHashFunction hash;
  48   SilcHashCompare compare;
  49   SilcHashDestructor destructor;
  50 };
  51
  52 /* Prime sizes for the hash table. The size of the table will always
  53    be one of these. */
  54 const uint32 primesize[42] =
  55 {
  56   1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
  57   1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
  58   65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
  59   4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
  60 };
  61
  62 /* Find appropriate size for the hash table. The size will be a prime. */
  63
  64 static uint32 silc_hash_table_primesize(uint32 size, uint32 *index)
  65 {
  66   int i;
  67
  68   for (i = 0; i < sizeof(primesize); i++)
  69     if (primesize[i] >= size) {
  70       *index = i;
  71       return primesize[i];
  72     }
  73
  74   *index = i - 1;
  75   return primesize[i - 1];
  76 }
  77
  78 /* Internal routine to find entry in the hash table by `key'. */
  79
  80 static inline SilcHashTableEntry *
  81 silc_hash_table_find_internal(SilcHashTable ht, void *key,
  82                               SilcHashTableEntry *prev_entry)
  83 {
  84   SilcHashTableEntry *entry, prev = NULL;
  85
  86   entry = &ht->table[SILC_HASH_TABLE_HASH];
  87   if (ht->compare) {
  88     while (*entry && ht->compare((*entry)->key, key) == FALSE) {
  89       prev = *entry;
  90       entry = &(*entry)->next;
  91     }
  92   } else {
  93     while (*entry && (*entry)->key != key) {
  94       prev = *entry;
  95       entry = &(*entry)->next;
  96     }
  97   }
  98
  99   *prev_entry = prev;
 100   return entry;
 101 }
 102
 103 /* Allocates new hash table and returns it.  If the `table_size' is not
 104    zero then the hash table size is the size provided. If zero then the
 105    default size will be used. Note that if the `table_size' is provided
 106    it should be a prime. The `hash', `compare' and `destructor' are
 107    the hash function, the key comparison function and key and context
 108    destructor function, respectively. The `hash' is mandatory, the others
 109    are optional. */
 110
 111 SilcHashTable silc_hash_table_alloc(uint32 table_size,
 112                                     SilcHashFunction hash,
 113                                     SilcHashCompare compare,
 114                                     SilcHashDestructor destructor)
 115 {
 116   SilcHashTable ht;
 117   uint32 size_index = SILC_HASH_TABLE_SIZE;
 118
 119   if (!hash)
 120     return NULL;
 121
 122   ht = silc_calloc(1, sizeof(*ht));
 123   ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
 124                                                                  &size_index) :
 125                           primesize[SILC_HASH_TABLE_SIZE],
 126                           sizeof(*ht->table));
 127   ht->table_size = size_index;
 128   ht->hash = hash;
 129   ht->compare = compare;
 130   ht->destructor = destructor;
 131
 132   return ht;
 133 }
 134
 135 /* Frees the hash table. The destructor function provided in the
 136    silc_hash_table_alloc will be called for all keys in the hash table. */
 137
 138 void silc_hash_table_free(SilcHashTable ht)
 139 {
 140   SilcHashTableEntry e, tmp;
 141   int i;
 142
 143   for (i = 0; i < primesize[ht->table_size]; i++) {
 144     e = ht->table[i];
 145     while (e) {
 146       if (ht->destructor)
 147         ht->destructor(e->key, e->context);
 148       tmp = e;
 149       e = e->next;
 150       silc_free(tmp);
 151     }
 152   }
 153
 154   silc_free(ht->table);
 155   silc_free(ht);
 156 }
 157
 158 /* Returns the size of the hash table */
 159
 160 uint32 silc_hash_table_size(SilcHashTable ht)
 161 {
 162   return primesize[ht->table_size];
 163 }
 164
 165 /* Returns the number of the entires in the hash table. If there is more
 166    entries in the table thatn the size of the hash table calling the
 167    silc_hash_table_rehash is recommended. */
 168
 169 uint32 silc_hash_table_count(SilcHashTable ht)
 170 {
 171   return ht->entry_count;
 172 }
 173
 174 /* Adds new entry to the hash table. The `key' is hashed using the
 175    hash function and the both `key' and `context' will be saved to the
 176    hash table. This function quarantees that the entry is always added
 177    to the hash table reliably (it is collision resistant). */
 178
 179 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 180 {
 181   SilcHashTableEntry *entry;
 182   uint32 index = SILC_HASH_TABLE_HASH;
 183
 184   entry = &ht->table[index];
 185   if (*entry) {
 186     /* The entry exists already. We have a collision, add it to the
 187        list to avoid collision. */
 188     SilcHashTableEntry e, tmp;
 189
 190     e = *entry;
 191     tmp = e->next;
 192     while (tmp) {
 193       e = tmp;
 194       tmp = tmp->next;
 195     }
 196
 197     e->next = silc_calloc(1, sizeof(*e->next));
 198     e->next->key = key;
 199     e->next->context = context;
 200     ht->entry_count++;
 201   } else {
 202     /* New key */
 203     *entry = silc_calloc(1, sizeof(**entry));
 204     (*entry)->key = key;
 205     (*entry)->context = context;
 206     ht->entry_count++;
 207   }
 208 }
 209
 210 /* Same as above but if the `key' already exists in the hash table
 211    the old key and the old context will be replace with the `key' and
 212    the `context. The destructor function will be called for the
 213    replaced key and context. */
 214
 215 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
 216 {
 217   SilcHashTableEntry *entry;
 218   uint32 index = SILC_HASH_TABLE_HASH;
 219
 220   entry = &ht->table[index];
 221   if (*entry) {
 222     /* The entry exists already. We have a collision, replace the old
 223        key and context. */
 224     if (ht->destructor)
 225       ht->destructor((*entry)->key, (*entry)->context);
 226   } else {
 227     /* New key */
 228     *entry = silc_calloc(1, sizeof(**entry));
 229     ht->entry_count++;
 230   }
 231
 232   (*entry)->key = key;
 233   (*entry)->context = context;
 234 }
 235
 236 /* Removes the entry from the hash table by the provided `key'. This will
 237    call the destructor funtion for the found entry. Return TRUE if the
 238    entry was removed successfully and FALSE otherwise. */
 239
 240 bool silc_hash_table_del(SilcHashTable ht, void *key)
 241 {
 242   SilcHashTableEntry *entry, prev, e;
 243
 244   entry = silc_hash_table_find_internal(ht, key, &prev);
 245   if (*entry == NULL)
 246     return FALSE;
 247
 248   e = *entry;
 249
 250   if (!prev && e->next)
 251     *entry = e->next;
 252   if (!prev && e->next == NULL)
 253     *entry = NULL;
 254   if (prev)
 255     prev->next = NULL;
 256   if (prev && e->next)
 257     prev->next = e->next;
 258
 259   if (ht->destructor)
 260     ht->destructor(e->key, e->context);
 261   silc_free(e);
 262
 263   ht->entry_count--;
 264
 265   return TRUE;
 266 }
 267
 268 /* Finds the entry in the hash table by the provided `key' as fast as
 269    possible. Return TRUE if the entry was found and FALSE otherwise.
 270    The found entry is returned to the `ret_key' and `ret_context',
 271    respectively. If the `ret_key and `ret_context' are NULL then this
 272    maybe used only to check whether given key exists in the table. */
 273
 274 bool silc_hash_table_find(SilcHashTable ht, void *key,
 275                           void **ret_key, void **ret_context)
 276 {
 277   SilcHashTableEntry *entry, prev;
 278
 279   entry = silc_hash_table_find_internal(ht, key, &prev);
 280   if (*entry == NULL)
 281     return FALSE;
 282
 283   if (ret_key)
 284     *ret_key = (*entry)->key;
 285   if (ret_context)
 286     *ret_context = (*entry)->context;
 287
 288   return TRUE;
 289 }
 290
 291 /* Rehashs the hash table. The size of the new hash table is provided
 292    as `new_size'. If the `new_size' is zero then this routine will make
 293    the new table of a suitable size. Note that this operation may be
 294    very slow. */
 295
 296 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
 297 {
 298   int i;
 299   SilcHashTableEntry *table, e, tmp;
 300   uint32 table_size, size_index;
 301
 302   /* Take old hash table */
 303   table = ht->table;
 304   table_size = ht->table_size;
 305
 306   /* Allocate new table */
 307   ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
 308                                                                &size_index) :
 309                           silc_hash_table_primesize(ht->entry_count,
 310                                                     &size_index),
 311                           sizeof(*ht->table));
 312   ht->table_size = size_index;
 313
 314   /* Rehash */
 315   for (i = 0; i < primesize[table_size]; i++) {
 316     e = table[i];
 317     while (e) {
 318       silc_hash_table_add(ht, e->key, e->context);
 319       tmp = e;
 320       e = e->next;
 321
 322       /* Remove old entry */
 323       silc_free(tmp);
 324     }
 325   }
 326
 327   /* Remove old table */
 328   silc_free(table);
 329 }