5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2005 Pekka Riikonen
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.
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.
20 /****h* silcutil/SILC Hash Table Interface
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 gets
28 * slower of course. However, this is reliable and no data is lost at any
29 * point. If you know that you never have duplicate keys then this is as
30 * fast as any simple hash table.
32 * The interface provides many ways to search the hash table including
33 * an extended interface where caller can specify its own hash and comparison
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.
42 * The hash table is not thread safe. If same hash table context is used in
43 * multi thread environment concurrency control must be employed.
47 #ifndef SILCHASHTABLE_H
48 #define SILCHASHTABLE_H
50 /****s* silcutil/SilcHashTableAPI/SilcHashTable
54 * typedef struct SilcHashTableStruct *SilcHashTable;
58 * This context is the actual hash table and is allocated
59 * by silc_hash_table_alloc and given as argument usually to
60 * all silc_hash_table_* functions. It is freed by the
61 * silc_hash_table_free function.
64 typedef struct SilcHashTableStruct *SilcHashTable;
66 /****s* silcutil/SilcHashTableAPI/SilcHashTableList
70 * typedef struct SilcHashTableListStruct SilcHashTableList;
74 * This structure is used to tarverse the hash table. This structure
75 * is given as argument to the silc_hash_table_list function to
76 * initialize it and then used to traverse the hash table with the
77 * silc_hash_table_get function. It needs not be allocated or freed.
81 * SilcHashTableList htl;
82 * silc_hash_table_list(hash_table, &htl);
83 * while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
85 * silc_hash_table_list_reset(&htl);
89 typedef struct SilcHashTableListStruct SilcHashTableList;
91 /* List structure to traverse the hash table. */
92 struct SilcHashTableListStruct {
95 unsigned int index : 31;
96 unsigned int auto_rehash : 1;
100 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
104 * typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
108 * A type for the hash function. This function is used to hash the
109 * provided key value `key' and return the index for the hash table.
110 * The `user_context' is application specific context and is delivered
114 typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
116 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
120 * typedef SilcBool (*SilcHashCompare)(void *key1, void *key2,
121 * void *user_context);
125 * A comparison funtion that is called to compare the two keys `key1' and
126 * `key2'. If they are equal this must return TRUE or FALSE otherwise.
127 * The application provides this function when allocating a new hash table.
128 * The `user_context' is application specific context and is delivered
132 typedef SilcBool (*SilcHashCompare)(void *key1, void *key2,
135 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
139 * typedef void (*SilcHashDestructor)(void *key, void *context,
140 * void *user_context);
144 * A destructor callback that the library will call to destroy the
145 * `key' and `context'. The application provides the function when
146 * allocating a new hash table. The `user_context' is application
147 * specific context and is delivered to the callback.
150 typedef void (*SilcHashDestructor)(void *key, void *context,
153 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
157 * typedef void (*SilcHashForeach)(void *key, void *context,
158 * void *user_context);
162 * Foreach function. This is called when traversing the entrys in the
163 * hash table using silc_hash_table_foreach. The `user_context' is
164 * application specific context and is delivered to the callback.
167 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
169 /* Simple hash table interface */
171 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
175 * SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
176 * SilcHashFunction hash,
177 * void *hash_user_context,
178 * SilcHashCompare compare,
179 * void *compare_user_context,
180 * SilcHashDestructor destructor,
181 * void *destructor_user_context,
182 * SilcBool auto_rehash);
186 * Allocates new hash table and returns it. If the `table_size' is not
187 * zero then the hash table size is the size provided. If zero then the
188 * default size will be used. Note that if the `table_size' is provided
189 * it should be a prime. The `hash', `compare' and `destructor' are
190 * the hash function, the key comparison function and key and context
191 * destructor function, respectively. The `hash' is mandatory, the others
195 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
196 SilcHashFunction hash,
197 void *hash_user_context,
198 SilcHashCompare compare,
199 void *compare_user_context,
200 SilcHashDestructor destructor,
201 void *destructor_user_context,
202 SilcBool auto_rehash);
204 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
208 * void silc_hash_table_free(SilcHashTable ht);
212 * Frees the hash table. The destructor function provided in the
213 * silc_hash_table_alloc will be called for all keys in the hash table.
216 void silc_hash_table_free(SilcHashTable ht);
218 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
222 * SilcUInt32 silc_hash_table_size(SilcHashTable ht);
226 * Returns the size of the hash table. This is the true size of the
230 SilcUInt32 silc_hash_table_size(SilcHashTable ht);
232 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
236 * SilcUInt32 silc_hash_table_count(SilcHashTable ht);
240 * Returns the number of the entires in the hash table. If there is more
241 * entries in the table thatn the size of the hash table calling the
242 * silc_hash_table_rehash is recommended.
245 SilcUInt32 silc_hash_table_count(SilcHashTable ht);
247 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
251 * SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context);
255 * Adds new entry to the hash table. The `key' is hashed using the
256 * hash function and the both `key' and `context' will be saved to the
257 * hash table. This function quarantees that the entry is always added
258 * to the hash table reliably (it is collision resistant).
261 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context);
263 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace
267 * SilcBool silc_hash_table_replace(SilcHashTable ht, void *key,
272 * Same as silc_hash_table_add but if the `key' already exists in the
273 * hash table the old key and the old context will be replaced with the
274 * `key' and the `context. The destructor function will be called for the
275 * replaced key and context.
278 SilcBool silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
280 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
284 * SilcBool silc_hash_table_del(SilcHashTable ht, void *key);
288 * Removes the entry from the hash table by the provided `key'. This will
289 * call the destructor funtion for the found entry. Return TRUE if the
290 * entry was removed successfully and FALSE otherwise.
293 SilcBool silc_hash_table_del(SilcHashTable ht, void *key);
295 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
299 * SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
304 * Same as silc_hash_table_del but verifies that the context associated
305 * with the `key' matches the `context'. This is handy to use with hash
306 * tables that may have duplicate keys. In that case the `context' may
307 * be used to check whether the correct entry is being deleted.
310 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
313 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
317 * SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
318 * void **ret_key, void **ret_context);
322 * Finds the entry in the hash table by the provided `key' as fast as
323 * possible. Return TRUE if the entry was found and FALSE otherwise.
324 * The found entry is returned to the `ret_key' and `ret_context',
325 * respectively. If the `ret_key and `ret_context' are NULL then this
326 * maybe used only to check whether given key exists in the table.
329 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
330 void **ret_key, void **ret_context);
332 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context
336 * SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
337 * void *context, void **ret_key);
341 * Finds the entry in the hash table by the provided `key' and
342 * `context' as fast as possible. This is handy function when there
343 * can be multiple same keys in the hash table. By using this function
344 * the specific key with specific context can be found. Return
345 * TRUE if the entry with the key and context was found and FALSE
346 * otherwise. The function returns only the key to `ret_key' since
347 * the caller already knows the context.
350 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
351 void *context, void **ret_key);
353 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
357 * void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
358 * SilcHashForeach foreach,
359 * void *user_context);
363 * As the hash table is collision resistant it is possible to save duplicate
364 * keys to the hash table. This function can be used to find all keys
365 * and contexts from the hash table that are found using the `key'. The
366 * `foreach' is called for every found key. If no entries can be found
367 * the `foreach' will be called once with the context set NULL and
368 * `key' and `user_context' sent to the function.
372 * The hash table will not be rehashed during the traversing of the table,
373 * even if the table was marked as auto rehashable. The caller also must
374 * not call silc_hash_table_rehash while traversing the table.
377 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
378 SilcHashForeach foreach, void *user_context);
380 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
384 * void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
385 * void *user_context);
389 * Traverse all entrys in the hash table and call the `foreach' for
390 * every entry with the `user_context' context.
394 * The hash table will not be rehashed during the traversing of the table,
395 * even if the table was marked as auto rehashable. The caller also must
396 * not call silc_hash_table_rehash while traversing the table.
399 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
402 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
406 * void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
410 * Rehashs the hash table. The size of the new hash table is provided
411 * as `new_size'. If the `new_size' is zero then this routine will make
412 * the new table of a suitable size. Note that this operation may be
416 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
418 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
422 * void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
426 * Prepares the `htl' SilcHashTableList sent as argument to be used in the
427 * hash table traversing with the silc_hash_table_get. After the hash
428 * table traversing is completed the silc_hash_table_list_reset must be
433 * The hash table will not be rehashed during the traversing of the list,
434 * even if the table was marked as auto rehashable. The caller also must
435 * not call silc_hash_table_rehash while traversing the list.
438 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
440 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list_reset
444 * void silc_hash_table_list_reset(SilcHashTableList *htl);
448 * Resets the `htl' SilcHashTableList. This must be called after the
449 * hash table traversing is completed.
452 void silc_hash_table_list_reset(SilcHashTableList *htl);
454 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
458 * SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
463 * Returns always the next entry in the hash table into the `key' and
464 * `context' and TRUE. If this returns FALSE then there are no anymore
468 SilcBool silc_hash_table_get(SilcHashTableList *htl,
469 void **key, void **context);
472 /* Extended hash table interface (same as above but with specific
473 hash and comparison functions). */
475 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
479 * SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key,
481 * SilcHashFunction hash,
482 * void *hash_user_context);
486 * Adds new entry to the hash table. The `key' is hashed using the
487 * hash function and the both `key' and `context' will be saved to the
488 * hash table. This function quarantees that the entry is always added
489 * to the hash table reliably (it is collision resistant).
491 * The `hash' and `hash_user_context' are application specified hash
492 * function. If not provided the hash table's default is used.
495 SilcBool silc_hash_table_add_ext(SilcHashTable ht,
496 void *key, void *context,
497 SilcHashFunction hash,
498 void *hash_user_context);
500 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
504 * SilcBool silc_hash_table_replace_ext(SilcHashTable ht, void *key,
506 * SilcHashFunction hash,
507 * void *hash_user_context);
511 * Same as silc_hash_table_add_ext but if the `key' already exists in the
512 * hash table the old key and the old context will be replaced with the
513 * `key' and the `context. The destructor function will be called for the
514 * replaced key and context.
516 * The `hash' and `hash_user_context' are application specified hash
517 * function. If not provided the hash table's default is used.
520 SilcBool silc_hash_table_replace_ext(SilcHashTable ht,
521 void *key, void *context,
522 SilcHashFunction hash,
523 void *hash_user_context);
525 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
529 * SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
530 * SilcHashFunction hash,
531 * void *hash_user_context,
532 * SilcHashCompare compare,
533 * void *compare_user_context,
534 * SilcHashDestructor destructor,
535 * void *destructor_user_context);
539 * Removes the entry from the hash table by the provided `key'. This will
540 * call the destructor funtion for the found entry. Return TRUE if the
541 * entry was removed successfully and FALSE otherwise.
543 * The `hash' and `hash_user_context' are application specified hash
544 * function. If not provided the hash table's default is used.
545 * The `compare' and `compare_user_context' are application specified
546 * comparing function. If not provided the hash table's default is used.
547 * The `destructor' and `destructor_user_context' are application
548 * specific destructor function.
551 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
552 SilcHashFunction hash,
553 void *hash_user_context,
554 SilcHashCompare compare,
555 void *compare_user_context,
556 SilcHashDestructor destructor,
557 void *destructor_user_context);
559 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
564 * silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
566 * SilcHashFunction hash,
567 * void *hash_user_context,
568 * SilcHashCompare compare,
569 * void *compare_user_context,
570 * SilcHashDestructor destructor,
571 * void *destructor_user_context);
575 * Same as silc_hash_table_del but verifies that the context associated
576 * with the `key' matches the `context'. This is handy to use with hash
577 * tables that may have duplicate keys. In that case the `context' may
578 * be used to check whether the correct entry is being deleted.
580 * The `hash' and `hash_user_context' are application specified hash
581 * function. If not provided the hash table's default is used.
582 * The `compare' and `compare_user_context' are application specified
583 * comparing function. If not provided the hash table's default is used.
584 * The `destructor' and `destructor_user_context' are application
585 * specific destructor function.
588 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
590 SilcHashFunction hash,
591 void *hash_user_context,
592 SilcHashCompare compare,
593 void *compare_user_context,
594 SilcHashDestructor destructor,
595 void *destructor_user_context);
597 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
601 * SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
602 * void **ret_key, void **ret_context,
603 * SilcHashFunction hash,
604 * void *hash_user_context,
605 * SilcHashCompare compare,
606 * void *compare_user_context);
610 * Finds the entry in the hash table by the provided `key' as fast as
611 * possible. Return TRUE if the entry was found and FALSE otherwise.
612 * The found entry is returned to the `ret_key' and `ret_context',
613 * respectively. If the `ret_key and `ret_context' are NULL then this
614 * maybe used only to check whether given key exists in the table.
616 * The `hash' and `hash_user_context' are application specified hash
617 * function. If not provided the hash table's default is used.
618 * The `compare' and `compare_user_context' are application specified
619 * comparing function. If not provided the hash table's default is used.
622 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
623 void **ret_key, void **ret_context,
624 SilcHashFunction hash,
625 void *hash_user_context,
626 SilcHashCompare compare,
627 void *compare_user_context);
629 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context_ext
634 * silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
635 * void *context, void **ret_key,
636 * SilcHashFunction hash,
637 * void *hash_user_context,
638 * SilcHashCompare compare,
639 * void *compare_user_context);
643 * Finds the entry in the hash table by the provided `key' and
644 * `context' as fast as possible. This is handy function when there
645 * can be multiple same keys in the hash table. By using this function
646 * the specific key with specific context can be found. Return
647 * TRUE if the entry with the key and context was found and FALSE
648 * otherwise. The function returns only the key to `ret_key' since
649 * the caller already knows the context.
651 * The `hash' and `hash_user_context' are application specified hash
652 * function. If not provided the hash table's default is used.
653 * The `compare' and `compare_user_context' are application specified
654 * comparing function. If not provided the hash table's default is used.
657 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
658 void *context, void **ret_key,
659 SilcHashFunction hash,
660 void *hash_user_context,
661 SilcHashCompare compare,
662 void *compare_user_context);
664 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
668 * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
669 * SilcHashFunction hash,
670 * void *hash_user_context,
671 * SilcHashCompare compare,
672 * void *compare_user_context,
673 * SilcHashForeach foreach,
674 * void *foreach_user_context);
678 * As the hash table is collision resistant it is possible to save duplicate
679 * keys to the hash table. This function can be used to find all keys
680 * and contexts from the hash table that are found using the `key'. The
681 * `foreach' is called for every found key. If no entries can be found
682 * the `foreach' will be called once with the context set NULL and
683 * `key' and `user_context' sent to the function.
685 * The `hash' and `hash_user_context' are application specified hash
686 * function. If not provided the hash table's default is used.
687 * The `compare' and `compare_user_context' are application specified
688 * comparing function. If not provided the hash table's default is used.
692 * The hash table will not be rehashed during the traversing of the table,
693 * even if the table was marked as auto rehashable. The caller also must
694 * not call silc_hash_table_rehash while traversing the table.
697 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
698 SilcHashFunction hash,
699 void *hash_user_context,
700 SilcHashCompare compare,
701 void *compare_user_context,
702 SilcHashForeach foreach,
703 void *foreach_user_context);
705 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
709 * void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
710 * SilcHashFunction hash,
711 * void *hash_user_context);
715 * Rehashs the hash table. The size of the new hash table is provided
716 * as `new_size'. If the `new_size' is zero then this routine will make
717 * the new table of a suitable size. Note that this operation may be
720 * The `hash' and `hash_user_context' are application specified hash
721 * function. If not provided the hash table's default is used.
724 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
725 SilcHashFunction hash,
726 void *hash_user_context);