Debian Codegraph @

testsuite/gtk/bitmask.c

raw
1 /* GtkRBTree tests.
2 *
3 * Copyright (C) 2011, Red Hat, Inc.
4 * Authors: Benjamin Otte <[email protected]>
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 (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, length - i - 1, FALSE);
50 else if (string[i] == '1')
51 mask = _gtk_bitmask_set (mask, 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 (masks[i]);
100 g_assert_cmpstr (to_string, ==, tests[i]);
101 g_free (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 (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 (0, MAX_INDEX);
146 copy = _gtk_bitmask_set (copy, indexes[j], g_test_rand_bit ());
147 }
148
149 for (j = 0; j < N_TRIES; j++)
150 {
151 copy = _gtk_bitmask_set (copy, indexes[j], _gtk_bitmask_get (mask, indexes[j]));
152 }
153
154 assert_cmpmasks (copy, mask);
155 _gtk_bitmask_free (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 (0, N_TRIES);
172 for (try = 0; try < n_tries; try++)
173 {
174 guint id = g_test_rand_int_range (0, MAX_INDEX);
175
176 if (g_test_rand_bit ())
177 left = _gtk_bitmask_set (left, id, TRUE);
178 else
179 right = _gtk_bitmask_set (right, id, TRUE);
180
181 expected = _gtk_bitmask_set (expected, id, TRUE);
182 }
183
184 left = _gtk_bitmask_union (left, right);
185 right = _gtk_bitmask_union (right, left);
186
187 assert_cmpmasks (left, expected);
188 assert_cmpmasks (right, expected);
189 _gtk_bitmask_free (left);
190 _gtk_bitmask_free (right);
191 _gtk_bitmask_free (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 (0, MAX_INDEX);
211 gboolean set = g_test_rand_bit ();
212
213 if (g_test_rand_bit ())
214 {
215 left = _gtk_bitmask_set (left, id, set);
216 expected = _gtk_bitmask_set (expected, id, set ? _gtk_bitmask_get (right, id) : 0);
217 }
218 else
219 {
220 right = _gtk_bitmask_set (right, id, set);
221 expected = _gtk_bitmask_set (expected, id, set ? _gtk_bitmask_get (left, id) : 0);
222 }
223 }
224
225 intersects = _gtk_bitmask_intersects (left, 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 (left, right);
230 right = _gtk_bitmask_intersect (right, left);
231
232 assert_cmpmasks (left, expected);
233 assert_cmpmasks (right, expected);
234 _gtk_bitmask_free (left);
235 _gtk_bitmask_free (right);
236 _gtk_bitmask_free (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 (tests[l]);
257 right_len = strlen (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 (expected, i, left_str[0] == '1' && right_str[0] == '1');
268 right_str++;
269 left_str++;
270 }
271
272 intersection = _gtk_bitmask_intersect (_gtk_bitmask_copy (left), 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 (intersection);
278 _gtk_bitmask_free (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 (tests[l]);
300 right_len = strlen (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 (expected, i, 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 (expected, i, left_str[0] == '1' && right_str[0] == '0');
315 right_str++;
316 left_str++;
317 }
318
319 g_test_message ("%s - %s\n", _gtk_bitmask_to_string (left), _gtk_bitmask_to_string (right));
320 subtracted = _gtk_bitmask_subtract (_gtk_bitmask_copy (left), right);
321
322 assert_cmpmasks (subtracted, expected);
323
324 _gtk_bitmask_free (subtracted);
325 _gtk_bitmask_free (expected);
326 }
327 }
328 }
329
330 #define SWAP(_a, _b) G_STMT_START{ \
331 guint _tmp = _a; \
332 _a = _b; \
333 _b = _tmp; \
334 }G_STMT_END
335
336 static void
337 test_invert_range_hardcoded (void)
338 {
339 guint t, l, r, i;
340 gsize r_len, l_len, ref_len;
341 char *ref_str;
342 GtkBitmask *bitmask, *ref;
343
344 for (t = 0; t < G_N_ELEMENTS (tests); t++)
345 {
346 for (l = 0; l < G_N_ELEMENTS (tests); l++)
347 {
348 l_len = strlen (tests[l]);
349
350 for (r = 0; r < G_N_ELEMENTS (tests); r++)
351 {
352 r_len = strlen (tests[r]);
353 if (r_len < l_len)
354 continue;
355
356 ref_len = MAX (r_len, strlen (tests[t]));
357 ref_str = g_strdup_printf ("%*s", (int) ref_len, tests[t]);
358 for (i = 0; i < ref_len && ref_str[i] == ' '; i++)
359 ref_str[i] = '0';
360 for (i = l_len - 1; i < r_len; i++)
361 {
362 ref_str[ref_len-i-1] = ref_str[ref_len-i-1] == '0' ? '1' : '0';
363 }
364 ref = gtk_bitmask_new_parse (ref_str);
365 g_free (ref_str);
366
367 bitmask = gtk_bitmask_new_parse (tests[t]);
368 bitmask = _gtk_bitmask_invert_range (bitmask, l_len - 1, r_len);
369
370 assert_cmpmasks (bitmask, ref);
371
372 _gtk_bitmask_free (bitmask);
373 _gtk_bitmask_free (ref);
374 }
375 }
376 }
377 }
378
379 static void
380 test_invert_range (void)
381 {
382 GtkBitmask *left, *right, *intersection, *expected;
383 guint run;
384 guint left_start, left_end, right_start, right_end, start, end;
385
386 for (run = 0; run < N_RUNS; run++)
387 {
388 left = _gtk_bitmask_new ();
389 right = _gtk_bitmask_new ();
390 expected = _gtk_bitmask_new ();
391
392 left_start = g_test_rand_int_range (0, MAX_INDEX);
393 left_end = g_test_rand_int_range (0, MAX_INDEX);
394 if (left_start > left_end)
395 SWAP (left_start, left_end);
396 right_start = g_test_rand_int_range (0, MAX_INDEX);
397 right_end = g_test_rand_int_range (0, MAX_INDEX);
398 if (right_start > right_end)
399 SWAP (right_start, right_end);
400 start = MAX (left_start, right_start);
401 end = MIN (left_end, right_end);
402
403 if (left_start != left_end)
404 left = _gtk_bitmask_invert_range (left, left_start, left_end);
405 if (right_start != right_end)
406 right = _gtk_bitmask_invert_range (right, right_start, right_end);
407 if (start < end)
408 expected = _gtk_bitmask_invert_range (expected, start, end);
409
410 intersection = _gtk_bitmask_copy (left);
411 intersection = _gtk_bitmask_intersect (intersection, right);
412
413 assert_cmpmasks (intersection, expected);
414
415 if (start < end)
416 expected = _gtk_bitmask_invert_range (expected, start, end);
417
418 g_assert_cmpint (_gtk_bitmask_is_empty (expected), ==, TRUE);
419
420 _gtk_bitmask_free (left);
421 _gtk_bitmask_free (right);
422 _gtk_bitmask_free (intersection);
423 _gtk_bitmask_free (expected);
424 }
425 }
426
427 /* SETUP & RUNNING */
428
429 static void
430 create_masks (void)
431 {
432 guint i;
433
434 for (i = 0; i < G_N_ELEMENTS (tests); i++)
435 masks[i] = gtk_bitmask_new_parse (tests[i]);
436 }
437
438 static void
439 free_masks (void)
440 {
441 guint i;
442
443 for (i = 0; i < G_N_ELEMENTS (tests); i++)
444 {
445 _gtk_bitmask_free (masks[i]);
446 masks[i] = NULL;
447 }
448 }
449
450 int
451 main (int argc, char *argv[])
452 {
453 int result;
454
455 g_test_init (&argc, &argv, NULL);
456 setlocale (LC_ALL, "C");
457 g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
458
459 create_masks ();
460
461 g_test_add_func ("/bitmask/to_string", test_to_string);
462 g_test_add_func ("/bitmask/is_empty", test_is_empty);
463 g_test_add_func ("/bitmask/equals", test_equals);
464 g_test_add_func ("/bitmask/set", test_set);
465 g_test_add_func ("/bitmask/union", test_union);
466 g_test_add_func ("/bitmask/intersect", test_intersect);
467 g_test_add_func ("/bitmask/intersect_hardcoded", test_intersect_hardcoded);
468 g_test_add_func ("/bitmask/subtract_hardcoded", test_subtract_hardcoded);
469 g_test_add_func ("/bitmask/invert_range", test_invert_range);
470 g_test_add_func ("/bitmask/invert_range_hardcoded", test_invert_range_hardcoded);
471
472 result = g_test_run ();
473
474 free_masks ();
475
476 return result;
477 }