diff options
Diffstat (limited to 'include/linux/hash.h')
-rw-r--r-- | include/linux/hash.h | 104 |
1 files changed, 0 insertions, 104 deletions
diff --git a/include/linux/hash.h b/include/linux/hash.h deleted file mode 100644 index ad6fa21d..00000000 --- a/include/linux/hash.h +++ /dev/null @@ -1,104 +0,0 @@ -#ifndef _LINUX_HASH_H -#define _LINUX_HASH_H -/* Fast hashing routine for ints, longs and pointers. - (C) 2002 Nadia Yvette Chambers, IBM */ - -#include <asm/types.h> -#include <linux/compiler.h> - -/* - * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and - * fs/inode.c. It's not actually prime any more (the previous primes - * were actively bad for hashing), but the name remains. - */ -#if BITS_PER_LONG == 32 -#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32 -#define hash_long(val, bits) hash_32(val, bits) -#elif BITS_PER_LONG == 64 -#define hash_long(val, bits) hash_64(val, bits) -#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64 -#else -#error Wordsize not 32 or 64 -#endif - -/* - * This hash multiplies the input by a large odd number and takes the - * high bits. Since multiplication propagates changes to the most - * significant end only, it is essential that the high bits of the - * product be used for the hash value. - * - * Chuck Lever verified the effectiveness of this technique: - * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf - * - * Although a random odd number will do, it turns out that the golden - * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice - * properties. (See Knuth vol 3, section 6.4, exercise 9.) - * - * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2, - * which is very slightly easier to multiply by and makes no - * difference to the hash distribution. - */ -#define GOLDEN_RATIO_32 0x61C88647 -#define GOLDEN_RATIO_64 0x61C8864680B583EBull - -#ifdef CONFIG_HAVE_ARCH_HASH -/* This header may use the GOLDEN_RATIO_xx constants */ -#include <asm/hash.h> -#endif - -/* - * The _generic versions exist only so lib/test_hash.c can compare - * the arch-optimized versions with the generic. - * - * Note that if you change these, any <asm/hash.h> that aren't updated - * to match need to have their HAVE_ARCH_* define values updated so the - * self-test will not false-positive. - */ -#ifndef HAVE_ARCH__HASH_32 -#define __hash_32 __hash_32_generic -#endif -static inline u32 __hash_32_generic(u32 val) -{ - return val * GOLDEN_RATIO_32; -} - -#ifndef HAVE_ARCH_HASH_32 -#define hash_32 hash_32_generic -#endif -static inline u32 hash_32_generic(u32 val, unsigned int bits) -{ - /* High bits are more random, so use them. */ - return __hash_32(val) >> (32 - bits); -} - -#ifndef HAVE_ARCH_HASH_64 -#define hash_64 hash_64_generic -#endif -static __always_inline u32 hash_64_generic(u64 val, unsigned int bits) -{ -#if BITS_PER_LONG == 64 - /* 64x64-bit multiply is efficient on all 64-bit processors */ - return val * GOLDEN_RATIO_64 >> (64 - bits); -#else - /* Hash 64 bits using only 32x32-bit multiply. */ - return hash_32((u32)val ^ __hash_32(val >> 32), bits); -#endif -} - -static inline u32 hash_ptr(const void *ptr, unsigned int bits) -{ - return hash_long((unsigned long)ptr, bits); -} - -/* This really should be called fold32_ptr; it does no hashing to speak of. */ -static inline u32 hash32_ptr(const void *ptr) -{ - unsigned long val = (unsigned long)ptr; - -#if BITS_PER_LONG == 64 - val ^= (val >> 32); -#endif - return (u32)val; -} - -#endif /* _LINUX_HASH_H */ |