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 // 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 52 size_t size() const { return array_size; } 53 54 // Make an Array starting at index |i| and size |s|. 55 Array make_array(size_t i, size_t s) const { 56 return Array(get(i), s, elem_size, compare); 57 } 58 }; 59 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 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