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_data.h" 11 #include "test/UnitTest/Test.h" 12 13 class SortingTest : public LIBC_NAMESPACE::testing::Test { 14 15 using Array = LIBC_NAMESPACE::internal::Array; 16 using Comparator = LIBC_NAMESPACE::internal::Comparator; 17 using SortingRoutine = LIBC_NAMESPACE::internal::SortingRoutine; 18 19 public: int_compare(const void * l,const void * r)20 static int int_compare(const void *l, const void *r) { 21 int li = *reinterpret_cast<const int *>(l); 22 int ri = *reinterpret_cast<const int *>(r); 23 if (li == ri) 24 return 0; 25 else if (li > ri) 26 return 1; 27 else 28 return -1; 29 } 30 test_sorted_array(SortingRoutine sort_func)31 void test_sorted_array(SortingRoutine sort_func) { 32 int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110, 33 123, 133, 135, 155, 170, 171, 1100, 1110, 1123, 34 1133, 1135, 1155, 1170, 1171, 11100, 12310}; 35 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 36 37 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 38 sizeof(int), Comparator(int_compare)); 39 40 sort_func(arr); 41 42 ASSERT_LE(array[0], 10); 43 ASSERT_LE(array[1], 23); 44 ASSERT_LE(array[2], 33); 45 ASSERT_LE(array[3], 35); 46 ASSERT_LE(array[4], 55); 47 ASSERT_LE(array[5], 70); 48 ASSERT_LE(array[6], 71); 49 ASSERT_LE(array[7], 100); 50 ASSERT_LE(array[8], 110); 51 ASSERT_LE(array[9], 123); 52 ASSERT_LE(array[10], 133); 53 ASSERT_LE(array[11], 135); 54 ASSERT_LE(array[12], 155); 55 ASSERT_LE(array[13], 170); 56 ASSERT_LE(array[14], 171); 57 ASSERT_LE(array[15], 1100); 58 ASSERT_LE(array[16], 1110); 59 ASSERT_LE(array[17], 1123); 60 ASSERT_LE(array[18], 1133); 61 ASSERT_LE(array[19], 1135); 62 ASSERT_LE(array[20], 1155); 63 ASSERT_LE(array[21], 1170); 64 ASSERT_LE(array[22], 1171); 65 ASSERT_LE(array[23], 11100); 66 ASSERT_LE(array[24], 12310); 67 } 68 test_reversed_sorted_array(SortingRoutine sort_func)69 void test_reversed_sorted_array(SortingRoutine sort_func) { 70 int array[] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 71 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 72 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 73 74 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 75 sizeof(int), Comparator(int_compare)); 76 77 sort_func(arr); 78 79 for (int i = 0; i < int(ARRAY_SIZE - 1); ++i) 80 ASSERT_EQ(array[i], i + 1); 81 } 82 test_all_equal_elements(SortingRoutine sort_func)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_SIZE = sizeof(array) / sizeof(int); 88 89 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 90 sizeof(int), Comparator(int_compare)); 91 92 sort_func(arr); 93 94 for (size_t i = 0; i < ARRAY_SIZE; ++i) 95 ASSERT_EQ(array[i], 100); 96 } 97 test_unsorted_array_1(SortingRoutine sort_func)98 void test_unsorted_array_1(SortingRoutine sort_func) { 99 int array[25] = {10, 23, 8, 35, 55, 45, 40, 100, 110, 100 123, 90, 80, 70, 60, 171, 11, 1, -1, 101 -5, -10, 1155, 1170, 1171, 12, -100}; 102 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 103 104 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 105 sizeof(int), Comparator(int_compare)); 106 107 sort_func(arr); 108 109 ASSERT_EQ(array[0], -100); 110 ASSERT_EQ(array[1], -10); 111 ASSERT_EQ(array[2], -5); 112 ASSERT_EQ(array[3], -1); 113 ASSERT_EQ(array[4], 1); 114 ASSERT_EQ(array[5], 8); 115 ASSERT_EQ(array[6], 10); 116 ASSERT_EQ(array[7], 11); 117 ASSERT_EQ(array[8], 12); 118 ASSERT_EQ(array[9], 23); 119 ASSERT_EQ(array[10], 35); 120 ASSERT_EQ(array[11], 40); 121 ASSERT_EQ(array[12], 45); 122 ASSERT_EQ(array[13], 55); 123 ASSERT_EQ(array[14], 60); 124 ASSERT_EQ(array[15], 70); 125 ASSERT_EQ(array[16], 80); 126 ASSERT_EQ(array[17], 90); 127 ASSERT_EQ(array[18], 100); 128 ASSERT_EQ(array[19], 110); 129 ASSERT_EQ(array[20], 123); 130 ASSERT_EQ(array[21], 171); 131 ASSERT_EQ(array[22], 1155); 132 ASSERT_EQ(array[23], 1170); 133 ASSERT_EQ(array[24], 1171); 134 } 135 test_unsorted_array_2(SortingRoutine sort_func)136 void test_unsorted_array_2(SortingRoutine sort_func) { 137 int array[7] = {10, 40, 45, 55, 35, 23, 60}; 138 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 139 140 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 141 sizeof(int), Comparator(int_compare)); 142 143 sort_func(arr); 144 145 ASSERT_EQ(array[0], 10); 146 ASSERT_EQ(array[1], 23); 147 ASSERT_EQ(array[2], 35); 148 ASSERT_EQ(array[3], 40); 149 ASSERT_EQ(array[4], 45); 150 ASSERT_EQ(array[5], 55); 151 ASSERT_EQ(array[6], 60); 152 } 153 test_unsorted_array_duplicated_1(SortingRoutine sort_func)154 void test_unsorted_array_duplicated_1(SortingRoutine sort_func) { 155 int array[6] = {10, 10, 20, 20, 5, 5}; 156 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 157 158 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 159 sizeof(int), Comparator(int_compare)); 160 161 sort_func(arr); 162 163 ASSERT_EQ(array[0], 5); 164 ASSERT_EQ(array[1], 5); 165 ASSERT_EQ(array[2], 10); 166 ASSERT_EQ(array[3], 10); 167 ASSERT_EQ(array[4], 20); 168 ASSERT_EQ(array[5], 20); 169 } 170 test_unsorted_array_duplicated_2(SortingRoutine sort_func)171 void test_unsorted_array_duplicated_2(SortingRoutine sort_func) { 172 int array[10] = {20, 10, 10, 10, 10, 20, 21, 21, 21, 21}; 173 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 174 175 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 176 sizeof(int), Comparator(int_compare)); 177 178 sort_func(arr); 179 180 ASSERT_EQ(array[0], 10); 181 ASSERT_EQ(array[1], 10); 182 ASSERT_EQ(array[2], 10); 183 ASSERT_EQ(array[3], 10); 184 ASSERT_EQ(array[4], 20); 185 ASSERT_EQ(array[5], 20); 186 ASSERT_EQ(array[6], 21); 187 ASSERT_EQ(array[7], 21); 188 ASSERT_EQ(array[8], 21); 189 ASSERT_EQ(array[9], 21); 190 } 191 test_unsorted_array_duplicated_3(SortingRoutine sort_func)192 void test_unsorted_array_duplicated_3(SortingRoutine sort_func) { 193 int array[10] = {20, 30, 30, 30, 30, 20, 21, 21, 21, 21}; 194 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 195 196 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 197 sizeof(int), Comparator(int_compare)); 198 199 sort_func(arr); 200 201 ASSERT_EQ(array[0], 20); 202 ASSERT_EQ(array[1], 20); 203 ASSERT_EQ(array[2], 21); 204 ASSERT_EQ(array[3], 21); 205 ASSERT_EQ(array[4], 21); 206 ASSERT_EQ(array[5], 21); 207 ASSERT_EQ(array[6], 30); 208 ASSERT_EQ(array[7], 30); 209 ASSERT_EQ(array[8], 30); 210 ASSERT_EQ(array[9], 30); 211 } 212 test_unsorted_three_element_1(SortingRoutine sort_func)213 void test_unsorted_three_element_1(SortingRoutine sort_func) { 214 int array[3] = {14999024, 0, 3}; 215 216 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 217 218 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 219 sizeof(int), Comparator(int_compare)); 220 221 sort_func(arr); 222 223 ASSERT_EQ(array[0], 0); 224 ASSERT_EQ(array[1], 3); 225 ASSERT_EQ(array[2], 14999024); 226 } 227 test_unsorted_three_element_2(SortingRoutine sort_func)228 void test_unsorted_three_element_2(SortingRoutine sort_func) { 229 int array[3] = {3, 14999024, 0}; 230 231 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 232 233 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 234 sizeof(int), Comparator(int_compare)); 235 236 sort_func(arr); 237 238 ASSERT_EQ(array[0], 0); 239 ASSERT_EQ(array[1], 3); 240 ASSERT_EQ(array[2], 14999024); 241 } 242 test_unsorted_three_element_3(SortingRoutine sort_func)243 void test_unsorted_three_element_3(SortingRoutine sort_func) { 244 int array[3] = {3, 0, 14999024}; 245 246 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 247 248 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 249 sizeof(int), Comparator(int_compare)); 250 251 sort_func(arr); 252 253 ASSERT_EQ(array[0], 0); 254 ASSERT_EQ(array[1], 3); 255 ASSERT_EQ(array[2], 14999024); 256 } 257 test_same_three_element(SortingRoutine sort_func)258 void test_same_three_element(SortingRoutine sort_func) { 259 int array[3] = {12345, 12345, 12345}; 260 261 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 262 263 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 264 sizeof(int), Comparator(int_compare)); 265 266 sort_func(arr); 267 268 ASSERT_EQ(array[0], 12345); 269 ASSERT_EQ(array[1], 12345); 270 ASSERT_EQ(array[2], 12345); 271 } 272 test_unsorted_two_element_1(SortingRoutine sort_func)273 void test_unsorted_two_element_1(SortingRoutine sort_func) { 274 int array[] = {14999024, 0}; 275 276 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 277 278 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 279 sizeof(int), Comparator(int_compare)); 280 281 sort_func(arr); 282 283 ASSERT_EQ(array[0], 0); 284 ASSERT_EQ(array[1], 14999024); 285 } 286 test_unsorted_two_element_2(SortingRoutine sort_func)287 void test_unsorted_two_element_2(SortingRoutine sort_func) { 288 int array[] = {0, 14999024}; 289 290 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 291 292 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 293 sizeof(int), Comparator(int_compare)); 294 295 sort_func(arr); 296 297 ASSERT_EQ(array[0], 0); 298 ASSERT_EQ(array[1], 14999024); 299 } 300 test_same_two_element(SortingRoutine sort_func)301 void test_same_two_element(SortingRoutine sort_func) { 302 int array[] = {12345, 12345}; 303 304 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 305 306 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 307 sizeof(int), Comparator(int_compare)); 308 309 sort_func(arr); 310 311 ASSERT_EQ(array[0], 12345); 312 ASSERT_EQ(array[1], 12345); 313 } 314 test_single_element(SortingRoutine sort_func)315 void test_single_element(SortingRoutine sort_func) { 316 int array[] = {12345}; 317 318 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 319 320 auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE, 321 sizeof(int), Comparator(int_compare)); 322 323 sort_func(arr); 324 325 ASSERT_EQ(array[0], 12345); 326 } 327 }; 328 329 #define LIST_SORTING_TESTS(Name, Func) \ 330 using LlvmLibc##Name##Test = SortingTest; \ 331 TEST_F(LlvmLibc##Name##Test, SortedArray) { test_sorted_array(Func); } \ 332 TEST_F(LlvmLibc##Name##Test, ReverseSortedArray) { \ 333 test_reversed_sorted_array(Func); \ 334 } \ 335 TEST_F(LlvmLibc##Name##Test, AllEqualElements) { \ 336 test_all_equal_elements(Func); \ 337 } \ 338 TEST_F(LlvmLibc##Name##Test, UnsortedArray1) { \ 339 test_unsorted_array_1(Func); \ 340 } \ 341 TEST_F(LlvmLibc##Name##Test, UnsortedArray2) { \ 342 test_unsorted_array_2(Func); \ 343 } \ 344 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements1) { \ 345 test_unsorted_array_duplicated_1(Func); \ 346 } \ 347 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements2) { \ 348 test_unsorted_array_duplicated_2(Func); \ 349 } \ 350 TEST_F(LlvmLibc##Name##Test, UnsortedArrayDuplicateElements3) { \ 351 test_unsorted_array_duplicated_3(Func); \ 352 } \ 353 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray1) { \ 354 test_unsorted_three_element_1(Func); \ 355 } \ 356 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray2) { \ 357 test_unsorted_three_element_2(Func); \ 358 } \ 359 TEST_F(LlvmLibc##Name##Test, UnsortedThreeElementArray3) { \ 360 test_unsorted_three_element_3(Func); \ 361 } \ 362 TEST_F(LlvmLibc##Name##Test, SameElementThreeElementArray) { \ 363 test_same_three_element(Func); \ 364 } \ 365 TEST_F(LlvmLibc##Name##Test, UnsortedTwoElementArray1) { \ 366 test_unsorted_two_element_1(Func); \ 367 } \ 368 TEST_F(LlvmLibc##Name##Test, UnsortedTwoElementArray2) { \ 369 test_unsorted_two_element_2(Func); \ 370 } \ 371 TEST_F(LlvmLibc##Name##Test, SameElementTwoElementArray) { \ 372 test_same_two_element(Func); \ 373 } \ 374 TEST_F(LlvmLibc##Name##Test, SingleElementArray) { \ 375 test_single_element(Func); \ 376 } \ 377 static_assert(true) 378