/root/src/xen/xen/include/xen/hash.h
Line | Count | Source (jump to first uncovered line) |
1 | | #ifndef _XEN_HASH_H |
2 | | #define _XEN_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 | | */ |
16 | | #if BITS_PER_LONG == 32 |
17 | | /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ |
18 | | #define GOLDEN_RATIO_PRIME 0x9e370001UL |
19 | | #elif BITS_PER_LONG == 64 |
20 | | /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ |
21 | | #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL |
22 | | #else |
23 | | #error Define GOLDEN_RATIO_PRIME for your wordsize. |
24 | | #endif |
25 | | |
26 | | static inline unsigned long hash_long(unsigned long val, unsigned int bits) |
27 | 0 | { |
28 | 0 | unsigned long hash = val; |
29 | 0 |
|
30 | 0 | #if BITS_PER_LONG == 64 |
31 | 0 | /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ |
32 | 0 | unsigned long n = hash; |
33 | 0 | n <<= 18; |
34 | 0 | hash -= n; |
35 | 0 | n <<= 33; |
36 | 0 | hash -= n; |
37 | 0 | n <<= 3; |
38 | 0 | hash += n; |
39 | 0 | n <<= 3; |
40 | 0 | hash -= n; |
41 | 0 | n <<= 4; |
42 | 0 | hash += n; |
43 | 0 | n <<= 2; |
44 | 0 | hash += n; |
45 | 0 | #else |
46 | | /* On some cpus multiply is faster, on others gcc will do shifts */ |
47 | | hash *= GOLDEN_RATIO_PRIME; |
48 | | #endif |
49 | 0 |
|
50 | 0 | /* High bits are more random, so use them. */ |
51 | 0 | return hash >> (BITS_PER_LONG - bits); |
52 | 0 | } Unexecuted instantiation: memory.c:hash_long Unexecuted instantiation: page_alloc.c:hash_long Unexecuted instantiation: tmem.c:hash_long Unexecuted instantiation: tmem_xen.c:hash_long Unexecuted instantiation: tmem_control.c:hash_long Unexecuted instantiation: setup.c:hash_long |
53 | | |
54 | | static inline unsigned long hash_ptr(void *ptr, unsigned int bits) |
55 | 0 | { |
56 | 0 | return hash_long((unsigned long)ptr, bits); |
57 | 0 | } Unexecuted instantiation: memory.c:hash_ptr Unexecuted instantiation: page_alloc.c:hash_ptr Unexecuted instantiation: tmem.c:hash_ptr Unexecuted instantiation: tmem_xen.c:hash_ptr Unexecuted instantiation: tmem_control.c:hash_ptr Unexecuted instantiation: setup.c:hash_ptr |
58 | | #endif /* _XEN_HASH_H */ |