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