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 */ 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 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