diff options
author | Johannes Schindelin <johannes.schindelin@gmx.de> | 2019-09-30 20:21:54 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2019-10-02 08:44:51 +0300 |
commit | 97fff6101220b66bc293239ab2cf29fc3624072b (patch) | |
tree | 8c0c9a1415c4160b8d0f798d79e539d984d7c501 /stable-qsort.c | |
parent | 5fa0f5238b0cd46cfe7f6fa76c3f526ea98148d9 (diff) |
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>
Diffstat (limited to 'stable-qsort.c')
-rw-r--r-- | stable-qsort.c | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/stable-qsort.c b/stable-qsort.c new file mode 100644 index 0000000000..6cbaf39f7b --- /dev/null +++ b/stable-qsort.c @@ -0,0 +1,62 @@ +#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_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]; + + 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); + } +} |