lib/silcutil/silchashtable.c

   1 /*
   2
   3   silchashtable.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2001 - 2005 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[] =
  81 {
  82   3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
  83   1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
  84   14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
  85   131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
  86   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 SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
  92 {
  93   int i;
  94
  95   for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); 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   SilcUInt32 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 to `prev_entry'. */
 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   SilcUInt32 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   if (prev_entry)
 175     *prev_entry = prev;
 176   return entry;
 177 }
 178
 179 /* Internal routine to find entry in the hash table by `key'. */
 180
 181 static inline SilcHashTableEntry *
 182 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
 183                                      SilcHashFunction hash,
 184                                      void *hash_user_context,
 185                                      SilcHashCompare compare,
 186                                      void *compare_user_context)
 187 {
 188   SilcHashTableEntry *entry;
 189   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 190
 191   SILC_HT_DEBUG(("index %d key %p", i, key));
 192
 193   entry = &ht->table[i];
 194   if (compare) {
 195     while (*entry && !compare((*entry)->key, key, compare_user_context))
 196       entry = &(*entry)->next;
 197   } else {
 198     while (*entry && (*entry)->key != key)
 199       entry = &(*entry)->next;
 200   }
 201
 202   return entry;
 203 }
 204
 205 /* Internal routine to find all keys by `key'. This may return multiple
 206    entries if multiple entries with same key exists. With specific
 207    hash and comparison functions. */
 208
 209 static inline void
 210 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
 211                                   SilcHashFunction hash,
 212                                   void *hash_user_context,
 213                                   SilcHashCompare compare,
 214                                   void *compare_user_context,
 215                                   SilcHashForeach foreach,
 216                                   void *foreach_user_context)
 217 {
 218   SilcHashTableEntry e, tmp;
 219   SilcBool auto_rehash, found = FALSE;
 220   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 221
 222   SILC_HT_DEBUG(("index %d key %p", i, key));
 223
 224   /* Disallow auto rehashing while going through the table since we call
 225      the `foreach' function which could alter the table. */
 226   auto_rehash = ht->auto_rehash;
 227   ht->auto_rehash = FALSE;
 228
 229   e = ht->table[i];
 230   if (compare) {
 231     while (e) {
 232       tmp = e->next;
 233       if (compare(e->key, key, compare_user_context)) {
 234         found = TRUE;
 235         foreach(e->key, e->context, foreach_user_context);
 236       }
 237       e = tmp;
 238     }
 239   } else {
 240     while (e) {
 241       tmp = e->next;
 242       if (e->key == key) {
 243         found = TRUE;
 244         foreach(e->key, e->context, foreach_user_context);
 245       }
 246       e = tmp;
 247     }
 248   }
 249
 250   /* If nothing was found call with NULL context the callback */
 251   if (!found)
 252     foreach(key, NULL, foreach_user_context);
 253
 254   ht->auto_rehash = auto_rehash;
 255 }
 256
 257 /* Internal routine to add new key to the hash table */
 258
 259 static inline SilcBool
 260 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
 261                              SilcHashFunction hash,
 262                              void *hash_user_context)
 263 {
 264   SilcHashTableEntry *entry;
 265   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 266
 267   SILC_HT_DEBUG(("index %d key %p", i, key));
 268
 269   entry = &ht->table[i];
 270   if (*entry) {
 271     /* The entry exists already. We have a collision, add it to the
 272        list to avoid collision. */
 273     SilcHashTableEntry e, tmp;
 274
 275     e = *entry;
 276     tmp = e->next;
 277     while (tmp) {
 278       e = tmp;
 279       tmp = tmp->next;
 280     }
 281
 282     SILC_HT_DEBUG(("Collision; adding new key to list"));
 283
 284     e->next = silc_calloc(1, sizeof(*e->next));
 285     if (!e->next)
 286       return FALSE;
 287     e->next->key = key;
 288     e->next->context = context;
 289     ht->entry_count++;
 290   } else {
 291     /* New key */
 292     SILC_HT_DEBUG(("New key"));
 293     *entry = silc_calloc(1, sizeof(**entry));
 294     if (!(*entry))
 295       return FALSE;
 296     (*entry)->key = key;
 297     (*entry)->context = context;
 298     ht->entry_count++;
 299   }
 300
 301   if (SILC_HASH_REHASH_INC)
 302     silc_hash_table_rehash(ht, 0);
 303
 304   return TRUE;
 305 }
 306
 307 /* Internal routine to replace old key with new one (if it exists) */
 308
 309 static inline SilcBool
 310 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 311                                  SilcHashFunction hash,
 312                                  void *hash_user_context)
 313 {
 314   SilcHashTableEntry *entry;
 315   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 316
 317   SILC_HT_DEBUG(("index %d key %p", i, key));
 318
 319   entry = &ht->table[i];
 320   if (*entry) {
 321     /* The entry exists already. We have a collision, replace the old
 322        key and context. */
 323     if (ht->destructor)
 324       ht->destructor((*entry)->key, (*entry)->context,
 325                      ht->destructor_user_context);
 326   } else {
 327     /* New key */
 328     *entry = silc_calloc(1, sizeof(**entry));
 329     if (!(*entry))
 330       return FALSE;
 331     ht->entry_count++;
 332   }
 333
 334   (*entry)->key = key;
 335   (*entry)->context = context;
 336
 337   if (SILC_HASH_REHASH_INC)
 338     silc_hash_table_rehash(ht, 0);
 339
 340   return TRUE;
 341 }
 342
 343 /* Allocates new hash table and returns it.  If the `table_size' is not
 344    zero then the hash table size is the size provided. If zero then the
 345    default size will be used. Note that if the `table_size' is provided
 346    it should be a prime. The `hash', `compare' and `destructor' are
 347    the hash function, the key comparison function and key and context
 348    destructor function, respectively. The `hash' is mandatory, the others
 349    are optional. */
 350
 351 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
 352                                     SilcHashFunction hash,
 353                                     void *hash_user_context,
 354                                     SilcHashCompare compare,
 355                                     void *compare_user_context,
 356                                     SilcHashDestructor destructor,
 357                                     void *destructor_user_context,
 358                                     SilcBool auto_rehash)
 359 {
 360   SilcHashTable ht;
 361   SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
 362
 363   if (!hash)
 364     return NULL;
 365
 366   ht = silc_calloc(1, sizeof(*ht));
 367   if (!ht)
 368     return NULL;
 369   ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
 370                                                                  &size_index) :
 371                           primesize[SILC_HASH_TABLE_SIZE],
 372                           sizeof(*ht->table));
 373   if (!ht->table) {
 374     silc_free(ht);
 375     return NULL;
 376   }
 377   ht->table_size = size_index;
 378   ht->hash = hash;
 379   ht->compare = compare;
 380   ht->destructor = destructor;
 381   ht->hash_user_context = hash_user_context;
 382   ht->compare_user_context = compare_user_context;
 383   ht->destructor_user_context = destructor_user_context;
 384   ht->auto_rehash = auto_rehash;
 385
 386   return ht;
 387 }
 388
 389 /* Frees the hash table. The destructor function provided in the
 390    silc_hash_table_alloc will be called for all keys in the hash table. */
 391
 392 void silc_hash_table_free(SilcHashTable ht)
 393 {
 394   SilcHashTableEntry e, tmp;
 395   int i;
 396
 397   for (i = 0; i < primesize[ht->table_size]; i++) {
 398     e = ht->table[i];
 399     while (e) {
 400       if (ht->destructor)
 401         ht->destructor(e->key, e->context, ht->destructor_user_context);
 402       tmp = e;
 403       e = e->next;
 404       silc_free(tmp);
 405     }
 406   }
 407
 408   silc_free(ht->table);
 409   silc_free(ht);
 410 }
 411
 412 /* Returns the size of the hash table */
 413
 414 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
 415 {
 416   return primesize[ht->table_size];
 417 }
 418
 419 /* Returns the number of the entires in the hash table. If there is more
 420    entries in the table thatn the size of the hash table calling the
 421    silc_hash_table_rehash is recommended. */
 422
 423 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
 424 {
 425   return ht->entry_count;
 426 }
 427
 428 /* Adds new entry to the hash table. The `key' is hashed using the
 429    hash function and the both `key' and `context' will be saved to the
 430    hash table. This function quarantees that the entry is always added
 431    to the hash table reliably (it is collision resistant). */
 432
 433 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 434 {
 435   silc_hash_table_add_internal(ht, key, context, ht->hash,
 436                                ht->hash_user_context);
 437 }
 438
 439 /* Same as above but with specific hash function and user context. */
 440
 441 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 442                              SilcHashFunction hash, void *hash_user_context)
 443 {
 444   silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
 445 }
 446
 447 /* Same as above but if the `key' already exists in the hash table
 448    the old key and the old context will be replace with the `key' and
 449    the `context. The destructor function will be called for the
 450    replaced key and context. */
 451
 452 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
 453 {
 454   silc_hash_table_replace_internal(ht, key, context, ht->hash,
 455                                    ht->hash_user_context);
 456 }
 457
 458 /* Same as above but with specific hash function. */
 459
 460 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
 461                                  SilcHashFunction hash,
 462                                  void *hash_user_context)
 463 {
 464   silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
 465 }
 466
 467 /* Removes the entry from the hash table by the provided `key'. This will
 468    call the destructor funtion for the found entry. Return TRUE if the
 469    entry was removed successfully and FALSE otherwise. */
 470
 471 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
 472 {
 473   SilcHashTableEntry *entry, prev, e;
 474
 475   entry = silc_hash_table_find_internal(ht, key, &prev,
 476                                         ht->hash, ht->hash_user_context,
 477                                         ht->compare, ht->compare_user_context);
 478   if (*entry == NULL)
 479     return FALSE;
 480
 481   e = *entry;
 482
 483   if (!prev && e->next)
 484     *entry = e->next;
 485   if (!prev && e->next == NULL)
 486     *entry = NULL;
 487   if (prev)
 488     prev->next = NULL;
 489   if (prev && e->next)
 490     prev->next = e->next;
 491
 492   if (ht->destructor)
 493     ht->destructor(e->key, e->context, ht->destructor_user_context);
 494   silc_free(e);
 495
 496   ht->entry_count--;
 497
 498   if (SILC_HASH_REHASH_DEC)
 499     silc_hash_table_rehash(ht, 0);
 500
 501   return TRUE;
 502 }
 503
 504 /* Same as above but with specific hash and compare functions. */
 505
 506 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 507                              SilcHashFunction hash,
 508                              void *hash_user_context,
 509                              SilcHashCompare compare,
 510                              void *compare_user_context,
 511                              SilcHashDestructor destructor,
 512                              void *destructor_user_context)
 513 {
 514   SilcHashTableEntry *entry, prev, e;
 515
 516   entry = silc_hash_table_find_internal(ht, key, &prev,
 517                                         hash ? hash : ht->hash,
 518                                         hash_user_context ? hash_user_context :
 519                                         ht->hash_user_context,
 520                                         compare ? compare : ht->compare,
 521                                         compare_user_context ?
 522                                         compare_user_context :
 523                                         ht->compare_user_context);
 524   if (*entry == NULL)
 525     return FALSE;
 526
 527   e = *entry;
 528
 529   if (!prev && e->next)
 530     *entry = e->next;
 531   if (!prev && e->next == NULL)
 532     *entry = NULL;
 533   if (prev)
 534     prev->next = NULL;
 535   if (prev && e->next)
 536     prev->next = e->next;
 537
 538   if (destructor) {
 539     destructor(e->key, e->context, destructor_user_context);
 540   } else {
 541     if (ht->destructor)
 542       ht->destructor(e->key, e->context, ht->destructor_user_context);
 543   }
 544   silc_free(e);
 545
 546   ht->entry_count--;
 547
 548   if (SILC_HASH_REHASH_DEC)
 549     silc_hash_table_rehash(ht, 0);
 550
 551   return TRUE;
 552 }
 553
 554 /* Same as above but verifies that the context associated with the `key'
 555    matches the `context'. This is handy to use with hash tables that may
 556    have duplicate keys. In that case the `context' may be used to check
 557    whether the correct entry is being deleted. */
 558
 559 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 560                                     void *context)
 561 {
 562   SilcHashTableEntry *entry, prev, e;
 563
 564   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 565                                                 ht->hash,
 566                                                 ht->hash_user_context,
 567                                                 ht->compare,
 568                                                 ht->compare_user_context);
 569   if (*entry == NULL)
 570     return FALSE;
 571
 572   e = *entry;
 573
 574   if (!prev && e->next)
 575     *entry = e->next;
 576   if (!prev && e->next == NULL)
 577     *entry = NULL;
 578   if (prev)
 579     prev->next = NULL;
 580   if (prev && e->next)
 581     prev->next = e->next;
 582
 583   if (ht->destructor)
 584     ht->destructor(e->key, e->context, ht->destructor_user_context);
 585   silc_free(e);
 586
 587   ht->entry_count--;
 588
 589   if (SILC_HASH_REHASH_DEC)
 590     silc_hash_table_rehash(ht, 0);
 591
 592   return TRUE;
 593 }
 594
 595 /* Same as above but with specific hash and compare functions. */
 596
 597 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 598                                         void *context,
 599                                         SilcHashFunction hash,
 600                                         void *hash_user_context,
 601                                         SilcHashCompare compare,
 602                                         void *compare_user_context,
 603                                         SilcHashDestructor destructor,
 604                                         void *destructor_user_context)
 605 {
 606   SilcHashTableEntry *entry, prev, e;
 607
 608   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 609                                                 hash ? hash : ht->hash,
 610                                                 hash_user_context ?
 611                                                 hash_user_context :
 612                                                 ht->hash_user_context,
 613                                                 compare ?
 614                                                 compare : ht->compare,
 615                                                 compare_user_context ?
 616                                                 compare_user_context :
 617                                                 ht->compare_user_context);
 618   if (*entry == NULL)
 619     return FALSE;
 620
 621   e = *entry;
 622
 623   if (!prev && e->next)
 624     *entry = e->next;
 625   if (!prev && e->next == NULL)
 626     *entry = NULL;
 627   if (prev)
 628     prev->next = NULL;
 629   if (prev && e->next)
 630     prev->next = e->next;
 631
 632   if (destructor) {
 633     destructor(e->key, e->context, destructor_user_context);
 634   } else {
 635     if (ht->destructor)
 636       ht->destructor(e->key, e->context, ht->destructor_user_context);
 637   }
 638   silc_free(e);
 639
 640   ht->entry_count--;
 641
 642   if (SILC_HASH_REHASH_DEC)
 643     silc_hash_table_rehash(ht, 0);
 644
 645   return TRUE;
 646 }
 647
 648 /* Finds the entry in the hash table by the provided `key' as fast as
 649    possible. Return TRUE if the entry was found and FALSE otherwise.
 650    The found entry is returned to the `ret_key' and `ret_context',
 651    respectively. If the `ret_key and `ret_context' are NULL then this
 652    maybe used only to check whether given key exists in the table. */
 653
 654 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
 655                           void **ret_key, void **ret_context)
 656 {
 657   return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
 658                                   NULL, NULL, NULL, NULL);
 659 }
 660
 661 /* Same as above but with specified hash and comparison functions. */
 662
 663 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 664                               void **ret_key, void **ret_context,
 665                               SilcHashFunction hash,
 666                               void *hash_user_context,
 667                               SilcHashCompare compare,
 668                               void *compare_user_context)
 669 {
 670   SilcHashTableEntry *entry;
 671
 672   entry = silc_hash_table_find_internal_simple(ht, key,
 673                                                hash ? hash : ht->hash,
 674                                                hash_user_context ?
 675                                                hash_user_context :
 676                                                ht->hash_user_context,
 677                                                compare ? compare :
 678                                                ht->compare,
 679                                                compare_user_context ?
 680                                                compare_user_context :
 681                                                ht->compare_user_context);
 682   if (*entry == NULL)
 683     return FALSE;
 684
 685   if (ret_key)
 686     *ret_key = (*entry)->key;
 687   if (ret_context)
 688     *ret_context = (*entry)->context;
 689
 690   return TRUE;
 691 }
 692
 693 /* Same as silc_hash_table_find but finds with specific context. */
 694
 695 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 696                                      void *context, void **ret_key)
 697 {
 698   return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
 699                                              NULL, NULL, NULL, NULL);
 700 }
 701
 702 /* Same as above but with specified hash and comparison functions. */
 703
 704 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
 705                                          void *context, void **ret_key,
 706                                          SilcHashFunction hash,
 707                                          void *hash_user_context,
 708                                          SilcHashCompare compare,
 709                                          void *compare_user_context)
 710 {
 711   SilcHashTableEntry *entry;
 712
 713   entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
 714                                                 hash ? hash : ht->hash,
 715                                                 hash_user_context ?
 716                                                 hash_user_context :
 717                                                 ht->hash_user_context,
 718                                                 compare ? compare :
 719                                                 ht->compare,
 720                                                 compare_user_context ?
 721                                                 compare_user_context :
 722                                                 ht->compare_user_context);
 723   if (!entry || !(*entry))
 724     return FALSE;
 725
 726   if (ret_key)
 727     *ret_key = (*entry)->key;
 728
 729   return TRUE;
 730 }
 731
 732 /* As the hash table is collision resistant it is possible to save duplicate
 733    keys to the hash table. This function can be used to find all keys
 734    and contexts from the hash table that are found using the `key'. The
 735    `foreach' is called for every found key. */
 736
 737 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 738                                   SilcHashForeach foreach, void *user_context)
 739 {
 740   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 741                                     ht->compare, ht->compare_user_context,
 742                                     foreach, user_context);
 743 }
 744
 745 /* Same as above but with specific hash and comparison functions. */
 746
 747 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 748                                       SilcHashFunction hash,
 749                                       void *hash_user_context,
 750                                       SilcHashCompare compare,
 751                                       void *compare_user_context,
 752                                       SilcHashForeach foreach,
 753                                       void *foreach_user_context)
 754 {
 755   silc_hash_table_find_internal_all(ht, key,
 756                                     hash ? hash : ht->hash,
 757                                     hash_user_context ?
 758                                     hash_user_context :
 759                                     ht->hash_user_context,
 760                                     compare ? compare :
 761                                     ht->compare,
 762                                     compare_user_context ?
 763                                     compare_user_context :
 764                                     ht->compare_user_context,
 765                                     foreach, foreach_user_context);
 766 }
 767
 768 /* Traverse all entrys in the hash table and call the `foreach' for
 769    every entry with the `user_context' context. */
 770
 771 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 772                              void *user_context)
 773 {
 774   SilcHashTableEntry e, tmp;
 775   int i;
 776   SilcBool auto_rehash;
 777
 778   if (!foreach)
 779     return;
 780
 781   auto_rehash = ht->auto_rehash;
 782   ht->auto_rehash = FALSE;
 783   for (i = 0; i < primesize[ht->table_size]; i++) {
 784     e = ht->table[i];
 785     while (e) {
 786       /* Entry may become invalid inside the `foreach' */
 787       tmp = e->next;
 788       foreach(e->key, e->context, user_context);
 789       e = tmp;
 790     }
 791   }
 792   ht->auto_rehash = auto_rehash;
 793 }
 794
 795 /* Rehashs the hash table. The size of the new hash table is provided
 796    as `new_size'. If the `new_size' is zero then this routine will make
 797    the new table of a suitable size. Note that this operation may be
 798    very slow. */
 799
 800 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 801 {
 802   int i;
 803   SilcHashTableEntry *table, e, tmp;
 804   SilcUInt32 table_size, size_index;
 805   SilcBool auto_rehash;
 806
 807   SILC_HT_DEBUG(("Start"));
 808
 809   if (new_size)
 810     silc_hash_table_primesize(new_size, &size_index);
 811   else
 812     silc_hash_table_primesize(ht->entry_count, &size_index);
 813
 814   if (size_index == ht->table_size)
 815     return;
 816
 817   SILC_HT_DEBUG(("Rehashing"));
 818
 819   /* Take old hash table */
 820   table = ht->table;
 821   table_size = ht->table_size;
 822   auto_rehash = ht->auto_rehash;
 823   ht->auto_rehash = FALSE;
 824
 825   /* Allocate new table */
 826   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 827   if (!ht->table)
 828     return;
 829   ht->table_size = size_index;
 830   ht->entry_count = 0;
 831
 832   /* Rehash */
 833   for (i = 0; i < primesize[table_size]; i++) {
 834     e = table[i];
 835     while (e) {
 836       silc_hash_table_add(ht, e->key, e->context);
 837       tmp = e;
 838       e = e->next;
 839
 840       /* Remove old entry */
 841       silc_free(tmp);
 842     }
 843   }
 844
 845   ht->auto_rehash = auto_rehash;
 846
 847   /* Remove old table */
 848   silc_free(table);
 849 }
 850
 851 /* Same as above but with specific hash function. */
 852
 853 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 854                                 SilcHashFunction hash,
 855                                 void *hash_user_context)
 856 {
 857   int i;
 858   SilcHashTableEntry *table, e, tmp;
 859   SilcUInt32 table_size, size_index;
 860   SilcBool auto_rehash;
 861
 862   SILC_HT_DEBUG(("Start"));
 863
 864   if (new_size)
 865     silc_hash_table_primesize(new_size, &size_index);
 866   else
 867     silc_hash_table_primesize(ht->entry_count, &size_index);
 868
 869   if (size_index == ht->table_size)
 870     return;
 871
 872   SILC_HT_DEBUG(("Rehashing"));
 873
 874   /* Take old hash table */
 875   table = ht->table;
 876   table_size = ht->table_size;
 877   auto_rehash = ht->auto_rehash;
 878   ht->auto_rehash = FALSE;
 879
 880   /* Allocate new table */
 881   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 882   if (!ht->table)
 883     return;
 884   ht->table_size = size_index;
 885   ht->entry_count = 0;
 886
 887   /* Rehash */
 888   for (i = 0; i < primesize[table_size]; i++) {
 889     e = table[i];
 890     while (e) {
 891       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 892                               hash_user_context);
 893       tmp = e;
 894       e = e->next;
 895
 896       /* Remove old entry */
 897       silc_free(tmp);
 898     }
 899   }
 900
 901   ht->auto_rehash = auto_rehash;
 902
 903   /* Remove old table */
 904   silc_free(table);
 905 }
 906
 907 /* Prepares the `htl' list structure sent as argument to be used in the
 908    hash table traversing with the silc_hash_table_get. Usage:
 909    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 910
 911 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 912 {
 913   htl->ht = ht;
 914   htl->entry = NULL;
 915   htl->index = 0;
 916   htl->auto_rehash = ht->auto_rehash;
 917
 918   /* Disallow rehashing of the table while traversing the table */
 919   ht->auto_rehash = FALSE;
 920 }
 921
 922 /* Resets the `htl' SilcHashTableList. */
 923
 924 void silc_hash_table_list_reset(SilcHashTableList *htl)
 925 {
 926   /* Set back the original auto rehash value to the table */
 927   htl->ht->auto_rehash = htl->auto_rehash;
 928 }
 929
 930 /* Returns always the next entry in the hash table into the `key' and
 931    `context' and TRUE.  If this returns FALSE then there are no anymore
 932    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 933
 934 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
 935 {
 936   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 937
 938   if (!htl->ht->entry_count)
 939     return FALSE;
 940
 941   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 942     entry = htl->ht->table[htl->index];
 943     htl->index++;
 944   }
 945
 946   if (!entry)
 947     return FALSE;
 948
 949   htl->entry = entry->next;
 950
 951   if (key)
 952     *key = entry->key;
 953   if (context)
 954     *context = entry->context;
 955
 956   return TRUE;
 957 }