lib/silcutil/silchashtable.c

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