IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Changeset 1371


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/sysUtils/psHash.c

    r1295 r1371  
    11/** @file  psHash.c
    2  *
    3  *  @brief Contains support for basic hashing functions.
    4  *
    5  *  This file will hold the functions for defining a hash table with arbitrary
    6  *  data types, allocating/deallocating that hash table, adding and removing
    7  *  data from that hash table, and listing all keys defined in the hash table.
    8  *
    9  *  @author Robert Lupton, Princeton University
    10  *  @author George Gusciora, MHPCC
    11  *   
    12  *  @version $Revision: 1.11 $ $Name: not supported by cvs2svn $
    13  *  @date $Date: 2004-07-24 03:31:06 $
    14  *
    15  *  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
    16  */
     2*
     3*  @brief Contains support for basic hashing functions.
     4*
     5*  This file will hold the functions for defining a hash table with arbitrary
     6*  data types, allocating/deallocating that hash table, adding and removing
     7*  data from that hash table, and listing all keys defined in the hash table.
     8*
     9*  @author Robert Lupton, Princeton University
     10*  @author George Gusciora, MHPCC
     11*   
     12*  @version $Revision: 1.12 $ $Name: not supported by cvs2svn $
     13*  @date $Date: 2004-08-02 22:31:02 $
     14*
     15*  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
     16*/
    1717#include <stdlib.h>
    1818#include <stdio.h>
    … …  
    2525#include "psAbort.h"
    2626
    27 static psHashBucket *hashBucketAlloc(const char *key,void *data,psHashBucket *next);
    28 static void hashBucketFree(psHashBucket *bucket);
    29 static void *doHashWork(psHash* table, const char* key, void* data, bool remove
    30                            );
    31 static void hashFree(psHash *table);
     27static psHashBucket *hashBucketAlloc( const char *key, void *data, psHashBucket *next );
     28static void hashBucketFree( psHashBucket *bucket );
     29static void *doHashWork( psHash* table, const char* key, void* data, bool remove
     30                       )
     31;
     32static void hashFree( psHash *table );
    3233
    3334/******************************************************************************
    … …  
    3940    The linked list
    4041 *****************************************************************************/
    41 psList *psHashKeyList(psHash *table)
     42psList *psHashKeyList( psHash *table )
    4243{
    4344    int i = 0;                          // Loop index variable
    4445    psList *myLinkList = NULL;  // The output data structure
    4546    psHashBucket *ptr = NULL;           // Used to step thru linked list.
    46 
    47     if (table == NULL) {
    48         return NULL;
    49     }
    50 
     47   
     48    if ( table == NULL ) {
     49            return NULL;
     50        }
     51       
    5152    // Create the linked list
    52     myLinkList = psListAlloc(NULL);
    53 
     53    myLinkList = psListAlloc( NULL );
     54   
    5455    // Loop through every bucket in the hash table.  If that bucket is not
    5556    // NULL, then add the bucket's key to the linked list.
    56     for (i=0;i<table->nbucket;i++) {
    57         if (table->buckets[i] != NULL) {
    58             // Since a bucket contains a linked list of keys/data, we must
    59             // step trough each key in that linked list:
    60 
    61             ptr = table->buckets[i];
    62             while (ptr != NULL) {
    63                 psListAdd(myLinkList, ptr->key, PS_LIST_HEAD);
    64                 ptr = ptr->next;
    65             }
    66         }
    67     }
    68 
     57    for ( i = 0;i < table->nbucket;i++ ) {
     58            if ( table->buckets[ i ] != NULL ) {
     59                    // Since a bucket contains a linked list of keys/data, we must
     60                    // step trough each key in that linked list:
     61                   
     62                    ptr = table->buckets[ i ];
     63                    while ( ptr != NULL ) {
     64                            psListAdd( myLinkList, ptr->key, PS_LIST_HEAD );
     65                            ptr = ptr->next;
     66                        }
     67                }
     68        }
     69       
    6970    // Return the linked list
    70     return(myLinkList);
     71    return ( myLinkList );
    7172}
    7273
    … …  
    8384    the new hash bucket.
    8485 *****************************************************************************/
    85 static psHashBucket *hashBucketAlloc(const char *key,
    86                                      void *data,
    87                                      psHashBucket *next)
    88 {
    89     if (key == NULL) {
    90         psAbort(__func__, "psHashBucket() called with NULL key.");
    91     }
    92 
     86static psHashBucket *hashBucketAlloc( const char *key,
     87                                      void *data,
     88                                      psHashBucket *next )
     89{
     90    if ( key == NULL ) {
     91            psAbort( __func__, "psHashBucket() called with NULL key." );
     92        }
     93       
    9394    // Allocate memory for the new hash bucket.
    94     psHashBucket *bucket = psAlloc(sizeof(psHashBucket));
    95     p_psMemSetDeallocator(bucket,(psFreeFcn)hashBucketFree);
    96 
     95    psHashBucket *bucket = psAlloc( sizeof( psHashBucket ) );
     96    p_psMemSetDeallocator( bucket, ( psFreeFcn ) hashBucketFree );
     97   
    9798    // Initialize the bucket.
    98     bucket->key = psStringCopy(key);
    99 
    100     if (data == NULL) {
    101         // NOTE: Should we flag a warning message?
    102         bucket->data = NULL;
    103     } else {
    104         bucket->data = psMemIncrRefCounter(data);
    105     }
    106 
     99    bucket->key = psStringCopy( key );
     100   
     101    if ( data == NULL ) {
     102            // NOTE: Should we flag a warning message?
     103            bucket->data = NULL;
     104        } else {
     105            bucket->data = psMemIncrRefCounter( data );
     106        }
     107       
    107108    bucket->next = next;
    108 
     109   
    109110    return bucket;
    110111}
    … …  
    119120    NONE
    120121 *****************************************************************************/
    121 static void hashBucketFree(psHashBucket *bucket)
    122 {
    123     if (bucket == NULL) {
    124         return;
    125     }
    126 
     122static void hashBucketFree( psHashBucket *bucket )
     123{
     124    if ( bucket == NULL ) {
     125            return ;
     126        }
     127       
    127128    // A bucket is actually a linked list of buckets.  We recursively step
    128129    // through that linked list, free each bucket.
    129     psFree(bucket->next);
    130 
    131     psFree(bucket->key);
    132 
    133     psFree(bucket->data);
     130    psFree( bucket->next );
     131   
     132    psFree( bucket->key );
     133   
     134    psFree( bucket->data );
    134135}
    135136
    … …  
    143144    The new hash table.
    144145 *****************************************************************************/
    145 psHash *psHashAlloc(int nbucket) // initial number of buckets
     146psHash *psHashAlloc( int nbucket ) // initial number of buckets
    146147{
    147148    int i = 0;   // loop index variable
    148149    // Create the new hash table.
    149     psHash *table = psAlloc(sizeof(psHash));
    150     p_psMemSetDeallocator(table,(psFreeFcn)hashFree);
    151 
     150    psHash *table = psAlloc( sizeof( psHash ) );
     151    p_psMemSetDeallocator( table, ( psFreeFcn ) hashFree );
     152   
    152153    // Allocate memory for the buckets.
    153     table->buckets = psAlloc(nbucket*sizeof(psHashBucket *));
     154    table->buckets = psAlloc( nbucket * sizeof( psHashBucket * ) );
    154155    table->nbucket = nbucket;
    155 
    156     psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket);
    157 
     156   
     157    psTrace( "utils.hash", 1, "Creating %d-element hash table\n", nbucket );
     158   
    158159    // Initialize all buckets to NULL.
    159     for (i = 0; i < nbucket; i++)
    160     {
    161         table->buckets[i] = NULL;
    162     }
    163 
     160    for ( i = 0; i < nbucket; i++ )
     161        {
     162            table->buckets[ i ] = NULL;
     163        }
     164       
    164165    // Return the new hash table.
    165166    return table;
    … …  
    178179    NONE
    179180 *****************************************************************************/
    180 static void hashFree(psHash *table)
    181 {
    182     psHashBucket *tmp = NULL;           // Used to step through linked list.
     181static void hashFree( psHash *table )
     182{
     183    psHashBucket * tmp = NULL;           // Used to step through linked list.
    183184    psHashBucket *ptr = NULL;           // Used to step through linked list.
    184185    int i = 0;                          // Loop index variable.
    185 
    186     if (table == NULL) {
    187         return;
    188     }
    189 
     186   
     187    if ( table == NULL ) {
     188            return ;
     189        }
     190       
    190191    // Loop through each bucket in the hash table.  If that bucket is not
    191192    // NULL, then free the bucket via a function call to hashBucketFree();
    192 
    193     for (i = 0; i < table->nbucket; i++) {
    194         // A bucket is composed of a linked list of buckets.  We use the
    195         // "tmp" and "ptr" pointers to step through that list and free each
    196         // non-NULL bucket.
    197 
    198         if (table->buckets[i] != NULL) {
    199             ptr = table->buckets[i];
    200             while (ptr != NULL) {
    201                 tmp = ptr->next;
    202                 psFree(ptr);
    203                 ptr = tmp;
    204             }
    205         }
    206     }
    207 
     193   
     194    for ( i = 0; i < table->nbucket; i++ ) {
     195            // A bucket is composed of a linked list of buckets.  We use the
     196            // "tmp" and "ptr" pointers to step through that list and free each
     197            // non-NULL bucket.
     198           
     199            if ( table->buckets[ i ] != NULL ) {
     200                    ptr = table->buckets[ i ];
     201                    while ( ptr != NULL ) {
     202                            tmp = ptr->next;
     203                            psFree( ptr );
     204                            ptr = tmp;
     205                        }
     206                }
     207        }
     208       
    208209    // Free the bucket structure, then the hash table.
    209     psFree(table->buckets);
     210    psFree( table->buckets );
    210211}
    211212
    … …  
    229230there is little common code between those functions.
    230231  *****************************************************************************/
    231 static void *doHashWork(psHash *table, const char *key, void *data, bool remove
    232                            )
     232static void *doHashWork( psHash *table, const char *key, void *data, bool remove
     233                       )
    233234{
    234235    long int hash = 1;                  // This will contain an integer value
    … …  
    238239    psHashBucket *optr = NULL;          // "original pointer": used to step
    239240    // thru the linked list for a bucket.
    240 
     241   
    241242    // The following condition should never be true, since this is a private
    242243    // function, but I'm checking it anyway since future coders might change
    243244    // the way this procedure is called.
    244     if ((table == NULL) || (key == NULL)) {
    245 
    246         psAbort(__func__, "psHashRemove() called with NULL key or table.");
    247     }
    248 
     245    if ( ( table == NULL ) || ( key == NULL ) ) {
     246   
     247            psAbort( __func__, "psHashRemove() called with NULL key or table." );
     248        }
     249       
    249250    // NOTE: This is the originally supplied hash function.
    250251    //    for (int i = 0, len = strlen(key); i < len; i++) {
    … …  
    252253    //    }
    253254    //    hash &= (table->nbucket - 1);
    254 
     255   
    255256    // This hash algorithm is from Sedgewick.  NOTE: must reread to ensure that
    256257    // the size of the hash table is not required to be a prime number.
    257     tmpchar = (char *) key;
    258     for (hash = 0; *tmpchar != '\0'; tmpchar++) {
    259         hash = (64 * hash + *tmpchar) % (table->nbucket);
    260     }
    261 
     258    tmpchar = ( char * ) key;
     259    for ( hash = 0; *tmpchar != '\0'; tmpchar++ ) {
     260            hash = ( 64 * hash + *tmpchar ) % ( table->nbucket );
     261        }
     262       
    262263    // NOTE: This should not be necessary, but for now, I'm checking bounds
    263264    // anyway.
    264     if ((hash < 0) || (hash >= table->nbucket)) {
    265         psAbort(__func__,"Internal hash function out of range (%d)", hash);
    266     }
    267 
     265    if ( ( hash < 0 ) || ( hash >= table->nbucket ) ) {
     266            psAbort( __func__, "Internal hash function out of range (%d)", hash );
     267        }
     268       
    268269    // ptr will have the correct hash bucket.
    269     ptr = table->buckets[hash];
    270 
     270    ptr = table->buckets[ hash ];
     271   
    271272    // We know the correct hash bucket, now we need to know what to do.
    272273    // If the data parameter is NULL, then, by definition, this is a retrieve
    273274    // or a remove operation on the hash table.
    274 
    275     if (data == NULL) {
    276         if (remove
    277            ) {
    278             // We search through the linked list for this bucket in
    279             // the hash table and look for an entry for this key.
    280 
    281             optr = ptr;
    282             while (ptr != NULL) {
    283                 // Dtermine if this entry holds the correct key.
    284                 if (strcmp(key, ptr->key) == 0) {
    285                     // The following lines of code are fairly standard ways
    286                     // of removing an item from a single-linked list.
    287 
    288                     void *data = ptr->data;
    289                     optr->next = ptr->next;
    290                     if (ptr == table->buckets[hash]) {
    291                         table->buckets[hash] = ptr->next;
    292                     }
    293 
    294                     psFree(ptr);
    295 
    296                     // By definition, the data associated with that key
    297                     // must be returned, not freed.
    298                     return data;
     275   
     276    if ( data == NULL ) {
     277            if ( remove
     278               ) {
     279                    // We search through the linked list for this bucket in
     280                    // the hash table and look for an entry for this key.
     281                   
     282                    optr = ptr;
     283                    while ( ptr != NULL ) {
     284                            // Dtermine if this entry holds the correct key.
     285                            if ( strcmp( key, ptr->key ) == 0 ) {
     286                                    // The following lines of code are fairly standard ways
     287                                    // of removing an item from a single-linked list.
     288                                   
     289                                    void * data = ptr->data;
     290                                    optr->next = ptr->next;
     291                                    if ( ptr == table->buckets[ hash ] ) {
     292                                            table->buckets[ hash ] = ptr->next;
     293                                        }
     294                                       
     295                                    psFree( ptr );
     296                                   
     297                                    // By definition, the data associated with that key
     298                                    // must be returned, not freed.
     299                                    return data;
     300                                }
     301                            optr = ptr;
     302                            ptr = ptr->next;
     303                        }
     304                    return NULL;   // not in hash
    299305                }
    300                 optr = ptr;
    301                 ptr = ptr->next;
    302             }
    303             return NULL;   // not in hash
    304         }
    305         else {
    306             // If we get here, then a retrieve operation is requested.  So,
    307             // we step trough the linked list at this bucket, and return the
    308             // data once we find it, or return NULL if we don't.
    309             while (ptr != NULL) {
    310                 if (strcmp(key, ptr->key) == 0) {
    311                     return ptr->data;
     306            else {
     307                    // If we get here, then a retrieve operation is requested.  So,
     308                    // we step trough the linked list at this bucket, and return the
     309                    // data once we find it, or return NULL if we don't.
     310                    while ( ptr != NULL ) {
     311                            if ( strcmp( key, ptr->key ) == 0 ) {
     312                                    return ptr->data;
     313                                }
     314                            ptr = ptr->next;
     315                        }
     316                    return NULL;   // not in hash
    312317                }
    313                 ptr = ptr->next;
    314             }
    315             return NULL;   // not in hash
    316         }
    317     } else {
    318         // We get here if this procedure was called with non-NULL data.
    319         // Therefore, we should insert that data into the hash table.
    320         // First, we search through the linked list for this bucket in
    321         // the hash table and look for a duplicate entry for this key.
    322 
    323         while (ptr != NULL) {
    324             if (strcmp(key, ptr->key) == 0) {
    325                 // We have found this key in the hash table.
    326 
    327                 psTrace("utils.hash.insert", 3, "Replacing data for %s\n",
    328                         key);
    329 
    330                 // NOTE: I have changed this behavior from the originally
    331                 // supplied code.  Formerly, if itemFree was NULL, then
    332                 // the new data was not inserted into the hash table.
    333 
    334                 psFree(ptr->data);
    335 
    336                 ptr->data = psMemIncrRefCounter(data);
    337                 return data;
    338             }
    339         }
    340         // We did not found key in the linked list for this bucket of the hash
    341         // table.  So, we insert this data at the head of that linked list.
    342 
    343         table->buckets[hash] = hashBucketAlloc(key,
    344                                                data,
    345                                                table->buckets[hash]);
    346         return data;
    347     }
     318        } else {
     319            // We get here if this procedure was called with non-NULL data.
     320            // Therefore, we should insert that data into the hash table.
     321            // First, we search through the linked list for this bucket in
     322            // the hash table and look for a duplicate entry for this key.
     323           
     324            while ( ptr != NULL ) {
     325                    if ( strcmp( key, ptr->key ) == 0 ) {
     326                            // We have found this key in the hash table.
     327                           
     328                            psTrace( "utils.hash.insert", 3, "Replacing data for %s\n",
     329                                     key );
     330                                     
     331                            // NOTE: I have changed this behavior from the originally
     332                            // supplied code.  Formerly, if itemFree was NULL, then
     333                            // the new data was not inserted into the hash table.
     334                           
     335                            psFree( ptr->data );
     336                           
     337                            ptr->data = psMemIncrRefCounter( data );
     338                            return data;
     339                        }
     340                    ptr = ptr->next;
     341                }
     342            // We did not found key in the linked list for this bucket of the hash
     343            // table.  So, we insert this data at the head of that linked list.
     344           
     345            table->buckets[ hash ] = hashBucketAlloc( key,
     346                                     data,
     347                                     table->buckets[ hash ] );
     348            return data;
     349        }
    348350}
    349351
    … …  
    359361    boolean value defining success or failure
    360362 *****************************************************************************/
    361 bool psHashAdd(psHash *table, const char *key, void *data)
    362 {
    363     if (table == NULL) {
    364         psAbort(__func__, "psHashInsert() called with NULL hash table.");
    365     }
    366     if (key == NULL) {
    367         psAbort(__func__, "psHashInsert() called with NULL key.");
    368     }
    369     if (data == NULL) {
    370         psAbort(__func__, "psHashLookup() called with NULL data.");
    371     }
    372 
    373     return (doHashWork(table, key, data, 0) != NULL);
     363bool psHashAdd( psHash *table, const char *key, void *data )
     364{
     365    if ( table == NULL ) {
     366            psAbort( __func__, "psHashInsert() called with NULL hash table." );
     367        }
     368    if ( key == NULL ) {
     369            psAbort( __func__, "psHashInsert() called with NULL key." );
     370        }
     371    if ( data == NULL ) {
     372            psAbort( __func__, "psHashLookup() called with NULL data." );
     373        }
     374       
     375    return ( doHashWork( table, key, data, 0 ) != NULL );
    374376}
    375377
    … …  
    385387    The data associated with that key.
    386388 *****************************************************************************/
    387 void *psHashLookup(psHash *table,   // table to lookup key in
    388                    const char *key) // key to lookup
    389 {
    390     if (table == NULL) {
    391         psAbort(__func__, "psHashLookup() called with NULL hash table.");
    392     }
    393     if (key == NULL) {
    394         psAbort(__func__, "psHashLookup() called with NULL key.");
    395     }
    396 
    397 
    398     return doHashWork(table, key, NULL, 0);
     389void *psHashLookup( psHash *table,    // table to lookup key in
     390                    const char *key ) // key to lookup
     391{
     392    if ( table == NULL ) {
     393            psAbort( __func__, "psHashLookup() called with NULL hash table." );
     394        }
     395    if ( key == NULL ) {
     396            psAbort( __func__, "psHashLookup() called with NULL key." );
     397        }
     398       
     399       
     400    return doHashWork( table, key, NULL, 0 );
    399401}
    400402
    … …  
    409411    boolean value defining success or failure
    410412 *****************************************************************************/
    411 bool psHashRemove(psHash *table, const char *key)
    412 {
    413     void *data = NULL;
     413bool psHashRemove( psHash *table, const char *key )
     414{
     415    void * data = NULL;
    414416    bool retVal = false;
    415 
    416     if (table == NULL) {
    417         psAbort(__func__, "psHashRemove() called with NULL hash table.");
    418     }
    419     if (key == NULL) {
    420         psAbort(__func__, "psHashRemove() called with NULL key.");
    421     }
    422 
    423     data = doHashWork(table, key, NULL, 1);
    424     if ( data != NULL) {
    425         psFree(data);
    426         retVal = true;
    427     } else {
    428         retVal = false;
    429     }
     417   
     418    if ( table == NULL ) {
     419            psAbort( __func__, "psHashRemove() called with NULL hash table." );
     420        }
     421    if ( key == NULL ) {
     422            psAbort( __func__, "psHashRemove() called with NULL key." );
     423        }
     424       
     425    data = doHashWork( table, key, NULL, 1 );
     426    if ( data != NULL ) {
     427            psFree( data );
     428            retVal = true;
     429        } else {
     430            retVal = false;
     431        }
    430432    return retVal;
    431433}
Note: See TracChangeset for help on using the changeset viewer.