| #ifndef _LINUX_HASH_H |
| #define _LINUX_HASH_H |
| /* Fast hashing routine for ints, longs and pointers. |
| (C) 2002 William Lee Irwin III, IBM */ |
| |
| /* |
| * Knuth recommends primes in approximately golden ratio to the maximum |
| * integer representable by a machine word for multiplicative hashing. |
| * Chuck Lever verified the effectiveness of this technique: |
| * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf |
| * |
| * These primes are chosen to be bit-sparse, that is operations on |
| * them can use shifts and additions instead of multiplications for |
| * machines where multiplications are slow. |
| */ |
| |
| #include <stdint.h> |
| |
| static inline uint64_t hash_64(const uint64_t val, const unsigned int bits) |
| { |
| return (val * 11400714819323198485LLU) >> (64 - bits); |
| } |
| |
| #endif /* _LINUX_HASH_H */ |