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_PIVOT_H 10 #define LLVM_LIBC_SRC_STDLIB_QSORT_PIVOT_H 11 12 #include <stddef.h> // For size_t 13 14 namespace LIBC_NAMESPACE_DECL { 15 namespace internal { 16 17 // Recursively select a pseudomedian if above this threshold. 18 constexpr size_t PSEUDO_MEDIAN_REC_THRESHOLD = 64; 19 20 // Selects a pivot from `array`. Algorithm taken from glidesort by Orson Peters. 21 // 22 // This chooses a pivot by sampling an adaptive amount of points, approximating 23 // the quality of a median of sqrt(n) elements. 24 template <typename A, typename F> 25 size_t choose_pivot(const A &array, const F &is_less) { 26 const size_t len = array.len(); 27 28 if (len < 8) { 29 return 0; 30 } 31 32 const size_t len_div_8 = len / 8; 33 34 const size_t a = 0; // [0, floor(n/8)) 35 const size_t b = len_div_8 * 4; // [4*floor(n/8), 5*floor(n/8)) 36 const size_t c = len_div_8 * 7; // [7*floor(n/8), 8*floor(n/8)) 37 38 if (len < PSEUDO_MEDIAN_REC_THRESHOLD) 39 return median3(array, a, b, c, is_less); 40 else 41 return median3_rec(array, a, b, c, len_div_8, is_less); 42 } 43 44 // Calculates an approximate median of 3 elements from sections a, b, c, or 45 // recursively from an approximation of each, if they're large enough. By 46 // dividing the size of each section by 8 when recursing we have logarithmic 47 // recursion depth and overall sample from f(n) = 3*f(n/8) -> f(n) = 48 // O(n^(log(3)/log(8))) ~= O(n^0.528) elements. 49 template <typename A, typename F> 50 size_t median3_rec(const A &array, size_t a, size_t b, size_t c, size_t n, 51 const F &is_less) { 52 if (n * 8 >= PSEUDO_MEDIAN_REC_THRESHOLD) { 53 const size_t n8 = n / 8; 54 a = median3_rec(array, a, a + (n8 * 4), a + (n8 * 7), n8, is_less); 55 b = median3_rec(array, b, b + (n8 * 4), b + (n8 * 7), n8, is_less); 56 c = median3_rec(array, c, c + (n8 * 4), c + (n8 * 7), n8, is_less); 57 } 58 return median3(array, a, b, c, is_less); 59 } 60 61 /// Calculates the median of 3 elements. 62 template <typename A, typename F> 63 size_t median3(const A &array, size_t a, size_t b, size_t c, const F &is_less) { 64 const void *a_ptr = array.get(a); 65 const void *b_ptr = array.get(b); 66 const void *c_ptr = array.get(c); 67 68 const bool x = is_less(a_ptr, b_ptr); 69 const bool y = is_less(a_ptr, c_ptr); 70 if (x == y) { 71 // If x=y=0 then b, c <= a. In this case we want to return max(b, c). 72 // If x=y=1 then a < b, c. In this case we want to return min(b, c). 73 // By toggling the outcome of b < c using XOR x we get this behavior. 74 const bool z = is_less(b_ptr, c_ptr); 75 return z ^ x ? c : b; 76 } else { 77 // Either c <= a < b or b <= a < c, thus a is our median. 78 return a; 79 } 80 } 81 82 } // namespace internal 83 } // namespace LIBC_NAMESPACE_DECL 84 85 #endif // LLVM_LIBC_SRC_STDLIB_QSORT_PIVOT_H 86