LXR linux/tools/include/linux/hash.h

   1#ifndef _LINUX_HASH_H
   2#define _LINUX_HASH_H
   3/* Fast hashing routine for ints,  longs and pointers.
   4   (C) 2002 Nadia Yvette Chambers, IBM */
   5
   6#include <asm/types.h>
   7#include <linux/compiler.h>
   8
   9/*
  10 * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
  11 * fs/inode.c.  It's not actually prime any more (the previous primes
  12 * were actively bad for hashing), but the name remains.
  13 */
  14#if BITS_PER_LONG == 32
  15#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
  16#define hash_long(val, bits) hash_32(val, bits)
  17#elif BITS_PER_LONG == 64
  18#define hash_long(val, bits) hash_64(val, bits)
  19#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
  20#else
  21#error Wordsize not 32 or 64
  22#endif
  23
  24/*
  25 * This hash multiplies the input by a large odd number and takes the
  26 * high bits.  Since multiplication propagates changes to the most
  27 * significant end only, it is essential that the high bits of the
  28 * product be used for the hash value.
  29 *
  30 * Chuck Lever verified the effectiveness of this technique:
  31 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
  32 *
  33 * Although a random odd number will do, it turns out that the golden
  34 * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
  35 * properties.  (See Knuth vol 3, section 6.4, exercise 9.)
  36 *
  37 * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
  38 * which is very slightly easier to multiply by and makes no
  39 * difference to the hash distribution.
  40 */
  41#define GOLDEN_RATIO_32 0x61C88647
  42#define GOLDEN_RATIO_64 0x61C8864680B583EBull
  43
  44#ifdef CONFIG_HAVE_ARCH_HASH
  45/* This header may use the GOLDEN_RATIO_xx constants */
  46#include <asm/hash.h>
  47#endif
  48
  49/*
  50 * The _generic versions exist only so lib/test_hash.c can compare
  51 * the arch-optimized versions with the generic.
  52 *
  53 * Note that if you change these, any <asm/hash.h> that aren't updated
  54 * to match need to have their HAVE_ARCH_* define values updated so the
  55 * self-test will not false-positive.
  56 */
  57#ifndef HAVE_ARCH__HASH_32
  58#define __hash_32 __hash_32_generic
  59#endif
  60static inline u32 __hash_32_generic(u32 val)
  61{
  62        return val * GOLDEN_RATIO_32;
  63}
  64
  65#ifndef HAVE_ARCH_HASH_32
  66#define hash_32 hash_32_generic
  67#endif
  68static inline u32 hash_32_generic(u32 val, unsigned int bits)
  69{
  70        /* High bits are more random, so use them. */
  71        return __hash_32(val) >> (32 - bits);
  72}
  73
  74#ifndef HAVE_ARCH_HASH_64
  75#define hash_64 hash_64_generic
  76#endif
  77static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
  78{
  79#if BITS_PER_LONG == 64
  80        /* 64x64-bit multiply is efficient on all 64-bit processors */
  81        return val * GOLDEN_RATIO_64 >> (64 - bits);
  82#else
  83        /* Hash 64 bits using only 32x32-bit multiply. */
  84        return hash_32((u32)val ^ __hash_32(val >> 32), bits);
  85#endif
  86}
  87
  88static inline u32 hash_ptr(const void *ptr, unsigned int bits)
  89{
  90        return hash_long((unsigned long)ptr, bits);
  91}
  92
  93/* This really should be called fold32_ptr; it does no hashing to speak of. */
  94static inline u32 hash32_ptr(const void *ptr)
  95{
  96        unsigned long val = (unsigned long)ptr;
  97
  98#if BITS_PER_LONG == 64
  99        val ^= (val >> 32);
 100#endif
 101        return (u32)val;
 102}
 103
 104#endif /* _LINUX_HASH_H */
 105