lib/silcutil/silchashtable.h

   1 /*
   2
   3   silchashtable.h
   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
  20 /****h* silcutil/SILC Hash Table Interface
  21  *
  22  * DESCRIPTION
  23  *
  24  * Implementation of collision resistant hash table. This is a hash table
  25  * that provides a reliable (what you add there stays there, and duplicate
  26  * keys are allowed) with as fast reference to the key as possible. If
  27  * there are a lot of duplicate keys in the hash table the lookup slows down.
  28  * However, this is reliable and no data is lost at any point. If you know
  29  * that you never have duplicate keys then this is as fast as any simple hash
  30  * table.
  31  *
  32  * The interface provides many ways to search the hash table including
  33  * an extended interface where caller can specify its own hash and comparison
  34  * functions.  The interface also supports SilcStack and all memory allocated
  35  * by the hash table can be allocated from SilcStack.
  36  *
  37  * There are two ways to traverse the entire hash table if this feature
  38  * is needed. There exists a foreach function that calls a foreach
  39  * callback for each entry in the hash table. Other way is to use
  40  * SilcHashTableList structure and traverse the hash table inside while()
  41  * using the list structure. Both are equally fast.
  42  *
  43  * The hash table is not thread safe.  If same SilcHashtable context is used
  44  * in multi thread environment concurrency control must be employed.
  45  *
  46  ***/
  47
  48 #ifndef SILCHASHTABLE_H
  49 #define SILCHASHTABLE_H
  50
  51 /****s* silcutil/SilcHashTableAPI/SilcHashTable
  52  *
  53  * NAME
  54  *
  55  *    typedef struct SilcHashTableStruct *SilcHashTable;
  56  *
  57  * DESCRIPTION
  58  *
  59  *    This context is the actual hash table and is allocated
  60  *    by silc_hash_table_alloc and given as argument usually to
  61  *    all silc_hash_table_* functions.  It is freed by the
  62  *    silc_hash_table_free function.
  63  *
  64  ***/
  65 typedef struct SilcHashTableStruct *SilcHashTable;
  66
  67 /****s* silcutil/SilcHashTableAPI/SilcHashTableList
  68  *
  69  * NAME
  70  *
  71  *    typedef struct SilcHashTableListStruct SilcHashTableList;
  72  *
  73  * DESCRIPTION
  74  *
  75  *    This structure is used to tarverse the hash table. This structure
  76  *    is given as argument to the silc_hash_table_list function to
  77  *    initialize it and then used to traverse the hash table with the
  78  *    silc_hash_table_get function. It needs not be allocated or freed.
  79  *
  80  * EXAMPLE
  81  *
  82  *    SilcHashTableList htl;
  83  *    silc_hash_table_list(hash_table, &htl);
  84  *    while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
  85  *      ...
  86  *    silc_hash_table_list_reset(&htl);
  87  *
  88  * SOURCE
  89  */
  90 typedef struct SilcHashTableListStruct SilcHashTableList;
  91
  92 /* List structure to traverse the hash table. */
  93 struct SilcHashTableListStruct {
  94   SilcHashTable ht;
  95   void *entry;
  96   unsigned int index        : 31;
  97   unsigned int auto_rehash  : 1;
  98 };
  99 /***/
 100
 101 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
 102  *
 103  * SYNOPSIS
 104  *
 105  *    typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
 106  *
 107  * DESCRIPTION
 108  *
 109  *    A type for the hash function. This function is used to hash the
 110  *    provided key value `key' and return the index for the hash table.
 111  *    The `user_context' is application specific context and is delivered
 112  *    to the callback.
 113  *
 114  ***/
 115 typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
 116
 117 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
 118  *
 119  * SYNOPSIS
 120  *
 121  *    typedef SilcBool (*SilcHashCompare)(void *key1, void *key2,
 122  *                                        void *user_context);
 123  *
 124  * DESCRIPTION
 125  *
 126  *    A comparison funtion that is called to compare the two keys `key1' and
 127  *    `key2'. If they are equal this must return TRUE or FALSE otherwise.
 128  *    The application provides this function when allocating a new hash table.
 129  *    The `user_context' is application specific context and is delivered
 130  *    to the callback.
 131  *
 132  ***/
 133 typedef SilcBool (*SilcHashCompare)(void *key1, void *key2,
 134                                     void *user_context);
 135
 136 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
 137  *
 138  * SYNOPSIS
 139  *
 140  *    typedef void (*SilcHashDestructor)(void *key, void *context,
 141  *                                       void *user_context);
 142  *
 143  * DESCRIPTION
 144  *
 145  *    A destructor callback that the library will call to destroy the
 146  *    `key' and `context'.  The application provides the function when
 147  *    allocating a new hash table. The `user_context' is application
 148  *    specific context and is delivered to the callback.
 149  *
 150  ***/
 151 typedef void (*SilcHashDestructor)(void *key, void *context,
 152                                    void *user_context);
 153
 154 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
 155  *
 156  * SYNOPSIS
 157  *
 158  *    typedef void (*SilcHashForeach)(void *key, void *context,
 159  *                                    void *user_context);
 160  *
 161  * DESCRIPTION
 162  *
 163  *    Foreach function. This is called when traversing the entrys in the
 164  *    hash table using silc_hash_table_foreach. The `user_context' is
 165  *    application specific context and is delivered to the callback.
 166  *
 167  ***/
 168 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
 169
 170 /* Simple hash table interface */
 171
 172 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
 173  *
 174  * SYNOPSIS
 175  *
 176  *    SilcHashTable silc_hash_table_alloc(SilcStack stack,
 177  *                                        SilcUInt32 table_size,
 178  *                                        SilcHashFunction hash,
 179  *                                        void *hash_user_context,
 180  *                                        SilcHashCompare compare,
 181  *                                        void *compare_user_context,
 182  *                                        SilcHashDestructor destructor,
 183  *                                        void *destructor_user_context,
 184  *                                        SilcBool auto_rehash);
 185  *
 186  * DESCRIPTION
 187  *
 188  *    Allocates new hash table and returns it.  If the `stack' is non-NULL
 189  *    the hash table is allocated from `stack'.  If the `table_size' is not
 190  *    zero then the hash table size is the size provided. If zero then the
 191  *    default size will be used. Note that if the `table_size' is provided
 192  *    it should be a prime. The `hash', `compare' and `destructor' are
 193  *    the hash function, the key comparison function and key and context
 194  *    destructor function, respectively. The `hash' is mandatory, the others
 195  *    are optional.  Returns NULL if system is out of memory.
 196  *
 197  ***/
 198 SilcHashTable silc_hash_table_alloc(SilcStack stack,
 199                                     SilcUInt32 table_size,
 200                                     SilcHashFunction hash,
 201                                     void *hash_user_context,
 202                                     SilcHashCompare compare,
 203                                     void *compare_user_context,
 204                                     SilcHashDestructor destructor,
 205                                     void *destructor_user_context,
 206                                     SilcBool auto_rehash);
 207
 208 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
 209  *
 210  * SYNOPSIS
 211  *
 212  *    void silc_hash_table_free(SilcHashTable ht);
 213  *
 214  * DESCRIPTION
 215  *
 216  *    Frees the hash table. The destructor function provided in the
 217  *    silc_hash_table_alloc will be called for all keys in the hash table.
 218  *
 219  *    If the SilcStack was given to silc_hash_table_alloc this call will
 220  *    release all memory allocated during the life time of the `ht' back
 221  *    to the SilcStack.
 222  *
 223  ***/
 224 void silc_hash_table_free(SilcHashTable ht);
 225
 226 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
 227  *
 228  * SYNOPSIS
 229  *
 230  *    SilcUInt32 silc_hash_table_size(SilcHashTable ht);
 231  *
 232  * DESCRIPTION
 233  *
 234  *    Returns the size of the hash table. This is the true size of the
 235  *    hash table.
 236  *
 237  ***/
 238 SilcUInt32 silc_hash_table_size(SilcHashTable ht);
 239
 240 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
 241  *
 242  * SYNOPSIS
 243  *
 244  *    SilcUInt32 silc_hash_table_count(SilcHashTable ht);
 245  *
 246  * DESCRIPTION
 247  *
 248  *    Returns the number of the entires in the hash table. If there is more
 249  *    entries in the table thatn the size of the hash table calling the
 250  *    silc_hash_table_rehash is recommended.
 251  *
 252  ***/
 253 SilcUInt32 silc_hash_table_count(SilcHashTable ht);
 254
 255 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
 256  *
 257  * SYNOPSIS
 258  *
 259  *    SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context);
 260  *
 261  * DESCRIPTION
 262  *
 263  *    Adds new entry to the hash table. The `key' is hashed using the
 264  *    hash function and the both `key' and `context' will be saved to the
 265  *    hash table. This function quarantees that the entry is always added
 266  *    to the hash table reliably (it is collision resistant).
 267  *
 268  ***/
 269 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context);
 270
 271 /****f* silcutil/SilcHashTableAPI/silc_hash_table_set
 272  *
 273  * SYNOPSIS
 274  *
 275  *    SilcBool silc_hash_table_set(SilcHashTable ht, void *key,
 276  *                                 void *context);
 277  *
 278  * DESCRIPTION
 279  *
 280  *    Same as silc_hash_table_add but if the `key' already exists in the
 281  *    hash table the old key and the old context will be replaced with the
 282  *    `key' and the `context. The destructor function will be called for the
 283  *    replaced key and context.
 284  *
 285  ***/
 286 SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context);
 287
 288 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
 289  *
 290  * SYNOPSIS
 291  *
 292  *    SilcBool silc_hash_table_del(SilcHashTable ht, void *key);
 293  *
 294  * DESCRIPTION
 295  *
 296  *    Removes the entry from the hash table by the provided `key'. This will
 297  *    call the destructor funtion for the found entry. Return TRUE if the
 298  *    entry was removed successfully and FALSE otherwise.
 299  *
 300  ***/
 301 SilcBool silc_hash_table_del(SilcHashTable ht, void *key);
 302
 303 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
 304  *
 305  * SYNOPSIS
 306  *
 307  *    SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 308  *                                            void *context);
 309  *
 310  * DESCRIPTION
 311  *
 312  *    Same as silc_hash_table_del but verifies that the context associated
 313  *    with the `key' matches the `context'. This is handy to use with hash
 314  *    tables that may have duplicate keys. In that case the `context' may
 315  *    be used to check whether the correct entry is being deleted.
 316  *
 317  ***/
 318 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 319                                         void *context);
 320
 321 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
 322  *
 323  * SYNOPSIS
 324  *
 325  *    SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
 326  *                                  void **ret_key, void **ret_context);
 327  *
 328  * DESCRIPTION
 329  *
 330  *    Finds the entry in the hash table by the provided `key' as fast as
 331  *    possible. Return TRUE if the entry was found and FALSE otherwise.
 332  *    The found entry is returned to the `ret_key' and `ret_context',
 333  *    respectively. If the `ret_key and `ret_context' are NULL then this
 334  *    maybe used only to check whether given key exists in the table.
 335  *
 336  ***/
 337 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
 338                               void **ret_key, void **ret_context);
 339
 340 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context
 341  *
 342  * SYNOPSIS
 343  *
 344  *    SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 345  *                                             void *context, void **ret_key);
 346  *
 347  * DESCRIPTION
 348  *
 349  *    Finds the entry in the hash table by the provided `key' and
 350  *    `context' as fast as possible.  This is handy function when there
 351  *    can be multiple same keys in the hash table.  By using this function
 352  *    the specific key with specific context can be found.  Return
 353  *    TRUE if the entry with the key and context was found and FALSE
 354  *    otherwise.  The function returns only the key to `ret_key' since
 355  *    the caller already knows the context.
 356  *
 357  ***/
 358 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 359                                          void *context, void **ret_key);
 360
 361 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
 362  *
 363  * SYNOPSIS
 364  *
 365  *    void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 366  *                                      SilcHashForeach foreach,
 367  *                                      void *user_context);
 368  *
 369  * DESCRIPTION
 370  *
 371  *    As the hash table is collision resistant it is possible to save duplicate
 372  *    keys to the hash table. This function can be used to find all keys
 373  *    and contexts from the hash table that are found using the `key'. The
 374  *    `foreach' is called for every found key. If no entries can be found
 375  *    the `foreach' will be called once with the context set NULL and
 376  *    `key' and `user_context' sent to the function.
 377  *
 378  * NOTES
 379  *
 380  *    The hash table will not be rehashed during the traversing of the table,
 381  *    even if the table was marked as auto rehashable.  The caller also must
 382  *    not call silc_hash_table_rehash while traversing the table.
 383  *
 384  ***/
 385 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 386                                   SilcHashForeach foreach, void *user_context);
 387
 388 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
 389  *
 390  * SYNOPSIS
 391  *
 392  *    void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 393  *                                 void *user_context);
 394  *
 395  * DESCRIPTION
 396  *
 397  *    Traverse all entrys in the hash table and call the `foreach' for
 398  *    every entry with the `user_context' context.
 399  *
 400  * NOTES
 401  *
 402  *    The hash table will not be rehashed during the traversing of the table,
 403  *    even if the table was marked as auto rehashable.  The caller also must
 404  *    not call silc_hash_table_rehash while traversing the table.
 405  *
 406  ***/
 407 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 408                              void *user_context);
 409
 410 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
 411  *
 412  * SYNOPSIS
 413  *
 414  *    void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
 415  *
 416  * DESCRIPTION
 417  *
 418  *    Rehashs the hash table. The size of the new hash table is provided
 419  *    as `new_size'. If the `new_size' is zero then this routine will make
 420  *    the new table of a suitable size. Note that this operation may be
 421  *    very slow.
 422  *
 423  ***/
 424 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
 425
 426 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
 427  *
 428  * SYNOPSIS
 429  *
 430  *    void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
 431  *
 432  * DESCRIPTION
 433  *
 434  *    Prepares the `htl' SilcHashTableList sent as argument to be used in the
 435  *    hash table traversing with the silc_hash_table_get.  After the hash
 436  *    table traversing is completed the silc_hash_table_list_reset must be
 437  *    called.
 438  *
 439  * NOTES
 440  *
 441  *    The hash table will not be rehashed during the traversing of the list,
 442  *    even if the table was marked as auto rehashable.  The caller also must
 443  *    not call silc_hash_table_rehash while traversing the list.
 444  *
 445  ***/
 446 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
 447
 448 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list_reset
 449  *
 450  * SYNOPSIS
 451  *
 452  *    void silc_hash_table_list_reset(SilcHashTableList *htl);
 453  *
 454  * DESCRIPTION
 455  *
 456  *    Resets the `htl' SilcHashTableList.  This must be called after the
 457  *    hash table traversing is completed.
 458  *
 459  ***/
 460 void silc_hash_table_list_reset(SilcHashTableList *htl);
 461
 462 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
 463  *
 464  * SYNOPSIS
 465  *
 466  *    SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
 467  *                                 void **context);
 468  *
 469  * DESCRIPTION
 470  *
 471  *    Returns always the next entry in the hash table into the `key' and
 472  *    `context' and TRUE.  If this returns FALSE then there are no more
 473  *    entries.
 474  *
 475  * EXAMPLE
 476  *
 477  *    SilcHashTableList htl;
 478  *    silc_hash_table_list(hash_table, &htl);
 479  *    while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
 480  *      ...
 481  *    silc_hash_table_list_reset(&htl);
 482  *
 483  ***/
 484 SilcBool silc_hash_table_get(SilcHashTableList *htl,
 485                              void **key, void **context);
 486
 487
 488 /* Extended hash table interface (same as above but with specific
 489    hash and comparison functions). */
 490
 491 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
 492  *
 493  * SYNOPSIS
 494  *
 495  *    SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key,
 496  *                                     void *context,
 497  *                                     SilcHashFunction hash,
 498  *                                     void *hash_user_context);
 499  *
 500  * DESCRIPTION
 501  *
 502  *    Adds new entry to the hash table. The `key' is hashed using the
 503  *    hash function and the both `key' and `context' will be saved to the
 504  *    hash table. This function quarantees that the entry is always added
 505  *    to the hash table reliably (it is collision resistant).
 506  *
 507  *    The `hash' and `hash_user_context' are application specified hash
 508  *    function. If not provided the hash table's default is used.
 509  *
 510  ***/
 511 SilcBool silc_hash_table_add_ext(SilcHashTable ht,
 512                                  void *key, void *context,
 513                                  SilcHashFunction hash,
 514                                  void *hash_user_context);
 515
 516 /****f* silcutil/SilcHashTableAPI/silc_hash_table_set_ext
 517  *
 518  * SYNOPSIS
 519  *
 520  *    SilcBool silc_hash_table_set_ext(SilcHashTable ht, void *key,
 521  *                                     void *context,
 522  *                                     SilcHashFunction hash,
 523  *                                     void *hash_user_context);
 524  *
 525  * DESCRIPTION
 526  *
 527  *    Same as silc_hash_table_add_ext but if the `key' already exists in the
 528  *    hash table the old key and the old context will be replaced with the
 529  *    `key' and the `context. The destructor function will be called for the
 530  *    replaced key and context.
 531  *
 532  *    The `hash' and `hash_user_context' are application specified hash
 533  *    function. If not provided the hash table's default is used.
 534  *
 535  ***/
 536 SilcBool silc_hash_table_set_ext(SilcHashTable ht,
 537                                  void *key, void *context,
 538                                  SilcHashFunction hash,
 539                                  void *hash_user_context);
 540
 541 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
 542  *
 543  * SYNOPSIS
 544  *
 545  *    SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 546  *                                     SilcHashFunction hash,
 547  *                                     void *hash_user_context,
 548  *                                     SilcHashCompare compare,
 549  *                                     void *compare_user_context,
 550  *                                     SilcHashDestructor destructor,
 551  *                                     void *destructor_user_context);
 552  *
 553  * DESCRIPTION
 554  *
 555  *    Removes the entry from the hash table by the provided `key'. This will
 556  *    call the destructor funtion for the found entry. Return TRUE if the
 557  *    entry was removed successfully and FALSE otherwise.
 558  *
 559  *    The `hash' and `hash_user_context' are application specified hash
 560  *    function. If not provided the hash table's default is used.
 561  *    The `compare' and `compare_user_context' are application specified
 562  *    comparing function. If not provided the hash table's default is used.
 563  *    The `destructor' and `destructor_user_context' are application
 564  *    specific destructor function.
 565  *
 566  ***/
 567 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 568                                  SilcHashFunction hash,
 569                                  void *hash_user_context,
 570                                  SilcHashCompare compare,
 571                                  void *compare_user_context,
 572                                  SilcHashDestructor destructor,
 573                                  void *destructor_user_context);
 574
 575 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
 576  *
 577  * SYNOPSIS
 578  *
 579  *    SilcBool
 580  *    silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 581  *                                       void *context,
 582  *                                       SilcHashFunction hash,
 583  *                                       void *hash_user_context,
 584  *                                       SilcHashCompare compare,
 585  *                                       void *compare_user_context,
 586  *                                       SilcHashDestructor destructor,
 587  *                                       void *destructor_user_context);
 588  *
 589  * DESCRIPTION
 590  *
 591  *    Same as silc_hash_table_del but verifies that the context associated
 592  *    with the `key' matches the `context'. This is handy to use with hash
 593  *    tables that may have duplicate keys. In that case the `context' may
 594  *    be used to check whether the correct entry is being deleted.
 595  *
 596  *    The `hash' and `hash_user_context' are application specified hash
 597  *    function. If not provided the hash table's default is used.
 598  *    The `compare' and `compare_user_context' are application specified
 599  *    comparing function. If not provided the hash table's default is used.
 600  *    The `destructor' and `destructor_user_context' are application
 601  *    specific destructor function.
 602  *
 603  ***/
 604 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 605                                             void *context,
 606                                             SilcHashFunction hash,
 607                                             void *hash_user_context,
 608                                             SilcHashCompare compare,
 609                                             void *compare_user_context,
 610                                             SilcHashDestructor destructor,
 611                                             void *destructor_user_context);
 612
 613 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
 614  *
 615  * SYNOPSIS
 616  *
 617  *    SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 618  *                                      void **ret_key, void **ret_context,
 619  *                                      SilcHashFunction hash,
 620  *                                      void *hash_user_context,
 621  *                                      SilcHashCompare compare,
 622  *                                      void *compare_user_context);
 623  *
 624  * DESCRIPTION
 625  *
 626  *    Finds the entry in the hash table by the provided `key' as fast as
 627  *    possible. Return TRUE if the entry was found and FALSE otherwise.
 628  *    The found entry is returned to the `ret_key' and `ret_context',
 629  *    respectively. If the `ret_key and `ret_context' are NULL then this
 630  *    maybe used only to check whether given key exists in the table.
 631  *
 632  *    The `hash' and `hash_user_context' are application specified hash
 633  *    function. If not provided the hash table's default is used.
 634  *    The `compare' and `compare_user_context' are application specified
 635  *    comparing function. If not provided the hash table's default is used.
 636  *
 637  ***/
 638 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 639                                   void **ret_key, void **ret_context,
 640                                   SilcHashFunction hash,
 641                                   void *hash_user_context,
 642                                   SilcHashCompare compare,
 643                                   void *compare_user_context);
 644
 645 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context_ext
 646  *
 647  * SYNOPSIS
 648  *
 649  *    SilcBool
 650  *    silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
 651  *                                        void *context, void **ret_key,
 652  *                                        SilcHashFunction hash,
 653  *                                        void *hash_user_context,
 654  *                                        SilcHashCompare compare,
 655  *                                        void *compare_user_context);
 656  *
 657  * DESCRIPTION
 658  *
 659  *    Finds the entry in the hash table by the provided `key' and
 660  *    `context' as fast as possible.  This is handy function when there
 661  *    can be multiple same keys in the hash table.  By using this function
 662  *    the specific key with specific context can be found.  Return
 663  *    TRUE if the entry with the key and context was found and FALSE
 664  *    otherwise.  The function returns only the key to `ret_key' since
 665  *    the caller already knows the context.
 666  *
 667  *    The `hash' and `hash_user_context' are application specified hash
 668  *    function. If not provided the hash table's default is used.
 669  *    The `compare' and `compare_user_context' are application specified
 670  *    comparing function. If not provided the hash table's default is used.
 671  *
 672  ***/
 673 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
 674                                              void *context, void **ret_key,
 675                                              SilcHashFunction hash,
 676                                              void *hash_user_context,
 677                                              SilcHashCompare compare,
 678                                              void *compare_user_context);
 679
 680 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
 681  *
 682  * SYNOPSIS
 683  *
 684  *    void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 685  *                                          SilcHashFunction hash,
 686  *                                          void *hash_user_context,
 687  *                                          SilcHashCompare compare,
 688  *                                          void *compare_user_context,
 689  *                                          SilcHashForeach foreach,
 690  *                                          void *foreach_user_context);
 691  *
 692  * DESCRIPTION
 693  *
 694  *    As the hash table is collision resistant it is possible to save duplicate
 695  *    keys to the hash table. This function can be used to find all keys
 696  *    and contexts from the hash table that are found using the `key'. The
 697  *    `foreach' is called for every found key. If no entries can be found
 698  *    the `foreach' will be called once with the context set NULL and
 699  *    `key' and `user_context' sent to the function.
 700  *
 701  *    The `hash' and `hash_user_context' are application specified hash
 702  *    function. If not provided the hash table's default is used.
 703  *    The `compare' and `compare_user_context' are application specified
 704  *    comparing function. If not provided the hash table's default is used.
 705  *
 706  * NOTES
 707  *
 708  *    The hash table will not be rehashed during the traversing of the table,
 709  *    even if the table was marked as auto rehashable.  The caller also must
 710  *    not call silc_hash_table_rehash while traversing the table.
 711  *
 712  ***/
 713 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 714                                       SilcHashFunction hash,
 715                                       void *hash_user_context,
 716                                       SilcHashCompare compare,
 717                                       void *compare_user_context,
 718                                       SilcHashForeach foreach,
 719                                       void *foreach_user_context);
 720
 721 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
 722  *
 723  * SYNOPSIS
 724  *
 725  *    void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 726  *                                    SilcHashFunction hash,
 727  *                                    void *hash_user_context);
 728  *
 729  * DESCRIPTION
 730  *
 731  *    Rehashs the hash table. The size of the new hash table is provided
 732  *    as `new_size'. If the `new_size' is zero then this routine will make
 733  *    the new table of a suitable size. Note that this operation may be
 734  *    very slow.
 735  *
 736  *    The `hash' and `hash_user_context' are application specified hash
 737  *    function. If not provided the hash table's default is used.
 738  *
 739  ***/
 740 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 741                                 SilcHashFunction hash,
 742                                 void *hash_user_context);
 743
 744 /* Hash functions */
 745
 746 /****f* silcutil/SilcHashTableAPI/silc_hash_string
 747  *
 748  * SYNOPSIS
 749  *
 750  *    SilcUInt32 silc_hash_string(void *key, void *user_context);
 751  *
 752  * DESCRIPTION
 753  *
 754  *    Basic hash function to hash strings. May be used with the SilcHashTable.
 755  *    This uses Bob Jenkin's one-at-a-time (described in Wikipedia) hash
 756  *    function.
 757  *
 758  ***/
 759 SilcUInt32 silc_hash_string(void *key, void *user_context);
 760
 761 /****f* silcutil/SilcHashTableAPI/silc_hash_string_case
 762  *
 763  * SYNOPSIS
 764  *
 765  *    SilcUInt32 silc_hash_string_case(void *key, void *user_context);
 766  *
 767  * DESCRIPTION
 768  *
 769  *    Basic hash function to hash strings. May be used with the SilcHashTable.
 770  *    This ignores the string's case, ie. 'Foo' and 'foo' will hash to same
 771  *    value.  This uses Bob Jenkin's one-at-a-time (described in Wikipedia)
 772  *    hash function.
 773  *
 774  ***/
 775 SilcUInt32 silc_hash_string_case(void *key, void *user_context);
 776
 777 /****f* silcutil/SilcHashTableAPI/silc_hash_utf8_string
 778  *
 779  * SYNOPSIS
 780  *
 781  *    SilcUInt32 silc_hash_utf8_string(void *key, void *user_context);
 782  *
 783  * DESCRIPTION
 784  *
 785  *    Basic has function to hash UTF-8 strings. May be used with the
 786  *    SilcHashTable.  Used with identifier strings.  The key is
 787  *    expected to be casefolded.
 788  *
 789  ***/
 790 SilcUInt32 silc_hash_utf8_string(void *key, void *user_context);
 791
 792 /****f* silcutil/SilcHashTableAPI/silc_hash_uint
 793  *
 794  * SYNOPSIS
 795  *
 796  *    SilcUInt32 silc_hash_uint(void *key, void *user_context);
 797  *
 798  * DESCRIPTION
 799  *
 800  *    Basic hash function to hash integers. May be used with the SilcHashTable.
 801  *    Comparison function is not needed, the SilcHashTable will automatically
 802  *    compare integer values.
 803  *
 804  ***/
 805 SilcUInt32 silc_hash_uint(void *key, void *user_context);
 806
 807 /****f* silcutil/SilcHashTableAPI/silc_hash_ptr
 808  *
 809  * SYNOPSIS
 810  *
 811  *    SilcUInt32 silc_hash_ptr(void *key, void *user_context);
 812  *
 813  * DESCRIPTION
 814  *
 815  *    Basic hash funtion to hash pointers. May be used with the SilcHashTable.
 816  *    Comparison function is not needed, the SilcHashTable will automatically
 817  *    compare pointer values.
 818  *
 819  ***/
 820 SilcUInt32 silc_hash_ptr(void *key, void *user_context);
 821
 822 /****f* silcutil/SilcHashTableAPI/silc_hash_data
 823  *
 824  * SYNOPSIS
 825  *
 826  *    SilcUInt32 silc_hash_data(void *key, void *user_context);
 827  *
 828  * DESCRIPTION
 829  *
 830  *    Hash binary data. The `user_context' is the data length.  This uses Bob
 831  *    Jenkin's one-at-a-time (described in Wikipedia) hash function.
 832  *
 833  ***/
 834 SilcUInt32 silc_hash_data(void *key, void *user_context);
 835
 836 /* Comparison functions */
 837
 838 /****f* silcutil/SilcHashTableAPI/silc_hash_string_compare
 839  *
 840  * SYNOPSIS
 841  *
 842  *    SilcBool silc_hash_string_compare(void *key1, void *key2,
 843  *                                      void *user_context);
 844  *
 845  * DESCRIPTION
 846  *
 847  *    Compares two strings. It may be used as SilcHashTable comparison
 848  *    function.
 849  *
 850  ***/
 851 SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context);
 852
 853 /****f* silcutil/SilcHashTableAPI/silc_hash_string_case_compare
 854  *
 855  * SYNOPSIS
 856  *
 857  *    SilcBool silc_hash_string_case_compare(void *key1, void *key2,
 858  *                                           void *user_context);
 859  *
 860  * DESCRIPTION
 861  *
 862  *    Compares two strings. This ignores the case while comparing.  It may
 863  *    be used as SilcHashTable comparison function.
 864  *
 865  ***/
 866 SilcBool silc_hash_string_case_compare(void *key1, void *key2,
 867                                        void *user_context);
 868
 869 /****f* silcutil/SilcHashTableAPI/silc_hash_utf8_compare
 870  *
 871  * SYNOPSIS
 872  *
 873  *    SilcBool silc_hash_utf8_compare(void *key1, void *key2,
 874  *                                    void *user_context);
 875  *
 876  * DESCRIPTION
 877  *
 878  *    Compares UTF-8 strings.  Casefolded and NULL terminated strings are
 879  *    expected.  May be used as SilcHashTable comparison function.
 880  *
 881  ***/
 882 SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context);
 883
 884 /****f* silcutil/SilcHashTableAPI/silc_hash_data_compare
 885  *
 886  * SYNOPSIS
 887  *
 888  *    SilcBool silc_hash_data_compare(void *key1, void *key2,
 889  *                                    void *user_context);
 890  *
 891  * DESCRIPTION
 892  *
 893  *    Compares binary data. May be used as SilcHashTable comparison function.
 894  *
 895  ***/
 896 SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context);
 897
 898 #endif