Index: trunk/psLib/src/collections/Makefile =================================================================== --- trunk/psLib/src/collections/Makefile (revision 1416) +++ 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