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"
  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         if (!ret) kh_del(32, h, k);
  37         kh_value(h, k) = 10;
  38         k = kh_get(32, h, 10);
  39         is_missing = (k == kh_end(h));
  40         k = kh_get(32, h, 5);
  41         kh_del(32, h, k);
  42         for (k = kh_begin(h); k != kh_end(h); ++k)
  43                 if (kh_exist(h, k)) kh_value(h, k) = 1;
  44         kh_destroy(32, h);
  45         return 0;
  46 }
  47 */
  48
  49 /*
  50   2011-02-14 (0.2.5):
  51
  52     * Allow to declare global functions.
  53
  54   2009-09-26 (0.2.4):
  55
  56     * Improve portability
  57
  58   2008-09-19 (0.2.3):
  59
  60         * Corrected the example
  61         * Improved interfaces
  62
  63   2008-09-11 (0.2.2):
  64
  65         * Improved speed a little in kh_put()
  66
  67   2008-09-10 (0.2.1):
  68
  69         * Added kh_clear()
  70         * Fixed a compiling error
  71
  72   2008-09-02 (0.2.0):
  73
  74         * Changed to token concatenation which increases flexibility.
  75
  76   2008-08-31 (0.1.2):
  77
  78         * Fixed a bug in kh_get(), which has not been tested previously.
  79
  80   2008-08-31 (0.1.1):
  81
  82         * Added destructor
  83 */
  84
  85
  86 #ifndef __AC_KHASH_H
  87 #define __AC_KHASH_H
  88
  89 /*!
  90   @header
  91
  92   Generic hash table library.
  93
  94   @copyright Heng Li
  95  */
  96
  97 #define AC_VERSION_KHASH_H "0.2.5"
  98
  99 #include <stdlib.h>
 100 #include <string.h>
 101 #include <limits.h>
 102
 103 /* compipler specific configuration */
 104
 105 #if UINT_MAX == 0xffffffffu
 106 typedef unsigned int khint32_t;
 107 #elif ULONG_MAX == 0xffffffffu
 108 typedef unsigned long khint32_t;
 109 #endif
 110
 111 #if ULONG_MAX == ULLONG_MAX
 112 typedef unsigned long khint64_t;
 113 #else
 114 typedef unsigned long long khint64_t;
 115 #endif
 116
 117 #ifdef _MSC_VER
 118 #define inline __inline
 119 #endif
 120
 121 typedef khint32_t khint_t;
 122 typedef khint_t khiter_t;
 123
 124 #define __ac_HASH_PRIME_SIZE 32
 125 static const khint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] =
 126 {
 127   0ul,          3ul,          11ul,         23ul,         53ul,
 128   97ul,         193ul,        389ul,        769ul,        1543ul,
 129   3079ul,       6151ul,       12289ul,      24593ul,      49157ul,
 130   98317ul,      196613ul,     393241ul,     786433ul,     1572869ul,
 131   3145739ul,    6291469ul,    12582917ul,   25165843ul,   50331653ul,
 132   100663319ul,  201326611ul,  402653189ul,  805306457ul,  1610612741ul,
 133   3221225473ul, 4294967291ul
 134 };
 135
 136 #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
 137 #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
 138 #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
 139 #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
 140 #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
 141 #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
 142 #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
 143
 144 static const double __ac_HASH_UPPER = 0.77;
 145
 146 #define KHASH_DECLARE(name, khkey_t, khval_t)                                                   \
 147         typedef struct {                                                                                                        \
 148                 khint_t n_buckets, size, n_occupied, upper_bound;                               \
 149                 khint32_t *flags;                                                                                               \
 150                 khkey_t *keys;                                                                                                  \
 151                 khval_t *vals;                                                                                                  \
 152         } kh_##name##_t;                                                                                                        \
 153         extern kh_##name##_t *kh_init_##name();                                                         \
 154         extern void kh_destroy_##name(kh_##name##_t *h);                                        \
 155         extern void kh_clear_##name(kh_##name##_t *h);                                          \
 156         extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key);      \
 157         extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
 158         extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
 159         extern void kh_del_##name(kh_##name##_t *h, khint_t x);
 160
 161 #define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 162         typedef struct {                                                                                                        \
 163                 khint_t n_buckets, size, n_occupied, upper_bound;                               \
 164                 khint32_t *flags;                                                                                               \
 165                 khkey_t *keys;                                                                                                  \
 166                 khval_t *vals;                                                                                                  \
 167         } kh_##name##_t;                                                                                                        \
 168         SCOPE kh_##name##_t *kh_init_##name() {                                                         \
 169                 return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));                \
 170         }                                                                                                                                       \
 171         SCOPE void kh_destroy_##name(kh_##name##_t *h)                                          \
 172         {                                                                                                                                       \
 173                 if (h) {                                                                                                                \
 174                         free(h->keys); free(h->flags);                                                          \
 175                         free(h->vals);                                                                                          \
 176                         free(h);                                                                                                        \
 177                 }                                                                                                                               \
 178         }                                                                                                                                       \
 179         SCOPE void kh_clear_##name(kh_##name##_t *h)                                            \
 180         {                                                                                                                                       \
 181                 if (h && h->flags) {                                                                                    \
 182                         memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(khint32_t)); \
 183                         h->size = h->n_occupied = 0;                                                            \
 184                 }                                                                                                                               \
 185         }                                                                                                                                       \
 186         SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key)        \
 187         {                                                                                                                                       \
 188                 if (h->n_buckets) {                                                                                             \
 189                         khint_t inc, k, i, last;                                                                        \
 190                         k = __hash_func(key); i = k % h->n_buckets;                                     \
 191                         inc = 1 + k % (h->n_buckets - 1); last = i;                                     \
 192                         while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 193                                 if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
 194                                 else i += inc;                                                                                  \
 195                                 if (i == last) return h->n_buckets;                                             \
 196                         }                                                                                                                       \
 197                         return __ac_iseither(h->flags, i)? h->n_buckets : i;            \
 198                 } else return 0;                                                                                                \
 199         }                                                                                                                                       \
 200         SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
 201         {                                                                                                                                       \
 202                 khint32_t *new_flags = 0;                                                                               \
 203                 khint_t j = 1;                                                                                                  \
 204                 {                                                                                                                               \
 205                         khint_t t = __ac_HASH_PRIME_SIZE - 1;                                           \
 206                         while (__ac_prime_list[t] > new_n_buckets) --t;                         \
 207                         new_n_buckets = __ac_prime_list[t+1];                                           \
 208                         if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
 209                         else {                                                                                                          \
 210                                 new_flags = (khint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(khint32_t));   \
 211                                 memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
 212                                 if (h->n_buckets < new_n_buckets) {                                             \
 213                                         h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 214                                         if (kh_is_map)                                                                          \
 215                                                 h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 216                                 }                                                                                                               \
 217                         }                                                                                                                       \
 218                 }                                                                                                                               \
 219                 if (j) {                                                                                                                \
 220                         for (j = 0; j != h->n_buckets; ++j) {                                           \
 221                                 if (__ac_iseither(h->flags, j) == 0) {                                  \
 222                                         khkey_t key = h->keys[j];                                                       \
 223                                         khval_t val;                                                                            \
 224                                         if (kh_is_map) val = h->vals[j];                                        \
 225                                         __ac_set_isdel_true(h->flags, j);                                       \
 226                                         while (1) {                                                                                     \
 227                                                 khint_t inc, k, i;                                                              \
 228                                                 k = __hash_func(key);                                                   \
 229                                                 i = k % new_n_buckets;                                                  \
 230                                                 inc = 1 + k % (new_n_buckets - 1);                              \
 231                                                 while (!__ac_isempty(new_flags, i)) {                   \
 232                                                         if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
 233                                                         else i += inc;                                                          \
 234                                                 }                                                                                               \
 235                                                 __ac_set_isempty_false(new_flags, i);                   \
 236                                                 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
 237                                                         { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
 238                                                         if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
 239                                                         __ac_set_isdel_true(h->flags, i);                       \
 240                                                 } else {                                                                                \
 241                                                         h->keys[i] = key;                                                       \
 242                                                         if (kh_is_map) h->vals[i] = val;                        \
 243                                                         break;                                                                          \
 244                                                 }                                                                                               \
 245                                         }                                                                                                       \
 246                                 }                                                                                                               \
 247                         }                                                                                                                       \
 248                         if (h->n_buckets > new_n_buckets) {                                                     \
 249                                 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
 250                                 if (kh_is_map)                                                                                  \
 251                                         h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 252                         }                                                                                                                       \
 253                         free(h->flags);                                                                                         \
 254                         h->flags = new_flags;                                                                           \
 255                         h->n_buckets = new_n_buckets;                                                           \
 256                         h->n_occupied = h->size;                                                                        \
 257                         h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
 258                 }                                                                                                                               \
 259         }                                                                                                                                       \
 260         SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
 261         {                                                                                                                                       \
 262                 khint_t x;                                                                                                              \
 263                 if (h->n_occupied >= h->upper_bound) {                                                  \
 264                         if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
 265                         else kh_resize_##name(h, h->n_buckets + 1);                                     \
 266                 }                                                                                                                               \
 267                 {                                                                                                                               \
 268                         khint_t inc, k, i, site, last;                                                          \
 269                         x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
 270                         if (__ac_isempty(h->flags, i)) x = i;                                           \
 271                         else {                                                                                                          \
 272                                 inc = 1 + k % (h->n_buckets - 1); last = i;                             \
 273                                 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 274                                         if (__ac_isdel(h->flags, i)) site = i;                          \
 275                                         if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
 276                                         else i += inc;                                                                          \
 277                                         if (i == last) { x = site; break; }                                     \
 278                                 }                                                                                                               \
 279                                 if (x == h->n_buckets) {                                                                \
 280                                         if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
 281                                         else x = i;                                                                                     \
 282                                 }                                                                                                               \
 283                         }                                                                                                                       \
 284                 }                                                                                                                               \
 285                 if (__ac_isempty(h->flags, x)) {                                                                \
 286                         h->keys[x] = key;                                                                                       \
 287                         __ac_set_isboth_false(h->flags, x);                                                     \
 288                         ++h->size; ++h->n_occupied;                                                                     \
 289                         *ret = 1;                                                                                                       \
 290                 } else if (__ac_isdel(h->flags, x)) {                                                   \
 291                         h->keys[x] = key;                                                                                       \
 292                         __ac_set_isboth_false(h->flags, x);                                                     \
 293                         ++h->size;                                                                                                      \
 294                         *ret = 2;                                                                                                       \
 295                 } else *ret = 0;                                                                                                \
 296                 return x;                                                                                                               \
 297         }                                                                                                                                       \
 298         SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)                           \
 299         {                                                                                                                                       \
 300                 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {                 \
 301                         __ac_set_isdel_true(h->flags, x);                                                       \
 302                         --h->size;                                                                                                      \
 303                 }                                                                                                                               \
 304         }
 305
 306 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 307         KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
 308
 309 /* --- BEGIN OF HASH FUNCTIONS --- */
 310
 311 /*! @function
 312   @abstract     Integer hash function
 313   @param  key   The integer [khint32_t]
 314   @return       The hash value [khint_t]
 315  */
 316 #define kh_int_hash_func(key) (khint32_t)(key)
 317 /*! @function
 318   @abstract     Integer comparison function
 319  */
 320 #define kh_int_hash_equal(a, b) ((a) == (b))
 321 /*! @function
 322   @abstract     64-bit integer hash function
 323   @param  key   The integer [khint64_t]
 324   @return       The hash value [khint_t]
 325  */
 326 #define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
 327 /*! @function
 328   @abstract     64-bit integer comparison function
 329  */
 330 #define kh_int64_hash_equal(a, b) ((a) == (b))
 331 /*! @function
 332   @abstract     const char* hash function
 333   @param  s     Pointer to a null terminated string
 334   @return       The hash value
 335  */
 336 static inline khint_t __ac_X31_hash_string(const char *s)
 337 {
 338         khint_t h = *s;
 339         if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
 340         return h;
 341 }
 342 /*! @function
 343   @abstract     Another interface to const char* hash function
 344   @param  key   Pointer to a null terminated string [const char*]
 345   @return       The hash value [khint_t]
 346  */
 347 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
 348 /*! @function
 349   @abstract     Const char* comparison function
 350  */
 351 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
 352
 353 /* --- END OF HASH FUNCTIONS --- */
 354
 355 /* Other necessary macros... */
 356
 357 /*!
 358   @abstract Type of the hash table.
 359   @param  name  Name of the hash table [symbol]
 360  */
 361 #define khash_t(name) kh_##name##_t
 362
 363 /*! @function
 364   @abstract     Initiate a hash table.
 365   @param  name  Name of the hash table [symbol]
 366   @return       Pointer to the hash table [khash_t(name)*]
 367  */
 368 #define kh_init(name) kh_init_##name()
 369
 370 /*! @function
 371   @abstract     Destroy a hash table.
 372   @param  name  Name of the hash table [symbol]
 373   @param  h     Pointer to the hash table [khash_t(name)*]
 374  */
 375 #define kh_destroy(name, h) kh_destroy_##name(h)
 376
 377 /*! @function
 378   @abstract     Reset a hash table without deallocating memory.
 379   @param  name  Name of the hash table [symbol]
 380   @param  h     Pointer to the hash table [khash_t(name)*]
 381  */
 382 #define kh_clear(name, h) kh_clear_##name(h)
 383
 384 /*! @function
 385   @abstract     Resize a hash table.
 386   @param  name  Name of the hash table [symbol]
 387   @param  h     Pointer to the hash table [khash_t(name)*]
 388   @param  s     New size [khint_t]
 389  */
 390 #define kh_resize(name, h, s) kh_resize_##name(h, s)
 391
 392 /*! @function
 393   @abstract     Insert a key to the hash table.
 394   @param  name  Name of the hash table [symbol]
 395   @param  h     Pointer to the hash table [khash_t(name)*]
 396   @param  k     Key [type of keys]
 397   @param  r     Extra return code: 0 if the key is present in the hash table;
 398                 1 if the bucket is empty (never used); 2 if the element in
 399                                 the bucket has been deleted [int*]
 400   @return       Iterator to the inserted element [khint_t]
 401  */
 402 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
 403
 404 /*! @function
 405   @abstract     Retrieve a key from the hash table.
 406   @param  name  Name of the hash table [symbol]
 407   @param  h     Pointer to the hash table [khash_t(name)*]
 408   @param  k     Key [type of keys]
 409   @return       Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
 410  */
 411 #define kh_get(name, h, k) kh_get_##name(h, k)
 412
 413 /*! @function
 414   @abstract     Remove a key from 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     Iterator to the element to be deleted [khint_t]
 418  */
 419 #define kh_del(name, h, k) kh_del_##name(h, k)
 420
 421
 422 /*! @function
 423   @abstract     Test whether a bucket contains data.
 424   @param  h     Pointer to the hash table [khash_t(name)*]
 425   @param  x     Iterator to the bucket [khint_t]
 426   @return       1 if containing data; 0 otherwise [int]
 427  */
 428 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
 429
 430 /*! @function
 431   @abstract     Get key given an iterator
 432   @param  h     Pointer to the hash table [khash_t(name)*]
 433   @param  x     Iterator to the bucket [khint_t]
 434   @return       Key [type of keys]
 435  */
 436 #define kh_key(h, x) ((h)->keys[x])
 437
 438 /*! @function
 439   @abstract     Get value given an iterator
 440   @param  h     Pointer to the hash table [khash_t(name)*]
 441   @param  x     Iterator to the bucket [khint_t]
 442   @return       Value [type of values]
 443   @discussion   For hash sets, calling this results in segfault.
 444  */
 445 #define kh_val(h, x) ((h)->vals[x])
 446
 447 /*! @function
 448   @abstract     Alias of kh_val()
 449  */
 450 #define kh_value(h, x) ((h)->vals[x])
 451
 452 /*! @function
 453   @abstract     Get the start iterator
 454   @param  h     Pointer to the hash table [khash_t(name)*]
 455   @return       The start iterator [khint_t]
 456  */
 457 #define kh_begin(h) (khint_t)(0)
 458
 459 /*! @function
 460   @abstract     Get the end iterator
 461   @param  h     Pointer to the hash table [khash_t(name)*]
 462   @return       The end iterator [khint_t]
 463  */
 464 #define kh_end(h) ((h)->n_buckets)
 465
 466 /*! @function
 467   @abstract     Get the number of elements in the hash table
 468   @param  h     Pointer to the hash table [khash_t(name)*]
 469   @return       Number of elements in the hash table [khint_t]
 470  */
 471 #define kh_size(h) ((h)->size)
 472
 473 /*! @function
 474   @abstract     Get the number of buckets in the hash table
 475   @param  h     Pointer to the hash table [khash_t(name)*]
 476   @return       Number of buckets in the hash table [khint_t]
 477  */
 478 #define kh_n_buckets(h) ((h)->n_buckets)
 479
 480 /* More conenient interfaces */
 481
 482 /*! @function
 483   @abstract     Instantiate a hash set containing integer keys
 484   @param  name  Name of the hash table [symbol]
 485  */
 486 #define KHASH_SET_INIT_INT(name)                                                                                \
 487         KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
 488
 489 /*! @function
 490   @abstract     Instantiate a hash map containing integer keys
 491   @param  name  Name of the hash table [symbol]
 492   @param  khval_t  Type of values [type]
 493  */
 494 #define KHASH_MAP_INIT_INT(name, khval_t)                                                               \
 495         KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
 496
 497 /*! @function
 498   @abstract     Instantiate a hash map containing 64-bit integer keys
 499   @param  name  Name of the hash table [symbol]
 500  */
 501 #define KHASH_SET_INIT_INT64(name)                                                                              \
 502         KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
 503
 504 /*! @function
 505   @abstract     Instantiate a hash map containing 64-bit integer keys
 506   @param  name  Name of the hash table [symbol]
 507   @param  khval_t  Type of values [type]
 508  */
 509 #define KHASH_MAP_INIT_INT64(name, khval_t)                                                             \
 510         KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
 511
 512 typedef const char *kh_cstr_t;
 513 /*! @function
 514   @abstract     Instantiate a hash map containing const char* keys
 515   @param  name  Name of the hash table [symbol]
 516  */
 517 #define KHASH_SET_INIT_STR(name)                                                                                \
 518         KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
 519
 520 /*! @function
 521   @abstract     Instantiate a hash map containing const char* keys
 522   @param  name  Name of the hash table [symbol]
 523   @param  khval_t  Type of values [type]
 524  */
 525 #define KHASH_MAP_INIT_STR(name, khval_t)                                                               \
 526         KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
 527
 528 #endif /* __AC_KHASH_H */