test/api/test-set.c

   1 /*
   2  * Copyright © 2013  Google, Inc.
   3  *
   4  *  This is part of HarfBuzz, a text shaping library.
   5  *
   6  * Permission is hereby granted, without written agreement and without
   7  * license or royalty fees, to use, copy, modify, and distribute this
   8  * software and its documentation for any purpose, provided that the
   9  * above copyright notice and the following two paragraphs appear in
  10  * all copies of this software.
  11  *
  12  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  13  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  14  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  15  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  16  * DAMAGE.
  17  *
  18  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  19  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  20  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  21  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  22  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  23  *
  24  * Google Author(s): Behdad Esfahbod
  25  */
  26
  27 #include "hb-test.h"
  28
  29 /* Unit tests for hb-set.h */
  30
  31
  32 static void
  33 test_empty (hb_set_t *s)
  34 {
  35   hb_codepoint_t next;
  36   g_assert_cmpint (hb_set_get_population (s), ==, 0);
  37   g_assert_cmpint (hb_set_get_min (s), ==, HB_SET_VALUE_INVALID);
  38   g_assert_cmpint (hb_set_get_max (s), ==, HB_SET_VALUE_INVALID);
  39   g_assert (!hb_set_has (s, 13));
  40   next = 53043;
  41   g_assert (!hb_set_next (s, &next));
  42   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
  43   next = 07734;
  44   g_assert (!hb_set_previous (s, &next));
  45   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
  46   g_assert (hb_set_is_empty (s));
  47 }
  48
  49 static void
  50 test_not_empty (hb_set_t *s)
  51 {
  52   hb_codepoint_t next;
  53   g_assert_cmpint (hb_set_get_population (s), !=, 0);
  54   g_assert_cmpint (hb_set_get_min (s), !=, HB_SET_VALUE_INVALID);
  55   g_assert_cmpint (hb_set_get_max (s), !=, HB_SET_VALUE_INVALID);
  56   next = HB_SET_VALUE_INVALID;
  57   g_assert (hb_set_next (s, &next));
  58   g_assert_cmpint (next, !=, HB_SET_VALUE_INVALID);
  59   next = HB_SET_VALUE_INVALID;
  60   g_assert (hb_set_previous (s, &next));
  61   g_assert_cmpint (next, !=, HB_SET_VALUE_INVALID);
  62 }
  63
  64 static void
  65 test_set_basic (void)
  66 {
  67   hb_set_t *s = hb_set_create ();
  68
  69   test_empty (s);
  70   hb_set_add (s, 13);
  71   test_not_empty (s);
  72
  73   hb_set_clear (s);
  74   test_empty (s);
  75
  76   hb_set_add (s, 33000);
  77   test_not_empty (s);
  78   hb_set_clear (s);
  79
  80   hb_set_add_range (s, 10, 29);
  81   test_not_empty (s);
  82   g_assert (hb_set_has (s, 13));
  83   g_assert_cmpint (hb_set_get_population (s), ==, 20);
  84   g_assert_cmpint (hb_set_get_min (s), ==, 10);
  85   g_assert_cmpint (hb_set_get_max (s), ==, 29);
  86
  87   test_not_empty (s);
  88   g_assert (hb_set_has (s, 13));
  89   g_assert_cmpint (hb_set_get_population (s), ==, 20);
  90   g_assert_cmpint (hb_set_get_min (s), ==, 10);
  91   g_assert_cmpint (hb_set_get_max (s), ==, 29);
  92
  93   hb_set_del_range (s, 10, 18);
  94   test_not_empty (s);
  95   g_assert (!hb_set_has (s, 13));
  96
  97   hb_set_add_range (s, 200, 800);
  98   test_not_empty (s);
  99   g_assert (!hb_set_has (s, 100));
 100   g_assert (!hb_set_has (s, 199));
 101   g_assert (hb_set_has (s, 200));
 102   g_assert (hb_set_has (s, 201));
 103   g_assert (hb_set_has (s, 243));
 104   g_assert (hb_set_has (s, 254));
 105   g_assert (hb_set_has (s, 255));
 106   g_assert (hb_set_has (s, 256));
 107   g_assert (hb_set_has (s, 257));
 108   g_assert (hb_set_has (s, 511));
 109   g_assert (hb_set_has (s, 512));
 110   g_assert (hb_set_has (s, 600));
 111   g_assert (hb_set_has (s, 767));
 112   g_assert (hb_set_has (s, 768));
 113   g_assert (hb_set_has (s, 769));
 114   g_assert (hb_set_has (s, 782));
 115   g_assert (hb_set_has (s, 798));
 116   g_assert (hb_set_has (s, 799));
 117   g_assert (hb_set_has (s, 800));
 118   g_assert (!hb_set_has (s, 801));
 119   g_assert (!hb_set_has (s, 802));
 120
 121   hb_set_del (s, 800);
 122   g_assert (!hb_set_has (s, 800));
 123
 124   hb_set_destroy (s);
 125 }
 126
 127
 128 // static inline void
 129 // print_set (hb_set_t *s)
 130 // {
 131 //   hb_codepoint_t next;
 132 //   printf ("{");
 133 //   for (next = HB_SET_VALUE_INVALID; hb_set_next (s, &next); )
 134 //     printf ("%d, ", next);
 135 //   printf ("}\n");
 136 // }
 137
 138 static void test_set_intersect_empty (void)
 139 {
 140   hb_set_t* a = hb_set_create ();
 141   hb_set_add (a, 3585);
 142   hb_set_add (a, 21333);
 143   hb_set_add (a, 24405);
 144
 145   hb_set_t* b = hb_set_create();
 146   hb_set_add (b, 21483);
 147   hb_set_add (b, 24064);
 148
 149   hb_set_intersect (a, b);
 150   g_assert (hb_set_is_empty (a));
 151
 152   hb_set_destroy (a);
 153   hb_set_destroy (b);
 154
 155
 156   a = hb_set_create ();
 157   hb_set_add (a, 16777216);
 158
 159   b = hb_set_create();
 160   hb_set_add (b, 0);
 161
 162   hb_set_intersect (a, b);
 163   g_assert (hb_set_is_empty (a));
 164
 165   hb_set_destroy (a);
 166   hb_set_destroy (b);
 167 }
 168
 169 static void test_set_intersect_page_reduction (void)
 170 {
 171   hb_set_t* a = hb_set_create ();
 172   hb_set_add (a, 3585);
 173   hb_set_add (a, 21333);
 174   hb_set_add (a, 24405);
 175
 176   hb_set_t* b = hb_set_create();
 177   hb_set_add (b, 3585);
 178   hb_set_add (b, 24405);
 179
 180   hb_set_intersect(a, b);
 181   g_assert (hb_set_is_equal (a, b));
 182
 183   hb_set_destroy (a);
 184   hb_set_destroy (b);
 185 }
 186
 187 static void test_set_union (void)
 188 {
 189   hb_set_t* a = hb_set_create();
 190   hb_set_add (a, 3585);
 191   hb_set_add (a, 21333);
 192   hb_set_add (a, 24405);
 193
 194   hb_set_t* b = hb_set_create();
 195   hb_set_add (b, 21483);
 196   hb_set_add (b, 24064);
 197
 198   hb_set_t* u = hb_set_create ();
 199   hb_set_add (u, 3585);
 200   hb_set_add (u, 21333);
 201   hb_set_add (u, 21483);
 202   hb_set_add (u, 24064);
 203   hb_set_add (u, 24405);
 204
 205   hb_set_union(b, a);
 206   g_assert (hb_set_is_equal (u, b));
 207
 208   hb_set_destroy (a);
 209   hb_set_destroy (b);
 210   hb_set_destroy (u);
 211 }
 212
 213 static void
 214 test_set_algebra (void)
 215 {
 216   hb_set_t *s = hb_set_create ();
 217   hb_set_t *o = hb_set_create ();
 218   hb_set_t *o2 = hb_set_create ();
 219
 220   hb_set_add (o, 13);
 221   hb_set_add (o, 19);
 222
 223   hb_set_add (o2, 0x660E);
 224
 225   test_empty (s);
 226   g_assert (!hb_set_is_equal (s, o));
 227   g_assert (hb_set_is_subset (s, o));
 228   g_assert (!hb_set_is_subset (o, s));
 229   hb_set_set (s, o);
 230   g_assert (hb_set_is_equal (s, o));
 231   g_assert (hb_set_is_subset (s, o));
 232   g_assert (hb_set_is_subset (o, s));
 233   test_not_empty (s);
 234   g_assert_cmpint (hb_set_get_population (s), ==, 2);
 235
 236   hb_set_clear (s);
 237   test_empty (s);
 238   hb_set_add (s, 10);
 239   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 240   hb_set_union (s, o);
 241   g_assert_cmpint (hb_set_get_population (s), ==, 3);
 242   g_assert (hb_set_has (s, 10));
 243   g_assert (hb_set_has (s, 13));
 244
 245   hb_set_clear (s);
 246   test_empty (s);
 247   g_assert_cmpint (hb_set_get_population (s), ==, 0);
 248   hb_set_union (s, o2);
 249   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 250   g_assert (hb_set_has (s, 0x660E));
 251
 252   hb_set_clear (s);
 253   test_empty (s);
 254   hb_set_add_range (s, 10, 17);
 255   g_assert (!hb_set_is_equal (s, o));
 256   hb_set_intersect (s, o);
 257   g_assert (!hb_set_is_equal (s, o));
 258   test_not_empty (s);
 259   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 260   g_assert (!hb_set_has (s, 10));
 261   g_assert (hb_set_has (s, 13));
 262
 263   hb_set_clear (s);
 264   test_empty (s);
 265   hb_set_add_range (s, 10, 17);
 266   g_assert (!hb_set_is_equal (s, o));
 267   hb_set_subtract (s, o);
 268   g_assert (!hb_set_is_equal (s, o));
 269   test_not_empty (s);
 270   g_assert_cmpint (hb_set_get_population (s), ==, 7);
 271   g_assert (hb_set_has (s, 12));
 272   g_assert (!hb_set_has (s, 13));
 273   g_assert (!hb_set_has (s, 19));
 274
 275   hb_set_clear (s);
 276   test_empty (s);
 277   hb_set_add_range (s, 10, 17);
 278   g_assert (!hb_set_is_equal (s, o));
 279   hb_set_symmetric_difference (s, o);
 280   g_assert (!hb_set_is_equal (s, o));
 281   test_not_empty (s);
 282   g_assert_cmpint (hb_set_get_population (s), ==, 8);
 283   g_assert (hb_set_has (s, 12));
 284   g_assert (!hb_set_has (s, 13));
 285   g_assert (hb_set_has (s, 19));
 286
 287   /* https://github.com/harfbuzz/harfbuzz/issues/579 */
 288   hb_set_clear (s);
 289   test_empty (s);
 290   hb_set_add_range (s, 886, 895);
 291   hb_set_add (s, 1024);
 292   hb_set_add (s, 1152);
 293   hb_set_clear (o);
 294   test_empty (o);
 295   hb_set_add (o, 889);
 296   hb_set_add (o, 1024);
 297   g_assert (!hb_set_is_equal (s, o));
 298   hb_set_intersect (o, s);
 299   test_not_empty (o);
 300   g_assert (!hb_set_is_equal (s, o));
 301   g_assert_cmpint (hb_set_get_population (o), ==, 2);
 302   g_assert (hb_set_has (o, 889));
 303   g_assert (hb_set_has (o, 1024));
 304   hb_set_clear (o);
 305   test_empty (o);
 306   hb_set_add_range (o, 887, 889);
 307   hb_set_add (o, 1121);
 308   g_assert (!hb_set_is_equal (s, o));
 309   hb_set_intersect (o, s);
 310   test_not_empty (o);
 311   g_assert (!hb_set_is_equal (s, o));
 312   g_assert_cmpint (hb_set_get_population (o), ==, 3);
 313   g_assert (hb_set_has (o, 887));
 314   g_assert (hb_set_has (o, 888));
 315   g_assert (hb_set_has (o, 889));
 316
 317   hb_set_clear (s);
 318   test_empty (s);
 319   hb_set_add_range (s, 886, 895);
 320   hb_set_add (s, 1014);
 321   hb_set_add (s, 1017);
 322   hb_set_add (s, 1024);
 323   hb_set_add (s, 1113);
 324   hb_set_add (s, 1121);
 325   g_assert_cmpint (hb_set_get_population (s), ==, 15);
 326
 327   hb_set_clear (o);
 328   test_empty (o);
 329   hb_set_add (o, 889);
 330   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 331   hb_set_intersect (o, s);
 332   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 333   g_assert (hb_set_has (o, 889));
 334
 335   hb_set_add (o, 511);
 336   g_assert_cmpint (hb_set_get_population (o), ==, 2);
 337   hb_set_intersect (o, s);
 338   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 339   g_assert (hb_set_has (o, 889));
 340
 341   hb_set_destroy (s);
 342   hb_set_destroy (o);
 343   hb_set_destroy (o2);
 344 }
 345
 346 static void
 347 test_set_iter (void)
 348 {
 349   hb_codepoint_t next, first, last;
 350   hb_set_t *s = hb_set_create ();
 351
 352   hb_set_add (s, 13);
 353   hb_set_add_range (s, 6, 6);
 354   hb_set_add_range (s, 10, 15);
 355   hb_set_add (s, 1100);
 356   hb_set_add (s, 1200);
 357   hb_set_add (s, 20005);
 358
 359   test_not_empty (s);
 360
 361   next = HB_SET_VALUE_INVALID;
 362   g_assert (hb_set_next (s, &next));
 363   g_assert_cmpint (next, ==, 6);
 364   g_assert (hb_set_next (s, &next));
 365   g_assert_cmpint (next, ==, 10);
 366   g_assert (hb_set_next (s, &next));
 367   g_assert (hb_set_next (s, &next));
 368   g_assert (hb_set_next (s, &next));
 369   g_assert_cmpint (next, ==, 13);
 370   g_assert (hb_set_next (s, &next));
 371   g_assert (hb_set_next (s, &next));
 372   g_assert_cmpint (next, ==, 15);
 373   g_assert (hb_set_next (s, &next));
 374   g_assert_cmpint (next, ==, 1100);
 375   g_assert (hb_set_next (s, &next));
 376   g_assert_cmpint (next, ==, 1200);
 377   g_assert (hb_set_next (s, &next));
 378   g_assert_cmpint (next, ==, 20005);
 379   g_assert (!hb_set_next (s, &next));
 380   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
 381
 382   next = HB_SET_VALUE_INVALID;
 383   g_assert (hb_set_previous (s, &next));
 384   g_assert_cmpint (next, ==, 20005);
 385   g_assert (hb_set_previous (s, &next));
 386   g_assert_cmpint (next, ==, 1200);
 387   g_assert (hb_set_previous (s, &next));
 388   g_assert_cmpint (next, ==, 1100);
 389   g_assert (hb_set_previous (s, &next));
 390   g_assert_cmpint (next, ==, 15);
 391   g_assert (hb_set_previous (s, &next));
 392   g_assert (hb_set_previous (s, &next));
 393   g_assert_cmpint (next, ==, 13);
 394   g_assert (hb_set_previous (s, &next));
 395   g_assert (hb_set_previous (s, &next));
 396   g_assert (hb_set_previous (s, &next));
 397   g_assert_cmpint (next, ==, 10);
 398   g_assert (hb_set_previous (s, &next));
 399   g_assert_cmpint (next, ==, 6);
 400   g_assert (!hb_set_previous (s, &next));
 401   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
 402
 403   first = last = HB_SET_VALUE_INVALID;
 404   g_assert (hb_set_next_range (s, &first, &last));
 405   g_assert_cmpint (first, ==, 6);
 406   g_assert_cmpint (last,  ==, 6);
 407   g_assert (hb_set_next_range (s, &first, &last));
 408   g_assert_cmpint (first, ==, 10);
 409   g_assert_cmpint (last,  ==, 15);
 410   g_assert (hb_set_next_range (s, &first, &last));
 411   g_assert_cmpint (first, ==, 1100);
 412   g_assert_cmpint (last,  ==, 1100);
 413   g_assert (hb_set_next_range (s, &first, &last));
 414   g_assert_cmpint (first, ==, 1200);
 415   g_assert_cmpint (last,  ==, 1200);
 416   g_assert (hb_set_next_range (s, &first, &last));
 417   g_assert_cmpint (first, ==, 20005);
 418   g_assert_cmpint (last,  ==, 20005);
 419   g_assert (!hb_set_next_range (s, &first, &last));
 420   g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
 421   g_assert_cmpint (last,  ==, HB_SET_VALUE_INVALID);
 422
 423   first = last = HB_SET_VALUE_INVALID;
 424   g_assert (hb_set_previous_range (s, &first, &last));
 425   g_assert_cmpint (first, ==, 20005);
 426   g_assert_cmpint (last,  ==, 20005);
 427   g_assert (hb_set_previous_range (s, &first, &last));
 428   g_assert_cmpint (first, ==, 1200);
 429   g_assert_cmpint (last,  ==, 1200);
 430   g_assert (hb_set_previous_range (s, &first, &last));
 431   g_assert_cmpint (first, ==, 1100);
 432   g_assert_cmpint (last,  ==, 1100);
 433   g_assert (hb_set_previous_range (s, &first, &last));
 434   g_assert_cmpint (first, ==, 10);
 435   g_assert_cmpint (last,  ==, 15);
 436   g_assert (hb_set_previous_range (s, &first, &last));
 437   g_assert_cmpint (first, ==, 6);
 438   g_assert_cmpint (last,  ==, 6);
 439   g_assert (!hb_set_previous_range (s, &first, &last));
 440   g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
 441   g_assert_cmpint (last,  ==, HB_SET_VALUE_INVALID);
 442
 443   hb_set_destroy (s);
 444 }
 445
 446 static void
 447 test_set_empty (void)
 448 {
 449   hb_set_t *b = hb_set_get_empty ();
 450
 451   g_assert (hb_set_get_empty ());
 452   g_assert (hb_set_get_empty () == b);
 453
 454   g_assert (!hb_set_allocation_successful (b));
 455
 456   test_empty (b);
 457
 458   hb_set_add (b, 13);
 459
 460   test_empty (b);
 461
 462   g_assert (!hb_set_allocation_successful (b));
 463
 464   hb_set_clear (b);
 465
 466   test_empty (b);
 467
 468   g_assert (!hb_set_allocation_successful (b));
 469
 470   hb_set_destroy (b);
 471 }
 472
 473 static void
 474 test_set_delrange (void)
 475 {
 476   const unsigned P = 512;       /* Page size. */
 477   struct { unsigned b, e; } ranges[] = {
 478     { 35, P-15 },               /* From page middle thru middle. */
 479     { P, P+100 },               /* From page start thru middle. */
 480     { P+300, P*2-1 },           /* From page middle thru end. */
 481     { P*3, P*4+100 },           /* From page start thru next page middle. */
 482     { P*4+300, P*6-1 },         /* From page middle thru next page end. */
 483     { P*6+200,P*8+100 },        /* From page middle covering one page thru page middle. */
 484     { P*9, P*10+105 },          /* From page start covering one page thru page middle. */
 485     { P*10+305, P*12-1 },       /* From page middle covering one page thru page end. */
 486     { P*13, P*15-1 },           /* From page start covering two pages thru page end. */
 487     { P*15+100, P*18+100 }      /* From page middle covering two pages thru page middle. */
 488   };
 489   unsigned n = sizeof (ranges) / sizeof(ranges[0]);
 490
 491   hb_set_t *s = hb_set_create ();
 492
 493   test_empty (s);
 494   for (unsigned int g = 0; g < ranges[n - 1].e + P; g += 2)
 495     hb_set_add (s, g);
 496
 497   hb_set_add (s, P*2-1);
 498   hb_set_add (s, P*6-1);
 499   hb_set_add (s, P*12-1);
 500   hb_set_add (s, P*15-1);
 501
 502   for (unsigned i = 0; i < n; i++)
 503     hb_set_del_range (s, ranges[i].b, ranges[i].e);
 504
 505   hb_set_del_range (s, P*13+5, P*15-10);        /* Deletion from deleted pages. */
 506
 507   for (unsigned i = 0; i < n; i++)
 508   {
 509     unsigned b = ranges[i].b;
 510     unsigned e = ranges[i].e;
 511     g_assert (hb_set_has (s, (b-2)&~1));
 512     while (b <= e)
 513       g_assert (!hb_set_has (s, b++));
 514     g_assert (hb_set_has (s, (e+2)&~1));
 515   }
 516
 517   hb_set_destroy (s);
 518 }
 519
 520 int
 521 main (int argc, char **argv)
 522 {
 523   hb_test_init (&argc, &argv);
 524
 525   hb_test_add (test_set_basic);
 526   hb_test_add (test_set_algebra);
 527   hb_test_add (test_set_iter);
 528   hb_test_add (test_set_empty);
 529   hb_test_add (test_set_delrange);
 530
 531   hb_test_add (test_set_intersect_empty);
 532   hb_test_add (test_set_intersect_page_reduction);
 533   hb_test_add (test_set_union);
 534
 535   return hb_test_run();
 536 }