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
int_compare_count(const void * l,const void * r,void * count_arg)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
TEST(LlvmLibcQsortRTest,SortedArray)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
66 // comparisons made.
67 ASSERT_GE(count, ARRAY_SIZE);
68 }
69
TEST(LlvmLibcQsortRTest,ReverseSortedArray)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
compare_priority_val(const PriorityVal * l,const PriorityVal * r)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>
type_erased_comp(const void * l,const void * r,void * erased_func_ptr)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
TEST(LlvmLibcQsortRTest,SafeTypeErasure)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