{"thread":{"id":"61203","subject":"[PATCH 1/3] list-objects-filter: use kh_size API","startedAt":"2024-03-25T23:07:15Z","lastAt":"2024-04-19T21:52:19Z","messageCount":11,"participants":["Eric Wong","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"491537","messageId":"20240325230704.262272-2-e@80x24.org","threadId":"61203","inReplyTo":"20240325230704.262272-1-e@80x24.org","subject":"[PATCH 1/3] list-objects-filter: use kh_size API","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-25T23:07:01Z","receivedAt":"2024-03-25T23:07:15Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"In order to ease a potential migration to from khash to khashl,\nuse the kh_size() macro instead of accessing the .size field\ndirectly.\n\nSigned-off-by: Eric Wong <e@80x24.org>\n---\n list-objects-filter.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 4346f8da45..440f112d23 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -704,7 +704,7 @@ static void filter_combine__free(void *filter_data)\n \tfor (sub = 0; sub < d->nr; sub++) {\n \t\tlist_objects_filter__free(d->sub[sub].filter);\n \t\toidset_clear(&d->sub[sub].seen);\n-\t\tif (d->sub[sub].omits.set.size)\n+\t\tif (kh_size(&d->sub[sub].omits.set))\n \t\t\tBUG(\"expected oidset to be cleared already\");\n \t}\n \tfree(d->sub);\n"},{"id":"491538","messageId":"20240325230704.262272-3-e@80x24.org","threadId":"61203","inReplyTo":"20240325230704.262272-1-e@80x24.org","subject":"[PATCH 2/3] treewide: switch to khashl for memory savings","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-25T23:07:02Z","receivedAt":"2024-03-25T23:07:23Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"khashl is an updated version of khash with less memory overhead\n(one bit/bucket instead of two) than the original khash and\nsimilar overall performance.  Insertions are simpler (linear\nprobing) but deletions may be slightly slower[1].  Of course,\nthe majority of hash tables in git do not delete individual\nelements.\n\nOverall memory usage did not decrease much, as the hash tables\nand elements we store in them are big and currently dwarf the\noverhead of the khash internals.  Only around 10 MB in\nallocations (not peak use) is saved when doing a no-op `git gc'\nof a Linux kernel object store with thousands of refs and\nislands.\n\nA summary of differences I've found from khash to khashl:\n\n* two 32-bit ints (instead of four) in the top-level struct\n\n* 2 heap allocations (instead of 3) for maps\n  (though I wonder locality suffers when probing is necessary)\n\n* 1 bit of metadata per-bucket (no tombstones for deleted elements)\n\n* 0.75 load factor.  Lowered slightly from 0.77, but no FP multiply\n  and responsible for the aforementioned struct size reduction\n\n* FNV-1A instead of x31 hash for strings\n\n* Fibonacci hashing (__kh_h2b), probably good for FNV-1A, but \n  I'm skeptical of its usefulness for our SHA-* using cases\n\n* linear probing instead of quadratic\n\n* Wang's integer hash functions (currently unused)\n\n* optional hash value caching and ensemble APIs (currently unused)\n\n* some API differences (see below), but not enough to easily\n  use both khash and khashl in the same compilation unit\n\nThis patch was made with two additional goals to ease review:\n\n1) minimize changes outside of khash*.h files\n\n2) minimize and document all differences from upstream[2] khashl.h\n\nOur khashl.h differences from upstream:\n\n* favor portability constructs from our codebase:\n  MAYBE_UNUSED over klib_unused, inline over kh_inline, and\n  various integer types\n\n* disable packed attribute to satisfy -Werror=address-of-packed-member,\n  AFAIK it doesn't change any of the data structures we use\n\n* port the following commits over from our old khash.h:\n  9249ca26aca3 (khash: factor out kh_release_*, 2018-10-04)\n  2756ca4347cb (use REALLOC_ARRAY for changing the allocation size of arrays, 2014-09-16)\n  5632e838f8fa (khash: clarify that allocations never fail, 2021-07-03)\n\n* use our memory allocation wrappers\n\n* provide wrappers for compatibility with existing callers using the\n  khash API.  The khashl function naming convention is: ${NOUN}_${VERB}\n  while the khash convention is: kh_${VERB}_${NOUN}.  The kh_${NAME}_t\n  typedef and naming convention are preserved via __KHASH_COMPAT macro\n  to ease review (despite the `_t' suffix being reserved and typedefs\n  being discouraged in the Linux kernel).\n\n* copy relevant API docs over from khash.h for identically named macros\n\n* preserve kh_begin, kh_foreach, kh_foreach_value from khash.h since\n  khashl.h doesn't provide them\n\n* flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize,\n  and *_release functions\n\n[1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/\n[2] git clone https://github.com/attractivechaos/klib.git\n    2895a16cb55e (support an ensemble of hash tables, 2023-12-18)\n\nkhashl.h API differences from khash.h which affected this change:\n\n* KHASHL_MAP_INIT and KHASHL_SET_INIT macros replace KHASH_INIT\n\n* user-supplied hash and equality functions use different names\n\n* object-store-ll.h avoided the kh_*_t convention (since I dislike\n  typedef) and was the only place where I had to change a definition.\n\nSigned-off-by: Eric Wong <e@80x24.org>\n---\n The git-specific changes are absolutely minimal :>\n\n builtin/fast-import.c       |   2 +-\n builtin/fsmonitor--daemon.c |   4 +-\n delta-islands.c             |   4 +-\n khash.h                     | 338 -----------------------\n khashl.h                    | 522 ++++++++++++++++++++++++++++++++++++\n object-store-ll.h           |   2 +-\n object-store.h              |   7 +-\n oidset.h                    |   2 +-\n pack-bitmap.h               |   2 +-\n 9 files changed, 534 insertions(+), 349 deletions(-)\n delete mode 100644 khash.h\n create mode 100644 khashl.h\n\ndiff --git a/builtin/fast-import.c b/builtin/fast-import.c\nindex 71a195ca22..29e50fd675 100644\n--- a/builtin/fast-import.c\n+++ b/builtin/fast-import.c\n@@ -24,7 +24,7 @@\n #include \"object-store-ll.h\"\n #include \"mem-pool.h\"\n #include \"commit-reach.h\"\n-#include \"khash.h\"\n+#include \"khashl.h\"\n #include \"date.h\"\n \n #define PACK_ID_BITS 16\ndiff --git a/builtin/fsmonitor--daemon.c b/builtin/fsmonitor--daemon.c\nindex 1593713f4c..1c71d96c6d 100644\n--- a/builtin/fsmonitor--daemon.c\n+++ b/builtin/fsmonitor--daemon.c\n@@ -13,7 +13,7 @@\n #include \"fsmonitor--daemon.h\"\n #include \"repository.h\"\n #include \"simple-ipc.h\"\n-#include \"khash.h\"\n+#include \"khashl.h\"\n #include \"run-command.h\"\n #include \"trace.h\"\n #include \"trace2.h\"\n@@ -650,7 +650,7 @@ static int fsmonitor_parse_client_token(const char *buf_token,\n \treturn 0;\n }\n \n-KHASH_INIT(str, const char *, int, 0, kh_str_hash_func, kh_str_hash_equal)\n+KHASHL_SET_INIT(KH_LOCAL, kh_str, str, const char *, kh_hash_str, kh_eq_str)\n \n static int do_handle_client(struct fsmonitor_daemon_state *state,\n \t\t\t    const char *command,\ndiff --git a/delta-islands.c b/delta-islands.c\nindex ee2318d45a..aa35839f15 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -10,14 +10,14 @@\n #include \"diff.h\"\n #include \"progress.h\"\n #include \"refs.h\"\n-#include \"khash.h\"\n+#include \"khashl.h\"\n #include \"pack-bitmap.h\"\n #include \"pack-objects.h\"\n #include \"delta-islands.h\"\n #include \"oid-array.h\"\n #include \"config.h\"\n \n-KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\n+KHASHL_MAP_INIT(KH_LOCAL, kh_str, str, const char *, void *, kh_hash_str, kh_eq_str)\n \n static kh_oid_map_t *island_marks;\n static unsigned island_counter;\ndiff --git a/khash.h b/khash.h\ndeleted file mode 100644\nindex ff88163177..0000000000\n--- a/khash.h\n+++ /dev/null\n@@ -1,338 +0,0 @@\n-/* The MIT License\n-\n-   Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk>\n-\n-   Permission is hereby granted, free of charge, to any person obtaining\n-   a copy of this software and associated documentation files (the\n-   \"Software\"), to deal in the Software without restriction, including\n-   without limitation the rights to use, copy, modify, merge, publish,\n-   distribute, sublicense, and/or sell copies of the Software, and to\n-   permit persons to whom the Software is furnished to do so, subject to\n-   the following conditions:\n-\n-   The above copyright notice and this permission notice shall be\n-   included in all copies or substantial portions of the Software.\n-\n-   THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND,\n-   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\n-   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\n-   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\n-   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\n-   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\n-   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\n-   SOFTWARE.\n-*/\n-\n-#ifndef __AC_KHASH_H\n-#define __AC_KHASH_H\n-\n-#include \"hash.h\"\n-\n-#define AC_VERSION_KHASH_H \"0.2.8\"\n-\n-typedef uint32_t khint32_t;\n-typedef uint64_t khint64_t;\n-\n-typedef khint32_t khint_t;\n-typedef khint_t khiter_t;\n-\n-#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)\n-#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)\n-#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)\n-#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))\n-#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))\n-#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))\n-#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))\n-\n-#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)\n-\n-#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))\n-\n-static inline khint_t __ac_X31_hash_string(const char *s)\n-{\n-\tkhint_t h = (khint_t)*s;\n-\tif (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;\n-\treturn h;\n-}\n-\n-#define kh_str_hash_func(key) __ac_X31_hash_string(key)\n-#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)\n-\n-static const double __ac_HASH_UPPER = 0.77;\n-\n-#define __KHASH_TYPE(name, khkey_t, khval_t) \\\n-\ttypedef struct kh_##name { \\\n-\t\tkhint_t n_buckets, size, n_occupied, upper_bound; \\\n-\t\tkhint32_t *flags; \\\n-\t\tkhkey_t *keys; \\\n-\t\tkhval_t *vals; \\\n-\t} kh_##name##_t;\n-\n-#define __KHASH_PROTOTYPES(name, khkey_t, khval_t)\t \t\t\t\\\n-\tkh_##name##_t *kh_init_##name(void);\t\t\t\t\t\t\\\n-\tvoid kh_destroy_##name(kh_##name##_t *h);\t\t\t\t\t\\\n-\tvoid kh_clear_##name(kh_##name##_t *h);\t\t\t\t\t\t\\\n-\tkhint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \\\n-\tvoid kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \\\n-\tkhint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \\\n-\tvoid kh_del_##name(kh_##name##_t *h, khint_t x);\n-\n-#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \\\n-\tSCOPE kh_##name##_t *kh_init_##name(void) {\t\t\t\t\t\t\t\\\n-\t\treturn (kh_##name##_t*)xcalloc(1, sizeof(kh_##name##_t));\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE void kh_release_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tfree(h->flags);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tfree((void *)h->keys);\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tfree((void *)h->vals);\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE void kh_destroy_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (h) {\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tkh_release_##name(h);\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tfree(h);\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE void kh_clear_##name(kh_##name##_t *h)\t\t\t\t\t\t\\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (h && h->flags) {\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tmemset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \\\n-\t\t\th->size = h->n_occupied = 0;\t\t\t\t\t\t\t\t\\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \t\\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (h->n_buckets) {\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tkhint_t k, i, last, mask, step = 0; \\\n-\t\t\tmask = h->n_buckets - 1;\t\t\t\t\t\t\t\t\t\\\n-\t\t\tk = __hash_func(key); i = k & mask;\t\t\t\t\t\t\t\\\n-\t\t\tlast = i; \\\n-\t\t\twhile (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \\\n-\t\t\t\ti = (i + (++step)) & mask; \\\n-\t\t\t\tif (i == last) return h->n_buckets;\t\t\t\t\t\t\\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\treturn __ac_iseither(h->flags, i)? h->n_buckets : i;\t\t\\\n-\t\t} else return 0;\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \\\n-\t{ /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \\\n-\t\tkhint32_t *new_flags = NULL;\t\t\t\t\t\t\t\t\t\t\\\n-\t\tkhint_t j = 1;\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tkroundup32(new_n_buckets); \t\t\t\t\t\t\t\t\t\\\n-\t\t\tif (new_n_buckets < 4) new_n_buckets = 4;\t\t\t\t\t\\\n-\t\t\tif (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0;\t/* requested size is too small */ \\\n-\t\t\telse { /* hash table size to be changed (shrink or expand); rehash */ \\\n-\t\t\t\tALLOC_ARRAY(new_flags, __ac_fsize(new_n_buckets)); \\\n-\t\t\t\tmemset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \\\n-\t\t\t\tif (h->n_buckets < new_n_buckets) {\t/* expand */\t\t\\\n-\t\t\t\t\tREALLOC_ARRAY(h->keys, new_n_buckets); \\\n-\t\t\t\t\tif (kh_is_map) {\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\t\tREALLOC_ARRAY(h->vals, new_n_buckets); \\\n-\t\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t} /* otherwise shrink */\t\t\t\t\t\t\t\t\\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (j) { /* rehashing is needed */\t\t\t\t\t\t\t\t\\\n-\t\t\tfor (j = 0; j != h->n_buckets; ++j) {\t\t\t\t\t\t\\\n-\t\t\t\tif (__ac_iseither(h->flags, j) == 0) {\t\t\t\t\t\\\n-\t\t\t\t\tkhkey_t key = h->keys[j];\t\t\t\t\t\t\t\\\n-\t\t\t\t\tkhval_t val;\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\tkhint_t new_mask;\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\tnew_mask = new_n_buckets - 1; \t\t\t\t\t\t\\\n-\t\t\t\t\tif (kh_is_map) val = h->vals[j];\t\t\t\t\t\\\n-\t\t\t\t\t__ac_set_isdel_true(h->flags, j);\t\t\t\t\t\\\n-\t\t\t\t\twhile (1) { /* kick-out process; sort of like in Cuckoo hashing */ \\\n-\t\t\t\t\t\tkhint_t k, i, step = 0; \\\n-\t\t\t\t\t\tk = __hash_func(key);\t\t\t\t\t\t\t\\\n-\t\t\t\t\t\ti = k & new_mask;\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\t\twhile (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \\\n-\t\t\t\t\t\t__ac_set_isempty_false(new_flags, i);\t\t\t\\\n-\t\t\t\t\t\tif (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \\\n-\t\t\t\t\t\t\t{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \\\n-\t\t\t\t\t\t\tif (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \\\n-\t\t\t\t\t\t\t__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \\\n-\t\t\t\t\t\t} else { /* write the element and jump out of the loop */ \\\n-\t\t\t\t\t\t\th->keys[i] = key;\t\t\t\t\t\t\t\\\n-\t\t\t\t\t\t\tif (kh_is_map) h->vals[i] = val;\t\t\t\\\n-\t\t\t\t\t\t\tbreak;\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tif (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \\\n-\t\t\t\tREALLOC_ARRAY(h->keys, new_n_buckets); \\\n-\t\t\t\tif (kh_is_map) REALLOC_ARRAY(h->vals, new_n_buckets); \\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tfree(h->flags); /* free the working space */\t\t\t\t\\\n-\t\t\th->flags = new_flags;\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\th->n_buckets = new_n_buckets;\t\t\t\t\t\t\t\t\\\n-\t\t\th->n_occupied = h->size;\t\t\t\t\t\t\t\t\t\\\n-\t\t\th->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tkhint_t x;\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (h->n_occupied >= h->upper_bound) { /* update the hash table */ \\\n-\t\t\tif (h->n_buckets > (h->size<<1)) {\t\t\t\t\t\t\t\\\n-\t\t\t\tkh_resize_##name(h, h->n_buckets - 1); /* clear \"deleted\" elements */ \\\n-\t\t\t} else { \\\n-\t\t\t\tkh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \\\n-\t\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\tkhint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \\\n-\t\t\tx = site = h->n_buckets; k = __hash_func(key); i = k & mask; \\\n-\t\t\tif (__ac_isempty(h->flags, i)) x = i; /* for speed up */\t\\\n-\t\t\telse {\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\tlast = i; \\\n-\t\t\t\twhile (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \\\n-\t\t\t\t\tif (__ac_isdel(h->flags, i)) site = i;\t\t\t\t\\\n-\t\t\t\t\ti = (i + (++step)) & mask; \\\n-\t\t\t\t\tif (i == last) { x = site; break; }\t\t\t\t\t\\\n-\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\tif (x == h->n_buckets) {\t\t\t\t\t\t\t\t\\\n-\t\t\t\t\tif (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \\\n-\t\t\t\t\telse x = i;\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (__ac_isempty(h->flags, x)) { /* not present at all */\t\t\\\n-\t\t\th->keys[x] = key;\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t__ac_set_isboth_false(h->flags, x);\t\t\t\t\t\t\t\\\n-\t\t\t++h->size; ++h->n_occupied;\t\t\t\t\t\t\t\t\t\\\n-\t\t\t*ret = 1;\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t} else if (__ac_isdel(h->flags, x)) { /* deleted */\t\t\t\t\\\n-\t\t\th->keys[x] = key;\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t__ac_set_isboth_false(h->flags, x);\t\t\t\t\t\t\t\\\n-\t\t\t++h->size;\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t\t*ret = 2;\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t} else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \\\n-\t\treturn x;\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\tSCOPE void kh_del_##name(kh_##name##_t *h, khint_t x)\t\t\t\t\\\n-\t{\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\tif (x != h->n_buckets && !__ac_iseither(h->flags, x)) {\t\t\t\\\n-\t\t\t__ac_set_isdel_true(h->flags, x);\t\t\t\t\t\t\t\\\n-\t\t\t--h->size;\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t\t}\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t}\n-\n-#define KHASH_DECLARE(name, khkey_t, khval_t)\t\t \t\t\t\t\t\\\n-\t__KHASH_TYPE(name, khkey_t, khval_t) \t\t\t\t\t\t\t\t\\\n-\t__KHASH_PROTOTYPES(name, khkey_t, khval_t)\n-\n-#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \\\n-\t__KHASH_TYPE(name, khkey_t, khval_t) \t\t\t\t\t\t\t\t\\\n-\t__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)\n-\n-#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \\\n-\tKHASH_INIT2(name, MAYBE_UNUSED static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)\n-\n-/* Other convenient macros... */\n-\n-/*! @function\n-  @abstract     Test whether a bucket contains data.\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @param  x     Iterator to the bucket [khint_t]\n-  @return       1 if containing data; 0 otherwise [int]\n- */\n-#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))\n-\n-/*! @function\n-  @abstract     Get key given an iterator\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @param  x     Iterator to the bucket [khint_t]\n-  @return       Key [type of keys]\n- */\n-#define kh_key(h, x) ((h)->keys[x])\n-\n-/*! @function\n-  @abstract     Get value given an iterator\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @param  x     Iterator to the bucket [khint_t]\n-  @return       Value [type of values]\n-  @discussion   For hash sets, calling this results in segfault.\n- */\n-#define kh_val(h, x) ((h)->vals[x])\n-\n-/*! @function\n-  @abstract     Alias of kh_val()\n- */\n-#define kh_value(h, x) ((h)->vals[x])\n-\n-/*! @function\n-  @abstract     Get the start iterator\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @return       The start iterator [khint_t]\n- */\n-#define kh_begin(h) (khint_t)(0)\n-\n-/*! @function\n-  @abstract     Get the end iterator\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @return       The end iterator [khint_t]\n- */\n-#define kh_end(h) ((h)->n_buckets)\n-\n-/*! @function\n-  @abstract     Get the number of elements in the hash table\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @return       Number of elements in the hash table [khint_t]\n- */\n-#define kh_size(h) ((h)->size)\n-\n-/*! @function\n-  @abstract     Get the number of buckets in the hash table\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @return       Number of buckets in the hash table [khint_t]\n- */\n-#define kh_n_buckets(h) ((h)->n_buckets)\n-\n-/*! @function\n-  @abstract     Iterate over the entries in the hash table\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @param  kvar  Variable to which key will be assigned\n-  @param  vvar  Variable to which value will be assigned\n-  @param  code  Block of code to execute\n- */\n-#define kh_foreach(h, kvar, vvar, code) { khint_t __i;\t\t\\\n-\tfor (__i = kh_begin(h); __i != kh_end(h); ++__i) {\t\t\\\n-\t\tif (!kh_exist(h,__i)) continue;\t\t\t\t\t\t\\\n-\t\t(kvar) = kh_key(h,__i);\t\t\t\t\t\t\t\t\\\n-\t\t(vvar) = kh_val(h,__i);\t\t\t\t\t\t\t\t\\\n-\t\tcode;\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t} }\n-\n-/*! @function\n-  @abstract     Iterate over the values in the hash table\n-  @param  h     Pointer to the hash table [khash_t(name)*]\n-  @param  vvar  Variable to which value will be assigned\n-  @param  code  Block of code to execute\n- */\n-#define kh_foreach_value(h, vvar, code) { khint_t __i;\t\t\\\n-\tfor (__i = kh_begin(h); __i != kh_end(h); ++__i) {\t\t\\\n-\t\tif (!kh_exist(h,__i)) continue;\t\t\t\t\t\t\\\n-\t\t(vvar) = kh_val(h,__i);\t\t\t\t\t\t\t\t\\\n-\t\tcode;\t\t\t\t\t\t\t\t\t\t\t\t\\\n-\t} }\n-\n-static inline unsigned int oidhash_by_value(struct object_id oid)\n-{\n-\treturn oidhash(&oid);\n-}\n-\n-static inline int oideq_by_value(struct object_id a, struct object_id b)\n-{\n-\treturn oideq(&a, &b);\n-}\n-\n-KHASH_INIT(oid_set, struct object_id, int, 0, oidhash_by_value, oideq_by_value)\n-\n-KHASH_INIT(oid_map, struct object_id, void *, 1, oidhash_by_value, oideq_by_value)\n-\n-KHASH_INIT(oid_pos, struct object_id, int, 1, oidhash_by_value, oideq_by_value)\n-\n-#endif /* __AC_KHASH_H */\ndiff --git a/khashl.h b/khashl.h\nnew file mode 100644\nindex 0000000000..3660fd2ce4\n--- /dev/null\n+++ b/khashl.h\n@@ -0,0 +1,522 @@\n+/* The MIT License\n+\n+   Copyright (c) 2019-2023 by Attractive Chaos <attractor@live.co.uk>\n+\n+   Permission is hereby granted, free of charge, to any person obtaining\n+   a copy of this software and associated documentation files (the\n+   \"Software\"), to deal in the Software without restriction, including\n+   without limitation the rights to use, copy, modify, merge, publish,\n+   distribute, sublicense, and/or sell copies of the Software, and to\n+   permit persons to whom the Software is furnished to do so, subject to\n+   the following conditions:\n+\n+   The above copyright notice and this permission notice shall be\n+   included in all copies or substantial portions of the Software.\n+\n+   THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND,\n+   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\n+   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\n+   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\n+   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\n+   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\n+   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\n+   SOFTWARE.\n+*/\n+\n+#ifndef __AC_KHASHL_H\n+#define __AC_KHASHL_H\n+\n+#include \"hash.h\"\n+\n+#define AC_VERSION_KHASHL_H \"0.2\"\n+\n+typedef uint32_t khint32_t;\n+typedef uint64_t khint64_t;\n+\n+typedef khint32_t khint_t;\n+typedef khint_t khiter_t;\n+\n+#define kh_inline inline /* portably handled elsewhere */\n+#define KH_LOCAL static kh_inline MAYBE_UNUSED\n+\n+#ifndef kcalloc\n+#define kcalloc(N,Z) xcalloc(N,Z)\n+#endif\n+#ifndef kfree\n+#define kfree(P) free(P)\n+#endif\n+\n+/****************************\n+ * Simple private functions *\n+ ****************************/\n+\n+#define __kh_used(flag, i)       (flag[i>>5] >> (i&0x1fU) & 1U)\n+#define __kh_set_used(flag, i)   (flag[i>>5] |= 1U<<(i&0x1fU))\n+#define __kh_set_unused(flag, i) (flag[i>>5] &= ~(1U<<(i&0x1fU)))\n+\n+#define __kh_fsize(m) ((m) < 32? 1 : (m)>>5)\n+\n+static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); }\n+\n+/*******************\n+ * Hash table base *\n+ *******************/\n+\n+#define __KHASHL_TYPE(HType, khkey_t) \\\n+\ttypedef struct HType { \\\n+\t\tkhint_t bits, count; \\\n+\t\tkhint32_t *used; \\\n+\t\tkhkey_t *keys; \\\n+\t} HType;\n+\n+#define __KHASHL_PROTOTYPES(HType, prefix, khkey_t) \\\n+\textern HType *prefix##_init(void); \\\n+\textern void prefix##_destroy(HType *h); \\\n+\textern void prefix##_clear(HType *h); \\\n+\textern khint_t prefix##_getp(const HType *h, const khkey_t *key); \\\n+\textern void prefix##_resize(HType *h, khint_t new_n_buckets); \\\n+\textern khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent); \\\n+\textern void prefix##_del(HType *h, khint_t k);\n+\n+#define __KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \\\n+\tSCOPE HType *prefix##_init(void) { \\\n+\t\treturn (HType*)kcalloc(1, sizeof(HType)); \\\n+\t} \\\n+\tSCOPE void prefix##_release(HType *h) { \\\n+\t\tkfree((void *)h->keys); kfree(h->used); \\\n+\t} \\\n+\tSCOPE void prefix##_destroy(HType *h) { \\\n+\t\tif (!h) return; \\\n+\t\tprefix##_release(h); \\\n+\t\tkfree(h); \\\n+\t} \\\n+\tSCOPE void prefix##_clear(HType *h) { \\\n+\t\tif (h && h->used) { \\\n+\t\t\tkhint_t n_buckets = (khint_t)1U << h->bits; \\\n+\t\t\tmemset(h->used, 0, __kh_fsize(n_buckets) * sizeof(khint32_t)); \\\n+\t\t\th->count = 0; \\\n+\t\t} \\\n+\t}\n+\n+#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\tSCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \\\n+\t\tkhint_t i, last, n_buckets, mask; \\\n+\t\tif (h->keys == 0) return 0; \\\n+\t\tn_buckets = (khint_t)1U << h->bits; \\\n+\t\tmask = n_buckets - 1U; \\\n+\t\ti = last = __kh_h2b(hash, h->bits); \\\n+\t\twhile (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \\\n+\t\t\ti = (i + 1U) & mask; \\\n+\t\t\tif (i == last) return n_buckets; \\\n+\t\t} \\\n+\t\treturn !__kh_used(h->used, i)? n_buckets : i; \\\n+\t} \\\n+\tSCOPE khint_t prefix##_getp(const HType *h, const khkey_t *key) { return prefix##_getp_core(h, key, __hash_fn(*key)); } \\\n+\tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { return prefix##_getp_core(h, &key, __hash_fn(key)); }\n+\n+#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\tSCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \\\n+\t\tkhint32_t *new_used = 0; \\\n+\t\tkhint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \\\n+\t\twhile ((x >>= 1) != 0) ++j; \\\n+\t\tif (new_n_buckets & (new_n_buckets - 1)) ++j; \\\n+\t\tnew_bits = j > 2? j : 2; \\\n+\t\tnew_n_buckets = (khint_t)1U << new_bits; \\\n+\t\tif (h->count > (new_n_buckets>>1) + (new_n_buckets>>2)) return; /* noop, requested size is too small */ \\\n+\t\tnew_used = (khint32_t*)kcalloc(__kh_fsize(new_n_buckets), sizeof(khint32_t)); \\\n+\t\tn_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \\\n+\t\tif (n_buckets < new_n_buckets) { /* expand */ \\\n+\t\t\tREALLOC_ARRAY(h->keys, new_n_buckets); \\\n+\t\t} /* otherwise shrink */ \\\n+\t\tnew_mask = new_n_buckets - 1; \\\n+\t\tfor (j = 0; j != n_buckets; ++j) { \\\n+\t\t\tkhkey_t key; \\\n+\t\t\tif (!__kh_used(h->used, j)) continue; \\\n+\t\t\tkey = h->keys[j]; \\\n+\t\t\t__kh_set_unused(h->used, j); \\\n+\t\t\twhile (1) { /* kick-out process; sort of like in Cuckoo hashing */ \\\n+\t\t\t\tkhint_t i; \\\n+\t\t\t\ti = __kh_h2b(__hash_fn(key), new_bits); \\\n+\t\t\t\twhile (__kh_used(new_used, i)) i = (i + 1) & new_mask; \\\n+\t\t\t\t__kh_set_used(new_used, i); \\\n+\t\t\t\tif (i < n_buckets && __kh_used(h->used, i)) { /* kick out the existing element */ \\\n+\t\t\t\t\t{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \\\n+\t\t\t\t\t__kh_set_unused(h->used, i); /* mark it as deleted in the old hash table */ \\\n+\t\t\t\t} else { /* write the element and jump out of the loop */ \\\n+\t\t\t\t\th->keys[i] = key; \\\n+\t\t\t\t\tbreak; \\\n+\t\t\t\t} \\\n+\t\t\t} \\\n+\t\t} \\\n+\t\tif (n_buckets > new_n_buckets) /* shrink the hash table */ \\\n+\t\t\tREALLOC_ARRAY(h->keys, new_n_buckets); \\\n+\t\tkfree(h->used); /* free the working space */ \\\n+\t\th->used = new_used, h->bits = new_bits; \\\n+\t}\n+\n+#define __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\tSCOPE khint_t prefix##_putp_core(HType *h, const khkey_t *key, khint_t hash, int *absent) { \\\n+\t\tkhint_t n_buckets, i, last, mask; \\\n+\t\tn_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \\\n+\t\t*absent = -1; \\\n+\t\tif (h->count >= (n_buckets>>1) + (n_buckets>>2)) { /* rehashing */ \\\n+\t\t\tprefix##_resize(h, n_buckets + 1U); \\\n+\t\t\tn_buckets = (khint_t)1U<<h->bits; \\\n+\t\t} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \\\n+\t\tmask = n_buckets - 1; \\\n+\t\ti = last = __kh_h2b(hash, h->bits); \\\n+\t\twhile (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \\\n+\t\t\ti = (i + 1U) & mask; \\\n+\t\t\tif (i == last) break; \\\n+\t\t} \\\n+\t\tif (!__kh_used(h->used, i)) { /* not present at all */ \\\n+\t\t\th->keys[i] = *key; \\\n+\t\t\t__kh_set_used(h->used, i); \\\n+\t\t\t++h->count; \\\n+\t\t\t*absent = 1; \\\n+\t\t} else *absent = 0; /* Don't touch h->keys[i] if present */ \\\n+\t\treturn i; \\\n+\t} \\\n+\tSCOPE khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent) { return prefix##_putp_core(h, key, __hash_fn(*key), absent); } \\\n+\tSCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { return prefix##_putp_core(h, &key, __hash_fn(key), absent); }\n+\n+#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \\\n+\tSCOPE int prefix##_del(HType *h, khint_t i) { \\\n+\t\tkhint_t j = i, k, mask, n_buckets; \\\n+\t\tif (h->keys == 0) return 0; \\\n+\t\tn_buckets = (khint_t)1U<<h->bits; \\\n+\t\tmask = n_buckets - 1U; \\\n+\t\twhile (1) { \\\n+\t\t\tj = (j + 1U) & mask; \\\n+\t\t\tif (j == i || !__kh_used(h->used, j)) break; /* j==i only when the table is completely full */ \\\n+\t\t\tk = __kh_h2b(__hash_fn(h->keys[j]), h->bits); \\\n+\t\t\tif ((j > i && (k <= i || k > j)) || (j < i && (k <= i && k > j))) \\\n+\t\t\t\th->keys[i] = h->keys[j], i = j; \\\n+\t\t} \\\n+\t\t__kh_set_unused(h->used, i); \\\n+\t\t--h->count; \\\n+\t\treturn 1; \\\n+\t}\n+\n+#define KHASHL_DECLARE(HType, prefix, khkey_t) \\\n+\t__KHASHL_TYPE(HType, khkey_t) \\\n+\t__KHASHL_PROTOTYPES(HType, prefix, khkey_t)\n+\n+/* compatibility wrappers to make khash -> khashl migration easier */\n+#define __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t) \\\n+\ttypedef HType HType##_t; \\\n+\tSCOPE HType *kh_init_##prefix(void) { return prefix##_init(); } \\\n+\tSCOPE void kh_release_##prefix(HType *h) { prefix##_release(h); } \\\n+\tSCOPE void kh_destroy_##prefix(HType *h) { prefix##_destroy(h); } \\\n+\tSCOPE void kh_clear_##prefix(HType *h) { prefix##_clear(h); } \\\n+\tSCOPE khint_t kh_get_##prefix(const HType *h, khkey_t key) { \\\n+\t\treturn prefix##_get(h, key); \\\n+\t} \\\n+\tSCOPE void kh_resize_##prefix(HType *h, khint_t new_n_buckets) { \\\n+\t\tprefix##_resize(h, new_n_buckets); \\\n+\t} \\\n+\tSCOPE khint_t kh_put_##prefix(HType *h, khkey_t key, int *absent) { \\\n+\t\treturn prefix##_put(h, key, absent); \\\n+\t} \\\n+\tSCOPE int kh_del_##prefix(HType *h, khint_t i) { \\\n+\t\treturn prefix##_del(h, i); \\\n+\t}\n+\n+#define KHASHL_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\t__KHASHL_TYPE(HType, khkey_t) \\\n+\t__KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \\\n+\t__KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\t__KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\t__KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\t__KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn)\n+\n+/***************************\n+ * Ensemble of hash tables *\n+ ***************************/\n+\n+typedef struct {\n+\tkhint_t sub, pos;\n+} kh_ensitr_t;\n+\n+#define KHASHE_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\tKHASHL_INIT(KH_LOCAL, HType##_sub, prefix##_sub, khkey_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct HType { \\\n+\t\tkhint64_t count:54, bits:8; \\\n+\t\tHType##_sub *sub; \\\n+\t} HType; \\\n+\tSCOPE HType *prefix##_init(int bits) { \\\n+\t\tHType *g; \\\n+\t\tg = (HType*)kcalloc(1, sizeof(*g)); \\\n+\t\tg->bits = bits; \\\n+\t\tg->sub = (HType##_sub*)kcalloc(1U<<bits, sizeof(*g->sub)); \\\n+\t\treturn g; \\\n+\t} \\\n+\tSCOPE void prefix##_destroy(HType *g) { \\\n+\t\tint t; \\\n+\t\tif (!g) return; \\\n+\t\tfor (t = 0; t < 1<<g->bits; ++t) { kfree((void*)g->sub[t].keys); kfree(g->sub[t].used); } \\\n+\t\tkfree(g->sub); kfree(g); \\\n+\t} \\\n+\tSCOPE kh_ensitr_t prefix##_getp(const HType *g, const khkey_t *key) { \\\n+\t\tkhint_t hash, low, ret; \\\n+\t\tkh_ensitr_t r; \\\n+\t\tHType##_sub *h; \\\n+\t\thash = __hash_fn(*key); \\\n+\t\tlow = hash & ((1U<<g->bits) - 1); \\\n+\t\th = &g->sub[low]; \\\n+\t\tret = prefix##_sub_getp_core(h, key, hash); \\\n+\t\tif (ret == 1U<<h->bits) r.sub = low, r.pos = (khint_t)-1; \\\n+\t\telse r.sub = low, r.pos = ret; \\\n+\t\treturn r; \\\n+\t} \\\n+\tSCOPE kh_ensitr_t prefix##_get(const HType *g, const khkey_t key) { return prefix##_getp(g, &key); } \\\n+\tSCOPE kh_ensitr_t prefix##_putp(HType *g, const khkey_t *key, int *absent) { \\\n+\t\tkhint_t hash, low, ret; \\\n+\t\tkh_ensitr_t r; \\\n+\t\tHType##_sub *h; \\\n+\t\thash = __hash_fn(*key); \\\n+\t\tlow = hash & ((1U<<g->bits) - 1); \\\n+\t\th = &g->sub[low]; \\\n+\t\tret = prefix##_sub_putp_core(h, key, hash, absent); \\\n+\t\tif (*absent) ++g->count; \\\n+\t\tif (ret == 1U<<h->bits) r.sub = low, r.pos = (khint_t)-1; \\\n+\t\telse r.sub = low, r.pos = ret; \\\n+\t\treturn r; \\\n+\t} \\\n+\tSCOPE kh_ensitr_t prefix##_put(HType *g, const khkey_t key, int *absent) { return prefix##_putp(g, &key, absent); } \\\n+\tSCOPE int prefix##_del(HType *g, kh_ensitr_t itr) { \\\n+\t\tHType##_sub *h = &g->sub[itr.sub]; \\\n+\t\tint ret; \\\n+\t\tret = prefix##_sub_del(h, itr.pos); \\\n+\t\tif (ret) --g->count; \\\n+\t\treturn ret; \\\n+\t}\n+\n+/*****************************\n+ * More convenient interface *\n+ *****************************/\n+\n+#define __kh_packed /* noop, we use -Werror=address-of-packed-member */\n+#define __kh_cached_hash(x) ((x).hash)\n+\n+#define KHASHL_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct { khkey_t key; } __kh_packed HType##_s_bucket_t; \\\n+\tstatic kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \\\n+\tstatic kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \\\n+\tKHASHL_INIT(KH_LOCAL, HType, prefix##_s, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \\\n+\tSCOPE HType *prefix##_init(void) { return prefix##_s_init(); } \\\n+\tSCOPE void prefix##_release(HType *h) { prefix##_s_release(h); } \\\n+\tSCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \\\n+\tSCOPE void prefix##_clear(HType *h) { prefix##_s_clear(h); } \\\n+\tSCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_s_resize(h, new_n_buckets); } \\\n+\tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \\\n+\tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \\\n+\tSCOPE 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); } \\\n+\t__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)\n+\n+#define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \\\n+\tstatic kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \\\n+\tstatic kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \\\n+\tKHASHL_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \\\n+\tSCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \\\n+\tSCOPE void prefix##_release(HType *h) { prefix##_m_release(h); } \\\n+\tSCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \\\n+\tSCOPE void prefix##_clear(HType *h) { prefix##_m_clear(h); } \\\n+\tSCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_m_resize(h, new_n_buckets); } \\\n+\tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \\\n+\tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \\\n+\tSCOPE 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); } \\\n+\t__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)\n+\n+#define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \\\n+\tstatic kh_inline int prefix##_cs_eq(HType##_cs_bucket_t x, HType##_cs_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \\\n+\tKHASHL_INIT(KH_LOCAL, HType, prefix##_cs, HType##_cs_bucket_t, __kh_cached_hash, prefix##_cs_eq) \\\n+\tSCOPE HType *prefix##_init(void) { return prefix##_cs_init(); } \\\n+\tSCOPE void prefix##_destroy(HType *h) { prefix##_cs_destroy(h); } \\\n+\tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cs_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cs_getp(h, &t); } \\\n+\tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cs_del(h, k); } \\\n+\tSCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cs_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cs_putp(h, &t, absent); }\n+\n+#define KHASHL_CMAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct { khkey_t key; kh_val_t val; khint_t hash; } __kh_packed HType##_cm_bucket_t; \\\n+\tstatic kh_inline int prefix##_cm_eq(HType##_cm_bucket_t x, HType##_cm_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \\\n+\tKHASHL_INIT(KH_LOCAL, HType, prefix##_cm, HType##_cm_bucket_t, __kh_cached_hash, prefix##_cm_eq) \\\n+\tSCOPE HType *prefix##_init(void) { return prefix##_cm_init(); } \\\n+\tSCOPE void prefix##_destroy(HType *h) { prefix##_cm_destroy(h); } \\\n+\tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cm_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cm_getp(h, &t); } \\\n+\tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cm_del(h, k); } \\\n+\tSCOPE 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); }\n+\n+#define KHASHE_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \\\n+\ttypedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \\\n+\tstatic kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \\\n+\tstatic kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \\\n+\tKHASHE_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \\\n+\tSCOPE HType *prefix##_init(int bits) { return prefix##_m_init(bits); } \\\n+\tSCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \\\n+\tSCOPE 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); } \\\n+\tSCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_m_del(h, k); } \\\n+\tSCOPE 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); }\n+\n+/**************************\n+ * Public macro functions *\n+ **************************/\n+\n+#define kh_bucket(h, x) ((h)->keys[x])\n+\n+/*! @function\n+  @abstract     Get the number of elements in the hash table\n+  @param  h     Pointer to the hash table\n+  @return       Number of elements in the hash table [khint_t]\n+ */\n+#define kh_size(h) ((h)->count)\n+\n+#define kh_capacity(h) ((h)->keys? 1U<<(h)->bits : 0U)\n+\n+/*! @function\n+  @abstract     Get the end iterator\n+  @param  h     Pointer to the hash table\n+  @return       The end iterator [khint_t]\n+ */\n+#define kh_end(h) kh_capacity(h)\n+\n+/*! @function\n+  @abstract     Get key given an iterator\n+  @param  h     Pointer to the hash table\n+  @param  x     Iterator to the bucket [khint_t]\n+  @return       Key [type of keys]\n+ */\n+#define kh_key(h, x) ((h)->keys[x].key)\n+\n+/*! @function\n+  @abstract     Get value given an iterator\n+  @param  h     Pointer to the hash table\n+  @param  x     Iterator to the bucket [khint_t]\n+  @return       Value [type of values]\n+  @discussion   For hash sets, calling this results in segfault.\n+ */\n+#define kh_val(h, x) ((h)->keys[x].val)\n+\n+/*! @function\n+  @abstract     Alias of kh_val()\n+ */\n+#define kh_value(h, x) kh_val(h, x)\n+\n+/*! @function\n+  @abstract     Test whether a bucket contains data.\n+  @param  h     Pointer to the hash table\n+  @param  x     Iterator to the bucket [khint_t]\n+  @return       1 if containing data; 0 otherwise [int]\n+ */\n+#define kh_exist(h, x) __kh_used((h)->used, (x))\n+\n+#define kh_ens_key(g, x) kh_key(&(g)->sub[(x).sub], (x).pos)\n+#define kh_ens_val(g, x) kh_val(&(g)->sub[(x).sub], (x).pos)\n+#define kh_ens_exist(g, x) kh_exist(&(g)->sub[(x).sub], (x).pos)\n+#define kh_ens_is_end(x) ((x).pos == (khint_t)-1)\n+#define kh_ens_size(g) ((g)->count)\n+\n+/**************************************\n+ * Common hash and equality functions *\n+ **************************************/\n+\n+#define kh_eq_generic(a, b) ((a) == (b))\n+#define kh_eq_str(a, b) (strcmp((a), (b)) == 0)\n+#define kh_hash_dummy(x) ((khint_t)(x))\n+\n+static kh_inline khint_t kh_hash_uint32(khint_t key) {\n+\tkey += ~(key << 15);\n+\tkey ^=  (key >> 10);\n+\tkey +=  (key << 3);\n+\tkey ^=  (key >> 6);\n+\tkey += ~(key << 11);\n+\tkey ^=  (key >> 16);\n+\treturn key;\n+}\n+\n+static kh_inline khint_t kh_hash_uint64(khint64_t key) {\n+\tkey = ~key + (key << 21);\n+\tkey = key ^ key >> 24;\n+\tkey = (key + (key << 3)) + (key << 8);\n+\tkey = key ^ key >> 14;\n+\tkey = (key + (key << 2)) + (key << 4);\n+\tkey = key ^ key >> 28;\n+\tkey = key + (key << 31);\n+\treturn (khint_t)key;\n+}\n+\n+#define KH_FNV_SEED 11\n+\n+static kh_inline khint_t kh_hash_str(const char *s) { /* FNV1a */\n+\tkhint_t h = KH_FNV_SEED ^ 2166136261U;\n+\tconst unsigned char *t = (const unsigned char*)s;\n+\tfor (; *t; ++t)\n+\t\th ^= *t, h *= 16777619;\n+\treturn h;\n+}\n+\n+static kh_inline khint_t kh_hash_bytes(int len, const unsigned char *s) {\n+\tkhint_t h = KH_FNV_SEED ^ 2166136261U;\n+\tint i;\n+\tfor (i = 0; i < len; ++i)\n+\t\th ^= s[i], h *= 16777619;\n+\treturn h;\n+}\n+\n+/*! @function\n+  @abstract     Get the start iterator\n+  @param  h     Pointer to the hash table\n+  @return       The start iterator [khint_t]\n+ */\n+#define kh_begin(h) (khint_t)(0)\n+\n+/*! @function\n+  @abstract     Iterate over the entries in the hash table\n+  @param  h     Pointer to the hash table\n+  @param  kvar  Variable to which key will be assigned\n+  @param  vvar  Variable to which value will be assigned\n+  @param  code  Block of code to execute\n+ */\n+#define kh_foreach(h, kvar, vvar, code) { khint_t __i;\t\t\\\n+\tfor (__i = kh_begin(h); __i != kh_end(h); ++__i) {\t\\\n+\t\tif (!kh_exist(h,__i)) continue;\t\t\t\\\n+\t\t(kvar) = kh_key(h,__i);\t\t\t\t\\\n+\t\t(vvar) = kh_val(h,__i);\t\t\t\t\\\n+\t\tcode;\t\t\t\t\t\t\\\n+\t} }\n+\n+/*! @function\n+  @abstract     Iterate over the values in the hash table\n+  @param  h     Pointer to the hash table\n+  @param  vvar  Variable to which value will be assigned\n+  @param  code  Block of code to execute\n+ */\n+#define kh_foreach_value(h, vvar, code) { khint_t __i;\t\t\\\n+\tfor (__i = kh_begin(h); __i != kh_end(h); ++__i) {\t\\\n+\t\tif (!kh_exist(h,__i)) continue;\t\t\t\\\n+\t\t(vvar) = kh_val(h,__i);\t\t\t\t\\\n+\t\tcode;\t\t\t\t\t\t\\\n+\t} }\n+\n+static inline unsigned int oidhash_by_value(struct object_id oid)\n+{\n+\treturn oidhash(&oid);\n+}\n+\n+static inline int oideq_by_value(struct object_id a, struct object_id b)\n+{\n+\treturn oideq(&a, &b);\n+}\n+\n+KHASHL_SET_INIT(KH_LOCAL, kh_oid_set, oid_set, struct object_id,\n+\t\toidhash_by_value, oideq_by_value)\n+\n+KHASHL_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,\n+\t\toidhash_by_value, oideq_by_value)\n+\n+KHASHL_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,\n+\t\toidhash_by_value, oideq_by_value)\n+\n+#endif /* __AC_KHASHL_H */\ndiff --git a/object-store-ll.h b/object-store-ll.h\nindex 26a3895c82..401c4beff5 100644\n--- a/object-store-ll.h\n+++ b/object-store-ll.h\n@@ -160,7 +160,7 @@ struct raw_object_store {\n \t */\n \tstruct object_directory *odb;\n \tstruct object_directory **odb_tail;\n-\tstruct kh_odb_path_map *odb_by_path;\n+\tstruct odb_path_map *odb_by_path;\n \n \tint loaded_alternates;\n \ndiff --git a/object-store.h b/object-store.h\nindex 1b3e3d7d01..3db4802e86 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -1,11 +1,12 @@\n #ifndef OBJECT_STORE_H\n #define OBJECT_STORE_H\n \n-#include \"khash.h\"\n+#include \"khashl.h\"\n #include \"dir.h\"\n #include \"object-store-ll.h\"\n \n-KHASH_INIT(odb_path_map, const char * /* key: odb_path */,\n-\tstruct object_directory *, 1, fspathhash, fspatheq)\n+KHASHL_MAP_INIT(KH_LOCAL, odb_path_map, odb_path_map,\n+\tconst char * /* key: odb_path */, struct object_directory *,\n+\tfspathhash, fspatheq)\n \n #endif /* OBJECT_STORE_H */\ndiff --git a/oidset.h b/oidset.h\nindex 262f4256d6..17af1b6708 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,7 +1,7 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n-#include \"khash.h\"\n+#include \"khashl.h\"\n \n /**\n  * This API is similar to oid-array, in that it maintains a set of object ids\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex c7dea13217..d018365f24 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -2,7 +2,7 @@\n #define PACK_BITMAP_H\n \n #include \"ewah/ewok.h\"\n-#include \"khash.h\"\n+#include \"khashl.h\"\n #include \"pack.h\"\n #include \"pack-objects.h\"\n #include \"string-list.h\"\n"},{"id":"491539","messageId":"20240325230704.262272-4-e@80x24.org","threadId":"61203","inReplyTo":"20240325230704.262272-1-e@80x24.org","subject":"[PATCH 3/3] khashl: fix ensemble lookups on empty table","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-25T23:07:03Z","receivedAt":"2024-03-25T23:07:31Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"The ->bits field of regular khashl structs is invalid when\nthe ->keys array is NULL.  Thus the ensemble *_getp implementation\nmust follow existing *_get and *_getp usage conventions and\ncheck the iterator against kh_end().\n\nThis fixes a fast-import crash on t3427-rebase-subtree.sh in an\nabandoned commit to use the ensemble implementation for oid_map\nand oid_pos.  I've abandoned the aforementioned commit for now\nsince it was more intrusive, more expensive for small tables,\nand realloc(3) on glibc is already optimized using mremap(2) for\nlarge hash resizes.\n\nSigned-off-by: Eric Wong <e@80x24.org>\n---\n khashl.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/khashl.h b/khashl.h\nindex 3660fd2ce4..8ffe80fbb2 100644\n--- a/khashl.h\n+++ b/khashl.h\n@@ -265,7 +265,7 @@ typedef struct {\n \t\tlow = hash & ((1U<<g->bits) - 1); \\\n \t\th = &g->sub[low]; \\\n \t\tret = prefix##_sub_getp_core(h, key, hash); \\\n-\t\tif (ret == 1U<<h->bits) r.sub = low, r.pos = (khint_t)-1; \\\n+\t\tif (ret >= kh_end(h)) r.sub = low, r.pos = (khint_t)-1; \\\n \t\telse r.sub = low, r.pos = ret; \\\n \t\treturn r; \\\n \t} \\\n"},{"id":"491540","messageId":"20240325230704.262272-5-e@80x24.org","threadId":"61203","inReplyTo":"20240325230704.262272-1-e@80x24.org","subject":"[REJECT 4/3] switch to khashl ensemble","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-25T23:07:04Z","receivedAt":"2024-03-25T23:07:38Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Using an ensemble of hash tables to implement a larger one can\nreduce the temporary space required to resize a hash table.\nHowever, I haven't been able to measure an improvement using\nglibc memusage(1), yet.\n\nI could be tuning it wrong (too few or too many sub hash\ntables), and it may not be useful with glibc malloc since large\nrealloc(3) are optimized with mremap(2) to provide in-place\ngrowth.\n---\n builtin/fast-import.c | 10 ++++----\n builtin/replay.c      | 10 ++++----\n delta-islands.c       | 54 +++++++++++++++++++-------------------\n fsck.c                | 10 ++++----\n khashl.h              | 60 ++++++++++++++++++++++++++++++++-----------\n pack-bitmap-write.c   |  4 +--\n pack-bitmap.c         | 32 +++++++++++------------\n 7 files changed, 105 insertions(+), 75 deletions(-)\n\ndiff --git a/builtin/fast-import.c b/builtin/fast-import.c\nindex 29e50fd675..190e136e2e 100644\n--- a/builtin/fast-import.c\n+++ b/builtin/fast-import.c\n@@ -2198,7 +2198,7 @@ static uintmax_t change_note_fanout(struct tree_entry *root,\n static int parse_mapped_oid_hex(const char *hex, struct object_id *oid, const char **end)\n {\n \tint algo;\n-\tkhiter_t it;\n+\tkh_ensitr_t it;\n \n \t/* Make SHA-1 object IDs have all-zero padding. */\n \tmemset(oid->hash, 0, sizeof(oid->hash));\n@@ -2209,13 +2209,13 @@ static int parse_mapped_oid_hex(const char *hex, struct object_id *oid, const ch\n \n \tit = kh_get_oid_map(sub_oid_map, *oid);\n \t/* No such object? */\n-\tif (it == kh_end(sub_oid_map)) {\n+\tif (kh_ens_is_end(it)) {\n \t\t/* If we're using the same algorithm, pass it through. */\n \t\tif (hash_algos[algo].format_id == the_hash_algo->format_id)\n \t\t\treturn 0;\n \t\treturn -1;\n \t}\n-\toidcpy(oid, kh_value(sub_oid_map, it));\n+\toidcpy(oid, kh_ens_val(sub_oid_map, it));\n \treturn 0;\n }\n \n@@ -3083,13 +3083,13 @@ static void insert_mapped_mark(uintmax_t mark, void *object, void *cbp)\n \tstruct object_id *fromoid = object;\n \tstruct object_id *tooid = find_mark(cbp, mark);\n \tint ret;\n-\tkhiter_t it;\n+\tkh_ensitr_t it;\n \n \tit = kh_put_oid_map(sub_oid_map, *fromoid, &ret);\n \t/* We've already seen this object. */\n \tif (ret == 0)\n \t\treturn;\n-\tkh_value(sub_oid_map, it) = tooid;\n+\tkh_ens_val(sub_oid_map, it) = tooid;\n }\n \n static void build_mark_map_one(struct mark_set *from, struct mark_set *to)\ndiff --git a/builtin/replay.c b/builtin/replay.c\nindex 6bc4b47f09..e084da8a94 100644\n--- a/builtin/replay.c\n+++ b/builtin/replay.c\n@@ -227,10 +227,10 @@ static struct commit *mapped_commit(kh_oid_map_t *replayed_commits,\n \t\t\t\t    struct commit *commit,\n \t\t\t\t    struct commit *fallback)\n {\n-\tkhint_t pos = kh_get_oid_map(replayed_commits, commit->object.oid);\n-\tif (pos == kh_end(replayed_commits))\n+\tkh_ensitr_t pos = kh_get_oid_map(replayed_commits, commit->object.oid);\n+\tif (kh_ens_is_end(pos))\n \t\treturn fallback;\n-\treturn kh_value(replayed_commits, pos);\n+\treturn kh_ens_val(replayed_commits, pos);\n }\n \n static struct commit *pick_regular_commit(struct commit *pickme,\n@@ -381,7 +381,7 @@ int cmd_replay(int argc, const char **argv, const char *prefix)\n \treplayed_commits = kh_init_oid_map();\n \twhile ((commit = get_revision(&revs))) {\n \t\tconst struct name_decoration *decoration;\n-\t\tkhint_t pos;\n+\t\tkh_ensitr_t pos;\n \t\tint hr;\n \n \t\tif (!commit->parents)\n@@ -399,7 +399,7 @@ int cmd_replay(int argc, const char **argv, const char *prefix)\n \t\tif (hr == 0)\n \t\t\tBUG(\"Duplicate rewritten commit: %s\\n\",\n \t\t\t    oid_to_hex(&commit->object.oid));\n-\t\tkh_value(replayed_commits, pos) = last_commit;\n+\t\tkh_ens_val(replayed_commits, pos) = last_commit;\n \n \t\t/* Update any necessary branches */\n \t\tif (advance_name)\ndiff --git a/delta-islands.c b/delta-islands.c\nindex aa35839f15..de159e98a8 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -90,7 +90,7 @@ static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n \n int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n {\n-\tkhiter_t trg_pos, src_pos;\n+\tkh_ensitr_t trg_pos, src_pos;\n \n \t/* If we aren't using islands, assume everything goes together. */\n \tif (!island_marks)\n@@ -101,7 +101,7 @@ int in_same_island(const struct object_id *trg_oid, const struct object_id *src_\n \t * against anything -- it's not an important object\n \t */\n \ttrg_pos = kh_get_oid_map(island_marks, *trg_oid);\n-\tif (trg_pos >= kh_end(island_marks))\n+\tif (kh_ens_is_end(trg_pos))\n \t\treturn 1;\n \n \t/*\n@@ -109,28 +109,28 @@ int in_same_island(const struct object_id *trg_oid, const struct object_id *src_\n \t * we don't want to base any deltas on it!\n \t */\n \tsrc_pos = kh_get_oid_map(island_marks, *src_oid);\n-\tif (src_pos >= kh_end(island_marks))\n+\tif (kh_ens_is_end(src_pos))\n \t\treturn 0;\n \n-\treturn island_bitmap_is_subset(kh_value(island_marks, trg_pos),\n-\t\t\t\tkh_value(island_marks, src_pos));\n+\treturn island_bitmap_is_subset(kh_ens_val(island_marks, trg_pos),\n+\t\t\t\tkh_ens_val(island_marks, src_pos));\n }\n \n int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n {\n-\tkhiter_t a_pos, b_pos;\n+\tkh_ensitr_t a_pos, b_pos;\n \tstruct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;\n \n \tif (!island_marks)\n \t\treturn 0;\n \n \ta_pos = kh_get_oid_map(island_marks, *a);\n-\tif (a_pos < kh_end(island_marks))\n-\t\ta_bitmap = kh_value(island_marks, a_pos);\n+\tif (!kh_ens_is_end(a_pos))\n+\t\ta_bitmap = kh_ens_val(island_marks, a_pos);\n \n \tb_pos = kh_get_oid_map(island_marks, *b);\n-\tif (b_pos < kh_end(island_marks))\n-\t\tb_bitmap = kh_value(island_marks, b_pos);\n+\tif (!kh_ens_is_end(b_pos))\n+\t\tb_bitmap = kh_ens_val(island_marks, b_pos);\n \n \tif (a_bitmap) {\n \t\tif (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))\n@@ -146,20 +146,20 @@ int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n \n static struct island_bitmap *create_or_get_island_marks(struct object *obj)\n {\n-\tkhiter_t pos;\n+\tkh_ensitr_t pos;\n \tint hash_ret;\n \n \tpos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);\n \tif (hash_ret)\n-\t\tkh_value(island_marks, pos) = island_bitmap_new(NULL);\n+\t\tkh_ens_val(island_marks, pos) = island_bitmap_new(NULL);\n \n-\treturn kh_value(island_marks, pos);\n+\treturn kh_ens_val(island_marks, pos);\n }\n \n static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n {\n \tstruct island_bitmap *b;\n-\tkhiter_t pos;\n+\tkh_ensitr_t pos;\n \tint hash_ret;\n \n \tpos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);\n@@ -169,7 +169,7 @@ static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n \t\t * parent.\n \t\t */\n \t\tmarks->refcount++;\n-\t\tkh_value(island_marks, pos) = marks;\n+\t\tkh_ens_val(island_marks, pos) = marks;\n \t\treturn;\n \t}\n \n@@ -177,10 +177,10 @@ static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n \t * We do have it. Make sure we split any copy-on-write before\n \t * updating.\n \t */\n-\tb = kh_value(island_marks, pos);\n+\tb = kh_ens_val(island_marks, pos);\n \tif (b->refcount > 1) {\n \t\tb->refcount--;\n-\t\tb = kh_value(island_marks, pos) = island_bitmap_new(b);\n+\t\tb = kh_ens_val(island_marks, pos) = island_bitmap_new(b);\n \t}\n \tisland_bitmap_or(b, marks);\n }\n@@ -272,13 +272,13 @@ void resolve_tree_islands(struct repository *r,\n \t\tstruct tree *tree;\n \t\tstruct tree_desc desc;\n \t\tstruct name_entry entry;\n-\t\tkhiter_t pos;\n+\t\tkh_ensitr_t pos;\n \n \t\tpos = kh_get_oid_map(island_marks, ent->idx.oid);\n-\t\tif (pos >= kh_end(island_marks))\n+\t\tif (kh_ens_is_end(pos))\n \t\t\tcontinue;\n \n-\t\troot_marks = kh_value(island_marks, pos);\n+\t\troot_marks = kh_ens_val(island_marks, pos);\n \n \t\ttree = lookup_tree(r, &ent->idx.oid);\n \t\tif (!tree || parse_tree(tree) < 0)\n@@ -499,11 +499,11 @@ void load_delta_islands(struct repository *r, int progress)\n \n void propagate_island_marks(struct commit *commit)\n {\n-\tkhiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);\n+\tkh_ensitr_t pos = kh_get_oid_map(island_marks, commit->object.oid);\n \n-\tif (pos < kh_end(island_marks)) {\n+\tif (!kh_ens_is_end(pos)) {\n \t\tstruct commit_list *p;\n-\t\tstruct island_bitmap *root_marks = kh_value(island_marks, pos);\n+\t\tstruct island_bitmap *root_marks = kh_ens_val(island_marks, pos);\n \n \t\trepo_parse_commit(the_repository, commit);\n \t\tset_island_marks(&repo_get_commit_tree(the_repository, commit)->object,\n@@ -518,7 +518,7 @@ void free_island_marks(void)\n \tstruct island_bitmap *bitmap;\n \n \tif (island_marks) {\n-\t\tkh_foreach_value(island_marks, bitmap, {\n+\t\tkh_ens_foreach_value(island_marks, bitmap, {\n \t\t\tif (!--bitmap->refcount)\n \t\t\t\tfree(bitmap);\n \t\t});\n@@ -538,12 +538,12 @@ int compute_pack_layers(struct packing_data *to_pack)\n \n \tfor (i = 0; i < to_pack->nr_objects; ++i) {\n \t\tstruct object_entry *entry = &to_pack->objects[i];\n-\t\tkhiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);\n+\t\tkh_ensitr_t pos = kh_get_oid_map(island_marks, entry->idx.oid);\n \n \t\toe_set_layer(to_pack, entry, 1);\n \n-\t\tif (pos < kh_end(island_marks)) {\n-\t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n+\t\tif (!kh_ens_is_end(pos)) {\n+\t\t\tstruct island_bitmap *bitmap = kh_ens_val(island_marks, pos);\n \n \t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n \t\t\t\toe_set_layer(to_pack, entry, 0);\ndiff --git a/fsck.c b/fsck.c\nindex 8ded0a473a..4c67e1e64c 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -266,13 +266,13 @@ void fsck_enable_object_names(struct fsck_options *options)\n const char *fsck_get_object_name(struct fsck_options *options,\n \t\t\t\t const struct object_id *oid)\n {\n-\tkhiter_t pos;\n+\tkh_ensitr_t pos;\n \tif (!options->object_names)\n \t\treturn NULL;\n \tpos = kh_get_oid_map(options->object_names, *oid);\n-\tif (pos >= kh_end(options->object_names))\n+\tif (kh_ens_is_end(pos))\n \t\treturn NULL;\n-\treturn kh_value(options->object_names, pos);\n+\treturn kh_ens_val(options->object_names, pos);\n }\n \n void fsck_put_object_name(struct fsck_options *options,\n@@ -281,7 +281,7 @@ void fsck_put_object_name(struct fsck_options *options,\n {\n \tva_list ap;\n \tstruct strbuf buf = STRBUF_INIT;\n-\tkhiter_t pos;\n+\tkh_ensitr_t pos;\n \tint hashret;\n \n \tif (!options->object_names)\n@@ -292,7 +292,7 @@ void fsck_put_object_name(struct fsck_options *options,\n \t\treturn;\n \tva_start(ap, fmt);\n \tstrbuf_vaddf(&buf, fmt, ap);\n-\tkh_value(options->object_names, pos) = strbuf_detach(&buf, NULL);\n+\tkh_ens_val(options->object_names, pos) = strbuf_detach(&buf, NULL);\n \tva_end(ap);\n }\n \ndiff --git a/khashl.h b/khashl.h\nindex 8ffe80fbb2..e950593d61 100644\n--- a/khashl.h\n+++ b/khashl.h\n@@ -203,22 +203,22 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26\n \t__KHASHL_PROTOTYPES(HType, prefix, khkey_t)\n \n /* compatibility wrappers to make khash -> khashl migration easier */\n-#define __KHASH_COMPAT(SCOPE, HType, prefix, khkey_t) \\\n+#define __KHASH_COMPAT(SCOPE, kh_idx, HType, prefix, khkey_t) \\\n \ttypedef HType HType##_t; \\\n \tSCOPE HType *kh_init_##prefix(void) { return prefix##_init(); } \\\n \tSCOPE void kh_release_##prefix(HType *h) { prefix##_release(h); } \\\n \tSCOPE void kh_destroy_##prefix(HType *h) { prefix##_destroy(h); } \\\n \tSCOPE void kh_clear_##prefix(HType *h) { prefix##_clear(h); } \\\n-\tSCOPE khint_t kh_get_##prefix(const HType *h, khkey_t key) { \\\n+\tSCOPE kh_idx kh_get_##prefix(const HType *h, khkey_t key) { \\\n \t\treturn prefix##_get(h, key); \\\n \t} \\\n \tSCOPE void kh_resize_##prefix(HType *h, khint_t new_n_buckets) { \\\n \t\tprefix##_resize(h, new_n_buckets); \\\n \t} \\\n-\tSCOPE khint_t kh_put_##prefix(HType *h, khkey_t key, int *absent) { \\\n+\tSCOPE kh_idx kh_put_##prefix(HType *h, khkey_t key, int *absent) { \\\n \t\treturn prefix##_put(h, key, absent); \\\n \t} \\\n-\tSCOPE int kh_del_##prefix(HType *h, khint_t i) { \\\n+\tSCOPE int kh_del_##prefix(HType *h, kh_idx i) { \\\n \t\treturn prefix##_del(h, i); \\\n \t}\n \n@@ -244,18 +244,32 @@ typedef struct {\n \t\tkhint64_t count:54, bits:8; \\\n \t\tHType##_sub *sub; \\\n \t} HType; \\\n-\tSCOPE HType *prefix##_init(int bits) { \\\n-\t\tHType *g; \\\n-\t\tg = (HType*)kcalloc(1, sizeof(*g)); \\\n+\tSCOPE HType *prefix##_init_bits(HType *g, size_t bits) { \\\n \t\tg->bits = bits; \\\n \t\tg->sub = (HType##_sub*)kcalloc(1U<<bits, sizeof(*g->sub)); \\\n \t\treturn g; \\\n \t} \\\n+\tSCOPE HType *prefix##_init(void) { \\\n+\t\tHType *g; \\\n+\t\tg = (HType*)kcalloc(1, sizeof(*g)); \\\n+\t\treturn prefix##_init_bits(g, 6); /* unsure about default */ \\\n+\t} \\\n+\tSCOPE void prefix##_release(HType *g) { \\\n+\t\tint t; \\\n+\t\tfor (t = 0; t < 1<<g->bits; ++t) \\\n+\t\t\tprefix##_sub_release(&g->sub[t]); \\\n+\t\tkfree(g->sub); \\\n+\t} \\\n \tSCOPE void prefix##_destroy(HType *g) { \\\n+\t\tif (!g) return; \\\n+\t\tprefix##_release(g); \\\n+\t\tkfree(g); \\\n+\t} \\\n+\tSCOPE void prefix##_clear(HType *g) { \\\n \t\tint t; \\\n \t\tif (!g) return; \\\n-\t\tfor (t = 0; t < 1<<g->bits; ++t) { kfree((void*)g->sub[t].keys); kfree(g->sub[t].used); } \\\n-\t\tkfree(g->sub); kfree(g); \\\n+\t\tfor (t = 0; t < 1<<g->bits; ++t) \\\n+\t\t\tprefix##_sub_clear(&g->sub[t]); \\\n \t} \\\n \tSCOPE kh_ensitr_t prefix##_getp(const HType *g, const khkey_t *key) { \\\n \t\tkhint_t hash, low, ret; \\\n@@ -312,7 +326,7 @@ typedef struct {\n \tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \\\n \tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \\\n \tSCOPE 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); } \\\n-\t__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)\n+\t__KHASH_COMPAT(SCOPE, khint_t, HType, prefix, khkey_t)\n \n #define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \\\n \ttypedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \\\n@@ -327,7 +341,7 @@ typedef struct {\n \tSCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \\\n \tSCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \\\n \tSCOPE 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); } \\\n-\t__KHASH_COMPAT(SCOPE, HType, prefix, khkey_t)\n+\t__KHASH_COMPAT(SCOPE, khint_t, HType, prefix, khkey_t)\n \n #define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n \ttypedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \\\n@@ -354,11 +368,15 @@ typedef struct {\n \tstatic kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \\\n \tstatic kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \\\n \tKHASHE_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \\\n-\tSCOPE HType *prefix##_init(int bits) { return prefix##_m_init(bits); } \\\n+\tSCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \\\n+\tSCOPE void prefix##_release(HType *h) { prefix##_m_release(h); } \\\n \tSCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \\\n+\tSCOPE void prefix##_clear(HType *h) { prefix##_m_clear(h); } \\\n+\tSCOPE void prefix##_resize(HType *h, khint_t ignore) { /* noop */ } \\\n \tSCOPE 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); } \\\n \tSCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_m_del(h, k); } \\\n-\tSCOPE 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); }\n+\tSCOPE 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); } \\\n+\t__KHASH_COMPAT(SCOPE, kh_ensitr_t, HType, prefix, khkey_t)\n \n /**************************\n  * Public macro functions *\n@@ -487,6 +505,18 @@ static kh_inline khint_t kh_hash_bytes(int len, const unsigned char *s) {\n \t\tcode;\t\t\t\t\t\t\\\n \t} }\n \n+#define kh_ens_foreach(g, kvar, vvar, code) do { \\\n+\tsize_t t; \\\n+\tfor (t = 0; t < 1<<g->bits; ++t) \\\n+\t\tkh_foreach(&g->sub[t], kvar, vvar, code); \\\n+} while (0)\n+\n+#define kh_ens_foreach_value(g, vvar, code) do { \\\n+\tsize_t t; \\\n+\tfor (t = 0; t < 1<<g->bits; ++t) \\\n+\t\tkh_foreach_value(&g->sub[t], vvar, code); \\\n+} while (0)\n+\n /*! @function\n   @abstract     Iterate over the values in the hash table\n   @param  h     Pointer to the hash table\n@@ -513,10 +543,10 @@ static inline int oideq_by_value(struct object_id a, struct object_id b)\n KHASHL_SET_INIT(KH_LOCAL, kh_oid_set, oid_set, struct object_id,\n \t\toidhash_by_value, oideq_by_value)\n \n-KHASHL_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,\n+KHASHE_MAP_INIT(KH_LOCAL, kh_oid_map, oid_map, struct object_id, void *,\n \t\toidhash_by_value, oideq_by_value)\n \n-KHASHL_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,\n+KHASHE_MAP_INIT(KH_LOCAL, kh_oid_pos, oid_pos, struct object_id, int,\n \t\toidhash_by_value, oideq_by_value)\n \n #endif /* __AC_KHASHL_H */\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 990a9498d7..bbf2090c46 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -465,7 +465,7 @@ static int fill_bitmap_commit(struct bb_commit *ent,\n static void store_selected(struct bb_commit *ent, struct commit *commit)\n {\n \tstruct bitmapped_commit *stored = &writer.selected[ent->idx];\n-\tkhiter_t hash_pos;\n+\tkh_ensitr_t hash_pos;\n \tint hash_ret;\n \n \tstored->bitmap = bitmap_to_ewah(ent->bitmap);\n@@ -474,7 +474,7 @@ static void store_selected(struct bb_commit *ent, struct commit *commit)\n \tif (hash_ret == 0)\n \t\tdie(\"Duplicate entry when writing index: %s\",\n \t\t    oid_to_hex(&commit->object.oid));\n-\tkh_value(writer.bitmaps, hash_pos) = stored;\n+\tkh_ens_val(writer.bitmaps, hash_pos) = stored;\n }\n \n int bitmap_writer_build(struct packing_data *to_pack)\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 2baeabacee..68cd893dee 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -214,7 +214,7 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,\n \t\t\t\t\t  int flags)\n {\n \tstruct stored_bitmap *stored;\n-\tkhiter_t hash_pos;\n+\tkh_ensitr_t hash_pos;\n \tint ret;\n \n \tstored = xmalloc(sizeof(struct stored_bitmap));\n@@ -235,7 +235,7 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,\n \t\treturn NULL;\n \t}\n \n-\tkh_value(index->bitmaps, hash_pos) = stored;\n+\tkh_ens_val(index->bitmaps, hash_pos) = stored;\n \treturn stored;\n }\n \n@@ -721,7 +721,7 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_\n \tstatic size_t xor_items_nr = 0, xor_items_alloc = 0;\n \tstatic int is_corrupt = 0;\n \tint xor_flags;\n-\tkhiter_t hash_pos;\n+\tkh_ensitr_t hash_pos;\n \tstruct bitmap_lookup_table_xor_item *xor_item;\n \n \tif (is_corrupt)\n@@ -766,8 +766,8 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_\n \t\t * has already been stored. So, assign this stored bitmap\n \t\t * to the xor_bitmap.\n \t\t */\n-\t\tif (hash_pos < kh_end(bitmap_git->bitmaps) &&\n-\t\t\t(xor_bitmap = kh_value(bitmap_git->bitmaps, hash_pos)))\n+\t\tif (!kh_ens_is_end(hash_pos) &&\n+\t\t\t(xor_bitmap = kh_ens_val(bitmap_git->bitmaps, hash_pos)))\n \t\t\tbreak;\n \t\txor_items_nr++;\n \t\txor_row = triplet.xor_row;\n@@ -841,9 +841,9 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_\n struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,\n \t\t\t\t      struct commit *commit)\n {\n-\tkhiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,\n+\tkh_ensitr_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,\n \t\t\t\t\t   commit->object.oid);\n-\tif (hash_pos >= kh_end(bitmap_git->bitmaps)) {\n+\tif (kh_ens_is_end(hash_pos)) {\n \t\tstruct stored_bitmap *bitmap = NULL;\n \t\tif (!bitmap_git->table_lookup)\n \t\t\treturn NULL;\n@@ -855,17 +855,17 @@ struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,\n \t\t\treturn NULL;\n \t\treturn lookup_stored_bitmap(bitmap);\n \t}\n-\treturn lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));\n+\treturn lookup_stored_bitmap(kh_ens_val(bitmap_git->bitmaps, hash_pos));\n }\n \n static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,\n \t\t\t\t\t   const struct object_id *oid)\n {\n \tkh_oid_pos_t *positions = bitmap_git->ext_index.positions;\n-\tkhiter_t pos = kh_get_oid_pos(positions, *oid);\n+\tkh_ensitr_t pos = kh_get_oid_pos(positions, *oid);\n \n-\tif (pos < kh_end(positions)) {\n-\t\tint bitmap_pos = kh_value(positions, pos);\n+\tif (!kh_ens_is_end(pos)) {\n+\t\tint bitmap_pos = kh_ens_val(positions, pos);\n \t\treturn bitmap_pos + bitmap_num_objects(bitmap_git);\n \t}\n \n@@ -913,7 +913,7 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git,\n {\n \tstruct eindex *eindex = &bitmap_git->ext_index;\n \n-\tkhiter_t hash_pos;\n+\tkh_ensitr_t hash_pos;\n \tint hash_ret;\n \tint bitmap_pos;\n \n@@ -928,10 +928,10 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git,\n \t\tbitmap_pos = eindex->count;\n \t\teindex->objects[eindex->count] = object;\n \t\teindex->hashes[eindex->count] = pack_name_hash(name);\n-\t\tkh_value(eindex->positions, hash_pos) = bitmap_pos;\n+\t\tkh_ens_val(eindex->positions, hash_pos) = bitmap_pos;\n \t\teindex->count++;\n \t} else {\n-\t\tbitmap_pos = kh_value(eindex->positions, hash_pos);\n+\t\tbitmap_pos = kh_ens_val(eindex->positions, hash_pos);\n \t}\n \n \treturn bitmap_pos + bitmap_num_objects(bitmap_git);\n@@ -2361,7 +2361,7 @@ int test_bitmap_commits(struct repository *r)\n \t\t\tdie(_(\"failed to load bitmap indexes\"));\n \t}\n \n-\tkh_foreach(bitmap_git->bitmaps, oid, value, {\n+\tkh_ens_foreach(bitmap_git->bitmaps, oid, value, {\n \t\tprintf_ln(\"%s\", oid_to_hex(&oid));\n \t});\n \n@@ -2479,7 +2479,7 @@ void free_bitmap_index(struct bitmap_index *b)\n \tewah_pool_free(b->tags);\n \tif (b->bitmaps) {\n \t\tstruct stored_bitmap *sb;\n-\t\tkh_foreach_value(b->bitmaps, sb, {\n+\t\tkh_ens_foreach_value(b->bitmaps, sb, {\n \t\t\tewah_pool_free(sb->root);\n \t\t\tfree(sb);\n \t\t});\n"},{"id":"491541","messageId":"20240325230704.262272-1-e@80x24.org","threadId":"61203","inReplyTo":null,"subject":"[PATCH 0/3] switch to tombstone-free khashl table","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-25T23:07:00Z","receivedAt":"2024-03-25T23:15:41Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"The memory improvement is minor, but any memory reduction at all\nis welcome at this point.  Fortunately, this set of changes is\nunintrusive.\n\nI have some other ideas that I'll hopefully get to implement before\nswapping kills all my SSDs (see bottom).\n\nEric Wong (3):\n  list-objects-filter: use kh_size API\n  treewide: switch to khashl for memory savings\n  khashl: fix ensemble lookups on empty table\n\n builtin/fast-import.c       |   2 +-\n builtin/fsmonitor--daemon.c |   4 +-\n delta-islands.c             |   4 +-\n khash.h                     | 338 -----------------------\n khashl.h                    | 522 ++++++++++++++++++++++++++++++++++++\n list-objects-filter.c       |   2 +-\n object-store-ll.h           |   2 +-\n object-store.h              |   7 +-\n oidset.h                    |   2 +-\n pack-bitmap.h               |   2 +-\n 10 files changed, 535 insertions(+), 350 deletions(-)\n delete mode 100644 khash.h\n create mode 100644 khashl.h\n\nTODO (some ideas stolen from khashl):\n\n* obj_hash can probably use a 0.75 load factor (instead of 0.5)\n  to save memory and not slow down too much.  oid_* khash has\n  always had 0.77 which was fine and now khashl has 0.75.\n  0.75 is cheaper to compute via (shifts + ORs) than 0.77.\n\n* obj_hash can use `i = (i + 1) & mask' like khashl does to\n  avoid branches in linear probe loops\n\n* obj_hash can use realloc and copy in-place resize logic khashl does.\n  khashl uses the ->used bitmap for this, but it should be\n  possible to do for obj_hash w/o additional allocations\n  via pointer tagging\n\n(not khashl inspired):\n\n* keep an identity pool of OIDs separately (similar to how Perl5\n  pools all hash keys) and only use tagged pointers for OIDs.\n  Pointer tagging can be used to distinguish between 7 hash\n  functions, leaving us room for 5 more in addition to SHA-(1|256).\n  This change will be a large effort (with a hopefully large savings).\n  If we ever need more than 7 hash functions, we can switch to\n  storing hash type information in slabs that can be looked up\n  using address ranges (AFAIK, jemalloc does this).\n"},{"id":"491586","messageId":"xmqqy1a4ao3t.fsf@gitster.g","threadId":"61203","inReplyTo":"20240325230704.262272-1-e@80x24.org","subject":"Re: [PATCH 0/3] switch to tombstone-free khashl table","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-26T17:40:06Z","receivedAt":"2024-03-26T17:40:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Wong <e@80x24.org> writes:\n\n> The memory improvement is minor, but any memory reduction at all\n> is welcome at this point.  Fortunately, this set of changes is\n> unintrusive.\n>\n> I have some other ideas that I'll hopefully get to implement before\n> swapping kills all my SSDs (see bottom).\n\nPlease describe what this topic aims at to sell the topic better.\nAre we trying to reduce memory footprint?  In other words, if this\ntopic were to hit a released version of Git, what would the short\nparagraph description for the topic in the release notes look like?\n\n * The khash.h hashtable implementation has been replaced with\n   khashl.h that is mostly API compatible with reduced memory\n   consumption, simpler insertion and a bit slower deletion.\n\nor somesuch.\n\nA performance oriented topic would be helped to have benchmark\nnumbers to show how much improvement it makes and a memory reduction\ntopic would be helped to have some numbers in the cover letter.  It\nis OK to summarize/duplicate what appears in the proposed log\nmessage of some step; it does not need too much text to say 100MB\ntotal allocations reduced by 10MB or something like that, for\nexample.\n\nAn API improvement topic would be helped to have an example rewrite\nof a caller (or just a reference to a representative one, i.e., \"see\nhow the caller in function X gets simplified in [PATCH 04/28]\") in\nthe cover letter.\n\nA bugfix topic would be helped to have an end-user visible effect in\nthe cover letter.\n\nThanks.\n\n"},{"id":"491587","messageId":"xmqqttksanpj.fsf@gitster.g","threadId":"61203","inReplyTo":"20240325230704.262272-3-e@80x24.org","subject":"Re: [PATCH 2/3] treewide: switch to khashl for memory savings","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-26T17:48:40Z","receivedAt":"2024-03-26T17:48:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Wong <e@80x24.org> writes:\n\n> khashl is an updated version of khash with less memory overhead\n> (one bit/bucket instead of two) than the original khash and\n> similar overall performance.  Insertions are simpler (linear\n> probing) but deletions may be slightly slower[1].  Of course,\n> the majority of hash tables in git do not delete individual\n> elements.\n\n$ make builtin/fast-import.sp ;# part of make sparse\n    SP builtin/fast-import.c\nbuiltin/fast-import.c: note: in included file (through oidset.h, packfile.h):\nkhashl.h:516:1: error: Using plain integer as NULL pointer\nkhashl.h:516:1: error: Using plain integer as NULL pointer\nmake: *** [Makefile:3237: builtin/fast-import.sp] Error 1\n\nI found IMPL_GET and IMPL_DEL's use of (h->keys == 0) were giving\none of these two, and managed to reduce the error to just one with\nthe attached patch, but I don't know what the other error is coming\nfrom.\n\n khashl.h | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git c/khashl.h w/khashl.h\nindex 8ffe80fbb2..663e36cd2d 100644\n--- c/khashl.h\n+++ w/khashl.h\n@@ -101,7 +101,7 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26\n #define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n \tSCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \\\n \t\tkhint_t i, last, n_buckets, mask; \\\n-\t\tif (h->keys == 0) return 0; \\\n+\t\tif (!h->keys) return 0; \\\n \t\tn_buckets = (khint_t)1U << h->bits; \\\n \t\tmask = n_buckets - 1U; \\\n \t\ti = last = __kh_h2b(hash, h->bits); \\\n@@ -183,7 +183,7 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26\n #define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \\\n \tSCOPE int prefix##_del(HType *h, khint_t i) { \\\n \t\tkhint_t j = i, k, mask, n_buckets; \\\n-\t\tif (h->keys == 0) return 0; \\\n+\t\tif (!h->keys) return 0; \\\n \t\tn_buckets = (khint_t)1U<<h->bits; \\\n \t\tmask = n_buckets - 1U; \\\n \t\twhile (1) { \\\n\n\n\n\t\n"},{"id":"491677","messageId":"20240327093710.GA847433@coredump.intra.peff.net","threadId":"61203","inReplyTo":"xmqqttksanpj.fsf@gitster.g","subject":"Re: [PATCH 2/3] treewide: switch to khashl for memory savings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-03-27T09:37:10Z","receivedAt":"2024-03-27T09:37:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 26, 2024 at 10:48:40AM -0700, Junio C Hamano wrote:\n\n> $ make builtin/fast-import.sp ;# part of make sparse\n>     SP builtin/fast-import.c\n> builtin/fast-import.c: note: in included file (through oidset.h, packfile.h):\n> khashl.h:516:1: error: Using plain integer as NULL pointer\n> khashl.h:516:1: error: Using plain integer as NULL pointer\n> make: *** [Makefile:3237: builtin/fast-import.sp] Error 1\n> \n> I found IMPL_GET and IMPL_DEL's use of (h->keys == 0) were giving\n> one of these two, and managed to reduce the error to just one with\n> the attached patch, but I don't know what the other error is coming\n> from.\n\nProbably:\n\ndiff --git a/khashl.h b/khashl.h\nindex 8fcebed237..1e724bbf88 100644\n--- a/khashl.h\n+++ b/khashl.h\n@@ -116,7 +116,7 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26\n \n #define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n \tSCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \\\n-\t\tkhint32_t *new_used = 0; \\\n+\t\tkhint32_t *new_used = NULL; \\\n \t\tkhint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \\\n \t\twhile ((x >>= 1) != 0) ++j; \\\n \t\tif (new_n_buckets & (new_n_buckets - 1)) ++j; \\\n\n-Peff\n"},{"id":"491712","messageId":"xmqq7chn1gtx.fsf@gitster.g","threadId":"61203","inReplyTo":"20240327093710.GA847433@coredump.intra.peff.net","subject":"Re: [PATCH 2/3] treewide: switch to khashl for memory savings","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-27T21:54:18Z","receivedAt":"2024-03-27T21:54:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Mar 26, 2024 at 10:48:40AM -0700, Junio C Hamano wrote:\n>\n>> $ make builtin/fast-import.sp ;# part of make sparse\n>>     SP builtin/fast-import.c\n>> builtin/fast-import.c: note: in included file (through oidset.h, packfile.h):\n>> khashl.h:516:1: error: Using plain integer as NULL pointer\n>> khashl.h:516:1: error: Using plain integer as NULL pointer\n>> make: *** [Makefile:3237: builtin/fast-import.sp] Error 1\n>> \n>> I found IMPL_GET and IMPL_DEL's use of (h->keys == 0) were giving\n>> one of these two, and managed to reduce the error to just one with\n>> the attached patch, but I don't know what the other error is coming\n>> from.\n>\n> Probably:\n>\n> diff --git a/khashl.h b/khashl.h\n> index 8fcebed237..1e724bbf88 100644\n> --- a/khashl.h\n> +++ b/khashl.h\n> @@ -116,7 +116,7 @@ static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 26\n>  \n>  #define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \\\n>  \tSCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { \\\n> -\t\tkhint32_t *new_used = 0; \\\n> +\t\tkhint32_t *new_used = NULL; \\\n>  \t\tkhint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \\\n>  \t\twhile ((x >>= 1) != 0) ++j; \\\n>  \t\tif (new_n_buckets & (new_n_buckets - 1)) ++j; \\\n>\n> -Peff\n\nSpot on.  With this (and the other two 0 -> NULL fixes), and with\nthe SWAP() thing in brian's credential series fixed, the tip of\n'seen' passes the static-analysis and sparse CI jobs again.\n\nThanks.\n"},{"id":"493237","messageId":"xmqqy19959b2.fsf@gitster.g","threadId":"61203","inReplyTo":"xmqqy1a4ao3t.fsf@gitster.g","subject":"Re: [PATCH 0/3] switch to tombstone-free khashl table","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-04-19T21:31:13Z","receivedAt":"2024-04-19T21:31:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Eric Wong <e@80x24.org> writes:\n>\n>> The memory improvement is minor, but any memory reduction at all\n>> is welcome at this point.  Fortunately, this set of changes is\n>> unintrusive.\n>>\n>> I have some other ideas that I'll hopefully get to implement before\n>> swapping kills all my SSDs (see bottom).\n>\n> Please describe what this topic aims at to sell the topic better.\n> Are we trying to reduce memory footprint?  In other words, if this\n> topic were to hit a released version of Git, what would the short\n> paragraph description for the topic in the release notes look like?\n> ...\n\nSo, did anything happened since this exchange?  I remember that we\ncaught and fixed a few minor sparse errors, but other than that, I\nam not sure what to do with this topic.\n\nNot that I want to merge loud tree-wide topics down during the\nprerelease period...\n\nThanks.\n"},{"id":"493238","messageId":"20240419214644.M168521@dcvr","threadId":"61203","inReplyTo":"xmqqy19959b2.fsf@gitster.g","subject":"Re: [PATCH 0/3] switch to tombstone-free khashl table","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-04-19T21:46:44Z","receivedAt":"2024-04-19T21:52:19Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> > Eric Wong <e@80x24.org> writes:\n> >\n> >> The memory improvement is minor, but any memory reduction at all\n> >> is welcome at this point.  Fortunately, this set of changes is\n> >> unintrusive.\n> >>\n> >> I have some other ideas that I'll hopefully get to implement before\n> >> swapping kills all my SSDs (see bottom).\n> >\n> > Please describe what this topic aims at to sell the topic better.\n> > Are we trying to reduce memory footprint?  In other words, if this\n> > topic were to hit a released version of Git, what would the short\n> > paragraph description for the topic in the release notes look like?\n> > ...\n> \n> So, did anything happened since this exchange?  I remember that we\n> caught and fixed a few minor sparse errors, but other than that, I\n> am not sure what to do with this topic.\n\nNot really...  I've been thinking we can beat khashl for our\npurposes usage by allowing explicit tombstones to be configured\nand getting rid of the ->used bitmap entirely.\n\nOne goal is to eventually reuse the code with the open-coded\nhash table in object.c   That said, I've been bogged down by\npersonal crap this year and don't know how/if I'll be able to\nhack on it this year.\n\n> Not that I want to merge loud tree-wide topics down during the\n> prerelease period...\n\nNo worries, we can keep it out for now and work on it\nincrementally or drop it entirely in favor of something else\ndown the line...\n\n\ngit's about to turn 20, and I really want to ensure it and the\ntools around it continue to be usable on computers from 20-25\nyears ago.\n"}]}