git.m6w6.name Git - awesomized/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 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 unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length)
  16 {
  17   uint32_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       uint64_t temp_hash;
  40
  41       temp_hash= FNV_64_INIT;
  42       for (x= 0; x < key_length; x++)
  43       {
  44         temp_hash *= FNV_64_PRIME;
  45         temp_hash ^= key[x];
  46       }
  47       hash= (uint32_t)temp_hash;
  48     }
  49     break;
  50   case MEMCACHED_HASH_FNV1A_64:
  51     {
  52       hash= FNV_64_INIT;
  53       for (x= 0; x < key_length; x++)
  54       {
  55         hash ^= key[x];
  56         hash *= FNV_64_PRIME;
  57       }
  58     }
  59     break;
  60   case MEMCACHED_HASH_FNV1_32:
  61     {
  62       hash= FNV_32_INIT;
  63       for (x= 0; x < key_length; x++)
  64       {
  65         hash *= FNV_32_PRIME;
  66         hash ^= key[x];
  67       }
  68     }
  69     break;
  70   case MEMCACHED_HASH_FNV1A_32:
  71     {
  72       hash= FNV_32_INIT;
  73       for (x= 0; x < key_length; x++)
  74       {
  75         hash ^= key[x];
  76         hash *= FNV_32_PRIME;
  77       }
  78     }
  79     break;
  80     case MEMCACHED_HASH_KETAMA:
  81     {
  82       hash= internal_generate_ketama_md5(key, key_length);
  83       break;
  84     }
  85     case MEMCACHED_HASH_HSIEH:
  86     {
  87       hash= hsieh_hash(key, key_length);
  88       break;
  89     }
  90   }
  91
  92   WATCHPOINT_ASSERT(hash);
  93
  94   if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA)
  95   {
  96     return hash % ptr->number_of_hosts;
  97   }
  98   else
  99   {
 100     unsigned int server_key;
 101
 102     server_key= hash % MEMCACHED_WHEEL_SIZE;
 103
 104     return ptr->wheel[server_key];
 105   }
 106 }
 107
 108 static uint32_t internal_generate_hash(char *key, size_t key_length)
 109 {
 110   char *ptr= key;
 111   uint32_t value= 0;
 112
 113   while (--key_length)
 114   {
 115     value += *ptr++;
 116     value += (value << 10);
 117     value ^= (value >> 6);
 118   }
 119   value += (value << 3);
 120   value ^= (value >> 11);
 121   value += (value << 15);
 122
 123   return value == 0 ? 1 : value;
 124 }
 125
 126 static uint32_t internal_generate_md5(char *key, size_t key_length)
 127 {
 128   unsigned char results[16];
 129
 130   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 131
 132   return (uint32_t)(( results[3] << 24 )
 133                     | ( results[2] << 16 )
 134                     | ( results[1] <<  8 )
 135                     |   results[0] );
 136 }
 137
 138 static uint32_t internal_generate_ketama_md5(char *key, size_t key_length)
 139 {
 140   unsigned char results[16];
 141
 142   md5_signature((unsigned char*)key, (unsigned int)key_length, results);
 143
 144   return ((uint32_t) (results[3] & 0xFF) << 24)
 145     | ((uint32_t) (results[2] & 0xFF) << 16)
 146     | ((uint32_t) (results[1] & 0xFF) << 8)
 147     | (results[0] & 0xFF);
 148 }