git.m6w6.name Git - awesomized/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(const char *key, size_t key_length);
  12 static uint32_t internal_generate_md5(const char *key, size_t key_length);
  13
  14 uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length)
  15 {
  16   uint32_t hash= 1; /* Just here to remove compile warning */
  17   uint32_t x= 0;
  18
  19
  20   WATCHPOINT_ASSERT(ptr->number_of_hosts);
  21
  22   if (ptr->number_of_hosts == 1)
  23     return 0;
  24
  25   switch (ptr->hash)
  26   {
  27   case MEMCACHED_HASH_DEFAULT:
  28     hash= internal_generate_hash(key, key_length);
  29     break;
  30   case MEMCACHED_HASH_MD5:
  31     hash= internal_generate_md5(key, key_length);
  32     break;
  33   case MEMCACHED_HASH_CRC:
  34     hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff);
  35     if (hash == 0)
  36       hash= 1;
  37     break;
  38     /* FNV hash'es lifted from Dustin Sallings work */
  39   case MEMCACHED_HASH_FNV1_64:
  40     {
  41       /* Thanks to pierre@demartines.com for the pointer */
  42       uint64_t temp_hash;
  43
  44       temp_hash= FNV_64_INIT;
  45       for (x= 0; x < key_length; x++)
  46       {
  47         temp_hash *= FNV_64_PRIME;
  48         temp_hash ^= key[x];
  49       }
  50       hash= (uint32_t)temp_hash;
  51     }
  52     break;
  53   case MEMCACHED_HASH_FNV1A_64:
  54     {
  55       hash= FNV_64_INIT;
  56       for (x= 0; x < key_length; x++)
  57       {
  58         hash ^= key[x];
  59         hash *= FNV_64_PRIME;
  60       }
  61     }
  62     break;
  63   case MEMCACHED_HASH_FNV1_32:
  64     {
  65       hash= FNV_32_INIT;
  66       for (x= 0; x < key_length; x++)
  67       {
  68         hash *= FNV_32_PRIME;
  69         hash ^= key[x];
  70       }
  71     }
  72     break;
  73   case MEMCACHED_HASH_FNV1A_32:
  74     {
  75       hash= FNV_32_INIT;
  76       for (x= 0; x < key_length; x++)
  77       {
  78         hash ^= key[x];
  79         hash *= FNV_32_PRIME;
  80       }
  81     }
  82     break;
  83     case MEMCACHED_HASH_HSIEH:
  84     {
  85       hash= hsieh_hash(key, key_length);
  86       break;
  87     }
  88     case MEMCACHED_HASH_MURMUR:
  89     {
  90       hash= murmur_hash(key, key_length);
  91       break;
  92     }
  93   }
  94
  95   WATCHPOINT_ASSERT(hash);
  96   return hash;
  97 }
  98
  99 unsigned int dispatch_host(memcached_st *ptr, uint32_t hash)
 100 {
 101   switch (ptr->distribution)
 102   {
 103   case MEMCACHED_DISTRIBUTION_CONSISTENT:
 104   case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA:
 105     {
 106       uint32_t num= ptr->number_of_hosts * MEMCACHED_POINTS_PER_SERVER;
 107       WATCHPOINT_ASSERT(ptr->continuum);
 108
 109       hash= hash;
 110       memcached_continuum_item_st *begin, *end, *left, *right, *middle;
 111       begin= left= ptr->continuum;
 112       end= right= ptr->continuum + (num - 1);
 113
 114       while (1)
 115       {
 116         memcached_continuum_item_st *rmiddle;
 117
 118         middle = left + (right - left) / 2;
 119
 120         if (middle==end)
 121           return begin->index;
 122
 123         if (middle==begin)
 124           return end->index;
 125
 126         rmiddle = middle+1;
 127
 128         if (hash<rmiddle->value && hash>=middle->value)
 129           return middle->index;
 130
 131         if (middle->value < hash)
 132           left = middle + 1;
 133         else if (middle->value > hash)
 134           right = middle - 1;
 135
 136         if (left>right)
 137           return left->index;
 138       }
 139     }
 140     break;
 141   case MEMCACHED_DISTRIBUTION_MODULA:
 142     return hash % ptr->number_of_hosts;
 143   default:
 144     WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
 145     return hash % ptr->number_of_hosts;
 146   }
 147
 148   WATCHPOINT_ASSERT(0); /* We should never reach here */
 149   return 0;
 150 }
 151
 152 /*
 153   One day make this public, and have it return the actual memcached_server_st
 154   to the calling application.
 155 */
 156 uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_length)
 157 {
 158   uint32_t hash= 1; /* Just here to remove compile warning */
 159
 160   WATCHPOINT_ASSERT(ptr->number_of_hosts);
 161
 162   if (ptr->number_of_hosts == 1)
 163     return 0;
 164
 165   hash = generate_hash(ptr, key, key_length);
 166
 167   WATCHPOINT_ASSERT(hash);
 168   return dispatch_host(ptr, hash);
 169 }
 170
 171 static uint32_t internal_generate_hash(const char *key, size_t key_length)
 172 {
 173   const char *ptr= key;
 174   uint32_t value= 0;
 175
 176   while (--key_length)
 177   {
 178     value += *ptr++;
 179     value += (value << 10);
 180     value ^= (value >> 6);
 181   }
 182   value += (value << 3);
 183   value ^= (value >> 11);
 184   value += (value << 15);
 185
 186   return value == 0 ? 1 : value;
 187 }
 188
 189 static uint32_t internal_generate_md5(const char *key, size_t key_length)
 190 {
 191   unsigned char results[16];
 192
 193   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 194
 195   return ((uint32_t) (results[3] & 0xFF) << 24)
 196     | ((uint32_t) (results[2] & 0xFF) << 16)
 197     | ((uint32_t) (results[1] & 0xFF) << 8)
 198     | (results[0] & 0xFF);
 199 }