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