summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/regress/lib/libc/qsort/qsort_test.c563
1 files changed, 421 insertions, 142 deletions
diff --git a/src/regress/lib/libc/qsort/qsort_test.c b/src/regress/lib/libc/qsort/qsort_test.c
index 03d73216bd..8ab3d9f50d 100644
--- a/src/regress/lib/libc/qsort/qsort_test.c
+++ b/src/regress/lib/libc/qsort/qsort_test.c
@@ -35,13 +35,20 @@
35 * M. D. McIlroy's "A Killer Adversary for Quicksort" 35 * M. D. McIlroy's "A Killer Adversary for Quicksort"
36 */ 36 */
37 37
38/*
39 * TODO:
40 * test with unaligned elements (char[]?)
41 */
38struct test_distribution { 42struct test_distribution {
39 const char *name; 43 const char *name;
40 void (*fill)(int *x, int n, int m); 44 void (*fill)(void *x, int n, int m);
41 int (*test)(struct test_distribution *d, int n, int *x, int *y, int *z); 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);
42}; 48};
43 49
44#define min(a, b) (((a) < (b)) ? (a) : (b)) 50#define MINIMUM(a, b) (((a) < (b)) ? (a) : (b))
51#define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b))
45 52
46static size_t compares; 53static size_t compares;
47static size_t max_compares; 54static size_t max_compares;
@@ -52,7 +59,7 @@ static bool dump_table, timing, verbose;
52extern int antiqsort(int n, int *a, int *ptr); 59extern int antiqsort(int n, int *a, int *ptr);
53 60
54static int 61static int
55cmp(const void *v1, const void *v2) 62cmp_i(const void *v1, const void *v2)
56{ 63{
57 const int a = *(const int *)v1; 64 const int a = *(const int *)v1;
58 const int b = *(const int *)v2; 65 const int b = *(const int *)v2;
@@ -61,7 +68,7 @@ cmp(const void *v1, const void *v2)
61} 68}
62 69
63static int 70static int
64cmp_checked(const void *v1, const void *v2) 71cmp_checked_i(const void *v1, const void *v2)
65{ 72{
66 const int a = *(const int *)v1; 73 const int a = *(const int *)v1;
67 const int b = *(const int *)v2; 74 const int b = *(const int *)v2;
@@ -73,7 +80,49 @@ cmp_checked(const void *v1, const void *v2)
73} 80}
74 81
75static int 82static int
76check_result(char *sub, int *got, int *expected, struct test_distribution *d, 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,
77 int m, int n) 126 int m, int n)
78{ 127{
79 int i; 128 int i;
@@ -103,8 +152,10 @@ check_result(char *sub, int *got, int *expected, struct test_distribution *d,
103 } 152 }
104 153
105 for (i = 0; i < n; i++) { 154 for (i = 0; i < n; i++) {
106 if (got[i] != expected[i]) 155 if (memcmp(got, expected, es) != 0)
107 break; 156 break;
157 got += es;
158 expected += es;
108 } 159 }
109 if (i == n) 160 if (i == n)
110 return 0; 161 return 0;
@@ -119,90 +170,228 @@ check_result(char *sub, int *got, int *expected, struct test_distribution *d,
119 return 1; 170 return 1;
120} 171}
121 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
122static void 180static void
123fill_sawtooth(int *x, int n, int m) 181fill_sawtooth_i(void *v, int n, int m)
124{ 182{
125 int i; 183 int *x = v;
184 FILL_SAWTOOTH(x, n, m);
185}
126 186
127 for (i = 0; i < n; i++) 187static void
128 x[i] = i % m; 188fill_sawtooth_ll(void *v, int n, int m)
189{
190 long long *x = v;
191 FILL_SAWTOOTH(x, n, m);
129} 192}
130 193
131static void 194static void
132fill_random(int *x, int n, int m) 195fill_sawtooth_double(void *v, int n, int m)
133{ 196{
134 int i; 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)
135 207
136 for (i = 0; i < n; i++) 208
137 x[i] = arc4random_uniform(m); 209static void
210fill_random_i(void *v, int n, int m)
211{
212 int *x = v;
213 FILL_RANDOM(x, n, m);
138} 214}
139 215
140static void 216static void
141fill_stagger(int *x, int n, int m) 217fill_random_ll(void *v, int n, int m)
142{ 218{
143 int i; 219 long long *x = v;
220 FILL_RANDOM(x, n, m);
221}
144 222
145 for (i = 0; i < n; i++) 223static void
146 x[i] = (i * m + i) % n; 224fill_random_double(void *v, int n, int m)
225{
226 double *x = v;
227 FILL_RANDOM(x, n, m);
147} 228}
148 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
149static void 238static void
150fill_plateau(int *x, int n, int m) 239fill_stagger_i(void *v, int n, int m)
151{ 240{
152 int i; 241 int *x = v;
242 FILL_STAGGER(x, n, m);
243}
153 244
154 for (i = 0; i < n; i++) 245static void
155 x[i] = min(i, m); 246fill_stagger_ll(void *v, int n, int m)
247{
248 long long *x = v;
249 FILL_STAGGER(x, n, m);
156} 250}
157 251
158static void 252static void
159fill_shuffle(int *x, int n, int m) 253fill_stagger_double(void *v, int n, int m)
160{ 254{
161 int i, j, k; 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)
162 265
163 for (i = 0, j = 0, k = 1; i < n; i++) 266static void
164 x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); 267fill_plateau_i(void *v, int n, int m)
268{
269 int *x = v;
270 FILL_PLATEAU(x, n, m);
165} 271}
166 272
167static void 273static void
168fill_bsd_killer(int *x, int n, int m) 274fill_plateau_ll(void *v, int n, int m)
169{ 275{
170 int i, k; 276 long long *x = v;
277 FILL_PLATEAU(x, n, m);
278}
171 279
172 /* 4.4BSD insertion sort optimization killer, Mats Linander */ 280static void
173 k = n / 2; 281fill_plateau_double(void *v, int n, int m)
174 for (i = 0; i < n; i++) { 282{
175 if (i < k) 283 double *x = v;
176 x[i] = k - i; 284 FILL_PLATEAU(x, n, m);
177 else if (i > k)
178 x[i] = n + k + 1 - i;
179 else
180 x[i] = k + 1;
181 }
182} 285}
183 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
184static void 294static void
185fill_med3_killer(int *x, int n, int m) 295fill_shuffle_i(void *v, int n, int m)
186{ 296{
187 int i, k; 297 int *x = v;
298 FILL_SHUFFLE(x, n, m);
299}
188 300
189 /* 301static void
190 * Median of 3 killer, as seen in David R Musser's 302fill_shuffle_ll(void *v, int n, int m)
191 * "Introspective Sorting and Selection Algorithms" 303{
192 */ 304 long long *x = v;
193 if (n & 1) { 305 FILL_SHUFFLE(x, n, m);
194 /* odd size, store last at end and make even. */ 306}
195 x[n - 1] = n; 307
196 n--; 308static void
197 } 309fill_shuffle_double(void *v, int n, int m)
198 k = n / 2; 310{
199 for (i = 0; i < n; i++) { 311 double *x = v;
200 if (i & 1) { 312 FILL_SHUFFLE(x, n, m);
201 x[i] = k + x[i - 1]; 313}
202 } else { 314
203 x[i] = i + 1; 315#define FILL_BSD_KILLER(x, n, m) do { \
204 } 316 int i, k; \
205 } 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);
206} 395}
207 396
208static void 397static void
@@ -228,7 +417,7 @@ print_timing(struct test_distribution *d, char *sub, int m, int n, double elapse
228} 417}
229 418
230static int 419static int
231do_test(struct test_distribution *d, char *sub, int m, int n, int *y, int *z) 420do_test(struct test_distribution *d, char *sub, int m, int n, size_t es, void *y, void *z)
232{ 421{
233 int ret = 0; 422 int ret = 0;
234 struct timespec before, after; 423 struct timespec before, after;
@@ -246,7 +435,7 @@ do_test(struct test_distribution *d, char *sub, int m, int n, int *y, int *z)
246 } else { 435 } else {
247 if (timing) 436 if (timing)
248 clock_gettime(CLOCK_MONOTONIC, &before); 437 clock_gettime(CLOCK_MONOTONIC, &before);
249 qsort(y, n, sizeof(y[0]), cmp_checked); 438 qsort(y, n, es, d->cmp_checked);
250 if (timing) { 439 if (timing) {
251 double elapsed; 440 double elapsed;
252 clock_gettime(CLOCK_MONOTONIC, &after); 441 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)
254 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0; 443 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0;
255 print_timing(d, sub, m, n, elapsed); 444 print_timing(d, sub, m, n, elapsed);
256 } 445 }
257 if (check_result(sub, y, z, d, m, n) != 0) 446 if (check_result(sub, es, y, z, d, m, n) != 0)
258 ret = 1; 447 ret = 1;
259 } 448 }
260 return ret; 449 return ret;
261} 450}
262 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
263static int 514static int
264test_perturbed(struct test_distribution *d, int n, int *x, int *y, int *z) 515test_perturbed_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
265{ 516{
266 int i, j, m; 517 int *x = vx;
518 int *y = vx;
519 int *z = vz;
267 int ret = 0; 520 int ret = 0;
268 521
269 for (m = 1; m < 2 * n; m *= 2) { 522 TEST_PERTURBED(d, n, x, y, z);
270 /* Fill in x[n] modified by m */ 523 return ret;
271 d->fill(x, n, m); 524}
272
273 /* Test on copy of x[] */
274 for (i = 0; i < n; i++)
275 y[i] = z[i] = x[i];
276 if (mergesort(z, n, sizeof(z[0]), cmp) != 0)
277 err(1, NULL);
278 if (do_test(d, "copy", m, n, y, z) != 0)
279 ret = 1;
280
281 /* Test on reversed copy of x[] */
282 for (i = 0, j = n - 1; i < n; i++, j--)
283 y[i] = z[i] = x[j];
284 if (mergesort(z, n, sizeof(z[0]), cmp) != 0)
285 err(1, NULL);
286 if (do_test(d, "reversed", m, n, y, z) != 0)
287 ret = 1;
288
289 /* Test with front half of x[] reversed */
290 for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--)
291 y[i] = z[i] = x[j];
292 for (; i < n; i++)
293 y[i] = z[i] = x[i];
294 if (mergesort(z, n, sizeof(z[0]), cmp) != 0)
295 err(1, NULL);
296 if (do_test(d, "front reversed", m, n, y, z) != 0)
297 ret = 1;
298 525
299 /* Test with back half of x[] reversed */ 526static int
300 for (i = 0; i < n / 2; i++) 527test_perturbed_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
301 y[i] = z[i] = x[i]; 528{
302 for (j = n - 1; i < n; i++, j--) 529 long long *x = vx;
303 y[i] = z[i] = x[j]; 530 long long *y = vx;
304 if (mergesort(z, n, sizeof(z[0]), cmp) != 0) 531 long long *z = vz;
305 err(1, NULL); 532 int ret = 0;
306 if (do_test(d, "back reversed", m, n, y, z) != 0)
307 ret = 1;
308 533
309 /* Test on sorted copy of x[] */ 534 TEST_PERTURBED(d, n, x, y, z);
310 if (mergesort(x, n, sizeof(x[0]), cmp) != 0) 535 return ret;
311 err(1, NULL); 536}
312 for (i = 0; i < n; i++)
313 y[i] = x[i];
314 if (do_test(d, "sorted", m, n, y, x) != 0)
315 ret = 1;
316 537
317 /* Test with i%5 added to x[i] (dither) */ 538static int
318 for (i = 0, j = n - 1; i < n; i++, j--) 539test_perturbed_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
319 y[i] = z[i] = x[j] + (i % 5); 540{
320 if (mergesort(z, n, sizeof(z[0]), cmp) != 0) 541 double *x = vx;
321 err(1, NULL); 542 double *y = vx;
322 if (do_test(d, "front reversed", m, n, y, z) != 0) 543 double *z = vz;
323 ret = 1; 544 int ret = 0;
324 }
325 545
546 TEST_PERTURBED(d, n, x, y, z);
326 return ret; 547 return ret;
327} 548}
328 549
329/* 550/*
330 * Like test_perturbed() but because the input is tailored to cause 551 * Like TEST_PERTURBED but because the input is tailored to cause
331 * quicksort to go quadratic we don't perturb the input. 552 * quicksort to go quadratic we don't perturb the input.
332 */ 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
333static int 569static int
334test_simple(struct test_distribution *d, int n, int *x, int *y, int *z) 570test_simple_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
335{ 571{
336 int i, ret = 0; 572 int *x = vx;
573 int *y = vx;
574 int *z = vz;
575 int ret = 0;
337 576
338 /* Fill in x[n] */ 577 TEST_SIMPLE(d, n, x, y, z);
339 d->fill(x, n, 0); 578 return ret;
579}
340 580
341 /* Make a copy of x[] */ 581static int
342 for (i = 0; i < n; i++) 582test_simple_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
343 y[i] = z[i] = x[i]; 583{
344 if (mergesort(z, n, sizeof(z[0]), cmp) != 0) 584 long long *x = vx;
345 err(1, NULL); 585 long long *y = vx;
346 if (do_test(d, NULL, 0, n, y, z) != 0) 586 long long *z = vz;
347 ret = 1; 587 int ret = 0;
348 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);
349 return ret; 602 return ret;
350} 603}
351 604
@@ -354,9 +607,11 @@ test_simple(struct test_distribution *d, int n, int *x, int *y, int *z)
354 * We don't compare the results in this case. 607 * We don't compare the results in this case.
355 */ 608 */
356static int 609static int
357test_antiqsort(struct test_distribution *d, int n, int *x, int *y, int *z) 610test_antiqsort(struct test_distribution *d, int n, void *vx, void *vy, void *vz)
358{ 611{
359 struct timespec before, after; 612 struct timespec before, after;
613 int *x = vx;
614 int *y = vx;
360 int i, ret = 0; 615 int i, ret = 0;
361 616
362 /* 617 /*
@@ -396,23 +651,38 @@ test_antiqsort(struct test_distribution *d, int n, int *x, int *y, int *z)
396} 651}
397 652
398static struct test_distribution distributions[] = { 653static struct test_distribution distributions[] = {
399 { "sawtooth", fill_sawtooth, test_perturbed }, 654 { "sawtooth_i", fill_sawtooth_i, test_perturbed_i, cmp_i, cmp_checked_i },
400 { "random", fill_random, test_perturbed }, 655 { "sawtooth_ll", fill_sawtooth_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
401 { "stagger", fill_stagger, test_perturbed }, 656 { "sawtooth_d", fill_sawtooth_double, test_perturbed_double, cmp_d, cmp_checked_d },
402 { "plateau", fill_plateau, test_perturbed }, 657 { "random_i", fill_random_i, test_perturbed_i, cmp_i, cmp_checked_i },
403 { "shuffle", fill_shuffle, test_perturbed }, 658 { "random_ll", fill_random_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll },
404 { "bsd_killer", fill_bsd_killer, test_simple }, 659 { "random_d", fill_random_double, test_perturbed_double, cmp_d, cmp_checked_d },
405 { "med3_killer", fill_med3_killer, test_simple }, 660 { "stagger_i", fill_stagger_i, test_perturbed_i, cmp_i, cmp_checked_i },
406 { "antiqsort", NULL, test_antiqsort }, 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 },
407 { NULL } 676 { NULL }
408}; 677};
409 678
410static int 679static int
411run_tests(int n, const char *name) 680run_tests(int n, const char *name)
412{ 681{
413 int *x, *y, *z; 682 void *x, *y, *z;
414 int i, nlgn = 0; 683 int i, nlgn = 0;
415 int ret = 0; 684 int ret = 0;
685 size_t es;
416 struct test_distribution *d; 686 struct test_distribution *d;
417 687
418 /* 688 /*
@@ -426,14 +696,16 @@ run_tests(int n, const char *name)
426 max_compares = nlgn * 1.5; 696 max_compares = nlgn * 1.5;
427 abrt_compares = nlgn * 10; 697 abrt_compares = nlgn * 10;
428 698
429 x = reallocarray(NULL, n, sizeof(x[0])); 699 /* Allocate enough space to store ints or doubles. */
430 y = reallocarray(NULL, n, sizeof(y[0])); 700 es = MAXIMUM(sizeof(int), sizeof(double));
431 z = reallocarray(NULL, n, sizeof(z[0])); 701 x = reallocarray(NULL, n, es);
702 y = reallocarray(NULL, n, es);
703 z = reallocarray(NULL, n, es);
432 if (x == NULL || y == NULL || z == NULL) 704 if (x == NULL || y == NULL || z == NULL)
433 err(1, NULL); 705 err(1, NULL);
434 706
435 for (d = distributions; d->name != NULL; d++) { 707 for (d = distributions; d->name != NULL; d++) {
436 if (name != NULL && strcmp(name, d->name) != 0) 708 if (name != NULL && strncmp(name, d->name, strlen(name)) != 0)
437 continue; 709 continue;
438 if (d->test(d, n, x, y, z) != 0) 710 if (d->test(d, n, x, y, z) != 0)
439 ret = 1; 711 ret = 1;
@@ -456,6 +728,7 @@ int
456main(int argc, char *argv[]) 728main(int argc, char *argv[])
457{ 729{
458 char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" }; 730 char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" };
731 struct test_distribution *d;
459 int ch, n, ret = 0; 732 int ch, n, ret = 0;
460 char *name = NULL; 733 char *name = NULL;
461 734
@@ -465,6 +738,12 @@ main(int argc, char *argv[])
465 dump_table = true; 738 dump_table = true;
466 break; 739 break;
467 case 'n': 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);
468 name = optarg; 747 name = optarg;
469 break; 748 break;
470 case 't': 749 case 't':
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-20 13:33:57 +0000