1//===-- Unittests for sorting routines ------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "src/__support/macros/config.h"
10#include "test/UnitTest/Test.h"
11
12class SortingTest : public LIBC_NAMESPACE::testing::Test {
13
14 using SortingRoutine = void (*)(void *array, size_t array_len,
15 size_t elem_size,
16 int (*compare)(const void *, const void *));
17
18 static int int_compare(const void *l, const void *r) {
19 int li = *reinterpret_cast<const int *>(l);
20 int ri = *reinterpret_cast<const int *>(r);
21
22 if (li == ri)
23 return 0;
24 else if (li > ri)
25 return 1;
26 else
27 return -1;
28 }
29
30 static void int_sort(SortingRoutine sort_func, int *array, size_t array_len) {
31 sort_func(reinterpret_cast<void *>(array), array_len, sizeof(int),
32 int_compare);
33 }
34
35public:
36 void test_sorted_array(SortingRoutine sort_func) {
37 int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110,
38 123, 133, 135, 155, 170, 171, 1100, 1110, 1123,
39 1133, 1135, 1155, 1170, 1171, 11100, 12310};
40 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
41
42 int_sort(sort_func, array, ARRAY_LEN);
43
44 ASSERT_LE(array[0], 10);
45 ASSERT_LE(array[1], 23);
46 ASSERT_LE(array[2], 33);
47 ASSERT_LE(array[3], 35);
48 ASSERT_LE(array[4], 55);
49 ASSERT_LE(array[5], 70);
50 ASSERT_LE(array[6], 71);
51 ASSERT_LE(array[7], 100);
52 ASSERT_LE(array[8], 110);
53 ASSERT_LE(array[9], 123);
54 ASSERT_LE(array[10], 133);
55 ASSERT_LE(array[11], 135);
56 ASSERT_LE(array[12], 155);
57 ASSERT_LE(array[13], 170);
58 ASSERT_LE(array[14], 171);
59 ASSERT_LE(array[15], 1100);
60 ASSERT_LE(array[16], 1110);
61 ASSERT_LE(array[17], 1123);
62 ASSERT_LE(array[18], 1133);
63 ASSERT_LE(array[19], 1135);
64 ASSERT_LE(array[20], 1155);
65 ASSERT_LE(array[21], 1170);
66 ASSERT_LE(array[22], 1171);
67 ASSERT_LE(array[23], 11100);
68 ASSERT_LE(array[24], 12310);
69 }
70
71 void test_reversed_sorted_array(SortingRoutine sort_func) {
72 int array[] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
73 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
74 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
75
76 int_sort(sort_func, array, ARRAY_LEN);
77
78 for (int i = 0; i < int(ARRAY_LEN - 1); ++i)
79 ASSERT_EQ(array[i], i + 1);
80 }
81
82 void test_all_equal_elements(SortingRoutine sort_func) {
83 int array[] = {100, 100, 100, 100, 100, 100, 100, 100, 100,
84 100, 100, 100, 100, 100, 100, 100, 100, 100,
85 100, 100, 100, 100, 100, 100, 100};
86 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
87
88 int_sort(sort_func, array, ARRAY_LEN);
89
90 for (size_t i = 0; i < ARRAY_LEN; ++i)
91 ASSERT_EQ(array[i], 100);
92 }
93
94 void test_unsorted_array_1(SortingRoutine sort_func) {
95 int array[25] = {10, 23, 8, 35, 55, 45, 40, 100, 110,
96 123, 90, 80, 70, 60, 171, 11, 1, -1,
97 -5, -10, 1155, 1170, 1171, 12, -100};
98 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
99
100 int_sort(sort_func, array, ARRAY_LEN);
101
102 ASSERT_EQ(array[0], -100);
103 ASSERT_EQ(array[1], -10);
104 ASSERT_EQ(array[2], -5);
105 ASSERT_EQ(array[3], -1);
106 ASSERT_EQ(array[4], 1);
107 ASSERT_EQ(array[5], 8);
108 ASSERT_EQ(array[6], 10);
109 ASSERT_EQ(array[7], 11);
110 ASSERT_EQ(array[8], 12);
111 ASSERT_EQ(array[9], 23);
112 ASSERT_EQ(array[10], 35);
113 ASSERT_EQ(array[11], 40);
114 ASSERT_EQ(array[12], 45);
115 ASSERT_EQ(array[13], 55);
116 ASSERT_EQ(array[14], 60);
117 ASSERT_EQ(array[15], 70);
118 ASSERT_EQ(array[16], 80);
119 ASSERT_EQ(array[17], 90);
120 ASSERT_EQ(array[18], 100);
121 ASSERT_EQ(array[19], 110);
122 ASSERT_EQ(array[20], 123);
123 ASSERT_EQ(array[21], 171);
124 ASSERT_EQ(array[22], 1155);
125 ASSERT_EQ(array[23], 1170);
126 ASSERT_EQ(array[24], 1171);
127 }
128
129 void test_unsorted_array_2(SortingRoutine sort_func) {
130 int array[7] = {10, 40, 45, 55, 35, 23, 60};
131 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
132
133 int_sort(sort_func, array, ARRAY_LEN);
134
135 ASSERT_EQ(array[0], 10);
136 ASSERT_EQ(array[1], 23);
137 ASSERT_EQ(array[2], 35);
138 ASSERT_EQ(array[3], 40);
139 ASSERT_EQ(array[4], 45);
140 ASSERT_EQ(array[5], 55);
141 ASSERT_EQ(array[6], 60);
142 }
143
144 void test_unsorted_array_duplicated_1(SortingRoutine sort_func) {
145 int array[6] = {10, 10, 20, 20, 5, 5};
146 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
147
148 int_sort(sort_func, array, ARRAY_LEN);
149
150 ASSERT_EQ(array[0], 5);
151 ASSERT_EQ(array[1], 5);
152 ASSERT_EQ(array[2], 10);
153 ASSERT_EQ(array[3], 10);
154 ASSERT_EQ(array[4], 20);
155 ASSERT_EQ(array[5], 20);
156 }
157
158 void test_unsorted_array_duplicated_2(SortingRoutine sort_func) {
159 int array[10] = {20, 10, 10, 10, 10, 20, 21, 21, 21, 21};
160 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
161
162 int_sort(sort_func, array, ARRAY_LEN);
163
164 ASSERT_EQ(array[0], 10);
165 ASSERT_EQ(array[1], 10);
166 ASSERT_EQ(array[2], 10);
167 ASSERT_EQ(array[3], 10);
168 ASSERT_EQ(array[4], 20);
169 ASSERT_EQ(array[5], 20);
170 ASSERT_EQ(array[6], 21);
171 ASSERT_EQ(array[7], 21);
172 ASSERT_EQ(array[8], 21);
173 ASSERT_EQ(array[9], 21);
174 }
175
176 void test_unsorted_array_duplicated_3(SortingRoutine sort_func) {
177 int array[10] = {20, 30, 30, 30, 30, 20, 21, 21, 21, 21};
178 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
179
180 int_sort(sort_func, array, ARRAY_LEN);
181
182 ASSERT_EQ(array[0], 20);
183 ASSERT_EQ(array[1], 20);
184 ASSERT_EQ(array[2], 21);
185 ASSERT_EQ(array[3], 21);
186 ASSERT_EQ(array[4], 21);
187 ASSERT_EQ(array[5], 21);
188 ASSERT_EQ(array[6], 30);
189 ASSERT_EQ(array[7], 30);
190 ASSERT_EQ(array[8], 30);
191 ASSERT_EQ(array[9], 30);
192 }
193
194 void test_unsorted_three_element_1(SortingRoutine sort_func) {
195 int array[3] = {14999024, 0, 3};
196
197 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
198
199 int_sort(sort_func, array, ARRAY_LEN);
200
201 ASSERT_EQ(array[0], 0);
202 ASSERT_EQ(array[1], 3);
203 ASSERT_EQ(array[2], 14999024);
204 }
205
206 void test_unsorted_three_element_2(SortingRoutine sort_func) {
207 int array[3] = {3, 14999024, 0};
208
209 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
210
211 int_sort(sort_func, array, ARRAY_LEN);
212
213 ASSERT_EQ(array[0], 0);
214 ASSERT_EQ(array[1], 3);
215 ASSERT_EQ(array[2], 14999024);
216 }
217
218 void test_unsorted_three_element_3(SortingRoutine sort_func) {
219 int array[3] = {3, 0, 14999024};
220
221 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
222
223 int_sort(sort_func, array, ARRAY_LEN);
224
225 ASSERT_EQ(array[0], 0);
226 ASSERT_EQ(array[1], 3);
227 ASSERT_EQ(array[2], 14999024);
228 }
229
230 void test_same_three_element(SortingRoutine sort_func) {
231 int array[3] = {12345, 12345, 12345};
232
233 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
234
235 int_sort(sort_func, array, ARRAY_LEN);
236
237 ASSERT_EQ(array[0], 12345);
238 ASSERT_EQ(array[1], 12345);
239 ASSERT_EQ(array[2], 12345);
240 }
241
242 void test_unsorted_two_element_1(SortingRoutine sort_func) {
243 int array[] = {14999024, 0};
244
245 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
246
247 int_sort(sort_func, array, ARRAY_LEN);
248
249 ASSERT_EQ(array[0], 0);
250 ASSERT_EQ(array[1], 14999024);
251 }
252
253 void test_unsorted_two_element_2(SortingRoutine sort_func) {
254 int array[] = {0, 14999024};
255
256 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
257
258 int_sort(sort_func, array, ARRAY_LEN);
259
260 ASSERT_EQ(array[0], 0);
261 ASSERT_EQ(array[1], 14999024);
262 }
263
264 void test_same_two_element(SortingRoutine sort_func) {
265 int array[] = {12345, 12345};
266
267 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
268
269 int_sort(sort_func, array, ARRAY_LEN);
270
271 ASSERT_EQ(array[0], 12345);
272 ASSERT_EQ(array[1], 12345);
273 }
274
275 void test_single_element(SortingRoutine sort_func) {
276 int array[] = {12345};
277
278 constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
279
280 int_sort(sort_func, array, ARRAY_LEN);
281
282 ASSERT_EQ(array[0], 12345);
283 }
284
285 void test_different_elem_size(SortingRoutine sort_func) {
286 // Random order of values [0,50) to avoid only testing pre-sorted handling.
287 // Long enough to reach interesting code.
288 constexpr uint8_t ARRAY_INITIAL_VALS[] = {
289 42, 13, 8, 4, 17, 28, 20, 32, 22, 29, 7, 2, 46, 37, 26, 49, 24,
290 38, 10, 18, 40, 36, 47, 15, 11, 48, 44, 33, 1, 5, 16, 35, 39, 41,
291 14, 23, 3, 9, 6, 27, 21, 25, 31, 45, 12, 43, 34, 30, 19, 0};
292
293 constexpr size_t ARRAY_LEN = sizeof(ARRAY_INITIAL_VALS);
294 constexpr size_t MAX_ELEM_SIZE = 150;
295 constexpr size_t BUF_SIZE = ARRAY_LEN * MAX_ELEM_SIZE;
296
297 static_assert(ARRAY_LEN < 256); // so we can encode the values.
298
299 // Minimum alignment to test implementation for bugs related to assuming
300 // incorrect association between alignment and element size. The buffer is
301 // 'static' as otherwise it will exhaust the stack on the GPU targets.
302 alignas(1) static uint8_t buf[BUF_SIZE];
303
304 // GCC still requires capturing the constant ARRAY_INITIAL_VALS in the
305 // lambda hence, let's use & to implicitly capture all needed variables
306 // automatically.
307 const auto fill_buf = [&](size_t elem_size) {
308 for (size_t i = 0; i < BUF_SIZE; ++i) {
309 buf[i] = 0;
310 }
311
312 for (size_t elem_i = 0, buf_i = 0; elem_i < ARRAY_LEN; ++elem_i) {
313 const uint8_t elem_val = ARRAY_INITIAL_VALS[elem_i];
314 for (size_t elem_byte_i = 0; elem_byte_i < elem_size; ++elem_byte_i) {
315 buf[buf_i] = elem_val;
316 buf_i += 1;
317 }
318 }
319 };
320
321 for (size_t elem_size = 0; elem_size <= MAX_ELEM_SIZE; ++elem_size) {
322 // Fill all bytes with data to ensure mistakes in elem swap are noticed.
323 fill_buf(elem_size);
324
325 sort_func(reinterpret_cast<void *>(buf), ARRAY_LEN, elem_size,
326 [](const void *a, const void *b) -> int {
327 const uint8_t a_val = *reinterpret_cast<const uint8_t *>(a);
328 const uint8_t b_val = *reinterpret_cast<const uint8_t *>(b);
329
330 if (a_val < b_val) {
331 return -1;
332 } else if (a_val > b_val) {
333 return 1;
334 } else {
335 return 0;
336 }
337 });
338
339 for (size_t elem_i = 0, buf_i = 0; elem_i < ARRAY_LEN; ++elem_i) {
340 const uint8_t expected_elem_val = static_cast<uint8_t>(elem_i);
341
342 for (size_t elem_byte_i = 0; elem_byte_i < elem_size; ++elem_byte_i) {
343 const uint8_t buf_val = buf[buf_i];
344 // Check that every byte in the element has the expected value.
345 ASSERT_EQ(buf_val, expected_elem_val)
346 << "elem_size: " << elem_size << " buf_i: " << buf_i << '\n';
347 buf_i += 1;
348 }
349 }
350 }
351 }
352};
353
354#define LIST_SORTING_TESTS(Name, Func) \
355 using LlvmLibc##Name##Test = SortingTest; \
356 TEST_F(LlvmLibc##Name##Test, SortedArray) { test_sorted_array(Func); } \
357 TEST_F(LlvmLibc##Name##Test, ReverseSortedArray) { \
358 test_reversed_sorted_array(Func); \
359 } \
360 TEST_F(LlvmLibc##Name##Test, AllEqualElements) { \
361 test_all_equal_elements(Func); \
362 } \
363 TEST_F(LlvmLibc##Name##Test, UnsortedArray1) { \
364 test_unsorted_array_1(Func); \
365 } \
366 TEST_F(LlvmLibc##Name##Test, UnsortedArray2) { \
367 test_unsorted_array_2(Func); \
368 } \
369 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements1) { \
370 test_unsorted_array_duplicated_1(Func); \
371 } \
372 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements2) { \
373 test_unsorted_array_duplicated_2(Func); \
374 } \
375 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements3) { \
376 test_unsorted_array_duplicated_3(Func); \
377 } \
378 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray1) { \
379 test_unsorted_three_element_1(Func); \
380 } \
381 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray2) { \
382 test_unsorted_three_element_2(Func); \
383 } \
384 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray3) { \
385 test_unsorted_three_element_3(Func); \
386 } \
387 TEST_F(LlvmLibc##Name##Test, SameElementThreeElementArray) { \
388 test_same_three_element(Func); \
389 } \
390 TEST_F(LlvmLibc##Name##Test, UnsortedTwoElementArray1) { \
391 test_unsorted_two_element_1(Func); \
392 } \
393 TEST_F(LlvmLibc##Name##Test, UnsortedTwoElementArray2) { \
394 test_unsorted_two_element_2(Func); \
395 } \
396 TEST_F(LlvmLibc##Name##Test, SameElementTwoElementArray) { \
397 test_same_two_element(Func); \
398 } \
399 TEST_F(LlvmLibc##Name##Test, SingleElementArray) { \
400 test_single_element(Func); \
401 } \
402 TEST_F(LlvmLibc##Name##Test, DifferentElemSizeArray) { \
403 test_different_elem_size(Func); \
404 } \
405 static_assert(true)
406

source code of libc/test/src/stdlib/SortingTest.h