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