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