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