1 /**
2 * Copyright (C) 2008 Happy Fish / YuQing
3 *
4 * FastDFS may be copied only under the terms of the GNU General
5 * Public License V3, which may be found in the FastDFS source kit.
6 * Please visit the FastDFS Home Page http://www.fastken.com/ for more detail.
7 **/
8
9 #ifndef _HASH_H_
10 #define _HASH_H_
11
12 #include <sys/types.h>
13 #include <pthread.h>
14 #include "common_define.h"
15
16 #ifdef __cplusplus
17 extern "C" {
18 #endif
19
20 #define CRC32_XINIT 0xFFFFFFFF /* initial value */
21 #define CRC32_XOROT 0xFFFFFFFF /* final xor value */
22
23 typedef int (*HashFunc) (const void *key, const int key_len);
24
25 #ifdef HASH_STORE_HASH_CODE
26 #define HASH_CODE(pHash, hash_data) hash_data->hash_code
27 #else
28 #define HASH_CODE(pHash, hash_data) ((unsigned int)pHash->hash_func( \
29 hash_data->key, hash_data->key_len))
30 #endif
31
32 #define CALC_NODE_MALLOC_BYTES(key_len, value_size) \
33 sizeof(HashData) + key_len + value_size
34
35 #define FREE_HASH_DATA(pHash, hash_data) \
36 pHash->item_count--; \
37 pHash->bytes_used -= CALC_NODE_MALLOC_BYTES(hash_data->key_len, \
38 hash_data->malloc_value_size); \
39 free(hash_data);
40
41
42 typedef struct tagHashData
43 {
44 int key_len;
45 int value_len;
46 int malloc_value_size;
47
48 #ifdef HASH_STORE_HASH_CODE
49 unsigned int hash_code;
50 #endif
51
52 char *value;
53 struct tagHashData *next;
54 char key[0];
55 } HashData;
56
57 typedef int64_t (*ConvertValueFunc)(const HashData *old_data, const int inc,
58 char *new_value, int *new_value_len, void *arg);
59
60 typedef struct tagHashArray
61 {
62 HashData **buckets;
63 HashFunc hash_func;
64 int item_count;
65 unsigned int *capacity;
66 double load_factor;
67 int64_t max_bytes;
68 int64_t bytes_used;
69 bool is_malloc_capacity;
70 bool is_malloc_value;
71 unsigned int lock_count;
72 pthread_mutex_t *locks;
73 } HashArray;
74
75 typedef struct tagHashStat
76 {
77 unsigned int capacity;
78 int item_count;
79 int bucket_used;
80 double bucket_avg_length;
81 int bucket_max_length;
82 } HashStat;
83
84 /**
85 * hash walk function
86 * parameters:
87 * index: item index based 0
88 * data: hash data, including key and value
89 * args: passed by hash_walk function
90 * return 0 for success, != 0 for error
91 */
92 typedef int (*HashWalkFunc)(const int index, const HashData *data, void *args);
93
94 #define hash_init(pHash, hash_func, capacity, load_factor) \
95 hash_init_ex(pHash, hash_func, capacity, load_factor, 0, false)
96
97 #define hash_insert(pHash, key, key_len, value) \
98 hash_insert_ex(pHash, key, key_len, value, 0, true)
99
100 /**
101 * hash init function
102 * parameters:
103 * pHash: the hash table
104 * hash_func: hash function
105 * capacity: init capacity
106 * load_factor: hash load factor (or watermark), >= 0.10 for auto rehash. eg. 0.75
107 * max_bytes: max memory can be used (bytes)
108 * bMallocValue: if need malloc value buffer
109 * return 0 for success, != 0 for error
110 */
111 int hash_init_ex(HashArray *pHash, HashFunc hash_func, \
112 const unsigned int capacity, const double load_factor, \
113 const int64_t max_bytes, const bool bMallocValue);
114
115 /**
116 * set hash locks function
117 * parameters:
118 * lock_count: the lock count
119 * return 0 for success, != 0 for error
120 */
121 int hash_set_locks(HashArray *pHash, const int lock_count);
122
123 /**
124 * convert the value
125 * parameters:
126 * HashData: the old hash data
127 * inc: the increasement value
128 * new_value: return the new value
129 * new_value_len: return the length of the new value
130 * arg: the user data
131 * return the number after increasement
132 */
133 int64_t hash_inc_value(const HashData *old_data, const int inc,
134 char *new_value, int *new_value_len, void *arg);
135
136 #define hash_inc(pHash, key, key_len, inc, value, value_len) \
137 hash_inc_ex(pHash, key, key_len, inc, value, value_len, \
138 hash_inc_value, NULL)
139
140 /**
141 * atomic increase value
142 * parameters:
143 * pHash: the hash table
144 * key: the key to insert
145 * key_len: length of th key
146 * inc: the increasement value
147 * value: return the new value
148 * value_len: return the length of the new value
149 * convert_func: the convert function
150 * arg: the arg to convert function
151 * return 0 for success, != 0 for error (errno)
152 *
153 */
154 int hash_inc_ex(HashArray *pHash, const void *key, const int key_len,
155 const int inc, char *value, int *value_len,
156 ConvertValueFunc convert_func, void *arg);
157
158 /**
159 * hash destroy function
160 * parameters:
161 * pHash: the hash table
162 * return none
163 */
164 void hash_destroy(HashArray *pHash);
165
166 /**
167 * hash insert key
168 * parameters:
169 * pHash: the hash table
170 * key: the key to insert
171 * key_len: length of th key
172 * value: the value
173 * value_len: length of the value
174 * needLock: if need lock
175 * return >= 0 for success, 0 for key already exist (update),
176 * 1 for new key (insert), < 0 for error
177 */
178 int hash_insert_ex(HashArray *pHash, const void *key, const int key_len, \
179 void *value, const int value_len, const bool needLock);
180
181 /**
182 * hash find key
183 * parameters:
184 * pHash: the hash table
185 * key: the key to find
186 * key_len: length of th key
187 * return user data, return NULL when the key not exist
188 */
189 void *hash_find(HashArray *pHash, const void *key, const int key_len);
190
191 /**
192 * hash find key
193 * parameters:
194 * pHash: the hash table
195 * key: the key to find
196 * key_len: length of th key
197 * return hash data, return NULL when the key not exist
198 */
199 HashData *hash_find_ex(HashArray *pHash, const void *key, const int key_len);
200
201 /**
202 * hash find key
203 * parameters:
204 * pHash: the hash table
205 * key: the key to find
206 * return user data, return NULL when the key not exist
207 */
hash_find1(HashArray * pHash,const string_t * key)208 static inline void *hash_find1(HashArray *pHash, const string_t *key)
209 {
210 return hash_find(pHash, key->str, key->len);
211 }
212
213 /**
214 * hash get the value of the key
215 * parameters:
216 * pHash: the hash table
217 * key: the key to find
218 * value: store the value
219 * return 0 for success, != 0 fail (errno)
220 */
221 int hash_find2(HashArray *pHash, const string_t *key, string_t *value);
222
223 /**
224 * hash find key
225 * parameters:
226 * pHash: the hash table
227 * key: the key to find
228 * return hash data, return NULL when the key not exist
229 */
230 HashData *hash_find1_ex(HashArray *pHash, const string_t *key);
231
232 /**
233 * hash get the value of the key
234 * parameters:
235 * pHash: the hash table
236 * key: the key to find
237 * key_len: length of th key
238 * value: store the value
239 * value_len: input for the max size of the value
240 * output for the length fo the value
241 * return 0 for success, != 0 fail (errno)
242 */
243 int hash_get(HashArray *pHash, const void *key, const int key_len,
244 void *value, int *value_len);
245
246
247 /**
248 * hash partial set
249 * parameters:
250 * pHash: the hash table
251 * key: the key to insert
252 * key_len: length of th key
253 * value: the value
254 * offset: the offset of existed value
255 * value_len: length of the value
256 * return 0 for success, != 0 fail (errno)
257 */
258 int hash_partial_set(HashArray *pHash, const void *key, const int key_len,
259 const char *value, const int offset, const int value_len);
260
261 /**
262 * hash delete key
263 * parameters:
264 * pHash: the hash table
265 * key: the key to delete
266 * key_len: length of th key
267 * return 0 for success, != 0 fail (errno)
268 */
269 int hash_delete(HashArray *pHash, const void *key, const int key_len);
270
271 /**
272 * hash walk (iterator)
273 * parameters:
274 * pHash: the hash table
275 * walkFunc: walk (interator) function
276 * args: extra args which will be passed to walkFunc
277 * return 0 for success, != 0 fail (errno)
278 */
279 int hash_walk(HashArray *pHash, HashWalkFunc walkFunc, void *args);
280
281 /**
282 * get hash item count
283 * parameters:
284 * pHash: the hash table
285 * return item count
286 */
287 int hash_count(HashArray *pHash);
288
289 /**
290 * hash best optimize
291 * parameters:
292 * pHash: the hash table
293 * suggest_capacity: suggest init capacity for speed
294 * return >0 for success, < 0 fail (errno)
295 */
296 int hash_best_op(HashArray *pHash, const int suggest_capacity);
297
298 /**
299 * hash stat
300 * parameters:
301 * pHash: the hash table
302 * pStat: return stat info
303 * stat_by_lens: return stats array by bucket length
304 * stat_by_lens[0] empty buckets count
305 * stat_by_lens[1] contain 1 key buckets count
306 * stat_by_lens[2] contain 2 key buckets count, etc
307 * stat_size: stats array size (contain max elments)
308 * return 0 for success, != 0 fail (errno)
309 */
310 int hash_stat(HashArray *pHash, HashStat *pStat, \
311 int *stat_by_lens, const int stat_size);
312
313 /**
314 * print hash stat info
315 * parameters:
316 * pHash: the hash table
317 * return none
318 */
319 void hash_stat_print(HashArray *pHash);
320
321 /**
322 * lock the bucket of hash table
323 * parameters:
324 * pHash: the hash table
325 * bucket_index: the index of bucket
326 * return 0 for success, != 0 fail (errno)
327 */
328 int hash_bucket_lock(HashArray *pHash, const unsigned int bucket_index);
329
330 /**
331 * unlock the bucket of hash table
332 * parameters:
333 * pHash: the hash table
334 * bucket_index: the index of bucket
335 * return 0 for success, != 0 fail (errno)
336 */
337 int hash_bucket_unlock(HashArray *pHash, const unsigned int bucket_index);
338
339 int RSHash(const void *key, const int key_len);
340
341 int JSHash(const void *key, const int key_len);
342 int JSHash_ex(const void *key, const int key_len, \
343 const int init_value);
344
345 int PJWHash(const void *key, const int key_len);
346 int PJWHash_ex(const void *key, const int key_len, \
347 const int init_value);
348
349 int ELFHash(const void *key, const int key_len);
350 int ELFHash_ex(const void *key, const int key_len, \
351 const int init_value);
352
353 int BKDRHash(const void *key, const int key_len);
354 int BKDRHash_ex(const void *key, const int key_len, \
355 const int init_value);
356
357 int SDBMHash(const void *key, const int key_len);
358 int SDBMHash_ex(const void *key, const int key_len, \
359 const int init_value);
360
361 int Time33Hash(const void *key, const int key_len);
362 int Time33Hash_ex(const void *key, const int key_len, \
363 const int init_value);
364
365 int DJBHash(const void *key, const int key_len);
366 int DJBHash_ex(const void *key, const int key_len, \
367 const int init_value);
368
369 int APHash(const void *key, const int key_len);
370 int APHash_ex(const void *key, const int key_len, \
371 const int init_value);
372
373 int calc_hashnr (const void* key, const int key_len);
374
375 int calc_hashnr1(const void* key, const int key_len);
376 int calc_hashnr1_ex(const void* key, const int key_len, \
377 const int init_value);
378
379 int simple_hash(const void* key, const int key_len);
380 int simple_hash_ex(const void* key, const int key_len, \
381 const int init_value);
382
383 int CRC32(const void *key, const int key_len);
384 int64_t CRC32_ex(const void *key, const int key_len, \
385 const int64_t init_value);
386
387 #define CRC32_FINAL(crc) (crc ^ CRC32_XOROT)
388
389 #define INIT_HASH_CODES4(hash_codes) \
390 hash_codes[0] = CRC32_XINIT; \
391 hash_codes[1] = 0; \
392 hash_codes[2] = 0; \
393 hash_codes[3] = 0; \
394
395 #define CALC_HASH_CODES4(buff, buff_len, hash_codes) \
396 hash_codes[0] = CRC32_ex(buff, buff_len, hash_codes[0]); \
397 hash_codes[1] = ELFHash_ex(buff, buff_len, hash_codes[1]); \
398 hash_codes[2] = simple_hash_ex(buff, buff_len, hash_codes[2]); \
399 hash_codes[3] = Time33Hash_ex(buff, buff_len, hash_codes[3]); \
400
401
402 #define FINISH_HASH_CODES4(hash_codes) \
403 hash_codes[0] = CRC32_FINAL(hash_codes[0]); \
404
405
406 unsigned int *hash_get_prime_capacity(const int capacity);
407
408 #ifdef __cplusplus
409 }
410 #endif
411
412 #endif
413
414