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(const char *key
, size_t key_length
);
12 static uint32_t internal_generate_md5(const char *key
, size_t key_length
);
14 uint32_t memcached_generate_hash_value(const char *key
, size_t key_length
, memcached_hash hash_algorithm
)
16 uint32_t hash
= 1; /* Just here to remove compile warning */
19 switch (hash_algorithm
)
21 case MEMCACHED_HASH_DEFAULT
:
22 hash
= internal_generate_hash(key
, key_length
);
24 case MEMCACHED_HASH_MD5
:
25 hash
= internal_generate_md5(key
, key_length
);
27 case MEMCACHED_HASH_CRC
:
28 hash
= ((hash_crc32(key
, key_length
) >> 16) & 0x7fff);
32 /* FNV hash'es lifted from Dustin Sallings work */
33 case MEMCACHED_HASH_FNV1_64
:
35 /* Thanks to pierre@demartines.com for the pointer */
38 temp_hash
= FNV_64_INIT
;
39 for (x
= 0; x
< key_length
; x
++)
41 temp_hash
*= FNV_64_PRIME
;
44 hash
= (uint32_t)temp_hash
;
47 case MEMCACHED_HASH_FNV1A_64
:
50 for (x
= 0; x
< key_length
; x
++)
57 case MEMCACHED_HASH_FNV1_32
:
60 for (x
= 0; x
< key_length
; x
++)
67 case MEMCACHED_HASH_FNV1A_32
:
70 for (x
= 0; x
< key_length
; x
++)
77 #ifdef HAVE_HSIEH_HASH
78 case MEMCACHED_HASH_HSIEH
:
80 hash
= hsieh_hash(key
, key_length
);
84 case MEMCACHED_HASH_MURMUR
:
86 hash
= murmur_hash(key
, key_length
);
89 case MEMCACHED_HASH_JENKINS
:
91 hash
=jenkins_hash(key
, key_length
, 13);
98 uint32_t generate_hash(memcached_st
*ptr
, const char *key
, size_t key_length
)
100 uint32_t hash
= 1; /* Just here to remove compile warning */
103 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
105 if (ptr
->number_of_hosts
== 1)
108 hash
= memcached_generate_hash_value(key
, key_length
, ptr
->hash
);
109 WATCHPOINT_ASSERT(hash
);
113 static uint32_t dispatch_host(memcached_st
*ptr
, uint32_t hash
)
115 switch (ptr
->distribution
)
117 case MEMCACHED_DISTRIBUTION_CONSISTENT
:
118 case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA
:
120 uint32_t num
= ptr
->continuum_points_counter
;
121 WATCHPOINT_ASSERT(ptr
->continuum
);
124 memcached_continuum_item_st
*begin
, *end
, *left
, *right
, *middle
;
125 begin
= left
= ptr
->continuum
;
126 end
= right
= ptr
->continuum
+ num
;
130 middle
= left
+ (right
- left
) / 2;
131 if (middle
->value
< hash
)
141 case MEMCACHED_DISTRIBUTION_MODULA
:
142 return hash
% ptr
->number_of_hosts
;
143 case MEMCACHED_DISTRIBUTION_RANDOM
:
144 return random() % ptr
->number_of_hosts
;
146 WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
147 return hash
% ptr
->number_of_hosts
;
154 One day make this public, and have it return the actual memcached_server_st
155 to the calling application.
157 uint32_t memcached_generate_hash(memcached_st
*ptr
, const char *key
, size_t key_length
)
159 uint32_t hash
= 1; /* Just here to remove compile warning */
161 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
163 if (ptr
->number_of_hosts
== 1)
166 if (ptr
->flags
& MEM_HASH_WITH_PREFIX_KEY
)
168 int temp_len
= ptr
->prefix_key_length
+ key_length
;
169 char *temp
= (char *)malloc(temp_len
);
170 strncpy(temp
, ptr
->prefix_key
, ptr
->prefix_key_length
);
171 strncpy(temp
+ ptr
->prefix_key_length
, key
, key_length
);
172 hash
= generate_hash(ptr
, temp
, temp_len
);
177 hash
= generate_hash(ptr
, key
, key_length
);
180 WATCHPOINT_ASSERT(hash
);
182 if (memcached_behavior_get(ptr
, MEMCACHED_BEHAVIOR_AUTO_EJECT_HOSTS
) && ptr
->next_distribution_rebuild
) {
185 if (gettimeofday(&now
, NULL
) == 0 &&
186 now
.tv_sec
> ptr
->next_distribution_rebuild
)
187 run_distribution(ptr
);
190 return dispatch_host(ptr
, hash
);
193 static uint32_t internal_generate_hash(const char *key
, size_t key_length
)
195 const char *ptr
= key
;
201 value
+= (value
<< 10);
202 value
^= (value
>> 6);
204 value
+= (value
<< 3);
205 value
^= (value
>> 11);
206 value
+= (value
<< 15);
208 return value
== 0 ? 1 : value
;
211 static uint32_t internal_generate_md5(const char *key
, size_t key_length
)
213 unsigned char results
[16];
215 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
217 return ((uint32_t) (results
[3] & 0xFF) << 24)
218 | ((uint32_t) (results
[2] & 0xFF) << 16)
219 | ((uint32_t) (results
[1] & 0xFF) << 8)
220 | (results
[0] & 0xFF);