Adding in patch for DEAD server completion.
[awesomized/libmemcached] / libhashkit / hsieh.cc
1 /* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh
2 * derivative license.
3 * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
4 * details.
5 * http://www.azillionmonkeys.com/qed/hash.html
6 */
7
8 #include <libhashkit/common.h>
9
10 #undef get16bits
11 #if (defined(__GNUC__) && defined(__i386__))
12 #define get16bits(d) (*((const uint16_t *) (d)))
13 #endif
14
15 #if !defined (get16bits)
16 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
17 +(uint32_t)(((const uint8_t *)(d))[0]) )
18 #endif
19
20 #ifdef HAVE_HSIEH_HASH
21 uint32_t hashkit_hsieh(const char *key, size_t key_length, void *)
22 {
23 uint32_t hash = 0, tmp;
24 int rem;
25
26 if (key_length <= 0 || key == NULL)
27 return 0;
28
29 rem = key_length & 3;
30 key_length >>= 2;
31
32 /* Main loop */
33 for (;key_length > 0; key_length--)
34 {
35 hash += get16bits (key);
36 tmp = (get16bits (key+2) << 11) ^ hash;
37 hash = (hash << 16) ^ tmp;
38 key += 2*sizeof (uint16_t);
39 hash += hash >> 11;
40 }
41
42 /* Handle end cases */
43 switch (rem)
44 {
45 case 3: hash += get16bits (key);
46 hash ^= hash << 16;
47 hash ^= (uint32_t)key[sizeof (uint16_t)] << 18;
48 hash += hash >> 11;
49 break;
50 case 2: hash += get16bits (key);
51 hash ^= hash << 11;
52 hash += hash >> 17;
53 break;
54 case 1: hash += (unsigned char)(*key);
55 hash ^= hash << 10;
56 hash += hash >> 1;
57 default:
58 break;
59 }
60
61 /* Force "avalanching" of final 127 bits */
62 hash ^= hash << 3;
63 hash += hash >> 5;
64 hash ^= hash << 4;
65 hash += hash >> 17;
66 hash ^= hash << 25;
67 hash += hash >> 6;
68
69 return hash;
70 }
71 #else
72 uint32_t hashkit_hsieh(const char *, size_t , void *)
73 {
74 return 0;
75 }
76 #endif