# HG changeset patch # User yamahata@xxxxxxxxxxxxx # Node ID 07d24fb809cfd78569af89cff0882127dca08feb # Parent 0ff3964bde81f7acd09522817d11ee018f89f8c9 import linux/include/linux/hash.h. PATCHNAME: import_linux_hash.h Signed-off-by: Isaku Yamahata diff -r 0ff3964bde81 -r 07d24fb809cf xen/include/asm-ia64/linux/README.origin --- a/xen/include/asm-ia64/linux/README.origin Fri Jul 14 15:21:05 2006 +0900 +++ b/xen/include/asm-ia64/linux/README.origin Fri Jul 14 15:21:08 2006 +0900 @@ -8,6 +8,7 @@ bitmap.h -> linux/include/linux/bitmap. bitmap.h -> linux/include/linux/bitmap.h bitops.h -> linux/include/linux/bitops.h initrd.h -> linux/include/linux/initrd.h +hash.h -> linux/include/linux/hash.h jiffies.h -> linux/include/linux/jiffies.h kmalloc_sizes.h -> linux/include/linux/kmalloc_sizes.h linkage.h -> linux/include/linux/linkage.h diff -r 0ff3964bde81 -r 07d24fb809cf xen/include/asm-ia64/linux/hash.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/xen/include/asm-ia64/linux/hash.h Fri Jul 14 15:21:08 2006 +0900 @@ -0,0 +1,58 @@ +#ifndef _LINUX_HASH_H +#define _LINUX_HASH_H +/* Fast hashing routine for a long. + (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. + */ +#if BITS_PER_LONG == 32 +/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ +#define GOLDEN_RATIO_PRIME 0x9e370001UL +#elif BITS_PER_LONG == 64 +/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ +#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL +#else +#error Define GOLDEN_RATIO_PRIME for your wordsize. +#endif + +static inline unsigned long hash_long(unsigned long val, unsigned int bits) +{ + unsigned long hash = val; + +#if BITS_PER_LONG == 64 + /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ + unsigned long n = hash; + n <<= 18; + hash -= n; + n <<= 33; + hash -= n; + n <<= 3; + hash += n; + n <<= 3; + hash -= n; + n <<= 4; + hash += n; + n <<= 2; + hash += n; +#else + /* On some cpus multiply is faster, on others gcc will do shifts */ + hash *= GOLDEN_RATIO_PRIME; +#endif + + /* High bits are more random, so use them. */ + return hash >> (BITS_PER_LONG - bits); +} + +static inline unsigned long hash_ptr(void *ptr, unsigned int bits) +{ + return hash_long((unsigned long)ptr, bits); +} +#endif /* _LINUX_HASH_H */