< prev index next >

`rev 50962 : [mq]: 8207011`
 ``` `````` 266 print_key( b->_keyvals[j+j ]); 267 printf(" -> "); 268 print_value(b->_keyvals[j+j+1]); 269 printf("\n"); 270 } 271 } 272 } 273 274 //------------------------------Hashing Functions---------------------------- 275 // Convert string to hash key. This algorithm implements a universal hash 276 // function with the multipliers frozen (ok, so it's not universal). The 277 // multipliers (and allowable characters) are all odd, so the resultant sum 278 // is odd - guaranteed not divisible by any power of two, so the hash tables 279 // can be any power of two with good results. Also, I choose multipliers 280 // that have only 2 bits set (the low is always set to be odd) so 281 // multiplication requires only shifts and adds. Characters are required to 282 // be in the range 0-127 (I double & add 1 to force oddness). Keys are 283 // limited to MAXID characters in length. Experimental evidence on 150K of 284 // C text shows excellent spreading of values for any size hash table. 285 int hashstr(const void *t) { 286 register char c, k = 0; 287 register int sum = 0; 288 register const char *s = (const char *)t; 289 290 while (((c = s[k]) != '\0') && (k < MAXID-1)) { // Get characters till nul 291 c = (char) ((c << 1) + 1); // Characters are always odd! 292 sum += c + (c << shft[k++]); // Universal hash function 293 } 294 assert(k < (MAXID), "Exceeded maximum name length"); 295 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size 296 } 297 298 //------------------------------hashptr-------------------------------------- 299 // Slimey cheap hash function; no guaranteed performance. Better than the 300 // default for pointers, especially on MS-DOS machines. 301 int hashptr(const void *key) { 302 #ifdef __TURBOC__ 303 return (int)((intptr_t)key >> 16); 304 #else // __TURBOC__ 305 return (int)((intptr_t)key >> 2); 306 #endif 307 } 308 ``` ``` `````` 266 print_key( b->_keyvals[j+j ]); 267 printf(" -> "); 268 print_value(b->_keyvals[j+j+1]); 269 printf("\n"); 270 } 271 } 272 } 273 274 //------------------------------Hashing Functions---------------------------- 275 // Convert string to hash key. This algorithm implements a universal hash 276 // function with the multipliers frozen (ok, so it's not universal). The 277 // multipliers (and allowable characters) are all odd, so the resultant sum 278 // is odd - guaranteed not divisible by any power of two, so the hash tables 279 // can be any power of two with good results. Also, I choose multipliers 280 // that have only 2 bits set (the low is always set to be odd) so 281 // multiplication requires only shifts and adds. Characters are required to 282 // be in the range 0-127 (I double & add 1 to force oddness). Keys are 283 // limited to MAXID characters in length. Experimental evidence on 150K of 284 // C text shows excellent spreading of values for any size hash table. 285 int hashstr(const void *t) { 286 char c, k = 0; 287 int sum = 0; 288 const char *s = (const char *)t; 289 290 while (((c = s[k]) != '\0') && (k < MAXID-1)) { // Get characters till nul 291 c = (char) ((c << 1) + 1); // Characters are always odd! 292 sum += c + (c << shft[k++]); // Universal hash function 293 } 294 assert(k < (MAXID), "Exceeded maximum name length"); 295 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size 296 } 297 298 //------------------------------hashptr-------------------------------------- 299 // Slimey cheap hash function; no guaranteed performance. Better than the 300 // default for pointers, especially on MS-DOS machines. 301 int hashptr(const void *key) { 302 #ifdef __TURBOC__ 303 return (int)((intptr_t)key >> 16); 304 #else // __TURBOC__ 305 return (int)((intptr_t)key >> 2); 306 #endif 307 } 308 ```