From 26444aa7f78e19b50a0b9fb6cdf351a6e7699f94 Mon Sep 17 00:00:00 2001 From: Attractive Chaos Date: Mon, 6 May 2024 09:39:23 -0400 Subject: [PATCH] sync with khashl --- khashl.h | 58 ++++++++++---------------------------------------------- 1 file changed, 10 insertions(+), 48 deletions(-) diff --git a/khashl.h b/khashl.h index 59662c3..7f2a81a 100644 --- a/khashl.h +++ b/khashl.h @@ -26,7 +26,7 @@ #ifndef __AC_KHASHL_H #define __AC_KHASHL_H -#define AC_VERSION_KHASHL_H "0.3" +#define AC_VERSION_KHASHL_H "r20" #include #include @@ -67,6 +67,7 @@ typedef unsigned long long khint64_t; #define KH_LOCAL static kh_inline klib_unused typedef khint32_t khint_t; +typedef const char *kh_cstr_t; /*********************** * Configurable macros * @@ -145,7 +146,7 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26 #define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \ khint_t i, last, n_buckets, mask; \ - if (h->keys == 0) return 1; \ + if (h->keys == 0) return 0; \ n_buckets = (khint_t)1U << h->bits; \ mask = n_buckets - 1U; \ i = last = __kh_h2b(hash, h->bits); \ @@ -295,7 +296,7 @@ typedef struct { low = hash & ((1U<bits) - 1); \ h = &g->sub[low]; \ ret = prefix##_sub_getp_core(h, key, hash); \ - if (ret == 1U<bits) r.sub = low, r.pos = (khint_t)-1; \ + if (ret == kh_end(h)) r.sub = low, r.pos = (khint_t)-1; \ else r.sub = low, r.pos = ret; \ return r; \ } \ @@ -309,8 +310,7 @@ typedef struct { h = &g->sub[low]; \ ret = prefix##_sub_putp_core(h, key, hash, absent); \ if (*absent) ++g->count; \ - if (ret == 1U<bits) r.sub = low, r.pos = (khint_t)-1; \ - else r.sub = low, r.pos = ret; \ + r.sub = low, r.pos = ret; \ return r; \ } \ SCOPE kh_ensitr_t prefix##_put(HType *g, const khkey_t key, int *absent) { return prefix##_putp(g, &key, absent); } \ @@ -329,16 +329,7 @@ typedef struct { #define __kh_cached_hash(x) ((x).hash) #define KHASHL_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; } kh_packed HType##_s_bucket_t; \ - static kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \ - static kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \ - KHASHL_INIT(KH_LOCAL, HType, prefix##_s, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \ - SCOPE HType *prefix##_init(void) { return prefix##_s_init(); } \ - SCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \ - SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_s_resize(h, new_n_buckets); } \ - SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \ - SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } + KHASHL_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) #define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ typedef struct { khkey_t key; kh_val_t val; } kh_packed HType##_m_bucket_t; \ @@ -372,15 +363,7 @@ typedef struct { SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cm_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cm_putp(h, &t, absent); } #define KHASHE_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; } kh_packed HType##_s_bucket_t; \ - static kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \ - static kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \ - KHASHE_INIT(KH_LOCAL, HType, prefix##_m, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \ - SCOPE HType *prefix##_init(int bits) { return prefix##_s_init(bits); } \ - SCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \ - SCOPE kh_ensitr_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \ - SCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_s_del(h, k); } \ - SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } + KHASHE_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) #define KHASHE_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ typedef struct { khkey_t key; kh_val_t val; } kh_packed HType##_m_bucket_t; \ @@ -424,17 +407,7 @@ typedef struct { #define kh_eq_str(a, b) (strcmp((a), (b)) == 0) #define kh_hash_dummy(x) ((khint_t)(x)) -static kh_inline khint_t kh_hash_uint32(khint_t key) { - key += ~(key << 15); - key ^= (key >> 10); - key += (key << 3); - key ^= (key >> 6); - key += ~(key << 11); - key ^= (key >> 16); - return key; -} - -static kh_inline khint_t kh_hash_murmurmix32(khint_t x) { +static kh_inline khint_t kh_hash_uint32(khint_t x) { /* murmur finishing */ x ^= x >> 16; x *= 0x85ebca6bU; x ^= x >> 13; @@ -443,18 +416,7 @@ static kh_inline khint_t kh_hash_murmurmix32(khint_t x) { return x; } -static kh_inline khint_t kh_hash_uint64(khint64_t key) { - key = ~key + (key << 21); - key = key ^ key >> 24; - key = (key + (key << 3)) + (key << 8); - key = key ^ key >> 14; - key = (key + (key << 2)) + (key << 4); - key = key ^ key >> 28; - key = key + (key << 31); - return (khint_t)key; -} - -static kh_inline khint_t kh_hash_splitmix64(khint64_t x) { +static kh_inline khint_t kh_hash_uint64(khint64_t x) { /* splitmix64; see https://nullprogram.com/blog/2018/07/31/ for inversion */ x ^= x >> 30; x *= 0xbf58476d1ce4e5b9ULL; x ^= x >> 27; @@ -465,7 +427,7 @@ static kh_inline khint_t kh_hash_splitmix64(khint64_t x) { #define KH_FNV_SEED 11 -static kh_inline khint_t kh_hash_str(const char *s) { /* FNV1a */ +static kh_inline khint_t kh_hash_str(kh_cstr_t s) { /* FNV1a */ khint_t h = KH_FNV_SEED ^ 2166136261U; const unsigned char *t = (const unsigned char*)s; for (; *t; ++t) -- 2.47.3