1 | /* GtkRBTree tests. |
2 | * |
3 | * Copyright (C) 2011, Red Hat, Inc. |
4 | * Authors: Benjamin Otte <otte@gnome.org> |
5 | * |
6 | * This library is free software; you can redistribute it and/or |
7 | * modify it under the terms of the GNU Lesser General Public |
8 | * License as published by the Free Software Foundation; either |
9 | * version 2 of the License, or (at your option) any later version. |
10 | * |
11 | * This library is distributed in the hope that it will be useful, |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | * Lesser General Public License for more details. |
15 | * |
16 | * You should have received a copy of the GNU Lesser General Public |
17 | * License along with this library. If not, see <http://www.gnu.org/licenses/>. |
18 | */ |
19 | |
20 | #include <locale.h> |
21 | |
22 | #include "../../gtk/gtkbitmaskprivate.h" |
23 | |
24 | #include <string.h> |
25 | |
26 | /* how often we run the random tests */ |
27 | #define N_RUNS 20 |
28 | |
29 | /* how many tries we do in our random tests */ |
30 | #define N_TRIES 100 |
31 | |
32 | /* the maximum index we use for bitmask values */ |
33 | #define MAX_INDEX 1000 |
34 | |
35 | /* UTILITIES */ |
36 | |
37 | static GtkBitmask * |
38 | gtk_bitmask_new_parse (const char *string) |
39 | { |
40 | guint i, length; |
41 | GtkBitmask *mask; |
42 | |
43 | length = strlen (s: string); |
44 | mask = _gtk_bitmask_new (); |
45 | |
46 | for (i = 0; i < length; i++) |
47 | { |
48 | if (string[i] == '0') |
49 | mask = _gtk_bitmask_set (mask, index_: length - i - 1, FALSE); |
50 | else if (string[i] == '1') |
51 | mask = _gtk_bitmask_set (mask, index_: length - i - 1, TRUE); |
52 | else |
53 | g_assert_not_reached (); |
54 | } |
55 | |
56 | return mask; |
57 | } |
58 | |
59 | #define assert_cmpmasks(mask,other) G_STMT_START { \ |
60 | if (G_UNLIKELY (!_gtk_bitmask_equals (mask, other))) \ |
61 | { \ |
62 | char *mask_string = _gtk_bitmask_to_string (mask); \ |
63 | char *other_string = _gtk_bitmask_to_string (other); \ |
64 | char *msg = g_strdup_printf ("%s (%s) != %s (%s)", \ |
65 | G_STRINGIFY (mask), mask_string, \ |
66 | G_STRINGIFY (other), other_string); \ |
67 | g_assertion_message (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, msg); \ |
68 | g_free (msg); \ |
69 | g_free (mask_string); \ |
70 | g_free (other_string); \ |
71 | } \ |
72 | }G_STMT_END |
73 | |
74 | static const char *tests[] = { |
75 | "0" , |
76 | "1" , |
77 | "1000000000000000000000000000000" , |
78 | "10000000000000000000000000000000" , |
79 | "100000000000000000000000000000000000000000000000000000000000000" , |
80 | "1000000000000000000000000000000000000000000000000000000000000000" , |
81 | "10000000000000000000000000000000000000000000000000000000000000000" , |
82 | "1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010" , |
83 | "1000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000" , |
84 | "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" |
85 | }; |
86 | |
87 | static GtkBitmask *masks[G_N_ELEMENTS (tests)]; |
88 | |
89 | /* TEST */ |
90 | |
91 | static void |
92 | test_to_string (void) |
93 | { |
94 | guint i; |
95 | char *to_string; |
96 | |
97 | for (i = 0; i < G_N_ELEMENTS (tests); i++) |
98 | { |
99 | to_string = _gtk_bitmask_to_string (mask: masks[i]); |
100 | g_assert_cmpstr (to_string, ==, tests[i]); |
101 | g_free (mem: to_string); |
102 | } |
103 | } |
104 | |
105 | static void |
106 | test_is_empty (void) |
107 | { |
108 | guint i; |
109 | |
110 | for (i = 0; i < G_N_ELEMENTS (tests); i++) |
111 | { |
112 | g_assert_cmpint (_gtk_bitmask_is_empty (masks[i]), ==, i == 0); |
113 | } |
114 | } |
115 | |
116 | static void |
117 | test_equals (void) |
118 | { |
119 | guint i, j; |
120 | |
121 | for (i = 0; i < G_N_ELEMENTS (tests); i++) |
122 | { |
123 | for (j = 0; j < G_N_ELEMENTS (tests); j++) |
124 | { |
125 | g_assert_cmpint (_gtk_bitmask_equals (masks[i], masks[j]), ==, i == j); |
126 | } |
127 | } |
128 | } |
129 | |
130 | static void |
131 | test_set (void) |
132 | { |
133 | guint i, j; |
134 | guint indexes[N_TRIES]; |
135 | GtkBitmask *copy; |
136 | const GtkBitmask *mask; |
137 | |
138 | for (i = 0; i < N_RUNS; i++) |
139 | { |
140 | mask = masks[g_test_rand_int_range (begin: 0, G_N_ELEMENTS (tests))]; |
141 | copy = _gtk_bitmask_copy (mask); |
142 | |
143 | for (j = 0; j < N_TRIES; j++) |
144 | { |
145 | indexes[j] = g_test_rand_int_range (begin: 0, MAX_INDEX); |
146 | copy = _gtk_bitmask_set (mask: copy, index_: indexes[j], g_test_rand_bit ()); |
147 | } |
148 | |
149 | for (j = 0; j < N_TRIES; j++) |
150 | { |
151 | copy = _gtk_bitmask_set (mask: copy, index_: indexes[j], value: _gtk_bitmask_get (mask, index_: indexes[j])); |
152 | } |
153 | |
154 | assert_cmpmasks (copy, mask); |
155 | _gtk_bitmask_free (mask: copy); |
156 | } |
157 | } |
158 | |
159 | static void |
160 | test_union (void) |
161 | { |
162 | GtkBitmask *left, *right, *expected; |
163 | guint run, try, n_tries; |
164 | |
165 | for (run = 0; run < N_RUNS; run++) |
166 | { |
167 | left = _gtk_bitmask_new (); |
168 | right = _gtk_bitmask_new (); |
169 | expected = _gtk_bitmask_new (); |
170 | |
171 | n_tries = g_test_perf () ? N_TRIES : g_test_rand_int_range (begin: 0, N_TRIES); |
172 | for (try = 0; try < n_tries; try++) |
173 | { |
174 | guint id = g_test_rand_int_range (begin: 0, MAX_INDEX); |
175 | |
176 | if (g_test_rand_bit ()) |
177 | left = _gtk_bitmask_set (mask: left, index_: id, TRUE); |
178 | else |
179 | right = _gtk_bitmask_set (mask: right, index_: id, TRUE); |
180 | |
181 | expected = _gtk_bitmask_set (mask: expected, index_: id, TRUE); |
182 | } |
183 | |
184 | left = _gtk_bitmask_union (mask: left, other: right); |
185 | right = _gtk_bitmask_union (mask: right, other: left); |
186 | |
187 | assert_cmpmasks (left, expected); |
188 | assert_cmpmasks (right, expected); |
189 | _gtk_bitmask_free (mask: left); |
190 | _gtk_bitmask_free (mask: right); |
191 | _gtk_bitmask_free (mask: expected); |
192 | } |
193 | } |
194 | |
195 | static void |
196 | test_intersect (void) |
197 | { |
198 | GtkBitmask *left, *right, *expected; |
199 | guint run, try; |
200 | gboolean intersects; |
201 | |
202 | for (run = 0; run < N_RUNS; run++) |
203 | { |
204 | left = _gtk_bitmask_new (); |
205 | right = _gtk_bitmask_new (); |
206 | expected = _gtk_bitmask_new (); |
207 | |
208 | for (try = 0; try < N_TRIES; try++) |
209 | { |
210 | guint id = g_test_rand_int_range (begin: 0, MAX_INDEX); |
211 | gboolean set = g_test_rand_bit (); |
212 | |
213 | if (g_test_rand_bit ()) |
214 | { |
215 | left = _gtk_bitmask_set (mask: left, index_: id, value: set); |
216 | expected = _gtk_bitmask_set (mask: expected, index_: id, value: set ? _gtk_bitmask_get (mask: right, index_: id) : 0); |
217 | } |
218 | else |
219 | { |
220 | right = _gtk_bitmask_set (mask: right, index_: id, value: set); |
221 | expected = _gtk_bitmask_set (mask: expected, index_: id, value: set ? _gtk_bitmask_get (mask: left, index_: id) : 0); |
222 | } |
223 | } |
224 | |
225 | intersects = _gtk_bitmask_intersects (mask: left, other: right); |
226 | g_assert_cmpint (intersects, ==, _gtk_bitmask_intersects (right, left)); |
227 | g_assert_cmpint (intersects, !=, _gtk_bitmask_is_empty (expected)); |
228 | |
229 | left = _gtk_bitmask_intersect (mask: left, other: right); |
230 | right = _gtk_bitmask_intersect (mask: right, other: left); |
231 | |
232 | assert_cmpmasks (left, expected); |
233 | assert_cmpmasks (right, expected); |
234 | _gtk_bitmask_free (mask: left); |
235 | _gtk_bitmask_free (mask: right); |
236 | _gtk_bitmask_free (mask: expected); |
237 | } |
238 | } |
239 | |
240 | static void |
241 | test_intersect_hardcoded (void) |
242 | { |
243 | GtkBitmask *left, *right, *intersection, *expected; |
244 | const char *left_str, *right_str; |
245 | guint left_len, right_len; |
246 | guint i, l, r; |
247 | |
248 | for (l = 0; l < G_N_ELEMENTS (tests); l++) |
249 | { |
250 | for (r = 0; r < G_N_ELEMENTS (tests); r++) |
251 | { |
252 | left = masks[l]; |
253 | right = masks[r]; |
254 | left_str = tests[l]; |
255 | right_str = tests[r]; |
256 | left_len = strlen (s: tests[l]); |
257 | right_len = strlen (s: tests[r]); |
258 | |
259 | expected = _gtk_bitmask_new (); |
260 | if (left_len > right_len) |
261 | left_str += left_len - right_len; |
262 | if (right_len > left_len) |
263 | right_str += right_len - left_len; |
264 | i = MIN (right_len, left_len); |
265 | while (i--) |
266 | { |
267 | expected = _gtk_bitmask_set (mask: expected, index_: i, value: left_str[0] == '1' && right_str[0] == '1'); |
268 | right_str++; |
269 | left_str++; |
270 | } |
271 | |
272 | intersection = _gtk_bitmask_intersect (mask: _gtk_bitmask_copy (mask: left), other: right); |
273 | |
274 | assert_cmpmasks (intersection, expected); |
275 | g_assert_cmpint (_gtk_bitmask_is_empty (expected), ==, !_gtk_bitmask_intersects (left, right)); |
276 | |
277 | _gtk_bitmask_free (mask: intersection); |
278 | _gtk_bitmask_free (mask: expected); |
279 | } |
280 | } |
281 | } |
282 | |
283 | static void |
284 | test_subtract_hardcoded (void) |
285 | { |
286 | GtkBitmask *left, *right, *subtracted, *expected; |
287 | const char *left_str, *right_str; |
288 | guint left_len, right_len; |
289 | guint i, l, r; |
290 | |
291 | for (l = 0; l < G_N_ELEMENTS (tests); l++) |
292 | { |
293 | for (r = 0; r < G_N_ELEMENTS (tests); r++) |
294 | { |
295 | left = masks[l]; |
296 | right = masks[r]; |
297 | left_str = tests[l]; |
298 | right_str = tests[r]; |
299 | left_len = strlen (s: tests[l]); |
300 | right_len = strlen (s: tests[r]); |
301 | |
302 | expected = _gtk_bitmask_new (); |
303 | for (i = MIN (right_len, left_len); i < left_len; i++) |
304 | { |
305 | expected = _gtk_bitmask_set (mask: expected, index_: i, value: left_str[left_len - i - 1] == '1'); |
306 | } |
307 | if (left_len > right_len) |
308 | left_str += left_len - right_len; |
309 | if (right_len > left_len) |
310 | right_str += right_len - left_len; |
311 | i = MIN (right_len, left_len); |
312 | while (i--) |
313 | { |
314 | expected = _gtk_bitmask_set (mask: expected, index_: i, value: left_str[0] == '1' && right_str[0] == '0'); |
315 | right_str++; |
316 | left_str++; |
317 | } |
318 | |
319 | { |
320 | char *sl = _gtk_bitmask_to_string (mask: left); |
321 | char *sr = _gtk_bitmask_to_string (mask: right); |
322 | g_test_message (format: "%s - %s\n" , sl, sr); |
323 | g_free (mem: sl); |
324 | g_free (mem: sr); |
325 | } |
326 | subtracted = _gtk_bitmask_subtract (mask: _gtk_bitmask_copy (mask: left), other: right); |
327 | |
328 | assert_cmpmasks (subtracted, expected); |
329 | |
330 | _gtk_bitmask_free (mask: subtracted); |
331 | _gtk_bitmask_free (mask: expected); |
332 | } |
333 | } |
334 | } |
335 | |
336 | #define SWAP(_a, _b) G_STMT_START{ \ |
337 | guint _tmp = _a; \ |
338 | _a = _b; \ |
339 | _b = _tmp; \ |
340 | }G_STMT_END |
341 | |
342 | static void |
343 | test_invert_range_hardcoded (void) |
344 | { |
345 | guint t, l, r, i; |
346 | gsize r_len, l_len, ref_len; |
347 | char *ref_str; |
348 | GtkBitmask *bitmask, *ref; |
349 | |
350 | for (t = 0; t < G_N_ELEMENTS (tests); t++) |
351 | { |
352 | for (l = 0; l < G_N_ELEMENTS (tests); l++) |
353 | { |
354 | l_len = strlen (s: tests[l]); |
355 | |
356 | for (r = 0; r < G_N_ELEMENTS (tests); r++) |
357 | { |
358 | r_len = strlen (s: tests[r]); |
359 | if (r_len < l_len) |
360 | continue; |
361 | |
362 | ref_len = MAX (r_len, strlen (tests[t])); |
363 | ref_str = g_strdup_printf (format: "%*s" , (int) ref_len, tests[t]); |
364 | for (i = 0; i < ref_len && ref_str[i] == ' '; i++) |
365 | ref_str[i] = '0'; |
366 | for (i = l_len - 1; i < r_len; i++) |
367 | { |
368 | ref_str[ref_len-i-1] = ref_str[ref_len-i-1] == '0' ? '1' : '0'; |
369 | } |
370 | ref = gtk_bitmask_new_parse (string: ref_str); |
371 | g_free (mem: ref_str); |
372 | |
373 | bitmask = gtk_bitmask_new_parse (string: tests[t]); |
374 | bitmask = _gtk_bitmask_invert_range (mask: bitmask, start: l_len - 1, end: r_len); |
375 | |
376 | assert_cmpmasks (bitmask, ref); |
377 | |
378 | _gtk_bitmask_free (mask: bitmask); |
379 | _gtk_bitmask_free (mask: ref); |
380 | } |
381 | } |
382 | } |
383 | } |
384 | |
385 | static void |
386 | test_invert_range (void) |
387 | { |
388 | GtkBitmask *left, *right, *intersection, *expected; |
389 | guint run; |
390 | guint left_start, left_end, right_start, right_end, start, end; |
391 | |
392 | for (run = 0; run < N_RUNS; run++) |
393 | { |
394 | left = _gtk_bitmask_new (); |
395 | right = _gtk_bitmask_new (); |
396 | expected = _gtk_bitmask_new (); |
397 | |
398 | left_start = g_test_rand_int_range (begin: 0, MAX_INDEX); |
399 | left_end = g_test_rand_int_range (begin: 0, MAX_INDEX); |
400 | if (left_start > left_end) |
401 | SWAP (left_start, left_end); |
402 | right_start = g_test_rand_int_range (begin: 0, MAX_INDEX); |
403 | right_end = g_test_rand_int_range (begin: 0, MAX_INDEX); |
404 | if (right_start > right_end) |
405 | SWAP (right_start, right_end); |
406 | start = MAX (left_start, right_start); |
407 | end = MIN (left_end, right_end); |
408 | |
409 | if (left_start != left_end) |
410 | left = _gtk_bitmask_invert_range (mask: left, start: left_start, end: left_end); |
411 | if (right_start != right_end) |
412 | right = _gtk_bitmask_invert_range (mask: right, start: right_start, end: right_end); |
413 | if (start < end) |
414 | expected = _gtk_bitmask_invert_range (mask: expected, start, end); |
415 | |
416 | intersection = _gtk_bitmask_copy (mask: left); |
417 | intersection = _gtk_bitmask_intersect (mask: intersection, other: right); |
418 | |
419 | assert_cmpmasks (intersection, expected); |
420 | |
421 | if (start < end) |
422 | expected = _gtk_bitmask_invert_range (mask: expected, start, end); |
423 | |
424 | g_assert_cmpint (_gtk_bitmask_is_empty (expected), ==, TRUE); |
425 | |
426 | _gtk_bitmask_free (mask: left); |
427 | _gtk_bitmask_free (mask: right); |
428 | _gtk_bitmask_free (mask: intersection); |
429 | _gtk_bitmask_free (mask: expected); |
430 | } |
431 | } |
432 | |
433 | /* SETUP & RUNNING */ |
434 | |
435 | static void |
436 | create_masks (void) |
437 | { |
438 | guint i; |
439 | |
440 | for (i = 0; i < G_N_ELEMENTS (tests); i++) |
441 | masks[i] = gtk_bitmask_new_parse (string: tests[i]); |
442 | } |
443 | |
444 | static void |
445 | free_masks (void) |
446 | { |
447 | guint i; |
448 | |
449 | for (i = 0; i < G_N_ELEMENTS (tests); i++) |
450 | { |
451 | _gtk_bitmask_free (mask: masks[i]); |
452 | masks[i] = NULL; |
453 | } |
454 | } |
455 | |
456 | int |
457 | main (int argc, char *argv[]) |
458 | { |
459 | int result; |
460 | |
461 | (g_test_init) (argc: &argc, argv: &argv, NULL); |
462 | setlocale (LC_ALL, locale: "C" ); |
463 | |
464 | create_masks (); |
465 | |
466 | g_test_add_func (testpath: "/bitmask/to_string" , test_func: test_to_string); |
467 | g_test_add_func (testpath: "/bitmask/is_empty" , test_func: test_is_empty); |
468 | g_test_add_func (testpath: "/bitmask/equals" , test_func: test_equals); |
469 | g_test_add_func (testpath: "/bitmask/set" , test_func: test_set); |
470 | g_test_add_func (testpath: "/bitmask/union" , test_func: test_union); |
471 | g_test_add_func (testpath: "/bitmask/intersect" , test_func: test_intersect); |
472 | g_test_add_func (testpath: "/bitmask/intersect_hardcoded" , test_func: test_intersect_hardcoded); |
473 | g_test_add_func (testpath: "/bitmask/subtract_hardcoded" , test_func: test_subtract_hardcoded); |
474 | g_test_add_func (testpath: "/bitmask/invert_range" , test_func: test_invert_range); |
475 | g_test_add_func (testpath: "/bitmask/invert_range_hardcoded" , test_func: test_invert_range_hardcoded); |
476 | |
477 | result = g_test_run (); |
478 | |
479 | free_masks (); |
480 | |
481 | return result; |
482 | } |
483 | |