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   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                              SilcHashDestructor destructor,
 477                              void *destructor_user_context)
 478 {
 479   SilcHashTableEntry *entry, prev, e;
 480
 481   entry = silc_hash_table_find_internal(ht, key, &prev,
 482                                         hash ? hash : ht->hash,
 483                                         hash_user_context ? hash_user_context :
 484                                         ht->hash_user_context,
 485                                         compare ? compare : ht->compare,
 486                                         compare_user_context ?
 487                                         compare_user_context :
 488                                         ht->compare_user_context);
 489   if (*entry == NULL)
 490     return FALSE;
 491
 492   e = *entry;
 493
 494   if (!prev && e->next)
 495     *entry = e->next;
 496   if (!prev && e->next == NULL)
 497     *entry = NULL;
 498   if (prev)
 499     prev->next = NULL;
 500   if (prev && e->next)
 501     prev->next = e->next;
 502
 503   if (destructor) {
 504     destructor(e->key, e->context, destructor_user_context);
 505   } else {
 506     if (ht->destructor)
 507       ht->destructor(e->key, e->context, ht->destructor_user_context);
 508   }
 509   silc_free(e);
 510
 511   ht->entry_count--;
 512
 513   if (SILC_HASH_REHASH_DEC)
 514     silc_hash_table_rehash(ht, 0);
 515
 516   return TRUE;
 517 }
 518
 519 /* Same as above but verifies that the context associated with the `key'
 520    matches the `context'. This is handy to use with hash tables that may
 521    have duplicate keys. In that case the `context' may be used to check
 522    whether the correct entry is being deleted. */
 523
 524 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 525                                     void *context)
 526 {
 527   SilcHashTableEntry *entry, prev, e;
 528
 529   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 530                                                 ht->hash,
 531                                                 ht->hash_user_context,
 532                                                 ht->compare,
 533                                                 ht->compare_user_context);
 534   if (*entry == NULL)
 535     return FALSE;
 536
 537   e = *entry;
 538
 539   if (!prev && e->next)
 540     *entry = e->next;
 541   if (!prev && e->next == NULL)
 542     *entry = NULL;
 543   if (prev)
 544     prev->next = NULL;
 545   if (prev && e->next)
 546     prev->next = e->next;
 547
 548   if (ht->destructor)
 549     ht->destructor(e->key, e->context, ht->destructor_user_context);
 550   silc_free(e);
 551
 552   ht->entry_count--;
 553
 554   if (SILC_HASH_REHASH_DEC)
 555     silc_hash_table_rehash(ht, 0);
 556
 557   return TRUE;
 558 }
 559
 560 /* Same as above but with specific hash and compare functions. */
 561
 562 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 563                                         void *context,
 564                                         SilcHashFunction hash,
 565                                         void *hash_user_context,
 566                                         SilcHashCompare compare,
 567                                         void *compare_user_context,
 568                                         SilcHashDestructor destructor,
 569                                         void *destructor_user_context)
 570 {
 571   SilcHashTableEntry *entry, prev, e;
 572
 573   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 574                                                 hash ? hash : ht->hash,
 575                                                 hash_user_context ?
 576                                                 hash_user_context :
 577                                                 ht->hash_user_context,
 578                                                 compare ?
 579                                                 compare : ht->compare,
 580                                                 compare_user_context ?
 581                                                 compare_user_context :
 582                                                 ht->compare_user_context);
 583   if (*entry == NULL)
 584     return FALSE;
 585
 586   e = *entry;
 587
 588   if (!prev && e->next)
 589     *entry = e->next;
 590   if (!prev && e->next == NULL)
 591     *entry = NULL;
 592   if (prev)
 593     prev->next = NULL;
 594   if (prev && e->next)
 595     prev->next = e->next;
 596
 597   if (destructor) {
 598     destructor(e->key, e->context, destructor_user_context);
 599   } else {
 600     if (ht->destructor)
 601       ht->destructor(e->key, e->context, ht->destructor_user_context);
 602   }
 603   silc_free(e);
 604
 605   ht->entry_count--;
 606
 607   if (SILC_HASH_REHASH_DEC)
 608     silc_hash_table_rehash(ht, 0);
 609
 610   return TRUE;
 611 }
 612
 613 /* Finds the entry in the hash table by the provided `key' as fast as
 614    possible. Return TRUE if the entry was found and FALSE otherwise.
 615    The found entry is returned to the `ret_key' and `ret_context',
 616    respectively. If the `ret_key and `ret_context' are NULL then this
 617    maybe used only to check whether given key exists in the table. */
 618
 619 bool silc_hash_table_find(SilcHashTable ht, void *key,
 620                           void **ret_key, void **ret_context)
 621 {
 622   SilcHashTableEntry *entry;
 623
 624   entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
 625                                                ht->hash_user_context,
 626                                                ht->compare,
 627                                                ht->compare_user_context);
 628   if (*entry == NULL)
 629     return FALSE;
 630
 631   if (ret_key)
 632     *ret_key = (*entry)->key;
 633   if (ret_context)
 634     *ret_context = (*entry)->context;
 635
 636   return TRUE;
 637 }
 638
 639 /* Same as above but with specified hash and comparison functions. */
 640
 641 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 642                               void **ret_key, void **ret_context,
 643                               SilcHashFunction hash,
 644                               void *hash_user_context,
 645                               SilcHashCompare compare,
 646                               void *compare_user_context)
 647 {
 648   SilcHashTableEntry *entry;
 649
 650   entry = silc_hash_table_find_internal_simple(ht, key,
 651                                                hash ? hash : ht->hash,
 652                                                hash_user_context ?
 653                                                hash_user_context :
 654                                                ht->hash_user_context,
 655                                                compare ? compare :
 656                                                ht->compare,
 657                                                compare_user_context ?
 658                                                compare_user_context :
 659                                                ht->compare_user_context);
 660   if (*entry == NULL)
 661     return FALSE;
 662
 663   if (ret_key)
 664     *ret_key = (*entry)->key;
 665   if (ret_context)
 666     *ret_context = (*entry)->context;
 667
 668   return TRUE;
 669 }
 670
 671 /* As the hash table is collision resistant it is possible to save duplicate
 672    keys to the hash table. This function can be used to find all keys
 673    and contexts from the hash table that are found using the `key'. The
 674    `foreach' is called for every found key. */
 675
 676 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 677                                   SilcHashForeach foreach, void *user_context)
 678 {
 679   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 680                                     ht->compare, ht->compare_user_context,
 681                                     foreach, user_context);
 682 }
 683
 684 /* Same as above but with specific hash and comparison functions. */
 685
 686 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 687                                       SilcHashFunction hash,
 688                                       void *hash_user_context,
 689                                       SilcHashCompare compare,
 690                                       void *compare_user_context,
 691                                       SilcHashForeach foreach,
 692                                       void *foreach_user_context)
 693 {
 694   silc_hash_table_find_internal_all(ht, key,
 695                                     hash ? hash : ht->hash,
 696                                     hash_user_context ?
 697                                     hash_user_context :
 698                                     ht->hash_user_context,
 699                                     compare ? compare :
 700                                     ht->compare,
 701                                     compare_user_context ?
 702                                     compare_user_context :
 703                                     ht->compare_user_context,
 704                                     foreach, foreach_user_context);
 705 }
 706
 707 /* Traverse all entrys in the hash table and call the `foreach' for
 708    every entry with the `user_context' context. */
 709
 710 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 711                              void *user_context)
 712 {
 713   SilcHashTableEntry e, tmp;
 714   int i;
 715
 716   if (!foreach)
 717     return;
 718
 719   for (i = 0; i < primesize[ht->table_size]; i++) {
 720     e = ht->table[i];
 721     while (e) {
 722       /* Entry may become invalid inside the `foreach' */
 723       tmp = e->next;
 724       foreach(e->key, e->context, user_context);
 725       e = tmp;
 726     }
 727   }
 728 }
 729
 730 /* Rehashs the hash table. The size of the new hash table is provided
 731    as `new_size'. If the `new_size' is zero then this routine will make
 732    the new table of a suitable size. Note that this operation may be
 733    very slow. */
 734
 735 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
 736 {
 737   int i;
 738   SilcHashTableEntry *table, e, tmp;
 739   uint32 table_size, size_index;
 740
 741   SILC_HT_DEBUG(("Start"));
 742
 743   if (new_size)
 744     silc_hash_table_primesize(new_size, &size_index);
 745   else
 746     silc_hash_table_primesize(ht->entry_count, &size_index);
 747
 748   if (size_index == ht->table_size)
 749     return;
 750
 751   SILC_HT_DEBUG(("Rehashing"));
 752
 753   /* Take old hash table */
 754   table = ht->table;
 755   table_size = ht->table_size;
 756
 757   /* Allocate new table */
 758   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 759   ht->table_size = size_index;
 760   ht->entry_count = 0;
 761
 762   /* Rehash */
 763   for (i = 0; i < primesize[table_size]; i++) {
 764     e = table[i];
 765     while (e) {
 766       silc_hash_table_add(ht, e->key, e->context);
 767       tmp = e;
 768       e = e->next;
 769
 770       /* Remove old entry */
 771       silc_free(tmp);
 772     }
 773   }
 774
 775   /* Remove old table */
 776   silc_free(table);
 777 }
 778
 779 /* Same as above but with specific hash function. */
 780
 781 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
 782                                 SilcHashFunction hash,
 783                                 void *hash_user_context)
 784 {
 785   int i;
 786   SilcHashTableEntry *table, e, tmp;
 787   uint32 table_size, size_index;
 788
 789   SILC_HT_DEBUG(("Start"));
 790
 791   if (new_size)
 792     silc_hash_table_primesize(new_size, &size_index);
 793   else
 794     silc_hash_table_primesize(ht->entry_count, &size_index);
 795
 796   if (size_index == ht->table_size)
 797     return;
 798
 799   SILC_HT_DEBUG(("Rehashing"));
 800
 801   /* Take old hash table */
 802   table = ht->table;
 803   table_size = ht->table_size;
 804
 805   /* Allocate new table */
 806   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 807   ht->table_size = size_index;
 808   ht->entry_count = 0;
 809
 810   /* Rehash */
 811   for (i = 0; i < primesize[table_size]; i++) {
 812     e = table[i];
 813     while (e) {
 814       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 815                               hash_user_context);
 816       tmp = e;
 817       e = e->next;
 818
 819       /* Remove old entry */
 820       silc_free(tmp);
 821     }
 822   }
 823
 824   /* Remove old table */
 825   silc_free(table);
 826 }
 827
 828 /* Prepares the `htl' list structure sent as argument to be used in the
 829    hash table traversing with the silc_hash_table_get. Usage:
 830    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 831
 832 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 833 {
 834   htl->ht = ht;
 835   htl->entry = NULL;
 836   htl->index = 0;
 837   htl->auto_rehash = ht->auto_rehash;
 838
 839   /* Disallow rehashing of the table while traversing the table */
 840   ht->auto_rehash = FALSE;
 841 }
 842
 843 /* Resets the `htl' SilcHashTableList. */
 844
 845 void silc_hash_table_list_reset(SilcHashTableList *htl)
 846 {
 847   /* Set back the original auto rehash value to the table */
 848   htl->ht->auto_rehash = htl->auto_rehash;
 849 }
 850
 851 /* Returns always the next entry in the hash table into the `key' and
 852    `context' and TRUE.  If this returns FALSE then there are no anymore
 853    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 854
 855 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
 856 {
 857   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 858
 859   if (!htl->ht->entry_count)
 860     return FALSE;
 861
 862   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 863     entry = htl->ht->table[htl->index];
 864     htl->index++;
 865   }
 866
 867   if (!entry)
 868     return FALSE;
 869
 870   htl->entry = entry->next;
 871
 872   if (key)
 873     *key = entry->key;
 874   if (context)
 875     *context = entry->context;
 876
 877   return TRUE;
 878 }