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/gtk.h>
23
24#define LARGE_VALUE (1000 * 1000)
25
26static GtkBitset *
27create_powers_of_10 (void)
28{
29 GtkBitset *set;
30 guint i;
31
32 set = gtk_bitset_new_empty ();
33 for (i = 1; i <= LARGE_VALUE; i *= 10)
34 gtk_bitset_add (self: set, value: i);
35
36 return set;
37}
38
39static GtkBitset *
40create_powers_of_10_ranges (void)
41{
42 GtkBitset *set;
43 guint i, j;
44
45 set = gtk_bitset_new_empty ();
46 for (i = 1, j = 0; i <= LARGE_VALUE; i *= 10, j++)
47 gtk_bitset_add_range (self: set, start: i - j, n_items: 2 * j);
48
49 return set;
50}
51
52static GtkBitset *
53create_large_range (void)
54{
55 GtkBitset *set;
56
57 set = gtk_bitset_new_empty ();
58 gtk_bitset_add_range (self: set, start: 0, LARGE_VALUE);
59
60 return set;
61}
62
63static GtkBitset *
64create_large_rectangle (void)
65{
66 GtkBitset *set;
67
68 set = gtk_bitset_new_empty ();
69 gtk_bitset_add_rectangle (self: set, start: 0, width: 900, height: 900, stride: 1000);
70
71 return set;
72}
73
74static struct {
75 GtkBitset * (* create) (void);
76 guint n_elements;
77 guint minimum;
78 guint maximum;
79} bitsets[] =
80{
81 { gtk_bitset_new_empty, 0, G_MAXUINT, 0 },
82 { create_powers_of_10, 7, 1, LARGE_VALUE },
83 { create_powers_of_10_ranges, 42, 9, LARGE_VALUE + 5, },
84 { create_large_range, LARGE_VALUE, 0, LARGE_VALUE - 1 },
85 { create_large_rectangle, 900 * 900, 0, 899899 }
86};
87
88/* UTILITIES */
89
90/* TEST */
91
92static void
93test_is_empty (void)
94{
95 guint i;
96 GtkBitset *set;
97
98 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
99 {
100 set = bitsets[i].create();
101
102 if (bitsets[i].n_elements == 0)
103 g_assert_true (gtk_bitset_is_empty (set));
104 else
105 g_assert_false (gtk_bitset_is_empty (set));
106
107 gtk_bitset_unref (self: set);
108 }
109}
110
111static void
112test_minimum (void)
113{
114 guint i;
115 GtkBitset *set;
116 GtkBitsetIter iter;
117 gboolean success;
118 guint value;
119
120 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
121 {
122 set = bitsets[i].create();
123
124 g_assert_cmpint (gtk_bitset_get_minimum (set), ==, bitsets[i].minimum);
125
126 success = gtk_bitset_iter_init_first (iter: &iter, set, value: &value);
127 if (success)
128 {
129 g_assert_false (bitsets[i].n_elements == 0);
130 g_assert_cmpint (value, ==, bitsets[i].minimum);
131 }
132 else
133 {
134 g_assert_true (bitsets[i].n_elements == 0);
135 g_assert_cmpint (value, ==, 0);
136 }
137 g_assert_cmpint (gtk_bitset_iter_is_valid (&iter), ==, success);
138 g_assert_cmpint (gtk_bitset_iter_get_value (&iter), ==, value);
139
140 gtk_bitset_unref (self: set);
141 }
142}
143
144static void
145test_maximum (void)
146{
147 guint i;
148 GtkBitset *set;
149 GtkBitsetIter iter;
150 gboolean success;
151 guint value;
152
153 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
154 {
155 set = bitsets[i].create();
156
157 g_assert_cmpint (gtk_bitset_get_maximum (set), ==, bitsets[i].maximum);
158
159 success = gtk_bitset_iter_init_last (iter: &iter, set, value: &value);
160 if (success)
161 {
162 g_assert_false (bitsets[i].n_elements == 0);
163 g_assert_cmpint (value, ==, bitsets[i].maximum);
164 }
165 else
166 {
167 g_assert_true (bitsets[i].n_elements == 0);
168 g_assert_cmpint (value, ==, 0);
169 }
170 g_assert_cmpint (gtk_bitset_iter_is_valid (&iter), ==, success);
171 g_assert_cmpint (gtk_bitset_iter_get_value (&iter), ==, value);
172
173 gtk_bitset_unref (self: set);
174 }
175}
176
177static void
178test_equals (void)
179{
180 guint i, j;
181 GtkBitset *iset, *jset;
182
183 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
184 {
185 iset = bitsets[i].create();
186
187 g_assert_true (gtk_bitset_equals (iset, iset));
188
189 for (j = 0; j < G_N_ELEMENTS (bitsets); j++)
190 {
191 jset = bitsets[j].create();
192
193 if (i == j)
194 g_assert_true (gtk_bitset_equals (iset, jset));
195 else
196 g_assert_false (gtk_bitset_equals (iset, jset));
197
198 gtk_bitset_unref (self: jset);
199 }
200
201 gtk_bitset_unref (self: iset);
202 }
203}
204
205static void
206test_union (void)
207{
208 guint i, j, k, min, max;
209 GtkBitset *iset, *jset, *testset;
210
211 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
212 {
213 iset = bitsets[i].create();
214
215 g_assert_true (gtk_bitset_equals (iset, iset));
216
217 for (j = 0; j < G_N_ELEMENTS (bitsets); j++)
218 {
219 jset = bitsets[j].create();
220
221 testset = gtk_bitset_copy (self: iset);
222 gtk_bitset_union (self: testset, other: jset);
223
224 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset));
225 g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset));
226 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset));
227 g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset));
228
229 for (k = min; k <= max; k++)
230 {
231 g_assert_cmpint (gtk_bitset_contains (iset, k) || gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k));
232 }
233
234 gtk_bitset_unref (self: testset);
235 gtk_bitset_unref (self: jset);
236 }
237
238 gtk_bitset_unref (self: iset);
239 }
240}
241
242static void
243test_intersect (void)
244{
245 guint i, j, k, min, max;
246 GtkBitset *iset, *jset, *testset;
247
248 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
249 {
250 iset = bitsets[i].create();
251
252 g_assert_true (gtk_bitset_equals (iset, iset));
253
254 for (j = 0; j < G_N_ELEMENTS (bitsets); j++)
255 {
256 jset = bitsets[j].create();
257
258 testset = gtk_bitset_copy (self: iset);
259 gtk_bitset_intersect (self: testset, other: jset);
260
261 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset));
262 g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset));
263 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset));
264 g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset));
265
266 for (k = min; k <= max; k++)
267 {
268 g_assert_cmpint (gtk_bitset_contains (iset, k) && gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k));
269 }
270
271 gtk_bitset_unref (self: testset);
272 gtk_bitset_unref (self: jset);
273 }
274
275 gtk_bitset_unref (self: iset);
276 }
277}
278
279static void
280test_difference (void)
281{
282 guint i, j, k, min, max;
283 GtkBitset *iset, *jset, *testset;
284
285 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
286 {
287 iset = bitsets[i].create();
288
289 g_assert_true (gtk_bitset_equals (iset, iset));
290
291 for (j = 0; j < G_N_ELEMENTS (bitsets); j++)
292 {
293 jset = bitsets[j].create();
294
295 testset = gtk_bitset_copy (self: iset);
296 gtk_bitset_difference (self: testset, other: jset);
297
298 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset));
299 g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset));
300 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset));
301 g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset));
302
303 for (k = min; k <= max; k++)
304 {
305 g_assert_cmpint (gtk_bitset_contains (iset, k) ^ gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k));
306 }
307
308 gtk_bitset_unref (self: testset);
309 gtk_bitset_unref (self: jset);
310 }
311
312 gtk_bitset_unref (self: iset);
313 }
314}
315
316static void
317test_subtract (void)
318{
319 guint i, j, k, min, max;
320 GtkBitset *iset, *jset, *testset;
321
322 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
323 {
324 iset = bitsets[i].create();
325
326 g_assert_true (gtk_bitset_equals (iset, iset));
327
328 for (j = 0; j < G_N_ELEMENTS (bitsets); j++)
329 {
330 jset = bitsets[j].create();
331
332 testset = gtk_bitset_copy (self: iset);
333 gtk_bitset_subtract (self: testset, other: jset);
334
335 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (jset));
336 g_assert_cmpint (min, <=, gtk_bitset_get_minimum (testset));
337 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (jset));
338 g_assert_cmpint (max, >=, gtk_bitset_get_maximum (testset));
339
340 for (k = min; k <= max; k++)
341 {
342 g_assert_cmpint (gtk_bitset_contains (iset, k) && !gtk_bitset_contains (jset, k), ==, gtk_bitset_contains (testset, k));
343 }
344
345 gtk_bitset_unref (self: testset);
346 gtk_bitset_unref (self: jset);
347 }
348
349 gtk_bitset_unref (self: iset);
350 }
351}
352
353static void
354test_shift_left (void)
355{
356 guint i, j, k, min, max;
357 GtkBitset *iset, *testset;
358
359 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
360 {
361 iset = bitsets[i].create();
362
363 for (j = 1; j < 10000000; j *= 10)
364 {
365 testset = gtk_bitset_copy (self: iset);
366
367 gtk_bitset_shift_left (self: testset, amount: j);
368
369 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (testset));
370 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (testset));
371
372 for (k = min; k <= max; k++)
373 {
374 if (k >= j)
375 g_assert_cmpint (gtk_bitset_contains (iset, k), ==, gtk_bitset_contains (testset, k - j));
376 }
377
378 gtk_bitset_unref (self: testset);
379 }
380
381 gtk_bitset_unref (self: iset);
382 }
383}
384
385static void
386test_shift_right (void)
387{
388 guint i, j, k, min, max;
389 GtkBitset *iset, *testset;
390
391 for (i = 0; i < G_N_ELEMENTS (bitsets); i++)
392 {
393 iset = bitsets[i].create();
394
395 for (j = 1; j < 10000000; j *= 10)
396 {
397 testset = gtk_bitset_copy (self: iset);
398
399 gtk_bitset_shift_right (self: testset, amount: j);
400
401 min = MIN (gtk_bitset_get_minimum (iset), gtk_bitset_get_minimum (testset));
402 max = MAX (gtk_bitset_get_maximum (iset), gtk_bitset_get_maximum (testset));
403
404 for (k = min; k <= max; k++)
405 {
406 if (k <= G_MAXUINT - j)
407 g_assert_cmpint (gtk_bitset_contains (iset, k), ==, gtk_bitset_contains (testset, k + j));
408 }
409
410 gtk_bitset_unref (self: testset);
411 }
412
413 gtk_bitset_unref (self: iset);
414 }
415}
416
417static void
418test_slice (void)
419{
420 GtkBitset *set;
421 guint i;
422
423 set = gtk_bitset_new_empty ();
424
425 gtk_bitset_add_range (self: set, start: 10, n_items: 30);
426
427 gtk_bitset_splice (self: set, position: 20, removed: 10, added: 20);
428
429 for (i = 0; i < 60; i++)
430 g_assert_cmpint (gtk_bitset_contains (set, i), ==, (i >= 10 && i < 20) ||
431 (i >= 40 && i < 50));
432
433 gtk_bitset_splice (self: set, position: 25, removed: 10, added: 0);
434
435 for (i = 0; i < 60; i++)
436 g_assert_cmpint (gtk_bitset_contains (set, i), ==, (i >= 10 && i < 20) ||
437 (i >= 30 && i < 40));
438
439 gtk_bitset_unref (self: set);
440}
441
442static void
443test_rectangle (void)
444{
445 GtkBitset *set;
446 GString *s;
447 guint i, j;
448
449 set = gtk_bitset_new_empty ();
450
451 gtk_bitset_add_rectangle (self: set, start: 8, width: 5, height: 5, stride: 7);
452 gtk_bitset_remove_rectangle (self: set, start: 16, width: 3, height: 3, stride: 7);
453 gtk_bitset_add_rectangle (self: set, start: 24, width: 1, height: 1, stride: 7);
454
455 s = g_string_new (init: "");
456 for (i = 0; i < 7; i++)
457 {
458 for (j = 0; j < 7; j++)
459 g_string_append_printf (string: s, format: "%c ",
460 gtk_bitset_contains (self: set, value: i * 7 + j) ? '*' : ' ');
461 g_string_append (string: s, val: "\n");
462 }
463 g_assert_cmpstr (s->str, ==,
464 " \n"
465 " * * * * * \n"
466 " * * \n"
467 " * * * \n"
468 " * * \n"
469 " * * * * * \n"
470 " \n");
471
472 g_string_free (string: s, TRUE);
473 gtk_bitset_unref (self: set);
474}
475
476static void
477test_iter (void)
478{
479 GtkBitset *set;
480 GtkBitsetIter iter;
481 gboolean ret;
482 guint value;
483
484 set = gtk_bitset_new_empty ();
485
486 ret = gtk_bitset_iter_init_first (iter: &iter, set, value: &value);
487 g_assert_false (ret);
488
489 g_assert_false (gtk_bitset_iter_is_valid (&iter));
490 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0);
491 g_assert_false (gtk_bitset_iter_previous (&iter, &value));
492 g_assert_false (gtk_bitset_iter_next (&iter, &value));
493
494 ret = gtk_bitset_iter_init_last (iter: &iter, set, value: &value);
495 g_assert_false (ret);
496
497 g_assert_false (gtk_bitset_iter_is_valid (&iter));
498 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0);
499 g_assert_false (gtk_bitset_iter_previous (&iter, &value));
500 g_assert_false (gtk_bitset_iter_next (&iter, &value));
501
502 ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 0, value: &value);
503
504 g_assert_false (gtk_bitset_iter_is_valid (&iter));
505 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 0);
506 g_assert_false (gtk_bitset_iter_previous (&iter, &value));
507 g_assert_false (gtk_bitset_iter_next (&iter, &value));
508
509 gtk_bitset_add_range_closed (self: set, first: 10, last: 20);
510
511 ret = gtk_bitset_iter_init_first (iter: &iter, set, value: &value);
512 g_assert_true (ret);
513 g_assert_true (gtk_bitset_iter_is_valid (&iter));
514 g_assert_cmpuint (value, ==, 10);
515 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 10);
516
517 ret = gtk_bitset_iter_next (iter: &iter, value: &value);
518 g_assert_true (ret);
519 g_assert_cmpuint (value, ==, 11);
520
521 ret = gtk_bitset_iter_next (iter: &iter, NULL);
522 g_assert_true (ret);
523 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 12);
524
525 ret = gtk_bitset_iter_init_last (iter: &iter, set, value: &value);
526 g_assert_true (ret);
527 g_assert_true (gtk_bitset_iter_is_valid (&iter));
528 g_assert_cmpuint (value, ==, 20);
529
530 ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 5, NULL);
531 g_assert_true (ret);
532 g_assert_true (gtk_bitset_iter_is_valid (&iter));
533 g_assert_cmpuint (gtk_bitset_iter_get_value (&iter), ==, 10);
534
535 ret = gtk_bitset_iter_previous (iter: &iter, NULL);
536 g_assert_false (ret);
537
538 g_assert_false (gtk_bitset_iter_is_valid (&iter));
539
540 ret = gtk_bitset_iter_init_at (iter: &iter, set, target: 100, NULL);
541 g_assert_false (ret);
542
543 gtk_bitset_unref (self: set);
544}
545
546static void
547test_splice_overflow (void)
548{
549 GtkBitset *set, *compare;
550
551 set = gtk_bitset_new_range (start: 3, n_items: 1);
552 gtk_bitset_splice (self: set, position: 0, removed: 0, added: 13);
553
554 compare = gtk_bitset_new_range (start: 16, n_items: 1);
555 g_assert_true (gtk_bitset_equals (set, compare));
556
557 gtk_bitset_unref (self: compare);
558 gtk_bitset_unref (self: set);
559}
560
561int
562main (int argc, char *argv[])
563{
564 (g_test_init) (argc: &argc, argv: &argv, NULL);
565 setlocale (LC_ALL, locale: "C");
566
567 g_test_add_func (testpath: "/bitset/is_empty", test_func: test_is_empty);
568 g_test_add_func (testpath: "/bitset/minimum", test_func: test_minimum);
569 g_test_add_func (testpath: "/bitset/maximum", test_func: test_maximum);
570 g_test_add_func (testpath: "/bitset/equals", test_func: test_equals);
571 g_test_add_func (testpath: "/bitset/union", test_func: test_union);
572 g_test_add_func (testpath: "/bitset/intersect", test_func: test_intersect);
573 g_test_add_func (testpath: "/bitset/difference", test_func: test_difference);
574 g_test_add_func (testpath: "/bitset/subtract", test_func: test_subtract);
575 g_test_add_func (testpath: "/bitset/shift-left", test_func: test_shift_left);
576 g_test_add_func (testpath: "/bitset/shift-right", test_func: test_shift_right);
577 g_test_add_func (testpath: "/bitset/slice", test_func: test_slice);
578 g_test_add_func (testpath: "/bitset/rectangle", test_func: test_rectangle);
579 g_test_add_func (testpath: "/bitset/iter", test_func: test_iter);
580 g_test_add_func (testpath: "/bitset/splice-overflow", test_func: test_splice_overflow);
581
582 return g_test_run ();
583}
584

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