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/__support/macros/attributes.h"
13 #include <stdint.h>
14 #include <stdlib.h>
15
16 namespace LIBC_NAMESPACE::internal {
17
18 // A simple quicksort implementation using the Hoare partition scheme.
19
20 using Compare = int(const void *, const void *);
21 using CompareWithState = int(const void *, const void *, void *);
22
23 enum class CompType { COMPARE, COMPARE_WITH_STATE };
24
25 struct Comparator {
26 union {
27 Compare *comp_func;
28 CompareWithState *comp_func_r;
29 };
30 const CompType comp_type;
31
32 void *arg;
33
ComparatorComparator34 Comparator(Compare *func)
35 : comp_func(func), comp_type(CompType::COMPARE), arg(nullptr) {}
36
ComparatorComparator37 Comparator(CompareWithState *func, void *arg_val)
38 : comp_func_r(func), comp_type(CompType::COMPARE_WITH_STATE),
39 arg(arg_val) {}
40
41 #if defined(__clang__)
42 // Recent upstream changes to -fsanitize=function find more instances of
43 // function type mismatches. One case is with the comparator passed to this
44 // class. Libraries will tend to pass comparators that take pointers to
45 // varying types while this comparator expects to accept const void pointers.
46 // Ideally those tools would pass a function that strictly accepts const
47 // void*s to avoid UB, or would use qsort_r to pass their own comparator.
48 [[clang::no_sanitize("function")]]
49 #endif
comp_valsComparator50 int comp_vals(const void *a, const void *b) const {
51 if (comp_type == CompType::COMPARE) {
52 return comp_func(a, b);
53 } else {
54 return comp_func_r(a, b, arg);
55 }
56 }
57 };
58
59 class Array {
60 uint8_t *array;
61 size_t array_size;
62 size_t elem_size;
63 Comparator compare;
64
65 public:
Array(uint8_t * a,size_t s,size_t e,Comparator c)66 Array(uint8_t *a, size_t s, size_t e, Comparator c)
67 : array(a), array_size(s), elem_size(e), compare(c) {}
68
get(size_t i)69 uint8_t *get(size_t i) const { return array + i * elem_size; }
70
swap(size_t i,size_t j)71 void swap(size_t i, size_t j) const {
72 uint8_t *elem_i = get(i);
73 uint8_t *elem_j = get(j);
74 for (size_t b = 0; b < elem_size; ++b) {
75 uint8_t temp = elem_i[b];
76 elem_i[b] = elem_j[b];
77 elem_j[b] = temp;
78 }
79 }
80
elem_compare(size_t i,const uint8_t * other)81 int elem_compare(size_t i, const uint8_t *other) const {
82 // An element must compare equal to itself so we don't need to consult the
83 // user provided comparator.
84 if (get(i) == other)
85 return 0;
86 return compare.comp_vals(get(i), other);
87 }
88
size()89 size_t size() const { return array_size; }
90
91 // Make an Array starting at index |i| and size |s|.
make_array(size_t i,size_t s)92 Array make_array(size_t i, size_t s) const {
93 return Array(get(i), s, elem_size, compare);
94 }
95 };
96
partition(const Array & array)97 static size_t partition(const Array &array) {
98 const size_t array_size = array.size();
99 size_t pivot_index = array_size / 2;
100 uint8_t *pivot = array.get(pivot_index);
101 size_t i = 0;
102 size_t j = array_size - 1;
103
104 while (true) {
105 int compare_i, compare_j;
106
107 while ((compare_i = array.elem_compare(i, pivot)) < 0)
108 ++i;
109 while ((compare_j = array.elem_compare(j, pivot)) > 0)
110 --j;
111
112 // At some point i will crossover j so we will definitely break out of
113 // this while loop.
114 if (i >= j)
115 return j + 1;
116
117 array.swap(i, j);
118
119 // The pivot itself might have got swapped so we will update the pivot.
120 if (i == pivot_index) {
121 pivot = array.get(j);
122 pivot_index = j;
123 } else if (j == pivot_index) {
124 pivot = array.get(i);
125 pivot_index = i;
126 }
127
128 if (compare_i == 0 && compare_j == 0) {
129 // If we do not move the pointers, we will end up with an
130 // infinite loop as i and j will be stuck without advancing.
131 ++i;
132 --j;
133 }
134 }
135 }
136
quicksort(const Array & array)137 LIBC_INLINE void quicksort(const Array &array) {
138 const size_t array_size = array.size();
139 if (array_size <= 1)
140 return;
141 size_t split_index = partition(array);
142 if (array_size <= 2) {
143 // The partition operation sorts the two element array.
144 return;
145 }
146 quicksort(array.make_array(0, split_index));
147 quicksort(array.make_array(split_index, array.size() - split_index));
148 }
149
150 } // namespace LIBC_NAMESPACE::internal
151
152 #endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H
153