diff options
| author | millert <> | 2017-05-18 14:50:08 +0000 |
|---|---|---|
| committer | millert <> | 2017-05-18 14:50:08 +0000 |
| commit | 9b92cdd78cb9cf5ccef1941bc1d989802b7e9f0e (patch) | |
| tree | 2fc942ff3e7a48417af56dc1e4511c4ec41050f4 /src/regress/lib/libc | |
| parent | 676818f5d9d7309fc3c3c923183eb05b15da3018 (diff) | |
| download | openbsd-9b92cdd78cb9cf5ccef1941bc1d989802b7e9f0e.tar.gz openbsd-9b92cdd78cb9cf5ccef1941bc1d989802b7e9f0e.tar.bz2 openbsd-9b92cdd78cb9cf5ccef1941bc1d989802b7e9f0e.zip | |
use mergesort instead of heapsort when comparing results
Diffstat (limited to 'src/regress/lib/libc')
| -rw-r--r-- | src/regress/lib/libc/qsort/qsort_test.c | 26 |
1 files changed, 17 insertions, 9 deletions
diff --git a/src/regress/lib/libc/qsort/qsort_test.c b/src/regress/lib/libc/qsort/qsort_test.c index b1e1a25c92..f8507ce88c 100644 --- a/src/regress/lib/libc/qsort/qsort_test.c +++ b/src/regress/lib/libc/qsort/qsort_test.c | |||
| @@ -22,9 +22,11 @@ | |||
| 22 | 22 | ||
| 23 | /* | 23 | /* |
| 24 | * Test program based on Bentley & McIlroy's "Engineering a Sort Function". | 24 | * Test program based on Bentley & McIlroy's "Engineering a Sort Function". |
| 25 | * Uses heapsort(3) to check the results. | 25 | * Additional tests include the "median of three" killer from |
| 26 | * The "killer" input is from: | 26 | * David R. Musser's "Introspective Sorting and Selection Algorithms" |
| 27 | * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html | 27 | * and 4.4BSD qsort killer input from |
| 28 | * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html | ||
| 29 | * Uses mergesort(3) to check the results. | ||
| 28 | */ | 30 | */ |
| 29 | 31 | ||
| 30 | enum distribution { | 32 | enum distribution { |
| @@ -168,7 +170,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) | |||
| 168 | ret = 1; | 170 | ret = 1; |
| 169 | } else { | 171 | } else { |
| 170 | qsort(y, n, sizeof(y[0]), cmp_checked); | 172 | qsort(y, n, sizeof(y[0]), cmp_checked); |
| 171 | heapsort(z, n, sizeof(z[0]), cmp); | 173 | if (mergesort(z, n, sizeof(z[0]), cmp) != 0) |
| 174 | err(1, NULL); | ||
| 172 | if (check_result("copy", y, z, dist, m, n) != 0) | 175 | if (check_result("copy", y, z, dist, m, n) != 0) |
| 173 | ret = 1; | 176 | ret = 1; |
| 174 | } | 177 | } |
| @@ -183,7 +186,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) | |||
| 183 | ret = 1; | 186 | ret = 1; |
| 184 | } else { | 187 | } else { |
| 185 | qsort(y, n, sizeof(y[0]), cmp_checked); | 188 | qsort(y, n, sizeof(y[0]), cmp_checked); |
| 186 | heapsort(z, n, sizeof(z[0]), cmp); | 189 | if (mergesort(z, n, sizeof(z[0]), cmp) != 0) |
| 190 | err(1, NULL); | ||
| 187 | if (check_result("reversed", y, z, dist, m, n) != 0) | 191 | if (check_result("reversed", y, z, dist, m, n) != 0) |
| 188 | ret = 1; | 192 | ret = 1; |
| 189 | } | 193 | } |
| @@ -200,7 +204,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) | |||
| 200 | ret = 1; | 204 | ret = 1; |
| 201 | } else { | 205 | } else { |
| 202 | qsort(y, n, sizeof(y[0]), cmp_checked); | 206 | qsort(y, n, sizeof(y[0]), cmp_checked); |
| 203 | heapsort(z, n, sizeof(z[0]), cmp); | 207 | if (mergesort(z, n, sizeof(z[0]), cmp) != 0) |
| 208 | err(1, NULL); | ||
| 204 | if (check_result("front reversed", y, z, dist, m, n) != 0) | 209 | if (check_result("front reversed", y, z, dist, m, n) != 0) |
| 205 | ret = 1; | 210 | ret = 1; |
| 206 | } | 211 | } |
| @@ -217,13 +222,15 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) | |||
| 217 | ret = 1; | 222 | ret = 1; |
| 218 | } else { | 223 | } else { |
| 219 | qsort(y, n, sizeof(y[0]), cmp_checked); | 224 | qsort(y, n, sizeof(y[0]), cmp_checked); |
| 220 | heapsort(z, n, sizeof(z[0]), cmp); | 225 | if (mergesort(z, n, sizeof(z[0]), cmp) != 0) |
| 226 | err(1, NULL); | ||
| 221 | if (check_result("back reversed", y, z, dist, m, n) != 0) | 227 | if (check_result("back reversed", y, z, dist, m, n) != 0) |
| 222 | ret = 1; | 228 | ret = 1; |
| 223 | } | 229 | } |
| 224 | 230 | ||
| 225 | /* Test on sorted copy of x[] */ | 231 | /* Test on sorted copy of x[] */ |
| 226 | heapsort(x, n, sizeof(x[0]), cmp); | 232 | if (mergesort(x, n, sizeof(x[0]), cmp) != 0) |
| 233 | err(1, NULL); | ||
| 227 | for (i = 0; i < n; i++) | 234 | for (i = 0; i < n; i++) |
| 228 | y[i] = x[i]; | 235 | y[i] = x[i]; |
| 229 | compares = 0; | 236 | compares = 0; |
| @@ -247,7 +254,8 @@ test_distribution(int dist, int m, int n, int *x, int *y, int *z) | |||
| 247 | ret = 1; | 254 | ret = 1; |
| 248 | } else { | 255 | } else { |
| 249 | qsort(y, n, sizeof(y[0]), cmp_checked); | 256 | qsort(y, n, sizeof(y[0]), cmp_checked); |
| 250 | heapsort(z, n, sizeof(z[0]), cmp); | 257 | if (mergesort(z, n, sizeof(z[0]), cmp) != 0) |
| 258 | err(1, NULL); | ||
| 251 | if (check_result("dithered", y, z, dist, m, n) != 0) | 259 | if (check_result("dithered", y, z, dist, m, n) != 0) |
| 252 | ret = 1; | 260 | ret = 1; |
| 253 | } | 261 | } |