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 41 struct hb_set_t 42 { 43 HB_DELETE_COPY_ASSIGN (hb_set_t); hb_set_thb_set_t44 hb_set_t () { init (); } ~hb_set_thb_set_t45 ~hb_set_t () { fini (); } 46 47 struct page_map_t 48 { cmphb_set_t::page_map_t49 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 { init0hb_set_t::page_t57 void init0 () { v.clear (); } init1hb_set_t::page_t58 void init1 () { v.clear (0xFF); } 59 lenhb_set_t::page_t60 unsigned int len () const 61 { return ARRAY_LENGTH_CONST (v); } 62 is_emptyhb_set_t::page_t63 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 addhb_set_t::page_t71 void add (hb_codepoint_t g) { elt (g) |= mask (g); } delhb_set_t::page_t72 void del (hb_codepoint_t g) { elt (g) &= ~mask (g); } gethb_set_t::page_t73 bool get (hb_codepoint_t g) const { return elt (g) & mask (g); } 74 add_rangehb_set_t::page_t75 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 is_equalhb_set_t::page_t92 bool is_equal (const page_t *other) const 93 { 94 return 0 == hb_memcmp (&v, &other->v, sizeof (v)); 95 } 96 get_populationhb_set_t::page_t97 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 nexthb_set_t::page_t105 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 } previoushb_set_t::page_t127 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 } get_minhb_set_t::page_t154 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 } get_maxhb_set_t::page_t161 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 elt_get_minhb_set_t::page_t173 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); } elt_get_maxhb_set_t::page_t174 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 elthb_set_t::page_t184 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } elthb_set_t::page_t185 elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } maskhb_set_t::page_t186 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 init_shallowhb_set_t198 void init_shallow () 199 { 200 successful = true; 201 population = 0; 202 page_map.init (); 203 pages.init (); 204 } inithb_set_t205 void init () 206 { 207 hb_object_init (this); 208 init_shallow (); 209 } fini_shallowhb_set_t210 void fini_shallow () 211 { 212 population = 0; 213 page_map.fini (); 214 pages.fini (); 215 } finihb_set_t216 void fini () 217 { 218 hb_object_fini (this); 219 fini_shallow (); 220 } 221 in_errorhb_set_t222 bool in_error () const { return !successful; } 223 resizehb_set_t224 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 resethb_set_t236 void reset () 237 { 238 if (unlikely (hb_object_is_immutable (this))) 239 return; 240 clear (); 241 successful = true; 242 } 243 clearhb_set_t244 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 } is_emptyhb_set_t252 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 dirtyhb_set_t261 void dirty () { population = (unsigned int) -1; } 262 addhb_set_t263 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 } add_rangehb_set_t271 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> add_arrayhb_set_t301 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> add_sorted_arrayhb_set_t327 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 delhb_set_t355 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 } del_rangehb_set_t365 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 } gethb_set_t373 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; operator []hb_set_t384 value_t operator [] (hb_codepoint_t k) const { return get (k); } hashb_set_t385 bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; } 386 /* Predicate. */ operator ()hb_set_t387 bool operator () (hb_codepoint_t k) const { return has (k); } 388 389 /* Sink interface. */ operator <<hb_set_t390 hb_set_t& operator << (hb_codepoint_t v) { add (v); return *this; } 391 intersectshb_set_t392 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 } sethb_set_t397 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 is_equalhb_set_t408 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 is_subsethb_set_t435 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> processhb_set_t450 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 union_hb_set_t548 void union_ (const hb_set_t *other) 549 { 550 process (hb_bitwise_or, other); 551 } intersecthb_set_t552 void intersect (const hb_set_t *other) 553 { 554 process (hb_bitwise_and, other); 555 } subtracthb_set_t556 void subtract (const hb_set_t *other) 557 { 558 process (hb_bitwise_sub, other); 559 } symmetric_differencehb_set_t560 void symmetric_difference (const hb_set_t *other) 561 { 562 process (hb_bitwise_xor, other); 563 } nexthb_set_t564 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 } previoushb_set_t595 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 } next_rangehb_set_t626 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 } previous_rangehb_set_t644 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 get_populationhb_set_t663 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 } get_minhb_set_t676 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 } get_maxhb_set_t684 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; iter_thb_set_t::iter_t701 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__; __item__hb_set_t::iter_t705 hb_codepoint_t __item__ () const { return v; } __more__hb_set_t::iter_t706 bool __more__ () const { return v != INVALID; } __next__hb_set_t::iter_t707 void __next__ () { s->next (&v); if (l) l--; } __prev__hb_set_t::iter_t708 void __prev__ () { s->previous (&v); } __len__hb_set_t::iter_t709 unsigned __len__ () const { return l; } endhb_set_t::iter_t710 iter_t end () const { return iter_t (*s); } operator !=hb_set_t::iter_t711 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 }; iterhb_set_t719 iter_t iter () const { return iter_t (*this); } operator iter_thb_set_t720 operator iter_t () const { return iter (); } 721 722 protected: 723 page_for_inserthb_set_t724 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 } page_forhb_set_t741 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 } page_forhb_set_t749 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 } page_athb_set_t757 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } page_athb_set_t758 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } get_majorhb_set_t759 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; } major_starthb_set_t760 hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; } 761 }; 762 763 764 #endif /* HB_SET_HH */ 765