From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: X-Spam-Status: No, score=-4.2 required=3.0 tests=ALL_TRUSTED,AWL,BAYES_00, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF shortcircuit=no autolearn=ham autolearn_force=no version=3.4.6 Received: from localhost (dcvr.yhbt.net [127.0.0.1]) by dcvr.yhbt.net (Postfix) with ESMTP id DD4EB1F44D for ; Sun, 24 Mar 2024 23:05:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=80x24.org; s=selector1; t=1711321542; bh=yu7zL95dpCp5kqgm3jSel8KbvNYlKAmiDizQyD3R3UA=; h=From:To:Subject:Date:From; b=4OiAUNGraRtNi/9gV8chCcDvjqisTRQV8xhqLUdX9JGp35Di5BMJzTIYeJpvVrkS2 +BAFt8v+XAcUdjxCrgszYIn+wwiD5ed0kxSLvbekmQyjklkW5t20QAtjxUdkJE6+35 mzZOp9hNX+rvhPB021FZSXe1tkUcbrq6EZlr5fcM= From: Eric Wong To: spew@80x24.org Subject: [PATCH 1/2] khashl: fix ensemble lookups on empty table Date: Sun, 24 Mar 2024 23:05:41 +0000 Message-ID: <20240324230542.2364726-1-e@80x24.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit List-Id: 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<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<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<bits; ++t) { kfree((void*)g->sub[t].keys); kfree(g->sub[t].used); } \ - kfree(g->sub); kfree(g); \ + for (t = 0; t < 1<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<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; \ } \ @@ -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<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<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 */