diff options
Diffstat (limited to 'fs/ceph/ceph_hash.c')
| -rw-r--r-- | fs/ceph/ceph_hash.c | 118 |
1 files changed, 0 insertions, 118 deletions
diff --git a/fs/ceph/ceph_hash.c b/fs/ceph/ceph_hash.c deleted file mode 100644 index bd570015d147..000000000000 --- a/fs/ceph/ceph_hash.c +++ /dev/null | |||
| @@ -1,118 +0,0 @@ | |||
| 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 | { | ||
| 85 | unsigned long hash = 0; | ||
| 86 | unsigned char c; | ||
| 87 | |||
| 88 | while (length--) { | ||
| 89 | c = *str++; | ||
| 90 | hash = (hash + (c << 4) + (c >> 4)) * 11; | ||
| 91 | } | ||
| 92 | return hash; | ||
| 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 | |||
| 108 | const char *ceph_str_hash_name(int type) | ||
| 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 | } | ||
