/****************************************************************** * $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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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: * \*--------------------------------------------------------------------------*/ 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 */