PLplot
5.10.0
|
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