~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/hash.h

Version: ~ [ linux-5.9-rc5 ] ~ [ linux-5.8.10 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.66 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.146 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.198 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.236 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.236 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 #ifndef _LINUX_HASH_H
  2 #define _LINUX_HASH_H
  3 /* Fast hashing routine for ints,  longs and pointers.
  4    (C) 2002 Nadia Yvette Chambers, 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 <asm/types.h>
 18 #include <linux/compiler.h>
 19 
 20 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
 21 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
 22 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
 23 #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
 24 
 25 #if BITS_PER_LONG == 32
 26 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32
 27 #define hash_long(val, bits) hash_32(val, bits)
 28 #elif BITS_PER_LONG == 64
 29 #define hash_long(val, bits) hash_64(val, bits)
 30 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64
 31 #else
 32 #error Wordsize not 32 or 64
 33 #endif
 34 
 35 static __always_inline u64 hash_64(u64 val, unsigned int bits)
 36 {
 37         u64 hash = val;
 38 
 39         /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 40         u64 n = hash;
 41         n <<= 18;
 42         hash -= n;
 43         n <<= 33;
 44         hash -= n;
 45         n <<= 3;
 46         hash += n;
 47         n <<= 3;
 48         hash -= n;
 49         n <<= 4;
 50         hash += n;
 51         n <<= 2;
 52         hash += n;
 53 
 54         /* High bits are more random, so use them. */
 55         return hash >> (64 - bits);
 56 }
 57 
 58 static inline u32 hash_32(u32 val, unsigned int bits)
 59 {
 60         /* On some cpus multiply is faster, on others gcc will do shifts */
 61         u32 hash = val * GOLDEN_RATIO_PRIME_32;
 62 
 63         /* High bits are more random, so use them. */
 64         return hash >> (32 - bits);
 65 }
 66 
 67 static inline unsigned long hash_ptr(const void *ptr, unsigned int bits)
 68 {
 69         return hash_long((unsigned long)ptr, bits);
 70 }
 71 
 72 static inline u32 hash32_ptr(const void *ptr)
 73 {
 74         unsigned long val = (unsigned long)ptr;
 75 
 76 #if BITS_PER_LONG == 64
 77         val ^= (val >> 32);
 78 #endif
 79         return (u32)val;
 80 }
 81 #endif /* _LINUX_HASH_H */
 82 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp