Index: trunk/psLib/src/sysUtils/psHash.c =================================================================== --- trunk/psLib/src/sysUtils/psHash.c (revision 1406) +++ trunk/psLib/src/sysUtils/psHash.c (revision 1407) @@ -1,2 +1,3 @@ + /** @file psHash.c * @@ -10,6 +11,6 @@ * @author George Gusciora, MHPCC * -* @version $Revision: 1.15 $ $Name: not supported by cvs2svn $ -* @date $Date: 2004-08-06 22:34:05 $ +* @version $Revision: 1.16 $ $Name: not supported by cvs2svn $ +* @date $Date: 2004-08-07 00:06:06 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -25,10 +26,9 @@ #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); /****************************************************************************** @@ -40,27 +40,26 @@ The linked list *****************************************************************************/ -psList *psHashKeyList( psHash *table ) -{ - int i = 0; // Loop index variable +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 ) { + psHashBucket *ptr = NULL; // Used to step thru linked list. + + 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;i < table->nbucket;i++ ) { - if ( table->buckets[ i ] != NULL ) { + 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 = table->buckets[i]; + while (ptr != NULL) { + psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); ptr = ptr->next; } @@ -69,8 +68,6 @@ // Return the linked list - return ( myLinkList ); -} - - + return (myLinkList); +} /****************************************************************************** @@ -84,24 +81,22 @@ 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 ) { + bucket->key = psStringCopy(key); + + if (data == NULL) { // NOTE: Should we flag a warning message? bucket->data = NULL; } else { - bucket->data = psMemIncrRefCounter( data ); + bucket->data = psMemIncrRefCounter(data); } @@ -110,5 +105,4 @@ return bucket; } - /****************************************************************************** @@ -120,19 +114,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); +} /****************************************************************************** @@ -144,21 +136,23 @@ The new hash table. *****************************************************************************/ -psHash *psHashAlloc( int nbucket ) // initial number of buckets -{ - int i = 0; // loop index variable +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++ ) + for (i = 0; i < nbucket; i++) { - table->buckets[ i ] = NULL; + table->buckets[i] = NULL; } @@ -166,6 +160,4 @@ return table; } - - /****************************************************************************** @@ -179,24 +171,23 @@ NONE *****************************************************************************/ -static void hashFree( psHash *table ) -{ - int i = 0; // Loop index variable. - - if ( table == NULL ) { - return ; - } - +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++ ) { + for (i = 0; i < table->nbucket; i++) { // A bucket is composed of a linked list of buckets. - if ( table->buckets[ i ] != NULL ) { - psFree( table->buckets[ i ] ); + if (table->buckets[i] != NULL) { + psFree(table->buckets[i]); } } // Free the bucket structure, then the hash table. - psFree( table->buckets ); + psFree(table->buckets); } @@ -220,12 +211,14 @@ 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 + 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 + 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. @@ -233,30 +226,28 @@ // 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++) { - // hash = (hash << 1) ^ key[i]; - // } - // hash &= (table->nbucket - 1); + // 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 ); + 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. @@ -264,45 +255,46 @@ // 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. - + 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; - 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 + 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 ) { + while (ptr != NULL) { + if (strcmp(key, ptr->key) == 0) { return ptr->data; } ptr = ptr->next; } - return NULL; // not in hash + return NULL; // not in hash } } else { @@ -312,10 +304,9 @@ // the hash table and look for a duplicate entry for this key. - while ( ptr != NULL ) { - if ( strcmp( key, ptr->key ) == 0 ) { + 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 ); + psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); // NOTE: I have changed this behavior from the originally @@ -323,7 +314,7 @@ // the new data was not inserted into the hash table. - psFree( ptr->data ); - - ptr->data = psMemIncrRefCounter( data ); + psFree(ptr->data); + + ptr->data = psMemIncrRefCounter(data); return data; } @@ -333,7 +324,5 @@ // table. So, we insert this data at the head of that linked list. - table->buckets[ hash ] = hashBucketAlloc( key, - data, - table->buckets[ hash ] ); + table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); return data; } @@ -351,17 +340,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); } @@ -377,16 +366,15 @@ 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); } @@ -401,19 +389,19 @@ 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 ); + 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 {