Line data Source code
1 : /*
2 : * Unix SMB/CIFS implementation.
3 : *
4 : * Copyright (C) 2018 Andreas Schneider <asn@samba.org>
5 : * Copyright (C) 2022 Douglas Bagnall <dbagnall@samba.org>
6 : *
7 : * This program is free software; you can redistribute it and/or modify
8 : * it under the terms of the GNU General Public License as published by
9 : * the Free Software Foundation; either version 3 of the License, or
10 : * (at your option) any later version.
11 : *
12 : * This program is distributed in the hope that it will be useful,
13 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : * GNU General Public License for more details.
16 : *
17 : * You should have received a copy of the GNU General Public License
18 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
19 : */
20 :
21 : #include <stdarg.h>
22 : #include <stddef.h>
23 : #include <setjmp.h>
24 : #include <cmocka.h>
25 : #include <stdbool.h>
26 : #include "replace.h"
27 : #include <talloc.h>
28 :
29 : #include "../stable_sort.h"
30 :
31 :
32 9666 : static int cmp_integer(int *a, int *b)
33 : {
34 9666 : if (a == NULL || b == NULL) {
35 : return 0;
36 : }
37 :
38 9666 : if (*a > *b) {
39 : return 1;
40 : }
41 :
42 3762 : if (*a < *b) {
43 3762 : return -1;
44 : }
45 :
46 : return 0;
47 : }
48 :
49 1 : static void test_stable_sort(void **state)
50 : {
51 1 : int a[6] = { 6, 3, 2, 7, 9, 4 };
52 1 : int tmp[6];
53 1 : bool ok;
54 1 : ok = stable_sort(a, tmp,
55 : 6, sizeof(int), (samba_compare_fn_t)cmp_integer);
56 :
57 1 : assert_true(ok);
58 1 : assert_int_equal(a[0], 2);
59 1 : assert_int_equal(a[1], 3);
60 1 : assert_int_equal(a[2], 4);
61 1 : assert_int_equal(a[3], 6);
62 1 : assert_int_equal(a[4], 7);
63 1 : assert_int_equal(a[5], 9);
64 1 : }
65 :
66 1 : static void test_stable_sort_talloc_short(void **state)
67 : {
68 1 : int a[6] = { 6, 3, 2, 7, 9, 4 };
69 1 : int ret;
70 1 : ret = stable_sort_talloc(NULL, a, 6, sizeof(int),
71 : (samba_compare_fn_t)cmp_integer);
72 1 : assert_true(ret);
73 :
74 1 : assert_int_equal(a[0], 2);
75 1 : assert_int_equal(a[1], 3);
76 1 : assert_int_equal(a[2], 4);
77 1 : assert_int_equal(a[3], 6);
78 1 : assert_int_equal(a[4], 7);
79 1 : assert_int_equal(a[5], 9);
80 1 : }
81 :
82 1 : static void test_stable_sort_talloc_long(void **state)
83 : {
84 1 : int i, ret;
85 1 : size_t n = 1500;
86 1 : TALLOC_CTX *mem_ctx = talloc_new(NULL);
87 1 : int *a = talloc_array(mem_ctx, int, n);
88 1502 : for (i = 0; i < n; i++) {
89 1500 : a[i] = n - i;
90 : }
91 :
92 1 : ret = stable_sort_talloc(mem_ctx, a, n, sizeof(int),
93 : (samba_compare_fn_t)cmp_integer);
94 1 : assert_true(ret);
95 :
96 1502 : for (i = 0; i < n; i++) {
97 1500 : assert_int_equal(a[i], 1 + i);
98 : }
99 1 : }
100 :
101 :
102 : /*
103 : * Sort an array of structs with:
104 : * - unwieldy uneven size
105 : * - sort key not at the start
106 : * - comparison depends on context
107 : *
108 : * which are things we sometimes do.
109 : */
110 :
111 : struct contrived_struct {
112 : char padding_1[13];
113 : int key[3];
114 : char padding_2[18];
115 : size_t *index;
116 : };
117 :
118 :
119 42903256 : static int cmp_contrived_struct(struct contrived_struct *as,
120 : struct contrived_struct *bs)
121 : {
122 42903256 : int i = *as->index;
123 42903256 : int a = as->key[i];
124 42903256 : int b = bs->key[i];
125 42903256 : return a - b;
126 : }
127 :
128 14959079 : static int cmp_contrived_struct_rev(struct contrived_struct *as,
129 : struct contrived_struct *bs)
130 : {
131 : /* will sort in reverseo order */
132 14959079 : int i = *as->index;
133 14959079 : int a = as->key[i];
134 14959079 : int b = bs->key[i];
135 14959079 : return b - a;
136 : }
137 :
138 :
139 1 : static void test_stable_sort_talloc_contrived_struct(void **state)
140 : {
141 1 : int i, ret, prev;
142 1 : size_t n = 800000;
143 1 : TALLOC_CTX *mem_ctx = talloc_new(NULL);
144 1 : size_t key_index = 0;
145 :
146 1 : struct contrived_struct *a = talloc_zero_array(mem_ctx,
147 : struct contrived_struct,
148 : n);
149 :
150 : /* we don't really want a good RNG, we want mess and repeated values. */
151 1 : uint32_t x = 89, y = (uint32_t)-6, z = 11;
152 800002 : for (i = 0; i < n; i++) {
153 800000 : a[i].index = &key_index;
154 800000 : a[i].key[0] = (x & 0xffff) - 0x8000;
155 800000 : a[i].key[1] = z & 255;
156 : /* key[2] is original order, useful for checking stability */
157 800000 : a[i].key[2] = i;
158 800000 : x += z ^ y;
159 800000 : y *= z + (x + 0x5555);
160 800000 : z -= x ^ i;
161 : }
162 :
163 : /* 1. sort by key[0] */
164 1 : ret = stable_sort_talloc(mem_ctx, a, n,
165 : sizeof(struct contrived_struct),
166 : (samba_compare_fn_t)cmp_contrived_struct);
167 1 : assert_true(ret);
168 1 : prev = a[0].key[0];
169 800000 : for (i = 1; i < n; i++) {
170 799999 : int value = a[i].key[0];
171 799999 : assert_true(value >= prev);
172 799999 : if (value == prev) {
173 : /* we can test the stability by comparing key[2] */
174 769043 : assert_true(a[i].key[2] >= a[i - 1].key[2]);
175 : }
176 799999 : prev = value;
177 : }
178 :
179 : /* 2. sort by key[1]. key[0] now indicates stability. */
180 1 : key_index = 1;
181 1 : ret = stable_sort_talloc(mem_ctx, a, n,
182 : sizeof(struct contrived_struct),
183 : (samba_compare_fn_t)cmp_contrived_struct);
184 1 : assert_true(ret);
185 1 : prev = a[0].key[1];
186 800000 : for (i = 1; i < n; i++) {
187 799999 : int value = a[i].key[1];
188 799999 : assert_true(value >= prev);
189 799999 : if (value == prev) {
190 799887 : assert_true(a[i].key[0] >= a[i - 1].key[0]);
191 : }
192 799999 : prev = value;
193 : }
194 :
195 : /*
196 : * 3. sort by key[2]. key[1] would now indicate stability, but we know
197 : * that key[2] has no duplicates, so stability is moot.
198 : */
199 1 : key_index = 2;
200 1 : ret = stable_sort_talloc(mem_ctx, a, n,
201 : sizeof(struct contrived_struct),
202 : (samba_compare_fn_t)cmp_contrived_struct);
203 1 : assert_true(ret);
204 1 : prev = a[0].key[2];
205 800000 : for (i = 1; i < n; i++) {
206 799999 : int value = a[i].key[2];
207 799999 : assert_true(value > prev);
208 799999 : prev = value;
209 : }
210 :
211 : /*
212 : * 4. sort by key[0] again, using descending sort order. key[2] should
213 : * still be in ascending order where there are duplicate key[0] values.
214 : */
215 1 : key_index = 0;
216 1 : ret = stable_sort_talloc(mem_ctx, a, n,
217 : sizeof(struct contrived_struct),
218 : (samba_compare_fn_t)cmp_contrived_struct_rev);
219 1 : assert_true(ret);
220 1 : prev = a[0].key[0];
221 800000 : for (i = 1; i < n; i++) {
222 799999 : int value = a[i].key[0];
223 799999 : assert_true(value <= prev);
224 799999 : if (value == prev) {
225 769043 : assert_true(a[i].key[2] >= a[i - 1].key[2]);
226 : }
227 799999 : prev = value;
228 : }
229 1 : }
230 :
231 :
232 :
233 13624 : static int cmp_integer_xor_blob(int *_a, int *_b, int *opaque)
234 : {
235 13624 : int a = *_a ^ *opaque;
236 13624 : int b = *_b ^ *opaque;
237 :
238 13624 : if (a > b) {
239 : return 1;
240 : }
241 :
242 7489 : if (a < b) {
243 5477 : return -1;
244 : }
245 :
246 : return 0;
247 : }
248 :
249 1 : static void test_stable_sort_talloc_r(void **state)
250 : {
251 1 : int i;
252 1 : size_t n = 1500;
253 1 : TALLOC_CTX *mem_ctx = talloc_new(NULL);
254 1 : int opaque = 42;
255 1 : bool ok;
256 1 : int *a = talloc_array(mem_ctx, int, n);
257 1502 : for (i = 0; i < n; i++) {
258 1500 : a[i] = (i * 7) & 255;
259 : }
260 :
261 1 : ok = stable_sort_talloc_r(mem_ctx, a, n, sizeof(int),
262 : (samba_compare_with_context_fn_t)cmp_integer_xor_blob,
263 : &opaque);
264 1 : assert_true(ok);
265 :
266 1501 : for (i = 1; i < n; i++) {
267 1499 : assert_true((a[i - 1] ^ opaque) <= (a[i] ^ opaque));
268 : }
269 1 : }
270 :
271 :
272 1 : static void test_stable_sort_silly_size(void **state)
273 : {
274 1 : bool ok;
275 1 : int a[33] = {0};
276 1 : int b[33] = {0};
277 :
278 1 : ok = stable_sort(a,
279 : b,
280 : (SIZE_MAX / 2) + 2,
281 : (SIZE_MAX / 2) + 2,
282 : (samba_compare_fn_t)cmp_integer);
283 1 : assert_false(ok);
284 1 : }
285 :
286 1 : static void test_stable_sort_null_array(void **state)
287 : {
288 1 : bool ok;
289 1 : int a[33] = {0};
290 :
291 1 : ok = stable_sort(a,
292 : NULL,
293 : 33,
294 : sizeof(int),
295 : (samba_compare_fn_t)cmp_integer);
296 1 : assert_false(ok);
297 1 : }
298 :
299 :
300 :
301 :
302 :
303 1 : int main(void) {
304 1 : const struct CMUnitTest tests[] = {
305 : cmocka_unit_test(test_stable_sort),
306 : cmocka_unit_test(test_stable_sort_talloc_short),
307 : cmocka_unit_test(test_stable_sort_talloc_long),
308 : cmocka_unit_test(test_stable_sort_talloc_contrived_struct),
309 : cmocka_unit_test(test_stable_sort_talloc_r),
310 : cmocka_unit_test(test_stable_sort_silly_size),
311 : cmocka_unit_test(test_stable_sort_null_array),
312 : };
313 1 : if (!isatty(1)) {
314 1 : cmocka_set_message_output(CM_OUTPUT_SUBUNIT);
315 : }
316 1 : return cmocka_run_group_tests(tests, NULL, NULL);
317 : }
|
