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