PLplot  5.10.0
hash.c
Go to the documentation of this file.
00001 //--------------------------------------------------------------------------
00002 //
00003 // File:           hash.c
00004 //
00005 // Purpose:        Hash table implementation
00006 //
00007 // Author:         Jerry Coffin
00008 //
00009 // Description:    Public domain code by Jerry Coffin, with improvements by
00010 //                 HenkJan Wolthuis.
00011 //                 Date last modified: 05-Jul-1997
00012 //
00013 // Revisions:      18-09-2002 -- modified by Pavel Sakov
00014 //
00015 //--------------------------------------------------------------------------
00016 
00017 #include <string.h>
00018 #include <stdlib.h>
00019 #include <assert.h>
00020 #include "hash.h"
00021 
00022 #define INT_PER_DOUBLE    2
00023 
00024 //* A hash table consists of an array of these buckets.
00025 //
00026 typedef struct ht_bucket
00027 {
00028     void * key;
00029     void            * data;
00030     int  id;                    // unique id -- just in case
00031     struct ht_bucket* next;
00032 } ht_bucket;
00033 
00034 //* Hash table structure.
00035 // Note that more nodes than `size' can be inserted in the table,
00036 // but performance degrades as this happens.
00037 //
00038 struct hashtable
00039 {
00040     int         size;           // table size
00041     int         n;              // current number of entries
00042     int         naccum;         // number of inserted entries
00043     int         nhash;          // number of used table elements
00044     ht_keycp    cp;
00045     ht_keyeq    eq;
00046     ht_key2hash hash;
00047     ht_bucket   ** table;
00048 };
00049 
00050 int d1eq( void* key1, void* key2 );
00051 
00052 // Creates a hashtable of specified size.
00053 //
00054 hashtable* ht_create( int size, ht_keycp cp, ht_keyeq eq, ht_key2hash hash )
00055 {
00056     hashtable* table = malloc( sizeof ( hashtable ) );
00057     ht_bucket** bucket;
00058     int      i;
00059 
00060     assert( sizeof ( double ) == INT_PER_DOUBLE * sizeof ( int ) );
00061     //
00062     // (used in d1hash() and d2hash())
00063     //
00064 
00065     if ( table == NULL )
00066         return NULL;
00067 
00068     if ( size <= 0 )
00069     {
00070         free( table );
00071         return NULL;
00072     }
00073 
00074     table->size  = size;
00075     table->table = malloc( sizeof ( ht_bucket* ) * (size_t) size );
00076     bucket       = table->table;
00077 
00078     if ( bucket == NULL )
00079     {
00080         free( table );
00081         return NULL;
00082     }
00083 
00084     for ( i = 0; i < size; ++i )
00085         bucket[i] = NULL;
00086     table->n      = 0;
00087     table->naccum = 0;
00088     table->nhash  = 0;
00089     table->eq     = eq;
00090     table->cp     = cp;
00091     table->hash   = hash;
00092 
00093     return table;
00094 }
00095 
00096 // Destroys a hash table.
00097 // (Take care of deallocating data by ht_process() prior to destroying the
00098 // table if necessary.)
00099 //
00100 // @param table Hash table to be destroyed
00101 //
00102 void ht_destroy( hashtable* table )
00103 {
00104     int i;
00105 
00106     if ( table == NULL )
00107         return;
00108 
00109     for ( i = 0; i < table->size; ++i )
00110     {
00111         ht_bucket* bucket;
00112 
00113         for ( bucket = ( table->table )[i]; bucket != NULL; )
00114         {
00115             ht_bucket* prev = bucket;
00116 
00117             free( bucket->key );
00118             bucket = bucket->next;
00119             free( prev );
00120         }
00121     }
00122 
00123     free( table->table );
00124     free( table );
00125 }
00126 
00127 // Inserts a new entry into the hash table.
00128 //
00129 // @param table The hash table
00130 // @param key Ponter to entry's key
00131 // @param data Pointer to associated data
00132 // @return Pointer to the old data associated with the key, NULL if the key
00133 //         wasn't in the table previously
00134 //
00135 void* ht_insert( hashtable* table, void* key, void* data )
00136 {
00137     unsigned int val = table->hash( key ) % (unsigned int) table->size;
00138     ht_bucket    * bucket;
00139 
00140     //
00141     // NULL means this bucket hasn't been used yet.  We'll simply allocate
00142     // space for our new bucket and put our data there, with the table
00143     // pointing at it.
00144     //
00145     if ( ( table->table )[val] == NULL )
00146     {
00147         bucket = malloc( sizeof ( ht_bucket ) );
00148         if ( bucket == NULL )
00149             return NULL;
00150 
00151         bucket->key  = table->cp( key );
00152         bucket->next = NULL;
00153         bucket->data = data;
00154         bucket->id   = table->naccum;
00155 
00156         ( table->table )[val] = bucket;
00157         table->n++;
00158         table->naccum++;
00159         table->nhash++;
00160 
00161         return bucket->data;
00162     }
00163 
00164     //
00165     // This spot in the table is already in use.  See if the current string
00166     // has already been inserted, and if so, return corresponding data.
00167     //
00168     for ( bucket = ( table->table )[val]; bucket != NULL; bucket = bucket->next )
00169         if ( table->eq( key, bucket->key ) == 1 )
00170         {
00171             void* old_data = bucket->data;
00172 
00173             bucket->data = data;
00174             bucket->id   = table->naccum;
00175             table->naccum++;
00176 
00177             return old_data;
00178         }
00179 
00180     //
00181     // This key must not be in the table yet.  We'll add it to the head of
00182     // the list at this spot in the hash table.  Speed would be slightly
00183     // improved if the list was kept sorted instead.  In this case, this
00184     // code would be moved into the loop above, and the insertion would take
00185     // place as soon as it was determined that the present key in the list
00186     // was larger than this one.
00187     //
00188     bucket = (ht_bucket *) malloc( sizeof ( ht_bucket ) );
00189     if ( bucket == NULL )
00190         return 0;
00191     bucket->key  = table->cp( key );
00192     bucket->data = data;
00193     bucket->next = ( table->table )[val];
00194     bucket->id   = table->naccum;
00195 
00196     ( table->table )[val] = bucket;
00197     table->n++;
00198     table->naccum++;
00199 
00200     return data;
00201 }
00202 
00203 // Returns a pointer to the data associated with a key.  If the key has
00204 // not been inserted in the table, returns NULL.
00205 //
00206 // @param table The hash table
00207 // @param key The key
00208 // @return The associated data or NULL
00209 //
00210 void* ht_find( hashtable* table, void* key )
00211 {
00212     unsigned int val = table->hash( key ) % (unsigned int) table->size;
00213     ht_bucket    * bucket;
00214 
00215     if ( ( table->table )[val] == NULL )
00216         return NULL;
00217 
00218     for ( bucket = ( table->table )[val]; bucket != NULL; bucket = bucket->next )
00219         if ( table->eq( key, bucket->key ) == 1 )
00220             return bucket->data;
00221 
00222     return NULL;
00223 }
00224 
00225 // Deletes an entry from the table.  Returns a pointer to the data that
00226 // was associated with the key so that the calling code can dispose it
00227 // properly.
00228 //
00229 // @param table The hash table
00230 // @param key The key
00231 // @return The associated data or NULL
00232 //
00233 void* ht_delete( hashtable* table, void* key )
00234 {
00235     unsigned int val = table->hash( key ) % (unsigned int) table->size;
00236     ht_bucket    * prev;
00237     ht_bucket    * bucket;
00238     void         * data;
00239 
00240     if ( ( table->table )[val] == NULL )
00241         return NULL;
00242 
00243     //
00244     // Traverse the list, keeping track of the previous node in the list.
00245     // When we find the node to delete, we set the previous node's next
00246     // pointer to point to the node after ourself instead.  We then delete
00247     // the key from the present node, and return a pointer to the data it
00248     // contains.
00249     //
00250     for ( prev = NULL, bucket = ( table->table )[val]; bucket != NULL; prev = bucket, bucket = bucket->next )
00251     {
00252         if ( table->eq( key, bucket->key ) == 1 )
00253         {
00254             data = bucket->data;
00255             if ( prev != NULL )
00256                 prev->next = bucket->next;
00257             else
00258             {
00259                 //
00260                 // If 'prev' still equals NULL, it means that we need to
00261                 // delete the first node in the list. This simply consists
00262                 // of putting our own 'next' pointer in the array holding
00263                 // the head of the list.  We then dispose of the current
00264                 // node as above.
00265                 //
00266                 ( table->table )[val] = bucket->next;
00267                 table->nhash--;
00268             }
00269             free( bucket->key );
00270             free( bucket );
00271             table->n--;
00272 
00273             return data;
00274         }
00275     }
00276 
00277     //
00278     // If we get here, it means we didn't find the item in the table. Signal
00279     // this by returning NULL.
00280     //
00281     return NULL;
00282 }
00283 
00284 // For each entry, calls a specified function with corresponding data as a
00285 // parameter.
00286 //
00287 // @param table The hash table
00288 // @param func The action function
00289 //
00290 void ht_process( hashtable* table, void ( *func )( void* ) )
00291 {
00292     int i;
00293 
00294     for ( i = 0; i < table->size; ++i )
00295         if ( ( table->table )[i] != NULL )
00296         {
00297             ht_bucket* bucket;
00298 
00299             for ( bucket = ( table->table )[i]; bucket != NULL; bucket = bucket->next )
00300                 func( bucket->data );
00301         }
00302 }
00303 
00304 //
00305 // functions for for string keys
00306 //
00307 
00308 static unsigned int strhash( void* key )
00309 {
00310     char         * str     = (char *) key;
00311     unsigned int hashvalue = 0;
00312 
00313     while ( *str != 0 )
00314     {
00315         hashvalue  ^= *(unsigned int *) str;
00316         hashvalue <<= 1;
00317         str++;
00318     }
00319 
00320     return hashvalue;
00321 }
00322 
00323 static void* strcp( void* key )
00324 {
00325     return (void *) strdup( (const char *) key );
00326 }
00327 
00328 static int streq( void* key1, void* key2 )
00329 {
00330     return !strcmp( key1, key2 );
00331 }
00332 
00333 // functions for for double keys
00334 
00335 static unsigned int d1hash( void* key )
00336 {
00337     unsigned int* v = (unsigned int *) key;
00338 
00339 #if INT_PER_DOUBLE == 2
00340     return v[0] + v[1];
00341 #else
00342 #error not implemented
00343 #endif
00344 }
00345 
00346 static void* d1cp( void* key )
00347 {
00348     double* newkey = malloc( sizeof ( double ) );
00349 
00350     *newkey = *(double *) key;
00351 
00352     return newkey;
00353 }
00354 
00355 int d1eq( void* key1, void* key2 )
00356 {
00357     return *(double *) key1 == *(double *) key2;
00358 }
00359 
00360 //
00361 // functions for for double[2] keys
00362 //
00363 
00364 #include "math.h"
00365 
00366 static unsigned int d2hash( void* key )
00367 {
00368     unsigned int* v = (unsigned int *) key;
00369 
00370 #if INT_PER_DOUBLE == 2
00371     //
00372     // PS: here multiplications suppose to make (a,b) and (b,a) generate
00373     // different hash values
00374     //
00375     return v[0] + v[1] + v[2] * 3 + v[3] * 7;
00376 #else
00377 #error not implemented
00378 #endif
00379 }
00380 
00381 static void* d2cp( void* key )
00382 {
00383     double* newkey = malloc( sizeof ( double ) * 2 );
00384 
00385     newkey[0] = ( (double *) key )[0];
00386     newkey[1] = ( (double *) key )[1];
00387 
00388     return newkey;
00389 }
00390 
00391 static int d2eq( void* key1, void* key2 )
00392 {
00393     return ( ( (double *) key1 )[0] == ( (double *) key2 )[0] ) && ( ( (double *) key1 )[1] == ( (double *) key2 )[1] );
00394 }
00395 
00396 hashtable* ht_create_d1( int size )
00397 {
00398     return ht_create( size, d1cp, d1eq, d1hash );
00399 }
00400 
00401 hashtable* ht_create_d2( int size )
00402 {
00403     return ht_create( size, d2cp, d2eq, d2hash );
00404 }
00405 
00406 hashtable* ht_create_str( int size )
00407 {
00408     return ht_create( size, strcp, streq, strhash );
00409 }
00410 
00411 #ifdef HT_TEST
00412 
00413 #include <stdio.h>
00414 #include <limits.h>
00415 
00416 #define BUFSIZE    1024
00417 
00418 static void print_double( void* data )
00419 {
00420     printf( " \"%d\"", (int) *(double *) data );
00421 }
00422 
00423 static void print_string( void* data )
00424 {
00425     printf( " \"%s\"", (char *) data );
00426 }
00427 
00428 int main()
00429 {
00430     double   points[] = {
00431         922803.7855, 7372394.688,   0,
00432         922849.2037, 7372307.027,   1,
00433         922894.657,  7372219.306,   2,
00434         922940.1475, 7372131.528,   3,
00435         922985.6777, 7372043.692,   4,
00436         923031.2501, 7371955.802,   5,
00437         923076.8669, 7371867.857,   6,
00438         923122.5307, 7371779.861,   7,
00439         923168.2439, 7371691.816,   8,
00440         923214.0091, 7371603.722,   9,
00441         923259.8288, 7371515.583,  10,
00442         922891.3958, 7372440.117,  11,
00443         922936.873,  7372352.489,  12,
00444         922982.3839, 7372264.804,  13,
00445         923027.9308, 7372177.064,  14,
00446         923073.5159, 7372089.268,  15,
00447         923119.1415,  7372001.42,  16,
00448         923164.8099, 7371913.521,  17,
00449         923210.5233, 7371825.572,  18,
00450         923256.2841, 7371737.575,  19,
00451         923302.0946, 7371649.534,  20,
00452         923347.9572,  7371561.45,  21,
00453         922978.9747, 7372485.605,  22,
00454         923024.5085, 7372398.009,  23,
00455         923070.0748, 7372310.358,  24,
00456         923115.6759, 7372222.654,  25,
00457         923161.3136, 7372134.897,  26,
00458         923206.9903,  7372047.09,  27,
00459         923252.7079, 7371959.233,  28,
00460         923298.4686,  7371871.33,  29,
00461         923344.2745, 7371783.381,  30,
00462         923390.1279, 7371695.389,  31,
00463         923436.0309, 7371607.357,  32,
00464         923066.5232, 7372531.148,  33,
00465         923112.1115, 7372443.583,  34,
00466         923157.7311, 7372355.966,  35,
00467         923203.3842, 7372268.296,  36,
00468         923249.0725, 7372180.577,  37,
00469         923294.7981, 7372092.808,  38,
00470         923340.5628, 7372004.993,  39,
00471         923386.3686, 7371917.132,  40,
00472         923432.2176, 7371829.229,  41,
00473         923478.1116, 7371741.284,  42,
00474         923524.0527, 7371653.302,  43,
00475         923154.0423, 7372576.746,  44,
00476         923199.6831, 7372489.211,  45,
00477         923245.3541, 7372401.625,  46,
00478         923291.0572, 7372313.989,  47,
00479         923336.7941, 7372226.305,  48,
00480         923382.5667, 7372138.574,  49,
00481         923428.3766, 7372050.798,  50,
00482         923474.2256, 7371962.978,  51,
00483         923520.1155, 7371875.118,  52,
00484         923566.0481, 7371787.218,  53,
00485         923612.0252, 7371699.282,  54,
00486         923241.533,  7372622.396,  55,
00487         923287.2244, 7372534.889,  56,
00488         923332.9449, 7372447.334,  57,
00489         923378.6963, 7372359.731,  58,
00490         923424.4801, 7372272.081,  59,
00491         923470.2979, 7372184.385,  60,
00492         923516.1513, 7372096.646,  61,
00493         923562.0418, 7372008.866,  62,
00494         923607.9709, 7371921.046,  63,
00495         923653.9402, 7371833.188,  64,
00496         923699.9514, 7371745.296,  65,
00497         923328.9962, 7372668.095,  66,
00498         923374.7365, 7372580.617,  67,
00499         923420.5049, 7372493.091,  68,
00500         923466.303,  7372405.519,  69,
00501         923512.1321, 7372317.901,  70,
00502         923557.9936,  7372230.24,  71,
00503         923603.8889, 7372142.536,  72,
00504         923649.8192, 7372054.793,  73,
00505         923695.786,  7371967.011,  74,
00506         923741.7905, 7371879.193,  75,
00507         923787.8341, 7371791.342,  76,
00508         923416.4327, 7372713.844,  77,
00509         923462.2204, 7372626.393,  78,
00510         923508.0353, 7372538.895,  79,
00511         923553.8787, 7372451.353,  80,
00512         923599.7517, 7372363.766,  81,
00513         923645.6555, 7372276.137,  82,
00514         923691.5914, 7372188.467,  83,
00515         923737.5603, 7372100.757,  84,
00516         923783.5634, 7372013.011,  85,
00517         923829.6017, 7371925.231,  86,
00518         923875.6763, 7371837.419,  87,
00519         923503.8433,  7372759.64,  88,
00520         923549.6771, 7372672.214,  89,
00521         923595.5372, 7372584.744,  90,
00522         923641.4246,  7372497.23,  91,
00523         923687.3404, 7372409.673,  92,
00524         923733.2855, 7372322.074,  93,
00525         923779.2608, 7372234.436,  94,
00526         923825.2672, 7372146.759,  95,
00527         923871.3056, 7372059.047,  96,
00528         923917.3766, 7371971.301,  97,
00529         923963.4812, 7371883.524,  98,
00530         923591.2288, 7372805.481,  99,
00531         923637.1076, 7372718.081, 100,
00532         923683.0118, 7372630.638, 101,
00533         923728.9423, 7372543.151, 102,
00534         923774.8998, 7372455.622, 103,
00535         923820.8852, 7372368.052, 104,
00536         923866.8991, 7372280.443, 105,
00537         923912.9422, 7372192.797, 106,
00538         923959.015,  7372105.116, 107,
00539         924005.118,  7372017.402, 108,
00540         924051.2518, 7371929.657, 109,
00541         923678.5898, 7372851.367, 110,
00542         923724.5126, 7372763.992, 111,
00543         923770.46,   7372676.574, 112,
00544         923816.4328, 7372589.113, 113,
00545         923862.4314, 7372501.611, 114,
00546         923908.4564, 7372414.069, 115,
00547         923954.5083, 7372326.488, 116,
00548         924000.5875,  7372238.87, 117,
00549         924046.6941, 7372151.218, 118,
00550         924092.8286, 7372063.533, 119,
00551         924138.9911, 7371975.818, 120
00552     };
00553 
00554     int      size = sizeof ( points ) / sizeof ( double ) / 3;
00555     hashtable* ht;
00556     int      i;
00557 
00558     //
00559     // double[2] key
00560     //
00561 
00562     printf( "\n1. Testing a table with key of double[2] type\n\n" );
00563 
00564     printf( "  creating a table..." );
00565     ht = ht_create_d2( size );
00566     printf( "done\n" );
00567 
00568     printf( "  inserting %d values from a file...", size );
00569     for ( i = 0; i < size; ++i )
00570         ht_insert( ht, &points[i * 3], &points[i * 3 + 2] );
00571     printf( "done\n" );
00572 
00573     printf( "  stats:\n" );
00574     printf( "    %d entries, %d table elements, %d filled elements\n", ht->n, ht->size, ht->nhash );
00575     printf( "    %f entries per hash value in use\n", (double) ht->n / ht->nhash );
00576 
00577     printf( "  finding and printing each 10th data:\n" );
00578     for ( i = 0; i < size; i += 10 )
00579     {
00580         double* point = &points[i * 3];
00581         double* data  = ht_find( ht, point );
00582 
00583         if ( data != NULL )
00584             printf( "    i = %d; data = \"%d\"\n", i, (int) *data );
00585         else
00586             printf( "    i = %d; data = <none>\n", i );
00587     }
00588 
00589     printf( "  removing every 3rd element..." );
00590     for ( i = 0; i < size; i += 3 )
00591     {
00592         double* point = &points[i * 3];
00593         ht_delete( ht, point );
00594     }
00595     printf( "done\n" );
00596 
00597     printf( "  stats:\n" );
00598     printf( "    %d entries, %d table elements, %d filled elements\n", ht->n, ht->size, ht->nhash );
00599     printf( "    %f entries per hash value in use\n", (double) ht->n / ht->nhash );
00600 
00601     printf( "  finding and printing each 10th data:\n" );
00602     for ( i = 0; i < size; i += 10 )
00603     {
00604         double* point = &points[i * 3];
00605         double* data  = ht_find( ht, point );
00606 
00607         if ( data != NULL )
00608             printf( "    i = %d; data = \"%d\"\n", i, (int) *data );
00609         else
00610             printf( "    i = %d; data = <none>\n", i );
00611     }
00612 
00613     printf( "  printing all data by calling ht_process():\n " );
00614     ht_process( ht, print_double );
00615 
00616     printf( "\n  destroying the hash table..." );
00617     ht_destroy( ht );
00618     printf( "done\n" );
00619 
00620     //
00621     // char* key
00622     //
00623 
00624     printf( "\n2. Testing a table with key of char* type\n\n" );
00625 
00626     printf( "  creating a table..." );
00627     ht = ht_create_str( size );
00628     printf( "done\n" );
00629 
00630     printf( "  inserting %d elements with deep copy of each data string...", size );
00631     for ( i = 0; i < size; ++i )
00632     {
00633         char key[BUFSIZE];
00634         char str[BUFSIZE];
00635         char * data;
00636 
00637         sprintf( key, "%d-th key", i );
00638         sprintf( str, "%d-th data", i );
00639         data = strdup( str );
00640         ht_insert( ht, key, data );
00641     }
00642     printf( "done\n" );
00643 
00644     printf( "  stats:\n" );
00645     printf( "    %d entries, %d table elements, %d filled elements\n", ht->n, ht->size, ht->nhash );
00646     printf( "    %f entries per hash value in use\n", (double) ht->n / ht->nhash );
00647 
00648     printf( "  finding and printing each 10th data:\n" );
00649     for ( i = 0; i < size; i += 10 )
00650     {
00651         char key[BUFSIZE];
00652         char * data;
00653 
00654         sprintf( key, "%d-th key", i );
00655         data = ht_find( ht, key );
00656         if ( data != NULL )
00657             printf( "    i = %d; data = \"%s\"\n", i, data );
00658         else
00659             printf( "    i = %d; data = <none>\n", i );
00660     }
00661 
00662     printf( "  removing every 3rd element..." );
00663     for ( i = 0; i < size; i += 3 )
00664     {
00665         char key[BUFSIZE];
00666 
00667         sprintf( key, "%d-th key", i );
00668         free( ht_delete( ht, key ) );
00669     }
00670     printf( "done\n" );
00671 
00672     printf( "  stats:\n" );
00673     printf( "    %d entries, %d table elements, %d filled elements\n", ht->n, ht->size, ht->nhash );
00674     printf( "    %f entries per hash value in use\n", (double) ht->n / ht->nhash );
00675 
00676     printf( "  finding and printing each 10th data:\n" );
00677     for ( i = 0; i < size; i += 10 )
00678     {
00679         char key[BUFSIZE];
00680         char * data;
00681 
00682         sprintf( key, "%d-th key", i );
00683         data = ht_find( ht, key );
00684         if ( data != NULL )
00685             printf( "    i = %d; data = \"%s\"\n", i, data );
00686         else
00687             printf( "    i = %d; data = <none>\n", i );
00688     }
00689 
00690     printf( "  printing all data by calling ht_process():\n " );
00691     ht_process( ht, print_string );
00692 
00693     printf( "\n  freeing the remaining data by calling ht_process()..." );
00694     ht_process( ht, free );
00695     printf( "done\n" );
00696 
00697     printf( "  destroying the hash table..." );
00698     ht_destroy( ht );
00699     printf( "done\n" );
00700 
00701     return 0;
00702 }
00703 
00704 #endif                          // HT_TEST
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines