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--------------------- |