Debian Codegraph @

include/hash.h

raw
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 #ifdef __GLIBC__
7 #include <bits/wordsize.h>
8 #else
9 #include <bits/reg.h>
10 #endif
11 #include <linux/stddef.h>
12 #include <sys/types.h>
13 #include <stdint.h>
14
15 /*
16 * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
17 * fs/inode.c. It's not actually prime any more (the previous primes
18 * were actively bad for hashing), but the name remains.
19 */
20 #if __WORDSIZE == 32
21 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
22 #define hash_long(val, bits) hash_32(val, bits)
23 #elif __WORDSIZE == 64
24 #define hash_long(val, bits) hash_64(val, bits)
25 #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
26 #else
27 #error Wordsize not 32 or 64
28 #endif
29
30 /* String based hash function */
31 static uint32_t inline hash(const char *key, unsigned int size)
32 {
33 u_int32_t hashval;
34 char *s = (char *) key;
35
36 for (hashval = 0; *s != '\0';) {
37 hashval += (unsigned char) *s++;
38 hashval += (hashval << 10);
39 hashval ^= (hashval >> 6);
40 }
41
42 hashval += (hashval << 3);
43 hashval ^= (hashval >> 11);
44 hashval += (hashval << 15);
45
46 return hashval % size;
47 }
48
49 /*
50 * This hash multiplies the input by a large odd number and takes the
51 * high bits. Since multiplication propagates changes to the most
52 * significant end only, it is essential that the high bits of the
53 * product be used for the hash value.
54 *
55 * Chuck Lever verified the effectiveness of this technique:
56 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
57 *
58 * Although a random odd number will do, it turns out that the golden
59 * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
60 * properties. (See Knuth vol 3, section 6.4, exercise 9.)
61 *
62 * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
63 * which is very slightly easier to multiply by and makes no
64 * difference to the hash distribution.
65 */
66 #define GOLDEN_RATIO_32 0x61C88647
67 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
68
69 static inline uint32_t __hash_32(uint32_t val)
70 {
71 return val * GOLDEN_RATIO_32;
72 }
73
74 static inline uint32_t hash_32(uint32_t val, unsigned int bits)
75 {
76 /* High bits are more random, so use them. */
77 return __hash_32(val) >> (32 - bits);
78 }
79
80 static __always_inline uint32_t hash_64(uint64_t val, unsigned int bits)
81 {
82 #if __WORDSIZE == 64
83 /* 64x64-bit multiply is efficient on all 64-bit processors */
84 return val * GOLDEN_RATIO_64 >> (64 - bits);
85 #else
86 /* Hash 64 bits using only 32x32-bit multiply. */
87 return hash_32((uint32_t) val ^ __hash_32(val >> 32), bits);
88 #endif
89 }
90
91 static inline uint32_t hash_ptr(const void *ptr, unsigned int bits)
92 {
93 return hash_long((unsigned long) ptr, bits);
94 }
95
96 /* This really should be called fold32_ptr; it does no hashing to speak of. */
97 static inline uint32_t hash32_ptr(const void *ptr)
98 {
99 unsigned long val = (unsigned long) ptr;
100
101 #if __WORDSIZE == 64
102 val ^= (val >> 32);
103 #endif
104 return (uint32_t) val;
105 }
106
107 #endif /* _LINUX_HASH_H */