From: Johannes Schindelin <johannes.schindelin@xxxxxx> 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@xxxxxx> --- 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
