5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2003 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.
44 #ifndef SILCHASHTABLE_H
45 #define SILCHASHTABLE_H
47 /****s* silcutil/SilcHashTableAPI/SilcHashTable
51 * typedef struct SilcHashTableStruct *SilcHashTable;
55 * This context is the actual hash table and is allocated
56 * by silc_hash_table_alloc and given as argument usually to
57 * all silc_hash_table_* functions. It is freed by the
58 * silc_hash_table_free function.
61 typedef struct SilcHashTableStruct *SilcHashTable;
63 /****s* silcutil/SilcHashTableAPI/SilcHashTableList
67 * typedef struct SilcHashTableListStruct SilcHashTableList;
71 * This structure is used to tarverse the hash table. This structure
72 * is given as argument to the silc_hash_table_list function to
73 * initialize it and then used to traverse the hash table with the
74 * silc_hash_table_get function. It needs not be allocated or freed.
78 * SilcHashTableList htl;
79 * silc_hash_table_list(hash_table, &htl);
80 * while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
82 * silc_hash_table_list_reset(&htl);
86 typedef struct SilcHashTableListStruct SilcHashTableList;
88 /* List structure to traverse the hash table. */
89 struct SilcHashTableListStruct {
92 unsigned int index : 31;
93 unsigned int auto_rehash : 1;
97 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
101 * typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
105 * A type for the hash function. This function is used to hash the
106 * provided key value `key' and return the index for the hash table.
107 * The `user_context' is application specific context and is delivered
111 typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context);
113 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
117 * typedef bool (*SilcHashCompare)(void *key1, void *key2,
118 * void *user_context);
122 * A comparison funtion that is called to compare the two keys `key1' and
123 * `key2'. If they are equal this must return TRUE or FALSE otherwise.
124 * The application provides this function when allocating a new hash table.
125 * The `user_context' is application specific context and is delivered
129 typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context);
131 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
135 * typedef void (*SilcHashDestructor)(void *key, void *context,
136 * void *user_context);
140 * A destructor callback that the library will call to destroy the
141 * `key' and `context'. The application provides the function when
142 * allocating a new hash table. The `user_context' is application
143 * specific context and is delivered to the callback.
146 typedef void (*SilcHashDestructor)(void *key, void *context,
149 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
153 * typedef void (*SilcHashForeach)(void *key, void *context,
154 * void *user_context);
158 * Foreach function. This is called when traversing the entrys in the
159 * hash table using silc_hash_table_foreach. The `user_context' is
160 * application specific context and is delivered to the callback.
163 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
165 /* Simple hash table interface */
167 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
171 * SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
172 * SilcHashFunction hash,
173 * void *hash_user_context,
174 * SilcHashCompare compare,
175 * void *compare_user_context,
176 * SilcHashDestructor destructor,
177 * void *destructor_user_context,
182 * Allocates new hash table and returns it. If the `table_size' is not
183 * zero then the hash table size is the size provided. If zero then the
184 * default size will be used. Note that if the `table_size' is provided
185 * it should be a prime. The `hash', `compare' and `destructor' are
186 * the hash function, the key comparison function and key and context
187 * destructor function, respectively. The `hash' is mandatory, the others
191 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
192 SilcHashFunction hash,
193 void *hash_user_context,
194 SilcHashCompare compare,
195 void *compare_user_context,
196 SilcHashDestructor destructor,
197 void *destructor_user_context,
200 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
204 * void silc_hash_table_free(SilcHashTable ht);
208 * Frees the hash table. The destructor function provided in the
209 * silc_hash_table_alloc will be called for all keys in the hash table.
212 void silc_hash_table_free(SilcHashTable ht);
214 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
218 * SilcUInt32 silc_hash_table_size(SilcHashTable ht);
222 * Returns the size of the hash table. This is the true size of the
226 SilcUInt32 silc_hash_table_size(SilcHashTable ht);
228 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
232 * SilcUInt32 silc_hash_table_count(SilcHashTable ht);
236 * Returns the number of the entires in the hash table. If there is more
237 * entries in the table thatn the size of the hash table calling the
238 * silc_hash_table_rehash is recommended.
241 SilcUInt32 silc_hash_table_count(SilcHashTable ht);
243 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
247 * void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
251 * Adds new entry to the hash table. The `key' is hashed using the
252 * hash function and the both `key' and `context' will be saved to the
253 * hash table. This function quarantees that the entry is always added
254 * to the hash table reliably (it is collision resistant).
257 void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
259 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace
263 * void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
267 * Same as silc_hash_table_add but if the `key' already exists in the
268 * hash table the old key and the old context will be replaced with the
269 * `key' and the `context. The destructor function will be called for the
270 * replaced key and context.
273 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
275 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
279 * bool silc_hash_table_del(SilcHashTable ht, void *key);
283 * Removes the entry from the hash table by the provided `key'. This will
284 * call the destructor funtion for the found entry. Return TRUE if the
285 * entry was removed successfully and FALSE otherwise.
288 bool silc_hash_table_del(SilcHashTable ht, void *key);
290 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
294 * bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
299 * Same as silc_hash_table_del but verifies that the context associated
300 * with the `key' matches the `context'. This is handy to use with hash
301 * tables that may have duplicate keys. In that case the `context' may
302 * be used to check whether the correct entry is being deleted.
305 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
308 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
312 * bool silc_hash_table_find(SilcHashTable ht, void *key,
313 * void **ret_key, void **ret_context);
317 * Finds the entry in the hash table by the provided `key' as fast as
318 * possible. Return TRUE if the entry was found and FALSE otherwise.
319 * The found entry is returned to the `ret_key' and `ret_context',
320 * respectively. If the `ret_key and `ret_context' are NULL then this
321 * maybe used only to check whether given key exists in the table.
324 bool silc_hash_table_find(SilcHashTable ht, void *key,
325 void **ret_key, void **ret_context);
327 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context
331 * bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
332 * void *context, void **ret_key);
336 * Finds the entry in the hash table by the provided `key' and
337 * `context' as fast as possible. This is handy function when there
338 * can be multiple same keys in the hash table. By using this function
339 * the specific key with specific context can be found. Return
340 * TRUE if the entry with the key and context was found and FALSE
341 * otherwise. The function returns only the key to `ret_key' since
342 * the caller already knows the context.
345 bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
346 void *context, void **ret_key);
348 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
352 * void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
353 * SilcHashForeach foreach,
354 * void *user_context);
358 * As the hash table is collision resistant it is possible to save duplicate
359 * keys to the hash table. This function can be used to find all keys
360 * and contexts from the hash table that are found using the `key'. The
361 * `foreach' is called for every found key. If no entries can be found
362 * the `foreach' will be called once with the context set NULL and
363 * `key' and `user_context' sent to the function.
367 * The hash table will not be rehashed during the traversing of the table,
368 * even if the table was marked as auto rehashable. The caller also must
369 * not call silc_hash_table_rehash while traversing the table.
372 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
373 SilcHashForeach foreach, void *user_context);
375 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
379 * void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
380 * void *user_context);
384 * Traverse all entrys in the hash table and call the `foreach' for
385 * every entry with the `user_context' context.
389 * The hash table will not be rehashed during the traversing of the table,
390 * even if the table was marked as auto rehashable. The caller also must
391 * not call silc_hash_table_rehash while traversing the table.
394 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
397 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
401 * void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
405 * Rehashs the hash table. The size of the new hash table is provided
406 * as `new_size'. If the `new_size' is zero then this routine will make
407 * the new table of a suitable size. Note that this operation may be
411 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size);
413 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
417 * void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
421 * Prepares the `htl' SilcHashTableList sent as argument to be used in the
422 * hash table traversing with the silc_hash_table_get. After the hash
423 * table traversing is completed the silc_hash_table_list_reset must be
428 * The hash table will not be rehashed during the traversing of the list,
429 * even if the table was marked as auto rehashable. The caller also must
430 * not call silc_hash_table_rehash while traversing the list.
433 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
435 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list_reset
439 * void silc_hash_table_list_reset(SilcHashTableList *htl);
443 * Resets the `htl' SilcHashTableList. This must be called after the
444 * hash table traversing is completed.
447 void silc_hash_table_list_reset(SilcHashTableList *htl);
449 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
453 * bool silc_hash_table_get(SilcHashTableList *htl, void **key,
458 * Returns always the next entry in the hash table into the `key' and
459 * `context' and TRUE. If this returns FALSE then there are no anymore
463 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context);
466 /* Extended hash table interface (same as above but with specific
467 hash and comparison functions). */
469 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
473 * void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
474 * SilcHashFunction hash,
475 * void *hash_user_context);
479 * Adds new entry to the hash table. The `key' is hashed using the
480 * hash function and the both `key' and `context' will be saved to the
481 * hash table. This function quarantees that the entry is always added
482 * to the hash table reliably (it is collision resistant).
484 * The `hash' and `hash_user_context' are application specified hash
485 * function. If not provided the hash table's default is used.
488 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
489 SilcHashFunction hash, void *hash_user_context);
491 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
495 * void silc_hash_table_replace_ext(SilcHashTable ht, void *key,
497 * SilcHashFunction hash,
498 * void *hash_user_context);
502 * Same as silc_hash_table_add_ext but if the `key' already exists in the
503 * hash table the old key and the old context will be replaced with the
504 * `key' and the `context. The destructor function will be called for the
505 * replaced key and context.
507 * The `hash' and `hash_user_context' are application specified hash
508 * function. If not provided the hash table's default is used.
511 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
512 SilcHashFunction hash,
513 void *hash_user_context);
515 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
519 * bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
520 * SilcHashFunction hash,
521 * void *hash_user_context,
522 * SilcHashCompare compare,
523 * void *compare_user_context,
524 * SilcHashDestructor destructor,
525 * void *destructor_user_context);
529 * Removes the entry from the hash table by the provided `key'. This will
530 * call the destructor funtion for the found entry. Return TRUE if the
531 * entry was removed successfully and FALSE otherwise.
533 * The `hash' and `hash_user_context' are application specified hash
534 * function. If not provided the hash table's default is used.
535 * The `compare' and `compare_user_context' are application specified
536 * comparing function. If not provided the hash table's default is used.
537 * The `destructor' and `destructor_user_context' are application
538 * specific destructor function.
541 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
542 SilcHashFunction hash,
543 void *hash_user_context,
544 SilcHashCompare compare,
545 void *compare_user_context,
546 SilcHashDestructor destructor,
547 void *destructor_user_context);
549 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
553 * bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
555 * SilcHashFunction hash,
556 * void *hash_user_context,
557 * SilcHashCompare compare,
558 * void *compare_user_context,
559 * SilcHashDestructor destructor,
560 * void *destructor_user_context);
564 * Same as silc_hash_table_del but verifies that the context associated
565 * with the `key' matches the `context'. This is handy to use with hash
566 * tables that may have duplicate keys. In that case the `context' may
567 * be used to check whether the correct entry is being deleted.
569 * The `hash' and `hash_user_context' are application specified hash
570 * function. If not provided the hash table's default is used.
571 * The `compare' and `compare_user_context' are application specified
572 * comparing function. If not provided the hash table's default is used.
573 * The `destructor' and `destructor_user_context' are application
574 * specific destructor function.
577 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
579 SilcHashFunction hash,
580 void *hash_user_context,
581 SilcHashCompare compare,
582 void *compare_user_context,
583 SilcHashDestructor destructor,
584 void *destructor_user_context);
586 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
590 * bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
591 * void **ret_key, void **ret_context,
592 * SilcHashFunction hash,
593 * void *hash_user_context,
594 * SilcHashCompare compare,
595 * void *compare_user_context);
599 * Finds the entry in the hash table by the provided `key' as fast as
600 * possible. Return TRUE if the entry was found and FALSE otherwise.
601 * The found entry is returned to the `ret_key' and `ret_context',
602 * respectively. If the `ret_key and `ret_context' are NULL then this
603 * maybe used only to check whether given key exists in the table.
605 * The `hash' and `hash_user_context' are application specified hash
606 * function. If not provided the hash table's default is used.
607 * The `compare' and `compare_user_context' are application specified
608 * comparing function. If not provided the hash table's default is used.
611 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
612 void **ret_key, void **ret_context,
613 SilcHashFunction hash,
614 void *hash_user_context,
615 SilcHashCompare compare,
616 void *compare_user_context);
618 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context_ext
622 * bool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
623 * void *context, void **ret_key,
624 * SilcHashFunction hash,
625 * void *hash_user_context,
626 * SilcHashCompare compare,
627 * void *compare_user_context);
631 * Finds the entry in the hash table by the provided `key' and
632 * `context' as fast as possible. This is handy function when there
633 * can be multiple same keys in the hash table. By using this function
634 * the specific key with specific context can be found. Return
635 * TRUE if the entry with the key and context was found and FALSE
636 * otherwise. The function returns only the key to `ret_key' since
637 * the caller already knows the context.
639 * The `hash' and `hash_user_context' are application specified hash
640 * function. If not provided the hash table's default is used.
641 * The `compare' and `compare_user_context' are application specified
642 * comparing function. If not provided the hash table's default is used.
645 bool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
646 void *context, void **ret_key,
647 SilcHashFunction hash,
648 void *hash_user_context,
649 SilcHashCompare compare,
650 void *compare_user_context);
652 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
656 * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
657 * SilcHashFunction hash,
658 * void *hash_user_context,
659 * SilcHashCompare compare,
660 * void *compare_user_context,
661 * SilcHashForeach foreach,
662 * void *foreach_user_context);
666 * As the hash table is collision resistant it is possible to save duplicate
667 * keys to the hash table. This function can be used to find all keys
668 * and contexts from the hash table that are found using the `key'. The
669 * `foreach' is called for every found key. If no entries can be found
670 * the `foreach' will be called once with the context set NULL and
671 * `key' and `user_context' sent to the function.
673 * The `hash' and `hash_user_context' are application specified hash
674 * function. If not provided the hash table's default is used.
675 * The `compare' and `compare_user_context' are application specified
676 * comparing function. If not provided the hash table's default is used.
680 * The hash table will not be rehashed during the traversing of the table,
681 * even if the table was marked as auto rehashable. The caller also must
682 * not call silc_hash_table_rehash while traversing the table.
685 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
686 SilcHashFunction hash,
687 void *hash_user_context,
688 SilcHashCompare compare,
689 void *compare_user_context,
690 SilcHashForeach foreach,
691 void *foreach_user_context);
693 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
697 * void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
698 * SilcHashFunction hash,
699 * void *hash_user_context);
703 * Rehashs the hash table. The size of the new hash table is provided
704 * as `new_size'. If the `new_size' is zero then this routine will make
705 * the new table of a suitable size. Note that this operation may be
708 * The `hash' and `hash_user_context' are application specified hash
709 * function. If not provided the hash table's default is used.
712 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
713 SilcHashFunction hash,
714 void *hash_user_context);