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))
86 typedef struct SilcHashTableListStruct SilcHashTableList;
88 /* List structure to traverse the hash table. */
89 struct SilcHashTableListStruct {
96 /****f* silcutil/SilcHashTableAPI/SilcHashFunction
100 * typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
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
110 typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
112 /****f* silcutil/SilcHashTableAPI/SilcHashCompare
116 * typedef bool (*SilcHashCompare)(void *key1, void *key2,
117 * void *user_context);
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
128 typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context);
130 /****f* silcutil/SilcHashTableAPI/SilcHashDestructor
134 * typedef void (*SilcHashDestructor)(void *key, void *context,
135 * void *user_context);
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.
145 typedef void (*SilcHashDestructor)(void *key, void *context,
148 /****f* silcutil/SilcHashTableAPI/SilcHashForeach
152 * typedef void (*SilcHashForeach)(void *key, void *context,
153 * void *user_context);
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.
162 typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
164 /* Simple hash table interface */
166 /****f* silcutil/SilcHashTableAPI/silc_hash_table_alloc
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,
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
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,
199 /****f* silcutil/SilcHashTableAPI/silc_hash_table_free
203 * void silc_hash_table_free(SilcHashTable ht);
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.
211 void silc_hash_table_free(SilcHashTable ht);
213 /****f* silcutil/SilcHashTableAPI/silc_hash_table_size
217 * uint32 silc_hash_table_size(SilcHashTable ht);
221 * Returns the size of the hash table. This is the true size of the
225 uint32 silc_hash_table_size(SilcHashTable ht);
227 /****f* silcutil/SilcHashTableAPI/silc_hash_table_count
231 * uint32 silc_hash_table_count(SilcHashTable ht);
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.
240 uint32 silc_hash_table_count(SilcHashTable ht);
242 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add
246 * void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
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).
256 void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
258 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace
262 * void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
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.
272 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
274 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del
278 * bool silc_hash_table_del(SilcHashTable ht, void *key);
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.
287 bool silc_hash_table_del(SilcHashTable ht, void *key);
289 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context
293 * bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
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.
304 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
307 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find
311 * bool silc_hash_table_find(SilcHashTable ht, void *key,
312 * void **ret_key, void **ret_context);
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.
323 bool silc_hash_table_find(SilcHashTable ht, void *key,
324 void **ret_key, void **ret_context);
326 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach
330 * void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
331 * SilcHashForeach foreach,
332 * void *user_context);
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.
342 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
343 SilcHashForeach foreach, void *user_context);
345 /****f* silcutil/SilcHashTableAPI/silc_hash_table_foreach
349 * void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
350 * void *user_context);
354 * Traverse all entrys in the hash table and call the `foreach' for
355 * every entry with the `user_context' context.
358 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
361 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash
365 * void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
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
375 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
377 /****f* silcutil/SilcHashTableAPI/silc_hash_table_list
381 * void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
385 * Prepares the `htl' SilcHashTableList sent as argument to be used in the
386 * hash table traversing with the silc_hash_table_get.
389 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl);
391 /****f* silcutil/SilcHashTableAPI/silc_hash_table_get
395 * bool silc_hash_table_get(SilcHashTableList *htl, void **key,
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
405 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context);
408 /* Extended hash table interface (same as above but with specific
409 hash and comparison functions). */
411 /****f* silcutil/SilcHashTableAPI/silc_hash_table_add_ext
415 * void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
416 * SilcHashFunction hash,
417 * void *hash_user_context);
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).
426 * The `hash' and `hash_user_context' are application specified hash
427 * function. If not provided the hash table's default is used.
430 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
431 SilcHashFunction hash, void *hash_user_context);
433 /****f* silcutil/SilcHashTableAPI/silc_hash_table_replace_ext
437 * void silc_hash_table_replace_ext(SilcHashTable ht, void *key,
439 * SilcHashFunction hash,
440 * void *hash_user_context);
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.
449 * The `hash' and `hash_user_context' are application specified hash
450 * function. If not provided the hash table's default is used.
453 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
454 SilcHashFunction hash,
455 void *hash_user_context);
457 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext
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);
469 * Removes the entry from the hash table by the provided `key'. This will
470 * call the destructor funtion for the found entry. Return TRUE if the
471 * entry was removed successfully and FALSE otherwise.
473 * The `hash' and `hash_user_context' are application specified hash
474 * function. If not provided the hash table's default is used.
475 * The `compare' and `compare_user_context' are application specified
476 * comparing function. If not provided the hash table's default is used.
479 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
480 SilcHashFunction hash,
481 void *hash_user_context,
482 SilcHashCompare compare,
483 void *compare_user_context);
485 /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext
489 * bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
491 * SilcHashFunction hash,
492 * void *hash_user_context,
493 * SilcHashCompare compare,
494 * void *compare_user_context);
498 * Same as silc_hash_table_del but verifies that the context associated
499 * with the `key' matches the `context'. This is handy to use with hash
500 * tables that may have duplicate keys. In that case the `context' may
501 * be used to check whether the correct entry is being deleted.
503 * The `hash' and `hash_user_context' are application specified hash
504 * function. If not provided the hash table's default is used.
505 * The `compare' and `compare_user_context' are application specified
506 * comparing function. If not provided the hash table's default is used.
509 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
511 SilcHashFunction hash,
512 void *hash_user_context,
513 SilcHashCompare compare,
514 void *compare_user_context);
516 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext
520 * bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
521 * void **ret_key, void **ret_context,
522 * SilcHashFunction hash,
523 * void *hash_user_context,
524 * SilcHashCompare compare,
525 * void *compare_user_context);
529 * Finds the entry in the hash table by the provided `key' as fast as
530 * possible. Return TRUE if the entry was found and FALSE otherwise.
531 * The found entry is returned to the `ret_key' and `ret_context',
532 * respectively. If the `ret_key and `ret_context' are NULL then this
533 * maybe used only to check whether given key exists in the table.
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.
541 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
542 void **ret_key, void **ret_context,
543 SilcHashFunction hash,
544 void *hash_user_context,
545 SilcHashCompare compare,
546 void *compare_user_context);
548 /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext
552 * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
553 * SilcHashFunction hash,
554 * void *hash_user_context,
555 * SilcHashCompare compare,
556 * void *compare_user_context,
557 * SilcHashForeach foreach,
558 * void *foreach_user_context);
562 * As the hash table is collision resistant it is possible to save duplicate
563 * keys to the hash table. This function can be used to find all keys
564 * and contexts from the hash table that are found using the `key'. The
565 * `foreach' is called for every found key.
567 * The `hash' and `hash_user_context' are application specified hash
568 * function. If not provided the hash table's default is used.
569 * The `compare' and `compare_user_context' are application specified
570 * comparing function. If not provided the hash table's default is used.
573 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
574 SilcHashFunction hash,
575 void *hash_user_context,
576 SilcHashCompare compare,
577 void *compare_user_context,
578 SilcHashForeach foreach,
579 void *foreach_user_context);
581 /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext
585 * void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
586 * SilcHashFunction hash,
587 * void *hash_user_context);
591 * Rehashs the hash table. The size of the new hash table is provided
592 * as `new_size'. If the `new_size' is zero then this routine will make
593 * the new table of a suitable size. Note that this operation may be
596 * The `hash' and `hash_user_context' are application specified hash
597 * function. If not provided the hash table's default is used.
600 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
601 SilcHashFunction hash,
602 void *hash_user_context);