# [PATCH] sha1_file: use llist_mergesort() for sorting packs

2 messages from 2016-09-13 to 2016-09-13. Participants: René Scharfe, Jeff King.
Thread: https://gitlist.dev/t/44078

## René Scharfe, 2016-09-13 17:54

Subject: [PATCH] sha1_file: use llist_mergesort() for sorting packs
Message-ID: <a313343b-173e-4a07-f383-859a6f262651@web.de>
URL: https://gitlist.dev/e/a313343b-173e-4a07-f383-859a6f262651%40web.de

```
Sort the linked list of packs directly using llist_mergesort() instead
of building an array, calling qsort(3) and fixing up the list pointers.
This is shorter and less complicated.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
Peff: Or do you have other plans, e.g. to replace packed_git with
packed_git_mru completely?

 sha1_file.c | 39 +++++++++++++++------------------------
 1 file changed, 15 insertions(+), 24 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 472ccb2..66dccaa 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -25,6 +25,7 @@
 #include "dir.h"
 #include "mru.h"
 #include "list.h"
+#include "mergesort.h"
 
 #ifndef O_NOATIME
 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -1380,10 +1381,20 @@ static void prepare_packed_git_one(char *objdir, int local)
 	strbuf_release(&path);
 }
 
+static void *get_next_packed_git(const void *p)
+{
+	return ((const struct packed_git *)p)->next;
+}
+
+static void set_next_packed_git(void *p, void *next)
+{
+	((struct packed_git *)p)->next = next;
+}
+
 static int sort_pack(const void *a_, const void *b_)
 {
-	struct packed_git *a = *((struct packed_git **)a_);
-	struct packed_git *b = *((struct packed_git **)b_);
+	const struct packed_git *a = a_;
+	const struct packed_git *b = b_;
 	int st;
 
 	/*
@@ -1410,28 +1421,8 @@ static int sort_pack(const void *a_, const void *b_)
 
 static void rearrange_packed_git(void)
 {
-	struct packed_git **ary, *p;
-	int i, n;
-
-	for (n = 0, p = packed_git; p; p = p->next)
-		n++;
-	if (n < 2)
-		return;
-
-	/* prepare an array of packed_git for easier sorting */
-	ary = xcalloc(n, sizeof(struct packed_git *));
-	for (n = 0, p = packed_git; p; p = p->next)
-		ary[n++] = p;
-
-	qsort(ary, n, sizeof(struct packed_git *), sort_pack);
-
-	/* link them back again */
-	for (i = 0; i < n - 1; i++)
-		ary[i]->next = ary[i + 1];
-	ary[n - 1]->next = NULL;
-	packed_git = ary[0];
-
-	free(ary);
+	packed_git = llist_mergesort(packed_git, get_next_packed_git,
+				     set_next_packed_git, sort_pack);
 }
 
 static void prepare_packed_git_mru(void)
-- 
2.10.0


```

## Jeff King, 2016-09-13 18:13

Subject: Re: [PATCH] sha1_file: use llist_mergesort() for sorting packs
Message-ID: <20160913181325.32sdyyaf5dholjy2@sigill.intra.peff.net>
URL: https://gitlist.dev/e/20160913181325.32sdyyaf5dholjy2%40sigill.intra.peff.net
In-Reply-To: <a313343b-173e-4a07-f383-859a6f262651@web.de>

```
On Tue, Sep 13, 2016 at 07:54:42PM +0200, René Scharfe wrote:

> Sort the linked list of packs directly using llist_mergesort() instead
> of building an array, calling qsort(3) and fixing up the list pointers.
> This is shorter and less complicated.

Makes sense.

> Peff: Or do you have other plans, e.g. to replace packed_git with
> packed_git_mru completely?

Nope. I haven't looked into it, but I think there would be some benefit
to replacing packed_git_mru with the code in list.h. But I don't see any
benefit in replacing packed_git with that, or with the MRU itself (once
list.h is in use, one _could_ shove the MRU into packed_git itself, but
I think we would still retain the original link order for reference).

Thanks for asking.

-Peff

```