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