lib/silcutil/silchashtable.c

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