lib/silcutil/silchashtable.c

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