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: trunk/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: trunk/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