X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=libmemcached%2Fmemcached_hash.c;h=de0ce1dcab98ceecf4e4d8a23832353fc7e3ea6e;hb=d455dd963105dc3ccc120887215f66dec8f55377;hp=4cb442cbd78fd7dedeb3675715e248a9576a3781;hpb=83d63a1f916b073f8cf44cf91b6c0b3d118dabe5;p=awesomized%2Flibmemcached diff --git a/libmemcached/memcached_hash.c b/libmemcached/memcached_hash.c index 4cb442cb..de0ce1dc 100644 --- a/libmemcached/memcached_hash.c +++ b/libmemcached/memcached_hash.c @@ -8,22 +8,15 @@ 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); -uint32_t generate_hash(memcached_st *ptr, char *key, size_t key_length) +uint32_t 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; - - WATCHPOINT_ASSERT(ptr->number_of_hosts); - - if (ptr->number_of_hosts == 1) - return 0; - - switch (ptr->hash) + switch (hash_algorithm) { case MEMCACHED_HASH_DEFAULT: hash= internal_generate_hash(key, key_length); @@ -81,11 +74,6 @@ uint32_t generate_hash(memcached_st *ptr, char *key, size_t key_length) } } break; - case MEMCACHED_HASH_KETAMA: - { - hash= internal_generate_ketama_md5(key, key_length); - break; - } case MEMCACHED_HASH_HSIEH: { hash= hsieh_hash(key, key_length); @@ -96,64 +84,62 @@ uint32_t generate_hash(memcached_st *ptr, char *key, size_t key_length) hash= murmur_hash(key, key_length); break; } + case MEMCACHED_HASH_JENKINS: + { + hash=jenkins_hash(key, key_length, 13); + 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= 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) { case MEMCACHED_DISTRIBUTION_CONSISTENT: case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA: { - int num= ptr->number_of_hosts * MEMCACHED_POINTS_PER_SERVER; + 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 - 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_CONSISTENT_WHEEL: - { - unsigned int server_key; - - server_key= hash % MEMCACHED_STRIDE * ptr->wheel_count; - - return ptr->wheel[server_key]; - } case MEMCACHED_DISTRIBUTION_MODULA: return hash % ptr->number_of_hosts; + case MEMCACHED_DISTRIBUTION_RANDOM: + return random() % ptr->number_of_hosts; default: WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */ return hash % ptr->number_of_hosts; @@ -163,7 +149,11 @@ unsigned int dispatch_host(memcached_st *ptr, uint32_t hash) return 0; } -unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length) +/* + 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 */ @@ -172,18 +162,31 @@ unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_le if (ptr->number_of_hosts == 1) return 0; - hash = generate_hash(ptr, key, key_length); + if (ptr->flags & MEM_HASH_WITH_PREFIX_KEY) + { + int temp_len= ptr->prefix_key_length + key_length; + char *temp= (char *)malloc(temp_len); + strncpy(temp, ptr->prefix_key, ptr->prefix_key_length); + strncpy(temp + ptr->prefix_key_length, key, key_length); + hash= generate_hash(ptr, temp, temp_len); + free(temp); + } + else + { + hash= generate_hash(ptr, key, key_length); + } WATCHPOINT_ASSERT(hash); + 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++; value += (value << 10); @@ -196,19 +199,7 @@ static uint32_t internal_generate_hash(char *key, size_t key_length) 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); - - return (uint32_t)(( results[3] << 24 ) - | ( results[2] << 16 ) - | ( results[1] << 8 ) - | results[0] ); -} - -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];