diff options
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | compat/qsort_s.c | 69 | ||||
| -rw-r--r-- | git-compat-util.h | 11 | ||||
| -rw-r--r-- | ref-filter.c | 6 | ||||
| -rw-r--r-- | string-list.c | 13 | ||||
| -rw-r--r-- | t/helper/test-string-list.c | 25 | ||||
| -rwxr-xr-x | t/perf/p0071-sort.sh | 26 |
7 files changed, 146 insertions, 12 deletions
@@ -279,6 +279,9 @@ all:: # 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(). # +# Define HAVE_ISO_QSORT_S if your platform provides a qsort_s() that's +# compatible with the one described in C11 Annex K. +# # Define UNRELIABLE_FSTAT if your system's fstat does not return the same # information on a not yet closed file that lstat would return for the same # file after it was closed. @@ -1418,6 +1421,11 @@ ifdef INTERNAL_QSORT COMPAT_CFLAGS += -DINTERNAL_QSORT COMPAT_OBJS += compat/qsort.o endif +ifdef HAVE_ISO_QSORT_S + COMPAT_CFLAGS += -DHAVE_ISO_QSORT_S +else + COMPAT_OBJS += compat/qsort_s.o +endif ifdef RUNTIME_PREFIX COMPAT_CFLAGS += -DRUNTIME_PREFIX endif diff --git a/compat/qsort_s.c b/compat/qsort_s.c new file mode 100644 index 000000000..52d1f0a73 --- /dev/null +++ b/compat/qsort_s.c @@ -0,0 +1,69 @@ +#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. + * Added context pointer, safety checks and return value. + */ + +static void msort_with_tmp(void *b, size_t n, size_t s, + int (*cmp)(const void *, const void *, void *), + char *t, void *ctx) +{ + 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, ctx); + msort_with_tmp(b2, n2, s, cmp, t, ctx); + + tmp = t; + + while (n1 > 0 && n2 > 0) { + if (cmp(b1, b2, ctx) <= 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); +} + +int git_qsort_s(void *b, size_t n, size_t s, + int (*cmp)(const void *, const void *, void *), void *ctx) +{ + const size_t size = st_mult(n, s); + char buf[1024]; + + if (!n) + return 0; + if (!b || !cmp) + return -1; + + if (size < sizeof(buf)) { + /* The temporary array fits on the small on-stack buffer. */ + msort_with_tmp(b, n, s, cmp, buf, ctx); + } else { + /* It's somewhat large, so malloc it. */ + char *tmp = xmalloc(size); + msort_with_tmp(b, n, s, cmp, tmp, ctx); + free(tmp); + } + return 0; +} diff --git a/git-compat-util.h b/git-compat-util.h index 87237b092..f46d40e4a 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -988,6 +988,17 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size, qsort(base, nmemb, size, 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); +#define qsort_s git_qsort_s +#endif + +#define QSORT_S(base, n, compar, ctx) do { \ + if (qsort_s((base), (n), sizeof(*(base)), compar, ctx)) \ + die("BUG: qsort_s() failed"); \ +} while (0) + #ifndef REG_STARTEND #error "Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd" #endif diff --git a/ref-filter.c b/ref-filter.c index 5f4b08792..3820b21cc 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -1594,8 +1594,7 @@ static int cmp_ref_sorting(struct ref_sorting *s, struct ref_array_item *a, stru return (s->reverse) ? -cmp : cmp; } -static struct ref_sorting *ref_sorting; -static int compare_refs(const void *a_, const void *b_) +static int compare_refs(const void *a_, const void *b_, void *ref_sorting) { struct ref_array_item *a = *((struct ref_array_item **)a_); struct ref_array_item *b = *((struct ref_array_item **)b_); @@ -1611,8 +1610,7 @@ static int compare_refs(const void *a_, const void *b_) void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array) { - ref_sorting = sorting; - QSORT(array->items, array->nr, compare_refs); + QSORT_S(array->items, array->nr, compare_refs, sorting); } static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state) diff --git a/string-list.c b/string-list.c index 8c83cac18..45016ad86 100644 --- a/string-list.c +++ b/string-list.c @@ -211,21 +211,18 @@ struct string_list_item *string_list_append(struct string_list *list, list->strdup_strings ? xstrdup(string) : (char *)string); } -/* Yuck */ -static compare_strings_fn compare_for_qsort; - -/* Only call this from inside string_list_sort! */ -static int cmp_items(const void *a, const void *b) +static int cmp_items(const void *a, const void *b, void *ctx) { + compare_strings_fn cmp = ctx; const struct string_list_item *one = a; const struct string_list_item *two = b; - return compare_for_qsort(one->string, two->string); + return cmp(one->string, two->string); } void string_list_sort(struct string_list *list) { - compare_for_qsort = list->cmp ? list->cmp : strcmp; - QSORT(list->items, list->nr, cmp_items); + QSORT_S(list->items, list->nr, cmp_items, + list->cmp ? list->cmp : strcmp); } struct string_list_item *unsorted_string_list_lookup(struct string_list *list, diff --git a/t/helper/test-string-list.c b/t/helper/test-string-list.c index 4a68967bd..c502fa16d 100644 --- a/t/helper/test-string-list.c +++ b/t/helper/test-string-list.c @@ -97,6 +97,31 @@ int cmd_main(int argc, const char **argv) return 0; } + if (argc == 2 && !strcmp(argv[1], "sort")) { + struct string_list list = STRING_LIST_INIT_NODUP; + struct strbuf sb = STRBUF_INIT; + struct string_list_item *item; + + strbuf_read(&sb, 0, 0); + + /* + * Split by newline, but don't create a string_list item + * for the empty string after the last separator. + */ + if (sb.buf[sb.len - 1] == '\n') + strbuf_setlen(&sb, sb.len - 1); + string_list_split_in_place(&list, sb.buf, '\n', -1); + + string_list_sort(&list); + + for_each_string_list_item(item, &list) + puts(item->string); + + string_list_clear(&list, 0); + strbuf_release(&sb); + return 0; + } + fprintf(stderr, "%s: unknown function name: %s\n", argv[0], argv[1] ? argv[1] : "(there was none)"); return 1; diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh new file mode 100755 index 000000000..7c9a35a64 --- /dev/null +++ b/t/perf/p0071-sort.sh @@ -0,0 +1,26 @@ +#!/bin/sh + +test_description='Basic sort performance tests' +. ./perf-lib.sh + +test_perf_default_repo + +test_expect_success 'setup' ' + git ls-files --stage "*.[ch]" "*.sh" | + cut -f2 -d" " | + git cat-file --batch >unsorted +' + +test_perf 'sort(1)' ' + sort <unsorted >expect +' + +test_perf 'string_list_sort()' ' + test-string-list sort <unsorted >actual +' + +test_expect_success 'string_list_sort() sorts like sort(1)' ' + test_cmp_bin expect actual +' + +test_done |