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
26 static GtkBitset *
create_powers_of_10(void)27 create_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 (set, i);
35
36 return set;
37 }
38
39 static GtkBitset *
create_powers_of_10_ranges(void)40 create_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 (set, i - j, 2 * j);
48
49 return set;
50 }
51
52 static GtkBitset *
create_large_range(void)53 create_large_range (void)
54 {
55 GtkBitset *set;
56
57 set = gtk_bitset_new_empty ();
58 gtk_bitset_add_range (set, 0, LARGE_VALUE);
59
60 return set;
61 }
62
63 static GtkBitset *
create_large_rectangle(void)64 create_large_rectangle (void)
65 {
66 GtkBitset *set;
67
68 set = gtk_bitset_new_empty ();
69 gtk_bitset_add_rectangle (set, 0, 900, 900, 1000);
70
71 return set;
72 }
73
74 static 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
92 static void
test_is_empty(void)93 test_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 (set);
108 }
109 }
110
111 static void
test_minimum(void)112 test_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, set, &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 (set);
141 }
142 }
143
144 static void
test_maximum(void)145 test_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, set, &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 (set);
174 }
175 }
176
177 static void
test_equals(void)178 test_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 (jset);
199 }
200
201 gtk_bitset_unref (iset);
202 }
203 }
204
205 static void
test_union(void)206 test_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 (iset);
222 gtk_bitset_union (testset, 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 (testset);
235 gtk_bitset_unref (jset);
236 }
237
238 gtk_bitset_unref (iset);
239 }
240 }
241
242 static void
test_intersect(void)243 test_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 (iset);
259 gtk_bitset_intersect (testset, 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 (testset);
272 gtk_bitset_unref (jset);
273 }
274
275 gtk_bitset_unref (iset);
276 }
277 }
278
279 static void
test_difference(void)280 test_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 (iset);
296 gtk_bitset_difference (testset, 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 (testset);
309 gtk_bitset_unref (jset);
310 }
311
312 gtk_bitset_unref (iset);
313 }
314 }
315
316 static void
test_subtract(void)317 test_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 (iset);
333 gtk_bitset_subtract (testset, 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 (testset);
346 gtk_bitset_unref (jset);
347 }
348
349 gtk_bitset_unref (iset);
350 }
351 }
352
353 static void
test_shift_left(void)354 test_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 (iset);
366
367 gtk_bitset_shift_left (testset, 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 (testset);
379 }
380
381 gtk_bitset_unref (iset);
382 }
383 }
384
385 static void
test_shift_right(void)386 test_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 (iset);
398
399 gtk_bitset_shift_right (testset, 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 (testset);
411 }
412
413 gtk_bitset_unref (iset);
414 }
415 }
416
417 static void
test_slice(void)418 test_slice (void)
419 {
420 GtkBitset *set;
421 guint i;
422
423 set = gtk_bitset_new_empty ();
424
425 gtk_bitset_add_range (set, 10, 30);
426
427 gtk_bitset_splice (set, 20, 10, 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 (set, 25, 10, 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 (set);
440 }
441
442 static void
test_rectangle(void)443 test_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 (set, 8, 5, 5, 7);
452 gtk_bitset_remove_rectangle (set, 16, 3, 3, 7);
453 gtk_bitset_add_rectangle (set, 24, 1, 1, 7);
454
455 s = g_string_new ("");
456 for (i = 0; i < 7; i++)
457 {
458 for (j = 0; j < 7; j++)
459 g_string_append_printf (s, "%c ",
460 gtk_bitset_contains (set, i * 7 + j) ? '*' : ' ');
461 g_string_append (s, "\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 (s, TRUE);
473 gtk_bitset_unref (set);
474 }
475
476 static void
test_iter(void)477 test_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, set, &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, set, &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, set, 0, &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 (set, 10, 20);
510
511 ret = gtk_bitset_iter_init_first (&iter, set, &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, &value);
518 g_assert_true (ret);
519 g_assert_cmpuint (value, ==, 11);
520
521 ret = gtk_bitset_iter_next (&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, set, &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, set, 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, 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, set, 100, NULL);
541 g_assert_false (ret);
542
543 gtk_bitset_unref (set);
544 }
545
546 static void
test_splice_overflow(void)547 test_splice_overflow (void)
548 {
549 GtkBitset *set, *compare;
550
551 set = gtk_bitset_new_range (3, 1);
552 gtk_bitset_splice (set, 0, 0, 13);
553
554 compare = gtk_bitset_new_range (16, 1);
555 g_assert_true (gtk_bitset_equals (set, compare));
556
557 gtk_bitset_unref (compare);
558 gtk_bitset_unref (set);
559 }
560
561 int
main(int argc,char * argv[])562 main (int argc, char *argv[])
563 {
564 (g_test_init) (&argc, &argv, NULL);
565 setlocale (LC_ALL, "C");
566
567 g_test_add_func ("/bitset/is_empty", test_is_empty);
568 g_test_add_func ("/bitset/minimum", test_minimum);
569 g_test_add_func ("/bitset/maximum", test_maximum);
570 g_test_add_func ("/bitset/equals", test_equals);
571 g_test_add_func ("/bitset/union", test_union);
572 g_test_add_func ("/bitset/intersect", test_intersect);
573 g_test_add_func ("/bitset/difference", test_difference);
574 g_test_add_func ("/bitset/subtract", test_subtract);
575 g_test_add_func ("/bitset/shift-left", test_shift_left);
576 g_test_add_func ("/bitset/shift-right", test_shift_right);
577 g_test_add_func ("/bitset/slice", test_slice);
578 g_test_add_func ("/bitset/rectangle", test_rectangle);
579 g_test_add_func ("/bitset/iter", test_iter);
580 g_test_add_func ("/bitset/splice-overflow", test_splice_overflow);
581
582 return g_test_run ();
583 }
584