Page MenuHomeFreeBSD
Files F172541639

D12677.id34116.diff
No OneTemporary
Actions

D12677.id34116.diff
View Options

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,16 +29,160 @@
*/
#include <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
+__FBSDID("$FreeBSD: head/lib/libc/tests/stdlib/mergesort_test.c 290538 2015-11-08 07:03:17Z ngie $");
#include <assert.h>
+#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
+#include "stdlib/wiki.c"
#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_WikiSort_test
+ * Test from 2^BASE to 2^MAX elements of type SORT_TYPE
+ */
+#define BASE 10
+#define MAX 27
+#define SORT_TYPE int
+
+/*
+ * Structures to allow for the creation of predefined variable sized arrays.
+ * The len field is necessary 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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+
+ /* Populate test vectors */
+ memcpy(testvector, testarrays[i].elts, len);
+ memcpy(sresvector, testarrays[i].elts, len);
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), sorthelp);
+ /* Sort using reference slow sorting routine */
+ ssort(sresvector, len);
+
+ for (int k = 0; k < len; k++)
+ ATF_CHECK_MSG(testvector[k] == sresvector[k],
+ "item at index %d didn't match: %d != %d",
+ k, testvector[k], sresvector[k]);
+ }
+}
+
+/*
+ * 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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+
+ /* Populate test vectors */
+ memcpy(testvector, testarrays[i].elts, len);
+ memcpy(sresvector, testarrays[i].elts, len);
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), sorthelp);
+ /* Sort using reference slow sorting routine */
+ ssort(sresvector, len);
+
+ for (int k = 0; k < len; k++)
+ ATF_CHECK_MSG(testvector[k] == sresvector[k],
+ "item at index %d didn't match: %d != %d",
+ k, testvector[k], sresvector[k]);
+ }
+}
+
+/*
+ * 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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+
+ /* Populate test vectors */
+ memcpy(testvector, testarrays[i].elts, len);
+ memcpy(sresvector, testarrays[i].elts, len);
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), sorthelp);
+ /* Sort using reference slow sorting routine */
+ ssort(sresvector, len);
+
+ for (int j = 0; j < len; k++)
+ ATF_CHECK_MSG(testvector[j] == sresvector[j],
+ "item at index %d didn't match: %d != %d",
+ j, testvector[j], sresvector[j]);
+ }
+}
+
+/*
+ * 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];
@@ -46,11 +190,11 @@
for (j = 2; j < IVEC_LEN; j++) {
/* Populate test vectors */
- for (i = 0; i < j; i++)
- testvector[i] = sresvector[i] = initvector[i];
+ memcpy(testvector, initvector, j);
+ memcpy(sresvector, initvector, j);
- /* Sort using mergesort(3) */
- mergesort(testvector, j, sizeof(testvector[0]), sorthelp);
+ /* Sort using WikiSort */
+ WikiSort(testvector, j, sizeof(testvector[0]), sorthelp);
/* Sort using reference slow sorting routine */
ssort(sresvector, j);
@@ -62,10 +206,386 @@
}
}
-ATF_TP_ADD_TCS(tp)
+/*
+ * 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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+ /* Populate test vectors */
+ memcpy(testvector, testarrays[i].elts, len);
+ memcpy(sresvector, testarrays[i].elts, len);
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), csorthelp);
+ /* Sort using reference slow sorting routine */
+ scsort(sresvector, len);
+
+ for (int j = 0; j < len; j++)
+ ATF_CHECK_MSG(testvector[j] == sresvector[j],
+ "item at index %d didn't match: %d != %d",
+ j, testvector[j], sresvector[j]);
+}
+}
+
+/*
+ * Sort an array of char[5] arrays. Tests for possible alignment issues.
+ */
+ATF_TC_WITHOUT_HEAD(oddelt_WikiSort_test);
+ATF_TC_BODY(oddelt_WikiSort_test, tc)
+{
+#define NCHARS 5
+ 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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+ /* Populate test vectors */
+ for (int j = 0; j < len; j++) {
+ for (int k = 0; k < NCHARS; k++)
+ testvector[j][k] = sresvector[j][k] =
+ testarrays[i].elts[j][k];
+ }
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), oddsorthelp);
+ /* Sort using reference slow sorting routine */
+ mergesort(sresvector, len, sizeof(sresvector[0]), oddsorthelp);
+ for (int j = 0; j < len; j++)
+ for (int k = 0; k < NCHARS; k++) {
+ ATF_CHECK_MSG(testvector[j][k] !=
+ sresvector[j][k],
+ "item at index %d didn't match: %d != %d\n",
+ j, testvector[j][k], sresvector[j][k]);
+ }
+ }
+}
+
+/*
+ * Sort an array of int*'s
+ */
+ATF_TC_WITHOUT_HEAD(pointer_WikiSort_test);
+ATF_TC_BODY(pointer_WikiSort_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);
+
+ for (int i = 0; i < num_tests; i++) {
+ int len = testarrays[i].len;
+ /* Populate test vectors */
+ for (int j = 0; j < len; j++)
+ testvector[j] = sresvector[j] = testarrays[i].elts[j];
+ /* Sort using WikiSort */
+ WikiSort(testvector, len, sizeof(testvector[0]), ptrsorthelp);
+ /* Reference sort */
+ mergesort(sresvector, len, sizeof(testvector[0]), ptrsorthelp);
+
+ for (int k = 0; k < len; k++)
+ ATF_CHECK_MSG(testvector[k] != sresvector[k],
+ "item at index %d didn't match: %p != %p\n",
+ k, testvector[k], sresvector[k]);
+ }
+}
+
+/*
+ * Sort an array of random int*'s
+ */
+ATF_TC_WITHOUT_HEAD(rand_pointer_WikiSort_test);
+ATF_TC_BODY(rand_pointer_WikiSort_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[rand() % IVEC_LEN]);
+
+ /* Sort using WikiSort */
+ WikiSort(rand_testvector, j, sizeof(rand_testvector[0]),
+ ptrsorthelp);
+ /* Reference sort */
+ mergesort(rand_sresvector, j, sizeof(rand_sresvector[0]),
+ ptrsorthelp);
+
+ /* Compare results */
+ for (i = 0; i < j; 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]);
+ }
+}
+
+/*
+ * Sort an array of nontrivially large structs
+ */
+ATF_TC_WITHOUT_HEAD(bigstruct_WikiSort_test);
+ATF_TC_BODY(bigstruct_WikiSort_test, tc)
+{
+ struct big sresvector[IVEC_LEN];
+ struct big testvector[IVEC_LEN];
+ int i, j;
+
+ for (j = 2; j < IVEC_LEN; j++) {
+ /* Populate test vectors */
+ for (i = 0; i < j; i++)
+ testvector[i].value = sresvector[i].value =
+ initvector[i];
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, j, sizeof(testvector[0]), bigsorthelp);
+ /* Reference sort */
+ mergesort(sresvector, j, sizeof(testvector[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);
+ }
+}
+
+/*
+ * 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_WikiSort_test);
+ATF_TC_BODY(stability_WikiSort_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 = rand() % KEYS;
+ testvector[i].value = sresvector[i].value = value;
+ testvector[i].key = sresvector[i].key = keys[value];
+ keys[value]++;
+ }
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, j, sizeof(testvector[0]), stablesorthelp);
+ /* Reference sort */
+ mergesort(sresvector, j, sizeof(testvector[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
+check(SORT_TYPE *array1, SORT_TYPE *array2, int elts)
{
+ for (int k = 0; k < elts; k++)
+ ATF_CHECK_MSG(array1[k] == array2[k],
+ "item at index %d didn't match: %d != %d",
+ k, array1[k],array2[k]);
+}
+
+static void
+rand_test(int elts)
+{
+ SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts);
+ SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts);
+
+ for (int i = 0; i < elts; i++) {
+ testvector[i] = sresvector[i] = rand();
+ }
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+ /* Sort using reference sorting routine */
+ mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+
+ check(testvector, sresvector, elts);
+
+ free(testvector);
+ free(sresvector);
+}
+
+static void
+sort_test(int elts)
+{
+ SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts);
+ SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts);
+
+ for (int i = 0; i < elts; i++) {
+ testvector[i] = sresvector[i] = i;
+ }
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+ /* Sort using reference sorting routine */
+ mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+
+ check(testvector, sresvector, elts);
+
+ free(testvector);
+ free(sresvector);
+}
+
+static void
+partial_test(int elts)
+{
+ SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts);
+ SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts);
+
+ for (int i = 0; i < elts; i++) {
+ if (i <= elts / 2)
+ testvector[i] = sresvector[i] = i;
+ else
+ testvector[i] = sresvector[i] = rand();
+ }
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+ /* Sort using reference sorting routine */
+ mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
- ATF_TP_ADD_TC(tp, mergesort_test);
+ check(testvector, sresvector, elts);
+
+ free(testvector);
+ free(sresvector);
+}
+
+static void
+reverse_test(int elts)
+{
+ SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts);
+ SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts);
+
+ for (int i = 0; i < elts; i++) {
+ testvector[i] = sresvector[i] = elts - i;
+ }
+
+ /* Sort using WikiSort */
+ WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+ /* Sort using reference sorting routine */
+ mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp);
+
+ check(testvector, sresvector, elts);
+
+ free(testvector);
+ free(sresvector);
+}
+
+/*
+ * Sort an array of integers from 2^BASE to 2^MAX elements
+ */
+ATF_TC_WITHOUT_HEAD(sizeable_WikiSort_test);
+ATF_TC_BODY(sizeable_WikiSort_test, tc)
+{
+ int max = pow(2, MAX);
+ int base = pow(2, BASE);
+ for (int elts = base; elts < max; elts *= 2) {
+ rand_test(elts);
+ sort_test(elts);
+ partial_test(elts);
+ reverse_test(elts);
+ }
+}
+
+
+/*
+ * 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_WikiSort_test);
+ ATF_TP_ADD_TC(tp, pointer_WikiSort_test);
+ ATF_TP_ADD_TC(tp, rand_pointer_WikiSort_test);
+ ATF_TP_ADD_TC(tp, bigstruct_WikiSort_test);
+ ATF_TP_ADD_TC(tp, stability_WikiSort_test);
+ ATF_TP_ADD_TC(tp, sizeable_WikiSort_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,9 @@
#include <atf-c.h>
+/*
+ * Integer comparison function for stdlib sorting algorithms
+ */
static int
sorthelp(const void *a, const void *b)
{
@@ -48,7 +51,116 @@
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[100];
+};
+
+/*
+ * 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);
+}
+
+/* Reference sorting routine for integers (slooow!) */
static void
ssort(int v[], int nmemb)
{
@@ -65,6 +177,24 @@
}
}
+/* Reference sorting routine for chars (slooow!) */
+static void
+scsort(char v[], int nmemb)
+{
+ int i, j;
+ char k;
+
+ 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;
+ }
+ }
+ }
+}
+
/* Some random data */
static int initvector[1024] = {
599853225, 371951333, -428880425, 1450668530, 85530178, -460170550,
Index: tools/tools/msortbench/Makefile
===================================================================
--- /dev/null
+++ tools/tools/msortbench/Makefile
@@ -0,0 +1,7 @@
+# $FreeBSD$
+
+PROG= mergesort_bench
+CFLAGS+=-I${SRCTOP}/lib/libc
+MAN=
+
+.include <bsd.prog.mk>
Index: tools/tools/msortbench/README
===================================================================
--- /dev/null
+++ tools/tools/msortbench/README
@@ -0,0 +1,15 @@
+Running:
+1. Compile mergesort_bench.c into mergesort_bench
+2. Run bench.py with python bench.py [elts]
+2a. Bench will optionally run 2 ^ elts elements as the dataset size when provided. Otherwise it will run 2 ^ 20 elements.
+
+Output:
+Files will be output in a new folder called stats with separate files for each statistical comparison and the raw results in a subfolder called data.
+This files will contain the results of the running of ministat with time required to sort as the dataset.
+
+Modifications:
+Change bench.py's WIKI variable to be true if you have wiki.c implemented and want to test it.
+
+As the script runs, it is running each of the stdlib sorting algorithms (and wikisort if provided) with 2 ^ elts elements,
+5 trials of the sort time as it's output. That output is saved in the data folder and then passed into the command line
+utility ministat which then provides the confidence interval of difference between the data in stats folder.
Index: tools/tools/msortbench/bench.py
===================================================================
--- /dev/null
+++ tools/tools/msortbench/bench.py
@@ -0,0 +1,73 @@
+"""
+Copyright (c) 2017 Miles Fertel
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions
+are met:
+1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+SUCH DAMAGE.
+
+ $FreeBSD$
+ """
+
+#!/usr/bin/env python
+
+from time import time
+import os
+import sys
+
+WIKI = False
+sorts=["heap", "merge", "quick"]
+if (WIKI):
+ sorts.append("wiki")
+tests=["rand", "sort", "rev", "part"]
+runs = 5
+trials = 5
+outdir = "stats"
+datadir = '{}/data'.format(outdir)
+progname = "mergesort_bench"
+try:
+ elts = sys.argv[1]
+except:
+ elts = 20
+
+if (not os.path.isdir(datadir)):
+ os.makedirs(datadir)
+
+for test in tests:
+ files = []
+ for sort in sorts:
+ filename = '{}/{}{}'.format(datadir, test, sort)
+ files.append(filename)
+ with open(filename, 'w+') as f:
+ for _ in range(trials):
+ start = time()
+ ret = os.system('./{} {} {} {} {}'.format(progname, sort, test, runs, elts))
+ total = time() - start
+ if (ret):
+ sys.exit("Bench program failed. Did you remember to compile it?")
+ f.write('{}\n'.format(str(total)))
+ f.close()
+ with open('{}/{}'.format(outdir, test), 'w+') as f:
+ command = 'ministat -s -w 60 '
+ for filename in files:
+ command += '{} '.format(filename)
+ command += '> {}/{}stats'.format(outdir, test)
+ os.system(command)
+
Index: tools/tools/msortbench/mergesort_bench.c
===================================================================
--- /dev/null
+++ tools/tools/msortbench/mergesort_bench.c
@@ -0,0 +1,259 @@
+/*-
+ * Copyright (c) 2017 Miles Fertel
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer,
+ * without modification.
+ * 2. Redistributions in binary form must reproduce at minimum a disclaimer
+ * similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
+ * redistribution must be conditioned upon including a substantially
+ * similar Disclaimer requirement for further binary redistribution.
+ *
+ * NO WARRANTY
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
+ * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
+ * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGES.
+ *
+ * $FreeBSD$
+ */
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sysexits.h>
+#include <unistd.h>
+
+#ifdef WIKI
+#include "stdlib/wiki.c"
+#endif
+
+/*
+ * Integer comparison function for stdlib sorting algorithms
+ */
+static int
+sorthelp(const void *a, const void *b)
+{
+ if (*(int *)a > *(int *)b)
+ return 1;
+ if (*(int *)a < *(int *)b)
+ return -1;
+ return 0;
+}
+
+#define NARGS 5
+
+/*
+ * Enumerated types for the different types of tests and sorting algorithms
+ */
+enum test { RAND, SORT, PART, REV, INVALID_TEST };
+
+#ifdef WIKI
+enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
+#else
+enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
+#endif
+
+/*
+ * Sort an array with the given algorithm
+ */
+static void
+sort(int *testarray, int elts, enum sort s)
+{
+ switch (s) {
+ case MERGE:
+ mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+#ifdef WIKI
+ case WIKI:
+ WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+#endif
+ case QUICK:
+ qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+ case HEAP:
+ heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+ // Should never be reached
+ case INVALID_ALG:
+ exit(EX_DATAERR);
+ }
+}
+
+/*
+ * Sort an array of randomly generated integers
+ */
+static void
+rand_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ arc4random_buf(array, size);
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of increasing integers
+ */
+static void
+sort_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ array[i] = i;
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of partially increasing, partially random integers
+ */
+static void
+partial_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ if (i <= elts / 2)
+ array[i] = i;
+ else
+ array[i] = arc4random();
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of decreasing integers
+ */
+static void
+reverse_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ array[i] = elts - i;
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+static void
+run_bench(enum sort s, enum test t, int runs, int elts)
+{
+ for (int i = 0; i < runs; i++) {
+ switch (t) {
+ case RAND:
+ rand_bench(elts, s);
+ break;
+ case SORT:
+ sort_bench(elts, s);
+ break;
+ case PART:
+ partial_bench(elts, s);
+ break;
+ case REV:
+ reverse_bench(elts, s);
+ break;
+ // Should never be reached
+ case INVALID_TEST:
+ exit(EX_DATAERR);
+ }
+ }
+}
+
+static enum sort
+parse_alg(char *alg)
+{
+ if (strcmp(alg, "merge") == 0)
+ return MERGE;
+#ifdef WIKI
+ else if (strcmp(alg, "wiki") == 0)
+ return WIKI;
+#endif
+ else if (strcmp(alg, "quick") == 0)
+ return QUICK;
+ else if (strcmp(alg, "heap") == 0)
+ return HEAP;
+ else
+ return INVALID_ALG;
+}
+
+static enum test
+parse_test(char *test)
+{
+ if (strcmp(test, "rand") == 0)
+ return RAND;
+ else if (strcmp(test, "sort") == 0)
+ return SORT;
+ else if (strcmp(test, "part") == 0)
+ return PART;
+ else if (strcmp(test, "rev") == 0)
+ return REV;
+ else
+ return INVALID_TEST;
+}
+
+static void
+usage(const char *progname)
+{
+ printf("Usage:\n");
+ printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
+ printf("\n");
+ printf("Valid algs:\n");
+#ifdef WIKI
+ printf("\theap merge quick wiki\n");
+#else
+ printf("\theap merge quick\n");
+#endif
+ printf("Valid tests:\n");
+ printf("\trand sort part rev\n");
+ printf("\trand: Random element array \n");
+ printf("\tsort: Increasing order array \n");
+ printf("\tpart: Partially ordered array\n");
+ printf("\trev: Decreasing order array\n");
+ printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
+ exit(EX_USAGE);
+}
+
+/*
+ * Runs a sorting algorithm with a provided data configuration according to
+ * command line arguments
+ */
+int
+main(int argc, char *argv[])
+{
+ const char *progname = argv[0];
+ int runs, elts;
+ if (argc != NARGS)
+ usage(progname);
+
+ enum sort s = parse_alg(argv[1]);
+ if (s == INVALID_ALG)
+ usage(progname);
+
+ enum test t = parse_test(argv[2]);
+ if (t == INVALID_TEST)
+ usage(progname);
+
+ runs = atoi(argv[3]);
+ elts = pow(2, atoi(argv[4]));
+
+ run_bench(s, t, runs, elts);
+}
Index: tools/tools/sortbench/Makefile
===================================================================
--- /dev/null
+++ tools/tools/sortbench/Makefile
@@ -0,0 +1,18 @@
+# $FreeBSD$
+
+PROG= sort_bench
+MAN=
+
+LIBADD= m
+
+.ifdef WITH_WIKISORT
+CFLAGS= -I${SRCTOP}/lib/libc -DWIKI
+.endif
+
+CLEANDIRS= stats
+ELEMENT_BITS= 20
+bench: .PHONY
+ ${.CURDIR}/bench.py ${ELEMENT_BITS}
+ echo "See results in ${.OBJDIR}/stats"
+
+.include <bsd.prog.mk>
Index: tools/tools/sortbench/README
===================================================================
--- /dev/null
+++ tools/tools/sortbench/README
@@ -0,0 +1,15 @@
+Running:
+1. Compile mergesort_bench.c into mergesort_bench
+2. Run bench.py with python bench.py [elts]
+2a. Bench will optionally run 2 ^ elts elements as the dataset size when provided. Otherwise it will run 2 ^ 20 elements.
+
+Output:
+Files will be output in a new folder called stats with separate files for each statistical comparison and the raw results in a subfolder called data.
+This files will contain the results of the running of ministat with time required to sort as the dataset.
+
+Modifications:
+Change bench.py's WIKI variable to be true if you have wiki.c implemented and want to test it.
+
+As the script runs, it is running each of the stdlib sorting algorithms (and wikisort if provided) with 2 ^ elts elements,
+5 trials of the sort time as it's output. That output is saved in the data folder and then passed into the command line
+utility ministat which then provides the confidence interval of difference between the data in stats folder.
Index: tools/tools/sortbench/bench.py
===================================================================
--- /dev/null
+++ tools/tools/sortbench/bench.py
@@ -0,0 +1,45 @@
+#!/usr/bin/env python
+
+from time import time
+import os
+import sys
+
+WIKI = False
+sorts=["heap", "merge", "quick"]
+if (WIKI):
+ sorts.append("wiki")
+tests=["rand", "sort", "rev", "part"]
+runs = 5
+trials = 5
+outdir = "stats"
+datadir = '{}/data'.format(outdir)
+progname = "sort_bench"
+try:
+ elts = sys.argv[1]
+except:
+ elts = 20
+
+if (not os.path.isdir(datadir)):
+ os.makedirs(datadir)
+
+for test in tests:
+ files = []
+ for sort in sorts:
+ filename = '{}/{}{}'.format(datadir, test, sort)
+ files.append(filename)
+ with open(filename, 'w+') as f:
+ for _ in range(trials):
+ start = time()
+ ret = os.system('./{} {} {} {} {}'.format(progname, sort, test, runs, elts))
+ total = time() - start
+ if (ret):
+ sys.exit("Bench program failed. Did you remember to compile it?")
+ f.write('{}\n'.format(str(total)))
+ f.close()
+ with open('{}/{}'.format(outdir, test), 'w+') as f:
+ command = 'ministat -s -w 60 '
+ for filename in files:
+ command += '{} '.format(filename)
+ command += '> {}/{}stats'.format(outdir, test)
+ os.system(command)
+
Index: tools/tools/sortbench/sort_bench.c
===================================================================
--- /dev/null
+++ tools/tools/sortbench/sort_bench.c
@@ -0,0 +1,228 @@
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sysexits.h>
+#include <unistd.h>
+
+#ifdef WIKI
+#include "stdlib/wiki.c"
+#endif
+
+/*
+ * Integer comparison function for stdlib sorting algorithms
+ */
+static int
+sorthelp(const void *a, const void *b)
+{
+ if (*(int *)a > *(int *)b)
+ return 1;
+ if (*(int *)a < *(int *)b)
+ return -1;
+ return 0;
+}
+
+#define NARGS 5
+
+/*
+ * Enumerated types for the different types of tests and sorting algorithms
+ */
+enum test { RAND, SORT, PART, REV, INVALID_TEST };
+
+#ifdef WIKI
+enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
+#else
+enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
+#endif
+
+/*
+ * Sort an array with the given algorithm
+ */
+static void
+sort(int *testarray, int elts, enum sort s)
+{
+ switch (s) {
+ case MERGE:
+ mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+#ifdef WIKI
+ case WIKI:
+ WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+#endif
+ case QUICK:
+ qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+ case HEAP:
+ heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
+ break;
+ // Should never be reached
+ case INVALID_ALG:
+ exit(EX_DATAERR);
+ }
+}
+
+/*
+ * Sort an array of randomly generated integers
+ */
+static void
+rand_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ arc4random_buf(array, size);
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of increasing integers
+ */
+static void
+sort_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ array[i] = i;
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of partially increasing, partially random integers
+ */
+static void
+partial_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ if (i <= elts / 2)
+ array[i] = i;
+ else
+ array[i] = arc4random();
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+/*
+ * Sort an array of decreasing integers
+ */
+static void
+reverse_bench(int elts, enum sort s)
+{
+ size_t size = sizeof(int) * elts;
+ int *array = malloc(size);
+ for (int i = 0; i < elts; i++) {
+ array[i] = elts - i;
+ }
+ sort(array, elts, s);
+ free(array);
+}
+
+static void
+run_bench(enum sort s, enum test t, int runs, int elts)
+{
+ for (int i = 0; i < runs; i++) {
+ switch (t) {
+ case RAND:
+ rand_bench(elts, s);
+ break;
+ case SORT:
+ sort_bench(elts, s);
+ break;
+ case PART:
+ partial_bench(elts, s);
+ break;
+ case REV:
+ reverse_bench(elts, s);
+ break;
+ // Should never be reached
+ case INVALID_TEST:
+ exit(EX_DATAERR);
+ }
+ }
+}
+
+static enum sort
+parse_alg(char *alg)
+{
+ if (strcmp(alg, "merge") == 0)
+ return MERGE;
+#ifdef WIKI
+ else if (strcmp(alg, "wiki") == 0)
+ return WIKI;
+#endif
+ else if (strcmp(alg, "quick") == 0)
+ return QUICK;
+ else if (strcmp(alg, "heap") == 0)
+ return HEAP;
+ else
+ return INVALID_ALG;
+}
+
+static enum test
+parse_test(char *test)
+{
+ if (strcmp(test, "rand") == 0)
+ return RAND;
+ else if (strcmp(test, "sort") == 0)
+ return SORT;
+ else if (strcmp(test, "part") == 0)
+ return PART;
+ else if (strcmp(test, "rev") == 0)
+ return REV;
+ else
+ return INVALID_TEST;
+}
+
+static void
+usage(const char *progname)
+{
+ printf("Usage:\n");
+ printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
+ printf("\n");
+ printf("Valid algs:\n");
+#ifdef WIKI
+ printf("\theap merge quick wiki\n");
+#else
+ printf("\theap merge quick\n");
+#endif
+ printf("Valid tests:\n");
+ printf("\trand sort part rev\n");
+ printf("\trand: Random element array \n");
+ printf("\tsort: Increasing order array \n");
+ printf("\tpart: Partially ordered array\n");
+ printf("\trev: Decreasing order array\n");
+ printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
+ exit(EX_USAGE);
+}
+
+/*
+ * Runs a sorting algorithm with a provided data configuration according to
+ * command line arguments
+ */
+int
+main(int argc, char *argv[])
+{
+ const char *progname = argv[0];
+ int runs, elts;
+ if (argc != NARGS)
+ usage(progname);
+
+ enum sort s = parse_alg(argv[1]);
+ if (s == INVALID_ALG)
+ usage(progname);
+
+ enum test t = parse_test(argv[2]);
+ if (t == INVALID_TEST)
+ usage(progname);
+
+ runs = atoi(argv[3]);
+ elts = pow(2, atoi(argv[4]));
+
+ run_bench(s, t, runs, elts);
+}

File Metadata

Mime Type
text/plain
Expires
Sun, Sep 20, 3:28 AM (3 h, 49 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39272869
Default Alt Text
D12677.id34116.diff (37 KB)

Event Timeline