src/hb-set.hh

   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);
  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     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
 109     bool is_equal (const page_t *other) const
 110     {
 111       return 0 == hb_memcmp (&v, &other->v, sizeof (v));
 112     }
 113
 114     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
 122     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     }
 144     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     }
 175     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     }
 182     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
 194     static unsigned int elt_get_min (const elt_t &elt) { return hb_ctz (elt); }
 195     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
 205     elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }
 206     elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }
 207     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
 219   void init_shallow ()
 220   {
 221     successful = true;
 222     population = 0;
 223     page_map.init ();
 224     pages.init ();
 225   }
 226   void init ()
 227   {
 228     hb_object_init (this);
 229     init_shallow ();
 230   }
 231   void fini_shallow ()
 232   {
 233     population = 0;
 234     page_map.fini ();
 235     pages.fini ();
 236   }
 237   void fini ()
 238   {
 239     hb_object_fini (this);
 240     fini_shallow ();
 241   }
 242
 243   bool in_error () const { return !successful; }
 244
 245   bool resize (unsigned int count)
 246   {
 247     if (unlikely (!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
 257   void reset ()
 258   {
 259     if (unlikely (hb_object_is_immutable (this)))
 260       return;
 261     clear ();
 262     successful = true;
 263   }
 264
 265   void clear ()
 266   {
 267     if (unlikely (hb_object_is_immutable (this)))
 268       return;
 269     population = 0;
 270     page_map.resize (0);
 271     pages.resize (0);
 272   }
 273   bool is_empty () const
 274   {
 275     unsigned int count = pages.length;
 276     for (unsigned int i = 0; i < count; i++)
 277       if (!pages[i].is_empty ())
 278         return false;
 279     return true;
 280   }
 281
 282   void dirty () { population = UINT_MAX; }
 283
 284   void add (hb_codepoint_t g)
 285   {
 286     if (unlikely (!successful)) return;
 287     if (unlikely (g == INVALID)) return;
 288     dirty ();
 289     page_t *page = page_for_insert (g); if (unlikely (!page)) return;
 290     page->add (g);
 291   }
 292   bool add_range (hb_codepoint_t a, hb_codepoint_t b)
 293   {
 294     if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
 295     if (unlikely (a > b || a == INVALID || b == INVALID)) return false;
 296     dirty ();
 297     unsigned int ma = get_major (a);
 298     unsigned int mb = get_major (b);
 299     if (ma == mb)
 300     {
 301       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
 302       page->add_range (a, b);
 303     }
 304     else
 305     {
 306       page_t *page = page_for_insert (a); if (unlikely (!page)) return false;
 307       page->add_range (a, major_start (ma + 1) - 1);
 308
 309       for (unsigned int m = ma + 1; m < mb; m++)
 310       {
 311         page = page_for_insert (major_start (m)); if (unlikely (!page)) return false;
 312         page->init1 ();
 313       }
 314
 315       page = page_for_insert (b); if (unlikely (!page)) return false;
 316       page->add_range (major_start (mb), b);
 317     }
 318     return true;
 319   }
 320
 321   template <typename T>
 322   void add_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 323   {
 324     if (unlikely (!successful)) return;
 325     if (!count) return;
 326     dirty ();
 327     hb_codepoint_t g = *array;
 328     while (count)
 329     {
 330       unsigned int m = get_major (g);
 331       page_t *page = page_for_insert (g); if (unlikely (!page)) return;
 332       unsigned int start = major_start (m);
 333       unsigned int end = major_start (m + 1);
 334       do
 335       {
 336         page->add (g);
 337
 338         array = &StructAtOffsetUnaligned<T> (array, stride);
 339         count--;
 340       }
 341       while (count && (g = *array, start <= g && g < end));
 342     }
 343   }
 344
 345   /* Might return false if array looks unsorted.
 346    * Used for faster rejection of corrupt data. */
 347   template <typename T>
 348   bool add_sorted_array (const T *array, unsigned int count, unsigned int stride=sizeof(T))
 349   {
 350     if (unlikely (!successful)) return true; /* https://github.com/harfbuzz/harfbuzz/issues/657 */
 351     if (!count) return true;
 352     dirty ();
 353     hb_codepoint_t g = *array;
 354     hb_codepoint_t last_g = g;
 355     while (count)
 356     {
 357       unsigned int m = get_major (g);
 358       page_t *page = page_for_insert (g); if (unlikely (!page)) return false;
 359       unsigned int end = major_start (m + 1);
 360       do
 361       {
 362         /* If we try harder we can change the following comparison to <=;
 363          * Not sure if it's worth it. */
 364         if (g < last_g) return false;
 365         last_g = g;
 366         page->add (g);
 367
 368         array = (const T *) ((const char *) array + stride);
 369         count--;
 370       }
 371       while (count && (g = *array, g < end));
 372     }
 373     return true;
 374   }
 375
 376   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:
 388   void del_pages (int ds, int de)
 389   {
 390     if (ds <= de)
 391     {
 392       unsigned int write_index = 0;
 393       for (unsigned int i = 0; i < page_map.length; i++)
 394       {
 395         int m = (int) page_map[i].major;
 396         if (m < ds || de < m)
 397           page_map[write_index++] = page_map[i];
 398       }
 399       compact (write_index);
 400       resize (write_index);
 401     }
 402   }
 403
 404   public:
 405   void del_range (hb_codepoint_t a, hb_codepoint_t b)
 406   {
 407     /* TODO perform op even if !successful. */
 408     if (unlikely (!successful)) return;
 409     if (unlikely (a > b || a == INVALID || b == INVALID)) return;
 410     dirty ();
 411     unsigned int ma = get_major (a);
 412     unsigned int mb = get_major (b);
 413     /* Delete pages from ds through de if ds <= de. */
 414     int ds = (a == major_start (ma))? (int) ma: (int) (ma + 1);
 415     int de = (b + 1 == major_start (mb + 1))? (int) mb: ((int) mb - 1);
 416     if (ds > de || (int) ma < ds)
 417     {
 418       page_t *page = page_for (a);
 419       if (page)
 420       {
 421         if (ma == mb)
 422           page->del_range (a, b);
 423         else
 424           page->del_range (a, major_start (ma + 1) - 1);
 425       }
 426     }
 427     if (de < (int) mb && ma != mb)
 428     {
 429       page_t *page = page_for (b);
 430       if (page)
 431         page->del_range (major_start (mb), b);
 432     }
 433     del_pages (ds, de);
 434   }
 435
 436   bool get (hb_codepoint_t g) const
 437   {
 438     const page_t *page = page_for (g);
 439     if (!page)
 440       return false;
 441     return page->get (g);
 442   }
 443
 444   /* Has interface. */
 445   static constexpr bool SENTINEL = false;
 446   typedef bool value_t;
 447   value_t operator [] (hb_codepoint_t k) const { return get (k); }
 448   bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; }
 449   /* Predicate. */
 450   bool operator () (hb_codepoint_t k) const { return has (k); }
 451
 452   /* Sink interface. */
 453   hb_set_t& operator << (hb_codepoint_t v)
 454   { add (v); return *this; }
 455   hb_set_t& operator << (const hb_pair_t<hb_codepoint_t, hb_codepoint_t>& range)
 456   { add_range (range.first, range.second); return *this; }
 457
 458   bool intersects (hb_codepoint_t first, hb_codepoint_t last) const
 459   {
 460     hb_codepoint_t c = first - 1;
 461     return next (&c) && c <= last;
 462   }
 463   void set (const hb_set_t *other)
 464   {
 465     if (unlikely (!successful)) return;
 466     unsigned int count = other->pages.length;
 467     if (!resize (count))
 468       return;
 469     population = other->population;
 470     memcpy ((void *) pages, (const void *) other->pages, count * pages.item_size);
 471     memcpy ((void *) page_map, (const void *) other->page_map, count * page_map.item_size);
 472   }
 473
 474   bool is_equal (const hb_set_t *other) const
 475   {
 476     if (get_population () != other->get_population ())
 477       return false;
 478
 479     unsigned int na = pages.length;
 480     unsigned int nb = other->pages.length;
 481
 482     unsigned int a = 0, b = 0;
 483     for (; a < na && b < nb; )
 484     {
 485       if (page_at (a).is_empty ()) { a++; continue; }
 486       if (other->page_at (b).is_empty ()) { b++; continue; }
 487       if (page_map[a].major != other->page_map[b].major ||
 488           !page_at (a).is_equal (&other->page_at (b)))
 489         return false;
 490       a++;
 491       b++;
 492     }
 493     for (; a < na; a++)
 494       if (!page_at (a).is_empty ()) { return false; }
 495     for (; b < nb; b++)
 496       if (!other->page_at (b).is_empty ()) { return false; }
 497
 498     return true;
 499   }
 500
 501   bool is_subset (const hb_set_t *larger_set) const
 502   {
 503     if (get_population () > larger_set->get_population ())
 504       return false;
 505
 506     /* TODO Optimize to use pages. */
 507     hb_codepoint_t c = INVALID;
 508     while (next (&c))
 509       if (!larger_set->has (c))
 510         return false;
 511
 512     return true;
 513   }
 514
 515   void compact (unsigned int length)
 516   {
 517     hb_vector_t<uint32_t> old_index_to_page_map_index;
 518     old_index_to_page_map_index.resize(pages.length);
 519     for (uint32_t i = 0; i < old_index_to_page_map_index.length; i++)
 520       old_index_to_page_map_index[i] = 0xFFFFFFFF;
 521
 522     for (uint32_t i = 0; i < length; i++)
 523       old_index_to_page_map_index[page_map[i].index] =  i;
 524
 525     compact_pages (old_index_to_page_map_index);
 526   }
 527
 528   void compact_pages (const hb_vector_t<uint32_t>& old_index_to_page_map_index)
 529   {
 530     unsigned int write_index = 0;
 531     for (unsigned int i = 0; i < pages.length; i++)
 532     {
 533       if (old_index_to_page_map_index[i] == 0xFFFFFFFF) continue;
 534
 535       if (write_index < i)
 536         pages[write_index] = pages[i];
 537
 538       page_map[old_index_to_page_map_index[i]].index = write_index;
 539       write_index++;
 540     }
 541   }
 542
 543   template <typename Op>
 544   void process (const Op& op, const hb_set_t *other)
 545   {
 546     if (unlikely (!successful)) return;
 547
 548     dirty ();
 549
 550     unsigned int na = pages.length;
 551     unsigned int nb = other->pages.length;
 552     unsigned int next_page = na;
 553
 554     unsigned int count = 0, newCount = 0;
 555     unsigned int a = 0, b = 0;
 556     unsigned int write_index = 0;
 557     for (; a < na && b < nb; )
 558     {
 559       if (page_map[a].major == other->page_map[b].major)
 560       {
 561         if (!Op::passthru_left)
 562         {
 563           // Move page_map entries that we're keeping from the left side set
 564           // to the front of the page_map vector. This isn't necessary if
 565           // passthru_left is set since no left side pages will be removed
 566           // in that case.
 567           if (write_index < a)
 568             page_map[write_index] = page_map[a];
 569           write_index++;
 570         }
 571
 572         count++;
 573         a++;
 574         b++;
 575       }
 576       else if (page_map[a].major < other->page_map[b].major)
 577       {
 578         if (Op::passthru_left)
 579           count++;
 580         a++;
 581       }
 582       else
 583       {
 584         if (Op::passthru_right)
 585           count++;
 586         b++;
 587       }
 588     }
 589     if (Op::passthru_left)
 590       count += na - a;
 591     if (Op::passthru_right)
 592       count += nb - b;
 593
 594     if (!Op::passthru_left)
 595     {
 596       na  = write_index;
 597       next_page = write_index;
 598       compact (write_index);
 599     }
 600
 601     if (!resize (count))
 602       return;
 603
 604     newCount = count;
 605
 606     /* Process in-place backward. */
 607     a = na;
 608     b = nb;
 609     for (; a && b; )
 610     {
 611       if (page_map[a - 1].major == other->page_map[b - 1].major)
 612       {
 613         a--;
 614         b--;
 615         count--;
 616         page_map[count] = page_map[a];
 617         page_at (count).v = op (page_at (a).v, other->page_at (b).v);
 618       }
 619       else if (page_map[a - 1].major > other->page_map[b - 1].major)
 620       {
 621         a--;
 622         if (Op::passthru_left)
 623         {
 624           count--;
 625           page_map[count] = page_map[a];
 626         }
 627       }
 628       else
 629       {
 630         b--;
 631         if (Op::passthru_right)
 632         {
 633           count--;
 634           page_map[count].major = other->page_map[b].major;
 635           page_map[count].index = next_page++;
 636           page_at (count).v = other->page_at (b).v;
 637         }
 638       }
 639     }
 640     if (Op::passthru_left)
 641       while (a)
 642       {
 643         a--;
 644         count--;
 645         page_map[count] = page_map [a];
 646       }
 647     if (Op::passthru_right)
 648       while (b)
 649       {
 650         b--;
 651         count--;
 652         page_map[count].major = other->page_map[b].major;
 653         page_map[count].index = next_page++;
 654         page_at (count).v = other->page_at (b).v;
 655       }
 656     assert (!count);
 657     if (pages.length > newCount)
 658       resize (newCount);
 659   }
 660
 661   void union_ (const hb_set_t *other)
 662   {
 663     process (hb_bitwise_or, other);
 664   }
 665   void intersect (const hb_set_t *other)
 666   {
 667     process (hb_bitwise_and, other);
 668   }
 669   void subtract (const hb_set_t *other)
 670   {
 671     process (hb_bitwise_sub, other);
 672   }
 673   void symmetric_difference (const hb_set_t *other)
 674   {
 675     process (hb_bitwise_xor, other);
 676   }
 677   bool next (hb_codepoint_t *codepoint) const
 678   {
 679     if (unlikely (*codepoint == INVALID)) {
 680       *codepoint = get_min ();
 681       return *codepoint != INVALID;
 682     }
 683
 684     page_map_t map = {get_major (*codepoint), 0};
 685     unsigned int i;
 686     page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
 687     if (i < page_map.length && page_map[i].major == map.major)
 688     {
 689       if (pages[page_map[i].index].next (codepoint))
 690       {
 691         *codepoint += page_map[i].major * page_t::PAGE_BITS;
 692         return true;
 693       }
 694       i++;
 695     }
 696     for (; i < page_map.length; i++)
 697     {
 698       hb_codepoint_t m = pages[page_map[i].index].get_min ();
 699       if (m != INVALID)
 700       {
 701         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
 702         return true;
 703       }
 704     }
 705     *codepoint = INVALID;
 706     return false;
 707   }
 708   bool previous (hb_codepoint_t *codepoint) const
 709   {
 710     if (unlikely (*codepoint == INVALID)) {
 711       *codepoint = get_max ();
 712       return *codepoint != INVALID;
 713     }
 714
 715     page_map_t map = {get_major (*codepoint), 0};
 716     unsigned int i;
 717     page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST);
 718     if (i < page_map.length && page_map[i].major == map.major)
 719     {
 720       if (pages[page_map[i].index].previous (codepoint))
 721       {
 722         *codepoint += page_map[i].major * page_t::PAGE_BITS;
 723         return true;
 724       }
 725     }
 726     i--;
 727     for (; (int) i >= 0; i--)
 728     {
 729       hb_codepoint_t m = pages[page_map[i].index].get_max ();
 730       if (m != INVALID)
 731       {
 732         *codepoint = page_map[i].major * page_t::PAGE_BITS + m;
 733         return true;
 734       }
 735     }
 736     *codepoint = INVALID;
 737     return false;
 738   }
 739   bool next_range (hb_codepoint_t *first, hb_codepoint_t *last) const
 740   {
 741     hb_codepoint_t i;
 742
 743     i = *last;
 744     if (!next (&i))
 745     {
 746       *last = *first = INVALID;
 747       return false;
 748     }
 749
 750     /* TODO Speed up. */
 751     *last = *first = i;
 752     while (next (&i) && i == *last + 1)
 753       (*last)++;
 754
 755     return true;
 756   }
 757   bool previous_range (hb_codepoint_t *first, hb_codepoint_t *last) const
 758   {
 759     hb_codepoint_t i;
 760
 761     i = *first;
 762     if (!previous (&i))
 763     {
 764       *last = *first = INVALID;
 765       return false;
 766     }
 767
 768     /* TODO Speed up. */
 769     *last = *first = i;
 770     while (previous (&i) && i == *first - 1)
 771       (*first)--;
 772
 773     return true;
 774   }
 775
 776   unsigned int get_population () const
 777   {
 778     if (population != UINT_MAX)
 779       return population;
 780
 781     unsigned int pop = 0;
 782     unsigned int count = pages.length;
 783     for (unsigned int i = 0; i < count; i++)
 784       pop += pages[i].get_population ();
 785
 786     population = pop;
 787     return pop;
 788   }
 789   hb_codepoint_t get_min () const
 790   {
 791     unsigned int count = pages.length;
 792     for (unsigned int i = 0; i < count; i++)
 793       if (!page_at (i).is_empty ())
 794         return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();
 795     return INVALID;
 796   }
 797   hb_codepoint_t get_max () const
 798   {
 799     unsigned int count = pages.length;
 800     for (int i = count - 1; i >= 0; i++)
 801       if (!page_at (i).is_empty ())
 802         return page_map[(unsigned) i].major * page_t::PAGE_BITS + page_at (i).get_max ();
 803     return INVALID;
 804   }
 805
 806   static constexpr hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
 807
 808   /*
 809    * Iterator implementation.
 810    */
 811   struct iter_t : hb_iter_with_fallback_t<iter_t, hb_codepoint_t>
 812   {
 813     static constexpr bool is_sorted_iterator = true;
 814     iter_t (const hb_set_t &s_ = Null (hb_set_t),
 815             bool init = true) : s (&s_), v (INVALID), l(0)
 816     {
 817       if (init)
 818       {
 819         l = s->get_population () + 1;
 820         __next__ ();
 821       }
 822     }
 823
 824     typedef hb_codepoint_t __item_t__;
 825     hb_codepoint_t __item__ () const { return v; }
 826     bool __more__ () const { return v != INVALID; }
 827     void __next__ () { s->next (&v); if (l) l--; }
 828     void __prev__ () { s->previous (&v); }
 829     unsigned __len__ () const { return l; }
 830     iter_t end () const { return iter_t (*s, false); }
 831     bool operator != (const iter_t& o) const
 832     { return s != o.s || v != o.v; }
 833
 834     protected:
 835     const hb_set_t *s;
 836     hb_codepoint_t v;
 837     unsigned l;
 838   };
 839   iter_t iter () const { return iter_t (*this); }
 840   operator iter_t () const { return iter (); }
 841
 842   protected:
 843
 844   page_t *page_for_insert (hb_codepoint_t g)
 845   {
 846     page_map_t map = {get_major (g), pages.length};
 847     unsigned int i;
 848     if (!page_map.bfind (map, &i, HB_BFIND_NOT_FOUND_STORE_CLOSEST))
 849     {
 850       if (!resize (pages.length + 1))
 851         return nullptr;
 852
 853       pages[map.index].init0 ();
 854       memmove (page_map + i + 1,
 855                page_map + i,
 856                (page_map.length - 1 - i) * page_map.item_size);
 857       page_map[i] = map;
 858     }
 859     return &pages[page_map[i].index];
 860   }
 861   page_t *page_for (hb_codepoint_t g)
 862   {
 863     page_map_t key = {get_major (g)};
 864     const page_map_t *found = page_map.bsearch (key);
 865     if (found)
 866       return &pages[found->index];
 867     return nullptr;
 868   }
 869   const page_t *page_for (hb_codepoint_t g) const
 870   {
 871     page_map_t key = {get_major (g)};
 872     const page_map_t *found = page_map.bsearch (key);
 873     if (found)
 874       return &pages[found->index];
 875     return nullptr;
 876   }
 877   page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }
 878   const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }
 879   unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }
 880   hb_codepoint_t major_start (unsigned int major) const { return major * page_t::PAGE_BITS; }
 881 };
 882
 883
 884 #endif /* HB_SET_HH */