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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H 10 #define LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H 11 12 #include "src/stdlib/heap_sort.h" 13 #include "src/stdlib/quick_sort.h" 14 15 #define LIBC_QSORT_QUICK_SORT 1 16 #define LIBC_QSORT_HEAP_SORT 2 17 18 #ifndef LIBC_QSORT_IMPL 19 #define LIBC_QSORT_IMPL LIBC_QSORT_QUICK_SORT 20 #endif // LIBC_QSORT_IMPL 21 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 #endif 26 27 namespace LIBC_NAMESPACE_DECL { 28 namespace internal { 29 30 template <bool USE_QUICKSORT, typename F> 31 LIBC_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 66 template <typename F> 67 LIBC_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 internal 74 } // namespace LIBC_NAMESPACE_DECL 75 76 #endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H 77