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 unsigned int memcached_generate_hash(memcached_st
*ptr
, char *key
, size_t key_length
)
17 uint32_t hash
= 1; /* Just here to remove compile warning */
20 WATCHPOINT_ASSERT(ptr
->number_of_hosts
);
24 case MEMCACHED_HASH_DEFAULT
:
25 hash
= internal_generate_hash(key
, key_length
);
27 case MEMCACHED_HASH_MD5
:
28 hash
= internal_generate_md5(key
, key_length
);
30 case MEMCACHED_HASH_CRC
:
31 hash
= ((hash_crc32(key
, key_length
) >> 16) & 0x7fff);
35 /* FNV hash'es lifted from Dustin Sallings work */
36 case MEMCACHED_HASH_FNV1_64
:
38 /* Thanks to pierre@demartines.com for the pointer */
41 temp_hash
= FNV_64_INIT
;
42 for (x
= 0; x
< key_length
; x
++)
44 temp_hash
*= FNV_64_PRIME
;
47 hash
= (uint32_t)temp_hash
;
50 case MEMCACHED_HASH_FNV1A_64
:
53 for (x
= 0; x
< key_length
; x
++)
60 case MEMCACHED_HASH_FNV1_32
:
63 for (x
= 0; x
< key_length
; x
++)
70 case MEMCACHED_HASH_FNV1A_32
:
73 for (x
= 0; x
< key_length
; x
++)
80 case MEMCACHED_HASH_KETAMA
:
82 hash
= internal_generate_ketama_md5(key
, key_length
);
85 case MEMCACHED_HASH_HSIEH
:
87 hash
= hsieh_hash(key
, key_length
);
92 WATCHPOINT_ASSERT(hash
);
94 if (ptr
->distribution
== MEMCACHED_DISTRIBUTION_MODULA
)
96 return hash
% ptr
->number_of_hosts
;
100 unsigned int server_key
;
102 server_key
= hash
% MEMCACHED_WHEEL_SIZE
;
104 return ptr
->wheel
[server_key
];
108 static uint32_t internal_generate_hash(char *key
, size_t key_length
)
116 value
+= (value
<< 10);
117 value
^= (value
>> 6);
119 value
+= (value
<< 3);
120 value
^= (value
>> 11);
121 value
+= (value
<< 15);
123 return value
== 0 ? 1 : value
;
126 static uint32_t internal_generate_md5(char *key
, size_t key_length
)
128 unsigned char results
[16];
130 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
132 return (uint32_t)(( results
[3] << 24 )
133 | ( results
[2] << 16 )
134 | ( results
[1] << 8 )
138 static uint32_t internal_generate_ketama_md5(char *key
, size_t key_length
)
140 unsigned char results
[16];
142 md5_signature((unsigned char*)key
, (unsigned int)key_length
, results
);
144 return ((uint32_t) (results
[3] & 0xFF) << 24)
145 | ((uint32_t) (results
[2] & 0xFF) << 16)
146 | ((uint32_t) (results
[1] & 0xFF) << 8)
147 | (results
[0] & 0xFF);