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