[libc] Add qsort_r

[michaelrj]

Summary

This patch adds the reentrent qsort entrypoint, qsort_r. This is done by
extending the qsort functionality and moving it to a shared utility
header. For this reason the qsort_r tests focus mostly on the places
where it differs from qsort, since they share the same sorting code.

[michaelrj]

add a comment explaining which variety of qsort_r this is, and why.

[sivachandra]

libc/src/stdlib/qsort_util.h

20–39

May be Compare and CompareWithState.

21

Nit: Since you are touching this anyway, you can change it to:

using Compare = int(const void *, const void *);
using CompareWithState = int(const void *, const void *, void *);

24

All caps. Also, if you make it an enum class, then you can get scoped names like COMPARE and COMPARE_WITH_STATE.

[michaelrj]

address comments. I will land this next business day.

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.atoll
     libc.src.stdlib.bsearch
     libc.src.stdlib.div
     libc.src.stdlib.labs
     libc.src.stdlib.ldiv
     libc.src.stdlib.llabs
     libc.src.stdlib.lldiv
     libc.src.stdlib.qsort
+    libc.src.stdlib.qsort_r
     libc.src.stdlib.rand
     libc.src.stdlib.srand
     libc.src.stdlib.strtod
     libc.src.stdlib.strtof
     libc.src.stdlib.strtol
     libc.src.stdlib.strtold
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul

libc/config/linux/api.td

 def StdlibAPI : PublicAPI<"stdlib.h"> {
   let Types = [
     "div_t",
     "ldiv_t",
     "lldiv_t",
     "size_t",
     "__bsearchcompare_t",
     "__qsortcompare_t",
+    "__qsortrcompare_t",
     "__atexithandler_t",
   ];
 }
 
 def TimeAPI : PublicAPI<"time.h"> {
   let Types = [
     "clock_t",
     "time_t",

libc/config/linux/arm/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.atoll
     libc.src.stdlib.bsearch
     libc.src.stdlib.div
     libc.src.stdlib.labs
     libc.src.stdlib.ldiv
     libc.src.stdlib.llabs
     libc.src.stdlib.lldiv
     libc.src.stdlib.qsort
+    libc.src.stdlib.qsort_r
     libc.src.stdlib.strtod
     libc.src.stdlib.strtof
     libc.src.stdlib.strtol
     libc.src.stdlib.strtold
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul
     libc.src.stdlib.strtoull
 

libc/config/linux/riscv64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.atoll
     libc.src.stdlib.bsearch
     libc.src.stdlib.div
     libc.src.stdlib.labs
     libc.src.stdlib.ldiv
     libc.src.stdlib.llabs
     libc.src.stdlib.lldiv
     libc.src.stdlib.qsort
+    libc.src.stdlib.qsort_r
     libc.src.stdlib.rand
     libc.src.stdlib.srand
     libc.src.stdlib.strtod
     libc.src.stdlib.strtof
     libc.src.stdlib.strtol
     libc.src.stdlib.strtold
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.atoll
     libc.src.stdlib.bsearch
     libc.src.stdlib.div
     libc.src.stdlib.labs
     libc.src.stdlib.ldiv
     libc.src.stdlib.llabs
     libc.src.stdlib.lldiv
     libc.src.stdlib.qsort
+    libc.src.stdlib.qsort_r
     libc.src.stdlib.rand
     libc.src.stdlib.srand
     libc.src.stdlib.strtod
     libc.src.stdlib.strtof
     libc.src.stdlib.strtol
     libc.src.stdlib.strtold
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul

libc/include/CMakeLists.txt

DEPENDS
     .llvm_libc_common_h
     .llvm-libc-macros.stdlib_macros
     .llvm-libc-types.div_t
     .llvm-libc-types.ldiv_t
     .llvm-libc-types.lldiv_t
     .llvm-libc-types.size_t
     .llvm-libc-types.__bsearchcompare_t
     .llvm-libc-types.__qsortcompare_t
+    .llvm-libc-types.__qsortrcompare_t
     .llvm-libc-types.__atexithandler_t
 )
 
 add_gen_header(
   unistd
   DEF_FILE unistd.h.def
   GEN_HDR unistd.h
   DEPENDS

libc/include/llvm-libc-types/CMakeLists.txt

 add_header(off64_t HDR off64_t.h)
 add_header(size_t HDR size_t.h)
 add_header(ssize_t HDR ssize_t.h)
 add_header(__atfork_callback_t HDR __atfork_callback_t.h)
 add_header(__bsearchcompare_t HDR __bsearchcompare_t.h)
 add_header(__call_once_func_t HDR __call_once_func_t.h)
 add_header(__exec_argv_t HDR __exec_argv_t.h)
 add_header(__exec_envp_t HDR __exec_envp_t.h)
 add_header(__futex_word HDR __futex_word.h)
 add_header(__mutex_type HDR __mutex_type.h DEPENDS .__futex_word)
 add_header(__pthread_once_func_t HDR __pthread_once_func_t.h)
 add_header(__pthread_start_t HDR __pthread_start_t.h)
 add_header(__pthread_tss_dtor_t HDR __pthread_tss_dtor_t.h)
 add_header(__qsortcompare_t HDR __qsortcompare_t.h)
+add_header(__qsortrcompare_t HDR __qsortrcompare_t.h)
 add_header(__sighandler_t HDR __sighandler_t.h)
 add_header(__thread_type HDR __thread_type.h)
 add_header(blkcnt_t HDR blkcnt_t.h)
 add_header(blksize_t HDR blksize_t.h)
 add_header(cc_t HDR cc_t.h)
 add_header(clock_t HDR clock_t.h)
 add_header(clockid_t HDR clockid_t.h)
 add_header(cnd_t HDR cnd_t.h)

libc/include/llvm-libc-types/__qsortrcompare_t.h

+//===-- Definition of type __qsortrcompare_t ------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef __LLVM_LIBC_TYPES_QSORTRCOMPARE_T_H__
+#define __LLVM_LIBC_TYPES_QSORTRCOMPARE_T_H__
+
+typedef int (*__qsortrcompare_t)(const void *, const void *, void *);
+
+#endif // __LLVM_LIBC_TYPES_QSORTRCOMPARE_T_H__

libc/spec/gnu_ext.td

 def CpuSetT : NamedType<"cpu_set_t">;
 def CpuSetPtr : PtrType<CpuSetT>;
 def ConstCpuSetPtr : ConstType<CpuSetPtr>;
 
+def QSortRCompareT : NamedType<"__qsortrcompare_t">;
+
 def GnuExtensions : StandardSpec<"GNUExtensions"> {
   NamedType CookieIOFunctionsT = NamedType<"cookie_io_functions_t">;
   HeaderSpec CType = HeaderSpec<
     "ctype.h",
     [], // Macros
     [], // Types
     [], // Enumerations
     [
HeaderSpec StdIO = HeaderSpec<
           FunctionSpec<
               "fgetc_unlocked",
               RetValSpec<IntType>,
               [ArgSpec<FILEPtr>]
           >,
       ]
   >;
 
+  HeaderSpec StdLib = HeaderSpec<
+      "stdlib.h",
+      [], // Macros
+      [QSortRCompareT], // Types
+      [], // Enumerations
+      [
+          FunctionSpec<
+                "qsort_r", 
+                RetValSpec<VoidType>, 
+                [ArgSpec<VoidPtr>, ArgSpec<SizeTType>, ArgSpec<SizeTType>, ArgSpec<QSortRCompareT>, ArgSpec<VoidPtr>]
+          >,
+      ]
+  >;
+
   HeaderSpec PThread = HeaderSpec<
       "pthread.h",
       [], // Macros
       [], // Types
       [], // Enumerations
       [
           FunctionSpec<
               "pthread_setname_np",
let Headers = [
     CType,
     FEnv,
     Math,
     PThread,
     Sched,
     SendFile,
     SysAuxv,
     StdIO,
+    StdLib,
     String,
     UniStd,
   ];
 }

libc/src/stdlib/CMakeLists.txt

add_entrypoint_object(
   SRCS
     bsearch.cpp
   HDRS
     bsearch.h
   DEPENDS
     libc.include.stdlib
 )
 
+add_header_library(
+  qsort_util
+  HDRS
+    qsort_util.h
+  DEPENDS
+    libc.include.stdlib
+)
+
 add_entrypoint_object(
   qsort
   SRCS
     qsort.cpp
   HDRS
     qsort.h
   DEPENDS
+    .qsort_util
+    libc.include.stdlib
+)
+
+add_entrypoint_object(
+  qsort_r
+  SRCS
+    qsort_r.cpp
+  HDRS
+    qsort_r.h
+  DEPENDS
+    .qsort_util
     libc.include.stdlib
 )
 
 add_object_library(
   rand_util
   SRCS
     rand_util.cpp
   HDRS

libc/src/stdlib/qsort.cpp

 //===-- Implementation of 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 "src/stdlib/qsort.h"
 #include "src/__support/common.h"
+#include "src/stdlib/qsort_util.h"
 
 #include <stdint.h>
 
 namespace __llvm_libc {
 
-namespace internal {
-
-// A simple quicksort implementation using the Hoare partition scheme.
-
-class Array {
-  typedef int (*comparator)(const void *, const void *);
-
-  uint8_t *array;
-  size_t array_size;
-  size_t elem_size;
-  comparator compare;
-
-public:
-  Array(uint8_t *a, size_t s, size_t e, comparator c)
-      : array(a), array_size(s), elem_size(e), compare(c) {}
-
-  uint8_t *get(size_t i) const { return array + i * elem_size; }
-
-  void swap(size_t i, size_t j) const {
-    uint8_t *elem_i = get(i);
-    uint8_t *elem_j = get(j);
-    for (size_t b = 0; b < elem_size; ++b) {
-      uint8_t temp = elem_i[b];
-      elem_i[b] = elem_j[b];
-      elem_j[b] = temp;
-    }
-  }
-
-#if defined(__clang__)
-  // Recent upstream changes to -fsanitize=function find more instances of
-  // function type mismatches. One case is with the comparator passed to this
-  // class. Libraries like boringssl will tend to pass comparators that take
-  // pointers to varying types while this comparator expects to accept const
-  // void pointers. Ideally those tools would pass a function that strictly
-  // accepts const void*s to avoid UB, or we'd have something like qsort_r/s.
-  [[clang::no_sanitize("function")]]
-#endif
-  int elem_compare(size_t i, const uint8_t *other) const {
-    // An element must compare equal to itself so we don't need to consult the
-    // user provided comparator.
-    if (get(i) == other)
-      return 0;
-    return compare(get(i), other);
-  }
-
-  size_t size() const { return array_size; }
-
-  // Make an Array starting at index |i| and size |s|.
-  Array make_array(size_t i, size_t s) const {
-    return Array(get(i), s, elem_size, compare);
-  }
-};
-
-static size_t partition(const Array &array) {
-  const size_t array_size = array.size();
-  size_t pivot_index = array_size / 2;
-  uint8_t *pivot = array.get(pivot_index);
-  size_t i = 0;
-  size_t j = array_size - 1;
-
-  while (true) {
-    int compare_i, compare_j;
-
-    while ((compare_i = array.elem_compare(i, pivot)) < 0)
-      ++i;
-    while ((compare_j = array.elem_compare(j, pivot)) > 0)
-      --j;
-
-    // At some point i will crossover j so we will definitely break out of
-    // this while loop.
-    if (i >= j)
-      return j + 1;
-
-    array.swap(i, j);
-
-    // The pivot itself might have got swapped so we will update the pivot.
-    if (i == pivot_index) {
-      pivot = array.get(j);
-      pivot_index = j;
-    } else if (j == pivot_index) {
-      pivot = array.get(i);
-      pivot_index = i;
-    }
-
-    if (compare_i == 0 && compare_j == 0) {
-      // If we do not move the pointers, we will end up with an
-      // infinite loop as i and j will be stuck without advancing.
-      ++i;
-      --j;
-    }
-  }
-}
-
-static void quicksort(const Array &array) {
-  const size_t array_size = array.size();
-  if (array_size <= 1)
-    return;
-  size_t split_index = partition(array);
-  if (array_size <= 2) {
-    // The partition operation sorts the two element array.
-    return;
-  }
-  quicksort(array.make_array(0, split_index));
-  quicksort(array.make_array(split_index, array.size() - split_index));
-}
-
-} // namespace internal
-
 LLVM_LIBC_FUNCTION(void, qsort,
                    (void *array, size_t array_size, size_t elem_size,
                     int (*compare)(const void *, const void *))) {
   if (array == nullptr || array_size == 0 || elem_size == 0)
     return;
+  internal::Comparator c(compare);
   internal::quicksort(internal::Array(reinterpret_cast<uint8_t *>(array),
-                                      array_size, elem_size, compare));
+                                      array_size, elem_size, c));
 }
 
 } // namespace __llvm_libc

libc/src/stdlib/qsort_r.h

+//===-- Implementation header for qsort_r -----------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STDLIB_QSORT_R_H
+#define LLVM_LIBC_SRC_STDLIB_QSORT_R_H
+
+#include <stdlib.h>
+
+namespace __llvm_libc {
+
+// This qsort_r uses the glibc argument ordering instead of the BSD argument
+// ordering (which puts arg before the function pointer). Putting arg after the
+// function pointer more closely matches the ordering for qsort_s, which is the
+// standardized equivalent of qsort_r.
+
+void qsort_r(void *array, size_t array_size, size_t elem_size,
+             int (*compare)(const void *, const void *, void *), void *arg);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_QSORT_R_H

libc/src/stdlib/qsort_r.cpp

+//===-- Implementation of qsort_r -----------------------------------------===//
+//
+// 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 "src/stdlib/qsort_r.h"
+#include "src/__support/common.h"
+#include "src/stdlib/qsort_util.h"
+
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(void, qsort_r,
+                   (void *array, size_t array_size, size_t elem_size,
+                    int (*compare)(const void *, const void *, void *),
+                    void *arg)) {
+  if (array == nullptr || array_size == 0 || elem_size == 0)
+    return;
+  internal::Comparator c(compare, arg);
+  internal::quicksort(internal::Array(reinterpret_cast<uint8_t *>(array),
+                                      array_size, elem_size, c));
+}
+
+} // namespace __llvm_libc

libc/src/stdlib/qsort_util.h

-//===-- Implementation of qsort -------------------------------------------===//
+//===-- Implementation header for qsort utilities ---------------*- C++ -*-===//
 //
 // 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 "src/stdlib/qsort.h"
-#include "src/__support/common.h"
+#ifndef LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H
+#define LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H
 
+#include "src/__support/macros/attributes.h"
 #include <stdint.h>
+#include <stdlib.h>
 
-namespace __llvm_libc {
-
-namespace internal {
+namespace __llvm_libc::internal {
 
 // A simple quicksort implementation using the Hoare partition scheme.
 
-class Array {
-  typedef int (*comparator)(const void *, const void *);
+using Compare = int(const void *, const void *);
+using CompareWithState = int(const void *, const void *, void *);
+
+enum class CompType { COMPARE, COMPARE_WITH_STATE };
+
+struct Comparator {
+  union {
+    Compare *comp_func;
+    CompareWithState *comp_func_r;
+  };
+  const CompType comp_type;
+
+  void *arg;
+
+  Comparator(Compare *func)
+      : comp_func(func), comp_type(CompType::COMPARE), arg(nullptr) {}
+
+  Comparator(CompareWithState *func, void *arg_val)
+      : comp_func_r(func), comp_type(CompType::COMPARE_WITH_STATE),
+        arg(arg_val) {}
+
+#if defined(__clang__)
+  // Recent upstream changes to -fsanitize=function find more instances of
+  // function type mismatches. One case is with the comparator passed to this
+  // class. Libraries will tend to pass comparators that take pointers to
+  // varying types while this comparator expects to accept const void pointers.
+  // Ideally those tools would pass a function that strictly accepts const
+  // void*s to avoid UB, or would use qsort_r to pass their own comparator.
+  [[clang::no_sanitize("function")]]
+#endif
+  int comp_vals(const void *a, const void *b) const {
+    if (comp_type == CompType::COMPARE) {
+      return comp_func(a, b);
+    } else {
+      return comp_func_r(a, b, arg);
+    }
+  }
+};
 
+class Array {
   uint8_t *array;
   size_t array_size;
   size_t elem_size;
-  comparator compare;
+  Comparator compare;
 
 public:
-  Array(uint8_t *a, size_t s, size_t e, comparator c)
+  Array(uint8_t *a, size_t s, size_t e, Comparator c)
       : array(a), array_size(s), elem_size(e), compare(c) {}
 
   uint8_t *get(size_t i) const { return array + i * elem_size; }
 
   void swap(size_t i, size_t j) const {
     uint8_t *elem_i = get(i);
     uint8_t *elem_j = get(j);
     for (size_t b = 0; b < elem_size; ++b) {
       uint8_t temp = elem_i[b];
       elem_i[b] = elem_j[b];
       elem_j[b] = temp;
     }
   }
 
-#if defined(__clang__)
-  // Recent upstream changes to -fsanitize=function find more instances of
-  // function type mismatches. One case is with the comparator passed to this
-  // class. Libraries like boringssl will tend to pass comparators that take
-  // pointers to varying types while this comparator expects to accept const
-  // void pointers. Ideally those tools would pass a function that strictly
-  // accepts const void*s to avoid UB, or we'd have something like qsort_r/s.
-  [[clang::no_sanitize("function")]]
-#endif
   int elem_compare(size_t i, const uint8_t *other) const {
     // An element must compare equal to itself so we don't need to consult the
     // user provided comparator.
     if (get(i) == other)
       return 0;
-    return compare(get(i), other);
+    return compare.comp_vals(get(i), other);
   }
 
   size_t size() const { return array_size; }
 
   // Make an Array starting at index |i| and size |s|.
   Array make_array(size_t i, size_t s) const {
     return Array(get(i), s, elem_size, compare);
   }
if (compare_i == 0 && compare_j == 0) {
       // If we do not move the pointers, we will end up with an
       // infinite loop as i and j will be stuck without advancing.
       ++i;
       --j;
     }
   }
 }
 
-static void quicksort(const Array &array) {
+LIBC_INLINE void quicksort(const Array &array) {
   const size_t array_size = array.size();
   if (array_size <= 1)
     return;
   size_t split_index = partition(array);
   if (array_size <= 2) {
     // The partition operation sorts the two element array.
     return;
   }
   quicksort(array.make_array(0, split_index));
   quicksort(array.make_array(split_index, array.size() - split_index));
 }
 
-} // namespace internal
-
-LLVM_LIBC_FUNCTION(void, qsort,
-                   (void *array, size_t array_size, size_t elem_size,
-                    int (*compare)(const void *, const void *))) {
-  if (array == nullptr || array_size == 0 || elem_size == 0)
-    return;
-  internal::quicksort(internal::Array(reinterpret_cast<uint8_t *>(array),
-                                      array_size, elem_size, compare));
-}
+} // namespace __llvm_libc::internal
 
-} // namespace __llvm_libc
+#endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H

libc/test/src/stdlib/CMakeLists.txt

SUITE
     libc-stdlib-tests
   SRCS
     qsort_test.cpp
   DEPENDS
     libc.include.stdlib
     libc.src.stdlib.qsort
 )
 
+
+add_libc_test(
+  qsort_r_test
+  SUITE
+    libc-stdlib-tests
+  SRCS
+    qsort_r_test.cpp
+  DEPENDS
+    libc.include.stdlib
+    libc.src.stdlib.qsort_r
+)
+
 add_libc_test(
   rand_test
   SUITE
     libc-stdlib-tests
   SRCS
     rand_test.cpp
   DEPENDS
     libc.include.stdlib

libc/test/src/stdlib/qsort_r_test.cpp

+//===-- Unittests for qsort_r ---------------------------------------------===//
+//
+// 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 "src/stdlib/qsort_r.h"
+
+#include "test/UnitTest/Test.h"
+
+#include <stdlib.h>
+
+static int int_compare_count(const void *l, const void *r, void *count_arg) {
+  int li = *reinterpret_cast<const int *>(l);
+  int ri = *reinterpret_cast<const int *>(r);
+  size_t *count = reinterpret_cast<size_t *>(count_arg);
+  *count = *count + 1;
+  if (li == ri)
+    return 0;
+  else if (li > ri)
+    return 1;
+  else
+    return -1;
+}
+
+TEST(LlvmLibcQsortRTest, SortedArray) {
+  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);
+
+  size_t count = 0;
+
+  __llvm_libc::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
+                       &count);
+
+  ASSERT_LE(array[0], 10);
+  ASSERT_LE(array[1], 23);
+  ASSERT_LE(array[2], 33);
+  ASSERT_LE(array[3], 35);
+  ASSERT_LE(array[4], 55);
+  ASSERT_LE(array[5], 70);
+  ASSERT_LE(array[6], 71);
+  ASSERT_LE(array[7], 100);
+  ASSERT_LE(array[8], 110);
+  ASSERT_LE(array[9], 123);
+  ASSERT_LE(array[10], 133);
+  ASSERT_LE(array[11], 135);
+  ASSERT_LE(array[12], 155);
+  ASSERT_LE(array[13], 170);
+  ASSERT_LE(array[14], 171);
+  ASSERT_LE(array[15], 1100);
+  ASSERT_LE(array[16], 1110);
+  ASSERT_LE(array[17], 1123);
+  ASSERT_LE(array[18], 1133);
+  ASSERT_LE(array[19], 1135);
+  ASSERT_LE(array[20], 1155);
+  ASSERT_LE(array[21], 1170);
+  ASSERT_LE(array[22], 1171);
+  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
+  // comparisons made.
+  ASSERT_GE(count, ARRAY_SIZE);
+}
+
+TEST(LlvmLibcQsortRTest, ReverseSortedArray) {
+  int array[25] = {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);
+
+  size_t count = 0;
+
+  __llvm_libc::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
+                       &count);
+
+  for (int i = 0; i < int(ARRAY_SIZE - 1); ++i)
+    ASSERT_LE(array[i], i + 1);
+
+  ASSERT_GE(count, ARRAY_SIZE);
+}
+
+// The following test is intended to mimic the CPP library pattern of having a
+// comparison function that takes a specific type, which is passed to a library
+// that then needs to sort an array of that type. The library can't safely pass
+// the comparison function to qsort because a function that takes const T*
+// being cast to a function that takes const void* is undefined behavior. The
+// safer pattern is to pass a type erased comparator that calls into the typed
+// comparator to qsort_r.
+
+struct PriorityVal {
+  int priority;
+  int size;
+};
+
+static int compare_priority_val(const PriorityVal *l, const PriorityVal *r) {
+  // Subtracting the priorities is unsafe, but it's fine for this test.
+  int priority_diff = l->priority - r->priority;
+  if (priority_diff != 0) {
+    return priority_diff;
+  }
+  if (l->size == r->size) {
+    return 0;
+  } else if (l->size > r->size) {
+    return 1;
+  } else {
+    return -1;
+  }
+}
+
+template <typename T>
+static int type_erased_comp(const void *l, const void *r,
+                            void *erased_func_ptr) {
+  typedef int (*TypedComp)(const T *, const T *);
+  TypedComp typed_func_ptr = reinterpret_cast<TypedComp>(erased_func_ptr);
+  const T *lt = reinterpret_cast<const T *>(l);
+  const T *rt = reinterpret_cast<const T *>(r);
+  return typed_func_ptr(lt, rt);
+}
+
+TEST(LlvmLibcQsortRTest, SafeTypeErasure) {
+  PriorityVal array[5] = {
+      {10, 3}, {1, 10}, {-1, 100}, {10, 0}, {3, 3},
+  };
+  constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(PriorityVal);
+
+  __llvm_libc::qsort_r(array, ARRAY_SIZE, sizeof(PriorityVal),
+                       type_erased_comp<PriorityVal>,
+                       reinterpret_cast<void *>(compare_priority_val));
+
+  EXPECT_EQ(array[0].priority, -1);
+  EXPECT_EQ(array[0].size, 100);
+  EXPECT_EQ(array[1].priority, 1);
+  EXPECT_EQ(array[1].size, 10);
+  EXPECT_EQ(array[2].priority, 3);
+  EXPECT_EQ(array[2].size, 3);
+  EXPECT_EQ(array[3].priority, 10);
+  EXPECT_EQ(array[3].size, 0);
+  EXPECT_EQ(array[4].priority, 10);
+  EXPECT_EQ(array[4].size, 3);
+}

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

libc_function(
     name = "bsearch",
     srcs = ["src/stdlib/bsearch.cpp"],
     hdrs = ["src/stdlib/bsearch.h"],
     deps = [
         ":__support_common",
     ],
 )
 
+libc_support_library(
+    name = "qsort_util",
+    hdrs = ["src/stdlib/qsort_util.h"],
+    deps = [
+        ":__support_common",
+        ":__support_macros_attributes",
+    ],
+)
+
 libc_function(
     name = "qsort",
     srcs = ["src/stdlib/qsort.cpp"],
     hdrs = ["src/stdlib/qsort.h"],
     deps = [
         ":__support_common",
+        ":qsort_util",
+    ],
+)
+
+libc_function(
+    name = "qsort_r",
+    srcs = ["src/stdlib/qsort_r.cpp"],
+    hdrs = ["src/stdlib/qsort_r.h"],
+    deps = [
+        ":__support_common",
+        ":qsort_util",
     ],
 )
 
 libc_function(
     name = "strtol",
     srcs = ["src/stdlib/strtol.cpp"],
     hdrs = ["src/stdlib/strtol.h"],
     deps = [

utils/bazel/llvm-project-overlay/libc/test/src/stdlib/BUILD.bazel

 libc_test(
     name = "qsort_test",
     srcs = ["qsort_test.cpp"],
     libc_function_deps = [
         "//libc:qsort",
     ],
 )
 
+libc_test(
+    name = "qsort_r_test",
+    srcs = ["qsort_r_test.cpp"],
+    libc_function_deps = [
+        "//libc:qsort_r",
+    ],
+)
+
 cc_library(
     name = "strtol_test_helper",
     hdrs = ["StrtolTest.h"],
     deps = [
         "//libc:__support_cpp_limits",
         "//libc:__support_cpp_type_traits",
         "//libc:errno.__internal__",
         "//libc/test/UnitTest:LibcUnitTest",