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