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_QUICK_SORT_H
10 #define LLVM_LIBC_SRC_STDLIB_QUICK_SORT_H
11
12 #include "src/__support/macros/attributes.h"
13 #include "src/__support/macros/config.h"
14 #include "src/stdlib/qsort_data.h"
15
16 #include <stdint.h>
17
18 namespace LIBC_NAMESPACE_DECL {
19 namespace internal {
20
21 // A simple quicksort implementation using the Hoare partition scheme.
partition(const Array & array)22 LIBC_INLINE size_t partition(const Array &array) {
23 const size_t array_size = array.size();
24 size_t pivot_index = array_size / 2;
25 uint8_t *pivot = array.get(pivot_index);
26 size_t i = 0;
27 size_t j = array_size - 1;
28
29 while (true) {
30 int compare_i, compare_j;
31
32 while ((compare_i = array.elem_compare(i, pivot)) < 0)
33 ++i;
34 while ((compare_j = array.elem_compare(j, pivot)) > 0)
35 --j;
36
37 // At some point i will crossover j so we will definitely break out of
38 // this while loop.
39 if (i >= j)
40 return j + 1;
41
42 array.swap(i, j);
43
44 // The pivot itself might have got swapped so we will update the pivot.
45 if (i == pivot_index) {
46 pivot = array.get(j);
47 pivot_index = j;
48 } else if (j == pivot_index) {
49 pivot = array.get(i);
50 pivot_index = i;
51 }
52
53 if (compare_i == 0 && compare_j == 0) {
54 // If we do not move the pointers, we will end up with an
55 // infinite loop as i and j will be stuck without advancing.
56 ++i;
57 --j;
58 }
59 }
60 }
61
quick_sort(Array array)62 LIBC_INLINE void quick_sort(Array array) {
63 while (true) {
64 const size_t array_size = array.size();
65 if (array_size <= 1)
66 return;
67 size_t split_index = partition(array);
68 if (array_size == 2)
69 // The partition operation sorts the two element array.
70 return;
71
72 // Make Arrays describing the two sublists that still need sorting.
73 Array left = array.make_array(0, split_index);
74 Array right = array.make_array(split_index, array.size() - split_index);
75
76 // Recurse to sort the smaller of the two, and then loop round within this
77 // function to sort the larger. This way, recursive call depth is bounded
78 // by log2 of the total array size, because every recursive call is sorting
79 // a list at most half the length of the one in its caller.
80 if (left.size() < right.size()) {
81 quick_sort(left);
82 array.reset_bounds(right.get(0), right.size());
83 } else {
84 quick_sort(right);
85 array.reset_bounds(left.get(0), left.size());
86 }
87 }
88 }
89
90 } // namespace internal
91 } // namespace LIBC_NAMESPACE_DECL
92
93 #endif // LLVM_LIBC_SRC_STDLIB_QUICK_SORT_H
94