hash.h

   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 <stdint.h>
  18
  19 static inline uint64_t hash_64(const uint64_t val, const unsigned int bits)
  20 {
  21         return (val * 11400714819323198485LLU) >> (64 - bits);
  22 }
  23
  24 #endif /* _LINUX_HASH_H */