libc/src/stdlib/quick_sort.h

   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.
  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
  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