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:
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 
32   uint8_t *get(size_t i) const { return array + i * elem_size; }
33 
34   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 
44   int elem_compare(size_t i, const uint8_t *other) const {
45     return compare(get(i), other);
46   }
47 
48   size_t size() const { return array_size; }
49 
50   // Make an Array starting at index |i| and size |s|.
51   Array make_array(size_t i, size_t s) const {
52     return Array(get(i), s, elem_size, compare);
53   }
54 };
55 
56 static size_t partition(const Array &array) {
57   const size_t array_size = array.size();
58   size_t pivot_index = array_size / 2;
59   uint8_t *pivot = array.get(pivot_index);
60   size_t i = 0;
61   size_t j = array_size - 1;
62 
63   while (true) {
64     int compare_i, compare_j;
65 
66     while ((compare_i = array.elem_compare(i, pivot)) < 0)
67       ++i;
68     while ((compare_j = array.elem_compare(j, pivot)) > 0)
69       --j;
70 
71     // At some point i will crossover j so we will definitely break out of
72     // this while loop.
73     if (i >= j)
74       return j + 1;
75 
76     array.swap(i, j);
77 
78     // The pivot itself might have got swapped so we will update the pivot.
79     if (i == pivot_index) {
80       pivot = array.get(j);
81       pivot_index = j;
82     } else if (j == pivot_index) {
83       pivot = array.get(i);
84       pivot_index = i;
85     }
86 
87     if (compare_i == 0 && compare_j == 0) {
88       // If we do not move the pointers, we will end up with an
89       // infinite loop as i and j will be stuck without advancing.
90       ++i;
91       --j;
92     }
93   }
94 }
95 
96 static void quicksort(const Array &array) {
97   const size_t array_size = array.size();
98   if (array_size <= 1)
99     return;
100   size_t split_index = partition(array);
101   if (array_size <= 2) {
102     // The partition operation sorts the two element array.
103     return;
104   }
105   quicksort(array.make_array(0, split_index));
106   quicksort(array.make_array(split_index, array.size() - split_index));
107 }
108 
109 } // namespace internal
110 
111 LLVM_LIBC_FUNCTION(void, qsort,
112                    (void *array, size_t array_size, size_t elem_size,
113                     int (*compare)(const void *, const void *))) {
114   if (array == nullptr || array_size == 0 || elem_size == 0)
115     return;
116   internal::quicksort(internal::Array(reinterpret_cast<uint8_t *>(array),
117                                       array_size, elem_size, compare));
118 }
119 
120 } // namespace __llvm_libc
121