thodg/libgit2/tests/core/qsort.c
Tag
-
Show log
Commit
-
Hash : 8cbef12d
Author :
Date : 2019-08-08T11:52:54
util: do not perform allocations in insertsort Our hand-rolled fallback sorting function `git__insertsort_r` does an in-place sort of the given array. As elements may not necessarily be pointers, it needs a way of swapping two values of arbitrary size, which is currently implemented by allocating a temporary buffer of the element's size. This is problematic, though, as the emulated `qsort` interface doesn't provide any return values and thus cannot signal an error if allocation of that temporary buffer has failed. Convert the function to swap via a temporary buffer allocated on the stack. Like this, it can `memcpy` contents of both elements in small batches without requiring a heap allocation. The buffer size has been chosen such that in most cases, a single iteration of copying will suffice. Most importantly, it can fully contain `git_oid` structures and pointers. Add a bunch of tests for the `git__qsort_r` interface to verify nothing breaks. Furthermore, this removes the declaration of `git__insertsort_r` and makes it static as it is not used anywhere else.
-
tests/core/qsort.c
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
#include "clar_libgit2.h" #define assert_sorted(a, cmp) \ _assert_sorted(a, ARRAY_SIZE(a), sizeof(*a), cmp) struct big_entries { char c[311]; }; static void _assert_sorted(void *els, size_t n, size_t elsize, git__sort_r_cmp cmp) { int8_t *p = els; git__qsort_r(p, n, elsize, cmp, NULL); while (n-- > 1) { cl_assert(cmp(p, p + elsize, NULL) <= 0); p += elsize; } } static int cmp_big(const void *_a, const void *_b, void *payload) { const struct big_entries *a = (const struct big_entries *)_a, *b = (const struct big_entries *)_b; GIT_UNUSED(payload); return (a->c[0] < b->c[0]) ? -1 : (a->c[0] > b->c[0]) ? +1 : 0; } static int cmp_int(const void *_a, const void *_b, void *payload) { int a = *(const int *)_a, b = *(const int *)_b; GIT_UNUSED(payload); return (a < b) ? -1 : (a > b) ? +1 : 0; } static int cmp_str(const void *_a, const void *_b, void *payload) { GIT_UNUSED(payload); return strcmp((const char *) _a, (const char *) _b); } void test_core_qsort__array_with_single_entry(void) { int a[] = { 10 }; assert_sorted(a, cmp_int); } void test_core_qsort__array_with_equal_entries(void) { int a[] = { 4, 4, 4, 4 }; assert_sorted(a, cmp_int); } void test_core_qsort__sorted_array(void) { int a[] = { 1, 10 }; assert_sorted(a, cmp_int); } void test_core_qsort__unsorted_array(void) { int a[] = { 123, 9, 412938, 10, 234, 89 }; assert_sorted(a, cmp_int); } void test_core_qsort__sorting_strings(void) { char *a[] = { "foo", "bar", "baz" }; assert_sorted(a, cmp_str); } void test_core_qsort__sorting_big_entries(void) { struct big_entries a[5]; memset(&a, 0, sizeof(a)); memset(a[0].c, 'w', sizeof(a[0].c) - 1); memset(a[1].c, 'c', sizeof(a[1].c) - 1); memset(a[2].c, 'w', sizeof(a[2].c) - 1); memset(a[3].c, 'h', sizeof(a[3].c) - 1); memset(a[4].c, 'a', sizeof(a[4].c) - 1); assert_sorted(a, cmp_big); cl_assert_equal_i(strspn(a[0].c, "a"), sizeof(a[0].c) - 1); cl_assert_equal_i(strspn(a[1].c, "c"), sizeof(a[1].c) - 1); cl_assert_equal_i(strspn(a[2].c, "h"), sizeof(a[2].c) - 1); cl_assert_equal_i(strspn(a[3].c, "w"), sizeof(a[3].c) - 1); cl_assert_equal_i(strspn(a[4].c, "w"), sizeof(a[4].c) - 1); }