From b5fd066153c40a70a29caa1ea7987723ab687763 Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Tue, 16 Jan 2024 17:00:02 -0500 Subject: Move c_src dirs back to toplevel We just wanted c sourcefiles out of the top level, not c source directories. Signed-off-by: Kent Overstreet --- c_src/include/linux/hash.h | 104 --------------------------------------------- 1 file changed, 104 deletions(-) delete mode 100644 c_src/include/linux/hash.h (limited to 'c_src/include/linux/hash.h') diff --git a/c_src/include/linux/hash.h b/c_src/include/linux/hash.h deleted file mode 100644 index ad6fa21d..00000000 --- a/c_src/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 -#include - -/* - * 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 -#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 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 */ -- cgit v1.2.3