97#define AC_VERSION_KHASH_H "0.2.5"
105#if UINT_MAX == 0xffffffffu
106typedef unsigned int khint32_t;
107#elif ULONG_MAX == 0xffffffffu
108typedef unsigned long khint32_t;
111#if ULONG_MAX == ULLONG_MAX
112typedef unsigned long khint64_t;
114typedef unsigned long long khint64_t;
118#define inline __inline
122#define inline __inline
125typedef khint32_t khint_t;
126typedef khint_t khiter_t;
128#define __ac_HASH_PRIME_SIZE 32
129static const khint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] =
131 0ul, 3ul, 11ul, 23ul, 53ul,
132 97ul, 193ul, 389ul, 769ul, 1543ul,
133 3079ul, 6151ul, 12289ul, 24593ul, 49157ul,
134 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul,
135 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul,
136 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul,
137 3221225473ul, 4294967291ul
140#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
141#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
142#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
143#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
144#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
145#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
146#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
148static const double __ac_HASH_UPPER = 0.77;
150#define KHASH_DECLARE(name, khkey_t, khval_t) \
152 khint_t n_buckets, size, n_occupied, upper_bound; \
157 extern kh_##name##_t *kh_init_##name(); \
158 extern void kh_destroy_##name(kh_##name##_t *h); \
159 extern void kh_clear_##name(kh_##name##_t *h); \
160 extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \
161 extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
162 extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
163 extern void kh_del_##name(kh_##name##_t *h, khint_t x);
165#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
167 khint_t n_buckets, size, n_occupied, upper_bound; \
172 SCOPE kh_##name##_t *kh_init_##name() { \
173 return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \
175 SCOPE void kh_destroy_##name(kh_##name##_t *h) \
178 free(h->keys); free(h->flags); \
183 SCOPE void kh_clear_##name(kh_##name##_t *h) \
185 if (h && h->flags) { \
186 memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(khint32_t)); \
187 h->size = h->n_occupied = 0; \
190 SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
192 if (h->n_buckets) { \
193 khint_t inc, k, i, last; \
194 k = __hash_func(key); i = k % h->n_buckets; \
195 inc = 1 + k % (h->n_buckets - 1); last = i; \
196 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
197 if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
199 if (i == last) return h->n_buckets; \
201 return __ac_iseither(h->flags, i)? h->n_buckets : i; \
204 SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
206 khint32_t *new_flags = 0; \
209 khint_t t = __ac_HASH_PRIME_SIZE - 1; \
210 while (__ac_prime_list[t] > new_n_buckets) --t; \
211 new_n_buckets = __ac_prime_list[t+1]; \
212 if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
214 new_flags = (khint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
215 memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
216 if (h->n_buckets < new_n_buckets) { \
217 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
219 h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
224 for (j = 0; j != h->n_buckets; ++j) { \
225 if (__ac_iseither(h->flags, j) == 0) { \
226 khkey_t key = h->keys[j]; \
228 if (kh_is_map) val = h->vals[j]; \
229 __ac_set_isdel_true(h->flags, j); \
232 k = __hash_func(key); \
233 i = k % new_n_buckets; \
234 inc = 1 + k % (new_n_buckets - 1); \
235 while (!__ac_isempty(new_flags, i)) { \
236 if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
239 __ac_set_isempty_false(new_flags, i); \
240 if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
241 { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
242 if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
243 __ac_set_isdel_true(h->flags, i); \
246 if (kh_is_map) h->vals[i] = val; \
252 if (h->n_buckets > new_n_buckets) { \
253 h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
255 h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
258 h->flags = new_flags; \
259 h->n_buckets = new_n_buckets; \
260 h->n_occupied = h->size; \
261 h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
264 SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
267 if (h->n_occupied >= h->upper_bound) { \
268 if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
269 else kh_resize_##name(h, h->n_buckets + 1); \
272 khint_t inc, k, i, site, last; \
273 x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
274 if (__ac_isempty(h->flags, i)) x = i; \
276 inc = 1 + k % (h->n_buckets - 1); last = i; \
277 while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
278 if (__ac_isdel(h->flags, i)) site = i; \
279 if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
281 if (i == last) { x = site; break; } \
283 if (x == h->n_buckets) { \
284 if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
289 if (__ac_isempty(h->flags, x)) { \
291 __ac_set_isboth_false(h->flags, x); \
292 ++h->size; ++h->n_occupied; \
294 } else if (__ac_isdel(h->flags, x)) { \
296 __ac_set_isboth_false(h->flags, x); \
302 SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \
304 if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
305 __ac_set_isdel_true(h->flags, x); \
310#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
311 KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
320#define kh_int_hash_func(key) (khint32_t)(key)
324#define kh_int_hash_equal(a, b) ((a) == (b))
330#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
334#define kh_int64_hash_equal(a, b) ((a) == (b))
340static inline khint_t __ac_X31_hash_string(
const char *s)
343 if (h)
for (++s ; *s; ++s) h = (h << 5) - h + *s;
351#define kh_str_hash_func(key) __ac_X31_hash_string(key)
355#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
365#define khash_t(name) kh_##name##_t
372#define kh_init(name) kh_init_##name()
379#define kh_destroy(name, h) kh_destroy_##name(h)
386#define kh_clear(name, h) kh_clear_##name(h)
394#define kh_resize(name, h, s) kh_resize_##name(h, s)
406#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
415#define kh_get(name, h, k) kh_get_##name(h, k)
423#define kh_del(name, h, k) kh_del_##name(h, k)
432#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
440#define kh_key(h, x) ((h)->keys[x])
449#define kh_val(h, x) ((h)->vals[x])
454#define kh_value(h, x) ((h)->vals[x])
461#define kh_begin(h) (khint_t)(0)
468#define kh_end(h) ((h)->n_buckets)
475#define kh_size(h) ((h)->size)
482#define kh_n_buckets(h) ((h)->n_buckets)
490#define KHASH_SET_INIT_INT(name) \
491 KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
498#define KHASH_MAP_INIT_INT(name, khval_t) \
499 KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
505#define KHASH_SET_INIT_INT64(name) \
506 KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
513#define KHASH_MAP_INIT_INT64(name, khval_t) \
514 KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
516typedef const char *kh_cstr_t;
521#define KHASH_SET_INIT_STR(name) \
522 KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
529#define KHASH_MAP_INIT_STR(name, khval_t) \
530 KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)