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_subsets(void)219 test_set_subsets (void)
220 {
221 hb_set_t *s = hb_set_create ();
222 hb_set_t *l = hb_set_create ();
223
224 hb_set_add (l, 0x0FFFF);
225 hb_set_add (s, 0x1FFFF);
226 g_assert (!hb_set_is_subset (s, l));
227 hb_set_clear (s);
228
229 hb_set_add (s, 0x0FFF0);
230 g_assert (!hb_set_is_subset (s, l));
231 hb_set_clear (s);
232
233 hb_set_add (s, 0x0AFFF);
234 g_assert (!hb_set_is_subset (s, l));
235
236 hb_set_clear (s);
237 g_assert (hb_set_is_subset (s, l));
238
239 hb_set_clear (l);
240 g_assert (hb_set_is_subset (s, l));
241
242 hb_set_add (s, 0x1FFFF);
243 g_assert (!hb_set_is_subset (s, l));
244 hb_set_clear (s);
245
246 hb_set_add (s, 0xFF);
247 hb_set_add (s, 0x1FFFF);
248 hb_set_add (s, 0x2FFFF);
249
250 hb_set_add (l, 0xFF);
251 hb_set_add (l, 0x1FFFF);
252 hb_set_add (l, 0x2FFFF);
253
254 g_assert (hb_set_is_subset (s, l));
255 hb_set_del (l, 0xFF);
256 g_assert (!hb_set_is_subset (s, l));
257 hb_set_add (l, 0xFF);
258
259 hb_set_del (l, 0x2FFFF);
260 g_assert (!hb_set_is_subset (s, l));
261 hb_set_add (l, 0x2FFFF);
262
263 hb_set_del (l, 0x1FFFF);
264 g_assert (!hb_set_is_subset (s, l));
265
266 hb_set_destroy (s);
267 hb_set_destroy (l);
268 }
269
270 static void
test_set_algebra(void)271 test_set_algebra (void)
272 {
273 hb_set_t *s = hb_set_create ();
274 hb_set_t *o = hb_set_create ();
275 hb_set_t *o2 = hb_set_create ();
276
277 hb_set_add (o, 13);
278 hb_set_add (o, 19);
279
280 hb_set_add (o2, 0x660E);
281
282 test_empty (s);
283 g_assert (!hb_set_is_equal (s, o));
284 g_assert (hb_set_is_subset (s, o));
285 g_assert (!hb_set_is_subset (o, s));
286 hb_set_set (s, o);
287 g_assert (hb_set_is_equal (s, o));
288 g_assert (hb_set_is_subset (s, o));
289 g_assert (hb_set_is_subset (o, s));
290 test_not_empty (s);
291 g_assert_cmpint (hb_set_get_population (s), ==, 2);
292
293 hb_set_clear (s);
294 test_empty (s);
295 hb_set_add (s, 10);
296 g_assert_cmpint (hb_set_get_population (s), ==, 1);
297 hb_set_union (s, o);
298 g_assert_cmpint (hb_set_get_population (s), ==, 3);
299 g_assert (hb_set_has (s, 10));
300 g_assert (hb_set_has (s, 13));
301
302 hb_set_clear (s);
303 test_empty (s);
304 g_assert_cmpint (hb_set_get_population (s), ==, 0);
305 hb_set_union (s, o2);
306 g_assert_cmpint (hb_set_get_population (s), ==, 1);
307 g_assert (hb_set_has (s, 0x660E));
308
309 hb_set_clear (s);
310 test_empty (s);
311 hb_set_add_range (s, 10, 17);
312 g_assert (!hb_set_is_equal (s, o));
313 hb_set_intersect (s, o);
314 g_assert (!hb_set_is_equal (s, o));
315 test_not_empty (s);
316 g_assert_cmpint (hb_set_get_population (s), ==, 1);
317 g_assert (!hb_set_has (s, 10));
318 g_assert (hb_set_has (s, 13));
319
320 hb_set_clear (s);
321 test_empty (s);
322 hb_set_add_range (s, 10, 17);
323 g_assert (!hb_set_is_equal (s, o));
324 hb_set_subtract (s, o);
325 g_assert (!hb_set_is_equal (s, o));
326 test_not_empty (s);
327 g_assert_cmpint (hb_set_get_population (s), ==, 7);
328 g_assert (hb_set_has (s, 12));
329 g_assert (!hb_set_has (s, 13));
330 g_assert (!hb_set_has (s, 19));
331
332 hb_set_clear (s);
333 test_empty (s);
334 hb_set_add_range (s, 10, 17);
335 g_assert (!hb_set_is_equal (s, o));
336 hb_set_symmetric_difference (s, o);
337 g_assert (!hb_set_is_equal (s, o));
338 test_not_empty (s);
339 g_assert_cmpint (hb_set_get_population (s), ==, 8);
340 g_assert (hb_set_has (s, 12));
341 g_assert (!hb_set_has (s, 13));
342 g_assert (hb_set_has (s, 19));
343
344 /* https://github.com/harfbuzz/harfbuzz/issues/579 */
345 hb_set_clear (s);
346 test_empty (s);
347 hb_set_add_range (s, 886, 895);
348 hb_set_add (s, 1024);
349 hb_set_add (s, 1152);
350 hb_set_clear (o);
351 test_empty (o);
352 hb_set_add (o, 889);
353 hb_set_add (o, 1024);
354 g_assert (!hb_set_is_equal (s, o));
355 hb_set_intersect (o, s);
356 test_not_empty (o);
357 g_assert (!hb_set_is_equal (s, o));
358 g_assert_cmpint (hb_set_get_population (o), ==, 2);
359 g_assert (hb_set_has (o, 889));
360 g_assert (hb_set_has (o, 1024));
361 hb_set_clear (o);
362 test_empty (o);
363 hb_set_add_range (o, 887, 889);
364 hb_set_add (o, 1121);
365 g_assert (!hb_set_is_equal (s, o));
366 hb_set_intersect (o, s);
367 test_not_empty (o);
368 g_assert (!hb_set_is_equal (s, o));
369 g_assert_cmpint (hb_set_get_population (o), ==, 3);
370 g_assert (hb_set_has (o, 887));
371 g_assert (hb_set_has (o, 888));
372 g_assert (hb_set_has (o, 889));
373
374 hb_set_clear (s);
375 test_empty (s);
376 hb_set_add_range (s, 886, 895);
377 hb_set_add (s, 1014);
378 hb_set_add (s, 1017);
379 hb_set_add (s, 1024);
380 hb_set_add (s, 1113);
381 hb_set_add (s, 1121);
382 g_assert_cmpint (hb_set_get_population (s), ==, 15);
383
384 hb_set_clear (o);
385 test_empty (o);
386 hb_set_add (o, 889);
387 g_assert_cmpint (hb_set_get_population (o), ==, 1);
388 hb_set_intersect (o, s);
389 g_assert_cmpint (hb_set_get_population (o), ==, 1);
390 g_assert (hb_set_has (o, 889));
391
392 hb_set_add (o, 511);
393 g_assert_cmpint (hb_set_get_population (o), ==, 2);
394 hb_set_intersect (o, s);
395 g_assert_cmpint (hb_set_get_population (o), ==, 1);
396 g_assert (hb_set_has (o, 889));
397
398 hb_set_destroy (s);
399 hb_set_destroy (o);
400 hb_set_destroy (o2);
401 }
402
403 static void
test_set_iter(void)404 test_set_iter (void)
405 {
406 hb_codepoint_t next, first, last;
407 hb_set_t *s = hb_set_create ();
408
409 hb_set_add (s, 13);
410 hb_set_add_range (s, 6, 6);
411 hb_set_add_range (s, 10, 15);
412 hb_set_add (s, 1100);
413 hb_set_add (s, 1200);
414 hb_set_add (s, 20005);
415
416 test_not_empty (s);
417
418 next = HB_SET_VALUE_INVALID;
419 g_assert (hb_set_next (s, &next));
420 g_assert_cmpint (next, ==, 6);
421 g_assert (hb_set_next (s, &next));
422 g_assert_cmpint (next, ==, 10);
423 g_assert (hb_set_next (s, &next));
424 g_assert (hb_set_next (s, &next));
425 g_assert (hb_set_next (s, &next));
426 g_assert_cmpint (next, ==, 13);
427 g_assert (hb_set_next (s, &next));
428 g_assert (hb_set_next (s, &next));
429 g_assert_cmpint (next, ==, 15);
430 g_assert (hb_set_next (s, &next));
431 g_assert_cmpint (next, ==, 1100);
432 g_assert (hb_set_next (s, &next));
433 g_assert_cmpint (next, ==, 1200);
434 g_assert (hb_set_next (s, &next));
435 g_assert_cmpint (next, ==, 20005);
436 g_assert (!hb_set_next (s, &next));
437 g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
438
439 next = HB_SET_VALUE_INVALID;
440 g_assert (hb_set_previous (s, &next));
441 g_assert_cmpint (next, ==, 20005);
442 g_assert (hb_set_previous (s, &next));
443 g_assert_cmpint (next, ==, 1200);
444 g_assert (hb_set_previous (s, &next));
445 g_assert_cmpint (next, ==, 1100);
446 g_assert (hb_set_previous (s, &next));
447 g_assert_cmpint (next, ==, 15);
448 g_assert (hb_set_previous (s, &next));
449 g_assert (hb_set_previous (s, &next));
450 g_assert_cmpint (next, ==, 13);
451 g_assert (hb_set_previous (s, &next));
452 g_assert (hb_set_previous (s, &next));
453 g_assert (hb_set_previous (s, &next));
454 g_assert_cmpint (next, ==, 10);
455 g_assert (hb_set_previous (s, &next));
456 g_assert_cmpint (next, ==, 6);
457 g_assert (!hb_set_previous (s, &next));
458 g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
459
460 first = last = HB_SET_VALUE_INVALID;
461 g_assert (hb_set_next_range (s, &first, &last));
462 g_assert_cmpint (first, ==, 6);
463 g_assert_cmpint (last, ==, 6);
464 g_assert (hb_set_next_range (s, &first, &last));
465 g_assert_cmpint (first, ==, 10);
466 g_assert_cmpint (last, ==, 15);
467 g_assert (hb_set_next_range (s, &first, &last));
468 g_assert_cmpint (first, ==, 1100);
469 g_assert_cmpint (last, ==, 1100);
470 g_assert (hb_set_next_range (s, &first, &last));
471 g_assert_cmpint (first, ==, 1200);
472 g_assert_cmpint (last, ==, 1200);
473 g_assert (hb_set_next_range (s, &first, &last));
474 g_assert_cmpint (first, ==, 20005);
475 g_assert_cmpint (last, ==, 20005);
476 g_assert (!hb_set_next_range (s, &first, &last));
477 g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
478 g_assert_cmpint (last, ==, HB_SET_VALUE_INVALID);
479
480 first = last = HB_SET_VALUE_INVALID;
481 g_assert (hb_set_previous_range (s, &first, &last));
482 g_assert_cmpint (first, ==, 20005);
483 g_assert_cmpint (last, ==, 20005);
484 g_assert (hb_set_previous_range (s, &first, &last));
485 g_assert_cmpint (first, ==, 1200);
486 g_assert_cmpint (last, ==, 1200);
487 g_assert (hb_set_previous_range (s, &first, &last));
488 g_assert_cmpint (first, ==, 1100);
489 g_assert_cmpint (last, ==, 1100);
490 g_assert (hb_set_previous_range (s, &first, &last));
491 g_assert_cmpint (first, ==, 10);
492 g_assert_cmpint (last, ==, 15);
493 g_assert (hb_set_previous_range (s, &first, &last));
494 g_assert_cmpint (first, ==, 6);
495 g_assert_cmpint (last, ==, 6);
496 g_assert (!hb_set_previous_range (s, &first, &last));
497 g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
498 g_assert_cmpint (last, ==, HB_SET_VALUE_INVALID);
499
500 hb_set_destroy (s);
501 }
502
503 static void
test_set_empty(void)504 test_set_empty (void)
505 {
506 hb_set_t *b = hb_set_get_empty ();
507
508 g_assert (hb_set_get_empty ());
509 g_assert (hb_set_get_empty () == b);
510
511 g_assert (!hb_set_allocation_successful (b));
512
513 test_empty (b);
514
515 hb_set_add (b, 13);
516
517 test_empty (b);
518
519 g_assert (!hb_set_allocation_successful (b));
520
521 hb_set_clear (b);
522
523 test_empty (b);
524
525 g_assert (!hb_set_allocation_successful (b));
526
527 hb_set_destroy (b);
528 }
529
530 static void
test_set_delrange(void)531 test_set_delrange (void)
532 {
533 const unsigned P = 512; /* Page size. */
534 struct { unsigned b, e; } ranges[] = {
535 { 35, P-15 }, /* From page middle thru middle. */
536 { P, P+100 }, /* From page start thru middle. */
537 { P+300, P*2-1 }, /* From page middle thru end. */
538 { P*3, P*4+100 }, /* From page start thru next page middle. */
539 { P*4+300, P*6-1 }, /* From page middle thru next page end. */
540 { P*6+200,P*8+100 }, /* From page middle covering one page thru page middle. */
541 { P*9, P*10+105 }, /* From page start covering one page thru page middle. */
542 { P*10+305, P*12-1 }, /* From page middle covering one page thru page end. */
543 { P*13, P*15-1 }, /* From page start covering two pages thru page end. */
544 { P*15+100, P*18+100 } /* From page middle covering two pages thru page middle. */
545 };
546 unsigned n = sizeof (ranges) / sizeof(ranges[0]);
547
548 hb_set_t *s = hb_set_create ();
549
550 test_empty (s);
551 for (unsigned int g = 0; g < ranges[n - 1].e + P; g += 2)
552 hb_set_add (s, g);
553
554 hb_set_add (s, P*2-1);
555 hb_set_add (s, P*6-1);
556 hb_set_add (s, P*12-1);
557 hb_set_add (s, P*15-1);
558
559 for (unsigned i = 0; i < n; i++)
560 hb_set_del_range (s, ranges[i].b, ranges[i].e);
561
562 hb_set_del_range (s, P*13+5, P*15-10); /* Deletion from deleted pages. */
563
564 for (unsigned i = 0; i < n; i++)
565 {
566 unsigned b = ranges[i].b;
567 unsigned e = ranges[i].e;
568 g_assert (hb_set_has (s, (b-2)&~1));
569 while (b <= e)
570 g_assert (!hb_set_has (s, b++));
571 g_assert (hb_set_has (s, (e+2)&~1));
572 }
573
574 hb_set_destroy (s);
575 }
576
577 static const unsigned max_set_elements = -1;
578
579 static void
test_set_inverted_basics(void)580 test_set_inverted_basics (void)
581 {
582 // Tests:
583 // add, del, has, get_population, is_empty, get_min, get_max
584 // for inverted sets.
585 hb_set_t *s = hb_set_create ();
586 hb_set_invert (s);
587
588 g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements);
589 g_assert (hb_set_has (s, 0));
590 g_assert (hb_set_has (s, 13));
591 g_assert (hb_set_has (s, max_set_elements - 1));
592 g_assert (!hb_set_is_empty (s));
593 g_assert_cmpint (hb_set_get_min (s), ==, 0);
594 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
595
596 hb_set_del (s, 13);
597 g_assert (!hb_set_has (s, 13));
598 g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 1);
599 g_assert_cmpint (hb_set_get_min (s), ==, 0);
600 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
601
602 hb_set_add (s, 13);
603 g_assert (hb_set_has (s, 13));
604 g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements);
605
606 hb_set_del (s, 0);
607 hb_set_del (s, max_set_elements - 1);
608 g_assert (!hb_set_has (s, 0));
609 g_assert (hb_set_has (s, 13));
610 g_assert (!hb_set_has (s, max_set_elements - 1));
611 g_assert (!hb_set_is_empty (s));
612 g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 2);
613 g_assert_cmpint (hb_set_get_min (s), ==, 1);
614 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 2);
615
616 hb_set_destroy (s);
617 }
618
619 static void
test_set_inverted_ranges(void)620 test_set_inverted_ranges (void)
621 {
622 // Tests:
623 // add_range, del_range, has, get_population, is_empty, get_min, get_max
624 // for inverted sets.
625 hb_set_t *s = hb_set_create ();
626 hb_set_invert (s);
627
628 hb_set_del_range (s, 41, 4000);
629 hb_set_add_range (s, 78, 601);
630
631 g_assert (hb_set_has (s, 40));
632 g_assert (!hb_set_has (s, 41));
633 g_assert (!hb_set_has (s, 64));
634 g_assert (!hb_set_has (s, 77));
635 g_assert (hb_set_has (s, 78));
636 g_assert (hb_set_has (s, 300));
637 g_assert (hb_set_has (s, 601));
638 g_assert (!hb_set_has (s, 602));
639 g_assert (!hb_set_has (s, 3000));
640 g_assert (!hb_set_has (s, 4000));
641 g_assert (hb_set_has (s, 4001));
642
643 g_assert (!hb_set_is_empty (s));
644 g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 3436);
645 g_assert_cmpint (hb_set_get_min (s), ==, 0);
646 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
647
648 hb_set_del_range (s, 0, 37);
649 g_assert (!hb_set_has (s, 0));
650 g_assert (!hb_set_has (s, 37));
651 g_assert (hb_set_has (s, 38));
652 g_assert (!hb_set_is_empty (s));
653 g_assert_cmpint (hb_set_get_population (s), ==,
654 max_set_elements - 3436 - 38);
655 g_assert_cmpint (hb_set_get_min (s), ==, 38);
656 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
657
658 hb_set_del_range (s, max_set_elements - 13, max_set_elements - 1);
659 g_assert (!hb_set_has (s, max_set_elements - 1));
660 g_assert (!hb_set_has (s, max_set_elements - 13));
661 g_assert (hb_set_has (s, max_set_elements - 14));
662
663 g_assert (!hb_set_is_empty (s));
664 g_assert_cmpint (hb_set_get_population (s), ==,
665 max_set_elements - 3436 - 38 - 13);
666 g_assert_cmpint (hb_set_get_min (s), ==, 38);
667 g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 14);
668
669 hb_set_destroy (s);
670 }
671
672 static void
test_set_inverted_iteration_next(void)673 test_set_inverted_iteration_next (void)
674 {
675 // Tests:
676 // next, next_range
677 hb_set_t *s = hb_set_create ();
678 hb_set_invert (s);
679
680 hb_set_del_range (s, 41, 4000);
681 hb_set_add_range (s, 78, 601);
682
683 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
684 hb_codepoint_t start = 0;
685 hb_codepoint_t end = 0;
686 g_assert (hb_set_next (s, &cp));
687 g_assert_cmpint (cp, ==, 0);
688 g_assert (hb_set_next (s, &cp));
689 g_assert_cmpint (cp, ==, 1);
690
691 g_assert (hb_set_next_range (s, &start, &end));
692 g_assert_cmpint (start, ==, 1);
693 g_assert_cmpint (end, ==, 40);
694
695 start = 40;
696 end = 40;
697 g_assert (hb_set_next_range (s, &start, &end));
698 g_assert_cmpint (start, ==, 78);
699 g_assert_cmpint (end, ==, 601);
700
701 start = 40;
702 end = 57;
703 g_assert (hb_set_next_range (s, &start, &end));
704 g_assert_cmpint (start, ==, 78);
705 g_assert_cmpint (end, ==, 601);
706
707 cp = 39;
708 g_assert (hb_set_next (s, &cp));
709 g_assert_cmpint (cp, ==, 40);
710
711 g_assert (hb_set_next (s, &cp));
712 g_assert_cmpint (cp, ==, 78);
713
714 cp = 56;
715 g_assert (hb_set_next (s, &cp));
716 g_assert_cmpint (cp, ==, 78);
717
718 cp = 78;
719 g_assert (hb_set_next (s, &cp));
720 g_assert_cmpint (cp, ==, 79);
721
722 cp = 601;
723 g_assert (hb_set_next (s, &cp));
724 g_assert_cmpint (cp, ==, 4001);
725
726 cp = HB_SET_VALUE_INVALID;
727 hb_set_del (s, 0);
728 g_assert (hb_set_next (s, &cp));
729 g_assert_cmpint (cp, ==, 1);
730
731 start = 0;
732 end = 0;
733 g_assert (hb_set_next_range (s, &start, &end));
734 g_assert_cmpint (start, ==, 1);
735 g_assert_cmpint (end, ==, 40);
736
737 cp = max_set_elements - 1;
738 g_assert (!hb_set_next (s, &cp));
739 g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
740
741 start = 4000;
742 end = 4000;
743 g_assert (hb_set_next_range (s, &start, &end));
744 g_assert_cmpint (start, ==, 4001);
745 g_assert_cmpint (end, ==, max_set_elements - 1);
746
747 start = max_set_elements - 1;
748 end = max_set_elements - 1;
749 g_assert (!hb_set_next_range (s, &start, &end));
750 g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
751 g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
752
753 cp = max_set_elements - 3;
754 hb_set_del (s, max_set_elements - 1);
755 g_assert (hb_set_next (s, &cp));
756 g_assert_cmpint (cp, ==, max_set_elements - 2);
757 g_assert (!hb_set_next (s, &cp));
758 g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
759
760
761 start = max_set_elements - 2;
762 end = max_set_elements - 2;
763 g_assert (!hb_set_next_range (s, &start, &end));
764 g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
765 g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
766
767 start = max_set_elements - 3;
768 end = max_set_elements - 3;
769 g_assert (hb_set_next_range (s, &start, &end));
770 g_assert_cmpint (start, ==, max_set_elements - 2);
771 g_assert_cmpint (end, ==, max_set_elements - 2);
772
773 hb_set_destroy (s);
774 }
775
776 static void
test_set_inverted_iteration_prev(void)777 test_set_inverted_iteration_prev (void)
778 {
779 // Tests:
780 // previous, previous_range
781 hb_set_t *s = hb_set_create ();
782 hb_set_invert (s);
783
784 hb_set_del_range (s, 41, 4000);
785 hb_set_add_range (s, 78, 601);
786
787 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
788 hb_codepoint_t start = max_set_elements - 1;
789 hb_codepoint_t end = max_set_elements - 1;
790 g_assert (hb_set_previous (s, &cp));
791 g_assert_cmpint (cp, ==, max_set_elements - 1);
792 g_assert (hb_set_previous (s, &cp));
793 g_assert_cmpint (cp, ==, max_set_elements - 2);
794
795 g_assert (hb_set_previous_range (s, &start, &end));
796 g_assert_cmpint (start, ==, 4001);
797 g_assert_cmpint (end, ==, max_set_elements - 2);
798
799 start = 4001;
800 end = 4001;
801 g_assert (hb_set_previous_range (s, &start, &end));
802 g_assert_cmpint (start, ==, 78);
803 g_assert_cmpint (end, ==, 601);
804
805 start = 2500;
806 end = 3000;
807 g_assert (hb_set_previous_range (s, &start, &end));
808 g_assert_cmpint (start, ==, 78);
809 g_assert_cmpint (end, ==, 601);
810
811 cp = 4002;
812 g_assert (hb_set_previous (s, &cp));
813 g_assert_cmpint (cp, ==, 4001);
814
815 g_assert (hb_set_previous (s, &cp));
816 g_assert_cmpint (cp, ==, 601);
817
818 cp = 3500;
819 g_assert (hb_set_previous (s, &cp));
820 g_assert_cmpint (cp, ==, 601);
821
822 cp = 601;
823 g_assert (hb_set_previous (s, &cp));
824 g_assert_cmpint (cp, ==, 600);
825
826 cp = 78;
827 g_assert (hb_set_previous (s, &cp));
828 g_assert_cmpint (cp, ==, 40);
829
830 cp = HB_SET_VALUE_INVALID;
831 hb_set_del (s, max_set_elements - 1);
832 g_assert (hb_set_previous (s, &cp));
833 g_assert_cmpint (cp, ==, max_set_elements - 2);
834
835 start = max_set_elements - 1;
836 end = max_set_elements - 1;
837 g_assert (hb_set_previous_range (s, &start, &end));
838 g_assert_cmpint (start, ==, 4001);
839 g_assert_cmpint (end, ==, max_set_elements - 2);
840
841 cp = 0;
842 g_assert (!hb_set_previous (s, &cp));
843 g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
844
845 cp = 40;
846 g_assert (hb_set_previous (s, &cp));
847 g_assert_cmpint (cp, ==, 39);
848
849 start = 40;
850 end = 40;
851 g_assert (hb_set_previous_range (s, &start, &end));
852 g_assert_cmpint (start, ==, 0);
853 g_assert_cmpint (end, ==, 39);
854
855 start = 0;
856 end = 0;
857 g_assert (!hb_set_previous_range (s, &start, &end));
858 g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
859 g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
860
861
862 cp = 2;
863 hb_set_del (s, 0);
864 g_assert (hb_set_previous (s, &cp));
865 g_assert_cmpint (cp, ==, 1);
866 g_assert (!hb_set_previous (s, &cp));
867 g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
868
869 start = 1;
870 end = 1;
871 g_assert (!hb_set_previous_range (s, &start, &end));
872 g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
873 g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
874
875 start = 2;
876 end = 2;
877 g_assert (hb_set_previous_range (s, &start, &end));
878 g_assert_cmpint (start, ==, 1);
879 g_assert_cmpint (end, ==, 1);
880
881 hb_set_destroy (s);
882 }
883
884
885 static void
test_set_inverted_equality(void)886 test_set_inverted_equality (void)
887 {
888 hb_set_t *a = hb_set_create ();
889 hb_set_t *b = hb_set_create ();
890 hb_set_invert (a);
891 hb_set_invert (b);
892
893 g_assert (hb_set_is_equal (a, b));
894 g_assert (hb_set_is_equal (b, a));
895
896 hb_set_add (a, 10);
897 g_assert (hb_set_is_equal (a, b));
898 g_assert (hb_set_is_equal (b, a));
899
900 hb_set_del (a, 42);
901 g_assert (!hb_set_is_equal (a, b));
902 g_assert (!hb_set_is_equal (b, a));
903
904 hb_set_del (b, 42);
905 g_assert (hb_set_is_equal (a, b));
906 g_assert (hb_set_is_equal (b, a));
907
908 hb_set_del_range (a, 43, 50);
909 hb_set_del_range (a, 51, 76);
910 hb_set_del_range (b, 43, 76);
911 g_assert (hb_set_is_equal (a, b));
912 g_assert (hb_set_is_equal (b, a));
913
914 hb_set_del (a, 0);
915 g_assert (!hb_set_is_equal (a, b));
916 g_assert (!hb_set_is_equal (b, a));
917
918 hb_set_del (b, 0);
919 g_assert (hb_set_is_equal (a, b));
920 g_assert (hb_set_is_equal (b, a));
921
922 hb_set_del (a, max_set_elements - 1);
923 g_assert (!hb_set_is_equal (a, b));
924 g_assert (!hb_set_is_equal (b, a));
925
926 hb_set_del (b, max_set_elements - 1);
927 g_assert (hb_set_is_equal (a, b));
928 g_assert (hb_set_is_equal (b, a));
929
930 hb_set_invert (a);
931 g_assert (!hb_set_is_equal (a, b));
932 g_assert (!hb_set_is_equal (b, a));
933
934 hb_set_invert (b);
935 g_assert (hb_set_is_equal (a, b));
936 g_assert (hb_set_is_equal (b, a));
937
938 hb_set_destroy (a);
939 hb_set_destroy (b);
940 }
941
942 typedef enum {
943 UNION = 0,
944 INTERSECT,
945 SUBTRACT,
946 SYM_DIFF,
947 LAST,
948 } set_operation;
949
prepare_set(hb_bool_t has_x,hb_bool_t inverted,hb_bool_t has_page,hb_bool_t is_null)950 static hb_set_t* prepare_set(hb_bool_t has_x,
951 hb_bool_t inverted,
952 hb_bool_t has_page,
953 hb_bool_t is_null)
954 {
955 static const hb_codepoint_t x = 13;
956 if (is_null)
957 return hb_set_get_empty ();
958
959 hb_set_t* s = hb_set_create ();
960 if (inverted) hb_set_invert (s);
961 if (has_page)
962 {
963 // Ensure a page exists for x.
964 inverted ? hb_set_del (s, x) : hb_set_add (s, x);
965 }
966 if (has_x)
967 hb_set_add (s, x);
968 else
969 hb_set_del (s, x);
970
971 return s;
972 }
973
974 static hb_bool_t
check_set_operations(hb_bool_t a_has_x,hb_bool_t a_inverted,hb_bool_t a_has_page,hb_bool_t a_is_null,hb_bool_t b_has_x,hb_bool_t b_inverted,hb_bool_t b_has_page,hb_bool_t b_is_null,set_operation op)975 check_set_operations(hb_bool_t a_has_x,
976 hb_bool_t a_inverted,
977 hb_bool_t a_has_page,
978 hb_bool_t a_is_null,
979 hb_bool_t b_has_x,
980 hb_bool_t b_inverted,
981 hb_bool_t b_has_page,
982 hb_bool_t b_is_null,
983 set_operation op)
984 {
985 hb_codepoint_t x = 13;
986 hb_set_t* a = prepare_set (a_has_x, a_inverted, a_has_page, a_is_null);
987 hb_set_t* b = prepare_set (b_has_x, b_inverted, b_has_page, b_is_null);
988
989 const char* op_name;
990 hb_bool_t has_expected;
991 hb_bool_t should_have_x;
992 switch (op) {
993 default:
994 case LAST:
995 case UNION:
996 op_name = "union";
997 should_have_x = (a_has_x || b_has_x) && !a_is_null;
998 hb_set_union (a, b);
999 has_expected = (hb_set_has (a, x) == should_have_x);
1000 break;
1001 case INTERSECT:
1002 op_name = "intersect";
1003 should_have_x = (a_has_x && b_has_x) && !a_is_null;
1004 hb_set_intersect (a, b);
1005 has_expected = (hb_set_has (a, x) == should_have_x);
1006 break;
1007 case SUBTRACT:
1008 op_name = "subtract";
1009 should_have_x = (a_has_x && !b_has_x) && !a_is_null;
1010 hb_set_subtract (a, b);
1011 has_expected = (hb_set_has (a, x) == should_have_x);
1012 break;
1013 case SYM_DIFF:
1014 op_name = "sym_diff";
1015 should_have_x = (a_has_x ^ b_has_x) && !a_is_null;
1016 hb_set_symmetric_difference (a, b);
1017 has_expected = (hb_set_has (a, x) == should_have_x);
1018 break;
1019 }
1020
1021 printf ("%s%s%s%s %-9s %s%s%s%s == %s [%s]\n",
1022 a_inverted ? "i" : " ",
1023 a_has_page ? "p" : " ",
1024 a_is_null ? "n" : " ",
1025 a_has_x ? "{13}" : "{} ",
1026 op_name,
1027 b_inverted ? "i" : " ",
1028 b_has_page ? "p" : " ",
1029 b_is_null ? "n" : " ",
1030 b_has_x ? "{13}" : "{} ",
1031 should_have_x ? "{13}" : "{} ",
1032 has_expected ? "succeeded" : "failed");
1033
1034 hb_set_destroy (a);
1035 hb_set_destroy (b);
1036
1037 return has_expected;
1038 }
1039
1040 static void
test_set_inverted_operations(void)1041 test_set_inverted_operations (void)
1042 {
1043 hb_bool_t all_succeeded = 1;
1044 for (hb_bool_t a_has_x = 0; a_has_x <= 1; a_has_x++) {
1045 for (hb_bool_t a_inverted = 0; a_inverted <= 1; a_inverted++) {
1046 for (hb_bool_t b_has_x = 0; b_has_x <= 1; b_has_x++) {
1047 for (hb_bool_t b_inverted = 0; b_inverted <= 1; b_inverted++) {
1048 for (hb_bool_t a_has_page = 0; a_has_page <= !(a_has_x ^ a_inverted); a_has_page++) {
1049 for (hb_bool_t b_has_page = 0; b_has_page <= !(b_has_x ^ b_inverted); b_has_page++) {
1050 for (hb_bool_t a_is_null = 0; a_is_null <= (!a_has_x && !a_has_page && !a_inverted); a_is_null++) {
1051 for (hb_bool_t b_is_null = 0; b_is_null <= (!b_has_x && !b_has_page && !b_inverted); b_is_null++) {
1052 for (set_operation op = UNION; op < LAST; op++) {
1053 all_succeeded = check_set_operations (a_has_x, a_inverted, a_has_page, a_is_null,
1054 b_has_x, b_inverted, b_has_page, b_is_null,
1055 op)
1056 && all_succeeded;
1057 }
1058 }
1059 }
1060 }
1061 }
1062 }
1063 }
1064 }
1065 }
1066
1067 g_assert (all_succeeded);
1068 }
1069
1070 int
main(int argc,char ** argv)1071 main (int argc, char **argv)
1072 {
1073 hb_test_init (&argc, &argv);
1074
1075 hb_test_add (test_set_basic);
1076 hb_test_add (test_set_subsets);
1077 hb_test_add (test_set_algebra);
1078 hb_test_add (test_set_iter);
1079 hb_test_add (test_set_empty);
1080 hb_test_add (test_set_delrange);
1081
1082 hb_test_add (test_set_intersect_empty);
1083 hb_test_add (test_set_intersect_page_reduction);
1084 hb_test_add (test_set_union);
1085
1086 hb_test_add (test_set_inverted_basics);
1087 hb_test_add (test_set_inverted_ranges);
1088 hb_test_add (test_set_inverted_iteration_next);
1089 hb_test_add (test_set_inverted_iteration_prev);
1090 hb_test_add (test_set_inverted_equality);
1091 hb_test_add (test_set_inverted_operations);
1092
1093 return hb_test_run();
1094 }
1095