X-Git-Url: http://git.silcnet.org/gitweb/?a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilchashtable.h;h=612038034c9f4c38414c0e8e2f9e75cd4f87d860;hb=c257b555225193e54d85daf541d29578b3c93882;hp=9578965b918e1b8d4c3bdb19603f64b0677705ce;hpb=b74b6d75c86bb03e3ef291f60f89ccc01164ad88;p=silc.git diff --git a/lib/silcutil/silchashtable.h b/lib/silcutil/silchashtable.h index 9578965b..61203803 100644 --- a/lib/silcutil/silchashtable.h +++ b/lib/silcutil/silchashtable.h @@ -1,24 +1,23 @@ -/****h* silcutil/silchashtable.h - * - * NAME - * - * silchashtable.h - * - * COPYRIGHT - * - * Author: Pekka Riikonen - * - * Copyright (C) 2001 Pekka Riikonen - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. +/* + + silchashtable.h + + Author: Pekka Riikonen + + Copyright (C) 2001 - 2003 Pekka Riikonen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + +*/ + +/****h* silcutil/SILC Hash Table Interface * * DESCRIPTION * @@ -34,7 +33,7 @@ * an extended interface where caller can specify its own hash and comparison * functions. * - * There are two ways tro traverse the entire hash table if this feature + * There are two ways to traverse the entire hash table if this feature * is needed. There exists a foreach function that calls a foreach * callback for each entry in the hash table. Other way is to use * SilcHashTableList structure and traverse the hash table inside while() @@ -48,7 +47,7 @@ /****s* silcutil/SilcHashTableAPI/SilcHashTable * * NAME - * + * * typedef struct SilcHashTableStruct *SilcHashTable; * * DESCRIPTION @@ -64,13 +63,13 @@ typedef struct SilcHashTableStruct *SilcHashTable; /****s* silcutil/SilcHashTableAPI/SilcHashTableList * * NAME - * + * * typedef struct SilcHashTableListStruct SilcHashTableList; * * DESCRIPTION * * This structure is used to tarverse the hash table. This structure - * is given as argument to the silc_hash_table_list function to + * is given as argument to the silc_hash_table_list function to * initialize it and then used to traverse the hash table with the * silc_hash_table_get function. It needs not be allocated or freed. * @@ -80,6 +79,7 @@ typedef struct SilcHashTableStruct *SilcHashTable; * silc_hash_table_list(hash_table, &htl); * while (silc_hash_table_get(&htl, (void *)&key, (void *)&context)) * ... + * silc_hash_table_list_reset(&htl); * * SOURCE */ @@ -89,7 +89,8 @@ typedef struct SilcHashTableListStruct SilcHashTableList; struct SilcHashTableListStruct { SilcHashTable ht; void *entry; - uint32 index; + unsigned int index : 31; + unsigned int auto_rehash : 1; }; /***/ @@ -97,7 +98,7 @@ struct SilcHashTableListStruct { * * SYNOPSIS * - * typedef uint32 (*SilcHashFunction)(void *key, void *user_context); + * typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context); * * DESCRIPTION * @@ -107,13 +108,13 @@ struct SilcHashTableListStruct { * to the callback. * ***/ -typedef uint32 (*SilcHashFunction)(void *key, void *user_context); +typedef SilcUInt32 (*SilcHashFunction)(void *key, void *user_context); /****f* silcutil/SilcHashTableAPI/SilcHashCompare * * SYNOPSIS * - * typedef bool (*SilcHashCompare)(void *key1, void *key2, + * typedef bool (*SilcHashCompare)(void *key1, void *key2, * void *user_context); * * DESCRIPTION @@ -131,25 +132,25 @@ typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context); * * SYNOPSIS * - * typedef void (*SilcHashDestructor)(void *key, void *context, + * typedef void (*SilcHashDestructor)(void *key, void *context, * void *user_context); * * DESCRIPTION * - * A destructor callback that the library will call to destroy the - * `key' and `context'. The appliation provides the function when + * A destructor callback that the library will call to destroy the + * `key' and `context'. The application provides the function when * allocating a new hash table. The `user_context' is application * specific context and is delivered to the callback. * ***/ -typedef void (*SilcHashDestructor)(void *key, void *context, +typedef void (*SilcHashDestructor)(void *key, void *context, void *user_context); /****f* silcutil/SilcHashTableAPI/SilcHashForeach * * SYNOPSIS * - * typedef void (*SilcHashForeach)(void *key, void *context, + * typedef void (*SilcHashForeach)(void *key, void *context, * void *user_context); * * DESCRIPTION @@ -167,7 +168,7 @@ typedef void (*SilcHashForeach)(void *key, void *context, void *user_context); * * SYNOPSIS * - * SilcHashTable silc_hash_table_alloc(uint32 table_size, + * SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size, * SilcHashFunction hash, * void *hash_user_context, * SilcHashCompare compare, @@ -187,7 +188,7 @@ typedef void (*SilcHashForeach)(void *key, void *context, void *user_context); * are optional. * ***/ -SilcHashTable silc_hash_table_alloc(uint32 table_size, +SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size, SilcHashFunction hash, void *hash_user_context, SilcHashCompare compare, @@ -214,7 +215,7 @@ void silc_hash_table_free(SilcHashTable ht); * * SYNOPSIS * - * uint32 silc_hash_table_size(SilcHashTable ht); + * SilcUInt32 silc_hash_table_size(SilcHashTable ht); * * DESCRIPTION * @@ -222,13 +223,13 @@ void silc_hash_table_free(SilcHashTable ht); * hash table. * ***/ -uint32 silc_hash_table_size(SilcHashTable ht); +SilcUInt32 silc_hash_table_size(SilcHashTable ht); /****f* silcutil/SilcHashTableAPI/silc_hash_table_count * * SYNOPSIS * - * uint32 silc_hash_table_count(SilcHashTable ht); + * SilcUInt32 silc_hash_table_count(SilcHashTable ht); * * DESCRIPTION * @@ -237,7 +238,7 @@ uint32 silc_hash_table_size(SilcHashTable ht); * silc_hash_table_rehash is recommended. * ***/ -uint32 silc_hash_table_count(SilcHashTable ht); +SilcUInt32 silc_hash_table_count(SilcHashTable ht); /****f* silcutil/SilcHashTableAPI/silc_hash_table_add * @@ -264,7 +265,7 @@ void silc_hash_table_add(SilcHashTable ht, void *key, void *context); * DESCRIPTION * * Same as silc_hash_table_add but if the `key' already exists in the - * hash table the old key and the old context will be replace with the + * hash table the old key and the old context will be replaced with the * `key' and the `context. The destructor function will be called for the * replaced key and context. * @@ -290,7 +291,7 @@ bool silc_hash_table_del(SilcHashTable ht, void *key); * * SYNOPSIS * - * bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, + * bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, * void *context); * * DESCRIPTION @@ -301,7 +302,7 @@ bool silc_hash_table_del(SilcHashTable ht, void *key); * be used to check whether the correct entry is being deleted. * ***/ -bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, +bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, void *context); /****f* silcutil/SilcHashTableAPI/silc_hash_table_find @@ -314,7 +315,7 @@ bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, * DESCRIPTION * * Finds the entry in the hash table by the provided `key' as fast as - * possible. Return TRUE if the entry was found and FALSE otherwise. + * possible. Return TRUE if the entry was found and FALSE otherwise. * The found entry is returned to the `ret_key' and `ret_context', * respectively. If the `ret_key and `ret_context' are NULL then this * maybe used only to check whether given key exists in the table. @@ -323,12 +324,33 @@ bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, bool silc_hash_table_find(SilcHashTable ht, void *key, void **ret_key, void **ret_context); +/****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context + * + * SYNOPSIS + * + * bool silc_hash_table_find_by_context(SilcHashTable ht, void *key, + * void *context, void **ret_key); + * + * DESCRIPTION + * + * Finds the entry in the hash table by the provided `key' and + * `context' as fast as possible. This is handy function when there + * can be multiple same keys in the hash table. By using this function + * the specific key with specific context can be found. Return + * TRUE if the entry with the key and context was found and FALSE + * otherwise. The function returns only the key to `ret_key' since + * the caller already knows the context. + * + ***/ +bool silc_hash_table_find_by_context(SilcHashTable ht, void *key, + void *context, void **ret_key); + /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach * * SYNOPSIS * * void silc_hash_table_find_foreach(SilcHashTable ht, void *key, - * SilcHashForeach foreach, + * SilcHashForeach foreach, * void *user_context); * * DESCRIPTION @@ -336,7 +358,15 @@ bool silc_hash_table_find(SilcHashTable ht, void *key, * As the hash table is collision resistant it is possible to save duplicate * keys to the hash table. This function can be used to find all keys * and contexts from the hash table that are found using the `key'. The - * `foreach' is called for every found key. + * `foreach' is called for every found key. If no entries can be found + * the `foreach' will be called once with the context set NULL and + * `key' and `user_context' sent to the function. + * + * NOTES + * + * The hash table will not be rehashed during the traversing of the table, + * even if the table was marked as auto rehashable. The caller also must + * not call silc_hash_table_rehash while traversing the table. * ***/ void silc_hash_table_find_foreach(SilcHashTable ht, void *key, @@ -354,6 +384,12 @@ void silc_hash_table_find_foreach(SilcHashTable ht, void *key, * Traverse all entrys in the hash table and call the `foreach' for * every entry with the `user_context' context. * + * NOTES + * + * The hash table will not be rehashed during the traversing of the table, + * even if the table was marked as auto rehashable. The caller also must + * not call silc_hash_table_rehash while traversing the table. + * ***/ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, void *user_context); @@ -362,7 +398,7 @@ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, * * SYNOPSIS * - * void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); + * void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size); * * DESCRIPTION * @@ -372,7 +408,7 @@ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, * very slow. * ***/ -void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); +void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size); /****f* silcutil/SilcHashTableAPI/silc_hash_table_list * @@ -383,16 +419,38 @@ void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); * DESCRIPTION * * Prepares the `htl' SilcHashTableList sent as argument to be used in the - * hash table traversing with the silc_hash_table_get. + * hash table traversing with the silc_hash_table_get. After the hash + * table traversing is completed the silc_hash_table_list_reset must be + * called. + * + * NOTES + * + * The hash table will not be rehashed during the traversing of the list, + * even if the table was marked as auto rehashable. The caller also must + * not call silc_hash_table_rehash while traversing the list. * ***/ void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl); +/****f* silcutil/SilcHashTableAPI/silc_hash_table_list_reset + * + * SYNOPSIS + * + * void silc_hash_table_list_reset(SilcHashTableList *htl); + * + * DESCRIPTION + * + * Resets the `htl' SilcHashTableList. This must be called after the + * hash table traversing is completed. + * + ***/ +void silc_hash_table_list_reset(SilcHashTableList *htl); + /****f* silcutil/SilcHashTableAPI/silc_hash_table_get * * SYNOPSIS * - * bool silc_hash_table_get(SilcHashTableList *htl, void **key, + * bool silc_hash_table_get(SilcHashTableList *htl, void **key, * void **context); * * DESCRIPTION @@ -413,7 +471,7 @@ bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context); * SYNOPSIS * * void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context); * * DESCRIPTION @@ -434,15 +492,15 @@ void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, * * SYNOPSIS * - * void silc_hash_table_replace_ext(SilcHashTable ht, void *key, + * void silc_hash_table_replace_ext(SilcHashTable ht, void *key, * void *context, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context); * * DESCRIPTION * * Same as silc_hash_table_add_ext but if the `key' already exists in the - * hash table the old key and the old context will be replace with the + * hash table the old key and the old context will be replaced with the * `key' and the `context. The destructor function will be called for the * replaced key and context. * @@ -451,7 +509,7 @@ void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, * ***/ void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, - SilcHashFunction hash, + SilcHashFunction hash, void *hash_user_context); /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_ext @@ -459,10 +517,12 @@ void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, * SYNOPSIS * * bool silc_hash_table_del_ext(SilcHashTable ht, void *key, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context, - * SilcHashCompare compare, - * void *compare_user_context); + * SilcHashCompare compare, + * void *compare_user_context, + * SilcHashDestructor destructor, + * void *destructor_user_context); * * DESCRIPTION * @@ -474,24 +534,30 @@ void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, * function. If not provided the hash table's default is used. * The `compare' and `compare_user_context' are application specified * comparing function. If not provided the hash table's default is used. + * The `destructor' and `destructor_user_context' are application + * specific destructor function. * ***/ bool silc_hash_table_del_ext(SilcHashTable ht, void *key, - SilcHashFunction hash, + SilcHashFunction hash, void *hash_user_context, - SilcHashCompare compare, - void *compare_user_context); + SilcHashCompare compare, + void *compare_user_context, + SilcHashDestructor destructor, + void *destructor_user_context); /****f* silcutil/SilcHashTableAPI/silc_hash_table_del_by_context_ext * * SYNOPSIS * - * bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, + * bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, * void *context, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context, - * SilcHashCompare compare, - * void *compare_user_context); + * SilcHashCompare compare, + * void *compare_user_context, + * SilcHashDestructor destructor, + * void *destructor_user_context); * * DESCRIPTION * @@ -504,14 +570,18 @@ bool silc_hash_table_del_ext(SilcHashTable ht, void *key, * function. If not provided the hash table's default is used. * The `compare' and `compare_user_context' are application specified * comparing function. If not provided the hash table's default is used. + * The `destructor' and `destructor_user_context' are application + * specific destructor function. * ***/ -bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, +bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, void *context, - SilcHashFunction hash, + SilcHashFunction hash, void *hash_user_context, - SilcHashCompare compare, - void *compare_user_context); + SilcHashCompare compare, + void *compare_user_context, + SilcHashDestructor destructor, + void *destructor_user_context); /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_ext * @@ -519,15 +589,15 @@ bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, * * bool silc_hash_table_find_ext(SilcHashTable ht, void *key, * void **ret_key, void **ret_context, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context, - * SilcHashCompare compare, + * SilcHashCompare compare, * void *compare_user_context); * * DESCRIPTION * * Finds the entry in the hash table by the provided `key' as fast as - * possible. Return TRUE if the entry was found and FALSE otherwise. + * possible. Return TRUE if the entry was found and FALSE otherwise. * The found entry is returned to the `ret_key' and `ret_context', * respectively. If the `ret_key and `ret_context' are NULL then this * maybe used only to check whether given key exists in the table. @@ -540,21 +610,55 @@ bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, ***/ bool silc_hash_table_find_ext(SilcHashTable ht, void *key, void **ret_key, void **ret_context, - SilcHashFunction hash, + SilcHashFunction hash, void *hash_user_context, - SilcHashCompare compare, + SilcHashCompare compare, void *compare_user_context); +/****f* silcutil/SilcHashTableAPI/silc_hash_table_find_by_context_ext + * + * SYNOPSIS + * + * bool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key, + * void *context, void **ret_key, + * SilcHashFunction hash, + * void *hash_user_context, + * SilcHashCompare compare, + * void *compare_user_context); + * + * DESCRIPTION + * + * Finds the entry in the hash table by the provided `key' and + * `context' as fast as possible. This is handy function when there + * can be multiple same keys in the hash table. By using this function + * the specific key with specific context can be found. Return + * TRUE if the entry with the key and context was found and FALSE + * otherwise. The function returns only the key to `ret_key' since + * the caller already knows the context. + * + * The `hash' and `hash_user_context' are application specified hash + * function. If not provided the hash table's default is used. + * The `compare' and `compare_user_context' are application specified + * comparing function. If not provided the hash table's default is used. + * + ***/ +bool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key, + void *context, void **ret_key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context); + /****f* silcutil/SilcHashTableAPI/silc_hash_table_find_foreach_ext * * SYNOPSIS * * void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key, - * SilcHashFunction hash, + * SilcHashFunction hash, * void *hash_user_context, - * SilcHashCompare compare, + * SilcHashCompare compare, * void *compare_user_context, - * SilcHashForeach foreach, + * SilcHashForeach foreach, * void *foreach_user_context); * * DESCRIPTION @@ -562,28 +666,36 @@ bool silc_hash_table_find_ext(SilcHashTable ht, void *key, * As the hash table is collision resistant it is possible to save duplicate * keys to the hash table. This function can be used to find all keys * and contexts from the hash table that are found using the `key'. The - * `foreach' is called for every found key. + * `foreach' is called for every found key. If no entries can be found + * the `foreach' will be called once with the context set NULL and + * `key' and `user_context' sent to the function. * * The `hash' and `hash_user_context' are application specified hash * function. If not provided the hash table's default is used. * The `compare' and `compare_user_context' are application specified * comparing function. If not provided the hash table's default is used. * + * NOTES + * + * The hash table will not be rehashed during the traversing of the table, + * even if the table was marked as auto rehashable. The caller also must + * not call silc_hash_table_rehash while traversing the table. + * ***/ void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key, - SilcHashFunction hash, + SilcHashFunction hash, void *hash_user_context, - SilcHashCompare compare, + SilcHashCompare compare, void *compare_user_context, - SilcHashForeach foreach, + SilcHashForeach foreach, void *foreach_user_context); /****f* silcutil/SilcHashTableAPI/silc_hash_table_rehash_ext * * SYNOPSIS * - * void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size, - * SilcHashFunction hash, + * void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size, + * SilcHashFunction hash, * void *hash_user_context); * * DESCRIPTION @@ -597,8 +709,8 @@ void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key, * function. If not provided the hash table's default is used. * ***/ -void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size, - SilcHashFunction hash, +void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size, + SilcHashFunction hash, void *hash_user_context); #endif