]>
git.ipfire.org Git - thirdparty/glibc.git/blob - stdlib/tst-qsort4.c
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
;
33 /* Wrapper around heapsort_r that set ups the required variables. */
35 heapsort_wrapper (void *const pbase
, size_t total_elems
, size_t size
,
36 __compar_d_fn_t cmp
, void *arg
)
38 char *base_ptr
= (char *) pbase
;
40 char *hi
= &lo
[size
* (total_elems
- 1)];
43 /* Avoid lossage with unsigned arithmetic below. */
46 enum swap_type_t swap_type
;
47 if (is_aligned (pbase
, size
, 8))
48 swap_type
= SWAP_WORDS_64
;
49 else if (is_aligned (pbase
, size
, 4))
50 swap_type
= SWAP_WORDS_32
;
52 swap_type
= SWAP_BYTES
;
53 heapsort_r (lo
, hi
, size
, swap_type
, cmp
, arg
);
57 check_one_sort (signed char *array
, int length
)
59 signed char *copy
= xmalloc (length
);
60 memcpy (copy
, array
, length
);
61 heapsort_wrapper (copy
, length
, 1, cmp
, NULL
);
63 /* Verify that the result is sorted. */
64 for (int i
= 1; i
< length
; ++i
)
65 if (copy
[i
] < copy
[i
- 1])
67 support_record_failure ();
68 printf ("error: sorting failure for length %d at offset %d\n",
71 for (int i
= 0; i
< length
; ++i
)
72 printf (" %d", array
[i
]);
74 for (int i
= 0; i
< length
; ++i
)
75 printf (" %d", copy
[i
]);
80 /* Verify that no elements went away or were added. */
82 int expected_counts
[256];
83 for (int i
= 0; i
< length
; ++i
)
84 ++expected_counts
[array
[i
] & 0xff];
85 int actual_counts
[256];
86 for (int i
= 0; i
< length
; ++i
)
87 ++actual_counts
[copy
[i
] & 0xff];
88 for (int i
= 0; i
< 256; ++i
)
89 TEST_COMPARE (expected_counts
[i
], expected_counts
[i
]);
95 /* Enumerate all possible combinations of LENGTH elements. */
97 check_combinations (int length
, signed char *start
, int offset
)
100 check_one_sort (start
, length
);
102 for (int i
= 0; i
< length
; ++i
)
105 check_combinations(length
, start
, offset
+ 1);
112 /* A random permutation of 20 values. */
113 check_one_sort ((signed char[20]) {5, 12, 16, 10, 14, 11, 9, 13, 8, 15,
114 0, 17, 3, 7, 1, 18, 2, 19, 4, 6}, 20);
117 /* A permutation that appeared during adversarial testing for the
119 check_one_sort ((signed char[16]) {15, 3, 4, 2, 1, 0, 8, 7, 6, 5, 14,
120 13, 12, 11, 10, 9}, 16);
122 /* Array lengths 2 and less are not handled by heapsort_r and
123 deferred to insertion sort. */
124 for (int i
= 3; i
<= 8; ++i
)
126 signed char *buf
= xmalloc (i
);
127 check_combinations (i
, buf
, 0);
134 #include <support/test-driver.c>