lib/silcutil/silchashtable.c

   1 /*
   2
   3   silchashtable.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2001 - 2008 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
  27 #include "silcruntime.h"
  28
  29 /* Define to 1 if you want hash table debug enabled */
  30 #define SILC_HASH_TABLE_DEBUG 0
  31
  32 #if SILC_HASH_TABLE_DEBUG == 1
  33 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
  34 #else
  35 #define SILC_HT_DEBUG(fmt)
  36 #endif
  37
  38 /* Default size of the hash table (index to prime table) */
  39 #define SILC_HASH_TABLE_SIZE 2
  40
  41 /* Produce the index by hashing the key */
  42 #define SILC_HASH_TABLE_HASH(f, c) \
  43   ((f)(key, (c)) % primesize[ht->table_size])
  44
  45 /* Check whether need to rehash */
  46 #define SILC_HASH_REHASH_INC \
  47   (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
  48 #define SILC_HASH_REHASH_DEC \
  49   (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
  50    ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
  51
  52 /* One entry in the hash table. Includes the key and the associated
  53    context. The `next' pointer is non-NULL if two (or more) different
  54    keys hashed to same value.  The pointer is the pointer to the next
  55    entry. */
  56 typedef struct SilcHashTableEntryStruct {
  57   void *key;
  58   void *context;
  59   struct SilcHashTableEntryStruct *next;
  60 } *SilcHashTableEntry;
  61
  62 /* Hash table. */
  63 struct SilcHashTableStruct {
  64   SilcStack stack;
  65   SilcHashTableEntry *table;
  66   SilcUInt32 table_size;
  67   SilcUInt32 entry_count;
  68   SilcHashFunction hash;
  69   SilcHashCompare compare;
  70   SilcHashDestructor destructor;
  71   void *hash_user_context;
  72   void *compare_user_context;
  73   void *destructor_user_context;
  74   unsigned int auto_rehash : 1;
  75 };
  76
  77 /* Prime sizes for the hash table. The size of the table will always
  78    be one of these. */
  79 const SilcUInt32 primesize[] =
  80 {
  81   3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
  82   1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
  83   14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
  84   131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
  85   6153409, 8388617, 13845163, 16777259, 33554467, 67108879
  86 };
  87
  88 /* Find appropriate size for the hash table. The size will be a prime. */
  89
  90 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
  91 {
  92   int i;
  93
  94   for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
  95     if (primesize[i] >= size) {
  96       *index = i;
  97       SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
  98       return primesize[i];
  99     }
 100
 101   *index = i - 1;
 102   SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
 103   return primesize[i - 1];
 104 }
 105
 106 /* Internal routine to find entry in the hash table by `key'. Returns
 107    the previous entry (if exists) as well. */
 108
 109 static inline SilcHashTableEntry *
 110 silc_hash_table_find_internal(SilcHashTable ht, void *key,
 111                               SilcHashTableEntry *prev_entry,
 112                               SilcHashFunction hash, void *hash_user_context,
 113                               SilcHashCompare compare,
 114                               void *compare_user_context)
 115 {
 116   SilcHashTableEntry *entry, prev = NULL;
 117   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 118
 119   SILC_HT_DEBUG(("index %d key %p", i, key));
 120
 121   entry = &ht->table[i];
 122   if (compare) {
 123     while (*entry && !compare((*entry)->key, key, compare_user_context)) {
 124       prev = *entry;
 125       entry = &(*entry)->next;
 126     }
 127   } else {
 128     while (*entry && (*entry)->key != key) {
 129       prev = *entry;
 130       entry = &(*entry)->next;
 131     }
 132   }
 133
 134   *prev_entry = prev;
 135   return entry;
 136 }
 137
 138 /* Internal routine to find entry in the hash table by `key' and `context'.
 139    Returns the previous entry (if exists) as well to `prev_entry'. */
 140
 141 static inline SilcHashTableEntry *
 142 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
 143                                       void *context,
 144                                       SilcHashTableEntry *prev_entry,
 145                                       SilcHashFunction hash,
 146                                       void *hash_user_context,
 147                                       SilcHashCompare compare,
 148                                       void *compare_user_context)
 149 {
 150   SilcHashTableEntry *entry, prev = NULL;
 151   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 152
 153   SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
 154
 155   entry = &ht->table[i];
 156   if (ht->compare) {
 157     while (*entry) {
 158       if (compare((*entry)->key, key, compare_user_context) &&
 159           (*entry)->context == context)
 160         break;
 161       prev = *entry;
 162       entry = &(*entry)->next;
 163     }
 164   } else {
 165     while (*entry) {
 166       if ((*entry)->key == key && (*entry)->context == context)
 167         break;
 168       prev = *entry;
 169       entry = &(*entry)->next;
 170     }
 171   }
 172
 173   if (prev_entry)
 174     *prev_entry = prev;
 175   return entry;
 176 }
 177
 178 /* Internal routine to find entry in the hash table by `key'. */
 179
 180 static inline SilcHashTableEntry *
 181 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
 182                                      SilcHashFunction hash,
 183                                      void *hash_user_context,
 184                                      SilcHashCompare compare,
 185                                      void *compare_user_context)
 186 {
 187   SilcHashTableEntry *entry;
 188   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 189
 190   SILC_HT_DEBUG(("index %d key %p", i, key));
 191
 192   entry = &ht->table[i];
 193   if (compare) {
 194     while (*entry && !compare((*entry)->key, key, compare_user_context))
 195       entry = &(*entry)->next;
 196   } else {
 197     while (*entry && (*entry)->key != key)
 198       entry = &(*entry)->next;
 199   }
 200
 201   return entry;
 202 }
 203
 204 /* Internal routine to find all keys by `key'. This may return multiple
 205    entries if multiple entries with same key exists. With specific
 206    hash and comparison functions. */
 207
 208 static inline void
 209 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
 210                                   SilcHashFunction hash,
 211                                   void *hash_user_context,
 212                                   SilcHashCompare compare,
 213                                   void *compare_user_context,
 214                                   SilcHashForeach foreach,
 215                                   void *foreach_user_context)
 216 {
 217   SilcHashTableEntry e, tmp;
 218   SilcBool auto_rehash, found = FALSE;
 219   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 220
 221   SILC_HT_DEBUG(("index %d key %p", i, key));
 222
 223   /* Disallow auto rehashing while going through the table since we call
 224      the `foreach' function which could alter the table. */
 225   auto_rehash = ht->auto_rehash;
 226   ht->auto_rehash = FALSE;
 227
 228   e = ht->table[i];
 229   if (compare) {
 230     while (e) {
 231       tmp = e->next;
 232       if (compare(e->key, key, compare_user_context)) {
 233         found = TRUE;
 234         foreach(e->key, e->context, foreach_user_context);
 235       }
 236       e = tmp;
 237     }
 238   } else {
 239     while (e) {
 240       tmp = e->next;
 241       if (e->key == key) {
 242         found = TRUE;
 243         foreach(e->key, e->context, foreach_user_context);
 244       }
 245       e = tmp;
 246     }
 247   }
 248
 249   /* If nothing was found call with NULL context the callback */
 250   if (!found)
 251     foreach(key, NULL, foreach_user_context);
 252
 253   ht->auto_rehash = auto_rehash;
 254 }
 255
 256 /* Internal routine to add new key to the hash table */
 257
 258 static inline SilcBool
 259 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
 260                              SilcHashFunction hash,
 261                              void *hash_user_context)
 262 {
 263   SilcHashTableEntry *entry;
 264   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 265
 266   SILC_HT_DEBUG(("index %d key %p", i, key));
 267
 268   entry = &ht->table[i];
 269   if (*entry) {
 270     /* The entry exists already. We have a collision, add it to the
 271        list to avoid collision. */
 272     SilcHashTableEntry e, tmp;
 273
 274     e = *entry;
 275     tmp = e->next;
 276     while (tmp) {
 277       e = tmp;
 278       tmp = tmp->next;
 279     }
 280
 281     SILC_HT_DEBUG(("Collision; adding new key to list"));
 282
 283     e->next = silc_scalloc(ht->stack, 1, sizeof(*e->next));
 284     if (!e->next)
 285       return FALSE;
 286     e->next->key = key;
 287     e->next->context = context;
 288     ht->entry_count++;
 289   } else {
 290     /* New key */
 291     SILC_HT_DEBUG(("New key"));
 292     *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
 293     if (!(*entry))
 294       return FALSE;
 295     (*entry)->key = key;
 296     (*entry)->context = context;
 297     ht->entry_count++;
 298   }
 299
 300   if (SILC_HASH_REHASH_INC)
 301     silc_hash_table_rehash(ht, 0);
 302
 303   return TRUE;
 304 }
 305
 306 /* Internal routine to replace old key with new one (if it exists) */
 307
 308 static inline SilcBool
 309 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 310                                  SilcHashFunction hash,
 311                                  void *hash_user_context)
 312 {
 313   SilcHashTableEntry *entry;
 314   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 315
 316   SILC_HT_DEBUG(("index %d key %p", i, key));
 317
 318   entry = &ht->table[i];
 319   if (*entry) {
 320     /* The entry exists already. We have a collision, replace the old
 321        key and context. */
 322     if (ht->destructor)
 323       ht->destructor((*entry)->key, (*entry)->context,
 324                      ht->destructor_user_context);
 325   } else {
 326     /* New key */
 327     *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
 328     if (!(*entry))
 329       return FALSE;
 330     ht->entry_count++;
 331   }
 332
 333   (*entry)->key = key;
 334   (*entry)->context = context;
 335
 336   if (SILC_HASH_REHASH_INC)
 337     silc_hash_table_rehash(ht, 0);
 338
 339   return TRUE;
 340 }
 341
 342 /* Allocates new hash table and returns it.  If the `table_size' is not
 343    zero then the hash table size is the size provided. If zero then the
 344    default size will be used. Note that if the `table_size' is provided
 345    it should be a prime. The `hash', `compare' and `destructor' are
 346    the hash function, the key comparison function and key and context
 347    destructor function, respectively. The `hash' is mandatory, the others
 348    are optional. */
 349
 350 SilcHashTable silc_hash_table_alloc(SilcStack stack,
 351                                     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     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
 365     return NULL;
 366   }
 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     silc_set_errno(SILC_ERR_NOT_FOUND);
 496     return FALSE;
 497   }
 498
 499   e = *entry;
 500
 501   if (!prev && e->next)
 502     *entry = e->next;
 503   if (!prev && e->next == NULL)
 504     *entry = NULL;
 505   if (prev)
 506     prev->next = NULL;
 507   if (prev && e->next)
 508     prev->next = e->next;
 509
 510   if (ht->destructor)
 511     ht->destructor(e->key, e->context, ht->destructor_user_context);
 512   silc_sfree(ht->stack, e);
 513
 514   ht->entry_count--;
 515
 516   if (SILC_HASH_REHASH_DEC)
 517     silc_hash_table_rehash(ht, 0);
 518
 519   return TRUE;
 520 }
 521
 522 /* Same as above but with specific hash and compare functions. */
 523
 524 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 525                                  SilcHashFunction hash,
 526                                  void *hash_user_context,
 527                                  SilcHashCompare compare,
 528                                  void *compare_user_context,
 529                                  SilcHashDestructor destructor,
 530                                  void *destructor_user_context)
 531 {
 532   SilcHashTableEntry *entry, prev, e;
 533
 534   entry = silc_hash_table_find_internal(ht, key, &prev,
 535                                         hash ? hash : ht->hash,
 536                                         hash_user_context ? hash_user_context :
 537                                         ht->hash_user_context,
 538                                         compare ? compare : ht->compare,
 539                                         compare_user_context ?
 540                                         compare_user_context :
 541                                         ht->compare_user_context);
 542   if (*entry == NULL) {
 543     silc_set_errno(SILC_ERR_NOT_FOUND);
 544     return FALSE;
 545   }
 546
 547   e = *entry;
 548
 549   if (!prev && e->next)
 550     *entry = e->next;
 551   if (!prev && e->next == NULL)
 552     *entry = NULL;
 553   if (prev)
 554     prev->next = NULL;
 555   if (prev && e->next)
 556     prev->next = e->next;
 557
 558   if (destructor) {
 559     destructor(e->key, e->context, destructor_user_context);
 560   } else {
 561     if (ht->destructor)
 562       ht->destructor(e->key, e->context, ht->destructor_user_context);
 563   }
 564   silc_sfree(ht->stack, e);
 565
 566   ht->entry_count--;
 567
 568   if (SILC_HASH_REHASH_DEC)
 569     silc_hash_table_rehash(ht, 0);
 570
 571   return TRUE;
 572 }
 573
 574 /* Same as above but verifies that the context associated with the `key'
 575    matches the `context'. This is handy to use with hash tables that may
 576    have duplicate keys. In that case the `context' may be used to check
 577    whether the correct entry is being deleted. */
 578
 579 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 580                                         void *context)
 581 {
 582   SilcHashTableEntry *entry, prev, e;
 583
 584   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 585                                                 ht->hash,
 586                                                 ht->hash_user_context,
 587                                                 ht->compare,
 588                                                 ht->compare_user_context);
 589   if (*entry == NULL) {
 590     silc_set_errno(SILC_ERR_NOT_FOUND);
 591     return FALSE;
 592   }
 593
 594   e = *entry;
 595
 596   if (!prev && e->next)
 597     *entry = e->next;
 598   if (!prev && e->next == NULL)
 599     *entry = NULL;
 600   if (prev)
 601     prev->next = NULL;
 602   if (prev && e->next)
 603     prev->next = e->next;
 604
 605   if (ht->destructor)
 606     ht->destructor(e->key, e->context, ht->destructor_user_context);
 607   silc_sfree(ht->stack, e);
 608
 609   ht->entry_count--;
 610
 611   if (SILC_HASH_REHASH_DEC)
 612     silc_hash_table_rehash(ht, 0);
 613
 614   return TRUE;
 615 }
 616
 617 /* Same as above but with specific hash and compare functions. */
 618
 619 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 620                                             void *context,
 621                                             SilcHashFunction hash,
 622                                             void *hash_user_context,
 623                                             SilcHashCompare compare,
 624                                             void *compare_user_context,
 625                                             SilcHashDestructor destructor,
 626                                             void *destructor_user_context)
 627 {
 628   SilcHashTableEntry *entry, prev, e;
 629
 630   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 631                                                 hash ? hash : ht->hash,
 632                                                 hash_user_context ?
 633                                                 hash_user_context :
 634                                                 ht->hash_user_context,
 635                                                 compare ?
 636                                                 compare : ht->compare,
 637                                                 compare_user_context ?
 638                                                 compare_user_context :
 639                                                 ht->compare_user_context);
 640   if (*entry == NULL) {
 641     silc_set_errno(SILC_ERR_NOT_FOUND);
 642     return FALSE;
 643   }
 644
 645   e = *entry;
 646
 647   if (!prev && e->next)
 648     *entry = e->next;
 649   if (!prev && e->next == NULL)
 650     *entry = NULL;
 651   if (prev)
 652     prev->next = NULL;
 653   if (prev && e->next)
 654     prev->next = e->next;
 655
 656   if (destructor) {
 657     destructor(e->key, e->context, destructor_user_context);
 658   } else {
 659     if (ht->destructor)
 660       ht->destructor(e->key, e->context, ht->destructor_user_context);
 661   }
 662   silc_sfree(ht->stack, e);
 663
 664   ht->entry_count--;
 665
 666   if (SILC_HASH_REHASH_DEC)
 667     silc_hash_table_rehash(ht, 0);
 668
 669   return TRUE;
 670 }
 671
 672 /* Finds the entry in the hash table by the provided `key' as fast as
 673    possible. Return TRUE if the entry was found and FALSE otherwise.
 674    The found entry is returned to the `ret_key' and `ret_context',
 675    respectively. If the `ret_key and `ret_context' are NULL then this
 676    maybe used only to check whether given key exists in the table. */
 677
 678 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
 679                               void **ret_key, void **ret_context)
 680 {
 681   return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
 682                                   NULL, NULL, NULL, NULL);
 683 }
 684
 685 /* Same as above but with specified hash and comparison functions. */
 686
 687 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 688                                   void **ret_key, void **ret_context,
 689                                   SilcHashFunction hash,
 690                                   void *hash_user_context,
 691                                   SilcHashCompare compare,
 692                                   void *compare_user_context)
 693 {
 694   SilcHashTableEntry *entry;
 695
 696   entry = silc_hash_table_find_internal_simple(ht, key,
 697                                                hash ? hash : ht->hash,
 698                                                hash_user_context ?
 699                                                hash_user_context :
 700                                                ht->hash_user_context,
 701                                                compare ? compare :
 702                                                ht->compare,
 703                                                compare_user_context ?
 704                                                compare_user_context :
 705                                                ht->compare_user_context);
 706   if (*entry == NULL) {
 707     silc_set_errno(SILC_ERR_NOT_FOUND);
 708     return FALSE;
 709   }
 710
 711   if (ret_key)
 712     *ret_key = (*entry)->key;
 713   if (ret_context)
 714     *ret_context = (*entry)->context;
 715
 716   return TRUE;
 717 }
 718
 719 /* Same as silc_hash_table_find but finds with specific context. */
 720
 721 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 722                                          void *context, void **ret_key)
 723 {
 724   return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
 725                                              NULL, NULL, NULL, NULL);
 726 }
 727
 728 /* Same as above but with specified hash and comparison functions. */
 729
 730 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
 731                                              void *context, void **ret_key,
 732                                              SilcHashFunction hash,
 733                                              void *hash_user_context,
 734                                              SilcHashCompare compare,
 735                                              void *compare_user_context)
 736 {
 737   SilcHashTableEntry *entry;
 738
 739   entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
 740                                                 hash ? hash : ht->hash,
 741                                                 hash_user_context ?
 742                                                 hash_user_context :
 743                                                 ht->hash_user_context,
 744                                                 compare ? compare :
 745                                                 ht->compare,
 746                                                 compare_user_context ?
 747                                                 compare_user_context :
 748                                                 ht->compare_user_context);
 749   if (!entry || !(*entry)) {
 750     silc_set_errno(SILC_ERR_NOT_FOUND);
 751     return FALSE;
 752   }
 753
 754   if (ret_key)
 755     *ret_key = (*entry)->key;
 756
 757   return TRUE;
 758 }
 759
 760 /* As the hash table is collision resistant it is possible to save duplicate
 761    keys to the hash table. This function can be used to find all keys
 762    and contexts from the hash table that are found using the `key'. The
 763    `foreach' is called for every found key. */
 764
 765 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 766                                   SilcHashForeach foreach, void *user_context)
 767 {
 768   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 769                                     ht->compare, ht->compare_user_context,
 770                                     foreach, user_context);
 771 }
 772
 773 /* Same as above but with specific hash and comparison functions. */
 774
 775 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 776                                       SilcHashFunction hash,
 777                                       void *hash_user_context,
 778                                       SilcHashCompare compare,
 779                                       void *compare_user_context,
 780                                       SilcHashForeach foreach,
 781                                       void *foreach_user_context)
 782 {
 783   silc_hash_table_find_internal_all(ht, key,
 784                                     hash ? hash : ht->hash,
 785                                     hash_user_context ?
 786                                     hash_user_context :
 787                                     ht->hash_user_context,
 788                                     compare ? compare :
 789                                     ht->compare,
 790                                     compare_user_context ?
 791                                     compare_user_context :
 792                                     ht->compare_user_context,
 793                                     foreach, foreach_user_context);
 794 }
 795
 796 /* Traverse all entrys in the hash table and call the `foreach' for
 797    every entry with the `user_context' context. */
 798
 799 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 800                              void *user_context)
 801 {
 802   SilcHashTableEntry e, tmp;
 803   int i;
 804   SilcBool auto_rehash;
 805
 806   if (!foreach)
 807     return;
 808
 809   auto_rehash = ht->auto_rehash;
 810   ht->auto_rehash = FALSE;
 811   for (i = 0; i < primesize[ht->table_size]; i++) {
 812     e = ht->table[i];
 813     while (e) {
 814       /* Entry may become invalid inside the `foreach' */
 815       tmp = e->next;
 816       foreach(e->key, e->context, user_context);
 817       e = tmp;
 818     }
 819   }
 820   ht->auto_rehash = auto_rehash;
 821 }
 822
 823 /* Rehashs the hash table. The size of the new hash table is provided
 824    as `new_size'. If the `new_size' is zero then this routine will make
 825    the new table of a suitable size. Note that this operation may be
 826    very slow. */
 827
 828 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 829 {
 830   int i;
 831   SilcHashTableEntry *table, e, tmp;
 832   SilcUInt32 table_size, size_index;
 833   SilcBool auto_rehash;
 834
 835   SILC_HT_DEBUG(("Start"));
 836
 837   if (new_size)
 838     silc_hash_table_primesize(new_size, &size_index);
 839   else
 840     silc_hash_table_primesize(ht->entry_count, &size_index);
 841
 842   if (size_index == ht->table_size)
 843     return;
 844
 845   SILC_HT_DEBUG(("Rehashing"));
 846
 847   /* Take old hash table */
 848   table = ht->table;
 849   table_size = ht->table_size;
 850   auto_rehash = ht->auto_rehash;
 851   ht->auto_rehash = FALSE;
 852
 853   /* Allocate new table */
 854   ht->table = silc_scalloc(ht->stack,
 855                            primesize[size_index], sizeof(*ht->table));
 856   if (!ht->table)
 857     return;
 858   ht->table_size = size_index;
 859   ht->entry_count = 0;
 860
 861   /* Rehash */
 862   for (i = 0; i < primesize[table_size]; i++) {
 863     e = table[i];
 864     while (e) {
 865       silc_hash_table_add(ht, e->key, e->context);
 866       tmp = e;
 867       e = e->next;
 868
 869       /* Remove old entry */
 870       silc_sfree(ht->stack, tmp);
 871     }
 872   }
 873
 874   ht->auto_rehash = auto_rehash;
 875
 876   /* Remove old table */
 877   silc_sfree(ht->stack, table);
 878 }
 879
 880 /* Same as above but with specific hash function. */
 881
 882 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 883                                 SilcHashFunction hash,
 884                                 void *hash_user_context)
 885 {
 886   int i;
 887   SilcHashTableEntry *table, e, tmp;
 888   SilcUInt32 table_size, size_index;
 889   SilcBool auto_rehash;
 890
 891   SILC_HT_DEBUG(("Start"));
 892
 893   if (new_size)
 894     silc_hash_table_primesize(new_size, &size_index);
 895   else
 896     silc_hash_table_primesize(ht->entry_count, &size_index);
 897
 898   if (size_index == ht->table_size)
 899     return;
 900
 901   SILC_HT_DEBUG(("Rehashing"));
 902
 903   /* Take old hash table */
 904   table = ht->table;
 905   table_size = ht->table_size;
 906   auto_rehash = ht->auto_rehash;
 907   ht->auto_rehash = FALSE;
 908
 909   /* Allocate new table */
 910   ht->table = silc_scalloc(ht->stack,
 911                            primesize[size_index], sizeof(*ht->table));
 912   if (!ht->table)
 913     return;
 914   ht->table_size = size_index;
 915   ht->entry_count = 0;
 916
 917   /* Rehash */
 918   for (i = 0; i < primesize[table_size]; i++) {
 919     e = table[i];
 920     while (e) {
 921       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 922                               hash_user_context);
 923       tmp = e;
 924       e = e->next;
 925
 926       /* Remove old entry */
 927       silc_sfree(ht->stack, tmp);
 928     }
 929   }
 930
 931   ht->auto_rehash = auto_rehash;
 932
 933   /* Remove old table */
 934   silc_sfree(ht->stack, table);
 935 }
 936
 937 /* Prepares the `htl' list structure sent as argument to be used in the
 938    hash table traversing with the silc_hash_table_get. Usage:
 939    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 940
 941 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 942 {
 943   htl->ht = ht;
 944   htl->entry = NULL;
 945   htl->index = 0;
 946   htl->auto_rehash = ht->auto_rehash;
 947
 948   /* Disallow rehashing of the table while traversing the table */
 949   ht->auto_rehash = FALSE;
 950 }
 951
 952 /* Resets the `htl' SilcHashTableList. */
 953
 954 void silc_hash_table_list_reset(SilcHashTableList *htl)
 955 {
 956   /* Set back the original auto rehash value to the table */
 957   htl->ht->auto_rehash = htl->auto_rehash;
 958 }
 959
 960 /* Returns always the next entry in the hash table into the `key' and
 961    `context' and TRUE.  If this returns FALSE then there are no anymore
 962    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 963
 964 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
 965                              void **context)
 966 {
 967   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 968
 969   if (!htl->ht->entry_count)
 970     return FALSE;
 971
 972   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 973     entry = htl->ht->table[htl->index];
 974     htl->index++;
 975   }
 976
 977   if (!entry)
 978     return FALSE;
 979
 980   htl->entry = entry->next;
 981
 982   if (key)
 983     *key = entry->key;
 984   if (context)
 985     *context = entry->context;
 986
 987   return TRUE;
 988 }
 989
 990 /**************************** Utility functions *****************************/
 991
 992 /* Case sensitive hashing */
 993
 994 SilcUInt32 silc_hash_string(void *key, void *user_context)
 995 {
 996   char *s = (char *)key;
 997   SilcUInt32 h = 0;
 998
 999   while (*s != '\0') {
1000     h += *s++;
1001     h += (h << 10);
1002     h ^= (h >> 6);
1003   }
1004
1005   h += (h << 3);
1006   h ^= (h >> 11);
1007   h += (h << 15);
1008
1009   return h;
1010 }
1011
1012 /* Case-insensitive hashing */
1013
1014 SilcUInt32 silc_hash_string_case(void *key, void *user_context)
1015 {
1016   char *s = (char *)key;
1017   SilcUInt32 h = 0;
1018
1019   while (*s != '\0') {
1020     h += tolower((int)*s);
1021     h += (h << 10);
1022     h ^= (h >> 6);
1023     s++;
1024   }
1025
1026   h += (h << 3);
1027   h ^= (h >> 11);
1028   h += (h << 15);
1029
1030   return h;
1031 }
1032
1033 /* Hash UTF-8 string */
1034
1035 SilcUInt32 silc_hash_utf8_string(void *key, void *user_context)
1036 {
1037   char *s = (char *)key;
1038   SilcUInt32 h = 0;
1039
1040   while (*s != '\0') {
1041     h += *s++;
1042     h += (h << 10);
1043     h ^= (h >> 6);
1044   }
1045
1046   h += (h << 3);
1047   h ^= (h >> 11);
1048   h += (h << 15);
1049
1050   return h;
1051 }
1052
1053 /* Basic hash function to hash integers. */
1054
1055 SilcUInt32 silc_hash_uint(void *key, void *user_context)
1056 {
1057   return SILC_PTR_TO_32(key);
1058 }
1059
1060 /* Basic hash funtion to hash pointers. */
1061
1062 SilcUInt32 silc_hash_ptr(void *key, void *user_context)
1063 {
1064   return SILC_PTR_TO_32(key);
1065 }
1066
1067 /* Hash binary data. The `user_context' is the data length. */
1068
1069 SilcUInt32 silc_hash_data(void *key, void *user_context)
1070 {
1071   SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i;
1072   unsigned char *data = (char *)key;
1073
1074   h = (data[0] * data[len - 1] + 1) * len;
1075
1076   for (i = 0; i < len; i++) {
1077     h += data[i];
1078     h += (h << 10);
1079     h ^= (h >> 6);
1080   }
1081
1082   h += (h << 3);
1083   h ^= (h >> 11);
1084   h += (h << 15);
1085
1086   return h;
1087 }
1088
1089 /* Compares two strings. */
1090
1091 SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context)
1092 {
1093   return !strcmp((char *)key1, (char *)key2);
1094 }
1095
1096 /* Compares two strings, ignores case. */
1097
1098 SilcBool silc_hash_string_case_compare(void *key1, void *key2,
1099                                        void *user_context)
1100 {
1101   return !strcasecmp((char *)key1, (char *)key2);
1102 }
1103
1104 /* Compares binary data. */
1105
1106 SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context)
1107 {
1108   SilcUInt32 len = SILC_PTR_TO_32(user_context);
1109   return !memcmp(key1, key2, len);
1110 }
1111
1112 /* Compares UTF-8 string. */
1113
1114 SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context)
1115 {
1116   int l1 = strlen((char *)key1);
1117   int l2 = strlen((char *)key2);
1118   if (l1 != l2)
1119     return FALSE;
1120   return !memcmp(key1, key2, l2);
1121 }
1122
1123 /* Generic destructor */
1124
1125 void silc_hash_destructor(void *key, void *context, void *user_context)
1126 {
1127   silc_free(key);
1128   silc_free(context);
1129 }