{"thread":{"id":"44078","subject":"[PATCH] sha1_file: use llist_mergesort() for sorting packs","startedAt":"2016-09-13T17:55:14Z","lastAt":"2016-09-13T18:13:35Z","messageCount":2,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"301861","messageId":"a313343b-173e-4a07-f383-859a6f262651@web.de","threadId":"44078","inReplyTo":null,"subject":"[PATCH] sha1_file: use llist_mergesort() for sorting packs","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-13T17:54:42Z","receivedAt":"2016-09-13T17:55:14Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Sort the linked list of packs directly using llist_mergesort() instead\nof building an array, calling qsort(3) and fixing up the list pointers.\nThis is shorter and less complicated.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nPeff: Or do you have other plans, e.g. to replace packed_git with\npacked_git_mru completely?\n\n sha1_file.c | 39 +++++++++++++++------------------------\n 1 file changed, 15 insertions(+), 24 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 472ccb2..66dccaa 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -25,6 +25,7 @@\n #include \"dir.h\"\n #include \"mru.h\"\n #include \"list.h\"\n+#include \"mergesort.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -1380,10 +1381,20 @@ static void prepare_packed_git_one(char *objdir, int local)\n \tstrbuf_release(&path);\n }\n \n+static void *get_next_packed_git(const void *p)\n+{\n+\treturn ((const struct packed_git *)p)->next;\n+}\n+\n+static void set_next_packed_git(void *p, void *next)\n+{\n+\t((struct packed_git *)p)->next = next;\n+}\n+\n static int sort_pack(const void *a_, const void *b_)\n {\n-\tstruct packed_git *a = *((struct packed_git **)a_);\n-\tstruct packed_git *b = *((struct packed_git **)b_);\n+\tconst struct packed_git *a = a_;\n+\tconst struct packed_git *b = b_;\n \tint st;\n \n \t/*\n@@ -1410,28 +1421,8 @@ static int sort_pack(const void *a_, const void *b_)\n \n static void rearrange_packed_git(void)\n {\n-\tstruct packed_git **ary, *p;\n-\tint i, n;\n-\n-\tfor (n = 0, p = packed_git; p; p = p->next)\n-\t\tn++;\n-\tif (n < 2)\n-\t\treturn;\n-\n-\t/* prepare an array of packed_git for easier sorting */\n-\tary = xcalloc(n, sizeof(struct packed_git *));\n-\tfor (n = 0, p = packed_git; p; p = p->next)\n-\t\tary[n++] = p;\n-\n-\tqsort(ary, n, sizeof(struct packed_git *), sort_pack);\n-\n-\t/* link them back again */\n-\tfor (i = 0; i < n - 1; i++)\n-\t\tary[i]->next = ary[i + 1];\n-\tary[n - 1]->next = NULL;\n-\tpacked_git = ary[0];\n-\n-\tfree(ary);\n+\tpacked_git = llist_mergesort(packed_git, get_next_packed_git,\n+\t\t\t\t     set_next_packed_git, sort_pack);\n }\n \n static void prepare_packed_git_mru(void)\n-- \n2.10.0\n\n"},{"id":"301862","messageId":"20160913181325.32sdyyaf5dholjy2@sigill.intra.peff.net","threadId":"44078","inReplyTo":"a313343b-173e-4a07-f383-859a6f262651@web.de","subject":"Re: [PATCH] sha1_file: use llist_mergesort() for sorting packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-13T18:13:26Z","receivedAt":"2016-09-13T18:13:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 13, 2016 at 07:54:42PM +0200, René Scharfe wrote:\n\n> Sort the linked list of packs directly using llist_mergesort() instead\n> of building an array, calling qsort(3) and fixing up the list pointers.\n> This is shorter and less complicated.\n\nMakes sense.\n\n> Peff: Or do you have other plans, e.g. to replace packed_git with\n> packed_git_mru completely?\n\nNope. I haven't looked into it, but I think there would be some benefit\nto replacing packed_git_mru with the code in list.h. But I don't see any\nbenefit in replacing packed_git with that, or with the MRU itself (once\nlist.h is in use, one _could_ shove the MRU into packed_git itself, but\nI think we would still retain the original link order for reference).\n\nThanks for asking.\n\n-Peff\n"}]}