5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 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; either version 2 of the License, or
12 (at your option) any later version.
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.
21 /****h* silcutil/SilcHashTableAPI
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.
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
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.
45 #ifndef SILCHASHTABLE_H
46 #define SILCHASHTABLE_H
48 /****s* silcutil/SilcHashTableAPI/SilcHashTable
52 * typedef struct SilcHashTableStruct *SilcHashTable;
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.
62 typedef struct SilcHashTableStruct *SilcHashTable;
64 /****s* silcutil/SilcHashTableAPI/SilcHashTableList
68 * typedef struct SilcHashTableListStruct SilcHashTableList;
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.
79 * SilcHashTableList htl;
80 * silc_hash_table_list(hash_table, &htl);
81 * while (silc_hash_table_get(&htl, (void *)&key, (void *)&context))
83 * silc_hash_table_list_reset(&htl);
87 typedef struct SilcHashTableListStruct SilcHashTableList;
89 /* List structure to traverse the hash table. */
90 struct SilcHashTableListStruct {
98 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
102 * typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
106 * A type for the hash function. This function is used to hash the
107 * provided key value `key' and return the index for the hash table.
108 * The `user_context' is application specific context and is delivered
112 typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
114 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
118 * typedef bool (*SilcHashCompare)(void *key1, void *key2,
119 * void *user_context);
123 * A comparison funtion that is called to compare the two keys `key1' and
124 * `key2'. If they are equal this must return TRUE or FALSE otherwise.
125 * The application provides this function when allocating a new hash table.
126 * The `user_context' is application specific context and is delivered
130 typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context);
132 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
136 * typedef void (*SilcHashDestructor)(void *key, void *context,
137 * void *user_context);
141 * A destructor callback that the library will call to destroy the
142 * `key' and `context'. The appliation provides the function when
143 * allocating a new hash table. The `user_context' is application
144 * specific context and is delivered to the callback.
147 typedef void (*SilcHashDestructor)(void *key, void *context,
150 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
154 * typedef void (*SilcHashForeach)(void *key, void *context,
155 * void *user_context);
159 * Foreach function. This is called when traversing the entrys in the
160 * hash table using silc_hash_table_foreach. The `user_context' is
161 * application specific context and is delivered to the callback.
164 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
166 /* Simple hash table interface */
168 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
172 * SilcHashTable silc_hash_table_alloc(uint32 table_size,
173 * SilcHashFunction hash,
174 * void *hash_user_context,
175 * SilcHashCompare compare,
176 * void *compare_user_context,
177 * SilcHashDestructor destructor,
178 * void *destructor_user_context,
183 * Allocates new hash table and returns it. If the `table_size' is not
184 * zero then the hash table size is the size provided. If zero then the
185 * default size will be used. Note that if the `table_size' is provided
186 * it should be a prime. The `hash', `compare' and `destructor' are
187 * the hash function, the key comparison function and key and context
188 * destructor function, respectively. The `hash' is mandatory, the others
192 SilcHashTable silc_hash_table_alloc(uint32 table_size,
193 SilcHashFunction hash,
194 void *hash_user_context,
195 SilcHashCompare compare,
196 void *compare_user_context,
197 SilcHashDestructor destructor,
198 void *destructor_user_context,
201 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
205 * void silc_hash_table_free(SilcHashTable ht);
209 * Frees the hash table. The destructor function provided in the
210 * silc_hash_table_alloc will be called for all keys in the hash table.
213 void silc_hash_table_free(SilcHashTable ht);
215 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
219 * uint32 silc_hash_table_size(SilcHashTable ht);
223 * Returns the size of the hash table. This is the true size of the
227 uint32 silc_hash_table_size(SilcHashTable ht);
229 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
233 * uint32 silc_hash_table_count(SilcHashTable ht);
237 * Returns the number of the entires in the hash table. If there is more
238 * entries in the table thatn the size of the hash table calling the
239 * silc_hash_table_rehash is recommended.
242 uint32 silc_hash_table_count(SilcHashTable ht);
244 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
248 * void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
252 * Adds new entry to the hash table. The `key' is hashed using the
253 * hash function and the both `key' and `context' will be saved to the
254 * hash table. This function quarantees that the entry is always added
255 * to the hash table reliably (it is collision resistant).
258 void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
260 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace
264 * void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
268 * Same as silc_hash_table_add but if the `key' already exists in the
269 * hash table the old key and the old context will be replaced with the
270 * `key' and the `context. The destructor function will be called for the
271 * replaced key and context.
274 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
276 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
280 * bool silc_hash_table_del(SilcHashTable ht, void *key);
284 * Removes the entry from the hash table by the provided `key'. This will
285 * call the destructor funtion for the found entry. Return TRUE if the
286 * entry was removed successfully and FALSE otherwise.
289 bool silc_hash_table_del(SilcHashTable ht, void *key);
291 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
295 * bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
300 * Same as silc_hash_table_del but verifies that the context associated
301 * with the `key' matches the `context'. This is handy to use with hash
302 * tables that may have duplicate keys. In that case the `context' may
303 * be used to check whether the correct entry is being deleted.
306 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
309 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
313 * bool silc_hash_table_find(SilcHashTable ht, void *key,
314 * void **ret_key, void **ret_context);
318 * Finds the entry in the hash table by the provided `key' as fast as
319 * possible. Return TRUE if the entry was found and FALSE otherwise.
320 * The found entry is returned to the `ret_key' and `ret_context',
321 * respectively. If the `ret_key and `ret_context' are NULL then this
322 * maybe used only to check whether given key exists in the table.
325 bool silc_hash_table_find(SilcHashTable ht, void *key,
326 void **ret_key, void **ret_context);
328 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
332 * void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
333 * SilcHashForeach foreach,
334 * void *user_context);
338 * As the hash table is collision resistant it is possible to save duplicate
339 * keys to the hash table. This function can be used to find all keys
340 * and contexts from the hash table that are found using the `key'. The
341 * `foreach' is called for every found key.
344 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
345 SilcHashForeach foreach, void *user_context);
347 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
351 * void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
352 * void *user_context);
356 * Traverse all entrys in the hash table and call the `foreach' for
357 * every entry with the `user_context' context.
360 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
363 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
367 * void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
371 * Rehashs the hash table. The size of the new hash table is provided
372 * as `new_size'. If the `new_size' is zero then this routine will make
373 * the new table of a suitable size. Note that this operation may be
377 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
379 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
383 * void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
387 * Prepares the `htl' SilcHashTableList sent as argument to be used in the
388 * hash table traversing with the silc_hash_table_get. After the hash
389 * table traversing is completed the silc_hash_table_list_reset must be
394 * The hash table will not be rehashed during the traversing of the list,
395 * even if the table was marked as auto rehashable. The caller also must
396 * not call silc_hash_table_rehash while traversing the list.
399 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
401 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list_reset
405 * void silc_hash_table_list_reset(SilcHashTableList *htl);
409 * Resets the `htl' SilcHashTableList. This must be called after the
410 * hash table traversing is completed.
413 void silc_hash_table_list_reset(SilcHashTableList *htl);
415 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
419 * bool silc_hash_table_get(SilcHashTableList *htl, void **key,
424 * Returns always the next entry in the hash table into the `key' and
425 * `context' and TRUE. If this returns FALSE then there are no anymore
429 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context);
432 /* Extended hash table interface (same as above but with specific
433 hash and comparison functions). */
435 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
439 * void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
440 * SilcHashFunction hash,
441 * void *hash_user_context);
445 * Adds new entry to the hash table. The `key' is hashed using the
446 * hash function and the both `key' and `context' will be saved to the
447 * hash table. This function quarantees that the entry is always added
448 * to the hash table reliably (it is collision resistant).
450 * The `hash' and `hash_user_context' are application specified hash
451 * function. If not provided the hash table's default is used.
454 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
455 SilcHashFunction hash, void *hash_user_context);
457 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
461 * void silc_hash_table_replace_ext(SilcHashTable ht, void *key,
463 * SilcHashFunction hash,
464 * void *hash_user_context);
468 * Same as silc_hash_table_add_ext but if the `key' already exists in the
469 * hash table the old key and the old context will be replaced with the
470 * `key' and the `context. The destructor function will be called for the
471 * replaced key and context.
473 * The `hash' and `hash_user_context' are application specified hash
474 * function. If not provided the hash table's default is used.
477 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
478 SilcHashFunction hash,
479 void *hash_user_context);
481 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
485 * bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
486 * SilcHashFunction hash,
487 * void *hash_user_context,
488 * SilcHashCompare compare,
489 * void *compare_user_context,
490 * SilcHashDestructor destructor,
491 * void *destructor_user_context);
495 * Removes the entry from the hash table by the provided `key'. This will
496 * call the destructor funtion for the found entry. Return TRUE if the
497 * entry was removed successfully and FALSE otherwise.
499 * The `hash' and `hash_user_context' are application specified hash
500 * function. If not provided the hash table's default is used.
501 * The `compare' and `compare_user_context' are application specified
502 * comparing function. If not provided the hash table's default is used.
503 * The `destructor' and `destructor_user_context' are application
504 * specific destructor function.
507 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
508 SilcHashFunction hash,
509 void *hash_user_context,
510 SilcHashCompare compare,
511 void *compare_user_context,
512 SilcHashDestructor destructor,
513 void *destructor_user_context);
515 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
519 * bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
521 * SilcHashFunction hash,
522 * void *hash_user_context,
523 * SilcHashCompare compare,
524 * void *compare_user_context,
525 * SilcHashDestructor destructor,
526 * void *destructor_user_context);
530 * Same as silc_hash_table_del but verifies that the context associated
531 * with the `key' matches the `context'. This is handy to use with hash
532 * tables that may have duplicate keys. In that case the `context' may
533 * be used to check whether the correct entry is being deleted.
535 * The `hash' and `hash_user_context' are application specified hash
536 * function. If not provided the hash table's default is used.
537 * The `compare' and `compare_user_context' are application specified
538 * comparing function. If not provided the hash table's default is used.
539 * The `destructor' and `destructor_user_context' are application
540 * specific destructor function.
543 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
545 SilcHashFunction hash,
546 void *hash_user_context,
547 SilcHashCompare compare,
548 void *compare_user_context,
549 SilcHashDestructor destructor,
550 void *destructor_user_context);
552 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
556 * bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
557 * void **ret_key, void **ret_context,
558 * SilcHashFunction hash,
559 * void *hash_user_context,
560 * SilcHashCompare compare,
561 * void *compare_user_context);
565 * Finds the entry in the hash table by the provided `key' as fast as
566 * possible. Return TRUE if the entry was found and FALSE otherwise.
567 * The found entry is returned to the `ret_key' and `ret_context',
568 * respectively. If the `ret_key and `ret_context' are NULL then this
569 * maybe used only to check whether given key exists in the table.
571 * The `hash' and `hash_user_context' are application specified hash
572 * function. If not provided the hash table's default is used.
573 * The `compare' and `compare_user_context' are application specified
574 * comparing function. If not provided the hash table's default is used.
577 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
578 void **ret_key, void **ret_context,
579 SilcHashFunction hash,
580 void *hash_user_context,
581 SilcHashCompare compare,
582 void *compare_user_context);
584 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
588 * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
589 * SilcHashFunction hash,
590 * void *hash_user_context,
591 * SilcHashCompare compare,
592 * void *compare_user_context,
593 * SilcHashForeach foreach,
594 * void *foreach_user_context);
598 * As the hash table is collision resistant it is possible to save duplicate
599 * keys to the hash table. This function can be used to find all keys
600 * and contexts from the hash table that are found using the `key'. The
601 * `foreach' is called for every found key.
603 * The `hash' and `hash_user_context' are application specified hash
604 * function. If not provided the hash table's default is used.
605 * The `compare' and `compare_user_context' are application specified
606 * comparing function. If not provided the hash table's default is used.
609 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
610 SilcHashFunction hash,
611 void *hash_user_context,
612 SilcHashCompare compare,
613 void *compare_user_context,
614 SilcHashForeach foreach,
615 void *foreach_user_context);
617 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
621 * void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
622 * SilcHashFunction hash,
623 * void *hash_user_context);
627 * Rehashs the hash table. The size of the new hash table is provided
628 * as `new_size'. If the `new_size' is zero then this routine will make
629 * the new table of a suitable size. Note that this operation may be
632 * The `hash' and `hash_user_context' are application specified hash
633 * function. If not provided the hash table's default is used.
636 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
637 SilcHashFunction hash,
638 void *hash_user_context);