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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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