lib/silcutil/silchashtable.h

   1 /*
   2
   3   silchashtable.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2001 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; either version 2 of the License, or
  12   (at your option) any later version.
  13
  14   This program is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19 */
  20
  21 /****h* silcutil/SilcHashTableAPI
  22  *
  23  * DESCRIPTION
  24  *
  25  * Implementation of collision resistant hash table. This is a hash table
  26  * that provides a reliable (what you add there stays there, and duplicate
  27  * keys are allowed) with as fast reference to the key as possible. If
  28  * there are a lot of duplicate keys in the hash table the lookup gets
  29  * slower of course. However, this is reliable and no data is lost at any
  30  * point. If you know that you never have duplicate keys then this is as
  31  * fast as any simple hash table.
  32  *
  33  * The interface provides many ways to search the hash table including
  34  * an extended interface where caller can specify its own hash and comparison
  35  * functions.
  36  *
  37  * There are two ways tro 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  ***/
  44
  45 #ifndef SILCHASHTABLE_H
  46 #define SILCHASHTABLE_H
  47
  48 /****s* silcutil/SilcHashTableAPI/SilcHashTable
  49  *
  50  * NAME
  51  *
  52  *    typedef struct SilcHashTableStruct *SilcHashTable;
  53  *
  54  * DESCRIPTION
  55  *
  56  *    This context is the actual hash table and is allocated
  57  *    by silc_hash_table_alloc and given as argument usually to
  58  *    all silc_hash_table_* functions.  It is freed by the
  59  *    silc_hash_table_free function.
  60  *
  61  ***/
  62 typedef struct SilcHashTableStruct *SilcHashTable;
  63
  64 /****s* silcutil/SilcHashTableAPI/SilcHashTableList
  65  *
  66  * NAME
  67  *
  68  *    typedef struct SilcHashTableListStruct SilcHashTableList;
  69  *
  70  * DESCRIPTION
  71  *
  72  *    This structure is used to tarverse the hash table. This structure
  73  *    is given as argument to the silc_hash_table_list function to
  74  *    initialize it and then used to traverse the hash table with the
  75  *    silc_hash_table_get function. It needs not be allocated or freed.
  76  *
  77  * EXAMPLE
  78  *
  79  *    SilcHashTableList htl;
  80  *    silc_hash_table_list(hash_table, &htl);
  81  *    while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
  82  *      ...
  83  *
  84  * SOURCE
  85  */
  86 typedef struct SilcHashTableListStruct SilcHashTableList;
  87
  88 /* List structure to traverse the hash table. */
  89 struct SilcHashTableListStruct {
  90   SilcHashTable ht;
  91   void *entry;
  92   uint32 index;
  93 };
  94 /***/
  95
  96 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
  97  *
  98  * SYNOPSIS
  99  *
 100  *    typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
 101  *
 102  * DESCRIPTION
 103  *
 104  *    A type for the hash function. This function is used to hash the
 105  *    provided key value `key' and return the index for the hash table.
 106  *    The `user_context' is application specific context and is delivered
 107  *    to the callback.
 108  *
 109  ***/
 110 typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
 111
 112 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
 113  *
 114  * SYNOPSIS
 115  *
 116  *    typedef bool (*SilcHashCompare)(void *key1, void *key2,
 117  *                                    void *user_context);
 118  *
 119  * DESCRIPTION
 120  *
 121  *    A comparison funtion that is called to compare the two keys `key1' and
 122  *    `key2'. If they are equal this must return TRUE or FALSE otherwise.
 123  *    The application provides this function when allocating a new hash table.
 124  *    The `user_context' is application specific context and is delivered
 125  *    to the callback.
 126  *
 127  ***/
 128 typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context);
 129
 130 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
 131  *
 132  * SYNOPSIS
 133  *
 134  *    typedef void (*SilcHashDestructor)(void *key, void *context,
 135  *                                       void *user_context);
 136  *
 137  * DESCRIPTION
 138  *
 139  *    A destructor callback that the library will call to destroy the
 140  *    `key' and `context'.  The appliation provides the function when
 141  *    allocating a new hash table. The `user_context' is application
 142  *    specific context and is delivered to the callback.
 143  *
 144  ***/
 145 typedef void (*SilcHashDestructor)(void *key, void *context,
 146                                    void *user_context);
 147
 148 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
 149  *
 150  * SYNOPSIS
 151  *
 152  *    typedef void (*SilcHashForeach)(void *key, void *context,
 153  *                                    void *user_context);
 154  *
 155  * DESCRIPTION
 156  *
 157  *    Foreach function. This is called when traversing the entrys in the
 158  *    hash table using silc_hash_table_foreach. The `user_context' is
 159  *    application specific context and is delivered to the callback.
 160  *
 161  ***/
 162 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
 163
 164 /* Simple hash table interface */
 165
 166 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
 167  *
 168  * SYNOPSIS
 169  *
 170  *    SilcHashTable silc_hash_table_alloc(uint32 table_size,
 171  *                                        SilcHashFunction hash,
 172  *                                        void *hash_user_context,
 173  *                                        SilcHashCompare compare,
 174  *                                        void *compare_user_context,
 175  *                                        SilcHashDestructor destructor,
 176  *                                        void *destructor_user_context,
 177  *                                        bool auto_rehash);
 178  *
 179  * DESCRIPTION
 180  *
 181  *    Allocates new hash table and returns it.  If the `table_size' is not
 182  *    zero then the hash table size is the size provided. If zero then the
 183  *    default size will be used. Note that if the `table_size' is provided
 184  *    it should be a prime. The `hash', `compare' and `destructor' are
 185  *    the hash function, the key comparison function and key and context
 186  *    destructor function, respectively. The `hash' is mandatory, the others
 187  *    are optional.
 188  *
 189  ***/
 190 SilcHashTable silc_hash_table_alloc(uint32 table_size,
 191                                     SilcHashFunction hash,
 192                                     void *hash_user_context,
 193                                     SilcHashCompare compare,
 194                                     void *compare_user_context,
 195                                     SilcHashDestructor destructor,
 196                                     void *destructor_user_context,
 197                                     bool auto_rehash);
 198
 199 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
 200  *
 201  * SYNOPSIS
 202  *
 203  *    void silc_hash_table_free(SilcHashTable ht);
 204  *
 205  * DESCRIPTION
 206  *
 207  *    Frees the hash table. The destructor function provided in the
 208  *    silc_hash_table_alloc will be called for all keys in the hash table.
 209  *
 210  ***/
 211 void silc_hash_table_free(SilcHashTable ht);
 212
 213 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
 214  *
 215  * SYNOPSIS
 216  *
 217  *    uint32 silc_hash_table_size(SilcHashTable ht);
 218  *
 219  * DESCRIPTION
 220  *
 221  *    Returns the size of the hash table. This is the true size of the
 222  *    hash table.
 223  *
 224  ***/
 225 uint32 silc_hash_table_size(SilcHashTable ht);
 226
 227 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
 228  *
 229  * SYNOPSIS
 230  *
 231  *    uint32 silc_hash_table_count(SilcHashTable ht);
 232  *
 233  * DESCRIPTION
 234  *
 235  *    Returns the number of the entires in the hash table. If there is more
 236  *    entries in the table thatn the size of the hash table calling the
 237  *    silc_hash_table_rehash is recommended.
 238  *
 239  ***/
 240 uint32 silc_hash_table_count(SilcHashTable ht);
 241
 242 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
 243  *
 244  * SYNOPSIS
 245  *
 246  *    void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
 247  *
 248  * DESCRIPTION
 249  *
 250  *    Adds new entry to the hash table. The `key' is hashed using the
 251  *    hash function and the both `key' and `context' will be saved to the
 252  *    hash table. This function quarantees that the entry is always added
 253  *    to the hash table reliably (it is collision resistant).
 254  *
 255  ***/
 256 void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
 257
 258 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace
 259  *
 260  * SYNOPSIS
 261  *
 262  *    void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
 263  *
 264  * DESCRIPTION
 265  *
 266  *    Same as silc_hash_table_add but if the `key' already exists in the
 267  *    hash table the old key and the old context will be replaced with the
 268  *    `key' and the `context. The destructor function will be called for the
 269  *    replaced key and context.
 270  *
 271  ***/
 272 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
 273
 274 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
 275  *
 276  * SYNOPSIS
 277  *
 278  *    bool silc_hash_table_del(SilcHashTable ht, void *key);
 279  *
 280  * DESCRIPTION
 281  *
 282  *    Removes the entry from the hash table by the provided `key'. This will
 283  *    call the destructor funtion for the found entry. Return TRUE if the
 284  *    entry was removed successfully and FALSE otherwise.
 285  *
 286  ***/
 287 bool silc_hash_table_del(SilcHashTable ht, void *key);
 288
 289 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
 290  *
 291  * SYNOPSIS
 292  *
 293  *    bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 294  *                                        void *context);
 295  *
 296  * DESCRIPTION
 297  *
 298  *    Same as silc_hash_table_del but verifies that the context associated
 299  *    with the `key' matches the `context'. This is handy to use with hash
 300  *    tables that may have duplicate keys. In that case the `context' may
 301  *    be used to check whether the correct entry is being deleted.
 302  *
 303  ***/
 304 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 305                                     void *context);
 306
 307 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
 308  *
 309  * SYNOPSIS
 310  *
 311  *    bool silc_hash_table_find(SilcHashTable ht, void *key,
 312  *                              void **ret_key, void **ret_context);
 313  *
 314  * DESCRIPTION
 315  *
 316  *    Finds the entry in the hash table by the provided `key' as fast as
 317  *    possible. Return TRUE if the entry was found and FALSE otherwise.
 318  *    The found entry is returned to the `ret_key' and `ret_context',
 319  *    respectively. If the `ret_key and `ret_context' are NULL then this
 320  *    maybe used only to check whether given key exists in the table.
 321  *
 322  ***/
 323 bool silc_hash_table_find(SilcHashTable ht, void *key,
 324                           void **ret_key, void **ret_context);
 325
 326 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
 327  *
 328  * SYNOPSIS
 329  *
 330  *    void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 331  *                                      SilcHashForeach foreach,
 332  *                                      void *user_context);
 333  *
 334  * DESCRIPTION
 335  *
 336  *    As the hash table is collision resistant it is possible to save duplicate
 337  *    keys to the hash table. This function can be used to find all keys
 338  *    and contexts from the hash table that are found using the `key'. The
 339  *    `foreach' is called for every found key.
 340  *
 341  ***/
 342 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 343                                   SilcHashForeach foreach, void *user_context);
 344
 345 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
 346  *
 347  * SYNOPSIS
 348  *
 349  *    void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 350  *                                 void *user_context);
 351  *
 352  * DESCRIPTION
 353  *
 354  *    Traverse all entrys in the hash table and call the `foreach' for
 355  *    every entry with the `user_context' context.
 356  *
 357  ***/
 358 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 359                              void *user_context);
 360
 361 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
 362  *
 363  * SYNOPSIS
 364  *
 365  *    void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
 366  *
 367  * DESCRIPTION
 368  *
 369  *    Rehashs the hash table. The size of the new hash table is provided
 370  *    as `new_size'. If the `new_size' is zero then this routine will make
 371  *    the new table of a suitable size. Note that this operation may be
 372  *    very slow.
 373  *
 374  ***/
 375 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
 376
 377 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
 378  *
 379  * SYNOPSIS
 380  *
 381  *    void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
 382  *
 383  * DESCRIPTION
 384  *
 385  *    Prepares the `htl' SilcHashTableList sent as argument to be used in the
 386  *    hash table traversing with the silc_hash_table_get.
 387  *
 388  ***/
 389 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
 390
 391 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
 392  *
 393  * SYNOPSIS
 394  *
 395  *    bool silc_hash_table_get(SilcHashTableList *htl, void **key,
 396  *                             void **context);
 397  *
 398  * DESCRIPTION
 399  *
 400  *    Returns always the next entry in the hash table into the `key' and
 401  *    `context' and TRUE.  If this returns FALSE then there are no anymore
 402  *    any entrys.
 403  *
 404  ***/
 405 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context);
 406
 407
 408 /* Extended hash table interface (same as above but with specific
 409    hash and comparison functions). */
 410
 411 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
 412  *
 413  * SYNOPSIS
 414  *
 415  *    void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 416  *                                 SilcHashFunction hash,
 417  *                                 void *hash_user_context);
 418  *
 419  * DESCRIPTION
 420  *
 421  *    Adds new entry to the hash table. The `key' is hashed using the
 422  *    hash function and the both `key' and `context' will be saved to the
 423  *    hash table. This function quarantees that the entry is always added
 424  *    to the hash table reliably (it is collision resistant).
 425  *
 426  *    The `hash' and `hash_user_context' are application specified hash
 427  *    function. If not provided the hash table's default is used.
 428  *
 429  ***/
 430 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 431                              SilcHashFunction hash, void *hash_user_context);
 432
 433 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
 434  *
 435  * SYNOPSIS
 436  *
 437  *    void silc_hash_table_replace_ext(SilcHashTable ht, void *key,
 438  *                                     void *context,
 439  *                                     SilcHashFunction hash,
 440  *                                     void *hash_user_context);
 441  *
 442  * DESCRIPTION
 443  *
 444  *    Same as silc_hash_table_add_ext but if the `key' already exists in the
 445  *    hash table the old key and the old context will be replaced with the
 446  *    `key' and the `context. The destructor function will be called for the
 447  *    replaced key and context.
 448  *
 449  *    The `hash' and `hash_user_context' are application specified hash
 450  *    function. If not provided the hash table's default is used.
 451  *
 452  ***/
 453 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
 454                                  SilcHashFunction hash,
 455                                  void *hash_user_context);
 456
 457 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
 458  *
 459  * SYNOPSIS
 460  *
 461  *    bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 462  *                                 SilcHashFunction hash,
 463  *                                 void *hash_user_context,
 464  *                                 SilcHashCompare compare,
 465  *                                 void *compare_user_context,
 466  *                                 SilcHashDestructor destructor,
 467  *                                 void *destructor_user_context);
 468  *
 469  * DESCRIPTION
 470  *
 471  *    Removes the entry from the hash table by the provided `key'. This will
 472  *    call the destructor funtion for the found entry. Return TRUE if the
 473  *    entry was removed successfully and FALSE otherwise.
 474  *
 475  *    The `hash' and `hash_user_context' are application specified hash
 476  *    function. If not provided the hash table's default is used.
 477  *    The `compare' and `compare_user_context' are application specified
 478  *    comparing function. If not provided the hash table's default is used.
 479  *    The `destructor' and `destructor_user_context' are application
 480  *    specific destructor function.
 481  *
 482  ***/
 483 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 484                              SilcHashFunction hash,
 485                              void *hash_user_context,
 486                              SilcHashCompare compare,
 487                              void *compare_user_context,
 488                              SilcHashDestructor destructor,
 489                              void *destructor_user_context);
 490
 491 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
 492  *
 493  * SYNOPSIS
 494  *
 495  *    bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 496  *                                            void *context,
 497  *                                            SilcHashFunction hash,
 498  *                                            void *hash_user_context,
 499  *                                            SilcHashCompare compare,
 500  *                                            void *compare_user_context,
 501  *                                            SilcHashDestructor destructor,
 502  *                                            void *destructor_user_context);
 503  *
 504  * DESCRIPTION
 505  *
 506  *    Same as silc_hash_table_del but verifies that the context associated
 507  *    with the `key' matches the `context'. This is handy to use with hash
 508  *    tables that may have duplicate keys. In that case the `context' may
 509  *    be used to check whether the correct entry is being deleted.
 510  *
 511  *    The `hash' and `hash_user_context' are application specified hash
 512  *    function. If not provided the hash table's default is used.
 513  *    The `compare' and `compare_user_context' are application specified
 514  *    comparing function. If not provided the hash table's default is used.
 515  *    The `destructor' and `destructor_user_context' are application
 516  *    specific destructor function.
 517  *
 518  ***/
 519 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 520                                         void *context,
 521                                         SilcHashFunction hash,
 522                                         void *hash_user_context,
 523                                         SilcHashCompare compare,
 524                                         void *compare_user_context,
 525                                         SilcHashDestructor destructor,
 526                                         void *destructor_user_context);
 527
 528 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
 529  *
 530  * SYNOPSIS
 531  *
 532  *    bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 533  *                                  void **ret_key, void **ret_context,
 534  *                                  SilcHashFunction hash,
 535  *                                  void *hash_user_context,
 536  *                                  SilcHashCompare compare,
 537  *                                  void *compare_user_context);
 538  *
 539  * DESCRIPTION
 540  *
 541  *    Finds the entry in the hash table by the provided `key' as fast as
 542  *    possible. Return TRUE if the entry was found and FALSE otherwise.
 543  *    The found entry is returned to the `ret_key' and `ret_context',
 544  *    respectively. If the `ret_key and `ret_context' are NULL then this
 545  *    maybe used only to check whether given key exists in the table.
 546  *
 547  *    The `hash' and `hash_user_context' are application specified hash
 548  *    function. If not provided the hash table's default is used.
 549  *    The `compare' and `compare_user_context' are application specified
 550  *    comparing function. If not provided the hash table's default is used.
 551  *
 552  ***/
 553 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 554                               void **ret_key, void **ret_context,
 555                               SilcHashFunction hash,
 556                               void *hash_user_context,
 557                               SilcHashCompare compare,
 558                               void *compare_user_context);
 559
 560 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
 561  *
 562  * SYNOPSIS
 563  *
 564  *    void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 565  *                                          SilcHashFunction hash,
 566  *                                          void *hash_user_context,
 567  *                                          SilcHashCompare compare,
 568  *                                          void *compare_user_context,
 569  *                                          SilcHashForeach foreach,
 570  *                                          void *foreach_user_context);
 571  *
 572  * DESCRIPTION
 573  *
 574  *    As the hash table is collision resistant it is possible to save duplicate
 575  *    keys to the hash table. This function can be used to find all keys
 576  *    and contexts from the hash table that are found using the `key'. The
 577  *    `foreach' is called for every found key.
 578  *
 579  *    The `hash' and `hash_user_context' are application specified hash
 580  *    function. If not provided the hash table's default is used.
 581  *    The `compare' and `compare_user_context' are application specified
 582  *    comparing function. If not provided the hash table's default is used.
 583  *
 584  ***/
 585 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 586                                       SilcHashFunction hash,
 587                                       void *hash_user_context,
 588                                       SilcHashCompare compare,
 589                                       void *compare_user_context,
 590                                       SilcHashForeach foreach,
 591                                       void *foreach_user_context);
 592
 593 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
 594  *
 595  * SYNOPSIS
 596  *
 597  *    void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
 598  *                                    SilcHashFunction hash,
 599  *                                    void *hash_user_context);
 600  *
 601  * DESCRIPTION
 602  *
 603  *    Rehashs the hash table. The size of the new hash table is provided
 604  *    as `new_size'. If the `new_size' is zero then this routine will make
 605  *    the new table of a suitable size. Note that this operation may be
 606  *    very slow.
 607  *
 608  *    The `hash' and `hash_user_context' are application specified hash
 609  *    function. If not provided the hash table's default is used.
 610  *
 611  ***/
 612 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
 613                                 SilcHashFunction hash,
 614                                 void *hash_user_context);
 615
 616 #endif