lib/silcutil/silchashtable.c

   1 /*
   2
   3   silchashtable.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2001 - 2002 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; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19 /* Implementation of collision resistant hash table. This is a hash table
  20    that provides a reliable (what you add stays there, and duplicate keys
  21    are allowed) with as fast reference to the key as possible. If duplicate
  22    keys are a lot in the hash table the lookup gets slower of course.
  23    However, this is reliable and no data is lost at any point. If you know
  24    that you never have duplicate keys then this is as fast as any simple
  25    hash table. */
  26 /* $Id$ */
  27
  28 #include "silcincludes.h"
  29 #include "silchashtable.h"
  30
  31 /* Define to 1 if you want hash table debug enabled */
  32 #define SILC_HASH_TABLE_DEBUG 0
  33
  34 #if SILC_HASH_TABLE_DEBUG == 1
  35 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
  36 #else
  37 #define SILC_HT_DEBUG(fmt)
  38 #endif
  39
  40 /* Default size of the hash table (index to prime table) */
  41 #define SILC_HASH_TABLE_SIZE 3
  42
  43 /* Produce the index by hashing the key */
  44 #define SILC_HASH_TABLE_HASH(f, c) \
  45   ((f)(key, (c)) % primesize[ht->table_size])
  46
  47 /* Check whether need to rehash */
  48 #define SILC_HASH_REHASH_INC \
  49   (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
  50 #define SILC_HASH_REHASH_DEC \
  51   (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
  52    ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
  53
  54 /* One entry in the hash table. Includes the key and the associated
  55    context. The `next' pointer is non-NULL if two (or more) different
  56    keys hashed to same value.  The pointer is the pointer to the next
  57    entry. */
  58 typedef struct SilcHashTableEntryStruct {
  59   void *key;
  60   void *context;
  61   struct SilcHashTableEntryStruct *next;
  62 } *SilcHashTableEntry;
  63
  64 /* Hash table. */
  65 struct SilcHashTableStruct {
  66   SilcHashTableEntry *table;
  67   SilcUInt32 table_size;
  68   SilcUInt32 entry_count;
  69   SilcHashFunction hash;
  70   SilcHashCompare compare;
  71   SilcHashDestructor destructor;
  72   void *hash_user_context;
  73   void *compare_user_context;
  74   void *destructor_user_context;
  75   bool auto_rehash;
  76 };
  77
  78 /* Prime sizes for the hash table. The size of the table will always
  79    be one of these. */
  80 const SilcUInt32 primesize[42] =
  81 {
  82   1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
  83   1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
  84   65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
  85   4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
  86 };
  87
  88 /* Find appropriate size for the hash table. The size will be a prime. */
  89
  90 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
  91 {
  92   int i;
  93
  94   for (i = 0; i < sizeof(primesize); i++)
  95     if (primesize[i] >= size) {
  96       *index = i;
  97       SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
  98       return primesize[i];
  99     }
 100
 101   *index = i - 1;
 102   SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
 103   return primesize[i - 1];
 104 }
 105
 106 /* Internal routine to find entry in the hash table by `key'. Returns
 107    the previous entry (if exists) as well. */
 108
 109 static inline SilcHashTableEntry *
 110 silc_hash_table_find_internal(SilcHashTable ht, void *key,
 111                               SilcHashTableEntry *prev_entry,
 112                               SilcHashFunction hash, void *hash_user_context,
 113                               SilcHashCompare compare,
 114                               void *compare_user_context)
 115 {
 116   SilcHashTableEntry *entry, prev = NULL;
 117   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 118
 119   SILC_HT_DEBUG(("index %d key %p", i, key));
 120
 121   entry = &ht->table[i];
 122   if (compare) {
 123     while (*entry && !compare((*entry)->key, key, compare_user_context)) {
 124       prev = *entry;
 125       entry = &(*entry)->next;
 126     }
 127   } else {
 128     while (*entry && (*entry)->key != key) {
 129       prev = *entry;
 130       entry = &(*entry)->next;
 131     }
 132   }
 133
 134   *prev_entry = prev;
 135   return entry;
 136 }
 137
 138 /* Internal routine to find entry in the hash table by `key' and `context'.
 139    Returns the previous entry (if exists) as well to `prev_entry'. */
 140
 141 static inline SilcHashTableEntry *
 142 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
 143                                       void *context,
 144                                       SilcHashTableEntry *prev_entry,
 145                                       SilcHashFunction hash,
 146                                       void *hash_user_context,
 147                                       SilcHashCompare compare,
 148                                       void *compare_user_context)
 149 {
 150   SilcHashTableEntry *entry, prev = NULL;
 151   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 152
 153   SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
 154
 155   entry = &ht->table[i];
 156   if (ht->compare) {
 157     while (*entry) {
 158       if (compare((*entry)->key, key, compare_user_context) &&
 159           (*entry)->context == context)
 160         break;
 161       prev = *entry;
 162       entry = &(*entry)->next;
 163     }
 164   } else {
 165     while (*entry) {
 166       if ((*entry)->key == key && (*entry)->context == context)
 167         break;
 168       prev = *entry;
 169       entry = &(*entry)->next;
 170     }
 171   }
 172
 173   if (prev_entry)
 174     *prev_entry = prev;
 175   return entry;
 176 }
 177
 178 /* Internal routine to find entry in the hash table by `key'. */
 179
 180 static inline SilcHashTableEntry *
 181 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
 182                                      SilcHashFunction hash,
 183                                      void *hash_user_context,
 184                                      SilcHashCompare compare,
 185                                      void *compare_user_context)
 186 {
 187   SilcHashTableEntry *entry;
 188   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 189
 190   SILC_HT_DEBUG(("index %d key %p", i, key));
 191
 192   entry = &ht->table[i];
 193   if (compare) {
 194     while (*entry && !compare((*entry)->key, key, compare_user_context))
 195       entry = &(*entry)->next;
 196   } else {
 197     while (*entry && (*entry)->key != key)
 198       entry = &(*entry)->next;
 199   }
 200
 201   return entry;
 202 }
 203
 204 /* Internal routine to find all keys by `key'. This may return multiple
 205    entries if multiple entries with same key exists. With specific
 206    hash and comparison functions. */
 207
 208 static inline void
 209 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
 210                                   SilcHashFunction hash,
 211                                   void *hash_user_context,
 212                                   SilcHashCompare compare,
 213                                   void *compare_user_context,
 214                                   SilcHashForeach foreach,
 215                                   void *foreach_user_context)
 216 {
 217   SilcHashTableEntry *entry, *tmp;
 218   bool auto_rehash;
 219   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 220
 221   SILC_HT_DEBUG(("index %d key %p", i, key));
 222
 223   /* Disallow auto rehashing while going through the table since we call
 224      the `foreach' function which could alter the table. */
 225   auto_rehash = ht->auto_rehash;
 226   ht->auto_rehash = FALSE;
 227
 228   entry = &ht->table[i];
 229   if (compare) {
 230     while (*entry) {
 231       if (compare((*entry)->key, key, compare_user_context)) {
 232         tmp = &(*entry)->next;
 233         foreach((*entry)->key, (*entry)->context, foreach_user_context);
 234         entry = tmp;
 235         continue;
 236       }
 237       entry = &(*entry)->next;
 238     }
 239   } else {
 240     while (*entry) {
 241       if ((*entry)->key == key) {
 242         tmp = &(*entry)->next;
 243         foreach((*entry)->key, (*entry)->context, foreach_user_context);
 244         entry = tmp;
 245         continue;
 246       }
 247       entry = &(*entry)->next;
 248     }
 249   }
 250
 251   ht->auto_rehash = auto_rehash;
 252 }
 253
 254 /* Internal routine to add new key to the hash table */
 255
 256 static inline void
 257 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
 258                              SilcHashFunction hash,
 259                              void *hash_user_context)
 260 {
 261   SilcHashTableEntry *entry;
 262   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 263
 264   SILC_HT_DEBUG(("index %d key %p", i, key));
 265
 266   entry = &ht->table[i];
 267   if (*entry) {
 268     /* The entry exists already. We have a collision, add it to the
 269        list to avoid collision. */
 270     SilcHashTableEntry e, tmp;
 271
 272     e = *entry;
 273     tmp = e->next;
 274     while (tmp) {
 275       e = tmp;
 276       tmp = tmp->next;
 277     }
 278
 279     SILC_HT_DEBUG(("Collision; adding new key to list"));
 280
 281     e->next = silc_calloc(1, sizeof(*e->next));
 282     e->next->key = key;
 283     e->next->context = context;
 284     ht->entry_count++;
 285   } else {
 286     /* New key */
 287     SILC_HT_DEBUG(("New key"));
 288     *entry = silc_calloc(1, sizeof(**entry));
 289     (*entry)->key = key;
 290     (*entry)->context = context;
 291     ht->entry_count++;
 292   }
 293
 294   if (SILC_HASH_REHASH_INC)
 295     silc_hash_table_rehash(ht, 0);
 296 }
 297
 298 /* Internal routine to replace old key with new one (if it exists) */
 299
 300 static inline void
 301 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 302                                  SilcHashFunction hash,
 303                                  void *hash_user_context)
 304 {
 305   SilcHashTableEntry *entry;
 306   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 307
 308   SILC_HT_DEBUG(("index %d key %p", i, key));
 309
 310   entry = &ht->table[i];
 311   if (*entry) {
 312     /* The entry exists already. We have a collision, replace the old
 313        key and context. */
 314     if (ht->destructor)
 315       ht->destructor((*entry)->key, (*entry)->context,
 316                      ht->destructor_user_context);
 317   } else {
 318     /* New key */
 319     *entry = silc_calloc(1, sizeof(**entry));
 320     ht->entry_count++;
 321   }
 322
 323   (*entry)->key = key;
 324   (*entry)->context = context;
 325
 326   if (SILC_HASH_REHASH_INC)
 327     silc_hash_table_rehash(ht, 0);
 328 }
 329
 330 /* Allocates new hash table and returns it.  If the `table_size' is not
 331    zero then the hash table size is the size provided. If zero then the
 332    default size will be used. Note that if the `table_size' is provided
 333    it should be a prime. The `hash', `compare' and `destructor' are
 334    the hash function, the key comparison function and key and context
 335    destructor function, respectively. The `hash' is mandatory, the others
 336    are optional. */
 337
 338 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
 339                                     SilcHashFunction hash,
 340                                     void *hash_user_context,
 341                                     SilcHashCompare compare,
 342                                     void *compare_user_context,
 343                                     SilcHashDestructor destructor,
 344                                     void *destructor_user_context,
 345                                     bool auto_rehash)
 346 {
 347   SilcHashTable ht;
 348   SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
 349
 350   if (!hash)
 351     return NULL;
 352
 353   ht = silc_calloc(1, sizeof(*ht));
 354   ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
 355                                                                  &size_index) :
 356                           primesize[SILC_HASH_TABLE_SIZE],
 357                           sizeof(*ht->table));
 358   ht->table_size = size_index;
 359   ht->hash = hash;
 360   ht->compare = compare;
 361   ht->destructor = destructor;
 362   ht->hash_user_context = hash_user_context;
 363   ht->compare_user_context = compare_user_context;
 364   ht->destructor_user_context = destructor_user_context;
 365   ht->auto_rehash = auto_rehash;
 366
 367   return ht;
 368 }
 369
 370 /* Frees the hash table. The destructor function provided in the
 371    silc_hash_table_alloc will be called for all keys in the hash table. */
 372
 373 void silc_hash_table_free(SilcHashTable ht)
 374 {
 375   SilcHashTableEntry e, tmp;
 376   int i;
 377
 378   for (i = 0; i < primesize[ht->table_size]; i++) {
 379     e = ht->table[i];
 380     while (e) {
 381       if (ht->destructor)
 382         ht->destructor(e->key, e->context, ht->destructor_user_context);
 383       tmp = e;
 384       e = e->next;
 385       silc_free(tmp);
 386     }
 387   }
 388
 389   silc_free(ht->table);
 390   silc_free(ht);
 391 }
 392
 393 /* Returns the size of the hash table */
 394
 395 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
 396 {
 397   return primesize[ht->table_size];
 398 }
 399
 400 /* Returns the number of the entires in the hash table. If there is more
 401    entries in the table thatn the size of the hash table calling the
 402    silc_hash_table_rehash is recommended. */
 403
 404 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
 405 {
 406   return ht->entry_count;
 407 }
 408
 409 /* Adds new entry to the hash table. The `key' is hashed using the
 410    hash function and the both `key' and `context' will be saved to the
 411    hash table. This function quarantees that the entry is always added
 412    to the hash table reliably (it is collision resistant). */
 413
 414 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 415 {
 416   silc_hash_table_add_internal(ht, key, context, ht->hash,
 417                                ht->hash_user_context);
 418 }
 419
 420 /* Same as above but with specific hash function and user context. */
 421
 422 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 423                              SilcHashFunction hash, void *hash_user_context)
 424 {
 425   silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
 426 }
 427
 428 /* Same as above but if the `key' already exists in the hash table
 429    the old key and the old context will be replace with the `key' and
 430    the `context. The destructor function will be called for the
 431    replaced key and context. */
 432
 433 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
 434 {
 435   silc_hash_table_replace_internal(ht, key, context, ht->hash,
 436                                    ht->hash_user_context);
 437 }
 438
 439 /* Same as above but with specific hash function. */
 440
 441 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
 442                                  SilcHashFunction hash,
 443                                  void *hash_user_context)
 444 {
 445   silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
 446 }
 447
 448 /* Removes the entry from the hash table by the provided `key'. This will
 449    call the destructor funtion for the found entry. Return TRUE if the
 450    entry was removed successfully and FALSE otherwise. */
 451
 452 bool silc_hash_table_del(SilcHashTable ht, void *key)
 453 {
 454   SilcHashTableEntry *entry, prev, e;
 455
 456   entry = silc_hash_table_find_internal(ht, key, &prev,
 457                                         ht->hash, ht->hash_user_context,
 458                                         ht->compare, ht->compare_user_context);
 459   if (*entry == NULL)
 460     return FALSE;
 461
 462   e = *entry;
 463
 464   if (!prev && e->next)
 465     *entry = e->next;
 466   if (!prev && e->next == NULL)
 467     *entry = NULL;
 468   if (prev)
 469     prev->next = NULL;
 470   if (prev && e->next)
 471     prev->next = e->next;
 472
 473   if (ht->destructor)
 474     ht->destructor(e->key, e->context, ht->destructor_user_context);
 475   silc_free(e);
 476
 477   ht->entry_count--;
 478
 479   if (SILC_HASH_REHASH_DEC)
 480     silc_hash_table_rehash(ht, 0);
 481
 482   return TRUE;
 483 }
 484
 485 /* Same as above but with specific hash and compare functions. */
 486
 487 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 488                              SilcHashFunction hash,
 489                              void *hash_user_context,
 490                              SilcHashCompare compare,
 491                              void *compare_user_context,
 492                              SilcHashDestructor destructor,
 493                              void *destructor_user_context)
 494 {
 495   SilcHashTableEntry *entry, prev, e;
 496
 497   entry = silc_hash_table_find_internal(ht, key, &prev,
 498                                         hash ? hash : ht->hash,
 499                                         hash_user_context ? hash_user_context :
 500                                         ht->hash_user_context,
 501                                         compare ? compare : ht->compare,
 502                                         compare_user_context ?
 503                                         compare_user_context :
 504                                         ht->compare_user_context);
 505   if (*entry == NULL)
 506     return FALSE;
 507
 508   e = *entry;
 509
 510   if (!prev && e->next)
 511     *entry = e->next;
 512   if (!prev && e->next == NULL)
 513     *entry = NULL;
 514   if (prev)
 515     prev->next = NULL;
 516   if (prev && e->next)
 517     prev->next = e->next;
 518
 519   if (destructor) {
 520     destructor(e->key, e->context, destructor_user_context);
 521   } else {
 522     if (ht->destructor)
 523       ht->destructor(e->key, e->context, ht->destructor_user_context);
 524   }
 525   silc_free(e);
 526
 527   ht->entry_count--;
 528
 529   if (SILC_HASH_REHASH_DEC)
 530     silc_hash_table_rehash(ht, 0);
 531
 532   return TRUE;
 533 }
 534
 535 /* Same as above but verifies that the context associated with the `key'
 536    matches the `context'. This is handy to use with hash tables that may
 537    have duplicate keys. In that case the `context' may be used to check
 538    whether the correct entry is being deleted. */
 539
 540 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 541                                     void *context)
 542 {
 543   SilcHashTableEntry *entry, prev, e;
 544
 545   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 546                                                 ht->hash,
 547                                                 ht->hash_user_context,
 548                                                 ht->compare,
 549                                                 ht->compare_user_context);
 550   if (*entry == NULL)
 551     return FALSE;
 552
 553   e = *entry;
 554
 555   if (!prev && e->next)
 556     *entry = e->next;
 557   if (!prev && e->next == NULL)
 558     *entry = NULL;
 559   if (prev)
 560     prev->next = NULL;
 561   if (prev && e->next)
 562     prev->next = e->next;
 563
 564   if (ht->destructor)
 565     ht->destructor(e->key, e->context, ht->destructor_user_context);
 566   silc_free(e);
 567
 568   ht->entry_count--;
 569
 570   if (SILC_HASH_REHASH_DEC)
 571     silc_hash_table_rehash(ht, 0);
 572
 573   return TRUE;
 574 }
 575
 576 /* Same as above but with specific hash and compare functions. */
 577
 578 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 579                                         void *context,
 580                                         SilcHashFunction hash,
 581                                         void *hash_user_context,
 582                                         SilcHashCompare compare,
 583                                         void *compare_user_context,
 584                                         SilcHashDestructor destructor,
 585                                         void *destructor_user_context)
 586 {
 587   SilcHashTableEntry *entry, prev, e;
 588
 589   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 590                                                 hash ? hash : ht->hash,
 591                                                 hash_user_context ?
 592                                                 hash_user_context :
 593                                                 ht->hash_user_context,
 594                                                 compare ?
 595                                                 compare : ht->compare,
 596                                                 compare_user_context ?
 597                                                 compare_user_context :
 598                                                 ht->compare_user_context);
 599   if (*entry == NULL)
 600     return FALSE;
 601
 602   e = *entry;
 603
 604   if (!prev && e->next)
 605     *entry = e->next;
 606   if (!prev && e->next == NULL)
 607     *entry = NULL;
 608   if (prev)
 609     prev->next = NULL;
 610   if (prev && e->next)
 611     prev->next = e->next;
 612
 613   if (destructor) {
 614     destructor(e->key, e->context, destructor_user_context);
 615   } else {
 616     if (ht->destructor)
 617       ht->destructor(e->key, e->context, ht->destructor_user_context);
 618   }
 619   silc_free(e);
 620
 621   ht->entry_count--;
 622
 623   if (SILC_HASH_REHASH_DEC)
 624     silc_hash_table_rehash(ht, 0);
 625
 626   return TRUE;
 627 }
 628
 629 /* Finds the entry in the hash table by the provided `key' as fast as
 630    possible. Return TRUE if the entry was found and FALSE otherwise.
 631    The found entry is returned to the `ret_key' and `ret_context',
 632    respectively. If the `ret_key and `ret_context' are NULL then this
 633    maybe used only to check whether given key exists in the table. */
 634
 635 bool silc_hash_table_find(SilcHashTable ht, void *key,
 636                           void **ret_key, void **ret_context)
 637 {
 638   SilcHashTableEntry *entry;
 639
 640   entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
 641                                                ht->hash_user_context,
 642                                                ht->compare,
 643                                                ht->compare_user_context);
 644   if (*entry == NULL)
 645     return FALSE;
 646
 647   if (ret_key)
 648     *ret_key = (*entry)->key;
 649   if (ret_context)
 650     *ret_context = (*entry)->context;
 651
 652   return TRUE;
 653 }
 654
 655 /* Same as above but with specified hash and comparison functions. */
 656
 657 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 658                               void **ret_key, void **ret_context,
 659                               SilcHashFunction hash,
 660                               void *hash_user_context,
 661                               SilcHashCompare compare,
 662                               void *compare_user_context)
 663 {
 664   SilcHashTableEntry *entry;
 665
 666   entry = silc_hash_table_find_internal_simple(ht, key,
 667                                                hash ? hash : ht->hash,
 668                                                hash_user_context ?
 669                                                hash_user_context :
 670                                                ht->hash_user_context,
 671                                                compare ? compare :
 672                                                ht->compare,
 673                                                compare_user_context ?
 674                                                compare_user_context :
 675                                                ht->compare_user_context);
 676   if (*entry == NULL)
 677     return FALSE;
 678
 679   if (ret_key)
 680     *ret_key = (*entry)->key;
 681   if (ret_context)
 682     *ret_context = (*entry)->context;
 683
 684   return TRUE;
 685 }
 686
 687 /* Same as silc_hash_table_find but finds with specific context. */
 688
 689 bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 690                                      void *context, void **ret_key)
 691 {
 692   SilcHashTableEntry *entry;
 693
 694   entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
 695                                                 ht->hash,
 696                                                 ht->hash_user_context,
 697                                                 ht->compare,
 698                                                 ht->compare_user_context);
 699   if (!entry || !(*entry))
 700     return FALSE;
 701
 702   if (ret_key)
 703     *ret_key = (*entry)->key;
 704
 705   return TRUE;
 706 }
 707
 708 /* As the hash table is collision resistant it is possible to save duplicate
 709    keys to the hash table. This function can be used to find all keys
 710    and contexts from the hash table that are found using the `key'. The
 711    `foreach' is called for every found key. */
 712
 713 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 714                                   SilcHashForeach foreach, void *user_context)
 715 {
 716   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 717                                     ht->compare, ht->compare_user_context,
 718                                     foreach, user_context);
 719 }
 720
 721 /* Same as above but with specific hash and comparison functions. */
 722
 723 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 724                                       SilcHashFunction hash,
 725                                       void *hash_user_context,
 726                                       SilcHashCompare compare,
 727                                       void *compare_user_context,
 728                                       SilcHashForeach foreach,
 729                                       void *foreach_user_context)
 730 {
 731   silc_hash_table_find_internal_all(ht, key,
 732                                     hash ? hash : ht->hash,
 733                                     hash_user_context ?
 734                                     hash_user_context :
 735                                     ht->hash_user_context,
 736                                     compare ? compare :
 737                                     ht->compare,
 738                                     compare_user_context ?
 739                                     compare_user_context :
 740                                     ht->compare_user_context,
 741                                     foreach, foreach_user_context);
 742 }
 743
 744 /* Traverse all entrys in the hash table and call the `foreach' for
 745    every entry with the `user_context' context. */
 746
 747 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 748                              void *user_context)
 749 {
 750   SilcHashTableEntry e, tmp;
 751   int i;
 752   bool auto_rehash;
 753
 754   if (!foreach)
 755     return;
 756
 757   auto_rehash = ht->auto_rehash;
 758   ht->auto_rehash = FALSE;
 759   for (i = 0; i < primesize[ht->table_size]; i++) {
 760     e = ht->table[i];
 761     while (e) {
 762       /* Entry may become invalid inside the `foreach' */
 763       tmp = e->next;
 764       foreach(e->key, e->context, user_context);
 765       e = tmp;
 766     }
 767   }
 768   ht->auto_rehash = auto_rehash;
 769 }
 770
 771 /* Rehashs the hash table. The size of the new hash table is provided
 772    as `new_size'. If the `new_size' is zero then this routine will make
 773    the new table of a suitable size. Note that this operation may be
 774    very slow. */
 775
 776 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 777 {
 778   int i;
 779   SilcHashTableEntry *table, e, tmp;
 780   SilcUInt32 table_size, size_index;
 781
 782   SILC_HT_DEBUG(("Start"));
 783
 784   if (new_size)
 785     silc_hash_table_primesize(new_size, &size_index);
 786   else
 787     silc_hash_table_primesize(ht->entry_count, &size_index);
 788
 789   if (size_index == ht->table_size)
 790     return;
 791
 792   SILC_HT_DEBUG(("Rehashing"));
 793
 794   /* Take old hash table */
 795   table = ht->table;
 796   table_size = ht->table_size;
 797
 798   /* Allocate new table */
 799   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 800   ht->table_size = size_index;
 801   ht->entry_count = 0;
 802
 803   /* Rehash */
 804   for (i = 0; i < primesize[table_size]; i++) {
 805     e = table[i];
 806     while (e) {
 807       silc_hash_table_add(ht, e->key, e->context);
 808       tmp = e;
 809       e = e->next;
 810
 811       /* Remove old entry */
 812       silc_free(tmp);
 813     }
 814   }
 815
 816   /* Remove old table */
 817   silc_free(table);
 818 }
 819
 820 /* Same as above but with specific hash function. */
 821
 822 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 823                                 SilcHashFunction hash,
 824                                 void *hash_user_context)
 825 {
 826   int i;
 827   SilcHashTableEntry *table, e, tmp;
 828   SilcUInt32 table_size, size_index;
 829
 830   SILC_HT_DEBUG(("Start"));
 831
 832   if (new_size)
 833     silc_hash_table_primesize(new_size, &size_index);
 834   else
 835     silc_hash_table_primesize(ht->entry_count, &size_index);
 836
 837   if (size_index == ht->table_size)
 838     return;
 839
 840   SILC_HT_DEBUG(("Rehashing"));
 841
 842   /* Take old hash table */
 843   table = ht->table;
 844   table_size = ht->table_size;
 845
 846   /* Allocate new table */
 847   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 848   ht->table_size = size_index;
 849   ht->entry_count = 0;
 850
 851   /* Rehash */
 852   for (i = 0; i < primesize[table_size]; i++) {
 853     e = table[i];
 854     while (e) {
 855       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 856                               hash_user_context);
 857       tmp = e;
 858       e = e->next;
 859
 860       /* Remove old entry */
 861       silc_free(tmp);
 862     }
 863   }
 864
 865   /* Remove old table */
 866   silc_free(table);
 867 }
 868
 869 /* Prepares the `htl' list structure sent as argument to be used in the
 870    hash table traversing with the silc_hash_table_get. Usage:
 871    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 872
 873 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 874 {
 875   htl->ht = ht;
 876   htl->entry = NULL;
 877   htl->index = 0;
 878   htl->auto_rehash = ht->auto_rehash;
 879
 880   /* Disallow rehashing of the table while traversing the table */
 881   ht->auto_rehash = FALSE;
 882 }
 883
 884 /* Resets the `htl' SilcHashTableList. */
 885
 886 void silc_hash_table_list_reset(SilcHashTableList *htl)
 887 {
 888   /* Set back the original auto rehash value to the table */
 889   htl->ht->auto_rehash = htl->auto_rehash;
 890 }
 891
 892 /* Returns always the next entry in the hash table into the `key' and
 893    `context' and TRUE.  If this returns FALSE then there are no anymore
 894    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 895
 896 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
 897 {
 898   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 899
 900   if (!htl->ht->entry_count)
 901     return FALSE;
 902
 903   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 904     entry = htl->ht->table[htl->index];
 905     htl->index++;
 906   }
 907
 908   if (!entry)
 909     return FALSE;
 910
 911   htl->entry = entry->next;
 912
 913   if (key)
 914     *key = entry->key;
 915   if (context)
 916     *context = entry->context;
 917
 918   return TRUE;
 919 }