Changeset 964 for trunk/psLib/src/sysUtils/psHash.c
- Timestamp:
- Jun 9, 2004, 2:09:55 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
r919 r964 4 4 * 5 5 * This file will hold the functions for defining a hash table with arbitrary 6 * data types, allocating/deallocating that has table, adding and removing6 * data types, allocating/deallocating that hash table, adding and removing 7 7 * data from that hash table, and listing all keys defined in the hash table. 8 8 * … … 10 10 * @author George Gusciora, MHPCC 11 11 * 12 * @version $Revision: 1. 7$ $Name: not supported by cvs2svn $13 * @date $Date: 2004-06- 08 19:08:40$12 * @version $Revision: 1.8 $ $Name: not supported by cvs2svn $ 13 * @date $Date: 2004-06-10 00:09:55 $ 14 14 * 15 15 * Copyright 2004 Maui High Performance Computing Center, University of Hawaii … … 18 18 #include <stdio.h> 19 19 #include <string.h> 20 //#include "psLib.h"21 20 #include "psHash.h" 22 21 #include "psMemory.h" … … 25 24 #include "psAbort.h" 26 25 26 27 /****************************************************************************** 28 psHashKeyList(table): this function creates a linked list with an entry in 29 that list for every key in the hash table. 30 Inputs: 31 table: a hash table 32 Return; 33 The linked list 34 *****************************************************************************/ 27 35 psList *psHashKeyList(psHash *table) 28 36 { 29 int i = 0; 30 psList *myLinkList = NULL; 37 int i = 0; // Loop index variable 38 psList *myLinkList = NULL; // The output data structure 39 psHashBucket *ptr = NULL; // Used to step thru linked list. 31 40 32 41 if (table == NULL) { … … 34 43 } 35 44 45 // Create the linked list 36 46 myLinkList = psListAlloc(NULL); 37 47 48 // Loop through every bucket in the hash table. If that bucket is not 49 // NULL, then add the bucket's key to the linked list. 38 50 for (i=0;i<table->nbucket;i++) { 39 51 if (table->buckets[i] != NULL) { 40 psListAdd(myLinkList, (table->buckets[i])->key, PS_LIST_HEAD); 52 // Since a bucket contains a linked list of keys/data, we must 53 // step trough each key in that linked list: 54 55 ptr = table->buckets[i]; 56 while (ptr != NULL) { 57 psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); 58 ptr = ptr->next; 59 } 41 60 } 42 61 } 43 62 63 // Return the linked list 44 64 return(myLinkList); 45 65 } 46 66 47 /****************************************************************************** 48 Construct buckets 67 68 69 /****************************************************************************** 70 hashBucketAlloc(key, data, next): This procedure creates a new hash bucket 71 with the specified key, data, and next. 72 Inputs: 73 key: the new bucket's key pointer 74 data: the new bucket's data pointer 75 next: the new bucket's key pointer 76 Return: 77 the new hash bucket. 49 78 *****************************************************************************/ 50 79 static psHashBucket *hashBucketAlloc(const char *key, … … 52 81 psHashBucket *next) 53 82 { 83 if (key == NULL) { 84 psAbort(__func__, "psHashBucket() called with NULL key."); 85 } 86 87 // Allocate memory for the new hash bucket. 54 88 psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); 55 89 90 // Initialize the bucket. 56 91 bucket->key = psStringCopy(key); 57 bucket->data = psMemIncrRefCounter(data); 92 93 if (data == NULL) { 94 // NOTE: Should we flag a warning message? 95 bucket->data = NULL; 96 } else { 97 bucket->data = psMemIncrRefCounter(data); 98 } 99 58 100 bucket->next = next; 59 101 … … 61 103 } 62 104 63 /****************************************************************************** 64 Destruct buckets 105 106 /****************************************************************************** 107 hashBucketFree(bucket, itemFree): This procedure deallocates the specified 108 hash bucket. If "itemFree" is NULL, then we simply free the data with the 109 standard psFree() function. If "itemFree" is not NULL, then it must be a 110 function pointer which takes the hash bucket as a parameter, and frees the 111 data in that hash bucket. 112 Inputs: 113 bucket: the hash bucket to be freed. 114 itemFree: a function pointer, possibly NULL. 115 Return: 116 NONE 65 117 *****************************************************************************/ 66 118 static void hashBucketFree(psHashBucket *bucket, // bucket to free … … 72 124 } 73 125 126 // A bucket is actually a linked list of buckets. We recursively step 127 // through that linked list, free each bucket. 74 128 if (bucket->next != NULL) 75 129 { … … 83 137 { 84 138 itemFree(bucket->data); 139 } else 140 { 141 psFree(bucket->data); 85 142 } 86 143 … … 88 145 } 89 146 90 /****************************************************************************** 91 Con/Destruct psHash tables 147 148 /****************************************************************************** 149 psHashAlloc(nbucket): this procedure creates a new hash table with the 150 specified number of buckets. 151 Inputs: 152 nbucket: initial number of buckets 153 Return: 154 The new hash table. 92 155 *****************************************************************************/ 93 156 psHash *psHashAlloc(int nbucket) // initial number of buckets 94 157 { 158 int i = 0; // loop index variable 159 // Create the new hash table. 95 160 psHash *table = psAlloc(sizeof(psHash)); 161 162 // Allocate memory for the buckets. 96 163 table->buckets = psAlloc(nbucket*sizeof(psHashBucket *)); 97 164 table->nbucket = nbucket; … … 99 166 psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); 100 167 101 for (int i = 0; i < nbucket; i++) 168 // Initialize all buckets to NULL. 169 for (i = 0; i < nbucket; i++) 102 170 { 103 171 table->buckets[i] = NULL; 104 172 } 105 173 174 // Return the new hash table. 106 175 return table; 107 176 } 108 177 109 /****************************************************************************** 178 179 180 /****************************************************************************** 181 psHashFree(table, itemFree): This procedure deallocates the specified hash 182 table. It loops through each bucket, and calls hashBucketFree() on that 183 bucket. 110 184 185 Inputs: 186 table: a hash table 187 itemFree: a function pointer, possibly NULL. 188 Return: 189 NONE 111 190 *****************************************************************************/ 112 191 void psHashFree(psHash *table, // hash table to be freed 113 192 void (*itemFree)(void *item)) // how to free hashed data; or NULL 114 193 { 194 psHashBucket *tmp = NULL; // Used to step through linked list. 195 psHashBucket *ptr = NULL; // Used to step through linked list. 196 int i = 0; // Loop index variable. 197 115 198 if (table == NULL) 116 199 { 117 200 return; 118 201 } 119 /* 120 * Release data interned on the list, and delete the buckets 121 */ 122 123 for (int i = 0; i < table->nbucket; i++) 124 { 202 203 // Loop through each bucket in the hash table. If that bucket is not 204 // NULL, then free the bucket via a function call to hashBucketFree(); 205 206 for (i = 0; i < table->nbucket; i++) 207 { 208 // A bucket is composed of a linked list of buckets. We use the 209 // "tmp" and "ptr" pointers to step through that list and free each 210 // non-NULL bucket. 211 125 212 if (table->buckets[i] != NULL) { 126 p sHashBucket *ptr = table->buckets[i];213 ptr = table->buckets[i]; 127 214 while (ptr != NULL) { 128 psHashBucket *tmp = ptr->next;215 tmp = ptr->next; 129 216 hashBucketFree(ptr, itemFree); 130 217 ptr = tmp; … … 133 220 } 134 221 222 // Free the bucket structure, then the hash table. 135 223 psFree(table->buckets); 136 224 psFree(table); … … 138 226 139 227 /****************************************************************************** 140 Here's the routine to do the work of insertion/retrieval/removal 228 doHashWork(table, key, data, remove, itemFree): This is an internal 229 procedure which does the bulk of the work in using the hash table. Depending 230 upon the input parameters, it will either insert a new key/data into the hash 231 table, retrieve the data for a specified key, or remove a key/data item. If 232 we try to insert a key that already exists in the hash table, then we call 233 the user-supplied function itemfree (or psFree if that is NULL), to free the 234 existing data/key item. 235 Inputs: 236 table: a hash table 237 key: the key to insert, retrieve, or remove. Must not be NULL. 238 data: the data to insert, if not NULL 239 remove: set to non-zero if the key/data should be removed from the table. 240 itemFree: function pointer 241 Return: 242 NONE 141 243 142 We need itemFree if the key is already in use and we're inserting 244 NOTE: consider removing this private function and simply putting the code 245 into the psHashInsert(), psHashLookup(), and psHashRemove(). Why? Because 246 there is little common code between those functions. 143 247 *****************************************************************************/ 144 248 static void *doHashWork(psHash *table, // table to insert in … … 149 253 void (*itemFree)(void *item)) // how to free hashed data 150 254 { 151 long int hash = 1; // This will contain edan integer value255 long int hash = 1; // This will contain an integer value 152 256 // "hashed" from the key. 153 psHashBucket *ptr = NULL; // Used to retrieve the requested hash 154 // bucket. 155 psHashBucket *optr = NULL; 156 char *tmpchar = NULL; 157 158 // NOTE: this is NOT a good hash function! See Knuth. 159 // 257 char *tmpchar = NULL; // Used in computing the hash function. 258 psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. 259 psHashBucket *optr = NULL; // "original pointer": used to step 260 // thru the linked list for a bucket. 261 262 // The following condition should never be true, since this is a private 263 // function, but I'm checking it anyway since future coders might change 264 // the way this procedure is called. 265 if ((table == NULL) || (key == NULL)) { 266 267 psAbort(__func__, "psHashRemove() called with NULL key or table."); 268 } 269 270 // NOTE: This is the originally supplied hash function. 160 271 // for (int i = 0, len = strlen(key); i < len; i++) { 161 272 // hash = (hash << 1) ^ key[i]; … … 172 283 // NOTE: This should not be necessary, but for now, I'm checking bounds 173 284 // anyway. 174 if ((hash < 0) || 175 (hash >= table->nbucket)) { 176 psAbort(__func__,"Internal hash function out of range (%d)", 177 hash); 178 } 179 285 if ((hash < 0) || (hash >= table->nbucket)) { 286 psAbort(__func__,"Internal hash function out of range (%d)", hash); 287 } 288 289 // ptr will have the correct hash bucket. 180 290 ptr = table->buckets[hash]; 181 291 182 // We 've foundthe correct hash bucket, now we need to know what to do.292 // We know the correct hash bucket, now we need to know what to do. 183 293 // If the data parameter is NULL, then, by definition, this is a retrieve 184 294 // or a remove operation on the hash table. 295 185 296 if (data == NULL) { 186 297 if (remove … … 191 302 optr = ptr; 192 303 while (ptr != NULL) { 304 // Dtermine if this entry holds the correct key. 193 305 if (strcmp(key, ptr->key) == 0) { 306 // The following lines of code are fairly standard ways 307 // of removing an item from a single-linked list. 308 194 309 void *data = ptr->data; 195 310 optr->next = ptr->next; 196 197 311 if (ptr == table->buckets[hash]) { 198 312 table->buckets[hash] = ptr->next; 199 313 } 200 314 201 // if (itemFree != NULL) {202 // printf("Calling itemFree()\n");203 // itemFree(psMemDecrRefCounter(ptr->data));204 // printf("Called itemFree()\n");205 // }206 207 315 psFree(ptr->key); 208 316 psFree(ptr); 209 317 210 return psMemDecrRefCounter(data); // return data 318 // By definition, the data associated with that key 319 // must be returned, not freed. 320 return psMemDecrRefCounter(data); 211 321 } 212 213 322 optr = ptr; 214 323 ptr = ptr->next; 215 324 } 325 return NULL; // not in hash 216 326 } 217 327 else { 328 // If we get here, then a retrieve operation is requested. So, 329 // we step trough the linked list at this bucket, and return the 330 // data once we find it, or return NULL if we don't. 218 331 while (ptr != NULL) { 219 if (strcmp(key, ptr->key) == 0) { // found it!332 if (strcmp(key, ptr->key) == 0) { 220 333 return ptr->data; 221 334 } 222 335 ptr = ptr->next; 223 336 } 337 return NULL; // not in hash 224 338 } 225 226 return NULL; // not in hash227 339 } else { 228 340 // We get here if this procedure was called with non-NULL data. … … 231 343 // the hash table and look for a duplicate entry for this key. 232 344 233 234 345 while (ptr != NULL) { 235 346 if (strcmp(key, ptr->key) == 0) { 236 347 // We have found this key in the hash table. 237 if (itemFree == NULL) {238 // The user has not supplied a routine, so we cannot239 // insert the data.240 return NULL;241 }242 348 243 349 psTrace("utils.hash.insert", 3, "Replacing data for %s\n", 244 350 key); 245 351 246 itemFree(psMemDecrRefCounter(ptr->data)); 352 // NOTE: I have changed this behavior from the originally 353 // supplied code. Formerly, if itemFree was NULL, then 354 // the new data was not inserted into the hash table. 355 356 if (itemFree == NULL) { 357 psFree(psMemDecrRefCounter(ptr->data)); 358 } else { 359 itemFree(psMemDecrRefCounter(ptr->data)); 360 } 361 247 362 ptr->data = psMemIncrRefCounter(data); 248 249 363 return data; 250 364 } 251 365 } 252 253 366 // We did not found key in the linked list for this bucket of the hash 254 367 // table. So, we insert this data at the head of that linked list. 368 255 369 table->buckets[hash] = hashBucketAlloc(key, 256 370 data, 257 371 table->buckets[hash]); 258 259 372 return data; 260 373 } … … 262 375 263 376 /****************************************************************************** 264 Insert a value into a hash table 377 psHashInsert(table, key, data, itemFree): this procedure, which is part of 378 the public API, inserts a new key/data pair into the hash table. 379 Inputs: 380 table: a hash table 381 key: the key to use 382 data: the data to insert. 383 itemFree: a function pointer 384 Return: 385 NONE 265 386 *****************************************************************************/ 266 387 void *psHashInsert(psHash *table, // table to insert in … … 269 390 void (*itemFree)(void *item)) // how to free hashed data; 270 391 { 271 void *tmp; 272 273 tmp = doHashWork(table, key, data, 0, itemFree); 274 return(tmp); 275 } 276 277 /****************************************************************************** 278 Lookup a value in a hash table 392 if (table == NULL) { 393 psAbort(__func__, "psHashInsert() called with NULL hash table."); 394 } 395 if (key == NULL) { 396 psAbort(__func__, "psHashInsert() called with NULL key."); 397 } 398 if (data == NULL) { 399 psAbort(__func__, "psHashLookup() called with NULL data."); 400 } 401 402 return doHashWork(table, key, data, 0, itemFree); 403 } 404 405 /****************************************************************************** 406 psHashLookup(table, key): this procedure, which is part of the public API, 407 looks up the specified key in the hash table and returns the data associated 408 with that key. 409 410 Inputs: 411 table: a hash table 412 key: the key to use 413 Return: 414 The data associated with that key. 279 415 *****************************************************************************/ 280 416 void *psHashLookup(psHash *table, // table to lookup key in 281 417 const char *key) // key to lookup 282 418 { 419 if (table == NULL) { 420 psAbort(__func__, "psHashLookup() called with NULL hash table."); 421 } 422 if (key == NULL) { 423 psAbort(__func__, "psHashLookup() called with NULL key."); 424 } 425 426 283 427 return doHashWork(table, key, NULL, 0, NULL); 284 428 } 285 429 286 430 /****************************************************************************** 287 Remove and return a value from a hash table 431 psHashRemove(table, key, itemFree): this procedure, which is part of the 432 public API, removes the specified key from the hash table. 433 Inputs: 434 table: a hash table 435 key: the key to remove 436 itemFree: a function pointer 437 Return: 438 The data that was associated with that key. 288 439 *****************************************************************************/ 289 440 void *psHashRemove(psHash *table, // table to lookup key in … … 291 442 void (*itemFree)(void *item)) // how to free hashed data; 292 443 { 444 if (table == NULL) { 445 psAbort(__func__, "psHashRemove() called with NULL hash table."); 446 } 447 if (key == NULL) { 448 psAbort(__func__, "psHashRemove() called with NULL key."); 449 } 450 293 451 return doHashWork(table, key, NULL, 1, itemFree); 294 452 }
Note:
See TracChangeset
for help on using the changeset viewer.
