From 97fff6101220b66bc293239ab2cf29fc3624072b Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Mon, 30 Sep 2019 10:21:54 -0700 Subject: 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 Signed-off-by: Junio C Hamano --- compat/mingw.c | 11 +++-------- compat/qsort.c | 62 ---------------------------------------------------------- 2 files changed, 3 insertions(+), 70 deletions(-) delete mode 100644 compat/qsort.c (limited to 'compat') diff --git a/compat/mingw.c b/compat/mingw.c index 738f0a826a..50af33b2b3 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. @@ -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/compat/qsort.c b/compat/qsort.c deleted file mode 100644 index 7d071afb70..0000000000 --- a/compat/qsort.c +++ /dev/null @@ -1,62 +0,0 @@ -#include "../git-compat-util.h" - -/* - * A merge sort implementation, simplified from the qsort implementation - * by Mike Haertel, which is a part of the GNU C Library. - */ - -static void msort_with_tmp(void *b, size_t n, size_t s, - int (*cmp)(const void *, const void *), - char *t) -{ - char *tmp; - char *b1, *b2; - size_t n1, n2; - - if (n <= 1) - return; - - n1 = n / 2; - n2 = n - n1; - b1 = b; - b2 = (char *)b + (n1 * s); - - msort_with_tmp(b1, n1, s, cmp, t); - msort_with_tmp(b2, n2, s, cmp, t); - - tmp = t; - - while (n1 > 0 && n2 > 0) { - if (cmp(b1, b2) <= 0) { - memcpy(tmp, b1, s); - tmp += s; - b1 += s; - --n1; - } else { - memcpy(tmp, b2, s); - tmp += s; - b2 += s; - --n2; - } - } - if (n1 > 0) - memcpy(tmp, b1, n1 * s); - memcpy(b, t, (n - n2) * s); -} - -void git_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]; - - if (size < sizeof(buf)) { - /* The temporary array fits on the small on-stack buffer. */ - msort_with_tmp(b, n, s, cmp, buf); - } else { - /* It's somewhat large, so malloc it. */ - char *tmp = xmalloc(size); - msort_with_tmp(b, n, s, cmp, tmp); - free(tmp); - } -} -- cgit v1.2.3