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 del_rangehb_set_t::page_t92 void del_range (hb_codepoint_t a, hb_codepoint_t b) 93 { 94 elt_t *la = &elt (a); 95 elt_t *lb = &elt (b); 96 if (la == lb) 97 *la &= ~((mask (b) << 1) - mask(a)); 98 else 99 { 100 *la &= mask (a) - 1; 101 la++; 102 103 memset (la, 0, (char *) lb - (char *) la); 104 105 *lb &= ~((mask (b) << 1) - 1); 106 } 107 } 108 is_equalhb_set_t::page_t109 bool is_equal (const page_t *other) const 110 { 111 return 0 == hb_memcmp (&v, &other->v, sizeof (v)); 112 } 113 get_populationhb_set_t::page_t114 unsigned int get_population () const 115 { 116 unsigned int pop = 0; 117 for (unsigned int i = 0; i < len (); i++) 118 pop += hb_popcount (v[i]); 119 return pop; 120 } 121 nexthb_set_t::page_t122 bool next (hb_codepoint_t *codepoint) const 123 { 124 unsigned int m = (*codepoint + 1) & MASK; 125 if (!m) 126 { 127 *codepoint = INVALID; 128 return false; 129 } 130 unsigned int i = m / ELT_BITS; 131 unsigned int j = m & ELT_MASK; 132 133 const elt_t vv = v[i] & ~((elt_t (1) << j) - 1); 134 for (const elt_t *p = &vv; i < len (); p = &v[++i]) 135 if (*p) 136 { 137 *codepoint = i * ELT_BITS + elt_get_min (*p); 138 return true; 139 } 140 141 *codepoint = INVALID; 142 return false; 143 } previoushb_set_t::page_t144 bool previous (hb_codepoint_t *codepoint) const 145 { 146 unsigned int m = (*codepoint - 1) & MASK; 147 if (m == MASK) 148 { 149 *codepoint = INVALID; 150 return false; 151 } 152 unsigned int i = m / ELT_BITS; 153 unsigned int j = m & ELT_MASK; 154 155 /* Fancy mask to avoid shifting by elt_t bitsize, which is undefined. */ 156 const elt_t mask = j < 8 * sizeof (elt_t) - 1 ? 157 ((elt_t (1) << (j + 1)) - 1) : 158 (elt_t) -1; 159 const elt_t vv = v[i] & mask; 160 const elt_t *p = &vv; 161 while (true) 162 { 163 if (*p) 164 { 165 *codepoint = i * ELT_BITS + elt_get_max (*p); 166 return true; 167 } 168 if ((int) i <= 0) break; 169 p = &v[--i]; 170 } 171 172 *codepoint = INVALID; 173 return false; 174 } get_minhb_set_t::page_t175 hb_codepoint_t get_min () const 176 { 177 for (unsigned int i = 0; i < len (); i++) 178 if (v[i]) 179 return i * ELT_BITS + elt_get_min (v[i]); 180 return INVALID; 181 } get_maxhb_set_t::page_t182 hb_codepoint_t get_max () const 183 { 184 for (int i = len () - 1; i >= 0; i--) 185 if (v[i]) 186 return i * ELT_BITS + elt_get_max (v[i]); 187 return 0; 188 } 189 190 typedef unsigned long long elt_t; 191 static constexpr unsigned PAGE_BITS = 512; 192 static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, ""); 193 elt_get_minhb_set_t::page_t194 static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); } elt_get_maxhb_set_t::page_t195 static unsigned int elt_get_max (const elt_t &elt) { return hb_bit_storage (elt) - 1; } 196 197 typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t; 198 199 static constexpr unsigned ELT_BITS = sizeof (elt_t) * 8; 200 static constexpr unsigned ELT_MASK = ELT_BITS - 1; 201 static constexpr unsigned BITS = sizeof (vector_t) * 8; 202 static constexpr unsigned MASK = BITS - 1; 203 static_assert ((unsigned) PAGE_BITS == (unsigned) BITS, ""); 204 elthb_set_t::page_t205 elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; } elthb_set_t::page_t206 elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; } maskhb_set_t::page_t207 elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); } 208 209 vector_t v; 210 }; 211 static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, ""); 212 213 hb_object_header_t header; 214 bool successful; /* Allocations successful */ 215 mutable unsigned int population; 216 hb_sorted_vector_t<page_map_t> page_map; 217 hb_vector_t<page_t> pages; 218 init_shallowhb_set_t219 void init_shallow () 220 { 221 successful = true; 222 population = 0; 223 page_map.init (); 224 pages.init (); 225 } inithb_set_t226 void init () 227 { 228 hb_object_init (this); 229 init_shallow (); 230 } fini_shallowhb_set_t231 void fini_shallow () 232 { 233 population = 0; 234 page_map.fini (); 235 pages.fini (); 236 } finihb_set_t237 void fini () 238 { 239 hb_object_fini (this); 240 fini_shallow (); 241 } 242 in_errorhb_set_t243 bool in_error () const { return !successful; } 244 resizehb_set_t245 bool resize (unsigned int count) 246 { 247 if (unlikely (count > pages.length && !successful)) return false; 248 if (!pages.resize (count) || !page_map.resize (count)) 249 { 250 pages.resize (page_map.length); 251 successful = false; 252 return false; 253 } 254 return true; 255 } 256 resethb_set_t257 void reset () 258 { 259 successful = true; 260 clear (); 261 } 262 clearhb_set_t263 void clear () 264 { 265 if (resize (0)) 266 population = 0; 267 } is_emptyhb_set_t268 bool is_empty () const 269 { 270 unsigned int count = pages.length; 271 for (unsigned int i = 0; i < count; i++) 272 if (!pages[i].is_empty ()) 273 return false; 274 return true; 275 } operator boolhb_set_t276 explicit operator bool () const { return !is_empty (); } 277 dirtyhb_set_t278 void dirty () { population = UINT_MAX; } 279 addhb_set_t280 void add (hb_codepoint_t g) 281 { 282 if (unlikely (!successful)) return; 283 if (unlikely (g == INVALID)) return; 284 dirty (); 285 page_t *page = page_for_insert (g); if (unlikely (!page)) return; 286 page->add (g); 287 } add_rangehb_set_t288 bool add_range (hb_codepoint_t a, hb_codepoint_t b) 289 { 290 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */ 291 if (unlikely (a > b || a == INVALID || b == INVALID)) return false; 292 dirty (); 293 unsigned int ma = get_major (a); 294 unsigned int mb = get_major (b); 295 if (ma == mb) 296 { 297 page_t *page = page_for_insert (a); if (unlikely (!page)) return false; 298 page->add_range (a, b); 299 } 300 else 301 { 302 page_t *page = page_for_insert (a); if (unlikely (!page)) return false; 303 page->add_range (a, major_start (ma + 1) - 1); 304 305 for (unsigned int m = ma + 1; m < mb; m++) 306 { 307 page = page_for_insert (major_start (m)); if (unlikely (!page)) return false; 308 page->init1 (); 309 } 310 311 page = page_for_insert (b); if (unlikely (!page)) return false; 312 page->add_range (major_start (mb), b); 313 } 314 return true; 315 } 316 317 template <typename T> add_arrayhb_set_t318 void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 319 { 320 if (unlikely (!successful)) return; 321 if (!count) return; 322 dirty (); 323 hb_codepoint_t g = *array; 324 while (count) 325 { 326 unsigned int m = get_major (g); 327 page_t *page = page_for_insert (g); if (unlikely (!page)) return; 328 unsigned int start = major_start (m); 329 unsigned int end = major_start (m + 1); 330 do 331 { 332 page->add (g); 333 334 array = &StructAtOffsetUnaligned<T> (array, stride); 335 count--; 336 } 337 while (count && (g = *array, start <= g && g < end)); 338 } 339 } 340 template <typename T> add_arrayhb_set_t341 void add_array (const hb_array_t<const T>& arr) { add_array (&arr, arr.len ()); } 342 343 /* Might return false if array looks unsorted. 344 * Used for faster rejection of corrupt data. */ 345 template <typename T> add_sorted_arrayhb_set_t346 bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T)) 347 { 348 if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */ 349 if (!count) return true; 350 dirty (); 351 hb_codepoint_t g = *array; 352 hb_codepoint_t last_g = g; 353 while (count) 354 { 355 unsigned int m = get_major (g); 356 page_t *page = page_for_insert (g); if (unlikely (!page)) return false; 357 unsigned int end = major_start (m + 1); 358 do 359 { 360 /* If we try harder we can change the following comparison to <=; 361 * Not sure if it's worth it. */ 362 if (g < last_g) return false; 363 last_g = g; 364 page->add (g); 365 366 array = (const T *) ((const char *) array + stride); 367 count--; 368 } 369 while (count && (g = *array, g < end)); 370 } 371 return true; 372 } 373 template <typename T> add_sorted_arrayhb_set_t374 bool add_sorted_array (const hb_sorted_array_t<const T>& arr) { return add_sorted_array (&arr, arr.len ()); } 375 delhb_set_t376 void del (hb_codepoint_t g) 377 { 378 /* TODO perform op even if !successful. */ 379 if (unlikely (!successful)) return; 380 page_t *page = page_for (g); 381 if (!page) 382 return; 383 dirty (); 384 page->del (g); 385 } 386 387 private: del_pageshb_set_t388 void del_pages (int ds, int de) 389 { 390 if (ds <= de) 391 { 392 // Pre-allocate the workspace that compact() will need so we can bail on allocation failure 393 // before attempting to rewrite the page map. 394 hb_vector_t<unsigned> compact_workspace; 395 if (unlikely (!allocate_compact_workspace (compact_workspace))) return; 396 397 unsigned int write_index = 0; 398 for (unsigned int i = 0; i < page_map.length; i++) 399 { 400 int m = (int) page_map[i].major; 401 if (m < ds || de < m) 402 page_map[write_index++] = page_map[i]; 403 } 404 compact (compact_workspace, write_index); 405 resize (write_index); 406 } 407 } 408 409 410 public: del_rangehb_set_t411 void del_range (hb_codepoint_t a, hb_codepoint_t b) 412 { 413 /* TODO perform op even if !successful. */ 414 if (unlikely (!successful)) return; 415 if (unlikely (a > b || a == INVALID || b == INVALID)) return; 416 dirty (); 417 unsigned int ma = get_major (a); 418 unsigned int mb = get_major (b); 419 /* Delete pages from ds through de if ds <= de. */ 420 int ds = (a == major_start (ma))? (int) ma: (int) (ma + 1); 421 int de = (b + 1 == major_start (mb + 1))? (int) mb: ((int) mb - 1); 422 if (ds > de || (int) ma < ds) 423 { 424 page_t *page = page_for (a); 425 if (page) 426 { 427 if (ma == mb) 428 page->del_range (a, b); 429 else 430 page->del_range (a, major_start (ma + 1) - 1); 431 } 432 } 433 if (de < (int) mb && ma != mb) 434 { 435 page_t *page = page_for (b); 436 if (page) 437 page->del_range (major_start (mb), b); 438 } 439 del_pages (ds, de); 440 } 441 gethb_set_t442 bool get (hb_codepoint_t g) const 443 { 444 const page_t *page = page_for (g); 445 if (!page) 446 return false; 447 return page->get (g); 448 } 449 450 /* Has interface. */ 451 static constexpr bool SENTINEL = false; 452 typedef bool value_t; operator []hb_set_t453 value_t operator [] (hb_codepoint_t k) const { return get (k); } hashb_set_t454 bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; } 455 /* Predicate. */ operator ()hb_set_t456 bool operator () (hb_codepoint_t k) const { return has (k); } 457 458 /* Sink interface. */ operator <<hb_set_t459 hb_set_t& operator << (hb_codepoint_t v) 460 { add (v); return *this; } operator <<hb_set_t461 hb_set_t& operator << (const hb_pair_t<hb_codepoint_t, hb_codepoint_t>& range) 462 { add_range (range.first, range.second); return *this; } 463 intersectshb_set_t464 bool intersects (hb_codepoint_t first, hb_codepoint_t last) const 465 { 466 hb_codepoint_t c = first - 1; 467 return next (&c) && c <= last; 468 } sethb_set_t469 void set (const hb_set_t *other) 470 { 471 if (unlikely (!successful)) return; 472 unsigned int count = other->pages.length; 473 if (!resize (count)) 474 return; 475 population = other->population; 476 memcpy ((void *) pages, (const void *) other->pages, count * pages.item_size); 477 memcpy ((void *) page_map, (const void *) other->page_map, count * page_map.item_size); 478 } 479 is_equalhb_set_t480 bool is_equal (const hb_set_t *other) const 481 { 482 if (get_population () != other->get_population ()) 483 return false; 484 485 unsigned int na = pages.length; 486 unsigned int nb = other->pages.length; 487 488 unsigned int a = 0, b = 0; 489 for (; a < na && b < nb; ) 490 { 491 if (page_at (a).is_empty ()) { a++; continue; } 492 if (other->page_at (b).is_empty ()) { b++; continue; } 493 if (page_map[a].major != other->page_map[b].major || 494 !page_at (a).is_equal (&other->page_at (b))) 495 return false; 496 a++; 497 b++; 498 } 499 for (; a < na; a++) 500 if (!page_at (a).is_empty ()) { return false; } 501 for (; b < nb; b++) 502 if (!other->page_at (b).is_empty ()) { return false; } 503 504 return true; 505 } 506 is_subsethb_set_t507 bool is_subset (const hb_set_t *larger_set) const 508 { 509 if (get_population () > larger_set->get_population ()) 510 return false; 511 512 /* TODO Optimize to use pages. */ 513 hb_codepoint_t c = INVALID; 514 while (next (&c)) 515 if (!larger_set->has (c)) 516 return false; 517 518 return true; 519 } 520 allocate_compact_workspacehb_set_t521 bool allocate_compact_workspace(hb_vector_t<unsigned>& workspace) 522 { 523 if (unlikely(!workspace.resize (pages.length))) 524 { 525 successful = false; 526 return false; 527 } 528 529 return true; 530 } 531 532 533 /* 534 * workspace should be a pre-sized vector allocated to hold at exactly pages.length 535 * elements. 536 */ compacthb_set_t537 void compact (hb_vector_t<unsigned>& workspace, 538 unsigned int length) 539 { 540 assert(workspace.length == pages.length); 541 hb_vector_t<unsigned>& old_index_to_page_map_index = workspace; 542 543 hb_fill (old_index_to_page_map_index.writer(), 0xFFFFFFFF); 544 /* TODO(iter) Rewrite as dagger? */ 545 for (unsigned i = 0; i < length; i++) 546 old_index_to_page_map_index[page_map[i].index] = i; 547 548 compact_pages (old_index_to_page_map_index); 549 } 550 compact_pageshb_set_t551 void compact_pages (const hb_vector_t<unsigned>& old_index_to_page_map_index) 552 { 553 unsigned int write_index = 0; 554 for (unsigned int i = 0; i < pages.length; i++) 555 { 556 if (old_index_to_page_map_index[i] == 0xFFFFFFFF) continue; 557 558 if (write_index < i) 559 pages[write_index] = pages[i]; 560 561 page_map[old_index_to_page_map_index[i]].index = write_index; 562 write_index++; 563 } 564 } 565 566 template <typename Op> processhb_set_t567 void process (const Op& op, const hb_set_t *other) 568 { 569 const bool passthru_left = op (1, 0); 570 const bool passthru_right = op (0, 1); 571 572 if (unlikely (!successful)) return; 573 574 dirty (); 575 576 unsigned int na = pages.length; 577 unsigned int nb = other->pages.length; 578 unsigned int next_page = na; 579 580 unsigned int count = 0, newCount = 0; 581 unsigned int a = 0, b = 0; 582 unsigned int write_index = 0; 583 584 // Pre-allocate the workspace that compact() will need so we can bail on allocation failure 585 // before attempting to rewrite the page map. 586 hb_vector_t<unsigned> compact_workspace; 587 if (!passthru_left && unlikely (!allocate_compact_workspace (compact_workspace))) return; 588 589 for (; a < na && b < nb; ) 590 { 591 if (page_map[a].major == other->page_map[b].major) 592 { 593 if (!passthru_left) 594 { 595 // Move page_map entries that we're keeping from the left side set 596 // to the front of the page_map vector. This isn't necessary if 597 // passthru_left is set since no left side pages will be removed 598 // in that case. 599 if (write_index < a) 600 page_map[write_index] = page_map[a]; 601 write_index++; 602 } 603 604 count++; 605 a++; 606 b++; 607 } 608 else if (page_map[a].major < other->page_map[b].major) 609 { 610 if (passthru_left) 611 count++; 612 a++; 613 } 614 else 615 { 616 if (passthru_right) 617 count++; 618 b++; 619 } 620 } 621 if (passthru_left) 622 count += na - a; 623 if (passthru_right) 624 count += nb - b; 625 626 if (!passthru_left) 627 { 628 na = write_index; 629 next_page = write_index; 630 compact (compact_workspace, write_index); 631 } 632 633 if (!resize (count)) 634 return; 635 636 newCount = count; 637 638 /* Process in-place backward. */ 639 a = na; 640 b = nb; 641 for (; a && b; ) 642 { 643 if (page_map[a - 1].major == other->page_map[b - 1].major) 644 { 645 a--; 646 b--; 647 count--; 648 page_map[count] = page_map[a]; 649 page_at (count).v = op (page_at (a).v, other->page_at (b).v); 650 } 651 else if (page_map[a - 1].major > other->page_map[b - 1].major) 652 { 653 a--; 654 if (passthru_left) 655 { 656 count--; 657 page_map[count] = page_map[a]; 658 } 659 } 660 else 661 { 662 b--; 663 if (passthru_right) 664 { 665 count--; 666 page_map[count].major = other->page_map[b].major; 667 page_map[count].index = next_page++; 668 page_at (count).v = other->page_at (b).v; 669 } 670 } 671 } 672 if (passthru_left) 673 while (a) 674 { 675 a--; 676 count--; 677 page_map[count] = page_map [a]; 678 } 679 if (passthru_right) 680 while (b) 681 { 682 b--; 683 count--; 684 page_map[count].major = other->page_map[b].major; 685 page_map[count].index = next_page++; 686 page_at (count).v = other->page_at (b).v; 687 } 688 assert (!count); 689 if (pages.length > newCount) 690 // This resize() doesn't need to be checked because we can't get here 691 // if the set is currently in_error() and this only resizes downwards 692 // which will always succeed if the set is not in_error(). 693 resize (newCount); 694 } 695 union_hb_set_t696 void union_ (const hb_set_t *other) 697 { 698 process (hb_bitwise_or, other); 699 } intersecthb_set_t700 void intersect (const hb_set_t *other) 701 { 702 process (hb_bitwise_and, other); 703 } subtracthb_set_t704 void subtract (const hb_set_t *other) 705 { 706 process (hb_bitwise_sub, other); 707 } symmetric_differencehb_set_t708 void symmetric_difference (const hb_set_t *other) 709 { 710 process (hb_bitwise_xor, other); 711 } nexthb_set_t712 bool next (hb_codepoint_t *codepoint) const 713 { 714 if (unlikely (*codepoint == INVALID)) { 715 *codepoint = get_min (); 716 return *codepoint != INVALID; 717 } 718 719 page_map_t map = {get_major (*codepoint), 0}; 720 unsigned int i; 721 page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST); 722 if (i < page_map.length && page_map[i].major == map.major) 723 { 724 if (pages[page_map[i].index].next (codepoint)) 725 { 726 *codepoint += page_map[i].major * page_t::PAGE_BITS; 727 return true; 728 } 729 i++; 730 } 731 for (; i < page_map.length; i++) 732 { 733 hb_codepoint_t m = pages[page_map[i].index].get_min (); 734 if (m != INVALID) 735 { 736 *codepoint = page_map[i].major * page_t::PAGE_BITS + m; 737 return true; 738 } 739 } 740 *codepoint = INVALID; 741 return false; 742 } previoushb_set_t743 bool previous (hb_codepoint_t *codepoint) const 744 { 745 if (unlikely (*codepoint == INVALID)) { 746 *codepoint = get_max (); 747 return *codepoint != INVALID; 748 } 749 750 page_map_t map = {get_major (*codepoint), 0}; 751 unsigned int i; 752 page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST); 753 if (i < page_map.length && page_map[i].major == map.major) 754 { 755 if (pages[page_map[i].index].previous (codepoint)) 756 { 757 *codepoint += page_map[i].major * page_t::PAGE_BITS; 758 return true; 759 } 760 } 761 i--; 762 for (; (int) i >= 0; i--) 763 { 764 hb_codepoint_t m = pages[page_map[i].index].get_max (); 765 if (m != INVALID) 766 { 767 *codepoint = page_map[i].major * page_t::PAGE_BITS + m; 768 return true; 769 } 770 } 771 *codepoint = INVALID; 772 return false; 773 } next_rangehb_set_t774 bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const 775 { 776 hb_codepoint_t i; 777 778 i = *last; 779 if (!next (&i)) 780 { 781 *last = *first = INVALID; 782 return false; 783 } 784 785 /* TODO Speed up. */ 786 *last = *first = i; 787 while (next (&i) && i == *last + 1) 788 (*last)++; 789 790 return true; 791 } previous_rangehb_set_t792 bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const 793 { 794 hb_codepoint_t i; 795 796 i = *first; 797 if (!previous (&i)) 798 { 799 *last = *first = INVALID; 800 return false; 801 } 802 803 /* TODO Speed up. */ 804 *last = *first = i; 805 while (previous (&i) && i == *first - 1) 806 (*first)--; 807 808 return true; 809 } 810 get_populationhb_set_t811 unsigned int get_population () const 812 { 813 if (population != UINT_MAX) 814 return population; 815 816 unsigned int pop = 0; 817 unsigned int count = pages.length; 818 for (unsigned int i = 0; i < count; i++) 819 pop += pages[i].get_population (); 820 821 population = pop; 822 return pop; 823 } get_minhb_set_t824 hb_codepoint_t get_min () const 825 { 826 unsigned int count = pages.length; 827 for (unsigned int i = 0; i < count; i++) 828 if (!page_at (i).is_empty ()) 829 return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min (); 830 return INVALID; 831 } get_maxhb_set_t832 hb_codepoint_t get_max () const 833 { 834 unsigned int count = pages.length; 835 for (int i = count - 1; i >= 0; i--) 836 if (!page_at (i).is_empty ()) 837 return page_map[(unsigned) i].major * page_t::PAGE_BITS + page_at (i).get_max (); 838 return INVALID; 839 } 840 841 static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID; 842 843 /* 844 * Iterator implementation. 845 */ 846 struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t> 847 { 848 static constexpr bool is_sorted_iterator = true; iter_thb_set_t::iter_t849 iter_t (const hb_set_t &s_ = Null (hb_set_t), 850 bool init = true) : s (&s_), v (INVALID), l(0) 851 { 852 if (init) 853 { 854 l = s->get_population () + 1; 855 __next__ (); 856 } 857 } 858 859 typedef hb_codepoint_t __item_t__; __item__hb_set_t::iter_t860 hb_codepoint_t __item__ () const { return v; } __more__hb_set_t::iter_t861 bool __more__ () const { return v != INVALID; } __next__hb_set_t::iter_t862 void __next__ () { s->next (&v); if (l) l--; } __prev__hb_set_t::iter_t863 void __prev__ () { s->previous (&v); } __len__hb_set_t::iter_t864 unsigned __len__ () const { return l; } endhb_set_t::iter_t865 iter_t end () const { return iter_t (*s, false); } operator !=hb_set_t::iter_t866 bool operator != (const iter_t& o) const 867 { return s != o.s || v != o.v; } 868 869 protected: 870 const hb_set_t *s; 871 hb_codepoint_t v; 872 unsigned l; 873 }; iterhb_set_t874 iter_t iter () const { return iter_t (*this); } operator iter_thb_set_t875 operator iter_t () const { return iter (); } 876 877 protected: 878 page_for_inserthb_set_t879 page_t *page_for_insert (hb_codepoint_t g) 880 { 881 page_map_t map = {get_major (g), pages.length}; 882 unsigned int i; 883 if (!page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST)) 884 { 885 if (!resize (pages.length + 1)) 886 return nullptr; 887 888 pages[map.index].init0 (); 889 memmove (page_map + i + 1, 890 page_map + i, 891 (page_map.length - 1 - i) * page_map.item_size); 892 page_map[i] = map; 893 } 894 return &pages[page_map[i].index]; 895 } page_forhb_set_t896 page_t *page_for (hb_codepoint_t g) 897 { 898 page_map_t key = {get_major (g)}; 899 const page_map_t *found = page_map.bsearch (key); 900 if (found) 901 return &pages[found->index]; 902 return nullptr; 903 } page_forhb_set_t904 const page_t *page_for (hb_codepoint_t g) const 905 { 906 page_map_t key = {get_major (g)}; 907 const page_map_t *found = page_map.bsearch (key); 908 if (found) 909 return &pages[found->index]; 910 return nullptr; 911 } page_athb_set_t912 page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } page_athb_set_t913 const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } get_majorhb_set_t914 unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; } major_starthb_set_t915 hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; } 916 }; 917 918 919 #endif /* HB_SET_HH */ 920