Merge branch 'users/chapuni/cov/single/base' into users/chapuni/cov/single/switchusers/chapuni/cov/single/switch

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);