summary | shortlog | log | commit | commitdiff | tree

blob | blame (non-incremental) | history | HEAD

blob | blame (non-incremental) | history | HEAD

... / ...

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

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 | */ | |

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 | { | |

28 | unsigned long hash = val; | |

29 | ||

30 | #if BITS_PER_LONG == 64 | |

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

32 | unsigned long n = hash; | |

33 | n <<= 18; | |

34 | hash -= n; | |

35 | n <<= 33; | |

36 | hash -= n; | |

37 | n <<= 3; | |

38 | hash += n; | |

39 | n <<= 3; | |

40 | hash -= n; | |

41 | n <<= 4; | |

42 | hash += n; | |

43 | n <<= 2; | |

44 | hash += n; | |

45 | #else | |

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

47 | hash *= GOLDEN_RATIO_PRIME; | |

48 | #endif | |

49 | ||

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

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

52 | } | |

53 | ||

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

55 | { | |

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

57 | } | |

58 | #endif /* _LINUX_HASH_H */ |