| 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 */ |