Blame view
net/ceph/ceph_hash.c
2.88 KB
1654dd0cf ceph: make object... |
1 |
|
3d14c5d2b ceph: factor out ... |
2 |
#include <linux/ceph/types.h> |
6c0f3af72 ceph: add dir_lay... |
3 |
#include <linux/module.h> |
1654dd0cf ceph: make object... |
4 5 6 |
/* * Robert Jenkin's hash function. |
94f17c00d libceph: replace ... |
7 |
* https://burtleburtle.net/bob/hash/evahash.html |
1654dd0cf ceph: make object... |
8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
* This is in the public domain. */ #define mix(a, b, c) \ do { \ a = a - b; a = a - c; a = a ^ (c >> 13); \ b = b - c; b = b - a; b = b ^ (a << 8); \ c = c - a; c = c - b; c = c ^ (b >> 13); \ a = a - b; a = a - c; a = a ^ (c >> 12); \ b = b - c; b = b - a; b = b ^ (a << 16); \ c = c - a; c = c - b; c = c ^ (b >> 5); \ a = a - b; a = a - c; a = a ^ (c >> 3); \ b = b - c; b = b - a; b = b ^ (a << 10); \ c = c - a; c = c - b; c = c ^ (b >> 15); \ } while (0) |
95c961747 net: cleanup unsi... |
22 |
unsigned int ceph_str_hash_rjenkins(const char *str, unsigned int length) |
1654dd0cf ceph: make object... |
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
{ const unsigned char *k = (const unsigned char *)str; __u32 a, b, c; /* the internal state */ __u32 len; /* how many key bytes still need mixing */ /* Set up the internal state */ len = length; a = 0x9e3779b9; /* the golden ratio; an arbitrary value */ b = a; c = 0; /* variable initialization of internal state */ /* handle most of the key */ while (len >= 12) { a = a + (k[0] + ((__u32)k[1] << 8) + ((__u32)k[2] << 16) + ((__u32)k[3] << 24)); b = b + (k[4] + ((__u32)k[5] << 8) + ((__u32)k[6] << 16) + ((__u32)k[7] << 24)); c = c + (k[8] + ((__u32)k[9] << 8) + ((__u32)k[10] << 16) + ((__u32)k[11] << 24)); mix(a, b, c); k = k + 12; len = len - 12; } /* handle the last 11 bytes */ c = c + length; |
18370b36b ceph: mark expect... |
49 |
switch (len) { |
1654dd0cf ceph: make object... |
50 51 |
case 11: c = c + ((__u32)k[10] << 24); |
df561f668 treewide: Use fal... |
52 |
fallthrough; |
1654dd0cf ceph: make object... |
53 54 |
case 10: c = c + ((__u32)k[9] << 16); |
df561f668 treewide: Use fal... |
55 |
fallthrough; |
1654dd0cf ceph: make object... |
56 57 58 |
case 9: c = c + ((__u32)k[8] << 8); /* the first byte of c is reserved for the length */ |
df561f668 treewide: Use fal... |
59 |
fallthrough; |
1654dd0cf ceph: make object... |
60 61 |
case 8: b = b + ((__u32)k[7] << 24); |
df561f668 treewide: Use fal... |
62 |
fallthrough; |
1654dd0cf ceph: make object... |
63 64 |
case 7: b = b + ((__u32)k[6] << 16); |
df561f668 treewide: Use fal... |
65 |
fallthrough; |
1654dd0cf ceph: make object... |
66 67 |
case 6: b = b + ((__u32)k[5] << 8); |
df561f668 treewide: Use fal... |
68 |
fallthrough; |
1654dd0cf ceph: make object... |
69 70 |
case 5: b = b + k[4]; |
df561f668 treewide: Use fal... |
71 |
fallthrough; |
1654dd0cf ceph: make object... |
72 73 |
case 4: a = a + ((__u32)k[3] << 24); |
df561f668 treewide: Use fal... |
74 |
fallthrough; |
1654dd0cf ceph: make object... |
75 76 |
case 3: a = a + ((__u32)k[2] << 16); |
df561f668 treewide: Use fal... |
77 |
fallthrough; |
1654dd0cf ceph: make object... |
78 79 |
case 2: a = a + ((__u32)k[1] << 8); |
df561f668 treewide: Use fal... |
80 |
fallthrough; |
1654dd0cf ceph: make object... |
81 82 83 84 85 86 87 88 89 90 91 92 |
case 1: a = a + k[0]; /* case 0: nothing left to add */ } mix(a, b, c); return c; } /* * linux dcache hash */ |
95c961747 net: cleanup unsi... |
93 |
unsigned int ceph_str_hash_linux(const char *str, unsigned int length) |
1654dd0cf ceph: make object... |
94 |
{ |
50b885b96 ceph: whitespace ... |
95 |
unsigned long hash = 0; |
1654dd0cf ceph: make object... |
96 |
unsigned char c; |
50b885b96 ceph: whitespace ... |
97 |
while (length--) { |
1654dd0cf ceph: make object... |
98 99 100 |
c = *str++; hash = (hash + (c << 4) + (c >> 4)) * 11; } |
50b885b96 ceph: whitespace ... |
101 |
return hash; |
1654dd0cf ceph: make object... |
102 |
} |
95c961747 net: cleanup unsi... |
103 |
unsigned int ceph_str_hash(int type, const char *s, unsigned int len) |
1654dd0cf ceph: make object... |
104 105 106 107 108 109 110 111 112 113 |
{ switch (type) { case CEPH_STR_HASH_LINUX: return ceph_str_hash_linux(s, len); case CEPH_STR_HASH_RJENKINS: return ceph_str_hash_rjenkins(s, len); default: return -1; } } |
6c0f3af72 ceph: add dir_lay... |
114 |
EXPORT_SYMBOL(ceph_str_hash); |
1654dd0cf ceph: make object... |
115 |
|
50b885b96 ceph: whitespace ... |
116 |
const char *ceph_str_hash_name(int type) |
1654dd0cf ceph: make object... |
117 118 119 120 121 122 123 124 125 126 |
{ switch (type) { case CEPH_STR_HASH_LINUX: return "linux"; case CEPH_STR_HASH_RJENKINS: return "rjenkins"; default: return "unknown"; } } |
6c0f3af72 ceph: add dir_lay... |
127 |
EXPORT_SYMBOL(ceph_str_hash_name); |