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. */
 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   *prev_entry = prev;
 174   return entry;
 175 }
 176
 177 /* Internal routine to find entry in the hash table by `key'. */
 178
 179 static inline SilcHashTableEntry *
 180 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
 181                                      SilcHashFunction hash,
 182                                      void *hash_user_context,
 183                                      SilcHashCompare compare,
 184                                      void *compare_user_context)
 185 {
 186   SilcHashTableEntry *entry;
 187   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 188
 189   SILC_HT_DEBUG(("index %d key %p", i, key));
 190
 191   entry = &ht->table[i];
 192   if (compare) {
 193     while (*entry && !compare((*entry)->key, key, compare_user_context))
 194       entry = &(*entry)->next;
 195   } else {
 196     while (*entry && (*entry)->key != key)
 197       entry = &(*entry)->next;
 198   }
 199
 200   return entry;
 201 }
 202
 203 /* Internal routine to find all keys by `key'. This may return multiple
 204    entries if multiple entries with same key exists. With specific
 205    hash and comparison functions. */
 206
 207 static inline void
 208 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
 209                                   SilcHashFunction hash,
 210                                   void *hash_user_context,
 211                                   SilcHashCompare compare,
 212                                   void *compare_user_context,
 213                                   SilcHashForeach foreach,
 214                                   void *foreach_user_context)
 215 {
 216   SilcHashTableEntry *entry, *tmp;
 217   bool auto_rehash;
 218   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 219
 220   SILC_HT_DEBUG(("index %d key %p", i, key));
 221
 222   /* Disallow auto rehashing while going through the table since we call
 223      the `foreach' function which could alter the table. */
 224   auto_rehash = ht->auto_rehash;
 225   ht->auto_rehash = FALSE;
 226
 227   entry = &ht->table[i];
 228   if (compare) {
 229     while (*entry) {
 230       if (compare((*entry)->key, key, compare_user_context)) {
 231         tmp = &(*entry)->next;
 232         foreach((*entry)->key, (*entry)->context, foreach_user_context);
 233         entry = tmp;
 234         continue;
 235       }
 236       entry = &(*entry)->next;
 237     }
 238   } else {
 239     while (*entry) {
 240       if ((*entry)->key == key) {
 241         tmp = &(*entry)->next;
 242         foreach((*entry)->key, (*entry)->context, foreach_user_context);
 243         entry = tmp;
 244         continue;
 245       }
 246       entry = &(*entry)->next;
 247     }
 248   }
 249
 250   ht->auto_rehash = auto_rehash;
 251 }
 252
 253 /* Internal routine to add new key to the hash table */
 254
 255 static inline void
 256 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
 257                              SilcHashFunction hash,
 258                              void *hash_user_context)
 259 {
 260   SilcHashTableEntry *entry;
 261   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 262
 263   SILC_HT_DEBUG(("index %d key %p", i, key));
 264
 265   entry = &ht->table[i];
 266   if (*entry) {
 267     /* The entry exists already. We have a collision, add it to the
 268        list to avoid collision. */
 269     SilcHashTableEntry e, tmp;
 270
 271     e = *entry;
 272     tmp = e->next;
 273     while (tmp) {
 274       e = tmp;
 275       tmp = tmp->next;
 276     }
 277
 278     SILC_HT_DEBUG(("Collision; adding new key to list"));
 279
 280     e->next = silc_calloc(1, sizeof(*e->next));
 281     e->next->key = key;
 282     e->next->context = context;
 283     ht->entry_count++;
 284   } else {
 285     /* New key */
 286     SILC_HT_DEBUG(("New key"));
 287     *entry = silc_calloc(1, sizeof(**entry));
 288     (*entry)->key = key;
 289     (*entry)->context = context;
 290     ht->entry_count++;
 291   }
 292
 293   if (SILC_HASH_REHASH_INC)
 294     silc_hash_table_rehash(ht, 0);
 295 }
 296
 297 /* Internal routine to replace old key with new one (if it exists) */
 298
 299 static inline void
 300 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 301                                  SilcHashFunction hash,
 302                                  void *hash_user_context)
 303 {
 304   SilcHashTableEntry *entry;
 305   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 306
 307   SILC_HT_DEBUG(("index %d key %p", i, key));
 308
 309   entry = &ht->table[i];
 310   if (*entry) {
 311     /* The entry exists already. We have a collision, replace the old
 312        key and context. */
 313     if (ht->destructor)
 314       ht->destructor((*entry)->key, (*entry)->context,
 315                      ht->destructor_user_context);
 316   } else {
 317     /* New key */
 318     *entry = silc_calloc(1, sizeof(**entry));
 319     ht->entry_count++;
 320   }
 321
 322   (*entry)->key = key;
 323   (*entry)->context = context;
 324
 325   if (SILC_HASH_REHASH_INC)
 326     silc_hash_table_rehash(ht, 0);
 327 }
 328
 329 /* Allocates new hash table and returns it.  If the `table_size' is not
 330    zero then the hash table size is the size provided. If zero then the
 331    default size will be used. Note that if the `table_size' is provided
 332    it should be a prime. The `hash', `compare' and `destructor' are
 333    the hash function, the key comparison function and key and context
 334    destructor function, respectively. The `hash' is mandatory, the others
 335    are optional. */
 336
 337 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
 338                                     SilcHashFunction hash,
 339                                     void *hash_user_context,
 340                                     SilcHashCompare compare,
 341                                     void *compare_user_context,
 342                                     SilcHashDestructor destructor,
 343                                     void *destructor_user_context,
 344                                     bool auto_rehash)
 345 {
 346   SilcHashTable ht;
 347   SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
 348
 349   if (!hash)
 350     return NULL;
 351
 352   ht = silc_calloc(1, sizeof(*ht));
 353   ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
 354                                                                  &size_index) :
 355                           primesize[SILC_HASH_TABLE_SIZE],
 356                           sizeof(*ht->table));
 357   ht->table_size = size_index;
 358   ht->hash = hash;
 359   ht->compare = compare;
 360   ht->destructor = destructor;
 361   ht->hash_user_context = hash_user_context;
 362   ht->compare_user_context = compare_user_context;
 363   ht->destructor_user_context = destructor_user_context;
 364   ht->auto_rehash = auto_rehash;
 365
 366   return ht;
 367 }
 368
 369 /* Frees the hash table. The destructor function provided in the
 370    silc_hash_table_alloc will be called for all keys in the hash table. */
 371
 372 void silc_hash_table_free(SilcHashTable ht)
 373 {
 374   SilcHashTableEntry e, tmp;
 375   int i;
 376
 377   for (i = 0; i < primesize[ht->table_size]; i++) {
 378     e = ht->table[i];
 379     while (e) {
 380       if (ht->destructor)
 381         ht->destructor(e->key, e->context, ht->destructor_user_context);
 382       tmp = e;
 383       e = e->next;
 384       silc_free(tmp);
 385     }
 386   }
 387
 388   silc_free(ht->table);
 389   silc_free(ht);
 390 }
 391
 392 /* Returns the size of the hash table */
 393
 394 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
 395 {
 396   return primesize[ht->table_size];
 397 }
 398
 399 /* Returns the number of the entires in the hash table. If there is more
 400    entries in the table thatn the size of the hash table calling the
 401    silc_hash_table_rehash is recommended. */
 402
 403 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
 404 {
 405   return ht->entry_count;
 406 }
 407
 408 /* Adds new entry to the hash table. The `key' is hashed using the
 409    hash function and the both `key' and `context' will be saved to the
 410    hash table. This function quarantees that the entry is always added
 411    to the hash table reliably (it is collision resistant). */
 412
 413 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 414 {
 415   silc_hash_table_add_internal(ht, key, context, ht->hash,
 416                                ht->hash_user_context);
 417 }
 418
 419 /* Same as above but with specific hash function and user context. */
 420
 421 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 422                              SilcHashFunction hash, void *hash_user_context)
 423 {
 424   silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
 425 }
 426
 427 /* Same as above but if the `key' already exists in the hash table
 428    the old key and the old context will be replace with the `key' and
 429    the `context. The destructor function will be called for the
 430    replaced key and context. */
 431
 432 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
 433 {
 434   silc_hash_table_replace_internal(ht, key, context, ht->hash,
 435                                    ht->hash_user_context);
 436 }
 437
 438 /* Same as above but with specific hash function. */
 439
 440 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
 441                                  SilcHashFunction hash,
 442                                  void *hash_user_context)
 443 {
 444   silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
 445 }
 446
 447 /* Removes the entry from the hash table by the provided `key'. This will
 448    call the destructor funtion for the found entry. Return TRUE if the
 449    entry was removed successfully and FALSE otherwise. */
 450
 451 bool silc_hash_table_del(SilcHashTable ht, void *key)
 452 {
 453   SilcHashTableEntry *entry, prev, e;
 454
 455   entry = silc_hash_table_find_internal(ht, key, &prev,
 456                                         ht->hash, ht->hash_user_context,
 457                                         ht->compare, ht->compare_user_context);
 458   if (*entry == NULL)
 459     return FALSE;
 460
 461   e = *entry;
 462
 463   if (!prev && e->next)
 464     *entry = e->next;
 465   if (!prev && e->next == NULL)
 466     *entry = NULL;
 467   if (prev)
 468     prev->next = NULL;
 469   if (prev && e->next)
 470     prev->next = e->next;
 471
 472   if (ht->destructor)
 473     ht->destructor(e->key, e->context, ht->destructor_user_context);
 474   silc_free(e);
 475
 476   ht->entry_count--;
 477
 478   if (SILC_HASH_REHASH_DEC)
 479     silc_hash_table_rehash(ht, 0);
 480
 481   return TRUE;
 482 }
 483
 484 /* Same as above but with specific hash and compare functions. */
 485
 486 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 487                              SilcHashFunction hash,
 488                              void *hash_user_context,
 489                              SilcHashCompare compare,
 490                              void *compare_user_context,
 491                              SilcHashDestructor destructor,
 492                              void *destructor_user_context)
 493 {
 494   SilcHashTableEntry *entry, prev, e;
 495
 496   entry = silc_hash_table_find_internal(ht, key, &prev,
 497                                         hash ? hash : ht->hash,
 498                                         hash_user_context ? hash_user_context :
 499                                         ht->hash_user_context,
 500                                         compare ? compare : ht->compare,
 501                                         compare_user_context ?
 502                                         compare_user_context :
 503                                         ht->compare_user_context);
 504   if (*entry == NULL)
 505     return FALSE;
 506
 507   e = *entry;
 508
 509   if (!prev && e->next)
 510     *entry = e->next;
 511   if (!prev && e->next == NULL)
 512     *entry = NULL;
 513   if (prev)
 514     prev->next = NULL;
 515   if (prev && e->next)
 516     prev->next = e->next;
 517
 518   if (destructor) {
 519     destructor(e->key, e->context, destructor_user_context);
 520   } else {
 521     if (ht->destructor)
 522       ht->destructor(e->key, e->context, ht->destructor_user_context);
 523   }
 524   silc_free(e);
 525
 526   ht->entry_count--;
 527
 528   if (SILC_HASH_REHASH_DEC)
 529     silc_hash_table_rehash(ht, 0);
 530
 531   return TRUE;
 532 }
 533
 534 /* Same as above but verifies that the context associated with the `key'
 535    matches the `context'. This is handy to use with hash tables that may
 536    have duplicate keys. In that case the `context' may be used to check
 537    whether the correct entry is being deleted. */
 538
 539 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 540                                     void *context)
 541 {
 542   SilcHashTableEntry *entry, prev, e;
 543
 544   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 545                                                 ht->hash,
 546                                                 ht->hash_user_context,
 547                                                 ht->compare,
 548                                                 ht->compare_user_context);
 549   if (*entry == NULL)
 550     return FALSE;
 551
 552   e = *entry;
 553
 554   if (!prev && e->next)
 555     *entry = e->next;
 556   if (!prev && e->next == NULL)
 557     *entry = NULL;
 558   if (prev)
 559     prev->next = NULL;
 560   if (prev && e->next)
 561     prev->next = e->next;
 562
 563   if (ht->destructor)
 564     ht->destructor(e->key, e->context, ht->destructor_user_context);
 565   silc_free(e);
 566
 567   ht->entry_count--;
 568
 569   if (SILC_HASH_REHASH_DEC)
 570     silc_hash_table_rehash(ht, 0);
 571
 572   return TRUE;
 573 }
 574
 575 /* Same as above but with specific hash and compare functions. */
 576
 577 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 578                                         void *context,
 579                                         SilcHashFunction hash,
 580                                         void *hash_user_context,
 581                                         SilcHashCompare compare,
 582                                         void *compare_user_context,
 583                                         SilcHashDestructor destructor,
 584                                         void *destructor_user_context)
 585 {
 586   SilcHashTableEntry *entry, prev, e;
 587
 588   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 589                                                 hash ? hash : ht->hash,
 590                                                 hash_user_context ?
 591                                                 hash_user_context :
 592                                                 ht->hash_user_context,
 593                                                 compare ?
 594                                                 compare : ht->compare,
 595                                                 compare_user_context ?
 596                                                 compare_user_context :
 597                                                 ht->compare_user_context);
 598   if (*entry == NULL)
 599     return FALSE;
 600
 601   e = *entry;
 602
 603   if (!prev && e->next)
 604     *entry = e->next;
 605   if (!prev && e->next == NULL)
 606     *entry = NULL;
 607   if (prev)
 608     prev->next = NULL;
 609   if (prev && e->next)
 610     prev->next = e->next;
 611
 612   if (destructor) {
 613     destructor(e->key, e->context, destructor_user_context);
 614   } else {
 615     if (ht->destructor)
 616       ht->destructor(e->key, e->context, ht->destructor_user_context);
 617   }
 618   silc_free(e);
 619
 620   ht->entry_count--;
 621
 622   if (SILC_HASH_REHASH_DEC)
 623     silc_hash_table_rehash(ht, 0);
 624
 625   return TRUE;
 626 }
 627
 628 /* Finds the entry in the hash table by the provided `key' as fast as
 629    possible. Return TRUE if the entry was found and FALSE otherwise.
 630    The found entry is returned to the `ret_key' and `ret_context',
 631    respectively. If the `ret_key and `ret_context' are NULL then this
 632    maybe used only to check whether given key exists in the table. */
 633
 634 bool silc_hash_table_find(SilcHashTable ht, void *key,
 635                           void **ret_key, void **ret_context)
 636 {
 637   SilcHashTableEntry *entry;
 638
 639   entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
 640                                                ht->hash_user_context,
 641                                                ht->compare,
 642                                                ht->compare_user_context);
 643   if (*entry == NULL)
 644     return FALSE;
 645
 646   if (ret_key)
 647     *ret_key = (*entry)->key;
 648   if (ret_context)
 649     *ret_context = (*entry)->context;
 650
 651   return TRUE;
 652 }
 653
 654 /* Same as above but with specified hash and comparison functions. */
 655
 656 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 657                               void **ret_key, void **ret_context,
 658                               SilcHashFunction hash,
 659                               void *hash_user_context,
 660                               SilcHashCompare compare,
 661                               void *compare_user_context)
 662 {
 663   SilcHashTableEntry *entry;
 664
 665   entry = silc_hash_table_find_internal_simple(ht, key,
 666                                                hash ? hash : ht->hash,
 667                                                hash_user_context ?
 668                                                hash_user_context :
 669                                                ht->hash_user_context,
 670                                                compare ? compare :
 671                                                ht->compare,
 672                                                compare_user_context ?
 673                                                compare_user_context :
 674                                                ht->compare_user_context);
 675   if (*entry == NULL)
 676     return FALSE;
 677
 678   if (ret_key)
 679     *ret_key = (*entry)->key;
 680   if (ret_context)
 681     *ret_context = (*entry)->context;
 682
 683   return TRUE;
 684 }
 685
 686 /* As the hash table is collision resistant it is possible to save duplicate
 687    keys to the hash table. This function can be used to find all keys
 688    and contexts from the hash table that are found using the `key'. The
 689    `foreach' is called for every found key. */
 690
 691 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 692                                   SilcHashForeach foreach, void *user_context)
 693 {
 694   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 695                                     ht->compare, ht->compare_user_context,
 696                                     foreach, user_context);
 697 }
 698
 699 /* Same as above but with specific hash and comparison functions. */
 700
 701 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 702                                       SilcHashFunction hash,
 703                                       void *hash_user_context,
 704                                       SilcHashCompare compare,
 705                                       void *compare_user_context,
 706                                       SilcHashForeach foreach,
 707                                       void *foreach_user_context)
 708 {
 709   silc_hash_table_find_internal_all(ht, key,
 710                                     hash ? hash : ht->hash,
 711                                     hash_user_context ?
 712                                     hash_user_context :
 713                                     ht->hash_user_context,
 714                                     compare ? compare :
 715                                     ht->compare,
 716                                     compare_user_context ?
 717                                     compare_user_context :
 718                                     ht->compare_user_context,
 719                                     foreach, foreach_user_context);
 720 }
 721
 722 /* Traverse all entrys in the hash table and call the `foreach' for
 723    every entry with the `user_context' context. */
 724
 725 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 726                              void *user_context)
 727 {
 728   SilcHashTableEntry e, tmp;
 729   int i;
 730   bool auto_rehash;
 731
 732   if (!foreach)
 733     return;
 734
 735   auto_rehash = ht->auto_rehash;
 736   ht->auto_rehash = FALSE;
 737   for (i = 0; i < primesize[ht->table_size]; i++) {
 738     e = ht->table[i];
 739     while (e) {
 740       /* Entry may become invalid inside the `foreach' */
 741       tmp = e->next;
 742       foreach(e->key, e->context, user_context);
 743       e = tmp;
 744     }
 745   }
 746   ht->auto_rehash = auto_rehash;
 747 }
 748
 749 /* Rehashs the hash table. The size of the new hash table is provided
 750    as `new_size'. If the `new_size' is zero then this routine will make
 751    the new table of a suitable size. Note that this operation may be
 752    very slow. */
 753
 754 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 755 {
 756   int i;
 757   SilcHashTableEntry *table, e, tmp;
 758   SilcUInt32 table_size, size_index;
 759
 760   SILC_HT_DEBUG(("Start"));
 761
 762   if (new_size)
 763     silc_hash_table_primesize(new_size, &size_index);
 764   else
 765     silc_hash_table_primesize(ht->entry_count, &size_index);
 766
 767   if (size_index == ht->table_size)
 768     return;
 769
 770   SILC_HT_DEBUG(("Rehashing"));
 771
 772   /* Take old hash table */
 773   table = ht->table;
 774   table_size = ht->table_size;
 775
 776   /* Allocate new table */
 777   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 778   ht->table_size = size_index;
 779   ht->entry_count = 0;
 780
 781   /* Rehash */
 782   for (i = 0; i < primesize[table_size]; i++) {
 783     e = table[i];
 784     while (e) {
 785       silc_hash_table_add(ht, e->key, e->context);
 786       tmp = e;
 787       e = e->next;
 788
 789       /* Remove old entry */
 790       silc_free(tmp);
 791     }
 792   }
 793
 794   /* Remove old table */
 795   silc_free(table);
 796 }
 797
 798 /* Same as above but with specific hash function. */
 799
 800 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 801                                 SilcHashFunction hash,
 802                                 void *hash_user_context)
 803 {
 804   int i;
 805   SilcHashTableEntry *table, e, tmp;
 806   SilcUInt32 table_size, size_index;
 807
 808   SILC_HT_DEBUG(("Start"));
 809
 810   if (new_size)
 811     silc_hash_table_primesize(new_size, &size_index);
 812   else
 813     silc_hash_table_primesize(ht->entry_count, &size_index);
 814
 815   if (size_index == ht->table_size)
 816     return;
 817
 818   SILC_HT_DEBUG(("Rehashing"));
 819
 820   /* Take old hash table */
 821   table = ht->table;
 822   table_size = ht->table_size;
 823
 824   /* Allocate new table */
 825   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 826   ht->table_size = size_index;
 827   ht->entry_count = 0;
 828
 829   /* Rehash */
 830   for (i = 0; i < primesize[table_size]; i++) {
 831     e = table[i];
 832     while (e) {
 833       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 834                               hash_user_context);
 835       tmp = e;
 836       e = e->next;
 837
 838       /* Remove old entry */
 839       silc_free(tmp);
 840     }
 841   }
 842
 843   /* Remove old table */
 844   silc_free(table);
 845 }
 846
 847 /* Prepares the `htl' list structure sent as argument to be used in the
 848    hash table traversing with the silc_hash_table_get. Usage:
 849    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 850
 851 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 852 {
 853   htl->ht = ht;
 854   htl->entry = NULL;
 855   htl->index = 0;
 856   htl->auto_rehash = ht->auto_rehash;
 857
 858   /* Disallow rehashing of the table while traversing the table */
 859   ht->auto_rehash = FALSE;
 860 }
 861
 862 /* Resets the `htl' SilcHashTableList. */
 863
 864 void silc_hash_table_list_reset(SilcHashTableList *htl)
 865 {
 866   /* Set back the original auto rehash value to the table */
 867   htl->ht->auto_rehash = htl->auto_rehash;
 868 }
 869
 870 /* Returns always the next entry in the hash table into the `key' and
 871    `context' and TRUE.  If this returns FALSE then there are no anymore
 872    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 873
 874 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
 875 {
 876   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 877
 878   if (!htl->ht->entry_count)
 879     return FALSE;
 880
 881   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 882     entry = htl->ht->table[htl->index];
 883     htl->index++;
 884   }
 885
 886   if (!entry)
 887     return FALSE;
 888
 889   htl->entry = entry->next;
 890
 891   if (key)
 892     *key = entry->key;
 893   if (context)
 894     *context = entry->context;
 895
 896   return TRUE;
 897 }