Move git_sort(), a stable sort, into into libgit.a

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, and rename it to `git_stable_qsort()`.

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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/Makefile b/Makefile
index f9255344ae5009a192ab83a332be749632d94531..60c809e5807af2a782a0b5f0eec6cdc912da7455 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -983,6 +983,7 @@ LIB_OBJS += shallow.o
 LIB_OBJS += sideband.o
 LIB_OBJS += sigchain.o
 LIB_OBJS += split-index.o
+LIB_OBJS += stable-qsort.o
 LIB_OBJS += strbuf.o
 LIB_OBJS += streaming.o
 LIB_OBJS += string-list.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 738f0a826a51b850fcc93f0cadbf707c7eb0b492..50af33b2b33c98062470acf6bf8a90ef1cb20668 100644 (file)
--- 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.
@@ -1272,8 +1267,8 @@ static wchar_t *make_environment_block(char **deltaenv)
 
        /*
         * If there is a deltaenv, let's accumulate all keys into `array`,
-        * sort them using the stable git_qsort() and then copy, skipping
-        * duplicate keys
+        * sort them using the stable git_stable_qsort() and then copy,
+        * skipping duplicate keys
         */
        for (p = wenv; p && *p; ) {
                ALLOC_GROW(array, nr + 1, alloc);
@@ -1296,7 +1291,7 @@ static wchar_t *make_environment_block(char **deltaenv)
                p += wlen + 1;
        }
 
-       git_qsort(array, nr, sizeof(*array), wenvcmp);
+       git_stable_qsort(array, nr, sizeof(*array), wenvcmp);
        ALLOC_ARRAY(result, size + delta_size);
 
        for (p = result, i = 0; i < nr; i++) {

diff --git a/git-compat-util.h b/git-compat-util.h
index 83be89de0aac7c96799635e3b2858a465f440acf..7ec2c8fe3183aefaa107362b8768f66e57ec4ff2 100644 (file)
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -1094,10 +1094,10 @@ static inline int strtol_i(char const *s, int base, int *result)
        return 0;
 }
 
+void git_stable_qsort(void *base, size_t nmemb, size_t size,
+                     int(*compar)(const void *, const void *));
 #ifdef INTERNAL_QSORT
-void git_qsort(void *base, size_t nmemb, size_t size,
-              int(*compar)(const void *, const void *));
-#define qsort git_qsort
+#define qsort git_stable_qsort
 #endif
 
 #define QSORT(base, n, compar) sane_qsort((base), (n), sizeof(*(base)), compar)
@@ -1108,6 +1108,9 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
                qsort(base, nmemb, size, compar);
 }
 
+#define STABLE_QSORT(base, n, compar) \
+       git_stable_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/stable-qsort.c
similarity index 89%
rename from compat/qsort.c
rename to stable-qsort.c
index 7d071afb70530ede222ed9cdb4645baf4277fb79..6cbaf39f7b6ccbb265d77dd17d8c3146d629ca90 100644 (file)
--- a/compat/qsort.c
+++ b/stable-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
@@ -44,8 +44,8 @@ static void msort_with_tmp(void *b, size_t n, size_t s,
        memcpy(b, t, (n - n2) * s);
 }
 
-void git_qsort(void *b, size_t n, size_t s,
-              int (*cmp)(const void *, const void *))
+void git_stable_qsort(void *b, size_t n, size_t s,
+                     int (*cmp)(const void *, const void *))
 {
        const size_t size = st_mult(n, s);
        char buf[1024];