libcfs/include/libcfs/libcfs_hash.h

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * vim:expandtab:shiftwidth=8:tabstop=8:
   3  *
   4  * GPL HEADER START
   5  *
   6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License version 2 only,
  10  * as published by the Free Software Foundation.
  11  *
  12  * This program is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License version 2 for more details (a copy is included
  16  * in the LICENSE file that accompanied this code).
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * version 2 along with this program; If not, see
  20  * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
  21  *
  22  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  23  * CA 95054 USA or visit www.sun.com if you need additional information or
  24  * have any questions.
  25  *
  26  * GPL HEADER END
  27  */
  28 /*
  29  * Copyright  2008 Sun Microsystems, Inc. All rights reserved
  30  * Use is subject to license terms.
  31  */
  32 /*
  33  * This file is part of Lustre, http://www.lustre.org/
  34  * Lustre is a trademark of Sun Microsystems, Inc.
  35  *
  36  * libcfs/include/libcfs/libcfs_hash.h
  37  *
  38  * Hashing routines
  39  *
  40  */
  41
  42 #ifndef __LIBCFS_HASH_H__
  43 #define __LIBCFS_HASH_H__
  44
  45 /*
  46  * Ideally we would use HAVE_HASH_LONG for this, but on linux we configure
  47  * the linux kernel and user space at the same time, so we need to differentiate
  48  * between them explicitely. If this is not needed on other architectures, then
  49  * we'll need to move the functions to archi specific headers.
  50  */
  51
  52 #if (defined __linux__ && defined __KERNEL__)
  53 #include <linux/hash.h>
  54 #else
  55 /* Fast hashing routine for a long.
  56    (C) 2002 William Lee Irwin III, IBM */
  57
  58 /*
  59  * Knuth recommends primes in approximately golden ratio to the maximum
  60  * integer representable by a machine word for multiplicative hashing.
  61  * Chuck Lever verified the effectiveness of this technique:
  62  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
  63  *
  64  * These primes are chosen to be bit-sparse, that is operations on
  65  * them can use shifts and additions instead of multiplications for
  66  * machines where multiplications are slow.
  67  */
  68 #if BITS_PER_LONG == 32
  69 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  70 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  71 #elif BITS_PER_LONG == 64
  72 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  73 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  74 #else
  75 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  76 #endif
  77
  78 static inline unsigned long hash_long(unsigned long val, unsigned int bits)
  79 {
  80         unsigned long hash = val;
  81
  82 #if BITS_PER_LONG == 64
  83         /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  84         unsigned long n = hash;
  85         n <<= 18;
  86         hash -= n;
  87         n <<= 33;
  88         hash -= n;
  89         n <<= 3;
  90         hash += n;
  91         n <<= 3;
  92         hash -= n;
  93         n <<= 4;
  94         hash += n;
  95         n <<= 2;
  96         hash += n;
  97 #else
  98         /* On some cpus multiply is faster, on others gcc will do shifts */
  99         hash *= GOLDEN_RATIO_PRIME;
 100 #endif
 101
 102         /* High bits are more random, so use them. */
 103         return hash >> (BITS_PER_LONG - bits);
 104 }
 105 #if 0
 106 static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
 107 {
 108         return hash_long((unsigned long)ptr, bits);
 109 }
 110 #endif
 111
 112 /* !(__linux__ && __KERNEL__) */
 113 #endif
 114
 115 /* !__LIBCFS__HASH_H__ */
 116 #endif