Blame view
include/linux/hash.h
1.83 KB
1da177e4c
|
1 2 |
#ifndef _LINUX_HASH_H #define _LINUX_HASH_H |
4e701482d
|
3 |
/* Fast hashing routine for ints, longs and pointers. |
1da177e4c
|
4 5 6 7 8 9 10 11 12 13 14 15 |
(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. */ |
4e701482d
|
16 17 |
#include <asm/types.h> |
1da177e4c
|
18 |
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ |
4e701482d
|
19 |
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL |
1da177e4c
|
20 |
/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ |
4e701482d
|
21 22 23 24 25 26 27 28 |
#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL #if BITS_PER_LONG == 32 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32 #define hash_long(val, bits) hash_32(val, bits) #elif BITS_PER_LONG == 64 #define hash_long(val, bits) hash_64(val, bits) #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 |
1da177e4c
|
29 |
#else |
4e701482d
|
30 |
#error Wordsize not 32 or 64 |
1da177e4c
|
31 |
#endif |
4e701482d
|
32 |
static inline u64 hash_64(u64 val, unsigned int bits) |
1da177e4c
|
33 |
{ |
4e701482d
|
34 |
u64 hash = val; |
1da177e4c
|
35 |
|
1da177e4c
|
36 |
/* Sigh, gcc can't optimise this alone like it does for 32 bits. */ |
4e701482d
|
37 |
u64 n = hash; |
1da177e4c
|
38 39 40 41 42 43 44 45 46 47 48 49 |
n <<= 18; hash -= n; n <<= 33; hash -= n; n <<= 3; hash += n; n <<= 3; hash -= n; n <<= 4; hash += n; n <<= 2; hash += n; |
4e701482d
|
50 51 52 53 54 55 56 |
/* High bits are more random, so use them. */ return hash >> (64 - bits); } static inline u32 hash_32(u32 val, unsigned int bits) { |
1da177e4c
|
57 |
/* On some cpus multiply is faster, on others gcc will do shifts */ |
4e701482d
|
58 |
u32 hash = val * GOLDEN_RATIO_PRIME_32; |
1da177e4c
|
59 60 |
/* High bits are more random, so use them. */ |
4e701482d
|
61 |
return hash >> (32 - bits); |
1da177e4c
|
62 |
} |
4e701482d
|
63 |
|
1da177e4c
|
64 65 66 67 68 |
static inline unsigned long hash_ptr(void *ptr, unsigned int bits) { return hash_long((unsigned long)ptr, bits); } #endif /* _LINUX_HASH_H */ |