← Back to branch summary

~mordred/libmemcached/fix-weird-link

« back to all changes in this revision

Viewing changes to lib/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:
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
 
  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
 
}