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

Timestamp:

Aug 4, 2004, 1:37:39 PM (22 years ago)

Author:

desonia

Message:

found the server astyle upgrade was faulty, so the format was reset.

File:

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

trunk/psLib/src/sysUtils/psHash.c

@@ -10 +10 @@
 *  @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 +28 @@
 static void hashBucketFree( psHashBucket *bucket );
 static void *doHashWork( psHash* table, const char* key, void* data, bool remove
-                       )
-;
+                           )
+    ;
 static void hashFree( psHash *table );
 
@@ -45 +45 @@
     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 +89 @@
 {
     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 +123 @@
 {
     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 +150 @@
     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 +182 @@
 {
     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 +221 @@
   *****************************************************************************/
 static void *doHashWork( psHash *table, const char *key, void *data, bool remove
-                       )
+                           )
 {
     long int hash = 1;                  // This will contain an integer value
@@ -229 +229 @@
     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 +243 @@
     //    }
     //    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 +354 @@
 {
     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 +381 @@
 {
     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 +405 @@
     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;
 }