X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=libmemcached%2Fhash.c;h=e5f87a7564e9a8cd958890d28aa5d2f1afd2b80f;hb=259ed7e68a0de0887e9aedbe0aa5fdd9404929f9;hp=6ead8d46e38793fb5bfea0606346ee03c95a0cfa;hpb=e7561db4b56f2e78948710a0f360f65f5703a8e6;p=m6w6%2Flibmemcached diff --git a/libmemcached/hash.c b/libmemcached/hash.c index 6ead8d46..e5f87a75 100644 --- a/libmemcached/hash.c +++ b/libmemcached/hash.c @@ -1,141 +1,71 @@ -#include "common.h" +/* vim:expandtab:shiftwidth=2:tabstop=2:smarttab: + * + * Libmemcached library + * + * Copyright (C) 2011 Data Differential, http://datadifferential.com/ + * Copyright (C) 2006-2009 Brian Aker All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * * The names of its contributors may not be used to endorse or + * promote products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + */ + + +#include +#include -/* Defines */ -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(const char *key, size_t key_length); -static uint32_t internal_generate_md5(const 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 */ - uint32_t x= 0; - - switch (hash_algorithm) - { - case MEMCACHED_HASH_DEFAULT: - hash= internal_generate_hash(key, key_length); - break; - case MEMCACHED_HASH_MD5: - hash= internal_generate_md5(key, key_length); - break; - case MEMCACHED_HASH_CRC: - hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff); - if (hash == 0) - hash= 1; - break; - /* FNV hash'es lifted from Dustin Sallings work */ - 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++) - { - temp_hash *= FNV_64_PRIME; - temp_hash ^= (uint64_t)key[x]; - } - hash= (uint32_t)temp_hash; - } - break; - case MEMCACHED_HASH_FNV1A_64: - { - hash= (uint32_t) FNV_64_INIT; - for (x= 0; x < key_length; x++) - { - uint32_t val= (uint32_t)key[x]; - hash ^= val; - hash *= (uint32_t) FNV_64_PRIME; - } - } - break; - case MEMCACHED_HASH_FNV1_32: - { - hash= FNV_32_INIT; - for (x= 0; x < key_length; x++) - { - uint32_t val= (uint32_t)key[x]; - hash *= FNV_32_PRIME; - hash ^= val; - } - } - break; - case MEMCACHED_HASH_FNV1A_32: - { - hash= FNV_32_INIT; - for (x= 0; x < key_length; 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: - { - hash= murmur_hash(key, key_length); - break; - } - case MEMCACHED_HASH_JENKINS: - { - hash= jenkins_hash(key, key_length, 13); - break; - } - case MEMCACHED_HASH_MAX: - default: - { - WATCHPOINT_ASSERT(0); - break; - } - } - - return hash; + return libhashkit_digest(key, key_length, (hashkit_hash_algorithm_t)hash_algorithm); } -uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length) +static inline uint32_t generate_hash(const memcached_st *ptr, const char *key, size_t key_length) { - uint32_t hash= 1; /* Just here to remove compile warning */ - - - WATCHPOINT_ASSERT(memcached_server_count(ptr)); - - if (memcached_server_count(ptr) == 1) - return 0; - - hash= memcached_generate_hash_value(key, key_length, ptr->hash); - WATCHPOINT_ASSERT(hash); - return hash; + return hashkit_digest(&ptr->hashkit, key, key_length); } -static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash) +static uint32_t dispatch_host(const memcached_st *ptr, uint32_t hash) { switch (ptr->distribution) { case MEMCACHED_DISTRIBUTION_CONSISTENT: + case MEMCACHED_DISTRIBUTION_CONSISTENT_WEIGHTED: case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA: case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA_SPY: { - uint32_t num= ptr->continuum_points_counter; + uint32_t num= ptr->ketama.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; + begin= left= ptr->ketama.continuum; + end= right= ptr->ketama.continuum + num; while (left < right) { @@ -153,8 +83,12 @@ static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash) return hash % memcached_server_count(ptr); case MEMCACHED_DISTRIBUTION_RANDOM: return (uint32_t) random() % memcached_server_count(ptr); - case MEMCACHED_DISTRIBUTION_CONSISTENT_MAX: + case MEMCACHED_DISTRIBUTION_VIRTUAL_BUCKET: + { + return memcached_virtual_bucket_get(ptr, hash); + } default: + case MEMCACHED_DISTRIBUTION_CONSISTENT_MAX: WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */ return hash % memcached_server_count(ptr); } @@ -162,13 +96,10 @@ static uint32_t dispatch_host(memcached_st *ptr, uint32_t hash) } /* - One day make this public, and have it return the actual memcached_server_st - to the calling application. + One version is public and will not modify the distribution hash, the other will. */ -uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length) +static inline uint32_t _generate_hash_wrapper(const memcached_st *ptr, const char *key, size_t key_length) { - uint32_t hash= 1; /* Just here to remove compile warning */ - WATCHPOINT_ASSERT(memcached_server_count(ptr)); if (memcached_server_count(ptr) == 1) @@ -176,64 +107,70 @@ uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_ if (ptr->flags.hash_with_prefix_key) { - size_t temp_length= ptr->prefix_key_length + key_length; + size_t temp_length= memcached_array_size(ptr->prefix_key) + 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); + strncpy(temp, memcached_array_string(ptr->prefix_key), memcached_array_size(ptr->prefix_key)); + strncpy(temp + memcached_array_size(ptr->prefix_key), key, key_length); + + return generate_hash(ptr, temp, temp_length); } else { - hash= generate_hash(ptr, key, key_length); + return generate_hash(ptr, key, key_length); } +} - WATCHPOINT_ASSERT(hash); - - if (memcached_behavior_get(ptr, MEMCACHED_BEHAVIOR_AUTO_EJECT_HOSTS) && ptr->next_distribution_rebuild) +static inline void _regen_for_auto_eject(memcached_st *ptr) +{ + if (_is_auto_eject_host(ptr) && ptr->ketama.next_distribution_rebuild) { struct timeval now; if (gettimeofday(&now, NULL) == 0 && - now.tv_sec > ptr->next_distribution_rebuild) + now.tv_sec > ptr->ketama.next_distribution_rebuild) { run_distribution(ptr); } } +} - return dispatch_host(ptr, hash); +void memcached_autoeject(memcached_st *ptr) +{ + _regen_for_auto_eject(ptr); } -static uint32_t internal_generate_hash(const char *key, size_t key_length) +uint32_t memcached_generate_hash_with_redistribution(memcached_st *ptr, const char *key, size_t key_length) { - const char *ptr= key; - uint32_t value= 0; + uint32_t hash= _generate_hash_wrapper(ptr, key, key_length); - while (key_length--) - { - uint32_t val= (uint32_t) *ptr++; - value += val; - value += (value << 10); - value ^= (value >> 6); - } - value += (value << 3); - value ^= (value >> 11); - value += (value << 15); + _regen_for_auto_eject(ptr); - return value == 0 ? 1 : (uint32_t) value; + return dispatch_host(ptr, hash); } -static uint32_t internal_generate_md5(const char *key, size_t key_length) +uint32_t memcached_generate_hash(const memcached_st *ptr, const char *key, size_t key_length) { - unsigned char results[16]; + return dispatch_host(ptr, _generate_hash_wrapper(ptr, key, key_length)); +} - md5_signature((unsigned char*)key, (unsigned int)key_length, results); +const hashkit_st *memcached_get_hashkit(const memcached_st *ptr) +{ + return &ptr->hashkit; +} + +memcached_return_t memcached_set_hashkit(memcached_st *self, hashkit_st *hashk) +{ + hashkit_free(&self->hashkit); + hashkit_clone(&self->hashkit, hashk); - return ((uint32_t) (results[3] & 0xFF) << 24) - | ((uint32_t) (results[2] & 0xFF) << 16) - | ((uint32_t) (results[1] & 0xFF) << 8) - | (results[0] & 0xFF); + return MEMCACHED_SUCCESS; +} + +const char * libmemcached_string_hash(memcached_hash_t type) +{ + return libhashkit_string_hash((hashkit_hash_algorithm_t)type); }