Index: trunk/psLib/src/sysUtils/psHash.c =================================================================== --- trunk/psLib/src/sysUtils/psHash.c (revision 1375) +++ trunk/psLib/src/sysUtils/psHash.c (revision 1385) @@ -10,6 +10,6 @@ * @author George Gusciora, MHPCC * -* @version $Revision: 1.13 $ $Name: not supported by cvs2svn $ -* @date $Date: 2004-08-04 01:21:33 $ +* @version $Revision: 1.14 $ $Name: not supported by cvs2svn $ +* @date $Date: 2004-08-04 23:37:39 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -28,6 +28,6 @@ static void hashBucketFree( psHashBucket *bucket ); static void *doHashWork( psHash* table, const char* key, void* data, bool remove - ) -; + ) + ; static void hashFree( psHash *table ); @@ -45,27 +45,27 @@ psList *myLinkList = NULL; // The output data structure psHashBucket *ptr = NULL; // Used to step thru linked list. - + if ( table == NULL ) { - return 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; - } - } + 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 ); @@ -89,23 +89,23 @@ { if ( key == NULL ) { - psAbort( __func__, "psHashBucket() called with NULL key." ); - } - + 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 ); - } - + // NOTE: Should we flag a warning message? + bucket->data = NULL; + } else { + bucket->data = psMemIncrRefCounter( data ); + } + bucket->next = next; - + return bucket; } @@ -123,13 +123,13 @@ { if ( bucket == NULL ) { - return ; - } - + 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 ); } @@ -150,17 +150,17 @@ 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; - } - + { + table->buckets[ i ] = NULL; + } + // Return the new hash table. return table; @@ -182,19 +182,19 @@ { int i = 0; // Loop index variable. - + if ( table == NULL ) { - return ; - } - + 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. - if ( table->buckets[ i ] != NULL ) { - psFree( table->buckets[ i ] ); - } + + // A bucket is composed of a linked list of buckets. + if ( table->buckets[ i ] != NULL ) { + psFree( table->buckets[ i ] ); } - + } + // Free the bucket structure, then the hash table. psFree( table->buckets ); @@ -221,5 +221,5 @@ *****************************************************************************/ static void *doHashWork( psHash *table, const char *key, void *data, bool remove - ) + ) { long int hash = 1; // This will contain an integer value @@ -229,13 +229,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." ); - } - + + 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++) { @@ -243,99 +243,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 ); - } - + 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 ); - } - + 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 + if ( remove ) { - // We search through the linked list for this bucket in - // the hash table and look for an entry for this key. - + // 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 - } - 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; + 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; + } } @@ -354,13 +354,13 @@ { if ( table == NULL ) { - psAbort( __func__, "psHashInsert() called with NULL hash table." ); - } + psAbort( __func__, "psHashInsert() called with NULL hash table." ); + } if ( key == NULL ) { - psAbort( __func__, "psHashInsert() called with NULL key." ); - } + psAbort( __func__, "psHashInsert() called with NULL key." ); + } if ( data == NULL ) { - psAbort( __func__, "psHashLookup() called with NULL data." ); - } - + psAbort( __func__, "psHashLookup() called with NULL data." ); + } + return ( doHashWork( table, key, data, 0 ) != NULL ); } @@ -381,11 +381,11 @@ { if ( table == NULL ) { - psAbort( __func__, "psHashLookup() called with NULL hash table." ); - } + psAbort( __func__, "psHashLookup() called with NULL hash table." ); + } if ( key == NULL ) { - psAbort( __func__, "psHashLookup() called with NULL key." ); - } - - + psAbort( __func__, "psHashLookup() called with NULL key." ); + } + + return doHashWork( table, key, NULL, 0 ); } @@ -405,19 +405,19 @@ void * data = NULL; bool retVal = false; - + if ( table == NULL ) { - psAbort( __func__, "psHashRemove() called with NULL hash table." ); - } + psAbort( __func__, "psHashRemove() called with NULL hash table." ); + } if ( key == NULL ) { - psAbort( __func__, "psHashRemove() called with NULL key." ); - } - + psAbort( __func__, "psHashRemove() called with NULL key." ); + } + data = doHashWork( table, key, NULL, 1 ); if ( data != NULL ) { - psFree( data ); - retVal = true; - } else { - retVal = false; - } + psFree( data ); + retVal = true; + } else { + retVal = false; + } return retVal; }