Index: lib/libc/tests/stdlib/Makefile =================================================================== --- lib/libc/tests/stdlib/Makefile +++ lib/libc/tests/stdlib/Makefile @@ -47,6 +47,7 @@ PROGS+= h_getopt h_getopt_long CFLAGS+= -I${.CURDIR} +CFLAGS+= -I${.CURDIR:H:H} CXXFLAGS.cxa_thread_atexit_test+= -std=c++11 CXXFLAGS.cxa_thread_atexit_nothr_test+= -std=c++11 Index: lib/libc/tests/stdlib/mergesort_test.c =================================================================== --- lib/libc/tests/stdlib/mergesort_test.c +++ lib/libc/tests/stdlib/mergesort_test.c @@ -29,43 +29,587 @@ */ #include -__FBSDID("$FreeBSD$"); +__FBSDID("$FreeBSD: head/lib/libc/tests/stdlib/mergesort_test.c 290538 2015-11-08 07:03:17Z ngie $"); #include +#include +#include #include #include #include "test-sort.h" -ATF_TC_WITHOUT_HEAD(mergesort_test); -ATF_TC_BODY(mergesort_test, tc) +#define ELT_MAX 16 +/* + * Number of keys in stability test. + * Chosen to be low enough that every element would probabilistically need + * to be properly ordered for stability, without being trivially small. + */ +#define KEYS 50 +/* + * Definitions for sizeable_mergesort_test + * Test from 2^BASE_EXP to 2^MAX_EXP elements of type SORT_TYPE + */ +#define BASE_EXP 10 +#define MAX_EXP 18 +#define SORT_TYPE int + +// Number of chars in the odd elt subarray +#define NCHARS 5 + +// Canary value to verify buffer is intact +#define CANARY 0XDEADBEEF + +#define check_array_eq(it, len, expected, actual) do { \ + for (it = 0; it < len; it++) \ + ATF_CHECK_MSG( \ + actual[it] == expected[it], \ + "item at index %d didn't match: %d != %d", \ + it, actual[it], expected[it]); \ +} while(0) + +/* + * Structures to allow for the creation of predefined variable sized arrays. + * The len field is necesary to determine how many elements are being used + * in the elts array + */ +struct int_array { + int len; + int elts[ELT_MAX]; +}; + +struct char_array { + int len; + char elts[ELT_MAX]; +}; + +/* + * Sorting arrays of small size and simple element combinations to ensure + * basic competency. + */ +ATF_TC_WITHOUT_HEAD(trivial_mergesort_test); +ATF_TC_BODY(trivial_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {1, {0}}, {2, {0, 0}}, {3, {0, 0, 0}}, {2, {0, 1}}, + {2, {1, 0}}, {3, {0, 1, 2}}, {3, {0, 2, 1}}, {3, {1, 0, 2}}, + {3, {1, 2, 0}}, {3, {2, 0, 1}}, {3, {2, 1, 0}}, {3, {0, 1, 1}}, + {3, {1, 0, 1}}, {3, {1, 1, 0}}, {3, {0, -1, -1}}, {3, {0, -1, 0}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + int i, j, len; + size_t size; + + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + size = len * sizeof(testvector[0]); + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, size); + memcpy(sresvector, testarrays[i].elts, size); + + /* Sort using mergesort(3) */ + mergesort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + insertionsort(sresvector, len, sizeof(sresvector[0]), sorthelp); + + check_array_eq(j, len, testvector, sresvector); + } +} + +/* + * Sorting arrays in which the elements are either ordered, partially ordered, + * or reverse ordered. + */ +ATF_TC_WITHOUT_HEAD(ordering_mergesort_test); +ATF_TC_BODY(ordering_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {3, {-1, -2, -3}}, + {3, {-3, -2, -1}}, + {11, {1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1}}, + {10, {5, 5, 4, 4, 3, 3, 2, 2, 1, 1}}, + {10, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}, + {10, {1, 2, 3, 4, 5, 6, -7, -8, -9, -10}}, + {10, {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + int i, j, len; + size_t size; + + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + size = len * sizeof(testvector[0]); + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, size); + memcpy(sresvector, testarrays[i].elts, size); + + /* Sort using mergesort(3) */ + mergesort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + insertionsort(sresvector, len, sizeof(sresvector[0]), sorthelp); + + check_array_eq(j, len, testvector, sresvector); + } +} + +/* + * Sorting arrays with a variety of challenges: i.e. max integer values, + * multiple identical values, etc. + */ +ATF_TC_WITHOUT_HEAD(misc_mergesort_test); +ATF_TC_BODY(misc_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {10, {42, 9, 17, 123, 602, -3, 123, 969, -11, INT_MAX}}, + {10, {-11, -3, 9, 17, 42, 54, 54, 602, 969, INT_MIN}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + int i, j, len; + size_t size; + + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + size = len * sizeof(testvector[0]); + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, size); + memcpy(sresvector, testarrays[i].elts, size); + + /* Sort using mergesort(3) */ + mergesort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + insertionsort(sresvector, len, sizeof(sresvector[0]), sorthelp); + + check_array_eq(j, len, testvector, sresvector); + } +} + +/* + * Sort an array of random integers. + */ +ATF_TC_WITHOUT_HEAD(rand_mergesort_test); +ATF_TC_BODY(rand_mergesort_test, tc) { int sresvector[IVEC_LEN]; int testvector[IVEC_LEN]; int i, j; + size_t size; for (j = 2; j < IVEC_LEN; j++) { + size = j * sizeof(testvector[0]); /* Populate test vectors */ - for (i = 0; i < j; i++) - testvector[i] = sresvector[i] = initvector[i]; + memcpy(testvector, initvector, size); + memcpy(sresvector, initvector, size); /* Sort using mergesort(3) */ mergesort(testvector, j, sizeof(testvector[0]), sorthelp); /* Sort using reference slow sorting routine */ - ssort(sresvector, j); + insertionsort(sresvector, j, sizeof(sresvector[0]), sorthelp); + + /* Compare results */ + check_array_eq(i, j, testvector, sresvector); + } +} + +/* + * Sort an array of chars + */ +ATF_TC_WITHOUT_HEAD(small_elt_mergesort_test); +ATF_TC_BODY(small_elt_mergesort_test, tc) +{ + static const struct char_array testarrays[] = { + {1, {0}}, + {2, {0, 0}}, + {3, {0, 0, 0}}, + {2, {0, 1}}, + {2, {1, 0}}, + {3, {0, 1, 2}}, + {3, {0, 2, 1}}, + {3, {1, 0, 2}}, + {3, {1, 2, 0}}, + {3, {2, 0, 1}}, + {3, {2, 1, 0}}, + {3, {0, 1, 1}}, + {3, {1, 0, 1}}, + {3, {1, 1, 0}}, + {3, {0, -1, -1}}, + {3, {0, -1, 0}}, + {3, {-1, -2, -3}}, + {3, {-3, -2, -1}}, + {11, {1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1}}, + {10, {5, 5, 4, 4, 3, 3, 2, 2, 1, 1}}, + {10, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}, + {10, {1, 2, 3, 4, 5, 6, -7, -8, -9, -10}}, + {10, {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}}, + {10, {42, 9, 17, 123, 62, -3, 123, 99, -11, CHAR_MAX}}, + {10, {-11, -3, 9, 17, 42, 54, 54, -62, 9, CHAR_MIN}}}; + + char sresvector[ELT_MAX]; + char testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + int i, j, len, ret; + size_t size; + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + size = len * sizeof(testvector[0]); + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, size); + memcpy(sresvector, testarrays[i].elts, size); + + atf_tc_expect_fail( + "Mergesort implementation does not support arguments less " + "than sizeof(void *)/2"); + /* Sort using mergesort(3) */ + ret = mergesort(testvector, len, sizeof(testvector[0]), + csorthelp); + ATF_CHECK(ret == 0); + /* Sort using reference slow sorting routine */ + insertionsort(sresvector, len, sizeof(sresvector[0]), + csorthelp); + + /* Compare results */ + check_array_eq(j, len, testvector, sresvector); + } +} + +/* + * Sort an array of char[5] arrays. Tests for possible alignment issues. + */ +ATF_TC_WITHOUT_HEAD(oddelt_mergesort_test); +ATF_TC_BODY(oddelt_mergesort_test, tc) +{ + struct odd_array { + int len; + char elts[ELT_MAX][NCHARS]; + }; + + static const struct odd_array testarrays[] = { + {2, {{0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}}}, + {3, {{1, 2, 3, 4, 5}, {0, 1, 2, 3, 4}, {2, 3, 1, 0, 0}}}, + {3, {{-1, 2, -3, 4, 5}, {0, 1, 2, -3, 4}, {2, 3, -1, 0, 0}}}, + {3, {{-1, 7, 4, 0, 0}, {0, 1, 2, 0, 0}, {4, 3, 5, 0, 0}}}, + {3, {{1, 7, 4, 0, 0}, {0, 1, -2, 0, 0}, {4, -3, 5, 0, 0}}}, + {10, + {{-1, 0, 0, 0, 0}, + {-2, 0, 0, 0, 0}, + {-3, 0, 0, 0, 0}, + {-4, 0, 0, 0, 0}, + {-5, 0, 0, 0, 0}, + {-6, 0, 0, 0, 0}, + {-7, 0, 0, 0, 0}, + {-8, 0, 0, 0, 0}, + {-9, 0, 0, 0, 0}, + {-10, 0, 0, 0, 0}}}}; + + char sresvector[ELT_MAX][NCHARS]; + char testvector[ELT_MAX][NCHARS]; + int num_tests = nitems(testarrays); + int i, j, k, len; + + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + /* Populate test vectors */ + for (j = 0; j < len; j++) { + for (k = 0; k < NCHARS; k++) + testvector[j][k] = sresvector[j][k] = + testarrays[i].elts[j][k]; + } + /* Sort using mergesort(3) */ + mergesort(testvector, len, sizeof(testvector[0]), oddsorthelp); + /* Sort using reference slow sorting routine */ + insertionsort(sresvector, len, sizeof(sresvector[0]), + oddsorthelp); + for (j = 0; j < len; j++) + check_array_eq(k, NCHARS, testvector[j], sresvector[j]); + } +} + +/* + * Sort an array of int*'s + */ +ATF_TC_WITHOUT_HEAD(pointer_mergesort_test); +ATF_TC_BODY(pointer_mergesort_test, tc) +{ + struct ptr_array { + int len; + int *elts[ELT_MAX]; + }; + + static const struct ptr_array testarrays[] = { + {3, {NULL, (int *)0x200, (int *)0x100}}, + {3, {(int *)0xFFFF, (int *)0xFFFE, (int *)0xFFFD}}, + {3, {NULL, NULL, NULL}}, + {6, + {(int *)0xFFFFFFFF, (int *)0x100000000, NULL, (int *)1234, + (int *)0x1234, (int *)0xFFFFFFFF}}}; + + int *sresvector[ELT_MAX]; + int *testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + int i, j, len; + for (i = 0; i < num_tests; i++) { + len = testarrays[i].len; + /* Populate test vectors */ + for (j = 0; j < len; j++) + testvector[j] = sresvector[j] = testarrays[i].elts[j]; + /* Sort using mergesort(3) */ + mergesort(testvector, len, sizeof(testvector[0]), ptrsorthelp); + /* Reference sort */ + insertionsort(sresvector, len, sizeof(testvector[0]), + ptrsorthelp); + + for (j = 0; j < len; j++) + ATF_CHECK_MSG(testvector[j] == sresvector[j], + "item at index %d didn't match: %p != %p\n", + j, testvector[j], sresvector[j]); + } +} + +/* + * Sort an array of random int*'s + */ +ATF_TC_WITHOUT_HEAD(rand_pointer_mergesort_test); +ATF_TC_BODY(rand_pointer_mergesort_test, tc) +{ + int *rand_sresvector[IVEC_LEN]; + int *rand_testvector[IVEC_LEN]; + int i, j; + + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) + rand_testvector[i] = rand_sresvector[i] = + &(initvector[arc4random() % IVEC_LEN]); + + /* Sort using mergesort(3) */ + mergesort(rand_testvector, j, sizeof(rand_testvector[0]), + ptrsorthelp); + /* Reference sort */ + insertionsort(rand_sresvector, j, sizeof(rand_sresvector[0]), + ptrsorthelp); /* Compare results */ for (i = 0; i < j; i++) - ATF_CHECK_MSG(testvector[i] == sresvector[i], - "item at index %d didn't match: %d != %d", - i, testvector[i], sresvector[i]); + ATF_CHECK_MSG(rand_testvector[i] == rand_sresvector[i], + "item at index %d didn't match: %p != %p\n", + i, rand_testvector[i], rand_sresvector[i]); } } -ATF_TP_ADD_TCS(tp) +/* + * Sort an array of nontrivially large structs + */ +ATF_TC_WITHOUT_HEAD(bigstruct_mergesort_test); +ATF_TC_BODY(bigstruct_mergesort_test, tc) +{ + struct big sresvector[IVEC_LEN]; + struct big testvector[IVEC_LEN]; + int i, j; + size_t size = SPACE_LEN * sizeof(int); + + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) { + testvector[i].value = sresvector[i].value = + initvector[i]; + memset(testvector[i].spacetaker, CANARY, size); + memset(sresvector[i].spacetaker, CANARY, size); + } + + /* Sort using mergesort(3) */ + mergesort(testvector, j, sizeof(testvector[0]), bigsorthelp); + /* Reference sort */ + insertionsort(sresvector, j, sizeof(sresvector[0]), + bigsorthelp); + + /* Compare results */ + for (i = 0; i < j; i++) { + ATF_CHECK_MSG(testvector[i].value == + sresvector[i].value, + "item at index %d didn't match: %d != %d\n", + i, testvector[i].value, sresvector[i].value); + ATF_CHECK_MSG(memcmp(testvector[i].spacetaker, + sresvector[i].spacetaker, size) == 0, + "Spacetaker corrupted at index %d\n", i); + } + } +} + +/* + * Sort an array of structs with identical values but different keys in order + * to check for stability. The sorted elements with the same value should + * be in the same order by key. + */ +ATF_TC_WITHOUT_HEAD(stability_mergesort_test); +ATF_TC_BODY(stability_mergesort_test, tc) +{ + struct stable sresvector[IVEC_LEN]; + struct stable testvector[IVEC_LEN]; + int i, j; + int keys[KEYS] = {0}; + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) { + int value = arc4random() % KEYS; + testvector[i].value = sresvector[i].value = value; + testvector[i].key = sresvector[i].key = keys[value]; + keys[value]++; + } + + /* Sort using mergesort(3) */ + mergesort(testvector, j, sizeof(testvector[0]), stablesorthelp); + /* Reference sort */ + insertionsort(sresvector, j, sizeof(sresvector[0]), + stablesorthelp); + + /* Compare results */ + for (i = 0; i < j; i++) { + ATF_CHECK_MSG(testvector[i].value == + sresvector[i].value && + testvector[i].key == sresvector[i].key, + "item at index %d didn't match: value %d " + "!= %d or key %d != %d\n", + i, testvector[i].value, sresvector[i].value, + testvector[i].key, sresvector[i].key); + } + } +} + +static void +rand_test(int elts) +{ + int i; + size_t size = sizeof(SORT_TYPE) * elts; + SORT_TYPE *testvector = malloc(size); + SORT_TYPE *sresvector = malloc(size); + + arc4random_buf(testvector, size); + memcpy(sresvector, testvector, size); + + /* Sort using mergesort(3) */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + insertionsort(sresvector, elts, sizeof(SORT_TYPE), sorthelp); + + check_array_eq(i, elts, testvector, sresvector); + + free(testvector); + free(sresvector); +} + +static void +sort_test(int elts) +{ + int i; + size_t size = sizeof(SORT_TYPE) * elts; + SORT_TYPE *testvector = malloc(size); + SORT_TYPE *sresvector = malloc(size); + + for (i = 0; i < elts; i++) { + testvector[i] = sresvector[i] = i; + } + + /* Sort using mergesort(3) */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + insertionsort(sresvector, elts, sizeof(SORT_TYPE), sorthelp); + + check_array_eq(i, elts, testvector, sresvector); + + free(testvector); + free(sresvector); +} + +static void +partial_test(int elts) +{ + int i; + size_t size = sizeof(SORT_TYPE) * elts; + SORT_TYPE *testvector = malloc(size); + SORT_TYPE *sresvector = malloc(size); + + for (i = 0; i < elts; i++) { + if (i <= elts / 2) + testvector[i] = sresvector[i] = i; + else + testvector[i] = sresvector[i] = arc4random(); + } + + /* Sort using mergesort(3) */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + insertionsort(sresvector, elts, sizeof(SORT_TYPE), sorthelp); + + check_array_eq(i, elts, testvector, sresvector); + + free(testvector); + free(sresvector); +} + +static void +reverse_test(int elts) +{ + int i; + size_t size = sizeof(SORT_TYPE) * elts; + SORT_TYPE *testvector = malloc(size); + SORT_TYPE *sresvector = malloc(size); + + for (i = 0; i < elts; i++) { + testvector[i] = sresvector[i] = elts - i; + } + + /* Sort using mergesort(3) */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + insertionsort(sresvector, elts, sizeof(SORT_TYPE), sorthelp); + + check_array_eq(i, elts, testvector, sresvector); + + free(testvector); + free(sresvector); +} + +/* + * Sort an array of integers from 2^BASE_EXP to 2^MAX_EXP elements + */ +ATF_TC_WITHOUT_HEAD(sizeable_mergesort_test); +ATF_TC_BODY(sizeable_mergesort_test, tc) { + int max = pow(2, MAX_EXP); + int base = pow(2, BASE_EXP); + for (int elts = base; elts < max; elts *= 2) { + rand_test(elts); + sort_test(elts); + partial_test(elts); + reverse_test(elts); + } +} - ATF_TP_ADD_TC(tp, mergesort_test); + +/* + * Test cases to ensure correctness of stdlib mergesort function + */ +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, trivial_mergesort_test); + ATF_TP_ADD_TC(tp, ordering_mergesort_test); + ATF_TP_ADD_TC(tp, misc_mergesort_test); + ATF_TP_ADD_TC(tp, rand_mergesort_test); + ATF_TP_ADD_TC(tp, small_elt_mergesort_test); + ATF_TP_ADD_TC(tp, oddelt_mergesort_test); + ATF_TP_ADD_TC(tp, pointer_mergesort_test); + ATF_TP_ADD_TC(tp, rand_pointer_mergesort_test); + ATF_TP_ADD_TC(tp, bigstruct_mergesort_test); + ATF_TP_ADD_TC(tp, stability_mergesort_test); + ATF_TP_ADD_TC(tp, sizeable_mergesort_test); return (atf_no_error()); } Index: lib/libc/tests/stdlib/test-sort.h =================================================================== --- lib/libc/tests/stdlib/test-sort.h +++ lib/libc/tests/stdlib/test-sort.h @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $FreeBSD$ + * $FreeBSD: head/lib/libc/tests/stdlib/test-sort.h 290538 2015-11-08 07:03:17Z ngie $ */ #ifndef _TEST_SORT_H @@ -33,6 +33,12 @@ #include +// Number of ints in the bigstruct array +#define SPACE_LEN 100 + +/* + * Integer comparison function for stdlib sorting algorithms + */ static int sorthelp(const void *a, const void *b) { @@ -48,21 +54,142 @@ return (0); } -/* Reference sorting routine (slooow!) */ +/* + * Char comparison function for stdlib sorting algorithms + */ +static int +csorthelp(const void *a, const void *b) +{ + const char *oa, *ob; + + oa = a; + ob = b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (*oa < *ob) + return (-1); + if (*oa > *ob) + return (1); + return (0); +} + +/* + * Char[5] comparison function for stdlib sorting algorithms + * Simply sorts the arrays by the first element of each array + */ +static int +oddsorthelp(const void *a, const void *b) +{ + const char(*oa)[3], (*ob)[3]; + + oa = a; + ob = b; + /* Don't use "return *oa[0] - *ob[0]" since it's easy to cause overflow! */ + if (*oa[0] > *ob[0]) + return (1); + if (*oa[0] < *ob[0]) + return (-1); + return (0); +} + +/* + * Int* comparison function for stdlib sorting algorithms + */ +static int +ptrsorthelp(const void *a, const void *b) +{ + const int **oa, **ob; + oa = (const int **)a; + ob = (const int **)b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (*oa > *ob) + return (1); + if (*oa < *ob) + return (-1); + return (0); +} + +/* + * Struct used to test stdlib sorting algorithms ability to sort nontrivially + * large elements + */ +struct big { + int value; + int spacetaker[SPACE_LEN]; +}; + +/* + * Struct big comparison function for stdlib sorting algorithms + */ +static int +bigsorthelp(const void *a, const void *b) +{ + const struct big *oa, *ob; + oa = a; + ob = b; + /* + * Don't use "return oa->value - *ob->value" + * since it's easy to cause overflow! + */ + if (oa->value > ob->value) + return (1); + if (oa->value < ob->value) + return (-1); + return (0); +} + +/* + * Struct used to test stdlib sorting algorithms ability to sort data with + * stability + */ +struct stable { + int key; + int value; +}; + +/* + * Struct stable comparison function for stdlib sorting algorithms + */ +static int +stablesorthelp(const void *a, const void *b) +{ + const struct stable *oa, *ob; + oa = a; + ob = b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (oa->value > ob->value) + return (1); + if (oa->value < ob->value) + return (-1); + return (0); +} + +#define swap(a, b) \ + { \ + s = b; \ + i = size; \ + do { \ + tmp = *a; \ + *a++ = *s; \ + *s++ = tmp; \ + } while (--i); \ + a -= size; \ + } + +/* Reference stable sorting routine for integers (slooow!) */ static void -ssort(int v[], int nmemb) +insertionsort(void *arr, size_t n, size_t size, + int (*compar)(const void *, const void *)) { - int i, j, k; + u_char *a = arr; + u_char *ai, *s, *t, *u, tmp; + int i; - for (i = 0; i < nmemb; i++) { - for (j = i + 1; j < nmemb; j++) { - if (v[j] < v[i]) { - k = v[i]; - v[i] = v[j]; - v[j] = k; - } + for (ai = a + size; --n >= 1; ai += size) + for (t = ai; t > a; t -= size) { + u = t - size; + if (compar(u, t) <= 0) break; + swap(u, t); } - } } /* Some random data */