Changeset 1407 for trunk/psLib/src/sysUtils/psHash.c
- Timestamp:
- Aug 6, 2004, 2:06:06 PM (22 years ago)
- File:
-
- 1 edited
-
trunk/psLib/src/sysUtils/psHash.c (modified) (20 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/psLib/src/sysUtils/psHash.c
r1406 r1407 1 1 2 /** @file psHash.c 2 3 * … … 10 11 * @author George Gusciora, MHPCC 11 12 * 12 * @version $Revision: 1.1 5$ $Name: not supported by cvs2svn $13 * @date $Date: 2004-08-0 6 22:34:05$13 * @version $Revision: 1.16 $ $Name: not supported by cvs2svn $ 14 * @date $Date: 2004-08-07 00:06:06 $ 14 15 * 15 16 * Copyright 2004 Maui High Performance Computing Center, University of Hawaii … … 25 26 #include "psAbort.h" 26 27 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 ; 32 static void hashFree( psHash *table ); 28 static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next); 29 static void hashBucketFree(psHashBucket * bucket); 30 static void *doHashWork(psHash * table, const char *key, void *data, bool remove 31 ); 32 static void hashFree(psHash * table); 33 33 34 34 /****************************************************************************** … … 40 40 The linked list 41 41 *****************************************************************************/ 42 psList *psHashKeyList( psHash *table)43 { 44 int i = 0; 42 psList *psHashKeyList(psHash * table) 43 { 44 int i = 0; // Loop index variable 45 45 psList *myLinkList = NULL; // The output data structure 46 psHashBucket *ptr = NULL; 47 48 if ( table == NULL) {46 psHashBucket *ptr = NULL; // Used to step thru linked list. 47 48 if (table == NULL) { 49 49 return NULL; 50 50 } 51 52 51 // Create the linked list 53 myLinkList = psListAlloc( NULL);52 myLinkList = psListAlloc(NULL); 54 53 55 54 // Loop through every bucket in the hash table. If that bucket is not 56 55 // NULL, then add the bucket's key to the linked list. 57 for ( i = 0;i < table->nbucket;i++) {58 if ( table->buckets[ i ] != NULL) {56 for (i = 0; i < table->nbucket; i++) { 57 if (table->buckets[i] != NULL) { 59 58 // Since a bucket contains a linked list of keys/data, we must 60 59 // step trough each key in that linked list: 61 60 62 ptr = table->buckets[ i];63 while ( ptr != NULL) {64 psListAdd( myLinkList, ptr->key, PS_LIST_HEAD);61 ptr = table->buckets[i]; 62 while (ptr != NULL) { 63 psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); 65 64 ptr = ptr->next; 66 65 } … … 69 68 70 69 // Return the linked list 71 return ( myLinkList ); 72 } 73 74 70 return (myLinkList); 71 } 75 72 76 73 /****************************************************************************** … … 84 81 the new hash bucket. 85 82 *****************************************************************************/ 86 static 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 83 static psHashBucket *hashBucketAlloc(const char *key, void *data, psHashBucket * next) 84 { 85 if (key == NULL) { 86 psAbort(__func__, "psHashBucket() called with NULL key."); 87 } 94 88 // Allocate memory for the new hash bucket. 95 psHashBucket *bucket = psAlloc( sizeof( psHashBucket ) ); 96 p_psMemSetDeallocator( bucket, ( psFreeFcn ) hashBucketFree ); 89 psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); 90 91 p_psMemSetDeallocator(bucket, (psFreeFcn) hashBucketFree); 97 92 98 93 // Initialize the bucket. 99 bucket->key = psStringCopy( key);100 101 if ( data == NULL) {94 bucket->key = psStringCopy(key); 95 96 if (data == NULL) { 102 97 // NOTE: Should we flag a warning message? 103 98 bucket->data = NULL; 104 99 } else { 105 bucket->data = psMemIncrRefCounter( data);100 bucket->data = psMemIncrRefCounter(data); 106 101 } 107 102 … … 110 105 return bucket; 111 106 } 112 113 107 114 108 /****************************************************************************** … … 120 114 NONE 121 115 *****************************************************************************/ 122 static void hashBucketFree( psHashBucket *bucket ) 123 { 124 if ( bucket == NULL ) { 125 return ; 126 } 127 116 static void hashBucketFree(psHashBucket * bucket) 117 { 118 if (bucket == NULL) { 119 return; 120 } 128 121 // A bucket is actually a linked list of buckets. We recursively step 129 122 // through that linked list, free each bucket. 130 psFree( bucket->next ); 131 132 psFree( bucket->key ); 133 134 psFree( bucket->data ); 135 } 136 123 psFree(bucket->next); 124 125 psFree(bucket->key); 126 127 psFree(bucket->data); 128 } 137 129 138 130 /****************************************************************************** … … 144 136 The new hash table. 145 137 *****************************************************************************/ 146 psHash *psHashAlloc( int nbucket ) // initial number of buckets 147 { 148 int i = 0; // loop index variable 138 psHash *psHashAlloc(int nbucket) // initial number of buckets 139 { 140 int i = 0; // loop index variable 141 149 142 // Create the new hash table. 150 psHash *table = psAlloc( sizeof( psHash ) ); 151 p_psMemSetDeallocator( table, ( psFreeFcn ) hashFree ); 143 psHash *table = psAlloc(sizeof(psHash)); 144 145 p_psMemSetDeallocator(table, (psFreeFcn) hashFree); 152 146 153 147 // Allocate memory for the buckets. 154 table->buckets = psAlloc( nbucket * sizeof( psHashBucket * ));148 table->buckets = psAlloc(nbucket * sizeof(psHashBucket *)); 155 149 table->nbucket = nbucket; 156 150 157 psTrace( "utils.hash", 1, "Creating %d-element hash table\n", nbucket);151 psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); 158 152 159 153 // Initialize all buckets to NULL. 160 for ( i = 0; i < nbucket; i++)154 for (i = 0; i < nbucket; i++) 161 155 { 162 table->buckets[ i] = NULL;156 table->buckets[i] = NULL; 163 157 } 164 158 … … 166 160 return table; 167 161 } 168 169 170 162 171 163 /****************************************************************************** … … 179 171 NONE 180 172 *****************************************************************************/ 181 static void hashFree( psHash *table ) 182 { 183 int i = 0; // Loop index variable. 184 185 if ( table == NULL ) { 186 return ; 187 } 188 173 static void hashFree(psHash * table) 174 { 175 int i = 0; // Loop index variable. 176 177 if (table == NULL) { 178 return; 179 } 189 180 // Loop through each bucket in the hash table. If that bucket is not 190 181 // NULL, then free the bucket via a function call to hashBucketFree(); 191 for ( i = 0; i < table->nbucket; i++) {182 for (i = 0; i < table->nbucket; i++) { 192 183 193 184 // A bucket is composed of a linked list of buckets. 194 if ( table->buckets[ i ] != NULL) {195 psFree( table->buckets[ i ]);185 if (table->buckets[i] != NULL) { 186 psFree(table->buckets[i]); 196 187 } 197 188 } 198 189 199 190 // Free the bucket structure, then the hash table. 200 psFree( table->buckets);191 psFree(table->buckets); 201 192 } 202 193 … … 220 211 there is little common code between those functions. 221 212 *****************************************************************************/ 222 static void *doHashWork( psHash *table, const char *key, void *data, bool remove213 static void *doHashWork(psHash * table, const char *key, void *data, bool remove 223 214 ) 224 215 { 225 long int hash = 1; // This will contain an integer value 216 long int hash = 1; // This will contain an integer value 217 226 218 // "hashed" from the key. 227 char *tmpchar = NULL; // Used in computing the hash function. 228 psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. 229 psHashBucket *optr = NULL; // "original pointer": used to step 219 char *tmpchar = NULL; // Used in computing the hash function. 220 psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. 221 psHashBucket *optr = NULL; // "original pointer": used to step 222 230 223 // thru the linked list for a bucket. 231 224 … … 233 226 // function, but I'm checking it anyway since future coders might change 234 227 // the way this procedure is called. 235 if ( ( table == NULL ) || ( key == NULL ) ) { 236 237 psAbort( __func__, "psHashRemove() called with NULL key or table." ); 238 } 239 228 if ((table == NULL) || (key == NULL)) { 229 230 psAbort(__func__, "psHashRemove() called with NULL key or table."); 231 } 240 232 // NOTE: This is the originally supplied hash function. 241 // 242 // 243 // 244 // 233 // for (int i = 0, len = strlen(key); i < len; i++) { 234 // hash = (hash << 1) ^ key[i]; 235 // } 236 // hash &= (table->nbucket - 1); 245 237 246 238 // This hash algorithm is from Sedgewick. NOTE: must reread to ensure that 247 239 // the size of the hash table is not required to be a prime number. 248 tmpchar = ( char * )key;249 for ( hash = 0; *tmpchar != '\0'; tmpchar++) {250 hash = ( 64 * hash + *tmpchar ) % ( table->nbucket);240 tmpchar = (char *)key; 241 for (hash = 0; *tmpchar != '\0'; tmpchar++) { 242 hash = (64 * hash + *tmpchar) % (table->nbucket); 251 243 } 252 244 253 245 // NOTE: This should not be necessary, but for now, I'm checking bounds 254 246 // anyway. 255 if ( ( hash < 0 ) || ( hash >= table->nbucket ) ) { 256 psAbort( __func__, "Internal hash function out of range (%d)", hash ); 257 } 258 247 if ((hash < 0) || (hash >= table->nbucket)) { 248 psAbort(__func__, "Internal hash function out of range (%d)", hash); 249 } 259 250 // ptr will have the correct hash bucket. 260 ptr = table->buckets[ hash];251 ptr = table->buckets[hash]; 261 252 262 253 // We know the correct hash bucket, now we need to know what to do. … … 264 255 // or a remove operation on the hash table. 265 256 266 if ( data == NULL ) { 267 if ( remove 268 ) { 269 // We search through the linked list for this bucket in 270 // the hash table and look for an entry for this key. 271 257 if (data == NULL) { 258 if (remove 259 ) { 260 // We search through the linked list for this bucket in 261 // the hash table and look for an entry for this key. 262 263 optr = ptr; 264 while (ptr != NULL) { 265 // Dtermine if this entry holds the correct key. 266 if (strcmp(key, ptr->key) == 0) { 267 // The following lines of code are fairly standard ways 268 // of removing an item from a single-linked list. 269 270 void *data = ptr->data; 271 272 optr->next = ptr->next; 273 if (ptr == table->buckets[hash]) { 274 table->buckets[hash] = ptr->next; 275 } 276 277 psFree(ptr); 278 279 // By definition, the data associated with that key 280 // must be returned, not freed. 281 return data; 282 } 272 283 optr = ptr; 273 while ( ptr != NULL ) { 274 // Dtermine if this entry holds the correct key. 275 if ( strcmp( key, ptr->key ) == 0 ) { 276 // The following lines of code are fairly standard ways 277 // of removing an item from a single-linked list. 278 279 void * data = ptr->data; 280 optr->next = ptr->next; 281 if ( ptr == table->buckets[ hash ] ) { 282 table->buckets[ hash ] = ptr->next; 283 } 284 285 psFree( ptr ); 286 287 // By definition, the data associated with that key 288 // must be returned, not freed. 289 return data; 290 } 291 optr = ptr; 292 ptr = ptr->next; 293 } 294 return NULL; // not in hash 284 ptr = ptr->next; 295 285 } 286 return NULL; // not in hash 287 } 296 288 else { 297 289 // If we get here, then a retrieve operation is requested. So, 298 290 // we step trough the linked list at this bucket, and return the 299 291 // data once we find it, or return NULL if we don't. 300 while ( ptr != NULL) {301 if ( strcmp( key, ptr->key ) == 0) {292 while (ptr != NULL) { 293 if (strcmp(key, ptr->key) == 0) { 302 294 return ptr->data; 303 295 } 304 296 ptr = ptr->next; 305 297 } 306 return NULL; // not in hash298 return NULL; // not in hash 307 299 } 308 300 } else { … … 312 304 // the hash table and look for a duplicate entry for this key. 313 305 314 while ( ptr != NULL) {315 if ( strcmp( key, ptr->key ) == 0) {306 while (ptr != NULL) { 307 if (strcmp(key, ptr->key) == 0) { 316 308 // We have found this key in the hash table. 317 309 318 psTrace( "utils.hash.insert", 3, "Replacing data for %s\n", 319 key ); 310 psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); 320 311 321 312 // NOTE: I have changed this behavior from the originally … … 323 314 // the new data was not inserted into the hash table. 324 315 325 psFree( ptr->data);326 327 ptr->data = psMemIncrRefCounter( data);316 psFree(ptr->data); 317 318 ptr->data = psMemIncrRefCounter(data); 328 319 return data; 329 320 } … … 333 324 // table. So, we insert this data at the head of that linked list. 334 325 335 table->buckets[ hash ] = hashBucketAlloc( key, 336 data, 337 table->buckets[ hash ] ); 326 table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); 338 327 return data; 339 328 } … … 351 340 boolean value defining success or failure 352 341 *****************************************************************************/ 353 bool psHashAdd( psHash *table, const char *key, void *data)354 { 355 if ( table == NULL) {356 psAbort( __func__, "psHashInsert() called with NULL hash table.");357 } 358 if ( key == NULL) {359 psAbort( __func__, "psHashInsert() called with NULL key.");360 } 361 if ( data == NULL) {362 psAbort( __func__, "psHashLookup() called with NULL data.");363 } 364 365 return ( doHashWork( table, key, data, 0 ) != NULL);342 bool psHashAdd(psHash * table, const char *key, void *data) 343 { 344 if (table == NULL) { 345 psAbort(__func__, "psHashInsert() called with NULL hash table."); 346 } 347 if (key == NULL) { 348 psAbort(__func__, "psHashInsert() called with NULL key."); 349 } 350 if (data == NULL) { 351 psAbort(__func__, "psHashLookup() called with NULL data."); 352 } 353 354 return (doHashWork(table, key, data, 0) != NULL); 366 355 } 367 356 … … 377 366 The data associated with that key. 378 367 *****************************************************************************/ 379 void *psHashLookup( psHash *table, // table to lookup key in 380 const char *key ) // key to lookup 381 { 382 if ( table == NULL ) { 383 psAbort( __func__, "psHashLookup() called with NULL hash table." ); 384 } 385 if ( key == NULL ) { 386 psAbort( __func__, "psHashLookup() called with NULL key." ); 387 } 388 389 390 return doHashWork( table, key, NULL, 0 ); 368 void *psHashLookup(psHash * table, // table to lookup key in 369 const char *key) // key to lookup 370 { 371 if (table == NULL) { 372 psAbort(__func__, "psHashLookup() called with NULL hash table."); 373 } 374 if (key == NULL) { 375 psAbort(__func__, "psHashLookup() called with NULL key."); 376 } 377 378 return doHashWork(table, key, NULL, 0); 391 379 } 392 380 … … 401 389 boolean value defining success or failure 402 390 *****************************************************************************/ 403 bool psHashRemove( psHash *table, const char *key)404 { 405 void * 391 bool psHashRemove(psHash * table, const char *key) 392 { 393 void *data = NULL; 406 394 bool retVal = false; 407 395 408 if ( table == NULL) {409 psAbort( __func__, "psHashRemove() called with NULL hash table.");410 } 411 if ( key == NULL) {412 psAbort( __func__, "psHashRemove() called with NULL key.");413 } 414 415 data = doHashWork( table, key, NULL, 1);416 if ( data != NULL) {417 psFree( data);396 if (table == NULL) { 397 psAbort(__func__, "psHashRemove() called with NULL hash table."); 398 } 399 if (key == NULL) { 400 psAbort(__func__, "psHashRemove() called with NULL key."); 401 } 402 403 data = doHashWork(table, key, NULL, 1); 404 if (data != NULL) { 405 psFree(data); 418 406 retVal = true; 419 407 } else {
Note:
See TracChangeset
for help on using the changeset viewer.
