186 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_QUICK_SORT_H10#define LLVM_LIBC_SRC_STDLIB_QUICK_SORT_H11 12#include "hdr/stdint_proxy.h"13#include "src/__support/CPP/bit.h"14#include "src/__support/CPP/cstddef.h"15#include "src/__support/macros/config.h"16#include "src/stdlib/qsort_pivot.h"17 18namespace LIBC_NAMESPACE_DECL {19namespace internal {20 21// Branchless Lomuto partition based on the implementation by Lukas22// Bergdoll and Orson Peters23// https://github.com/Voultapher/sort-research-rs/blob/main/writeup/lomcyc_partition/text.md.24// Simplified to avoid having to stack allocate.25template <typename A, typename F>26LIBC_INLINE size_t partition_lomuto_branchless(const A &array,27 const void *pivot,28 const F &is_less) {29 const size_t array_len = array.len();30 31 size_t left = 0;32 size_t right = 0;33 34 while (right < array_len) {35 const bool right_is_lt = is_less(array.get(right), pivot);36 array.swap(left, right);37 left += static_cast<size_t>(right_is_lt);38 right += 1;39 }40 41 return left;42}43 44// Optimized for large types that are expensive to move. Not optimized45// for integers. It's possible to use a cyclic permutation here for46// large types as done in ipnsort but the advantages of this are limited47// as `is_less` is a small wrapper around a call to a function pointer48// and won't incur much binary-size overhead. The other reason to use49// cyclic permutation is to have more efficient swapping, but we don't50// know the element size so this isn't applicable here either.51template <typename A, typename F>52LIBC_INLINE size_t partition_hoare_branchy(const A &array, const void *pivot,53 const F &is_less) {54 const size_t array_len = array.len();55 56 size_t left = 0;57 size_t right = array_len;58 59 while (true) {60 while (left < right && is_less(array.get(left), pivot))61 ++left;62 63 while (true) {64 --right;65 if (left >= right || is_less(array.get(right), pivot)) {66 break;67 }68 }69 70 if (left >= right)71 break;72 73 array.swap(left, right);74 ++left;75 }76 77 return left;78}79 80template <typename A, typename F>81LIBC_INLINE size_t partition(const A &array, size_t pivot_index,82 const F &is_less) {83 // Place the pivot at the beginning of the array.84 if (pivot_index != 0) {85 array.swap(0, pivot_index);86 }87 88 const A array_without_pivot = array.make_array(1, array.len() - 1);89 const void *pivot = array.get(0);90 91 size_t num_lt;92 if constexpr (A::has_fixed_size()) {93 // Branchless Lomuto avoid branch misprediction penalties, but94 // it also swaps more often which is only faster if the swap is a fast95 // constant operation.96 num_lt = partition_lomuto_branchless(array_without_pivot, pivot, is_less);97 } else {98 num_lt = partition_hoare_branchy(array_without_pivot, pivot, is_less);99 }100 101 // Place the pivot between the two partitions.102 array.swap(0, num_lt);103 104 return num_lt;105}106 107template <typename A, typename F>108LIBC_INLINE void quick_sort_impl(A &array, const void *ancestor_pivot,109 size_t limit, const F &is_less) {110 while (true) {111 const size_t array_len = array.len();112 if (array_len <= 1)113 return;114 115 // If too many bad pivot choices were made, simply fall back to116 // heapsort in order to guarantee `O(N x log(N))` worst-case.117 if (limit == 0) {118 heap_sort(array, is_less);119 return;120 }121 122 limit -= 1;123 124 const size_t pivot_index = choose_pivot(array, is_less);125 126 // If the chosen pivot is equal to the predecessor, then it's the smallest127 // element in the slice. Partition the slice into elements equal to and128 // elements greater than the pivot. This case is usually hit when the slice129 // contains many duplicate elements.130 if (ancestor_pivot) {131 if (!is_less(ancestor_pivot, array.get(pivot_index))) {132 const size_t num_lt =133 partition(array, pivot_index,134 [is_less](const void *a, const void *b) -> bool {135 return !is_less(b, a);136 });137 138 // Continue sorting elements greater than the pivot. We know that139 // `num_lt` cont140 array.reset_bounds(num_lt + 1, array.len() - (num_lt + 1));141 ancestor_pivot = nullptr;142 continue;143 }144 }145 146 size_t split_index = partition(array, pivot_index, is_less);147 148 if (array_len == 2)149 // The partition operation sorts the two element array.150 return;151 152 // Split the array into `left`, `pivot`, and `right`.153 A left = array.make_array(0, split_index);154 const void *pivot = array.get(split_index);155 const size_t right_start = split_index + 1;156 A right = array.make_array(right_start, array.len() - right_start);157 158 // Recurse into the left side. We have a fixed recursion limit,159 // testing shows no real benefit for recursing into the shorter160 // side.161 quick_sort_impl(left, ancestor_pivot, limit, is_less);162 163 // Continue with the right side.164 array = right;165 ancestor_pivot = pivot;166 }167}168 169constexpr size_t ilog2(size_t n) {170 return static_cast<size_t>(cpp::bit_width(n)) - 1;171}172 173template <typename A, typename F>174LIBC_INLINE void quick_sort(A &array, const F &is_less) {175 const void *ancestor_pivot = nullptr;176 // Limit the number of imbalanced partitions to `2 * floor(log2(len))`.177 // The binary OR by one is used to eliminate the zero-check in the logarithm.178 const size_t limit = 2 * ilog2((array.len() | 1));179 quick_sort_impl(array, ancestor_pivot, limit, is_less);180}181 182} // namespace internal183} // namespace LIBC_NAMESPACE_DECL184 185#endif // LLVM_LIBC_SRC_STDLIB_QUICK_SORT_H186