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