git.m6w6.name Git - m6w6/libmemcached/blob - lib/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 uint64_t internal_generate_hash(char *key, size_t key_length);
  12 static uint64_t internal_generate_md5(char *key, size_t key_length);
  13 static uint64_t internal_generate_ketama_md5(char *key, size_t key_length);
  14
  15 unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length)
  16 {
  17   uint64_t hash= 1; /* Just here to remove compile warning */
  18   unsigned int x;
  19
  20   WATCHPOINT_ASSERT(ptr->number_of_hosts);
  21
  22   switch (ptr->hash)
  23   {
  24   case MEMCACHED_HASH_DEFAULT:
  25     hash= internal_generate_hash(key, key_length);
  26     break;
  27   case MEMCACHED_HASH_MD5:
  28     hash= internal_generate_md5(key, key_length);
  29     break;
  30   case MEMCACHED_HASH_CRC:
  31     hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff);
  32     if (hash == 0)
  33       hash= 1;
  34     break;
  35     /* FNV hash'es lifted from Dustin Sallings work */
  36   case MEMCACHED_HASH_FNV1_64:
  37     {
  38       /* Thanks to pierre@demartines.com for the pointer */
  39       hash= FNV_64_INIT;
  40       for (x= 0; x < key_length; x++)
  41       {
  42         hash *= FNV_64_PRIME;
  43         hash ^= key[x];
  44       }
  45     }
  46     break;
  47   case MEMCACHED_HASH_FNV1A_64:
  48     {
  49       hash= FNV_64_INIT;
  50       for (x= 0; x < key_length; x++)
  51       {
  52         hash ^= key[x];
  53         hash *= FNV_64_PRIME;
  54       }
  55     }
  56     break;
  57   case MEMCACHED_HASH_FNV1_32:
  58     {
  59       hash= FNV_32_INIT;
  60       for (x= 0; x < key_length; x++)
  61       {
  62         hash *= FNV_32_PRIME;
  63         hash ^= key[x];
  64       }
  65     }
  66     break;
  67   case MEMCACHED_HASH_FNV1A_32:
  68     {
  69       hash= FNV_32_INIT;
  70       for (x= 0; x < key_length; x++)
  71       {
  72         hash ^= key[x];
  73         hash *= FNV_32_PRIME;
  74       }
  75     }
  76     break;
  77     case MEMCACHED_HASH_KETAMA:
  78     {
  79       hash= internal_generate_ketama_md5(key, key_length);
  80       break;
  81     }
  82     case MEMCACHED_HASH_HSIEH:
  83     {
  84       hash= hsieh_hash(key, key_length);
  85       break;
  86     }
  87   }
  88
  89   WATCHPOINT_ASSERT(hash);
  90
  91   if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA)
  92   {
  93     return hash % ptr->number_of_hosts;
  94   }
  95   else
  96   {
  97     unsigned int server_key;
  98
  99     server_key= hash % MEMCACHED_WHEEL_SIZE;
 100
 101     return ptr->wheel[server_key];
 102   }
 103 }
 104
 105 static uint64_t internal_generate_hash(char *key, size_t key_length)
 106 {
 107   char *ptr= key;
 108   uint64_t value= 0;
 109
 110   while (--key_length)
 111   {
 112     value += *ptr++;
 113     value += (value << 10);
 114     value ^= (value >> 6);
 115   }
 116   value += (value << 3);
 117   value ^= (value >> 11);
 118   value += (value << 15);
 119
 120   return value == 0 ? 1 : value;
 121 }
 122
 123 static uint64_t internal_generate_md5(char *key, size_t key_length)
 124 {
 125   unsigned char results[16];
 126
 127   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 128
 129   return (uint64_t)(( results[3] << 24 )
 130                     | ( results[2] << 16 )
 131                     | ( results[1] <<  8 )
 132                     |   results[0] );
 133 }
 134
 135 static uint64_t internal_generate_ketama_md5(char *key, size_t key_length)
 136 {
 137   unsigned char results[16];
 138
 139   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 140
 141   return ((uint32_t) (results[3] & 0xFF) << 24)
 142     | ((uint32_t) (results[2] & 0xFF) << 16)
 143     | ((uint32_t) (results[1] & 0xFF) << 8)
 144     | (results[0] & 0xFF);
 145 }