< prev index next >

`rev 50962 : [mq]: 8207011`
 ``` `````` 288 DictI i(this); // Moved definition in iterator here because of g++. 289 tty->print("Dict@" INTPTR_FORMAT "[%d] = {", p2i(this), _cnt); 290 for( ; i.test(); ++i ) { 291 tty->print("(" INTPTR_FORMAT "," INTPTR_FORMAT "),", p2i(i._key), p2i(i._value)); 292 } 293 tty->print_cr("}"); 294 } 295 296 //------------------------------Hashing Functions---------------------------- 297 // Convert string to hash key. This algorithm implements a universal hash 298 // function with the multipliers frozen (ok, so it's not universal). The 299 // multipliers (and allowable characters) are all odd, so the resultant sum 300 // is odd - guaranteed not divisible by any power of two, so the hash tables 301 // can be any power of two with good results. Also, I choose multipliers 302 // that have only 2 bits set (the low is always set to be odd) so 303 // multiplication requires only shifts and adds. Characters are required to 304 // be in the range 0-127 (I double & add 1 to force oddness). Keys are 305 // limited to MAXID characters in length. Experimental evidence on 150K of 306 // C text shows excellent spreading of values for any size hash table. 307 int hashstr(const void *t) { 308 register char c, k = 0; 309 register int32_t sum = 0; 310 register const char *s = (const char *)t; 311 312 while( ((c = *s++) != '\0') && (k < MAXID-1) ) { // Get characters till null or MAXID-1 313 c = (c<<1)+1; // Characters are always odd! 314 sum += c + (c<> 1); // Hash key, un-modulo'd table size 317 } 318 319 //------------------------------hashptr-------------------------------------- 320 // Slimey cheap hash function; no guaranteed performance. Better than the 321 // default for pointers, especially on MS-DOS machines. 322 int hashptr(const void *key) { 323 return ((intptr_t)key >> 2); 324 } 325 326 // Slimey cheap hash function; no guaranteed performance. 327 int hashkey(const void *key) { 328 return (intptr_t)key; 329 } 330 ``` ``` `````` 288 DictI i(this); // Moved definition in iterator here because of g++. 289 tty->print("Dict@" INTPTR_FORMAT "[%d] = {", p2i(this), _cnt); 290 for( ; i.test(); ++i ) { 291 tty->print("(" INTPTR_FORMAT "," INTPTR_FORMAT "),", p2i(i._key), p2i(i._value)); 292 } 293 tty->print_cr("}"); 294 } 295 296 //------------------------------Hashing Functions---------------------------- 297 // Convert string to hash key. This algorithm implements a universal hash 298 // function with the multipliers frozen (ok, so it's not universal). The 299 // multipliers (and allowable characters) are all odd, so the resultant sum 300 // is odd - guaranteed not divisible by any power of two, so the hash tables 301 // can be any power of two with good results. Also, I choose multipliers 302 // that have only 2 bits set (the low is always set to be odd) so 303 // multiplication requires only shifts and adds. Characters are required to 304 // be in the range 0-127 (I double & add 1 to force oddness). Keys are 305 // limited to MAXID characters in length. Experimental evidence on 150K of 306 // C text shows excellent spreading of values for any size hash table. 307 int hashstr(const void *t) { 308 char c, k = 0; 309 int32_t sum = 0; 310 const char *s = (const char *)t; 311 312 while( ((c = *s++) != '\0') && (k < MAXID-1) ) { // Get characters till null or MAXID-1 313 c = (c<<1)+1; // Characters are always odd! 314 sum += c + (c<> 1); // Hash key, un-modulo'd table size 317 } 318 319 //------------------------------hashptr-------------------------------------- 320 // Slimey cheap hash function; no guaranteed performance. Better than the 321 // default for pointers, especially on MS-DOS machines. 322 int hashptr(const void *key) { 323 return ((intptr_t)key >> 2); 324 } 325 326 // Slimey cheap hash function; no guaranteed performance. 327 int hashkey(const void *key) { 328 return (intptr_t)key; 329 } 330 ```