Pileus Git - ~andy/gtk/blob - gtk/tests/bitmask.c

   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 "../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 #define SWAP(_a, _b) G_STMT_START{ \
 284   guint _tmp = _a; \
 285   _a = _b; \
 286   _b = _tmp; \
 287 }G_STMT_END
 288
 289 static void
 290 test_invert_range (void)
 291 {
 292   GtkBitmask *left, *right, *intersection, *expected;
 293   guint run;
 294   guint left_start, left_end, right_start, right_end, start, end;
 295
 296   for (run = 0; run < N_RUNS; run++)
 297     {
 298       left = _gtk_bitmask_new ();
 299       right = _gtk_bitmask_new ();
 300       expected = _gtk_bitmask_new ();
 301
 302       left_start = g_test_rand_int_range (0, MAX_INDEX);
 303       left_end = g_test_rand_int_range (0, MAX_INDEX);
 304       if (left_start > left_end)
 305         SWAP (left_start, left_end);
 306       right_start = g_test_rand_int_range (0, MAX_INDEX);
 307       right_end = g_test_rand_int_range (0, MAX_INDEX);
 308       if (right_start > right_end)
 309         SWAP (right_start, right_end);
 310       start = MAX (left_start, right_start);
 311       end = MIN (left_end, right_end);
 312
 313       if (left_start != left_end)
 314         left = _gtk_bitmask_invert_range (left, left_start, left_end);
 315       if (right_start != right_end)
 316         right = _gtk_bitmask_invert_range (right, right_start, right_end);
 317       if (start < end)
 318         expected = _gtk_bitmask_invert_range (expected, start, end);
 319
 320       intersection = _gtk_bitmask_copy (left);
 321       intersection = _gtk_bitmask_intersect (intersection, right);
 322
 323       assert_cmpmasks (intersection, expected);
 324
 325       if (start < end)
 326         expected = _gtk_bitmask_invert_range (expected, start, end);
 327
 328       g_assert_cmpint (_gtk_bitmask_is_empty (expected), ==, TRUE);
 329
 330       _gtk_bitmask_free (left);
 331       _gtk_bitmask_free (right);
 332       _gtk_bitmask_free (intersection);
 333       _gtk_bitmask_free (expected);
 334     }
 335 }
 336
 337 /* SETUP & RUNNING */
 338
 339 static void
 340 create_masks (void)
 341 {
 342   guint i;
 343
 344   for (i = 0; i < G_N_ELEMENTS (tests); i++)
 345     masks[i] = gtk_bitmask_new_parse (tests[i]);
 346 }
 347
 348 static void
 349 free_masks (void)
 350 {
 351   guint i;
 352
 353   for (i = 0; i < G_N_ELEMENTS (tests); i++)
 354     {
 355       _gtk_bitmask_free (masks[i]);
 356       masks[i] = NULL;
 357     }
 358 }
 359
 360 int
 361 main (int argc, char *argv[])
 362 {
 363   int result;
 364
 365   g_test_init (&argc, &argv, NULL);
 366   setlocale (LC_ALL, "C");
 367   g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
 368
 369   create_masks ();
 370
 371   g_test_add_func ("/bitmask/to_string", test_to_string);
 372   g_test_add_func ("/bitmask/is_empty", test_is_empty);
 373   g_test_add_func ("/bitmask/equals", test_equals);
 374   g_test_add_func ("/bitmask/set", test_set);
 375   g_test_add_func ("/bitmask/union", test_union);
 376   g_test_add_func ("/bitmask/intersect", test_intersect);
 377   g_test_add_func ("/bitmask/intersect_hardcoded", test_intersect_hardcoded);
 378   g_test_add_func ("/bitmask/invert_range", test_invert_range);
 379
 380   result = g_test_run ();
 381
 382   free_masks ();
 383
 384   return result;
 385 }