direct-io.hg

changeset 11976:435e2275ea62

[IA64] linux/include/linux/hash.h.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
author awilliam@xenbuild.aw
date Sat Oct 14 16:42:15 2006 -0600 (2006-10-14)
parents c8fa605f131f
children 0c18c6009448
files xen/include/asm-ia64/linux/README.origin xen/include/asm-ia64/linux/hash.h
line diff
     1.1 --- a/xen/include/asm-ia64/linux/README.origin	Sat Oct 14 16:34:41 2006 -0600
     1.2 +++ b/xen/include/asm-ia64/linux/README.origin	Sat Oct 14 16:42:15 2006 -0600
     1.3 @@ -7,6 +7,7 @@
     1.4  bcd.h			-> linux/include/linux/bcd.h
     1.5  bitmap.h		-> linux/include/linux/bitmap.h
     1.6  bitops.h		-> linux/include/linux/bitops.h
     1.7 +hash.h			-> linux/include/linux/hash.h
     1.8  initrd.h		-> linux/include/linux/initrd.h
     1.9  jiffies.h		-> linux/include/linux/jiffies.h
    1.10  kmalloc_sizes.h		-> linux/include/linux/kmalloc_sizes.h
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/xen/include/asm-ia64/linux/hash.h	Sat Oct 14 16:42:15 2006 -0600
     2.3 @@ -0,0 +1,58 @@
     2.4 +#ifndef _LINUX_HASH_H
     2.5 +#define _LINUX_HASH_H
     2.6 +/* Fast hashing routine for a long.
     2.7 +   (C) 2002 William Lee Irwin III, IBM */
     2.8 +
     2.9 +/*
    2.10 + * Knuth recommends primes in approximately golden ratio to the maximum
    2.11 + * integer representable by a machine word for multiplicative hashing.
    2.12 + * Chuck Lever verified the effectiveness of this technique:
    2.13 + * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
    2.14 + *
    2.15 + * These primes are chosen to be bit-sparse, that is operations on
    2.16 + * them can use shifts and additions instead of multiplications for
    2.17 + * machines where multiplications are slow.
    2.18 + */
    2.19 +#if BITS_PER_LONG == 32
    2.20 +/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
    2.21 +#define GOLDEN_RATIO_PRIME 0x9e370001UL
    2.22 +#elif BITS_PER_LONG == 64
    2.23 +/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
    2.24 +#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
    2.25 +#else
    2.26 +#error Define GOLDEN_RATIO_PRIME for your wordsize.
    2.27 +#endif
    2.28 +
    2.29 +static inline unsigned long hash_long(unsigned long val, unsigned int bits)
    2.30 +{
    2.31 +	unsigned long hash = val;
    2.32 +
    2.33 +#if BITS_PER_LONG == 64
    2.34 +	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
    2.35 +	unsigned long n = hash;
    2.36 +	n <<= 18;
    2.37 +	hash -= n;
    2.38 +	n <<= 33;
    2.39 +	hash -= n;
    2.40 +	n <<= 3;
    2.41 +	hash += n;
    2.42 +	n <<= 3;
    2.43 +	hash -= n;
    2.44 +	n <<= 4;
    2.45 +	hash += n;
    2.46 +	n <<= 2;
    2.47 +	hash += n;
    2.48 +#else
    2.49 +	/* On some cpus multiply is faster, on others gcc will do shifts */
    2.50 +	hash *= GOLDEN_RATIO_PRIME;
    2.51 +#endif
    2.52 +
    2.53 +	/* High bits are more random, so use them. */
    2.54 +	return hash >> (BITS_PER_LONG - bits);
    2.55 +}
    2.56 +	
    2.57 +static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
    2.58 +{
    2.59 +	return hash_long((unsigned long)ptr, bits);
    2.60 +}
    2.61 +#endif /* _LINUX_HASH_H */