1/*
2 * Copyright © 2012,2017 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#ifndef HB_SET_HH
28#define HB_SET_HH
29
30#include "hb.hh"
31#include "hb-machinery.hh"
32
33
34/*
35 * hb_set_t
36 */
37
38/* TODO Keep a free-list so we can free pages that are completely zeroed. At that
39 * point maybe also use a sentinel value for "all-1" pages? */
40
41struct hb_set_t
42{
43 HB_DELETE_COPY_ASSIGN (hb_set_t);
44 hb_set_t () { init (); }
45 ~hb_set_t () { fini (); }
46
47 struct page_map_t
48 {
49 int cmp (const page_map_t &o) const { return (int) o.major - (int) major; }
50
51 uint32_t major;
52 uint32_t index;
53 };
54
55 struct page_t
56 {
57 void init0 () { v.clear (); }
58 void init1 () { v.clear (0xFF); }
59
60 unsigned int len () const
61 { return ARRAY_LENGTH_CONST (v); }
62
63 bool is_empty () const
64 {
65 for (unsigned int i = 0; i < len (); i++)
66 if (v[i])
67 return false;
68 return true;
69 }
70
71 void add (hb_codepoint_t g) { elt (g) |= mask (g); }
72 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
73 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
74
75 void add_range (hb_codepoint_t a, hb_codepoint_t b)
76 {
77 elt_t *la = &elt (a);
78 elt_t *lb = &elt (b);
79 if (la == lb)
80 *la |= (mask (b) << 1) - mask(a);
81 else
82 {
83 *la |= ~(mask (a) - 1);
84 la++;
85
86 memset (la, 0xff, (char *) lb - (char *) la);
87
88 *lb |= ((mask (b) << 1) - 1);
89 }
90 }
91
92 bool is_equal (const page_t *other) const
93 {
94 return 0 == hb_memcmp (&v, &other->v, sizeof (v));
95 }
96
97 unsigned int get_population () const
98 {
99 unsigned int pop = 0;
100 for (unsigned int i = 0; i < len (); i++)
101 pop += hb_popcount (v[i]);
102 return pop;
103 }
104
105 bool next (hb_codepoint_t *codepoint) const
106 {
107 unsigned int m = (*codepoint + 1) & MASK;
108 if (!m)
109 {
110 *codepoint = INVALID;
111 return false;
112 }
113 unsigned int i = m / ELT_BITS;
114 unsigned int j = m & ELT_MASK;
115
116 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1);
117 for (const elt_t *p = &vv; i < len (); p = &v[++i])
118 if (*p)
119 {
120 *codepoint = i * ELT_BITS + elt_get_min (*p);
121 return true;
122 }
123
124 *codepoint = INVALID;
125 return false;
126 }
127 bool previous (hb_codepoint_t *codepoint) const
128 {
129 unsigned int m = (*codepoint - 1) & MASK;
130 if (m == MASK)
131 {
132 *codepoint = INVALID;
133 return false;
134 }
135 unsigned int i = m / ELT_BITS;
136 unsigned int j = m & ELT_MASK;
137
138 const elt_t vv = v[i] & ((elt_t (1) << (j + 1)) - 1);
139 const elt_t *p = &vv;
140 while (true)
141 {
142 if (*p)
143 {
144 *codepoint = i * ELT_BITS + elt_get_max (*p);
145 return true;
146 }
147 if ((int) i <= 0) break;
148 p = &v[--i];
149 }
150
151 *codepoint = INVALID;
152 return false;
153 }
154 hb_codepoint_t get_min () const
155 {
156 for (unsigned int i = 0; i < len (); i++)
157 if (v[i])
158 return i * ELT_BITS + elt_get_min (v[i]);
159 return INVALID;
160 }
161 hb_codepoint_t get_max () const
162 {
163 for (int i = len () - 1; i >= 0; i--)
164 if (v[i])
165 return i * ELT_BITS + elt_get_max (v[i]);
166 return 0;
167 }
168
169 typedef unsigned long long elt_t;
170 static constexpr unsigned PAGE_BITS = 512;
171 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");
172
173 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
174 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; }
175
176 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;
177
178 static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8;
179 static constexpr unsigned ELT_MASK = ELT_BITS - 1;
180 static constexpr unsigned BITS = sizeof (vector_t) * 8;
181 static constexpr unsigned MASK = BITS - 1;
182 static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, "");
183
184 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
185 elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
186 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }
187
188 vector_t v;
189 };
190 static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");
191
192 hb_object_header_t header;
193 bool successful; /* Allocations successful */
194 mutable unsigned int population;
195 hb_sorted_vector_t<page_map_t> page_map;
196 hb_vector_t<page_t> pages;
197
198 void init_shallow ()
199 {
200 successful = true;
201 population = 0;
202 page_map.init ();
203 pages.init ();
204 }
205 void init ()
206 {
207 hb_object_init (this);
208 init_shallow ();
209 }
210 void fini_shallow ()
211 {
212 population = 0;
213 page_map.fini ();
214 pages.fini ();
215 }
216 void fini ()
217 {
218 hb_object_fini (this);
219 fini_shallow ();
220 }
221
222 bool in_error () const { return !successful; }
223
224 bool resize (unsigned int count)
225 {
226 if (unlikely (!successful)) return false;
227 if (!pages.resize (count) || !page_map.resize (count))
228 {
229 pages.resize (page_map.length);
230 successful = false;
231 return false;
232 }
233 return true;
234 }
235
236 void reset ()
237 {
238 if (unlikely (hb_object_is_immutable (this)))
239 return;
240 clear ();
241 successful = true;
242 }
243
244 void clear ()
245 {
246 if (unlikely (hb_object_is_immutable (this)))
247 return;
248 population = 0;
249 page_map.resize (0);
250 pages.resize (0);
251 }
252 bool is_empty () const
253 {
254 unsigned int count = pages.length;
255 for (unsigned int i = 0; i < count; i++)
256 if (!pages[i].is_empty ())
257 return false;
258 return true;
259 }
260
261 void dirty () { population = (unsigned int) -1; }
262
263 void add (hb_codepoint_t g)
264 {
265 if (unlikely (!successful)) return;
266 if (unlikely (g == INVALID)) return;
267 dirty ();
268 page_t *page = page_for_insert (g); if (unlikely (!page)) return;
269 page->add (g);
270 }
271 bool add_range (hb_codepoint_t a, hb_codepoint_t b)
272 {
273 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
274 if (unlikely (a > b || a == INVALID || b == INVALID)) return false;
275 dirty ();
276 unsigned int ma = get_major (a);
277 unsigned int mb = get_major (b);
278 if (ma == mb)
279 {
280 page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
281 page->add_range (a, b);
282 }
283 else
284 {
285 page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
286 page->add_range (a, major_start (ma + 1) - 1);
287
288 for (unsigned int m = ma + 1; m < mb; m++)
289 {
290 page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;
291 page->init1 ();
292 }
293
294 page = page_for_insert (b); if (unlikely (!page)) return false;
295 page->add_range (major_start (mb), b);
296 }
297 return true;
298 }
299
300 template <typename T>
301 void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
302 {
303 if (unlikely (!successful)) return;
304 if (!count) return;
305 dirty ();
306 hb_codepoint_t g = *array;
307 while (count)
308 {
309 unsigned int m = get_major (g);
310 page_t *page = page_for_insert (g); if (unlikely (!page)) return;
311 unsigned int start = major_start (m);
312 unsigned int end = major_start (m + 1);
313 do
314 {
315 page->add (g);
316
317 array = &StructAtOffsetUnaligned<T> (array, stride);
318 count--;
319 }
320 while (count && (g = *array, start <= g && g < end));
321 }
322 }
323
324 /* Might return false if array looks unsorted.
325 * Used for faster rejection of corrupt data. */
326 template <typename T>
327 bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
328 {
329 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
330 if (!count) return true;
331 dirty ();
332 hb_codepoint_t g = *array;
333 hb_codepoint_t last_g = g;
334 while (count)
335 {
336 unsigned int m = get_major (g);
337 page_t *page = page_for_insert (g); if (unlikely (!page)) return false;
338 unsigned int end = major_start (m + 1);
339 do
340 {
341 /* If we try harder we can change the following comparison to <=;
342 * Not sure if it's worth it. */
343 if (g < last_g) return false;
344 last_g = g;
345 page->add (g);
346
347 array = (const T *) ((const char *) array + stride);
348 count--;
349 }
350 while (count && (g = *array, g < end));
351 }
352 return true;
353 }
354
355 void del (hb_codepoint_t g)
356 {
357 /* TODO perform op even if !successful. */
358 if (unlikely (!successful)) return;
359 page_t *page = page_for (g);
360 if (!page)
361 return;
362 dirty ();
363 page->del (g);
364 }
365 void del_range (hb_codepoint_t a, hb_codepoint_t b)
366 {
367 /* TODO perform op even if !successful. */
368 /* TODO Optimize, like add_range(). */
369 if (unlikely (!successful)) return;
370 for (unsigned int i = a; i < b + 1; i++)
371 del (i);
372 }
373 bool get (hb_codepoint_t g) const
374 {
375 const page_t *page = page_for (g);
376 if (!page)
377 return false;
378 return page->get (g);
379 }
380
381 /* Has interface. */
382 static constexpr bool SENTINEL = false;
383 typedef bool value_t;
384 value_t operator [] (hb_codepoint_t k) const { return get (k); }
385 bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; }
386 /* Predicate. */
387 bool operator () (hb_codepoint_t k) const { return has (k); }
388
389 /* Sink interface. */
390 hb_set_t& operator << (hb_codepoint_t v) { add (v); return *this; }
391
392 bool intersects (hb_codepoint_t first, hb_codepoint_t last) const
393 {
394 hb_codepoint_t c = first - 1;
395 return next (&c) && c <= last;
396 }
397 void set (const hb_set_t *other)
398 {
399 if (unlikely (!successful)) return;
400 unsigned int count = other->pages.length;
401 if (!resize (count))
402 return;
403 population = other->population;
404 memcpy ((void *) pages, (const void *) other->pages, count * pages.item_size);
405 memcpy ((void *) page_map, (const void *) other->page_map, count * page_map.item_size);
406 }
407
408 bool is_equal (const hb_set_t *other) const
409 {
410 if (get_population () != other->get_population ())
411 return false;
412
413 unsigned int na = pages.length;
414 unsigned int nb = other->pages.length;
415
416 unsigned int a = 0, b = 0;
417 for (; a < na && b < nb; )
418 {
419 if (page_at (a).is_empty ()) { a++; continue; }
420 if (other->page_at (b).is_empty ()) { b++; continue; }
421 if (page_map[a].major != other->page_map[b].major ||
422 !page_at (a).is_equal (&other->page_at (b)))
423 return false;
424 a++;
425 b++;
426 }
427 for (; a < na; a++)
428 if (!page_at (a).is_empty ()) { return false; }
429 for (; b < nb; b++)
430 if (!other->page_at (b).is_empty ()) { return false; }
431
432 return true;
433 }
434
435 bool is_subset (const hb_set_t *larger_set) const
436 {
437 if (get_population () > larger_set->get_population ())
438 return false;
439
440 /* TODO Optimize to use pages. */
441 hb_codepoint_t c = INVALID;
442 while (next (&c))
443 if (!larger_set->has (c))
444 return false;
445
446 return true;
447 }
448
449 template <typename Op>
450 void process (const Op& op, const hb_set_t *other)
451 {
452 if (unlikely (!successful)) return;
453
454 dirty ();
455
456 unsigned int na = pages.length;
457 unsigned int nb = other->pages.length;
458 unsigned int next_page = na;
459
460 unsigned int count = 0, newCount = 0;
461 unsigned int a = 0, b = 0;
462 for (; a < na && b < nb; )
463 {
464 if (page_map[a].major == other->page_map[b].major)
465 {
466 count++;
467 a++;
468 b++;
469 }
470 else if (page_map[a].major < other->page_map[b].major)
471 {
472 if (Op::passthru_left)
473 count++;
474 a++;
475 }
476 else
477 {
478 if (Op::passthru_right)
479 count++;
480 b++;
481 }
482 }
483 if (Op::passthru_left)
484 count += na - a;
485 if (Op::passthru_right)
486 count += nb - b;
487
488 if (count > pages.length)
489 if (!resize (count))
490 return;
491 newCount = count;
492
493 /* Process in-place backward. */
494 a = na;
495 b = nb;
496 for (; a && b; )
497 {
498 if (page_map[a - 1].major == other->page_map[b - 1].major)
499 {
500 a--;
501 b--;
502 count--;
503 page_map[count] = page_map[a];
504 page_at (count).v = op (page_at (a).v, other->page_at (b).v);
505 }
506 else if (page_map[a - 1].major > other->page_map[b - 1].major)
507 {
508 a--;
509 if (Op::passthru_left)
510 {
511 count--;
512 page_map[count] = page_map[a];
513 }
514 }
515 else
516 {
517 b--;
518 if (Op::passthru_right)
519 {
520 count--;
521 page_map[count].major = other->page_map[b].major;
522 page_map[count].index = next_page++;
523 page_at (count).v = other->page_at (b).v;
524 }
525 }
526 }
527 if (Op::passthru_left)
528 while (a)
529 {
530 a--;
531 count--;
532 page_map[count] = page_map [a];
533 }
534 if (Op::passthru_right)
535 while (b)
536 {
537 b--;
538 count--;
539 page_map[count].major = other->page_map[b].major;
540 page_map[count].index = next_page++;
541 page_at (count).v = other->page_at (b).v;
542 }
543 assert (!count);
544 if (pages.length > newCount)
545 resize (newCount);
546 }
547
548 void union_ (const hb_set_t *other)
549 {
550 process (hb_bitwise_or, other);
551 }
552 void intersect (const hb_set_t *other)
553 {
554 process (hb_bitwise_and, other);
555 }
556 void subtract (const hb_set_t *other)
557 {
558 process (hb_bitwise_sub, other);
559 }
560 void symmetric_difference (const hb_set_t *other)
561 {
562 process (hb_bitwise_xor, other);
563 }
564 bool next (hb_codepoint_t *codepoint) const
565 {
566 if (unlikely (*codepoint == INVALID)) {
567 *codepoint = get_min ();
568 return *codepoint != INVALID;
569 }
570
571 page_map_t map = {get_major (*codepoint), 0};
572 unsigned int i;
573 page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
574 if (i < page_map.length && page_map[i].major == map.major)
575 {
576 if (pages[page_map[i].index].next (codepoint))
577 {
578 *codepoint += page_map[i].major * page_t::PAGE_BITS;
579 return true;
580 }
581 i++;
582 }
583 for (; i < page_map.length; i++)
584 {
585 hb_codepoint_t m = pages[page_map[i].index].get_min ();
586 if (m != INVALID)
587 {
588 *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
589 return true;
590 }
591 }
592 *codepoint = INVALID;
593 return false;
594 }
595 bool previous (hb_codepoint_t *codepoint) const
596 {
597 if (unlikely (*codepoint == INVALID)) {
598 *codepoint = get_max ();
599 return *codepoint != INVALID;
600 }
601
602 page_map_t map = {get_major (*codepoint), 0};
603 unsigned int i;
604 page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
605 if (i < page_map.length && page_map[i].major == map.major)
606 {
607 if (pages[page_map[i].index].previous (codepoint))
608 {
609 *codepoint += page_map[i].major * page_t::PAGE_BITS;
610 return true;
611 }
612 }
613 i--;
614 for (; (int) i >= 0; i--)
615 {
616 hb_codepoint_t m = pages[page_map[i].index].get_max ();
617 if (m != INVALID)
618 {
619 *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
620 return true;
621 }
622 }
623 *codepoint = INVALID;
624 return false;
625 }
626 bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
627 {
628 hb_codepoint_t i;
629
630 i = *last;
631 if (!next (&i))
632 {
633 *last = *first = INVALID;
634 return false;
635 }
636
637 /* TODO Speed up. */
638 *last = *first = i;
639 while (next (&i) && i == *last + 1)
640 (*last)++;
641
642 return true;
643 }
644 bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const
645 {
646 hb_codepoint_t i;
647
648 i = *first;
649 if (!previous (&i))
650 {
651 *last = *first = INVALID;
652 return false;
653 }
654
655 /* TODO Speed up. */
656 *last = *first = i;
657 while (previous (&i) && i == *first - 1)
658 (*first)--;
659
660 return true;
661 }
662
663 unsigned int get_population () const
664 {
665 if (population != (unsigned int) -1)
666 return population;
667
668 unsigned int pop = 0;
669 unsigned int count = pages.length;
670 for (unsigned int i = 0; i < count; i++)
671 pop += pages[i].get_population ();
672
673 population = pop;
674 return pop;
675 }
676 hb_codepoint_t get_min () const
677 {
678 unsigned int count = pages.length;
679 for (unsigned int i = 0; i < count; i++)
680 if (!page_at (i).is_empty ())
681 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();
682 return INVALID;
683 }
684 hb_codepoint_t get_max () const
685 {
686 unsigned int count = pages.length;
687 for (int i = count - 1; i >= 0; i++)
688 if (!page_at (i).is_empty ())
689 return page_map[(unsigned) i].major * page_t::PAGE_BITS + page_at (i).get_max ();
690 return INVALID;
691 }
692
693 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
694
695 /*
696 * Iterator implementation.
697 */
698 struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
699 {
700 static constexpr bool is_sorted_iterator = true;
701 iter_t (const hb_set_t &s_ = Null(hb_set_t)) :
702 s (&s_), v (INVALID), l (s->get_population () + 1) { __next__ (); }
703
704 typedef hb_codepoint_t __item_t__;
705 hb_codepoint_t __item__ () const { return v; }
706 bool __more__ () const { return v != INVALID; }
707 void __next__ () { s->next (&v); if (l) l--; }
708 void __prev__ () { s->previous (&v); }
709 unsigned __len__ () const { return l; }
710 iter_t end () const { return iter_t (*s); }
711 bool operator != (const iter_t& o) const
712 { return s != o.s || v != o.v; }
713
714 protected:
715 const hb_set_t *s;
716 hb_codepoint_t v;
717 unsigned l;
718 };
719 iter_t iter () const { return iter_t (*this); }
720 operator iter_t () const { return iter (); }
721
722 protected:
723
724 page_t *page_for_insert (hb_codepoint_t g)
725 {
726 page_map_t map = {get_major (g), pages.length};
727 unsigned int i;
728 if (!page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST))
729 {
730 if (!resize (pages.length + 1))
731 return nullptr;
732
733 pages[map.index].init0 ();
734 memmove (page_map + i + 1,
735 page_map + i,
736 (page_map.length - 1 - i) * page_map.item_size);
737 page_map[i] = map;
738 }
739 return &pages[page_map[i].index];
740 }
741 page_t *page_for (hb_codepoint_t g)
742 {
743 page_map_t key = {get_major (g)};
744 const page_map_t *found = page_map.bsearch (key);
745 if (found)
746 return &pages[found->index];
747 return nullptr;
748 }
749 const page_t *page_for (hb_codepoint_t g) const
750 {
751 page_map_t key = {get_major (g)};
752 const page_map_t *found = page_map.bsearch (key);
753 if (found)
754 return &pages[found->index];
755 return nullptr;
756 }
757 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }
758 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }
759 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }
760 hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }
761};
762
763
764#endif /* HB_SET_HH */
765