X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=libmemcached%2Fmemcached_hash.c;h=395020a39afb2de33616be39633bf4be03cf2c0e;hb=fa11f4a5d1a9c92eda13f8a5aa11dcff542b8815;hp=f365cc0ee6815b817e3304573b316a0d3f098144;hpb=34a8c3858f30b02568c87f56a827f618aba6d6be;p=m6w6%2Flibmemcached diff --git a/libmemcached/memcached_hash.c b/libmemcached/memcached_hash.c index f365cc0e..395020a3 100644 --- a/libmemcached/memcached_hash.c +++ b/libmemcached/memcached_hash.c @@ -1,28 +1,23 @@ #include "common.h" + /* Defines */ -static uint64_t FNV_64_INIT= 0xcbf29ce484222325LL; -static uint64_t FNV_64_PRIME= 0x100000001b3LL; +static uint64_t FNV_64_INIT= UINT64_C(0xcbf29ce484222325); +static uint64_t FNV_64_PRIME= UINT64_C(0x100000001b3); static uint32_t FNV_32_INIT= 2166136261UL; static uint32_t FNV_32_PRIME= 16777619; /* Prototypes */ -static uint32_t internal_generate_hash(char *key, size_t key_length); -static uint32_t internal_generate_md5(char *key, size_t key_length); -static uint32_t internal_generate_ketama_md5(char *key, size_t key_length); +static uint32_t internal_generate_hash(const char *key, size_t key_length); +static uint32_t internal_generate_md5(const char *key, size_t key_length); -unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length) +uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash_t hash_algorithm) { uint32_t hash= 1; /* Just here to remove compile warning */ - unsigned int x; - - WATCHPOINT_ASSERT(ptr->number_of_hosts); - - if (ptr->number_of_hosts == 1) - return 0; + uint32_t x= 0; - switch (ptr->hash) + switch (hash_algorithm) { case MEMCACHED_HASH_DEFAULT: hash= internal_generate_hash(key, key_length); @@ -36,58 +31,58 @@ unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_le hash= 1; break; /* FNV hash'es lifted from Dustin Sallings work */ - case MEMCACHED_HASH_FNV1_64: + case MEMCACHED_HASH_FNV1_64: { /* Thanks to pierre@demartines.com for the pointer */ uint64_t temp_hash; temp_hash= FNV_64_INIT; - for (x= 0; x < key_length; x++) + for (x= 0; x < key_length; x++) { temp_hash *= FNV_64_PRIME; - temp_hash ^= key[x]; + temp_hash ^= (uint64_t)key[x]; } hash= (uint32_t)temp_hash; } break; - case MEMCACHED_HASH_FNV1A_64: + case MEMCACHED_HASH_FNV1A_64: { - hash= FNV_64_INIT; - for (x= 0; x < key_length; x++) + hash= (uint32_t) FNV_64_INIT; + for (x= 0; x < key_length; x++) { - hash ^= key[x]; - hash *= FNV_64_PRIME; + uint32_t val= (uint32_t)key[x]; + hash ^= val; + hash *= (uint32_t) FNV_64_PRIME; } } break; - case MEMCACHED_HASH_FNV1_32: + case MEMCACHED_HASH_FNV1_32: { hash= FNV_32_INIT; - for (x= 0; x < key_length; x++) + for (x= 0; x < key_length; x++) { + uint32_t val= (uint32_t)key[x]; hash *= FNV_32_PRIME; - hash ^= key[x]; + hash ^= val; } } break; - case MEMCACHED_HASH_FNV1A_32: + case MEMCACHED_HASH_FNV1A_32: { hash= FNV_32_INIT; - for (x= 0; x < key_length; x++) + for (x= 0; x < key_length; x++) { - hash ^= key[x]; + uint32_t val= (uint32_t)key[x]; + hash ^= val; hash *= FNV_32_PRIME; } } break; - case MEMCACHED_HASH_KETAMA: - { - hash= internal_generate_ketama_md5(key, key_length); - break; - } case MEMCACHED_HASH_HSIEH: { +#ifdef HAVE_HSIEH_HASH hash= hsieh_hash(key, key_length); +#endif break; } case MEMCACHED_HASH_MURMUR: @@ -95,55 +90,138 @@ unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_le hash= murmur_hash(key, key_length); break; } + case MEMCACHED_HASH_JENKINS: + { + hash=jenkins_hash(key, key_length, 13); + break; + } + default: + { + WATCHPOINT_ASSERT(hash_algorithm); + break; + } } + return hash; +} + +uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length) +{ + uint32_t hash= 1; /* Just here to remove compile warning */ + + WATCHPOINT_ASSERT(ptr->number_of_hosts); + + if (ptr->number_of_hosts == 1) + return 0; + + hash= memcached_generate_hash_value(key, key_length, ptr->hash); WATCHPOINT_ASSERT(hash); + return hash; +} - if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA) +static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash) +{ + switch (ptr->distribution) { + case MEMCACHED_DISTRIBUTION_CONSISTENT: + case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA: + case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA_SPY: + { + uint32_t num= ptr->continuum_points_counter; + WATCHPOINT_ASSERT(ptr->continuum); + + hash= hash; + memcached_continuum_item_st *begin, *end, *left, *right, *middle; + begin= left= ptr->continuum; + end= right= ptr->continuum + num; + + while (left < right) + { + middle= left + (right - left) / 2; + if (middle->value < hash) + left= middle + 1; + else + right= middle; + } + if (right == end) + right= begin; + return right->index; + } + case MEMCACHED_DISTRIBUTION_MODULA: + return hash % ptr->number_of_hosts; + case MEMCACHED_DISTRIBUTION_RANDOM: + return (uint32_t) random() % ptr->number_of_hosts; + default: + WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */ return hash % ptr->number_of_hosts; } + + /* NOTREACHED */ +} + +/* + One day make this public, and have it return the actual memcached_server_st + to the calling application. +*/ +uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length) +{ + uint32_t hash= 1; /* Just here to remove compile warning */ + + WATCHPOINT_ASSERT(ptr->number_of_hosts); + + if (ptr->number_of_hosts == 1) + return 0; + + if (ptr->flags.hash_with_prefix_key) + { + size_t temp_length= ptr->prefix_key_length + key_length; + char temp[temp_length]; + + if (temp_length > MEMCACHED_MAX_KEY -1) + return 0; + + strncpy(temp, ptr->prefix_key, ptr->prefix_key_length); + strncpy(temp + ptr->prefix_key_length, key, key_length); + hash= generate_hash(ptr, temp, temp_length); + } else { - unsigned int server_key; + hash= generate_hash(ptr, key, key_length); + } + + WATCHPOINT_ASSERT(hash); - server_key= hash % MEMCACHED_WHEEL_SIZE; + if (memcached_behavior_get(ptr, MEMCACHED_BEHAVIOR_AUTO_EJECT_HOSTS) && ptr->next_distribution_rebuild) { + struct timeval now; - return ptr->wheel[server_key]; + if (gettimeofday(&now, NULL) == 0 && + now.tv_sec > ptr->next_distribution_rebuild) + run_distribution(ptr); } + + return dispatch_host(ptr, hash); } -static uint32_t internal_generate_hash(char *key, size_t key_length) +static uint32_t internal_generate_hash(const char *key, size_t key_length) { - char *ptr= key; + const char *ptr= key; uint32_t value= 0; - while (--key_length) + while (key_length--) { - value += *ptr++; + uint32_t val= (uint32_t) *ptr++; + value += val; value += (value << 10); value ^= (value >> 6); } value += (value << 3); value ^= (value >> 11); - value += (value << 15); - - return value == 0 ? 1 : value; -} - -static uint32_t internal_generate_md5(char *key, size_t key_length) -{ - unsigned char results[16]; - - md5_signature((unsigned char*)key, (unsigned int)key_length, results); + value += (value << 15); - return (uint32_t)(( results[3] << 24 ) - | ( results[2] << 16 ) - | ( results[1] << 8 ) - | results[0] ); + return value == 0 ? 1 : (uint32_t) value; } -static uint32_t internal_generate_ketama_md5(char *key, size_t key_length) +static uint32_t internal_generate_md5(const char *key, size_t key_length) { unsigned char results[16];