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
16namespace LIBC_NAMESPACE::internal {
17
18// A simple quicksort implementation using the Hoare partition scheme.
19
20using Compare = int(const void *, const void *);
21using CompareWithState = int(const void *, const void *, void *);
22
23enum class CompType { COMPARE, COMPARE_WITH_STATE };
24
25struct Comparator {
26 union {
27 Compare *comp_func;
28 CompareWithState *comp_func_r;
29 };
30 const CompType comp_type;
31
32 void *arg;
33
34 Comparator(Compare *func)
35 : comp_func(func), comp_type(CompType::COMPARE), arg(nullptr) {}
36
37 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
50 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
59class Array {
60 uint8_t *array;
61 size_t array_size;
62 size_t elem_size;
63 Comparator compare;
64
65public:
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
69 uint8_t *get(size_t i) const { return array + i * elem_size; }
70
71 void swap(size_t i, size_t j) const {
72 uint8_t *elem_i = get(i);
73 uint8_t *elem_j = get(i: 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
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(a: get(i), b: other);
87 }
88
89 size_t size() const { return array_size; }
90
91 // Make an Array starting at index |i| and size |s|.
92 Array make_array(size_t i, size_t s) const {
93 return Array(get(i), s, elem_size, compare);
94 }
95};
96
97static 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(i: 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, other: pivot)) < 0)
108 ++i;
109 while ((compare_j = array.elem_compare(i: j, other: 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(i: 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
137LIBC_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: array.make_array(i: 0, s: split_index));
147 quicksort(array: array.make_array(i: split_index, s: array.size() - split_index));
148}
149
150} // namespace LIBC_NAMESPACE::internal
151
152#endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H
153

source code of libc/src/stdlib/qsort_util.h