1 //===-- Data structures for sorting routines --------------------*- 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_DATA_H 10 #define LLVM_LIBC_SRC_STDLIB_QSORT_DATA_H 11 12 #include "src/__support/CPP/cstddef.h" 13 #include "src/__support/macros/config.h" 14 15 #include <stdint.h> 16 17 namespace LIBC_NAMESPACE_DECL { 18 namespace internal { 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 ComparatorComparator34 Comparator(Compare *func) 35 : comp_func(func), comp_type(CompType::COMPARE), arg(nullptr) {} 36 ComparatorComparator37 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 comp_valsComparator50 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: Array(uint8_t * a,size_t s,size_t e,Comparator c)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 get(size_t i)69 uint8_t *get(size_t i) const { return array + i * elem_size; } 70 swap(size_t i,size_t j)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 elem_compare(size_t i,const uint8_t * other)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 size()89 size_t size() const { return array_size; } 90 91 // Make an Array starting at index |i| and size |s|. make_array(size_t i,size_t s)92 LIBC_INLINE Array make_array(size_t i, size_t s) const { 93 return Array(get(i), s, elem_size, compare); 94 } 95 96 // Reset this Array to point at a different interval of the same items. reset_bounds(uint8_t * a,size_t s)97 LIBC_INLINE void reset_bounds(uint8_t *a, size_t s) { 98 array = a; 99 array_size = s; 100 } 101 }; 102 103 using SortingRoutine = void(const Array &); 104 105 } // namespace internal 106 } // namespace LIBC_NAMESPACE_DECL 107 108 #endif // LLVM_LIBC_SRC_STDLIB_QSORT_DATA_H 109