{"thread":{"id":"61216","subject":"[PATCH 0/3] switch to tombstone-free khashl table","startedAt":"2024-03-28T10:14:02Z","lastAt":"2024-03-28T17:56:30Z","messageCount":7,"participants":["Eric Wong","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"491737","messageId":"20240328101356.300374-1-e@80x24.org","threadId":"61216","inReplyTo":null,"subject":"[PATCH 0/3] switch to tombstone-free khashl table","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-28T10:13:53Z","receivedAt":"2024-03-28T10:14:02Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"This is another step in slowly reducing memory usage of `git gc'\nand associated tasks.  khashl is an updated version of khash\nwhich eliminates tombstones for deleted elements to save space.\n\nThe overall memory improvement with our codebase is tiny (a few\ndozen KB out of several GB at peak, about 10MB over the lifetime\nof a process).  Any memory reduction at all is welcome at this\npoint; and khashl comes with some new optional features and\nenhancements which may come in handy someday.\n\nI haven't been able to validate CPU-dependent improvements\nclaimed by the author due to system noise from working on a\nshared server.  No aberrant behavior has been noticed in\nday-to-day `production' use on public facing servers.\n\nKeep in mind the switch linear probing for performance is\nconsistent with findings made for the open-coded ->obj_hash in\nobject.c\n\nFortunately, this set of changes is unintrusive; but I'm\nhoping to have more time to make deeper changes this year.\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\nRange-diff:\n-:  ---------- > 1:  3bf3148cab list-objects-filter: use kh_size API\n1:  e74965907e ! 2:  09900edb48 treewide: switch to khashl for memory savings\n    @@ Commit message\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    +    similar overall performance.  According to its author,\n    +    insertions are simpler (linear probing) but deletions may be\n    +    slightly slower[1].  Of course, the majority of hash tables in\n    +    git do not delete individual elements.\n     \n         Overall memory usage did not decrease much, as the hash tables\n         and elements we store in them are big and currently dwarf the\n         overhead of the khash internals.  Only around 10 MB in\n    -    allocations (not peak use) is saved when doing a no-op `git gc'\n    -    of a Linux kernel object store with thousands of refs and\n    -    islands.\n    +    allocations (and a few dozen KB peak use out of ~6 GB) is saved\n    +    when doing a no-op `git gc' of a Linux kernel object store with\n    +    thousands of refs and islands.\n     \n         A summary of differences I've found from khash to khashl:\n     \n    @@ Commit message\n         * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize,\n           and *_release functions\n     \n    +    * sparse fixes from Junio and Jeff\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    @@ Commit message\n           typedef) and was the only place where I had to change a definition.\n     \n         Signed-off-by: Eric Wong <e@80x24.org>\n    +    Helped-by: Junio C Hamano <gitster@pobox.com>\n    +    Helped-by: Jeff King <peff@peff.net>\n     \n      ## builtin/fast-import.c ##\n     @@\n    @@ khashl.h (new)\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    @@ khashl.h (new)\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    @@ khashl.h (new)\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) { \\\n2:  744e1b7198 = 3:  bfb20eae37 khashl: fix ensemble lookups on empty table\n"},{"id":"491738","messageId":"20240328101356.300374-2-e@80x24.org","threadId":"61216","inReplyTo":"20240328101356.300374-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-28T10:13:54Z","receivedAt":"2024-03-28T10:14:10Z","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":"491739","messageId":"20240328101356.300374-3-e@80x24.org","threadId":"61216","inReplyTo":"20240328101356.300374-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-28T10:13:55Z","receivedAt":"2024-03-28T10:14:16Z","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.  According to its author,\ninsertions are simpler (linear probing) but deletions may be\nslightly slower[1].  Of course, the majority of hash tables in\ngit do not delete individual elements.\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 (and a few dozen KB peak use out of ~6 GB) is saved\nwhen doing a no-op `git gc' of a Linux kernel object store with\nthousands of refs and islands.\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* sparse fixes from Junio and Jeff\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>\nHelped-by: Junio C Hamano <gitster@pobox.com>\nHelped-by: Jeff King <peff@peff.net>\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..1e724bbf88\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) 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 = 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+\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) 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":"491740","messageId":"20240328101356.300374-4-e@80x24.org","threadId":"61216","inReplyTo":"20240328101356.300374-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-28T10:13:56Z","receivedAt":"2024-03-28T10:14:25Z","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 1e724bbf88..30f85dc5e2 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":"491741","messageId":"20240328101459.M24469@dcvr","threadId":"61216","inReplyTo":"20240328101356.300374-1-e@80x24.org","subject":"oops, forgot [v2]","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-28T10:14:58Z","receivedAt":"2024-03-28T10:14:59Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Sorry, been running on fumes all week :<\n"},{"id":"491754","messageId":"xmqqh6gqwdz0.fsf@gitster.g","threadId":"61216","inReplyTo":"20240328101356.300374-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-28T15:52:35Z","receivedAt":"2024-03-28T15:52:37Z","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> Fortunately, this set of changes is unintrusive; but I'm\n> hoping to have more time to make deeper changes this year.\n>\n> Eric 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>\n> Range-diff:\n> -:  ---------- > 1:  3bf3148cab list-objects-filter: use kh_size API\n> 1:  e74965907e ! 2:  09900edb48 treewide: switch to khashl for memory savings\n\nDo you have the correct range-diff?  The previous round had the\nchange to the list-object-filter.c to use kh_size() already.\n\nBut I see the 0 -> NULL fixes.  Perhaps the left-side base was off\nby one when you took the range-diff and there is nothing else going\non that we should be worried about...\n\n>     @@ Commit message\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>     +    similar overall performance.  According to its author,\n>     +    insertions are simpler (linear probing) but deletions may be\n>     +    slightly slower[1].  Of course, the majority of hash tables in\n>     +    git do not delete individual elements.\n>      \n>          Overall memory usage did not decrease much, as the hash tables\n>          and elements we store in them are big and currently dwarf the\n>          overhead of the khash internals.  Only around 10 MB in\n>     -    allocations (not peak use) is saved when doing a no-op `git gc'\n>     -    of a Linux kernel object store with thousands of refs and\n>     -    islands.\n>     +    allocations (and a few dozen KB peak use out of ~6 GB) is saved\n>     +    when doing a no-op `git gc' of a Linux kernel object store with\n>     +    thousands of refs and islands.\n>      \n>          A summary of differences I've found from khash to khashl:\n>      \n>     @@ Commit message\n>          * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize,\n>            and *_release functions\n>      \n>     +    * sparse fixes from Junio and Jeff\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>     @@ Commit message\n>            typedef) and was the only place where I had to change a definition.\n>      \n>          Signed-off-by: Eric Wong <e@80x24.org>\n>     +    Helped-by: Junio C Hamano <gitster@pobox.com>\n>     +    Helped-by: Jeff King <peff@peff.net>\n>      \n>       ## builtin/fast-import.c ##\n>      @@\n>     @@ khashl.h (new)\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>     @@ khashl.h (new)\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>     @@ khashl.h (new)\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> 2:  744e1b7198 = 3:  bfb20eae37 khashl: fix ensemble lookups on empty table\n"},{"id":"491770","messageId":"20240328175629.M707542@dcvr","threadId":"61216","inReplyTo":"xmqqh6gqwdz0.fsf@gitster.g","subject":"Re: [PATCH 0/3] switch to tombstone-free khashl table","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2024-03-28T17:56:29Z","receivedAt":"2024-03-28T17:56:30Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> wrote:\n> Eric Wong <e@80x24.org> writes:\n> > Range-diff:\n> > -:  ---------- > 1:  3bf3148cab list-objects-filter: use kh_size API\n> > 1:  e74965907e ! 2:  09900edb48 treewide: switch to khashl for memory savings\n> \n> Do you have the correct range-diff?  The previous round had the\n> change to the list-object-filter.c to use kh_size() already.\n> \n> But I see the 0 -> NULL fixes.  Perhaps the left-side base was off\n> by one when you took the range-diff and there is nothing else going\n> on that we should be worried about...\n\nOdd...  I switched to a different machine (w) for v2 due to\nconnectivity problems to the original machine (m) I did v1 on\nand applied the patches sent to the list.\n\nI did end up rebasing v1 on (w) against the newer master:\nc75fd8d815 (The eleventh batch, 2024-03-25)\ninstead of commit 11c821f2f2 (The tenth batch, 2024-03-21)\non (m).\n\nOn (w):\n\n\tgit format-patch -o $OUT/ khashl-base..khashl-v2 \\\n\t\t --cover-letter --range-diff=khashl-v1 -v2\n\nSeems to mess up infer_range_diff_ranges and it chose `khashl-v2'\ninstead of `khash-base' as the `a' part of the range for r1.\n(m) doesn't do this, both running 2.44.0.32*-ish\n\nHere it is from (w) with the explicit `a..' part for --range-diff:\n\n\tgit format-patch -o $OUT/ khashl-base..khashl-v2 \\\n\t\t --cover-letter --range-diff=khashl-base..khashl-v1 -v2\n\nRange-diff against v1:\n1:  3bf3148cab = 1:  3bf3148cab list-objects-filter: use kh_size API\n2:  e74965907e ! 2:  09900edb48 treewide: switch to khashl for memory savings\n    @@ Commit message\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    +    similar overall performance.  According to its author,\n    +    insertions are simpler (linear probing) but deletions may be\n    +    slightly slower[1].  Of course, the majority of hash tables in\n    +    git do not delete individual elements.\n     \n         Overall memory usage did not decrease much, as the hash tables\n         and elements we store in them are big and currently dwarf the\n         overhead of the khash internals.  Only around 10 MB in\n    -    allocations (not peak use) is saved when doing a no-op `git gc'\n    -    of a Linux kernel object store with thousands of refs and\n    -    islands.\n    +    allocations (and a few dozen KB peak use out of ~6 GB) is saved\n    +    when doing a no-op `git gc' of a Linux kernel object store with\n    +    thousands of refs and islands.\n     \n         A summary of differences I've found from khash to khashl:\n     \n    @@ Commit message\n         * flesh out KHASHL_{SET,MAP}_INIT wrappers with *_clear, *_resize,\n           and *_release functions\n     \n    +    * sparse fixes from Junio and Jeff\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    @@ Commit message\n           typedef) and was the only place where I had to change a definition.\n     \n         Signed-off-by: Eric Wong <e@80x24.org>\n    +    Helped-by: Junio C Hamano <gitster@pobox.com>\n    +    Helped-by: Jeff King <peff@peff.net>\n     \n      ## builtin/fast-import.c ##\n     @@\n    @@ khashl.h (new)\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    @@ khashl.h (new)\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    @@ khashl.h (new)\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) { \\\n3:  744e1b7198 = 3:  bfb20eae37 khashl: fix ensemble lookups on empty table\n"}]}