/
hash.c
138 lines (115 loc) · 3.52 KB
/
hash.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/* LibMemcached
* Copyright (C) 2006-2010 Brian Aker
* All rights reserved.
*
* Use and distribution licensed under the BSD license. See
* the COPYING file in the parent directory for full text.
*
* Summary:
*
*/
#include "common.h"
uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash_t hash_algorithm)
{
return libhashkit_digest(key, key_length, (hashkit_hash_algorithm_t)hash_algorithm);
}
static inline uint32_t generate_hash(const memcached_st *ptr, const char *key, size_t key_length)
{
return hashkit_digest(&ptr->hashkit, key, key_length);
}
static uint32_t dispatch_host(const memcached_st *ptr, uint32_t hash)
{
switch (ptr->distribution)
{
case MEMCACHED_DISTRIBUTION_CONSISTENT:
case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA:
case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA_SPY:
{
uint32_t num= ptr->continuum_points_counter;
WATCHPOINT_ASSERT(ptr->continuum);
hash= hash;
memcached_continuum_item_st *begin, *end, *left, *right, *middle;
begin= left= ptr->continuum;
end= right= ptr->continuum + num;
while (left < right)
{
middle= left + (right - left) / 2;
if (middle->value < hash)
left= middle + 1;
else
right= middle;
}
if (right == end)
right= begin;
return right->index;
}
case MEMCACHED_DISTRIBUTION_MODULA:
return hash % memcached_server_count(ptr);
case MEMCACHED_DISTRIBUTION_RANDOM:
return (uint32_t) random() % memcached_server_count(ptr);
case MEMCACHED_DISTRIBUTION_CONSISTENT_MAX:
default:
WATCHPOINT_ASSERT(0); /* We have added a distribution without extending the logic */
return hash % memcached_server_count(ptr);
}
/* NOTREACHED */
}
/*
One version is public and will not modify the distribution hash, the other will.
*/
static inline uint32_t _generate_hash_wrapper(const memcached_st *ptr, const char *key, size_t key_length)
{
WATCHPOINT_ASSERT(memcached_server_count(ptr));
if (memcached_server_count(ptr) == 1)
return 0;
if (ptr->flags.hash_with_prefix_key)
{
size_t temp_length= ptr->prefix_key_length + key_length;
char temp[temp_length];
if (temp_length > MEMCACHED_MAX_KEY -1)
return 0;
strncpy(temp, ptr->prefix_key, ptr->prefix_key_length);
strncpy(temp + ptr->prefix_key_length, key, key_length);
return generate_hash(ptr, temp, temp_length);
}
else
{
return generate_hash(ptr, key, key_length);
}
}
static inline void _regen_for_auto_eject(memcached_st *ptr)
{
if (_is_auto_eject_host(ptr) && ptr->next_distribution_rebuild)
{
struct timeval now;
if (gettimeofday(&now, NULL) == 0 &&
now.tv_sec > ptr->next_distribution_rebuild)
{
run_distribution(ptr);
}
}
}
void memcached_autoeject(memcached_st *ptr)
{
_regen_for_auto_eject(ptr);
}
uint32_t memcached_generate_hash_with_redistribution(memcached_st *ptr, const char *key, size_t key_length)
{
uint32_t hash= _generate_hash_wrapper(ptr, key, key_length);
_regen_for_auto_eject(ptr);
return dispatch_host(ptr, hash);
}
uint32_t memcached_generate_hash(const memcached_st *ptr, const char *key, size_t key_length)
{
return dispatch_host(ptr, _generate_hash_wrapper(ptr, key, key_length));
}
const hashkit_st *memcached_get_hashkit(const memcached_st *ptr)
{
return &ptr->hashkit;
}
memcached_return_t memcached_set_hashkit(memcached_st *self, hashkit_st *hashk)
{
hashkit_free(&self->hashkit);
hashkit_clone(&self->hashkit, hashk);
return MEMCACHED_SUCCESS;
}