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