diff options
Diffstat (limited to 'utils/hashtable.h')
| -rwxr-xr-x | utils/hashtable.h | 451 |
1 files changed, 451 insertions, 0 deletions
diff --git a/utils/hashtable.h b/utils/hashtable.h new file mode 100755 index 0000000..66f9fbf --- /dev/null +++ b/utils/hashtable.h @@ -0,0 +1,451 @@ +/****************************************************************** +* $Id: hashtable.h,v 1.1 2004/10/29 09:28:25 snowdrop Exp $ +* +* CSOAP Project: A http client/server library in C +* Copyright (C) 2003-2004 Ferhat Ayaz +* +* This library is free software; you can redistribute it and/or +* modify it under the terms of the GNU Library General Public +* License as published by the Free Software Foundation; either +* version 2 of the License, or (at your option) any later version. +* +* This library 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 +* Library General Public License for more details. +* +* You should have received a copy of the GNU Library General Public +* License along with this library; if not, write to the +* Free Software Foundation, Inc., 59 Temple Place - Suite 330, +* Boston, MA 02111-1307, USA. +* +* Email: ferhatayaz@yahoo.com +******************************************************************/ +#ifndef UTILS_HASHTABLE_H +#define UTILS_HASHTABLE_H + +/* These structs should not be accessed directly from user code. + * All access should be via the public functions declared below. */ + +typedef struct _hashpair { + const void *key; + void *value; + struct _hashpair *next; +} hashpair_t; + +typedef struct { + long numOfBuckets; + long numOfElements; + hashpair_t **bucketArray; + float idealRatio, lowerRehashThreshold, upperRehashThreshold; + int (*keycmp)(const void *key1, const void *key2); + int (*valuecmp)(const void *value1, const void *value2); + unsigned long (*hashFunction)(const void *key); + void (*keyDeallocator)(void *key); + void (*valueDeallocator)(void *value); +} hashtable_t; + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_create() - creates a new HashTable + * DESCRIPTION: + * Creates a new HashTable. When finished with this HashTable, it + * should be explicitly destroyed by calling the hashtable_destroy() + * function. + * EFFICIENCY: + * O(1) + * ARGUMENTS: + * numOfBuckets - the number of buckets to start the HashTable out with. + * Must be greater than zero, and should be prime. + * Ideally, the number of buckets should between 1/5 + * and 1 times the expected number of elements in the + * HashTable. Values much more or less than this will + * result in wasted memory or decreased performance + * respectively. The number of buckets in a HashTable + * can be re-calculated to an appropriate number by + * calling the hashtable_rehash() function once the + * HashTable has been populated. The number of buckets + * in a HashTable may also be re-calculated + * automatically if the ratio of elements to buckets + * passes the thresholds set by hashtable_set_ideal_ration(). + * RETURNS: + * HashTable - a new Hashtable, or NULL on error +\*--------------------------------------------------------------------------*/ + +hashtable_t *hashtable_create(long numOfBuckets); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_destroy() - destroys an existing HashTable + * DESCRIPTION: + * Destroys an existing HashTable. + * EFFICIENCY: + * O(n) + * ARGUMENTS: + * hashTable - the HashTable to destroy + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_destroy(hashtable_t *hashTable); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_contains_key() - checks the existence of a key in a HashTable + * DESCRIPTION: + * Determines whether or not the specified HashTable contains the + * specified key. Uses the comparison function specified by + * hashtable_set_key_comparision_function(). + * EFFICIENCY: + * O(1), assuming a good hash function and element-to-bucket ratio + * ARGUMENTS: + * hashTable - the HashTable to search + * key - the key to search for + * RETURNS: + * bool - whether or not the specified HashTable contains the + * specified key. +\*--------------------------------------------------------------------------*/ + +int hashtable_contains_key(const hashtable_t *hashTable, const void *key); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_contains_value() + * - checks the existence of a value in a HashTable + * DESCRIPTION: + * Determines whether or not the specified HashTable contains the + * specified value. Unlike hashtable_contains_key(), this function is + * not very efficient, since it has to scan linearly looking for a + * match. Uses the comparison function specified by + * hashtable_set_value_comparision_function(). + * EFFICIENCY: + * O(n) + * ARGUMENTS: + * hashTable - the HashTable to search + * value - the value to search for + * RETURNS: + * bool - whether or not the specified HashTable contains the + * specified value. +\*--------------------------------------------------------------------------*/ + +int hashtable_contains_value(const hashtable_t *hashTable, const void *value); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_put() - adds a key/value pair to a HashTable + * DESCRIPTION: + * Adds the specified key/value pair to the specified HashTable. If + * the key already exists in the HashTable (determined by the comparison + * function specified by hashtable_set_key_comparision_function()), its value + * is replaced by the new value. May trigger an auto-rehash (see + * hashtable_set_ideal_ration()). It is illegal to specify NULL as the + * key or value. + * EFFICIENCY: + * O(1), assuming a good hash function and element-to-bucket ratio + * ARGUMENTS: + * hashTable - the HashTable to add to + * key - the key to add or whose value to replace + * value - the value associated with the key + * RETURNS: + * err - 0 if successful, -1 if an error was encountered +\*--------------------------------------------------------------------------*/ + +int hashtable_put(hashtable_t *hashTable, const void *key, void *value); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_get() - retrieves the value of a key in a HashTable + * DESCRIPTION: + * Retrieves the value of the specified key in the specified HashTable. + * Uses the comparison function specified by + * hashtable_set_key_comparision_function(). + * EFFICIENCY: + * O(1), assuming a good hash function and element-to-bucket ratio + * ARGUMENTS: + * hashTable - the HashTable to search + * key - the key whose value is desired + * RETURNS: + * void * - the value of the specified key, or NULL if the key + * doesn't exist in the HashTable +\*--------------------------------------------------------------------------*/ + +void *hashtable_get(const hashtable_t *hashTable, const void *key); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_remove() - removes a key/value pair from a HashTable + * DESCRIPTION: + * Removes the key/value pair identified by the specified key from the + * specified HashTable if the key exists in the HashTable. May trigger + * an auto-rehash (see hashtable_set_ideal_ration()). + * EFFICIENCY: + * O(1), assuming a good hash function and element-to-bucket ratio + * ARGUMENTS: + * hashTable - the HashTable to remove the key/value pair from + * key - the key specifying the key/value pair to be removed + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_remove(hashtable_t *hashTable, const void *key); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_remove_all() - removes all key/value pairs from a HashTable + * DESCRIPTION: + * Removes all key/value pairs from the specified HashTable. May trigger + * an auto-rehash (see hashtable_set_ideal_ration()). + * EFFICIENCY: + * O(n) + * ARGUMENTS: + * hashTable - the HashTable to remove all key/value pairs from + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_remove_all(hashtable_t *hashTable); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_is_empty() - determines if a HashTable is empty + * DESCRIPTION: + * Determines whether or not the specified HashTable contains any + * key/value pairs. + * EFFICIENCY: + * O(1) + * ARGUMENTS: + * hashTable - the HashTable to check + * RETURNS: + * bool - whether or not the specified HashTable contains any + * key/value pairs +\*--------------------------------------------------------------------------*/ + +int hashtable_is_empty(const hashtable_t *hashTable); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_size() - returns the number of elements in a HashTable + * DESCRIPTION: + * Returns the number of key/value pairs that are present in the + * specified HashTable. + * EFFICIENCY: + * O(1) + * ARGUMENTS: + * hashTable - the HashTable whose size is requested + * RETURNS: + * long - the number of key/value pairs that are present in + * the specified HashTable +\*--------------------------------------------------------------------------*/ + +long hashtable_size(const hashtable_t *hashTable); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_getNumBuckets() - returns the number of buckets in a HashTable + * DESCRIPTION: + * Returns the number of buckets that are in the specified HashTable. + * This may change dynamically throughout the life of a HashTable if + * automatic or manual rehashing is performed. + * EFFICIENCY: + * O(1) + * ARGUMENTS: + * hashTable - the HashTable whose number of buckets is requested + * RETURNS: + * long - the number of buckets that are in the specified + * HashTable +\*--------------------------------------------------------------------------*/ + +long hashtable_get_num_buckets(const hashtable_t *hashTable); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_set_key_comparision_function() + * - specifies the function used to compare keys in a HashTable + * DESCRIPTION: + * Specifies the function used to compare keys in the specified + * HashTable. The specified function should return zero if the two + * keys are considered equal, and non-zero otherwise. The default + * function is one that simply compares pointers. + * ARGUMENTS: + * hashTable - the HashTable whose key comparison function is being + * specified + * keycmp - a function which returns zero if the two arguments + * passed to it are considered "equal" keys and non-zero + * otherwise + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_set_key_comparision_function(hashtable_t *hashTable, + int (*keycmp)(const void *key1, const void *key2)); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_set_value_comparision_function() + * - specifies the function used to compare values in a HashTable + * DESCRIPTION: + * Specifies the function used to compare values in the specified + * HashTable. The specified function should return zero if the two + * values are considered equal, and non-zero otherwise. The default + * function is one that simply compares pointers. + * ARGUMENTS: + * hashTable - the HashTable whose value comparison function is being + * specified + * valuecmp - a function which returns zero if the two arguments + * passed to it are considered "equal" values and non-zero + * otherwise + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_set_value_comparision_function(hashtable_t *hashTable, + int (*valuecmp)(const void *value1, const void *value2)); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_set_hashfunction() + * - specifies the hash function used by a HashTable + * DESCRIPTION: + * Specifies the function used to determine the hash value for a key + * in the specified HashTable (before modulation). An ideal hash + * function is one which is easy to compute and approximates a + * "random" function. The default function is one that works + * relatively well for pointers. If the HashTable keys are to be + * strings (which is probably the case), then this default function + * will not suffice, in which case consider using the provided + * hashtable_string_hash_function() function. + * ARGUMENTS: + * hashTable - the HashTable whose hash function is being specified + * hashFunction - a function which returns an appropriate hash code + * for a given key + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_set_hashfunction(hashtable_t *hashTable, + unsigned long (*hashFunction)(const void *key)); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_rehash() - reorganizes a HashTable to be more efficient + * DESCRIPTION: + * Reorganizes a HashTable to be more efficient. If a number of + * buckets is specified, the HashTable is rehashed to that number of + * buckets. If 0 is specified, the HashTable is rehashed to a number + * of buckets which is automatically calculated to be a prime number + * that achieves (as closely as possible) the ideal element-to-bucket + * ratio specified by the hashtable_set_ideal_ration() function. + * EFFICIENCY: + * O(n) + * ARGUMENTS: + * hashTable - the HashTable to be reorganized + * numOfBuckets - the number of buckets to rehash the HashTable to. + * Should be prime. Ideally, the number of buckets + * should be between 1/5 and 1 times the expected + * number of elements in the HashTable. Values much + * more or less than this will result in wasted memory + * or decreased performance respectively. If 0 is + * specified, an appropriate number of buckets is + * automatically calculated. + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_rehash(hashtable_t *hashTable, long numOfBuckets); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_set_ideal_ration() + * - sets the ideal element-to-bucket ratio of a HashTable + * DESCRIPTION: + * Sets the ideal element-to-bucket ratio, as well as the lower and + * upper auto-rehash thresholds, of the specified HashTable. Note + * that this function doesn't actually perform a rehash. + * + * The default values for these properties are 3.0, 0.0 and 15.0 + * respectively. This is likely fine for most situations, so there + * is probably no need to call this function. + * ARGUMENTS: + * hashTable - a HashTable + * idealRatio - the ideal element-to-bucket ratio. When a rehash + * occurs (either manually via a call to the + * hashtable_rehash() function or automatically due the + * the triggering of one of the thresholds below), the + * number of buckets in the HashTable will be + * recalculated to be a prime number that achieves (as + * closely as possible) this ideal ratio. Must be a + * positive number. + * lowerRehashThreshold + * - the element-to-bucket ratio that is considered + * unacceptably low (i.e., too few elements per bucket). + * If the actual ratio falls below this number, a + * rehash will automatically be performed. Must be + * lower than the value of idealRatio. If no ratio + * is considered unacceptably low, a value of 0.0 can + * be specified. + * upperRehashThreshold + * - the element-to-bucket ratio that is considered + * unacceptably high (i.e., too many elements per bucket). + * If the actual ratio rises above this number, a + * rehash will automatically be performed. Must be + * higher than idealRatio. However, if no ratio + * is considered unacceptably high, a value of 0.0 can + * be specified. + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_set_ideal_ration(hashtable_t *hashTable, float idealRatio, + float lowerRehashThreshold, + float upperRehashThreshold); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_set_deallocation_function() + * - sets the key and value deallocation functions of a HashTable + * DESCRIPTION: + * Sets the key and value deallocation functions of the specified + * HashTable. This determines what happens to a key or a value when it + * is removed from the HashTable. If the deallocation function is NULL + * (the default if this function is never called), its reference is + * simply dropped and it is up to the calling program to perform the + * proper memory management. If the deallocation function is non-NULL, + * it is called to free the memory used by the object. E.g., for simple + * objects, an appropriate deallocation function may be free(). + * + * This affects the behaviour of the hashtable_destroy(), hashtable_put(), + * hashtable_remove() and hashtable_remove_all() functions. + * ARGUMENTS: + * hashTable - a HashTable + * keyDeallocator + * - if non-NULL, the function to be called when a key is + * removed from the HashTable. + * valueDeallocator + * - if non-NULL, the function to be called when a value is + * removed from the HashTable. + * RETURNS: + * <nothing> +\*--------------------------------------------------------------------------*/ + +void hashtable_set_deallocation_function(hashtable_t *hashTable, + void (*keyDeallocator)(void *key), + void (*valueDeallocator)(void *value)); + +/*--------------------------------------------------------------------------*\ + * NAME: + * hashtable_string_hash_function() - a good hash function for strings + * DESCRIPTION: + * A hash function that is appropriate for hashing strings. Note that + * this is not the default hash function. To make it the default hash + * function, call hashtable_set_hashfunction(hashtable_string_hash_function). + * ARGUMENTS: + * key - the key to be hashed + * RETURNS: + * long - the unmodulated hash value of the key +\*--------------------------------------------------------------------------*/ + +unsigned long hashtable_string_hash_function(const void *key); + +#endif /* UTILS_HASHTABLE_H */ + + |