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 *
gtk_bitmask_new_parse(const char * string)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
test_to_string(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
test_is_empty(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
test_equals(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
test_set(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
test_union(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
test_intersect(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
test_intersect_hardcoded(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
test_subtract_hardcoded(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 {
320 char *sl = _gtk_bitmask_to_string (left);
321 char *sr = _gtk_bitmask_to_string (right);
322 g_test_message ("%s - %s\n", sl, sr);
323 g_free (sl);
324 g_free (sr);
325 }
326 subtracted = _gtk_bitmask_subtract (_gtk_bitmask_copy (left), right);
327
328 assert_cmpmasks (subtracted, expected);
329
330 _gtk_bitmask_free (subtracted);
331 _gtk_bitmask_free (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
test_invert_range_hardcoded(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 (tests[l]);
355
356 for (r = 0; r < G_N_ELEMENTS (tests); r++)
357 {
358 r_len = strlen (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 ("%*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 (ref_str);
371 g_free (ref_str);
372
373 bitmask = gtk_bitmask_new_parse (tests[t]);
374 bitmask = _gtk_bitmask_invert_range (bitmask, l_len - 1, r_len);
375
376 assert_cmpmasks (bitmask, ref);
377
378 _gtk_bitmask_free (bitmask);
379 _gtk_bitmask_free (ref);
380 }
381 }
382 }
383 }
384
385 static void
test_invert_range(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 (0, MAX_INDEX);
399 left_end = g_test_rand_int_range (0, MAX_INDEX);
400 if (left_start > left_end)
401 SWAP (left_start, left_end);
402 right_start = g_test_rand_int_range (0, MAX_INDEX);
403 right_end = g_test_rand_int_range (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 (left, left_start, left_end);
411 if (right_start != right_end)
412 right = _gtk_bitmask_invert_range (right, right_start, right_end);
413 if (start < end)
414 expected = _gtk_bitmask_invert_range (expected, start, end);
415
416 intersection = _gtk_bitmask_copy (left);
417 intersection = _gtk_bitmask_intersect (intersection, right);
418
419 assert_cmpmasks (intersection, expected);
420
421 if (start < end)
422 expected = _gtk_bitmask_invert_range (expected, start, end);
423
424 g_assert_cmpint (_gtk_bitmask_is_empty (expected), ==, TRUE);
425
426 _gtk_bitmask_free (left);
427 _gtk_bitmask_free (right);
428 _gtk_bitmask_free (intersection);
429 _gtk_bitmask_free (expected);
430 }
431 }
432
433 /* SETUP & RUNNING */
434
435 static void
create_masks(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 (tests[i]);
442 }
443
444 static void
free_masks(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 (masks[i]);
452 masks[i] = NULL;
453 }
454 }
455
456 int
main(int argc,char * argv[])457 main (int argc, char *argv[])
458 {
459 int result;
460
461 (g_test_init) (&argc, &argv, NULL);
462 setlocale (LC_ALL, "C");
463
464 create_masks ();
465
466 g_test_add_func ("/bitmask/to_string", test_to_string);
467 g_test_add_func ("/bitmask/is_empty", test_is_empty);
468 g_test_add_func ("/bitmask/equals", test_equals);
469 g_test_add_func ("/bitmask/set", test_set);
470 g_test_add_func ("/bitmask/union", test_union);
471 g_test_add_func ("/bitmask/intersect", test_intersect);
472 g_test_add_func ("/bitmask/intersect_hardcoded", test_intersect_hardcoded);
473 g_test_add_func ("/bitmask/subtract_hardcoded", test_subtract_hardcoded);
474 g_test_add_func ("/bitmask/invert_range", test_invert_range);
475 g_test_add_func ("/bitmask/invert_range_hardcoded", test_invert_range_hardcoded);
476
477 result = g_test_run ();
478
479 free_masks ();
480
481 return result;
482 }
483