104 lines · 3.0 KB · C
RawDownload
#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#endifstatic inline u32 __hash_32_generic(u32 val){	return val * GOLDEN_RATIO_32;} #ifndef HAVE_ARCH_HASH_32#define hash_32 hash_32_generic#endifstatic 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#endifstatic __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 */

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t