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