* Copyright © 2012,2017  Google, Inc.

  struct page_map_t

  {

    inline int cmp (const page_map_t *o) const { return (int) o->major - (int) major; }

    uint32_t major;

    uint32_t index;

  };

  struct page_t

  {

    inline void init (void) {

      memset (&v, 0, sizeof (v));

    }

    inline unsigned int len (void) const

    { return ARRAY_LENGTH_CONST (v); }

    inline bool is_empty (void) const

    {

      for (unsigned int i = 0; i < len (); i++)

        if (v[i])

          return false;

      return true;

    }

    inline void add (hb_codepoint_t g) { elt (g) |= mask (g); }

    inline void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }

    inline bool has (hb_codepoint_t g) const { return !!(elt (g) & mask (g)); }

    inline bool is_equal (const page_t *other) const

    {

      return 0 == memcmp (&v, &other->v, sizeof (v));

    }

    inline unsigned int get_population (void) const

    {

      unsigned int pop = 0;

      for (unsigned int i = 0; i < len (); i++)

        pop += _hb_popcount (v[i]);

      return pop;

    }

    inline bool next (hb_codepoint_t *codepoint) const

    {

      unsigned int m = (*codepoint + 1) & MASK;

      if (!m)

      {

        *codepoint = INVALID;

        return false;

      }

      unsigned int i = m / ELT_BITS;

      unsigned int j = m & ELT_MASK;

      for (; j < ELT_BITS; j++)

        if (v[i] & (elt_t (1) << j))

          goto found;

      for (i++; i < len (); i++)

        if (v[i])

          for (j = 0; j < ELT_BITS; j++)

            if (v[i] & (elt_t (1) << j))

              goto found;

      *codepoint = INVALID;

      return false;

    found:

      *codepoint = i * ELT_BITS + j;

      return true;

    }

    inline hb_codepoint_t get_min (void) const

    {

      for (unsigned int i = 0; i < len (); i++)

        if (v[i])

        {

          elt_t e = v[i];

          for (unsigned int j = 0; j < ELT_BITS; j++)

            if (e & (elt_t (1) << j))

              return i * ELT_BITS + j;

        }

      return INVALID;

    }

    inline hb_codepoint_t get_max (void) const

    {

      for (int i = len () - 1; i >= 0; i--)

        if (v[i])

        {

          elt_t e = v[i];

          for (int j = ELT_BITS - 1; j >= 0; j--)

            if (e & (elt_t (1) << j))

              return i * ELT_BITS + j;

        }

      return 0;

    }

    static const unsigned int PAGE_BITS = 512; /* Use to tune. */

    static_assert ((PAGE_BITS & ((PAGE_BITS) - 1)) == 0, "");

    typedef uint64_t elt_t;

#if 0 && HAVE_VECTOR_SIZE

    /* The vectorized version does not work with clang as non-const

     * elt() errs "non-const reference cannot bind to vector element". */

    typedef elt_t vector_t __attribute__((vector_size (PAGE_BITS / 8)));

#else

    typedef hb_vector_size_t<elt_t, PAGE_BITS / 8> vector_t;

#endif

    vector_t v;

    static const unsigned int ELT_BITS = sizeof (elt_t) * 8;

    static const unsigned int ELT_MASK = ELT_BITS - 1;

    static const unsigned int BITS = sizeof (vector_t) * 8;

    static const unsigned int MASK = BITS - 1;

    static_assert (PAGE_BITS == BITS, "");

    elt_t &elt (hb_codepoint_t g) { return v[(g & MASK) / ELT_BITS]; }

    elt_t const &elt (hb_codepoint_t g) const { return v[(g & MASK) / ELT_BITS]; }

    elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & ELT_MASK); }

  };

  static_assert (page_t::PAGE_BITS == sizeof (page_t) * 8, "");

  hb_prealloced_array_t<page_map_t, 8> page_map;

  hb_prealloced_array_t<page_t, 8> pages;

  inline bool resize (unsigned int count)

  {

    if (unlikely (in_error)) return false;

    if (!pages.resize (count) || !page_map.resize (count))

    {

      pages.resize (page_map.len);

      in_error = true;

      return false;

    }

    return true;

    page_map.resize (0);

    pages.resize (0);

    unsigned int count = pages.len;

    for (unsigned int i = 0; i < count; i++)

      if (!pages[i].is_empty ())

    page_t *page = page_for_insert (g);

    if (!page)

      return;

    page->add (g);

    page_t *p = page_for (g);

    if (!p)

      return;

    p->del (g);

    const page_t *p = page_for (g);

    if (!p)

      return false;

    return p->has (g);

    hb_codepoint_t c = first - 1;

    return next (&c) && c <= last;

    unsigned int count = other->pages.len;

    if (!resize (count))

      return;

    memcpy (pages.array, other->pages.array, count * sizeof (pages.array[0]));

    memcpy (page_map.array, other->page_map.array, count * sizeof (page_map.array[0]));

  }

  inline bool is_equal (const hb_set_t *other) const

  {

    unsigned int na = pages.len;

    unsigned int nb = other->pages.len;

    unsigned int a = 0, b = 0;

    for (; a < na && b < nb; )

    {

      if (page_at (a).is_empty ()) { a++; continue; }

      if (other->page_at (b).is_empty ()) { b++; continue; }

      if (page_map[a].major != other->page_map[b].major ||

          !page_at (a).is_equal (&other->page_at (b)))

        return false;

      a++;

      b++;

    }

    for (; a < na; a++)

      if (!page_at (a).is_empty ()) { return false; }

    for (; b < nb; b++)

      if (!other->page_at (b).is_empty ()) { return false; }

    return true;

  template <class Op>

  inline void process (const hb_set_t *other)

  {

    if (unlikely (in_error)) return;

    unsigned int na = pages.len;

    unsigned int nb = other->pages.len;

    unsigned int count = 0;

    unsigned int a = 0, b = 0;

    for (; a < na && b < nb; )

    {

      if (page_map[a].major == other->page_map[b].major)

      {

        count++;

        a++;

        b++;

      }

      else if (page_map[a].major < other->page_map[b].major)

      {

        if (Op::passthru_left)

          count++;

        a++;

      }

      else

      {

        if (Op::passthru_right)

          count++;

        b++;

      }

    }

    if (Op::passthru_left)

      count += na - a;

    if (Op::passthru_right)

      count += nb - b;

    if (!resize (count))

      return;

    /* Process in-place backward. */

    a = na;

    b = nb;

    for (; a && b; )

    {

      if (page_map[a - 1].major == other->page_map[b - 1].major)

      {

        a--;

        b--;

        Op::process (page_at (--count).v, page_at (a).v, other->page_at (b).v);

      }

      else if (page_map[a - 1].major > other->page_map[b - 1].major)

      {

        a--;

        if (Op::passthru_left)

          page_at (--count).v = page_at (a).v;

      }

      else

      {

        b--;

        if (Op::passthru_right)

          page_at (--count).v = other->page_at (b).v;

      }

    }

    if (Op::passthru_left)

      while (a)

        page_at (--count).v = page_at (--a).v;

    if (Op::passthru_right)

      while (b)

        page_at (--count).v = other->page_at (--b).v;

    assert (!count);

  }

    process<HbOpOr> (other);

    process<HbOpAnd> (other);

    process<HbOpMinus> (other);

    process<HbOpXor> (other);

      *codepoint = get_min ();

      return *codepoint != INVALID;

    }

    page_map_t map = {get_major (*codepoint), 0};

    unsigned int i;

    page_map.bfind (&map, &i);

    if (i < page_map.len)

    {

      if (pages[page_map[i].index].next (codepoint))

      {

        *codepoint += page_map[i].major * page_t::PAGE_BITS;

      }

      i++;

    }

    for (; i < page_map.len; i++)

    {

      hb_codepoint_t m = pages[page_map[i].index].get_min ();

      if (m != INVALID)

      {

        *codepoint = page_map[i].major * page_t::PAGE_BITS + m;

        return true;

    unsigned int pop = 0;

    unsigned int count = pages.len;

    for (unsigned int i = 0; i < count; i++)

      pop += pages[i].get_population ();

    return pop;

    unsigned int count = pages.len;

    for (unsigned int i = 0; i < count; i++)

      if (!page_at (i).is_empty ())

        return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_min ();

    unsigned int count = pages.len;

    for (int i = count - 1; i >= 0; i++)

      if (!page_at (i).is_empty ())

        return page_map[i].major * page_t::PAGE_BITS + page_at (i).get_max ();

  page_t *page_for_insert (hb_codepoint_t g)

    page_map_t map = {get_major (g), pages.len};

    unsigned int i;

    if (!page_map.bfind (&map, &i))

    {

      if (!resize (pages.len + 1))

        return nullptr;

      pages[map.index].init ();

      memmove (&page_map[i + 1], &page_map[i], (page_map.len - 1 - i) * sizeof (page_map[0]));

      page_map[i] = map;

    return &pages[page_map[i].index];

  page_t *page_for (hb_codepoint_t g)

    page_map_t key = {get_major (g)};

    const page_map_t *found = page_map.bsearch (&key);

    if (found)

      return &pages[found->index];

    return nullptr;

  const page_t *page_for (hb_codepoint_t g) const

    page_map_t key = {get_major (g)};

    const page_map_t *found = page_map.bsearch (&key);

    if (found)

      return &pages[found->index];

    return nullptr;

  page_t &page_at (unsigned int i) { return pages[page_map[i].index]; }

  const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; }

  unsigned int get_major (hb_codepoint_t g) const { return g / page_t::PAGE_BITS; }