1 //===-- Unittests for qsort -----------------------------------------------===//
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.h"
10
11 #include "utils/UnitTest/Test.h"
12
13 #include <stdlib.h>
14
int_compare(const void * l,const void * r)15 static int int_compare(const void *l, const void *r) {
16 int li = *reinterpret_cast<const int *>(l);
17 int ri = *reinterpret_cast<const int *>(r);
18 if (li == ri)
19 return 0;
20 else if (li > ri)
21 return 1;
22 else
23 return -1;
24 }
25
TEST(LlvmLibcQsortTest,SortedArray)26 TEST(LlvmLibcQsortTest, SortedArray) {
27 int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110,
28 123, 133, 135, 155, 170, 171, 1100, 1110, 1123,
29 1133, 1135, 1155, 1170, 1171, 11100, 12310};
30 constexpr size_t array_size = sizeof(array) / sizeof(int);
31
32 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
33
34 ASSERT_LE(array[0], 10);
35 ASSERT_LE(array[1], 23);
36 ASSERT_LE(array[2], 33);
37 ASSERT_LE(array[3], 35);
38 ASSERT_LE(array[4], 55);
39 ASSERT_LE(array[5], 70);
40 ASSERT_LE(array[6], 71);
41 ASSERT_LE(array[7], 100);
42 ASSERT_LE(array[8], 110);
43 ASSERT_LE(array[9], 123);
44 ASSERT_LE(array[10], 133);
45 ASSERT_LE(array[11], 135);
46 ASSERT_LE(array[12], 155);
47 ASSERT_LE(array[13], 170);
48 ASSERT_LE(array[14], 171);
49 ASSERT_LE(array[15], 1100);
50 ASSERT_LE(array[16], 1110);
51 ASSERT_LE(array[17], 1123);
52 ASSERT_LE(array[18], 1133);
53 ASSERT_LE(array[19], 1135);
54 ASSERT_LE(array[20], 1155);
55 ASSERT_LE(array[21], 1170);
56 ASSERT_LE(array[22], 1171);
57 ASSERT_LE(array[23], 11100);
58 ASSERT_LE(array[24], 12310);
59 }
60
TEST(LlvmLibcQsortTest,ReverseSortedArray)61 TEST(LlvmLibcQsortTest, ReverseSortedArray) {
62 int array[25] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
63 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
64 constexpr size_t array_size = sizeof(array) / sizeof(int);
65
66 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
67
68 for (int i = 0; i < int(array_size - 1); ++i)
69 ASSERT_LE(array[i], i + 1);
70 }
71
TEST(LlvmLibcQsortTest,AllEqualElements)72 TEST(LlvmLibcQsortTest, AllEqualElements) {
73 int array[25] = {100, 100, 100, 100, 100, 100, 100, 100, 100,
74 100, 100, 100, 100, 100, 100, 100, 100, 100,
75 100, 100, 100, 100, 100, 100, 100};
76 constexpr size_t array_size = sizeof(array) / sizeof(int);
77
78 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
79
80 for (size_t i = 0; i < array_size - 1; ++i)
81 ASSERT_LE(array[i], 100);
82 }
83
TEST(LlvmLibcQsortTest,UnsortedArray1)84 TEST(LlvmLibcQsortTest, UnsortedArray1) {
85 int array[25] = {10, 23, 8, 35, 55, 45, 40, 100, 110, 123, 90, 80, 70,
86 60, 171, 11, 1, -1, -5, -10, 1155, 1170, 1171, 12, -100};
87 constexpr size_t array_size = sizeof(array) / sizeof(int);
88
89 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
90
91 ASSERT_LE(array[0], -100);
92 ASSERT_LE(array[1], -10);
93 ASSERT_LE(array[2], -5);
94 ASSERT_LE(array[3], -1);
95 ASSERT_LE(array[4], 1);
96 ASSERT_LE(array[5], 8);
97 ASSERT_LE(array[6], 10);
98 ASSERT_LE(array[7], 11);
99 ASSERT_LE(array[8], 12);
100 ASSERT_LE(array[9], 23);
101 ASSERT_LE(array[10], 35);
102 ASSERT_LE(array[11], 40);
103 ASSERT_LE(array[12], 45);
104 ASSERT_LE(array[13], 55);
105 ASSERT_LE(array[14], 60);
106 ASSERT_LE(array[15], 70);
107 ASSERT_LE(array[16], 80);
108 ASSERT_LE(array[17], 90);
109 ASSERT_LE(array[18], 100);
110 ASSERT_LE(array[19], 110);
111 ASSERT_LE(array[20], 123);
112 ASSERT_LE(array[21], 171);
113 ASSERT_LE(array[22], 1155);
114 ASSERT_LE(array[23], 1170);
115 ASSERT_LE(array[24], 1171);
116 }
117
TEST(LlvmLibcQsortTest,UnsortedArray2)118 TEST(LlvmLibcQsortTest, UnsortedArray2) {
119 int array[7] = {10, 40, 45, 55, 35, 23, 60};
120 constexpr size_t array_size = sizeof(array) / sizeof(int);
121
122 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
123
124 ASSERT_LE(array[0], 10);
125 ASSERT_LE(array[1], 23);
126 ASSERT_LE(array[2], 35);
127 ASSERT_LE(array[3], 40);
128 ASSERT_LE(array[4], 45);
129 ASSERT_LE(array[5], 55);
130 ASSERT_LE(array[6], 60);
131 }
132
TEST(LlvmLibcQsortTest,UnsortedArrayDuplicateElements1)133 TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements1) {
134 int array[6] = {10, 10, 20, 20, 5, 5};
135 constexpr size_t array_size = sizeof(array) / sizeof(int);
136
137 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
138
139 ASSERT_LE(array[0], 5);
140 ASSERT_LE(array[1], 5);
141 ASSERT_LE(array[2], 10);
142 ASSERT_LE(array[3], 10);
143 ASSERT_LE(array[4], 20);
144 ASSERT_LE(array[5], 20);
145 }
146
TEST(LlvmLibcQsortTest,UnsortedArrayDuplicateElements2)147 TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements2) {
148 int array[10] = {20, 10, 10, 10, 10, 20, 21, 21, 21, 21};
149 constexpr size_t array_size = sizeof(array) / sizeof(int);
150
151 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
152
153 ASSERT_LE(array[0], 10);
154 ASSERT_LE(array[1], 10);
155 ASSERT_LE(array[2], 10);
156 ASSERT_LE(array[3], 10);
157 ASSERT_LE(array[4], 20);
158 ASSERT_LE(array[5], 20);
159 ASSERT_LE(array[6], 21);
160 ASSERT_LE(array[7], 21);
161 ASSERT_LE(array[8], 21);
162 ASSERT_LE(array[9], 21);
163 }
164
TEST(LlvmLibcQsortTest,UnsortedArrayDuplicateElements3)165 TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements3) {
166 int array[10] = {20, 30, 30, 30, 30, 20, 21, 21, 21, 21};
167 constexpr size_t array_size = sizeof(array) / sizeof(int);
168
169 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
170
171 ASSERT_LE(array[0], 20);
172 ASSERT_LE(array[1], 20);
173 ASSERT_LE(array[2], 21);
174 ASSERT_LE(array[3], 21);
175 ASSERT_LE(array[4], 21);
176 ASSERT_LE(array[5], 21);
177 ASSERT_LE(array[6], 30);
178 ASSERT_LE(array[7], 30);
179 ASSERT_LE(array[8], 30);
180 ASSERT_LE(array[9], 30);
181 }
182
TEST(LlvmLibcQsortTest,UnsortedThreeElementArray1)183 TEST(LlvmLibcQsortTest, UnsortedThreeElementArray1) {
184 int array[3] = {14999024, 0, 3};
185 constexpr size_t array_size = sizeof(array) / sizeof(int);
186
187 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
188
189 ASSERT_LE(array[0], 0);
190 ASSERT_LE(array[1], 3);
191 ASSERT_LE(array[2], 14999024);
192 }
193
TEST(LlvmLibcQsortTest,UnsortedThreeElementArray2)194 TEST(LlvmLibcQsortTest, UnsortedThreeElementArray2) {
195 int array[3] = {3, 14999024, 0};
196 constexpr size_t array_size = sizeof(array) / sizeof(int);
197
198 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
199
200 ASSERT_LE(array[0], 0);
201 ASSERT_LE(array[1], 3);
202 ASSERT_LE(array[2], 14999024);
203 }
204
TEST(LlvmLibcQsortTest,UnsortedThreeElementArray3)205 TEST(LlvmLibcQsortTest, UnsortedThreeElementArray3) {
206 int array[3] = {3, 0, 14999024};
207 constexpr size_t array_size = sizeof(array) / sizeof(int);
208
209 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
210
211 ASSERT_LE(array[0], 0);
212 ASSERT_LE(array[1], 3);
213 ASSERT_LE(array[2], 14999024);
214 }
215
TEST(LlvmLibcQsortTest,SameElementThreeElementArray)216 TEST(LlvmLibcQsortTest, SameElementThreeElementArray) {
217 int array[3] = {12345, 12345, 12345};
218 constexpr size_t array_size = sizeof(array) / sizeof(int);
219
220 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
221
222 ASSERT_LE(array[0], 12345);
223 ASSERT_LE(array[1], 12345);
224 ASSERT_LE(array[2], 12345);
225 }
226
TEST(LlvmLibcQsortTest,UnsortedTwoElementArray1)227 TEST(LlvmLibcQsortTest, UnsortedTwoElementArray1) {
228 int array[2] = {14999024, 0};
229 constexpr size_t array_size = sizeof(array) / sizeof(int);
230
231 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
232
233 ASSERT_LE(array[0], 0);
234 ASSERT_LE(array[1], 14999024);
235 }
236
TEST(LlvmLibcQsortTest,UnsortedTwoElementArray2)237 TEST(LlvmLibcQsortTest, UnsortedTwoElementArray2) {
238 int array[2] = {0, 14999024};
239 constexpr size_t array_size = sizeof(array) / sizeof(int);
240
241 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
242
243 ASSERT_LE(array[0], 0);
244 ASSERT_LE(array[1], 14999024);
245 }
246
TEST(LlvmLibcQsortTest,SameElementTwoElementArray)247 TEST(LlvmLibcQsortTest, SameElementTwoElementArray) {
248 int array[2] = {12345, 12345};
249 constexpr size_t array_size = sizeof(array) / sizeof(int);
250
251 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
252
253 ASSERT_LE(array[0], 12345);
254 ASSERT_LE(array[1], 12345);
255 }
256
TEST(LlvmLibcQSortTest,SingleElementArray)257 TEST(LlvmLibcQSortTest, SingleElementArray) {
258 constexpr int elem = 12345;
259 int array[1] = {elem};
260 constexpr size_t array_size = sizeof(array) / sizeof(int);
261
262 __llvm_libc::qsort(array, array_size, sizeof(int), int_compare);
263
264 ASSERT_LE(array[0], elem);
265 }
266