Index: /trunk/psLib/src/collections/Makefile =================================================================== --- /trunk/psLib/src/collections/Makefile (revision 1419) +++ /trunk/psLib/src/collections/Makefile (revision 1420) @@ -3,6 +3,6 @@ ## Makefile: collections ## -## $Revision: 1.27 $ $Name: not supported by cvs2svn $ -## $Date: 2004-07-29 21:43:11 $ +## $Revision: 1.28 $ $Name: not supported by cvs2svn $ +## $Date: 2004-08-09 20:29:43 $ ## ## Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -35,5 +35,6 @@ psScalar.o \ psCompare.o \ - psArray.o + psArray.o \ + psHash.o OBJS = $(addprefix makedir/,$(SRC_OBJS)) Index: /trunk/psLib/src/collections/psHash.c =================================================================== --- /trunk/psLib/src/collections/psHash.c (revision 1420) +++ /trunk/psLib/src/collections/psHash.c (revision 1420) @@ -0,0 +1,408 @@ + +/** @file psHash.c +* +* @brief Contains support for basic hashing functions. +* +* This file will hold the functions for defining a hash table with arbitrary +* data types, allocating/deallocating that hash table, adding and removing +* data from that hash table, and listing all keys defined in the hash table. +* +* @author Robert Lupton, Princeton University +* @author George Gusciora, MHPCC +* +* @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ +* @date $Date: 2004-08-09 20:29:43 $ +* +* Copyright 2004 Maui High Performance Computing Center, University of Hawaii +*/ +#include +#include +#include +#include +#include "psHash.h" +#include "psMemory.h" +#include "psString.h" +#include "psTrace.h" +#include "psAbort.h" + +static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next); +static void hashBucketFree(psHashBucket * bucket); +static void *doHashWork(psHash * table, const char *key, void *data, bool remove + ); +static void hashFree(psHash * table); + +/****************************************************************************** +psHashKeyList(table): this function creates a linked list with an entry in +that list for every key in the hash table. +Inputs: + table: a hash table +Return; + The linked list + *****************************************************************************/ +psList *psHashKeyList(psHash * table) +{ + int i = 0; // Loop index variable + psList *myLinkList = NULL; // The output data structure + psHashBucket *ptr = NULL; // Used to step thru linked list. + + if (table == NULL) { + return NULL; + } + // Create the linked list + myLinkList = psListAlloc(NULL); + + // Loop through every bucket in the hash table. If that bucket is not + // NULL, then add the bucket's key to the linked list. + for (i = 0; i < table->nbucket; i++) { + if (table->buckets[i] != NULL) { + // Since a bucket contains a linked list of keys/data, we must + // step trough each key in that linked list: + + ptr = table->buckets[i]; + while (ptr != NULL) { + psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); + ptr = ptr->next; + } + } + } + + // Return the linked list + return (myLinkList); +} + +/****************************************************************************** +hashBucketAlloc(key, data, next): This procedure creates a new hash bucket +with the specified key, data, and next. +Inputs: + key: the new bucket's key pointer + data: the new bucket's data pointer + next: the new bucket's key pointer +Return: + the new hash bucket. + *****************************************************************************/ +static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next) +{ + if (key == NULL) { + psAbort(__func__, "psHashBucket() called with NULL key."); + } + // Allocate memory for the new hash bucket. + psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); + + p_psMemSetDeallocator(bucket, (psFreeFcn) hashBucketFree); + + // Initialize the bucket. + bucket->key = psStringCopy(key); + + if (data == NULL) { + // NOTE: Should we flag a warning message? + bucket->data = NULL; + } else { + bucket->data = psMemIncrRefCounter(data); + } + + bucket->next = next; + + return bucket; +} + +/****************************************************************************** +hashBucketFree(bucket): This procedure deallocates the specified +hash bucket. +Inputs: + bucket: the hash bucket to be freed. +Return: + NONE + *****************************************************************************/ +static void hashBucketFree(psHashBucket * bucket) +{ + if (bucket == NULL) { + return; + } + + psFree(bucket->key); + + psFree(bucket->data); +} + +/****************************************************************************** +psHashAlloc(nbucket): this procedure creates a new hash table with the +specified number of buckets. +Inputs: + nbucket: initial number of buckets +Return: + The new hash table. + *****************************************************************************/ +psHash *psHashAlloc(int nbucket) // initial number of buckets +{ + int i = 0; // loop index variable + + // Create the new hash table. + psHash *table = psAlloc(sizeof(psHash)); + + p_psMemSetDeallocator(table, (psFreeFcn) hashFree); + + // Allocate memory for the buckets. + table->buckets = psAlloc(nbucket * sizeof(psHashBucket *)); + table->nbucket = nbucket; + + psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); + + // Initialize all buckets to NULL. + for (i = 0; i < nbucket; i++) + { + table->buckets[i] = NULL; + } + + // Return the new hash table. + return table; +} + +/****************************************************************************** +psHashFree(table, itemFree): This procedure deallocates the specified hash +table. It loops through each bucket, and calls hashBucketFree() on that +bucket. + +Inputs: + table: a hash table +Return: + NONE + *****************************************************************************/ +static void hashFree(psHash * table) +{ + int i = 0; // Loop index variable. + + if (table == NULL) { + return; + } + // Loop through each bucket in the hash table. If that bucket is not + // NULL, then free the bucket via a function call to hashBucketFree(); + for (i = 0; i < table->nbucket; i++) { + + // A bucket is composed of a linked list of buckets. + while (table->buckets[i] != NULL) { + psHashBucket* bucket = table->buckets[i]; + table->buckets[i] = bucket->next; + psFree(bucket); + } + } + + // Free the bucket structure, then the hash table. + psFree(table->buckets); +} + +/****************************************************************************** +doHashWork(table, key, data, remove): This is an internal +procedure which does the bulk of the work in using the hash table. Depending +upon the input parameters, it will either insert a new key/data into the hash +table, retrieve the data for a specified key, or remove a key/data item. If +we try to insert a key that already exists in the hash table, then we deallocate +the existing data/key item. +Inputs: + table: a hash table + key: the key to insert, retrieve, or remove. Must not be NULL. + data: the data to insert, if not NULL + remove: set to non-zero if the key/data should be removed from the table. +Return: + NONE + +NOTE: consider removing this private function and simply putting the code +into the psHashInsert(), psHashLookup(), and psHashRemove(). Why? Because +there is little common code between those functions. + *****************************************************************************/ +static void *doHashWork(psHash * table, const char *key, void *data, bool remove + ) +{ + long int hash = 1; // This will contain an integer value + + // "hashed" from the key. + char *tmpchar = NULL; // Used in computing the hash function. + psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. + psHashBucket *optr = NULL; // "original pointer": used to step + + // thru the linked list for a bucket. + + // The following condition should never be true, since this is a private + // function, but I'm checking it anyway since future coders might change + // the way this procedure is called. + if ((table == NULL) || (key == NULL)) { + + psAbort(__func__, "psHashRemove() called with NULL key or table."); + } + // NOTE: This is the originally supplied hash function. + // for (int i = 0, len = strlen(key); i < len; i++) { + // hash = (hash << 1) ^ key[i]; + // } + // hash &= (table->nbucket - 1); + + // This hash algorithm is from Sedgewick. NOTE: must reread to ensure that + // the size of the hash table is not required to be a prime number. + tmpchar = (char *)key; + for (hash = 0; *tmpchar != '\0'; tmpchar++) { + hash = (64 * hash + *tmpchar) % (table->nbucket); + } + + // NOTE: This should not be necessary, but for now, I'm checking bounds + // anyway. + if ((hash < 0) || (hash >= table->nbucket)) { + psAbort(__func__, "Internal hash function out of range (%d)", hash); + } + // ptr will have the correct hash bucket. + ptr = table->buckets[hash]; + + // We know the correct hash bucket, now we need to know what to do. + // If the data parameter is NULL, then, by definition, this is a retrieve + // or a remove operation on the hash table. + + if (data == NULL) { + if (remove + ) { + // We search through the linked list for this bucket in + // the hash table and look for an entry for this key. + + optr = ptr; + while (ptr != NULL) { + // Determine if this entry holds the correct key. + if (strcmp(key, ptr->key) == 0) { + // The following lines of code are fairly standard ways + // of removing an item from a single-linked list. + + void *data = ptr->data; + + optr->next = ptr->next; + if (ptr == table->buckets[hash]) { + table->buckets[hash] = ptr->next; + } + psFree(ptr); + + // By definition, the data associated with that key + // must be returned, not freed. + return data; + } + optr = ptr; + ptr = ptr->next; + } + return NULL; // not in hash + } + else { + // If we get here, then a retrieve operation is requested. So, + // we step trough the linked list at this bucket, and return the + // data once we find it, or return NULL if we don't. + while (ptr != NULL) { + if (strcmp(key, ptr->key) == 0) { + return ptr->data; + } + ptr = ptr->next; + } + return NULL; // not in hash + } + } else { + // We get here if this procedure was called with non-NULL data. + // Therefore, we should insert that data into the hash table. + // First, we search through the linked list for this bucket in + // the hash table and look for a duplicate entry for this key. + + while (ptr != NULL) { + if (strcmp(key, ptr->key) == 0) { + // We have found this key in the hash table. + + psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); + + // NOTE: I have changed this behavior from the originally + // supplied code. Formerly, if itemFree was NULL, then + // the new data was not inserted into the hash table. + + psFree(ptr->data); + + ptr->data = psMemIncrRefCounter(data); + return data; + } + ptr = ptr->next; + } + // We did not found key in the linked list for this bucket of the hash + // table. So, we insert this data at the head of that linked list. + + table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); + return data; + } +} + +/****************************************************************************** +psHashInsert(table, key, data, itemFree): this procedure, which is part of +the public API, inserts a new key/data pair into the hash table. +Inputs: + table: a hash table + key: the key to use + data: the data to insert. + itemFree: a function pointer +Return: + boolean value defining success or failure + *****************************************************************************/ +bool psHashAdd(psHash * table, const char *key, void *data) +{ + if (table == NULL) { + psAbort(__func__, "psHashInsert() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashInsert() called with NULL key."); + } + if (data == NULL) { + psAbort(__func__, "psHashLookup() called with NULL data."); + } + + return (doHashWork(table, key, data, 0) != NULL); +} + +/****************************************************************************** +psHashLookup(table, key): this procedure, which is part of the public API, +looks up the specified key in the hash table and returns the data associated +with that key. + +Inputs: + table: a hash table + key: the key to use +Return: + The data associated with that key. + *****************************************************************************/ +void *psHashLookup(psHash * table, // table to lookup key in + const char *key) // key to lookup +{ + if (table == NULL) { + psAbort(__func__, "psHashLookup() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashLookup() called with NULL key."); + } + + return doHashWork(table, key, NULL, 0); +} + +/****************************************************************************** +psHashRemove(table, key, itemFree): this procedure, which is part of the +public API, removes the specified key from the hash table. +Inputs: + table: a hash table + key: the key to remove + itemFree: a function pointer +Return: + boolean value defining success or failure + *****************************************************************************/ +bool psHashRemove(psHash * table, const char *key) +{ + void *data = NULL; + bool retVal = false; + + if (table == NULL) { + psAbort(__func__, "psHashRemove() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashRemove() called with NULL key."); + } + + data = doHashWork(table, key, NULL, 1); + if (data != NULL) { + retVal = true; + } else { + retVal = false; + } + return retVal; +} Index: /trunk/psLib/src/collections/psHash.h =================================================================== --- /trunk/psLib/src/collections/psHash.h (revision 1420) +++ /trunk/psLib/src/collections/psHash.h (revision 1420) @@ -0,0 +1,73 @@ + +/** @file psHash.h + * @brief Contains support for basic hashing functions. + * @ingroup HashTable + * + * This file will hold the prototypes for defining a hash table with arbitrary + * data types, allocating/deallocating that has table, adding and removing + * data from that hash table, and listing all keys defined in the hash table. + * + * @author Robert Lupton, Princeton University + * @author George Gusciora, MHPCC + * + * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-08-09 20:29:43 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ +#if !defined(PS_HASH_H) +# define PS_HASH_H + +/** \addtogroup HashTable + * \{ + */ +# include + +# include "psList.h" + +/** A bucket that holds an item of data. */ +typedef struct psHashBucket +{ + char *key; // /< key for this item of data + void *data; // /< the data itself + struct psHashBucket *next; // /< list of other possible keys +} +psHashBucket; + +//typedef struct HashTable psHash; ///< Opaque type for a hash table + +/** The hash-table itself. */ +typedef struct psHash +{ + int nbucket; // /< Number of buckets in hash table. + psHashBucket **buckets; // /< The bucket data. +} +psHash; + +/// Allocate hash buckets in table. +psHash *psHashAlloc(int nbucket // /< The number of buckets to allocate. + ); + +/// Insert entry into table. +bool psHashAdd(psHash * table, // /< table to insert in + const char *key, // /< key to use + void *data // /< data to insert + ); + +/// Lookup key in table. +void *psHashLookup(psHash * table, // /< table to lookup key in + const char *key // /< key to lookup + ); + +/// Remove key from table. +bool psHashRemove(psHash * table, // /< table to lookup key in + const char *key // /< key to lookup + ); + +/// List all keys in table. +psList *psHashKeyList(psHash * table // /< table to list keys from. + ); + +/* \} */// End of DataGroup Functions + +#endif Index: /trunk/psLib/src/sysUtils/Makefile =================================================================== --- /trunk/psLib/src/sysUtils/Makefile (revision 1419) +++ /trunk/psLib/src/sysUtils/Makefile (revision 1420) @@ -3,6 +3,6 @@ ## Makefile: sysUtils ## -## $Revision: 1.17 $ $Name: not supported by cvs2svn $ -## $Date: 2004-07-29 21:43:11 $ +## $Revision: 1.18 $ $Name: not supported by cvs2svn $ +## $Date: 2004-08-09 20:28:54 $ ## ## Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -34,5 +34,4 @@ psTrace.o \ psLogMsg.o \ - psHash.o \ psAbort.o \ psString.o Index: unk/psLib/src/sysUtils/psHash.c =================================================================== --- /trunk/psLib/src/sysUtils/psHash.c (revision 1419) +++ (revision ) @@ -1,408 +1,0 @@ - -/** @file psHash.c -* -* @brief Contains support for basic hashing functions. -* -* This file will hold the functions for defining a hash table with arbitrary -* data types, allocating/deallocating that hash table, adding and removing -* data from that hash table, and listing all keys defined in the hash table. -* -* @author Robert Lupton, Princeton University -* @author George Gusciora, MHPCC -* -* @version $Revision: 1.18 $ $Name: not supported by cvs2svn $ -* @date $Date: 2004-08-09 20:21:16 $ -* -* Copyright 2004 Maui High Performance Computing Center, University of Hawaii -*/ -#include -#include -#include -#include -#include "psHash.h" -#include "psMemory.h" -#include "psString.h" -#include "psTrace.h" -#include "psAbort.h" - -static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next); -static void hashBucketFree(psHashBucket * bucket); -static void *doHashWork(psHash * table, const char *key, void *data, bool remove - ); -static void hashFree(psHash * table); - -/****************************************************************************** -psHashKeyList(table): this function creates a linked list with an entry in -that list for every key in the hash table. -Inputs: - table: a hash table -Return; - The linked list - *****************************************************************************/ -psList *psHashKeyList(psHash * table) -{ - int i = 0; // Loop index variable - psList *myLinkList = NULL; // The output data structure - psHashBucket *ptr = NULL; // Used to step thru linked list. - - if (table == NULL) { - return NULL; - } - // Create the linked list - myLinkList = psListAlloc(NULL); - - // Loop through every bucket in the hash table. If that bucket is not - // NULL, then add the bucket's key to the linked list. - for (i = 0; i < table->nbucket; i++) { - if (table->buckets[i] != NULL) { - // Since a bucket contains a linked list of keys/data, we must - // step trough each key in that linked list: - - ptr = table->buckets[i]; - while (ptr != NULL) { - psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); - ptr = ptr->next; - } - } - } - - // Return the linked list - return (myLinkList); -} - -/****************************************************************************** -hashBucketAlloc(key, data, next): This procedure creates a new hash bucket -with the specified key, data, and next. -Inputs: - key: the new bucket's key pointer - data: the new bucket's data pointer - next: the new bucket's key pointer -Return: - the new hash bucket. - *****************************************************************************/ -static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next) -{ - if (key == NULL) { - psAbort(__func__, "psHashBucket() called with NULL key."); - } - // Allocate memory for the new hash bucket. - psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); - - p_psMemSetDeallocator(bucket, (psFreeFcn) hashBucketFree); - - // Initialize the bucket. - bucket->key = psStringCopy(key); - - if (data == NULL) { - // NOTE: Should we flag a warning message? - bucket->data = NULL; - } else { - bucket->data = psMemIncrRefCounter(data); - } - - bucket->next = next; - - return bucket; -} - -/****************************************************************************** -hashBucketFree(bucket): This procedure deallocates the specified -hash bucket. -Inputs: - bucket: the hash bucket to be freed. -Return: - NONE - *****************************************************************************/ -static void hashBucketFree(psHashBucket * bucket) -{ - if (bucket == NULL) { - return; - } - - psFree(bucket->key); - - psFree(bucket->data); -} - -/****************************************************************************** -psHashAlloc(nbucket): this procedure creates a new hash table with the -specified number of buckets. -Inputs: - nbucket: initial number of buckets -Return: - The new hash table. - *****************************************************************************/ -psHash *psHashAlloc(int nbucket) // initial number of buckets -{ - int i = 0; // loop index variable - - // Create the new hash table. - psHash *table = psAlloc(sizeof(psHash)); - - p_psMemSetDeallocator(table, (psFreeFcn) hashFree); - - // Allocate memory for the buckets. - table->buckets = psAlloc(nbucket * sizeof(psHashBucket *)); - table->nbucket = nbucket; - - psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); - - // Initialize all buckets to NULL. - for (i = 0; i < nbucket; i++) - { - table->buckets[i] = NULL; - } - - // Return the new hash table. - return table; -} - -/****************************************************************************** -psHashFree(table, itemFree): This procedure deallocates the specified hash -table. It loops through each bucket, and calls hashBucketFree() on that -bucket. - -Inputs: - table: a hash table -Return: - NONE - *****************************************************************************/ -static void hashFree(psHash * table) -{ - int i = 0; // Loop index variable. - - if (table == NULL) { - return; - } - // Loop through each bucket in the hash table. If that bucket is not - // NULL, then free the bucket via a function call to hashBucketFree(); - for (i = 0; i < table->nbucket; i++) { - - // A bucket is composed of a linked list of buckets. - while (table->buckets[i] != NULL) { - psHashBucket* bucket = table->buckets[i]; - table->buckets[i] = bucket->next; - psFree(bucket); - } - } - - // Free the bucket structure, then the hash table. - psFree(table->buckets); -} - -/****************************************************************************** -doHashWork(table, key, data, remove): This is an internal -procedure which does the bulk of the work in using the hash table. Depending -upon the input parameters, it will either insert a new key/data into the hash -table, retrieve the data for a specified key, or remove a key/data item. If -we try to insert a key that already exists in the hash table, then we deallocate -the existing data/key item. -Inputs: - table: a hash table - key: the key to insert, retrieve, or remove. Must not be NULL. - data: the data to insert, if not NULL - remove: set to non-zero if the key/data should be removed from the table. -Return: - NONE - -NOTE: consider removing this private function and simply putting the code -into the psHashInsert(), psHashLookup(), and psHashRemove(). Why? Because -there is little common code between those functions. - *****************************************************************************/ -static void *doHashWork(psHash * table, const char *key, void *data, bool remove - ) -{ - long int hash = 1; // This will contain an integer value - - // "hashed" from the key. - char *tmpchar = NULL; // Used in computing the hash function. - psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. - psHashBucket *optr = NULL; // "original pointer": used to step - - // thru the linked list for a bucket. - - // The following condition should never be true, since this is a private - // function, but I'm checking it anyway since future coders might change - // the way this procedure is called. - if ((table == NULL) || (key == NULL)) { - - psAbort(__func__, "psHashRemove() called with NULL key or table."); - } - // NOTE: This is the originally supplied hash function. - // for (int i = 0, len = strlen(key); i < len; i++) { - // hash = (hash << 1) ^ key[i]; - // } - // hash &= (table->nbucket - 1); - - // This hash algorithm is from Sedgewick. NOTE: must reread to ensure that - // the size of the hash table is not required to be a prime number. - tmpchar = (char *)key; - for (hash = 0; *tmpchar != '\0'; tmpchar++) { - hash = (64 * hash + *tmpchar) % (table->nbucket); - } - - // NOTE: This should not be necessary, but for now, I'm checking bounds - // anyway. - if ((hash < 0) || (hash >= table->nbucket)) { - psAbort(__func__, "Internal hash function out of range (%d)", hash); - } - // ptr will have the correct hash bucket. - ptr = table->buckets[hash]; - - // We know the correct hash bucket, now we need to know what to do. - // If the data parameter is NULL, then, by definition, this is a retrieve - // or a remove operation on the hash table. - - if (data == NULL) { - if (remove - ) { - // We search through the linked list for this bucket in - // the hash table and look for an entry for this key. - - optr = ptr; - while (ptr != NULL) { - // Determine if this entry holds the correct key. - if (strcmp(key, ptr->key) == 0) { - // The following lines of code are fairly standard ways - // of removing an item from a single-linked list. - - void *data = ptr->data; - - optr->next = ptr->next; - if (ptr == table->buckets[hash]) { - table->buckets[hash] = ptr->next; - } - psFree(ptr); - - // By definition, the data associated with that key - // must be returned, not freed. - return data; - } - optr = ptr; - ptr = ptr->next; - } - return NULL; // not in hash - } - else { - // If we get here, then a retrieve operation is requested. So, - // we step trough the linked list at this bucket, and return the - // data once we find it, or return NULL if we don't. - while (ptr != NULL) { - if (strcmp(key, ptr->key) == 0) { - return ptr->data; - } - ptr = ptr->next; - } - return NULL; // not in hash - } - } else { - // We get here if this procedure was called with non-NULL data. - // Therefore, we should insert that data into the hash table. - // First, we search through the linked list for this bucket in - // the hash table and look for a duplicate entry for this key. - - while (ptr != NULL) { - if (strcmp(key, ptr->key) == 0) { - // We have found this key in the hash table. - - psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); - - // NOTE: I have changed this behavior from the originally - // supplied code. Formerly, if itemFree was NULL, then - // the new data was not inserted into the hash table. - - psFree(ptr->data); - - ptr->data = psMemIncrRefCounter(data); - return data; - } - ptr = ptr->next; - } - // We did not found key in the linked list for this bucket of the hash - // table. So, we insert this data at the head of that linked list. - - table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); - return data; - } -} - -/****************************************************************************** -psHashInsert(table, key, data, itemFree): this procedure, which is part of -the public API, inserts a new key/data pair into the hash table. -Inputs: - table: a hash table - key: the key to use - data: the data to insert. - itemFree: a function pointer -Return: - boolean value defining success or failure - *****************************************************************************/ -bool psHashAdd(psHash * table, const char *key, void *data) -{ - if (table == NULL) { - psAbort(__func__, "psHashInsert() called with NULL hash table."); - } - if (key == NULL) { - psAbort(__func__, "psHashInsert() called with NULL key."); - } - if (data == NULL) { - psAbort(__func__, "psHashLookup() called with NULL data."); - } - - return (doHashWork(table, key, data, 0) != NULL); -} - -/****************************************************************************** -psHashLookup(table, key): this procedure, which is part of the public API, -looks up the specified key in the hash table and returns the data associated -with that key. - -Inputs: - table: a hash table - key: the key to use -Return: - The data associated with that key. - *****************************************************************************/ -void *psHashLookup(psHash * table, // table to lookup key in - const char *key) // key to lookup -{ - if (table == NULL) { - psAbort(__func__, "psHashLookup() called with NULL hash table."); - } - if (key == NULL) { - psAbort(__func__, "psHashLookup() called with NULL key."); - } - - return doHashWork(table, key, NULL, 0); -} - -/****************************************************************************** -psHashRemove(table, key, itemFree): this procedure, which is part of the -public API, removes the specified key from the hash table. -Inputs: - table: a hash table - key: the key to remove - itemFree: a function pointer -Return: - boolean value defining success or failure - *****************************************************************************/ -bool psHashRemove(psHash * table, const char *key) -{ - void *data = NULL; - bool retVal = false; - - if (table == NULL) { - psAbort(__func__, "psHashRemove() called with NULL hash table."); - } - if (key == NULL) { - psAbort(__func__, "psHashRemove() called with NULL key."); - } - - data = doHashWork(table, key, NULL, 1); - if (data != NULL) { - retVal = true; - } else { - retVal = false; - } - return retVal; -} Index: unk/psLib/src/sysUtils/psHash.h =================================================================== --- /trunk/psLib/src/sysUtils/psHash.h (revision 1419) +++ (revision ) @@ -1,73 +1,0 @@ - -/** @file psHash.h - * @brief Contains support for basic hashing functions. - * @ingroup HashTable - * - * This file will hold the prototypes for defining a hash table with arbitrary - * data types, allocating/deallocating that has table, adding and removing - * data from that hash table, and listing all keys defined in the hash table. - * - * @author Robert Lupton, Princeton University - * @author George Gusciora, MHPCC - * - * @version $Revision: 1.19 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-08-07 00:06:06 $ - * - * Copyright 2004 Maui High Performance Computing Center, University of Hawaii - */ -#if !defined(PS_HASH_H) -# define PS_HASH_H - -/** \addtogroup HashTable - * \{ - */ -# include - -# include "psList.h" - -/** A bucket that holds an item of data. */ -typedef struct psHashBucket -{ - char *key; // /< key for this item of data - void *data; // /< the data itself - struct psHashBucket *next; // /< list of other possible keys -} -psHashBucket; - -//typedef struct HashTable psHash; ///< Opaque type for a hash table - -/** The hash-table itself. */ -typedef struct psHash -{ - int nbucket; // /< Number of buckets in hash table. - psHashBucket **buckets; // /< The bucket data. -} -psHash; - -/// Allocate hash buckets in table. -psHash *psHashAlloc(int nbucket // /< The number of buckets to allocate. - ); - -/// Insert entry into table. -bool psHashAdd(psHash * table, // /< table to insert in - const char *key, // /< key to use - void *data // /< data to insert - ); - -/// Lookup key in table. -void *psHashLookup(psHash * table, // /< table to lookup key in - const char *key // /< key to lookup - ); - -/// Remove key from table. -bool psHashRemove(psHash * table, // /< table to lookup key in - const char *key // /< key to lookup - ); - -/// List all keys in table. -psList *psHashKeyList(psHash * table // /< table to list keys from. - ); - -/* \} */// End of DataGroup Functions - -#endif Index: /trunk/psLib/src/types/psHash.c =================================================================== --- /trunk/psLib/src/types/psHash.c (revision 1420) +++ /trunk/psLib/src/types/psHash.c (revision 1420) @@ -0,0 +1,408 @@ + +/** @file psHash.c +* +* @brief Contains support for basic hashing functions. +* +* This file will hold the functions for defining a hash table with arbitrary +* data types, allocating/deallocating that hash table, adding and removing +* data from that hash table, and listing all keys defined in the hash table. +* +* @author Robert Lupton, Princeton University +* @author George Gusciora, MHPCC +* +* @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ +* @date $Date: 2004-08-09 20:29:43 $ +* +* Copyright 2004 Maui High Performance Computing Center, University of Hawaii +*/ +#include +#include +#include +#include +#include "psHash.h" +#include "psMemory.h" +#include "psString.h" +#include "psTrace.h" +#include "psAbort.h" + +static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next); +static void hashBucketFree(psHashBucket * bucket); +static void *doHashWork(psHash * table, const char *key, void *data, bool remove + ); +static void hashFree(psHash * table); + +/****************************************************************************** +psHashKeyList(table): this function creates a linked list with an entry in +that list for every key in the hash table. +Inputs: + table: a hash table +Return; + The linked list + *****************************************************************************/ +psList *psHashKeyList(psHash * table) +{ + int i = 0; // Loop index variable + psList *myLinkList = NULL; // The output data structure + psHashBucket *ptr = NULL; // Used to step thru linked list. + + if (table == NULL) { + return NULL; + } + // Create the linked list + myLinkList = psListAlloc(NULL); + + // Loop through every bucket in the hash table. If that bucket is not + // NULL, then add the bucket's key to the linked list. + for (i = 0; i < table->nbucket; i++) { + if (table->buckets[i] != NULL) { + // Since a bucket contains a linked list of keys/data, we must + // step trough each key in that linked list: + + ptr = table->buckets[i]; + while (ptr != NULL) { + psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); + ptr = ptr->next; + } + } + } + + // Return the linked list + return (myLinkList); +} + +/****************************************************************************** +hashBucketAlloc(key, data, next): This procedure creates a new hash bucket +with the specified key, data, and next. +Inputs: + key: the new bucket's key pointer + data: the new bucket's data pointer + next: the new bucket's key pointer +Return: + the new hash bucket. + *****************************************************************************/ +static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next) +{ + if (key == NULL) { + psAbort(__func__, "psHashBucket() called with NULL key."); + } + // Allocate memory for the new hash bucket. + psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); + + p_psMemSetDeallocator(bucket, (psFreeFcn) hashBucketFree); + + // Initialize the bucket. + bucket->key = psStringCopy(key); + + if (data == NULL) { + // NOTE: Should we flag a warning message? + bucket->data = NULL; + } else { + bucket->data = psMemIncrRefCounter(data); + } + + bucket->next = next; + + return bucket; +} + +/****************************************************************************** +hashBucketFree(bucket): This procedure deallocates the specified +hash bucket. +Inputs: + bucket: the hash bucket to be freed. +Return: + NONE + *****************************************************************************/ +static void hashBucketFree(psHashBucket * bucket) +{ + if (bucket == NULL) { + return; + } + + psFree(bucket->key); + + psFree(bucket->data); +} + +/****************************************************************************** +psHashAlloc(nbucket): this procedure creates a new hash table with the +specified number of buckets. +Inputs: + nbucket: initial number of buckets +Return: + The new hash table. + *****************************************************************************/ +psHash *psHashAlloc(int nbucket) // initial number of buckets +{ + int i = 0; // loop index variable + + // Create the new hash table. + psHash *table = psAlloc(sizeof(psHash)); + + p_psMemSetDeallocator(table, (psFreeFcn) hashFree); + + // Allocate memory for the buckets. + table->buckets = psAlloc(nbucket * sizeof(psHashBucket *)); + table->nbucket = nbucket; + + psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); + + // Initialize all buckets to NULL. + for (i = 0; i < nbucket; i++) + { + table->buckets[i] = NULL; + } + + // Return the new hash table. + return table; +} + +/****************************************************************************** +psHashFree(table, itemFree): This procedure deallocates the specified hash +table. It loops through each bucket, and calls hashBucketFree() on that +bucket. + +Inputs: + table: a hash table +Return: + NONE + *****************************************************************************/ +static void hashFree(psHash * table) +{ + int i = 0; // Loop index variable. + + if (table == NULL) { + return; + } + // Loop through each bucket in the hash table. If that bucket is not + // NULL, then free the bucket via a function call to hashBucketFree(); + for (i = 0; i < table->nbucket; i++) { + + // A bucket is composed of a linked list of buckets. + while (table->buckets[i] != NULL) { + psHashBucket* bucket = table->buckets[i]; + table->buckets[i] = bucket->next; + psFree(bucket); + } + } + + // Free the bucket structure, then the hash table. + psFree(table->buckets); +} + +/****************************************************************************** +doHashWork(table, key, data, remove): This is an internal +procedure which does the bulk of the work in using the hash table. Depending +upon the input parameters, it will either insert a new key/data into the hash +table, retrieve the data for a specified key, or remove a key/data item. If +we try to insert a key that already exists in the hash table, then we deallocate +the existing data/key item. +Inputs: + table: a hash table + key: the key to insert, retrieve, or remove. Must not be NULL. + data: the data to insert, if not NULL + remove: set to non-zero if the key/data should be removed from the table. +Return: + NONE + +NOTE: consider removing this private function and simply putting the code +into the psHashInsert(), psHashLookup(), and psHashRemove(). Why? Because +there is little common code between those functions. + *****************************************************************************/ +static void *doHashWork(psHash * table, const char *key, void *data, bool remove + ) +{ + long int hash = 1; // This will contain an integer value + + // "hashed" from the key. + char *tmpchar = NULL; // Used in computing the hash function. + psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. + psHashBucket *optr = NULL; // "original pointer": used to step + + // thru the linked list for a bucket. + + // The following condition should never be true, since this is a private + // function, but I'm checking it anyway since future coders might change + // the way this procedure is called. + if ((table == NULL) || (key == NULL)) { + + psAbort(__func__, "psHashRemove() called with NULL key or table."); + } + // NOTE: This is the originally supplied hash function. + // for (int i = 0, len = strlen(key); i < len; i++) { + // hash = (hash << 1) ^ key[i]; + // } + // hash &= (table->nbucket - 1); + + // This hash algorithm is from Sedgewick. NOTE: must reread to ensure that + // the size of the hash table is not required to be a prime number. + tmpchar = (char *)key; + for (hash = 0; *tmpchar != '\0'; tmpchar++) { + hash = (64 * hash + *tmpchar) % (table->nbucket); + } + + // NOTE: This should not be necessary, but for now, I'm checking bounds + // anyway. + if ((hash < 0) || (hash >= table->nbucket)) { + psAbort(__func__, "Internal hash function out of range (%d)", hash); + } + // ptr will have the correct hash bucket. + ptr = table->buckets[hash]; + + // We know the correct hash bucket, now we need to know what to do. + // If the data parameter is NULL, then, by definition, this is a retrieve + // or a remove operation on the hash table. + + if (data == NULL) { + if (remove + ) { + // We search through the linked list for this bucket in + // the hash table and look for an entry for this key. + + optr = ptr; + while (ptr != NULL) { + // Determine if this entry holds the correct key. + if (strcmp(key, ptr->key) == 0) { + // The following lines of code are fairly standard ways + // of removing an item from a single-linked list. + + void *data = ptr->data; + + optr->next = ptr->next; + if (ptr == table->buckets[hash]) { + table->buckets[hash] = ptr->next; + } + psFree(ptr); + + // By definition, the data associated with that key + // must be returned, not freed. + return data; + } + optr = ptr; + ptr = ptr->next; + } + return NULL; // not in hash + } + else { + // If we get here, then a retrieve operation is requested. So, + // we step trough the linked list at this bucket, and return the + // data once we find it, or return NULL if we don't. + while (ptr != NULL) { + if (strcmp(key, ptr->key) == 0) { + return ptr->data; + } + ptr = ptr->next; + } + return NULL; // not in hash + } + } else { + // We get here if this procedure was called with non-NULL data. + // Therefore, we should insert that data into the hash table. + // First, we search through the linked list for this bucket in + // the hash table and look for a duplicate entry for this key. + + while (ptr != NULL) { + if (strcmp(key, ptr->key) == 0) { + // We have found this key in the hash table. + + psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); + + // NOTE: I have changed this behavior from the originally + // supplied code. Formerly, if itemFree was NULL, then + // the new data was not inserted into the hash table. + + psFree(ptr->data); + + ptr->data = psMemIncrRefCounter(data); + return data; + } + ptr = ptr->next; + } + // We did not found key in the linked list for this bucket of the hash + // table. So, we insert this data at the head of that linked list. + + table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); + return data; + } +} + +/****************************************************************************** +psHashInsert(table, key, data, itemFree): this procedure, which is part of +the public API, inserts a new key/data pair into the hash table. +Inputs: + table: a hash table + key: the key to use + data: the data to insert. + itemFree: a function pointer +Return: + boolean value defining success or failure + *****************************************************************************/ +bool psHashAdd(psHash * table, const char *key, void *data) +{ + if (table == NULL) { + psAbort(__func__, "psHashInsert() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashInsert() called with NULL key."); + } + if (data == NULL) { + psAbort(__func__, "psHashLookup() called with NULL data."); + } + + return (doHashWork(table, key, data, 0) != NULL); +} + +/****************************************************************************** +psHashLookup(table, key): this procedure, which is part of the public API, +looks up the specified key in the hash table and returns the data associated +with that key. + +Inputs: + table: a hash table + key: the key to use +Return: + The data associated with that key. + *****************************************************************************/ +void *psHashLookup(psHash * table, // table to lookup key in + const char *key) // key to lookup +{ + if (table == NULL) { + psAbort(__func__, "psHashLookup() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashLookup() called with NULL key."); + } + + return doHashWork(table, key, NULL, 0); +} + +/****************************************************************************** +psHashRemove(table, key, itemFree): this procedure, which is part of the +public API, removes the specified key from the hash table. +Inputs: + table: a hash table + key: the key to remove + itemFree: a function pointer +Return: + boolean value defining success or failure + *****************************************************************************/ +bool psHashRemove(psHash * table, const char *key) +{ + void *data = NULL; + bool retVal = false; + + if (table == NULL) { + psAbort(__func__, "psHashRemove() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashRemove() called with NULL key."); + } + + data = doHashWork(table, key, NULL, 1); + if (data != NULL) { + retVal = true; + } else { + retVal = false; + } + return retVal; +} Index: /trunk/psLib/src/types/psHash.h =================================================================== --- /trunk/psLib/src/types/psHash.h (revision 1420) +++ /trunk/psLib/src/types/psHash.h (revision 1420) @@ -0,0 +1,73 @@ + +/** @file psHash.h + * @brief Contains support for basic hashing functions. + * @ingroup HashTable + * + * This file will hold the prototypes for defining a hash table with arbitrary + * data types, allocating/deallocating that has table, adding and removing + * data from that hash table, and listing all keys defined in the hash table. + * + * @author Robert Lupton, Princeton University + * @author George Gusciora, MHPCC + * + * @version $Revision: 1.1 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-08-09 20:29:43 $ + * + * Copyright 2004 Maui High Performance Computing Center, University of Hawaii + */ +#if !defined(PS_HASH_H) +# define PS_HASH_H + +/** \addtogroup HashTable + * \{ + */ +# include + +# include "psList.h" + +/** A bucket that holds an item of data. */ +typedef struct psHashBucket +{ + char *key; // /< key for this item of data + void *data; // /< the data itself + struct psHashBucket *next; // /< list of other possible keys +} +psHashBucket; + +//typedef struct HashTable psHash; ///< Opaque type for a hash table + +/** The hash-table itself. */ +typedef struct psHash +{ + int nbucket; // /< Number of buckets in hash table. + psHashBucket **buckets; // /< The bucket data. +} +psHash; + +/// Allocate hash buckets in table. +psHash *psHashAlloc(int nbucket // /< The number of buckets to allocate. + ); + +/// Insert entry into table. +bool psHashAdd(psHash * table, // /< table to insert in + const char *key, // /< key to use + void *data // /< data to insert + ); + +/// Lookup key in table. +void *psHashLookup(psHash * table, // /< table to lookup key in + const char *key // /< key to lookup + ); + +/// Remove key from table. +bool psHashRemove(psHash * table, // /< table to lookup key in + const char *key // /< key to lookup + ); + +/// List all keys in table. +psList *psHashKeyList(psHash * table // /< table to list keys from. + ); + +/* \} */// End of DataGroup Functions + +#endif