77 lines · c
1//===-- Implementation header for qsort utilities ---------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H10#define LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H11 12#include "src/stdlib/heap_sort.h"13#include "src/stdlib/quick_sort.h"14 15#define LIBC_QSORT_QUICK_SORT 116#define LIBC_QSORT_HEAP_SORT 217 18#ifndef LIBC_QSORT_IMPL19#define LIBC_QSORT_IMPL LIBC_QSORT_QUICK_SORT20#endif // LIBC_QSORT_IMPL21 22#if (LIBC_QSORT_IMPL != LIBC_QSORT_QUICK_SORT && \23 LIBC_QSORT_IMPL != LIBC_QSORT_HEAP_SORT)24#error "LIBC_QSORT_IMPL is not recognized."25#endif26 27namespace LIBC_NAMESPACE_DECL {28namespace internal {29 30template <bool USE_QUICKSORT, typename F>31LIBC_INLINE void unstable_sort_impl(void *array, size_t array_len,32 size_t elem_size, const F &is_less) {33 if (array == nullptr || array_len == 0 || elem_size == 0)34 return;35 36 if constexpr (USE_QUICKSORT) {37 switch (elem_size) {38 case 4: {39 auto arr_fixed_size = internal::ArrayFixedSize<4>(array, array_len);40 quick_sort(arr_fixed_size, is_less);41 return;42 }43 case 8: {44 auto arr_fixed_size = internal::ArrayFixedSize<8>(array, array_len);45 quick_sort(arr_fixed_size, is_less);46 return;47 }48 case 16: {49 auto arr_fixed_size = internal::ArrayFixedSize<16>(array, array_len);50 quick_sort(arr_fixed_size, is_less);51 return;52 }53 default:54 auto arr_generic_size =55 internal::ArrayGenericSize(array, array_len, elem_size);56 quick_sort(arr_generic_size, is_less);57 return;58 }59 } else {60 auto arr_generic_size =61 internal::ArrayGenericSize(array, array_len, elem_size);62 heap_sort(arr_generic_size, is_less);63 }64}65 66template <typename F>67LIBC_INLINE void unstable_sort(void *array, size_t array_len, size_t elem_size,68 const F &is_less) {69#define USE_QUICK_SORT ((LIBC_QSORT_IMPL) == (LIBC_QSORT_QUICK_SORT))70 unstable_sort_impl<USE_QUICK_SORT, F>(array, array_len, elem_size, is_less);71}72 73} // namespace internal74} // namespace LIBC_NAMESPACE_DECL75 76#endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H77