1 /* Test the heapsort implementation behind qsort.
2 Copyright (C) 2023-2024 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <http://www.gnu.org/licenses/>. */
22 #include <support/check.h>
23 #include <support/support.h>
26 cmp (const void *a1
, const void *b1
, void *closure
)
28 const signed char *a
= a1
;
29 const signed char *b
= b1
;
34 check_one_sort (signed char *array
, int length
)
36 signed char *copy
= xmalloc (length
);
37 memcpy (copy
, array
, length
);
38 heapsort_r (copy
, length
- 1, 1, cmp
, NULL
);
40 /* Verify that the result is sorted. */
41 for (int i
= 1; i
< length
; ++i
)
42 if (copy
[i
] < copy
[i
- 1])
44 support_record_failure ();
45 printf ("error: sorting failure for length %d at offset %d\n",
48 for (int i
= 0; i
< length
; ++i
)
49 printf (" %d", array
[i
]);
51 for (int i
= 0; i
< length
; ++i
)
52 printf (" %d", copy
[i
]);
57 /* Verify that no elements went away or were added. */
59 int expected_counts
[256];
60 for (int i
= 0; i
< length
; ++i
)
61 ++expected_counts
[array
[i
] & 0xff];
62 int actual_counts
[256];
63 for (int i
= 0; i
< length
; ++i
)
64 ++actual_counts
[copy
[i
] & 0xff];
65 for (int i
= 0; i
< 256; ++i
)
66 TEST_COMPARE (expected_counts
[i
], expected_counts
[i
]);
72 /* Enumerate all possible combinations of LENGTH elements. */
74 check_combinations (int length
, signed char *start
, int offset
)
77 check_one_sort (start
, length
);
79 for (int i
= 0; i
< length
; ++i
)
82 check_combinations(length
, start
, offset
+ 1);
89 /* A random permutation of 20 values. */
90 check_one_sort ((signed char[20]) {5, 12, 16, 10, 14, 11, 9, 13, 8, 15,
91 0, 17, 3, 7, 1, 18, 2, 19, 4, 6}, 20);
94 /* A permutation that appeared during adversarial testing for the
96 check_one_sort ((signed char[16]) {15, 3, 4, 2, 1, 0, 8, 7, 6, 5, 14,
97 13, 12, 11, 10, 9}, 16);
99 for (int i
= 2; i
<= 8; ++i
)
101 signed char *buf
= xmalloc (i
);
102 check_combinations (i
, buf
, 0);
109 #include <support/test-driver.c>