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