upstream-dependencies/seqtk/khash.h
1/* The MIT License
2
3 Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk>
4
5 Permission is hereby granted, free of charge, to any person obtaining
6 a copy of this software and associated documentation files (the
7 "Software"), to deal in the Software without restriction, including
8 without limitation the rights to use, copy, modify, merge, publish,
9 distribute, sublicense, and/or sell copies of the Software, and to
10 permit persons to whom the Software is furnished to do so, subject to
11 the following conditions:
12
13 The above copyright notice and this permission notice shall be
14 included in all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 SOFTWARE.
24*/
25
26/*
27 An example:
28
29#include "khash.h"
30KHASH_MAP_INIT_INT(32, char)
31int main() {
32 int ret, is_missing;
33 khiter_t k;
34 khash_t(32) *h = kh_init(32);
35 k = kh_put(32, h, 5, &ret);
36 kh_value(h, k) = 10;
37 k = kh_get(32, h, 10);
38 is_missing = (k == kh_end(h));
39 k = kh_get(32, h, 5);
40 kh_del(32, h, k);
41 for (k = kh_begin(h); k != kh_end(h); ++k)
42 if (kh_exist(h, k)) kh_value(h, k) = 1;
43 kh_destroy(32, h);
44 return 0;
45}
46*/
47
48/*
49 2011-12-29 (0.2.7):
50
51 * Minor code clean up; no actual effect.
52
53 2011-09-16 (0.2.6):
54
55 * The capacity is a power of 2. This seems to dramatically improve the
56 speed for simple keys. Thank Zilong Tan for the suggestion. Reference:
57
58 - http://code.google.com/p/ulib/
59 - http://nothings.org/computer/judy/
60
61 * Allow to optionally use linear probing which usually has better
62 performance for random input. Double hashing is still the default as it
63 is more robust to certain non-random input.
64
65 * Added Wang's integer hash function (not used by default). This hash
66 function is more robust to certain non-random input.
67
68 2011-02-14 (0.2.5):
69
70 * Allow to declare global functions.
71
72 2009-09-26 (0.2.4):
73
74 * Improve portability
75
76 2008-09-19 (0.2.3):
77
78 * Corrected the example
79 * Improved interfaces
80
81 2008-09-11 (0.2.2):
82
83 * Improved speed a little in kh_put()
84
85 2008-09-10 (0.2.1):
86
87 * Added kh_clear()
88 * Fixed a compiling error
89
90 2008-09-02 (0.2.0):
91
92 * Changed to token concatenation which increases flexibility.
93
94 2008-08-31 (0.1.2):
95
96 * Fixed a bug in kh_get(), which has not been tested previously.
97
98 2008-08-31 (0.1.1):
99
100 * Added destructor
101*/
102
103
104#ifndef __AC_KHASH_H
105#define __AC_KHASH_H
106
107/*!
108 @header
109
110 Generic hash table library.
111 */
112
113#define AC_VERSION_KHASH_H "0.2.6"
114
115#include <stdlib.h>
116#include <string.h>
117#include <limits.h>
118
119/* compipler specific configuration */
120
121#if UINT_MAX == 0xffffffffu
122typedef unsigned int khint32_t;
123#elif ULONG_MAX == 0xffffffffu
124typedef unsigned long khint32_t;
125#endif
126
127#if ULONG_MAX == ULLONG_MAX
128typedef unsigned long khint64_t;
129#else
130typedef unsigned long long khint64_t;
131#endif
132
133#ifdef _MSC_VER
134#define inline __inline
135#endif
136
137typedef khint32_t khint_t;
138typedef khint_t khiter_t;
139
140#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
141#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
142#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
143#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
144#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
145#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
146#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
147
148#ifdef KHASH_LINEAR
149#define __ac_inc(k, m) 1
150#else
151#define __ac_inc(k, m) (((k)>>3 ^ (k)<<3) | 1) & (m)
152#endif
153
154#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
155
156#ifndef kroundup32
157#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
158#endif
159
160static const double __ac_HASH_UPPER = 0.77;
161
162#define __KHASH_TYPE(name, khkey_t, khval_t) \
163 typedef struct { \
164 khint_t n_buckets, size, n_occupied, upper_bound; \
165 khint32_t *flags; \
166 khkey_t *keys; \
167 khval_t *vals; \
168 } kh_##name##_t;
169
170#define KHASH_DECLARE(name, khkey_t, khval_t) \
171 __KHASH_TYPE(name, khkey_t, khval_t) \
172 extern kh_##name##_t *kh_init_##name(); \
173 extern void kh_destroy_##name(kh_##name##_t *h); \
174 extern void kh_clear_##name(kh_##name##_t *h); \
175 extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \
176 extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
177 extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
178 extern void kh_del_##name(kh_##name##_t *h, khint_t x);
179
180#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
181 __KHASH_TYPE(name, khkey_t, khval_t) \
182 SCOPE kh_##name##_t *kh_init_##name() { \
183 return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \
184 } \
185 SCOPE void kh_destroy_##name(kh_##name##_t *h) \
186 { \
187 if (h) { \
188 free(h->keys); free(h->flags); \
189 free(h->vals); \
190 free(h); \
191 } \
192 } \
193 SCOPE void kh_clear_##name(kh_##name##_t *h) \
194 { \
195 if (h && h->flags) { \
196 memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
197 h->size = h->n_occupied = 0; \
198 } \
199 } \
200 SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
201 { \
202 if (h->n_buckets) { \
203 khint_t inc, k, i, last, mask; \
204 mask = h->n_buckets - 1; \
205 k = __hash_func(key); i = k & mask; \
206 inc = __ac_inc(k, mask); last = i; /* inc==1 for linear probing */ \
207 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
208 i = (i + inc) & mask; \
209 if (i == last) return h->n_buckets; \
210 } \
211 return __ac_iseither(h->flags, i)? h->n_buckets : i; \
212 } else return 0; \
213 } \
214 SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
215 { /* This function uses 0.25*n_bucktes bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
216 khint32_t *new_flags = 0; \
217 khint_t j = 1; \
218 { \
219 kroundup32(new_n_buckets); \
220 if (new_n_buckets < 4) new_n_buckets = 4; \
221 if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \
222 else { /* hash table size to be changed (shrink or expand); rehash */ \
223 new_flags = (khint32_t*)malloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
224 memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
225 if (h->n_buckets < new_n_buckets) { /* expand */ \
226 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
227 if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
228 } /* otherwise shrink */ \
229 } \
230 } \
231 if (j) { /* rehashing is needed */ \
232 for (j = 0; j != h->n_buckets; ++j) { \
233 if (__ac_iseither(h->flags, j) == 0) { \
234 khkey_t key = h->keys[j]; \
235 khval_t val; \
236 khint_t new_mask; \
237 new_mask = new_n_buckets - 1; \
238 if (kh_is_map) val = h->vals[j]; \
239 __ac_set_isdel_true(h->flags, j); \
240 while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
241 khint_t inc, k, i; \
242 k = __hash_func(key); \
243 i = k & new_mask; \
244 inc = __ac_inc(k, new_mask); \
245 while (!__ac_isempty(new_flags, i)) i = (i + inc) & new_mask; \
246 __ac_set_isempty_false(new_flags, i); \
247 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
248 { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
249 if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
250 __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
251 } else { /* write the element and jump out of the loop */ \
252 h->keys[i] = key; \
253 if (kh_is_map) h->vals[i] = val; \
254 break; \
255 } \
256 } \
257 } \
258 } \
259 if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
260 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
261 if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
262 } \
263 free(h->flags); /* free the working space */ \
264 h->flags = new_flags; \
265 h->n_buckets = new_n_buckets; \
266 h->n_occupied = h->size; \
267 h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
268 } \
269 } \
270 SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
271 { \
272 khint_t x; \
273 if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
274 if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \
275 else kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \
276 } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
277 { \
278 khint_t inc, k, i, site, last, mask = h->n_buckets - 1; \
279 x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
280 if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \
281 else { \
282 inc = __ac_inc(k, mask); last = i; \
283 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
284 if (__ac_isdel(h->flags, i)) site = i; \
285 i = (i + inc) & mask; \
286 if (i == last) { x = site; break; } \
287 } \
288 if (x == h->n_buckets) { \
289 if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
290 else x = i; \
291 } \
292 } \
293 } \
294 if (__ac_isempty(h->flags, x)) { /* not present at all */ \
295 h->keys[x] = key; \
296 __ac_set_isboth_false(h->flags, x); \
297 ++h->size; ++h->n_occupied; \
298 *ret = 1; \
299 } else if (__ac_isdel(h->flags, x)) { /* deleted */ \
300 h->keys[x] = key; \
301 __ac_set_isboth_false(h->flags, x); \
302 ++h->size; \
303 *ret = 2; \
304 } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
305 return x; \
306 } \
307 SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \
308 { \
309 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
310 __ac_set_isdel_true(h->flags, x); \
311 --h->size; \
312 } \
313 }
314
315#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
316 KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
317
318/* --- BEGIN OF HASH FUNCTIONS --- */
319
320/*! @function
321 @abstract Integer hash function
322 @param key The integer [khint32_t]
323 @return The hash value [khint_t]
324 */
325#define kh_int_hash_func(key) (khint32_t)(key)
326/*! @function
327 @abstract Integer comparison function
328 */
329#define kh_int_hash_equal(a, b) ((a) == (b))
330/*! @function
331 @abstract 64-bit integer hash function
332 @param key The integer [khint64_t]
333 @return The hash value [khint_t]
334 */
335#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
336/*! @function
337 @abstract 64-bit integer comparison function
338 */
339#define kh_int64_hash_equal(a, b) ((a) == (b))
340/*! @function
341 @abstract const char* hash function
342 @param s Pointer to a null terminated string
343 @return The hash value
344 */
345static inline khint_t __ac_X31_hash_string(const char *s)
346{
347 khint_t h = *s;
348 if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
349 return h;
350}
351/*! @function
352 @abstract Another interface to const char* hash function
353 @param key Pointer to a null terminated string [const char*]
354 @return The hash value [khint_t]
355 */
356#define kh_str_hash_func(key) __ac_X31_hash_string(key)
357/*! @function
358 @abstract Const char* comparison function
359 */
360#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
361
362static inline khint_t __ac_Wang_hash(khint_t key)
363{
364 key += ~(key << 15);
365 key ^= (key >> 10);
366 key += (key << 3);
367 key ^= (key >> 6);
368 key += ~(key << 11);
369 key ^= (key >> 16);
370 return key;
371}
372#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
373
374/* --- END OF HASH FUNCTIONS --- */
375
376/* Other convenient macros... */
377
378/*!
379 @abstract Type of the hash table.
380 @param name Name of the hash table [symbol]
381 */
382#define khash_t(name) kh_##name##_t
383
384/*! @function
385 @abstract Initiate a hash table.
386 @param name Name of the hash table [symbol]
387 @return Pointer to the hash table [khash_t(name)*]
388 */
389#define kh_init(name) kh_init_##name()
390
391/*! @function
392 @abstract Destroy a hash table.
393 @param name Name of the hash table [symbol]
394 @param h Pointer to the hash table [khash_t(name)*]
395 */
396#define kh_destroy(name, h) kh_destroy_##name(h)
397
398/*! @function
399 @abstract Reset a hash table without deallocating memory.
400 @param name Name of the hash table [symbol]
401 @param h Pointer to the hash table [khash_t(name)*]
402 */
403#define kh_clear(name, h) kh_clear_##name(h)
404
405/*! @function
406 @abstract Resize a hash table.
407 @param name Name of the hash table [symbol]
408 @param h Pointer to the hash table [khash_t(name)*]
409 @param s New size [khint_t]
410 */
411#define kh_resize(name, h, s) kh_resize_##name(h, s)
412
413/*! @function
414 @abstract Insert a key to the hash table.
415 @param name Name of the hash table [symbol]
416 @param h Pointer to the hash table [khash_t(name)*]
417 @param k Key [type of keys]
418 @param r Extra return code: 0 if the key is present in the hash table;
419 1 if the bucket is empty (never used); 2 if the element in
420 the bucket has been deleted [int*]
421 @return Iterator to the inserted element [khint_t]
422 */
423#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
424
425/*! @function
426 @abstract Retrieve a key from the hash table.
427 @param name Name of the hash table [symbol]
428 @param h Pointer to the hash table [khash_t(name)*]
429 @param k Key [type of keys]
430 @return Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
431 */
432#define kh_get(name, h, k) kh_get_##name(h, k)
433
434/*! @function
435 @abstract Remove a key from the hash table.
436 @param name Name of the hash table [symbol]
437 @param h Pointer to the hash table [khash_t(name)*]
438 @param k Iterator to the element to be deleted [khint_t]
439 */
440#define kh_del(name, h, k) kh_del_##name(h, k)
441
442/*! @function
443 @abstract Test whether a bucket contains data.
444 @param h Pointer to the hash table [khash_t(name)*]
445 @param x Iterator to the bucket [khint_t]
446 @return 1 if containing data; 0 otherwise [int]
447 */
448#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
449
450/*! @function
451 @abstract Get key given an iterator
452 @param h Pointer to the hash table [khash_t(name)*]
453 @param x Iterator to the bucket [khint_t]
454 @return Key [type of keys]
455 */
456#define kh_key(h, x) ((h)->keys[x])
457
458/*! @function
459 @abstract Get value given an iterator
460 @param h Pointer to the hash table [khash_t(name)*]
461 @param x Iterator to the bucket [khint_t]
462 @return Value [type of values]
463 @discussion For hash sets, calling this results in segfault.
464 */
465#define kh_val(h, x) ((h)->vals[x])
466
467/*! @function
468 @abstract Alias of kh_val()
469 */
470#define kh_value(h, x) ((h)->vals[x])
471
472/*! @function
473 @abstract Get the start iterator
474 @param h Pointer to the hash table [khash_t(name)*]
475 @return The start iterator [khint_t]
476 */
477#define kh_begin(h) (khint_t)(0)
478
479/*! @function
480 @abstract Get the end iterator
481 @param h Pointer to the hash table [khash_t(name)*]
482 @return The end iterator [khint_t]
483 */
484#define kh_end(h) ((h)->n_buckets)
485
486/*! @function
487 @abstract Get the number of elements in the hash table
488 @param h Pointer to the hash table [khash_t(name)*]
489 @return Number of elements in the hash table [khint_t]
490 */
491#define kh_size(h) ((h)->size)
492
493/*! @function
494 @abstract Get the number of buckets in the hash table
495 @param h Pointer to the hash table [khash_t(name)*]
496 @return Number of buckets in the hash table [khint_t]
497 */
498#define kh_n_buckets(h) ((h)->n_buckets)
499
500/* More conenient interfaces */
501
502/*! @function
503 @abstract Instantiate a hash set containing integer keys
504 @param name Name of the hash table [symbol]
505 */
506#define KHASH_SET_INIT_INT(name) \
507 KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
508
509/*! @function
510 @abstract Instantiate a hash map containing integer keys
511 @param name Name of the hash table [symbol]
512 @param khval_t Type of values [type]
513 */
514#define KHASH_MAP_INIT_INT(name, khval_t) \
515 KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
516
517/*! @function
518 @abstract Instantiate a hash map containing 64-bit integer keys
519 @param name Name of the hash table [symbol]
520 */
521#define KHASH_SET_INIT_INT64(name) \
522 KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
523
524/*! @function
525 @abstract Instantiate a hash map containing 64-bit integer keys
526 @param name Name of the hash table [symbol]
527 @param khval_t Type of values [type]
528 */
529#define KHASH_MAP_INIT_INT64(name, khval_t) \
530 KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
531
532typedef const char *kh_cstr_t;
533/*! @function
534 @abstract Instantiate a hash map containing const char* keys
535 @param name Name of the hash table [symbol]
536 */
537#define KHASH_SET_INIT_STR(name) \
538 KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
539
540/*! @function
541 @abstract Instantiate a hash map containing const char* keys
542 @param name Name of the hash table [symbol]
543 @param khval_t Type of values [type]
544 */
545#define KHASH_MAP_INIT_STR(name, khval_t) \
546 KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
547
548#endif /* __AC_KHASH_H */