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
);
14 uint32_t generate_hash(memcached_st
*ptr
, char *key
, size_t key_length
)
16 uint32_t hash
= 1; /* Just here to remove compile warning */
20 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
22 if (ptr
->number_of_hosts
== 1)
27 case MEMCACHED_HASH_DEFAULT
:
28 hash
= internal_generate_hash(key
, key_length
);
30 case MEMCACHED_HASH_MD5
:
31 hash
= internal_generate_md5(key
, key_length
);
33 case MEMCACHED_HASH_CRC
:
34 hash
= ((hash_crc32(key
, key_length
) >> 16) & 0x7fff);
38 /* FNV hash'es lifted from Dustin Sallings work */
39 case MEMCACHED_HASH_FNV1_64
:
41 /* Thanks to pierre@demartines.com for the pointer */
44 temp_hash
= FNV_64_INIT
;
45 for (x
= 0; x
< key_length
; x
++)
47 temp_hash
*= FNV_64_PRIME
;
50 hash
= (uint32_t)temp_hash
;
53 case MEMCACHED_HASH_FNV1A_64
:
56 for (x
= 0; x
< key_length
; x
++)
63 case MEMCACHED_HASH_FNV1_32
:
66 for (x
= 0; x
< key_length
; x
++)
73 case MEMCACHED_HASH_FNV1A_32
:
76 for (x
= 0; x
< key_length
; x
++)
83 case MEMCACHED_HASH_HSIEH
:
85 hash
= hsieh_hash(key
, key_length
);
88 case MEMCACHED_HASH_MURMUR
:
90 hash
= murmur_hash(key
, key_length
);
95 WATCHPOINT_ASSERT(hash
);
99 unsigned int dispatch_host(memcached_st
*ptr
, uint32_t hash
)
101 switch (ptr
->distribution
)
103 case MEMCACHED_DISTRIBUTION_CONSISTENT
:
104 case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA
:
106 uint32_t num
= ptr
->number_of_hosts
* MEMCACHED_POINTS_PER_SERVER
;
107 WATCHPOINT_ASSERT(ptr
->continuum
);
110 memcached_continuum_item_st
*begin
, *end
, *left
, *right
, *middle
;
111 begin
= left
= ptr
->continuum
;
112 end
= right
= ptr
->continuum
+ (num
- 1);
116 memcached_continuum_item_st
*rmiddle
;
118 middle
= left
+ (right
- left
) / 2;
128 if (hash
<rmiddle
->value
&& hash
>=middle
->value
)
129 return middle
->index
;
131 if (middle
->value
< hash
)
133 else if (middle
->value
> hash
)
141 case MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL
:
143 unsigned int server_key
;
145 server_key
= hash
% MEMCACHED_STRIDE
* ptr
->wheel_count
;
147 return ptr
->wheel
[server_key
];
149 case MEMCACHED_DISTRIBUTION_MODULA
:
150 return hash
% ptr
->number_of_hosts
;
152 WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
153 return hash
% ptr
->number_of_hosts
;
156 WATCHPOINT_ASSERT(0); /* We should never reach here */
161 One day make this public, and have it return the actual memcached_server_st
162 to the calling application.
164 uint32_t memcached_generate_hash(memcached_st
*ptr
, char *key
, size_t key_length
)
166 uint32_t hash
= 1; /* Just here to remove compile warning */
168 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
170 if (ptr
->number_of_hosts
== 1)
173 hash
= generate_hash(ptr
, key
, key_length
);
175 WATCHPOINT_ASSERT(hash
);
176 return dispatch_host(ptr
, hash
);
179 static uint32_t internal_generate_hash(char *key
, size_t key_length
)
187 value
+= (value
<< 10);
188 value
^= (value
>> 6);
190 value
+= (value
<< 3);
191 value
^= (value
>> 11);
192 value
+= (value
<< 15);
194 return value
== 0 ? 1 : value
;
197 static uint32_t internal_generate_md5(char *key
, size_t key_length
)
199 unsigned char results
[16];
201 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
203 return ((uint32_t) (results
[3] & 0xFF) << 24)
204 | ((uint32_t) (results
[2] & 0xFF) << 16)
205 | ((uint32_t) (results
[1] & 0xFF) << 8)
206 | (results
[0] & 0xFF);