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
test_empty(hb_set_t * s)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
test_not_empty(hb_set_t * s)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
test_set_basic(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 g_assert_cmpint (hb_set_get_max (s), ==, 799);
125
126 hb_set_del_range (s, 0, 799);
127 g_assert_cmpint (hb_set_get_max (s), ==, HB_SET_VALUE_INVALID);
128
129 hb_set_destroy (s);
130 }
131
132
133 // static inline void
134 // print_set (hb_set_t *s)
135 // {
136 // hb_codepoint_t next;
137 // printf ("{");
138 // for (next = HB_SET_VALUE_INVALID; hb_set_next (s, &next); )
139 // printf ("%d, ", next);
140 // printf ("}\n");
141 // }
142
test_set_intersect_empty(void)143 static void test_set_intersect_empty (void)
144 {
145 hb_set_t* a = hb_set_create ();
146 hb_set_add (a, 3585);
147 hb_set_add (a, 21333);
148 hb_set_add (a, 24405);
149
150 hb_set_t* b = hb_set_create();
151 hb_set_add (b, 21483);
152 hb_set_add (b, 24064);
153
154 hb_set_intersect (a, b);
155 g_assert (hb_set_is_empty (a));
156
157 hb_set_destroy (a);
158 hb_set_destroy (b);
159
160
161 a = hb_set_create ();
162 hb_set_add (a, 16777216);
163
164 b = hb_set_create();
165 hb_set_add (b, 0);
166
167 hb_set_intersect (a, b);
168 g_assert (hb_set_is_empty (a));
169
170 hb_set_destroy (a);
171 hb_set_destroy (b);
172 }
173
test_set_intersect_page_reduction(void)174 static void test_set_intersect_page_reduction (void)
175 {
176 hb_set_t* a = hb_set_create ();
177 hb_set_add (a, 3585);
178 hb_set_add (a, 21333);
179 hb_set_add (a, 24405);
180
181 hb_set_t* b = hb_set_create();
182 hb_set_add (b, 3585);
183 hb_set_add (b, 24405);
184
185 hb_set_intersect(a, b);
186 g_assert (hb_set_is_equal (a, b));
187
188 hb_set_destroy (a);
189 hb_set_destroy (b);
190 }
191
test_set_union(void)192 static void test_set_union (void)
193 {
194 hb_set_t* a = hb_set_create();
195 hb_set_add (a, 3585);
196 hb_set_add (a, 21333);
197 hb_set_add (a, 24405);
198
199 hb_set_t* b = hb_set_create();
200 hb_set_add (b, 21483);
201 hb_set_add (b, 24064);
202
203 hb_set_t* u = hb_set_create ();
204 hb_set_add (u, 3585);
205 hb_set_add (u, 21333);
206 hb_set_add (u, 21483);
207 hb_set_add (u, 24064);
208 hb_set_add (u, 24405);
209
210 hb_set_union(b, a);
211 g_assert (hb_set_is_equal (u, b));
212
213 hb_set_destroy (a);
214 hb_set_destroy (b);
215 hb_set_destroy (u);
216 }
217
218 static void
test_set_algebra(void)219 test_set_algebra (void)
220 {
221 hb_set_t *s = hb_set_create ();
222 hb_set_t *o = hb_set_create ();
223 hb_set_t *o2 = hb_set_create ();
224
225 hb_set_add (o, 13);
226 hb_set_add (o, 19);
227
228 hb_set_add (o2, 0x660E);
229
230 test_empty (s);
231 g_assert (!hb_set_is_equal (s, o));
232 g_assert (hb_set_is_subset (s, o));
233 g_assert (!hb_set_is_subset (o, s));
234 hb_set_set (s, o);
235 g_assert (hb_set_is_equal (s, o));
236 g_assert (hb_set_is_subset (s, o));
237 g_assert (hb_set_is_subset (o, s));
238 test_not_empty (s);
239 g_assert_cmpint (hb_set_get_population (s), ==, 2);
240
241 hb_set_clear (s);
242 test_empty (s);
243 hb_set_add (s, 10);
244 g_assert_cmpint (hb_set_get_population (s), ==, 1);
245 hb_set_union (s, o);
246 g_assert_cmpint (hb_set_get_population (s), ==, 3);
247 g_assert (hb_set_has (s, 10));
248 g_assert (hb_set_has (s, 13));
249
250 hb_set_clear (s);
251 test_empty (s);
252 g_assert_cmpint (hb_set_get_population (s), ==, 0);
253 hb_set_union (s, o2);
254 g_assert_cmpint (hb_set_get_population (s), ==, 1);
255 g_assert (hb_set_has (s, 0x660E));
256
257 hb_set_clear (s);
258 test_empty (s);
259 hb_set_add_range (s, 10, 17);
260 g_assert (!hb_set_is_equal (s, o));
261 hb_set_intersect (s, o);
262 g_assert (!hb_set_is_equal (s, o));
263 test_not_empty (s);
264 g_assert_cmpint (hb_set_get_population (s), ==, 1);
265 g_assert (!hb_set_has (s, 10));
266 g_assert (hb_set_has (s, 13));
267
268 hb_set_clear (s);
269 test_empty (s);
270 hb_set_add_range (s, 10, 17);
271 g_assert (!hb_set_is_equal (s, o));
272 hb_set_subtract (s, o);
273 g_assert (!hb_set_is_equal (s, o));
274 test_not_empty (s);
275 g_assert_cmpint (hb_set_get_population (s), ==, 7);
276 g_assert (hb_set_has (s, 12));
277 g_assert (!hb_set_has (s, 13));
278 g_assert (!hb_set_has (s, 19));
279
280 hb_set_clear (s);
281 test_empty (s);
282 hb_set_add_range (s, 10, 17);
283 g_assert (!hb_set_is_equal (s, o));
284 hb_set_symmetric_difference (s, o);
285 g_assert (!hb_set_is_equal (s, o));
286 test_not_empty (s);
287 g_assert_cmpint (hb_set_get_population (s), ==, 8);
288 g_assert (hb_set_has (s, 12));
289 g_assert (!hb_set_has (s, 13));
290 g_assert (hb_set_has (s, 19));
291
292 /* https://github.com/harfbuzz/harfbuzz/issues/579 */
293 hb_set_clear (s);
294 test_empty (s);
295 hb_set_add_range (s, 886, 895);
296 hb_set_add (s, 1024);
297 hb_set_add (s, 1152);
298 hb_set_clear (o);
299 test_empty (o);
300 hb_set_add (o, 889);
301 hb_set_add (o, 1024);
302 g_assert (!hb_set_is_equal (s, o));
303 hb_set_intersect (o, s);
304 test_not_empty (o);
305 g_assert (!hb_set_is_equal (s, o));
306 g_assert_cmpint (hb_set_get_population (o), ==, 2);
307 g_assert (hb_set_has (o, 889));
308 g_assert (hb_set_has (o, 1024));
309 hb_set_clear (o);
310 test_empty (o);
311 hb_set_add_range (o, 887, 889);
312 hb_set_add (o, 1121);
313 g_assert (!hb_set_is_equal (s, o));
314 hb_set_intersect (o, s);
315 test_not_empty (o);
316 g_assert (!hb_set_is_equal (s, o));
317 g_assert_cmpint (hb_set_get_population (o), ==, 3);
318 g_assert (hb_set_has (o, 887));
319 g_assert (hb_set_has (o, 888));
320 g_assert (hb_set_has (o, 889));
321
322 hb_set_clear (s);
323 test_empty (s);
324 hb_set_add_range (s, 886, 895);
325 hb_set_add (s, 1014);
326 hb_set_add (s, 1017);
327 hb_set_add (s, 1024);
328 hb_set_add (s, 1113);
329 hb_set_add (s, 1121);
330 g_assert_cmpint (hb_set_get_population (s), ==, 15);
331
332 hb_set_clear (o);
333 test_empty (o);
334 hb_set_add (o, 889);
335 g_assert_cmpint (hb_set_get_population (o), ==, 1);
336 hb_set_intersect (o, s);
337 g_assert_cmpint (hb_set_get_population (o), ==, 1);
338 g_assert (hb_set_has (o, 889));
339
340 hb_set_add (o, 511);
341 g_assert_cmpint (hb_set_get_population (o), ==, 2);
342 hb_set_intersect (o, s);
343 g_assert_cmpint (hb_set_get_population (o), ==, 1);
344 g_assert (hb_set_has (o, 889));
345
346 hb_set_destroy (s);
347 hb_set_destroy (o);
348 hb_set_destroy (o2);
349 }
350
351 static void
test_set_iter(void)352 test_set_iter (void)
353 {
354 hb_codepoint_t next, first, last;
355 hb_set_t *s = hb_set_create ();
356
357 hb_set_add (s, 13);
358 hb_set_add_range (s, 6, 6);
359 hb_set_add_range (s, 10, 15);
360 hb_set_add (s, 1100);
361 hb_set_add (s, 1200);
362 hb_set_add (s, 20005);
363
364 test_not_empty (s);
365
366 next = HB_SET_VALUE_INVALID;
367 g_assert (hb_set_next (s, &next));
368 g_assert_cmpint (next, ==, 6);
369 g_assert (hb_set_next (s, &next));
370 g_assert_cmpint (next, ==, 10);
371 g_assert (hb_set_next (s, &next));
372 g_assert (hb_set_next (s, &next));
373 g_assert (hb_set_next (s, &next));
374 g_assert_cmpint (next, ==, 13);
375 g_assert (hb_set_next (s, &next));
376 g_assert (hb_set_next (s, &next));
377 g_assert_cmpint (next, ==, 15);
378 g_assert (hb_set_next (s, &next));
379 g_assert_cmpint (next, ==, 1100);
380 g_assert (hb_set_next (s, &next));
381 g_assert_cmpint (next, ==, 1200);
382 g_assert (hb_set_next (s, &next));
383 g_assert_cmpint (next, ==, 20005);
384 g_assert (!hb_set_next (s, &next));
385 g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
386
387 next = HB_SET_VALUE_INVALID;
388 g_assert (hb_set_previous (s, &next));
389 g_assert_cmpint (next, ==, 20005);
390 g_assert (hb_set_previous (s, &next));
391 g_assert_cmpint (next, ==, 1200);
392 g_assert (hb_set_previous (s, &next));
393 g_assert_cmpint (next, ==, 1100);
394 g_assert (hb_set_previous (s, &next));
395 g_assert_cmpint (next, ==, 15);
396 g_assert (hb_set_previous (s, &next));
397 g_assert (hb_set_previous (s, &next));
398 g_assert_cmpint (next, ==, 13);
399 g_assert (hb_set_previous (s, &next));
400 g_assert (hb_set_previous (s, &next));
401 g_assert (hb_set_previous (s, &next));
402 g_assert_cmpint (next, ==, 10);
403 g_assert (hb_set_previous (s, &next));
404 g_assert_cmpint (next, ==, 6);
405 g_assert (!hb_set_previous (s, &next));
406 g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
407
408 first = last = HB_SET_VALUE_INVALID;
409 g_assert (hb_set_next_range (s, &first, &last));
410 g_assert_cmpint (first, ==, 6);
411 g_assert_cmpint (last, ==, 6);
412 g_assert (hb_set_next_range (s, &first, &last));
413 g_assert_cmpint (first, ==, 10);
414 g_assert_cmpint (last, ==, 15);
415 g_assert (hb_set_next_range (s, &first, &last));
416 g_assert_cmpint (first, ==, 1100);
417 g_assert_cmpint (last, ==, 1100);
418 g_assert (hb_set_next_range (s, &first, &last));
419 g_assert_cmpint (first, ==, 1200);
420 g_assert_cmpint (last, ==, 1200);
421 g_assert (hb_set_next_range (s, &first, &last));
422 g_assert_cmpint (first, ==, 20005);
423 g_assert_cmpint (last, ==, 20005);
424 g_assert (!hb_set_next_range (s, &first, &last));
425 g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
426 g_assert_cmpint (last, ==, HB_SET_VALUE_INVALID);
427
428 first = last = HB_SET_VALUE_INVALID;
429 g_assert (hb_set_previous_range (s, &first, &last));
430 g_assert_cmpint (first, ==, 20005);
431 g_assert_cmpint (last, ==, 20005);
432 g_assert (hb_set_previous_range (s, &first, &last));
433 g_assert_cmpint (first, ==, 1200);
434 g_assert_cmpint (last, ==, 1200);
435 g_assert (hb_set_previous_range (s, &first, &last));
436 g_assert_cmpint (first, ==, 1100);
437 g_assert_cmpint (last, ==, 1100);
438 g_assert (hb_set_previous_range (s, &first, &last));
439 g_assert_cmpint (first, ==, 10);
440 g_assert_cmpint (last, ==, 15);
441 g_assert (hb_set_previous_range (s, &first, &last));
442 g_assert_cmpint (first, ==, 6);
443 g_assert_cmpint (last, ==, 6);
444 g_assert (!hb_set_previous_range (s, &first, &last));
445 g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
446 g_assert_cmpint (last, ==, HB_SET_VALUE_INVALID);
447
448 hb_set_destroy (s);
449 }
450
451 static void
test_set_empty(void)452 test_set_empty (void)
453 {
454 hb_set_t *b = hb_set_get_empty ();
455
456 g_assert (hb_set_get_empty ());
457 g_assert (hb_set_get_empty () == b);
458
459 g_assert (!hb_set_allocation_successful (b));
460
461 test_empty (b);
462
463 hb_set_add (b, 13);
464
465 test_empty (b);
466
467 g_assert (!hb_set_allocation_successful (b));
468
469 hb_set_clear (b);
470
471 test_empty (b);
472
473 g_assert (!hb_set_allocation_successful (b));
474
475 hb_set_destroy (b);
476 }
477
478 static void
test_set_delrange(void)479 test_set_delrange (void)
480 {
481 const unsigned P = 512; /* Page size. */
482 struct { unsigned b, e; } ranges[] = {
483 { 35, P-15 }, /* From page middle thru middle. */
484 { P, P+100 }, /* From page start thru middle. */
485 { P+300, P*2-1 }, /* From page middle thru end. */
486 { P*3, P*4+100 }, /* From page start thru next page middle. */
487 { P*4+300, P*6-1 }, /* From page middle thru next page end. */
488 { P*6+200,P*8+100 }, /* From page middle covering one page thru page middle. */
489 { P*9, P*10+105 }, /* From page start covering one page thru page middle. */
490 { P*10+305, P*12-1 }, /* From page middle covering one page thru page end. */
491 { P*13, P*15-1 }, /* From page start covering two pages thru page end. */
492 { P*15+100, P*18+100 } /* From page middle covering two pages thru page middle. */
493 };
494 unsigned n = sizeof (ranges) / sizeof(ranges[0]);
495
496 hb_set_t *s = hb_set_create ();
497
498 test_empty (s);
499 for (unsigned int g = 0; g < ranges[n - 1].e + P; g += 2)
500 hb_set_add (s, g);
501
502 hb_set_add (s, P*2-1);
503 hb_set_add (s, P*6-1);
504 hb_set_add (s, P*12-1);
505 hb_set_add (s, P*15-1);
506
507 for (unsigned i = 0; i < n; i++)
508 hb_set_del_range (s, ranges[i].b, ranges[i].e);
509
510 hb_set_del_range (s, P*13+5, P*15-10); /* Deletion from deleted pages. */
511
512 for (unsigned i = 0; i < n; i++)
513 {
514 unsigned b = ranges[i].b;
515 unsigned e = ranges[i].e;
516 g_assert (hb_set_has (s, (b-2)&~1));
517 while (b <= e)
518 g_assert (!hb_set_has (s, b++));
519 g_assert (hb_set_has (s, (e+2)&~1));
520 }
521
522 hb_set_destroy (s);
523 }
524
525 int
main(int argc,char ** argv)526 main (int argc, char **argv)
527 {
528 hb_test_init (&argc, &argv);
529
530 hb_test_add (test_set_basic);
531 hb_test_add (test_set_algebra);
532 hb_test_add (test_set_iter);
533 hb_test_add (test_set_empty);
534 hb_test_add (test_set_delrange);
535
536 hb_test_add (test_set_intersect_empty);
537 hb_test_add (test_set_intersect_page_reduction);
538 hb_test_add (test_set_union);
539
540 return hb_test_run();
541 }
542