Changeset 1371 for trunk/psLib/src/sysUtils/psHash.c

Timestamp:

Aug 2, 2004, 12:31:02 PM (22 years ago)

Author:

desonia

Message:

Added an advance to next bucket in the doWork function where it searches for an entry in the hash table.

File:

• trunk/psLib/src/sysUtils/psHash.c (modified) (13 diffs)

trunk/psLib/src/sysUtils/psHash.c

@@ -1 +1 @@
 /** @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 <stdlib.h>
 #include <stdio.h>
@@ -25 +25 @@
 #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 +40 @@
     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;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;
-            }
-        }
-    }
-
+    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 +84 @@
     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 +120 @@
     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 +144 @@
     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 +179 @@
     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 +230 @@
 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 +239 @@
     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 +253 @@
     //    }
     //    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 +361 @@
     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 +387 @@
     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 +411 @@
     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;
 }