From f4609b896fac842433bd495c166d5987852a6a73 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Sat, 21 Nov 2020 19:20:35 +0100 Subject: merge(3p/git): Merge git subtree at v2.29.2 This also bumps the stable nixpkgs to 20.09 as of 2020-11-21, because there is some breakage in the git build related to the netrc credentials helper which someone has taken care of in nixpkgs. The stable channel is not used for anything other than git, so this should be fine. Change-Id: I3575a19dab09e1e9556cf8231d717de9890484fb --- third_party/git/stable-qsort.c | 62 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) create mode 100644 third_party/git/stable-qsort.c (limited to 'third_party/git/stable-qsort.c') diff --git a/third_party/git/stable-qsort.c b/third_party/git/stable-qsort.c new file mode 100644 index 0000000000..6cbaf39f7b --- /dev/null +++ b/third_party/git/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); + } +} -- cgit 1.4.1