Commit | Line | Data |
---|---|---|

bdc7211e JA |
1 | #ifndef _LINUX_HASH_H |

2 | #define _LINUX_HASH_H | |

daaa166f JA |
3 | |

4 | #include "arch/arch.h" | |

5 | ||

bdc7211e JA |
6 | /* Fast hashing routine for a long. |

7 | (C) 2002 William Lee Irwin III, IBM */ | |

8 | ||

9 | /* | |

10 | * Knuth recommends primes in approximately golden ratio to the maximum | |

11 | * integer representable by a machine word for multiplicative hashing. | |

12 | * Chuck Lever verified the effectiveness of this technique: | |

13 | * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf | |

14 | * | |

15 | * These primes are chosen to be bit-sparse, that is operations on | |

16 | * them can use shifts and additions instead of multiplications for | |

17 | * machines where multiplications are slow. | |

18 | */ | |

5921e80c | 19 | |

bdc7211e JA |
20 | #if BITS_PER_LONG == 32 |

21 | /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ | |

22 | #define GOLDEN_RATIO_PRIME 0x9e370001UL | |

23 | #elif BITS_PER_LONG == 64 | |

24 | /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ | |

25 | #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL | |

26 | #else | |

27 | #error Define GOLDEN_RATIO_PRIME for your wordsize. | |

28 | #endif | |

29 | ||

30 | static inline unsigned long hash_long(unsigned long val, unsigned int bits) | |

31 | { | |

32 | unsigned long hash = val; | |

33 | ||

34 | #if BITS_PER_LONG == 64 | |

35 | /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ | |

36 | unsigned long n = hash; | |

37 | n <<= 18; | |

38 | hash -= n; | |

39 | n <<= 33; | |

40 | hash -= n; | |

41 | n <<= 3; | |

42 | hash += n; | |

43 | n <<= 3; | |

44 | hash -= n; | |

45 | n <<= 4; | |

46 | hash += n; | |

47 | n <<= 2; | |

48 | hash += n; | |

49 | #else | |

50 | /* On some cpus multiply is faster, on others gcc will do shifts */ | |

51 | hash *= GOLDEN_RATIO_PRIME; | |

52 | #endif | |

53 | ||

54 | /* High bits are more random, so use them. */ | |

55 | return hash >> (BITS_PER_LONG - bits); | |

56 | } | |

57 | ||

58 | static inline unsigned long hash_ptr(void *ptr, unsigned int bits) | |

59 | { | |

60 | return hash_long((unsigned long)ptr, bits); | |

61 | } | |

62 | #endif /* _LINUX_HASH_H */ |