From: Eric Wong <e@80x24.org>
To: spew@80x24.org
Subject: [PATCH 1/2] khashl: fix ensemble lookups on empty table
Date: Sun, 24 Mar 2024 23:05:41 +0000 [thread overview]
Message-ID: <20240324230542.2364726-1-e@80x24.org> (raw)
The ->bits field of regular khashl structs is invalid when
the ->keys array is NULL. Thus the ensemble *_getp implementation
must follow existing *_get and *_getp usage convensions and
check the iterator against kh_end().
This fixes a fast-import crash on t3427-rebase-subtree.sh in a
subsequent commit to use ensemble implementation for oid_map and
oid_pos.
---
khashl.h | 62 +++++++++++++++++++++++++++++++++++++++++---------------
1 file changed, 46 insertions(+), 16 deletions(-)
diff --git a/khashl.h b/khashl.h
index 8b222a2350..a1eca0f3fd 100644
--- a/khashl.h
+++ b/khashl.h
@@ -204,22 +204,22 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26
__KHASHL_PROTOTYPES(HType, prefix, khkey_t)
/* compatibility wrappers to make khash -> khashl migration easier */
-#define __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t) \
+#define __KHASH_COMPAT(SCOPE, kh_idx, HType, prefix, khkey_t) \
typedef HType HType##_t; \
SCOPE HType *kh_init_##prefix(void) { return prefix##_init(); } \
SCOPE void kh_release_##prefix(HType *h) { prefix##_release(h); } \
SCOPE void kh_destroy_##prefix(HType *h) { prefix##_destroy(h); } \
SCOPE void kh_clear_##prefix(HType *h) { prefix##_clear(h); } \
- SCOPE khint_t kh_get_##prefix(const HType *h, khkey_t key) { \
+ SCOPE kh_idx kh_get_##prefix(const HType *h, khkey_t key) { \
return prefix##_get(h, key); \
} \
SCOPE void kh_resize_##prefix(HType *h, khint_t new_n_buckets) { \
prefix##_resize(h, new_n_buckets); \
} \
- SCOPE khint_t kh_put_##prefix(HType *h, khkey_t key, int *absent) { \
+ SCOPE kh_idx kh_put_##prefix(HType *h, khkey_t key, int *absent) { \
return prefix##_put(h, key, absent); \
} \
- SCOPE int kh_del_##prefix(HType *h, khint_t i) { \
+ SCOPE int kh_del_##prefix(HType *h, kh_idx i) { \
return prefix##_del(h, i); \
}
@@ -245,18 +245,32 @@ typedef struct {
khint64_t count:54, bits:8; \
HType##_sub *sub; \
} HType; \
- SCOPE HType *prefix##_init(int bits) { \
- HType *g; \
- g = (HType*)kcalloc(1, sizeof(*g)); \
+ SCOPE HType *prefix##_init_sub(HType *g, size_t bits) { \
g->bits = bits; \
g->sub = (HType##_sub*)kcalloc(1U<<bits, sizeof(*g->sub)); \
return g; \
} \
+ SCOPE HType *prefix##_init(void) { \
+ HType *g; \
+ g = (HType*)kcalloc(1, sizeof(*g)); \
+ return prefix##_init_sub(g, 0); /* unsure about default */ \
+ } \
+ SCOPE void prefix##_release(HType *g) { \
+ int t; \
+ for (t = 0; t < 1<<g->bits; ++t) \
+ prefix##_sub_release(&g->sub[t]); \
+ kfree(g->sub); \
+ } \
SCOPE void prefix##_destroy(HType *g) { \
+ if (!g) return; \
+ prefix##_release(g); \
+ kfree(g); \
+ } \
+ SCOPE void prefix##_clear(HType *g) { \
int t; \
if (!g) return; \
- for (t = 0; t < 1<<g->bits; ++t) { kfree((void*)g->sub[t].keys); kfree(g->sub[t].used); } \
- kfree(g->sub); kfree(g); \
+ for (t = 0; t < 1<<g->bits; ++t) \
+ prefix##_sub_clear(&g->sub[t]); \
} \
SCOPE kh_ensitr_t prefix##_getp(const HType *g, const khkey_t *key) { \
khint_t hash, low, ret; \
@@ -266,7 +280,7 @@ typedef struct {
low = hash & ((1U<<g->bits) - 1); \
h = &g->sub[low]; \
ret = prefix##_sub_getp_core(h, key, hash); \
- if (ret == 1U<<h->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; \
} \
@@ -313,7 +327,7 @@ typedef struct {
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); } \
- __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)
+ __KHASH_COMPAT(SCOPE, khint_t, HType, prefix, khkey_t)
#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; \
@@ -328,7 +342,7 @@ typedef struct {
SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \
SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \
SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } \
- __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)
+ __KHASH_COMPAT(SCOPE, khint_t, HType, prefix, khkey_t)
#define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \
typedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \
@@ -355,11 +369,15 @@ typedef struct {
static kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \
static kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \
KHASHE_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \
- SCOPE HType *prefix##_init(int bits) { return prefix##_m_init(bits); } \
+ SCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \
+ SCOPE void prefix##_release(HType *h) { prefix##_m_release(h); } \
SCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \
+ SCOPE void prefix##_clear(HType *h) { prefix##_m_clear(h); } \
+ SCOPE void prefix##_resize(HType *h, khint_t ignore) { /* noop */ } \
SCOPE kh_ensitr_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \
SCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_m_del(h, k); } \
- SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); }
+ SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } \
+ __KHASH_COMPAT(SCOPE, kh_ensitr_t, HType, prefix, khkey_t)
/**************************
* Public macro functions *
@@ -488,6 +506,18 @@ static kh_inline khint_t kh_hash_bytes(int len, const unsigned char *s) {
code; \
} }
+#define kh_ens_foreach(g, kvar, vvar, code) do { \
+ size_t t; \
+ for (t = 0; t < 1<<g->bits; ++t) \
+ kh_foreach(&g->sub[t], kvar, vvar, code); \
+} while (0)
+
+#define kh_ens_foreach_value(g, vvar, code) do { \
+ size_t t; \
+ for (t = 0; t < 1<<g->bits; ++t) \
+ kh_foreach_value(&g->sub[t], vvar, code); \
+} while (0)
+
/*! @function
@abstract Iterate over the values in the hash table
@param h Pointer to the hash table
@@ -514,10 +544,10 @@ static inline int oideq_by_value(struct object_id a, struct object_id b)
KHASHL_SET_INIT(KH_LOCAL, kh_oid_set, oid_set, struct object_id,
oidhash_by_value, oideq_by_value)
-KHASHL_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,
+KHASHE_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,
oidhash_by_value, oideq_by_value)
-KHASHL_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,
+KHASHE_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,
oidhash_by_value, oideq_by_value)
#endif /* __AC_KHASHL_H */
next reply other threads:[~2024-03-24 23:05 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-24 23:05 Eric Wong [this message]
2024-03-24 23:05 ` [PATCH 2/2] switch to khashl ensemble Eric Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240324230542.2364726-1-e@80x24.org \
--to=e@80x24.org \
--cc=spew@80x24.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).