5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2006 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 more
469 * SilcHashTableList htl;
470 * silc_hash_table_list(hash_table, &htl);
471 * while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
473 * silc_hash_table_list_reset(&htl);
476 SilcBool silc_hash_table_get(SilcHashTableList *htl,
477 void **key, void **context);
480 /* Extended hash table interface (same as above but with specific
481 hash and comparison functions). */
483 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
487 * SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key,
489 * SilcHashFunction hash,
490 * void *hash_user_context);
494 * Adds new entry to the hash table. The `key' is hashed using the
495 * hash function and the both `key' and `context' will be saved to the
496 * hash table. This function quarantees that the entry is always added
497 * to the hash table reliably (it is collision resistant).
499 * The `hash' and `hash_user_context' are application specified hash
500 * function. If not provided the hash table's default is used.
503 SilcBool silc_hash_table_add_ext(SilcHashTable ht,
504 void *key, void *context,
505 SilcHashFunction hash,
506 void *hash_user_context);
508 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
512 * SilcBool silc_hash_table_replace_ext(SilcHashTable ht, void *key,
514 * SilcHashFunction hash,
515 * void *hash_user_context);
519 * Same as silc_hash_table_add_ext but if the `key' already exists in the
520 * hash table the old key and the old context will be replaced with the
521 * `key' and the `context. The destructor function will be called for the
522 * replaced key and context.
524 * The `hash' and `hash_user_context' are application specified hash
525 * function. If not provided the hash table's default is used.
528 SilcBool silc_hash_table_replace_ext(SilcHashTable ht,
529 void *key, void *context,
530 SilcHashFunction hash,
531 void *hash_user_context);
533 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
537 * SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
538 * SilcHashFunction hash,
539 * void *hash_user_context,
540 * SilcHashCompare compare,
541 * void *compare_user_context,
542 * SilcHashDestructor destructor,
543 * void *destructor_user_context);
547 * Removes the entry from the hash table by the provided `key'. This will
548 * call the destructor funtion for the found entry. Return TRUE if the
549 * entry was removed successfully and FALSE otherwise.
551 * The `hash' and `hash_user_context' are application specified hash
552 * function. If not provided the hash table's default is used.
553 * The `compare' and `compare_user_context' are application specified
554 * comparing function. If not provided the hash table's default is used.
555 * The `destructor' and `destructor_user_context' are application
556 * specific destructor function.
559 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
560 SilcHashFunction hash,
561 void *hash_user_context,
562 SilcHashCompare compare,
563 void *compare_user_context,
564 SilcHashDestructor destructor,
565 void *destructor_user_context);
567 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
572 * silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
574 * SilcHashFunction hash,
575 * void *hash_user_context,
576 * SilcHashCompare compare,
577 * void *compare_user_context,
578 * SilcHashDestructor destructor,
579 * void *destructor_user_context);
583 * Same as silc_hash_table_del but verifies that the context associated
584 * with the `key' matches the `context'. This is handy to use with hash
585 * tables that may have duplicate keys. In that case the `context' may
586 * be used to check whether the correct entry is being deleted.
588 * The `hash' and `hash_user_context' are application specified hash
589 * function. If not provided the hash table's default is used.
590 * The `compare' and `compare_user_context' are application specified
591 * comparing function. If not provided the hash table's default is used.
592 * The `destructor' and `destructor_user_context' are application
593 * specific destructor function.
596 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
598 SilcHashFunction hash,
599 void *hash_user_context,
600 SilcHashCompare compare,
601 void *compare_user_context,
602 SilcHashDestructor destructor,
603 void *destructor_user_context);
605 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
609 * SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
610 * void **ret_key, void **ret_context,
611 * SilcHashFunction hash,
612 * void *hash_user_context,
613 * SilcHashCompare compare,
614 * void *compare_user_context);
618 * Finds the entry in the hash table by the provided `key' as fast as
619 * possible. Return TRUE if the entry was found and FALSE otherwise.
620 * The found entry is returned to the `ret_key' and `ret_context',
621 * respectively. If the `ret_key and `ret_context' are NULL then this
622 * maybe used only to check whether given key exists in the table.
624 * The `hash' and `hash_user_context' are application specified hash
625 * function. If not provided the hash table's default is used.
626 * The `compare' and `compare_user_context' are application specified
627 * comparing function. If not provided the hash table's default is used.
630 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
631 void **ret_key, void **ret_context,
632 SilcHashFunction hash,
633 void *hash_user_context,
634 SilcHashCompare compare,
635 void *compare_user_context);
637 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context_ext
642 * silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
643 * void *context, void **ret_key,
644 * SilcHashFunction hash,
645 * void *hash_user_context,
646 * SilcHashCompare compare,
647 * void *compare_user_context);
651 * Finds the entry in the hash table by the provided `key' and
652 * `context' as fast as possible. This is handy function when there
653 * can be multiple same keys in the hash table. By using this function
654 * the specific key with specific context can be found. Return
655 * TRUE if the entry with the key and context was found and FALSE
656 * otherwise. The function returns only the key to `ret_key' since
657 * the caller already knows the context.
659 * The `hash' and `hash_user_context' are application specified hash
660 * function. If not provided the hash table's default is used.
661 * The `compare' and `compare_user_context' are application specified
662 * comparing function. If not provided the hash table's default is used.
665 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
666 void *context, void **ret_key,
667 SilcHashFunction hash,
668 void *hash_user_context,
669 SilcHashCompare compare,
670 void *compare_user_context);
672 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
676 * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
677 * SilcHashFunction hash,
678 * void *hash_user_context,
679 * SilcHashCompare compare,
680 * void *compare_user_context,
681 * SilcHashForeach foreach,
682 * void *foreach_user_context);
686 * As the hash table is collision resistant it is possible to save duplicate
687 * keys to the hash table. This function can be used to find all keys
688 * and contexts from the hash table that are found using the `key'. The
689 * `foreach' is called for every found key. If no entries can be found
690 * the `foreach' will be called once with the context set NULL and
691 * `key' and `user_context' sent to the function.
693 * The `hash' and `hash_user_context' are application specified hash
694 * function. If not provided the hash table's default is used.
695 * The `compare' and `compare_user_context' are application specified
696 * comparing function. If not provided the hash table's default is used.
700 * The hash table will not be rehashed during the traversing of the table,
701 * even if the table was marked as auto rehashable. The caller also must
702 * not call silc_hash_table_rehash while traversing the table.
705 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
706 SilcHashFunction hash,
707 void *hash_user_context,
708 SilcHashCompare compare,
709 void *compare_user_context,
710 SilcHashForeach foreach,
711 void *foreach_user_context);
713 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
717 * void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
718 * SilcHashFunction hash,
719 * void *hash_user_context);
723 * Rehashs the hash table. The size of the new hash table is provided
724 * as `new_size'. If the `new_size' is zero then this routine will make
725 * the new table of a suitable size. Note that this operation may be
728 * The `hash' and `hash_user_context' are application specified hash
729 * function. If not provided the hash table's default is used.
732 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
733 SilcHashFunction hash,
734 void *hash_user_context);