4 static uint64_t FNV_64_INIT
= 0xcbf29ce484222325LL
;
5 static uint64_t FNV_64_PRIME
= 0x100000001b3LL
;
7 static uint32_t FNV_32_INIT
= 2166136261UL;
8 static uint32_t FNV_32_PRIME
= 16777619;
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
);
15 uint32_t generate_hash(memcached_st
*ptr
, char *key
, size_t key_length
)
17 uint32_t hash
= 1; /* Just here to remove compile warning */
21 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
23 if (ptr
->number_of_hosts
== 1)
28 case MEMCACHED_HASH_DEFAULT
:
29 hash
= internal_generate_hash(key
, key_length
);
31 case MEMCACHED_HASH_MD5
:
32 hash
= internal_generate_md5(key
, key_length
);
34 case MEMCACHED_HASH_CRC
:
35 hash
= ((hash_crc32(key
, key_length
) >> 16) & 0x7fff);
39 /* FNV hash'es lifted from Dustin Sallings work */
40 case MEMCACHED_HASH_FNV1_64
:
42 /* Thanks to pierre@demartines.com for the pointer */
45 temp_hash
= FNV_64_INIT
;
46 for (x
= 0; x
< key_length
; x
++)
48 temp_hash
*= FNV_64_PRIME
;
51 hash
= (uint32_t)temp_hash
;
54 case MEMCACHED_HASH_FNV1A_64
:
57 for (x
= 0; x
< key_length
; x
++)
64 case MEMCACHED_HASH_FNV1_32
:
67 for (x
= 0; x
< key_length
; x
++)
74 case MEMCACHED_HASH_FNV1A_32
:
77 for (x
= 0; x
< key_length
; x
++)
84 case MEMCACHED_HASH_KETAMA
:
86 hash
= internal_generate_ketama_md5(key
, key_length
);
89 case MEMCACHED_HASH_HSIEH
:
91 hash
= hsieh_hash(key
, key_length
);
94 case MEMCACHED_HASH_MURMUR
:
96 hash
= murmur_hash(key
, key_length
);
101 WATCHPOINT_ASSERT(hash
);
105 unsigned int dispatch_host(memcached_st
*ptr
, uint32_t hash
)
107 switch (ptr
->distribution
)
109 case MEMCACHED_DISTRIBUTION_CONSISTENT
:
110 case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA
:
112 int num
= ptr
->number_of_hosts
* MEMCACHED_POINTS_PER_SERVER
;
115 struct continuum_item
*begin
, *end
, *left
, *right
, *middle
;
116 begin
= left
= ptr
->continuum
;
117 end
= right
= ptr
->continuum
+ (num
- 1);
121 struct continuum_item
*rmiddle
;
123 middle
= left
+ (right
- left
) / 2;
133 if (hash
<rmiddle
->value
&& hash
>=middle
->value
)
134 return middle
->index
;
136 if (middle
->value
< hash
)
138 else if (middle
->value
> hash
)
146 case MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL
:
148 unsigned int server_key
;
150 server_key
= hash
% MEMCACHED_WHEEL_SIZE
;
152 return ptr
->wheel
[server_key
];
154 case MEMCACHED_DISTRIBUTION_MODULA
:
155 return hash
% ptr
->number_of_hosts
;
157 WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
158 return hash
% ptr
->number_of_hosts
;
161 if (ptr
->distribution
== MEMCACHED_DISTRIBUTION_MODULA
)
163 return hash
% ptr
->number_of_hosts
;
165 else if (ptr
->distribution
== MEMCACHED_DISTRIBUTION_CONSISTENT
)
167 unsigned int server_key
;
169 server_key
= hash
% MEMCACHED_WHEEL_SIZE
;
171 return ptr
->wheel
[server_key
];
173 else if (ptr
->distribution
== MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA
)
175 int num
= ptr
->number_of_hosts
* MEMCACHED_POINTS_PER_SERVER
;
178 struct continuum_item
*begin
, *end
, *left
, *right
, *middle
;
179 begin
= left
= ptr
->continuum
;
180 end
= right
= ptr
->continuum
+ (num
- 1);
183 middle
= left
+ (right
- left
) / 2;
192 struct continuum_item
*rmiddle
= middle
+1;
193 if(hash
<rmiddle
->value
&& hash
>=middle
->value
)
194 return middle
->index
;
196 if(middle
->value
< hash
) {
198 }else if(middle
->value
> hash
) {
208 WATCHPOINT_ASSERT(0);
212 unsigned int memcached_generate_hash(memcached_st
*ptr
, char *key
, size_t key_length
)
214 uint32_t hash
= 1; /* Just here to remove compile warning */
216 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
218 if (ptr
->number_of_hosts
== 1)
221 hash
= generate_hash(ptr
, key
, key_length
);
223 WATCHPOINT_ASSERT(hash
);
224 return dispatch_host(ptr
, hash
);
227 static uint32_t internal_generate_hash(char *key
, size_t key_length
)
235 value
+= (value
<< 10);
236 value
^= (value
>> 6);
238 value
+= (value
<< 3);
239 value
^= (value
>> 11);
240 value
+= (value
<< 15);
242 return value
== 0 ? 1 : value
;
245 static uint32_t internal_generate_md5(char *key
, size_t key_length
)
247 unsigned char results
[16];
249 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
251 return (uint32_t)(( results
[3] << 24 )
252 | ( results
[2] << 16 )
253 | ( results
[1] << 8 )
257 static uint32_t internal_generate_ketama_md5(char *key
, size_t key_length
)
259 unsigned char results
[16];
261 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
263 return ((uint32_t) (results
[3] & 0xFF) << 24)
264 | ((uint32_t) (results
[2] & 0xFF) << 16)
265 | ((uint32_t) (results
[1] & 0xFF) << 8)
266 | (results
[0] & 0xFF);