1 //===-- Implementation of qsort -------------------------------------------===//
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 #include "src/stdlib/qsort.h"
10 #include "src/__support/common.h"
11
12 #include <stdint.h>
13
14 namespace __llvm_libc {
15
16 namespace internal {
17
18 // A simple quicksort implementation using the Hoare partition scheme.
19
20 class Array {
21 typedef int (*comparator)(const void *, const void *);
22
23 uint8_t *array;
24 size_t array_size;
25 size_t elem_size;
26 comparator compare;
27
28 public:
Array(uint8_t * a,size_t s,size_t e,comparator c)29 Array(uint8_t *a, size_t s, size_t e, comparator c)
30 : array(a), array_size(s), elem_size(e), compare(c) {}
31
get(size_t i) const32 uint8_t *get(size_t i) const { return array + i * elem_size; }
33
swap(size_t i,size_t j) const34 void swap(size_t i, size_t j) const {
35 uint8_t *elem_i = get(i);
36 uint8_t *elem_j = get(j);
37 for (size_t b = 0; b < elem_size; ++b) {
38 uint8_t temp = elem_i[b];
39 elem_i[b] = elem_j[b];
40 elem_j[b] = temp;
41 }
42 }
43
elem_compare(size_t i,const uint8_t * other) const44 int elem_compare(size_t i, const uint8_t *other) const {
45 // An element must compare equal to itself so we don't need to consult the
46 // user provided comparator.
47 if (get(i) == other)
48 return 0;
49 return compare(get(i), other);
50 }
51
size() const52 size_t size() const { return array_size; }
53
54 // Make an Array starting at index |i| and size |s|.
make_array(size_t i,size_t s) const55 Array make_array(size_t i, size_t s) const {
56 return Array(get(i), s, elem_size, compare);
57 }
58 };
59
partition(const Array & array)60 static size_t partition(const Array &array) {
61 const size_t array_size = array.size();
62 size_t pivot_index = array_size / 2;
63 uint8_t *pivot = array.get(pivot_index);
64 size_t i = 0;
65 size_t j = array_size - 1;
66
67 while (true) {
68 int compare_i, compare_j;
69
70 while ((compare_i = array.elem_compare(i, pivot)) < 0)
71 ++i;
72 while ((compare_j = array.elem_compare(j, pivot)) > 0)
73 --j;
74
75 // At some point i will crossover j so we will definitely break out of
76 // this while loop.
77 if (i >= j)
78 return j + 1;
79
80 array.swap(i, j);
81
82 // The pivot itself might have got swapped so we will update the pivot.
83 if (i == pivot_index) {
84 pivot = array.get(j);
85 pivot_index = j;
86 } else if (j == pivot_index) {
87 pivot = array.get(i);
88 pivot_index = i;
89 }
90
91 if (compare_i == 0 && compare_j == 0) {
92 // If we do not move the pointers, we will end up with an
93 // infinite loop as i and j will be stuck without advancing.
94 ++i;
95 --j;
96 }
97 }
98 }
99
quicksort(const Array & array)100 static void quicksort(const Array &array) {
101 const size_t array_size = array.size();
102 if (array_size <= 1)
103 return;
104 size_t split_index = partition(array);
105 if (array_size <= 2) {
106 // The partition operation sorts the two element array.
107 return;
108 }
109 quicksort(array.make_array(0, split_index));
110 quicksort(array.make_array(split_index, array.size() - split_index));
111 }
112
113 } // namespace internal
114
115 LLVM_LIBC_FUNCTION(void, qsort,
116 (void *array, size_t array_size, size_t elem_size,
117 int (*compare)(const void *, const void *))) {
118 if (array == nullptr || array_size == 0 || elem_size == 0)
119 return;
120 internal::quicksort(internal::Array(reinterpret_cast<uint8_t *>(array),
121 array_size, elem_size, compare));
122 }
123
124 } // namespace __llvm_libc
125