lib/silcutil/silchashtable.h

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