273 |
273 |
274 //------------------------------Hashing Functions---------------------------- |
274 //------------------------------Hashing Functions---------------------------- |
275 // Convert string to hash key. This algorithm implements a universal hash |
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 |
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 |
277 // multipliers (and allowable characters) are all odd, so the resultant sum |
278 // is odd - guarenteed not divisible by any power of two, so the hash tables |
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 |
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 |
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 |
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 |
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 |
283 // limited to MAXID characters in length. Experimental evidence on 150K of |
294 assert( k < (MAXID + 1), "Exceeded maximum name length"); |
294 assert( k < (MAXID + 1), "Exceeded maximum name length"); |
295 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size |
295 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size |
296 } |
296 } |
297 |
297 |
298 //------------------------------hashptr-------------------------------------- |
298 //------------------------------hashptr-------------------------------------- |
299 // Slimey cheap hash function; no guarenteed performance. Better than the |
299 // Slimey cheap hash function; no guaranteed performance. Better than the |
300 // default for pointers, especially on MS-DOS machines. |
300 // default for pointers, especially on MS-DOS machines. |
301 int hashptr(const void *key) { |
301 int hashptr(const void *key) { |
302 #ifdef __TURBOC__ |
302 #ifdef __TURBOC__ |
303 return (int)((intptr_t)key >> 16); |
303 return (int)((intptr_t)key >> 16); |
304 #else // __TURBOC__ |
304 #else // __TURBOC__ |
305 return (int)((intptr_t)key >> 2); |
305 return (int)((intptr_t)key >> 2); |
306 #endif |
306 #endif |
307 } |
307 } |
308 |
308 |
309 // Slimey cheap hash function; no guarenteed performance. |
309 // Slimey cheap hash function; no guaranteed performance. |
310 int hashkey(const void *key) { |
310 int hashkey(const void *key) { |
311 return (int)((intptr_t)key); |
311 return (int)((intptr_t)key); |
312 } |
312 } |
313 |
313 |
314 //------------------------------Key Comparator Functions--------------------- |
314 //------------------------------Key Comparator Functions--------------------- |