Root/
1 | #ifndef _LINUX_HASH_H |
2 | #define _LINUX_HASH_H |
3 | /* Fast hashing routine for ints, longs and pointers. |
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 | */ |
16 | |
17 | #include <asm/types.h> |
18 | |
19 | /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ |
20 | #define GOLDEN_RATIO_PRIME_32 0x9e370001UL |
21 | /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ |
22 | #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL |
23 | |
24 | #if BITS_PER_LONG == 32 |
25 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32 |
26 | #define hash_long(val, bits) hash_32(val, bits) |
27 | #elif BITS_PER_LONG == 64 |
28 | #define hash_long(val, bits) hash_64(val, bits) |
29 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 |
30 | #else |
31 | #error Wordsize not 32 or 64 |
32 | #endif |
33 | |
34 | static inline u64 hash_64(u64 val, unsigned int bits) |
35 | { |
36 | u64 hash = val; |
37 | |
38 | /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ |
39 | u64 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 | |
53 | /* High bits are more random, so use them. */ |
54 | return hash >> (64 - bits); |
55 | } |
56 | |
57 | static inline u32 hash_32(u32 val, unsigned int bits) |
58 | { |
59 | /* On some cpus multiply is faster, on others gcc will do shifts */ |
60 | u32 hash = val * GOLDEN_RATIO_PRIME_32; |
61 | |
62 | /* High bits are more random, so use them. */ |
63 | return hash >> (32 - bits); |
64 | } |
65 | |
66 | static inline unsigned long hash_ptr(void *ptr, unsigned int bits) |
67 | { |
68 | return hash_long((unsigned long)ptr, bits); |
69 | } |
70 | #endif /* _LINUX_HASH_H */ |
71 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9