X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=libmemcached%2Fmemcached_hash.c;h=129d76127e8e7271a5d19861892da6b4c474addd;hb=9131482f7923cf9e90b5a715b38e70e3a229b052;hp=b8c8cfe5529923f1f0c5546a4c0ba04db5434e9d;hpb=db3442ca6769650638eab10b130a54882045fff0;p=m6w6%2Flibmemcached diff --git a/libmemcached/memcached_hash.c b/libmemcached/memcached_hash.c index b8c8cfe5..129d7612 100644 --- a/libmemcached/memcached_hash.c +++ b/libmemcached/memcached_hash.c @@ -1,8 +1,9 @@ #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; @@ -11,7 +12,7 @@ static uint32_t FNV_32_PRIME= 16777619; 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); -uint32_t generate_hash_value(const char *key, size_t key_length, memcached_hash hash_algorithm) +uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash hash_algorithm) { uint32_t hash= 1; /* Just here to remove compile warning */ uint32_t x= 0; @@ -39,18 +40,19 @@ uint32_t generate_hash_value(const char *key, size_t key_length, memcached_hash 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: { - hash= FNV_64_INIT; + 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; @@ -59,8 +61,9 @@ uint32_t generate_hash_value(const char *key, size_t key_length, memcached_hash hash= FNV_32_INIT; for (x= 0; x < key_length; x++) { + uint32_t val= (uint32_t)key[x]; hash *= FNV_32_PRIME; - hash ^= key[x]; + hash ^= val; } } break; @@ -69,14 +72,17 @@ uint32_t generate_hash_value(const char *key, size_t key_length, memcached_hash hash= FNV_32_INIT; 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_HSIEH: { +#ifdef HAVE_HSIEH_HASH hash= hsieh_hash(key, key_length); +#endif break; } case MEMCACHED_HASH_MURMUR: @@ -84,6 +90,16 @@ uint32_t generate_hash_value(const char *key, size_t key_length, memcached_hash 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; } @@ -98,12 +114,12 @@ uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length) if (ptr->number_of_hosts == 1) return 0; - hash= generate_hash_value(key, key_length, ptr->hash); + hash= memcached_generate_hash_value(key, key_length, ptr->hash); WATCHPOINT_ASSERT(hash); return hash; } -unsigned int dispatch_host(memcached_st *ptr, uint32_t hash) +static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash) { switch (ptr->distribution) { @@ -116,44 +132,30 @@ unsigned int dispatch_host(memcached_st *ptr, uint32_t hash) hash= hash; memcached_continuum_item_st *begin, *end, *left, *right, *middle; begin= left= ptr->continuum; - end= right= ptr->continuum + (num - 1); + end= right= ptr->continuum + num; - while (1) + while (left < right) { - memcached_continuum_item_st *rmiddle; - - middle = left + (right - left) / 2; - - if (middle==end) - return begin->index; - - if (middle==begin) - return end->index; - - rmiddle = middle+1; - - if (hashvalue && hash>=middle->value) - return middle->index; - + middle= left + (right - left) / 2; if (middle->value < hash) - left = middle + 1; - else if (middle->value > hash) - right = middle - 1; - - if (left>right) - return left->index; + left= middle + 1; + else + right= middle; } + if (right == end) + right= begin; + return right->index; } - break; 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; } - WATCHPOINT_ASSERT(0); /* We should never reach here */ - return 0; + /* NOTREACHED */ } /* @@ -169,10 +171,33 @@ uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_ if (ptr->number_of_hosts == 1) return 0; - hash = generate_hash(ptr, key, key_length); + if (ptr->flags & MEM_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 + { + hash= generate_hash(ptr, key, key_length); + } WATCHPOINT_ASSERT(hash); + if (memcached_behavior_get(ptr, MEMCACHED_BEHAVIOR_AUTO_EJECT_HOSTS) && ptr->next_distribution_rebuild) { + struct timeval now; + + if (gettimeofday(&now, NULL) == 0 && + now.tv_sec > ptr->next_distribution_rebuild) + run_distribution(ptr); + } + return dispatch_host(ptr, hash); } @@ -181,9 +206,10 @@ static uint32_t internal_generate_hash(const char *key, size_t key_length) 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); } @@ -191,7 +217,7 @@ static uint32_t internal_generate_hash(const char *key, size_t key_length) value ^= (value >> 11); value += (value << 15); - return value == 0 ? 1 : value; + return value == 0 ? 1 : (uint32_t) value; } static uint32_t internal_generate_md5(const char *key, size_t key_length)