summaryrefslogtreecommitdiff
path: root/libc/test/src/stdlib
diff options
context:
space:
mode:
Diffstat (limited to 'libc/test/src/stdlib')
-rw-r--r--libc/test/src/stdlib/CMakeLists.txt18
-rw-r--r--libc/test/src/stdlib/SortingTest.h203
-rw-r--r--libc/test/src/stdlib/heap_sort_test.cpp18
-rw-r--r--libc/test/src/stdlib/qsort_r_test.cpp4
-rw-r--r--libc/test/src/stdlib/qsort_test.cpp17
-rw-r--r--libc/test/src/stdlib/quick_sort_test.cpp19
6 files changed, 149 insertions, 130 deletions
diff --git a/libc/test/src/stdlib/CMakeLists.txt b/libc/test/src/stdlib/CMakeLists.txt
index 4ca2043ab4c9..8cc0428632ba 100644
--- a/libc/test/src/stdlib/CMakeLists.txt
+++ b/libc/test/src/stdlib/CMakeLists.txt
@@ -301,18 +301,6 @@ add_libc_test(
)
add_libc_test(
- quick_sort_test
- SUITE
- libc-stdlib-tests
- SRCS
- quick_sort_test.cpp
- HDRS
- SortingTest.h
- DEPENDS
- libc.src.stdlib.qsort_util
-)
-
-add_libc_test(
heap_sort_test
SUITE
libc-stdlib-tests
@@ -321,15 +309,15 @@ add_libc_test(
HDRS
SortingTest.h
DEPENDS
- libc.src.stdlib.qsort_util
+ libc.src.stdlib.qsort
)
add_libc_test(
- qsort_test
+ quick_sort_test
SUITE
libc-stdlib-tests
SRCS
- qsort_test.cpp
+ quick_sort_test.cpp
HDRS
SortingTest.h
DEPENDS
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)
diff --git a/libc/test/src/stdlib/heap_sort_test.cpp b/libc/test/src/stdlib/heap_sort_test.cpp
index d70e3dc2272b..18d4244506ec 100644
--- a/libc/test/src/stdlib/heap_sort_test.cpp
+++ b/libc/test/src/stdlib/heap_sort_test.cpp
@@ -7,10 +7,20 @@
//===----------------------------------------------------------------------===//
#include "SortingTest.h"
-#include "src/stdlib/heap_sort.h"
+#include "src/stdlib/qsort_util.h"
-void sort(const LIBC_NAMESPACE::internal::Array &array) {
- LIBC_NAMESPACE::internal::heap_sort(array);
+void heap_sort(void *array, size_t array_size, size_t elem_size,
+ int (*compare)(const void *, const void *)) {
+
+ constexpr bool USE_QUICKSORT = false;
+
+ const auto is_less = [compare](const void *a,
+ const void *b) noexcept -> bool {
+ return compare(a, b) < 0;
+ };
+
+ LIBC_NAMESPACE::internal::unstable_sort_impl<USE_QUICKSORT>(
+ array, array_size, elem_size, is_less);
}
-LIST_SORTING_TESTS(HeapSort, sort);
+LIST_SORTING_TESTS(HeapSort, heap_sort);
diff --git a/libc/test/src/stdlib/qsort_r_test.cpp b/libc/test/src/stdlib/qsort_r_test.cpp
index 6893fdc7b74c..f18923618ed5 100644
--- a/libc/test/src/stdlib/qsort_r_test.cpp
+++ b/libc/test/src/stdlib/qsort_r_test.cpp
@@ -62,9 +62,9 @@ TEST(LlvmLibcQsortRTest, SortedArray) {
ASSERT_LE(array[23], 11100);
ASSERT_LE(array[24], 12310);
- // This is a sorted list, but there still have to have been at least N
+ // This is a sorted list, but there still have to have been at least N - 1
// comparisons made.
- ASSERT_GE(count, ARRAY_SIZE);
+ ASSERT_GE(count, ARRAY_SIZE - 1);
}
TEST(LlvmLibcQsortRTest, ReverseSortedArray) {
diff --git a/libc/test/src/stdlib/qsort_test.cpp b/libc/test/src/stdlib/qsort_test.cpp
deleted file mode 100644
index 1e921a86fd1f..000000000000
--- a/libc/test/src/stdlib/qsort_test.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-//===-- Unittests for qsort -----------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "SortingTest.h"
-#include "src/stdlib/qsort.h"
-
-void sort(const LIBC_NAMESPACE::internal::Array &array) {
- LIBC_NAMESPACE::qsort(reinterpret_cast<void *>(array.get(0)), array.size(),
- sizeof(int), SortingTest::int_compare);
-}
-
-LIST_SORTING_TESTS(Qsort, sort);
diff --git a/libc/test/src/stdlib/quick_sort_test.cpp b/libc/test/src/stdlib/quick_sort_test.cpp
index d6bf77ebfd40..2832c855370b 100644
--- a/libc/test/src/stdlib/quick_sort_test.cpp
+++ b/libc/test/src/stdlib/quick_sort_test.cpp
@@ -1,4 +1,4 @@
-//===-- Unittests for quick sort ------------------------------------------===//
+//===-- Unittests for qsort -----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
@@ -7,10 +7,19 @@
//===----------------------------------------------------------------------===//
#include "SortingTest.h"
-#include "src/stdlib/quick_sort.h"
+#include "src/stdlib/qsort_util.h"
-void sort(const LIBC_NAMESPACE::internal::Array &array) {
- LIBC_NAMESPACE::internal::quick_sort(array);
+void quick_sort(void *array, size_t array_size, size_t elem_size,
+ int (*compare)(const void *, const void *)) {
+ constexpr bool USE_QUICKSORT = true;
+
+ const auto is_less = [compare](const void *a,
+ const void *b) noexcept -> bool {
+ return compare(a, b) < 0;
+ };
+
+ LIBC_NAMESPACE::internal::unstable_sort_impl<USE_QUICKSORT>(
+ array, array_size, elem_size, is_less);
}
-LIST_SORTING_TESTS(QuickSort, sort);
+LIST_SORTING_TESTS(Qsort, quick_sort);
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-31 19:55:20 +0000