{"thread":{"id":"54763","subject":"[PATCH 1/9] oid-array.h: drop sha1 mention from header guard","startedAt":"2020-12-04T18:50:04Z","lastAt":"2020-12-07T19:27:40Z","messageCount":40,"participants":["Jeff King","Taylor Blau","Eric Sunshine","Derrick Stolee","Junio C Hamano","Ævar Arnfjörð Bjarmason"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"411342","messageId":"X8qEllD9I5eU+n06@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 1/9] oid-array.h: drop sha1 mention from header guard","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:48:54Z","receivedAt":"2020-12-04T18:50:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When this file was moved from sha1-array.h, we forgot to update the\npreprocessor header guard to match the new name.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.h | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/oid-array.h b/oid-array.h\nindex f28d322c90..2c8b64c393 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -1,5 +1,5 @@\n-#ifndef SHA1_ARRAY_H\n-#define SHA1_ARRAY_H\n+#ifndef OID_ARRAY_H\n+#define OID_ARRAY_H\n \n /**\n  * The API provides storage and manipulation of sets of object identifiers.\n@@ -106,4 +106,4 @@ void oid_array_filter(struct oid_array *array,\n \t\t      for_each_oid_fn want,\n \t\t      void *cbdata);\n \n-#endif /* SHA1_ARRAY_H */\n+#endif /* OID_ARRAY_H */\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411343","messageId":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","threadId":"54763","inReplyTo":null,"subject":"[PATCH 0/9] misc commit-graph and oid-array cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:48:35Z","receivedAt":"2020-12-04T18:50:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This series came out of an off-list discussion about using oid-array in\ncommit-graph.c to replace a similar data structure. But I found a couple\nof things to clean up along the way.\n\nSurprisingly, this doesn't conflict with Stolee's \"chunk-format API\"\nseries from yesterday. Nor any of the other commit-graph work in \"seen\".\n\n  [1/9]: oid-array.h: drop sha1 mention from header guard\n  [2/9]: t0064: drop sha1 mention from filename\n  [3/9]: t0064: make duplicate tests more robust\n  [4/9]: cache.h: move hash/oid functions to hash.h\n  [5/9]: oid-array: make sort function public\n  [6/9]: oid-array: provide a for-loop iterator\n  [7/9]: commit-graph: drop count_distinct_commits() function\n  [8/9]: commit-graph: replace packed_oid_list with oid_array\n  [9/9]: commit-graph: use size_t for array allocation and indexing\n\n cache.h                                       |  94 ---------------\n commit-graph.c                                | 107 +++---------------\n hash.h                                        |  95 ++++++++++++++++\n oid-array.c                                   |  17 ++-\n oid-array.h                                   |  33 +++++-\n t/{t0064-sha1-array.sh => t0064-oid-array.sh} |   9 +-\n 6 files changed, 156 insertions(+), 199 deletions(-)\n rename t/{t0064-sha1-array.sh => t0064-oid-array.sh} (90%)\n\n-Peff\n"},{"id":"411344","messageId":"X8qEtPrZCTrMiX/t@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 2/9] t0064: drop sha1 mention from filename","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:49:24Z","receivedAt":"2020-12-04T18:50:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The data type is an oid_array these days, and we are using \"test-tool\noid-array\", so let's name the test script appropriately.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/{t0064-sha1-array.sh => t0064-oid-array.sh} | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n rename t/{t0064-sha1-array.sh => t0064-oid-array.sh} (96%)\n\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-oid-array.sh\nsimilarity index 96%\nrename from t/t0064-sha1-array.sh\nrename to t/t0064-oid-array.sh\nindex 45685af2fd..71034a8007 100755\n--- a/t/t0064-sha1-array.sh\n+++ b/t/t0064-oid-array.sh\n@@ -1,6 +1,6 @@\n #!/bin/sh\n \n-test_description='basic tests for the SHA1 array implementation'\n+test_description='basic tests for the oid array implementation'\n . ./test-lib.sh\n \n echoid () {\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411345","messageId":"X8qE762PqN8svc9H@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 3/9] t0064: make duplicate tests more robust","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:50:23Z","receivedAt":"2020-12-04T18:51:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our tests for handling duplicates in oid-array provide only a single\nduplicate for each number, so our sorted array looks like:\n\n  44 44 55 55 88 88 aa aa\n\nA slightly more interesting test is to have multiple duplicates, which\nmakes sure that we not only skip the duplicate, but keep skipping until\nwe are out of the set of matching duplicates.\n\nUnsurprisingly this works just fine, but it's worth beefing up this test\nsince we're about to change the duplicate-detection code.\n\nNote that we do need to adjust the results on the lookup test, since it\nis returning the index of the found item (and now we have more items\nbefore our range, and the range itself is slightly larger, since we'll\naccept a match of any element).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/t0064-oid-array.sh | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t0064-oid-array.sh b/t/t0064-oid-array.sh\nindex 71034a8007..2e5438ccda 100755\n--- a/t/t0064-oid-array.sh\n+++ b/t/t0064-oid-array.sh\n@@ -25,6 +25,7 @@ test_expect_success 'ordered enumeration' '\n test_expect_success 'ordered enumeration with duplicate suppression' '\n \techoid \"\" 44 55 88 aa >expect &&\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techo for_each_unique\n@@ -52,17 +53,19 @@ test_expect_success 'lookup non-existing entry' '\n \n test_expect_success 'lookup with duplicates' '\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 55\n \t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n-\ttest \"$n\" -ge 2 &&\n-\ttest \"$n\" -le 3\n+\ttest \"$n\" -ge 3 &&\n+\ttest \"$n\" -le 5\n '\n \n test_expect_success 'lookup non-existing entry with duplicates' '\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 66\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411346","messageId":"X8qFOw2TPiu7bFpI@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 4/9] cache.h: move hash/oid functions to hash.h","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:51:39Z","receivedAt":"2020-12-04T18:52:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We define git_hash_algo and object_id in hash.h, but most of the utility\nfunctions are declared in the main cache.h. Let's move them to hash.h\nalong with their struct definitions. This cleans up cache.h a bit, but\nalso avoids circular dependencies when other headers need to know about\nthese functions (e.g., if oid-array.h were to have an inline that used\noideq(), it couldn't include cache.h because it is itself included by\ncache.h).\n\nNo including C files should be affected, because hash.h is always\nincluded in cache.h already.\n\nWe do have to mention repository.h at the top of hash.h, though, since\nwe depend on the_repository in some of our inline functions.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nPure movement, as shown by --color-moved. I wish we had a clever way to\nannotate that in emailed patches.\n\n cache.h | 94 --------------------------------------------------------\n hash.h  | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 95 insertions(+), 94 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e986cf4ea9..ec98f5d32c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1123,100 +1123,6 @@ const char *repo_find_unique_abbrev(struct repository *r, const struct object_id\n int repo_find_unique_abbrev_r(struct repository *r, char *hex, const struct object_id *oid, int len);\n #define find_unique_abbrev_r(hex, oid, len) repo_find_unique_abbrev_r(the_repository, hex, oid, len)\n \n-extern const struct object_id null_oid;\n-\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n-{\n-\t/*\n-\t * Teach the compiler that there are only two possibilities of hash size\n-\t * here, so that it can optimize for this case as much as possible.\n-\t */\n-\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n-\t\treturn memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n-\treturn memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n-}\n-\n-static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)\n-{\n-\treturn hashcmp(oid1->hash, oid2->hash);\n-}\n-\n-static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2)\n-{\n-\t/*\n-\t * We write this here instead of deferring to hashcmp so that the\n-\t * compiler can properly inline it and avoid calling memcmp.\n-\t */\n-\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n-\t\treturn !memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n-\treturn !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n-}\n-\n-static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)\n-{\n-\treturn hasheq(oid1->hash, oid2->hash);\n-}\n-\n-static inline int is_null_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, &null_oid);\n-}\n-\n-static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n-{\n-\tmemcpy(sha_dst, sha_src, the_hash_algo->rawsz);\n-}\n-\n-static inline void oidcpy(struct object_id *dst, const struct object_id *src)\n-{\n-\tmemcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);\n-}\n-\n-static inline struct object_id *oiddup(const struct object_id *src)\n-{\n-\tstruct object_id *dst = xmalloc(sizeof(struct object_id));\n-\toidcpy(dst, src);\n-\treturn dst;\n-}\n-\n-static inline void hashclr(unsigned char *hash)\n-{\n-\tmemset(hash, 0, the_hash_algo->rawsz);\n-}\n-\n-static inline void oidclr(struct object_id *oid)\n-{\n-\tmemset(oid->hash, 0, GIT_MAX_RAWSZ);\n-}\n-\n-static inline void oidread(struct object_id *oid, const unsigned char *hash)\n-{\n-\tmemcpy(oid->hash, hash, the_hash_algo->rawsz);\n-}\n-\n-static inline int is_empty_blob_sha1(const unsigned char *sha1)\n-{\n-\treturn hasheq(sha1, the_hash_algo->empty_blob->hash);\n-}\n-\n-static inline int is_empty_blob_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, the_hash_algo->empty_blob);\n-}\n-\n-static inline int is_empty_tree_sha1(const unsigned char *sha1)\n-{\n-\treturn hasheq(sha1, the_hash_algo->empty_tree->hash);\n-}\n-\n-static inline int is_empty_tree_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, the_hash_algo->empty_tree);\n-}\n-\n-const char *empty_tree_oid_hex(void);\n-const char *empty_blob_oid_hex(void);\n-\n /* set default permissions by passing mode arguments to open(2) */\n int git_mkstemps_mode(char *pattern, int suffix_len, int mode);\n int git_mkstemp_mode(char *pattern, int mode);\ndiff --git a/hash.h b/hash.h\nindex e0f3f16b06..3fb0c3d400 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -2,6 +2,7 @@\n #define HASH_H\n \n #include \"git-compat-util.h\"\n+#include \"repository.h\"\n \n #if defined(SHA1_PPC)\n #include \"ppc/sha1.h\"\n@@ -184,4 +185,98 @@ struct object_id {\n \n #define the_hash_algo the_repository->hash_algo\n \n+extern const struct object_id null_oid;\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+{\n+\t/*\n+\t * Teach the compiler that there are only two possibilities of hash size\n+\t * here, so that it can optimize for this case as much as possible.\n+\t */\n+\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n+\t\treturn memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n+\treturn memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n+}\n+\n+static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)\n+{\n+\treturn hashcmp(oid1->hash, oid2->hash);\n+}\n+\n+static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2)\n+{\n+\t/*\n+\t * We write this here instead of deferring to hashcmp so that the\n+\t * compiler can properly inline it and avoid calling memcmp.\n+\t */\n+\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n+\t\treturn !memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n+\treturn !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n+}\n+\n+static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)\n+{\n+\treturn hasheq(oid1->hash, oid2->hash);\n+}\n+\n+static inline int is_null_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, &null_oid);\n+}\n+\n+static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n+{\n+\tmemcpy(sha_dst, sha_src, the_hash_algo->rawsz);\n+}\n+\n+static inline void oidcpy(struct object_id *dst, const struct object_id *src)\n+{\n+\tmemcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);\n+}\n+\n+static inline struct object_id *oiddup(const struct object_id *src)\n+{\n+\tstruct object_id *dst = xmalloc(sizeof(struct object_id));\n+\toidcpy(dst, src);\n+\treturn dst;\n+}\n+\n+static inline void hashclr(unsigned char *hash)\n+{\n+\tmemset(hash, 0, the_hash_algo->rawsz);\n+}\n+\n+static inline void oidclr(struct object_id *oid)\n+{\n+\tmemset(oid->hash, 0, GIT_MAX_RAWSZ);\n+}\n+\n+static inline void oidread(struct object_id *oid, const unsigned char *hash)\n+{\n+\tmemcpy(oid->hash, hash, the_hash_algo->rawsz);\n+}\n+\n+static inline int is_empty_blob_sha1(const unsigned char *sha1)\n+{\n+\treturn hasheq(sha1, the_hash_algo->empty_blob->hash);\n+}\n+\n+static inline int is_empty_blob_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, the_hash_algo->empty_blob);\n+}\n+\n+static inline int is_empty_tree_sha1(const unsigned char *sha1)\n+{\n+\treturn hasheq(sha1, the_hash_algo->empty_tree->hash);\n+}\n+\n+static inline int is_empty_tree_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, the_hash_algo->empty_tree);\n+}\n+\n+const char *empty_tree_oid_hex(void);\n+const char *empty_blob_oid_hex(void);\n+\n #endif\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411347","messageId":"X8qFV70BrlPAdpGO@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 5/9] oid-array: make sort function public","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:52:07Z","receivedAt":"2020-12-04T18:53:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We sort the oid-array as a side effect of calling the lookup or\nunique-iteration functions. But callers may want to sort it themselves\n(especially as we add new iteration options in future patches).\n\nWe'll also move the check of the \"sorted\" flag into the sort function,\nso callers don't have to remember to check it.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.c | 10 +++++-----\n oid-array.h |  5 +++++\n 2 files changed, 10 insertions(+), 5 deletions(-)\n\ndiff --git a/oid-array.c b/oid-array.c\nindex 8657a5cedf..29f718d835 100644\n--- a/oid-array.c\n+++ b/oid-array.c\n@@ -14,8 +14,10 @@ static int void_hashcmp(const void *a, const void *b)\n \treturn oidcmp(a, b);\n }\n \n-static void oid_array_sort(struct oid_array *array)\n+void oid_array_sort(struct oid_array *array)\n {\n+\tif (array->sorted)\n+\t\treturn;\n \tQSORT(array->oid, array->nr, void_hashcmp);\n \tarray->sorted = 1;\n }\n@@ -28,8 +30,7 @@ static const unsigned char *sha1_access(size_t index, void *table)\n \n int oid_array_lookup(struct oid_array *array, const struct object_id *oid)\n {\n-\tif (!array->sorted)\n-\t\toid_array_sort(array);\n+\toid_array_sort(array);\n \treturn sha1_pos(oid->hash, array->oid, array->nr, sha1_access);\n }\n \n@@ -64,8 +65,7 @@ int oid_array_for_each_unique(struct oid_array *array,\n {\n \tsize_t i;\n \n-\tif (!array->sorted)\n-\t\toid_array_sort(array);\n+\toid_array_sort(array);\n \n \tfor (i = 0; i < array->nr; i++) {\n \t\tint ret;\ndiff --git a/oid-array.h b/oid-array.h\nindex 2c8b64c393..6a22c0ac94 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -106,4 +106,9 @@ void oid_array_filter(struct oid_array *array,\n \t\t      for_each_oid_fn want,\n \t\t      void *cbdata);\n \n+/**\n+ * Sort the array in order of ascending object id.\n+ */\n+void oid_array_sort(struct oid_array *array);\n+\n #endif /* OID_ARRAY_H */\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411348","messageId":"X8qFo+GJJTbaPV58@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:53:23Z","receivedAt":"2020-12-04T18:54:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We provide oid_array_for_each_unique() for iterating over the\nde-duplicated items in an array. But it's awkward to use for two\nreasons:\n\n  1. It uses a callback, which means marshaling arguments into a struct\n     and passing it to the callback with a void parameter.\n\n  2. The callback doesn't know the numeric index of the oid we're\n     looking at. This is useful for things like progress meters.\n\nIterating with a for-loop is much more natural for some cases, but the\ncaller has to do the de-duping itself. However, we can provide a small\nhelper to make this easier (see the docstring in the header for an\nexample use).\n\nThe caller does have to remember to sort the array first. We could add\nan assertion into the helper that array->sorted is set, but I didn't\nwant to complicate what is otherwise a pretty fast code path.\n\nI also considered adding a full iterator type with init/next/end\nfunctions (similar to what we have for hashmaps). But it ended up making\nthe callers much harder to read. This version keeps us close to a basic\nfor-loop.\n\nYet another option would be adding an option to sort the array and\ncompact out the duplicates. This would mean iterating over the array an\nextra time, though that's probably not a big deal (we did just do an\nO(n log n) sort). But we'd still have to write a for-loop to iterate, so\nit doesn't really make anything easier for the caller.\n\nNo new test, since we'll convert the callback iterator (which is covered\nby t0064, among other callers) to use the new code.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.c |  7 ++-----\n oid-array.h | 22 ++++++++++++++++++++++\n 2 files changed, 24 insertions(+), 5 deletions(-)\n\ndiff --git a/oid-array.c b/oid-array.c\nindex 29f718d835..8e1bcedc0c 100644\n--- a/oid-array.c\n+++ b/oid-array.c\n@@ -67,11 +67,8 @@ int oid_array_for_each_unique(struct oid_array *array,\n \n \toid_array_sort(array);\n \n-\tfor (i = 0; i < array->nr; i++) {\n-\t\tint ret;\n-\t\tif (i > 0 && oideq(array->oid + i, array->oid + i - 1))\n-\t\t\tcontinue;\n-\t\tret = fn(array->oid + i, data);\n+\tfor (i = 0; i < array->nr; i = oid_array_next_unique(array, i)) {\n+\t\tint ret = fn(array->oid + i, data);\n \t\tif (ret)\n \t\t\treturn ret;\n \t}\ndiff --git a/oid-array.h b/oid-array.h\nindex 6a22c0ac94..5d86ea5a30 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -1,6 +1,8 @@\n #ifndef OID_ARRAY_H\n #define OID_ARRAY_H\n \n+#include \"hash.h\"\n+\n /**\n  * The API provides storage and manipulation of sets of object identifiers.\n  * The emphasis is on storage and processing efficiency, making them suitable\n@@ -111,4 +113,24 @@ void oid_array_filter(struct oid_array *array,\n  */\n void oid_array_sort(struct oid_array *array);\n \n+/**\n+ * Find the next unique oid in the array after position \"cur\". You\n+ * can use this to iterate over unique elements, like:\n+ *\n+ *   size_t i;\n+ *   oid_array_sort(array);\n+ *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n+ *\tprintf(\"%s\", oid_to_hex(array->oids[i]);\n+ *\n+ * Non-unique iteration can just increment with \"i++\" to visit each element.\n+ */\n+static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n+{\n+\tdo {\n+\t\tcur++;\n+\t} while (cur < array->nr &&\n+\t\t oideq(array->oid + cur, array->oid + cur - 1));\n+\treturn cur;\n+}\n+\n #endif /* OID_ARRAY_H */\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411349","messageId":"X8qGTaIdnNa5mAfC@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:56:13Z","receivedAt":"2020-12-04T18:57:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When writing a commit graph, we collect a list of object ids in an\narray, which we'll eventually copy into an array of \"struct commit\"\npointers. Before we do that, though, we count the number of distinct\ncommit entries. There's a subtle bug in this step, though.\n\nWe eliminate not only duplicate oids, but also in split mode, any oids\nwhich are not commits or which are already in a graph file. However, the\nloop starts at index 1, always counting index 0 as distinct. And indeed\nit can't be a duplicate, since we check for those by comparing against\nthe previous entry, and there isn't one for index 0. But it could be a\ncommit that's already in a graph file, and we'd overcount the number of\ncommits by 1 in that case.\n\nThat turns out not to be a problem, though. The only things we do with\nthe count are:\n\n  - check if our count will overflow our data structures. But the limit\n    there is 2^31 commits, so it's not likely to happen in practice.\n\n  - pre-allocate the array of commit pointers. But over-allocating by\n    one isn't a problem.\n\nThe bug would be easy enough to fix, but we can observe that neither of\nthose steps is necessary. We'll check the count of the commit array\nafter we build it anyway, so checking at this point is redundant. And we\nuse ALLOC_GROW() when building the commit array, so there's no need to\npreallocate it (it's possible that doing so is slightly more efficient,\nbut if we care we can just optimistically allocate one slot for each\noid; I didn't bother here).\n\nSo count_distinct_commits() isn't doing anything useful. Let's just get\nrid of that step.\n\nNote that a side effect of the function was that we sorted the list of\noids, which we do rely on in copy_oids_to_commits(), since it must also\nskip the duplicates. So we'll move the qsort there.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 43 ++-----------------------------------------\n 1 file changed, 2 insertions(+), 41 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 6f62a07313..1ac3516cf5 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1588,35 +1588,6 @@ static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx)\n \tstop_progress(&ctx->progress);\n }\n \n-static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n-{\n-\tuint32_t i, count_distinct = 1;\n-\n-\tif (ctx->report_progress)\n-\t\tctx->progress = start_delayed_progress(\n-\t\t\t_(\"Counting distinct commits in commit graph\"),\n-\t\t\tctx->oids.nr);\n-\tdisplay_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */\n-\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n-\n-\tfor (i = 1; i < ctx->oids.nr; i++) {\n-\t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (!oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i])) {\n-\t\t\tif (ctx->split) {\n-\t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n-\n-\t\t\t\tif (!c || commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tcount_distinct++;\n-\t\t}\n-\t}\n-\tstop_progress(&ctx->progress);\n-\n-\treturn count_distinct;\n-}\n-\n static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n {\n \tuint32_t i;\n@@ -1628,6 +1599,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->progress = start_delayed_progress(\n \t\t\t_(\"Finding extra edges in commit graph\"),\n \t\t\tctx->oids.nr);\n+\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tunsigned int num_parents;\n \n@@ -2155,7 +2127,7 @@ int write_commit_graph(struct object_directory *odb,\n \t\t       const struct commit_graph_opts *opts)\n {\n \tstruct write_commit_graph_context *ctx;\n-\tuint32_t i, count_distinct = 0;\n+\tuint32_t i;\n \tint res = 0;\n \tint replace = 0;\n \tstruct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;\n@@ -2268,17 +2240,6 @@ int write_commit_graph(struct object_directory *odb,\n \n \tclose_reachable(ctx);\n \n-\tcount_distinct = count_distinct_commits(ctx);\n-\n-\tif (count_distinct >= GRAPH_EDGE_LAST_MASK) {\n-\t\terror(_(\"the commit graph format cannot write %d commits\"), count_distinct);\n-\t\tres = -1;\n-\t\tgoto cleanup;\n-\t}\n-\n-\tctx->commits.alloc = count_distinct;\n-\tALLOC_ARRAY(ctx->commits.list, ctx->commits.alloc);\n-\n \tcopy_oids_to_commits(ctx);\n \n \tif (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411350","messageId":"X8qGqHvHbJQL9B22@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 8/9] commit-graph: replace packed_oid_list with oid_array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:57:44Z","receivedAt":"2020-12-04T18:58:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our custom packed_oid_list data structure is really just an oid_array in\ndisguise. Let's switch to using the generic structure, which shortens\nand simplifies the code slightly.\n\nThere's one slightly awkward part: in the old code we copied a hash\nstraight from the mmap'd on-disk data into the final object_id. And now\nwe'll copy to a temporary oid, which we'll then pass to\noid_array_append(). But this is an operation we have to do all over the\ncommit-graph code already, since it mostly uses object_id structs\ninternally. I also measured \"git commit-graph --append\", which triggers\nthis code path, and it showed no difference.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 62 ++++++++++++--------------------------------------\n 1 file changed, 15 insertions(+), 47 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 1ac3516cf5..4a718fd6e6 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -936,17 +936,11 @@ struct packed_commit_list {\n \tint alloc;\n };\n \n-struct packed_oid_list {\n-\tstruct object_id *list;\n-\tint nr;\n-\tint alloc;\n-};\n-\n struct write_commit_graph_context {\n \tstruct repository *r;\n \tstruct object_directory *odb;\n \tchar *graph_name;\n-\tstruct packed_oid_list oids;\n+\tstruct oid_array oids;\n \tstruct packed_commit_list commits;\n \tint num_extra_edges;\n \tunsigned long approx_nr_objects;\n@@ -1240,13 +1234,6 @@ static int write_graph_chunk_bloom_data(struct hashfile *f,\n \treturn 0;\n }\n \n-static int oid_compare(const void *_a, const void *_b)\n-{\n-\tconst struct object_id *a = (const struct object_id *)_a;\n-\tconst struct object_id *b = (const struct object_id *)_b;\n-\treturn oidcmp(a, b);\n-}\n-\n static int add_packed_commits(const struct object_id *oid,\n \t\t\t      struct packed_git *pack,\n \t\t\t      uint32_t pos,\n@@ -1267,10 +1254,7 @@ static int add_packed_commits(const struct object_id *oid,\n \tif (type != OBJ_COMMIT)\n \t\treturn 0;\n \n-\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\toidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);\n-\tctx->oids.nr++;\n-\n+\toid_array_append(&ctx->oids, oid);\n \tset_commit_pos(ctx->r, oid);\n \n \treturn 0;\n@@ -1281,9 +1265,7 @@ static void add_missing_parents(struct write_commit_graph_context *ctx, struct c\n \tstruct commit_list *parent;\n \tfor (parent = commit->parents; parent; parent = parent->next) {\n \t\tif (!(parent->item->object.flags & REACHABLE)) {\n-\t\t\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\t\t\toidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid));\n-\t\t\tctx->oids.nr++;\n+\t\t\toid_array_append(&ctx->oids, &parent->item->object.oid);\n \t\t\tparent->item->object.flags |= REACHABLE;\n \t\t}\n \t}\n@@ -1302,7 +1284,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->oids.nr);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \t\tif (commit)\n \t\t\tcommit->object.flags |= REACHABLE;\n \t}\n@@ -1319,7 +1301,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\t0);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (!commit)\n \t\t\tcontinue;\n@@ -1339,7 +1321,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->oids.nr);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (commit)\n \t\t\tcommit->object.flags &= ~REACHABLE;\n@@ -1567,9 +1549,7 @@ static int fill_oids_from_commits(struct write_commit_graph_context *ctx,\n \n \toidset_iter_init(commits, &iter);\n \twhile ((oid = oidset_iter_next(&iter))) {\n-\t\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\t\toidcpy(&ctx->oids.list[ctx->oids.nr], oid);\n-\t\tctx->oids.nr++;\n+\t\toid_array_append(&ctx->oids, oid);\n \t}\n \n \treturn 0;\n@@ -1599,16 +1579,14 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->progress = start_delayed_progress(\n \t\t\t_(\"Finding extra edges in commit graph\"),\n \t\t\tctx->oids.nr);\n-\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n-\tfor (i = 0; i < ctx->oids.nr; i++) {\n+\toid_array_sort(&ctx->oids);\n+\tfor (i = 0; i < ctx->oids.nr; i = oid_array_next_unique(&ctx->oids, i)) {\n \t\tunsigned int num_parents;\n \n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (i > 0 && oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i]))\n-\t\t\tcontinue;\n \n \t\tALLOC_GROW(ctx->commits.list, ctx->commits.nr + 1, ctx->commits.alloc);\n-\t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n \t\t    commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n@@ -2199,26 +2177,16 @@ int write_commit_graph(struct object_directory *odb,\n \t}\n \n \tctx->approx_nr_objects = approximate_object_count();\n-\tctx->oids.alloc = ctx->approx_nr_objects / 32;\n \n-\tif (ctx->split && opts && ctx->oids.alloc > opts->max_commits)\n-\t\tctx->oids.alloc = opts->max_commits;\n-\n-\tif (ctx->append) {\n+\tif (ctx->append)\n \t\tprepare_commit_graph_one(ctx->r, ctx->odb);\n-\t\tif (ctx->r->objects->commit_graph)\n-\t\t\tctx->oids.alloc += ctx->r->objects->commit_graph->num_commits;\n-\t}\n-\n-\tif (ctx->oids.alloc < 1024)\n-\t\tctx->oids.alloc = 1024;\n-\tALLOC_ARRAY(ctx->oids.list, ctx->oids.alloc);\n \n \tif (ctx->append && ctx->r->objects->commit_graph) {\n \t\tstruct commit_graph *g = ctx->r->objects->commit_graph;\n \t\tfor (i = 0; i < g->num_commits; i++) {\n-\t\t\tconst unsigned char *hash = g->chunk_oid_lookup + g->hash_len * i;\n-\t\t\thashcpy(ctx->oids.list[ctx->oids.nr++].hash, hash);\n+\t\t\tstruct object_id oid;\n+\t\t\thashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * i);\n+\t\t\toid_array_append(&ctx->oids, &oid);\n \t\t}\n \t}\n \n@@ -2274,7 +2242,7 @@ int write_commit_graph(struct object_directory *odb,\n cleanup:\n \tfree(ctx->graph_name);\n \tfree(ctx->commits.list);\n-\tfree(ctx->oids.list);\n+\toid_array_clear(&ctx->oids);\n \n \tif (ctx->commit_graph_filenames_after) {\n \t\tfor (i = 0; i < ctx->num_commit_graphs_after; i++) {\n-- \n2.29.2.896.g080220a959\n\n"},{"id":"411351","messageId":"X8qGvmsRJ1EsL4R8@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH 9/9] commit-graph: use size_t for array allocation and indexing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T18:58:06Z","receivedAt":"2020-12-04T18:58:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our packed_commit_list is an array of pointers to commit structs. We use\n\"int\" for the allocation, which is 32-bit even on 64-bit platforms. This\nisn't likely to overflow in practice (we're writing commit graphs, so\nyou'd need to actually have billions of unique commits in the\nrepository). But it's good practice to use size_t for allocations.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 4a718fd6e6..06f8dc1d89 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -932,8 +932,8 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit\n \n struct packed_commit_list {\n \tstruct commit **list;\n-\tint nr;\n-\tint alloc;\n+\tsize_t nr;\n+\tsize_t alloc;\n };\n \n struct write_commit_graph_context {\n-- \n2.29.2.896.g080220a959\n"},{"id":"411352","messageId":"X8qIaOe3aT1qr+es@nand.local","threadId":"54763","inReplyTo":"X8qFo+GJJTbaPV58@coredump.intra.peff.net","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-04T19:05:12Z","receivedAt":"2020-12-04T19:05:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Dec 04, 2020 at 01:53:23PM -0500, Jeff King wrote:\n> I also considered adding a full iterator type with init/next/end\n> functions (similar to what we have for hashmaps). But it ended up making\n> the callers much harder to read. This version keeps us close to a basic\n> for-loop.\n\nYeah, I think that a full-blown iterator type is overkill for this\npurpose. Another possible approach could be a macro:\n\n  #define for_each_oid_array_unique(arr, i) \\\n    for (i = 0; (i) < (array)->nr; i = oid_array_for_each_unique((arr), i))\n\nbut I don't think that's making anything more clear than\n'oid_array_for_each_unique' already is. So, I like the approach that you\ntook here.\n\n> @@ -111,4 +113,24 @@ void oid_array_filter(struct oid_array *array,\n>   */\n>  void oid_array_sort(struct oid_array *array);\n>\n> +/**\n> + * Find the next unique oid in the array after position \"cur\". You\n> + * can use this to iterate over unique elements, like:\n> + *\n> + *   size_t i;\n> + *   oid_array_sort(array);\n> + *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n> + *\tprintf(\"%s\", oid_to_hex(array->oids[i]);\n> + *\n> + * Non-unique iteration can just increment with \"i++\" to visit each element.\n> + */\n> +static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n> +{\n> +\tdo {\n> +\t\tcur++;\n> +\t} while (cur < array->nr &&\n> +\t\t oideq(array->oid + cur, array->oid + cur - 1));\n\nI don't love the pointer math here (would instead prefer\noideq(&array->oid[cur]) and so on), but I don't think that it matters\nenough to make a difference.\n\nI additionally had to make sure that cur - 1 >= 0 so that the second\nargument would always be valid, but it is, since we call cur++.\n\nYou could check that cur++ doesn't overflow, but I think that that's\nmostly academic.\n\nThanks,\nTaylor\n"},{"id":"411354","messageId":"X8qJ9yKVcGSw0bWx@nand.local","threadId":"54763","inReplyTo":"X8qIaOe3aT1qr+es@nand.local","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-04T19:11:51Z","receivedAt":"2020-12-04T19:12:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Dec 04, 2020 at 02:05:12PM -0500, Taylor Blau wrote:\n> On Fri, Dec 04, 2020 at 01:53:23PM -0500, Jeff King wrote:\n> > I also considered adding a full iterator type with init/next/end\n> > functions (similar to what we have for hashmaps). But it ended up making\n> > the callers much harder to read. This version keeps us close to a basic\n> > for-loop.\n>\n> Yeah, I think that a full-blown iterator type is overkill for this\n> purpose. Another possible approach could be a macro:\n>\n>   #define for_each_oid_array_unique(arr, i) \\\n>     for (i = 0; (i) < (array)->nr; i = oid_array_for_each_unique((arr), i))\n>\n> but I don't think that's making anything more clear than\n> 'oid_array_for_each_unique' already is. So, I like the approach that you\n> took here.\n\nHmm. I take part of that back; it would simplify the caller in the eighth\npatch, which first wants to sort the list before iterating it (which is\nnecessary, because we look at 'i = 0' before calling\noid_array_for_each_unique()).\n\nSo this could look instead like:\n\n#define for_each_oid_array_unique(arr, i) \\\n    for (oid_array_sort(), i = 0; (i) < (array)->nr; i = oid_array_for_each_unique((arr), i))\n\nMaybe a little too magical, who knows.\n"},{"id":"411355","messageId":"X8qKpL+mIFbjngwl@nand.local","threadId":"54763","inReplyTo":"X8qGqHvHbJQL9B22@coredump.intra.peff.net","subject":"Re: [PATCH 8/9] commit-graph: replace packed_oid_list with oid_array","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-04T19:14:44Z","receivedAt":"2020-12-04T19:15:29Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Dec 04, 2020 at 01:57:44PM -0500, Jeff King wrote:\n> Our custom packed_oid_list data structure is really just an oid_array in\n> disguise. Let's switch to using the generic structure, which shortens\n> and simplifies the code slightly.\n>\n> There's one slightly awkward part: in the old code we copied a hash\n> straight from the mmap'd on-disk data into the final object_id. And now\n> we'll copy to a temporary oid, which we'll then pass to\n> oid_array_append(). But this is an operation we have to do all over the\n> commit-graph code already, since it mostly uses object_id structs\n> internally. I also measured \"git commit-graph --append\", which triggers\n> this code path, and it showed no difference.\n\nI noticed that you also dropped the pre-allocation logic, which I think\nis the right thing to do (that is, removing it, not keeping it around).\n\nIt may be worth a mention here, though.\n\n> @@ -2199,26 +2177,16 @@ int write_commit_graph(struct object_directory *odb,\n>  \t}\n>\n>  \tctx->approx_nr_objects = approximate_object_count();\n> -\tctx->oids.alloc = ctx->approx_nr_objects / 32;\n>\n> -\tif (ctx->split && opts && ctx->oids.alloc > opts->max_commits)\n> -\t\tctx->oids.alloc = opts->max_commits;\n\nOne compelling reason to drop this logic is that we only have the\noid-array internals touching the .alloc variable, and we're not munging\nwith it ourselves (running the risk of getting it out-of-sync with the\nactual number of bytes allocated).\n\n> -\n> -\tif (ctx->append) {\n> +\tif (ctx->append)\n>  \t\tprepare_commit_graph_one(ctx->r, ctx->odb);\n\nGood, this still needs to happen here.\n\n> -\t\tif (ctx->r->objects->commit_graph)\n> -\t\t\tctx->oids.alloc += ctx->r->objects->commit_graph->num_commits;\n> -\t}\n> -\n> -\tif (ctx->oids.alloc < 1024)\n> -\t\tctx->oids.alloc = 1024;\n> -\tALLOC_ARRAY(ctx->oids.list, ctx->oids.alloc);\n>\n>  \tif (ctx->append && ctx->r->objects->commit_graph) {\n>  \t\tstruct commit_graph *g = ctx->r->objects->commit_graph;\n>  \t\tfor (i = 0; i < g->num_commits; i++) {\n> -\t\t\tconst unsigned char *hash = g->chunk_oid_lookup + g->hash_len * i;\n> -\t\t\thashcpy(ctx->oids.list[ctx->oids.nr++].hash, hash);\n> +\t\t\tstruct object_id oid;\n> +\t\t\thashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * i);\n> +\t\t\toid_array_append(&ctx->oids, &oid);\n\nAnd this must be the spot that you're talking about that requires the\nextra copy. I think that we could certainly live with what you have\nhere.\n\nThanks,\nTaylor\n"},{"id":"411356","messageId":"X8qK67IBtB3lqSaV@nand.local","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"Re: [PATCH 0/9] misc commit-graph and oid-array cleanups","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-04T19:15:55Z","receivedAt":"2020-12-04T19:16:41Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Dec 04, 2020 at 01:48:35PM -0500, Jeff King wrote:\n> This series came out of an off-list discussion about using oid-array in\n> commit-graph.c to replace a similar data structure. But I found a couple\n> of things to clean up along the way.\n\nThanks, I appreciate you taking this up. Everything that you wrote looks\nvery reasonable to me; I noted a couple of spots that might be worth\nchanging, but I won't be sad if you ignore them.\n\n  Reviewed-by: Taylor Blau <me@ttaylorr.com>\n\nThanks,\nTaylor\n"},{"id":"411357","messageId":"CAPig+cTLs5bkY=Pwg+4tT2KHfVHFjkrNTeS_ygGEwq0cOOJ9wQ@mail.gmail.com","threadId":"54763","inReplyTo":"X8qFo+GJJTbaPV58@coredump.intra.peff.net","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2020-12-04T19:18:45Z","receivedAt":"2020-12-04T19:19:39Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Dec 4, 2020 at 1:54 PM Jeff King <peff@peff.net> wrote:\n> [...]\n> The caller does have to remember to sort the array first. We could add\n> an assertion into the helper that array->sorted is set, but I didn't\n> want to complicate what is otherwise a pretty fast code path.\n> [...]\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> diff --git a/oid-array.h b/oid-array.h\n> @@ -111,4 +113,24 @@ void oid_array_filter(struct oid_array *array,\n> +/**\n> + * Find the next unique oid in the array after position \"cur\". You\n> + * can use this to iterate over unique elements, like:\n> + *\n> + *   size_t i;\n> + *   oid_array_sort(array);\n> + *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n> + *     printf(\"%s\", oid_to_hex(array->oids[i]);\n> + *\n> + * Non-unique iteration can just increment with \"i++\" to visit each element.\n> + */\n\nMinor: I see that the example code sorts the array first -- which is\nnecessary, as explained in the commit message -- but I wonder if it is\nworth calling out explicitly in the prose:\n\n    Find the next unique oid in the array after position `cur`.\n    The array must be sorted for this to work. You can use\n    this to iterate over unique elements like this:\n\n> +static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n> +{\n> +       do {\n> +               cur++;\n> +       } while (cur < array->nr &&\n> +                oideq(array->oid + cur, array->oid + cur - 1));\n> +       return cur;\n> +}\n"},{"id":"411362","messageId":"X8qTM22mVzrhqRnn@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qIaOe3aT1qr+es@nand.local","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T19:51:15Z","receivedAt":"2020-12-04T19:51:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 02:05:12PM -0500, Taylor Blau wrote:\n\n> > +static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n> > +{\n> > +\tdo {\n> > +\t\tcur++;\n> > +\t} while (cur < array->nr &&\n> > +\t\t oideq(array->oid + cur, array->oid + cur - 1));\n> \n> I don't love the pointer math here (would instead prefer\n> oideq(&array->oid[cur]) and so on), but I don't think that it matters\n> enough to make a difference.\n\nI think it is a matter of preference. I actually prefer the arithmetic\n(it's also what was in the code that we are replacing in\noid_array_for_each_unique(), but that is probably because I wrote that\none, too).\n\n> I additionally had to make sure that cur - 1 >= 0 so that the second\n> argument would always be valid, but it is, since we call cur++.\n\nYeah. I originally wrote it as:\n\n  cur++;\n  while (cur < array->nr) {\n\tif (!oideq(...))\n\t\tbreak;\n\tcur++;\n  }\n\nwhich maybe makes it more obvious that cur always gets implemented at\nleast once, but I found it harder to reason about the second increment.\nI think the do-while expresses it pretty clearly, but we're not that\nused to seeing them.\n\n> You could check that cur++ doesn't overflow, but I think that that's\n> mostly academic.\n\nIt can't overflow, because it can't ever go past array->nr (unless you\ncall it again after cur is already equal to array->nr, but that would be\na bug just like calling i++ after hitting the loop end would be).\n\n-Peff\n"},{"id":"411363","messageId":"X8qThjY9GTf5QZ8k@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qJ9yKVcGSw0bWx@nand.local","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T19:52:38Z","receivedAt":"2020-12-04T19:53:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 02:11:51PM -0500, Taylor Blau wrote:\n\n> > Yeah, I think that a full-blown iterator type is overkill for this\n> > purpose. Another possible approach could be a macro:\n> >\n> >   #define for_each_oid_array_unique(arr, i) \\\n> >     for (i = 0; (i) < (array)->nr; i = oid_array_for_each_unique((arr), i))\n> >\n> > but I don't think that's making anything more clear than\n> > 'oid_array_for_each_unique' already is. So, I like the approach that you\n> > took here.\n> \n> Hmm. I take part of that back; it would simplify the caller in the eighth\n> patch, which first wants to sort the list before iterating it (which is\n> necessary, because we look at 'i = 0' before calling\n> oid_array_for_each_unique()).\n> \n> So this could look instead like:\n> \n> #define for_each_oid_array_unique(arr, i) \\\n>     for (oid_array_sort(), i = 0; (i) < (array)->nr; i = oid_array_for_each_unique((arr), i))\n> \n> Maybe a little too magical, who knows.\n\nThat was one of the many variants I wrote on the way here. But yeah, I\nthink it is better to avoid magic macros unless they are getting us a\nlot. In the case of hashmap, there is a lot of magic needed to convert\nthe hashmap_entry field back into the parent struct pointer. But here,\nwe can get away with a pretty natural looking for-loop, so I think it's\nworth keeping it simple.\n\n-Peff\n"},{"id":"411369","messageId":"1103d97b-668f-8ad6-fc62-3fa09067a8bb@gmail.com","threadId":"54763","inReplyTo":"X8qGTaIdnNa5mAfC@coredump.intra.peff.net","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-04T20:06:24Z","receivedAt":"2020-12-04T20:07:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/4/2020 1:56 PM, Jeff King wrote:\n> That turns out not to be a problem, though. The only things we do with\n> the count are:\n> \n>   - check if our count will overflow our data structures. But the limit\n>     there is 2^31 commits, so it's not likely to happen in practice.\n\nYou do point out that you are removing this logic, done in this\nif statement:\n\n> -\tif (count_distinct >= GRAPH_EDGE_LAST_MASK) {\n> -\t\terror(_(\"the commit graph format cannot write %d commits\"), count_distinct);\n> -\t\tres = -1;\n> -\t\tgoto cleanup;\n> -\t}\n\nWhat is the harm of keeping this? I know it is very unlikely, but\nI'd rather fail here than write a commit-graph that gets parsed as\ngarbage.\n\nThanks,\n-Stolee\n"},{"id":"411372","messageId":"51e9f2c4-36e8-7d65-3b24-373a813a1eaf@gmail.com","threadId":"54763","inReplyTo":"X8qK67IBtB3lqSaV@nand.local","subject":"Re: [PATCH 0/9] misc commit-graph and oid-array cleanups","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-04T20:08:19Z","receivedAt":"2020-12-04T20:09:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/4/2020 2:15 PM, Taylor Blau wrote:\n> On Fri, Dec 04, 2020 at 01:48:35PM -0500, Jeff King wrote:\n>> This series came out of an off-list discussion about using oid-array in\n>> commit-graph.c to replace a similar data structure. But I found a couple\n>> of things to clean up along the way.\n> \n> Thanks, I appreciate you taking this up. Everything that you wrote looks\n> very reasonable to me; I noted a couple of spots that might be worth\n> changing, but I won't be sad if you ignore them.\n> \n>   Reviewed-by: Taylor Blau <me@ttaylorr.com>\n\nI have similar thoughts. Only one spot was worthy of a comment, and\nit has a very low chance of being important.\n\nThanks,\n-Stolee\n\n"},{"id":"411375","messageId":"X8qfRDsfLYTDL3HV@coredump.intra.peff.net","threadId":"54763","inReplyTo":"1103d97b-668f-8ad6-fc62-3fa09067a8bb@gmail.com","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T20:42:44Z","receivedAt":"2020-12-04T20:43:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 03:06:24PM -0500, Derrick Stolee wrote:\n\n> On 12/4/2020 1:56 PM, Jeff King wrote:\n> > That turns out not to be a problem, though. The only things we do with\n> > the count are:\n> > \n> >   - check if our count will overflow our data structures. But the limit\n> >     there is 2^31 commits, so it's not likely to happen in practice.\n> \n> You do point out that you are removing this logic, done in this\n> if statement:\n> \n> > -\tif (count_distinct >= GRAPH_EDGE_LAST_MASK) {\n> > -\t\terror(_(\"the commit graph format cannot write %d commits\"), count_distinct);\n> > -\t\tres = -1;\n> > -\t\tgoto cleanup;\n> > -\t}\n> \n> What is the harm of keeping this? I know it is very unlikely, but\n> I'd rather fail here than write a commit-graph that gets parsed as\n> garbage.\n\nI agree it's important to have. But this one is redundant. Look a few\nlines below this hunk, and we have:\n\n\tcopy_oids_to_commits(ctx);\n\n\tif (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {\n\t\terror(_(\"too many commits to write graph\"));\n\t\tres = -1;\n\t\tgoto cleanup;\n\t}\n\nSo before we were counting distinct commits, checking that our count\nfits, and then _ignoring_ that count in order to create the actual list\nof commits, and then checking that the actual list's count fits. We only\nneed one of those checks, and the important one is the one from the\nactual list (they _should_ match, but due to the bug, they sometimes\ndidn't).\n\nMy \"not likely to happen in practice\" is not about the quality of the\ncheck, but rather that being off by one would never matter in practice.\n\nDoes that make more sense?\n\n-Peff\n"},{"id":"411376","messageId":"X8qfr2B0OfaySjPh@coredump.intra.peff.net","threadId":"54763","inReplyTo":"CAPig+cTLs5bkY=Pwg+4tT2KHfVHFjkrNTeS_ygGEwq0cOOJ9wQ@mail.gmail.com","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T20:44:31Z","receivedAt":"2020-12-04T20:45:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 02:18:45PM -0500, Eric Sunshine wrote:\n\n> > + * Find the next unique oid in the array after position \"cur\". You\n> > + * can use this to iterate over unique elements, like:\n> > + *\n> > + *   size_t i;\n> > + *   oid_array_sort(array);\n> > + *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n> > + *     printf(\"%s\", oid_to_hex(array->oids[i]);\n> > + *\n> > + * Non-unique iteration can just increment with \"i++\" to visit each element.\n> > + */\n> \n> Minor: I see that the example code sorts the array first -- which is\n> necessary, as explained in the commit message -- but I wonder if it is\n> worth calling out explicitly in the prose:\n> \n>     Find the next unique oid in the array after position `cur`.\n>     The array must be sorted for this to work. You can use\n>     this to iterate over unique elements like this:\n\nThanks, that makes sense; I picked up your wording here.\n\n-Peff\n"},{"id":"411377","messageId":"05c616b0-138a-3e30-5a71-4ba9fb26e6ef@gmail.com","threadId":"54763","inReplyTo":"X8qfRDsfLYTDL3HV@coredump.intra.peff.net","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-04T20:47:43Z","receivedAt":"2020-12-04T20:48:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/4/2020 3:42 PM, Jeff King wrote:\n> On Fri, Dec 04, 2020 at 03:06:24PM -0500, Derrick Stolee wrote:\n> \n>> On 12/4/2020 1:56 PM, Jeff King wrote:\n>>> That turns out not to be a problem, though. The only things we do with\n>>> the count are:\n>>>\n>>>   - check if our count will overflow our data structures. But the limit\n>>>     there is 2^31 commits, so it's not likely to happen in practice.\n>>\n>> You do point out that you are removing this logic, done in this\n>> if statement:\n>>\n>>> -\tif (count_distinct >= GRAPH_EDGE_LAST_MASK) {\n>>> -\t\terror(_(\"the commit graph format cannot write %d commits\"), count_distinct);\n>>> -\t\tres = -1;\n>>> -\t\tgoto cleanup;\n>>> -\t}\n>>\n>> What is the harm of keeping this? I know it is very unlikely, but\n>> I'd rather fail here than write a commit-graph that gets parsed as\n>> garbage.\n> \n> I agree it's important to have. But this one is redundant. Look a few\n> lines below this hunk, and we have:\n> \n> \tcopy_oids_to_commits(ctx);\n> \n> \tif (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {\n> \t\terror(_(\"too many commits to write graph\"));\n> \t\tres = -1;\n> \t\tgoto cleanup;\n> \t}\n\n\nYep, my fault for not looking further in the context of your patch.\n\n> So before we were counting distinct commits, checking that our count\n> fits, and then _ignoring_ that count in order to create the actual list\n> of commits, and then checking that the actual list's count fits. We only\n> need one of those checks, and the important one is the one from the\n> actual list (they _should_ match, but due to the bug, they sometimes\n> didn't).\n> \n> My \"not likely to happen in practice\" is not about the quality of the\n> check, but rather that being off by one would never matter in practice.\n> \n> Does that make more sense?\nMakes sense to me. No need to change this patch at all.\n\nThanks,\n-Stolee\n"},{"id":"411399","messageId":"X8qhAO6uUDgHjP7S@coredump.intra.peff.net","threadId":"54763","inReplyTo":"05c616b0-138a-3e30-5a71-4ba9fb26e6ef@gmail.com","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-04T20:50:08Z","receivedAt":"2020-12-04T20:51:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 03:47:43PM -0500, Derrick Stolee wrote:\n\n> > So before we were counting distinct commits, checking that our count\n> > fits, and then _ignoring_ that count in order to create the actual list\n> > of commits, and then checking that the actual list's count fits. We only\n> > need one of those checks, and the important one is the one from the\n> > actual list (they _should_ match, but due to the bug, they sometimes\n> > didn't).\n> > \n> > My \"not likely to happen in practice\" is not about the quality of the\n> > check, but rather that being off by one would never matter in practice.\n> > \n> > Does that make more sense?\n> Makes sense to me. No need to change this patch at all.\n\nI brushed up the commit message a bit to make those points clearer:\n\n 7:  bbccccdc5c !  7:  23420dbd1b commit-graph: drop count_distinct_commits() function\n    @@ Commit message\n         the count are:\n     \n           - check if our count will overflow our data structures. But the limit\n    -        there is 2^31 commits, so it's not likely to happen in practice.\n    +        there is 2^31 commits, so while this is a useful check, the\n    +        off-by-one is not likely to matter.\n     \n           - pre-allocate the array of commit pointers. But over-allocating by\n    -        one isn't a problem.\n    +        one isn't a problem; we'll just waste a few extra bytes.\n     \n         The bug would be easy enough to fix, but we can observe that neither of\n    -    those steps is necessary. We'll check the count of the commit array\n    -    after we build it anyway, so checking at this point is redundant. And we\n    -    use ALLOC_GROW() when building the commit array, so there's no need to\n    -    preallocate it (it's possible that doing so is slightly more efficient,\n    -    but if we care we can just optimistically allocate one slot for each\n    -    oid; I didn't bother here).\n    +    those steps is necessary.\n    +\n    +    After building the actual commit array, we'll likewise check its count\n    +    for overflow. So the extra check of the distinct commit count here is\n    +    redundant.\n    +\n    +    And likewise we use ALLOC_GROW() when building the commit array, so\n    +    there's no need to preallocate it (it's possible that doing so is\n    +    slightly more efficient, but if we care we can just optimistically\n    +    allocate one slot for each oid; I didn't bother here).\n     \n         So count_distinct_commits() isn't doing anything useful. Let's just get\n         rid of that step.\n\n-Peff\n"},{"id":"411400","messageId":"CAPig+cQms-VgBCWM_CpxkwAu4aQBVmqHkr4TPu9CR08w3RiLVw@mail.gmail.com","threadId":"54763","inReplyTo":"X8qfr2B0OfaySjPh@coredump.intra.peff.net","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2020-12-04T20:57:09Z","receivedAt":"2020-12-04T20:58:17Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Fri, Dec 4, 2020 at 3:45 PM Jeff King <peff@peff.net> wrote:\n> On Fri, Dec 04, 2020 at 02:18:45PM -0500, Eric Sunshine wrote:\n> > Minor: I see that the example code sorts the array first -- which is\n> > necessary, as explained in the commit message -- but I wonder if it is\n> > worth calling out explicitly in the prose:\n> >\n> >     Find the next unique oid in the array after position `cur`.\n> >     The array must be sorted for this to work. You can use\n> >     this to iterate over unique elements like this:\n>\n> Thanks, that makes sense; I picked up your wording here.\n\nIt's probably not worth a re-roll just to update this comment, but if\nyou're re-rolling anyhow, the wording could be improved slightly:\n\n    Find the next unique oid in the array after position `cur`.\n    The array must be sorted for this to work. You can iterate\n    over unique elements like this:\n"},{"id":"411402","messageId":"22c74095-a552-b821-566b-ecc91c70b32d@gmail.com","threadId":"54763","inReplyTo":"X8qhAO6uUDgHjP7S@coredump.intra.peff.net","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-04T21:01:48Z","receivedAt":"2020-12-04T21:02:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/4/2020 3:50 PM, Jeff King wrote:\n> On Fri, Dec 04, 2020 at 03:47:43PM -0500, Derrick Stolee wrote:\n>>> Does that make more sense?\n>> Makes sense to me. No need to change this patch at all.\n> \n> I brushed up the commit message a bit to make those points clearer:\n\nLGTM. Thanks.\n\n-Stolee\n\n"},{"id":"411408","messageId":"xmqq1rg5dyp4.fsf@gitster.c.googlers.com","threadId":"54763","inReplyTo":"CAPig+cTLs5bkY=Pwg+4tT2KHfVHFjkrNTeS_ygGEwq0cOOJ9wQ@mail.gmail.com","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-04T21:54:31Z","receivedAt":"2020-12-04T21:55:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Sunshine <sunshine@sunshineco.com> writes:\n\n> On Fri, Dec 4, 2020 at 1:54 PM Jeff King <peff@peff.net> wrote:\n>> [...]\n>> The caller does have to remember to sort the array first. We could add\n>> an assertion into the helper that array->sorted is set, but I didn't\n>> want to complicate what is otherwise a pretty fast code path.\n>> [...]\n>> Signed-off-by: Jeff King <peff@peff.net>\n>> ---\n>> diff --git a/oid-array.h b/oid-array.h\n>> @@ -111,4 +113,24 @@ void oid_array_filter(struct oid_array *array,\n>> +/**\n>> + * Find the next unique oid in the array after position \"cur\". You\n>> + * can use this to iterate over unique elements, like:\n>> + *\n>> + *   size_t i;\n>> + *   oid_array_sort(array);\n>> + *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n>> + *     printf(\"%s\", oid_to_hex(array->oids[i]);\n>> + *\n>> + * Non-unique iteration can just increment with \"i++\" to visit each element.\n>> + */\n>\n> Minor: I see that the example code sorts the array first -- which is\n> necessary, as explained in the commit message -- but I wonder if it is\n> worth calling out explicitly in the prose:\n>\n>     Find the next unique oid in the array after position `cur`.\n>     The array must be sorted for this to work. You can use\n>     this to iterate over unique elements like this:\n>\n>> +static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n\nPerhaps the function can make it clear that it expects to be fed a\nsorted array in its name, which would be even better?\n\n>> +{\n>> +       do {\n>> +               cur++;\n>> +       } while (cur < array->nr &&\n>> +                oideq(array->oid + cur, array->oid + cur - 1));\n>> +       return cur;\n>> +}\n"},{"id":"411488","messageId":"87sg8lxa1b.fsf@evledraar.gmail.com","threadId":"54763","inReplyTo":"X8qGTaIdnNa5mAfC@coredump.intra.peff.net","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2020-12-05T02:26:56Z","receivedAt":"2020-12-05T02:28:00Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 04 2020, Jeff King wrote:\n\n> When writing a commit graph, we collect a list of object ids in an\n> array, which we'll eventually copy into an array of \"struct commit\"\n> pointers. Before we do that, though, we count the number of distinct\n> commit entries. There's a subtle bug in this step, though.\n> [...]\n> -\tdisplay_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */\n> -\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n> [...]\n> +\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n\nOne thing your commit messag doesn't note is the removal of this\nTODO. Theoretically we still have the issue I noted in 890226ccb57\n(commit-graph write: add itermediate progress, 2019-01-19), in practice\nI think it's fine to just forever remove this TODO.\n\nI tried now on a really big repo and couldn't even get the progress bar\nyou removed to appear, or the one you moved the QSORT() to.\n\nMaybe I need to go even bigger, but more likely I overdid things a bit\nwhen I added all these progress bars to commit-graph.c at the time.\n"},{"id":"411621","messageId":"X8578ZoJKcGOC5Po@coredump.intra.peff.net","threadId":"54763","inReplyTo":"87sg8lxa1b.fsf@evledraar.gmail.com","subject":"Re: [PATCH 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:01:05Z","receivedAt":"2020-12-07T19:02:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 05, 2020 at 03:26:56AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> On Fri, Dec 04 2020, Jeff King wrote:\n> \n> > When writing a commit graph, we collect a list of object ids in an\n> > array, which we'll eventually copy into an array of \"struct commit\"\n> > pointers. Before we do that, though, we count the number of distinct\n> > commit entries. There's a subtle bug in this step, though.\n> > [...]\n> > -\tdisplay_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */\n> > -\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n> > [...]\n> > +\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n> \n> One thing your commit messag doesn't note is the removal of this\n> TODO. Theoretically we still have the issue I noted in 890226ccb57\n> (commit-graph write: add itermediate progress, 2019-01-19), in practice\n> I think it's fine to just forever remove this TODO.\n\nYeah, I don't think we can really put progress bars on everything. If\nyou have a dataset so large that sorting the commits by oid takes a long\ntime, then I think you probably just need to accept that there are going\nto be some small pauses while Git works.\n\n-Peff\n"},{"id":"411622","messageId":"X858/2MkKU1Grqby@coredump.intra.peff.net","threadId":"54763","inReplyTo":"xmqq1rg5dyp4.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:05:35Z","receivedAt":"2020-12-07T19:06:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 04, 2020 at 01:54:31PM -0800, Junio C Hamano wrote:\n\n> >> +static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n> \n> Perhaps the function can make it clear that it expects to be fed a\n> sorted array in its name, which would be even better?\n\nThe name is already pretty clunky. I'm not thrilled with the idea of\nmaking it even longer. :)\n\nIMHO it's unlikely for somebody to stumble on it and not read the\ncomment or look at an existing call, if only because the function you'd\nprobably reach for immediately is more like oid_array_for_each_unique().\n\n-Peff\n"},{"id":"411625","messageId":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X8qEg/KiAQDugPC0@coredump.intra.peff.net","subject":"[PATCH v2 0/9] misc commit-graph and oid-array cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:17Z","receivedAt":"2020-12-07T19:11:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here's a re-roll of my series to clean up commit-graph and oid-array.\nThe changes are all cosmetic: comments and commit messages (and most of\nthose just in the for-loop patch). I recommend just reading the\nrange-diff below, if you reviewed v1.\n\n  [1/9]: oid-array.h: drop sha1 mention from header guard\n  [2/9]: t0064: drop sha1 mention from filename\n  [3/9]: t0064: make duplicate tests more robust\n  [4/9]: cache.h: move hash/oid functions to hash.h\n  [5/9]: oid-array: make sort function public\n  [6/9]: oid-array: provide a for-loop iterator\n  [7/9]: commit-graph: drop count_distinct_commits() function\n  [8/9]: commit-graph: replace packed_oid_list with oid_array\n  [9/9]: commit-graph: use size_t for array allocation and indexing\n\n cache.h                                       |  94 ---------------\n commit-graph.c                                | 107 +++---------------\n hash.h                                        |  95 ++++++++++++++++\n oid-array.c                                   |  17 ++-\n oid-array.h                                   |  34 +++++-\n t/{t0064-sha1-array.sh => t0064-oid-array.sh} |   9 +-\n 6 files changed, 157 insertions(+), 199 deletions(-)\n rename t/{t0064-sha1-array.sh => t0064-oid-array.sh} (90%)\n\nRange-diff from v1:\n\n 1:  7cfd2f9a29 =  1:  1b52a4ea67 oid-array.h: drop sha1 mention from header guard\n 2:  82b8902560 =  2:  96ef8b8bb8 t0064: drop sha1 mention from filename\n 3:  b69af2f0d5 =  3:  7382ad6d52 t0064: make duplicate tests more robust\n 4:  0e258a486a =  4:  a0b8b9aabf cache.h: move hash/oid functions to hash.h\n 5:  1ed342fe20 =  5:  336650a307 oid-array: make sort function public\n 6:  28893c76f8 !  6:  cc1c2a16da oid-array: provide a for-loop iterator\n    @@ oid-array.h: void oid_array_filter(struct oid_array *array,\n      void oid_array_sort(struct oid_array *array);\n      \n     +/**\n    -+ * Find the next unique oid in the array after position \"cur\". You\n    -+ * can use this to iterate over unique elements, like:\n    ++ * Find the next unique oid in the array after position \"cur\".\n    ++ * The array must be sorted for this to work. You can iterate\n    ++ * over unique elements like this:\n     + *\n     + *   size_t i;\n     + *   oid_array_sort(array);\n 7:  d025d6215c !  7:  16fd32e41c commit-graph: drop count_distinct_commits() function\n    @@ Commit message\n         the count are:\n     \n           - check if our count will overflow our data structures. But the limit\n    -        there is 2^31 commits, so it's not likely to happen in practice.\n    +        there is 2^31 commits, so while this is a useful check, the\n    +        off-by-one is not likely to matter.\n     \n           - pre-allocate the array of commit pointers. But over-allocating by\n    -        one isn't a problem.\n    +        one isn't a problem; we'll just waste a few extra bytes.\n     \n         The bug would be easy enough to fix, but we can observe that neither of\n    -    those steps is necessary. We'll check the count of the commit array\n    -    after we build it anyway, so checking at this point is redundant. And we\n    -    use ALLOC_GROW() when building the commit array, so there's no need to\n    -    preallocate it (it's possible that doing so is slightly more efficient,\n    -    but if we care we can just optimistically allocate one slot for each\n    -    oid; I didn't bother here).\n    +    those steps is necessary.\n    +\n    +    After building the actual commit array, we'll likewise check its count\n    +    for overflow. So the extra check of the distinct commit count here is\n    +    redundant.\n    +\n    +    And likewise we use ALLOC_GROW() when building the commit array, so\n    +    there's no need to preallocate it (it's possible that doing so is\n    +    slightly more efficient, but if we care we can just optimistically\n    +    allocate one slot for each oid; I didn't bother here).\n     \n         So count_distinct_commits() isn't doing anything useful. Let's just get\n         rid of that step.\n     \n         Note that a side effect of the function was that we sorted the list of\n         oids, which we do rely on in copy_oids_to_commits(), since it must also\n    -    skip the duplicates. So we'll move the qsort there.\n    +    skip the duplicates. So we'll move the qsort there. I didn't copy the\n    +    \"TODO\" about adding more progress meters. It's actually quite hard to\n    +    make a repository large enough for this qsort would take an appreciable\n    +    amount of time, so this doesn't seem like a useful note.\n     \n         Signed-off-by: Jeff King <peff@peff.net>\n     \n 8:  55d6052e0d =  8:  b0f6326fbe commit-graph: replace packed_oid_list with oid_array\n 9:  c9c6e2de47 =  9:  89848e2214 commit-graph: use size_t for array allocation and indexing\n"},{"id":"411626","messageId":"X85+Jlz/bjbuqTJq@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 1/9] oid-array.h: drop sha1 mention from header guard","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:30Z","receivedAt":"2020-12-07T19:11:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When this file was moved from sha1-array.h, we forgot to update the\npreprocessor header guard to match the new name.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.h | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/oid-array.h b/oid-array.h\nindex f28d322c90..2c8b64c393 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -1,5 +1,5 @@\n-#ifndef SHA1_ARRAY_H\n-#define SHA1_ARRAY_H\n+#ifndef OID_ARRAY_H\n+#define OID_ARRAY_H\n \n /**\n  * The API provides storage and manipulation of sets of object identifiers.\n@@ -106,4 +106,4 @@ void oid_array_filter(struct oid_array *array,\n \t\t      for_each_oid_fn want,\n \t\t      void *cbdata);\n \n-#endif /* SHA1_ARRAY_H */\n+#endif /* OID_ARRAY_H */\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411627","messageId":"X85+KDCTAt585oLk@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 2/9] t0064: drop sha1 mention from filename","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:32Z","receivedAt":"2020-12-07T19:11:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The data type is an oid_array these days, and we are using \"test-tool\noid-array\", so let's name the test script appropriately.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/{t0064-sha1-array.sh => t0064-oid-array.sh} | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n rename t/{t0064-sha1-array.sh => t0064-oid-array.sh} (96%)\n\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-oid-array.sh\nsimilarity index 96%\nrename from t/t0064-sha1-array.sh\nrename to t/t0064-oid-array.sh\nindex 45685af2fd..71034a8007 100755\n--- a/t/t0064-sha1-array.sh\n+++ b/t/t0064-oid-array.sh\n@@ -1,6 +1,6 @@\n #!/bin/sh\n \n-test_description='basic tests for the SHA1 array implementation'\n+test_description='basic tests for the oid array implementation'\n . ./test-lib.sh\n \n echoid () {\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411628","messageId":"X85+PGwkaOai2dLS@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 3/9] t0064: make duplicate tests more robust","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:52Z","receivedAt":"2020-12-07T19:11:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our tests for handling duplicates in oid-array provide only a single\nduplicate for each number, so our sorted array looks like:\n\n  44 44 55 55 88 88 aa aa\n\nA slightly more interesting test is to have multiple duplicates, which\nmakes sure that we not only skip the duplicate, but keep skipping until\nwe are out of the set of matching duplicates.\n\nUnsurprisingly this works just fine, but it's worth beefing up this test\nsince we're about to change the duplicate-detection code.\n\nNote that we do need to adjust the results on the lookup test, since it\nis returning the index of the found item (and now we have more items\nbefore our range, and the range itself is slightly larger, since we'll\naccept a match of any element).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n t/t0064-oid-array.sh | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t0064-oid-array.sh b/t/t0064-oid-array.sh\nindex 71034a8007..2e5438ccda 100755\n--- a/t/t0064-oid-array.sh\n+++ b/t/t0064-oid-array.sh\n@@ -25,6 +25,7 @@ test_expect_success 'ordered enumeration' '\n test_expect_success 'ordered enumeration with duplicate suppression' '\n \techoid \"\" 44 55 88 aa >expect &&\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techo for_each_unique\n@@ -52,17 +53,19 @@ test_expect_success 'lookup non-existing entry' '\n \n test_expect_success 'lookup with duplicates' '\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 55\n \t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n-\ttest \"$n\" -ge 2 &&\n-\ttest \"$n\" -le 3\n+\ttest \"$n\" -ge 3 &&\n+\ttest \"$n\" -le 5\n '\n \n test_expect_success 'lookup non-existing entry with duplicates' '\n \t{\n+\t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 66\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411629","messageId":"X85+P165Fk4DoCHc@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 4/9] cache.h: move hash/oid functions to hash.h","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:55Z","receivedAt":"2020-12-07T19:11:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We define git_hash_algo and object_id in hash.h, but most of the utility\nfunctions are declared in the main cache.h. Let's move them to hash.h\nalong with their struct definitions. This cleans up cache.h a bit, but\nalso avoids circular dependencies when other headers need to know about\nthese functions (e.g., if oid-array.h were to have an inline that used\noideq(), it couldn't include cache.h because it is itself included by\ncache.h).\n\nNo including C files should be affected, because hash.h is always\nincluded in cache.h already.\n\nWe do have to mention repository.h at the top of hash.h, though, since\nwe depend on the_repository in some of our inline functions.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n cache.h | 94 --------------------------------------------------------\n hash.h  | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 95 insertions(+), 94 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e986cf4ea9..ec98f5d32c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1123,100 +1123,6 @@ const char *repo_find_unique_abbrev(struct repository *r, const struct object_id\n int repo_find_unique_abbrev_r(struct repository *r, char *hex, const struct object_id *oid, int len);\n #define find_unique_abbrev_r(hex, oid, len) repo_find_unique_abbrev_r(the_repository, hex, oid, len)\n \n-extern const struct object_id null_oid;\n-\n-static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n-{\n-\t/*\n-\t * Teach the compiler that there are only two possibilities of hash size\n-\t * here, so that it can optimize for this case as much as possible.\n-\t */\n-\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n-\t\treturn memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n-\treturn memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n-}\n-\n-static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)\n-{\n-\treturn hashcmp(oid1->hash, oid2->hash);\n-}\n-\n-static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2)\n-{\n-\t/*\n-\t * We write this here instead of deferring to hashcmp so that the\n-\t * compiler can properly inline it and avoid calling memcmp.\n-\t */\n-\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n-\t\treturn !memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n-\treturn !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n-}\n-\n-static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)\n-{\n-\treturn hasheq(oid1->hash, oid2->hash);\n-}\n-\n-static inline int is_null_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, &null_oid);\n-}\n-\n-static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n-{\n-\tmemcpy(sha_dst, sha_src, the_hash_algo->rawsz);\n-}\n-\n-static inline void oidcpy(struct object_id *dst, const struct object_id *src)\n-{\n-\tmemcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);\n-}\n-\n-static inline struct object_id *oiddup(const struct object_id *src)\n-{\n-\tstruct object_id *dst = xmalloc(sizeof(struct object_id));\n-\toidcpy(dst, src);\n-\treturn dst;\n-}\n-\n-static inline void hashclr(unsigned char *hash)\n-{\n-\tmemset(hash, 0, the_hash_algo->rawsz);\n-}\n-\n-static inline void oidclr(struct object_id *oid)\n-{\n-\tmemset(oid->hash, 0, GIT_MAX_RAWSZ);\n-}\n-\n-static inline void oidread(struct object_id *oid, const unsigned char *hash)\n-{\n-\tmemcpy(oid->hash, hash, the_hash_algo->rawsz);\n-}\n-\n-static inline int is_empty_blob_sha1(const unsigned char *sha1)\n-{\n-\treturn hasheq(sha1, the_hash_algo->empty_blob->hash);\n-}\n-\n-static inline int is_empty_blob_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, the_hash_algo->empty_blob);\n-}\n-\n-static inline int is_empty_tree_sha1(const unsigned char *sha1)\n-{\n-\treturn hasheq(sha1, the_hash_algo->empty_tree->hash);\n-}\n-\n-static inline int is_empty_tree_oid(const struct object_id *oid)\n-{\n-\treturn oideq(oid, the_hash_algo->empty_tree);\n-}\n-\n-const char *empty_tree_oid_hex(void);\n-const char *empty_blob_oid_hex(void);\n-\n /* set default permissions by passing mode arguments to open(2) */\n int git_mkstemps_mode(char *pattern, int suffix_len, int mode);\n int git_mkstemp_mode(char *pattern, int mode);\ndiff --git a/hash.h b/hash.h\nindex e0f3f16b06..3fb0c3d400 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -2,6 +2,7 @@\n #define HASH_H\n \n #include \"git-compat-util.h\"\n+#include \"repository.h\"\n \n #if defined(SHA1_PPC)\n #include \"ppc/sha1.h\"\n@@ -184,4 +185,98 @@ struct object_id {\n \n #define the_hash_algo the_repository->hash_algo\n \n+extern const struct object_id null_oid;\n+\n+static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)\n+{\n+\t/*\n+\t * Teach the compiler that there are only two possibilities of hash size\n+\t * here, so that it can optimize for this case as much as possible.\n+\t */\n+\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n+\t\treturn memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n+\treturn memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n+}\n+\n+static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)\n+{\n+\treturn hashcmp(oid1->hash, oid2->hash);\n+}\n+\n+static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2)\n+{\n+\t/*\n+\t * We write this here instead of deferring to hashcmp so that the\n+\t * compiler can properly inline it and avoid calling memcmp.\n+\t */\n+\tif (the_hash_algo->rawsz == GIT_MAX_RAWSZ)\n+\t\treturn !memcmp(sha1, sha2, GIT_MAX_RAWSZ);\n+\treturn !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);\n+}\n+\n+static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)\n+{\n+\treturn hasheq(oid1->hash, oid2->hash);\n+}\n+\n+static inline int is_null_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, &null_oid);\n+}\n+\n+static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src)\n+{\n+\tmemcpy(sha_dst, sha_src, the_hash_algo->rawsz);\n+}\n+\n+static inline void oidcpy(struct object_id *dst, const struct object_id *src)\n+{\n+\tmemcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);\n+}\n+\n+static inline struct object_id *oiddup(const struct object_id *src)\n+{\n+\tstruct object_id *dst = xmalloc(sizeof(struct object_id));\n+\toidcpy(dst, src);\n+\treturn dst;\n+}\n+\n+static inline void hashclr(unsigned char *hash)\n+{\n+\tmemset(hash, 0, the_hash_algo->rawsz);\n+}\n+\n+static inline void oidclr(struct object_id *oid)\n+{\n+\tmemset(oid->hash, 0, GIT_MAX_RAWSZ);\n+}\n+\n+static inline void oidread(struct object_id *oid, const unsigned char *hash)\n+{\n+\tmemcpy(oid->hash, hash, the_hash_algo->rawsz);\n+}\n+\n+static inline int is_empty_blob_sha1(const unsigned char *sha1)\n+{\n+\treturn hasheq(sha1, the_hash_algo->empty_blob->hash);\n+}\n+\n+static inline int is_empty_blob_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, the_hash_algo->empty_blob);\n+}\n+\n+static inline int is_empty_tree_sha1(const unsigned char *sha1)\n+{\n+\treturn hasheq(sha1, the_hash_algo->empty_tree->hash);\n+}\n+\n+static inline int is_empty_tree_oid(const struct object_id *oid)\n+{\n+\treturn oideq(oid, the_hash_algo->empty_tree);\n+}\n+\n+const char *empty_tree_oid_hex(void);\n+const char *empty_blob_oid_hex(void);\n+\n #endif\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411630","messageId":"X85+QVRIX4L+k44J@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 5/9] oid-array: make sort function public","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:10:57Z","receivedAt":"2020-12-07T19:11:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We sort the oid-array as a side effect of calling the lookup or\nunique-iteration functions. But callers may want to sort it themselves\n(especially as we add new iteration options in future patches).\n\nWe'll also move the check of the \"sorted\" flag into the sort function,\nso callers don't have to remember to check it.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.c | 10 +++++-----\n oid-array.h |  5 +++++\n 2 files changed, 10 insertions(+), 5 deletions(-)\n\ndiff --git a/oid-array.c b/oid-array.c\nindex 8657a5cedf..29f718d835 100644\n--- a/oid-array.c\n+++ b/oid-array.c\n@@ -14,8 +14,10 @@ static int void_hashcmp(const void *a, const void *b)\n \treturn oidcmp(a, b);\n }\n \n-static void oid_array_sort(struct oid_array *array)\n+void oid_array_sort(struct oid_array *array)\n {\n+\tif (array->sorted)\n+\t\treturn;\n \tQSORT(array->oid, array->nr, void_hashcmp);\n \tarray->sorted = 1;\n }\n@@ -28,8 +30,7 @@ static const unsigned char *sha1_access(size_t index, void *table)\n \n int oid_array_lookup(struct oid_array *array, const struct object_id *oid)\n {\n-\tif (!array->sorted)\n-\t\toid_array_sort(array);\n+\toid_array_sort(array);\n \treturn sha1_pos(oid->hash, array->oid, array->nr, sha1_access);\n }\n \n@@ -64,8 +65,7 @@ int oid_array_for_each_unique(struct oid_array *array,\n {\n \tsize_t i;\n \n-\tif (!array->sorted)\n-\t\toid_array_sort(array);\n+\toid_array_sort(array);\n \n \tfor (i = 0; i < array->nr; i++) {\n \t\tint ret;\ndiff --git a/oid-array.h b/oid-array.h\nindex 2c8b64c393..6a22c0ac94 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -106,4 +106,9 @@ void oid_array_filter(struct oid_array *array,\n \t\t      for_each_oid_fn want,\n \t\t      void *cbdata);\n \n+/**\n+ * Sort the array in order of ascending object id.\n+ */\n+void oid_array_sort(struct oid_array *array);\n+\n #endif /* OID_ARRAY_H */\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411631","messageId":"X85+RNGwV9WWeIXZ@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 6/9] oid-array: provide a for-loop iterator","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:11:00Z","receivedAt":"2020-12-07T19:11:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We provide oid_array_for_each_unique() for iterating over the\nde-duplicated items in an array. But it's awkward to use for two\nreasons:\n\n  1. It uses a callback, which means marshaling arguments into a struct\n     and passing it to the callback with a void parameter.\n\n  2. The callback doesn't know the numeric index of the oid we're\n     looking at. This is useful for things like progress meters.\n\nIterating with a for-loop is much more natural for some cases, but the\ncaller has to do the de-duping itself. However, we can provide a small\nhelper to make this easier (see the docstring in the header for an\nexample use).\n\nThe caller does have to remember to sort the array first. We could add\nan assertion into the helper that array->sorted is set, but I didn't\nwant to complicate what is otherwise a pretty fast code path.\n\nI also considered adding a full iterator type with init/next/end\nfunctions (similar to what we have for hashmaps). But it ended up making\nthe callers much harder to read. This version keeps us close to a basic\nfor-loop.\n\nYet another option would be adding an option to sort the array and\ncompact out the duplicates. This would mean iterating over the array an\nextra time, though that's probably not a big deal (we did just do an\nO(n log n) sort). But we'd still have to write a for-loop to iterate, so\nit doesn't really make anything easier for the caller.\n\nNo new test, since we'll convert the callback iterator (which is covered\nby t0064, among other callers) to use the new code.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oid-array.c |  7 ++-----\n oid-array.h | 23 +++++++++++++++++++++++\n 2 files changed, 25 insertions(+), 5 deletions(-)\n\ndiff --git a/oid-array.c b/oid-array.c\nindex 29f718d835..8e1bcedc0c 100644\n--- a/oid-array.c\n+++ b/oid-array.c\n@@ -67,11 +67,8 @@ int oid_array_for_each_unique(struct oid_array *array,\n \n \toid_array_sort(array);\n \n-\tfor (i = 0; i < array->nr; i++) {\n-\t\tint ret;\n-\t\tif (i > 0 && oideq(array->oid + i, array->oid + i - 1))\n-\t\t\tcontinue;\n-\t\tret = fn(array->oid + i, data);\n+\tfor (i = 0; i < array->nr; i = oid_array_next_unique(array, i)) {\n+\t\tint ret = fn(array->oid + i, data);\n \t\tif (ret)\n \t\t\treturn ret;\n \t}\ndiff --git a/oid-array.h b/oid-array.h\nindex 6a22c0ac94..72bca78b7d 100644\n--- a/oid-array.h\n+++ b/oid-array.h\n@@ -1,6 +1,8 @@\n #ifndef OID_ARRAY_H\n #define OID_ARRAY_H\n \n+#include \"hash.h\"\n+\n /**\n  * The API provides storage and manipulation of sets of object identifiers.\n  * The emphasis is on storage and processing efficiency, making them suitable\n@@ -111,4 +113,25 @@ void oid_array_filter(struct oid_array *array,\n  */\n void oid_array_sort(struct oid_array *array);\n \n+/**\n+ * Find the next unique oid in the array after position \"cur\".\n+ * The array must be sorted for this to work. You can iterate\n+ * over unique elements like this:\n+ *\n+ *   size_t i;\n+ *   oid_array_sort(array);\n+ *   for (i = 0; i < array->nr; i = oid_array_next_unique(array, i))\n+ *\tprintf(\"%s\", oid_to_hex(array->oids[i]);\n+ *\n+ * Non-unique iteration can just increment with \"i++\" to visit each element.\n+ */\n+static inline size_t oid_array_next_unique(struct oid_array *array, size_t cur)\n+{\n+\tdo {\n+\t\tcur++;\n+\t} while (cur < array->nr &&\n+\t\t oideq(array->oid + cur, array->oid + cur - 1));\n+\treturn cur;\n+}\n+\n #endif /* OID_ARRAY_H */\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411632","messageId":"X85+RnO5rJQHnmmB@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 7/9] commit-graph: drop count_distinct_commits() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:11:02Z","receivedAt":"2020-12-07T19:11:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When writing a commit graph, we collect a list of object ids in an\narray, which we'll eventually copy into an array of \"struct commit\"\npointers. Before we do that, though, we count the number of distinct\ncommit entries. There's a subtle bug in this step, though.\n\nWe eliminate not only duplicate oids, but also in split mode, any oids\nwhich are not commits or which are already in a graph file. However, the\nloop starts at index 1, always counting index 0 as distinct. And indeed\nit can't be a duplicate, since we check for those by comparing against\nthe previous entry, and there isn't one for index 0. But it could be a\ncommit that's already in a graph file, and we'd overcount the number of\ncommits by 1 in that case.\n\nThat turns out not to be a problem, though. The only things we do with\nthe count are:\n\n  - check if our count will overflow our data structures. But the limit\n    there is 2^31 commits, so while this is a useful check, the\n    off-by-one is not likely to matter.\n\n  - pre-allocate the array of commit pointers. But over-allocating by\n    one isn't a problem; we'll just waste a few extra bytes.\n\nThe bug would be easy enough to fix, but we can observe that neither of\nthose steps is necessary.\n\nAfter building the actual commit array, we'll likewise check its count\nfor overflow. So the extra check of the distinct commit count here is\nredundant.\n\nAnd likewise we use ALLOC_GROW() when building the commit array, so\nthere's no need to preallocate it (it's possible that doing so is\nslightly more efficient, but if we care we can just optimistically\nallocate one slot for each oid; I didn't bother here).\n\nSo count_distinct_commits() isn't doing anything useful. Let's just get\nrid of that step.\n\nNote that a side effect of the function was that we sorted the list of\noids, which we do rely on in copy_oids_to_commits(), since it must also\nskip the duplicates. So we'll move the qsort there. I didn't copy the\n\"TODO\" about adding more progress meters. It's actually quite hard to\nmake a repository large enough for this qsort would take an appreciable\namount of time, so this doesn't seem like a useful note.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 43 ++-----------------------------------------\n 1 file changed, 2 insertions(+), 41 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 6f62a07313..1ac3516cf5 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1588,35 +1588,6 @@ static void fill_oids_from_all_packs(struct write_commit_graph_context *ctx)\n \tstop_progress(&ctx->progress);\n }\n \n-static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n-{\n-\tuint32_t i, count_distinct = 1;\n-\n-\tif (ctx->report_progress)\n-\t\tctx->progress = start_delayed_progress(\n-\t\t\t_(\"Counting distinct commits in commit graph\"),\n-\t\t\tctx->oids.nr);\n-\tdisplay_progress(ctx->progress, 0); /* TODO: Measure QSORT() progress */\n-\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n-\n-\tfor (i = 1; i < ctx->oids.nr; i++) {\n-\t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (!oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i])) {\n-\t\t\tif (ctx->split) {\n-\t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n-\n-\t\t\t\tif (!c || commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)\n-\t\t\t\t\tcontinue;\n-\t\t\t}\n-\n-\t\t\tcount_distinct++;\n-\t\t}\n-\t}\n-\tstop_progress(&ctx->progress);\n-\n-\treturn count_distinct;\n-}\n-\n static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n {\n \tuint32_t i;\n@@ -1628,6 +1599,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->progress = start_delayed_progress(\n \t\t\t_(\"Finding extra edges in commit graph\"),\n \t\t\tctx->oids.nr);\n+\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tunsigned int num_parents;\n \n@@ -2155,7 +2127,7 @@ int write_commit_graph(struct object_directory *odb,\n \t\t       const struct commit_graph_opts *opts)\n {\n \tstruct write_commit_graph_context *ctx;\n-\tuint32_t i, count_distinct = 0;\n+\tuint32_t i;\n \tint res = 0;\n \tint replace = 0;\n \tstruct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;\n@@ -2268,17 +2240,6 @@ int write_commit_graph(struct object_directory *odb,\n \n \tclose_reachable(ctx);\n \n-\tcount_distinct = count_distinct_commits(ctx);\n-\n-\tif (count_distinct >= GRAPH_EDGE_LAST_MASK) {\n-\t\terror(_(\"the commit graph format cannot write %d commits\"), count_distinct);\n-\t\tres = -1;\n-\t\tgoto cleanup;\n-\t}\n-\n-\tctx->commits.alloc = count_distinct;\n-\tALLOC_ARRAY(ctx->commits.list, ctx->commits.alloc);\n-\n \tcopy_oids_to_commits(ctx);\n \n \tif (ctx->commits.nr >= GRAPH_EDGE_LAST_MASK) {\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411633","messageId":"X85+SY6d1QG+5YSz@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 8/9] commit-graph: replace packed_oid_list with oid_array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:11:05Z","receivedAt":"2020-12-07T19:11:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our custom packed_oid_list data structure is really just an oid_array in\ndisguise. Let's switch to using the generic structure, which shortens\nand simplifies the code slightly.\n\nThere's one slightly awkward part: in the old code we copied a hash\nstraight from the mmap'd on-disk data into the final object_id. And now\nwe'll copy to a temporary oid, which we'll then pass to\noid_array_append(). But this is an operation we have to do all over the\ncommit-graph code already, since it mostly uses object_id structs\ninternally. I also measured \"git commit-graph --append\", which triggers\nthis code path, and it showed no difference.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 62 ++++++++++++--------------------------------------\n 1 file changed, 15 insertions(+), 47 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 1ac3516cf5..4a718fd6e6 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -936,17 +936,11 @@ struct packed_commit_list {\n \tint alloc;\n };\n \n-struct packed_oid_list {\n-\tstruct object_id *list;\n-\tint nr;\n-\tint alloc;\n-};\n-\n struct write_commit_graph_context {\n \tstruct repository *r;\n \tstruct object_directory *odb;\n \tchar *graph_name;\n-\tstruct packed_oid_list oids;\n+\tstruct oid_array oids;\n \tstruct packed_commit_list commits;\n \tint num_extra_edges;\n \tunsigned long approx_nr_objects;\n@@ -1240,13 +1234,6 @@ static int write_graph_chunk_bloom_data(struct hashfile *f,\n \treturn 0;\n }\n \n-static int oid_compare(const void *_a, const void *_b)\n-{\n-\tconst struct object_id *a = (const struct object_id *)_a;\n-\tconst struct object_id *b = (const struct object_id *)_b;\n-\treturn oidcmp(a, b);\n-}\n-\n static int add_packed_commits(const struct object_id *oid,\n \t\t\t      struct packed_git *pack,\n \t\t\t      uint32_t pos,\n@@ -1267,10 +1254,7 @@ static int add_packed_commits(const struct object_id *oid,\n \tif (type != OBJ_COMMIT)\n \t\treturn 0;\n \n-\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\toidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);\n-\tctx->oids.nr++;\n-\n+\toid_array_append(&ctx->oids, oid);\n \tset_commit_pos(ctx->r, oid);\n \n \treturn 0;\n@@ -1281,9 +1265,7 @@ static void add_missing_parents(struct write_commit_graph_context *ctx, struct c\n \tstruct commit_list *parent;\n \tfor (parent = commit->parents; parent; parent = parent->next) {\n \t\tif (!(parent->item->object.flags & REACHABLE)) {\n-\t\t\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\t\t\toidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid));\n-\t\t\tctx->oids.nr++;\n+\t\t\toid_array_append(&ctx->oids, &parent->item->object.oid);\n \t\t\tparent->item->object.flags |= REACHABLE;\n \t\t}\n \t}\n@@ -1302,7 +1284,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->oids.nr);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \t\tif (commit)\n \t\t\tcommit->object.flags |= REACHABLE;\n \t}\n@@ -1319,7 +1301,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\t0);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (!commit)\n \t\t\tcontinue;\n@@ -1339,7 +1321,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->oids.nr);\n \tfor (i = 0; i < ctx->oids.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tcommit = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tcommit = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (commit)\n \t\t\tcommit->object.flags &= ~REACHABLE;\n@@ -1567,9 +1549,7 @@ static int fill_oids_from_commits(struct write_commit_graph_context *ctx,\n \n \toidset_iter_init(commits, &iter);\n \twhile ((oid = oidset_iter_next(&iter))) {\n-\t\tALLOC_GROW(ctx->oids.list, ctx->oids.nr + 1, ctx->oids.alloc);\n-\t\toidcpy(&ctx->oids.list[ctx->oids.nr], oid);\n-\t\tctx->oids.nr++;\n+\t\toid_array_append(&ctx->oids, oid);\n \t}\n \n \treturn 0;\n@@ -1599,16 +1579,14 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->progress = start_delayed_progress(\n \t\t\t_(\"Finding extra edges in commit graph\"),\n \t\t\tctx->oids.nr);\n-\tQSORT(ctx->oids.list, ctx->oids.nr, oid_compare);\n-\tfor (i = 0; i < ctx->oids.nr; i++) {\n+\toid_array_sort(&ctx->oids);\n+\tfor (i = 0; i < ctx->oids.nr; i = oid_array_next_unique(&ctx->oids, i)) {\n \t\tunsigned int num_parents;\n \n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (i > 0 && oideq(&ctx->oids.list[i - 1], &ctx->oids.list[i]))\n-\t\t\tcontinue;\n \n \t\tALLOC_GROW(ctx->commits.list, ctx->commits.nr + 1, ctx->commits.alloc);\n-\t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n+\t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.oid[i]);\n \n \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n \t\t    commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n@@ -2199,26 +2177,16 @@ int write_commit_graph(struct object_directory *odb,\n \t}\n \n \tctx->approx_nr_objects = approximate_object_count();\n-\tctx->oids.alloc = ctx->approx_nr_objects / 32;\n \n-\tif (ctx->split && opts && ctx->oids.alloc > opts->max_commits)\n-\t\tctx->oids.alloc = opts->max_commits;\n-\n-\tif (ctx->append) {\n+\tif (ctx->append)\n \t\tprepare_commit_graph_one(ctx->r, ctx->odb);\n-\t\tif (ctx->r->objects->commit_graph)\n-\t\t\tctx->oids.alloc += ctx->r->objects->commit_graph->num_commits;\n-\t}\n-\n-\tif (ctx->oids.alloc < 1024)\n-\t\tctx->oids.alloc = 1024;\n-\tALLOC_ARRAY(ctx->oids.list, ctx->oids.alloc);\n \n \tif (ctx->append && ctx->r->objects->commit_graph) {\n \t\tstruct commit_graph *g = ctx->r->objects->commit_graph;\n \t\tfor (i = 0; i < g->num_commits; i++) {\n-\t\t\tconst unsigned char *hash = g->chunk_oid_lookup + g->hash_len * i;\n-\t\t\thashcpy(ctx->oids.list[ctx->oids.nr++].hash, hash);\n+\t\t\tstruct object_id oid;\n+\t\t\thashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * i);\n+\t\t\toid_array_append(&ctx->oids, &oid);\n \t\t}\n \t}\n \n@@ -2274,7 +2242,7 @@ int write_commit_graph(struct object_directory *odb,\n cleanup:\n \tfree(ctx->graph_name);\n \tfree(ctx->commits.list);\n-\tfree(ctx->oids.list);\n+\toid_array_clear(&ctx->oids);\n \n \tif (ctx->commit_graph_filenames_after) {\n \t\tfor (i = 0; i < ctx->num_commit_graphs_after; i++) {\n-- \n2.29.2.980.g762a4e4ed3\n\n"},{"id":"411634","messageId":"X85+TEQusPhTUmSj@coredump.intra.peff.net","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"[PATCH v2 9/9] commit-graph: use size_t for array allocation and indexing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-12-07T19:11:08Z","receivedAt":"2020-12-07T19:11:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our packed_commit_list is an array of pointers to commit structs. We use\n\"int\" for the allocation, which is 32-bit even on 64-bit platforms. This\nisn't likely to overflow in practice (we're writing commit graphs, so\nyou'd need to actually have billions of unique commits in the\nrepository). But it's good practice to use size_t for allocations.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n commit-graph.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 4a718fd6e6..06f8dc1d89 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -932,8 +932,8 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit\n \n struct packed_commit_list {\n \tstruct commit **list;\n-\tint nr;\n-\tint alloc;\n+\tsize_t nr;\n+\tsize_t alloc;\n };\n \n struct write_commit_graph_context {\n-- \n2.29.2.980.g762a4e4ed3\n"},{"id":"411637","messageId":"581165d3-1590-6a45-2a0e-94c0dfa5627f@gmail.com","threadId":"54763","inReplyTo":"X85+GbvmN4wIjsYY@coredump.intra.peff.net","subject":"Re: [PATCH v2 0/9] misc commit-graph and oid-array cleanups","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-07T19:26:20Z","receivedAt":"2020-12-07T19:27:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/7/2020 2:10 PM, Jeff King wrote:\n> Here's a re-roll of my series to clean up commit-graph and oid-array.\n> The changes are all cosmetic: comments and commit messages (and most of\n> those just in the for-loop patch). I recommend just reading the\n> range-diff below, if you reviewed v1.\n\nRange-diff LGTM. Thanks,\n-Stolee\n"}]}