diff options
author | Junio C Hamano <gitster@pobox.com> | 2008-02-17 05:11:10 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2008-02-17 05:11:47 +0300 |
commit | f8732c5596eb58d0daafdd61355e59831a95ae2e (patch) | |
tree | e2ba2efd1d5670d8920feee282581bc0cd989851 | |
parent | 2ac4b4b2228f3ef996db7b07aea74c4b1a796f38 (diff) | |
parent | 43fe901b71f81cdff142048dfc27e492c445d225 (diff) |
Merge branch 'bd/qsort'
* bd/qsort:
compat: Add simplified merge sort implementation from glibc
-rw-r--r-- | Makefile | 8 | ||||
-rw-r--r-- | compat/qsort.c | 62 | ||||
-rw-r--r-- | git-compat-util.h | 6 |
3 files changed, 76 insertions, 0 deletions
@@ -137,6 +137,10 @@ all:: # Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit # parallel delta searching when packing objects. # +# Define INTERNAL_QSORT to use Git's implementation of qsort(), which +# is a simplified version of the merge sort used in glibc. This is +# recommended if Git triggers O(n^2) behavior in your platform's qsort(). +# GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE @$(SHELL_PATH) ./GIT-VERSION-GEN @@ -722,6 +726,10 @@ ifdef NO_MEMMEM COMPAT_CFLAGS += -DNO_MEMMEM COMPAT_OBJS += compat/memmem.o endif +ifdef INTERNAL_QSORT + COMPAT_CFLAGS += -DINTERNAL_QSORT + COMPAT_OBJS += compat/qsort.o +endif ifdef THREADED_DELTA_SEARCH BASIC_CFLAGS += -DTHREADED_DELTA_SEARCH diff --git a/compat/qsort.c b/compat/qsort.c new file mode 100644 index 0000000000..d93dce2cf8 --- /dev/null +++ b/compat/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_qsort(void *b, size_t n, size_t s, + int (*cmp)(const void *, const void *)) +{ + const size_t size = 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 = malloc(size); + msort_with_tmp(b, n, s, cmp, tmp); + free(tmp); + } +} diff --git a/git-compat-util.h b/git-compat-util.h index 4df90cb34e..05146047e0 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -426,4 +426,10 @@ 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 *)); +#define qsort git_qsort +#endif + #endif |