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     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
 367     return NULL;
 368   }
 369
 370   if (stack)
 371     stack = silc_stack_alloc(0, stack);
 372
 373   ht = silc_scalloc(stack, 1, sizeof(*ht));
 374   if (!ht) {
 375     silc_stack_free(stack);
 376     return NULL;
 377   }
 378   ht->table = silc_scalloc(stack,
 379                            table_size ? silc_hash_table_primesize(table_size,
 380                                                                   &size_index) :
 381                            primesize[SILC_HASH_TABLE_SIZE],
 382                            sizeof(*ht->table));
 383   if (!ht->table) {
 384     silc_stack_free(stack);
 385     silc_sfree(stack, ht);
 386     return NULL;
 387   }
 388   ht->stack = stack;
 389   ht->table_size = size_index;
 390   ht->hash = hash;
 391   ht->compare = compare;
 392   ht->destructor = destructor;
 393   ht->hash_user_context = hash_user_context;
 394   ht->compare_user_context = compare_user_context;
 395   ht->destructor_user_context = destructor_user_context;
 396   ht->auto_rehash = auto_rehash;
 397
 398   return ht;
 399 }
 400
 401 /* Frees the hash table. The destructor function provided in the
 402    silc_hash_table_alloc will be called for all keys in the hash table. */
 403
 404 void silc_hash_table_free(SilcHashTable ht)
 405 {
 406   SilcStack stack = ht->stack;
 407   SilcHashTableEntry e, tmp;
 408   int i;
 409
 410   for (i = 0; i < primesize[ht->table_size]; i++) {
 411     e = ht->table[i];
 412     while (e) {
 413       if (ht->destructor)
 414         ht->destructor(e->key, e->context, ht->destructor_user_context);
 415       tmp = e;
 416       e = e->next;
 417       silc_sfree(stack, tmp);
 418     }
 419   }
 420
 421   silc_sfree(stack, ht->table);
 422   silc_sfree(stack, ht);
 423   silc_stack_free(stack);
 424 }
 425
 426 /* Returns the size of the hash table */
 427
 428 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
 429 {
 430   return primesize[ht->table_size];
 431 }
 432
 433 /* Returns the number of the entires in the hash table. If there is more
 434    entries in the table thatn the size of the hash table calling the
 435    silc_hash_table_rehash is recommended. */
 436
 437 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
 438 {
 439   return ht->entry_count;
 440 }
 441
 442 /* Adds new entry to the hash table. The `key' is hashed using the
 443    hash function and the both `key' and `context' will be saved to the
 444    hash table. This function quarantees that the entry is always added
 445    to the hash table reliably (it is collision resistant). */
 446
 447 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 448 {
 449   return silc_hash_table_add_internal(ht, key, context, ht->hash,
 450                                       ht->hash_user_context);
 451 }
 452
 453 /* Same as above but with specific hash function and user context. */
 454
 455 SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 456                                  SilcHashFunction hash,
 457                                  void *hash_user_context)
 458 {
 459   return silc_hash_table_add_internal(ht, key, context,
 460                                       hash, hash_user_context);
 461 }
 462
 463 /* Same as above but if the `key' already exists in the hash table
 464    the old key and the old context will be replace with the `key' and
 465    the `context. The destructor function will be called for the
 466    replaced key and context. */
 467
 468 SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context)
 469 {
 470   return silc_hash_table_replace_internal(ht, key, context, ht->hash,
 471                                           ht->hash_user_context);
 472 }
 473
 474 /* Same as above but with specific hash function. */
 475
 476 SilcBool silc_hash_table_set_ext(SilcHashTable ht, void *key,
 477                                  void *context,
 478                                  SilcHashFunction hash,
 479                                  void *hash_user_context)
 480 {
 481   return silc_hash_table_replace_internal(ht, key, context,
 482                                           hash, hash_user_context);
 483 }
 484
 485 /* Removes the entry from the hash table by the provided `key'. This will
 486    call the destructor funtion for the found entry. Return TRUE if the
 487    entry was removed successfully and FALSE otherwise. */
 488
 489 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
 490 {
 491   SilcHashTableEntry *entry, prev, e;
 492
 493   entry = silc_hash_table_find_internal(ht, key, &prev,
 494                                         ht->hash, ht->hash_user_context,
 495                                         ht->compare, ht->compare_user_context);
 496   if (*entry == NULL) {
 497     silc_set_errno(SILC_ERR_NOT_FOUND);
 498     return FALSE;
 499   }
 500
 501   e = *entry;
 502
 503   if (!prev && e->next)
 504     *entry = e->next;
 505   if (!prev && e->next == NULL)
 506     *entry = NULL;
 507   if (prev)
 508     prev->next = NULL;
 509   if (prev && e->next)
 510     prev->next = e->next;
 511
 512   if (ht->destructor)
 513     ht->destructor(e->key, e->context, ht->destructor_user_context);
 514   silc_sfree(ht->stack, e);
 515
 516   ht->entry_count--;
 517
 518   if (SILC_HASH_REHASH_DEC)
 519     silc_hash_table_rehash(ht, 0);
 520
 521   return TRUE;
 522 }
 523
 524 /* Same as above but with specific hash and compare functions. */
 525
 526 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 527                                  SilcHashFunction hash,
 528                                  void *hash_user_context,
 529                                  SilcHashCompare compare,
 530                                  void *compare_user_context,
 531                                  SilcHashDestructor destructor,
 532                                  void *destructor_user_context)
 533 {
 534   SilcHashTableEntry *entry, prev, e;
 535
 536   entry = silc_hash_table_find_internal(ht, key, &prev,
 537                                         hash ? hash : ht->hash,
 538                                         hash_user_context ? hash_user_context :
 539                                         ht->hash_user_context,
 540                                         compare ? compare : ht->compare,
 541                                         compare_user_context ?
 542                                         compare_user_context :
 543                                         ht->compare_user_context);
 544   if (*entry == NULL) {
 545     silc_set_errno(SILC_ERR_NOT_FOUND);
 546     return FALSE;
 547   }
 548
 549   e = *entry;
 550
 551   if (!prev && e->next)
 552     *entry = e->next;
 553   if (!prev && e->next == NULL)
 554     *entry = NULL;
 555   if (prev)
 556     prev->next = NULL;
 557   if (prev && e->next)
 558     prev->next = e->next;
 559
 560   if (destructor) {
 561     destructor(e->key, e->context, destructor_user_context);
 562   } else {
 563     if (ht->destructor)
 564       ht->destructor(e->key, e->context, ht->destructor_user_context);
 565   }
 566   silc_sfree(ht->stack, e);
 567
 568   ht->entry_count--;
 569
 570   if (SILC_HASH_REHASH_DEC)
 571     silc_hash_table_rehash(ht, 0);
 572
 573   return TRUE;
 574 }
 575
 576 /* Same as above but verifies that the context associated with the `key'
 577    matches the `context'. This is handy to use with hash tables that may
 578    have duplicate keys. In that case the `context' may be used to check
 579    whether the correct entry is being deleted. */
 580
 581 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 582                                         void *context)
 583 {
 584   SilcHashTableEntry *entry, prev, e;
 585
 586   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 587                                                 ht->hash,
 588                                                 ht->hash_user_context,
 589                                                 ht->compare,
 590                                                 ht->compare_user_context);
 591   if (*entry == NULL) {
 592     silc_set_errno(SILC_ERR_NOT_FOUND);
 593     return FALSE;
 594   }
 595
 596   e = *entry;
 597
 598   if (!prev && e->next)
 599     *entry = e->next;
 600   if (!prev && e->next == NULL)
 601     *entry = NULL;
 602   if (prev)
 603     prev->next = NULL;
 604   if (prev && e->next)
 605     prev->next = e->next;
 606
 607   if (ht->destructor)
 608     ht->destructor(e->key, e->context, ht->destructor_user_context);
 609   silc_sfree(ht->stack, e);
 610
 611   ht->entry_count--;
 612
 613   if (SILC_HASH_REHASH_DEC)
 614     silc_hash_table_rehash(ht, 0);
 615
 616   return TRUE;
 617 }
 618
 619 /* Same as above but with specific hash and compare functions. */
 620
 621 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 622                                             void *context,
 623                                             SilcHashFunction hash,
 624                                             void *hash_user_context,
 625                                             SilcHashCompare compare,
 626                                             void *compare_user_context,
 627                                             SilcHashDestructor destructor,
 628                                             void *destructor_user_context)
 629 {
 630   SilcHashTableEntry *entry, prev, e;
 631
 632   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 633                                                 hash ? hash : ht->hash,
 634                                                 hash_user_context ?
 635                                                 hash_user_context :
 636                                                 ht->hash_user_context,
 637                                                 compare ?
 638                                                 compare : ht->compare,
 639                                                 compare_user_context ?
 640                                                 compare_user_context :
 641                                                 ht->compare_user_context);
 642   if (*entry == NULL) {
 643     silc_set_errno(SILC_ERR_NOT_FOUND);
 644     return FALSE;
 645   }
 646
 647   e = *entry;
 648
 649   if (!prev && e->next)
 650     *entry = e->next;
 651   if (!prev && e->next == NULL)
 652     *entry = NULL;
 653   if (prev)
 654     prev->next = NULL;
 655   if (prev && e->next)
 656     prev->next = e->next;
 657
 658   if (destructor) {
 659     destructor(e->key, e->context, destructor_user_context);
 660   } else {
 661     if (ht->destructor)
 662       ht->destructor(e->key, e->context, ht->destructor_user_context);
 663   }
 664   silc_sfree(ht->stack, e);
 665
 666   ht->entry_count--;
 667
 668   if (SILC_HASH_REHASH_DEC)
 669     silc_hash_table_rehash(ht, 0);
 670
 671   return TRUE;
 672 }
 673
 674 /* Finds the entry in the hash table by the provided `key' as fast as
 675    possible. Return TRUE if the entry was found and FALSE otherwise.
 676    The found entry is returned to the `ret_key' and `ret_context',
 677    respectively. If the `ret_key and `ret_context' are NULL then this
 678    maybe used only to check whether given key exists in the table. */
 679
 680 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
 681                               void **ret_key, void **ret_context)
 682 {
 683   return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
 684                                   NULL, NULL, NULL, NULL);
 685 }
 686
 687 /* Same as above but with specified hash and comparison functions. */
 688
 689 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 690                                   void **ret_key, void **ret_context,
 691                                   SilcHashFunction hash,
 692                                   void *hash_user_context,
 693                                   SilcHashCompare compare,
 694                                   void *compare_user_context)
 695 {
 696   SilcHashTableEntry *entry;
 697
 698   entry = silc_hash_table_find_internal_simple(ht, key,
 699                                                hash ? hash : ht->hash,
 700                                                hash_user_context ?
 701                                                hash_user_context :
 702                                                ht->hash_user_context,
 703                                                compare ? compare :
 704                                                ht->compare,
 705                                                compare_user_context ?
 706                                                compare_user_context :
 707                                                ht->compare_user_context);
 708   if (*entry == NULL) {
 709     silc_set_errno(SILC_ERR_NOT_FOUND);
 710     return FALSE;
 711   }
 712
 713   if (ret_key)
 714     *ret_key = (*entry)->key;
 715   if (ret_context)
 716     *ret_context = (*entry)->context;
 717
 718   return TRUE;
 719 }
 720
 721 /* Same as silc_hash_table_find but finds with specific context. */
 722
 723 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 724                                          void *context, void **ret_key)
 725 {
 726   return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
 727                                              NULL, NULL, NULL, NULL);
 728 }
 729
 730 /* Same as above but with specified hash and comparison functions. */
 731
 732 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
 733                                              void *context, void **ret_key,
 734                                              SilcHashFunction hash,
 735                                              void *hash_user_context,
 736                                              SilcHashCompare compare,
 737                                              void *compare_user_context)
 738 {
 739   SilcHashTableEntry *entry;
 740
 741   entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
 742                                                 hash ? hash : ht->hash,
 743                                                 hash_user_context ?
 744                                                 hash_user_context :
 745                                                 ht->hash_user_context,
 746                                                 compare ? compare :
 747                                                 ht->compare,
 748                                                 compare_user_context ?
 749                                                 compare_user_context :
 750                                                 ht->compare_user_context);
 751   if (!entry || !(*entry)) {
 752     silc_set_errno(SILC_ERR_NOT_FOUND);
 753     return FALSE;
 754   }
 755
 756   if (ret_key)
 757     *ret_key = (*entry)->key;
 758
 759   return TRUE;
 760 }
 761
 762 /* As the hash table is collision resistant it is possible to save duplicate
 763    keys to the hash table. This function can be used to find all keys
 764    and contexts from the hash table that are found using the `key'. The
 765    `foreach' is called for every found key. */
 766
 767 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 768                                   SilcHashForeach foreach, void *user_context)
 769 {
 770   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 771                                     ht->compare, ht->compare_user_context,
 772                                     foreach, user_context);
 773 }
 774
 775 /* Same as above but with specific hash and comparison functions. */
 776
 777 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 778                                       SilcHashFunction hash,
 779                                       void *hash_user_context,
 780                                       SilcHashCompare compare,
 781                                       void *compare_user_context,
 782                                       SilcHashForeach foreach,
 783                                       void *foreach_user_context)
 784 {
 785   silc_hash_table_find_internal_all(ht, key,
 786                                     hash ? hash : ht->hash,
 787                                     hash_user_context ?
 788                                     hash_user_context :
 789                                     ht->hash_user_context,
 790                                     compare ? compare :
 791                                     ht->compare,
 792                                     compare_user_context ?
 793                                     compare_user_context :
 794                                     ht->compare_user_context,
 795                                     foreach, foreach_user_context);
 796 }
 797
 798 /* Traverse all entrys in the hash table and call the `foreach' for
 799    every entry with the `user_context' context. */
 800
 801 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 802                              void *user_context)
 803 {
 804   SilcHashTableEntry e, tmp;
 805   int i;
 806   SilcBool auto_rehash;
 807
 808   if (!foreach)
 809     return;
 810
 811   auto_rehash = ht->auto_rehash;
 812   ht->auto_rehash = FALSE;
 813   for (i = 0; i < primesize[ht->table_size]; i++) {
 814     e = ht->table[i];
 815     while (e) {
 816       /* Entry may become invalid inside the `foreach' */
 817       tmp = e->next;
 818       foreach(e->key, e->context, user_context);
 819       e = tmp;
 820     }
 821   }
 822   ht->auto_rehash = auto_rehash;
 823 }
 824
 825 /* Rehashs the hash table. The size of the new hash table is provided
 826    as `new_size'. If the `new_size' is zero then this routine will make
 827    the new table of a suitable size. Note that this operation may be
 828    very slow. */
 829
 830 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 831 {
 832   int i;
 833   SilcHashTableEntry *table, e, tmp;
 834   SilcUInt32 table_size, size_index;
 835   SilcBool auto_rehash;
 836
 837   SILC_HT_DEBUG(("Start"));
 838
 839   if (new_size)
 840     silc_hash_table_primesize(new_size, &size_index);
 841   else
 842     silc_hash_table_primesize(ht->entry_count, &size_index);
 843
 844   if (size_index == ht->table_size)
 845     return;
 846
 847   SILC_HT_DEBUG(("Rehashing"));
 848
 849   /* Take old hash table */
 850   table = ht->table;
 851   table_size = ht->table_size;
 852   auto_rehash = ht->auto_rehash;
 853   ht->auto_rehash = FALSE;
 854
 855   /* Allocate new table */
 856   ht->table = silc_scalloc(ht->stack,
 857                            primesize[size_index], sizeof(*ht->table));
 858   if (!ht->table)
 859     return;
 860   ht->table_size = size_index;
 861   ht->entry_count = 0;
 862
 863   /* Rehash */
 864   for (i = 0; i < primesize[table_size]; i++) {
 865     e = table[i];
 866     while (e) {
 867       silc_hash_table_add(ht, e->key, e->context);
 868       tmp = e;
 869       e = e->next;
 870
 871       /* Remove old entry */
 872       silc_sfree(ht->stack, tmp);
 873     }
 874   }
 875
 876   ht->auto_rehash = auto_rehash;
 877
 878   /* Remove old table */
 879   silc_sfree(ht->stack, table);
 880 }
 881
 882 /* Same as above but with specific hash function. */
 883
 884 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 885                                 SilcHashFunction hash,
 886                                 void *hash_user_context)
 887 {
 888   int i;
 889   SilcHashTableEntry *table, e, tmp;
 890   SilcUInt32 table_size, size_index;
 891   SilcBool auto_rehash;
 892
 893   SILC_HT_DEBUG(("Start"));
 894
 895   if (new_size)
 896     silc_hash_table_primesize(new_size, &size_index);
 897   else
 898     silc_hash_table_primesize(ht->entry_count, &size_index);
 899
 900   if (size_index == ht->table_size)
 901     return;
 902
 903   SILC_HT_DEBUG(("Rehashing"));
 904
 905   /* Take old hash table */
 906   table = ht->table;
 907   table_size = ht->table_size;
 908   auto_rehash = ht->auto_rehash;
 909   ht->auto_rehash = FALSE;
 910
 911   /* Allocate new table */
 912   ht->table = silc_scalloc(ht->stack,
 913                            primesize[size_index], sizeof(*ht->table));
 914   if (!ht->table)
 915     return;
 916   ht->table_size = size_index;
 917   ht->entry_count = 0;
 918
 919   /* Rehash */
 920   for (i = 0; i < primesize[table_size]; i++) {
 921     e = table[i];
 922     while (e) {
 923       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 924                               hash_user_context);
 925       tmp = e;
 926       e = e->next;
 927
 928       /* Remove old entry */
 929       silc_sfree(ht->stack, tmp);
 930     }
 931   }
 932
 933   ht->auto_rehash = auto_rehash;
 934
 935   /* Remove old table */
 936   silc_sfree(ht->stack, table);
 937 }
 938
 939 /* Prepares the `htl' list structure sent as argument to be used in the
 940    hash table traversing with the silc_hash_table_get. Usage:
 941    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 942
 943 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 944 {
 945   htl->ht = ht;
 946   htl->entry = NULL;
 947   htl->index = 0;
 948   htl->auto_rehash = ht->auto_rehash;
 949
 950   /* Disallow rehashing of the table while traversing the table */
 951   ht->auto_rehash = FALSE;
 952 }
 953
 954 /* Resets the `htl' SilcHashTableList. */
 955
 956 void silc_hash_table_list_reset(SilcHashTableList *htl)
 957 {
 958   /* Set back the original auto rehash value to the table */
 959   htl->ht->auto_rehash = htl->auto_rehash;
 960 }
 961
 962 /* Returns always the next entry in the hash table into the `key' and
 963    `context' and TRUE.  If this returns FALSE then there are no anymore
 964    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 965
 966 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
 967                              void **context)
 968 {
 969   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 970
 971   if (!htl->ht->entry_count)
 972     return FALSE;
 973
 974   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 975     entry = htl->ht->table[htl->index];
 976     htl->index++;
 977   }
 978
 979   if (!entry)
 980     return FALSE;
 981
 982   htl->entry = entry->next;
 983
 984   if (key)
 985     *key = entry->key;
 986   if (context)
 987     *context = entry->context;
 988
 989   return TRUE;
 990 }
 991
 992 /**************************** Utility functions *****************************/
 993
 994 /* Case sensitive hashing */
 995
 996 SilcUInt32 silc_hash_string(void *key, void *user_context)
 997 {
 998   char *s = (char *)key;
 999   SilcUInt32 h = 0;
1000
1001   while (*s != '\0') {
1002     h += *s++;
1003     h += (h << 10);
1004     h ^= (h >> 6);
1005   }
1006
1007   h += (h << 3);
1008   h ^= (h >> 11);
1009   h += (h << 15);
1010
1011   return h;
1012 }
1013
1014 /* Case-insensitive hashing */
1015
1016 SilcUInt32 silc_hash_string_case(void *key, void *user_context)
1017 {
1018   char *s = (char *)key;
1019   SilcUInt32 h = 0;
1020
1021   while (*s != '\0') {
1022     h += tolower((int)*s);
1023     h += (h << 10);
1024     h ^= (h >> 6);
1025     s++;
1026   }
1027
1028   h += (h << 3);
1029   h ^= (h >> 11);
1030   h += (h << 15);
1031
1032   return h;
1033 }
1034
1035 /* Hash UTF-8 string */
1036
1037 SilcUInt32 silc_hash_utf8_string(void *key, void *user_context)
1038 {
1039   char *s = (char *)key;
1040   SilcUInt32 h = 0;
1041
1042   while (*s != '\0') {
1043     h += *s++;
1044     h += (h << 10);
1045     h ^= (h >> 6);
1046   }
1047
1048   h += (h << 3);
1049   h ^= (h >> 11);
1050   h += (h << 15);
1051
1052   return h;
1053 }
1054
1055 /* Basic hash function to hash integers. */
1056
1057 SilcUInt32 silc_hash_uint(void *key, void *user_context)
1058 {
1059   return SILC_PTR_TO_32(key);
1060 }
1061
1062 /* Basic hash funtion to hash pointers. */
1063
1064 SilcUInt32 silc_hash_ptr(void *key, void *user_context)
1065 {
1066   return SILC_PTR_TO_32(key);
1067 }
1068
1069 /* Hash binary data. The `user_context' is the data length. */
1070
1071 SilcUInt32 silc_hash_data(void *key, void *user_context)
1072 {
1073   SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i;
1074   unsigned char *data = (char *)key;
1075
1076   h = (data[0] * data[len - 1] + 1) * len;
1077
1078   for (i = 0; i < len; i++) {
1079     h += data[i];
1080     h += (h << 10);
1081     h ^= (h >> 6);
1082   }
1083
1084   h += (h << 3);
1085   h ^= (h >> 11);
1086   h += (h << 15);
1087
1088   return h;
1089 }
1090
1091 /* Compares two strings. */
1092
1093 SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context)
1094 {
1095   return !strcmp((char *)key1, (char *)key2);
1096 }
1097
1098 /* Compares two strings, ignores case. */
1099
1100 SilcBool silc_hash_string_case_compare(void *key1, void *key2,
1101                                        void *user_context)
1102 {
1103   return !strcasecmp((char *)key1, (char *)key2);
1104 }
1105
1106 /* Compares binary data. */
1107
1108 SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context)
1109 {
1110   SilcUInt32 len = SILC_PTR_TO_32(user_context);
1111   return !memcmp(key1, key2, len);
1112 }
1113
1114 /* Compares UTF-8 string. */
1115
1116 SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context)
1117 {
1118   int l1 = strlen((char *)key1);
1119   int l2 = strlen((char *)key2);
1120   if (l1 != l2)
1121     return FALSE;
1122   return !memcmp(key1, key2, l2);
1123 }