← Back to branch summary

~brianaker/libmemcached/embedded

« back to all changes in this revision

Viewing changes to libmemcached/memcached_hash.c

  • Committer: brian@gir-2.local
  • Date: 2008-03-10 15:04:41 UTC
  • mto: (317.6.1)
  • mto: This revision was merged to the branch mainline in revision 321.
  • Revision ID: brian@gir-2.local-20080310150441-jyhbjx6bwo46f6tg
Huge refactoring of directory structure.

Show diffs side-by-side

added added

removed removed

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