Index: trunk/psLib/src/sysUtils/psHash.c =================================================================== --- trunk/psLib/src/sysUtils/psHash.c (revision 1295) +++ trunk/psLib/src/sysUtils/psHash.c (revision 1371) @@ -1,18 +1,18 @@ /** @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.11 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-07-24 03:31:06 $ - * - * Copyright 2004 Maui High Performance Computing Center, University of Hawaii - */ +* +* @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.12 $ $Name: not supported by cvs2svn $ +* @date $Date: 2004-08-02 22:31:02 $ +* +* Copyright 2004 Maui High Performance Computing Center, University of Hawaii +*/ #include #include @@ -25,9 +25,10 @@ #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); +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 ); /****************************************************************************** @@ -39,34 +40,34 @@ The linked list *****************************************************************************/ -psList *psHashKeyList(psHash *table) +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; - } - + + if ( table == NULL ) { + return NULL; + } + // Create the linked list - myLinkList = psListAlloc(NULL); - + 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;inbucket;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; - } - } - } - + 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); + return ( myLinkList ); } @@ -83,28 +84,28 @@ the new hash bucket. *****************************************************************************/ -static psHashBucket *hashBucketAlloc(const char *key, - void *data, - psHashBucket *next) -{ - if (key == NULL) { - psAbort(__func__, "psHashBucket() called with NULL key."); - } - +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); - + 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->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; } @@ -119,17 +120,17 @@ NONE *****************************************************************************/ -static void hashBucketFree(psHashBucket *bucket) -{ - if (bucket == NULL) { - return; - } - +static void hashBucketFree( psHashBucket *bucket ) +{ + if ( bucket == NULL ) { + return ; + } + // A bucket is actually a linked list of buckets. We recursively step // through that linked list, free each bucket. - psFree(bucket->next); - - psFree(bucket->key); - - psFree(bucket->data); + psFree( bucket->next ); + + psFree( bucket->key ); + + psFree( bucket->data ); } @@ -143,23 +144,23 @@ The new hash table. *****************************************************************************/ -psHash *psHashAlloc(int nbucket) // initial number of buckets +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); - + psHash *table = psAlloc( sizeof( psHash ) ); + p_psMemSetDeallocator( table, ( psFreeFcn ) hashFree ); + // Allocate memory for the buckets. - table->buckets = psAlloc(nbucket*sizeof(psHashBucket *)); + table->buckets = psAlloc( nbucket * sizeof( psHashBucket * ) ); table->nbucket = nbucket; - - psTrace("utils.hash", 1, "Creating %d-element hash table\n", 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; - } - + for ( i = 0; i < nbucket; i++ ) + { + table->buckets[ i ] = NULL; + } + // Return the new hash table. return table; @@ -178,34 +179,34 @@ NONE *****************************************************************************/ -static void hashFree(psHash *table) -{ - psHashBucket *tmp = NULL; // Used to step through linked list. +static void hashFree( psHash *table ) +{ + psHashBucket * tmp = NULL; // Used to step through linked list. psHashBucket *ptr = NULL; // Used to step through linked list. int i = 0; // Loop index variable. - - if (table == NULL) { - return; - } - + + 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. We use the - // "tmp" and "ptr" pointers to step through that list and free each - // non-NULL bucket. - - if (table->buckets[i] != NULL) { - ptr = table->buckets[i]; - while (ptr != NULL) { - tmp = ptr->next; - psFree(ptr); - ptr = tmp; - } - } - } - + + for ( i = 0; i < table->nbucket; i++ ) { + // A bucket is composed of a linked list of buckets. We use the + // "tmp" and "ptr" pointers to step through that list and free each + // non-NULL bucket. + + if ( table->buckets[ i ] != NULL ) { + ptr = table->buckets[ i ]; + while ( ptr != NULL ) { + tmp = ptr->next; + psFree( ptr ); + ptr = tmp; + } + } + } + // Free the bucket structure, then the hash table. - psFree(table->buckets); + psFree( table->buckets ); } @@ -229,6 +230,6 @@ there is little common code between those functions. *****************************************************************************/ -static void *doHashWork(psHash *table, const char *key, void *data, bool remove - ) +static void *doHashWork( psHash *table, const char *key, void *data, bool remove + ) { long int hash = 1; // This will contain an integer value @@ -238,13 +239,13 @@ 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."); - } - + 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++) { @@ -252,98 +253,99 @@ // } // 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); - } - + 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); - } - + 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]; - + 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) { - // Dtermine 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; + + 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 ) { + // Dtermine 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 } - 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; + 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 } - 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; - } - } - // 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; - } + } 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; + } } @@ -359,17 +361,17 @@ 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); +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 ); } @@ -385,16 +387,16 @@ 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); +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 ); } @@ -409,23 +411,23 @@ boolean value defining success or failure *****************************************************************************/ -bool psHashRemove(psHash *table, const char *key) -{ - void *data = NULL; +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) { - psFree(data); - retVal = true; - } else { - 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 ) { + psFree( data ); + retVal = true; + } else { + retVal = false; + } return retVal; }