Mercurial > hg > truffle
comparison src/share/vm/libadt/dict.cpp @ 628:7bb995fbd3c0
Merge
author | trims |
---|---|
date | Thu, 12 Mar 2009 18:16:36 -0700 |
parents | 0fbdb4381b99 98cb887364d3 |
children | c18cbe5936b8 |
comparison
equal
deleted
inserted
replaced
580:ce2272390558 | 628:7bb995fbd3c0 |
---|---|
304 | 304 |
305 //------------------------------Hashing Functions---------------------------- | 305 //------------------------------Hashing Functions---------------------------- |
306 // Convert string to hash key. This algorithm implements a universal hash | 306 // Convert string to hash key. This algorithm implements a universal hash |
307 // function with the multipliers frozen (ok, so it's not universal). The | 307 // function with the multipliers frozen (ok, so it's not universal). The |
308 // multipliers (and allowable characters) are all odd, so the resultant sum | 308 // multipliers (and allowable characters) are all odd, so the resultant sum |
309 // is odd - guarenteed not divisible by any power of two, so the hash tables | 309 // is odd - guaranteed not divisible by any power of two, so the hash tables |
310 // can be any power of two with good results. Also, I choose multipliers | 310 // can be any power of two with good results. Also, I choose multipliers |
311 // that have only 2 bits set (the low is always set to be odd) so | 311 // that have only 2 bits set (the low is always set to be odd) so |
312 // multiplication requires only shifts and adds. Characters are required to | 312 // multiplication requires only shifts and adds. Characters are required to |
313 // be in the range 0-127 (I double & add 1 to force oddness). Keys are | 313 // be in the range 0-127 (I double & add 1 to force oddness). Keys are |
314 // limited to MAXID characters in length. Experimental evidence on 150K of | 314 // limited to MAXID characters in length. Experimental evidence on 150K of |
324 } | 324 } |
325 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size | 325 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size |
326 } | 326 } |
327 | 327 |
328 //------------------------------hashptr-------------------------------------- | 328 //------------------------------hashptr-------------------------------------- |
329 // Slimey cheap hash function; no guarenteed performance. Better than the | 329 // Slimey cheap hash function; no guaranteed performance. Better than the |
330 // default for pointers, especially on MS-DOS machines. | 330 // default for pointers, especially on MS-DOS machines. |
331 int hashptr(const void *key) { | 331 int hashptr(const void *key) { |
332 #ifdef __TURBOC__ | 332 #ifdef __TURBOC__ |
333 return ((intptr_t)key >> 16); | 333 return ((intptr_t)key >> 16); |
334 #else // __TURBOC__ | 334 #else // __TURBOC__ |
335 return ((intptr_t)key >> 2); | 335 return ((intptr_t)key >> 2); |
336 #endif | 336 #endif |
337 } | 337 } |
338 | 338 |
339 // Slimey cheap hash function; no guarenteed performance. | 339 // Slimey cheap hash function; no guaranteed performance. |
340 int hashkey(const void *key) { | 340 int hashkey(const void *key) { |
341 return (intptr_t)key; | 341 return (intptr_t)key; |
342 } | 342 } |
343 | 343 |
344 //------------------------------Key Comparator Functions--------------------- | 344 //------------------------------Key Comparator Functions--------------------- |