1279546Sbapt/* The MIT License 2279546Sbapt 3279546Sbapt Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk> 4279546Sbapt 5279546Sbapt Permission is hereby granted, free of charge, to any person obtaining 6279546Sbapt a copy of this software and associated documentation files (the 7279546Sbapt "Software"), to deal in the Software without restriction, including 8279546Sbapt without limitation the rights to use, copy, modify, merge, publish, 9279546Sbapt distribute, sublicense, and/or sell copies of the Software, and to 10279546Sbapt permit persons to whom the Software is furnished to do so, subject to 11279546Sbapt the following conditions: 12279546Sbapt 13279546Sbapt The above copyright notice and this permission notice shall be 14279546Sbapt included in all copies or substantial portions of the Software. 15279546Sbapt 16279546Sbapt THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 17279546Sbapt EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 18279546Sbapt MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 19279546Sbapt NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 20279546Sbapt BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 21279546Sbapt ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 22279546Sbapt CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23279546Sbapt SOFTWARE. 24279546Sbapt*/ 25279546Sbapt 26279546Sbapt/* 27279546Sbapt An example: 28279546Sbapt 29279546Sbapt#include "khash.h" 30279546SbaptKHASH_MAP_INIT_INT(32, char) 31279546Sbaptint main() { 32279546Sbapt int ret, is_missing; 33279546Sbapt khiter_t k; 34279546Sbapt khash_t(32) *h = kh_init(32); 35279546Sbapt k = kh_put(32, h, 5, &ret); 36279546Sbapt kh_value(h, k) = 10; 37279546Sbapt k = kh_get(32, h, 10); 38279546Sbapt is_missing = (k == kh_end(h)); 39279546Sbapt k = kh_get(32, h, 5); 40279546Sbapt kh_del(32, h, k); 41279546Sbapt for (k = kh_begin(h); k != kh_end(h); ++k) 42279546Sbapt if (kh_exist(h, k)) kh_value(h, k) = 1; 43279546Sbapt kh_destroy(32, h); 44279546Sbapt return 0; 45279546Sbapt} 46279546Sbapt*/ 47279546Sbapt 48279546Sbapt/* 49279546Sbapt 2013-05-02 (0.2.8): 50279546Sbapt 51279546Sbapt * Use quadratic probing. When the capacity is power of 2, stepping function 52279546Sbapt i*(i+1)/2 guarantees to traverse each bucket. It is better than double 53279546Sbapt hashing on cache performance and is more robust than linear probing. 54279546Sbapt 55279546Sbapt In theory, double hashing should be more robust than quadratic probing. 56279546Sbapt However, my implementation is probably not for large hash tables, because 57279546Sbapt the second hash function is closely tied to the first hash function, 58279546Sbapt which reduce the effectiveness of double hashing. 59279546Sbapt 60279546Sbapt Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php 61279546Sbapt 62279546Sbapt 2011-12-29 (0.2.7): 63279546Sbapt 64279546Sbapt * Minor code clean up; no actual effect. 65279546Sbapt 66279546Sbapt 2011-09-16 (0.2.6): 67279546Sbapt 68279546Sbapt * The capacity is a power of 2. This seems to dramatically improve the 69279546Sbapt speed for simple keys. Thank Zilong Tan for the suggestion. Reference: 70279546Sbapt 71279546Sbapt - http://code.google.com/p/ulib/ 72279546Sbapt - http://nothings.org/computer/judy/ 73279546Sbapt 74279546Sbapt * Allow to optionally use linear probing which usually has better 75279546Sbapt performance for random input. Double hashing is still the default as it 76279546Sbapt is more robust to certain non-random input. 77279546Sbapt 78279546Sbapt * Added Wang's integer hash function (not used by default). This hash 79279546Sbapt function is more robust to certain non-random input. 80279546Sbapt 81279546Sbapt 2011-02-14 (0.2.5): 82279546Sbapt 83279546Sbapt * Allow to declare global functions. 84279546Sbapt 85279546Sbapt 2009-09-26 (0.2.4): 86279546Sbapt 87279546Sbapt * Improve portability 88279546Sbapt 89279546Sbapt 2008-09-19 (0.2.3): 90279546Sbapt 91279546Sbapt * Corrected the example 92279546Sbapt * Improved interfaces 93279546Sbapt 94279546Sbapt 2008-09-11 (0.2.2): 95279546Sbapt 96279546Sbapt * Improved speed a little in kh_put() 97279546Sbapt 98279546Sbapt 2008-09-10 (0.2.1): 99279546Sbapt 100279546Sbapt * Added kh_clear() 101279546Sbapt * Fixed a compiling error 102279546Sbapt 103279546Sbapt 2008-09-02 (0.2.0): 104279546Sbapt 105279546Sbapt * Changed to token concatenation which increases flexibility. 106279546Sbapt 107279546Sbapt 2008-08-31 (0.1.2): 108279546Sbapt 109279546Sbapt * Fixed a bug in kh_get(), which has not been tested previously. 110279546Sbapt 111279546Sbapt 2008-08-31 (0.1.1): 112279546Sbapt 113279546Sbapt * Added destructor 114279546Sbapt*/ 115279546Sbapt 116279546Sbapt 117279546Sbapt#ifndef __AC_KHASH_H 118279546Sbapt#define __AC_KHASH_H 119279546Sbapt 120279546Sbapt/*! 121279546Sbapt @header 122279546Sbapt 123279546Sbapt Generic hash table library. 124279546Sbapt */ 125279546Sbapt 126279546Sbapt#define AC_VERSION_KHASH_H "0.2.8" 127279546Sbapt 128279546Sbapt#include <stdlib.h> 129279546Sbapt#include <string.h> 130279546Sbapt#include <limits.h> 131279546Sbapt 132279546Sbapt/* compiler specific configuration */ 133279546Sbapt 134279546Sbapt#if UINT_MAX == 0xffffffffu 135279546Sbapttypedef unsigned int khint32_t; 136279546Sbapt#elif ULONG_MAX == 0xffffffffu 137279546Sbapttypedef unsigned long khint32_t; 138279546Sbapt#endif 139279546Sbapt 140279546Sbapt#if ULONG_MAX == ULLONG_MAX 141279546Sbapttypedef unsigned long khint64_t; 142279546Sbapt#else 143279546Sbapttypedef unsigned long long khint64_t; 144279546Sbapt#endif 145279546Sbapt 146279546Sbapt#ifndef kh_inline 147279546Sbapt#ifdef _MSC_VER 148279546Sbapt#define kh_inline __inline 149279546Sbapt#else 150279546Sbapt#define kh_inline inline 151279546Sbapt#endif 152279546Sbapt#endif /* kh_inline */ 153279546Sbapt 154279546Sbapt#ifndef kh_unused 155279546Sbapt# ifdef __GNUC__ 156279546Sbapt# define kh_unused(x) __attribute__((__unused__)) x 157279546Sbapt# else 158279546Sbapt# define kh_unused(x) x 159279546Sbapt# endif 160279546Sbapt#endif 161279546Sbapt 162279546Sbapttypedef khint32_t khint_t; 163279546Sbapttypedef khint_t khiter_t; 164279546Sbapt 165279546Sbapt#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) 166279546Sbapt#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) 167279546Sbapt#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) 168279546Sbapt#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1))) 169279546Sbapt#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1))) 170279546Sbapt#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1))) 171279546Sbapt#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1)) 172279546Sbapt 173279546Sbapt#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) 174279546Sbapt 175279546Sbapt#ifndef kroundup32 176279546Sbapt#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) 177279546Sbapt#endif 178279546Sbapt 179279546Sbapt#ifndef kcalloc 180279546Sbapt#define kcalloc(N,Z) calloc(N,Z) 181279546Sbapt#endif 182279546Sbapt#ifndef kmalloc 183279546Sbapt#define kmalloc(Z) malloc(Z) 184279546Sbapt#endif 185279546Sbapt#ifndef krealloc 186279546Sbapt#define krealloc(P,Z) realloc(P,Z) 187279546Sbapt#endif 188279546Sbapt#ifndef kfree 189279546Sbapt#define kfree(P) free(P) 190279546Sbapt#endif 191279546Sbapt 192279546Sbaptstatic const double __ac_HASH_UPPER = 0.77; 193279546Sbapt 194279546Sbapt#define __KHASH_TYPE(name, khkey_t, khval_t) \ 195279546Sbapt typedef struct kh_##name##_s { \ 196279546Sbapt khint_t n_buckets, size, n_occupied, upper_bound; \ 197279546Sbapt khint32_t *flags; \ 198279546Sbapt khkey_t *keys; \ 199279546Sbapt khval_t *vals; \ 200279546Sbapt } kh_##name##_t; 201279546Sbapt 202279546Sbapt#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ 203279546Sbapt extern kh_##name##_t * kh_init_##name(void); \ 204279546Sbapt extern void kh_destroy_##name(kh_##name##_t *h); \ 205279546Sbapt extern void kh_clear_##name(kh_##name##_t *h); \ 206279546Sbapt extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ 207279546Sbapt extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ 208279546Sbapt extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ 209279546Sbapt extern void kh_del_##name(kh_##name##_t *h, khint_t x); 210279546Sbapt 211279546Sbapt#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ 212279546Sbapt SCOPE kh_##name##_t *kh_init_##name(void) { \ 213279546Sbapt return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ 214279546Sbapt } \ 215279546Sbapt SCOPE void kh_destroy_##name(kh_##name##_t *h) \ 216279546Sbapt { \ 217279546Sbapt if (h) { \ 218279546Sbapt kfree((void *)h->keys); kfree(h->flags); \ 219279546Sbapt kfree((void *)h->vals); \ 220279546Sbapt kfree(h); \ 221279546Sbapt } \ 222279546Sbapt } \ 223279546Sbapt SCOPE void kh_unused(kh_clear_##name)(kh_##name##_t *h) \ 224279546Sbapt { \ 225279546Sbapt if (h && h->flags) { \ 226279546Sbapt memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ 227279546Sbapt h->size = h->n_occupied = 0; \ 228279546Sbapt } \ 229279546Sbapt } \ 230279546Sbapt SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ 231279546Sbapt { \ 232279546Sbapt if (h->n_buckets) { \ 233279546Sbapt khint_t k, i, last, mask, step = 0; \ 234279546Sbapt mask = h->n_buckets - 1; \ 235279546Sbapt k = __hash_func(key); i = k & mask; \ 236279546Sbapt last = i; \ 237279546Sbapt while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ 238279546Sbapt i = (i + (++step)) & mask; \ 239279546Sbapt if (i == last) return h->n_buckets; \ 240279546Sbapt } \ 241279546Sbapt return __ac_iseither(h->flags, i)? h->n_buckets : i; \ 242279546Sbapt } else return 0; \ 243279546Sbapt } \ 244279546Sbapt SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ 245279546Sbapt { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ 246279546Sbapt khint32_t *new_flags = 0; \ 247279546Sbapt khint_t j = 1; \ 248279546Sbapt { \ 249279546Sbapt kroundup32(new_n_buckets); \ 250279546Sbapt if (new_n_buckets < 4) new_n_buckets = 4; \ 251279546Sbapt if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ 252279546Sbapt else { /* hash table size to be changed (shrink or expand); rehash */ \ 253279546Sbapt new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ 254279546Sbapt if (!new_flags) return -1; \ 255279546Sbapt memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ 256279546Sbapt if (h->n_buckets < new_n_buckets) { /* expand */ \ 257279546Sbapt khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ 258279546Sbapt if (!new_keys) { kfree(new_flags); return -1; } \ 259279546Sbapt h->keys = new_keys; \ 260279546Sbapt if (kh_is_map) { \ 261279546Sbapt khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ 262279546Sbapt if (!new_vals) { kfree(new_flags); return -1; } \ 263279546Sbapt h->vals = new_vals; \ 264279546Sbapt } \ 265279546Sbapt } /* otherwise shrink */ \ 266279546Sbapt } \ 267279546Sbapt } \ 268279546Sbapt if (j) { /* rehashing is needed */ \ 269279546Sbapt for (j = 0; j != h->n_buckets; ++j) { \ 270279546Sbapt if (__ac_iseither(h->flags, j) == 0) { \ 271279546Sbapt khkey_t key = h->keys[j]; \ 272279546Sbapt khval_t val; \ 273279546Sbapt khint_t new_mask; \ 274279546Sbapt new_mask = new_n_buckets - 1; \ 275279546Sbapt if (kh_is_map) val = h->vals[j]; \ 276279546Sbapt __ac_set_isdel_true(h->flags, j); \ 277279546Sbapt while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ 278279546Sbapt khint_t k, i, step = 0; \ 279279546Sbapt k = __hash_func(key); \ 280279546Sbapt i = k & new_mask; \ 281279546Sbapt while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ 282279546Sbapt __ac_set_isempty_false(new_flags, i); \ 283279546Sbapt if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ 284279546Sbapt { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ 285279546Sbapt if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ 286279546Sbapt __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ 287279546Sbapt } else { /* write the element and jump out of the loop */ \ 288279546Sbapt h->keys[i] = key; \ 289279546Sbapt if (kh_is_map) h->vals[i] = val; \ 290279546Sbapt break; \ 291279546Sbapt } \ 292279546Sbapt } \ 293279546Sbapt } \ 294279546Sbapt } \ 295279546Sbapt if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ 296279546Sbapt h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ 297279546Sbapt if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ 298279546Sbapt } \ 299279546Sbapt kfree(h->flags); /* free the working space */ \ 300279546Sbapt h->flags = new_flags; \ 301279546Sbapt h->n_buckets = new_n_buckets; \ 302279546Sbapt h->n_occupied = h->size; \ 303279546Sbapt h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ 304279546Sbapt } \ 305279546Sbapt return 0; \ 306279546Sbapt } \ 307279546Sbapt SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ 308279546Sbapt { \ 309279546Sbapt khint_t x; \ 310279546Sbapt if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ 311279546Sbapt if (h->n_buckets > (h->size<<1)) { \ 312279546Sbapt if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ 313279546Sbapt *ret = -1; return h->n_buckets; \ 314279546Sbapt } \ 315279546Sbapt } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ 316279546Sbapt *ret = -1; return h->n_buckets; \ 317279546Sbapt } \ 318279546Sbapt } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ 319279546Sbapt { \ 320279546Sbapt khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ 321279546Sbapt x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ 322279546Sbapt if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ 323279546Sbapt else { \ 324279546Sbapt last = i; \ 325279546Sbapt while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ 326279546Sbapt if (__ac_isdel(h->flags, i)) site = i; \ 327279546Sbapt i = (i + (++step)) & mask; \ 328279546Sbapt if (i == last) { x = site; break; } \ 329279546Sbapt } \ 330279546Sbapt if (x == h->n_buckets) { \ 331279546Sbapt if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ 332279546Sbapt else x = i; \ 333279546Sbapt } \ 334279546Sbapt } \ 335279546Sbapt } \ 336279546Sbapt if (__ac_isempty(h->flags, x)) { /* not present at all */ \ 337279546Sbapt h->keys[x] = key; \ 338279546Sbapt __ac_set_isboth_false(h->flags, x); \ 339279546Sbapt ++h->size; ++h->n_occupied; \ 340279546Sbapt *ret = 1; \ 341279546Sbapt } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ 342279546Sbapt h->keys[x] = key; \ 343279546Sbapt __ac_set_isboth_false(h->flags, x); \ 344279546Sbapt ++h->size; \ 345279546Sbapt *ret = 2; \ 346279546Sbapt } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ 347279546Sbapt return x; \ 348279546Sbapt } \ 349279546Sbapt SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ 350279546Sbapt { \ 351279546Sbapt if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ 352279546Sbapt __ac_set_isdel_true(h->flags, x); \ 353279546Sbapt --h->size; \ 354279546Sbapt } \ 355279546Sbapt } 356279546Sbapt 357279546Sbapt#define KHASH_DECLARE(name, khkey_t, khval_t) \ 358279546Sbapt __KHASH_TYPE(name, khkey_t, khval_t) \ 359279546Sbapt __KHASH_PROTOTYPES(name, khkey_t, khval_t) 360279546Sbapt 361279546Sbapt#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ 362279546Sbapt __KHASH_TYPE(name, khkey_t, khval_t) \ 363279546Sbapt __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) 364279546Sbapt 365279546Sbapt#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ 366279546Sbapt KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) 367279546Sbapt 368279546Sbapt/* --- BEGIN OF HASH FUNCTIONS --- */ 369279546Sbapt 370279546Sbapt/*! @function 371279546Sbapt @abstract Integer hash function 372279546Sbapt @param key The integer [khint32_t] 373279546Sbapt @return The hash value [khint_t] 374279546Sbapt */ 375279546Sbapt#define kh_int_hash_func(key) (khint32_t)(key) 376279546Sbapt/*! @function 377279546Sbapt @abstract Integer comparison function 378279546Sbapt */ 379279546Sbapt#define kh_int_hash_equal(a, b) ((a) == (b)) 380279546Sbapt/*! @function 381279546Sbapt @abstract 64-bit integer hash function 382279546Sbapt @param key The integer [khint64_t] 383279546Sbapt @return The hash value [khint_t] 384279546Sbapt */ 385279546Sbapt#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) 386279546Sbapt/*! @function 387279546Sbapt @abstract 64-bit integer comparison function 388279546Sbapt */ 389279546Sbapt#define kh_int64_hash_equal(a, b) ((a) == (b)) 390279546Sbapt/*! @function 391279546Sbapt @abstract const char* hash function 392279546Sbapt @param s Pointer to a null terminated string 393279546Sbapt @return The hash value 394279546Sbapt */ 395279546Sbaptstatic kh_inline khint_t __ac_X31_hash_string(const char *s) 396279546Sbapt{ 397279546Sbapt khint_t h = (khint_t)*s; 398279546Sbapt if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; 399279546Sbapt return h; 400279546Sbapt} 401279546Sbapt/*! @function 402279546Sbapt @abstract Another interface to const char* hash function 403279546Sbapt @param key Pointer to a null terminated string [const char*] 404279546Sbapt @return The hash value [khint_t] 405279546Sbapt */ 406279546Sbapt#define kh_str_hash_func(key) __ac_X31_hash_string(key) 407279546Sbapt/*! @function 408279546Sbapt @abstract Const char* comparison function 409279546Sbapt */ 410279546Sbapt#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) 411279546Sbapt 412279546Sbaptstatic kh_inline khint_t __ac_Wang_hash(khint_t key) 413279546Sbapt{ 414279546Sbapt key += ~(key << 15); 415279546Sbapt key ^= (key >> 10); 416279546Sbapt key += (key << 3); 417279546Sbapt key ^= (key >> 6); 418279546Sbapt key += ~(key << 11); 419279546Sbapt key ^= (key >> 16); 420279546Sbapt return key; 421279546Sbapt} 422279546Sbapt#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key) 423279546Sbapt 424279546Sbapt/* --- END OF HASH FUNCTIONS --- */ 425279546Sbapt 426279546Sbapt/* Other convenient macros... */ 427279546Sbapt 428279546Sbapt/*! 429279546Sbapt @abstract Type of the hash table. 430279546Sbapt @param name Name of the hash table [symbol] 431279546Sbapt */ 432279546Sbapt#define khash_t(name) kh_##name##_t 433279546Sbapt 434279546Sbapt/*! @function 435279546Sbapt @abstract Initiate a hash table. 436279546Sbapt @param name Name of the hash table [symbol] 437279546Sbapt @return Pointer to the hash table [khash_t(name)*] 438279546Sbapt */ 439279546Sbapt#define kh_init(name) kh_init_##name() 440279546Sbapt 441279546Sbapt/*! @function 442279546Sbapt @abstract Destroy a hash table. 443279546Sbapt @param name Name of the hash table [symbol] 444279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 445279546Sbapt */ 446279546Sbapt#define kh_destroy(name, h) kh_destroy_##name(h) 447279546Sbapt 448279546Sbapt/*! @function 449279546Sbapt @abstract Reset a hash table without deallocating memory. 450279546Sbapt @param name Name of the hash table [symbol] 451279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 452279546Sbapt */ 453279546Sbapt#define kh_clear(name, h) kh_clear_##name(h) 454279546Sbapt 455279546Sbapt/*! @function 456279546Sbapt @abstract Resize a hash table. 457279546Sbapt @param name Name of the hash table [symbol] 458279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 459279546Sbapt @param s New size [khint_t] 460279546Sbapt */ 461279546Sbapt#define kh_resize(name, h, s) kh_resize_##name(h, s) 462279546Sbapt 463279546Sbapt/*! @function 464279546Sbapt @abstract Insert a key to the hash table. 465279546Sbapt @param name Name of the hash table [symbol] 466279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 467279546Sbapt @param k Key [type of keys] 468279546Sbapt @param r Extra return code: -1 if the operation failed; 469279546Sbapt 0 if the key is present in the hash table; 470279546Sbapt 1 if the bucket is empty (never used); 2 if the element in 471279546Sbapt the bucket has been deleted [int*] 472279546Sbapt @return Iterator to the inserted element [khint_t] 473279546Sbapt */ 474279546Sbapt#define kh_put(name, h, k, r) kh_put_##name(h, k, r) 475279546Sbapt 476279546Sbapt/*! @function 477279546Sbapt @abstract Retrieve a key from the hash table. 478279546Sbapt @param name Name of the hash table [symbol] 479279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 480279546Sbapt @param k Key [type of keys] 481279546Sbapt @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] 482279546Sbapt */ 483279546Sbapt#define kh_get(name, h, k) kh_get_##name(h, k) 484279546Sbapt 485279546Sbapt/*! @function 486279546Sbapt @abstract Remove a key from the hash table. 487279546Sbapt @param name Name of the hash table [symbol] 488279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 489279546Sbapt @param k Iterator to the element to be deleted [khint_t] 490279546Sbapt */ 491279546Sbapt#define kh_del(name, h, k) kh_del_##name(h, k) 492279546Sbapt 493279546Sbapt/*! @function 494279546Sbapt @abstract Test whether a bucket contains data. 495279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 496279546Sbapt @param x Iterator to the bucket [khint_t] 497279546Sbapt @return 1 if containing data; 0 otherwise [int] 498279546Sbapt */ 499279546Sbapt#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) 500279546Sbapt 501279546Sbapt/*! @function 502279546Sbapt @abstract Get key given an iterator 503279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 504279546Sbapt @param x Iterator to the bucket [khint_t] 505279546Sbapt @return Key [type of keys] 506279546Sbapt */ 507279546Sbapt#define kh_key(h, x) ((h)->keys[x]) 508279546Sbapt 509279546Sbapt/*! @function 510279546Sbapt @abstract Get value given an iterator 511279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 512279546Sbapt @param x Iterator to the bucket [khint_t] 513279546Sbapt @return Value [type of values] 514279546Sbapt @discussion For hash sets, calling this results in segfault. 515279546Sbapt */ 516279546Sbapt#define kh_val(h, x) ((h)->vals[x]) 517279546Sbapt 518279546Sbapt/*! @function 519279546Sbapt @abstract Alias of kh_val() 520279546Sbapt */ 521279546Sbapt#define kh_value(h, x) ((h)->vals[x]) 522279546Sbapt 523279546Sbapt/*! @function 524279546Sbapt @abstract Get the start iterator 525279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 526279546Sbapt @return The start iterator [khint_t] 527279546Sbapt */ 528279546Sbapt#define kh_begin(h) (khint_t)(0) 529279546Sbapt 530279546Sbapt/*! @function 531279546Sbapt @abstract Get the end iterator 532279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 533279546Sbapt @return The end iterator [khint_t] 534279546Sbapt */ 535279546Sbapt#define kh_end(h) ((h)->n_buckets) 536279546Sbapt 537279546Sbapt/*! @function 538279546Sbapt @abstract Get the number of elements in the hash table 539279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 540279546Sbapt @return Number of elements in the hash table [khint_t] 541279546Sbapt */ 542279546Sbapt#define kh_size(h) ((h)->size) 543279546Sbapt 544279546Sbapt/*! @function 545279546Sbapt @abstract Get the number of buckets in the hash table 546279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 547279546Sbapt @return Number of buckets in the hash table [khint_t] 548279546Sbapt */ 549279546Sbapt#define kh_n_buckets(h) ((h)->n_buckets) 550279546Sbapt 551279546Sbapt/*! @function 552279546Sbapt @abstract Iterate over the entries in the hash table 553279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 554279546Sbapt @param kvar Variable to which key will be assigned 555279546Sbapt @param vvar Variable to which value will be assigned 556279546Sbapt @param code Block of code to execute 557279546Sbapt */ 558279546Sbapt#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ 559279546Sbapt for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ 560279546Sbapt if (!kh_exist(h,__i)) continue; \ 561279546Sbapt (kvar) = kh_key(h,__i); \ 562279546Sbapt (vvar) = kh_val(h,__i); \ 563279546Sbapt code; \ 564279546Sbapt } } 565279546Sbapt 566279546Sbapt/*! @function 567279546Sbapt @abstract Iterate over the values in the hash table 568279546Sbapt @param h Pointer to the hash table [khash_t(name)*] 569279546Sbapt @param vvar Variable to which value will be assigned 570279546Sbapt @param code Block of code to execute 571279546Sbapt */ 572279546Sbapt#define kh_foreach_value(h, vvar, code) { khint_t __i; \ 573279546Sbapt for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ 574279546Sbapt if (!kh_exist(h,__i)) continue; \ 575279546Sbapt (vvar) = kh_val(h,__i); \ 576279546Sbapt code; \ 577279546Sbapt } } 578279546Sbapt 579279546Sbapt/* More conenient interfaces */ 580279546Sbapt 581279546Sbapt/*! @function 582279546Sbapt @abstract Instantiate a hash set containing integer keys 583279546Sbapt @param name Name of the hash table [symbol] 584279546Sbapt */ 585279546Sbapt#define KHASH_SET_INIT_INT(name) \ 586279546Sbapt KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) 587279546Sbapt 588279546Sbapt/*! @function 589279546Sbapt @abstract Instantiate a hash map containing integer keys 590279546Sbapt @param name Name of the hash table [symbol] 591279546Sbapt @param khval_t Type of values [type] 592279546Sbapt */ 593279546Sbapt#define KHASH_MAP_INIT_INT(name, khval_t) \ 594279546Sbapt KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) 595279546Sbapt 596279546Sbapt/*! @function 597279546Sbapt @abstract Instantiate a hash map containing 64-bit integer keys 598279546Sbapt @param name Name of the hash table [symbol] 599279546Sbapt */ 600279546Sbapt#define KHASH_SET_INIT_INT64(name) \ 601279546Sbapt KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) 602279546Sbapt 603279546Sbapt/*! @function 604279546Sbapt @abstract Instantiate a hash map containing 64-bit integer keys 605279546Sbapt @param name Name of the hash table [symbol] 606279546Sbapt @param khval_t Type of values [type] 607279546Sbapt */ 608279546Sbapt#define KHASH_MAP_INIT_INT64(name, khval_t) \ 609279546Sbapt KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) 610279546Sbapt 611279546Sbapttypedef const char *kh_cstr_t; 612279546Sbapt/*! @function 613279546Sbapt @abstract Instantiate a hash map containing const char* keys 614279546Sbapt @param name Name of the hash table [symbol] 615279546Sbapt */ 616279546Sbapt#define KHASH_SET_INIT_STR(name) \ 617279546Sbapt KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) 618279546Sbapt 619279546Sbapt/*! @function 620279546Sbapt @abstract Instantiate a hash map containing const char* keys 621279546Sbapt @param name Name of the hash table [symbol] 622279546Sbapt @param khval_t Type of values [type] 623279546Sbapt */ 624279546Sbapt#define KHASH_MAP_INIT_STR(name, khval_t) \ 625279546Sbapt KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) 626279546Sbapt 627279546Sbapt#endif /* __AC_KHASH_H */ 628