1 /* 2 * Copyright © 2012,2017 Google, Inc. 3 * Copyright © 2021 Behdad Esfahbod 4 * 5 * This is part of HarfBuzz, a text shaping library. 6 * 7 * Permission is hereby granted, without written agreement and without 8 * license or royalty fees, to use, copy, modify, and distribute this 9 * software and its documentation for any purpose, provided that the 10 * above copyright notice and the following two paragraphs appear in 11 * all copies of this software. 12 * 13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 17 * DAMAGE. 18 * 19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 21 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 24 * 25 * Google Author(s): Behdad Esfahbod 26 */ 27 28 #ifndef HB_BIT_SET_HH 29 #define HB_BIT_SET_HH 30 31 #include "hb.hh" 32 #include "hb-bit-page.hh" 33 #include "hb-machinery.hh" 34 35 36 struct hb_bit_set_t 37 { 38 hb_bit_set_t () = default; 39 ~hb_bit_set_t () = default; 40 hb_bit_set_thb_bit_set_t41 hb_bit_set_t (const hb_bit_set_t& other) : hb_bit_set_t () { set (other); } hb_bit_set_thb_bit_set_t42 hb_bit_set_t ( hb_bit_set_t&& other) : hb_bit_set_t () { hb_swap (*this, other); } operator =hb_bit_set_t43 hb_bit_set_t& operator= (const hb_bit_set_t& other) { set (other); return *this; } operator =hb_bit_set_t44 hb_bit_set_t& operator= (hb_bit_set_t&& other) { hb_swap (*this, other); return *this; } swap(hb_bit_set_t & a,hb_bit_set_t & b)45 friend void swap (hb_bit_set_t &a, hb_bit_set_t &b) 46 { 47 if (likely (!a.successful || !b.successful)) 48 return; 49 hb_swap (a.population, b.population); 50 hb_swap (a.last_page_lookup, b.last_page_lookup); 51 hb_swap (a.page_map, b.page_map); 52 hb_swap (a.pages, b.pages); 53 } 54 inithb_bit_set_t55 void init () 56 { 57 successful = true; 58 population = 0; 59 last_page_lookup = 0; 60 page_map.init (); 61 pages.init (); 62 } finihb_bit_set_t63 void fini () 64 { 65 page_map.fini (); 66 pages.fini (); 67 } 68 69 using page_t = hb_bit_page_t; 70 struct page_map_t 71 { cmphb_bit_set_t::page_map_t72 int cmp (const page_map_t &o) const { return cmp (o.major); } cmphb_bit_set_t::page_map_t73 int cmp (uint32_t o_major) const { return (int) o_major - (int) major; } 74 75 uint32_t major; 76 uint32_t index; 77 }; 78 79 bool successful = true; /* Allocations successful */ 80 mutable unsigned int population = 0; 81 mutable unsigned int last_page_lookup = 0; 82 hb_sorted_vector_t<page_map_t> page_map; 83 hb_vector_t<page_t> pages; 84 errhb_bit_set_t85 void err () { if (successful) successful = false; } /* TODO Remove */ in_errorhb_bit_set_t86 bool in_error () const { return !successful; } 87 resizehb_bit_set_t88 bool resize (unsigned int count) 89 { 90 if (unlikely (!successful)) return false; 91 if (unlikely (!pages.resize (count) || !page_map.resize (count))) 92 { 93 pages.resize (page_map.length); 94 successful = false; 95 return false; 96 } 97 return true; 98 } 99 resethb_bit_set_t100 void reset () 101 { 102 successful = true; 103 clear (); 104 } 105 clearhb_bit_set_t106 void clear () 107 { 108 resize (0); 109 if (likely (successful)) 110 population = 0; 111 } is_emptyhb_bit_set_t112 bool is_empty () const 113 { 114 unsigned int count = pages.length; 115 for (unsigned int i = 0; i < count; i++) 116 if (!pages[i].is_empty ()) 117 return false; 118 return true; 119 } operator boolhb_bit_set_t120 explicit operator bool () const { return !is_empty (); } 121 122 private: dirtyhb_bit_set_t123 void dirty () { population = UINT_MAX; } 124 public: 125 addhb_bit_set_t126 void add (hb_codepoint_t g) 127 { 128 if (unlikely (!successful)) return; 129 if (unlikely (g == INVALID)) return; 130 dirty (); 131 page_t *page = page_for (g, true); if (unlikely (!page)) return; 132 page->add (g); 133 } add_rangehb_bit_set_t134 bool add_range (hb_codepoint_t a, hb_codepoint_t b) 135 { 136 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */ 137 if (unlikely (a > b || a == INVALID || b == INVALID)) return false; 138 dirty (); 139 unsigned int ma = get_major (a); 140 unsigned int mb = get_major (b); 141 if (ma == mb) 142 { 143 page_t *page = page_for (a, true); if (unlikely (!page)) return false; 144 page->add_range (a, b); 145 } 146 else 147 { 148 page_t *page = page_for (a, true); if (unlikely (!page)) return false; 149 page->add_range (a, major_start (ma + 1) - 1); 150 151 for (unsigned int m = ma + 1; m < mb; m++) 152 { 153 page = page_for (major_start (m), true); if (unlikely (!page)) return false; 154 page->init1 (); 155 } 156 157 page = page_for (b, true); if (unlikely (!page)) return false; 158 page->add_range (major_start (mb), b); 159 } 160 return true; 161 } 162 163 template <typename T> set_arrayhb_bit_set_t164 void set_array (bool v, const T *array, unsigned int count, unsigned int stride=sizeof(T)) 165 { 166 if (unlikely (!successful)) return; 167 if (!count) return; 168 dirty (); 169 hb_codepoint_t g = *array; 170 while (count) 171 { 172 unsigned int m = get_major (g); 173 page_t *page = page_for (g, v); if (unlikely (v && !page)) return; 174 unsigned int start = major_start (m); 175 unsigned int end = major_start (m + 1); 176 do 177 { 178 if (v || page) /* The v check is to optimize out the page check if v is true. */ 179 page->set (g, v); 180 181 array = &StructAtOffsetUnaligned<T> (array, stride); 182 count--; 183 } 184 while (count && (g = *array, start <= g && g < end)); 185 } 186 } 187 188 template <typename T> add_arrayhb_bit_set_t189 void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 190 { set_array (true, array, count, stride); } 191 template <typename T> add_arrayhb_bit_set_t192 void add_array (const hb_array_t<const T>& arr) { add_array (&arr, arr.len ()); } 193 194 template <typename T> del_arrayhb_bit_set_t195 void del_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 196 { set_array (false, array, count, stride); } 197 template <typename T> del_arrayhb_bit_set_t198 void del_array (const hb_array_t<const T>& arr) { del_array (&arr, arr.len ()); } 199 200 /* Might return false if array looks unsorted. 201 * Used for faster rejection of corrupt data. */ 202 template <typename T> set_sorted_arrayhb_bit_set_t203 bool set_sorted_array (bool v, const T *array, unsigned int count, unsigned int stride=sizeof(T)) 204 { 205 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */ 206 if (!count) return true; 207 dirty (); 208 hb_codepoint_t g = *array; 209 hb_codepoint_t last_g = g; 210 while (count) 211 { 212 unsigned int m = get_major (g); 213 page_t *page = page_for (g, v); if (unlikely (v && !page)) return false; 214 unsigned int end = major_start (m + 1); 215 do 216 { 217 /* If we try harder we can change the following comparison to <=; 218 * Not sure if it's worth it. */ 219 if (g < last_g) return false; 220 last_g = g; 221 222 if (v || page) /* The v check is to optimize out the page check if v is true. */ 223 page->add (g); 224 225 array = (const T *) ((const char *) array + stride); 226 count--; 227 } 228 while (count && (g = *array, g < end)); 229 } 230 return true; 231 } 232 233 template <typename T> add_sorted_arrayhb_bit_set_t234 bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 235 { return set_sorted_array (true, array, count, stride); } 236 template <typename T> add_sorted_arrayhb_bit_set_t237 bool add_sorted_array (const hb_sorted_array_t<const T>& arr) { return add_sorted_array (&arr, arr.len ()); } 238 239 template <typename T> del_sorted_arrayhb_bit_set_t240 bool del_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 241 { return set_sorted_array (false, array, count, stride); } 242 template <typename T> del_sorted_arrayhb_bit_set_t243 bool del_sorted_array (const hb_sorted_array_t<const T>& arr) { return del_sorted_array (&arr, arr.len ()); } 244 delhb_bit_set_t245 void del (hb_codepoint_t g) 246 { 247 if (unlikely (!successful)) return; 248 page_t *page = page_for (g); 249 if (!page) 250 return; 251 dirty (); 252 page->del (g); 253 } 254 255 private: del_pageshb_bit_set_t256 void del_pages (int ds, int de) 257 { 258 if (ds <= de) 259 { 260 // Pre-allocate the workspace that compact() will need so we can bail on allocation failure 261 // before attempting to rewrite the page map. 262 hb_vector_t<unsigned> compact_workspace; 263 if (unlikely (!allocate_compact_workspace (compact_workspace))) return; 264 265 unsigned int write_index = 0; 266 for (unsigned int i = 0; i < page_map.length; i++) 267 { 268 int m = (int) page_map[i].major; 269 if (m < ds || de < m) 270 page_map[write_index++] = page_map[i]; 271 } 272 compact (compact_workspace, write_index); 273 resize (write_index); 274 } 275 } 276 277 278 public: del_rangehb_bit_set_t279 void del_range (hb_codepoint_t a, hb_codepoint_t b) 280 { 281 if (unlikely (!successful)) return; 282 if (unlikely (a > b || a == INVALID)) return; 283 dirty (); 284 unsigned int ma = get_major (a); 285 unsigned int mb = get_major (b); 286 /* Delete pages from ds through de if ds <= de. */ 287 int ds = (a == major_start (ma))? (int) ma: (int) (ma + 1); 288 int de = (b + 1 == major_start (mb + 1))? (int) mb: ((int) mb - 1); 289 if (ds > de || (int) ma < ds) 290 { 291 page_t *page = page_for (a); 292 if (page) 293 { 294 if (ma == mb) 295 page->del_range (a, b); 296 else 297 page->del_range (a, major_start (ma + 1) - 1); 298 } 299 } 300 if (de < (int) mb && ma != mb) 301 { 302 page_t *page = page_for (b); 303 if (page) 304 page->del_range (major_start (mb), b); 305 } 306 del_pages (ds, de); 307 } 308 gethb_bit_set_t309 bool get (hb_codepoint_t g) const 310 { 311 const page_t *page = page_for (g); 312 if (!page) 313 return false; 314 return page->get (g); 315 } 316 317 /* Has interface. */ 318 static constexpr bool SENTINEL = false; 319 typedef bool value_t; operator []hb_bit_set_t320 value_t operator [] (hb_codepoint_t k) const { return get (k); } hashb_bit_set_t321 bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; } 322 /* Predicate. */ operator ()hb_bit_set_t323 bool operator () (hb_codepoint_t k) const { return has (k); } 324 325 /* Sink interface. */ operator <<hb_bit_set_t326 hb_bit_set_t& operator << (hb_codepoint_t v) 327 { add (v); return *this; } operator <<hb_bit_set_t328 hb_bit_set_t& operator << (const hb_pair_t<hb_codepoint_t, hb_codepoint_t>& range) 329 { add_range (range.first, range.second); return *this; } 330 intersectshb_bit_set_t331 bool intersects (hb_codepoint_t first, hb_codepoint_t last) const 332 { 333 hb_codepoint_t c = first - 1; 334 return next (&c) && c <= last; 335 } sethb_bit_set_t336 void set (const hb_bit_set_t &other) 337 { 338 if (unlikely (!successful)) return; 339 unsigned int count = other.pages.length; 340 if (unlikely (!resize (count))) 341 return; 342 population = other.population; 343 344 /* TODO switch to vector operator =. */ 345 hb_memcpy ((void *) pages, (const void *) other.pages, count * pages.item_size); 346 hb_memcpy ((void *) page_map, (const void *) other.page_map, count * page_map.item_size); 347 } 348 is_equalhb_bit_set_t349 bool is_equal (const hb_bit_set_t &other) const 350 { 351 if (has_population () && other.has_population () && 352 get_population () != other.get_population ()) 353 return false; 354 355 unsigned int na = pages.length; 356 unsigned int nb = other.pages.length; 357 358 unsigned int a = 0, b = 0; 359 for (; a < na && b < nb; ) 360 { 361 if (page_at (a).is_empty ()) { a++; continue; } 362 if (other.page_at (b).is_empty ()) { b++; continue; } 363 if (page_map[a].major != other.page_map[b].major || 364 !page_at (a).is_equal (other.page_at (b))) 365 return false; 366 a++; 367 b++; 368 } 369 for (; a < na; a++) 370 if (!page_at (a).is_empty ()) { return false; } 371 for (; b < nb; b++) 372 if (!other.page_at (b).is_empty ()) { return false; } 373 374 return true; 375 } 376 is_subsethb_bit_set_t377 bool is_subset (const hb_bit_set_t &larger_set) const 378 { 379 if (has_population () && larger_set.has_population () && 380 get_population () != larger_set.get_population ()) 381 return false; 382 383 uint32_t spi = 0; 384 for (uint32_t lpi = 0; spi < page_map.length && lpi < larger_set.page_map.length; lpi++) 385 { 386 uint32_t spm = page_map[spi].major; 387 uint32_t lpm = larger_set.page_map[lpi].major; 388 auto sp = page_at (spi); 389 auto lp = larger_set.page_at (lpi); 390 391 if (spm < lpm && !sp.is_empty ()) 392 return false; 393 394 if (lpm < spm) 395 continue; 396 397 if (!sp.is_subset (lp)) 398 return false; 399 400 spi++; 401 } 402 403 while (spi < page_map.length) 404 if (!page_at (spi++).is_empty ()) 405 return false; 406 407 return true; 408 } 409 410 private: allocate_compact_workspacehb_bit_set_t411 bool allocate_compact_workspace (hb_vector_t<unsigned>& workspace) 412 { 413 if (unlikely (!workspace.resize (pages.length))) 414 { 415 successful = false; 416 return false; 417 } 418 419 return true; 420 } 421 422 /* 423 * workspace should be a pre-sized vector allocated to hold at exactly pages.length 424 * elements. 425 */ compacthb_bit_set_t426 void compact (hb_vector_t<unsigned>& workspace, 427 unsigned int length) 428 { 429 assert(workspace.length == pages.length); 430 hb_vector_t<unsigned>& old_index_to_page_map_index = workspace; 431 432 hb_fill (old_index_to_page_map_index.writer(), 0xFFFFFFFF); 433 for (unsigned i = 0; i < length; i++) 434 old_index_to_page_map_index[page_map[i].index] = i; 435 436 compact_pages (old_index_to_page_map_index); 437 } compact_pageshb_bit_set_t438 void compact_pages (const hb_vector_t<unsigned>& old_index_to_page_map_index) 439 { 440 unsigned int write_index = 0; 441 for (unsigned int i = 0; i < pages.length; i++) 442 { 443 if (old_index_to_page_map_index[i] == 0xFFFFFFFF) continue; 444 445 if (write_index < i) 446 pages[write_index] = pages[i]; 447 448 page_map[old_index_to_page_map_index[i]].index = write_index; 449 write_index++; 450 } 451 } 452 public: 453 454 template <typename Op> processhb_bit_set_t455 void process (const Op& op, const hb_bit_set_t &other) 456 { 457 const bool passthru_left = op (1, 0); 458 const bool passthru_right = op (0, 1); 459 460 if (unlikely (!successful)) return; 461 462 dirty (); 463 464 unsigned int na = pages.length; 465 unsigned int nb = other.pages.length; 466 unsigned int next_page = na; 467 468 unsigned int count = 0, newCount = 0; 469 unsigned int a = 0, b = 0; 470 unsigned int write_index = 0; 471 472 // Pre-allocate the workspace that compact() will need so we can bail on allocation failure 473 // before attempting to rewrite the page map. 474 hb_vector_t<unsigned> compact_workspace; 475 if (!passthru_left && unlikely (!allocate_compact_workspace (compact_workspace))) return; 476 477 for (; a < na && b < nb; ) 478 { 479 if (page_map[a].major == other.page_map[b].major) 480 { 481 if (!passthru_left) 482 { 483 // Move page_map entries that we're keeping from the left side set 484 // to the front of the page_map vector. This isn't necessary if 485 // passthru_left is set since no left side pages will be removed 486 // in that case. 487 if (write_index < a) 488 page_map[write_index] = page_map[a]; 489 write_index++; 490 } 491 492 count++; 493 a++; 494 b++; 495 } 496 else if (page_map[a].major < other.page_map[b].major) 497 { 498 if (passthru_left) 499 count++; 500 a++; 501 } 502 else 503 { 504 if (passthru_right) 505 count++; 506 b++; 507 } 508 } 509 if (passthru_left) 510 count += na - a; 511 if (passthru_right) 512 count += nb - b; 513 514 if (!passthru_left) 515 { 516 na = write_index; 517 next_page = write_index; 518 compact (compact_workspace, write_index); 519 } 520 521 if (unlikely (!resize (count))) 522 return; 523 524 newCount = count; 525 526 /* Process in-place backward. */ 527 a = na; 528 b = nb; 529 for (; a && b; ) 530 { 531 if (page_map[a - 1].major == other.page_map[b - 1].major) 532 { 533 a--; 534 b--; 535 count--; 536 page_map[count] = page_map[a]; 537 page_at (count).v = op (page_at (a).v, other.page_at (b).v); 538 } 539 else if (page_map[a - 1].major > other.page_map[b - 1].major) 540 { 541 a--; 542 if (passthru_left) 543 { 544 count--; 545 page_map[count] = page_map[a]; 546 } 547 } 548 else 549 { 550 b--; 551 if (passthru_right) 552 { 553 count--; 554 page_map[count].major = other.page_map[b].major; 555 page_map[count].index = next_page++; 556 page_at (count).v = other.page_at (b).v; 557 } 558 } 559 } 560 if (passthru_left) 561 while (a) 562 { 563 a--; 564 count--; 565 page_map[count] = page_map [a]; 566 } 567 if (passthru_right) 568 while (b) 569 { 570 b--; 571 count--; 572 page_map[count].major = other.page_map[b].major; 573 page_map[count].index = next_page++; 574 page_at (count).v = other.page_at (b).v; 575 } 576 assert (!count); 577 resize (newCount); 578 } 579 union_hb_bit_set_t580 void union_ (const hb_bit_set_t &other) { process (hb_bitwise_or, other); } intersecthb_bit_set_t581 void intersect (const hb_bit_set_t &other) { process (hb_bitwise_and, other); } subtracthb_bit_set_t582 void subtract (const hb_bit_set_t &other) { process (hb_bitwise_gt, other); } symmetric_differencehb_bit_set_t583 void symmetric_difference (const hb_bit_set_t &other) { process (hb_bitwise_xor, other); } 584 nexthb_bit_set_t585 bool next (hb_codepoint_t *codepoint) const 586 { 587 // TODO: this should be merged with prev() as both implementations 588 // are very similar. 589 if (unlikely (*codepoint == INVALID)) { 590 *codepoint = get_min (); 591 return *codepoint != INVALID; 592 } 593 594 const auto* page_map_array = page_map.arrayZ; 595 unsigned int major = get_major (*codepoint); 596 unsigned int i = last_page_lookup; 597 598 if (unlikely (i >= page_map.length || page_map_array[i].major != major)) 599 { 600 page_map.bfind (major, &i, HB_NOT_FOUND_STORE_CLOSEST); 601 if (i >= page_map.length) { 602 *codepoint = INVALID; 603 return false; 604 } 605 } 606 607 const auto* pages_array = pages.arrayZ; 608 const page_map_t ¤t = page_map_array[i]; 609 if (likely (current.major == major)) 610 { 611 if (pages_array[current.index].next (codepoint)) 612 { 613 *codepoint += current.major * page_t::PAGE_BITS; 614 last_page_lookup = i; 615 return true; 616 } 617 i++; 618 } 619 620 for (; i < page_map.length; i++) 621 { 622 const page_map_t ¤t = page_map.arrayZ[i]; 623 hb_codepoint_t m = pages_array[current.index].get_min (); 624 if (m != INVALID) 625 { 626 *codepoint = current.major * page_t::PAGE_BITS + m; 627 last_page_lookup = i; 628 return true; 629 } 630 } 631 last_page_lookup = 0; 632 *codepoint = INVALID; 633 return false; 634 } previoushb_bit_set_t635 bool previous (hb_codepoint_t *codepoint) const 636 { 637 if (unlikely (*codepoint == INVALID)) { 638 *codepoint = get_max (); 639 return *codepoint != INVALID; 640 } 641 642 page_map_t map = {get_major (*codepoint), 0}; 643 unsigned int i; 644 page_map.bfind (map, &i, HB_NOT_FOUND_STORE_CLOSEST); 645 if (i < page_map.length && page_map[i].major == map.major) 646 { 647 if (pages[page_map[i].index].previous (codepoint)) 648 { 649 *codepoint += page_map[i].major * page_t::PAGE_BITS; 650 return true; 651 } 652 } 653 i--; 654 for (; (int) i >= 0; i--) 655 { 656 hb_codepoint_t m = pages[page_map[i].index].get_max (); 657 if (m != INVALID) 658 { 659 *codepoint = page_map[i].major * page_t::PAGE_BITS + m; 660 return true; 661 } 662 } 663 *codepoint = INVALID; 664 return false; 665 } next_rangehb_bit_set_t666 bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const 667 { 668 hb_codepoint_t i; 669 670 i = *last; 671 if (!next (&i)) 672 { 673 *last = *first = INVALID; 674 return false; 675 } 676 677 /* TODO Speed up. */ 678 *last = *first = i; 679 while (next (&i) && i == *last + 1) 680 (*last)++; 681 682 return true; 683 } previous_rangehb_bit_set_t684 bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const 685 { 686 hb_codepoint_t i; 687 688 i = *first; 689 if (!previous (&i)) 690 { 691 *last = *first = INVALID; 692 return false; 693 } 694 695 /* TODO Speed up. */ 696 *last = *first = i; 697 while (previous (&i) && i == *first - 1) 698 (*first)--; 699 700 return true; 701 } 702 has_populationhb_bit_set_t703 bool has_population () const { return population != UINT_MAX; } get_populationhb_bit_set_t704 unsigned int get_population () const 705 { 706 if (has_population ()) 707 return population; 708 709 unsigned int pop = 0; 710 unsigned int count = pages.length; 711 for (unsigned int i = 0; i < count; i++) 712 pop += pages[i].get_population (); 713 714 population = pop; 715 return pop; 716 } get_minhb_bit_set_t717 hb_codepoint_t get_min () const 718 { 719 unsigned count = pages.length; 720 for (unsigned i = 0; i < count; i++) 721 { 722 const auto& map = page_map[i]; 723 const auto& page = pages[map.index]; 724 725 if (!page.is_empty ()) 726 return map.major * page_t::PAGE_BITS + page.get_min (); 727 } 728 return INVALID; 729 } get_maxhb_bit_set_t730 hb_codepoint_t get_max () const 731 { 732 unsigned count = pages.length; 733 for (signed i = count - 1; i >= 0; i--) 734 { 735 const auto& map = page_map[(unsigned) i]; 736 const auto& page = pages[map.index]; 737 738 if (!page.is_empty ()) 739 return map.major * page_t::PAGE_BITS + page.get_max (); 740 } 741 return INVALID; 742 } 743 744 static constexpr hb_codepoint_t INVALID = page_t::INVALID; 745 746 /* 747 * Iterator implementation. 748 */ 749 struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t> 750 { 751 static constexpr bool is_sorted_iterator = true; iter_thb_bit_set_t::iter_t752 iter_t (const hb_bit_set_t &s_ = Null (hb_bit_set_t), 753 bool init = true) : s (&s_), v (INVALID), l(0) 754 { 755 if (init) 756 { 757 l = s->get_population () + 1; 758 __next__ (); 759 } 760 } 761 762 typedef hb_codepoint_t __item_t__; __item__hb_bit_set_t::iter_t763 hb_codepoint_t __item__ () const { return v; } __more__hb_bit_set_t::iter_t764 bool __more__ () const { return v != INVALID; } __next__hb_bit_set_t::iter_t765 void __next__ () { s->next (&v); if (l) l--; } __prev__hb_bit_set_t::iter_t766 void __prev__ () { s->previous (&v); } __len__hb_bit_set_t::iter_t767 unsigned __len__ () const { return l; } endhb_bit_set_t::iter_t768 iter_t end () const { return iter_t (*s, false); } operator !=hb_bit_set_t::iter_t769 bool operator != (const iter_t& o) const 770 { return s != o.s || v != o.v; } 771 772 protected: 773 const hb_bit_set_t *s; 774 hb_codepoint_t v; 775 unsigned l; 776 }; iterhb_bit_set_t777 iter_t iter () const { return iter_t (*this); } operator iter_thb_bit_set_t778 operator iter_t () const { return iter (); } 779 780 protected: 781 page_forhb_bit_set_t782 page_t *page_for (hb_codepoint_t g, bool insert = false) 783 { 784 page_map_t map = {get_major (g), pages.length}; 785 unsigned int i; 786 if (!page_map.bfind (map, &i, HB_NOT_FOUND_STORE_CLOSEST)) 787 { 788 if (!insert) 789 return nullptr; 790 791 if (unlikely (!resize (pages.length + 1))) 792 return nullptr; 793 794 pages[map.index].init0 (); 795 memmove (page_map + i + 1, 796 page_map + i, 797 (page_map.length - 1 - i) * page_map.item_size); 798 page_map[i] = map; 799 } 800 return &pages[page_map[i].index]; 801 } page_forhb_bit_set_t802 const page_t *page_for (hb_codepoint_t g) const 803 { 804 page_map_t key = {get_major (g)}; 805 const page_map_t *found = page_map.bsearch (key); 806 if (found) 807 return &pages[found->index]; 808 return nullptr; 809 } page_athb_bit_set_t810 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } page_athb_bit_set_t811 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } get_majorhb_bit_set_t812 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; } major_starthb_bit_set_t813 hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; } 814 }; 815 816 817 #endif /* HB_BIT_SET_HH */ 818