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