This source file includes following definitions.
- __kh_X31_hash_string
- __luaS_hash_string
- __ac_Wang_hash
#ifndef __AC_KHASH_H
#define __AC_KHASH_H
#define AC_VERSION_KHASH_H "0.2.6p"
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef uint32_t khint_t;
typedef khint_t khiter_t;
#define KHASH_FLAG(name, h, i) *(uint32_t *)(h->table + kh_flag_##name(i))
#define KHASH_KEY(name, h, i) *kh_key_##name(h, i)
#define KHASH_VAL(name, h, i) *kh_val_##name(h, i)
#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
#define __kh_isempty(name, h, i) ((KHASH_FLAG(name, h, i)>>((i&0xfU)<<1))&2)
#define __kh_isdel(name, h, i) ((KHASH_FLAG(name, h, i)>>((i&0xfU)<<1))&1)
#define __kh_iseither(name, h, i) ((KHASH_FLAG(name, h, i)>>((i&0xfU)<<1))&3)
#define __kh_set_isdel_false(name, h, i) (KHASH_FLAG(name, h, i)&=~(1ul<<((i&0xfU)<<1)))
#define __kh_set_isempty_false(name, h, i) (KHASH_FLAG(name, h, i)&=~(2ul<<((i&0xfU)<<1)))
#define __kh_set_isboth_false(name, h, i) (KHASH_FLAG(name, h, i)&=~(3ul<<((i&0xfU)<<1)))
#define __kh_set_isdel_true(name, h, i) (KHASH_FLAG(name, h, i)|=1ul<<((i&0xfU)<<1))
#define __ac_inc(k) ((k) | 1)
#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
static const double __kh_HASH_UPPER = 0.77;
#define PN_TABLE_HEADER PN_SIZE n_buckets, size, n_occupied, upper_bound
#define KHASH_INIT(name, kh_t, khkey_t, khval_t, khkey_t2, kh_is_map, __hash_func, __hash_equal, __hash_func2, __hash_equal2) \
static inline khint_t kh_pair_##name() { return (kh_is_map ? (sizeof(khkey_t) + sizeof(khval_t)) : sizeof(khkey_t)); } \
static inline khint_t kh_size_##name(khint_t n) { return (((n >> 4) + 1) * (sizeof(uint32_t))) + (n * kh_pair_##name()); } \
static inline khint_t kh_flag_##name(khint_t i) { return (i >> 4) * (sizeof(uint32_t) + ((sizeof(uint32_t) * 4) * kh_pair_##name())); } \
static inline khint_t kh_key_at_##name(khint_t i) { return (((i >> 4) + 1) * sizeof(uint32_t)) + (i * kh_pair_##name()); } \
static inline khint_t kh_val_at_##name(khint_t i) { return (((i >> 4) + 1) * sizeof(uint32_t)) + (i * kh_pair_##name()) + sizeof(khkey_t); } \
static inline khkey_t *kh_key_##name(kh_t *h, khint_t i) { return (khkey_t *)(h->table + kh_key_at_##name(i)); } \
static inline khval_t *kh_val_##name(kh_t *h, khint_t i) { return (khval_t *)(h->table + kh_val_at_##name(i)); } \
static inline void kh_clear_##name(Potion *P, kh_t *h) \
{ \
if (h && h->n_buckets > 0) { \
\
int i = ((h->n_buckets) >> 4) + 1; \
while (i-- > 0) KHASH_FLAG(name, h, i) = 0xaaaaaaaa; \
h->size = h->n_occupied = 0; \
} \
} \
static inline khint_t kh_get_##name(Potion *P, kh_t *h, khkey_t2 key) \
{ \
if (h->n_buckets) { \
khint_t inc, k, i, last, mask; \
mask = h->n_buckets - 1; \
k = __hash_func2(key); i = k & mask; \
inc = __ac_inc(k) & mask; last = i; \
while (!__kh_isempty(name, h, i) && (__kh_isdel(name, h, i) || !__hash_equal2(KHASH_KEY(name, h, i), key))) { \
i = (i + inc) & mask; \
if (i == last) return h->n_buckets; \
} \
return __kh_iseither(name, h, i)? h->n_buckets : i; \
} else return 0; \
} \
static inline kh_t *kh_resize_##name(Potion *P, kh_t *h, khint_t new_n_buckets) \
{ \
vPN(Data) nft = 0; \
uint32_t *new_flags = 0; \
khint_t j = 1; \
{ \
new_n_buckets = h->n_buckets? h->n_buckets<<1 : 4; \
if (h->size >= (khint_t)(new_n_buckets * __kh_HASH_UPPER + 0.5)) j = 0; \
else { \
nft = PN_DALLOC_N(uint32_t, __ac_fsize(new_n_buckets)); \
if (h->n_buckets < new_n_buckets) \
PN_REALLOC(h, PN_TUSER, kh_t, kh_size_##name(new_n_buckets)); \
new_flags = (uint32_t *)nft->data; \
memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(uint32_t)); \
} \
} \
if (j) { \
for (j = 0; j != h->n_buckets; ++j) { \
if (__kh_iseither(name, h, j) == 0) { \
khkey_t key = KHASH_KEY(name, h, j); \
khval_t val; \
if (kh_is_map) val = KHASH_VAL(name, h, j); \
__kh_set_isdel_true(name, h, j); \
while (1) { \
khint_t inc, k, i, new_mask; \
new_mask = new_n_buckets - 1; \
k = __hash_func(key); \
i = k & new_mask; \
inc = __ac_inc(k) & new_mask; \
while (!__ac_isempty(new_flags, i)) i = (i + inc) & new_mask; \
__ac_set_isempty_false(new_flags, i); \
if (i < h->n_buckets && __kh_iseither(name, h, i) == 0) { \
{ khkey_t tmp = KHASH_KEY(name, h, i); KHASH_KEY(name, h, i) = key; key = tmp; } \
if (kh_is_map) { khval_t tmp = KHASH_VAL(name, h, i); KHASH_VAL(name, h, i) = val; val = tmp; } \
__kh_set_isdel_true(name, h, i); \
} else { \
KHASH_KEY(name, h, i) = key; \
if (kh_is_map) KHASH_VAL(name, h, i) = val; \
break; \
} \
} \
} \
} \
if (h->n_buckets > new_n_buckets) \
PN_REALLOC(h, PN_TUSER, kh_t, kh_size_##name(new_n_buckets)); \
j = (new_n_buckets >> 4) + 1; \
new_flags = (uint32_t *)nft->data; \
while (j-- > 0) KHASH_FLAG(name, h, j << 4) = new_flags[j]; \
h->n_buckets = new_n_buckets; \
h->n_occupied = h->size; \
h->upper_bound = (khint_t)(h->n_buckets * __kh_HASH_UPPER + 0.5); \
} \
return h; \
} \
static inline khint_t kh_put_##name(Potion *P, kh_t *h, khkey_t key, int *ret) \
{ \
khint_t x; \
if (h->n_occupied >= h->upper_bound) { \
if (h->n_buckets > (h->size<<1)) h = kh_resize_##name(P, h, h->n_buckets - 1); \
else h = kh_resize_##name(P, h, h->n_buckets + 1); \
} \
{ \
khint_t inc, k, i, site, last, mask = h->n_buckets - 1; \
x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
if (__kh_isempty(name, h, i)) x = i; \
else { \
inc = __ac_inc(k) & mask; last = i; \
while (!__kh_isempty(name, h, i) && (__kh_isdel(name, h, i) || !__hash_equal(KHASH_KEY(name, h, i), key))) { \
if (__kh_isdel(name, h, i)) site = i; \
i = (i + inc) & mask; \
if (i == last) { x = site; break; } \
} \
if (x == h->n_buckets) { \
if (__kh_isempty(name, h, i) && site != h->n_buckets) x = site; \
else x = i; \
} \
} \
} \
if (__kh_isempty(name, h, x)) { \
KHASH_KEY(name, h, x) = key; \
__kh_set_isboth_false(name, h, x); \
++h->size; ++h->n_occupied; \
*ret = 1; \
} else if (__kh_isdel(name, h, x)) { \
KHASH_KEY(name, h, x) = key; \
__kh_set_isboth_false(name, h, x); \
++h->size; \
*ret = 2; \
} else *ret = 0; \
return x; \
} \
static inline void kh_del_##name(Potion *P, kh_t *h, khint_t x) \
{ \
if (x != h->n_buckets && !__kh_iseither(name, h, x)) { \
__kh_set_isdel_true(name, h, x); \
--h->size; \
} \
}
#define kh_int_hash_func(key) (uint32_t)(key)
#define kh_int_hash_equal(a, b) (a == b)
#define kh_int64_hash_func(key) (uint32_t)((key)>>33^(key)^(key)<<11)
#define kh_int64_hash_equal(a, b) (a == b)
static inline khint_t __kh_X31_hash_string(const char *s)
{
khint_t h = *s;
if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
return h;
}
static inline khint_t __luaS_hash_string(const char *s)
{
size_t len = strlen(s);
khint_t h = len;
size_t step = (len >> 5) + 1;
size_t l1;
for (l1 = len; l1 >= step; l1 -= step)
h = h ^ ((h << 5) + (h >> 2) + (unsigned char)s[l1 - 1]);
return h;
}
#define kh_pnstr_hash_func(key) __luaS_hash_string(PN_STR_PTR(key))
#define kh_pnstr_hash_equal(a, b) (strcmp(PN_STR_PTR(a), PN_STR_PTR(b)) == 0)
#define kh_str_hash_func(key) __luaS_hash_string(key)
#define kh_str_hash_equal(a, b) (strcmp(PN_STR_PTR(a), b) == 0)
#define kh_pn_hash_func(key) (uint32_t)PN_UNIQ(key)
#define kh_pn_hash_equal(a, b) (a == b)
static inline khint_t __ac_Wang_hash(khint_t key)
{
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
#define kh_clear(name, h) kh_clear_##name(P, h)
#define kh_resize(name, h, s) h = kh_resize_##name(P, h, s)
#define kh_put(name, h, k, r) kh_put_##name(P, h, k, r)
#define kh_get(name, h, k) kh_get_##name(P, h, k)
#define kh_del(name, h, k) kh_del_##name(P, h, k)
#define kh_exist(name, h, x) (!__kh_iseither(name, (h), (x)))
#define kh_key(name, h, x) (KHASH_KEY(name, h, x))
#define kh_val(name, h, x) (KHASH_VAL(name, h, x))
#define kh_begin(h) (khint_t)(0)
#define kh_end(h) ((h)->n_buckets)
#define kh_size(h) ((h)->size)
#define kh_n_buckets(h) ((h)->n_buckets)
#define kh_mem(name, h) (((struct PNTable *)h)->n_buckets == 0 ? 0 : kh_size_##name(((struct PNTable *)h)->n_buckets))
#define KHASH_MAP_INIT_STR(name, t) \
KHASH_INIT(name, t, _PN, PNUniq, const char *, 0, kh_pnstr_hash_func, \
kh_pnstr_hash_equal, kh_str_hash_func, kh_str_hash_equal)
#define KHASH_MAP_INIT_PN(name, t) \
KHASH_INIT(name, t, _PN, _PN, _PN, 1, kh_pn_hash_func, \
kh_pn_hash_equal, kh_pn_hash_func, kh_pn_hash_equal)
#endif