[PATCH 1/2] Move git_sort(), a stable sort, into into libgit.a

From: Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com>
Date: Sep 25, 2019, 08:36 UTC
Message-ID: <1202809db71a7b0d06efd5e50716861ecff186de.1569400558.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.352.git.gitgitgadget@gmail.com>

From: Johannes Schindelin <johannes.schindelin@gmx.de>

The `qsort()` function is not guaranteed to be stable, i.e. it does not promise to maintain the order of items it is told to consider equal. In contrast, the `git_sort()` function we carry in `compat/qsort.c` _is_ stable, by virtue of implementing a merge sort algorithm.

In preparation for using a stable sort in Git's rename detection, move the stable sort into `libgit.a` so that it is compiled in unconditionally.

Note: this also makes the hack obsolete that was introduced in
fe21c6b285d (mingw: reencode environment variables on the fly (UTF-16
<-> UTF-8), 2018-10-30), where we included `compat/qsort.c` directly in
`compat/mingw.c` to use the stable sort.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 Makefile                  | 2 +-
 compat/mingw.c            | 5 -----
 git-compat-util.h         | 4 +++-
 compat/qsort.c => qsort.c | 2 +-
 4 files changed, 5 insertions(+), 8 deletions(-)
 rename compat/qsort.c => qsort.c (97%)

diff --git a/Makefile b/Makefile
index f9255344ae..1e144598e4 100644
--- a/Makefile
+++ b/Makefile
@@ -950,6 +950,7 @@ LIB_OBJS += prio-queue.o
 LIB_OBJS += progress.o
 LIB_OBJS += prompt.o
 LIB_OBJS += protocol.o
+LIB_OBJS += qsort.o
 LIB_OBJS += quote.o
 LIB_OBJS += range-diff.o
 LIB_OBJS += reachable.o
@@ -1714,7 +1715,6 @@ ifdef NO_GETPAGESIZE
 endif
 ifdef INTERNAL_QSORT
 	COMPAT_CFLAGS += -DINTERNAL_QSORT
-	COMPAT_OBJS += compat/qsort.o
 endif
 ifdef HAVE_ISO_QSORT_S
 	COMPAT_CFLAGS += -DHAVE_ISO_QSORT_S
diff --git a/compat/mingw.c b/compat/mingw.c
index 738f0a826a..77d4ef4d19 100644
--- a/compat/mingw.c
+++ b/compat/mingw.c
@@ -1229,11 +1229,6 @@ static int wenvcmp(const void *a, const void *b)
 	return _wcsnicmp(p, q, p_len);
 }
 
-/* We need a stable sort to convert the environment between UTF-16 <-> UTF-8 */
-#ifndef INTERNAL_QSORT
-#include "qsort.c"
-#endif
-
 /*
  * Build an environment block combining the inherited environment
  * merged with the given list of settings.
diff --git a/git-compat-util.h b/git-compat-util.h
index 83be89de0a..2d46162897 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -1094,9 +1094,9 @@ static inline int strtol_i(char const *s, int base, int *result)
 	return 0;
 }
 
-#ifdef INTERNAL_QSORT
 void git_qsort(void *base, size_t nmemb, size_t size,
 	       int(*compar)(const void *, const void *));
+#ifdef INTERNAL_QSORT
 #define qsort git_qsort
 #endif
 
@@ -1108,6 +1108,8 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
 		qsort(base, nmemb, size, compar);
 }
 
+#define QSORT_STABLE(base, n, compar) git_qsort((base), (n), sizeof(*(base)), compar)
+
 #ifndef HAVE_ISO_QSORT_S
 int git_qsort_s(void *base, size_t nmemb, size_t size,
 		int (*compar)(const void *, const void *, void *), void *ctx);
diff --git a/compat/qsort.c b/qsort.c
similarity index 97%
rename from compat/qsort.c
rename to qsort.c
index 7d071afb70..08f80eea09 100644
--- a/compat/qsort.c
+++ b/qsort.c
@@ -1,4 +1,4 @@
-#include "../git-compat-util.h"
+#include "git-compat-util.h"
 
 /*
  * A merge sort implementation, simplified from the qsort implementation

-- 
gitgitgadget