diff options
| author |   millert <millert@openbsd.org> | 2017-05-18 14:50:08 +0000 |
|---|---|---|
| committer | millert <millert@openbsd.org> | 2017-05-18 14:50:08 +0000 |
| commit | f996ae442d9f50886016262faef63e597bda2171 (patch) | |
| tree | d56e838a3289afac6f67dabc8181b9064799588d | |
| parent | Grab the netlock in umb_state_task() and umb_decode_ip_configuration() (diff) | |
| download | wireguard-openbsd-f996ae442d9f50886016262faef63e597bda2171.tar.xz wireguard-openbsd-f996ae442d9f50886016262faef63e597bda2171.zip | |
use mergesort instead of heapsort when comparing results
| -rw-r--r-- | regress/lib/libc/qsort/qsort_test.c | 26 |
1 files changed, 17 insertions, 9 deletions
diff --git a/regress/lib/libc/qsort/qsort_test.c b/regress/lib/libc/qsort/qsort_test.c index b1e1a25c92e..f8507ce88c6 100644 --- a/regress/lib/libc/qsort/qsort_test.c +++ b/regress/lib/libc/qsort/qsort_test.c @@ -22,9 +22,11 @@ /* * Test program based on Bentley & McIlroy's "Engineering a Sort Function". - * Uses heapsort(3) to check the results. - * The "killer" input is from: - * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html + * Additional tests include the "median of three" killer from + * David R. Musser's "Introspective Sorting and Selection Algorithms" + * and 4.4BSD qsort killer input from + * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html + * Uses mergesort(3) to check the results. */ enum distribution { @@ -168,7 +170,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) ret = 1; } else { qsort(y, n, sizeof(y[0]), cmp_checked); - heapsort(z, n, sizeof(z[0]), cmp); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); if (check_result("copy", y, z, dist, m, n) != 0) ret = 1; } @@ -183,7 +186,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) ret = 1; } else { qsort(y, n, sizeof(y[0]), cmp_checked); - heapsort(z, n, sizeof(z[0]), cmp); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); if (check_result("reversed", y, z, dist, m, n) != 0) ret = 1; } @@ -200,7 +204,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) ret = 1; } else { qsort(y, n, sizeof(y[0]), cmp_checked); - heapsort(z, n, sizeof(z[0]), cmp); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); if (check_result("front reversed", y, z, dist, m, n) != 0) ret = 1; } @@ -217,13 +222,15 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) ret = 1; } else { qsort(y, n, sizeof(y[0]), cmp_checked); - heapsort(z, n, sizeof(z[0]), cmp); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); if (check_result("back reversed", y, z, dist, m, n) != 0) ret = 1; } /* Test on sorted copy of x[] */ - heapsort(x, n, sizeof(x[0]), cmp); + if (mergesort(x, n, sizeof(x[0]), cmp) != 0) + err(1, NULL); for (i = 0; i < n; i++) y[i] = x[i]; compares = 0; @@ -247,7 +254,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) ret = 1; } else { qsort(y, n, sizeof(y[0]), cmp_checked); - heapsort(z, n, sizeof(z[0]), cmp); + if (mergesort(z, n, sizeof(z[0]), cmp) != 0) + err(1, NULL); if (check_result("dithered", y, z, dist, m, n) != 0) ret = 1; } |