← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xen/utopic

« back to all changes in this revision

Viewing changes to xen/include/xen/hash.h

  • Committer: Bazaar Package Importer
  • Author(s): Bastian Blank
  • Date: 2010-05-06 15:47:38 UTC
  • mto: (1.3.1) (15.1.1 sid) (4.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20100506154738-agoz0rlafrh1fnq7
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
xen/include/xen/hash.h
 
1
#ifndef _XEN_HASH_H
 
2
#define _XEN_HASH_H
 
3
/* Fast hashing routine for a long.
 
4
   (C) 2002 William Lee Irwin III, IBM */
 
5
 
 
6
/*
 
7
 * Knuth recommends primes in approximately golden ratio to the maximum
 
8
 * integer representable by a machine word for multiplicative hashing.
 
9
 * Chuck Lever verified the effectiveness of this technique:
 
10
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 
11
 *
 
12
 * These primes are chosen to be bit-sparse, that is operations on
 
13
 * them can use shifts and additions instead of multiplications for
 
14
 * machines where multiplications are slow.
 
15
 */
 
16
#if BITS_PER_LONG == 32
 
17
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
 
18
#define GOLDEN_RATIO_PRIME 0x9e370001UL
 
19
#elif BITS_PER_LONG == 64
 
20
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
 
21
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
 
22
#else
 
23
#error Define GOLDEN_RATIO_PRIME for your wordsize.
 
24
#endif
 
25
 
 
26
static inline unsigned long hash_long(unsigned long val, unsigned int bits)
 
27
{
 
28
    unsigned long hash = val;
 
29
 
 
30
#if BITS_PER_LONG == 64
 
31
    /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 
32
    unsigned long n = hash;
 
33
    n <<= 18;
 
34
    hash -= n;
 
35
    n <<= 33;
 
36
    hash -= n;
 
37
    n <<= 3;
 
38
    hash += n;
 
39
    n <<= 3;
 
40
    hash -= n;
 
41
    n <<= 4;
 
42
    hash += n;
 
43
    n <<= 2;
 
44
    hash += n;
 
45
#else
 
46
    /* On some cpus multiply is faster, on others gcc will do shifts */
 
47
    hash *= GOLDEN_RATIO_PRIME;
 
48
#endif
 
49
 
 
50
    /* High bits are more random, so use them. */
 
51
    return hash >> (BITS_PER_LONG - bits);
 
52
}
 
53
 
 
54
static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
 
55
{
 
56
    return hash_long((unsigned long)ptr, bits);
 
57
}
 
58
#endif /* _XEN_HASH_H */