Merge Jean-Charles
[m6w6/libmemcached] / libhashkit / hashkit.c
1 /* HashKit
2 * Copyright (C) 2006-2009 Brian Aker
3 * All rights reserved.
4 *
5 * Use and distribution licensed under the BSD license. See
6 * the COPYING file in the parent directory for full text.
7 */
8
9 #include "common.h"
10
11 inline static bool _is_allocated(const hashkit_st *hashk)
12 {
13 return hashk->options.is_allocated == true;
14 }
15
16 inline static bool _is_initialized(const hashkit_st *hashk)
17 {
18 return hashk->options.is_initialized == true;
19 }
20
21 /**
22 @note We make no assumptions that "hashk" has been, or not been allocated from heap/stack. We just know we didn't do it.
23 */
24 hashkit_st *hashkit_create(hashkit_st *hashk)
25 {
26 if (hashk == NULL)
27 {
28 hashk= (hashkit_st *)malloc(sizeof(hashkit_st));
29 if (hashk == NULL)
30 {
31 return NULL;
32 }
33
34 hashk->options.is_allocated= true;
35 }
36 else
37 {
38 hashk->options.is_allocated= false;
39 }
40
41 hashk->options.is_initialized= true;
42
43 hashk->distribution= HASHKIT_DISTRIBUTION_MODULA;
44 hashk->continuum_count= 0;
45 hashk->continuum_points_count= 0;
46 hashk->list_size= 0;
47 hashk->context_size= 0;
48 hashk->continuum= NULL;
49 hashk->hash_fn= NULL;
50 hashk->active_fn= NULL;
51 hashk->continuum_hash_fn= NULL;
52 hashk->continuum_key_fn= NULL;
53 hashk->sort_fn= NULL;
54 hashk->weight_fn= NULL;
55 hashk->list= NULL;
56
57 return hashk;
58 }
59
60
61 void hashkit_free(hashkit_st *hashk)
62 {
63 assert(_is_initialized(hashk) == true);
64
65 if (hashk->continuum != NULL)
66 {
67 free(hashk->continuum);
68 }
69
70 /**
71 We don't know if hashk is pointing to something else,
72 so we go on and set is_initialized.
73 */
74 hashk->options.is_initialized= false;
75
76 if (_is_allocated(hashk))
77 {
78 free(hashk);
79 }
80 }
81
82 /**
83 @note We do assume source is valid. If source does not exist, we allocate.
84 */
85 hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *source)
86 {
87 hashkit_st *new_clone;
88
89 if (source == NULL)
90 {
91 return hashkit_create(destination);
92 }
93 else
94 {
95 assert(_is_initialized(source) == true);
96 }
97
98 /* new_clone will be a pointer to destination */
99 new_clone= hashkit_create(destination);
100 assert((destination ? ((_is_allocated(new_clone) == false)) : (_is_allocated(new_clone) == true)));
101
102 // Should only happen on allocation failure.
103 if (new_clone == NULL)
104 {
105 return NULL;
106 }
107
108 // For the moment we will not clone this.
109 new_clone->continuum= NULL;
110
111 new_clone->distribution= source->distribution;
112 new_clone->continuum_count= source->continuum_count;
113 new_clone->continuum_points_count= source->continuum_points_count;
114 new_clone->list_size= source->list_size;
115 new_clone->context_size= source->context_size;
116
117
118 new_clone->hash_fn= source->hash_fn;
119 new_clone->active_fn= source->active_fn;
120 new_clone->continuum_hash_fn= source->continuum_hash_fn;
121 new_clone->continuum_key_fn= source->continuum_key_fn;
122 new_clone->sort_fn= source->sort_fn;
123 new_clone->weight_fn= source->weight_fn;
124 new_clone->list= source->list;
125
126 return new_clone;
127 }
128
129
130 #if 0
131 void hashkit_set_list(hashkit_st *hashkit, void *list, size_t list_size, size_t context_size)
132 {
133 hashkit->list= list;
134 hashkit->list_size= list_size;
135 hashkit->context_size= context_size;
136 }
137
138
139 uint32_t hashkit_value(hashkit_st *hashkit, const char *key, size_t key_length)
140 {
141 if (hashkit->hash_fn == NULL)
142 return hashkit_default(key, key_length);
143
144 return hashkit->hash_fn(key, key_length);
145 }
146
147
148 uint32_t hashkit_index(hashkit_st *hashkit, uint32_t hash_value)
149 {
150 if (hashkit->list_size == 1)
151 return 0;
152
153 switch (hashkit->distribution)
154 {
155 case HASHKIT_DISTRIBUTION_MODULA:
156 return hash_value % (uint32_t)hashkit->list_size;
157
158 case HASHKIT_DISTRIBUTION_RANDOM:
159 return (uint32_t)random() % (uint32_t)hashkit->list_size;
160
161 case HASHKIT_DISTRIBUTION_KETAMA:
162 {
163 hashkit_continuum_point_st *begin, *end, *left, *right, *middle;
164 begin= left= hashkit->continuum;
165 end= right= hashkit->continuum + hashkit->continuum_points_count;
166
167 while (left < right)
168 {
169 middle= left + (right - left) / 2;
170 if (middle->value < hash_value)
171 left= middle + 1;
172 else
173 right= middle;
174 }
175 if (right == end)
176 right= begin;
177 return right->index;
178 }
179
180 case HASHKIT_DISTRIBUTION_MAX:
181 default:
182 /* We have added a distribution without extending the logic */
183 return hash_value % (uint32_t)hashkit->list_size;
184 }
185
186 /* NOTREACHED */
187 }
188
189
190 int hashkit_run_distribution(hashkit_st *hashkit)
191 {
192 switch (hashkit->distribution)
193 {
194 case HASHKIT_DISTRIBUTION_MODULA:
195 if (hashkit->sort_fn != NULL && hashkit->list_size > 1)
196 hashkit->sort_fn(hashkit->list, hashkit->list_size);
197 break;
198 case HASHKIT_DISTRIBUTION_RANDOM:
199 break;
200 case HASHKIT_DISTRIBUTION_KETAMA:
201 return update_continuum(hashkit);
202 case HASHKIT_DISTRIBUTION_MAX:
203 default:
204 /* We have added a distribution without extending the logic */
205 break;
206 }
207
208 return 0;
209 }
210 #endif
211
212
213 uint32_t hashkit_generate_value(const char *key, size_t key_length, hashkit_hash_algorithm_t hash_algorithm)
214 {
215 switch (hash_algorithm)
216 {
217 case HASHKIT_HASH_DEFAULT:
218 return hashkit_default(key, key_length);
219 case HASHKIT_HASH_MD5:
220 return hashkit_md5(key, key_length);
221 case HASHKIT_HASH_CRC:
222 return hashkit_crc32(key, key_length);
223 case HASHKIT_HASH_FNV1_64:
224 return hashkit_fnv1_64(key, key_length);
225 case HASHKIT_HASH_FNV1A_64:
226 return hashkit_fnv1a_64(key, key_length);
227 case HASHKIT_HASH_FNV1_32:
228 return hashkit_fnv1_32(key, key_length);
229 case HASHKIT_HASH_FNV1A_32:
230 return hashkit_fnv1a_32(key, key_length);
231 case HASHKIT_HASH_HSIEH:
232 #ifdef HAVE_HSIEH_HASH
233 return hashkit_hsieh(key, key_length);
234 #else
235 return 1;
236 #endif
237 case HASHKIT_HASH_MURMUR:
238 return hashkit_murmur(key, key_length);
239 case HASHKIT_HASH_JENKINS:
240 return hashkit_jenkins(key, key_length);
241 case HASHKIT_HASH_MAX:
242 default:
243 #ifdef HAVE_DEBUG
244 fprintf(stderr, "hashkit_hash_t was extended but hashkit_generate_value was not updated\n");
245 fflush(stderr);
246 assert(0);
247 #endif
248 break;
249 }
250
251 return 1;
252 }