1 | /* qsort(_r) tests to trigger worst case for quicksort. |
2 | Copyright (C) 2023-2024 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
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. |
9 | |
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. |
14 | |
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/>. */ |
18 | |
19 | #include <array_length.h> |
20 | #include <errno.h> |
21 | #include <getopt.h> |
22 | #include <stdbool.h> |
23 | #include <stdint.h> |
24 | #include <stdio.h> |
25 | #include <stdlib.h> |
26 | #include <string.h> |
27 | #include <support/check.h> |
28 | #include <support/support.h> |
29 | #include <support/test-driver.h> |
30 | |
31 | typedef enum |
32 | { |
33 | Sorted, |
34 | Random, |
35 | Repeated, |
36 | Bitonic, |
37 | Duplicated, |
38 | } arraytype_t; |
39 | |
40 | /* Ratio of total of elements which will be repeated. */ |
41 | static const double RepeatedRatio = 0.2; |
42 | |
43 | /* Ratio of duplicated element . */ |
44 | static const double DuplicatedRatio = 0.4; |
45 | |
46 | struct array_t |
47 | { |
48 | arraytype_t type; |
49 | const char *name; |
50 | } static const arraytypes[] = |
51 | { |
52 | { Sorted, "Sorted" }, |
53 | { Random, "Random" }, |
54 | { Repeated, "Repeated" }, |
55 | { Bitonic, "Bitonic" }, |
56 | { Duplicated, "Duplicated" }, |
57 | }; |
58 | |
59 | /* Return the index of BASE as interpreted as an array of elements |
60 | of size SIZE. */ |
61 | static inline void * |
62 | arr (void *base, size_t idx, size_t size) |
63 | { |
64 | return (void*)((uintptr_t)base + (idx * size)); |
65 | } |
66 | |
67 | /* Functions used to check qsort. */ |
68 | static int |
69 | uint8_t_cmp (const void *a, const void *b) |
70 | { |
71 | uint8_t ia = *(uint8_t*)a; |
72 | uint8_t ib = *(uint8_t*)b; |
73 | return (ia > ib) - (ia < ib); |
74 | } |
75 | |
76 | static int |
77 | uint16_t_cmp (const void *a, const void *b) |
78 | { |
79 | uint16_t ia = *(uint16_t*)a; |
80 | uint16_t ib = *(uint16_t*)b; |
81 | return (ia > ib) - (ia < ib); |
82 | } |
83 | |
84 | static int |
85 | uint32_t_cmp (const void *a, const void *b) |
86 | { |
87 | uint32_t ia = *(uint32_t*)a; |
88 | uint32_t ib = *(uint32_t*)b; |
89 | return (ia > ib) - (ia < ib); |
90 | } |
91 | |
92 | static int |
93 | uint64_t_cmp (const void *a, const void *b) |
94 | { |
95 | uint64_t ia = *(uint64_t*)a; |
96 | uint64_t ib = *(uint64_t*)b; |
97 | return (ia > ib) - (ia < ib); |
98 | } |
99 | |
100 | #define LARGE_SIZE 47 |
101 | |
102 | static int |
103 | large_cmp (const void *a, const void *b) |
104 | { |
105 | return memcmp (a, b, LARGE_SIZE); |
106 | } |
107 | |
108 | /* Function used to check qsort_r. */ |
109 | typedef enum |
110 | { |
111 | UINT8_CMP_T, |
112 | UINT16_CMP_T, |
113 | UINT32_CMP_T, |
114 | UINT64_CMP_T, |
115 | LARGE_CMP_T |
116 | } type_cmp_t; |
117 | |
118 | static type_cmp_t |
119 | uint_t_cmp_type (size_t sz) |
120 | { |
121 | switch (sz) |
122 | { |
123 | case sizeof (uint8_t): return UINT8_CMP_T; |
124 | case sizeof (uint16_t): return UINT16_CMP_T; |
125 | case sizeof (uint64_t): return UINT64_CMP_T; |
126 | case sizeof (uint32_t): return UINT32_CMP_T; |
127 | default: return LARGE_CMP_T; |
128 | } |
129 | } |
130 | |
131 | static int |
132 | uint_t_cmp (const void *a, const void *b, void *arg) |
133 | { |
134 | type_cmp_t type = *(type_cmp_t*) arg; |
135 | switch (type) |
136 | { |
137 | case UINT8_CMP_T: return uint8_t_cmp (a, b); |
138 | case UINT32_CMP_T: return uint32_t_cmp (a, b); |
139 | case UINT16_CMP_T: return uint16_t_cmp (a, b); |
140 | case UINT64_CMP_T: return uint64_t_cmp (a, b); |
141 | default: return large_cmp (a, b); |
142 | } |
143 | } |
144 | |
145 | static void |
146 | seq (void *elem, size_t type_size, int value) |
147 | { |
148 | if (type_size == sizeof (uint8_t)) |
149 | *(uint8_t*)elem = value; |
150 | else if (type_size == sizeof (uint16_t)) |
151 | *(uint16_t*)elem = value; |
152 | else if (type_size == sizeof (uint32_t)) |
153 | *(uint32_t*)elem = value; |
154 | else if (type_size == sizeof (uint64_t)) |
155 | *(uint64_t*)elem = value; |
156 | else |
157 | memset (elem, value, type_size); |
158 | } |
159 | |
160 | static void |
161 | fill_array (void *array, void *refarray, size_t nmemb, size_t type_size, |
162 | arraytype_t type) |
163 | { |
164 | size_t size = nmemb * type_size; |
165 | |
166 | switch (type) |
167 | { |
168 | case Sorted: |
169 | for (size_t i = 0; i < nmemb; i++) |
170 | seq (elem: arr (base: array, idx: i, size: type_size), type_size, value: i); |
171 | break; |
172 | |
173 | case Random: |
174 | arc4random_buf (buf: array, size: size); |
175 | break; |
176 | |
177 | case Repeated: |
178 | { |
179 | arc4random_buf (buf: array, size: size); |
180 | |
181 | void *randelem = xmalloc (n: type_size); |
182 | arc4random_buf (buf: randelem, size: type_size); |
183 | |
184 | /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random |
185 | array. */ |
186 | size_t repeated = (size_t)(nmemb * RepeatedRatio); |
187 | for (size_t i = 0; i < repeated; i++) |
188 | { |
189 | size_t pos = arc4random_uniform (upper_bound: nmemb - 1); |
190 | memcpy (arr (base: array, idx: pos, size: type_size), randelem, type_size); |
191 | } |
192 | free (ptr: randelem); |
193 | } |
194 | break; |
195 | |
196 | case Bitonic: |
197 | { |
198 | size_t i; |
199 | for (i = 0; i < nmemb / 2; i++) |
200 | seq (elem: arr (base: array, idx: i, size: type_size), type_size, value: i); |
201 | for ( ; i < nmemb; i++) |
202 | seq (elem: arr (base: array, idx: i, size: type_size), type_size, value: (nmemb - 1) - i); |
203 | } |
204 | break; |
205 | |
206 | case Duplicated: |
207 | { |
208 | int randelem1 = arc4random (); |
209 | for (size_t i = 0; i < nmemb; i++) |
210 | seq (elem: arr (base: array, idx: i, size: type_size), type_size, value: randelem1); |
211 | |
212 | size_t duplicates = (size_t)(nmemb * DuplicatedRatio); |
213 | int randelem2 = arc4random (); |
214 | for (size_t i = 0; i < duplicates; i++) |
215 | { |
216 | size_t pos = arc4random_uniform (upper_bound: nmemb - 1); |
217 | seq (elem: arr (base: array, idx: pos, size: type_size), type_size, value: randelem2); |
218 | } |
219 | } |
220 | break; |
221 | } |
222 | |
223 | memcpy (refarray, array, size); |
224 | } |
225 | |
226 | typedef int (*cmpfunc_t)(const void *, const void *); |
227 | |
228 | /* Simple insertion sort to use as reference sort. */ |
229 | static void |
230 | qsort_r_ref (void *p, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) |
231 | { |
232 | if (n <= 1) |
233 | return; |
234 | |
235 | int i = 1; |
236 | char tmp[s]; |
237 | while (i < n) |
238 | { |
239 | memcpy (tmp, arr (base: p, idx: i, size: s), s); |
240 | int j = i - 1; |
241 | while (j >= 0 && cmp (arr (base: p, idx: j, size: s), tmp, arg) > 0) |
242 | { |
243 | memcpy (arr (base: p, idx: j + 1, size: s), arr (base: p, idx: j, size: s), s); |
244 | j = j - 1; |
245 | } |
246 | memcpy (arr (base: p, idx: j + 1, size: s), tmp, s); |
247 | i = i + 1; |
248 | } |
249 | } |
250 | |
251 | static void |
252 | qsort_ref (void *b, size_t n, size_t s, __compar_fn_t cmp) |
253 | { |
254 | return qsort_r_ref (p: b, n, s, cmp: (__compar_d_fn_t) cmp, NULL); |
255 | } |
256 | |
257 | /* Check if ARRAY of total NMEMB element of size SIZE is sorted |
258 | based on CMPFUNC. */ |
259 | static void |
260 | check_array (void *array, void *refarray, size_t nmemb, size_t type_size, |
261 | cmpfunc_t cmpfunc) |
262 | { |
263 | for (size_t i = 1; i < nmemb; i++) |
264 | { |
265 | int ret = cmpfunc (arr (base: array, idx: i, size: type_size), |
266 | arr (base: array, idx: i-1, size: type_size)); |
267 | TEST_VERIFY_EXIT (ret >= 0); |
268 | } |
269 | |
270 | size_t size = nmemb * type_size; |
271 | TEST_COMPARE_BLOB (array, size, refarray, size); |
272 | } |
273 | |
274 | static void |
275 | check_qsort (void *buf, void *refbuf, size_t nelem, size_t type_size, |
276 | arraytype_t type, cmpfunc_t cmpfunc) |
277 | { |
278 | fill_array (array: buf, refarray: refbuf, nmemb: nelem, type_size, type); |
279 | |
280 | qsort (buf, nelem, type_size, cmpfunc); |
281 | qsort_ref (b: refbuf, n: nelem, s: type_size, cmp: cmpfunc); |
282 | |
283 | check_array (array: buf, refarray: refbuf, nmemb: nelem, type_size, cmpfunc); |
284 | } |
285 | |
286 | static void |
287 | check_qsort_r (void *buf, void *refbuf, size_t nelem, size_t type_size, |
288 | arraytype_t type, cmpfunc_t cmpfunc) |
289 | { |
290 | fill_array (array: buf, refarray: refbuf, nmemb: nelem, type_size, type); |
291 | |
292 | type_cmp_t typecmp = uint_t_cmp_type (sz: type_size); |
293 | |
294 | qsort_r (base: buf, nmemb: nelem, size: type_size, compar: uint_t_cmp, arg: &typecmp); |
295 | qsort_r_ref (p: refbuf, n: nelem, s: type_size, cmp: uint_t_cmp, arg: &typecmp); |
296 | |
297 | check_array (array: buf, refarray: refbuf, nmemb: nelem, type_size, cmpfunc); |
298 | } |
299 | |
300 | static int |
301 | do_test (void) |
302 | { |
303 | /* Some random sizes. */ |
304 | static const size_t nelems[] = { 0, 1, 7, 20, 32, 100, 256, 1024, 4256 }; |
305 | size_t max_nelems = 0; |
306 | for (int i = 0; i < array_length (nelems); i++) |
307 | if (nelems[i] > max_nelems) |
308 | max_nelems = nelems[i]; |
309 | |
310 | static const struct test_t |
311 | { |
312 | size_t type_size; |
313 | cmpfunc_t cmpfunc; |
314 | } |
315 | tests[] = |
316 | { |
317 | { sizeof (uint8_t), uint8_t_cmp }, |
318 | { sizeof (uint16_t), uint16_t_cmp }, |
319 | { sizeof (uint32_t), uint32_t_cmp }, |
320 | { sizeof (uint64_t), uint64_t_cmp }, |
321 | /* Test swap with large elements. */ |
322 | { LARGE_SIZE, large_cmp }, |
323 | }; |
324 | size_t max_type_size = 0; |
325 | for (int i = 0; i < array_length (tests); i++) |
326 | if (tests[i].type_size > max_type_size) |
327 | max_type_size = tests[i].type_size; |
328 | |
329 | void *buf = reallocarray (NULL, nmemb: max_nelems, size: max_type_size); |
330 | TEST_VERIFY_EXIT (buf != NULL); |
331 | void *refbuf = reallocarray (NULL, nmemb: max_nelems, size: max_type_size); |
332 | TEST_VERIFY_EXIT (refbuf != NULL); |
333 | |
334 | for (const struct test_t *test = tests; test < array_end (tests); ++test) |
335 | { |
336 | if (test_verbose > 0) |
337 | printf (format: "info: testing qsort with type_size=%zu\n" , test->type_size); |
338 | for (const struct array_t *arraytype = arraytypes; |
339 | arraytype < array_end (arraytypes); |
340 | ++arraytype) |
341 | { |
342 | if (test_verbose > 0) |
343 | printf (format: " distribution=%s\n" , arraytype->name); |
344 | for (const size_t *nelem = nelems; |
345 | nelem < array_end (nelems); |
346 | ++nelem) |
347 | { |
348 | if (test_verbose > 0) |
349 | printf (format: " nelem=%zu, total size=%zu\n" , *nelem, |
350 | *nelem * test->type_size); |
351 | |
352 | check_qsort (buf, refbuf, nelem: *nelem, type_size: test->type_size, |
353 | type: arraytype->type, cmpfunc: test->cmpfunc); |
354 | check_qsort_r (buf, refbuf, nelem: *nelem, type_size: test->type_size, |
355 | type: arraytype->type, cmpfunc: test->cmpfunc); |
356 | } |
357 | } |
358 | } |
359 | |
360 | free (ptr: buf); |
361 | free (ptr: refbuf); |
362 | |
363 | return 0; |
364 | } |
365 | |
366 | #include <support/test-driver.c> |
367 | |