contrib/libucl/klib/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         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 /* 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 #ifndef kh_unused
 155 # ifdef __GNUC__
 156 #   define kh_unused(x) __attribute__((__unused__)) x
 157 # else
 158 #   define kh_unused(x) x
 159 # endif
 160 #endif
 161
 162 typedef khint32_t khint_t;
 163 typedef khint_t khiter_t;
 164
 165 #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
 166 #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
 167 #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
 168 #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
 169 #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
 170 #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
 171 #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
 172
 173 #define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
 174
 175 #ifndef kroundup32
 176 #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
 177 #endif
 178
 179 #ifndef kcalloc
 180 #define kcalloc(N,Z) calloc(N,Z)
 181 #endif
 182 #ifndef kmalloc
 183 #define kmalloc(Z) malloc(Z)
 184 #endif
 185 #ifndef krealloc
 186 #define krealloc(P,Z) realloc(P,Z)
 187 #endif
 188 #ifndef kfree
 189 #define kfree(P) free(P)
 190 #endif
 191
 192 static const double __ac_HASH_UPPER = 0.77;
 193
 194 #define __KHASH_TYPE(name, khkey_t, khval_t) \
 195         typedef struct kh_##name##_s { \
 196                 khint_t n_buckets, size, n_occupied, upper_bound; \
 197                 khint32_t *flags; \
 198                 khkey_t *keys; \
 199                 khval_t *vals; \
 200         } kh_##name##_t;
 201
 202 #define __KHASH_PROTOTYPES(name, khkey_t, khval_t)                                                      \
 203         extern kh_##name##_t * kh_init_##name(void);                                                    \
 204         extern void kh_destroy_##name(kh_##name##_t *h);                                                \
 205         extern void kh_clear_##name(kh_##name##_t *h);                                                  \
 206         extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key);              \
 207         extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets);   \
 208         extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret);  \
 209         extern void kh_del_##name(kh_##name##_t *h, khint_t x);
 210
 211 #define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 212         SCOPE kh_##name##_t *kh_init_##name(void) {                                                     \
 213                 return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t));               \
 214         }                                                                                                                                       \
 215         SCOPE void kh_destroy_##name(kh_##name##_t *h)                                          \
 216         {                                                                                                                                       \
 217                 if (h) {                                                                                                                \
 218                         kfree((void *)h->keys); kfree(h->flags);                                        \
 219                         kfree((void *)h->vals);                                                                         \
 220                         kfree(h);                                                                                                       \
 221                 }                                                                                                                               \
 222         }                                                                                                                                       \
 223         SCOPE void kh_unused(kh_clear_##name)(kh_##name##_t *h)                         \
 224         {                                                                                                                                       \
 225                 if (h && h->flags) {                                                                                    \
 226                         memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
 227                         h->size = h->n_occupied = 0;                                                            \
 228                 }                                                                                                                               \
 229         }                                                                                                                                       \
 230         SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key)        \
 231         {                                                                                                                                       \
 232                 if (h->n_buckets) {                                                                                             \
 233                         khint_t k, i, last, mask, step = 0; \
 234                         mask = h->n_buckets - 1;                                                                        \
 235                         k = __hash_func(key); i = k & mask;                                                     \
 236                         last = i; \
 237                         while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 238                                 i = (i + (++step)) & mask; \
 239                                 if (i == last) return h->n_buckets;                                             \
 240                         }                                                                                                                       \
 241                         return __ac_iseither(h->flags, i)? h->n_buckets : i;            \
 242                 } else return 0;                                                                                                \
 243         }                                                                                                                                       \
 244         SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
 245         { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
 246                 khint32_t *new_flags = 0;                                                                               \
 247                 khint_t j = 1;                                                                                                  \
 248                 {                                                                                                                               \
 249                         kroundup32(new_n_buckets);                                                                      \
 250                         if (new_n_buckets < 4) new_n_buckets = 4;                                       \
 251                         if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \
 252                         else { /* hash table size to be changed (shrink or expand); rehash */ \
 253                                 new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
 254                                 if (!new_flags) return -1;                                                              \
 255                                 memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
 256                                 if (h->n_buckets < new_n_buckets) {     /* expand */            \
 257                                         khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
 258                                         if (!new_keys) { kfree(new_flags); return -1; }         \
 259                                         h->keys = new_keys;                                                                     \
 260                                         if (kh_is_map) {                                                                        \
 261                                                 khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
 262                                                 if (!new_vals) { kfree(new_flags); return -1; } \
 263                                                 h->vals = new_vals;                                                             \
 264                                         }                                                                                                       \
 265                                 } /* otherwise shrink */                                                                \
 266                         }                                                                                                                       \
 267                 }                                                                                                                               \
 268                 if (j) { /* rehashing is needed */                                                              \
 269                         for (j = 0; j != h->n_buckets; ++j) {                                           \
 270                                 if (__ac_iseither(h->flags, j) == 0) {                                  \
 271                                         khkey_t key = h->keys[j];                                                       \
 272                                         khval_t val;                                                                            \
 273                                         khint_t new_mask;                                                                       \
 274                                         new_mask = new_n_buckets - 1;                                           \
 275                                         if (kh_is_map) val = h->vals[j];                                        \
 276                                         __ac_set_isdel_true(h->flags, j);                                       \
 277                                         while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
 278                                                 khint_t k, i, step = 0; \
 279                                                 k = __hash_func(key);                                                   \
 280                                                 i = k & new_mask;                                                               \
 281                                                 while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \
 282                                                 __ac_set_isempty_false(new_flags, i);                   \
 283                                                 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
 284                                                         { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
 285                                                         if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
 286                                                         __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
 287                                                 } else { /* write the element and jump out of the loop */ \
 288                                                         h->keys[i] = key;                                                       \
 289                                                         if (kh_is_map) h->vals[i] = val;                        \
 290                                                         break;                                                                          \
 291                                                 }                                                                                               \
 292                                         }                                                                                                       \
 293                                 }                                                                                                               \
 294                         }                                                                                                                       \
 295                         if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
 296                                 h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
 297                                 if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
 298                         }                                                                                                                       \
 299                         kfree(h->flags); /* free the working space */                           \
 300                         h->flags = new_flags;                                                                           \
 301                         h->n_buckets = new_n_buckets;                                                           \
 302                         h->n_occupied = h->size;                                                                        \
 303                         h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
 304                 }                                                                                                                               \
 305                 return 0;                                                                                                               \
 306         }                                                                                                                                       \
 307         SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
 308         {                                                                                                                                       \
 309                 khint_t x;                                                                                                              \
 310                 if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
 311                         if (h->n_buckets > (h->size<<1)) {                                                      \
 312                                 if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
 313                                         *ret = -1; return h->n_buckets;                                         \
 314                                 }                                                                                                               \
 315                         } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
 316                                 *ret = -1; return h->n_buckets;                                                 \
 317                         }                                                                                                                       \
 318                 } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
 319                 {                                                                                                                               \
 320                         khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \
 321                         x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
 322                         if (__ac_isempty(h->flags, i)) x = i; /* for speed up */        \
 323                         else {                                                                                                          \
 324                                 last = i; \
 325                                 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
 326                                         if (__ac_isdel(h->flags, i)) site = i;                          \
 327                                         i = (i + (++step)) & mask; \
 328                                         if (i == last) { x = site; break; }                                     \
 329                                 }                                                                                                               \
 330                                 if (x == h->n_buckets) {                                                                \
 331                                         if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
 332                                         else x = i;                                                                                     \
 333                                 }                                                                                                               \
 334                         }                                                                                                                       \
 335                 }                                                                                                                               \
 336                 if (__ac_isempty(h->flags, x)) { /* not present at all */               \
 337                         h->keys[x] = key;                                                                                       \
 338                         __ac_set_isboth_false(h->flags, x);                                                     \
 339                         ++h->size; ++h->n_occupied;                                                                     \
 340                         *ret = 1;                                                                                                       \
 341                 } else if (__ac_isdel(h->flags, x)) { /* deleted */                             \
 342                         h->keys[x] = key;                                                                                       \
 343                         __ac_set_isboth_false(h->flags, x);                                                     \
 344                         ++h->size;                                                                                                      \
 345                         *ret = 2;                                                                                                       \
 346                 } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
 347                 return x;                                                                                                               \
 348         }                                                                                                                                       \
 349         SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)                           \
 350         {                                                                                                                                       \
 351                 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) {                 \
 352                         __ac_set_isdel_true(h->flags, x);                                                       \
 353                         --h->size;                                                                                                      \
 354                 }                                                                                                                               \
 355         }
 356
 357 #define KHASH_DECLARE(name, khkey_t, khval_t)                                                   \
 358         __KHASH_TYPE(name, khkey_t, khval_t)                                                            \
 359         __KHASH_PROTOTYPES(name, khkey_t, khval_t)
 360
 361 #define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 362         __KHASH_TYPE(name, khkey_t, khval_t)                                                            \
 363         __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
 364
 365 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 366         KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
 367
 368 /* --- BEGIN OF HASH FUNCTIONS --- */
 369
 370 /*! @function
 371   @abstract     Integer hash function
 372   @param  key   The integer [khint32_t]
 373   @return       The hash value [khint_t]
 374  */
 375 #define kh_int_hash_func(key) (khint32_t)(key)
 376 /*! @function
 377   @abstract     Integer comparison function
 378  */
 379 #define kh_int_hash_equal(a, b) ((a) == (b))
 380 /*! @function
 381   @abstract     64-bit integer hash function
 382   @param  key   The integer [khint64_t]
 383   @return       The hash value [khint_t]
 384  */
 385 #define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
 386 /*! @function
 387   @abstract     64-bit integer comparison function
 388  */
 389 #define kh_int64_hash_equal(a, b) ((a) == (b))
 390 /*! @function
 391   @abstract     const char* hash function
 392   @param  s     Pointer to a null terminated string
 393   @return       The hash value
 394  */
 395 static kh_inline khint_t __ac_X31_hash_string(const char *s)
 396 {
 397         khint_t h = (khint_t)*s;
 398         if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;
 399         return h;
 400 }
 401 /*! @function
 402   @abstract     Another interface to const char* hash function
 403   @param  key   Pointer to a null terminated string [const char*]
 404   @return       The hash value [khint_t]
 405  */
 406 #define kh_str_hash_func(key) __ac_X31_hash_string(key)
 407 /*! @function
 408   @abstract     Const char* comparison function
 409  */
 410 #define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
 411
 412 static kh_inline khint_t __ac_Wang_hash(khint_t key)
 413 {
 414     key += ~(key << 15);
 415     key ^=  (key >> 10);
 416     key +=  (key << 3);
 417     key ^=  (key >> 6);
 418     key += ~(key << 11);
 419     key ^=  (key >> 16);
 420     return key;
 421 }
 422 #define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
 423
 424 /* --- END OF HASH FUNCTIONS --- */
 425
 426 /* Other convenient macros... */
 427
 428 /*!
 429   @abstract Type of the hash table.
 430   @param  name  Name of the hash table [symbol]
 431  */
 432 #define khash_t(name) kh_##name##_t
 433
 434 /*! @function
 435   @abstract     Initiate a hash table.
 436   @param  name  Name of the hash table [symbol]
 437   @return       Pointer to the hash table [khash_t(name)*]
 438  */
 439 #define kh_init(name) kh_init_##name()
 440
 441 /*! @function
 442   @abstract     Destroy a hash table.
 443   @param  name  Name of the hash table [symbol]
 444   @param  h     Pointer to the hash table [khash_t(name)*]
 445  */
 446 #define kh_destroy(name, h) kh_destroy_##name(h)
 447
 448 /*! @function
 449   @abstract     Reset a hash table without deallocating memory.
 450   @param  name  Name of the hash table [symbol]
 451   @param  h     Pointer to the hash table [khash_t(name)*]
 452  */
 453 #define kh_clear(name, h) kh_clear_##name(h)
 454
 455 /*! @function
 456   @abstract     Resize a hash table.
 457   @param  name  Name of the hash table [symbol]
 458   @param  h     Pointer to the hash table [khash_t(name)*]
 459   @param  s     New size [khint_t]
 460  */
 461 #define kh_resize(name, h, s) kh_resize_##name(h, s)
 462
 463 /*! @function
 464   @abstract     Insert a key to the hash table.
 465   @param  name  Name of the hash table [symbol]
 466   @param  h     Pointer to the hash table [khash_t(name)*]
 467   @param  k     Key [type of keys]
 468   @param  r     Extra return code: -1 if the operation failed;
 469                 0 if the key is present in the hash table;
 470                 1 if the bucket is empty (never used); 2 if the element in
 471                                 the bucket has been deleted [int*]
 472   @return       Iterator to the inserted element [khint_t]
 473  */
 474 #define kh_put(name, h, k, r) kh_put_##name(h, k, r)
 475
 476 /*! @function
 477   @abstract     Retrieve a key from the hash table.
 478   @param  name  Name of the hash table [symbol]
 479   @param  h     Pointer to the hash table [khash_t(name)*]
 480   @param  k     Key [type of keys]
 481   @return       Iterator to the found element, or kh_end(h) if the element is absent [khint_t]
 482  */
 483 #define kh_get(name, h, k) kh_get_##name(h, k)
 484
 485 /*! @function
 486   @abstract     Remove a key from the hash table.
 487   @param  name  Name of the hash table [symbol]
 488   @param  h     Pointer to the hash table [khash_t(name)*]
 489   @param  k     Iterator to the element to be deleted [khint_t]
 490  */
 491 #define kh_del(name, h, k) kh_del_##name(h, k)
 492
 493 /*! @function
 494   @abstract     Test whether a bucket contains data.
 495   @param  h     Pointer to the hash table [khash_t(name)*]
 496   @param  x     Iterator to the bucket [khint_t]
 497   @return       1 if containing data; 0 otherwise [int]
 498  */
 499 #define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
 500
 501 /*! @function
 502   @abstract     Get key 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       Key [type of keys]
 506  */
 507 #define kh_key(h, x) ((h)->keys[x])
 508
 509 /*! @function
 510   @abstract     Get value given an iterator
 511   @param  h     Pointer to the hash table [khash_t(name)*]
 512   @param  x     Iterator to the bucket [khint_t]
 513   @return       Value [type of values]
 514   @discussion   For hash sets, calling this results in segfault.
 515  */
 516 #define kh_val(h, x) ((h)->vals[x])
 517
 518 /*! @function
 519   @abstract     Alias of kh_val()
 520  */
 521 #define kh_value(h, x) ((h)->vals[x])
 522
 523 /*! @function
 524   @abstract     Get the start iterator
 525   @param  h     Pointer to the hash table [khash_t(name)*]
 526   @return       The start iterator [khint_t]
 527  */
 528 #define kh_begin(h) (khint_t)(0)
 529
 530 /*! @function
 531   @abstract     Get the end iterator
 532   @param  h     Pointer to the hash table [khash_t(name)*]
 533   @return       The end iterator [khint_t]
 534  */
 535 #define kh_end(h) ((h)->n_buckets)
 536
 537 /*! @function
 538   @abstract     Get the number of elements in the hash table
 539   @param  h     Pointer to the hash table [khash_t(name)*]
 540   @return       Number of elements in the hash table [khint_t]
 541  */
 542 #define kh_size(h) ((h)->size)
 543
 544 /*! @function
 545   @abstract     Get the number of buckets in the hash table
 546   @param  h     Pointer to the hash table [khash_t(name)*]
 547   @return       Number of buckets in the hash table [khint_t]
 548  */
 549 #define kh_n_buckets(h) ((h)->n_buckets)
 550
 551 /*! @function
 552   @abstract     Iterate over the entries in the hash table
 553   @param  h     Pointer to the hash table [khash_t(name)*]
 554   @param  kvar  Variable to which key will be assigned
 555   @param  vvar  Variable to which value will be assigned
 556   @param  code  Block of code to execute
 557  */
 558 #define kh_foreach(h, kvar, vvar, code) { khint_t __i;          \
 559         for (__i = kh_begin(h); __i != kh_end(h); ++__i) {              \
 560                 if (!kh_exist(h,__i)) continue;                                         \
 561                 (kvar) = kh_key(h,__i);                                                         \
 562                 (vvar) = kh_val(h,__i);                                                         \
 563                 code;                                                                                           \
 564         } }
 565
 566 /*! @function
 567   @abstract     Iterate over the values in the hash table
 568   @param  h     Pointer to the hash table [khash_t(name)*]
 569   @param  vvar  Variable to which value will be assigned
 570   @param  code  Block of code to execute
 571  */
 572 #define kh_foreach_value(h, vvar, code) { khint_t __i;          \
 573         for (__i = kh_begin(h); __i != kh_end(h); ++__i) {              \
 574                 if (!kh_exist(h,__i)) continue;                                         \
 575                 (vvar) = kh_val(h,__i);                                                         \
 576                 code;                                                                                           \
 577         } }
 578
 579 /* More conenient interfaces */
 580
 581 /*! @function
 582   @abstract     Instantiate a hash set containing integer keys
 583   @param  name  Name of the hash table [symbol]
 584  */
 585 #define KHASH_SET_INIT_INT(name)                                                                                \
 586         KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
 587
 588 /*! @function
 589   @abstract     Instantiate a hash map containing integer keys
 590   @param  name  Name of the hash table [symbol]
 591   @param  khval_t  Type of values [type]
 592  */
 593 #define KHASH_MAP_INIT_INT(name, khval_t)                                                               \
 594         KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
 595
 596 /*! @function
 597   @abstract     Instantiate a hash map containing 64-bit integer keys
 598   @param  name  Name of the hash table [symbol]
 599  */
 600 #define KHASH_SET_INIT_INT64(name)                                                                              \
 601         KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
 602
 603 /*! @function
 604   @abstract     Instantiate a hash map containing 64-bit integer keys
 605   @param  name  Name of the hash table [symbol]
 606   @param  khval_t  Type of values [type]
 607  */
 608 #define KHASH_MAP_INIT_INT64(name, khval_t)                                                             \
 609         KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
 610
 611 typedef const char *kh_cstr_t;
 612 /*! @function
 613   @abstract     Instantiate a hash map containing const char* keys
 614   @param  name  Name of the hash table [symbol]
 615  */
 616 #define KHASH_SET_INIT_STR(name)                                                                                \
 617         KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
 618
 619 /*! @function
 620   @abstract     Instantiate a hash map containing const char* keys
 621   @param  name  Name of the hash table [symbol]
 622   @param  khval_t  Type of values [type]
 623  */
 624 #define KHASH_MAP_INIT_STR(name, khval_t)                                                               \
 625         KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
 626
 627 #endif /* __AC_KHASH_H */