New version update
[m6w6/libmemcached] / libmemcached / memcached_hash.c
1 #include "common.h"
2
3 /* Defines */
4 static uint64_t FNV_64_INIT= 0xcbf29ce484222325LL;
5 static uint64_t FNV_64_PRIME= 0x100000001b3LL;
6
7 static uint32_t FNV_32_INIT= 2166136261UL;
8 static uint32_t FNV_32_PRIME= 16777619;
9
10 /* Prototypes */
11 static uint32_t internal_generate_hash(char *key, size_t key_length);
12 static uint32_t internal_generate_md5(char *key, size_t key_length);
13 static uint32_t internal_generate_ketama_md5(char *key, size_t key_length);
14
15 unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length)
16 {
17 uint32_t hash= 1; /* Just here to remove compile warning */
18 unsigned int x;
19
20 WATCHPOINT_ASSERT(ptr->number_of_hosts);
21
22 if (ptr->number_of_hosts == 1)
23 return 0;
24
25 switch (ptr->hash)
26 {
27 case MEMCACHED_HASH_DEFAULT:
28 hash= internal_generate_hash(key, key_length);
29 break;
30 case MEMCACHED_HASH_MD5:
31 hash= internal_generate_md5(key, key_length);
32 break;
33 case MEMCACHED_HASH_CRC:
34 hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff);
35 if (hash == 0)
36 hash= 1;
37 break;
38 /* FNV hash'es lifted from Dustin Sallings work */
39 case MEMCACHED_HASH_FNV1_64:
40 {
41 /* Thanks to pierre@demartines.com for the pointer */
42 uint64_t temp_hash;
43
44 temp_hash= FNV_64_INIT;
45 for (x= 0; x < key_length; x++)
46 {
47 temp_hash *= FNV_64_PRIME;
48 temp_hash ^= key[x];
49 }
50 hash= (uint32_t)temp_hash;
51 }
52 break;
53 case MEMCACHED_HASH_FNV1A_64:
54 {
55 hash= FNV_64_INIT;
56 for (x= 0; x < key_length; x++)
57 {
58 hash ^= key[x];
59 hash *= FNV_64_PRIME;
60 }
61 }
62 break;
63 case MEMCACHED_HASH_FNV1_32:
64 {
65 hash= FNV_32_INIT;
66 for (x= 0; x < key_length; x++)
67 {
68 hash *= FNV_32_PRIME;
69 hash ^= key[x];
70 }
71 }
72 break;
73 case MEMCACHED_HASH_FNV1A_32:
74 {
75 hash= FNV_32_INIT;
76 for (x= 0; x < key_length; x++)
77 {
78 hash ^= key[x];
79 hash *= FNV_32_PRIME;
80 }
81 }
82 break;
83 case MEMCACHED_HASH_KETAMA:
84 {
85 hash= internal_generate_ketama_md5(key, key_length);
86 break;
87 }
88 case MEMCACHED_HASH_HSIEH:
89 {
90 hash= hsieh_hash(key, key_length);
91 break;
92 }
93 case MEMCACHED_HASH_MURMUR:
94 {
95 hash= murmur_hash(key, key_length);
96 break;
97 }
98 }
99
100 WATCHPOINT_ASSERT(hash);
101
102 if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA)
103 {
104 return hash % ptr->number_of_hosts;
105 }
106 else
107 {
108 unsigned int server_key;
109
110 server_key= hash % MEMCACHED_WHEEL_SIZE;
111
112 return ptr->wheel[server_key];
113 }
114 }
115
116 static uint32_t internal_generate_hash(char *key, size_t key_length)
117 {
118 char *ptr= key;
119 uint32_t value= 0;
120
121 while (--key_length)
122 {
123 value += *ptr++;
124 value += (value << 10);
125 value ^= (value >> 6);
126 }
127 value += (value << 3);
128 value ^= (value >> 11);
129 value += (value << 15);
130
131 return value == 0 ? 1 : value;
132 }
133
134 static uint32_t internal_generate_md5(char *key, size_t key_length)
135 {
136 unsigned char results[16];
137
138 md5_signature((unsigned char*)key, (unsigned int)key_length, results);
139
140 return (uint32_t)(( results[3] << 24 )
141 | ( results[2] << 16 )
142 | ( results[1] << 8 )
143 | results[0] );
144 }
145
146 static uint32_t internal_generate_ketama_md5(char *key, size_t key_length)
147 {
148 unsigned char results[16];
149
150 md5_signature((unsigned char*)key, (unsigned int)key_length, results);
151
152 return ((uint32_t) (results[3] & 0xFF) << 24)
153 | ((uint32_t) (results[2] & 0xFF) << 16)
154 | ((uint32_t) (results[1] & 0xFF) << 8)
155 | (results[0] & 0xFF);
156 }