libc/src/stdlib/qsort_util.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_QSORT_UTIL_H
  10 #define LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H
  11
  12 #include "src/__support/macros/attributes.h"
  13 #include <stdint.h>
  14 #include <stdlib.h>
  15
  16 namespace LIBC_NAMESPACE::internal {
  17
  18 // A simple quicksort implementation using the Hoare partition scheme.
  19
  20 using Compare = int(const void *, const void *);
  21 using CompareWithState = int(const void *, const void *, void *);
  22
  23 enum class CompType { COMPARE, COMPARE_WITH_STATE };
  24
  25 struct Comparator {
  26   union {
  27     Compare *comp_func;
  28     CompareWithState *comp_func_r;
  29   };
  30   const CompType comp_type;
  31
  32   void *arg;
  33
  34   Comparator(Compare *func)
  35       : comp_func(func), comp_type(CompType::COMPARE), arg(nullptr) {}
  36
  37   Comparator(CompareWithState *func, void *arg_val)
  38       : comp_func_r(func), comp_type(CompType::COMPARE_WITH_STATE),
  39         arg(arg_val) {}
  40
  41 #if defined(__clang__)
  42   // Recent upstream changes to -fsanitize=function find more instances of
  43   // function type mismatches. One case is with the comparator passed to this
  44   // class. Libraries will tend to pass comparators that take pointers to
  45   // varying types while this comparator expects to accept const void pointers.
  46   // Ideally those tools would pass a function that strictly accepts const
  47   // void*s to avoid UB, or would use qsort_r to pass their own comparator.
  48   [[clang::no_sanitize("function")]]
  49 #endif
  50   int comp_vals(const void *a, const void *b) const {
  51     if (comp_type == CompType::COMPARE) {
  52       return comp_func(a, b);
  53     } else {
  54       return comp_func_r(a, b, arg);
  55     }
  56   }
  57 };
  58
  59 class Array {
  60   uint8_t *array;
  61   size_t array_size;
  62   size_t elem_size;
  63   Comparator compare;
  64
  65 public:
  66   Array(uint8_t *a, size_t s, size_t e, Comparator c)
  67       : array(a), array_size(s), elem_size(e), compare(c) {}
  68
  69   uint8_t *get(size_t i) const { return array + i * elem_size; }
  70
  71   void swap(size_t i, size_t j) const {
  72     uint8_t *elem_i = get(i);
  73     uint8_t *elem_j = get(j);
  74     for (size_t b = 0; b < elem_size; ++b) {
  75       uint8_t temp = elem_i[b];
  76       elem_i[b] = elem_j[b];
  77       elem_j[b] = temp;
  78     }
  79   }
  80
  81   int elem_compare(size_t i, const uint8_t *other) const {
  82     // An element must compare equal to itself so we don't need to consult the
  83     // user provided comparator.
  84     if (get(i) == other)
  85       return 0;
  86     return compare.comp_vals(get(i), other);
  87   }
  88
  89   size_t size() const { return array_size; }
  90
  91   // Make an Array starting at index |i| and size |s|.
  92   Array make_array(size_t i, size_t s) const {
  93     return Array(get(i), s, elem_size, compare);
  94   }
  95 };
  96
  97 static size_t partition(const Array &array) {
  98   const size_t array_size = array.size();
  99   size_t pivot_index = array_size / 2;
 100   uint8_t *pivot = array.get(pivot_index);
 101   size_t i = 0;
 102   size_t j = array_size - 1;
 103
 104   while (true) {
 105     int compare_i, compare_j;
 106
 107     while ((compare_i = array.elem_compare(i, pivot)) < 0)
 108       ++i;
 109     while ((compare_j = array.elem_compare(j, pivot)) > 0)
 110       --j;
 111
 112     // At some point i will crossover j so we will definitely break out of
 113     // this while loop.
 114     if (i >= j)
 115       return j + 1;
 116
 117     array.swap(i, j);
 118
 119     // The pivot itself might have got swapped so we will update the pivot.
 120     if (i == pivot_index) {
 121       pivot = array.get(j);
 122       pivot_index = j;
 123     } else if (j == pivot_index) {
 124       pivot = array.get(i);
 125       pivot_index = i;
 126     }
 127
 128     if (compare_i == 0 && compare_j == 0) {
 129       // If we do not move the pointers, we will end up with an
 130       // infinite loop as i and j will be stuck without advancing.
 131       ++i;
 132       --j;
 133     }
 134   }
 135 }
 136
 137 LIBC_INLINE void quicksort(const Array &array) {
 138   const size_t array_size = array.size();
 139   if (array_size <= 1)
 140     return;
 141   size_t split_index = partition(array);
 142   if (array_size <= 2) {
 143     // The partition operation sorts the two element array.
 144     return;
 145   }
 146   quicksort(array.make_array(0, split_index));
 147   quicksort(array.make_array(split_index, array.size() - split_index));
 148 }
 149
 150 } // namespace LIBC_NAMESPACE::internal
 151
 152 #endif // LLVM_LIBC_SRC_STDLIB_QSORT_UTIL_H