406 lines · c
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-exception6//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 else27 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 assuming300 // incorrect association between alignment and element size. The buffer is301 // '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 the305 // lambda hence, let's use & to implicitly capture all needed variables306 // 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