summaryrefslogtreecommitdiff
path: root/src/regress/lib/libc/qsort
diff options
context:
space:
mode:
Diffstat (limited to 'src/regress/lib/libc/qsort')
-rw-r--r--src/regress/lib/libc/qsort/Makefile13
-rw-r--r--src/regress/lib/libc/qsort/antiqsort.c58
-rw-r--r--src/regress/lib/libc/qsort/qsort_test.c777
3 files changed, 0 insertions, 848 deletions
diff --git a/src/regress/lib/libc/qsort/Makefile b/src/regress/lib/libc/qsort/Makefile
deleted file mode 100644
index 473432f423..0000000000
--- a/src/regress/lib/libc/qsort/Makefile
+++ /dev/null
@@ -1,13 +0,0 @@
1# $OpenBSD: Makefile,v 1.3 2017/05/22 17:16:43 millert Exp $
2
3PROG= qsort_test
4SRCS= qsort_test.c antiqsort.c
5CFLAGS+=-Wall
6
7qsort-regress: ${PROG}
8 ./${PROG}
9
10REGRESS_TARGETS=qsort-regress
11.PHONY: ${REGRESS_TARGETS}
12
13.include <bsd.regress.mk>
diff --git a/src/regress/lib/libc/qsort/antiqsort.c b/src/regress/lib/libc/qsort/antiqsort.c
deleted file mode 100644
index cb3b7b2525..0000000000
--- a/src/regress/lib/libc/qsort/antiqsort.c
+++ /dev/null
@@ -1,58 +0,0 @@
1/*
2 * A Killer Adversary for Quicksort
3 * M. D. MCILROY
4 * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
5 *
6 * For comparison:
7 * Bentley & McIlroy: 4096 items, 1645585 compares
8 * random pivot: 4096 items, 8388649 compares
9 * introsort: 4096 items, 151580 compares
10 * heapsort: 4096 items, 48233 compares
11 */
12
13#include <stdio.h>
14#include <stdlib.h>
15
16static int *val; /* item values */
17static int ncmp; /* number of comparisons */
18static int nsolid; /* number of solid items */
19static int candidate; /* pivot candidate */
20static int gas; /* gas value */
21
22#define freeze(x) (val[(x)] = nsolid++)
23
24static int
25cmp(const void *px, const void *py)
26{
27 const int x = *(const int *)px;
28 const int y = *(const int *)py;
29
30 ncmp++;
31 if (val[x] == gas && val[y] == gas) {
32 if (x == candidate)
33 freeze(x);
34 else
35 freeze(y);
36 }
37 if (val[x] == gas)
38 candidate = x;
39 else if (val[y] == gas)
40 candidate = y;
41 return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0;
42}
43
44int
45antiqsort(int n, int *a, int *ptr)
46{
47 int i;
48
49 val = a;
50 gas = n - 1;
51 nsolid = ncmp = candidate = 0;
52 for (i = 0; i < n; i++) {
53 ptr[i] = i;
54 val[i] = gas;
55 }
56 qsort(ptr, n, sizeof(*ptr), cmp);
57 return ncmp;
58}
diff --git a/src/regress/lib/libc/qsort/qsort_test.c b/src/regress/lib/libc/qsort/qsort_test.c
deleted file mode 100644
index 352c707718..0000000000
--- a/src/regress/lib/libc/qsort/qsort_test.c
+++ /dev/null
@@ -1,777 +0,0 @@
1/*
2 * Copyright (c) 2017 Todd C. Miller <millert@openbsd.org>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17#include <sys/time.h>
18
19#include <stdbool.h>
20#include <stdio.h>
21#include <stdlib.h>
22#include <string.h>
23#include <setjmp.h>
24#include <time.h>
25#include <unistd.h>
26#include <err.h>
27
28/*
29 * Test program based on Bentley & McIlroy's "Engineering a Sort Function".
30 * Uses mergesort(3) to check the results.
31 *
32 * Additional "killer" input taken from:
33 * David R. Musser's "Introspective Sorting and Selection Algorithms"
34 * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
35 * M. D. McIlroy's "A Killer Adversary for Quicksort"
36 */
37
38/*
39 * TODO:
40 * test with unaligned elements (char[]?)
41 */
42struct test_distribution {
43 const char *name;
44 void (*fill)(void *x, int n, int m);
45 int (*test)(struct test_distribution *d, int n, void *x, void *y, void *z);
46 int (*cmp)(const void *v1, const void *v2);
47 int (*cmp_checked)(const void *v1, const void *v2);
48};
49
50#define MINIMUM(a, b) (((a) < (b)) ? (a) : (b))
51#define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b))
52
53static size_t compares;
54static size_t max_compares;
55static size_t abrt_compares;
56static sigjmp_buf cmpjmp;
57static bool dump_table, timing, verbose;
58
59extern int antiqsort(int n, int *a, int *ptr);
60
61static int
62cmp_i(const void *v1, const void *v2)
63{
64 const int a = *(const int *)v1;
65 const int b = *(const int *)v2;
66
67 return a > b ? 1 : a < b ? -1 : 0;
68}
69
70static int
71cmp_checked_i(const void *v1, const void *v2)
72{
73 const int a = *(const int *)v1;
74 const int b = *(const int *)v2;
75
76 compares++;
77 if (compares > abrt_compares)
78 siglongjmp(cmpjmp, 1);
79 return a > b ? 1 : a < b ? -1 : 0;
80}
81
82static int
83cmp_ll(const void *v1, const void *v2)
84{
85 const long long a = *(const long long *)v1;
86 const long long b = *(const long long *)v2;
87
88 return a > b ? 1 : a < b ? -1 : 0;
89}
90
91static int
92cmp_checked_ll(const void *v1, const void *v2)
93{
94 const long long a = *(const long long *)v1;
95 const long long b = *(const long long *)v2;
96
97 compares++;
98 if (compares > abrt_compares)
99 siglongjmp(cmpjmp, 1);
100 return a > b ? 1 : a < b ? -1 : 0;
101}
102
103static int
104cmp_d(const void *v1, const void *v2)
105{
106 const double a = *(const double *)v1;
107 const double b = *(const double *)v2;
108
109 return a > b ? 1 : a < b ? -1 : 0;
110}
111
112static int
113cmp_checked_d(const void *v1, const void *v2)
114{
115 const double a = *(const double *)v1;
116 const double b = *(const double *)v2;
117
118 compares++;
119 if (compares > abrt_compares)
120 siglongjmp(cmpjmp, 1);
121 return a > b ? 1 : a < b ? -1 : 0;
122}
123
124static int
125check_result(char *sub, size_t es, char *got, char *expected, struct test_distribution *d,
126 int m, int n)
127{
128 int i;
129
130 if (verbose || compares > max_compares) {
131 if (sub != NULL) {
132 if (m != 0) {
133 warnx("%s (%s): m: %d, n: %d, %zu compares, "
134 "max %zu(%zu)", d->name, sub, m, n,
135 compares, max_compares, abrt_compares);
136 } else {
137 warnx("%s (%s): n: %d, %zu compares, "
138 "max %zu(%zu)", d->name, sub, n,
139 compares, max_compares, abrt_compares);
140 }
141 } else {
142 if (m != 0) {
143 warnx("%s: m: %d, n: %d, %zu compares, "
144 "max %zu(%zu)", d->name, m, n,
145 compares, max_compares, abrt_compares);
146 } else {
147 warnx("%s: n: %d, %zu compares, "
148 "max %zu(%zu)", d->name, n,
149 compares, max_compares, abrt_compares);
150 }
151 }
152 }
153
154 for (i = 0; i < n; i++) {
155 if (memcmp(got, expected, es) != 0)
156 break;
157 got += es;
158 expected += es;
159 }
160 if (i == n)
161 return 0;
162
163 if (sub != NULL) {
164 warnx("%s (%s): failure at %d, m: %d, n: %d",
165 d->name, sub, i, m, n);
166 } else {
167 warnx("%s: failure at %d, m: %d, n: %d",
168 d->name, i, m, n);
169 }
170 return 1;
171}
172
173#define FILL_SAWTOOTH(x, n, m) do { \
174 int i; \
175 \
176 for (i = 0; i < n; i++) \
177 x[i] = i % m; \
178} while (0)
179
180static void
181fill_sawtooth_i(void *v, int n, int m)
182{
183 int *x = v;
184 FILL_SAWTOOTH(x, n, m);
185}
186
187static void
188fill_sawtooth_ll(void *v, int n, int m)
189{
190 long long *x = v;
191 FILL_SAWTOOTH(x, n, m);
192}
193
194static void
195fill_sawtooth_double(void *v, int n, int m)
196{
197 double *x = v;
198 FILL_SAWTOOTH(x, n, m);
199}
200
201#define FILL_RANDOM(x, n, m) do { \
202 int i; \
203 \
204 for (i = 0; i < n; i++) \
205 x[i] = arc4random_uniform(m); \
206} while (0)
207
208
209static void
210fill_random_i(void *v, int n, int m)
211{
212 int *x = v;
213 FILL_RANDOM(x, n, m);
214}
215
216static void
217fill_random_ll(void *v, int n, int m)
218{
219 long long *x = v;
220 FILL_RANDOM(x, n, m);
221}
222
223static void
224fill_random_double(void *v, int n, int m)
225{
226 double *x = v;
227 FILL_RANDOM(x, n, m);
228}
229
230#define FILL_STAGGER(x, n, m) do { \
231 int i; \
232 \
233 for (i = 0; i < n; i++) \
234 x[i] = (i * m + i) % n; \
235} while (0)
236
237
238static void
239fill_stagger_i(void *v, int n, int m)
240{
241 int *x = v;
242 FILL_STAGGER(x, n, m);
243}
244
245static void
246fill_stagger_ll(void *v, int n, int m)
247{
248 long long *x = v;
249 FILL_STAGGER(x, n, m);
250}
251
252static void
253fill_stagger_double(void *v, int n, int m)
254{
255 double *x = v;
256 FILL_STAGGER(x, n, m);
257}
258
259#define FILL_PLATEAU(x, n, m) do { \
260 int i; \
261 \
262 for (i = 0; i < n; i++) \
263 x[i] = MINIMUM(i, m); \
264} while (0)
265
266static void
267fill_plateau_i(void *v, int n, int m)
268{
269 int *x = v;
270 FILL_PLATEAU(x, n, m);
271}
272
273static void
274fill_plateau_ll(void *v, int n, int m)
275{
276 long long *x = v;
277 FILL_PLATEAU(x, n, m);
278}
279
280static void
281fill_plateau_double(void *v, int n, int m)
282{
283 double *x = v;
284 FILL_PLATEAU(x, n, m);
285}
286
287#define FILL_SHUFFLE(x, n, m) do { \
288 int i, j, k; \
289 \
290 for (i = 0, j = 0, k = 1; i < n; i++) \
291 x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); \
292} while (0)
293
294static void
295fill_shuffle_i(void *v, int n, int m)
296{
297 int *x = v;
298 FILL_SHUFFLE(x, n, m);
299}
300
301static void
302fill_shuffle_ll(void *v, int n, int m)
303{
304 long long *x = v;
305 FILL_SHUFFLE(x, n, m);
306}
307
308static void
309fill_shuffle_double(void *v, int n, int m)
310{
311 double *x = v;
312 FILL_SHUFFLE(x, n, m);
313}
314
315#define FILL_BSD_KILLER(x, n, m) do { \
316 int i, k; \
317 \
318 /* 4.4BSD insertion sort optimization killer, Mats Linander */ \
319 k = n / 2; \
320 for (i = 0; i < n; i++) { \
321 if (i < k) \
322 x[i] = k - i; \
323 else if (i > k) \
324 x[i] = n + k + 1 - i; \
325 else \
326 x[i] = k + 1; \
327 } \
328} while (0)
329
330static void
331fill_bsd_killer_i(void *v, int n, int m)
332{
333 int *x = v;
334 FILL_BSD_KILLER(x, n, m);
335
336}
337
338static void
339fill_bsd_killer_ll(void *v, int n, int m)
340{
341 long long *x = v;
342 FILL_BSD_KILLER(x, n, m);
343
344}
345
346static void
347fill_bsd_killer_double(void *v, int n, int m)
348{
349 double *x = v;
350 FILL_BSD_KILLER(x, n, m);
351
352}
353
354#define FILL_MED3_KILLER(x, n, m) do { \
355 int i, k; \
356 \
357 /* \
358 * Median of 3 killer, as seen in David R Musser's \
359 * "Introspective Sorting and Selection Algorithms" \
360 */ \
361 if (n & 1) { \
362 /* odd size, store last at end and make even. */ \
363 x[n - 1] = n; \
364 n--; \
365 } \
366 k = n / 2; \
367 for (i = 0; i < n; i++) { \
368 if (i & 1) { \
369 x[i] = k + x[i - 1]; \
370 } else { \
371 x[i] = i + 1; \
372 } \
373 } \
374} while (0)
375
376static void
377fill_med3_killer_i(void *v, int n, int m)
378{
379 int *x = v;
380 FILL_MED3_KILLER(x, n, m);
381}
382
383static void
384fill_med3_killer_ll(void *v, int n, int m)
385{
386 long long *x = v;
387 FILL_MED3_KILLER(x, n, m);
388}
389
390static void
391fill_med3_killer_double(void *v, int n, int m)
392{
393 double *x = v;
394 FILL_MED3_KILLER(x, n, m);
395}
396
397static void
398print_timing(struct test_distribution *d, char *sub, int m, int n, double elapsed)
399{
400 if (sub != NULL) {
401 if (m != 0) {
402 warnx("%s (%s): m: %d, n: %d, %f seconds",
403 d->name, sub, m, n, elapsed);
404 } else {
405 warnx("%s (%s): n: %d, %f seconds",
406 d->name, sub, n, elapsed);
407 }
408 } else {
409 if (m != 0) {
410 warnx("%s: m: %d, n: %d, %f seconds",
411 d->name, m, n, elapsed);
412 } else {
413 warnx("%s: n: %d, %f seconds",
414 d->name, n, elapsed);
415 }
416 }
417}
418
419static int
420do_test(struct test_distribution *d, char *sub, int m, int n, size_t es, void *y, void *z)
421{
422 int ret = 0;
423 struct timespec before, after;
424
425 compares = 0;
426 if (sigsetjmp(cmpjmp, 1) != 0) {
427 if (sub != NULL) {
428 warnx("%s (%s): qsort aborted after %zu compares, m: %d, n: %d",
429 d->name, sub, compares, m, n);
430 } else {
431 warnx("%s: qsort aborted after %zu compares, m: %d, n: %d",
432 d->name, compares, m, n);
433 }
434 ret = 1;
435 } else {
436 if (timing)
437 clock_gettime(CLOCK_MONOTONIC, &before);
438 qsort(y, n, es, d->cmp_checked);
439 if (timing) {
440 double elapsed;
441 clock_gettime(CLOCK_MONOTONIC, &after);
442 timespecsub(&after, &before, &after);
443 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0;
444 print_timing(d, sub, m, n, elapsed);
445 }
446 if (check_result(sub, es, y, z, d, m, n) != 0)
447 ret = 1;
448 }
449 return ret;
450}
451
452#define TEST_PERTURBED(d, n, x, y, z) do { \
453 int i, j, m; \
454 const int es = sizeof(x[0]); \
455 \
456 for (m = 1; m < 2 * n; m *= 2) { \
457 /* Fill in x[n] modified by m */ \
458 d->fill(x, n, m); \
459 \
460 /* Test on copy of x[] */ \
461 for (i = 0; i < n; i++) \
462 y[i] = z[i] = x[i]; \
463 if (mergesort(z, n, es, d->cmp) != 0) \
464 err(1, NULL); \
465 if (do_test(d, "copy", m, n, es, y, z) != 0) \
466 ret = 1; \
467 \
468 /* Test on reversed copy of x[] */ \
469 for (i = 0, j = n - 1; i < n; i++, j--) \
470 y[i] = z[i] = x[j]; \
471 if (mergesort(z, n, es, d->cmp) != 0) \
472 err(1, NULL); \
473 if (do_test(d, "reversed", m, n, es, y, z) != 0) \
474 ret = 1; \
475 \
476 /* Test with front half of x[] reversed */ \
477 for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--) \
478 y[i] = z[i] = x[j]; \
479 for (; i < n; i++) \
480 y[i] = z[i] = x[i]; \
481 if (mergesort(z, n, es, d->cmp) != 0) \
482 err(1, NULL); \
483 if (do_test(d, "front reversed", m, n, es, y, z) != 0) \
484 ret = 1; \
485 \
486 /* Test with back half of x[] reversed */ \
487 for (i = 0; i < n / 2; i++) \
488 y[i] = z[i] = x[i]; \
489 for (j = n - 1; i < n; i++, j--) \
490 y[i] = z[i] = x[j]; \
491 if (mergesort(z, n, es, d->cmp) != 0) \
492 err(1, NULL); \
493 if (do_test(d, "back reversed", m, n, es, y, z) != 0) \
494 ret = 1; \
495 \
496 /* Test on sorted copy of x[] */ \
497 if (mergesort(x, n, es, d->cmp) != 0) \
498 err(1, NULL); \
499 for (i = 0; i < n; i++) \
500 y[i] = x[i]; \
501 if (do_test(d, "sorted", m, n, es, y, x) != 0) \
502 ret = 1; \
503 \
504 /* Test with i%5 added to x[i] (dither) */ \
505 for (i = 0, j = n - 1; i < n; i++, j--) \
506 y[i] = z[i] = x[j] + (i % 5); \
507 if (mergesort(z, n, es, d->cmp) != 0) \
508 err(1, NULL); \
509 if (do_test(d, "dithered", m, n, es, y, z) != 0) \
510 ret = 1; \
511 } \
512} while (0)
513
514static int
515test_perturbed_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
516{
517 int *x = vx;
518 int *y = vx;
519 int *z = vz;
520 int ret = 0;
521
522 TEST_PERTURBED(d, n, x, y, z);
523 return ret;
524}
525
526static int
527test_perturbed_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
528{
529 long long *x = vx;
530 long long *y = vx;
531 long long *z = vz;
532 int ret = 0;
533
534 TEST_PERTURBED(d, n, x, y, z);
535 return ret;
536}
537
538static int
539test_perturbed_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
540{
541 double *x = vx;
542 double *y = vx;
543 double *z = vz;
544 int ret = 0;
545
546 TEST_PERTURBED(d, n, x, y, z);
547 return ret;
548}
549
550/*
551 * Like TEST_PERTURBED but because the input is tailored to cause
552 * quicksort to go quadratic we don't perturb the input.
553 */
554#define TEST_SIMPLE(d, n, x, y, z) do { \
555 int i, ret = 0; \
556 \
557 /* Fill in x[n] */ \
558 d->fill(x, n, 0); \
559 \
560 /* Make a copy of x[] */ \
561 for (i = 0; i < n; i++) \
562 y[i] = z[i] = x[i]; \
563 if (mergesort(z, n, sizeof(z[0]), d->cmp) != 0) \
564 err(1, NULL); \
565 if (do_test(d, NULL, 0, n, sizeof(x[0]), y, z) != 0) \
566 ret = 1; \
567} while (0)
568
569static int
570test_simple_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
571{
572 int *x = vx;
573 int *y = vx;
574 int *z = vz;
575 int ret = 0;
576
577 TEST_SIMPLE(d, n, x, y, z);
578 return ret;
579}
580
581static int
582test_simple_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
583{
584 long long *x = vx;
585 long long *y = vx;
586 long long *z = vz;
587 int ret = 0;
588
589 TEST_SIMPLE(d, n, x, y, z);
590 return ret;
591}
592
593static int
594test_simple_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
595{
596 double *x = vx;
597 double *y = vx;
598 double *z = vz;
599 int ret = 0;
600
601 TEST_SIMPLE(d, n, x, y, z);
602 return ret;
603}
604
605/*
606 * Use D. McIlroy's "Killer Adversary for Quicksort"
607 * We don't compare the results in this case.
608 */
609static int
610test_antiqsort(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
611{
612 struct timespec before, after;
613 int *x = vx;
614 int *y = vx;
615 int i, ret = 0;
616
617 /*
618 * We expect antiqsort to generate > 1.5 * nlgn compares.
619 * If introspection is not used, it will be > 10 * nlgn compares.
620 */
621 if (timing)
622 clock_gettime(CLOCK_MONOTONIC, &before);
623 i = antiqsort(n, x, y);
624 if (timing)
625 clock_gettime(CLOCK_MONOTONIC, &after);
626 if (i > abrt_compares)
627 ret = 1;
628 if (dump_table) {
629 printf("/* %d items, %d compares */\n", n, i);
630 printf("static const int table_%d[] = {", n);
631 for (i = 0; i < n - 1; i++) {
632 if ((i % 12) == 0)
633 printf("\n\t");
634 printf("%4d, ", x[i]);
635 }
636 printf("%4d\n};\n", x[i]);
637 } else {
638 if (timing) {
639 double elapsed;
640 timespecsub(&after, &before, &after);
641 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0;
642 print_timing(d, NULL, 0, n, elapsed);
643 }
644 if (verbose || ret != 0) {
645 warnx("%s: n: %d, %d compares, max %zu(%zu)",
646 d->name, n, i, max_compares, abrt_compares);
647 }
648 }
649
650 return ret;
651}
652
653static struct test_distribution distributions[] = {
654 { "sawtooth_i", fill_sawtooth_i, test_perturbed_i, cmp_i, cmp_checked_i },
655 { "sawtooth_ll", fill_sawtooth_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
656 { "sawtooth_d", fill_sawtooth_double, test_perturbed_double, cmp_d, cmp_checked_d },
657 { "random_i", fill_random_i, test_perturbed_i, cmp_i, cmp_checked_i },
658 { "random_ll", fill_random_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
659 { "random_d", fill_random_double, test_perturbed_double, cmp_d, cmp_checked_d },
660 { "stagger_i", fill_stagger_i, test_perturbed_i, cmp_i, cmp_checked_i },
661 { "stagger_ll", fill_stagger_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
662 { "stagger_d", fill_stagger_double, test_perturbed_double, cmp_d, cmp_checked_d },
663 { "plateau_i", fill_plateau_i, test_perturbed_i, cmp_i, cmp_checked_i },
664 { "plateau_ll", fill_plateau_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
665 { "plateau_d", fill_plateau_double, test_perturbed_double, cmp_d, cmp_checked_d },
666 { "shuffle_i", fill_shuffle_i, test_perturbed_i, cmp_i, cmp_checked_i },
667 { "shuffle_ll", fill_shuffle_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
668 { "shuffle_d", fill_shuffle_double, test_perturbed_double, cmp_d, cmp_checked_d },
669 { "bsd_killer_i", fill_bsd_killer_i, test_simple_i, cmp_i, cmp_checked_i },
670 { "bsd_killer_ll", fill_bsd_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll },
671 { "bsd_killer_d", fill_bsd_killer_double, test_simple_double, cmp_d, cmp_checked_d },
672 { "med3_killer_i", fill_med3_killer_i, test_simple_i, cmp_i, cmp_checked_i },
673 { "med3_killer_ll", fill_med3_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll },
674 { "med3_killer_d", fill_med3_killer_double, test_simple_double, cmp_d, cmp_checked_d },
675 { "antiqsort", NULL, test_antiqsort, cmp_i, cmp_checked_i },
676 { NULL }
677};
678
679static int
680run_tests(int n, const char *name)
681{
682 void *x, *y, *z;
683 int i, nlgn = 0;
684 int ret = 0;
685 size_t es;
686 struct test_distribution *d;
687
688 /*
689 * We expect A*n*lg(n) compares where A is between 1 and 2.
690 * For A > 1.5, print a warning.
691 * For A > 10 abort the test since qsort has probably gone quadratic.
692 */
693 for (i = n - 1; i > 0; i >>= 1)
694 nlgn++;
695 nlgn *= n;
696 max_compares = nlgn * 1.5;
697 abrt_compares = nlgn * 10;
698
699 /* Allocate enough space to store ints or doubles. */
700 es = MAXIMUM(sizeof(int), sizeof(double));
701 x = reallocarray(NULL, n, es);
702 y = reallocarray(NULL, n, es);
703 z = reallocarray(NULL, n, es);
704 if (x == NULL || y == NULL || z == NULL)
705 err(1, NULL);
706
707 for (d = distributions; d->name != NULL; d++) {
708 if (name != NULL && strncmp(name, d->name, strlen(name)) != 0)
709 continue;
710 if (d->test(d, n, x, y, z) != 0)
711 ret = 1;
712 }
713
714 free(x);
715 free(y);
716 free(z);
717 return ret;
718}
719
720__dead void
721usage(void)
722{
723 fprintf(stderr, "usage: qsort_test [-dvt] [-n test_name] [num ...]\n");
724 exit(1);
725}
726
727int
728main(int argc, char *argv[])
729{
730 char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" };
731 struct test_distribution *d;
732 int ch, n, ret = 0;
733 char *name = NULL;
734
735 while ((ch = getopt(argc, argv, "dn:tv")) != -1) {
736 switch (ch) {
737 case 'd':
738 dump_table = true;
739 break;
740 case 'n':
741 for (d = distributions; d->name != NULL; d++) {
742 if (strncmp(optarg, d->name, strlen(optarg)) == 0)
743 break;
744 }
745 if (d->name == NULL)
746 errx(1, "unknown test %s", optarg);
747 name = optarg;
748 break;
749 case 't':
750 timing = true;
751 break;
752 case 'v':
753 verbose = true;
754 break;
755 default:
756 usage();
757 break;
758 }
759 }
760 argc -= optind;
761 argv += optind;
762
763 if (argc == 0) {
764 argv = nums;
765 argc = sizeof(nums) / sizeof(nums[0]);
766 }
767
768 while (argc > 0) {
769 n = atoi(*argv);
770 if (run_tests(n, name) != 0)
771 ret = 1;
772 argc--;
773 argv++;
774 }
775
776 return ret;
777}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-21 13:53:38 +0000