diff options
Diffstat (limited to 'regress/lib/libc')
-rw-r--r-- | regress/lib/libc/qsort/qsort_test.c | 563 |
1 files changed, 421 insertions, 142 deletions
diff --git a/regress/lib/libc/qsort/qsort_test.c b/regress/lib/libc/qsort/qsort_test.c index 03d73216bd6..8ab3d9f50df 100644 --- a/regress/lib/libc/qsort/qsort_test.c +++ b/regress/lib/libc/qsort/qsort_test.c @@ -35,13 +35,20 @@ * M. D. McIlroy's "A Killer Adversary for Quicksort" */ +/* + * TODO: + * test with unaligned elements (char[]?) + */ struct test_distribution { const char *name; - void (*fill)(int *x, int n, int m); - int (*test)(struct test_distribution *d, int n, int *x, int *y, int *z); + void (*fill)(void *x, int n, int m); + int (*test)(struct test_distribution *d, int n, void *x, void *y, void *z); + int (*cmp)(const void *v1, const void *v2); + int (*cmp_checked)(const void *v1, const void *v2); }; -#define min(a, b) (((a) < (b)) ? (a) : (b)) +#define MINIMUM(a, b) (((a) < (b)) ? (a) : (b)) +#define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b)) static size_t compares; static size_t max_compares; @@ -52,7 +59,7 @@ static bool dump_table, timing, verbose; extern int antiqsort(int n, int *a, int *ptr); static int -cmp(const void *v1, const void *v2) +cmp_i(const void *v1, const void *v2) { const int a = *(const int *)v1; const int b = *(const int *)v2; @@ -61,7 +68,7 @@ cmp(const void *v1, const void *v2) } static int -cmp_checked(const void *v1, const void *v2) +cmp_checked_i(const void *v1, const void *v2) { const int a = *(const int *)v1; const int b = *(const int *)v2; @@ -73,7 +80,49 @@ cmp_checked(const void *v1, const void *v2) } static int -check_result(char *sub, int *got, int *expected, struct test_distribution *d, +cmp_ll(const void *v1, const void *v2) +{ + const long long a = *(const long long *)v1; + const long long b = *(const long long *)v2; + + return a > b ? 1 : a < b ? -1 : 0; +} + +static int +cmp_checked_ll(const void *v1, const void *v2) +{ + const long long a = *(const long long *)v1; + const long long b = *(const long long *)v2; + + compares++; + if (compares > abrt_compares) + siglongjmp(cmpjmp, 1); + return a > b ? 1 : a < b ? -1 : 0; +} + +static int +cmp_d(const void *v1, const void *v2) +{ + const double a = *(const double *)v1; + const double b = *(const double *)v2; + + return a > b ? 1 : a < b ? -1 : 0; +} + +static int +cmp_checked_d(const void *v1, const void *v2) +{ + const double a = *(const double *)v1; + const double b = *(const double *)v2; + + compares++; + if (compares > abrt_compares) + siglongjmp(cmpjmp, 1); + return a > b ? 1 : a < b ? -1 : 0; +} + +static int +check_result(char *sub, size_t es, char *got, char *expected, struct test_distribution *d, int m, int n) { int i; @@ -103,8 +152,10 @@ check_result(char *sub, int *got, int *expected, struct test_distribution *d, } for (i = 0; i < n; i++) { - if (got[i] != expected[i]) + if (memcmp(got, expected, es) != 0) break; + got += es; + expected += es; } if (i == n) return 0; @@ -119,90 +170,228 @@ check_result(char *sub, int *got, int *expected, struct test_distribution *d, return 1; } +#define FILL_SAWTOOTH(x, n, m) do { \ + int i; \ + \ + for (i = 0; i < n; i++) \ + x[i] = i % m; \ +} while (0) + static void -fill_sawtooth(int *x, int n, int m) +fill_sawtooth_i(void *v, int n, int m) { - int i; + int *x = v; + FILL_SAWTOOTH(x, n, m); +} - for (i = 0; i < n; i++) - x[i] = i % m; +static void +fill_sawtooth_ll(void *v, int n, int m) +{ + long long *x = v; + FILL_SAWTOOTH(x, n, m); } static void -fill_random(int *x, int n, int m) +fill_sawtooth_double(void *v, int n, int m) { - int i; + double *x = v; + FILL_SAWTOOTH(x, n, m); +} + +#define FILL_RANDOM(x, n, m) do { \ + int i; \ + \ + for (i = 0; i < n; i++) \ + x[i] = arc4random_uniform(m); \ +} while (0) - for (i = 0; i < n; i++) - x[i] = arc4random_uniform(m); + +static void +fill_random_i(void *v, int n, int m) +{ + int *x = v; + FILL_RANDOM(x, n, m); } static void -fill_stagger(int *x, int n, int m) +fill_random_ll(void *v, int n, int m) { - int i; + long long *x = v; + FILL_RANDOM(x, n, m); +} - for (i = 0; i < n; i++) - x[i] = (i * m + i) % n; +static void +fill_random_double(void *v, int n, int m) +{ + double *x = v; + FILL_RANDOM(x, n, m); } +#define FILL_STAGGER(x, n, m) do { \ + int i; \ + \ + for (i = 0; i < n; i++) \ + x[i] = (i * m + i) % n; \ +} while (0) + + static void -fill_plateau(int *x, int n, int m) +fill_stagger_i(void *v, int n, int m) { - int i; + int *x = v; + FILL_STAGGER(x, n, m); +} - for (i = 0; i < n; i++) - x[i] = min(i, m); +static void +fill_stagger_ll(void *v, int n, int m) +{ + long long *x = v; + FILL_STAGGER(x, n, m); } static void -fill_shuffle(int *x, int n, int m) +fill_stagger_double(void *v, int n, int m) { - int i, j, k; + double *x = v; + FILL_STAGGER(x, n, m); +} + +#define FILL_PLATEAU(x, n, m) do { \ + int i; \ + \ + for (i = 0; i < n; i++) \ + x[i] = MINIMUM(i, m); \ +} while (0) - for (i = 0, j = 0, k = 1; i < n; i++) - x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); +static void +fill_plateau_i(void *v, int n, int m) +{ + int *x = v; + FILL_PLATEAU(x, n, m); } static void -fill_bsd_killer(int *x, int n, int m) +fill_plateau_ll(void *v, int n, int m) { - int i, k; + long long *x = v; + FILL_PLATEAU(x, n, m); +} - /* 4.4BSD insertion sort optimization killer, Mats Linander */ - k = n / 2; - for (i = 0; i < n; i++) { - if (i < k) - x[i] = k - i; - else if (i > k) - x[i] = n + k + 1 - i; - else - x[i] = k + 1; - } +static void +fill_plateau_double(void *v, int n, int m) +{ + double *x = v; + FILL_PLATEAU(x, n, m); } +#define FILL_SHUFFLE(x, n, m) do { \ + int i, j, k; \ + \ + for (i = 0, j = 0, k = 1; i < n; i++) \ + x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); \ +} while (0) + static void -fill_med3_killer(int *x, int n, int m) +fill_shuffle_i(void *v, int n, int m) { - int i, k; + int *x = v; + FILL_SHUFFLE(x, n, m); +} - /* - * Median of 3 killer, as seen in David R Musser's - * "Introspective Sorting and Selection Algorithms" - */ - if (n & 1) { - /* odd size, store last at end and make even. */ - x[n - 1] = n; - n--; - } - k = n / 2; - for (i = 0; i < n; i++) { - if (i & 1) { - x[i] = k + x[i - 1]; - } else { - x[i] = i + 1; - } - } +static void +fill_shuffle_ll(void *v, int n, int m) +{ + long long *x = v; + FILL_SHUFFLE(x, n, m); +} + +static void +fill_shuffle_double(void *v, int n, int m) +{ + double *x = v; + FILL_SHUFFLE(x, n, m); +} + +#define FILL_BSD_KILLER(x, n, m) do { \ + int i, k; \ + \ + /* 4.4BSD insertion sort optimization killer, Mats Linander */ \ + k = n / 2; \ + for (i = 0; i < n; i++) { \ + if (i < k) \ + x[i] = k - i; \ + else if (i > k) \ + x[i] = n + k + 1 - i; \ + else \ + x[i] = k + 1; \ + } \ +} while (0) + +static void +fill_bsd_killer_i(void *v, int n, int m) +{ + int *x = v; + FILL_BSD_KILLER(x, n, m); + +} + +static void +fill_bsd_killer_ll(void *v, int n, int m) +{ + long long *x = v; + FILL_BSD_KILLER(x, n, m); + +} + +static void +fill_bsd_killer_double(void *v, int n, int m) +{ + double *x = v; + FILL_BSD_KILLER(x, n, m); + +} + +#define FILL_MED3_KILLER(x, n, m) do { \ + int i, k; \ + \ + /* \ + * Median of 3 killer, as seen in David R Musser's \ + * "Introspective Sorting and Selection Algorithms" \ + */ \ + if (n & 1) { \ + /* odd size, store last at end and make even. */ \ + x[n - 1] = n; \ + n--; \ + } \ + k = n / 2; \ + for (i = 0; i < n; i++) { \ + if (i & 1) { \ + x[i] = k + x[i - 1]; \ + } else { \ + x[i] = i + 1; \ + } \ + } \ +} while (0) + +static void +fill_med3_killer_i(void *v, int n, int m) +{ + int *x = v; + FILL_MED3_KILLER(x, n, m); +} + +static void +fill_med3_killer_ll(void *v, int n, int m) +{ + long long *x = v; + FILL_MED3_KILLER(x, n, m); +} + +static void +fill_med3_killer_double(void *v, int n, int m) +{ + double *x = v; + FILL_MED3_KILLER(x, n, m); } static void @@ -228,7 +417,7 @@ print_timing(struct test_distribution *d, char *sub, int m, int n, double elapse } static int -do_test(struct test_distribution *d, char *sub, int m, int n, int *y, int *z) +do_test(struct test_distribution *d, char *sub, int m, int n, size_t es, void *y, void *z) { int ret = 0; struct timespec before, after; @@ -246,7 +435,7 @@ do_test(struct test_distribution *d, char *sub, int m, int n, int *y, int *z) } else { if (timing) clock_gettime(CLOCK_MONOTONIC, &before); - qsort(y, n, sizeof(y[0]), cmp_checked); + qsort(y, n, es, d->cmp_checked); if (timing) { double elapsed; clock_gettime(CLOCK_MONOTONIC, &after); @@ -254,98 +443,162 @@ do_test(struct test_distribution *d, char *sub, int m, int n, int *y, int *z) elapsed = after.tv_sec + after.tv_nsec / 1000000000.0; print_timing(d, sub, m, n, elapsed); } - if (check_result(sub, y, z, d, m, n) != 0) + if (check_result(sub, es, y, z, d, m, n) != 0) ret = 1; } return ret; } +#define TEST_PERTURBED(d, n, x, y, z) do { \ + int i, j, m; \ + const int es = sizeof(x[0]); \ + \ + for (m = 1; m < 2 * n; m *= 2) { \ + /* Fill in x[n] modified by m */ \ + d->fill(x, n, m); \ + \ + /* Test on copy of x[] */ \ + for (i = 0; i < n; i++) \ + y[i] = z[i] = x[i]; \ + if (mergesort(z, n, es, d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, "copy", m, n, es, y, z) != 0) \ + ret = 1; \ + \ + /* Test on reversed copy of x[] */ \ + for (i = 0, j = n - 1; i < n; i++, j--) \ + y[i] = z[i] = x[j]; \ + if (mergesort(z, n, es, d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, "reversed", m, n, es, y, z) != 0) \ + ret = 1; \ + \ + /* Test with front half of x[] reversed */ \ + for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--) \ + y[i] = z[i] = x[j]; \ + for (; i < n; i++) \ + y[i] = z[i] = x[i]; \ + if (mergesort(z, n, es, d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, "front reversed", m, n, es, y, z) != 0) \ + ret = 1; \ + \ + /* Test with back half of x[] reversed */ \ + for (i = 0; i < n / 2; i++) \ + y[i] = z[i] = x[i]; \ + for (j = n - 1; i < n; i++, j--) \ + y[i] = z[i] = x[j]; \ + if (mergesort(z, n, es, d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, "back reversed", m, n, es, y, z) != 0) \ + ret = 1; \ + \ + /* Test on sorted copy of x[] */ \ + if (mergesort(x, n, es, d->cmp) != 0) \ + err(1, NULL); \ + for (i = 0; i < n; i++) \ + y[i] = x[i]; \ + if (do_test(d, "sorted", m, n, es, y, x) != 0) \ + ret = 1; \ + \ + /* Test with i%5 added to x[i] (dither) */ \ + for (i = 0, j = n - 1; i < n; i++, j--) \ + y[i] = z[i] = x[j] + (i % 5); \ + if (mergesort(z, n, es, d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, "dithered", m, n, es, y, z) != 0) \ + ret = 1; \ + } \ +} while (0) + static int -test_perturbed(struct test_distribution *d, int n, int *x, int *y, int *z) +test_perturbed_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz) { - int i, j, m; + int *x = vx; + int *y = vx; + int *z = vz; int ret = 0; - for (m = 1; m < 2 * n; m *= 2) { - /* Fill in x[n] modified by m */ - d->fill(x, n, m); - - /* Test on copy of x[] */ - for (i = 0; i < n; i++) - y[i] = z[i] = x[i]; - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, "copy", m, n, y, z) != 0) - ret = 1; - - /* Test on reversed copy of x[] */ - for (i = 0, j = n - 1; i < n; i++, j--) - y[i] = z[i] = x[j]; - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, "reversed", m, n, y, z) != 0) - ret = 1; - - /* Test with front half of x[] reversed */ - for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--) - y[i] = z[i] = x[j]; - for (; i < n; i++) - y[i] = z[i] = x[i]; - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, "front reversed", m, n, y, z) != 0) - ret = 1; + TEST_PERTURBED(d, n, x, y, z); + return ret; +} - /* Test with back half of x[] reversed */ - for (i = 0; i < n / 2; i++) - y[i] = z[i] = x[i]; - for (j = n - 1; i < n; i++, j--) - y[i] = z[i] = x[j]; - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, "back reversed", m, n, y, z) != 0) - ret = 1; +static int +test_perturbed_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz) +{ + long long *x = vx; + long long *y = vx; + long long *z = vz; + int ret = 0; - /* Test on sorted copy of x[] */ - if (mergesort(x, n, sizeof(x[0]), cmp) != 0) - err(1, NULL); - for (i = 0; i < n; i++) - y[i] = x[i]; - if (do_test(d, "sorted", m, n, y, x) != 0) - ret = 1; + TEST_PERTURBED(d, n, x, y, z); + return ret; +} - /* Test with i%5 added to x[i] (dither) */ - for (i = 0, j = n - 1; i < n; i++, j--) - y[i] = z[i] = x[j] + (i % 5); - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, "front reversed", m, n, y, z) != 0) - ret = 1; - } +static int +test_perturbed_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz) +{ + double *x = vx; + double *y = vx; + double *z = vz; + int ret = 0; + TEST_PERTURBED(d, n, x, y, z); return ret; } /* - * Like test_perturbed() but because the input is tailored to cause + * Like TEST_PERTURBED but because the input is tailored to cause * quicksort to go quadratic we don't perturb the input. */ +#define TEST_SIMPLE(d, n, x, y, z) do { \ + int i, ret = 0; \ + \ + /* Fill in x[n] */ \ + d->fill(x, n, 0); \ + \ + /* Make a copy of x[] */ \ + for (i = 0; i < n; i++) \ + y[i] = z[i] = x[i]; \ + if (mergesort(z, n, sizeof(z[0]), d->cmp) != 0) \ + err(1, NULL); \ + if (do_test(d, NULL, 0, n, sizeof(x[0]), y, z) != 0) \ + ret = 1; \ +} while (0) + static int -test_simple(struct test_distribution *d, int n, int *x, int *y, int *z) +test_simple_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz) { - int i, ret = 0; + int *x = vx; + int *y = vx; + int *z = vz; + int ret = 0; - /* Fill in x[n] */ - d->fill(x, n, 0); + TEST_SIMPLE(d, n, x, y, z); + return ret; +} - /* Make a copy of x[] */ - for (i = 0; i < n; i++) - y[i] = z[i] = x[i]; - if (mergesort(z, n, sizeof(z[0]), cmp) != 0) - err(1, NULL); - if (do_test(d, NULL, 0, n, y, z) != 0) - ret = 1; +static int +test_simple_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz) +{ + long long *x = vx; + long long *y = vx; + long long *z = vz; + int ret = 0; + TEST_SIMPLE(d, n, x, y, z); + return ret; +} + +static int +test_simple_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz) +{ + double *x = vx; + double *y = vx; + double *z = vz; + int ret = 0; + + TEST_SIMPLE(d, n, x, y, z); return ret; } @@ -354,9 +607,11 @@ test_simple(struct test_distribution *d, int n, int *x, int *y, int *z) * We don't compare the results in this case. */ static int -test_antiqsort(struct test_distribution *d, int n, int *x, int *y, int *z) +test_antiqsort(struct test_distribution *d, int n, void *vx, void *vy, void *vz) { struct timespec before, after; + int *x = vx; + int *y = vx; int i, ret = 0; /* @@ -396,23 +651,38 @@ test_antiqsort(struct test_distribution *d, int n, int *x, int *y, int *z) } static struct test_distribution distributions[] = { - { "sawtooth", fill_sawtooth, test_perturbed }, - { "random", fill_random, test_perturbed }, - { "stagger", fill_stagger, test_perturbed }, - { "plateau", fill_plateau, test_perturbed }, - { "shuffle", fill_shuffle, test_perturbed }, - { "bsd_killer", fill_bsd_killer, test_simple }, - { "med3_killer", fill_med3_killer, test_simple }, - { "antiqsort", NULL, test_antiqsort }, + { "sawtooth_i", fill_sawtooth_i, test_perturbed_i, cmp_i, cmp_checked_i }, + { "sawtooth_ll", fill_sawtooth_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, + { "sawtooth_d", fill_sawtooth_double, test_perturbed_double, cmp_d, cmp_checked_d }, + { "random_i", fill_random_i, test_perturbed_i, cmp_i, cmp_checked_i }, + { "random_ll", fill_random_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, + { "random_d", fill_random_double, test_perturbed_double, cmp_d, cmp_checked_d }, + { "stagger_i", fill_stagger_i, test_perturbed_i, cmp_i, cmp_checked_i }, + { "stagger_ll", fill_stagger_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, + { "stagger_d", fill_stagger_double, test_perturbed_double, cmp_d, cmp_checked_d }, + { "plateau_i", fill_plateau_i, test_perturbed_i, cmp_i, cmp_checked_i }, + { "plateau_ll", fill_plateau_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, + { "plateau_d", fill_plateau_double, test_perturbed_double, cmp_d, cmp_checked_d }, + { "shuffle_i", fill_shuffle_i, test_perturbed_i, cmp_i, cmp_checked_i }, + { "shuffle_ll", fill_shuffle_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, + { "shuffle_d", fill_shuffle_double, test_perturbed_double, cmp_d, cmp_checked_d }, + { "bsd_killer_i", fill_bsd_killer_i, test_simple_i, cmp_i, cmp_checked_i }, + { "bsd_killer_ll", fill_bsd_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll }, + { "bsd_killer_d", fill_bsd_killer_double, test_simple_double, cmp_d, cmp_checked_d }, + { "med3_killer_i", fill_med3_killer_i, test_simple_i, cmp_i, cmp_checked_i }, + { "med3_killer_ll", fill_med3_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll }, + { "med3_killer_d", fill_med3_killer_double, test_simple_double, cmp_d, cmp_checked_d }, + { "antiqsort", NULL, test_antiqsort, cmp_i, cmp_checked_i }, { NULL } }; static int run_tests(int n, const char *name) { - int *x, *y, *z; + void *x, *y, *z; int i, nlgn = 0; int ret = 0; + size_t es; struct test_distribution *d; /* @@ -426,14 +696,16 @@ run_tests(int n, const char *name) max_compares = nlgn * 1.5; abrt_compares = nlgn * 10; - x = reallocarray(NULL, n, sizeof(x[0])); - y = reallocarray(NULL, n, sizeof(y[0])); - z = reallocarray(NULL, n, sizeof(z[0])); + /* Allocate enough space to store ints or doubles. */ + es = MAXIMUM(sizeof(int), sizeof(double)); + x = reallocarray(NULL, n, es); + y = reallocarray(NULL, n, es); + z = reallocarray(NULL, n, es); if (x == NULL || y == NULL || z == NULL) err(1, NULL); for (d = distributions; d->name != NULL; d++) { - if (name != NULL && strcmp(name, d->name) != 0) + if (name != NULL && strncmp(name, d->name, strlen(name)) != 0) continue; if (d->test(d, n, x, y, z) != 0) ret = 1; @@ -456,6 +728,7 @@ int main(int argc, char *argv[]) { char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" }; + struct test_distribution *d; int ch, n, ret = 0; char *name = NULL; @@ -465,6 +738,12 @@ main(int argc, char *argv[]) dump_table = true; break; case 'n': + for (d = distributions; d->name != NULL; d++) { + if (strncmp(optarg, d->name, strlen(optarg)) == 0) + break; + } + if (d->name == NULL) + errx(1, "unknown test %s", optarg); name = optarg; break; case 't': |