1 //===-- Unittests for qsort_r ---------------------------------------------===// 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_r.h" 10 11 #include "test/UnitTest/Test.h" 12 13 #include "hdr/types/size_t.h" 14 15 static int int_compare_count(const void *l, const void *r, void *count_arg) { 16 int li = *reinterpret_cast<const int *>(l); 17 int ri = *reinterpret_cast<const int *>(r); 18 size_t *count = reinterpret_cast<size_t *>(count_arg); 19 *count = *count + 1; 20 if (li == ri) 21 return 0; 22 else if (li > ri) 23 return 1; 24 else 25 return -1; 26 } 27 28 TEST(LlvmLibcQsortRTest, SortedArray) { 29 int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110, 30 123, 133, 135, 155, 170, 171, 1100, 1110, 1123, 31 1133, 1135, 1155, 1170, 1171, 11100, 12310}; 32 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 33 34 size_t count = 0; 35 36 LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count, 37 &count); 38 39 ASSERT_LE(array[0], 10); 40 ASSERT_LE(array[1], 23); 41 ASSERT_LE(array[2], 33); 42 ASSERT_LE(array[3], 35); 43 ASSERT_LE(array[4], 55); 44 ASSERT_LE(array[5], 70); 45 ASSERT_LE(array[6], 71); 46 ASSERT_LE(array[7], 100); 47 ASSERT_LE(array[8], 110); 48 ASSERT_LE(array[9], 123); 49 ASSERT_LE(array[10], 133); 50 ASSERT_LE(array[11], 135); 51 ASSERT_LE(array[12], 155); 52 ASSERT_LE(array[13], 170); 53 ASSERT_LE(array[14], 171); 54 ASSERT_LE(array[15], 1100); 55 ASSERT_LE(array[16], 1110); 56 ASSERT_LE(array[17], 1123); 57 ASSERT_LE(array[18], 1133); 58 ASSERT_LE(array[19], 1135); 59 ASSERT_LE(array[20], 1155); 60 ASSERT_LE(array[21], 1170); 61 ASSERT_LE(array[22], 1171); 62 ASSERT_LE(array[23], 11100); 63 ASSERT_LE(array[24], 12310); 64 65 // This is a sorted list, but there still have to have been at least N - 1 66 // comparisons made. 67 ASSERT_GE(count, ARRAY_SIZE - 1); 68 } 69 70 TEST(LlvmLibcQsortRTest, ReverseSortedArray) { 71 int array[25] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 72 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 73 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int); 74 75 size_t count = 0; 76 77 LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count, 78 &count); 79 80 for (int i = 0; i < int(ARRAY_SIZE - 1); ++i) 81 ASSERT_LE(array[i], i + 1); 82 83 ASSERT_GE(count, ARRAY_SIZE); 84 } 85 86 // The following test is intended to mimic the CPP library pattern of having a 87 // comparison function that takes a specific type, which is passed to a library 88 // that then needs to sort an array of that type. The library can't safely pass 89 // the comparison function to qsort because a function that takes const T* 90 // being cast to a function that takes const void* is undefined behavior. The 91 // safer pattern is to pass a type erased comparator that calls into the typed 92 // comparator to qsort_r. 93 94 struct PriorityVal { 95 int priority; 96 int size; 97 }; 98 99 static int compare_priority_val(const PriorityVal *l, const PriorityVal *r) { 100 // Subtracting the priorities is unsafe, but it's fine for this test. 101 int priority_diff = l->priority - r->priority; 102 if (priority_diff != 0) { 103 return priority_diff; 104 } 105 if (l->size == r->size) { 106 return 0; 107 } else if (l->size > r->size) { 108 return 1; 109 } else { 110 return -1; 111 } 112 } 113 114 template <typename T> 115 static int type_erased_comp(const void *l, const void *r, 116 void *erased_func_ptr) { 117 typedef int (*TypedComp)(const T *, const T *); 118 TypedComp typed_func_ptr = reinterpret_cast<TypedComp>(erased_func_ptr); 119 const T *lt = reinterpret_cast<const T *>(l); 120 const T *rt = reinterpret_cast<const T *>(r); 121 return typed_func_ptr(lt, rt); 122 } 123 124 TEST(LlvmLibcQsortRTest, SafeTypeErasure) { 125 PriorityVal array[5] = { 126 {10, 3}, {1, 10}, {-1, 100}, {10, 0}, {3, 3}, 127 }; 128 constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(PriorityVal); 129 130 LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(PriorityVal), 131 type_erased_comp<PriorityVal>, 132 reinterpret_cast<void *>(compare_priority_val)); 133 134 EXPECT_EQ(array[0].priority, -1); 135 EXPECT_EQ(array[0].size, 100); 136 EXPECT_EQ(array[1].priority, 1); 137 EXPECT_EQ(array[1].size, 10); 138 EXPECT_EQ(array[2].priority, 3); 139 EXPECT_EQ(array[2].size, 3); 140 EXPECT_EQ(array[3].priority, 10); 141 EXPECT_EQ(array[3].size, 0); 142 EXPECT_EQ(array[4].priority, 10); 143 EXPECT_EQ(array[4].size, 3); 144 } 145