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