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
37static GtkBitmask *
38gtk_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
74static 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
87static GtkBitmask *masks[G_N_ELEMENTS (tests)];
88
89/* TEST */
90
91static void
92test_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
105static void
106test_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
116static void
117test_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
130static void
131test_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
159static void
160test_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
195static void
196test_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
240static void
241test_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
283static void
284test_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
342static void
343test_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
385static void
386test_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
435static void
436create_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
444static void
445free_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
456int
457main (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

source code of gtk/testsuite/gtk/bitmask.c