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
31typedef 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. */
41static const double RepeatedRatio = 0.2;
42
43/* Ratio of duplicated element . */
44static const double DuplicatedRatio = 0.4;
45
46struct 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. */
61static inline void *
62arr (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. */
68static int
69uint8_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
76static int
77uint16_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
84static int
85uint32_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
92static int
93uint64_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
102static int
103large_cmp (const void *a, const void *b)
104{
105 return memcmp (a, b, LARGE_SIZE);
106}
107
108/* Function used to check qsort_r. */
109typedef 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
118static type_cmp_t
119uint_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
131static int
132uint_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
145static void
146seq (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
160static void
161fill_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
226typedef int (*cmpfunc_t)(const void *, const void *);
227
228/* Simple insertion sort to use as reference sort. */
229static void
230qsort_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
251static void
252qsort_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. */
259static void
260check_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
274static void
275check_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
286static void
287check_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
300static int
301do_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

source code of glibc/stdlib/tst-qsort3.c