From d3074f16a6f6b3447bf728d8a6d19f35f02179db Mon Sep 17 00:00:00 2001 From: Michael Jones Date: Thu, 8 Jun 2023 14:04:55 -0700 Subject: [PATCH] [libc] Add qsort_r 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. Reviewed By: sivachandra, lntue Differential Revision: https://reviews.llvm.org/D152467 --- libc/config/linux/aarch64/entrypoints.txt | 1 + libc/config/linux/api.td | 1 + libc/config/linux/arm/entrypoints.txt | 1 + libc/config/linux/riscv64/entrypoints.txt | 1 + libc/config/linux/x86_64/entrypoints.txt | 1 + libc/include/CMakeLists.txt | 1 + libc/include/llvm-libc-types/CMakeLists.txt | 1 + libc/include/llvm-libc-types/__qsortrcompare_t.h | 14 ++ libc/spec/gnu_ext.td | 17 +++ libc/src/stdlib/CMakeLists.txt | 20 +++ libc/src/stdlib/qsort.cpp | 112 +-------------- libc/src/stdlib/qsort_r.cpp | 28 ++++ libc/src/stdlib/qsort_r.h | 26 ++++ libc/src/stdlib/qsort_util.h | 152 +++++++++++++++++++++ libc/test/src/stdlib/CMakeLists.txt | 12 ++ libc/test/src/stdlib/qsort_r_test.cpp | 144 +++++++++++++++++++ utils/bazel/llvm-project-overlay/libc/BUILD.bazel | 20 +++ .../libc/test/src/stdlib/BUILD.bazel | 8 ++ 18 files changed, 451 insertions(+), 109 deletions(-) create mode 100644 libc/include/llvm-libc-types/__qsortrcompare_t.h create mode 100644 libc/src/stdlib/qsort_r.cpp create mode 100644 libc/src/stdlib/qsort_r.h create mode 100644 libc/src/stdlib/qsort_util.h create mode 100644 libc/test/src/stdlib/qsort_r_test.cpp diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt index 2020a45..d6c1ed7 100644 --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -102,6 +102,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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 diff --git a/libc/config/linux/api.td b/libc/config/linux/api.td index 4aa06c7..73cc5be 100644 --- a/libc/config/linux/api.td +++ b/libc/config/linux/api.td @@ -87,6 +87,7 @@ def StdlibAPI : PublicAPI<"stdlib.h"> { "size_t", "__bsearchcompare_t", "__qsortcompare_t", + "__qsortrcompare_t", "__atexithandler_t", ]; } diff --git a/libc/config/linux/arm/entrypoints.txt b/libc/config/linux/arm/entrypoints.txt index 73d11100..27c0b8e 100644 --- a/libc/config/linux/arm/entrypoints.txt +++ b/libc/config/linux/arm/entrypoints.txt @@ -80,6 +80,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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 diff --git a/libc/config/linux/riscv64/entrypoints.txt b/libc/config/linux/riscv64/entrypoints.txt index 85e1364..318f015 100644 --- a/libc/config/linux/riscv64/entrypoints.txt +++ b/libc/config/linux/riscv64/entrypoints.txt @@ -104,6 +104,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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 diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt index 546e792..1277c61 100644 --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -104,6 +104,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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 diff --git a/libc/include/CMakeLists.txt b/libc/include/CMakeLists.txt index 9482e16..f7b949f 100644 --- a/libc/include/CMakeLists.txt +++ b/libc/include/CMakeLists.txt @@ -202,6 +202,7 @@ add_gen_header( .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 ) diff --git a/libc/include/llvm-libc-types/CMakeLists.txt b/libc/include/llvm-libc-types/CMakeLists.txt index 0ff124a..ae9b335 100644 --- a/libc/include/llvm-libc-types/CMakeLists.txt +++ b/libc/include/llvm-libc-types/CMakeLists.txt @@ -12,6 +12,7 @@ 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) diff --git a/libc/include/llvm-libc-types/__qsortrcompare_t.h b/libc/include/llvm-libc-types/__qsortrcompare_t.h new file mode 100644 index 0000000..febf79d --- /dev/null +++ b/libc/include/llvm-libc-types/__qsortrcompare_t.h @@ -0,0 +1,14 @@ +//===-- 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__ diff --git a/libc/spec/gnu_ext.td b/libc/spec/gnu_ext.td index d027335..a358caf 100644 --- a/libc/spec/gnu_ext.td +++ b/libc/spec/gnu_ext.td @@ -2,6 +2,8 @@ def CpuSetT : NamedType<"cpu_set_t">; def CpuSetPtr : PtrType; def ConstCpuSetPtr : ConstType; +def QSortRCompareT : NamedType<"__qsortrcompare_t">; + def GnuExtensions : StandardSpec<"GNUExtensions"> { NamedType CookieIOFunctionsT = NamedType<"cookie_io_functions_t">; HeaderSpec CType = HeaderSpec< @@ -160,6 +162,20 @@ def GnuExtensions : StandardSpec<"GNUExtensions"> { ] >; + HeaderSpec StdLib = HeaderSpec< + "stdlib.h", + [], // Macros + [QSortRCompareT], // Types + [], // Enumerations + [ + FunctionSpec< + "qsort_r", + RetValSpec, + [ArgSpec, ArgSpec, ArgSpec, ArgSpec, ArgSpec] + >, + ] + >; + HeaderSpec PThread = HeaderSpec< "pthread.h", [], // Macros @@ -224,6 +240,7 @@ def GnuExtensions : StandardSpec<"GNUExtensions"> { SendFile, SysAuxv, StdIO, + StdLib, String, UniStd, ]; diff --git a/libc/src/stdlib/CMakeLists.txt b/libc/src/stdlib/CMakeLists.txt index 1a55db1..9b868ba 100644 --- a/libc/src/stdlib/CMakeLists.txt +++ b/libc/src/stdlib/CMakeLists.txt @@ -202,6 +202,14 @@ add_entrypoint_object( libc.include.stdlib ) +add_header_library( + qsort_util + HDRS + qsort_util.h + DEPENDS + libc.include.stdlib +) + add_entrypoint_object( qsort SRCS @@ -209,6 +217,18 @@ add_entrypoint_object( 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 ) diff --git a/libc/src/stdlib/qsort.cpp b/libc/src/stdlib/qsort.cpp index 0efeea9..73cf5f8 100644 --- a/libc/src/stdlib/qsort.cpp +++ b/libc/src/stdlib/qsort.cpp @@ -8,126 +8,20 @@ #include "src/stdlib/qsort.h" #include "src/__support/common.h" +#include "src/stdlib/qsort_util.h" #include 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(array), - array_size, elem_size, compare)); + array_size, elem_size, c)); } } // namespace __llvm_libc diff --git a/libc/src/stdlib/qsort_r.cpp b/libc/src/stdlib/qsort_r.cpp new file mode 100644 index 0000000..add0308 --- /dev/null +++ b/libc/src/stdlib/qsort_r.cpp @@ -0,0 +1,28 @@ +//===-- 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 + +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(array), + array_size, elem_size, c)); +} + +} // namespace __llvm_libc diff --git a/libc/src/stdlib/qsort_r.h b/libc/src/stdlib/qsort_r.h new file mode 100644 index 0000000..a998b05 --- /dev/null +++ b/libc/src/stdlib/qsort_r.h @@ -0,0 +1,26 @@ +//===-- 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 + +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 diff --git a/libc/src/stdlib/qsort_util.h b/libc/src/stdlib/qsort_util.h new file mode 100644 index 0000000..e9aefe4 --- /dev/null +++ b/libc/src/stdlib/qsort_util.h @@ -0,0 +1,152 @@ +//===-- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H +#define LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H + +#include "src/__support/macros/attributes.h" +#include +#include + +namespace __llvm_libc::internal { + +// A simple quicksort implementation using the Hoare partition scheme. + +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; + +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; + } + } + + 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.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); + } +}; + +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; + } + } +} + +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 __llvm_libc::internal + +#endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H diff --git a/libc/test/src/stdlib/CMakeLists.txt b/libc/test/src/stdlib/CMakeLists.txt index 071ffd2..73d3d6d 100644 --- a/libc/test/src/stdlib/CMakeLists.txt +++ b/libc/test/src/stdlib/CMakeLists.txt @@ -259,6 +259,18 @@ add_libc_test( 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 diff --git a/libc/test/src/stdlib/qsort_r_test.cpp b/libc/test/src/stdlib/qsort_r_test.cpp new file mode 100644 index 0000000..ceb58fc --- /dev/null +++ b/libc/test/src/stdlib/qsort_r_test.cpp @@ -0,0 +1,144 @@ +//===-- 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 + +static int int_compare_count(const void *l, const void *r, void *count_arg) { + int li = *reinterpret_cast(l); + int ri = *reinterpret_cast(r); + size_t *count = reinterpret_cast(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 +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(erased_func_ptr); + const T *lt = reinterpret_cast(l); + const T *rt = reinterpret_cast(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, + reinterpret_cast(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); +} diff --git a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel index bfe40c0..84c5c9b 100644 --- a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel @@ -1859,12 +1859,32 @@ libc_function( ], ) +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", ], ) diff --git a/utils/bazel/llvm-project-overlay/libc/test/src/stdlib/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/test/src/stdlib/BUILD.bazel index 485d61a..43b922f 100644 --- a/utils/bazel/llvm-project-overlay/libc/test/src/stdlib/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/test/src/stdlib/BUILD.bazel @@ -138,6 +138,14 @@ libc_test( ], ) +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"], -- 2.7.4