hash.h 1.6 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
  1. #ifndef _LINUX_HASH_H
  2. #define _LINUX_HASH_H
  3. /* Fast hashing routine for a long.
  4. (C) 2002 William Lee Irwin III, IBM */
  5. /*
  6. * Knuth recommends primes in approximately golden ratio to the maximum
  7. * integer representable by a machine word for multiplicative hashing.
  8. * Chuck Lever verified the effectiveness of this technique:
  9. * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
  10. *
  11. * These primes are chosen to be bit-sparse, that is operations on
  12. * them can use shifts and additions instead of multiplications for
  13. * machines where multiplications are slow.
  14. */
  15. #if BITS_PER_LONG == 32
  16. /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  17. #define GOLDEN_RATIO_PRIME 0x9e370001UL
  18. #elif BITS_PER_LONG == 64
  19. /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  20. #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  21. #else
  22. #error Define GOLDEN_RATIO_PRIME for your wordsize.
  23. #endif
  24. static inline unsigned long hash_long(unsigned long val, unsigned int bits)
  25. {
  26. unsigned long hash = val;
  27. #if BITS_PER_LONG == 64
  28. /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
  29. unsigned long n = hash;
  30. n <<= 18;
  31. hash -= n;
  32. n <<= 33;
  33. hash -= n;
  34. n <<= 3;
  35. hash += n;
  36. n <<= 3;
  37. hash -= n;
  38. n <<= 4;
  39. hash += n;
  40. n <<= 2;
  41. hash += n;
  42. #else
  43. /* On some cpus multiply is faster, on others gcc will do shifts */
  44. hash *= GOLDEN_RATIO_PRIME;
  45. #endif
  46. /* High bits are more random, so use them. */
  47. return hash >> (BITS_PER_LONG - bits);
  48. }
  49. static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
  50. {
  51. return hash_long((unsigned long)ptr, bits);
  52. }
  53. #endif /* _LINUX_HASH_H */