git.m6w6.name Git - m6w6/libmemcached/blob - libmemcached/memcached_hash.c

   1 #include "common.h"
   2
   3 /* Defines */
   4 static uint64_t FNV_64_INIT= 0xcbf29ce484222325LL;
   5 static uint64_t FNV_64_PRIME= 0x100000001b3LL;
   6
   7 static uint32_t FNV_32_INIT= 2166136261UL;
   8 static uint32_t FNV_32_PRIME= 16777619;
   9
  10 /* Prototypes */
  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);
  14
  15 uint32_t generate_hash(memcached_st *ptr, char *key, size_t key_length)
  16 {
  17   uint32_t hash= 1; /* Just here to remove compile warning */
  18   uint32_t x= 0;
  19
  20
  21   WATCHPOINT_ASSERT(ptr->number_of_hosts);
  22
  23   if (ptr->number_of_hosts == 1)
  24     return 0;
  25
  26   switch (ptr->hash)
  27   {
  28   case MEMCACHED_HASH_DEFAULT:
  29     hash= internal_generate_hash(key, key_length);
  30     break;
  31   case MEMCACHED_HASH_MD5:
  32     hash= internal_generate_md5(key, key_length);
  33     break;
  34   case MEMCACHED_HASH_CRC:
  35     hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff);
  36     if (hash == 0)
  37       hash= 1;
  38     break;
  39     /* FNV hash'es lifted from Dustin Sallings work */
  40   case MEMCACHED_HASH_FNV1_64:
  41     {
  42       /* Thanks to pierre@demartines.com for the pointer */
  43       uint64_t temp_hash;
  44
  45       temp_hash= FNV_64_INIT;
  46       for (x= 0; x < key_length; x++)
  47       {
  48         temp_hash *= FNV_64_PRIME;
  49         temp_hash ^= key[x];
  50       }
  51       hash= (uint32_t)temp_hash;
  52     }
  53     break;
  54   case MEMCACHED_HASH_FNV1A_64:
  55     {
  56       hash= FNV_64_INIT;
  57       for (x= 0; x < key_length; x++)
  58       {
  59         hash ^= key[x];
  60         hash *= FNV_64_PRIME;
  61       }
  62     }
  63     break;
  64   case MEMCACHED_HASH_FNV1_32:
  65     {
  66       hash= FNV_32_INIT;
  67       for (x= 0; x < key_length; x++)
  68       {
  69         hash *= FNV_32_PRIME;
  70         hash ^= key[x];
  71       }
  72     }
  73     break;
  74   case MEMCACHED_HASH_FNV1A_32:
  75     {
  76       hash= FNV_32_INIT;
  77       for (x= 0; x < key_length; x++)
  78       {
  79         hash ^= key[x];
  80         hash *= FNV_32_PRIME;
  81       }
  82     }
  83     break;
  84     case MEMCACHED_HASH_KETAMA:
  85     {
  86       hash= internal_generate_ketama_md5(key, key_length);
  87       break;
  88     }
  89     case MEMCACHED_HASH_HSIEH:
  90     {
  91       hash= hsieh_hash(key, key_length);
  92       break;
  93     }
  94     case MEMCACHED_HASH_MURMUR:
  95     {
  96       hash= murmur_hash(key, key_length);
  97       break;
  98     }
  99   }
 100
 101   WATCHPOINT_ASSERT(hash);
 102   return hash;
 103 }
 104
 105 unsigned int dispatch_host(memcached_st *ptr, uint32_t hash)
 106 {
 107   switch (ptr->distribution)
 108   {
 109   case MEMCACHED_DISTRIBUTION_CONSISTENT:
 110   case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA:
 111     {
 112       int num= ptr->number_of_hosts * MEMCACHED_POINTS_PER_SERVER;
 113       WATCHPOINT_ASSERT(ptr->continuum);
 114
 115       hash= hash;
 116       memcached_continuum_item_st *begin, *end, *left, *right, *middle;
 117       begin= left= ptr->continuum;
 118       end= right= ptr->continuum + (num - 1);
 119
 120       while (1)
 121       {
 122         memcached_continuum_item_st *rmiddle;
 123
 124         middle = left + (right - left) / 2;
 125
 126         if (middle==end)
 127           return begin->index;
 128
 129         if (middle==begin)
 130           return end->index;
 131
 132         rmiddle = middle+1;
 133
 134         if (hash<rmiddle->value && hash>=middle->value)
 135           return middle->index;
 136
 137         if (middle->value < hash)
 138           left = middle + 1;
 139         else if (middle->value > hash)
 140           right = middle - 1;
 141
 142         if (left>right)
 143           return left->index;
 144       }
 145     }
 146     break;
 147   case MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL:
 148     {
 149       unsigned int server_key;
 150
 151       server_key= hash % MEMCACHED_WHEEL_SIZE;
 152
 153       return ptr->wheel[server_key];
 154     }
 155   case MEMCACHED_DISTRIBUTION_MODULA:
 156     return hash % ptr->number_of_hosts;
 157   default:
 158     WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
 159     return hash % ptr->number_of_hosts;
 160   }
 161
 162   if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA)
 163   {
 164     return hash % ptr->number_of_hosts;
 165   }
 166   else if (ptr->distribution == MEMCACHED_DISTRIBUTION_CONSISTENT)
 167   {
 168     unsigned int server_key;
 169
 170     server_key= hash % MEMCACHED_WHEEL_SIZE;
 171
 172     return ptr->wheel[server_key];
 173   }
 174   else if (ptr->distribution == MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA)
 175   {
 176     int num = ptr->number_of_hosts * MEMCACHED_POINTS_PER_SERVER;
 177
 178     hash = hash;
 179     memcached_continuum_item_st *begin, *end, *left, *right, *middle;
 180     begin = left = ptr->continuum;
 181     end = right = ptr->continuum + (num - 1);
 182     while(1)
 183     {
 184       middle = left + (right - left) / 2;
 185       if(middle==end)
 186       {
 187         return begin->index;
 188       }
 189       if(middle==begin)
 190       {
 191         return end->index;
 192       }
 193       memcached_continuum_item_st *rmiddle = middle+1;
 194       if(hash<rmiddle->value && hash>=middle->value)
 195         return middle->index;
 196
 197       if(middle->value < hash) {
 198         left = middle + 1;
 199       }else if(middle->value > hash) {
 200         right = middle - 1;
 201       }
 202
 203       if (left>right)
 204         return left->index;
 205     }
 206   }
 207   else
 208   {
 209     WATCHPOINT_ASSERT(0);
 210   }
 211 }
 212
 213 unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length)
 214 {
 215   uint32_t hash= 1; /* Just here to remove compile warning */
 216
 217   WATCHPOINT_ASSERT(ptr->number_of_hosts);
 218
 219   if (ptr->number_of_hosts == 1)
 220     return 0;
 221
 222   hash = generate_hash(ptr, key, key_length);
 223
 224   WATCHPOINT_ASSERT(hash);
 225   return dispatch_host(ptr, hash);
 226 }
 227
 228 static uint32_t internal_generate_hash(char *key, size_t key_length)
 229 {
 230   char *ptr= key;
 231   uint32_t value= 0;
 232
 233   while (--key_length)
 234   {
 235     value += *ptr++;
 236     value += (value << 10);
 237     value ^= (value >> 6);
 238   }
 239   value += (value << 3);
 240   value ^= (value >> 11);
 241   value += (value << 15);
 242
 243   return value == 0 ? 1 : value;
 244 }
 245
 246 static uint32_t internal_generate_md5(char *key, size_t key_length)
 247 {
 248   unsigned char results[16];
 249
 250   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 251
 252   return (uint32_t)(( results[3] << 24 )
 253                     | ( results[2] << 16 )
 254                     | ( results[1] <<  8 )
 255                     |   results[0] );
 256 }
 257
 258 static uint32_t internal_generate_ketama_md5(char *key, size_t key_length)
 259 {
 260   unsigned char results[16];
 261
 262   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 263
 264   return ((uint32_t) (results[3] & 0xFF) << 24)
 265     | ((uint32_t) (results[2] & 0xFF) << 16)
 266     | ((uint32_t) (results[1] & 0xFF) << 8)
 267     | (results[0] & 0xFF);
 268 }