lib/silcutil/silchashtable.c

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