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"
30 KHASH_MAP_INIT_INT(32, char)
31 int 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 2013-05-02 (0.2.8):
50
51 * Use quadratic probing. When the capacity is power of 2, stepping function
52 i*(i+1)/2 guarantees to traverse each bucket. It is better than double
53 hashing on cache performance and is more robust than linear probing.
54
55 In theory, double hashing should be more robust than quadratic probing.
56 However, my implementation is probably not for large hash tables, because
57 the second hash function is closely tied to the first hash function,
58 which reduce the effectiveness of double hashing.
59
60 Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php
61
62 2011-12-29 (0.2.7):
63
64 * Minor code clean up; no actual effect.
65
66 2011-09-16 (0.2.6):
67
68 * The capacity is a power of 2. This seems to dramatically improve the
69 speed for simple keys. Thank Zilong Tan for the suggestion. Reference:
70
71 - http://code.google.com/p/ulib/
72 - http://nothings.org/computer/judy/
73
74 * Allow to optionally use linear probing which usually has better
75 performance for random input. Double hashing is still the default as it
76 is more robust to certain non-random input.
77
78 * Added Wang's integer hash function (not used by default). This hash
79 function is more robust to certain non-random input.
80
81 2011-02-14 (0.2.5):
82
83 * Allow to declare global functions.
84
85 2009-09-26 (0.2.4):
86
87 * Improve portability
88
89 2008-09-19 (0.2.3):
90
91 * Corrected the example
92 * Improved interfaces
93
94 2008-09-11 (0.2.2):
95
96 * Improved speed a little in kh_put()
97
98 2008-09-10 (0.2.1):
99
100 * Added kh_clear()
101 * Fixed a compiling error
102
103 2008-09-02 (0.2.0):
104
105 * Changed to token concatenation which increases flexibility.
106
107 2008-08-31 (0.1.2):
108
109 * Fixed a bug in kh_get(), which has not been tested previously.
110
111 2008-08-31 (0.1.1):
112
113 * Added destructor
114 */
115
116
117 #ifndef __AC_KHASH_H
118 #define __AC_KHASH_H
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 /* Clang analyzer thinks that `h->flags` can be NULL, but this is
133 * the wrong assumption - add `kassert()` to suppress the warning */
134 #ifdef __clang_analyzer__
135 #include <assert.h>
136 #define kassert(...) assert(__VA_ARGS__)
137 #define kmemset_analyzer(P, Z, N) kmemset(P, Z, N)
138 #else
139 #define kassert(...)
140 #define kmemset_analyzer(P, Z, N)
141 #endif
142
143 /* compiler specific configuration */
144
145 #if UINT_MAX == 0xffffffffu
146 typedef unsigned int khint32_t;
147 #elif ULONG_MAX == 0xffffffffu
148 typedef unsigned long khint32_t;
149 #endif
150
151 #if ULONG_MAX == ULLONG_MAX
152 typedef unsigned long khint64_t;
153 #else
154 typedef unsigned long long khint64_t;
155 #endif
156
157 #ifndef kh_inline
158 #ifdef _MSC_VER
159 #define kh_inline __inline
160 #else
161 #define kh_inline inline
162 #endif
163 #endif /* kh_inline */
164
165 #ifndef klib_unused
166 #if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3)
167 #define klib_unused __attribute__ ((__unused__))
168 #else
169 #define klib_unused
170 #endif
171 #endif /* klib_unused */
172
173 typedef khint32_t khint_t;
174 typedef khint_t khiter_t;
175
176 #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
177 #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
178 #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
179 #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
180 #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
181 #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
182 #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
183
184 #define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
185
186 #ifndef kroundup32
187 #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
188 #endif
189
190 #ifndef kcalloc
191 #define kcalloc(N,Z) calloc(N,Z)
192 #endif
193 #ifndef kmalloc
194 #define kmalloc(Z) malloc(Z)
195 #endif
196 #ifndef krealloc
197 #define krealloc(P,Z) realloc(P,Z)
198 #endif
199 #ifndef kfree
200 #define kfree(P) free(P)
201 #endif
202 #ifndef kmemset
203 #define kmemset(P,Z,N) memset(P,Z,N)
204 #endif
205
206 static const double __ac_HASH_UPPER = 0.77;
207
208 #define __KHASH_TYPE(name, khkey_t, khval_t) \
209 typedef struct kh_##name##_s { \
210 khint_t n_buckets, size, n_occupied, upper_bound; \
211 khint32_t *flags; \
212 khkey_t *keys; \
213 khval_t *vals; \
214 } kh_##name##_t;
215
216 #define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \
217 extern kh_##name##_t *kh_init_##name(void); \
218 extern kh_##name##_t *kh_init_##name##_inplace(kh_##name##_t *h); \
219 extern void kh_destroy_##name(kh_##name##_t *h); \
220 extern void kh_destroy_##name##_inplace(kh_##name##_t *h); \
221 extern void kh_clear_##name(kh_##name##_t *h); \
222 extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \
223 extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
224 extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
225 extern void kh_del_##name(kh_##name##_t *h, khint_t x);
226
227 #define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
228 SCOPE kh_##name##_t *kh_init_##name(void) { \
229 return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \
230 } \
231 SCOPE kh_##name##_t *kh_init_##name##_inplace(kh_##name##_t *h) { \
232 return (kh_##name##_t*)kmemset(h, 0, sizeof(kh_##name##_t)); \
233 } \
234 SCOPE void kh_destroy_##name(kh_##name##_t *h) \
235 { \
236 if (h) { \
237 kfree((void *)h->keys); kfree(h->flags); \
238 kfree((void *)h->vals); \
239 kfree(h); \
240 } \
241 } \
242 SCOPE void kh_destroy_##name##_inplace(kh_##name##_t *h) \
243 { \
244 kfree((void *)h->keys); \
245 kfree((void *)h->flags); \
246 kfree((void *)h->vals); \
247 } \
248 SCOPE void kh_clear_##name(kh_##name##_t *h) \
249 { \
250 if (h && h->flags) { \
251 memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
252 h->size = h->n_occupied = 0; \
253 } \
254 } \
255 SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
256 { \
257 if (h->n_buckets) { \
258 khint_t k, i, last, mask, step = 0; \
259 mask = h->n_buckets - 1; \
260 \
261 kassert(h->flags != NULL); \
262 \
263 k = __hash_func(key); i = k & mask; \
264 last = i; \
265 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
266 i = (i + (++step)) & mask; \
267 if (i == last) return h->n_buckets; \
268 } \
269 return __ac_iseither(h->flags, i)? h->n_buckets : i; \
270 } else return 0; \
271 } \
272 SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
273 { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
274 khint32_t *new_flags = 0; \
275 khint_t j = 1; \
276 { \
277 kroundup32(new_n_buckets); \
278 if (new_n_buckets < 4) new_n_buckets = 4; \
279 if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \
280 else { /* hash table size to be changed (shrink or expand); rehash */ \
281 new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
282 if (!new_flags) return -1; \
283 memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
284 if (h->n_buckets < new_n_buckets) { /* expand */ \
285 khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
286 if (!new_keys) { kfree(new_flags); return -1; } \
287 h->keys = new_keys; \
288 kmemset_analyzer(h->keys + (h->n_buckets * sizeof(khkey_t)), 0, \
289 (new_n_buckets - h->n_buckets) * sizeof(khkey_t)); \
290 if (kh_is_map) { \
291 khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
292 if (!new_vals) { kfree(new_flags); return -1; } \
293 h->vals = new_vals; \
294 } \
295 } /* otherwise shrink */ \
296 } \
297 } \
298 if (j) { /* rehashing is needed */ \
299 for (j = 0; j != h->n_buckets; ++j) { \
300 if (__ac_iseither(h->flags, j) == 0) { \
301 khkey_t key = h->keys[j]; \
302 khval_t val; \
303 khint_t new_mask; \
304 new_mask = new_n_buckets - 1; \
305 if (kh_is_map) val = h->vals[j]; \
306 __ac_set_isdel_true(h->flags, j); \
307 while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
308 khint_t k, i, step = 0; \
309 k = __hash_func(key); \
310 i = k & new_mask; \
311 while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \
312 __ac_set_isempty_false(new_flags, i); \
313 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
314 { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
315 if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
316 __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
317 } else { /* write the element and jump out of the loop */ \
318 h->keys[i] = key; \
319 if (kh_is_map) h->vals[i] = val; \
320 break; \
321 } \
322 } \
323 } \
324 } \
325 if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
326 h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
327 if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
328 } \
329 kfree(h->flags); /* free the working space */ \
330 h->flags = new_flags; \
331 h->n_buckets = new_n_buckets; \
332 h->n_occupied = h->size; \
333 h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
334 } \
335 return 0; \
336 } \
337 SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
338 { \
339 khint_t x; \
340 if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
341 if (h->n_buckets > (h->size<<1)) { \
342 if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
343 *ret = -1; return h->n_buckets; \
344 } \
345 } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
346 *ret = -1; return h->n_buckets; \
347 } \
348 } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
349 \
350 kassert(h->flags != NULL); \
351 \
352 { \
353 khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \
354 x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
355 if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \
356 else { \
357 last = i; \
358 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
359 if (__ac_isdel(h->flags, i)) site = i; \
360 i = (i + (++step)) & mask; \
361 if (i == last) { x = site; break; } \
362 } \
363 if (x == h->n_buckets) { \
364 if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
365 else x = i; \
366 } \
367 } \
368 } \
369 if (__ac_isempty(h->flags, x)) { /* not present at all */ \
370 h->keys[x] = key; \
371 __ac_set_isboth_false(h->flags, x); \
372 ++h->size; ++h->n_occupied; \
373 *ret = 1; \
374 } else if (__ac_isdel(h->flags, x)) { /* deleted */ \
375 h->keys[x] = key; \
376 __ac_set_isboth_false(h->flags, x); \
377 ++h->size; \
378 *ret = 2; \
379 } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
380 return x; \
381 } \
382 SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \
383 { \
384 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
385 __ac_set_isdel_true(h->flags, x); \
386 --h->size; \
387 } \
388 }
389
390 #define KHASH_DECLARE(name, khkey_t, khval_t) \
391 __KHASH_TYPE(name, khkey_t, khval_t) \
392 __KHASH_PROTOTYPES(name, khkey_t, khval_t)
393
394 #define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
395 __KHASH_TYPE(name, khkey_t, khval_t) \
396 __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
397
398 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
399 KHASH_INIT2(name, static kh_inline klib_unused, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
400
401 #define KHASH_TYPE(name, khkey_t, khval_t) \
402 __KHASH_TYPE(name, khkey_t, khval_t)
403
404 #define KHASH_IMPL(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
405 __KHASH_IMPL(name, static kh_inline klib_unused, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
406
407 /* --- BEGIN OF HASH FUNCTIONS --- */
408
409 /*! @function
410 @abstract Integer hash function
411 @param key The integer [khint32_t]
412 @return The hash value [khint_t]
413 */
414 #define kh_int_hash_func(key) (khint32_t)(key)
415 /*! @function
416 @abstract Integer comparison function
417 */
418 #define kh_int_hash_equal(a, b) ((a) == (b))
419 /*! @function
420 @abstract 64-bit integer hash function
421 @param key The integer [khint64_t]
422 @return The hash value [khint_t]
423 */
424 #define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
425 /*! @function
426 @abstract 64-bit integer comparison function
427 */
428 #define kh_int64_hash_equal(a, b) ((a) == (b))
429 /*! @function
430 @abstract const char* hash function
431 @param s Pointer to a null terminated string
432 @return The hash value
433 */
__ac_X31_hash_string(const char * s)434 static kh_inline khint_t __ac_X31_hash_string(const char *s)
435 {
436 khint_t h = (khint_t)*s;
437 if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;
438 return h;
439 }
440 /*! @function
441 @abstract Another interface to const char* hash function
442 @param key Pointer to a null terminated string [const char*]
443 @return The hash value [khint_t]
444 */
445 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
446 /*! @function
447 @abstract Const char* comparison function
448 */
449 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
450
__ac_Wang_hash(khint_t key)451 static kh_inline khint_t __ac_Wang_hash(khint_t key)
452 {
453 key += ~(key << 15);
454 key ^= (key >> 10);
455 key += (key << 3);
456 key ^= (key >> 6);
457 key += ~(key << 11);
458 key ^= (key >> 16);
459 return key;
460 }
461 #define kh_int_hash_func2(key) __ac_Wang_hash((khint_t)key)
462
463 /* --- END OF HASH FUNCTIONS --- */
464
465 /* Other convenient macros... */
466
467 /*!
468 @abstract Type of the hash table.
469 @param name Name of the hash table [symbol]
470 */
471 #define khash_t(name) kh_##name##_t
472
473 /*! @function
474 @abstract Initiate a hash table.
475 @param name Name of the hash table [symbol]
476 @return Pointer to the hash table [khash_t(name)*]
477 */
478 #define kh_init(name) kh_init_##name()
479
480 /*! @function
481 @abstract Initiate a hash table if the in-place case.
482 @param name Name of the hash table [symbol]
483 @param h Pointer to the hash table [khash_t(name)*]
484 */
485 #define kh_init_inplace(name, h) kh_init_##name##_inplace(h)
486
487 /*! @function
488 @abstract Destroy a hash table.
489 @param name Name of the hash table [symbol]
490 @param h Pointer to the hash table [khash_t(name)*]
491 */
492 #define kh_destroy(name, h) kh_destroy_##name(h)
493
494 /*! @function
495 @abstract Destroy a hash table if the in-place case.
496 @param name Name of the hash table [symbol]
497 @param h Pointer to the hash table [khash_t(name)*]
498 */
499 #define kh_destroy_inplace(name, h) kh_destroy_##name##_inplace(h)
500
501 /*! @function
502 @abstract Reset a hash table without deallocating memory.
503 @param name Name of the hash table [symbol]
504 @param h Pointer to the hash table [khash_t(name)*]
505 */
506 #define kh_clear(name, h) kh_clear_##name(h)
507
508 /*! @function
509 @abstract Resize a hash table.
510 @param name Name of the hash table [symbol]
511 @param h Pointer to the hash table [khash_t(name)*]
512 @param s New size [khint_t]
513 */
514 #define kh_resize(name, h, s) kh_resize_##name(h, s)
515
516 /*! @function
517 @abstract Insert a key to the hash table.
518 @param name Name of the hash table [symbol]
519 @param h Pointer to the hash table [khash_t(name)*]
520 @param k Key [type of keys]
521 @param r Extra return code: -1 if the operation failed;
522 0 if the key is present in the hash table;
523 1 if the bucket is empty (never used); 2 if the element in
524 the bucket has been deleted [int*]
525 @return Iterator to the inserted element [khint_t]
526 */
527 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
528
529 typedef enum ucs_kh_put {
530 UCS_KH_PUT_FAILED = -1,
531 UCS_KH_PUT_KEY_PRESENT = 0,
532 UCS_KH_PUT_BUCKET_EMPTY = 1,
533 UCS_KH_PUT_BUCKET_CLEAR = 2
534 } ucs_kh_put_t;
535
536 /*! @function
537 @abstract Retrieve a key from the hash table.
538 @param name Name of the hash table [symbol]
539 @param h Pointer to the hash table [khash_t(name)*]
540 @param k Key [type of keys]
541 @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t]
542 */
543 #define kh_get(name, h, k) kh_get_##name(h, k)
544
545 /*! @function
546 @abstract Remove a key from the hash table.
547 @param name Name of the hash table [symbol]
548 @param h Pointer to the hash table [khash_t(name)*]
549 @param k Iterator to the element to be deleted [khint_t]
550 */
551 #define kh_del(name, h, k) kh_del_##name(h, k)
552
553 /*! @function
554 @abstract Test whether a bucket contains data.
555 @param h Pointer to the hash table [khash_t(name)*]
556 @param x Iterator to the bucket [khint_t]
557 @return 1 if containing data; 0 otherwise [int]
558 */
559 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
560
561 /*! @function
562 @abstract Get key given an iterator
563 @param h Pointer to the hash table [khash_t(name)*]
564 @param x Iterator to the bucket [khint_t]
565 @return Key [type of keys]
566 */
567 #define kh_key(h, x) ((h)->keys[x])
568
569 /*! @function
570 @abstract Get value given an iterator
571 @param h Pointer to the hash table [khash_t(name)*]
572 @param x Iterator to the bucket [khint_t]
573 @return Value [type of values]
574 @discussion For hash sets, calling this results in segfault.
575 */
576 #define kh_val(h, x) ((h)->vals[x])
577
578 /*! @function
579 @abstract Alias of kh_val()
580 */
581 #define kh_value(h, x) ((h)->vals[x])
582
583 /*! @function
584 @abstract Get the start iterator
585 @param h Pointer to the hash table [khash_t(name)*]
586 @return The start iterator [khint_t]
587 */
588 #define kh_begin(h) (khint_t)(0)
589
590 /*! @function
591 @abstract Get the end iterator
592 @param h Pointer to the hash table [khash_t(name)*]
593 @return The end iterator [khint_t]
594 */
595 #define kh_end(h) ((h)->n_buckets)
596
597 /*! @function
598 @abstract Get the number of elements in the hash table
599 @param h Pointer to the hash table [khash_t(name)*]
600 @return Number of elements in the hash table [khint_t]
601 */
602 #define kh_size(h) ((h)->size)
603
604 /*! @function
605 @abstract Get the number of buckets in the hash table
606 @param h Pointer to the hash table [khash_t(name)*]
607 @return Number of buckets in the hash table [khint_t]
608 */
609 #define kh_n_buckets(h) ((h)->n_buckets)
610
611 /*! @function
612 @abstract Iterate over the entries in the hash table
613 @param h Pointer to the hash table [khash_t(name)*]
614 @param kvar Variable to which key will be assigned
615 @param vvar Variable to which value will be assigned
616 @param code Block of code to execute
617 */
618 #define kh_foreach(h, kvar, vvar, code) { khint_t __i; \
619 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
620 if (!kh_exist(h,__i)) continue; \
621 (kvar) = kh_key(h,__i); \
622 (vvar) = kh_val(h,__i); \
623 code; \
624 } }
625
626 /*! @function
627 @abstract Iterate over the keys in the hash table
628 @param h Pointer to the hash table [khash_t(name)*]
629 @param kvar Variable to which key will be assigned
630 @param code Block of code to execute
631 */
632 #define kh_foreach_key(h, kvar, code) { khint_t __i; \
633 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
634 if (!kh_exist(h,__i)) continue; \
635 (kvar) = kh_key(h,__i); \
636 code; \
637 } }
638
639 /*! @function
640 @abstract Iterate over the values in the hash table
641 @param h Pointer to the hash table [khash_t(name)*]
642 @param vvar Variable to which value will be assigned
643 @param code Block of code to execute
644 */
645 #define kh_foreach_value(h, vvar, code) { khint_t __i; \
646 for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
647 if (!kh_exist(h,__i)) continue; \
648 (vvar) = kh_val(h,__i); \
649 code; \
650 } }
651
652 /* More conenient interfaces */
653
654 /*! @function
655 @abstract Instantiate a hash set containing integer keys
656 @param name Name of the hash table [symbol]
657 */
658 #define KHASH_SET_INIT_INT(name) \
659 KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
660
661 /*! @function
662 @abstract Instantiate a hash map containing integer keys
663 @param name Name of the hash table [symbol]
664 @param khval_t Type of values [type]
665 */
666 #define KHASH_MAP_INIT_INT(name, khval_t) \
667 KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
668
669 /*! @function
670 @abstract Instantiate a hash map containing 64-bit integer keys
671 @param name Name of the hash table [symbol]
672 */
673 #define KHASH_SET_INIT_INT64(name) \
674 KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
675
676 /*! @function
677 @abstract Instantiate a hash map containing 64-bit integer keys
678 @param name Name of the hash table [symbol]
679 @param khval_t Type of values [type]
680 */
681 #define KHASH_MAP_INIT_INT64(name, khval_t) \
682 KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
683
684 typedef const char *kh_cstr_t;
685 /*! @function
686 @abstract Instantiate a hash map containing const char* keys
687 @param name Name of the hash table [symbol]
688 */
689 #define KHASH_SET_INIT_STR(name) \
690 KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
691
692 /*! @function
693 @abstract Instantiate a hash map containing const char* keys
694 @param name Name of the hash table [symbol]
695 @param khval_t Type of values [type]
696 */
697 #define KHASH_MAP_INIT_STR(name, khval_t) \
698 KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
699
700 #endif /* __AC_KHASH_H */
701