summaryrefslogtreecommitdiff
path: root/libc/test/src/stdlib/SortingTest.h
diff options
context:
space:
mode:
Diffstat (limited to 'libc/test/src/stdlib/SortingTest.h')
-rw-r--r--libc/test/src/stdlib/SortingTest.h203
1 files changed, 116 insertions, 87 deletions
diff --git a/libc/test/src/stdlib/SortingTest.h b/libc/test/src/stdlib/SortingTest.h
index d34584e5addf..681a420ea727 100644
--- a/libc/test/src/stdlib/SortingTest.h
+++ b/libc/test/src/stdlib/SortingTest.h
@@ -7,19 +7,19 @@
//===----------------------------------------------------------------------===//
#include "src/__support/macros/config.h"
-#include "src/stdlib/qsort_data.h"
+#include "src/stdlib/qsort.h"
#include "test/UnitTest/Test.h"
class SortingTest : public LIBC_NAMESPACE::testing::Test {
- using Array = LIBC_NAMESPACE::internal::Array;
- using Comparator = LIBC_NAMESPACE::internal::Comparator;
- using SortingRoutine = LIBC_NAMESPACE::internal::SortingRoutine;
+ using SortingRoutine = void (*)(void *array, size_t array_len,
+ size_t elem_size,
+ int (*compare)(const void *, const void *));
-public:
static int int_compare(const void *l, const void *r) {
int li = *reinterpret_cast<const int *>(l);
int ri = *reinterpret_cast<const int *>(r);
+
if (li == ri)
return 0;
else if (li > ri)
@@ -28,16 +28,19 @@ public:
return -1;
}
+ static void int_sort(SortingRoutine sort_func, int *array, size_t array_len) {
+ sort_func(reinterpret_cast<void *>(array), array_len, sizeof(int),
+ int_compare);
+ }
+
+public:
void test_sorted_array(SortingRoutine sort_func) {
int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110,
123, 133, 135, 155, 170, 171, 1100, 1110, 1123,
1133, 1135, 1155, 1170, 1171, 11100, 12310};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_LE(array[0], 10);
ASSERT_LE(array[1], 23);
@@ -69,14 +72,11 @@ public:
void test_reversed_sorted_array(SortingRoutine sort_func) {
int array[] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ int_sort(sort_func, array, ARRAY_LEN);
- sort_func(arr);
-
- for (int i = 0; i < int(ARRAY_SIZE - 1); ++i)
+ for (int i = 0; i < int(ARRAY_LEN - 1); ++i)
ASSERT_EQ(array[i], i + 1);
}
@@ -84,14 +84,11 @@ public:
int array[] = {100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
- for (size_t i = 0; i < ARRAY_SIZE; ++i)
+ for (size_t i = 0; i < ARRAY_LEN; ++i)
ASSERT_EQ(array[i], 100);
}
@@ -99,12 +96,9 @@ public:
int array[25] = {10, 23, 8, 35, 55, 45, 40, 100, 110,
123, 90, 80, 70, 60, 171, 11, 1, -1,
-5, -10, 1155, 1170, 1171, 12, -100};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], -100);
ASSERT_EQ(array[1], -10);
@@ -135,12 +129,9 @@ public:
void test_unsorted_array_2(SortingRoutine sort_func) {
int array[7] = {10, 40, 45, 55, 35, 23, 60};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
-
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 10);
ASSERT_EQ(array[1], 23);
@@ -153,12 +144,9 @@ public:
void test_unsorted_array_duplicated_1(SortingRoutine sort_func) {
int array[6] = {10, 10, 20, 20, 5, 5};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 5);
ASSERT_EQ(array[1], 5);
@@ -170,12 +158,9 @@ public:
void test_unsorted_array_duplicated_2(SortingRoutine sort_func) {
int array[10] = {20, 10, 10, 10, 10, 20, 21, 21, 21, 21};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 10);
ASSERT_EQ(array[1], 10);
@@ -191,12 +176,9 @@ public:
void test_unsorted_array_duplicated_3(SortingRoutine sort_func) {
int array[10] = {20, 30, 30, 30, 30, 20, 21, 21, 21, 21};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
-
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 20);
ASSERT_EQ(array[1], 20);
@@ -213,12 +195,9 @@ public:
void test_unsorted_three_element_1(SortingRoutine sort_func) {
int array[3] = {14999024, 0, 3};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 0);
ASSERT_EQ(array[1], 3);
@@ -228,12 +207,9 @@ public:
void test_unsorted_three_element_2(SortingRoutine sort_func) {
int array[3] = {3, 14999024, 0};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 0);
ASSERT_EQ(array[1], 3);
@@ -243,12 +219,9 @@ public:
void test_unsorted_three_element_3(SortingRoutine sort_func) {
int array[3] = {3, 0, 14999024};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
-
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 0);
ASSERT_EQ(array[1], 3);
@@ -258,12 +231,9 @@ public:
void test_same_three_element(SortingRoutine sort_func) {
int array[3] = {12345, 12345, 12345};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 12345);
ASSERT_EQ(array[1], 12345);
@@ -273,12 +243,9 @@ public:
void test_unsorted_two_element_1(SortingRoutine sort_func) {
int array[] = {14999024, 0};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 0);
ASSERT_EQ(array[1], 14999024);
@@ -287,12 +254,9 @@ public:
void test_unsorted_two_element_2(SortingRoutine sort_func) {
int array[] = {0, 14999024};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
-
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 0);
ASSERT_EQ(array[1], 14999024);
@@ -301,12 +265,9 @@ public:
void test_same_two_element(SortingRoutine sort_func) {
int array[] = {12345, 12345};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 12345);
ASSERT_EQ(array[1], 12345);
@@ -315,15 +276,80 @@ public:
void test_single_element(SortingRoutine sort_func) {
int array[] = {12345};
- constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
-
- auto arr = Array(reinterpret_cast<uint8_t *>(array), ARRAY_SIZE,
- sizeof(int), Comparator(int_compare));
+ constexpr size_t ARRAY_LEN = sizeof(array) / sizeof(int);
- sort_func(arr);
+ int_sort(sort_func, array, ARRAY_LEN);
ASSERT_EQ(array[0], 12345);
}
+
+ void test_different_elem_size(SortingRoutine sort_func) {
+ // Random order of values [0,50) to avoid only testing pre-sorted handling.
+ // Long enough to reach interesting code.
+ constexpr uint8_t ARRAY_INITIAL_VALS[] = {
+ 42, 13, 8, 4, 17, 28, 20, 32, 22, 29, 7, 2, 46, 37, 26, 49, 24,
+ 38, 10, 18, 40, 36, 47, 15, 11, 48, 44, 33, 1, 5, 16, 35, 39, 41,
+ 14, 23, 3, 9, 6, 27, 21, 25, 31, 45, 12, 43, 34, 30, 19, 0};
+
+ constexpr size_t ARRAY_LEN = sizeof(ARRAY_INITIAL_VALS);
+ constexpr size_t MAX_ELEM_SIZE = 150;
+ constexpr size_t BUF_SIZE = ARRAY_LEN * MAX_ELEM_SIZE;
+
+ static_assert(ARRAY_LEN < 256); // so we can encode the values.
+
+ // Minimum alignment to test implementation for bugs related to assuming
+ // incorrect association between alignment and element size. The buffer is
+ // 'static' as otherwise it will exhaust the stack on the GPU targets.
+ alignas(1) static uint8_t buf[BUF_SIZE];
+
+ // GCC still requires capturing the constant ARRAY_INITIAL_VALS in the
+ // lambda hence, let's use & to implicitly capture all needed variables
+ // automatically.
+ const auto fill_buf = [&](size_t elem_size) {
+ for (size_t i = 0; i < BUF_SIZE; ++i) {
+ buf[i] = 0;
+ }
+
+ for (size_t elem_i = 0, buf_i = 0; elem_i < ARRAY_LEN; ++elem_i) {
+ const uint8_t elem_val = ARRAY_INITIAL_VALS[elem_i];
+ for (size_t elem_byte_i = 0; elem_byte_i < elem_size; ++elem_byte_i) {
+ buf[buf_i] = elem_val;
+ buf_i += 1;
+ }
+ }
+ };
+
+ for (size_t elem_size = 0; elem_size <= MAX_ELEM_SIZE; ++elem_size) {
+ // Fill all bytes with data to ensure mistakes in elem swap are noticed.
+ fill_buf(elem_size);
+
+ sort_func(reinterpret_cast<void *>(buf), ARRAY_LEN, elem_size,
+ [](const void *a, const void *b) -> int {
+ const uint8_t a_val = *reinterpret_cast<const uint8_t *>(a);
+ const uint8_t b_val = *reinterpret_cast<const uint8_t *>(b);
+
+ if (a_val < b_val) {
+ return -1;
+ } else if (a_val > b_val) {
+ return 1;
+ } else {
+ return 0;
+ }
+ });
+
+ for (size_t elem_i = 0, buf_i = 0; elem_i < ARRAY_LEN; ++elem_i) {
+ const uint8_t expected_elem_val = static_cast<uint8_t>(elem_i);
+
+ for (size_t elem_byte_i = 0; elem_byte_i < elem_size; ++elem_byte_i) {
+ const uint8_t buf_val = buf[buf_i];
+ // Check that every byte in the element has the expected value.
+ ASSERT_EQ(buf_val, expected_elem_val)
+ << "elem_size: " << elem_size << " buf_i: " << buf_i << '\n';
+ buf_i += 1;
+ }
+ }
+ }
+ }
};
#define LIST_SORTING_TESTS(Name, Func) \
@@ -374,4 +400,7 @@ public:
TEST_F(LlvmLibc##Name##Test, SingleElementArray) { \
test_single_element(Func); \
} \
+ TEST_F(LlvmLibc##Name##Test, DifferentElemSizeArray) { \
+ test_different_elem_size(Func); \
+ } \
static_assert(true)
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-31 22:34:08 +0000